提出一种新型分布式在线优化算法,用单点残差反馈实现低后悔率。
Distributed Online Bandit Nonconvex Optimization with One-Point Residual Feedback via Dynamic Regret
- 利用两点残差估计梯度,提升单点反馈性能
- 期望动态后悔界与双点反馈算法相当,且每轮采样复杂度为O(1)
- 适用于非凸损失、时变图结构的分布式在线学习场景
本文研究在时变有向图上具有非凸损失函数的分布式在线贝叶斯优化问题。该问题可视为一组在线玩家与对手之间的重复博弈:每轮中,每个玩家从约束集选择决策,对手则分配任意(可能非凸)的损失函数;仅当前轮的损失值被私密地告知玩家,而损失函数本身或梯度等信息不可得。玩家目标是最小化一系列全局损失函数(即局部损失之和)。传统多点反馈算法不适用于在线场景(因损失数据非先验),而单点反馈算法后悔率较差。为此,我们提出一种新颖的一点残差反馈分布式在线算法,通过两点残差估计梯度,在保持每轮采样复杂度为$/mathcal{O}(1)$的前提下有效降低后悔界。采用动态后悔作为评估指标,通过合理选取步长与平滑参数,证明当目标函数序列偏差及最优路径长度以次线性增长时,该算法的期望动态后悔与使用两点反馈的现有算法相当。数值模拟验证了算法的有效性。
原文摘要 · Abstract (English)
This paper considers the distributed online bandit optimization problem with nonconvex loss functions over a time-varying digraph. This problem can be viewed as a repeated game between a group of online players and an adversary. At each round, each player selects a decision from the constraint set, and then the adversary assigns an arbitrary, possibly nonconvex, loss function to this player. Only the loss value at the current round, rather than the entire loss function or any other information (e.g. gradient), is privately revealed to the player. Players aim to minimize a sequence of global loss functions, which are the sum of local losses. We observe that traditional multi-point bandit algorithms are unsuitable for online optimization, where the data for the loss function are not all a priori, while the one-point bandit algorithms suffer from poor regret guarantees. To address these issues, we propose a novel one-point residual feedback distributed online algorithm. This algorithm estimates the gradient using residuals from two points, effectively reducing the regret bound while maintaining $\mathcal{O}(1)$ sampling complexity per iteration. We employ a rigorous metric, dynamic regret, to evaluate the algorithm's performance. By appropriately selecting the step size and smoothing parameters, we demonstrate that the expected dynamic regret of our algorithm is comparable to existing algorithms that use two-point feedback, provided the deviation in the objective function sequence and the path length of the minimization grows sublinearly. Finally, we validate the effectiveness of the proposed algorithm through numerical simulations.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。