Pith. sign in

REVIEW 2 major objections 4 minor 3 cited by

The Generative Leap: Sharp Sample Complexity for Efficiently Learning Gaussian Multi-Index Models

T0 review · 2 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read The paper establishes that every Gaussian multi-index model with $r=O_d(1)$ hidden directions has sharp sample complexity $n=\Theta(d^{1\vee k^\star/2})$ for efficient subspace recovery, where $k^\star$ is a newly defined generative leap…

desk verdict A technically strong paper whose advertised agnostic guarantee is not proven; the conditional known-parameters result is the real contribution and deserves review. read the letter →

arxiv 2506.05500 v1 pith:P4T6BU2A submitted 2025-06-05 cs.LG stat.ML

Alex Damian , Jason D. Lee , Joan Bruna This is my paper
classification cs.LGstat.ML MSC 68Q3262H25
keywords Gaussianmulti-indexmodelsgenerativeleapexponentsamplecomplexitylow-degreepolynomialsHermitetensorskernelU-statisticsparityReLUnetworks
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

The paper pins down the sample complexity of learning the hidden subspace of a Gaussian multi-index model: roughly $d^{k^\star/2}$ samples, with $k^\star$ a single exponent read off from the model's Hermite expansion, and exactly $d$ samples when $k^\star\le 2$. It proves a matching lower bound in the class of polynomial-time tests captured by low-degree polynomials, and an upper bound from a new sequential spectral algorithm that needs no knowledge of the link function. The algorithm reveals the subspace leap by leap, using a U-statistic built from Hermite tensors and a kernel over labels that automatically plays the role of any optimal label transformation. The same exponent is computed for several concrete model families, including Gaussian parity, intersections of halfspaces, polynomials, piecewise-linear link functions, and neural networks, and the results imply that most models become learnable with $n=\Theta(d)$ samples under generic linear reparameterizations.

What carries the argument

The load-bearing object is the leap decomposition of the hidden coordinate space, together with the Hermite kernel U-statistic. The leap decomposition is the flag $\emptyset=S_0\subsetneq S_1\subsetneq\cdots\subsetneq S_L=\mathbb{R}^r$ built recursively from $S_{i+1}=S_i\cup\operatorname{span}[\Lambda_{k_i}(S_i)]$, where $\Lambda_k(S)=\mathbb{E}[\zeta_{k,S}^{\otimes2}]$ and $\zeta_{k,S}=\mathbb{E}[h_k(\bar Z_S)\mid Y,Z_S]$ is the conditional Hermite coefficient of the unseen coordinates given the label and the coordinates already recovered. The generative leap exponent $k^\star$ is the largest of the leap orders $k_i$. The estimator that makes the exponent operational is $U_n=\frac{1}{n(n-1)}\sum_{i\neq j}\phi(x_i)\phi(x_j)^{\top}K(y_i,y_j)$ with $\phi(x)=\mathrm{Mat}_{d\times d^{k-1}}[h_k(x)]$, whose expectation is sandwiched between $c(P,K)\Pi_S$ and $C(P,K)\Pi_S$ on the subspace revealed by the next leap; the off-diagonal averaging removes the diagonal noise that would otherwise force $n\gg d^{k/2}$, and the strictly positive definite kernel $K$ replaces an unknown optimal label transformation.

What would settle it

Run Algorithm 2 with the automatic search from Remark 4 (no supplied $\{k_i,s_i\}$) on the paper's own example $Y=\sum_{i=1}^{r-1}Z_i^2+\operatorname{sign}(\prod_{i=1}^r Z_i)$ at the budget $n=C(P)d^{k^\star/2}$. If the eigenvalue scan cannot detect the second leap at that budget, or requires an extra $d$-dependent factor, then the agnostic claim fails as stated; alternatively, computing the Theorem 1 low-degree norm for this model and finding a polynomial test that weakly separates the planted subspace at $n=d^{k^\star/2-\gamma}$ would refute the lower bound.

Watch

Extended reading notes

Core claim

