Optimistic algorithm improves online learning with dynamic constraints
Dynamic Optimistic Constrained OCO with Memory via Delay Equivalence
Machine Learning
Summary
Online learning systems often have to make decisions over time while remembering past information and following changing rules or limits. The authors developed a new method that uses predictions to improve performance and reduce mistakes, even when the environment changes or predictions are imperfect. Their approach turns challenges caused by memory into a simpler problem related to delays and provides guarantees that get better with prediction accuracy. This work also relaxes previous strict assumptions and improves on existing methods for these kinds of problems.
What this means in practice
- •For robotics engineers: Develop control algorithms managing stateful robots under changing resource limits using improved regret and constraint guarantees.
- •For network operations teams: Implement adaptive scheduling methods for networks with evolving constraints and feedback delays to optimize performance and reliability.
Authors
Mohammed Abdullah, George Iosifidis, Salah Eddine Elayoubi, Tijani Chahed
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.