While the above works incorporate predictions in OCO problems with fixed time-invariant constraints (i.e., \(x\!\in \mathcal {X}\) ), we focus on the richer constrained OCO setting where \(\lbrace x_t\rbrace \)  are also subject to time-varying budget constraints (\(x\in \mathcal {X}_T\) ) for an unknown horizon \(T\) . We use a more general model than prior studies with no assumptions on the predictions quality, the geometry of set \(\mathcal {X}_T\)  or the functions \(\lbrace f_t, g_t\rbrace \) , beyond being convex. Technically, our approach benefits from a novel “lazy” update that aggregates all previous cost and constraint vectors and uses data-driven steps that adapt to prediction errors. In particular, we build on FTRL, cf. [1]}, which we extend here with time-varying accumulated constraints — a result of independent interest. Previous greedy-based algorithms for time-varying budget constraints and benchmarks in \(\mathcal {X}_T\)  include [2]}, [3]} which achieve \(\mathcal {R}_T\!=\!\mathcal {O}(\sqrt{T})\)  and \(\mathcal {V}_T\!=\!\mathcal {O}(T^{3/4})\)  assuming, however, fixed and known horizon \(T\) ; [4]} that offers \(\mathcal {R}_T, \mathcal {V}_T=\mathcal {O}(\sqrt{T})\)  but confines the constraints to be linearly-perturbed; [5]} with \(\mathcal {R}_T, \mathcal {V}_T=\mathcal {O}(\sqrt{T})\)  that restricts the constraints to be i.i.d. stochastic; and [6]} that supports \(\mathcal {R}_T, \mathcal {V}_T=\mathcal {O}(T^{2/3})\)  when \(T\)  is known and the constraints vary slowly; see also Table REF . Importantly, none of them can include and benefit from predictions.
