Constrained Online Convex Optimization with Memory and Predictions
This work addresses practical problems like control of constrained dynamical systems and scheduling, but it is incremental as it extends existing unconstrained frameworks to include constraints and memory.
The paper tackles constrained online convex optimization with memory, where losses and constraints depend on past decisions, by proposing algorithms that achieve sublinear regret and constraint violation under time-varying constraints, both with and without predictions, with performance improving as prediction accuracy increases.
We study Constrained Online Convex Optimization with Memory (COCO-M), where both the loss and the constraints depend on a finite window of past decisions made by the learner. This setting extends the previously studied unconstrained online optimization with memory framework and captures practical problems such as the control of constrained dynamical systems and scheduling with reconfiguration budgets. For this problem, we propose the first algorithms that achieve sublinear regret and sublinear cumulative constraint violation under time-varying constraints, both with and without predictions of future loss and constraint functions. Without predictions, we introduce an adaptive penalty approach that guarantees sublinear regret and constraint violation. When short-horizon and potentially unreliable predictions are available, we reinterpret the problem as online learning with delayed feedback and design an optimistic algorithm whose performance improves as prediction accuracy improves, while remaining robust when predictions are inaccurate. Our results bridge the gap between classical constrained online convex optimization and memory-dependent settings, and provide a versatile learning toolbox with diverse applications.