New Projection-free Algorithms for Online Convex Optimization with Adaptive Regret Guarantees
This work addresses the need for efficient and adaptive algorithms in online convex optimization, particularly for applications where projection operations are computationally expensive, offering incremental improvements over existing methods.
The paper tackles the problem of online convex optimization by introducing new projection-free algorithms that avoid costly orthogonal projections, achieving adaptive regret guarantees for any sub-interval of the sequence. It presents algorithms with $O(T^{3/4})$ adaptive regret using linear optimization oracles and $O(\sqrt{T})$ adaptive regret using separation oracles, matching or improving upon non-adaptive state-of-the-art bounds.
We present new efficient \textit{projection-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 \textit{follow-the-leader} framework, our algorithms are fundamentally different and are based on the \textit{online gradient descent} algorithm with a novel and efficient approach to computing so-called \textit{infeasible projections}. As a consequence, we obtain the first projection-free algorithms which naturally yield \textit{adaptive 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(T^{3/4})$ adaptive regret and $O(T^{3/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 \textit{not 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(\sqrt{T})$ adaptive regret and $O(T^{3/4})$ adaptive expected regret for the full-information and bandit settings, respectively.