An Ellipsoid Algorithm for Online Convex Optimization

Abstract

We study Online Convex Optimization (OCO) over a convex set accessed via a separation oracle. We introduce a new projection-free algorithm that achieves a regret bound of Õ(√(dT) + d²) with only logarithmic dependence on the set’s asphericity, addressing a limitation of prior separation-based methods which scaled poorly with this factor. This approach eliminates the need for costly geometric pre-processing, making it well-suited for online optimization over geometrically complex feasible sets. The algorithm is inspired by the classical ellipsoid method for convex optimization and requires only Õ(1) separation oracle calls per round.

Zak Mhammedi

Research Scientist

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