Pith. sign in

REVIEW 2 major objections 6 minor 81 references

The sharp SAT/UNSAT phase transition in random ellipsoid fitting

T0 review · 2 major / 6 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper proves that $n$ independent standard Gaussian points in $\mathbb{R}^d$ admit an exact centered ellipsoid fit with high probability exactly when $n/d^2<1/4$, and almost never when $n/d^2>1/4$.

desk verdict The paper proves the sharp SPW ellipsoid-fitting threshold at n ~ d^2/4, closing both gaps in Bandeira–Maillard; the only real weakness is that the unsatisfiable phase leans on a sketched universality extension (Prop 4.8) that deserves a full proof. read the letter →

arxiv 2608.10184 v1 pith:NXKCEPWH submitted 2026-08-10 math.PR cond-mat.dis-nncs.DSmath.STstat.MLstat.TH

Theodor Misiakiewicz , Garrett G. Wen This is my paper · ORCID
classification math.PRcond-mat.dis-nncs.DSmath.STstat.MLstat.TH MSC 60B2060D0590C2252A22
keywords ellipsoidfittingphasetransitionrandomsemidefiniteprogramGaussianequivalencestatisticaldimensionconicintegralgeometrymatricesuniversality
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper settles a decade-old conjecture about when $n$ independent standard Gaussian points in $\mathbb{R}^d$ all lie on the boundary of a common centered ellipsoid. The answer is sharp: if the density $n/d^2$ stays below $1/4$, a fitting positive-semidefinite matrix $S$ exists with probability tending to one, and can be chosen well-conditioned with all eigenvalues in a fixed interval; if $n/d^2$ stays above $1/4$, with probability tending to one no fit exists, even allowing wildly elongated ellipsoids. The threshold is the statistical dimension $d(d+1)/4$ of the positive semidefinite cone, and the proof transfers a Gaussian-surrogate phase transition to the exact, spectrally unrestricted problem.

What carries the argument

The argument runs through a Gaussian-comparison transfer from a surrogate problem with GOE measurements to the actual rank-one quadratic measurements. On the satisfiable side, the key object is a head–tail decomposition of the dual vector: coordinates with large magnitude are collected into a sparse head whose constraints are solved exactly using the quadratic feature Gram matrix, whose two-sided singular values are of order $d$ throughout $n/d^2<1/2$; the remaining low-influence tail is compared to its Gaussian counterpart through a second-order Lindeberg principle. On the unsatisfiable side, any candidate $S$ is split into a low-rank spectral head $H$ (eigenvalues above $d^{-1/4}$) and a Schatten-3 diffuse bulk $B$; conditioning on the head and replacing the bulk quadratic form by $\sqrt{m}$ times a GOE inner product produces a hybrid model, and an escape-through-a-mesh inequality yields a uniform positive risk gap for the hybrid model, which is then transferred back exactly. The constant $1/4$ enters only where the Gaussian width $d/2$ of the scaled positive semidefinite cap crosses $\sqrt{n}$.

What would settle it

Run the free-entropy comparison of Proposition 4.8 in the smallest non-degenerate case, say $n=1$, $m=2$, with a nonzero offset $a_1$ and the full Schatten-constrained set $C_m$; the proposition predicts the difference between the quadratic-chaos and GOE ground states vanishes as $m\to\infty$. A non-vanishing difference for any such offset would refute the bulk-universality step and with it the upper-bound theorem.

Watch

Extended reading notes

Core claim

The central discovery is that the exact feasibility problem for random quadratic constraints has the same threshold as its Gaussian surrogate: no spectral bound on the candidate matrix $S$ is needed, and no error tolerance is needed. Theorem 1.2 states that if $\limsup n/d^2 < 1/4$ then with probability tending to one there exists $S \succeq 0$ with $x_i^\top S x_i = d$ for all $i$, and if $\liminf n/d^2 > 1/4$ then with probability tending to one no such $S$ exists. In the satisfiable regime the proof yields more: for every fixed $\alpha<1/4$, one can take $S$ with $\lambda_- I \preceq S \preceq \lambda_+ I$ for constants depending only on $\alpha$ and with $\mathrm{Tr}\,S = d$, so the fitted ellipsoid's axes stay within constant factors of the sphere. In the unsatisfiable regime, the obstruction is uniform: an exponentially decaying loss gap holds over all trace-one PSD matrices without any operator-norm restriction. The same theorem, through the conic duality formulated in the paper, gives the sharp threshold for the alternative statement about the nonexistence or existence of balanced positive definite combinations of the random rank-one matrices.

