Distributed Online Convex Optimization with Time-Varying Coupled Inequality Constraints

Abstract

This paper considers distributed online optimization with time-varying coupled inequality constraints. The global objective function is composed of local convex cost and regularization functions and the coupled constraint function is the sum of local convex functions. A distributed online primal-dual dynamic mirror descent algorithm is proposed to solve this problem, where the local cost, regularization, and constraint functions are held privately and revealed only after each time slot. Without assuming Slater's condition, we first derive regret and constraint violation bounds for the algorithm and show how they depend on the stepsize sequences, the accumulated dynamic variation of the comparator sequence, the number of agents, and the network connectivity. As a result, under some natural decreasing stepsize sequences, we prove that the algorithm achieves sublinear dynamic regret and constraint violation if the accumulated dynamic variation of the optimal sequence also grows sublinearly. We also prove that the algorithm achieves sublinear static regret and constraint violation under mild conditions. Assuming Slater's condition, we show that the algorithm achieves smaller bounds on the constraint violation. In addition, smaller bounds on the static regret are achieved when the objective function is strongly convex. Finally, numerical simulations are provided to illustrate the effectiveness of the theoretical results.

References in corpus (14)

• An Online Convex Optimization Approach to Dynamic Network Resource Allocation
• Online Distributed Optimization on Dynamic Networks
• Trading Regret for Efficiency: Online Convex Optimization with Long Term Constraints
• An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedback
• Bandit Convex Optimization for Scalable and Dynamic IoT Management
• Online convex optimization for cumulative constraints
• Online Convex Optimization with Time-Varying Constraints
• On the Sublinear Regret of Distributed Primal-Dual Algorithms for Online Constrained Optimization
• Distributed Constrained Online Learning
• An optimal algorithm for bandit convex optimization
• A Low Complexity Algorithm with $O(\sqrt{T})$ Regret and $O(1)$ Constraint Violations for Online Convex Optimization with Long Term Constraints
• Distributed Online Linear Regression
• Distributed Zero-Order Algorithms for Nonconvex Multi-Agent Optimization
• Online Continuous DR-Submodular Maximization with Long-Term Budget Constraints

Cited by in corpus (2)

• Distributed Online Convex Optimization with Improved Dynamic Regret
• Distributed Online Optimization with Long-Term Constraints