Call a subspace $S$ already learned. The paper defines $\zeta_{k,S}=\mathbb{E}[h_k(\bar Z_S)\mid Y,Z_S]$, the $k$-th Hermite moment of the remaining coordinates given the label and the learned coordinates, and lets the next leap $k(S)$ be the smallest $k$ for which $\Lambda_k(S)=\mathbb{E}[\zeta_{k,S}^{\otimes 2}]$ is nonzero. Iterating $S_{i+1}=S_i\cup\operatorname{span}[\Lambda_{k_i}(S_i)]$ gives a flag of subspaces, and the generative leap exponent is $k^\star=\max_i k_i$. The central claim is that this single number controls efficient learnability: Theorem 1 shows that no degree-$O(\log^2 d)$ polynomial test can weakly detect the planted subspace when $n=O(d^{k^\star/2-\gamma})$, and Theorem 3 shows that $n\ge C(P,K)(d^{k^\star/2}/\varepsilon+d/\varepsilon^2)$ suffices for the iterative Hermite-kernel U-statistic algorithm to recover the full index space to distance $\varepsilon$ with overwhelming probability. The paper therefore claims the sample complexity $n=\Theta(d^{1\vee k^\star/2})$ is both necessary and sufficient in the polynomial-time regime, with the same exponent governing Gaussian parity, halfspace intersections, piecewise-linear and neural-network models.

Load-bearing premise

The formal guarantee requires the algorithm to be told which moment orders and how many new directions to look for at each step; the paper asserts these parameters can instead be discovered on the fly by increasing the order until outlier eigenvalues appear, but gives no proof that this search preserves the stated sample count.

Editorial extensions

If this is right

  • Gaussian $r$-parity models, for which $k^\star=r$, become learnable with $n=\Theta(d^{r/2})$ samples, which is optimal in the low-degree class and, the paper states, the first guarantee at this rate.
  • Intersections of $r$ halfspaces and polynomial multi-index models have $k^\star\le 2$, so their index space is recoverable from $n=\Theta(d)$ samples.
  • Arbitrarily deep ReLU networks with fixed biases have $k^\star\le 2$, yielding $n=C(\sigma)d/\varepsilon^2$ subspace recovery and extending prior bias-free results.
  • For models with $k^\star>2$, the matching lower and upper bounds expose a computational-statistical gap: efficient polynomial-time methods need $d^{k^\star/2}$ samples even though the underlying estimation task is dimension-reduced.
  • Under generic linear transformations of a fixed link function, the leap exponent drops to at most $2$ almost surely, so a large majority of Gaussian multi-index models are learnable at linear sample complexity.

Reading between the lines

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

  • Editorial: The automatic leap search described in Remark 4 is the step most worth probing; if thresholding eigenvalues of the U-statistic by the $\sqrt{d^k/n}$ bulk requires knowledge of the model's noise level or loses a $d$-factor, the agnostic version of the theorem is weaker than the abstract suggests.
  • Editorial: Because the U-statistic only uses Hermite orthogonality and sub-Gaussian concentration, the same estimator is a plausible template for non-isotropic or non-Gaussian covariates, with a broader polynomial basis replacing Hermite tensors; the paper does not pursue this extension.
  • Editorial: The hidden constant $C(P)$ can be exponentially large in $r$, so the sharpness in $d$ does not mean the algorithm is practical when the hidden dimension grows; a coarse-to-fine search over leaps, with early stopping on the eigenvalue bulk, would be the natural implementation.
  • Editorial: The kernel trick over labels suggests a unification of classical inverse-regression methods: hand-chosen slice or polynomial label transformations can be seen as finite-dimensional kernels, whereas a universal kernel adapts to the optimal transformation automatically.
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

2 major / 4 minor

Summary. The paper studies Gaussian multi-index models, where the label depends on the input only through a low-dimensional projection onto an unknown subspace U*. It introduces the generative leap exponent k*, a multi-index generalization of the single-index generative exponent, and claims that n = Θ(d^{1∨k*/2}) samples are both necessary and sufficient for efficient subspace recovery. The lower bound (Theorem 1) is established in the low-degree-polynomial framework for a detection task derived from the leap decomposition. The upper bound (Theorems 2 and 3, Algorithm 2) uses a kernel U-statistic built from Hermite tensors, with a concentration result based on matrix concentration and Gaussian universality. Several examples are computed: Gaussian parity, halfspace intersections, polynomials, piecewise-linear functions, ReLU networks, and shallow neural networks. The central issue assessed in this report is that the formal upper bound is not agnostic: Algorithm 2 takes the leap orders {k_i} and leap dimensions {s_i} as inputs, and the claimed removal of this requirement in Remark 4 is only a sketch.