Load-bearing premise

The unsatisfiable phase depends on an asserted rowwise extension of a previously proven free-entropy universality to losses with arbitrary deterministic offsets (Proposition 4.8); the paper says this extension is only sketched, and if it fails the no-fit conclusion for $n/d^2>1/4$ does not follow.

Editorial extensions

If this is right

  • For the dual problem, if $\limsup n/d^2<1/4$ then with probability tending to one no vector $y$ with $\sum_i y_i=0$ and $\sum_i y_i x_i x_i^\top \succ 0$ exists, while if $\liminf n/d^2>1/4$ such a vector exists.
  • In the satisfiable regime the proof produces a fit with $\lambda_- I \preceq S \preceq \lambda_+ I$ and $\mathrm{Tr}\,S=d$, so the semiaxes of the fitted ellipsoid stay within constant factors of the sphere's radius.
  • In the unsatisfiable regime the obstruction is quantitative: the empirical risk $\frac{1}{n}\sum_i (1-e^{-(x_i^\top S x_i - \mathrm{Tr}S - b)^2})$ is bounded below by a constant $e_\gamma>0$ uniformly over all $S\succeq0$ with $\|S\|_F=1$ and $|b|\le C_\gamma$, with probability exponentially close to one.
  • For a Haar-random rank-$r$ subspace of $\mathbb{R}^N$, minimum trace factor analysis succeeds with high probability when $N-r \ge (2+\varepsilon)\sqrt{N}$ and fails when $N-r \le (2-\varepsilon)\sqrt{N}$.
  • The canonical SDP relaxation of vector discrepancy certifies no nontrivial lower bound once the equivalent ellipsoid problem becomes infeasible.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The proof technique should transfer to other exact feasibility questions with rank-one or quadratic measurements, such as phase retrieval or matrix sensing, where Gaussian-surrogate thresholds are known but exact feasibility with no spectral restrictions has been open; the head-tail and head-bulk conditional Gaussianization is a plausible general repair mechanism.
  • The existence result below threshold does not settle the typical-solution structure predicted by replica theory, such as half the semiaxes diverging at criticality; the proof guarantees an atypical well-conditioned fit, so the typical geometry at the boundary remains open.
  • The sharpness at exactly $n=d^2/4$—the width of the crossover window and the finite-$d$ corrections—is not addressed; a natural conjecture from the statistical-dimension calculation is that the crossover has width of order $d^{3/2}$ or $d\log d$, and the proof's estimates could likely be sharpened to locate it.
  • The asserted rowwise extension of free-entropy universality to translated losses (used for the unsatisfiable phase) can be tested on small systems, and a nonvanishing discrepancy there would de-risk the entire upper-bound argument.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 6 minor

Summary. The paper proves the Saunderson–Parrilo–Willsky ellipsoid fitting conjecture: for n independent standard Gaussian vectors in R^d, exact feasibility of S ⪰ 0 with x_i^T S x_i = d for all i exhibits a sharp phase transition at n ~ d^2/4. Theorem 1.2 gives existence with probability tending to one when lim sup n/d^2 < 1/4, and nonexistence when lim inf n/d^2 > 1/4, with no spectral restriction on the fitted matrix. Theorem 1.3 strengthens the satisfiable phase to a well-conditioned fit, and Corollary 1.4 gives the equivalent threshold for balanced positive definite combinations. The satisfiable side is proved by a dual separation argument with an explicit head–tail decomposition of the dual vector, exact head correction, a second-order chaos Lindeberg principle, and a careful net argument. The unsatisfiable side splits a candidate matrix into a low-rank spectral head and a Schatten-3 diffuse bulk, Gaussianizes the bulk conditionally on the head, proves a uniform positive risk gap in a hybrid model via Gordon's escape theorem, and transfers the gap back to the original model via a translated-loss bulk universality proposition.

Significance. If correct, this is a major result: it resolves a long-standing conjecture with a sharp, parameter-free threshold that emerges from the statistical dimension d(d+1)/4 of the PSD cone (Lemma 2.1), and it closes the two gaps left by Bandeira and Maillard — exact fitting and the removal of the operator-norm constraint. The satisfiable side is carefully developed, with explicit lemmas, quantitative condition-number bounds, and a self-contained Gaussian comparison principle. The unsatisfiable side has a clear and credible architecture, but its central transferred-loss universality result, Proposition 4.8, is only sketched as a rowwise modification of an external theorem. Because that proposition is load-bearing for the no-fit phase, the paper is not fully supported as written.

