# Regret and Cumulative Constraint Violation Analysis for Distributed Online Constrained Convex Optimization

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 59 references that are in the map.
- First posted on arXiv 1 May 2021.

## Builds on (most cited first, 25 of 25)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication](https://mlsanity.com/paper/1902.00340/) (2019)
- [Adaptive Online Learning in Dynamic Environments](https://mlsanity.com/paper/1810.10815/) (2018)
- [An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedback](https://mlsanity.com/paper/1507.08752/) (2015)
- [Online Convex Optimization with Stochastic Constraints](https://mlsanity.com/paper/1708.03741/) (2017)
- [Distributed optimization over time-varying directed graphs](https://mlsanity.com/paper/1303.2289/) (2013)
- [Tracking Slowly Moving Clairvoyant: Optimal Dynamic Regret of Online Learning with True and Noisy Gradient](https://mlsanity.com/paper/1605.04638/) (2016)
- [Adaptive Algorithms for Online Convex Optimization with Long-term Constraints](https://mlsanity.com/paper/1512.07422/) (2015)
- [Online Convex Optimization with Time-Varying Constraints](https://mlsanity.com/paper/1702.04783/) (2017)
- [Online convex optimization for cumulative constraints](https://mlsanity.com/paper/1802.06472/) (2018)
- [An Online Convex Optimization Approach to Dynamic Network Resource Allocation](https://mlsanity.com/paper/1701.03974/) (2017)
- [Distributed Online Optimization in Dynamic Environments Using Mirror Descent](https://mlsanity.com/paper/1609.02845/) (2016)
- [Online Primal-Dual Mirror Descent under Stochastic Constraints](https://mlsanity.com/paper/1908.00305/) (2019)
- [Distributed Online Convex Optimization with Time-Varying Coupled Inequality Constraints](https://mlsanity.com/paper/1903.04277/) (2019)
- [Bandit Convex Optimization for Scalable and Dynamic IoT Management](https://mlsanity.com/paper/1707.09060/) (2017)
- [Online Distributed Optimization on Dynamic Networks](https://mlsanity.com/paper/1412.7215/) (2014)
- [Distributed Bandit Online Convex Optimization with Time-Varying Coupled Inequality Constraints](https://mlsanity.com/paper/1912.03719/) (2019)
- [A Distributed Online Convex Optimization Algorithm with Improved Dynamic Regret](https://mlsanity.com/paper/1911.05050/) (2019)
- [Distributed Online Optimization with Long-Term Constraints](https://mlsanity.com/paper/1912.09705/) (2019)
- [Online Continuous DR-Submodular Maximization with Long-Term Budget Constraints](https://mlsanity.com/paper/1907.00316/) (2019)
- [GTAdam: Gradient Tracking with Adaptive Momentum for Distributed Online Optimization](https://mlsanity.com/paper/2009.01745/) (2020)
- [Distributed Online Optimization for Multi-Agent Networks with Coupled Inequality Constraints](https://mlsanity.com/paper/1805.05573/) (2018)
- [Coordinate Dual Averaging for Decentralized Online Optimization with Nonseparable Global Objectives](https://mlsanity.com/paper/1508.07933/) (2015)
- [On Distributed Online Convex Optimization with Sublinear Dynamic Regret and Fit](https://mlsanity.com/paper/2001.03166/) (2020)
- [Distributed Online Convex Optimization with an Aggregative Variable](https://mlsanity.com/paper/2007.06844/) (2020)

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

- [Regret and Cumulative Constraint Violation Analysis for Online Convex Optimization with Long Term Constraints](https://mlsanity.com/paper/2106.05135/) (2021)
- [Optimal Algorithms for Online Convex Optimization with Adversarial Constraints](https://mlsanity.com/paper/2310.18955/) (2023)
- [Distributed Online Convex Optimization with Adversarial Constraints: Reduced Cumulative Constraint Violation Bounds under Slater's Condition](https://mlsanity.com/paper/2306.00149/) (2023)
- [Rectified Pessimistic-Optimistic Learning for Stochastic Continuum-armed Bandit with Constraints](https://mlsanity.com/paper/2211.14720/) (2022)
- [Safe Reinforcement Learning with Instantaneous Constraints: The Role of Aggressive Exploration](https://mlsanity.com/paper/2312.14470/) (2023)
- [Online Nonstochastic Control with Adversarial and Static Constraints](https://mlsanity.com/paper/2302.02426/) (2023)
- [Projection-Free Online Convex Optimization with Time-Varying Constraints](https://mlsanity.com/paper/2402.08799/) (2024)
- [Revisiting Projection-Free Online Learning with Time-Varying Constraints](https://mlsanity.com/paper/2501.16046/) (2025)
- [Dynamic Regret Analysis of Safe Distributed Online Optimization for Convex and Non-convex Problems](https://mlsanity.com/paper/2302.12320/) (2023)
- [Universal Dynamic Regret and Constraint Violation Bounds for Constrained Online Convex Optimization](https://mlsanity.com/paper/2510.01867/) (2025)
- [Doubly-Bounded Queue for Constrained Online Learning: Keeping Pace with Dynamics of Both Loss and Constraint](https://mlsanity.com/paper/2412.10703/) (2024)
- [Constrained Online Convex Optimization without Slater's Condition](https://mlsanity.com/paper/2606.31480/) (2026)
- [A Survey on Distributed Online Optimization and Game](https://mlsanity.com/paper/2205.00473/) (2022)
- [Locally Differentially Private Distributed Online Learning with Guaranteed Optimality](https://mlsanity.com/paper/2306.14094/) (2023)
- [Optimistic Safety for Online Convex Optimization with Unknown Linear Constraints](https://mlsanity.com/paper/2403.05786/) (2024)
- [Multi-point Feedback of Bandit Convex Optimization with Hard Constraints](https://mlsanity.com/paper/2310.10946/) (2023)
- [Distributed Online Bandit Nonconvex Optimization with One-Point Residual Feedback via Dynamic Regret](https://mlsanity.com/paper/2409.15680/) (2024)
- [Optimal Bounds for Adversarial Constrained Online Convex Optimization](https://mlsanity.com/paper/2503.13366/) (2025)
- [CLASP: An online learning algorithm for Convex Losses And Squared Penalties](https://mlsanity.com/paper/2601.16072/) (2026)
- [Data-Dependent Regret and Polyak Corrections for Constrained Online Convex Optimization](https://mlsanity.com/paper/2607.25480/) (2026)
- [Constrained Online Learning with Noisy Constraint Values](https://mlsanity.com/paper/2609.06921/) (2026)

## Abstract (arXiv)

This paper considers the distributed online convex optimization problem with time-varying constraints over a network of agents. This is a sequential decision making problem with two sequences of arbitrarily varying convex loss and constraint functions. At each round, each agent selects a decision from the decision set, and then only a portion of the loss function and a coordinate block of the constraint function at this round are privately revealed to this agent. The goal of the network is to minimize the network-wide loss accumulated over time. Two distributed online algorithms with full-information and bandit feedback are proposed. Both dynamic and static network regret bounds are analyzed for the proposed algorithms, and network cumulative constraint violation is used to measure constraint violation, which excludes the situation that strictly feasible constraints can compensate the effects of violated constraints. In particular, we show that the proposed algorithms achieve O(T^maxkappa,1-kappa) static network regret and O(T1-kappa/2) network cumulative constraint violation, where T is the time horizon and kappa∈(0,1) is a user-defined trade-off parameter. Moreover, if the loss functions are strongly convex, then the static network regret bound can be reduced to O(Tkappa). Finally, numerical simulations are provided to illustrate the effectiveness of the theoretical results.