We study the general constrained OCO problem where in round \(t\)  our algorithm, which we name LLP (Lazy Lagrangians with Predictions), has access to all prior cost gradients \(\lbrace \nabla f_i(x_i)\rbrace _{i=1}^{t-1}\)  and constraints \(\lbrace  g_i(x)\rbrace _{i=1}^{t-1}\) , and receives predictions \(\tilde{g}_t(\tilde{x}_t)\) , \(\nabla \tilde{f}_t(\tilde{x}_t)\)  and \(\tilde{g}_t(\cdot )\) . After selecting \(x_t\) , LLP incurs cost \(f_t(x_t)\)  and violation \(g_t(x_t)\) , and the process repeats in the next round. Our first result, Theorem REF , presents the regret and constraint violation bounds and demonstrates how they benefit from predictions. Theorem REF  characterizes the (tunable) growth rates of the bounds and exhibits their dependency on the accumulated prediction errors. Theorem REF  and Lemma REF  present the respective bounds when LLP employs fully-linearized cost and constraint functions and non-proximal regularizers, cf. [1]}, in order to reduce its computation and memory requirements. For this linearized version, it suffices to have gradient predictions \(\nabla \tilde{g}_t(\tilde{x}_t)\)  instead of predictions \(\tilde{g}_t(\cdot )\)  for the entire constraint function. Indeed, in some problems it might be easier to acquire such single-point predictions compared to predictions for the constraint function; but we note that this is not always the caseFor example, when \(g_t(x)\)  is the (non-linear) monetary cost for purchasing \(x\)  units of a resource, predicting \(\tilde{g}_t(\cdot )\)  requires knowing the price per unit; while \(\nabla \tilde{g}_t(\tilde{x}_t)\)  requires also to predict the actual purchased amount \(\tilde{x}_t\) .; LLP can handle both scenarios. Finally, Lemma REF  presents LLP's performance for linearly-perturbed constraints, a special but important case that was studied in [2]}.
