Learning Hierarchical Polynomials of Multiple Nonlinear Features with Three-Layer Networks

Eshaan Nichani; Hengyu Fu; Jason D. Lee; Zihao Wang

REVIEW 1 major objections 5 minor 1 cited by

Learning Hierarchical Polynomials of Multiple Nonlinear Features with Three-Layer Networks

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

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

Pith's one-line read This paper establishes that a three-layer network trained by layerwise gradient descent can recover the full span of r hidden quadratic features and then learn any degree-p polynomial over them, using ~d^4 samples and polynomial time…

desk verdict Real advance on multiple quadratic features, but the formal width assumption needs repair before the theorem as stated goes through. read the letter →

arxiv 2411.17201 v1 pith:BZ2HM5DR submitted 2024-11-26 cs.LG cs.AImath.STstat.MLstat.TH

Hengyu Fu , Zihao Wang , Eshaan Nichani , Jason D. Lee This is my paper · ORCID

classification cs.LGcs.AImath.STstat.MLstat.TH MSC 68T0768Q32

keywords three-layerneuralnetworksfeaturelearninghierarchicalpolynomialsquadraticfeaturesmulti-indexmodellayerwisegradientdescentsamplecomplexityuniversality

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper asks whether gradient descent can discover several hidden nonlinear features simultaneously. It studies targets $f^\star(x)=g^\star(x^\top A_1 x,\dots,x^\top A_r x)$ with $r\ll d$ unknown quadratic features and a degree-$p$ polynomial link $g^\star$. The main claim is that a three-layer network trained layerwise suffices: one gradient step on the inner weights recovers the span of all $r$ features with $\widetilde{\mathcal{O}}(d^4)$ samples, and the outer layer then learns $g^\star$ (or any other degree-$p$ polynomial over the same features) with $r^{\mathcal{O}(p)}$ additional samples. If correct, this replaces the $\Theta(d^{2p})$ sample complexity of kernel methods for these degree-$2p$ targets, showing that feature learning rather than kernel approximation is what makes the network efficient. The authors deliberately exclude targets with a large quadratic spherical-harmonic component, because a dominant linear combination of features would collapse the first gradient step onto one direction.

What carries the argument

The load-bearing object is the learned representation $h^{(1)}(x') = (n_1 m_2)^{-1}\sum_{x\in D_1} f^\star(x)\langle h^{(0)}(x), h^{(0)}(x')\rangle h^{(0)}(x)$ produced by one gradient step on the second-layer weights, where $h^{(0)}(x)=\sigma_2(Vx)$ is a random feature embedding built from Gegenbauer polynomial activations. Under the paper's assumptions the low-degree spherical-harmonic parts of $f^\star$ are suppressed, so $h^{(1)}$ is dominated by the degree-4 component of $f^\star$; by the universality lemma this component is approximately the expected Hessian $H$ of the link acting on the matrices $A_k$. Hence the reconstruction matrix $B^\star \propto H^{-1}[p(v_1),\dots,p(v_{m_2})]$ maps $h^{(1)}(x)$ back to $p(x)$. In the second stage the network is a random-feature model whose outer activation $\sigma_1$ can represent arbitrary univariate monomials on bounded inputs, so any degree-$p$ polynomial of the reconstructed features is expressible with outer weights of controlled norm.

What would settle it

