Pith. sign in

REVIEW 3 major objections 5 minor 1 cited by

Low-dimensional Functions are Efficiently Learnable under Randomly Biased Distributions

T0 review · 3 major / 5 minor · reviewed 2026-08-08 · deepseek-v4-flash

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

Pith's one-line read A random shift of the input distribution makes any non-linear single-index target as easy to learn as a linear function, and the same mechanism makes sparse Boolean functions learnable with near-linear samples.

desk verdict A novel and likely-correct idea—random input shifts kill the information-exponent barrier—but the Gaussian headline rests on a real proof gap in Lemma 5 that needs fixing before the main claim is fully supported. read the letter →

arxiv 2502.06443 v2 pith:X72CK2TH submitted 2025-02-10 cs.LG stat.ML

Elisabetta Cornacchia , Dan Mikulincer , Elchanan Mossel This is my paper · ORCID
classification cs.LGstat.ML MSC 68Q3260E15
keywords single-indexmodelsinformationexponentrandomshiftHermitecoefficientssmall-ballestimatessparseBooleanfunctionsjuntasstochasticgradientdescent
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

Hard instances of high-dimensional learning—single-index models with a large information exponent, or sparse Boolean functions with complex Fourier spectra—are rare in a quantifiable sense. The paper proves that adding a small random shift to the input distribution makes essentially every sufficiently regular non-linear target easy: the first Hermite coefficient of the shifted target is of constant order with high probability, so the information exponent becomes 1 and online SGD recovers the signal with $n = \Theta(d \ln^2 d)$ samples, independent of the target. The same mechanism works for $k$-sparse Boolean targets, where a random shift of the Rademacher biases makes the first-order Fourier–Walsh coefficients on the relevant coordinates of constant order and yields linear sample complexity for a two-layer ReLU network. The upshot is a uniform guarantee: algorithm performance no longer depends on the intrinsic difficulty of the target, which is why the authors describe high-complexity cases as rare.

What carries the argument

