pith. sign in

arxiv: 2606.20082 · v1 · pith:OPJE5DZBnew · submitted 2026-06-18 · 🧮 math.OC · cs.DS· cs.LG

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

Xiaoyu Li , Junwei Yu , Jiaojiao Jiang , Junbin Gao , Andi Han This is my paper

Pith reviewed 2026-06-26 16:18 UTC · model grok-4.3

classification 🧮 math.OC cs.DScs.LG
keywords John ellipsoidleverage score samplingD-optimal designFrank-Wolfe algorithmself-concordant minimizationfacial reductionapproximation algorithmsconvex optimization
0
0 comments X

The pith

John ellipsoid approximation reaches (1+ε) accuracy with doubly logarithmic dependence on ε after an ε-independent setup.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper separates the historical Θ(ε^{-1} log(n/d)) iteration bound for John ellipsoid approximation into three distinct costs: certification via averaging, identification of the optimal face, and accuracy refinement. In the equivalent D-optimal design formulation, the leverage-score oracle acts as an exact first-order oracle, so the uniform average of iterates produces a gap of Θ(1/T) while the last iterate permits a warm-started accelerated method that reaches the guarantee after a condition-dependent but ε-independent setup plus O(√κ log(1/ε)) queries. Once the optimal face is identified, the facial problem becomes an unconstrained self-concordant minimization whose Hessian is recovered exactly by the oracle, allowing damped Newton to finish in O(log log(1/ε)) steps for a total accuracy cost of O(d² log log(1/ε)). A sympathetic reader would care because this removes the linear 1/ε dependence that dominated prior work and isolates the remaining identification cost as the open question.

Core claim

In the D-optimal-design form min_p∈Δ_n -log det(∑ p_i a_i a_i^T) the (1+ε)-John guarantee is exactly the Frank-Wolfe gap g(p) ≤ ε d; the leverage-score oracle supplies exact first-order information, the uniform average produces gap Θ(1/T), but the last iterate with a warm-started accelerated method reaches the guarantee in C(A) + O(√κ log(1/ε)) queries, and after identification of the optimal face the resulting unconstrained self-concordant problem is solved by damped Newton in O(log log(1/ε)) steps because the oracle recovers the Hessian exactly, for total accuracy cost C(A) + O(d² log log(1/ε)).

What carries the argument

The separation of total complexity into certification cost (from uniform averaging of iterates), identification cost (reaching the optimal face), and accuracy cost (refinement once on the face), with the leverage-score oracle serving as an exact first-order oracle in the D-optimal design formulation.

If this is right

  • The historical linear dependence on 1/ε arises solely from certification via averaging and is independent of how cheap each iteration is made.
  • A warm-started accelerated method on the last iterate suffices for the accuracy phase with only √κ log(1/ε) additional queries.
  • Damped Newton on the identified face requires only O(log log(1/ε)) steps because the Hessian is recovered exactly.
  • The remaining bottleneck is a condition-free bound on the identification cost; accuracy is no longer the obstruction.
  • The overall query complexity after setup is O(d² log log(1/ε)) for the accuracy portion.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If a condition-free bound on identification can be obtained, the full algorithm would have near-optimal dependence on ε.
  • The same separation of certification, identification, and accuracy may apply to other Frank-Wolfe or first-order methods on polytopes where facial structure is present.
  • Lower bounds specifically on identification would clarify whether doubly logarithmic accuracy is information-theoretically optimal once the face is known.

Load-bearing premise

Once the optimal face is identified, the facial problem is an unconstrained self-concordant minimization whose Hessian the leverage-score oracle recovers exactly.

What would settle it

A concrete instance where, after the optimal face is reached, the leverage-score oracle fails to recover the exact Hessian or damped Newton requires more than O(log log(1/ε)) steps to achieve gap ε d.

Figures

Figures reproduced from arXiv: 2606.20082 by Andi Han, Jiaojiao Jiang, Junbin Gao, Junwei Yu, Xiaoyu Li.