Run Algorithm 1 with $n_1=d^4$ on the degenerate target $f^\star(x)=r^{-1/2}\sum_{k=1}^r x^\top A_k x$ from Remark 1; the paper predicts the first-step representation becomes nearly rank one and some reconstructed features stay uncorrelated with their true features, whereas the theorem's guarantee would require all $r$ features to be recovered.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1: with inner width and first-stage sample size $n_1,m_2=\widetilde{\Omega}(d^4)$, Algorithm 1 returns a network whose expected absolute error against $f^\star$ is at most $\widetilde{\mathcal{O}}(\sqrt{r^p \kappa_2^{2p}/\min(m_1,n_2)} + \sqrt{d^6 r^{p+1}/m_2} + \sqrt{d^2 r^{p+1}/n_1} + r^{p+2}/d^{1/6})$, and the same guarantee holds if the second stage is retrained on any degree-$p$ polynomial $g$ over the same features. The two supporting results are that a linear map $B^\star$ applied to the learned representations reconstructs $p(x)=(x^\top A_1 x,\dots,x^\top A_r x)$ up to error $\widetilde{\mathcal{O}}(d^3 r/\sqrt{m_2} + d r/\sqrt{n_1} + r^{(p+5)/2}/d^{1/6})$ (Proposition 1), and that the outer layer then expresses any degree-$p$ link with squared weight norm $\widetilde{\mathcal{O}}(m_1 r^p \kappa_2^{2p})$ (Proposition 2). The engine is a new multivariate universality lemma: for features with zero mean and identity covariance, the law of the $r$ features is within Wasserstein-1 distance $\mathcal{O}(r^2\kappa_1/\sqrt{d})$ of an $r$-dimensional standard Gaussian, which lets the authors transplant the multi-index analysis to nonlinear quadratic features.

Load-bearing premise

The proof needs the target's quadratic spherical-harmonic part to be nearly zero and the link's expected Hessian to be well conditioned, so that no single linear combination of the $r$ quadratic features dominates the first gradient step and collapses the learned representation onto one direction.

Editorial extensions

If this is right

Feature recovery is explicit: after Stage 1, a closed-form linear map with operator norm $\widetilde{\mathcal{O}}(d^6/(\lambda_{\min}(H)\sqrt{m_2}))$ recovers all $r$ quadratic features simultaneously.
The sample budget separates cleanly: the first stage needs $\widetilde{\mathcal{O}}(d^4 + d^2 r^{p+1})$ samples, and the second stage needs only $r^{\mathcal{O}(p)}\kappa_2^{2p}$ additional samples, independent of the ambient dimension.
Transfer learning follows: prepend just the pretrained first stage to any degree-$p$ polynomial head $g$ over the same features, and the extra sample cost is again $r^{\mathcal{O}(p)}$.
For these degree-$2p$ targets the improvement over kernel methods is super-polynomial in $d$: the kernel sample complexity $\Theta(d^{2p})$ is replaced by a bound whose $d$-dependence is at most $d^4$.
The $\widetilde{\mathcal{O}}(d^4)$ first-stage sample count is near-optimal among one-gradient-step feature-learning algorithms, because the leap index of the target class is 4.

Reading between the lines

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

Extension: because the universality lemma only uses moment and derivative bounds on $p$, the same two-stage argument should extend to any $r$-dimensional family of nonlinear features with well-behaved gradients and Hessians; degree-$q$ features would plausibly raise the first-stage exponent from $d^4$ to $d^{\mathcal{O}(q)}$.
Extension: the closed form $B^\star \propto H^{-1}[p(v_j)]$ makes the first stage a provable pretraining step that estimates both the feature projector and the inverse link Hessian, giving a concrete mechanism for why pretrained representations transfer across tasks sharing features.
Extension: the paper's failure mode is a sharp rank collapse when a single linear combination of features dominates; subtracting the dominant quadratic spherical harmonic from the target before training should restore the balanced regime and enlarge the learnable class.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

Two things to know. This is the first provable guarantee I know of for recovering the span of several quadratic features with a three-layer network, and the claimed improvement over kernels—roughly d^4 instead of d^{2p}—is credible in spirit. The multivariate universality lemma and the reconstruction matrix B* ∝ H^{-1}P^T are genuinely new, and the appendix is a serious argument, not a sketch. The citation pattern is fine: Nichani, Wang, Damian are used as building blocks, not smuggled in as assumptions.

That said, the proof as written has a parameter inconsistency. The corollary of Proposition 4 that controls ||/sqrt(m2) does not follow at m2 = eΩ(d^4). The first term in Proposition 4 is independent of m2, so at m2 = d^4 the normalized bound is roughly κ2 ι^5 / d^5, not the claimed d^{-6}. With the chosen η = C m2^{-1/2} d^6, this gives η|| ≈ d, violating the precondition for the outer-layer polynomial construction, Lemma 33, and the Rademacher analysis. Strengthening the condition to m2 = eΩ(d^6) saves that step and matches the authors' own discussion after Theorem 1. I would also ask the authors to check the reconstruction error d^3/sqrt(m2) in Proposition 5: at m2 = d^6 that term is constant, so the final feature-learning error seems to need m2 to grow faster than d^6 to vanish. The width condition and the final error bound need to be stated consistently.

