The John ellipsoid of a symmetric polytope $P=\{\mathbf{x}\in\mathbb{R}^d:\|\mathbf{A}\mathbf{x}\|_\infty\le1\}$, where $\mathbf{A}\in\mathbb{R}^{n\times d}$, is computed through a series of leverage-score algorithms from Cohen, Cousins, Lee, and Yang (COLT 2019) to subsequent works [WY24, CLS+25], all achieving a $(1+\varepsilon)$-approximation in $\Theta(\varepsilon^{-1}\log(n/d))$ iterations. This complexity is separated into three costs that the modern line conflates: certification, identification, and accuracy, locating the historical $\varepsilon^{-1}$ in the first alone.
In the equivalent D-optimal design form $\min_{\mathbf{p}\in\Delta_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+\varepsilon)$-John guarantee implies the Frank-Wolfe gap $g(\mathbf{p})\le\varepsilon d$; through this dictionary, the costs are disentangled. The $\varepsilon^{-1}$ is a certification artifact: the uniform average of iterates, the certificate used throughout, has a gap of exactly $\Theta(1/T)$, despite the low cost per iteration.
When focusing instead on the last iterate, the same oracle can operate quickly: a warm-started accelerated method achieves the guarantee in $C(\mathbf{A})+O(\sqrt{\kappa}\log(1/\varepsilon))$ queries after an $\varepsilon$-independent setup $C(\mathbf{A})$, and once the optimal face is identified, the facial problem becomes an unconstrained self-concordant minimization whose Hessian the oracle recovers exactly, allowing damped Newton to require only $O(\log\log(1/\varepsilon))$ steps, resulting in a total of $C(\mathbf{A})+O(d^2\log\log(1/\varepsilon))$ queries. Thus, the accuracy dependence is doubly logarithmic after an $\varepsilon$-independent, condition-dependent setup; the open problem remains the remaining identification cost (a condition-free bound on reaching the optimal face) and lower bounds. Accuracy is not the obstruction.