major comments (2)
  1. [§4.2, Prop. 4.8 (used in Prop. 4.3, Prop. 4.5, Thm. 4.1)] The proof of Proposition 4.8 is not supplied. The paper states that [BM25, Theorem 4.6], asserted for a common row loss, extends rowwise to losses ℓ_i(u)=βφ(a_i+u) with arbitrary deterministic offsets, finite priors A_m⊂T_m, and uniformity over n≤Λm², and that only the differences are sketched. This is load-bearing: Proposition 4.3 uses that uniformity to compare the ellipsoid bulk with the Gaussian bulk for every deterministic offset, and Lemma 4.12 then applies it conditionally on every head realization in E_U, Eq. (143). In the application the offsets a_i = g_i^T H g_i − TrH − b are neither centered nor bounded a priori, so any use of centering, boundedness of the loss argument, or a row-independent prior in [BM25, Theorem 4.6] would invalidate (143). If this extension fails, the no-fit conclusion for lim inf n/d^2 > 1/4 does not follow. Please provide a complete proof of Proposition 4.8, or a precise verification that all hypotheses of [BM25, Theorem 4.6] hold rowwise and uniformly over the offsets and priors used in Section 4.
  2. [§4.1 and §4.2, Prop. 4.3] Proposition 4.3 is stated as a supremum over arbitrary deterministic offsets and closed subsets of B_m(C0,κ), and this uniformity is essential for the net transfer in Section 4.4. The proof via Lemma 4.9 relies on the feature-edge events (27) and Proposition 2.8, but the text does not explicitly verify that the required uniformity over n/m² ∈ [ε,1/2−ε] and over the offset-dependent subsets C_U(H) is preserved when Lemma 4.12 conditions on every head realization in E_U. Please state and justify the uniformity claim for (103) at the level of detail used elsewhere in the paper, so that the conditional o(1) in Lemma 4.12, Eq. (143), is unambiguous.
minor comments (6)
  1. [§2.3, Prop. 2.8] The norm ∥G∥_{F→2} is used without definition; please define it as the operator norm from (S^p, ∥·∥_F) to (R^n, ∥·∥_2).
  2. [References] The reference [Sau11] lists the author as 'James James Francis Saunderson'; the duplicated first name appears to be a typo. The citation '[R V13]' should be '[RV13]'.
  3. [§2.2, Lemma 2.4] The sentence 'Lemma 2.4 also follows from the argument used for Lemma 2.3' is vague and unproved; since Lemma 2.4 is a standard Gordon escape estimate, either give a precise citation with the stated form or delete the sentence.
  4. [§4.1, Eq. (107)] The notation O_τ(d^{3/2}) is introduced without explicit definition; state that the implied constant depends only on τ, and similarly for other subscripted constants in the net-entropy estimates.
  5. [§3.4, Lemma 3.9] The statement of the second-chaos interpolation lemma uses the quantity R_{N,d} = E max_i ∥x_i∥_2^2; it would be helpful to note explicitly that this quantity is finite and uniform in the conditioning used later in Proposition 3.4, since the tail rows are not conditioned.
  6. [Acknowledgments] The disclosure of AI use is transparent and does not affect the mathematical assessment.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the 1/4 threshold is computed from the PSD-cone Gaussian width, and the only self-citation is motivational.

full rationale

The central constant 1/4 is not imported from a fit or from the conclusion: Lemma 2.1 computes the statistical dimension of the PSD cone as d(d+1)/4 via Moreau decomposition and standard width bounds, and Gordon's inequalities convert this into the sharp n ~ d^2/4 comparison. On the satisfiable side, Proposition 3.3 and the low-influence tail margin (Proposition 3.4) are proved in-paper: the head corrections use the feature-edge estimate Proposition 2.8, which is proved from the external KNH25 spectral-edge theorem and elementary data bounds, and the Gaussian transfer is a self-contained Lindeberg/interpolation argument (Lemmas 3.9–3.12). On the unsatisfiable side, the hybrid-model risk gap (Proposition 4.4) is derived from Gordon's escape theorem and in-paper small-ball/VC estimates, not from the no-fit conclusion. The universality transfer used to pass from the hybrid model to the ellipsoid model (Propositions 4.3 and 4.8) is imported from the external Bandeira–Maillard [BM25] theorem and asserted, rather than fully proved, to extend to row-dependent offsets and Schatten-3-constrained priors; that is a correctness/completeness risk, not a circular reduction, because the cited theorem is external and its assumptions do not include the target ellipsoid-fitting threshold. The paper's only self-citation, [WHL+25], is used purely as methodological motivation ('our conditional decompositions are more directly inspired by'), not as a load-bearing theorem; nothing in the proof of Theorem 1.2 reduces by construction to a fitted parameter, a self-defining quantity, or a self-citation chain.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No free parameters are fitted to data; all constants in the proof are chosen from inequalities and can be set explicitly. No new entities are postulated. The central claim rests on standard Gaussian comparison machinery plus two external theorems, the KNH25 feature edge and the BM25 free-entropy universality, the latter invoked in a sketched extended form.

