Research map / Learning theory and algorithms / Matrix and tensor methods
John Ellipsoids via Lazy Updates
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives a faster John ellipsoid algorithm that delays high-accuracy leverage score computation via row sampling and batches it with fast rectangular matrix multiplication, plus a low-space multi-pass streaming variant.
Problem
Computing approximate John ellipsoids (minimum volume enclosing ellipsoid of n points in d dimensions) faster than prior iterated leverage score algorithms, which cost O(eps^-1 n d^{omega-1} log(n/d)) for dense matrices.
Approach
Iterated leverage score fixed-point updates are accelerated by computing only quadratic forms in most iterations, sampling rows with low-accuracy leverage scores, and deferring high-accuracy weight computation to batched fast rectangular matrix multiplications every O(log n) iterations; leverage scores are also approximated in near-linear time via rectangular matrix multiplication.
Key results
- Algorithm runs in O(eps^-1 nd)(log(n/d)+poly log(eps^-1 log n)) + O(n)poly(eps^-1 log n) + O(n^0.1) d^{omega+1} eps^-3 (log n)^2 time, improving on prior O(eps^-1 n d^{omega-1} log(n/d)) for dense matrices.
- Leverage scores approximated to (1+eps) in O(nd) poly log time for dense matrices via fast rectangular matrix multiplication, improving on sketching-based methods for dense inputs.
- Low-space streaming algorithm makes O(eps^-1 log(n/d)) passes and uses O(d^2 T) words of space to output a (1+eps)-approximate John ellipsoid.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use lazy updates and fast rectangular matrix multiplication | John ellipsoid approximation for dense matrices · Dense n×d matrices, n ≫ d | running time: $O(\eps^{-1}nd)\log(n/d)$ versus $O(\eps^{-2}nd)(\log n)\log(n/d)$ | Helped |
| Use fast rectangular matrix multiplication for approximate leverage scores | Dense-matrix leverage score computation · Dense n×d matrix | running time: $O(nd)\poly\log(\eps^{-1}\log(n/\delta)) + O(n)\poly(\eps^{-1}\log(n/\delta))$ | Helped |
| Store quadratic forms rather than all per-row weights | Streaming John ellipsoid algorithm · John ellipsoid, streaming input | space: $O(d^2 T)$ words | Helped |
Limitations
- Relies on fast matrix multiplication, making it less attractive for practice and giving a large polynomial dependence on eps in the O(n)poly(eps^-1) term.
- Streaming algorithm stores O(d^2 T) words and assumes word-RAM style arithmetic; bit complexity not addressed.
- Does not achieve nearly linear or input-sparsity time John ellipsoid algorithms, which remain open.
Experimental setup
Metrics: running time approximation guarantee of John ellipsoid (sandwich bound)
Baselines: Cohen et al. 2019 iterated leverage score algorithm Cohen-Cole-Miller-Madry-Rel-Vladu sparse leverage score algorithm
Builds on: Cohen et al. 2019 iterated leverage score John ellipsoid algorithm Johnson-Lindenstrauss lemma fast rectangular matrix multiplication
Closest papers by meaning
- Faster Algorithms for Structured John Ellipsoid Computation (NeurIPS 2025 · similarity 0.91)
- ONLINE EPSILON NET & PIERCING SET FOR GEOMETRIC CONCEPTS (ICLR 2025 · similarity 0.82)
- High-Dimensional Geometric Streaming for Nearly Low Rank Data (ICML 2024 · similarity 0.82)
- Improved and Oracle-Efficient Online $\ell_1$-Multicalibration (ICML 2025 · similarity 0.80)
- Near-Linear Time Generalized Sinkhorn Algorithms for Bounded Genus Graphs (NeurIPS 2026 · similarity 0.80)
- Neuc-MDS: Non-Euclidean Multidimensional Scaling Through Bilinear Forms (NeurIPS 2024 · similarity 0.80)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.