Beyond Averaging in John Ellipsoid Approximation: High-Accuracy Algorithms in the Leverage-Score Model

Abstract

The John ellipsoid of a symmetric polytope P = {x ∈ R^d : ||Ax||∞ ≤ 1}, A ∈ R^{n×d}, is computed by a long line of leverage-score algorithms, from Cohen, Cousins, Lee and Yang (COLT 2019) [CCLY19] to its successors [WY24, CLS+25], all reaching a (1 + ε)-approximation in Θ(ε^{-1} log(n/d)) iterations. We separate this complexity into three costs the modern line conflates (certification, identification, and accuracy) and locate the historical ε^{-1} in the first alone. In the equivalent D-optimal-design form min_{p∈Δ_n} -log det(Σ_i p_i a_i a_i^T), the leverage-score oracle is exactly the first-order oracle and the (1 + ε)-John guarantee the Frank-Wolfe gap g(p) ≤ εd; through this dictionary the costs come apart. The ε^{-1} is a certification artifact: the uniform average of the iterates, the certificate used throughout the line, has gap exactly Θ(1/T), however cheap each iteration is made. Pointed instead at the last iterate the same oracle is fast: a warm-started accelerated method reaches the guarantee in C(A) + O(√κ log(1/ε)) queries after an ε-independent setup C(A), and once the optimal face is identified the facial problem is an unconstrained self-concordant minimization whose Hessian the oracle recovers exactly, so damped Newton needs only O(log log(1/ε)) steps, for a total of C(A) + O(d² log log(1/ε)) queries. The accuracy dependence is thus doubly logarithmic after an ε-independent, condition-dependent setup; the open problem is the remaining identification cost (a condition-free bound on reaching the optimal face) and lower bounds. Accuracy is not the obstruction.