Constrained Online Convex Optimization with Memory and Predictions

We study the problem of \emph{Constrained Online Convex Optimization with Memory} (\texttt{COCO‑M}), where both the loss and constraints depend on a window of $m$ past decisions of the learner ($m$ memory length). This setting extends the previously-studied unconstrained OCO-M framework and captures a range of practical problems arising, for instance, in the control of constrained dynamical systems and in scheduling problems with reconfiguration budgets, among others. For this new problem, we propose the first algorithms that achieve sublinear regret and cumulative constraint‑violation (CCV) over time‑varying constraints, both with and without predictions about the missing loss and constraint functions. In the absence of predictions, our approach achieves regret $\mathcal{O}(m^{3/2} \sqrt{T \log T})$ and CCV $\mathcal{O}\big(T^{3/4}\vee! m^{3/2} \sqrt{T \log T}\big)$ using an intuitive adaptive penalty method. When short-horizon ''untrusted'' predictions are available, we reinterpret the problem as an instance of online learning with delayed feedback, and design an optimistic algorithm with regret $\mathcal{O}!\bigl(\sqrt{\mathcal{E}T(f)}\,\vee\,\log T\bigr)$ and CCV $\mathcal{O}!\bigl((\sqrt{\mathcal{E}T(g)}+m)\log T\bigr)$. These bounds depend on the accumulated prediction errors of the losses and constraints ($\mathcal{E}T(f)$ and $\mathcal{E}T(g)$), and improve directly with the predictions accuracy while maintaining order-optimal convergence when they fail. Our results close the gap between classical COCO and memory-dependent COCO, and create a new versatile learning toolbox with diverse applications.