Pith. sign in

REVIEW 3 major objections 5 minor 47 references

Vanilla SGD provably cannot learn certain high-dimensional targets in polynomial time: its updates behave like an isotropic random walk, leaving the learned weights nearly orthogonal to the task-relevant directions for exponentially long ho

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · deepseek-v4-flash

2026-08-03 04:09 UTC pith:QHNJVJY4

load-bearing objection Genuinely new two-layer SGD lower bounds; the deep-network claims rest on an honest but unproved condition on κ_T. the 3 major comments →

arxiv 2602.05704 v2 pith:QHNJVJY4 submitted 2026-02-05 cs.LG stat.ML

Limitations of SGD for Multi-Index Models Beyond Statistical Queries

Daniel Barzilai , Ohad Shamir This is my paper
classification cs.LG stat.ML MSC 68Q3268T07
keywords SGD lower boundsmulti-index modelssingle-index modelsgradient condition numberinformation exponentalignmentstatistical querieshigh-dimensional learning
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

This paper proves that vanilla stochastic gradient descent — no projection onto spheres, no tiny learning rates, no injected noise — fails to learn a broad class of high-dimensional target functions within polynomial iteration counts, even when the target is easy statistically and well within the network's representational power. The setting covers single-index and multi-index models, where the target depends on inputs only through a low-dimensional subspace, with predictors ranging from two-layer nets to potentially deep networks with a linear first layer. The paper isolates the dynamical mechanism: when the learned subspace is nearly orthogonal to the task subspace, the population gradient is weak, the data-dependent SGD noise dominates, and the alignment process behaves like an isotropic random walk. A new quantity, the gradient condition number κ_T, governs when this intuition is rigorous; if κ_T is bounded, alignment stays at random scale for a long horizon. Consequences include an exp(d^{1/3}) lower bound for periodic targets and information-exponent bounds Ω~(d^{max(k*−1,1)}), previously available only for spherical SGD or Statistical-Query-style analyses.

Core claim

The central claim is a general alignment lower bound (Theorem 2): under sub-Gaussian inputs, standard initialization, and bounded gradient scale, if the gradient condition number κ_T is at most κ̄ and the population-gradient norm is controlled by an increasing function ψ of the alignment ρ = ∥P_W P_U∥, then with high probability every iterate up to time T keeps alignment below roughly C√(κ̄ m p log(Tdp/δ)/d), as long as T is no larger than 1/ψ(that same scale)². In words: the learned subspace cannot build more than random-scale correlation with the task subspace, because over long horizons the SGD noise makes the alignment process behave like an isotropic random walk. Instantiating ψ yields

What carries the argument

The gradient condition number κ_T := G² / inf_{v∈S^{m−1}} min_{t≤T} E_t[(v⊤ ∇_{W_{t-1}x_t} ℓ(θ_{t-1}; x_t))²], the ratio of a worst-case gradient bound to the smallest typical squared coordinate of the gradient in any direction, averaged over the history. If κ_T does not grow with the input dimension d, then the per-step SGD noise is well enough behaved that the martingale driving the learned subspace behaves like a sub-Gaussian isotropic random walk. The companion object is the alignment ρ(W,U) = ∥P_W P_U∥_op, the cosine of the smallest principal angle between the learned subspace and the task subspace; the population-gradient assumption ∥∇_W L(θ)∥_F ≤ ψ(ρ) is what makes weak alignment self

Load-bearing premise

The load-bearing premise is that the gradient condition number κ_T — how heavy-tailed the stochastic gradients are relative to their typical size — stays bounded independently of the input dimension; the paper proves this only for two-layer networks, while for general deep predictors it is assumed to hold, and if κ_T grows with d the alignment lower bound collapses.

What would settle it