assumptions (4)
  • standard math Sharp two-sided spectral edge for polynomial-scaling kernel random matrices (KNH25, Theorem 1.2(2a))
    Used in Proposition 2.8 and Corollary 2.9 to show the quadratic feature Gram matrix satisfies c d I <= QQ^* <= C d I for n/d^2 < 1/2; the paper cites rather than proves this theorem.
  • standard math Free-entropy universality of Bandeira-Maillard (BM25, Theorem 4.6) and its rowwise extension to translated losses
    Proposition 4.8 asserts a modification of this theorem for losses beta * phi(a_i + u) with deterministic offsets; the proof is only sketched. It underlies the bulk universality in Proposition 4.3.
  • standard math Gordon's Gaussian min-max and escape-through-a-mesh theorems
    Lemma 2.3 is proved in the text; Lemma 2.4 is used in its classical form. These are standard tools in convex Gaussian analysis.
  • standard math Standard concentration inequalities: Gaussian concentration, Hanson-Wright, matrix Bernstein, VC uniform deviation, measurable maximum theorem
    Used throughout Sections 2 through 4 for net arguments, spectral estimates, small-ball bounds, and measurable selection.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The sharp SAT/UNSAT phase transition in random ellipsoid fitting." pith.science (2026). https://pith.science/paper/NXKCEPWH

@misc{pith2026260810184,
  author       = {Pith},
  title        = {Pith review of: The sharp SAT/UNSAT phase transition in random ellipsoid fitting},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NXKCEPWH}},
  note         = {Machine review of arXiv:2608.10184}
}
abstract

Let $x_1,\ldots,x_n$ be independent standard Gaussian vectors in $\mathbb{R}^d$. An \emph{ellipsoid fit} is a matrix $S \succeq 0$ such that $x_i^\top S x_i =d$ for every $i$, so that all the points lie on the boundary of the centered ellipsoid $\{ x : x^\top S x = d\}$. Saunderson, Parrilo and Willsky conjectured that, as $n,d \to \infty$, this semidefinite feasibility problem undergoes a sharp transition at $n \sim d^2/4$. We prove this conjecture. If $\lim \sup n/d^2 = \alpha^* <1/4$, then, with probability tending to one, an ellipsoid fit exists; moreover, one can choose $S$ with all eigenvalues in a fixed interval $[\lambda_- , \lambda_+] \subset (0,\infty)$ depending only on $\alpha^*$. Conversely, if $\lim \inf n/d^2 > 1/4$, then, with probability tending to one, no ellipsoid fit exists, without any spectral restriction. Our proof builds on the Gaussian-equivalence framework developed by Bandeira and Maillard (2025) and closes the two gaps left open in their work: establishing exact fitting and removing the operator-norm constraint. On the satisfiable side, the new ingredients are a head-tail decomposition of the dual vector, exact correction of the sparse head constraints, and a Gaussian comparison principle for the low-influence tail. On the unsatisfiable side, we split a candidate into a low-rank spectral head and a Schatten-3 diffuse bulk, Gaussianize the bulk conditionally on the head, and apply a projected Gordon escape argument. The threshold is governed by the statistical dimension $d(d+1)/4$ of the positive semidefinite cone.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