Significance. If fully established, the paper would provide a sharp dimension-dependence for a broad class of Gaussian multi-index models and unify a number of existing results under one exponent. The introduction of the leap generative exponent is natural, and the U-statistic estimator is a technically interesting contribution; the proofs in the appendix are detailed and go beyond a simple extension of the single-index argument. The paper also gives genuinely new case studies, such as piecewise-linear functions with bias and deep ReLU networks. However, the flagship claim of an agnostic procedure with matching sample complexity is currently not supported by the formal theorems, and the lower bound is necessarily confined to the low-degree framework. These caveats do not diminish the value of the partial result, but they mean the paper's main advertised conclusion is conditional.

major comments (2)
  1. [Abstract, Section 4.1, Remark 4, Theorem 3] The agnostic claim is not established. The abstract and Theorem 3 claim an agnostic sequential procedure requiring no prior knowledge of the multi-index model, but Algorithm 2 takes the leap orders {k_i}_{i=1}^m and leap dimensions {s_i}_{i=1}^m as inputs, and Theorem 3 only holds when these are the true values. Remark 4 says the restriction can be lifted by increasing k until outlier eigenvalues appear outside a '√(d^{k/2}/n)-bulk', citing [DH18] 'in spirit', but no proof is supplied. This is load-bearing: for a wrong k<k*, E[U_n^{(k)}]=0, and the relevant fluctuation scale from the proof of Theorem 2 is d^{k/2}/n + r^{k/2}(d/n)^{1/2}, not (d^{k/2}/n)^{1/2}. At n≍d^{k*/2}/ε, this wrong-k scale is O(r^{k/2}d^{1/2-k*/4}) for k<k*; for k*=1,2 it is O(1), and for larger k* it decays only polynomially, so no separation from the true signal c(P,K) is shown. The choice of s_i, the number of top eigenvectors to keep in each leap, is not analyzed at all. Consequently, the formal upper bound in Theorem 3 is non-agnostic, and the abstract's claim of matching agnostic sample complexity is unsupported.
  2. [Section 3, Theorem 1] The lower bound is a low-degree-polynomial lower bound for a specific detection problem, and the paper carefully frames it that way. However, the reduction from the original index-estimation task to this detection problem is only stated informally ('detecting planted structure is a necessary byproduct of estimating the index space'). To make the claimed n=Ω(d^{k*/2}) a genuine lower bound for estimation, one would need to show that any estimator recovering U* to constant accuracy yields a low-degree test for the stated H0/H1 pair, or otherwise justify the reduction in the LDP model. This is likely standard, but it should be spelled out because Theorem 1 as stated analyzes only the likelihood-ratio norm for the detection problem.
minor comments (4)
  1. [Section 3, detection problem] The integer ilde r is used in the description of H1 ('a planted model of dimension ilde r > r0') but is never defined; presumably it is r-r0, the dimension of the remaining index space, and this should be stated.
  2. [Algorithm 2 and Algorithm 1] The inputs of Algorithm 2 include 'moments {k_i}_{i=1}^m' and 'subspace dimensions {s_i}_{i=1}^m', but m is never defined until the proof of Theorem 3, where it is implicitly the number of leaps L. Algorithm 1's input also lists 'recovery dimensions', but the pseudocode body does not use this parameter except through the final span[v_1,...,v_s]; please make the role of s explicit.
  3. [Section 6, Conclusions] The conclusions state the tight sample complexity as n=Θ(d^{k*∧1}), but the correct expression throughout the paper is d^{1∨k*/2}; the displayed formula should be corrected to d^{1∨k*/2}.
  4. [Remark 4] Remark 4 refers to 'the √(d^{k/2}/n)-bulk' as if it were the established fluctuation scale. The rigorous bound in Theorem 2 is instead d^{k/2}/n + r^{k/2}(d/n)^{1/2}, and the heuristic bulk expression should not be used without a formal statement.

Circularity Check

0 steps flagged · score 2.0 of 10

No by-construction circularity: k* is intrinsic and both bounds are derived from it; the main caveat is that the agnostic lifting in Remark 4 is asserted, not proved.

full rationale