Run vanilla SGD on Gaussian inputs with the correlation loss and a deep (or wide) network against a target with information exponent k*=4, and for d = 10², 10³, 10⁴ record the alignment ∥P_{W_t} P_U∥ and the empirical gradient condition number. If with κ_T ≈ O(1) the alignment rises to a constant in o(d³) iterations, the martingale argument is wrong; if κ_T grows polynomially in d, the deep-network theorem's premise fails, and the two-layer prediction (where the paper bounds κ_T unconditionally) becomes the testable version of the claim.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • Periodic targets sin(u⊤x) with ‖u‖=√d are not learnable by vanilla SGD on two-layer networks in any polynomial number of iterations: the horizon is exp(d^{1/3}), and polynomial width does not remove the barrier.
  • For targets with information exponent k* ≥ 2, vanilla SGD requires Ω~(d^{max(k*−1,1)}) iterations (hence samples), matching for unmodified SGD the bounds previously known only for spherical SGD or SQ-style algorithms.
  • For k*=1, an Ω(d) sample/iteration barrier holds, covering the case where the alignment-based signal bound is not small.
  • The Statistical Queries framework can mispredict SGD behavior: the paper exhibits a coordinate-identification problem where SQ predicts poly(d) queries yet SGD on a simple sparse two-layer network solves it in O(log d) iterations.
  • For two-layer networks the gradient condition number is bounded unconditionally under a standard activation regularity assumption, so the periodic and single-index lower bounds do not depend on the κ_T assumption that the general deep-network theorem requires.

Where Pith is reading between the lines

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

  • The framework makes κ_T a measurable diagnostic: architectures and training tricks (normalization, skip connections, adaptive rates) that keep κ_T bounded should sit inside the proven barrier, while mechanisms that push κ_T to infinity are precisely the ones that can escape it — the paper notes that the known parity-learning construction has κ_T diverging.
  • Whether natural deep networks keep κ_T = O(1) is an open empirical question the paper explicitly flags; if κ_T grows with d in standard architectures, the deep version of the information-exponent bound would vacate, while the two-layer results would stand.
  • Because periodic targets generalize parities to continuous inputs, the exp(d^{1/3}) result suggests the difficulty behind parity learning with SGD is not discrete combinatorial structure but the same weak-signal-relative-to-noise mechanism — implying practical parity learners must operate in the large-κ_T regime.
  • A natural next step, not taken in the paper, is to prove (or disprove) κ_T bounds for specific deep architectures — e.g., with normalization — which would convert the conditional deep-network theorem into an unconditional statement in either direction.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 5 minor

Summary. The paper proposes a new framework for proving lower bounds for vanilla SGD on multi-index models, avoiding SQ-type arguments. The central object is a trajectory-dependent gradient condition number κ_T (Definition 1), and the main technical result (Theorem 2) shows that if κ_T is bounded by κ̄ and the population gradient is controlled by an increasing function ψ of the alignment ρ=∥P_W P_U∥, then with high probability ρ_t stays below C√(κ̄ m p log(Tdp/δ)/d) for all t up to a horizon determined by ψ. This is applied to two-layer networks: periodic targets sin(u^T x) are shown to require exp(d^{1/3}) iterations (Theorem 3), and single-index targets with information exponent k* require Ω̃(d^{max(k*-1,1)}) iterations (Theorem 5). Theorem 6 extends the information-exponent bound to general predictors h(Wx;θ̄), but only conditionally on κ_T≤κ̄, a condition that Section 5.3.2 explicitly says is not proved for deep networks. Appendix A gives examples where SQ lower bounds are misleading. The proof of Theorem 2 uses martingale concentration and covering arguments; Lemma 31/32 bootstrap the alignment and κ_T bounds for two-layer networks.

Significance. If the unconditional two-layer results are correct, the paper makes a substantial technical contribution: it replaces SQ heuristics with a direct martingale analysis of vanilla SGD on a natural class of high-dimensional problems, identifies the gradient condition number as the key noise-to-signal quantity, and gives concrete lower bounds (exp(d^{1/3}) for periodic targets, d^{max(k*-1,1)} for information-exponent targets). The framework is conceptually appealing and the proofs are detailed, with the appendix containing the full argument. The bootstrap in Lemma 31 is legitimate: it applies Theorem 2 to each prefix and inductively transfers the alignment bound to the κ_T bound, so the two-layer results do not suffer from circularity. At the same time, the paper’s headline claim for deep networks is not established, and the final loss statements are relative to uncontrolled predictor norms. These issues are load-bearing for the abstract’s broadest claims, not merely presentation.

