On Distributed Online Convex Optimization with Sublinear Dynamic Regret and Fit
On Distributed Online Convex Optimization with Sublinear Dynamic Regret and Fit
复制标题
DOI：
10.1109/ieeeconf53345.2021.9723285
复制
发表时间：
2020-01
期刊：
影响因子：
--
通讯作者：
Pranay Sharma;Prashant Khanduri;Lixin Shen;Donald J. Bucci;P. Varshney
中科院分区：
文献类型：
--
作者：
Pranay Sharma;Prashant Khanduri;Lixin Shen;Donald J. Bucci;P. Varshney
在这项工作中，我们考虑具有时变（潜在对抗性）约束的分布式在线凸优化问题。一组节点共同致力于最小化全局目标函数，该函数是局部凸函数的总和。每次采取行动后，目标函数和约束函数都会在本地节点上显示。当然，约束不可能立即得到满足。因此，我们重新表述问题以长期满足这些约束。为此，我们提出了一种基于分布式原始-对偶镜像下降的算法，其中原始和对偶更新在所有节点本地进行。接下来，本地节点通过与直接邻居的通信来共享和混合原始变量。为了量化所提出算法的性能，我们利用了具有挑战性但更现实的动态后悔和拟合指标。动态遗憾衡量算法与最佳动态策略相比所产生的累积损失，而拟合则衡量长期累积约束违规情况。在不假设限制性斯莱特条件的情况下，我们表明所提出的算法在温和、常用的假设下实现了亚线性后悔和拟合。
In this work, we consider a distributed online convex optimization problem, with time-varying (potentially adversarial) constraints. A set of nodes, jointly aim to minimize a global objective function, which is the sum of local convex functions. The objective and constraint functions are revealed locally to the nodes, at each time, after taking an action. Naturally, the constraints cannot be instantaneously satisfied. Therefore, we reformulate the problem to satisfy these constraints in the long term. To this end, we propose a distributed primal-dual mirror descent-based algorithm, in which the primal and dual updates are carried out locally at all the nodes. This is followed by sharing and mixing of the primal variables by the local nodes via communication with the immediate neighbors. To quantify the performance of the proposed algorithm, we utilize the challenging, but more realistic metrics of dynamic regret and fit. Dynamic regret measures the cumulative loss incurred by the algorithm compared to the best dynamic strategy, while fit measures the long term cumulative constraint violations. Without assuming the restrictive Slater’s conditions, we show that the proposed algorithm achieves sublinear regret and fit under mild, commonly used assumptions.