OCO-S$^2$: Online Convex Optimization with Stateful Costs and Sparse Communication

Abstract

We study \textsc{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 \textsc{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, \textsc{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.