81 extracted references · 58 canonical work pages

  1. [1]

    2011 , school=

    Subspace identification via convex optimization , author=. 2011 , school=

    2011

  2. [2]

    SIAM Journal on Matrix Analysis and Applications , volume=

    Diagonal and low-rank matrix decompositions, correlation matrices, and ellipsoid fitting , author=. SIAM Journal on Matrix Analysis and Applications , volume=. 2012 , publisher=

    work page 2012

  3. [3]

    52nd IEEE Conference on Decision and Control , pages=

    Diagonal and low-rank decompositions and fitting ellipsoids to random points , author=. 52nd IEEE Conference on Decision and Control , pages=. 2013 , organization=

    work page 2013

  4. [4]

    The Thirty Sixth Annual Conference on Learning Theory , pages=

    Near-optimal fitting of ellipsoids to random points , author=. The Thirty Sixth Annual Conference on Learning Theory , pages=. 2023 , organization=

    work page 2023

  5. [5]

    Information and Inference: A Journal of the IMA , volume=

    Living on the edge: Phase transitions in convex programs with random data , author=. Information and Inference: A Journal of the IMA , volume=. 2014 , publisher=

    2014

  6. [6]

    2010 , publisher=

    An introduction to random matrices , author=. 2010 , publisher=

    2010

  7. [7]

    Israel Journal of Mathematics , volume=

    Some inequalities for Gaussian processes and applications , author=. Israel Journal of Mathematics , volume=. 1985 , publisher=

    1985

  8. [8]

    On Milman's inequality and random subspaces which escape through a mesh in

    Gordon, Yehoram , journal=. On Milman's inequality and random subspaces which escape through a mesh in. 1988 , publisher=

    work page 1988

