The complexity of LLP is analogous to its greedy-based counterparts — sans the additional prescient update (REF ) — i.e., it requires the solution of strongly convex problems and a closed-form iteration for the dual update; the calculation of the regularizers and steps is in \(\mathcal {O}(1)\) . Finally, it is worth emphasizing that the impossibility result of [1]} holds even if \(\lbrace f_t, g_t\rbrace \)  are revealed before \(\lbrace x_t\rbrace \)  is selected, as stated in the next Lemma that is proved in the Appendix. This exhibits the challenges in tackling constrained OCO problems.
