A Distributed Online Convex Optimization Algorithm with Improved Dynamic Regret
This work addresses the problem of improving regret bounds for distributed optimization in networks, but it is incremental as it builds on existing methods with a specific convexity assumption.
The paper tackles distributed online convex optimization by proposing a gradient tracking algorithm that removes the explicit dependence on the number of time steps in dynamic regret bounds, assuming strong convexity, and verifies this with numerical experiments.
In this paper, we consider the problem of distributed online convex optimization, where a network of local agents aim to jointly optimize a convex function over a period of multiple time steps. The agents do not have any information about the future. Existing algorithms have established dynamic regret bounds that have explicit dependence on the number of time steps. In this work, we show that we can remove this dependence assuming that the local objective functions are strongly convex. More precisely, we propose a gradient tracking algorithm where agents jointly communicate and descend based on corrected gradient steps. We verify our theoretical results through numerical experiments.