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

arXiv: https://arxiv.org/abs/2606.20082 · HTML: https://mlsanity.com/paper/2606.20082/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 37 of its 85 references that are in the map.
- First posted on arXiv 18 Jun 2026.

## Builds on (most cited first, 30 of 37)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Relatively-Smooth Convex Optimization by First-Order Methods, and Applications](https://mlsanity.com/paper/1610.05708/) (2016)
- [Less is More: Nystr"om Computational Regularization](https://mlsanity.com/paper/1507.04717/) (2015)
- [On the Global Linear Convergence of Frank-Wolfe Optimization Variants](https://mlsanity.com/paper/1511.05932/) (2015)
- [A Refined Laser Method and Faster Matrix Multiplication](https://mlsanity.com/paper/2010.05846/) (2020)
- [A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization](https://mlsanity.com/paper/1508.04874/) (2015)
- [Input Sparsity Time Low-Rank Approximation via Ridge Leverage Score Sampling](https://mlsanity.com/paper/1511.07263/) (2015)
- [Determinantal Point Processes in Randomized Numerical Linear Algebra](https://mlsanity.com/paper/2005.03185/) (2020)
- [New Frameworks for Offline and Streaming Coreset Constructions](https://mlsanity.com/paper/1612.00889/) (2016)
- [Randomized Numerical Linear Algebra : A Perspective on the Field With an Eye to Software](https://mlsanity.com/paper/2302.11474/) (2023)
- [New Bounds for Matrix Multiplication: from Alpha to Omega](https://mlsanity.com/paper/2307.07970/) (2023)
- [Uniform Sampling for Matrix Approximation](https://mlsanity.com/paper/1408.5099/) (2014)
- [Faster Algorithm for Structured John Ellipsoid Computation](https://mlsanity.com/paper/2211.14407/) (2022)
- [More Asymmetry Yields Faster Matrix Multiplication](https://mlsanity.com/paper/2404.16349/) (2024)
- [A near-optimal algorithm for approximating the John Ellipsoid](https://mlsanity.com/paper/1905.11580/) (2019)
- [Accelerated Bregman Proximal Gradient Methods for Relatively Smooth Convex Optimization](https://mlsanity.com/paper/1808.03045/) (2018)
- [Near Optimal Linear Algebra in the Online and Sliding Window Models](https://mlsanity.com/paper/1805.03765/) (2018)
- [Fast MCMC sampling algorithms on polytopes](https://mlsanity.com/paper/1710.08165/) (2017)
- [Optimal Complexity and Certification of Bregman First-Order Methods](https://mlsanity.com/paper/1911.08510/) (2019)
- [Online Row Sampling](https://mlsanity.com/paper/1604.05448/) (2016)
- [Leveraged volume sampling for linear regression](https://mlsanity.com/paper/1802.06749/) (2018)
- [Online Lewis Weight Sampling](https://mlsanity.com/paper/2207.08268/) (2022)
- [Polytope conditioning and linear convergence of the Frank-Wolfe algorithm](https://mlsanity.com/paper/1512.06142/) (2015)
- [Distributed Adaptive Sampling for Kernel Matrix Approximation](https://mlsanity.com/paper/1803.10172/) (2018)
- [ℓp Row Sampling by Lewis Weights](https://mlsanity.com/paper/1412.0588/) (2014)
- [Proportional Volume Sampling and Approximation Algorithms for A-Optimal Design](https://mlsanity.com/paper/1802.08318/) (2018)
- [Computing Lewis Weights to High Precision](https://mlsanity.com/paper/2110.15563/) (2021)
- [Fast John Ellipsoid Computation with Differential Privacy Optimization](https://mlsanity.com/paper/2408.06395/) (2024)
- [Quantum Speedups for Approximating the John Ellipsoid](https://mlsanity.com/paper/2408.14018/) (2024)

## Abstract (arXiv)

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.