Online Convex Optimization with a Separation Oracle

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(T3/4), while more recent separation-based approaches guarantee a regret bound of O(kappa √T), where kappa denotes the asphericity of the feasible set, defined as the ratio of the radii of the containing and contained balls. However, for ill-conditioned sets, kappa can be arbitrarily large, potentially leading to poor performance. Our algorithm achieves a regret bound of widetildeO(√dT + kappa d), while requiring only widetildeO(1) calls to a separation oracle per round. Crucially, the main term in the bound, widetildeO(√d T), is independent of kappa, addressing the limitations of previous methods. Additionally, as a by-product of our analysis, we recover the O(kappa √T) regret bound of existing OCO algorithms with a more straightforward analysis and improve the regret bound for projection-free online exp-concave optimization. Finally, for constrained stochastic convex optimization, we achieve a state-of-the-art convergence rate of widetildeO(σ/√T + kappa d/T), where σ represents the noise in the stochastic gradients, while requiring only widetildeO(1) calls to a separation oracle per iteration.