Dynamic Optimistic Constrained OCO with Memory via Delay Equivalence
cs.LG, math.OC
Submitted: 2026-11-05
Updated: 2026-11-05
Comments: Accepted at the 40th Conference on Neural Information Processing Systems (NeurIPS 2026)
License: http://creativecommons.org/licenses/by/4.0/
The gist: Online Convex Optimization with memory and time-varying constraints (COCO-M) is a recently-introduced framework that captures the dynamics of stateful online learning and non-stochastic control with…
Terminology
Abstract
Online Convex Optimization with memory and time-varying constraints (COCO-M) is a recently-introduced framework that captures the dynamics of stateful online learning and non-stochastic control with budget constraints. Despite its expressive power, COCO-M remains largely understudied. In this work, we tackle this problem in its full scale, providing an optimistic algorithm that incorporates untrusted predictions to tame universal dynamic regret and cumulative constraint violation. Our analysis leverages a potent reduction from memory to delay and treats state-dependent gradients as delayed feedback. We establish the first bounds that adapt to both environment non-stationarity (path length P T) and prediction accuracy, while lifting previous restrictive assumptions such as functional separability. En route to these results, we derive findings of independent interest for the memory-to-delay reduction, and for delayed OCO with time-varying constraints. The proposed framework ensures sublinear worst-case guarantees that improve with prediction accuracy, reaching O(1) regret under perfect predictions, with cumulative constraint violation (CCV) O(sqrt T) for unknown P T and O(T) for known or online observable P T, while recovering the optimal COCO rates when memory disappears.
Sources
- Online Learning: A Modern Introduction Using Convex Optimization
- Beyond $\tilde{O}(\sqrt{T})$ Constraint Violation for Online Convex Optimization with Adversarial Constraints
- An Optimistic Algorithm for Online Convex Optimization with Adversarial Constraints
- Universal Dynamic Regret and Constraint Violation Bounds for Constrained Online Convex Optimization
- Non-stationary Stochastic Optimization under $L_{p,q}$-Variation Measures
- $O(\sqrt{T})$ Static Regret and Instance Dependent Constraint Violation for Constrained Online Convex Optimization
- Online Nonstochastic Control with Convex Safety Constraints
Related papers
- A Physics-Regulated Neural Framework for Learning 3D Grain Growth Dynamics
- FlexMoE: Learning One-for-All Multi-Budget Expert Pruning for Flexible MoE Deployment
- OptiMind: Improving Small Language Models for Optimization Modeling through Formulation Guidance and Multi-Turn Learning
- Staying in the Sweet Spot: Boost Reasoning Evolution via Responsive Rollout Difficulty Manipulation
- Examining the Impact of Data and Training Methods on Emergent and Subliminal Misalignment
- Rethinking Black-Box On-Policy Distillation: A Rubric-based Analysis