LLP has key differences from previous constrained OCO algorithms. These stem from the usage of lazy as opposed to greedy updates in the primal and dual iteration, where instead of using \(x_{t-1}\)  and \(\lambda _t\)  to decide \(x_t\)  and \(\lambda _{t+1}\)  respectively, we aggregate in a projection-free fashion all prior cost gradients and constraints. This approach can be traced back to lazy algorithms discussed in [1]}; to fictitious (as opposed to best response) strategies in game theory [2]}; and to FTRL algorithms [3]} for problems with fixed constraints. However, to the best of our knowledge, this is the first time such lazy updates are used with time-varying budget constraints.