Smaller issues: the abstract says "complete recovery" but the results are approximate reconstruction, and Assumptions 2 and 3 heavily restrict the target class. The authors acknowledge this, and it is a real restriction rather than a hidden flaw. No code is provided for the experiments, which are modest in scale.

Net: the conceptual contribution is real and likely salvageable, but the formal theorem needs a corrected statement and proof. A serious referee should look at Appendix B.2 and B.3 specifically. This deserves peer review, not a desk rejection.

Referee Report

1 major / 5 minor

Summary. The paper studies three-layer networks trained by layerwise gradient descent for hierarchical targets f* = g*(p(x)), where p(x) = (x^T A_1 x, ..., x^T A_r x) is a vector of r quadratic features and g* is a degree-p polynomial link. The main theorem claims that after one gradient step on the second-layer weights and outer-layer training, the population absolute error is bounded by a term of the form sqrt(r^p kappa_2^{2p}/min(m1,n2)) plus feature-learning errors sqrt(d^6 r^{p+1}/m2), sqrt(d^2 r^{p+1}/n1), and r^{p+2}/d^{1/6}, under the hypothesis n1, m2 = eOmega(d^4). The proof is built around a multivariate universality lemma, an approximate reconstruction of the quadratic features by a linear map B* applied to the learned representations, an expressivity result for the outer layer, and a Rademacher complexity generalization bound. The appendix contains detailed proofs of the concentration, universality, approximation, and generalization statements.

Significance. If the main theorem is valid, it would be a substantial advance: it would give the first provable sample-complexity guarantee for learning hierarchical polynomials of multiple nonlinear features with neural networks, with sample complexity polynomial in d and independent of the link degree p, improving over the Theta(d^{2p}) kernel-method baseline, and it would give transfer learning across link functions. The multivariate universality lemma and the explicit reconstruction matrix B* are genuinely useful ideas, and the appendix is unusually detailed for a paper at this level. However, the current formal statement has a load-bearing parameter-regime inconsistency in the first-stage feature-learning analysis, so the theorem as stated is not proven.

major comments (1)

