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

The John ellipsoid of a symmetric polytope P={x\in\mathbb{R}^d:|Ax|\infty\le1}, A\in\mathbb{R}^{n\times 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 Θ(\varepsilon^{-1}\log(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 \min{p\inΔ_n}-\log\det(\sum_i p_ia_ia_i^\top), the leverage-score oracle is exactly the first-order oracle and the (1+\varepsilon)-John guarantee the Frank-Wolfe gap g(p)\le\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 Θ(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(\sqrtκ\log(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(\log\log(1/\varepsilon)) steps, for a total of C(A)+O(d^2\log\log(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.