# Distributed Online Convex Optimization with Adversarial Constraints: Reduced Cumulative Constraint Violation Bounds under Slater's Condition

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 43 references that are in the map.
- First posted on arXiv 31 May 2023.

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

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Online Convex Optimization with Stochastic Constraints](https://mlsanity.com/paper/1708.03741/) (2017)
- [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)
- [Regret and Cumulative Constraint Violation Analysis for Online Convex Optimization with Long Term Constraints](https://mlsanity.com/paper/2106.05135/) (2021)
- [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)
- [Regret and Cumulative Constraint Violation Analysis for Distributed Online Constrained Convex Optimization](https://mlsanity.com/paper/2105.00321/) (2021)
- [Online Distributed Optimization on Dynamic Networks](https://mlsanity.com/paper/1412.7215/) (2014)
- [Distributed Online Optimization with Long-Term Constraints](https://mlsanity.com/paper/1912.09705/) (2019)
- [Distributed Mirror Descent for Online Composite Optimization](https://mlsanity.com/paper/2004.00837/) (2020)
- [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)
- [Coordinate Dual Averaging for Decentralized Online Optimization with Nonseparable Global Objectives](https://mlsanity.com/paper/1508.07933/) (2015)
- [Stochastic Reactive Power Management in Microgrids with Renewables](https://mlsanity.com/paper/1409.6758/) (2014)

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

- [Optimal Algorithms for Online Convex Optimization with Adversarial Constraints](https://mlsanity.com/paper/2310.18955/) (2023)
- [An Optimistic Algorithm for Online Convex Optimization with Adversarial Constraints](https://mlsanity.com/paper/2412.08060/) (2024)
- [A Geometric Approach to Constrained Online Learning](https://mlsanity.com/paper/2605.21107/) (2026)
- [Convex Optimization with Nested Evolving Feasible Sets](https://mlsanity.com/paper/2605.07386/) (2026)
- [BAGEL: Adversarially Constrained Online Convex Optimization under Separation Oracle Access](https://mlsanity.com/paper/2502.16744/) (2025)
- [Breaking the O(√T) Cumulative Constraint Violation Barrier while Achieving O(√T) Static Regret in Constrained Online Convex Optimization](https://mlsanity.com/paper/2603.20671/) (2026)
- [Online Omniprediction with Long-Term Constraints](https://mlsanity.com/paper/2509.11357/) (2025)
- [Tight Bounds for Online Convex Optimization with Adversarial Constraints](https://mlsanity.com/paper/2405.09296/) (2024)
- [Optimal Anytime Algorithms for Online Convex Optimization with Adversarial Constraints](https://mlsanity.com/paper/2510.22579/) (2025)
- [Dynamic Regret Bounds for Online Omniprediction with Long Term Constraints](https://mlsanity.com/paper/2510.07266/) (2025)
- [Multi-Objective textitmin-max Online Convex Optimization](https://mlsanity.com/paper/2510.13560/) (2025)
- [Lower Bound on the Cumulative Constrained Violation for the OGD+Projection algorithm for Constrained Online Convex Optimization (COCO)](https://mlsanity.com/paper/2607.10808/) (2026)
- [Convex Optimization with Nested Evolving Feasible Sets (CONES) under Time-Varying Loss Functions](https://mlsanity.com/paper/2609.11207/) (2026)
- [tildeO(√T) Regret and Polylogarithmic Constraint Violation for COCO](https://mlsanity.com/paper/2610.03983/) (2026)

## Abstract (arXiv)

This paper considers distributed online convex optimization with adversarial constraints. In this setting, a network of agents makes decisions at each round, and then only a portion of the loss function and a coordinate block of the constraint function are privately revealed to each agent. The loss and constraint functions are convex and can vary arbitrarily across rounds. The agents collaborate to minimize network regret and cumulative constraint violation. A novel distributed online algorithm is proposed and it achieves an O(T^maxc,1-c) network regret bound and an O(T1-c/2) network cumulative constraint violation bound, where T is the number of rounds and c∈(0,1) is a user-defined trade-off parameter. When Slater's condition holds (i.e, there is a point that strictly satisfies the inequality constraints), the network cumulative constraint violation bound is reduced to O(T1-c). Moreover, if the loss functions are strongly convex, then the network regret bound is reduced to O(log(T)), and the network cumulative constraint violation bound is reduced to O(√log(T)T) and O(log(T)) without and with Slater's condition, respectively. To the best of our knowledge, this paper is the first to achieve reduced (network) cumulative constraint violation bounds for (distributed) online convex optimization with adversarial constraints under Slater's condition. Finally, the theoretical results are verified through numerical simulations.