[Appendix B.2 (Proposition 4) and Theorem 1 (Section 3)] The corollary to Proposition 4 is not valid under its stated hypothesis m2 ≳ d^4 iota^{2p+4}. In the proof of Proposition 4, the quantity (1/m2)<w, h^(1)(x')> is decomposed as A1 + A2 + A3, and Lemma 17 bounds A1 by iota^{p+2}/(m2 d^3). Therefore the first contribution to |<w, h^(1)(x')>| is iota^{p+2}/d^3, which is independent of m2; after dividing by sqrt(m2) it is iota^{p+2}/(d^3 sqrt(m2)). Setting m2 = d^4 iota^{2p+4} gives 1/d^5, not O(kappa_2 iota^5/d^6) as claimed in equation (26). Consequently the learning rate eta = C m2^{-1/2} kappa_2^{-1} iota^{-5} d^6 does not ensure |eta <w, h^(1)(x')>| ≤ 1: with m2 = d^4 the first contribution is of order d, which violates the precondition used in Lemma 33, Proposition 2, and the Rademacher analysis in Appendix D.1. The proof goes through if the condition on m2 is strengthened to m2 = eOmega(d^6), which is consistent with the authors' own discussion after Theorem 1, but then Theorem 1's stated assumption n1, m2 = eOmega(d^4) no longer supports the proof of the feature-learning guarantee.

minor comments (5)

[Abstract] The phrase "complete recovery of the space spanned by the nonlinear features" overstates Proposition 5, which provides an approximate reconstruction with an error that is controlled only asymptotically; I suggest saying "approximate recovery" or "asymptotic recovery".
[Appendix C.1, Proposition 6] The display ends with "= eOmega(kappa_2^{2p} r^p)" immediately after an upper bound of the form "≲"; the intended relation is "= eO(...)", not a lower bound. As written it is inconsistent with the subsequent use of this quantity to bound the complexity of a*.
[Section 2.2, Assumption 3] The heading contains the typo "Prepocessed target function"; it should be "Preprocessed target function".
[Section 4.1] The sentence contains the duplicate phrase "representations presentations" and should be corrected.
[Appendix C] The notation n is reused for n1 and for the total sample size in different parts of the appendix; this should be made explicit to avoid confusion when checking the displayed bounds.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the main theorem is an a priori guarantee with existential analytic constructions, not a fitted prediction or self-citation-reduced claim.

full rationale

The derivation is self-contained in the sense required by the circularity definition. Theorem 1 bounds the population absolute error of Algorithm 1 for any target in the stated class; the bound contains no fitted constants and the parameters (eta1, eta2, lambda1, lambda2, epsilon) are chosen in the proof, not estimated from data. The feature-reconstruction matrix B* in Proposition 1 is an existential construction built from the known target quantities H = E_z[grad^2 g*(z)] and p(v_j) = (v_j^T A_1 v_j, ..., v_j^T A_r v_j); it is not learned by the algorithm and is used only as an analysis device to show that the learned representation spans the features. The final prediction of Algorithm 1 never computes or uses B*, so the guarantee is not a renamed version of an input. The assumptions (Assumptions 1-4) are stated conditions on the target and activations, not conclusions derived from the theorem. Citations to the authors' prior work (Nichani et al. 2023; Wang et al. 2023) and to Damian et al. 2022 are used as technical building blocks, but the paper proves its own key propositions (Proposition 1, Proposition 2, and the supporting lemmas) with explicit error bounds rather than importing the target conclusion. A separate consistency concern about the stated m2 = eOmega(d^4) regime versus the d^6 regime needed by the proof of Proposition 4 is a correctness/internally-consistent-assumptions issue, not circularity: it does not make any prediction equivalent to an input by construction. No circular step was found.

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

No numerical parameters are fitted to data; learning rates and weight decays are chosen existentially in Theorem 1, and target constants (r, p, kappa1, kappa2) are assumptions, not fitted outputs. The hidden quadratic features are part of the assumed target class, not newly invented entities, and the paper introduces no new particles, forces, or mediators.

assumptions (6)

domain assumption Data lie on the sphere S^{d-1}(sqrt(d)) with uniform distribution
Section 2.2: all moment and spherical harmonic calculations assume this input distribution.
domain assumption Assumption 1: quadratic features are mean-zero, orthonormal in L2, and satisfy ||A_i||_op <= kappa1/sqrt(d) with kappa1 = poly(log d)
Section 2.2: needed for the Gaussian universality bound and for feature reconstruction.
domain assumption Assumption 2: g* is degree p, E[g*(z)^2] = Theta(1), and lambda_min(E[nabla^2 g*(z)]) >= C_H sqrt(r)
Section 2.2: invertibility of H is used to choose B* proportional to H^{-1}P^T.
domain assumption Assumption 3: P0(f*) = 0 and ||P2(f*)||_{L2} <= kappa2/sqrt(d)
Section 2.2: ensures the degree-4 component dominates after one gradient step, which is the fulcrum of Proposition 1.
domain assumption Assumption 4: outer activation sigma1 is the smoothed absolute value and inner activation sigma2 has Gegenbauer expansion with c2 = Theta(1) and no constant or linear terms
Section 2.2: the Q2 component of sigma2 is what converts P4(f) into feature information.
standard math Gegenbauer polynomial identities, hypercontractivity, Stein's method, and Rademacher complexity bounds
Appendices A.2-A.5 and D: cited from van Handel, Mei et al., Ross, and Ghorbani et al.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Learning Hierarchical Polynomials of Multiple Nonlinear Features with Three-Layer Networks." pith.science (2026). https://pith.science/paper/BZ2HM5DR

@misc{pith2026241117201,
  author       = {Pith},
  title        = {Pith review of: Learning Hierarchical Polynomials of Multiple Nonlinear Features with Three-Layer Networks},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/BZ2HM5DR}},
  note         = {Machine review of arXiv:2411.17201}
}

abstract

