OCO-S 2 : Online Convex Optimization with Stateful Costs and Sparse Communication
Yiwei Liu, Luwei Yang, Shunbo Lei · 2026
Read OCO-S 2 : Online Convex Optimization with Stateful Costs and Sparse Communication by Yiwei Liu, Luwei Yang, Shunbo Lei (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-16047.txt.
Introduction
Liu, Yang, and Lei study online convex optimization where each choice steers a stable dynamical state. Feedback comes only in sparse blocks, and only some agents take part each round. Their projected block gradient method comes with bounds on dynamic regret that weigh message passing, rival movement, state memory, and take-up. A version aided by forecasts improves the bound when the forecasts prove right.
Catalog record
| CREATOR | Yiwei Liu, Luwei Yang, Shunbo Lei |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 31495 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.16047
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
OCO-S 2 : Online Convex Optimization with Stateful Costs and Sparse Communication Yiwei Liu, Luwei Yang, Shunbo Lei Abstract We study OCO-S 2 , an online convex optimization setting in which decisions drive a stable dynamical state, losses are incurred along the induced state trajectory, and first-order feedback is available only through sparse block communication with partial participation. This coupling creates a dynamic-regret problem beyond pointwise OCO: the learner updates and holds decisions at the block scale, whereas the hindsight comparator may vary at the per-round scale. We propose OCO-S 2 -OGD , a projected block online gradient method that updates deployed decisions using sparse block-level distributed feedback. We prove dynamic-regret bounds for the incurred trajectory cost, quantifying the tradeoff among block communication, comparator variation, state-memory truncation, and partial participation. We further introduce a prediction-augmented variant, OCO-S 2 -OGD-P , and show that accurate block-level predictions improve the optimization term in the regret bound through their realized gradient-mismatch error. Overall, this work provides a regret-theoretic foundation for communication-efficient online decision-making in systems where algorithmic updates and physical state trajectories are intrinsically coupled. 1 Introduction Online convex optimization (OCO) provides a standard framework for sequential decision-making in nonstationary environments. At each round, a learner chooses a feasible decision, observes loss information, and is evaluated by regret against a hindsight benchmark. Dynamic-regret analysis further compares the learner with path-length-bounded time-varying comparators, making it suitable for environments with drifting optima ( Zinkevich 2003 ; Hall and Willett 2013 ; Jadbabaie et al. 2015 ; Zhao et al. 2020 ) . In many online decision systems, however, the setting is not a pointwise OCO problem with full per-round feedback. A deployed decision may drive an operational state through system dynamics, so its effect persists beyond the current round and later losses are incurred along the resulting state trajectory ( Li, Das, and Li 2021 ) . At the same time, distributed implementations often cannot synchronize all clients at every round: feedback is available only at block boundaries and may involve only a subset of clients ( Karimireddy et al. 2020 ) . The learner must therefore hold deployed decisions within communication blocks, while the operational state continues to evolve at the per-round time scale. This combination creates a trajectory-level dynamic-regret problem: sparse communication affects not only the information used for future updates, but also the state trajectory on which future costs are incurred. We study this coupled setting through OCO-S 2 : online convex optimization with stateful costs and sparse communication. In OCO-S 2 , sparse communication does not merely delay or restrict the feedback available to the learner. Because deployed decisions are held within communication blocks while the system state evolves at the per-round scale, the communication protocol also changes the realized state trajectory itself and hence the incurred cumulative cost. This coupling calls for an analysis that separates algorithmic update error from the trajectory error caused by block-held decisions. In particular, the learner is evaluated on the state trajectory generated by its sparse communication protocol, whereas the dynamic comparator is selected in hindsight from a path-length-bounded class and may vary at the per-round scale. The regret analysis must therefore account for the mismatch between a block-held online trajectory and a per-round dynamic benchmark, in addition to the approximation error caused by state memory and the sampling error caused by partial participation. To address these issues, we develop OCO-S 2 -OGD , a projected block online gradient method for OCO-S 2 . The algorithm exploits the fading-memory property of stable dynamics to build finite-memory surrogate losses. After each communication block, only activated clients return local surrogate gradients, and the server performs one projected update for the next block. Thus the method communicates only O(T/K) times over a horizon of length T , while its analysis controls dynamic regret for the incurred state-dependent cost. The contributions of this paper are summarized as follows. 1. We formulate OCO-S 2 , an online convex optimization problem with stateful incurred costs and sparse communication. In this setting, decisions drive a stable dynamical state, while first-order feedback is available only through block-level partial communication. 2. We develop OCO-S 2 -OGD , a projected block online gradient method with sparse distributed feedback, and prove its dynamic-regret bound for the incurred trajectory cost against path-length-bounded comparators. The bound decomposes the effects of online descent, sparse communication, comparator drift, state-memory truncation, and partial participation, while the method uses only O(T/K) synchronization rounds over a horizon of length T . 3. We extend the framework to a prediction-augmented variant, OCO-S 2 -OGD-P , and show that accurate block-level predictions can improve the optimization term in the regret bound. 2 Related Work Online convex optimization with memory. Online convex optimization with memory extends the classical OCO framework by allowing the loss at each round to depend on a finite window of past decisions ( Zinkevich 2003 ; Anava et al. 2013 ) . This formulation provides a natural model for temporal coupling caused by switching costs, reconfiguration costs, and finite-memory system dependence. Recent work has further incorporated constraints and predictions into memory-based online convex optimization, where losses and constraints may both depend on a finite decision window ( Abdullah et al. 2026 ) . This line is closest to ours because it moves beyond pointwise losses and explicitly accounts for the effect of past decisions on current performance. The key difference is that existing OCO-with-memory formulations usually take a finite memory length as part of the problem definition and do not make sparse communication a source of trajectory mismatch. In contrast, OCO-S 2 starts from a stable dynamical system: the current state, and therefore the incurred loss, depends in principle on the entire past decision history. Moreover, the learner receives first-order feedback only through block-level partial communication, so the deployed decision is held fixed within each communication block while the state continues to evolve at the per-round time scale. Thus sparse communication is not merely a feedback constraint; it also changes the realized state trajectory on which future costs are incurred. We exploit the fading-memory property of stable dynamics to control the contribution of remote history and approximate the incurred trajectory cost by finite-memory surrogate losses. In this sense, OCO-S 2 extends finite-memory OCO from explicitly windowed losses with regular feedback to stateful incurred costs under sparse block communication. Sparse communication and partial participation. Communication constraints are central in distributed online learning and communication-efficient optimization. Existing methods study how infrequent synchronization, incomplete feedback, heterogeneous local information, or partial participation affect optimization and regret performance ( Stich 2019 ; Karimireddy et al. 2020 ; Malinovskiy et al. 2020 ; Jhunjhunwala et al. 2022 ; Lin et al. 2022 ; Wan et al. 2022 ; Cao and Basar 2023 ) . In pointwise loss models, sparse communication mainly affects the update error or the variance of gradient estimates. In OCO-S 2 , sparse communication has an additional effect: because decisions are held fixed within communication blocks, it changes the realized state trajectory and therefore the future incurred costs. Moreover, the online learner updates only at block boundaries, whereas the dynamic comparator may vary at the per-round time scale under a path-length budget. Overall, existing work