Figure 1
Figure 1. Figure 1: traces the logical structure of the paper: an arrow X → Y means that the proof of Y invokes X. The three pillars—the averaging barrier (Section 3), the accelerated phase (Section 5), and the facial Newton phase (Section 6)—share the dictionary (Proposition 2.2); the two last-iterate phases additionally share the facial toolkit of Section 4. Dashed nodes are imported; bold nodes are the three headline theor… view at source ↗
Figure 2
Figure 2. Figure 2: The averaged-versus-last-iterate separation of Corollary 5.9, on A⋆ (left) and a random instance (right): the uniform-averaging certificate (CCLY-avg) needs Θ(ε −1 ) leverage evaluations, whereas CCLY’s own last iterate, away-step Frank–Wolfe, and both facial phases of Algorithm 1 (accelerated and Newton) are polylogarithmic in 1/ε. 43 [PITH_FULL_IMAGE:figures/full_fig_p043_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: The averaging law on A⋆ (Theorem 3.4): the gap of the uniform running average obeys T ·g(p¯ (T ) ) → γ ≈ 0.495 (so g ∝ 1/T), while the last iterate falls to the double-precision floor. 0 50 100 150 200 250 300 iteration on the optimal face 10 8 10 7 10 6 10 5 10 4 10 3 10 2 Frank-Wolfe gap acceleration on the face, face 59 plain PG ( ) accelerated PG ( ) 10 0 10 1 face 10 0 10 1 10 2 face-p h ase iters to … view at source ↗
Figure 4
Figure 4. Figure 4: The accelerated facial phase. Left: accelerated versus plain projected gradient on an instance with κ ≈ 59 (gap versus face-phase iteration). Right: the face-phase count versus κ across random instances, scaling as κ 0.43 (accelerated) versus κ 0.87 (plain)—the √ κ rate of Theorem 5.5. 44 [PITH_FULL_IMAGE:figures/full_fig_p044_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: The accelerated (Theorem 5.5) versus facial Newton (Theorem 6.6) phase, four views. (a) Accuracy: face-phase iterations grow linearly in log(1/ε) for the accelerated phase and stay essentially flat (doubly logarithmic, log log(1/ε)) for the Newton phase (κ ≈ 8). (b) Conditioning: across random instances the accelerated count scales as √ κ (fit ∝ κ 0.47), whereas the Newton count is condition-free (flat), c… view at source ↗
Figure 6
Figure 6. Figure 6: End-to-end cost, including the ε-independent warm start C(A) (Lemma 5.3), all from the uniform start 1/n. (a) Total leverage queries versus accuracy: CCLY’s uniform average is Θ(1/ε) (cheaper only at crude accuracy, before our setup amortizes), whereas warm + accel and warm + Newton are C(A) plus a √ κ log(1/ε) resp. d 2 log log(1/ε) tail. (b) The same total decomposed: the warm start is a fixed floor, the… view at source ↗
read the original abstract

The John ellipsoid of a symmetric polytope $P=\{\mathbf{x}\in\mathbb{R}^d:\|\mathbf{A}\mathbf{x}\|_\infty\le1\}$, $\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+\varepsilon)$-approximation in $\Theta(\varepsilon^{-1}\log(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 $\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 the Frank-Wolfe gap $g(\mathbf{p})\le\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(\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 is an unconstrained self-concordant minimization whose Hessian the oracle recovers exactly, so damped Newton needs only $O(\log\log(1/\varepsilon))$ steps, for a total of $C(\mathbf{A})+O(d^2\log\log(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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 0 minor

Summary. The paper separates the complexity of leverage-score algorithms for (1+ε)-approximating the John ellipsoid of a symmetric polytope into certification, identification, and accuracy costs. In the equivalent D-optimal design formulation min_p∈Δ_n -log det(∑ p_i a_i a_i^T), it argues that the historical Θ(ε^{-1} log(n/d)) dependence arises solely from certification via uniform averaging of iterates (which yields gap Θ(1/T)), while directing the first-order leverage-score oracle at the last iterate yields C(A) + O(√κ log(1/ε)) queries via warm-started acceleration, and once the optimal face is identified the facial problem reduces to unconstrained self-concordant minimization whose Hessian is recovered exactly by the oracle, allowing damped Newton in O(log log(1/ε)) steps for a total of C(A) + O(d² log log(1/ε)) queries. The open problems identified are condition-free identification and lower bounds; accuracy is claimed not to be the obstruction.

Significance. If the separation and the facial-reduction claims hold, the work clarifies that accuracy is not the historical bottleneck and isolates the remaining identification cost as the key open question. It builds on standard self-concordant minimization and Frank-Wolfe gap analysis without introducing new parameters or ad-hoc axioms, and the doubly-logarithmic accuracy dependence (after an ε-independent setup) would be a concrete improvement over prior ε^{-1} bounds if the oracle-Hessian equivalence is justified.

major comments (1)
  1. [Abstract] Abstract, paragraph on D-optimal-design form and facial reduction: the central accuracy claim of C(A) + O(d² log log(1/ε)) queries rests on the assertion that 'once the optimal face is identified the facial problem is an unconstrained self-concordant minimization whose Hessian the oracle recovers exactly'. However, the same paragraph defines the leverage-score oracle as 'exactly the first-order oracle'. The Hessian of f(p) = -log det(∑ p_i a_i a_i^T) is the d×d matrix whose (j,k) entry involves sums over leverage scores weighted by a_j a_k^T terms; a first-order oracle returns only the gradient vector ∇f(p). No mechanism is provided for recovering the exact Hessian at the same per-query cost, which is required for the exact Newton step and the resulting O(log log(1/ε)) bound. This is load-bearing for the doubly-logarithmic accuracy claim.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful review and for isolating this load-bearing point on oracle capabilities. We respond below and will revise the manuscript.

read point-by-point responses

  1. Referee: [Abstract] Abstract, paragraph on D-optimal-design form and facial reduction: the central accuracy claim of C(A) + O(d² log log(1/ε)) queries rests on the assertion that 'once the optimal face is identified the facial problem is an unconstrained self-concordant minimization whose Hessian the oracle recovers exactly'. However, the same paragraph defines the leverage-score oracle as 'exactly the first-order oracle'. The Hessian of f(p) = -log det(∑ p_i a_i a_i^T) is the d×d matrix whose (j,k) entry involves sums over leverage scores weighted by a_j a_k^T terms; a first-order oracle returns only the gradient vector ∇f(p). No mechanism is provided for recovering the exact Hessian at the same per-query cost, which is required for the exact Newton step and the resulting O(log log(1/ε)) bound. This is load-bearing for the doubly-logarithmic accuracy claim.

    Authors: We agree that the abstract does not supply an explicit mechanism showing how the leverage-score oracle (defined there as returning only the gradient via leverages) yields the exact d×d Hessian at equivalent per-query cost. The claim that the facial problem permits exact damped Newton therefore lacks justification in the presented text. We will revise the manuscript to either (a) add the missing derivation showing how the oracle outputs permit exact Hessian recovery without extra asymptotic cost or (b) adjust the accuracy bound and remove the O(log log(1/ε)) claim if no such mechanism exists. Revision_made will be yes. revision: yes

Circularity Check

0 steps flagged

No circularity; derivation from standard oracle and self-concordant theory

full rationale

The paper's accuracy bound C(A) + O(d² log log(1/ε)) is obtained by invoking the definition of the leverage-score oracle as first-order, the Frank-Wolfe gap equivalence to the John guarantee, and textbook damped-Newton convergence on self-concordant problems once the face is identified. These steps rest on external optimization facts rather than any fitted parameter renamed as prediction, self-definitional loop, or load-bearing self-citation chain. No equation or claim reduces by construction to its own inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract provides no explicit free parameters, axioms, or invented entities; all claims rest on standard convex-optimization facts (self-concordance, Frank-Wolfe gap, leverage-score oracles) assumed from prior literature.

pith-pipeline@v0.9.1-grok · 5952 in / 1239 out tokens · 29475 ms · 2026-06-26T16:18:09.836632+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

81 extracted references · 15 linked inside Pith

  1. [1]

    Linear convergence of a modified

    Selin Damla Ahipa. Linear convergence of a modified. Optimization Methods and Software , volume =

  2. [2]

    Mahoney , title =

    Ahmed El Alaoui and Michael W. Mahoney , title =. Advances in Neural Information Processing Systems (NeurIPS) , year =. 1411.0306 , eprinttype =

    Pith/arXiv arXiv

  3. [3]

    Haeberly and Michael L

    Farid Alizadeh and Jean-Pierre A. Haeberly and Michael L. Overton , title =. Mathematical Programming , volume =

  4. [4]

    International Conference on Machine Learning (ICML) , year =

    Zeyuan Allen-Zhu and Yuanzhi Li and Aarti Singh and Yining Wang , title =. International Conference on Machine Learning (ICML) , year =. 1711.05174 , eprinttype =

    Pith/arXiv arXiv

  5. [5]

    More asymmetry yields faster matrix multiplication , booktitle =

    Josh Alman and Ran Duan and Virginia. More asymmetry yields faster matrix multiplication , booktitle =. 2025 , eprint =

    2025

  6. [6]

    ACM-SIAM Symposium on Discrete Algorithms (SODA) , year =

    Josh Alman and Virginia Vassilevska Williams , title =. ACM-SIAM Symposium on Discrete Algorithms (SODA) , year =. 2010.05846 , eprinttype =

    arXiv 2010

  7. [7]

    Anstreicher , title =

    Kurt M. Anstreicher , title =. SIAM Journal on Optimization , volume =

  8. [8]

    SIAM Journal on Matrix Analysis and Applications , volume =

    Haim Avron and Christos Boutsidis , title =. SIAM Journal on Matrix Analysis and Applications , volume =

  9. [9]

    SIAM Journal on Imaging Sciences , volume =

    Amir Beck and Marc Teboulle , title =. SIAM Journal on Imaging Sciences , volume =

  10. [10]

    Bomze and Francesco Rinaldi and Damiano Zeffiro , title =

    Immanuel M. Bomze and Francesco Rinaldi and Damiano Zeffiro , title =. SIAM Journal on Optimization , volume =

  11. [11]

    2016 , note =

    Vladimir Braverman and Dan Feldman and Harry Lang and Adiel Statman and Samson Zhou , title =. 2016 , note =

    2016

  12. [12]

    Woodruff and Samson Zhou , title =

    Vladimir Braverman and Petros Drineas and Cameron Musco and Christopher Musco and Jalaj Upadhyay and David P. Woodruff and Samson Zhou , title =. IEEE Symposium on Foundations of Computer Science (FOCS) , year =. 1805.03765 , eprinttype =

    arXiv

  13. [13]

    Stephen Boyd and Lieven Vandenberghe , title =

  14. [14]

    International Conference on Artificial Intelligence and Statistics (AISTATS) , year =

    Daniele Calandriello and Alessandro Lazaric and Michal Valko , title =. International Conference on Artificial Intelligence and Statistics (AISTATS) , year =. 1803.10172 , eprinttype =

    Pith/arXiv arXiv

  15. [15]

    Advances in Neural Information Processing Systems (NeurIPS) , year =

    Yang Cao and Xiaoyu Li and Zhao Song and Xin Yang and Tianyi Zhou , title =. Advances in Neural Information Processing Systems (NeurIPS) , year =. 2211.14407 , eprinttype =

    arXiv

  16. [16]

    Wainwright and Bin Yu , title =

    Yuansi Chen and Raaz Dwivedi and Martin J. Wainwright and Bin Yu , title =. Journal of Machine Learning Research , volume =

  17. [17]

    Woodruff and Samson Zhou , title =

    Yeshwanth Cherapanamjeri and Sandeep Silwal and David P. Woodruff and Samson Zhou , title =. ACM-SIAM Symposium on Discrete Algorithms (SODA) , year =. 2211.09964 , eprinttype =

    arXiv

  18. [18]

    Clarkson and David P

    Kenneth L. Clarkson and David P. Woodruff , title =. ACM Symposium on Theory of Computing (STOC) , year =. 1207.6365 , eprinttype =

    Pith/arXiv arXiv

  19. [19]

    Cohen and Richard Peng , title =

    Michael B. Cohen and Richard Peng , title =. ACM Symposium on Theory of Computing (STOC) , year =

  20. [20]

    Cohen and Yin Tat Lee and Cameron Musco and Christopher Musco and Richard Peng and Aaron Sidford , title =

    Michael B. Cohen and Yin Tat Lee and Cameron Musco and Christopher Musco and Richard Peng and Aaron Sidford , title =. Innovations in Theoretical Computer Science (ITCS) , year =. 1408.5099 , eprinttype =

    Pith/arXiv arXiv

  21. [21]

    Cohen and Cameron Musco and Jakub Pachocki , title =

    Michael B. Cohen and Cameron Musco and Jakub Pachocki , title =. International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) , year =. 1604.05448 , eprinttype =

    Pith/arXiv arXiv

  22. [22]

    Cohen and Ben Cousins and Yin Tat Lee and Xin Yang , title =

    Michael B. Cohen and Ben Cousins and Yin Tat Lee and Xin Yang , title =. Conference on Learning Theory (COLT) , year =. 1905.11580 , eprinttype =

    arXiv 1905

  23. [23]

    Cohen and Cameron Musco and Christopher Musco , title =

    Michael B. Cohen and Cameron Musco and Christopher Musco , title =. ACM-SIAM Symposium on Discrete Algorithms (SODA) , year =. 1511.07263 , eprinttype =

    Pith/arXiv arXiv

  24. [24]

    Leveraged volume sampling for linear regression , booktitle =

    Micha. Leveraged volume sampling for linear regression , booktitle =. 2018 , eprint =

    2018

  25. [25]

    Determinantal point processes in randomized numerical linear algebra , journal =

    Micha. Determinantal point processes in randomized numerical linear algebra , journal =. 2021 , eprint =

    2021

  26. [26]

    Mathematical Programming , volume =

    Radu-Alexandru Dragomir and Adrien Taylor and Alexandre d'Aspremont and J\'er\^ome Bolte , title =. Mathematical Programming , volume =. 2022 , eprint =

    2022

  27. [27]

    Mahoney and S

    Petros Drineas and Michael W. Mahoney and S. Muthukrishnan , title =. ACM-SIAM Symposium on Discrete Algorithms (SODA) , year =

  28. [28]

    Mahoney and S

    Petros Drineas and Michael W. Mahoney and S. Muthukrishnan and Tam\'as Sarl\'os , title =. Numerische Mathematik , volume =. 2011 , eprint =

    2011

  29. [29]

    Mahoney and David P

    Petros Drineas and Malik Magdon-Ismail and Michael W. Mahoney and David P. Woodruff , title =. Journal of Machine Learning Research , volume =. 2012 , eprint =

    2012

  30. [30]

    Mahoney , title =

    Petros Drineas and Michael W. Mahoney , title =. Communications of the ACM , volume =

  31. [31]

    ACM-SIAM Symposium on Discrete Algorithms (SODA) , year =

    Maryam Fazel and Yin Tat Lee and Swati Padmanabhan and Aaron Sidford , title =. ACM-SIAM Symposium on Discrete Algorithms (SODA) , year =. 2110.15563 , eprinttype =

    arXiv

  32. [32]

    ACM Symposium on Theory of Computing (STOC) , year =

    Dan Feldman and Michael Langberg , title =. ACM Symposium on Theory of Computing (STOC) , year =. 1106.1379 , eprinttype =

    Pith/arXiv arXiv

  33. [33]

    2018 , note =

    Adam Gustafson and Hariharan Narayanan , title =. 2018 , note =

    2018

  34. [34]

    Gutman and Javier F

    David H. Gutman and Javier F. Pe\ na , title =. Mathematical Programming , year =. 1812.10198 , eprinttype =

    arXiv

  35. [35]

    Tropp , title =

    Nathan Halko and Per-Gunnar Martinsson and Joel A. Tropp , title =. SIAM Review , volume =

  36. [36]

    Computational Optimization and Applications , volume =

    Filip Hanzely and Peter Richt\'arik and Lin Xiao , title =. Computational Optimization and Applications , volume =

  37. [37]

    2024 , note =

    Elizabeth Harris and Ali Eshragh and Bishnu Lamichhane and Jordan Shaw-Carmody and Elizabeth Stojanovski , title =. 2024 , note =

    2024

  38. [38]

    Khachiyan , title =

    Leonid G. Khachiyan , title =. Mathematics of Operations Research , volume =

  39. [39]

    Khachiyan and Michael J

    Leonid G. Khachiyan and Michael J. Todd , title =. Mathematical Programming , volume =

  40. [40]

    Canadian Journal of Mathematics , volume =

    Jack Kiefer and Jacob Wolfowitz , title =. Canadian Journal of Mathematics , volume =

  41. [41]

    ACM Transactions on Algorithms , volume =

    Ioannis Koutis and Alex Levin and Richard Peng , title =. ACM Transactions on Algorithms , volume =. 2016 , eprint =

    2016

  42. [42]

    Alper Y ld r m , title =

    Piyush Kumar and E. Alper Y ld r m , title =. Journal of Optimization Theory and Applications , volume =

  43. [43]

    Advances in Neural Information Processing Systems (NeurIPS) , year =

    Simon Lacoste-Julien and Martin Jaggi , title =. Advances in Neural Information Processing Systems (NeurIPS) , year =

  44. [44]

    Miller and Richard Peng , title =

    Mu Li and Gary L. Miller and Richard Peng , title =. IEEE Symposium on Foundations of Computer Science (FOCS) , year =. 1211.2713 , eprinttype =

    Pith/arXiv arXiv

  45. [45]

    IEEE Symposium on Foundations of Computer Science (FOCS) , year =

    Yin Tat Lee and Aaron Sidford and Sam Chiu-wai Wong , title =. IEEE Symposium on Foundations of Computer Science (FOCS) , year =

  46. [46]

    Freund and Yurii Nesterov , title =

    Haihao Lu and Robert M. Freund and Yurii Nesterov , title =. SIAM Journal on Optimization , volume =

  47. [47]

    SIAM Journal on Matrix Analysis and Applications , volume =

    Zhaosong Lu and Ting Kei Pong , title =. SIAM Journal on Matrix Analysis and Applications , volume =. 2013 , eprint =

    2013

  48. [48]

    Conference on Learning Theory (COLT) , year =

    Vivek Madan and Mohit Singh and Uthaipon Tantipongpipat and Weijun Xie , title =. Conference on Learning Theory (COLT) , year =

  49. [49]

    Mahoney and Petros Drineas , title =

    Michael W. Mahoney and Petros Drineas , title =. Proceedings of the National Academy of Sciences , volume =

  50. [50]

    Mahoney , title =

    Michael W. Mahoney , title =. Foundations and Trends in Machine Learning , volume =. 2011 , eprint =

    2011

  51. [51]

    Tropp , title =

    Per-Gunnar Martinsson and Joel A. Tropp , title =. Acta Numerica , volume =

  52. [52]

    Mahoney , title =

    Xiangrui Meng and Michael W. Mahoney , title =. ACM Symposium on Theory of Computing (STOC) , year =. 1210.3135 , eprinttype =

    Pith/arXiv arXiv

  53. [53]

    KI---K\"unstliche Intelligenz , volume =

    Alexander Munteanu and Chris Schwiegelshohn , title =. KI---K\"unstliche Intelligenz , volume =

  54. [54]

    Mahoney and N

    Riley Murray and James Demmel and Michael W. Mahoney and N. Benjamin Erichson and Maksim Melnichenko and Osman Asif Malik and Laura Grigori and Piotr Luszczek and Micha. Randomized numerical linear algebra: a perspective on the field with an eye to software , year =

  55. [55]

    Advances in Neural Information Processing Systems (NeurIPS) , year =

    Cameron Musco and Christopher Musco , title =. Advances in Neural Information Processing Systems (NeurIPS) , year =. 1605.07583 , eprinttype =

    Pith/arXiv arXiv

  56. [56]

    Nguyen , title =

    Jelani Nelson and Huy L. Nguyen , title =. IEEE Symposium on Foundations of Computer Science (FOCS) , year =. 1211.1002 , eprinttype =

    Pith/arXiv arXiv

  57. [57]

    Optimization Methods and Software , volume =

    Arkadi Nemirovski , title =. Optimization Methods and Software , volume =

  58. [58]

    Yurii Nesterov and Arkadii Nemirovskii , title =

  59. [59]

    Yurii Nesterov , title =

  60. [60]

    ACM-SIAM Symposium on Discrete Algorithms (SODA) , year =

    Aleksandar Nikolov and Mohit Singh and Uthaipon Tao Tantipongpipat , title =. ACM-SIAM Symposium on Discrete Algorithms (SODA) , year =. 1802.08318 , eprinttype =

    Pith/arXiv arXiv

  61. [61]

    Ortega and Werner C

    James M. Ortega and Werner C. Rheinboldt , title =. 1970 , note =

    1970

  62. [62]

    Pe\ na and Daniel Rodr\'iguez , title =

    Javier F. Pe\ na and Daniel Rodr\'iguez , title =. Mathematics of Operations Research , volume =

  63. [63]

    Friedrich Pukelsheim , title =

  64. [64]

    Advances in Neural Information Processing Systems (NeurIPS) , year =

    Alessandro Rudi and Raffaello Camoriano and Lorenzo Rosasco , title =. Advances in Neural Information Processing Systems (NeurIPS) , year =. 1507.04717 , eprinttype =

    Pith/arXiv arXiv

  65. [65]

    IEEE Symposium on Foundations of Computer Science (FOCS) , year =

    Tam\'as Sarl\'os , title =. IEEE Symposium on Foundations of Computer Science (FOCS) , year =

  66. [66]

    Conference on Parsimony and Learning (CPAL) , year =

    Xiaoyu Li and Yingyu Liang and Zhenmei Shi and Zhao Song and Junwei Yu , title =. Conference on Parsimony and Learning (CPAL) , year =. 2408.06395 , eprinttype =

    arXiv

  67. [67]

    2024 , note =

    Xiaoyu Li and Zhao Song and Junwei Yu , title =. 2024 , note =

    2024

  68. [68]

    Woodruff and Lichen Zhang , title =

    Zhao Song and David P. Woodruff and Lichen Zhang , title =. 2025 , note =

    2025

  69. [69]

    International Conference on Learning Representations (ICLR) , year =

    Zhao Song and Shenghao Xie and Samson Zhou , title =. International Conference on Learning Representations (ICLR) , year =. 2510.03678 , eprinttype =

    arXiv

  70. [70]

    Spielman and Nikhil Srivastava , title =

    Daniel A. Spielman and Nikhil Srivastava , title =. ACM Symposium on Theory of Computing (STOC) , year =. 0803.0929 , eprinttype =

    Pith/arXiv arXiv

  71. [71]

    Michael Titterington , title =

    D. Michael Titterington , title =. Proc.\ 1976 Conference on Information Sciences and Systems , publisher =

    1976

  72. [72]

    Todd and E

    Michael J. Todd and E. Alper Y ld r m , title =. Discrete Applied Mathematics , volume =

  73. [73]

    Todd , title =

    Michael J. Todd , title =

  74. [74]

    Tropp , title =

    Joel A. Tropp , title =. Advances in Adaptive Data Analysis , volume =. 2011 , eprint =

    2011

  75. [75]

    New bounds for matrix multiplication: from alpha to omega , booktitle =

    Virginia. New bounds for matrix multiplication: from alpha to omega , booktitle =. 2024 , eprint =

    2024

  76. [76]

    Journal of Machine Learning Research , volume =

    Yining Wang and Adams Wei Yu and Aarti Singh , title =. Journal of Machine Learning Research , volume =. 2017 , eprint =

    2017

  77. [77]

    Woodruff , title =

    David P. Woodruff , title =. Foundations and Trends in Theoretical Computer Science , volume =. 2014 , eprint =

    2014

  78. [78]

    Woodruff and Taisuke Yasuda , title =

    David P. Woodruff and Taisuke Yasuda , title =. ACM-SIAM Symposium on Discrete Algorithms (SODA) , year =. 2207.08268 , eprinttype =

    arXiv

  79. [79]

    Woodruff and Taisuke Yasuda , title =

    David P. Woodruff and Taisuke Yasuda , title =. Advances in Neural Information Processing Systems (NeurIPS) , year =. 2501.01801 , eprinttype =

    arXiv

  80. [80]

    The Annals of Statistics , volume =

    Yaming Yu , title =. The Annals of Statistics , volume =. 2010 , eprint =

    2010

Showing first 80 references.