In deep learning theory, a critical question is to understand how neural networks learn hierarchical features. In this work, we study the learning of hierarchical polynomials of \textit{multiple nonlinear features} using three-layer neural networks. We examine a broad class of functions of the form $f^{\star}=g^{\star}\circ \bp$, where $\bp:\mathbb{R}^{d} \rightarrow \mathbb{R}^{r}$ represents multiple quadratic features with $r \ll d$ and $g^{\star}:\mathbb{R}^{r}\rightarrow \mathbb{R}$ is a polynomial of degree $p$. This can be viewed as a nonlinear generalization of the multi-index model \citep{damian2022neural}, and also an expansion upon previous work that focused only on a single nonlinear feature, i.e. $r = 1$ \citep{nichani2023provable,wang2023learning}. Our primary contribution shows that a three-layer neural network trained via layerwise gradient descent suffices for \begin{itemize}\item complete recovery of the space spanned by the nonlinear features \item efficient learning of the target function $f^{\star}=g^{\star}\circ \bp$ or transfer learning of $f=g\circ \bp$ with a different link function \end{itemize} within $\widetilde{\cO}(d^4)$ samples and polynomial time. For such hierarchical targets, our result substantially improves the sample complexity ${\Theta}(d^{2p})$ of the kernel methods, demonstrating the power of efficient feature learning. It is important to highlight that{ our results leverage novel techniques and thus manage to go beyond all prior settings} such as single-index and multi-index models as well as models depending just on one nonlinear feature, contributing to a more comprehensive understanding of feature learning in deep learning.

Figures

Figures reproduced from arXiv: 2411.17201 by the authors.

