Online Convex Optimization with Unbounded Memory
Main Conference Track
Authors: Raunak Kumar, Sarah Dean, Robert Kleinberg

Online convex optimization (OCO) is a widely used framework in online  learning. In each round, the learner chooses a decision in a convex set and an  adversary chooses a convex loss function, and then the learner suffers the  loss associated with their current decision. However, in many applications the  learner's loss depends not only on the current decision but on the entire  history of decisions until that point. The OCO framework and its existing  generalizations do not capture this, and they can only be applied to many  settings of interest after a long series of approximation arguments. They also  leave open the question of whether the dependence on memory is tight because  there are no non-trivial lower bounds. In this work we introduce a  generalization of the OCO framework, ``Online Convex Optimization with  Unbounded Memory'', that captures long-term dependence on past decisions. We  introduce the notion of $p$-effective memory capacity, $H_p$, that quantifies  the maximum influence of past decisions on present losses. We prove an  $O(\sqrt{H_p T})$ upper bound on the policy regret and a matching (worst-case)  lower bound. As a special case, we prove the first non-trivial lower bound for  OCO with finite memory~\citep{anavaHM2015online}, which could be of  independent interest, and also improve existing upper bounds. We demonstrate  the broad applicability of our framework by using it to derive regret bounds,  and to improve and simplify existing regret bound derivations, for a variety  of online learning problems including online linear control and an online  variant of performative prediction.