major comments (3)
  1. [§5.3.2 / Theorem 6] Theorem 6’s applicability to deep networks rests entirely on the unproved event κ_T≤κ̄. The text explicitly states that for general h(Wx;θ̄) “we can no longer unconditionally bound the gradient condition number κ_T” and only calls it “reasonable to assume” that it does not scale with d. This is not a minor technicality: κ_T (Definition 1) controls the sub-Gaussian parameter of the centered SGD increments relative to the drift (Definition 10, Lemma 20). If κ_T grows with d, the drift term ηt max∥∇W L∥ in Proposition 22 can be dominated, and the alignment bound ρ_t≤C√(κ̄ m p log/d) collapses. Thus Theorem 6 is a valid conditional statement, but it does not prove the abstract’s claim that the results apply to “(potentially deep) neural networks.” Moreover, the theorem’s d0 and T scale with κ̄, so a d-dependent κ̄ would degrade the claimed Ω̃(d^{max(k*-1,1)}) rate. A proof of κ_T≤κ̄ for at l
  2. [Theorems 5 and 6, statements] The final bounds are of the form |L(θ_t)-L(θ_0)| ≤ ∥f⋆∥_{L2}(∥fθ_t∥_{L2}+∥fθ_0∥_{L2})·ϵ, with no control on ∥fθ_t∥_{L2}. Since SGD can increase weight norms, the RHS is not an absolute loss bound. For example, the crude triangle inequality gives ∥W_t-W_0∥_F ≤ η G √d · t; with η≈d^{-1/2} and T≈d^{k*-1}, this can grow polynomially of degree k*-1. For k*>2 and the natural choice ϵ≈d^{-k*/2}, the RHS can exceed 1, so the bound does not imply that the loss stays near initialization. The alignment statement in Theorem 2 is unaffected, but the interpretation “SGD requires Ω̃(d^{...}) iterations to converge” needs an additional norm bound or a normalized-loss formulation. As written, Theorems 5 and 6 establish alignment lower bounds, not unconditional sample-complexity lower bounds for reaching small loss.
  3. [§5.3.2 / contributions] The only unconditional lower bounds for finite-width networks are Theorems 3 and 5, which are single-index/periodic targets. For multi-index targets with two-layer networks, the paper states that κ_T “can be explicitly bounded even for general multi-index target functions” but says “we omit this particular result.” Consequently, the only result covering multi-index targets for general predictors is Theorem 6, which is conditional on κ_T≤κ̄. The paper should state this limitation prominently in the introduction or abstract; currently the abstract’s “multi-index model” claim is stronger than the set of unconditional theorems.
minor comments (5)
  1. [§5.2] The probability bound 1-2m exp(-d^{1/3}) is only meaningful when m is not too large. State explicitly that the theorem is intended for m at most polynomial (or sub-exponential) in d, otherwise the failure probability may be large.
  2. [Definition 1] The informal sentence that κ_T “should not depend on d” is not a formal assumption. Since all theorems are conditional on κ_T≤κ̄, the informal claim could be removed or stated as a conjecture/research direction.
  3. [Eq. (4), Section 3] There is a sign inconsistency: the SGD update is θ_t=θ_{t-1}-η∇ℓ, but a_t is defined via ∂/∂(⟨w_{t-1},x_t⟩)ℓ without a minus sign. Later uses seem to absorb the sign, but the notation is confusing. A minus sign or a sentence clarifying the convention would help.
  4. [Appendix A, tensor PCA discussion] “poly(1/d) tolerance” should read “1/poly(d) tolerance” or “inverse-polynomial tolerance”.
  5. [Theorem 6] The notation Θ and Θ̃ hides constants depending on G1, G2, ∥∇f⋆∥, but the dependence on κ̄ in d0 and T is not made explicit in the theorem statement. Write d0 = Θ̃(κ̄² m² p² k⋆² ε^{-2/k⋆}) and T = (d/Θ̃(κ̄mpk⋆))^{k⋆-1}+Θ(dε²/p) explicitly.

