An Ellipsoid Algorithm for Online Convex Optimization

We study the problem of Online Convex Optimization (OCO) over a convex set K ⊂ R d , accessed via a separation oracle. While classical projection-based algorithms such as projected Online Gradient Descent (OGD) achieve the optimal O ( √ T ) regret, they require computing Euclidean projections onto K whenever an iterate falls outside the feasible set. These projections can be computationally expensive, especially for complex or high-dimensional sets. Projection-free algorithms address this by replacing projections with alternative oracle-based procedures, such as separation or linear optimization oracles. However, the regret bounds of existing separation-based methods scale poorly with the set’s asphericity κ , defined as the ratio between the radii of the smallest enclosing ball and the largest inscribed ball in K ; for ill-conditioned sets, κ can be arbitrarily large. We introduce a new separation-based algorithm for OCO that achieves a regret bound of ̃ O (√ dT + d 2 ) , with only logarithmic dependence on κ . This removes a key limitation of prior work and eliminates the need for costly geometric pre-processing, such as transforming K into isotropic position. Our algorithm is based on a novel reduction to online optimization over a sequence of dynamically updated ellipsoids, inspired by the classical ellipsoid method for convex optimization. It requires only ̃ O ( 1 ) separation oracle calls per round, on par with existing separation-based approaches. These advances make our method particularly well suited for online optimization over geometrically complex feasible sets.