arXiv preprint ·
Dynamic Optimistic Constrained OCO with Memory via Delay Equivalence
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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 $\mathcal O(1)$ regret under perfect predictions, with cumulative constraint violation (CCV) $\mathcal O(\sqrt{T})$ for unknown $P_T$ and $\mathcal O(\log T)$ for known or online observable $P_T$ , while recovering the optimal COCO rates when memory disappears.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Machine Learning
Last-Iterate Convergence of Stochastic Gradient Methods for Unbounded Problems
From What Is Used to What Is Missing: Rethinking Dynamic Rank in LoRA
Truncated backpropagation through time induces a two-sided gradient turnpike property
Learning and Steering in Incomplete-Information Games
A Bilevel Neurodynamic Approach for Distributed SCAD-Regularized Sparse Least Squares
Get the few papers worth your time in Machine Learning every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.