Circularity Check

0 steps flagged

No significant circularity: the main theorem is proved from explicit assumptions; the κ_T condition for deep networks is a stated scope limitation, not a circular step.

full rationale

The paper's central derivation is self-contained. Theorem 2 is proved in Appendix B from Assumptions 1–3 via concentration and martingale arguments; the applications (Theorems 3, 5, 6) instantiate this theorem with explicit ψ functions and verify, for two-layer networks, the required bound on the gradient condition number κ_T. The one mutual dependence that might look circular is the alignment-versus-κ_T relationship in Lemmas 31–32, but it is a genuine induction: initialization gives small alignment, small alignment gives small κ_T at the next step (through Lemma 30 and Assumption 4), and small κ_T gives small alignment through Theorem 2. The base case is the initialization alignment, so the loop is broken. No parameter is fitted to data and renamed as a prediction; κ_T is a defined trajectory-dependent quantity, and the general theorem is explicitly conditional on a bound on it. Self-citations (e.g., Shamir 2018; Shoshani and Shamir 2025; Safran and Shamir 2018) are historical/contextual and are not used to prove Theorem 2 or its applications. The one legitimate weakness is in the scope of the deep-network claim: Section 5.3.2 explicitly concedes 'we can no longer unconditionally bound the gradient condition number κ_T' and only calls it 'reasonable to assume' that it does not scale with d, so Theorem 6 is conditional for general deep predictors. This is a limitation of the theorem relative to the abstract's phrasing, not a circular step, because the proof does not use the theorem's conclusion to establish the condition. Similarly, the relative loss bounds in Theorems 5–6 weaken the lower-bound interpretation but are not circular.

Axiom & Free-Parameter Ledger

0 free parameters · 6 axioms · 1 invented entities

The paper's results rest on standard high-dimensional assumptions (sub-Gaussian inputs, random init, bounded gradients) plus the key conditioning assumption κ_T ≤ κ̄ for general predictors. For two-layer networks, κ_T is proved bounded under Assumption 4, so the unconditional results are self-contained. No free parameters are fitted; all constants are problem-dependent.

