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

The John ellipsoid of a symmetric polytope P=x∈ℝd:|Ax|_∞≤1, A∈ℝn× d, is computed by a long line of leverage-score algorithms, from Cohen, Cousins, Lee and Yang (COLT 2019) to its successors [WY24, CLS+25], all reaching a (1+varepsilon)-approximation in Theta(varepsilon-1log(n/d)) iterations. We separate this complexity into three costs the modern line conflates (certification, identification, and accuracy) and locate the historical varepsilon-1 in the first alone. In the equivalent D-optimal-design form minp∈Deltan-logdet(sumi piaiai^top), the leverage-score oracle is exactly the first-order oracle and the (1+varepsilon)-John guarantee the Frank-Wolfe gap g(p)≤varepsilon d; through this dictionary the costs come apart. The varepsilon-1 is a certification artifact: the uniform average of the iterates, the certificate used throughout the line, has gap exactly Theta(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(√kappalog(1/varepsilon)) queries after an varepsilon-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(loglog(1/varepsilon)) steps, for a total of C(A)+O(d2loglog(1/varepsilon)) queries. The accuracy dependence is thus doubly logarithmic after an varepsilon-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.