Show all 81 references
  1. [9]

    2013 , publisher=

    Concentration Inequalities: A Nonasymptotic Theory of Independence , author=. 2013 , publisher=

    2013

  2. [10]

    2018 , publisher=

    High-dimensional probability: An introduction with applications in data science , author=. 2018 , publisher=

    2018

  3. [11]

    Hanson-Wright inequality and sub-gaussian concentration , volume =

    Rudelson, Mark and Vershynin, Roman , year =. Hanson-Wright inequality and sub-gaussian concentration , volume =. Electronic Communications in Probability , doi =

  4. [12]

    2004 , publisher=

    Convex optimization , author=. 2004 , publisher=

    2004

  5. [13]

    2006 , publisher=

    Infinite dimensional analysis: a hitchhiker’s guide , author=. 2006 , publisher=

    2006

  6. [14]

    Random Matrices: Theory and Applications , volume=

    Extremal eigenvalues of random kernel matrices with polynomial scaling , author=. Random Matrices: Theory and Applications , volume=. 2025 , publisher=

    2025

  7. [15]

    Foundations and trends

    An introduction to matrix concentration inequalities , author=. Foundations and trends. 2015 , publisher=

    2015

  8. [16]

    IEEE Transactions on Information Theory , volume=

    Fitting an ellipsoid to random points: predictions using the replica method , author=. IEEE Transactions on Information Theory , volume=. 2024 , publisher=

    2024

  9. [18]

    Electronic Journal of Probability , volume=

    Exact threshold for approximate ellipsoid fitting of random points , author=. Electronic Journal of Probability , volume=. 2025 , publisher=

    2025

  10. [19]

    2013 , publisher=

    A probabilistic theory of pattern recognition , author=. 2013 , publisher=

    2013

  11. [20]

    Acta Mathematica , volume =

    The finite dimensional basis problem with an appendix on nets of Grassmann manifolds , author=. Acta Mathematica , volume =

  12. [21]

    Foundations of Computational mathematics , volume=

    The convex geometry of linear inverse problems , author=. Foundations of Computational mathematics , volume=. 2012 , publisher=

    2012

  13. [22]

    Sum-of-Squares Lower Bounds for Sherrington-Kirkpatrick via Planted Affine Planes , booktitle =

    Mrinalkanti Ghosh and Fernando Granha Jeronimo and Chris Jones and Aaron Potechin and Goutham Rajendran , editor =. Sum-of-Squares Lower Bounds for Sherrington-Kirkpatrick via Planted Affine Planes , booktitle =

  14. [23]

    A Nearly Tight Bound for Fitting an Ellipsoid to Gaussian Random Points , booktitle =

    Daniel Kane and Ilias Diakonikolas , editor =. A Nearly Tight Bound for Fitting an Ellipsoid to Gaussian Random Points , booktitle =

  15. [24]

    Fitting an ellipsoid to a quadratic number of random points , volume =

    Bandeira, Afonso and Maillard, Antoine and Mendelson, Shahar and Paquette, Elliot , year =. Fitting an ellipsoid to a quadratic number of random points , volume =. Latin American Journal of Probability and Mathematical Statistics , doi =

  16. [25]

    and Potechin, Aaron and Xu, Jeff , title =

    Hsieh, Jun-Ting and Kothari, Pravesh K. and Potechin, Aaron and Xu, Jeff , title =. 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) , volume =

    2023

  17. [26]

    2025 Symposium on Simplicity in Algorithms (SOSA) , pages =

    Madhur Tulsiani and June Wu , title =. 2025 Symposium on Simplicity in Algorithms (SOSA) , pages =. 2025 , publisher =

    2025

  18. [27]

    The Koml

    Nikolov, Aleksandar , journal=. The Koml

  19. [28]

    The 22nd international conference on artificial intelligence and statistics , pages=

    Overcomplete independent component analysis via SDP , author=. The 22nd international conference on artificial intelligence and statistics , pages=. 2019 , organization=

    2019

  20. [30]

    IEEE Transactions on Information Theory , volume=

    Universality laws for high-dimensional learning with random features , author=. IEEE Transactions on Information Theory , volume=. 2023 , doi=

    2023

  21. [33]

    Physical Review X , volume=

    Modeling the influence of data structure on learning in neural networks: The hidden manifold model , author=. Physical Review X , volume=. 2020 , publisher=

    2020

  22. [34]

    Physical Review E , volume=

    Gaussian universality of perceptrons with random labels , author=. Physical Review E , volume=. 2024 , publisher=

    2024

  23. [36]

    Mathematical and Scientific Machine Learning , pages=

    The gaussian equivalence of generative models for learning with shallow neural networks , author=. Mathematical and Scientific Machine Learning , pages=. 2022 , organization=

    2022

  24. [37]

    The Annals of Applied Probability , volume=

    Universality in polytope phase transitions and message passing algorithms , author=. The Annals of Applied Probability , volume=. 2015 , publisher=

    2015

  25. [38]

    Information and Inference: A Journal of the IMA , volume=

    Universality laws for randomized dimension reduction, with applications , author=. Information and Inference: A Journal of the IMA , volume=. 2018 , publisher=

    2018

  26. [39]

    The Annals of Statistics , volume=

    Universality of regularized regression estimators in high dimensions , author=. The Annals of Statistics , volume=. 2023 , publisher=

    2023

  27. [40]

    International Conference on Learning Representations , volume=

    The breakdown of Gaussian universality in classification of high-dimensional linear factor mixtures , author=. International Conference on Learning Representations , volume=

  28. [41]

    International Conference on Machine Learning , pages=

    Are Gaussian data all you need? The extents and limits of universality in high-dimensional generalized linear estimation , author=. International Conference on Machine Learning , pages=. 2023 , organization=

    2023

  29. [44]

    Advances in Neural Information Processing Systems , volume=

    The nuclear route: Sharp asymptotics of erm in overparameterized quadratic networks , author=. Advances in Neural Information Processing Systems , volume=

  30. [45]

    Charalambos D Aliprantis and Kim C Border, Infinite dimensional analysis: a hitchhiker’s guide, Springer, 2006

    2006

  31. [46]

    118, Cambridge university press, 2010

    Greg W Anderson, Alice Guionnet, and Ofer Zeitouni, An introduction to random matrices, no. 118, Cambridge university press, 2010

    2010

  32. [47]

    3, 224--294

    Dennis Amelunxen, Martin Lotz, Michael B McCoy, and Joel A Tropp, Living on the edge: Phase transitions in convex programs with random data, Information and Inference: A Journal of the IMA 3 (2014), no. 3, 224--294

    2014

  33. [48]

    Stéphane Boucheron, Gábor Lugosi, and Pascal Massart, Concentration inequalities: A nonasymptotic theory of independence, Oxford University Press, 2013

    2013

  34. [49]

    2, 753--822

    Mohsen Bayati, Marc Lelarge, and Andrea Montanari, Universality in polytope phase transitions and message passing algorithms, The Annals of Applied Probability 25 (2015), no. 2, 753--822

    2015

  35. [50]

    Afonso S Bandeira and Antoine Maillard, Exact threshold for approximate ellipsoid fitting of random points, Electronic Journal of Probability 30 (2025), 1--46

    2025

  36. [51]

    Afonso Bandeira, Antoine Maillard, Shahar Mendelson, and Elliot Paquette, Fitting an ellipsoid to a quadratic number of random points, Latin American Journal of Probability and Mathematical Statistics 21 (2024), 1835

    2024

  37. [52]

    Stephen Boyd and Lieven Vandenberghe, Convex optimization, Cambridge university press, 2004

    2004

  38. [53]

    6, 805--849

    Venkat Chandrasekaran, Benjamin Recht, Pablo A Parrilo, and Alan S Willsky, The convex geometry of linear inverse problems, Foundations of Computational mathematics 12 (2012), no. 6, 805--849

    2012

  39. [54]

    31, Springer Science & Business Media, 2013

    Luc Devroye, L \'a szl \'o Gy \"o rfi, and G \'a bor Lugosi, A probabilistic theory of pattern recognition, vol. 31, Springer Science & Business Media, 2013

    2013

  40. [55]

    Vittorio Erba, Emanuele Troiani, Lenka Zdeborov \'a , and Florent Krzakala, The nuclear route: Sharp asymptotics of erm in overparameterized quadratic networks, Advances in Neural Information Processing Systems 38 (2026), 88862--88901

    2026

  41. [56]

    954--965

    Mrinalkanti Ghosh, Fernando Granha Jeronimo, Chris Jones, Aaron Potechin, and Goutham Rajendran, Sum-of-squares lower bounds for sherrington-kirkpatrick via planted affine planes, 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, Novemb...

    2020

  42. [57]

    3, 034305

    Federica Gerace, Florent Krzakala, Bruno Loureiro, Ludovic Stephan, and Lenka Zdeborov \'a , Gaussian universality of perceptrons with random labels, Physical Review E 109 (2024), no. 3, 034305

    2024

  43. [58]

    426--471

    Sebastian Goldt, Bruno Loureiro, Galen Reeves, Florent Krzakala, Marc M \'e zard, and Lenka Zdeborov \'a , The gaussian equivalence of generative models for learning with shallow neural networks, Mathematical and Scientific Machine Learning, PMLR, 2022, pp. 426--471

    2022

  44. [59]

    4, 041044

    Sebastian Goldt, Marc M \'e zard, Florent Krzakala, and Lenka Zdeborov \'a , Modeling the influence of data structure on learning in neural networks: The hidden manifold model, Physical Review X 10 (2020), no. 4, 041044

    2020

  45. [60]

    4, 265--289

    Yehoram Gordon, Some inequalities for gaussian processes and applications, Israel Journal of Mathematics 50 (1985), no. 4, 265--289

    1985

  46. [61]

    , On milman's inequality and random subspaces which escape through a mesh in R ^n , Geometric Aspects of Functional Analysis (1988), 84

    1988

  47. [62]

    Kothari, Aaron Potechin, and Jeff Xu, Ellipsoid fitting up to a constant, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), vol

    Jun-Ting Hsieh, Pravesh K. Kothari, Aaron Potechin, and Jeff Xu, Ellipsoid fitting up to a constant, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), vol. 261, 2023

    2023

  48. [63]

    3, 1932--1964

    Hong Hu and Yue M Lu, Universality laws for high-dimensional learning with random features, IEEE Transactions on Information Theory 69 (2023), no. 3, 1932--1964

    2023

  49. [64]

    Hong Hu, Yue M Lu, and Theodor Misiakiewicz, Asymptotics of random feature regression beyond the linear scaling regime, arXiv:2403.08160 (2024)

    2024 arXiv

  50. [65]

    4, 1799--1823

    Qiyang Han and Yandi Shen, Universality of regularized regression estimators in high dimensions, The Annals of Statistics 51 (2023), no. 4, 1799--1823

    2023

  51. [66]

    195, PMLR , 2023, pp

    Daniel Kane and Ilias Diakonikolas, A nearly tight bound for fitting an ellipsoid to gaussian random points, The Thirty Sixth Annual Conference on Learning Theory, COLT 2023, 12-15 July 2023, Bangalore, India (Gergely Neu and Lorenzo Rosasco, eds.), Proceedings of Machine Lear...

    2023

  52. [67]

    04, 2550020

    David Kogan, Sagnik Nandy, and Jiaoyang Huang, Extremal eigenvalues of random kernel matrices with polynomial scaling, Random Matrices: Theory and Applications 14 (2025), no. 04, 2550020

    2025

  53. [68]

    10, 7273--7296

    Antoine Maillard and Dmitriy Kunisky, Fitting an ellipsoid to random points: predictions using the replica method, IEEE Transactions on Information Theory 70 (2024), no. 10, 7273--7296

    2024

  54. [69]

    2025, 2025, pp

    Xiaoyi Mai and Zhenyu Liao, The breakdown of gaussian universality in classification of high-dimensional linear factor mixtures, International Conference on Learning Representations, vol. 2025, 2025, pp. 7099--7130

    2025

  55. [70]

    Andrea Montanari, Feng Ruan, Basil Saeed, and Youngtak Sohn, Universality of max-margin classifiers, arXiv:2310.00176 (2023)

    2023 arXiv

  56. [71]

    Andrea Montanari and Basil Saeed, Universality of empirical risk minimization, arXiv:2202.08832 (2022)

    2022 arXiv

  57. [72]

    Aleksandar Nikolov, The koml \'o s conjecture holds for vector colorings , arXiv:1301.4039 (2013)

    2013 arXiv

  58. [73]

    3, 337--446

    Samet Oymak and Joel A Tropp, Universality laws for randomized dimension reduction, with applications, Information and Inference: A Journal of the IMA 7 (2018), no. 3, 337--446

    2018

  59. [74]

    27680--27708

    Luca Pesce, Florent Krzakala, Bruno Loureiro, and Ludovic Stephan, Are gaussian data all you need? the extents and limits of universality in high-dimensional generalized linear estimation, International Conference on Machine Learning, PMLR, 2023, pp. 27680--27708

    2023

  60. [75]

    2583--2592

    Anastasia Podosinnikova, Amelia Perry, Alexander S Wein, Francis Bach, Alexandre d’Aspremont, and David Sontag, Overcomplete independent component analysis via sdp, The 22nd international conference on artificial intelligence and statistics, PMLR, 2019, pp. 2583--2592

    2019

  61. [76]

    4235--4295

    Aaron Potechin, Paxton M Turner, Prayaag Venkat, and Alexander S Wein, Near-optimal fitting of ellipsoids to random points, The Thirty Sixth Annual Conference on Learning Theory, PMLR, 2023, pp. 4235--4295

    2023

  62. [77]

    Mark Rudelson and Roman Vershynin, Hanson-wright inequality and sub-gaussian concentration, Electronic Communications in Probability 18 (2013)

    2013

  63. [78]

    thesis, Massachusetts Institute of Technology, 2011

    James James Francis Saunderson, Subspace identification via convex optimization, Ph.D. thesis, Massachusetts Institute of Technology, 2011

    2011

  64. [79]

    4, 1395--1416

    James Saunderson, Venkat Chandrasekaran, Pablo A Parrilo, and Alan S Willsky, Diagonal and low-rank matrix decompositions, correlation matrices, and ellipsoid fitting, SIAM Journal on Matrix Analysis and Applications 33 (2012), no. 4, 1395--1416

    2012

  65. [80]

    6031--6036

    James Saunderson, Pablo A Parrilo, and Alan S Willsky, Diagonal and low-rank decompositions and fitting ellipsoids to random points, 52nd IEEE Conference on Decision and Control, IEEE, 2013, pp. 6031--6036

    2013

  66. [81]

    Stanislaw J Szarek, The finite dimensional basis problem with an appendix on nets of grassmann manifolds, Acta Mathematica 151 (1983), 153--179

    1983

  67. [82]

    Christos Thrampoulidis, Samet Oymak, and Babak Hassibi, The gaussian min-max theorem in the presence of convexity, arXiv:1408.4837 (2014)

    2014 arXiv

  68. [83]

    1-2, 1--230

    Joel A Tropp, An introduction to matrix concentration inequalities, Foundations and trends in machine learning 8 (2015), no. 1-2, 1--230

    2015

  69. [84]

    134--143

    Madhur Tulsiani and June Wu, Ellipsoid fitting up to constant via empirical covariance estimation, 2025 Symposium on Simplicity in Algorithms (SOSA), SIAM, 2025, pp. 134--143

    2025

  70. [85]

    47, Cambridge university press, 2018

    Roman Vershynin, High-dimensional probability: An introduction with applications in data science, vol. 47, Cambridge university press, 2018

    2018

  71. [86]

    Garrett G Wen, Hong Hu, Yue M Lu, Zhou Fan, and Theodor Misiakiewicz, When does gaussian equivalence fail and how to fix it: Non-universal behavior of random features with quadratic scaling, arXiv:2512.03325 (2025)

    2025

  72. [87]

    Yizhou Xu, Antoine Maillard, Lenka Zdeborov \'a , and Florent Krzakala, Fundamental limits of matrix sensing: Exact asymptotics, universality, and applications, arXiv:2503.14121 (2025)

    2025

  73. [88]

    Chiheb Yaakoubi, Cosme Louart, Malik Tiomoko, and Zhenyu Liao, Characterization of gaussian universality breakdown in high-dimensional empirical risk minimization, arXiv:2604.03146 (2026)

    2026 arXiv

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.