The object that carries the argument is the first Hermite coefficient of the randomly shifted link function, $F_1(\mu) = \mathbb{E}_{z\sim N(0,1)}[f(z+\mu) z]$, which by Gaussian integration by parts equals $\mathbb{E}_{z\sim N(0,1)}[f'(z+\mu)]$. The proof has three moving parts: Assumption 1's non-linearity condition guarantees $\mathrm{Var}(F_1(\mu)) \ge \varepsilon^2\delta^2/1000$; Lipschitz regularity of $f$ makes $F_1$ a $(\sqrt{2/\pi}L)$-Lipschitz function of $\mu$, and a small-ball lemma then says such functions cannot concentrate too much mass near zero; and $F_1$ extends to an entire function on the complex plane with growth $|\Psi(z)| \le \sqrt{(|z|+1)e^{|z|}}$, so local small-ball estimates for analytic functions [NSV03] convert the weak estimate into the super-polynomial bound $\exp(-c\log(1/\lambda)^{2/3})$. In the Boolean case the analogous object is the first-order Fourier–Walsh coefficient $\hat f_\mu(\{j\})$ of the shifted junta; its non-concentration follows from the polynomial anti-concentration inequality of [CW01] applied to $\hat f_\mu(\{j\})$ as a function of the shift variables, and the separation of all $2^k$ sign patterns is what lets the two-layer network realize the target.

What would settle it

For a concrete check, take the normalized degree-3 Hermite polynomial $f=H_3$, which satisfies Assumption 1 with information exponent 3, and by Monte Carlo compute $P(|F_1(\mu)|\le \lambda)$ for $\mu\sim N(0,1)$: the paper's Theorem 6 predicts decay faster than any polynomial in $\lambda$, so observing the $\lambda^{1/3}$ decay typical of a polynomial $F_1$ would refute the uniform claim; alternatively, symbolically verify Lemma 5's displayed integral inequality with the correct Gaussian tail term $e^{-r^2/(2L^2)}$ in place of $e^{-r^2/2}$, which is the step that must hold for the proof to go through.

Watch

Extended reading notes

Core claim

The paper's central discovery is that the classical hardness parameter of the single-index model—the information exponent $I(f)$, the index of the first non-zero Hermite coefficient—collapses under a random shift. If the input is drawn from $N(\alpha, I_d)$ with $\alpha \sim N(0, I_d)$, the shift seen by the target is $\mu = \langle w^\ast, \alpha\rangle \sim N(0,1)$, and for $f$ satisfying Assumption 1 the first shifted Hermite coefficient $F_1(\mu) = \mathbb{E}_{z \sim N(0,1)}[f(z+\mu)z]$ obeys the small-ball bound $P(|F_1(\mu)| \le \lambda) \le \exp(-c \log(1/\lambda)^{2/3})$, uniformly over the target class. Consequently the two-stage SGD algorithm of the paper achieves $\langle \theta, w^\ast\rangle \ge 1-o(1)$ with probability exceeding $1/2-\lambda$ using $n=\Theta(d\ln^2 d)$ samples, regardless of the original information exponent; the random shift is the only source of this uniformity. For sparse Boolean targets the analogous statement is that, under a random shift of each coordinate's bias, the first-order Fourier–Walsh coefficients on the support are of constant order with high probability, and layerwise SGD on a two-layer ReLU network learns any $k$-sparse function with $\tilde{O}(d)$ samples.

Load-bearing premise

The load-bearing premise is that a Lipschitz function of a standard Gaussian with variance at least 1 cannot place more than a bounded amount of mass near a single value, together with the non-linearity condition that the target's second derivative has a non-negligible integral over some small interval; the printed proof of the anti-concentration step appears to mishandle the Lipschitz constant in the Gaussian tail estimate.

Editorial extensions

If this is right

  • For Gaussian single-index targets satisfying Assumption 1, two-stage spherical SGD learns $w^\ast$ with $n=\Theta(d\ln^2 d)$ labeled samples and probability $>1/2-\lambda$, uniformly over the target class; the target's information and generative exponents no longer appear in the exponent of $d$.
  • The random shift makes $I(f_\mu)=1$ with high probability, so the online-SGD sample complexity $\Theta(d^{I(f)-1})$ of the unshifted problem reduces to near-linear for almost every shift.
  • In the semi-parametric setting with unknown link function, the same shift mechanism gives strong recovery with $n=\Omega(d^2\log d)$ and $L^2$ approximation of $f$ with $n=\Omega(d^3)$, using a shallow ReLU network of width $O(\sqrt{n/d^2})$.
  • For $k$-sparse Boolean functions with $k=O_d(1)$ and constant-order shift magnitude $\eta$, layerwise SGD on a two-layer ReLU network learns with $\tilde{O}(d)$ samples and network size $\tilde{\Omega}(\eta^{-(k+1)}d)$, independent of leap complexity; the worst-case $\Theta(d^{k-1})$ regime returns only as $\eta\to0$.
  • Hard targets are rare: for any fixed deterministic shift there exist $k$-sparse Boolean targets requiring super-linear sample complexity, but a random shift avoids them with probability $1-O(\varepsilon^c)$.

Reading between the lines

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

  • Editorial: the results give a smoothed-analysis explanation for why gradient methods succeed in practice—the difficult targets form a thin exceptional set, and a generic infinitesimal perturbation of the data distribution moves outside it; the paper establishes this for shifts of the first moment, leaving open whether other natural perturbations (covariance spikes, label noise, input noise) behave
  • Testable extension: for a fixed high-information-exponent target such as the degree-3 Hermite polynomial, Monte Carlo evaluation of $|F_1(\mu)|$ over $\mu\sim N(0,1)$ should show the fraction below $\lambda$ decaying super-polynomially; SGD on shifted batches should then escape the symmetric equator in a single step whenever $|\langle \theta_0,\alpha\rangle|$ is typical.
  • Editorial: the Boolean analysis suggests a general principle for product measures—randomly tilting the marginals collapses the statistical complexity of sparse structure to $O(d)$—and extending the guarantee from Rademacher marginals to smoothed Markov random fields is a natural next step along the lines of the smoothed-analysis literature the paper cites.
  • Editorial: the small-ball estimates are essentially dimension-free, so the random shift should also de-hard the multi-index setting in the sense of making one-directional Hermite coefficients large; the authors note that gradient-flow guarantees there are not automatic, so the constructive question is whether a shift-aware algorithm can exploit the dimension-free anti-concentration.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 5 minor

Summary. The paper studies learning single-index and multi-index models when the input distribution is perturbed by a random mean shift. For Gaussian inputs, the authors claim that a random shift makes the first Hermite coefficient of any sufficiently regular target function bounded away from zero with high probability uniformly over a broad class of targets, yielding near-linear sample complexity for online SGD independently of the information exponent. For sparse Boolean functions under randomly biased product distributions, they claim an analogous statement for first-order Fourier-Walsh coefficients and a linear-complexity guarantee for layerwise SGD on a two-layer ReLU network. The central technical engine is Theorem 6, a super-polynomial small-ball estimate for the shifted first Hermite coefficient, proved via a variance lower bound, a Lipschitz anti-concentration lemma, analytic continuation, and the Nazarov-Sodin-Volberg local estimate. The Boolean results use the Carbery-Wright inequality and are developed separately.

Significance. If the main results hold, the paper makes a strong and interesting point: the information-exponent and leap-complexity barriers for gradient methods are fragile under a small random shift of the data distribution. The Gaussian and Boolean settings are connected through a common smoothed-analysis message, and the paper gives explicit quantitative small-ball estimates rather than only existence statements. The Boolean part is largely self-contained and, modulo small typographical issues, appears sound. The Gaussian part is the headline contribution, but its proof currently has a load-bearing gap in Lemma 5 and a scaling error in Proposition 8; these affect Theorems 1, 2, 3, and 6. The results are likely repairable within the manuscript's scope, but they are not established as written.

major comments (3)
  1. [Appendix B.1, Lemma 5] The proof of Lemma 5 contains an invalid Gaussian tail estimate. After applying Gaussian isoperimetry, the proof upper-bounds 1 - Φ(Φ^{-1}(ξ)+r/L) by a Mills-ratio expression containing e^{-r^2/2}. The correct Mills-ratio bound contains e^{-(Φ^{-1}(ξ)+r/L)^2/2}. For L > 1 and r sufficiently large relative to Φ^{-1}(ξ)L/(L-1), the exponent in the printed bound underestimates the true exponent, so the displayed inequality is false and the subsequent integral estimates do not follow. Since Lemma 5 is the only mechanism in the paper that converts the variance lower bound of Lemma 3 into an anti-concentration statement, Proposition 8 and Theorem 6 are unsupported as written. The lemma may be salvageable with a change of variables or a more careful split of the integral, but the current proof is incomplete.
  2. [Appendix B.1, Proposition 8] There is a scaling error in the application of Lemma 5. Setting g = (√(1000)/(εδ)) F1 gives Var(g) ≥ 1, so Lemma 5 bounds only P(|g| ≤ 0.1) = P(|F1| ≤ 0.1 εδ / √1000). The proposition instead claims a bound for P(|F1| ≤ 0.1√(1000) εδ), which is event P(|g| ≤ 100) and is not controlled by Lemma 5. The displayed equality in the proof relates the wrong threshold and does not justify the proposition. Corollary 1 relies on this quantitative statement. The error appears fixable by choosing the small-ball threshold to be of order εδ / √1000, but as written the weak small-ball estimate is not proved.
  3. [Appendix A.2, proof of Theorem 3] The reduction to Theorem 7 is not fully spelled out. The proof conditions only on the event |\hat f_μ(1)| > m, but Theorem 7 is a statement about learning a fixed target f_μ with constants that may depend on spectral and regularity properties of that target. Since μ is random, one must verify that all constants in Theorem 7 are uniform over the event of positive probability, for example by adding a high-probability bound on |μ| and checking that the relevant norms of f_μ are controlled by the Assumption 1 parameters. Additionally, the proof invokes 'Theorem 8', which is not stated anywhere in the manuscript; presumably Theorem 6 or Proposition 8 is intended. These issues are local and likely fixable, but they are load-bearing for the semi-parametric guarantee.
minor comments (5)
  1. [Proof of Theorem 2, Appendix A.1] The proof says 'since n ≥ C^2 L^2 d^2 ln(d)', which contradicts the claimed n = Θ(d ln² d) and is not what Lemma 1 requires; the polynomial in d should be linear with polylogarithmic factors. Please correct this typo.
  2. [Proposition 4 and Appendix C.1] The proposition states probability O(ε^{1/k}), while the proof and the Carbery-Wright bound give O(ε^{1/(k+1)}). Please align the statement with the proof.
  3. [Corollary 1] The corollary concludes F1(μ′) > c̃, but the relevant event is |F1(μ′)| ≥ c̃; the sign can be handled by replacing f with -f if needed, but the statement should be written with absolute values.
  4. [Proposition 8 statement] The proposition writes P(F1(μ) ≥ ...), while the proof concerns |F1(μ)|. The statement should either use absolute values or explicitly allow the symmetric replacement f ↦ -f.
  5. [Appendix B.1, proof of Proposition 8] The proof says 'by Lemma 4, F1 is L-Lipschitz', but Lemma 4 gives a factor √(2/π). This factor can be absorbed into the constants, but the text should be consistent.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main estimates are derived from stated assumptions via external small-ball and isoperimetric results; self-citations are peripheral.

full rationale

The paper's central claim—Theorem 6, giving a super-polynomial small-ball bound for the first Hermite coefficient F1(µ) uniformly over a class of target functions—is a theorem whose proof starts from Assumption 1 (normalization, L-Lipschitz regularity, and non-linearity condition (7)) and proceeds through Lemma 3 (variance lower bound), Lemma 4 (Lipschitzness of F1), Lemma 5 (anti-concentration for Lipschitz functions), and the external Nazarov–Sodin–Volberg local small-ball bound [NSV03]. Nothing in these inputs asserts the target conclusion: the lower bound on Var(F1(µ)) is obtained from the non-linearity assumption via Stein's lemma and a mean-value/event argument, and the anti-concentration step is a general statement about L-Lipschitz functions of a Gaussian. The uniform-over-f nature of the bound is proved, not assumed. The algorithmic consequences (Theorems 2 and 3) invoke external results [BAGJ21, BES+22, BBSS22] as black boxes and use Theorem 6 only to guarantee that the first Hermite coefficient is large; the shift is random, not optimized to fit the conclusion. The Boolean results (Proposition 4 and Theorem 5) similarly derive first-order Fourier coefficient anti-concentration from the Carbery–Wright inequality applied to the explicit polynomial expression for the coefficient; no fitted parameter is renamed as a prediction. The only self-citations are [CM23, ACL23] for the covariance loss and curriculum-learning context, and the covariance loss itself is defined in Definition 2; these citations are not load-bearing. A separate concern raised in review—that Lemma 5's printed Mills-ratio estimate writes e^{-r^2/2} where the integrand should contain e^{-(Φ^{-1}(ξ)+r/L)^2/2}, which would invalidate the displayed inequality for L>1—is a proof-correctness issue and not an instance of circular reasoning, since the lemma's conclusion is not assumed among its hypotheses. Thus no circular step is present.

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

The theorems rest on Assumption 1 (a domain restriction), standard analytic and isoperimetric tools, and prior SGD/statistical results used as black boxes. There are no data-fitted free parameters, and the random shift is a modeling device rather than an invented entity.

assumptions (6)
  • domain assumption Assumption 1: f is normalized, L-Lipschitz, and has a distributional second derivative with |∫_{c-s}^{c+s} f''| > ε for all s ∈ (δ/2, δ)
    Invoked in Lemma 3 to lower-bound Var(F1(µ)); it excludes affine functions and functions flat in an interval, which is necessary for the small-ball estimate.
  • standard math Gaussian isoperimetric inequality and concentration from Led93
    Used in Lemma 5 to anti-concentrate Lipschitz functions of a Gaussian.
  • standard math NSV03 Theorem A: small-ball estimates for bounded analytic functions on the unit disk
    Used to boost the weak small-ball estimate to the full Theorem 6.
  • standard math Carbery-Wright inequality (CW01)
    Used in Proposition 4 and Lemma 10 to bound probabilities that random polynomials are small.
  • domain assumption Prior SGD guarantees: BAGJ21 online SGD for single-index, BES+22 weak-to-strong boosting, BBSS22 semi-parametric flow, SSBD14 convex SGD convergence
    Used as black boxes in Theorems 2, 3, and 5; the paper does not re-derive them.
  • standard math Stein's lemma and the heat equation representation for Hermite coefficients (Eva98)
    Used to express F1(µ) as E[f'(x+µ)] and to extend F1 analytically.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Low-dimensional Functions are Efficiently Learnable under Randomly Biased Distributions." pith.science (2026). https://pith.science/paper/X72CK2TH

@misc{pith2026250206443,
  author       = {Pith},
  title        = {Pith review of: Low-dimensional Functions are Efficiently Learnable under Randomly Biased Distributions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/X72CK2TH}},
  note         = {Machine review of arXiv:2502.06443}
}
read the original abstract

The problem of learning single index and multi index models has gained significant interest as a fundamental task in high-dimensional statistics. Many recent works have analysed gradient-based methods, particularly in the setting of isotropic data distributions, often in the context of neural network training. Such studies have uncovered precise characterisations of algorithmic sample complexity in terms of certain analytic properties of the target function, such as the leap, information, and generative exponents. These properties establish a quantitative separation between low and high complexity learning tasks. In this work, we show that high complexity cases are rare. Specifically, we prove that introducing a small random perturbation to the data distribution--via a random shift in the first moment--renders any Gaussian single index model as easy to learn as a linear function. We further extend this result to a class of multi index models, namely sparse Boolean functions, also known as Juntas.

Figures

Figures reproduced from arXiv: 2502.06443 by the authors.

Figure 1
Figure 1. Learning the Boolean function f(x) = x1 + x1x2x3 + x1x2...x6 using SGD on a two-layer ReLU network under randomly shifted Boolean inputs, with shift-magnitude η ∈ {0, 0.1, 0.25, 0.5}. Left: Evolution of the test error during training for fixed input dimension d = 50. Right: Number of training epochs required to achieve test error below 10−2 for varying input dimensions. evolution of the test error during training, f… view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. The Power of Power Law: Asymmetry Enables Compositional Reasoning

    cs.AI 2026-04 unverdicted novelty 6.0 of 10

    Power-law data sampling creates beneficial asymmetry in the loss landscape that lets models acquire high-frequency skill compositions first, enabling more efficient learning of rare long-tail skills than uniform distr...

Reference graph

Works this paper leans on

53 extracted references · 37 canonical work pages · cited by 1 Pith paper

  1. [1]

    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

    work page 2023

  2. [2]

    The merged-staircase property: a necessary and nearly sufficient condition for sgd learning of sparse functions on two-layer neural networks

    Emmanuel Abbe, Enric Boix-Adsera, and Theodor Misiakiewicz. The merged-staircase property: a necessary and nearly sufficient condition for sgd learning of sparse functions on two-layer neural networks. In Conference on Learning Theory , pages 4782--4887. PMLR, 2022

    work page 2022

  3. [3]

    Provable advantage of curriculum learning on parity targets with mixed inputs

    Emmanuel Abbe, Elisabetta Cornacchia, and Aryo Lotfi. Provable advantage of curriculum learning on parity targets with mixed inputs. Advances in Neural Information Processing Systems , 36:24291--24321, 2023

    work page 2023

  4. [4]

    Repetita iuvant: Data repetition allows SGD to learn high-dimensional multi-index functions

    Luca Arnaboldi, Yatin Dandi, Florent Krzakala, Luca Pesce, and Ludovic Stephan. Repetita iuvant: Data repetition allows SGD to learn high-dimensional multi-index functions. arXiv preprint arXiv:2405.15459 , 2024

    arXiv 2024

  5. [5]

    On the universality of deep learning

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

    work page 2020

  6. [6]

    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. The Journal of Machine Learning Research , 22(1):4788--4838, 2021

    work page 2021

  7. [7]

    High-dimensional limit theorems for SGD : Effective dynamics and critical scaling

    Gerard Ben Arous, Reza Gheissari, and Aukosh Jagannath. High-dimensional limit theorems for SGD : Effective dynamics and critical scaling. Advances in Neural Information Processing Systems , 35:25349--25362, 2022

    work page 2022

  8. [8]

    On learning G aussian multi-index models with gradient flow

    Alberto Bietti, Joan Bruna, and Loucas Pillaud-Vivien. On learning G aussian multi-index models with gradient flow. arXiv preprint arXiv:2310.19793 , 2023

    arXiv 2023

Show all 53 references
  1. [9]

    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:9768--9783, 2022

    2022

  2. [10]

    Id3 learns juntas for smoothed product distributions

    Alon Brutzkus, Amit Daniely, and Eran Malach. Id3 learns juntas for smoothed product distributions. In Conference on Learning Theory , pages 902--915. PMLR, 2020

    2020

  3. [11]

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

    Boaz Barak, Benjamin L Edelman, Surbhi Goel, Sham Kakade, Eran Malach, and Cyril Zhang. Hidden progress in deep learning: Sgd learns parities near the computational limit. arXiv preprint arXiv:2207.08799 , 2022

    2022 arXiv

  4. [12]

    High-dimensional asymptotics of feature learning: How one gradient step improves the representation

    Jimmy Ba, Murat A Erdogdu, Taiji Suzuki, Zhichao Wang, Denny Wu, and Greg Yang. High-dimensional asymptotics of feature learning: How one gradient step improves the representation. Advances in Neural Information Processing Systems , 35:37932--37946, 2022

    2022

  5. [13]

    Learning in the presence of low-dimensional structure: a spiked random matrix perspective

    Jimmy Ba, Murat A Erdogdu, Taiji Suzuki, Zhichao Wang, and Denny Wu. Learning in the presence of low-dimensional structure: a spiked random matrix perspective. Advances in Neural Information Processing Systems , 36, 2024

    2024

  6. [14]

    Learning time-scales in two-layers neural networks

    Rapha \"e l Berthier, Andrea Montanari, and Kangjie Zhou. Learning time-scales in two-layers neural networks. Foundations of Computational Mathematics , pages 1--84, 2024

    2024

  7. [15]

    The distribution of values of analytic functions on convex sets

    Alexander Brudnyi. The distribution of values of analytic functions on convex sets. arXiv preprint math/0104271 , 27, 2001

    2001 arXiv

  8. [16]

    Learning narrow one-hidden-layer ReLU networks

    Sitan Chen, Zehao Dou, Surbhi Goel, Adam Klivans, and Raghu Meka. Learning narrow one-hidden-layer ReLU networks. In The Thirty Sixth Annual Conference on Learning Theory , pages 5580--5614. PMLR, 2023

    2023

  9. [17]

    Learning juntas under markov random fields

    Gautam Chandrasekaran and Adam Klivans. Learning juntas under markov random fields. arXiv preprint arXiv:2506.00764 , 2025

    2025 arXiv

  10. [18]

    A mathematical model for curriculum learning for parities

    Elisabetta Cornacchia and Elchanan Mossel. A mathematical model for curriculum learning for parities. In International Conference on Machine Learning , pages 6402--6423. PMLR, 2023

    2023

  11. [19]

    Distributional and L^q norm inequalities for polynomials over convex bodies in R^n

    Anthony Carbery and James Wright. Distributional and L^q norm inequalities for polynomials over convex bodies in R^n . Math. Res. Lett. , 8(3):233--248, 2001

    2001

  12. [20]

    Learning single-index models in G aussian space

    Rishabh Dudeja and Daniel Hsu. Learning single-index models in G aussian space. In Conference On Learning Theory , pages 1887--1930. PMLR, 2018

    1930

  13. [21]

    How two-layer neural networks learn, one (giant) step at a time

    Yatin Dandi, Florent Krzakala, Bruno Loureiro, Luca Pesce, and Ludovic Stephan. How two-layer neural networks learn, one (giant) step at a time. arXiv preprint arXiv:2305.18270 , 2023

    2023 arXiv

  14. [22]

    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

  15. [23]

    Learning parities with neural networks

    Amit Daniely and Eran Malach. Learning parities with neural networks. Advances in Neural Information Processing Systems , 33:20356--20365, 2020

    2020

  16. [24]

    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

    2024

  17. [25]

    Computational-statistical gaps in G aussian single-index models

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

    2024

  18. [26]

    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 Zdeborov \'a , and Florent Krzakala. The benefits of reusing batches for gradient descent in two-layer networks: Breaking the curse of information and leap exponents. arXiv preprint arXiv:2402.03220 , 2024

    2024 arXiv

  19. [27]

    Lawrence C. Evans. Partial differential equations , volume 19 of Graduate Studies in Mathematics . American Mathematical Society, Providence, RI, 1998

    1998

  20. [28]

    Agnostic learning of a single neuron with gradient descent

    Spencer Frei, Yuan Cao, and Quanquan Gu. Agnostic learning of a single neuron with gradient descent. Advances in Neural Information Processing Systems , 33:5417--5428, 2020

    2020

  21. [29]

    Superpolynomial lower bounds for learning one-layer neural networks using gradient descent

    Surbhi Goel, Aravind Gollakota, Zhihan Jin, Sushrut Karmalkar, and Adam Klivans. Superpolynomial lower bounds for learning one-layer neural networks using gradient descent. In International Conference on Machine Learning , pages 3587--3596. PMLR, 2020

    2020

  22. [30]

    Modeling the influence of data structure on learning in neural networks: The hidden manifold model

    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(4):041044, 2020

    2020

  23. [31]

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

    Nirmit Joshi, Theodor Misiakiewicz, and Nathan Srebro. On the complexity of learning sparse functions with statistical and gradient queries. arXiv preprint arXiv:2407.05622 , 2024

    2024 arXiv

  24. [32]

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

    Yiwen Kou, Zixiang Chen, Quanquan Gu, and Sham M Kakade. Matching the statistical query lower bound for k-sparse parity problems with stochastic gradient descent. arXiv preprint arXiv:2404.12376 , 2024

    2024 arXiv

  25. [33]

    Moment-matching polynomials

    Adam Klivans and Raghu Meka. Moment-matching polynomials. arXiv preprint arXiv:1301.0820 , 2013

    2013 arXiv

  26. [34]

    Learning and smoothed analysis

    Adam Tauman Kalai, Alex Samorodnitsky, and Shang-Hua Teng. Learning and smoothed analysis. In 2009 50th Annual IEEE Symposium on Foundations of Computer Science , pages 395--404. IEEE, 2009

    2009

  27. [35]

    Decision trees are pac-learnable from most product distributions: a smoothed analysis

    Adam Tauman Kalai and Shang-Hua Teng. Decision trees are pac-learnable from most product distributions: a smoothed analysis. arXiv preprint arXiv:0812.0933 , 2008

    2008 arXiv

  28. [36]

    In\'egalit\'es isop\'erim\'etriques en analyse et probabilit\'es

    Michel Ledoux. In\'egalit\'es isop\'erim\'etriques en analyse et probabilit\'es. Ast\'erisque , (216):Exp. No. 773, 5, 343--375, 1993. S\'eminaire Bourbaki, Vol.\ 1992/93

    1993

  29. [37]

    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

    2024 arXiv

  30. [38]

    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:71449--71485, 2023

    2023

  31. [39]

    Quantifying the benefit of using differentiable learning over tangent kernels

    Eran Malach, Pritish Kamath, Emmanuel Abbe, and Nathan Srebro. Quantifying the benefit of using differentiable learning over tangent kernels. In International Conference on Machine Learning , pages 7379--7389. PMLR, 2021

    2021

  32. [40]

    Learning functions of k relevant variables

    Elchanan Mossel, Ryan O'Donnell, and Rocco A Servedio. Learning functions of k relevant variables. Journal of Computer and System Sciences , 69(3):421--434, 2004

    2004

  33. [41]

    Concentration inequalities under sub- G aussian and sub-exponential conditions

    Andreas Maurer and Massimiliano Pontil. Concentration inequalities under sub- G aussian and sub-exponential conditions. Advances in Neural Information Processing Systems , 34:7588--7597, 2021

    2021

  34. [42]

    Improved statistical and computational complexity of the mean-field L angevin dynamics under structured data

    Atsushi Nitanda, Kazusato Oko, Taiji Suzuki, and Denny Wu. Improved statistical and computational complexity of the mean-field L angevin dynamics under structured data. In The Twelfth International Conference on Learning Representations , 2024

    2024

  35. [43]

    Nazarov, M

    F. Nazarov, M. Sodin, and A. Volberg. Local dimension-free estimates for volumes of sublevel sets of analytic functions. Israel J. Math. , 133:269--283, 2003

    2003

  36. [44]

    Analysis of Boolean Functions

    Ryan O'Donnell. Analysis of Boolean Functions . Cambridge University Press, 2014

    2014

  37. [45]

    Distribution-specific hardness of learning neural networks

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

    2018

  38. [46]

    Understanding machine learning: From theory to algorithms

    Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms . Cambridge university press, 2014

    2014

  39. [47]

    Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time

    Daniel Spielman and Shang-Hua Teng. Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. In Proceedings of the thirty-third annual ACM symposium on Theory of computing , pages 296--305, 2001

    2001

  40. [48]

    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:29602--29615, 2021

    2021

  41. [49]

    Fundamental limits of weak learnability in high-dimensional multi-index models

    Emanuele Troiani, Yatin Dandi, Leonardo Defilippis, Lenka Zdeborov \'a , Bruno Loureiro, and Florent Krzakala. Fundamental limits of weak learnability in high-dimensional multi-index models. arXiv preprint arXiv:2405.15480 , 2024

    2024

  42. [50]

    Finding correlations in subquadratic time, with applications to learning parities and juntas

    Gregory Valiant. Finding correlations in subquadratic time, with applications to learning parities and juntas. In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science , pages 11--20. IEEE, 2012

    2012

  43. [51]

    Learning a single neuron for non-monotonic activation functions

    Lei Wu. Learning a single neuron for non-monotonic activation functions. In International Conference on Artificial Intelligence and Statistics , pages 4178--4197. PMLR, 2022

    2022

  44. [52]

    Learning a single neuron with gradient methods

    Gilad Yehudai and Ohad Shamir. Learning a single neuron with gradient methods. In Conference on Learning Theory , pages 3756--3786. PMLR, 2020

    2020

  45. [53]

    On single-index models beyond G aussian data

    Aaron Zweig, Loucas Pillaud-Vivien, and Joan Bruna. On single-index models beyond G aussian data. Advances in Neural Information Processing Systems , 36, 2024

    2024

Pith tools

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