mlsanityData to 7 Oct 2026

A near-optimal algorithm for approximating the John Ellipsoid

arXiv 1905.11580 ↗First posted 28 May 2019cs.DScited by 23

Not on the map. Why?

Abstract (arXiv)

We develop a simple and efficient algorithm for approximating the John Ellipsoid of a symmetric polytope. Our algorithm is near optimal in the sense that our time complexity matches the current best verification algorithm. We also provide the MATLAB code for further research.

Key facts. Cited by 23 papers in the map (data through 7 Oct 2026). First posted on arXiv 28 May 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 1; 2022: 2; 2023: 12; 2024: 4; 2025: 2; 2026: 2.

23 papers.

Sort:

  1. 2023Attention Scheme Inspired Softmax Regressioncited by 49
  2. 2022Contextual Bandits with Large Action Spaces: Made Practicalcited by 32
  3. 2023Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Timecited by 31
  4. 2023GradientCoin: A Peer-to-Peer Decentralized Large Language Modelscited by 23
  5. 2023Toward Highly Efficient and Private Submodular Maximization via Matrix-Based Accelerationcited by 11
  6. 2023Efficient SGD Neural Network Training via Sublinear Activated Neuron Identificationcited by 11
  7. 2023Nash Regret Guarantees for Linear Banditscited by 9
  8. 2023Solving Tensor Low Cycle Rank Approximationcited by 8
  9. 2023Fast and Efficient Matching Algorithm with Deadline Instancescited by 7
  10. 2024Fast John Ellipsoid Computation with Differential Privacy Optimizationcited by 7
  11. 2023Convergence of Two-Layer Regression with Nonlinear Unitscited by 6
  12. 2022A Faster k-means++ Algorithmcited by 4
11 more
  1. 2023Tight Bounds for Volumetric Spanners and Applicationscited by 4
  2. 2025When Can We Solve the Weighted Low Rank Approximation Problem in Truly Subquadratic Time?cited by 3
  3. 2021Fast Graph Neural Tangent Kernel via Kronecker Sketchingcited by 2
  4. 2025Learning Confidence Ellipsoids and Applications to Robust Subspace Recoverycited by 2
  5. 2024Quantum Speedup for Spectral Approximation of Kronecker Productscited by 1
  6. 2024Binary Hypothesis Testing for Softmax Models and Leverage Score Modelscited by 1
  7. 2024Log-concave Sampling from a Convex Body with a Barrier: a Robust and Unified Dikin Walkcited by 1
  8. 2026Improved Algorithms for Nash Welfare in Linear Banditscited by 1
  9. 2023Online Adaptive Mahalanobis Distance Estimationcited by 0
  10. 2023Fast Heavy Inner Product Identification Between Weights and Inputs in Neural Network Trainingcited by 0
  11. 2026Beyond Averaging in John Ellipsoid Approximation: High-Accuracy Algorithms in the Leverage-Score Modelcited by 0