New Projection-free Algorithms for Online Convex Optimization with Adaptive Regret Guarantees

We present new efficient textitprojection-free algorithms for online convex optimization (OCO), where by projection-free we refer to algorithms that avoid computing orthogonal projections onto the feasible set, and instead relay on different and potentially much more efficient oracles. While most state-of-the-art projection-free algorithms are based on the textitfollow-the-leader framework, our algorithms are fundamentally different and are based on the textitonline gradient descent algorithm with a novel and efficient approach to computing so-called textitinfeasible projections. As a consequence, we obtain the first projection-free algorithms which naturally yield textitadaptive regret guarantees, i.e., regret bounds that hold w.r.t. any sub-interval of the sequence. Concretely, when assuming the availability of a linear optimization oracle (LOO) for the feasible set, on a sequence of length T, our algorithms guarantee O(T3/4) adaptive regret and O(T3/4) adaptive expected regret, for the full-information and bandit settings, respectively, using only O(T) calls to the LOO. These bounds match the current state-of-the-art regret bounds for LOO-based projection-free OCO, which are textitnot adaptive. We also consider a new natural setting in which the feasible set is accessible through a separation oracle. We present algorithms which, using overall O(T) calls to the separation oracle, guarantee O(√T) adaptive regret and O(T3/4) adaptive expected regret for the full-information and bandit settings, respectively.