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

Abstract

The John ellipsoid of a symmetric polytope $P=\{\mathbf{x}\in {\mathbb{R}}^d:\Vert \mathbf{Ax}{\Vert }_{\infty }\le 1\}$, $\mathbf{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+\epsilon )$-approximation in $\hat{I}˜({\epsilon }^{-1}\log (n/d))$ iterations. We separate this complexity into three costs the modern line conflates (certification, identification, and accuracy) and locate the historical ${\epsilon }^{-1}$ in the first alone. In the equivalent D-optimal-design form ${\min }_{\mathbf{p}\in \hat{I}{”}_n}-\log \det ({\sum }_i{p}_i{\mathbf{a}}_i{\mathbf{a}}_i^{\top })$, the leverage-score oracle is exactly the first-order oracle and the $(1+\epsilon )$-John guarantee the Frank-Wolfe gap $g(\mathbf{p})\le \epsilon d$; through this dictionary the costs come apart. The ${\epsilon }^{-1}$ is a certification artifact: the uniform average of the iterates, the certificate used throughout the line, has gap exactly $\hat{I}˜(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(\mathbf{A})+O(\sqrt{\hat{I}}º\log (1/\epsilon ))$ queries after an $\epsilon$-independent setup $C(\mathbf{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/\epsilon ))$ steps, for a total of $C(\mathbf{A})+O(d^2\log \log (1/\epsilon ))$ queries. The accuracy dependence is thus doubly logarithmic after an $\epsilon$-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.