Online Convex Optimization with a Separation Oracle

Abstract

In this paper, we introduce a new projection-free algorithm for Online Convex Optimization (OCO) with a state-of-the-art regret guarantee among separation-based algorithms. Existing projection-free methods based on the classical Frank-Wolfe algorithm achieve a suboptimal regret bound of O(T^{3/4}), while more recent separation-based approaches guarantee a regret bound of O(κ√T), where κ denotes the asphericity of the feasible set. Our algorithm achieves a regret bound of Õ(√(dT) + κd), while requiring only Õ(1) calls to a separation oracle per round. Crucially, the main term in the bound, Õ(√(dT)), is independent of κ, addressing the limitations of previous methods.

Zak Mhammedi

Research Scientist

I work on the theoretical foundations of Reinforcement Learning, Controls, and Optimization.