The central derivation is self-contained rather than circular. The generative leap exponent k* is defined from the model's Hermite conditional expectations (Section 2, Definitions 2-3), not fitted to the sample count. Theorem 1 computes the low-degree likelihood-ratio norm directly (Appendix B), and the threshold n=O(d^{k*/2-gamma}) appears as a calculation from subgaussian overlaps of the planted subspace, not as an assumption. Theorem 2's U-statistic concentration is proved using external Gaussian universality results [BvH24], and Theorem 3 is an induction over the leap decomposition using Lemma 3 and Lemma 4; the d^{k*/2} dependence is obtained, not assumed. Self-citations to [DPVLB24] supply the single-index definitions, the density-ratio expansion, and a label-transformation lemma, all of which the paper restates and generalizes; these are not load-bearing in a way that makes the multi-index claims equivalent to their inputs. The one serious caveat is not circularity: Algorithm 2 takes {k_i},{s_i} as inputs and Remark 4 only asserts, without proof, that a spectral search can lift this restriction at n=Theta(d^{k*/2}); Theorem 2's wrong-k fluctuation scale is not analyzed, so the advertised agnostic sufficiency claim is unsupported. This is a missing proof / correctness risk, not a reduction by construction. Score 2 reflects the minor self-citations and the unproven agnostic lifting while the core derivation remains independent.

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

The paper introduces no physical entities and fits no data. Its central object, the generative leap exponent k⋆, is a mathematically defined property of the model rather than a postulated entity. The main assumptions are the LDP computational model, a regularity assumption on the kernel, and an unproven lifting step for agnostic parameter selection.

assumptions (6)
  • domain assumption Gaussian isotropic inputs X∼N(0,I_d), index dimension r=O_d(1), and P does not factor through a smaller subspace.
    Definition 1 and the paragraph 'We will assume this property from now on' in Section 1; recovery is otherwise ill-posed.
  • domain assumption The low-degree polynomial (LDP) framework is a valid proxy for polynomial-time algorithms.
    Theorem 1 and the surrounding discussion in Section 3; the necessity result is formally only for degree-O(log^2 d) polynomial tests.
  • domain assumption Kernel K is PSD, integrally strictly positive definite, satisfies K(y,y)≤1, and is Lipschitz.
    Lemma 3, Theorem 2, and Lemma 4 require these hypotheses to guarantee the spectral gap and concentration of the U-statistic.
  • standard math Gaussian universality and matrix concentration results from [BvH24] apply to the Hermite tensor U-statistic.
    Proof of Theorem 2 uses Corollary 4 and Lemma 12, which rely on [BvH24] and [BBvH23] without re-derivation.
  • ad hoc to paper The unknown leap orders {k_i} and sizes {s_i} can be detected by thresholding eigenvalues.
    Remark 4 claims this in the spirit of [DH18] without proof; the abstract's agnostic claim depends on it.
  • standard math Zero sets of nonzero real-analytic functions have measure zero, and Gaussian integrals over compact sets are analytic.
    Proof of Proposition 6 relies on [Mit15] and the analyticity of the functions ϕ and ψ.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The Generative Leap: Sharp Sample Complexity for Efficiently Learning Gaussian Multi-Index Models." pith.science (2026). https://pith.science/paper/P4T6BU2A

@misc{pith2026250605500,
  author       = {Pith},
  title        = {Pith review of: The Generative Leap: Sharp Sample Complexity for Efficiently Learning Gaussian Multi-Index Models},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/P4T6BU2A}},
  note         = {Machine review of arXiv:2506.05500}
}
abstract