**Figure 1.** The proof idea of Proposition 1. Block 1 characterizes the constant and linear terms of g ⋆ , which is approximately equivalent to the low-order terms P<4(f ⋆ ) by our universality theory and results into biases in the learned weights h (1)(x ′ ) after Stage 1. This bias is vanishing with d → ∞ by our assumptions on P0(f ⋆ ) and P2(f ⋆ ). Block 2 describes the second-order information of g ⋆ (approximately P4(f ⋆ … view at source ↗

**Figure 2.** For the left panel, Algorithm 1 uses two equally sized datasets, while the random feature model uses the full dataset. For the right panel, we conduct transfer learning with n1 = 216 pretraining samples and plot the dependence on n2. The figure reports the mean and normalized standard error of the test error using 10,000 fresh samples, based on 5 independent experimental instances. features r rather than the ambient… view at source ↗

**Figure 3.** Test error of Algorithm 1 and the naive random feature models with x-axis being the relative sample complexity (logd n). We plot the test error of 5 independent instances for each d ∈ {8, 16, 32}. −3 −2 −1 0 1 2 3 x >A1x −3 −2 −1 0 1 2 3 [B ? h1(x)]1 n1 = d 2 n1 = d 3 n1 = d 4 −3 −2 −1 0 1 2 3 x >A2x −3 −2 −1 0 1 2 3 [B ? h1(x)]2 n1 = d 2 n1 = d 3 n1 = d 4 −3 −2 −1 0 1 2 3 x >A3x −3 −2 −1 0 1 2 3 [B ? h1(x)] 3 n1 = … view at source ↗

Figures from the paper (1 more)

**Figure 4.** Figure 4: The linear correlation between the three true features and their corresponding [PITH_FULL_IMAGE:figures/full_fig_p018_4.png]

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

On The Concurrence of Layer-wise Preconditioning Methods and Provable Feature Learning
cs.LG 2025-02 conditional novelty 7.0 of 10

For two feature-learning models with anisotropic inputs, KFAC-style layer-wise preconditioning provably recovers features better than SGD and matches ridge regression in the single-index case.

Reference graph

Works this paper leans on

50 extracted references · 22 canonical work pages · cited by 1 Pith paper

[1]

write newline

" write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION format.date year duplicate empty "emp...
[2]

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

Emmanuel Abbe, Enric Boix Adser \`a , 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]

What can resnet learn efficiently, going beyond kernels? Advances in Neural Information Processing Systems, 32, 2019

Zeyuan Allen-Zhu and Yuanzhi Li. What can resnet learn efficiently, going beyond kernels? Advances in Neural Information Processing Systems, 32, 2019

work page 2019
[4]

Backward feature correction: How deep learning performs deep learning

Zeyuan Allen-Zhu and Yuanzhi Li. Backward feature correction: How deep learning performs deep learning. arXiv preprint arXiv:2001.04413, 2020

arXiv 2001
[5]

On exact computation with an infinitely wide neural net

Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. Advances in neural information processing systems, 32, 2019

2019
[6]

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: 0 37932--37946, 2022

2022
[7]

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. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Advances in Neural Information Processing Systems, volume 36, pages 17420--17449. Curran Associates, Inc., 2023. URL...

work page 2023
[8]

Yu Bai and Jason D. Lee. Beyond linearization: On quadratic and higher-order approximation of wide neural networks, 2020

work page 2020

Show all 50 references

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

2022
[10]

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. arXiv preprint arXiv:2310.19793, 2023

2023 arXiv
[11]

Fluctuations of eigenvalues and second order poincar\'e inequalities, 2007

Sourav Chatterjee. Fluctuations of eigenvalues and second order poincar\'e inequalities, 2007. URL https://arxiv.org/abs/0705.1224

2007 arXiv
[12]

On lazy training in differentiable programming

Lenaic Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable programming. Advances in neural information processing systems, 32, 2019

2019
[13]

Lu, Lenka Zdeborová, and Bruno Loureiro

Hugo Cui, Luca Pesce, Yatin Dandi, Florent Krzakala, Yue M. Lu, Lenka Zdeborová, and Bruno Loureiro. Asymptotics of feature learning in two-layer networks after one gradient-step, 2024. URL https://arxiv.org/abs/2402.04980

2024 arXiv
[14]

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
[16]

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

Yatin Dandi, Florent Krzakala, Bruno Loureiro, Luca Pesce, and Ludovic Stephan. How two-layer neural networks learn, one (giant) step at a time, 2023 b . URL https://arxiv.org/abs/2305.18270

2023 arXiv
[17]

Lu, and Bruno Loureiro

Yatin Dandi, Luca Pesce, Hugo Cui, Florent Krzakala, Yue M. Lu, and Bruno Loureiro. A random matrix theory perspective on the spectrum of learned features and asymptotic generalization capabilities, 2024 a . URL https://arxiv.org/abs/2410.18938

2024 arXiv
[18]

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

Yatin Dandi, Emanuele Troiani, Luca Arnaboldi, Luca Pesce, Lenka Zdeborová, and Florent Krzakala. The benefits of reusing batches for gradient descent in two-layer networks: Breaking the curse of information and leap exponents, 2024 b . URL https://arxiv.org/abs/2402.03220

2024 arXiv
[19]

Depth separation for neural networks, 2017

Amit Daniely. Depth separation for neural networks, 2017. URL https://arxiv.org/abs/1702.08489

2017 arXiv
[20]

Bert: Pre-training of deep bidirectional transformers for language understanding

Jacob Devlin. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04805, 2018

2018 arXiv
[21]

Gradient descent provably optimizes over-parameterized neural networks

Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. arXiv preprint arXiv:1810.02054, 2018

2018 arXiv
[22]

A comparative analysis of optimization and generalization properties of two-layer neural network and random feature models under gradient descent dynamics

Weinan E, Chao Ma, and Lei Wu. A comparative analysis of optimization and generalization properties of two-layer neural network and random feature models under gradient descent dynamics. Science China Mathematics, 63 0 (7): 0 1235--1258, jan 2020. doi:10.1007/s11425-019-1628-5...

2020 doi
[23]

Linearized two-layers neural networks in high dimension

Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Linearized two-layers neural networks in high dimension . The Annals of Statistics, 49 0 (2): 0 1029 -- 1054, 2021

2021
[24]

Deep residual learning for image recognition

Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770--778, 2016

2016
[25]

Neural tangent kernel: Convergence and generalization in neural networks

Arthur Jacot, Franck Gabriel, and Cl \'e ment Hongler. Neural tangent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems, 31, 2018

2018
[26]

Koornwinder

Tom H. Koornwinder. Dual Addition Formulas Associated with Dual Product Formulas, page 373–392. WORLD SCIENTIFIC, January 2018. ISBN 9789813228887. doi:10.1142/9789813228887_0019. URL http://dx.doi.org/10.1142/9789813228887_0019

2018 doi
[27]

ImageNet classification with deep convolutional neural networks

Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. ImageNet classification with deep convolutional neural networks. In Advances in Neural Information Processing Systems, 2012

2012
[28]

Layer-wise training of deep networks using kernel similarity, 2017

Mandar Kulkarni and Shirish Karande. Layer-wise training of deep networks using kernel similarity, 2017. URL https://arxiv.org/abs/1703.07115

2017 arXiv
[29]

Sparse deep belief net model for visual area v2

Honglak Lee, Chaitanya Ekanadham, and Andrew Ng. Sparse deep belief net model for visual area v2. volume Vol 20, 01 2007

2007
[30]

Finite versus infinite neural networks: an empirical study

Jaehoon Lee, Samuel Schoenholz, Jeffrey Pennington, Ben Adlam, Lechao Xiao, Roman Novak, and Jascha Sohl-Dickstein. Finite versus infinite neural networks: an empirical study. Advances in Neural Information Processing Systems, 33: 0 15156--15172, 2020

2020
[31]

Lee, Kazusato Oko, Taiji Suzuki, and Denny Wu

Jason D. Lee, Kazusato Oko, Taiji Suzuki, and Denny Wu. Neural network learns low-dimensional polynomials with sgd near the information-theoretic limit, 2024. URL https://arxiv.org/abs/2406.01581

2024 arXiv
[32]

Learning with invariances in random features and kernel models

Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Learning with invariances in random features and kernel models. In Conference on Learning Theory, pages 3351--3418. PMLR, 2021

2021
[33]

A theory of non-linear feature learning with one gradient step in two-layer neural networks, 2024

Behrad Moniri, Donghwan Lee, Hamed Hassani, and Edgar Dobriban. A theory of non-linear feature learning with one gradient step in two-layer neural networks, 2024. URL https://arxiv.org/abs/2310.07891

2024 arXiv
[34]

Alireza Mousavi-Hosseini, Denny Wu, Taiji Suzuki, and Murat A. Erdogdu. Gradient-based feature learning under structured data, 2023. URL https://arxiv.org/abs/2309.03843

2023 arXiv
[35]

Alireza Mousavi-Hosseini, Denny Wu, and Murat A. Erdogdu. Learning multi-index models with neural networks via mean-field langevin dynamics, 2024. URL https://arxiv.org/abs/2408.07254

2024 arXiv
[36]

Provable guarantees for nonlinear feature learning in three-layer neural networks

Eshaan Nichani, Alex Damian, and Jason D Lee. Provable guarantees for nonlinear feature learning in three-layer neural networks. arXiv preprint arXiv:2305.06986, 2023

2023 arXiv
[37]

Wick powers in stochastic pdes: an introduction

Giuseppe Da Prato and Luciano Tubaro. Wick powers in stochastic pdes: an introduction. 2007. URL https://api.semanticscholar.org/CorpusID:55493217

2007
[38]

Feature learning in neural networks and kernel machines that recursively learn features

Adityanarayanan Radhakrishnan, Daniel Beaglehole, Parthe Pandit, and Mikhail Belkin. Feature learning in neural networks and kernel machines that recursively learn features. arXiv preprint arXiv:2212.13881, 2022

2022 arXiv
[39]

Random features for large-scale kernel machines

Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In J. Platt, D. Koller, Y. Singer, and S. Roweis, editors, Advances in Neural Information Processing Systems, volume 20. Curran Associates, Inc., 2007. URL https://proceedings.neurips.cc/paper_file...

2007
[40]

Depth separation with multilayer mean-field networks

Yunwei Ren, Mo Zhou, and Rong Ge. Depth separation with multilayer mean-field networks. arXiv preprint arXiv:2304.01063, 2023

2023 arXiv
[41]

Fundamentals of stein’s method

Nathan Ross. Fundamentals of stein’s method. 2011

2011
[42]

Optimization-based separations for neural networks

Itay Safran and Jason Lee. Optimization-based separations for neural networks. In Conference on Learning Theory, pages 3--64. PMLR, 2022

2022
[43]

Theoretical insights into the optimization landscape of over-parameterized shallow neural networks

Mahdi Soltanolkotabi, Adel Javanmard, and Jason D Lee. Theoretical insights into the optimization landscape of over-parameterized shallow neural networks. IEEE Transactions on Information Theory, 65 0 (2): 0 742--769, 2018

2018
[44]

Probability in high dimensions

Ramon van Handel. Probability in high dimensions. 2016. URL https://web.math.princeton.edu/ rvan/APC550.pdf

2016
[45]

Nonlinear spiked covariance matrices and signal propagation in deep neural networks, 2024

Zhichao Wang, Denny Wu, and Zhou Fan. Nonlinear spiked covariance matrices and signal propagation in deep neural networks, 2024. URL https://arxiv.org/abs/2402.10127

2024 arXiv
[46]

Zihao Wang, Eshaan Nichani, and Jason D. Lee. Learning hierarchical polynomials with three-layer neural networks, 2023

2023
[47]

Lee, Qiang Liu, and Tengyu Ma

Colin Wei, Jason D. Lee, Qiang Liu, and Tengyu Ma. Regularization matters: Generalization and optimization of neural nets v.s. their induced kernel, 2020

2020
[48]

Tensor programs iv: Feature learning in infinite-width neural networks

Greg Yang and Edward J Hu. Tensor programs iv: Feature learning in infinite-width neural networks. In International Conference on Machine Learning, pages 11727--11737. PMLR, 2021

2021
[49]

@esa (Ref

\@ifxundefined[1] #1\@undefined \@firstoftwo \@secondoftwo \@ifnum[1] #1 \@firstoftwo \@secondoftwo \@ifx[1] #1 \@firstoftwo \@secondoftwo [2] @ #1 \@temptokena #2 #1 @ \@temptokena \@ifclassloaded agu2001 natbib The agu2001 class already includes natbib coding, so you should ...
[50]

\@lbibitem[] @bibitem@first@sw\@secondoftwo \@lbibitem[#1]#2 \@extra@b@citeb \@ifundefined br@#2\@extra@b@citeb \@namedef br@#2 \@nameuse br@#2\@extra@b@citeb \@ifundefined b@#2\@extra@b@citeb @num @parse #2 @tmp #1 NAT@b@open@#2 NAT@b@shut@#2 \@ifnum @merge>\@ne @bibitem@firs...
[51]

For a vector , we denote its Euclidean norm by 2

@open @close @open @close and [1] URL: #1 \@ifundefined chapter * \@mkboth \@ifxundefined @sectionbib * \@mkboth * \@mkboth\@gobbletwo \@ifclassloaded amsart * \@ifclassloaded amsbook * \@ifxundefined @heading @heading NAT@ctr thebibliography [1] @ \@biblabel @NAT@ctr \@bibset...

2017

Pith tools

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

[1] [1]

write newline

" write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION format.date year duplicate empty "emp...

[2] [2]

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

Emmanuel Abbe, Enric Boix Adser \`a , 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]

What can resnet learn efficiently, going beyond kernels? Advances in Neural Information Processing Systems, 32, 2019

Zeyuan Allen-Zhu and Yuanzhi Li. What can resnet learn efficiently, going beyond kernels? Advances in Neural Information Processing Systems, 32, 2019

work page 2019

[4] [4]

Backward feature correction: How deep learning performs deep learning

Zeyuan Allen-Zhu and Yuanzhi Li. Backward feature correction: How deep learning performs deep learning. arXiv preprint arXiv:2001.04413, 2020

arXiv 2001

[5] [5]

On exact computation with an infinitely wide neural net

Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. Advances in neural information processing systems, 32, 2019

2019

[6] [6]

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: 0 37932--37946, 2022

2022

[7] [7]

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. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Advances in Neural Information Processing Systems, volume 36, pages 17420--17449. Curran Associates, Inc., 2023. URL...

work page 2023

[8] [8]

Yu Bai and Jason D. Lee. Beyond linearization: On quadratic and higher-order approximation of wide neural networks, 2020

work page 2020