axioms (6)
  • domain assumption Assumption 1: inputs are mean-zero sub-Gaussian with norm concentration (∥x∥² near α²d).
    Used throughout Theorem 2 and all applications to control projection tails and norm fluctuations of SGD updates.
  • domain assumption Assumption 2: entries of W0 are i.i.d., zero mean, variance 1/d, sub-Gaussian.
    Ensures the initial alignment is small and the first-layer weights have the right scale. Holds for standard Gaussian/orthogonal init.
  • domain assumption Assumption 3: ∥∇_{Wx} ℓ(θ;x)∥ ≤ G for all θ,x.
    Bounds the magnitude of the gradient condition number and stochastic updates; satisfied for bounded activations and Lipschitz losses like correlation loss.
  • domain assumption Assumption 4: activation σ has bounded derivative and inf_{s>0} E_{x~N(0,s²)}[σ'(x)²] ≥ G1²/Kσ.
    Needed to prove κ_T is bounded for two-layer networks (Lemma 32). Verified for ReLU, sigmoid, GeLU, sin in Appendix D.1.
  • ad hoc to paper κ_T ≤ κ̄ for general predictors.
    Theorem 6 conditions on this; for deep networks the paper does not prove it, calling it 'reasonable to assume' in Section 5.3.2. This is the load-bearing unproved assumption for the deep-network claims.
  • domain assumption Target f* is L∞-bounded and, for information-exponent results, ∇φ ∈ L²(μ) and f* has a well-defined information exponent k*.
    Required for the Hermite-expansion bounds (Lemmas 33, 34) and to keep the correlation loss gradients bounded.
invented entities (1)
  • Gradient condition number κ_T = G² / inf_v min_t E_t[(v^⊤ ∇_{Wx}ℓ)²] independent evidence
    purpose: Quantifies how heavy-tailed the stochastic gradients are relative to their mean square; if κ_T is bounded, SGD noise behaves like an isotropic random walk.
    This is a defined mathematical quantity, not a physical entity. It is load-bearing for the general framework and is explicitly bounded for two-layer networks with standard activations. The paper itself notes that for the Abbe–Sandon parity network κ_T diverges, giving an independent consistency check.

pith-pipeline@v1.3.0-alltime-deepseek · 45404 in / 20614 out tokens · 221305 ms · 2026-08-03T04:09:42.409630+00:00 · methodology

0 comments
read the original abstract

Understanding the limitations of gradient methods, and stochastic gradient descent (SGD) in particular, is a central challenge in learning theory. To that end, a commonly used tool is the Statistical Queries (SQ) framework, which studies performance limits of algorithms based on noisy interaction with the data. However, it is known that the formal connection between the SQ framework and SGD is tenuous: Existing results typically rely on adversarial or specially-structured gradient noise that does not reflect the noise in standard SGD, and (as we point out here) can sometimes lead to incorrect predictions. Moreover, many analyses of SGD for challenging problems rely on non-trivial algorithmic modifications, such as restricting the SGD trajectory to the sphere or using very small learning rates. To address these shortcomings, we develop a new, non-SQ framework to study the limitations of standard vanilla SGD, for single-index and multi-index models (namely, when the target function depends on a low-dimensional projection of the inputs). Our results apply to a broad class of settings and architectures, including (potentially deep) neural networks.

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

47 extracted references · 7 linked inside Pith

  1. [1]

    On the non-universality of deep learning: quantifying the cost of symmetry

    Emmanuel Abbe and Enric Boix-Adsera. On the non-universality of deep learning: quantifying the cost of symmetry. Advances in Neural Information Processing Systems, 35: 0 17188--17201, 2022

    2022

  2. [2]

    On the universality of deep learning

    Emmanuel Abbe and Colin Sandon. On the universality of deep learning. Advances in Neural Information Processing Systems, 33: 0 20061--20072, 2020

    2020

  3. [3]

    On the power of differentiable learning versus pac and sq learning

    Emmanuel Abbe, Pritish Kamath, Eran Malach, Colin Sandon, and Nathan Srebro. On the power of differentiable learning versus pac and sq learning. Advances in Neural Information Processing Systems, 34: 0 24340--24351, 2021

    2021

  4. [4]

    Sgd learning on neural networks: leap complexity and saddle-to-saddle dynamics

    Emmanuel Abbe, Enric Boix Adsera, and Theodor Misiakiewicz. Sgd learning on neural networks: leap complexity and saddle-to-saddle dynamics. In The Thirty Sixth Annual Conference on Learning Theory, pages 2552--2623. PMLR, 2023

    2023

  5. [5]

    Learning high-degree parities: The crucial role of the initialization

    Emmanuel Abbe, Elisabetta Cornacchia, Jan H a z a, and Donald Kougang-Yombi. Learning high-degree parities: The crucial role of the initialization. In The Thirteenth International Conference on Learning Representations, 2025

    2025

  6. [6]

    Winnowing with gradient descent

    Ehsan Amid and Manfred K Warmuth. Winnowing with gradient descent. In Conference on Learning Theory, pages 163--182. PMLR, 2020

    2020

  7. [7]

    Sgd with large step sizes learns sparse features

    Maksym Andriushchenko, Aditya Vardhan Varre, Loucas Pillaud-Vivien, and Nicolas Flammarion. Sgd with large step sizes learns sparse features. In International Conference on Machine Learning, pages 903--925. PMLR, 2023

    2023

  8. [8]

    Hidden progress in deep learning: Sgd learns parities near the computational limit

    Boaz Barak, Benjamin Edelman, Surbhi Goel, Sham Kakade, Eran Malach, and Cyril Zhang. Hidden progress in deep learning: Sgd learns parities near the computational limit. Advances in Neural Information Processing Systems, 35: 0 21750--21764, 2022

    2022

  9. [9]

    Online stochastic gradient descent on non-convex losses from high-dimensional inference

    Gerard Ben Arous, Reza Gheissari, and Aukosh Jagannath. Online stochastic gradient descent on non-convex losses from high-dimensional inference. Journal of Machine Learning Research, 22 0 (106): 0 1--51, 2021

    2021

  10. [10]

    Learning single-index models with shallow neural networks

    Alberto Bietti, Joan Bruna, Clayton Sanford, and Min Jae Song. Learning single-index models with shallow neural networks. Advances in Neural Information Processing Systems, 35: 0 9768--9783, 2022

    2022

  11. [11]

    On learning gaussian multi-index models with gradient flow

    Alberto Bietti, Joan Bruna, and Loucas Pillaud-Vivien. On learning gaussian multi-index models with gradient flow. CoRR, 2023

    2023

  12. [12]

    Learning a single index model from anisotropic data with vanilla stochastic gradient descent

    Guillaume Braun, Minh Ha Quang, and Masaaki Imaizumi. Learning a single index model from anisotropic data with vanilla stochastic gradient descent. In International Conference on Artificial Intelligence and Statistics, pages 1216--1224. PMLR, 2025

    2025

  13. [13]

    Survey on algorithms for multi-index models

    Joan Bruna and Daniel Hsu. Survey on algorithms for multi-index models. arXiv preprint arXiv:2504.05426, 2025

    Pith/arXiv arXiv 2025

  14. [14]

    Learning polynomials in few relevant dimensions

    Sitan Chen and Raghu Meka. Learning polynomials in few relevant dimensions. In Conference on Learning Theory, pages 1161--1227. PMLR, 2020

    2020

  15. [15]

    The loss surfaces of multilayer networks

    Anna Choromanska, Mikael Henaff, Michael Mathieu, G \'e rard Ben Arous, and Yann LeCun. The loss surfaces of multilayer networks. In Artificial intelligence and statistics, pages 192--204. PMLR, 2015

    2015

  16. [16]

    Gradient descent on neural networks typically occurs at the edge of stability

    Jeremy M Cohen, Simran Kaur, Yuanzhi Li, J Zico Kolter, and Ameet Talwalkar. Gradient descent on neural networks typically occurs at the edge of stability. arXiv preprint arXiv:2103.00065, 2021

    Pith/arXiv arXiv 2021

  17. [17]

    Smoothing the landscape boosts the signal for sgd: Optimal sample complexity for learning single index models

    Alex Damian, Eshaan Nichani, Rong Ge, and Jason D Lee. Smoothing the landscape boosts the signal for sgd: Optimal sample complexity for learning single index models. Advances in Neural Information Processing Systems, 36, 2024 a

    2024

  18. [18]

    Computational-statistical gaps in gaussian single-index models

    Alex Damian, Loucas Pillaud-Vivien, Jason Lee, and Joan Bruna. Computational-statistical gaps in gaussian single-index models. In The Thirty Seventh Annual Conference on Learning Theory, pages 1262--1262. PMLR, 2024 b

    2024

  19. [19]

    The generative leap: Sharp sample complexity for efficiently learning gaussian multi-index models

    Alex Damian, Jason D Lee, and Joan Bruna. The generative leap: Sharp sample complexity for efficiently learning gaussian multi-index models. arXiv preprint arXiv:2506.05500, 2025

    Pith/arXiv arXiv 2025

  20. [20]

    Neural networks can learn representations with gradient descent

    Alexandru Damian, Jason Lee, and Mahdi Soltanolkotabi. Neural networks can learn representations with gradient descent. In Conference on Learning Theory, pages 5413--5452. PMLR, 2022

    2022

  21. [21]

    The benefits of reusing batches for gradient descent in two-layer networks: Breaking the curse of information and leap exponents

    Yatin Dandi, Emanuele Troiani, Luca Arnaboldi, Luca Pesce, Lenka Zdeborova, and Florent Krzakala. The benefits of reusing batches for gradient descent in two-layer networks: Breaking the curse of information and leap exponents. In Forty-first International Conference on Machine Learning, 2024

    2024

  22. [22]

    Algorithmic high-dimensional robust statistics

    Ilias Diakonikolas and Daniel M Kane. Algorithmic high-dimensional robust statistics. Cambridge university press, 2023

    2023

  23. [23]

    Statistical query lower bounds for tensor pca

    Rishabh Dudeja and Daniel Hsu. Statistical query lower bounds for tensor pca. Journal of Machine Learning Research, 22 0 (83): 0 1--51, 2021

    2021

  24. [24]

    Statistical algorithms and a lower bound for detecting planted cliques

    Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh S Vempala, and Ying Xiao. Statistical algorithms and a lower bound for detecting planted cliques. Journal of the ACM (JACM), 64 0 (2): 0 1--37, 2017

    2017

  25. [25]

    Note on n-dimensional hermite polynomials

    Harold Grad. Note on n-dimensional hermite polynomials. Communications on Pure and Applied Mathematics, 2 0 (4): 0 325--330, 1949

    1949

  26. [26]

    A short note on concentration inequalities for random vectors with subgaussian norm

    Chi Jin, Praneeth Netrapalli, Rong Ge, Sham M Kakade, and Michael I Jordan. A short note on concentration inequalities for random vectors with subgaussian norm. arXiv preprint arXiv:1902.03736, 2019

    Pith/arXiv arXiv 1902

  27. [27]

    On the complexity of learning sparse functions with statistical and gradient queries

    Nirmit Joshi, Theodor Misiakiewicz, and Nati Srebro. On the complexity of learning sparse functions with statistical and gradient queries. Advances in Neural Information Processing Systems, 37: 0 103198--103241, 2024

    2024

  28. [28]

    Efficient noise-tolerant learning from statistical queries

    Michael Kearns. Efficient noise-tolerant learning from statistical queries. Journal of the ACM (JACM), 45 0 (6): 0 983--1006, 1998

    1998

  29. [29]

    Matching the statistical query lower bound for k -sparse parity problems with sign stochastic gradient descent

    Yiwen Kou, Zixiang Chen, Quanquan Gu, and Sham Kakade. Matching the statistical query lower bound for k -sparse parity problems with sign stochastic gradient descent. Advances in Neural Information Processing Systems, 37: 0 113001--113037, 2024

    2024

  30. [30]

    Neural network learns low-dimensional polynomials with sgd near the information-theoretic limit

    Jason D Lee, Kazusato Oko, Taiji Suzuki, and Denny Wu. Neural network learns low-dimensional polynomials with sgd near the information-theoretic limit. arXiv preprint arXiv:2406.01581, 2024

    Pith/arXiv arXiv 2024

  31. [31]

    Visualizing the loss landscape of neural nets

    Hao Li, Zheng Xu, Gavin Taylor, Christoph Studer, and Tom Goldstein. Visualizing the loss landscape of neural nets. Advances in neural information processing systems, 31, 2018

    2018

  32. [32]

    On mean estimation for general norms with statistical queries

    Jerry Li, Aleksandar Nikolov, Ilya Razenshteyn, and Erik Waingarten. On mean estimation for general norms with statistical queries. In Conference on Learning Theory, pages 2158--2172. PMLR, 2019

    2019

  33. [33]

    Neural networks efficiently learn low-dimensional representations with sgd

    Alireza Mousavi-Hosseini, Sejun Park, Manuela Girotti, Ioannis Mitliagkas, and Murat A Erdogdu. Neural networks efficiently learn low-dimensional representations with sgd. In The Eleventh International Conference on Learning Representations, 2023 a

    2023

  34. [34]

    Gradient-based feature learning under structured data

    Alireza Mousavi-Hosseini, Denny Wu, Taiji Suzuki, and Murat A Erdogdu. Gradient-based feature learning under structured data. Advances in Neural Information Processing Systems, 36: 0 71449--71485, 2023 b

    2023

  35. [35]

    On symmetry and initialization for neural networks

    Ido Nachum and Amir Yehudayoff. On symmetry and initialization for neural networks. In Latin American Symposium on Theoretical Informatics, pages 401--412. Springer, 2020

    2020

  36. [36]

    Learning orthogonal multi-index models: A fine-grained information exponent analysis

    Yunwei Ren and Jason D Lee. Learning orthogonal multi-index models: A fine-grained information exponent analysis. arXiv preprint arXiv:2410.09678, 2024

    arXiv 2024

  37. [37]

    Emergence and scaling laws in sgd learning of shallow neural networks

    Yunwei Ren, Eshaan Nichani, Denny Wu, and Jason D Lee. Emergence and scaling laws in sgd learning of shallow neural networks. arXiv preprint arXiv:2504.19983, 2025

    arXiv 2025

  38. [38]

    Spurious local minima are common in two-layer relu neural networks

    Itay Safran and Ohad Shamir. Spurious local minima are common in two-layer relu neural networks. In International conference on machine learning, pages 4433--4441. PMLR, 2018

    2018

  39. [39]

    Failures of gradient-based deep learning

    Shai Shalev-Shwartz, Ohad Shamir, and Shaked Shammah. Failures of gradient-based deep learning. In International Conference on Machine Learning, pages 3067--3075. PMLR, 2017

    2017

  40. [40]

    Distribution-specific hardness of learning neural networks

    Ohad Shamir. Distribution-specific hardness of learning neural networks. Journal of Machine Learning Research, 19 0 (32): 0 1--29, 2018

    2018

  41. [41]

    Hardness of learning fixed parities with neural networks

    Itamar Shoshani and Ohad Shamir. Hardness of learning fixed parities with neural networks. arXiv preprint arXiv:2501.00817, 2025

    Pith/arXiv arXiv 2025

  42. [42]

    Learning gaussian multi-index models with gradient flow: Time complexity and directional convergence

    Berfin Simsek, Amire Bendjeddou, and Daniel Hsu. Learning gaussian multi-index models with gradient flow: Time complexity and directional convergence. In International Conference on Artificial Intelligence and Statistics, pages 4204--4212. PMLR, 2025

    2025

  43. [43]

    On the cryptographic hardness of learning single periodic neurons

    Min Jae Song, Ilias Zadik, and Joan Bruna. On the cryptographic hardness of learning single periodic neurons. Advances in neural information processing systems, 34: 0 29602--29615, 2021

    2021

  44. [44]

    User-friendly tail bounds for sums of random matrices

    Joel A Tropp. User-friendly tail bounds for sums of random matrices. Foundations of computational mathematics, 12 0 (4): 0 389--434, 2012

    2012

  45. [45]

    Introduction to the non-asymptotic analysis of random matrices

    Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint arXiv:1011.3027, 2010

    Pith/arXiv arXiv 2010

  46. [46]

    High-dimensional probability: An introduction with applications in data science

    Roman Vershynin. High-dimensional probability: An introduction with applications in data science. Cambridge university press, 2nd edition, 2025. URL https://www.math.uci.edu/ rvershyn/papers/HDP-book/HDP-2.pdf

    2025

  47. [47]

    New lower bounds for statistical query learning

    Ke Yang. New lower bounds for statistical query learning. Journal of Computer and System Sciences, 70 0 (4): 0 485--509, 2005

    2005