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

Publication date 31 May 2017

Abstract: This paper introduces consensus-based primal-dual methods for distributed online optimization where the time-varying system objective function

f_{t} (m a t h b f x)

is given as the sum of local agents' objective functions, i.e.,

f_{t} (m a t h b f x) = s u m_{i} f_{i, t} (m a t h b f x_{i})

, and the system constraint function

m a t h b f g (m a t h b f x)

is given as the sum of local agents' constraint functions, i.e.,

m a t h b f g (m a t h b f x) = s u m_{i} m a t h b f g_{i} (m a t h b f x_{i}) p r e c e q m a t h b f 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 (s q r t 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.

This page was built for publication: On the Sublinear Regret of Distributed Primal-Dual Algorithms for Online Constrained Optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6287322)