Dynamic Optimistic Constrained OCO with Memory via Delay Equivalence
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 PT) 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 𝒪(1) regret under perfect predictions, with cumulative constraint violation (CCV) 𝒪(√T) for unknown PT and 𝒪(log T) for known or online observable PT , while recovering the optimal COCO rates when memory disappears.
Related
- A Spatial Benders Algorithm for Delay Constrained Routing
- On the Delay-Constrained Maximum Concurrent Flow Problem
- Memory-induced blow-up solutions and their dynamical transitions in distributed delay differential equations
- Adaptive Conformal Inference Under Delayed Feedback: Coverage Guarantees and a Delay-to-Memory Diagnostic
- Dynamic invisibility of implicit and nested state-dependent delays in a class of externally forced delay equations
BibTeX
@misc{abdullah2026dynamic,
title = {{Dynamic Optimistic Constrained OCO with Memory via Delay Equivalence}},
author = {Mohammed Abdullah and George Iosifidis and Salah Eddine Elayoubi and Tijani Chahed},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.08302},
eprint = {2611.08302},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.08302},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Dynamic Optimistic Constrained OCO with Memory via Delay Equivalence
AU - Mohammed Abdullah
AU - George Iosifidis
AU - Salah Eddine Elayoubi
AU - Tijani Chahed
PY - 2026
DA - 2026/11/05
PB - arXiv
DO - 10.48550/arxiv.2611.08302
UR - https://arxiv.org/abs/2611.08302
AB - 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 𝒪(1) regret under perfect predictions, with cumulative constraint violation (CCV) 𝒪(√T) for unknown P_T and 𝒪(log T) for known or online observable P_T , while recovering the optimal COCO rates when memory disappears.
ER -