# Distributed Online Convex Optimization with Nonseparable Costs and Constraints

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 28 references that are in the map.
- First posted on arXiv 11 Feb 2026.

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

- [Partially Observable Markov Decision Processes in Robotics: A Survey](https://mlsanity.com/paper/2209.10342/) (2022)
- [Optimal Algorithms for Online Convex Optimization with Adversarial Constraints](https://mlsanity.com/paper/2310.18955/) (2023)
- [Distributed Online Convex Optimization with Time-Varying Coupled Inequality Constraints](https://mlsanity.com/paper/1903.04277/) (2019)
- [The Confluence of Networks, Games and Learning](https://mlsanity.com/paper/2105.08158/) (2021)
- [Distributed Bandit Online Convex Optimization with Time-Varying Coupled Inequality Constraints](https://mlsanity.com/paper/1912.03719/) (2019)
- [Distributed Online Optimization with Long-Term Constraints](https://mlsanity.com/paper/1912.09705/) (2019)
- [Coordinate Dual Averaging for Decentralized Online Optimization with Nonseparable Global Objectives](https://mlsanity.com/paper/1508.07933/) (2015)
- [On the Resilience of Traffic Networks under Non-Equilibrium Learning](https://mlsanity.com/paper/2210.03214/) (2022)
- [Multi-level Traffic-Responsive Tilt Camera Surveillance through Predictive Correlated Online Learning](https://mlsanity.com/paper/2408.02208/) (2024)
- [Is Stochastic Mirror Descent Vulnerable to Adversarial Delay Attacks? A Traffic Assignment Resilience Study](https://mlsanity.com/paper/2304.01161/) (2023)
- [Locally-Aware Constrained Games on Networks](https://mlsanity.com/paper/2011.10095/) (2020)
- [Online Convex Optimization with Long Term Constraints for Predictable Sequences](https://mlsanity.com/paper/2210.16735/) (2022)
- [On the Variational Interpretation of Mirror Play in Monotone Games](https://mlsanity.com/paper/2403.15636/) (2024)

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

- [Constrained Online Convex Optimization without Slater's Condition](https://mlsanity.com/paper/2606.31480/) (2026)

## Abstract (arXiv)

This paper studies distributed online convex optimization with time-varying coupled constraints, motivated by distributed online control in network systems. Most prior work assumes a separability condition: the global objective and coupled constraint functions are sums of local costs and individual constraints. In contrast, we study a group of agents, networked via a communication graph, that collectively select actions to minimize a sequence of nonseparable global cost functions and to satisfy nonseparable long-term constraints based on full-information feedback and intra-agent communication. We propose a distributed online primal-dual belief consensus algorithm, where each agent maintains and updates a local belief of the global collective decisions, which are repeatedly exchanged with neighboring agents. Unlike the previous consensus primal-dual algorithms under separability that ask agents to only communicate their local decisions, our belief-sharing protocol eliminates coupling between the primal consensus disagreement and the dual constraint violation, yielding sublinear regret and cumulative constraint violation (CCV) bounds, both in O(T1/2), where T denotes the time horizon. Such a result breaks the long-standing O(T3/4) barrier for CCV and matches the lower bound of online constrained convex optimization, indicating the online learning efficiency at the cost of communication overhead.