In this work we consider generic Gaussian Multi-index models, in which the labels only depend on the (Gaussian) $d$-dimensional inputs through their projection onto a low-dimensional $r = O_d(1)$ subspace, and we study efficient agnostic estimation procedures for this hidden subspace. We introduce the \emph{generative leap} exponent $k^\star$, a natural extension of the generative exponent from [Damian et al.'24] to the multi-index setting. We first show that a sample complexity of $n=\Theta(d^{1 \vee \k/2})$ is necessary in the class of algorithms captured by the Low-Degree-Polynomial framework. We then establish that this sample complexity is also sufficient, by giving an agnostic sequential estimation procedure (that is, requiring no prior knowledge of the multi-index model) based on a spectral U-statistic over appropriate Hermite tensors. We further compute the generative leap exponent for several examples including piecewise linear functions (deep ReLU networks with bias), and general deep neural networks (with $r$-dimensional first hidden layer).

Discussion (0). Sign in to comment.

Forward citations

Cited by 3 Pith papers

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

  1. Approximate Message Passing with Random Initialization for Phase Retrieval

    math.ST 2026-08 conditional novelty 7.0 of 10

    Randomly initialized Bayes-optimal AMP provably achieves the weak-recovery threshold δ=1/2 and arbitrarily accurate recovery for δ>1.13 in proportional-regime noiseless phase retrieval.

  2. Limitations of SGD for Multi-Index Models Beyond Statistical Queries

    cs.LG 2026-02 conditional novelty 7.0 of 10

    Vanilla SGD provably fails to learn periodic and low-information-exponent single/multi-index targets unless the input dimension is small or the number of iterations is large.

  3. The Multiscale Single-Index Model: A Stylized Model for Hierarchical Feature Learning

    cs.LG 2026-07 conditional novelty 6.5 of 10

    Online SGD on the correlation loss recovers Multiscale Single-Index Model features at n=Õ(d^{K-1}) samples, matching Tensor PCA, while shallow nets cannot approximate the target under higher-chaos non-cancellation.

Reference graph

Works this paper leans on

59 extracted references · 49 canonical work pages · cited by 3 Pith papers

  1. [1]

    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

  2. [2]

    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

  3. [3]

    The staircase property: How hierarchical structure can guide deep learning

    Emmanuel Abbe, Enric Boix-Adsera, Matthew S Brennan, Guy Bresler, and Dheeraj Nagaraj. The staircase property: How hierarchical structure can guide deep learning. Advances in Neural Information Processing Systems , 34:26989--27002, 2021

    work page 2021

  4. [4]

    Repetita iuvant: Data repetition allows sgd to learn high-dimensional multi-index functions, 2024

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

    work page 2024

  5. [5]

    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(106):1--51, 2021

    work page 2021

  6. [6]

    Stochastic gradient descent in high dimensions for multi-spiked tensor pca, 2024

    Gérard Ben Arous, Cédric Gerbelot, and Vanessa Piccolo. Stochastic gradient descent in high dimensions for multi-spiked tensor pca, 2024

    work page 2024

  7. [7]

    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 (JMLR) , 22:106--1, 2021

    work page 2021

  8. [8]

    Statistical query algorithms and low-degree tests are almost equivalent

    M Brennan, G Bresler, S Hopkins, J Li, and T Schramm. Statistical query algorithms and low-degree tests are almost equivalent. In Conference on Learning Theory , 2021

    work page 2021

Show all 59 references
  1. [9]

    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. Communications in Pure and Applied Mathematics , 2025

    2025

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

    2022

  3. [11]

    Bandeira, March T

    Afonso S. Bandeira, March T. Boedihardjo, and Ramon van Handel. Matrix concentration inequalities and free probability. Inventiones mathematicae , 234(1):419--487, June 2023

    2023

  4. [12]

    The franz-parisi criterion and computational trade-offs in high dimensional statistics

    Afonso S Bandeira, Ahmed El Alaoui, Samuel Hopkins, Tselil Schramm, Alexander S Wein, and Ilias Zadik. The franz-parisi criterion and computational trade-offs in high dimensional statistics. Advances in Neural Information Processing Systems , 35:33831--33844, 2022

    2022

  5. [13]

    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. arXiv preprint arXiv:2205.01445 , 2022

    2022 arXiv

  6. [14]

    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

    2025 arXiv

  7. [15]

    Universality and sharp matrix concentration inequalities

    Tatiana Brailovskaya and Ramon van Handel. Universality and sharp matrix concentration inequalities. Geometric and Functional Analysis , 34(6):1734--1838, 2024

    2024

  8. [16]

    Towards understanding hierarchical learning: Benefits of neural representations

    Minshuo Chen, Yu Bai, Jason D Lee, Tuo Zhao, Huan Wang, Caiming Xiong, and Richard Socher. Towards understanding hierarchical learning: Benefits of neural representations. Advances in Neural Information Processing Systems , 2020

    2020

  9. [17]

    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

  10. [18]

    Learning deep relu networks is fixed-parameter tractable

    Sitan Chen, Adam R Klivans, and Raghu Meka. Learning deep relu networks is fixed-parameter tractable. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) , pages 696--707. IEEE, 2022

    2021

  11. [19]

    Dimension reduction for conditional mean in regression

    R Dennis Cook and Bing Li. Dimension reduction for conditional mean in regression. The Annals of Statistics , 30(2):455--474, 2002

    2002

  12. [20]

    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

  13. [21]

    Dennis Cook

    R. Dennis Cook. SAVE : a method for dimension reduction and graphics in regression. Communications in Statistics - Theory and Methods , 29(9-10):2109--2121, 2000

    2000

  14. [22]

    Optimal spectral transitions in high-dimensional multi-index models

    Leonardo Defilippis, Yatin Dandi, Pierre Mergny, Florent Krzakala, and Bruno Loureiro. Optimal spectral transitions in high-dimensional multi-index models. arXiv preprint arXiv:2502.02545 , 2025

    2025 arXiv

  15. [23]

    Learning single-index models in gaussian space

    Rishabh Dudeja and Daniel Hsu. Learning single-index models in gaussian space. In Thirty-First Annual Conference on Learning Theory , 2018

    2018

  16. [24]

    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(83):1--51, 2021

    2021

  17. [25]

    Statistical-computational trade-offs in tensor PCA and related problems via communication complexity

    Rishabh Dudeja and Daniel Hsu. Statistical-computational trade-offs in tensor PCA and related problems via communication complexity. The Annals of Statistics , 52(1):131--156, 2024

    2024

  18. [26]

    Kane, and Lisheng Ren

    Ilias Diakonikolas, Giannis Iakovidis, Daniel M. Kane, and Lisheng Ren. Algorithms and sq lower bounds for robustly learning real-valued multi-index models, 2025

    2025

  19. [27]

    Kane, and Nikos Zarifis

    Ilias Diakonikolas, Giannis Iakovidis, Daniel M. Kane, and Nikos Zarifis. Robust learning of multi-index models via iterative subspace approximation, 2025

    2025

  20. [28]

    Efficiently learning one-hidden-layer relu networks via schur polynomials

    Ilias Diakonikolas and Daniel M Kane. Efficiently learning one-hidden-layer relu networks via schur polynomials. In The Thirty Seventh Annual Conference on Learning Theory , pages 1364--1378. PMLR, 2024

    2024

  21. [29]

    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. Journal of Machine Learning Research , 25(349):1--65, 2024

    2024

  22. [30]

    Kane, and Alistair Stewart

    Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart. Learning geometric concepts with nasty noise, 2017

    2017

  23. [31]

    de la Pe \ n a and Evarist Gin \'e

    V \'i ctor H. de la Pe \ n a and Evarist Gin \'e . Decoupling of U-Statistics and U-Processes , pages 97--152. Springer New York, New York, NY, 1999

    1999

  24. [32]

    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 , 2022

    2022

  25. [33]

    Online learning of neural networks

    Amit Daniely, Idan Mehalel, and Elchanan Mossel. Online learning of neural networks. arXiv preprint arXiv:2505.09167 , 2025

    2025 arXiv

  26. [34]

    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:752--784, 2023

    2023

  27. [35]

    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

    2024

  28. [36]

    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 Proceedings of the 41st International Conferen...

    2024

  29. [37]

    Structure adaptive approach for dimension reduction

    Marian Hristache, Anatoli Juditsky, Jorg Polzehl, and Vladimir Spokoiny. Structure adaptive approach for dimension reduction. The Annals of Statistics , 29(6):1537--1566, 2001

    2001

  30. [38]

    The power of sum-of-squares for detecting hidden structures

    Samuel B Hopkins, Pravesh K Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, and David Steurer. The power of sum-of-squares for detecting hidden structures. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) , pages 720--731. IEEE, 2017

    2017

  31. [39]

    Statistical inference and the sum of squares method

    Samuel Hopkins. Statistical inference and the sum of squares method . PhD thesis, Cornell University, 2018

    2018

  32. [40]

    Tensor principal component analysis via sum-of-square proofs

    Samuel B Hopkins, Jonathan Shi, and David Steurer. Tensor principal component analysis via sum-of-square proofs. In Conference on Learning Theory , pages 956--1006. PMLR, 2015

    2015

  33. [41]

    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:103198--103241, 2024

    2024

  34. [42]

    Learning geometric concepts via gaussian surface area

    Adam R Klivans, Ryan O'Donnell, and Rocco A Servedio. Learning geometric concepts via gaussian surface area. In 49th Annual IEEE Symposium on Foundations of Computer Science , pages 541--550, 2008

    2008

  35. [43]

    Learning intersections of halfspaces with distribution shift: Improved algorithms and sq lower bounds

    Adam Klivans, Konstantinos Stavropoulos, and Arsen Vasilyan. Learning intersections of halfspaces with distribution shift: Improved algorithms and sq lower bounds. In The Thirty Seventh Annual Conference on Learning Theory , pages 2944--2978. PMLR, 2024

    2024

  36. [44]

    Notes on computational hardness of hypothesis testing: Predictions using the low-degree likelihood ratio

    Dmitriy Kunisky, Alexander S Wein, and Afonso S Bandeira. Notes on computational hardness of hypothesis testing: Predictions using the low-degree likelihood ratio. arXiv preprint arXiv:1907.11636 , 2019

    1907 arXiv

  37. [45]

    Spectral estimators for multi-index models: Precise asymptotics and optimal weak recovery

    Filip Kova c evi \'c , Yihan Zhang, and Marco Mondelli. Spectral estimators for multi-index models: Precise asymptotics and optimal weak recovery. arXiv preprint arXiv:2502.01583 , 2025

    2025 arXiv

  38. [46]

    Sliced inverse regression for dimension reduction

    Ker-Chau Li. Sliced inverse regression for dimension reduction. Journal of the American Statistical Association , 86(414):316--327, 1991

    1991

  39. [47]

    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. Advances in Neural Information Processing Systems , 37:58716--58756, 2024

    2024

  40. [48]

    The zero set of a real analytic function

    Boris Mityagin. The zero set of a real analytic function. arXiv preprint arXiv:1512.07276 , 2015

    2015 arXiv

  41. [49]

    Learning juntas

    Elchanan Mossel, Ryan O'Donnell, and Rocco P Servedio. Learning juntas. In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing , pages 206--212, 2003

    2003

  42. [50]

    A statistical model for tensor pca

    Andrea Montanari and Emile Richard. A statistical model for tensor pca. Advances in neural information processing systems , 27, 2014

    2014

  43. [51]

    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

    2024

  44. [52]

    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

    2025

  45. [53]

    Sriperumbudur, Arthur Gretton, Kenji Fukumizu, Bernhard Sch \" o lkopf, and Gert R

    Bharath K. Sriperumbudur, Arthur Gretton, Kenji Fukumizu, Bernhard Sch \" o lkopf, and Gert R. G. Lanckriet. Hilbert Space Embeddings and Metrics on Probability Measures . Journal of Machine Learning Research (JMLR) , 11:1517--1561, 2010

    2010

  46. [54]

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

    Emanuele Troiani, Yatin Dandi, Leonardo Defilippis, Lenka Zdeborová, Bruno Loureiro, and Florent Krzakala. Fundamental limits of weak learnability in high-dimensional multi-index models, 2024

    2024

  47. [55]

    Learning convex concepts from gaussian distributions with pca

    Santosh S Vempala. Learning convex concepts from gaussian distributions with pca. In 51st Annual IEEE Symposium on Foundations of Computer Science , pages 124--130, 2010

    2010

  48. [56]

    Vempala and Ying Xiao

    Santosh S. Vempala and Ying Xiao. Structure from local optima: Learning subspace juntas via higher order pca, 2012

    2012

  49. [57]

    A multiple-index model and dimension reduction

    Yingcun Xia. A multiple-index model and dimension reduction. Journal of the American Statistical Association , 103(484):1631--1640, 2008

    2008

  50. [58]

    An adaptive estimation of dimension reduction space

    Yingcun Xia, Howell Tong, Wai Keung Li, and Li-Xing Zhu. An adaptive estimation of dimension reduction space. Journal of the Royal Statistical Society Series B: Statistical Methodology , 64(3):363--410, 2002

    2002

  51. [59]

    Interpolating convex and non-convex tensor decompositions via the subspace norm

    Qinqing Zheng and Ryota Tomioka. Interpolating convex and non-convex tensor decompositions via the subspace norm. Advances in Neural Information Processing Systems , 28, 2015

    2015

Pith tools

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