# On the Sublinear Regret of Distributed Primal-Dual Algorithms for Online Constrained Optimization

arXiv: https://arxiv.org/abs/1705.11128 · HTML: https://mlsanity.com/paper/1705.11128/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 May 2017.

## Built on by (most cited first, 2 of 2)

- [Distributed Online Non-convex Optimization with Composite Regret](https://mlsanity.com/paper/2209.10105/) (2022)
- [A Survey on Distributed Online Optimization and Game](https://mlsanity.com/paper/2205.00473/) (2022)

## Abstract (arXiv)

This paper introduces consensus-based primal-dual methods for distributed online optimization where the time-varying system objective function ft(x) is given as the sum of local agents' objective functions, i.e., ft(x) = sumi fi,t(xi), and the system constraint function g(x) is given as the sum of local agents' constraint functions, i.e., g(x) = sumi gi (xi) preceq 0. At each stage, each agent commits to an adaptive decision pertaining only to the past and locally available information, and incurs a new cost function reflecting the change in the environment. Our algorithm uses weighted averaging of the iterates for each agent to keep local estimates of the global constraints and dual variables. We show that the algorithm achieves a regret of order O(√T) with the time horizon T, in scenarios when the underlying communication topology is time-varying and jointly-connected. The regret is measured in regard to the cost function value as well as the constraint violation. Numerical results for online routing in wireless multi-hop networks with uncertain channel rates are provided to illustrate the performance of the proposed algorithm.