{"id":"87b1bbd4-2b7e-4c13-8c5b-4f13624aa89f","arxiv_id":"2411.17201","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A three-layer network with layerwise gradient descent provably recovers the span of multiple quadratic features in O~(d^4) samples and then learns any polynomial link in the features.","lead":"The paper proves that a three-layer neural network, trained one layer at a time, can recover several hidden quadratic features of a high-dimensional target and then learn the target as a polynomial of those features. This gives an O~(d^4)-sample guarantee that beats the d^{2p} sample cost of kernel methods.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1's parameter regime is internally inconsistent: Proposition 4's corollary requires m2 ≳ d^6, not d^4, because the dominant term in the learned-feature bound is m2-independent; under the stated m2 = eΩ(d^4), the η choice does not ensure |η⟨w,h(1)⟩| ≤ 1.","rationale":"The reader's CONDITIONAL verdict is reasonable: the core multi-feature recovery argument is substantial and the improvement over kernel methods is plausible, but there is a genuine formal gap. My stress test identifies a more concrete and more load-bearing flaw than the one the reader emphasized. The reader focused on Assumptions 2 and 3 restricting the target class; that is a real limitation but it is explicitly acknowledged by the authors as a deliberate separation from the degenerate single-direction case, and it does not break the proof for the stated class. The parameter-regime problem, by contrast, is an internal inconsistency: Proposition 4's corollary claims a width condition m2 ≳ d^4 that is algebraically insufficient for the claimed bound. The first term in the learned-feature estimate is independent of m2, so the only way to make (1/√m2)|⟨w,h(1)⟩| scale as κ2/d^6 is to take m2 ≳ d^6. This directly undermines Theorem 1 as stated, because the proof selects η based on the corollary and needs |η⟨w,h(1)⟩| ≤ 1 for the outer-layer polynomial representation and the Rademacher bound. The issue is fixable: the discussion already states m2 = eΩ(d^6 r^{p+1}) for full capture, and the sample complexity bound of Õ(d^4) for n1 remains intact; only the width condition in the formal theorem needs to be strengthened. Therefore the appropriate verdict remains CONDITIONAL — no change from the reader's verdict — but the revision required is more specific than the assumption criticism: correct Proposition 4's corollary and Theorem 1's stated m2 condition to eΩ(d^6 (and correspondingly in the proof). I did not find evidence that the multivariate universality lemma, the reconstruction construction, or the transfer-learning argument contain a similarly fatal flaw; those parts appear technically coherent, and the paper includes detailed appendices plus experiments, though no code is provided.","tokens_in":71318,"tokens_out":18921,"duration_ms":170189,"concrete_test":"Recompute the corollary of Proposition 4 with m2 = d^4 ι^{2p+4}. Using the definition A1 = (1/m2)⟨w,h(1)⟩ in the proof of Proposition 4 and Lemma 17's bound |A1| ≤ C3 ι^{p+2}/(m2 d^3), the first contribution to (1/√m2)|⟨w,h(1)⟩| is at least c ι^{p+2}/(d^3√m2) = c/d^5. Compare this with the corollary's claimed upper bound κ2 ι^5/d^6: for large d the lower bound exceeds the upper bound by a factor proportional to d, falsifying the corollary. Equivalently, substitute m2 = d^4 and η = C m2^{-1/2} κ2^{-1} ι^{-5} d^6 into the lower bound to obtain η|⟨w,h(1)⟩| ≳ d ι^{p+2}/κ2 ≫ 1, contradicting the asserted |η⟨w,h(1)⟩| ≤ 1. The test settles whether the stated m2 = eΩ(d^4) regime supports the proof; rerunning the same algebra with m2 ≥ d^6 confirms the corrected regime.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Proposition 4 bounds |⟨w, h(1)(x′)⟩| by three terms. Tracing the proof, the first term originates from Lemma 17's bound on A1, which is ι^{p+2}/(m2 d^3) for the quantity (1/m2)⟨w,h(1)⟩, so its contribution to |⟨w,h(1)⟩| is ι^{p+2}/d^3, independent of m2. The corollary of Proposition 4 then claims that when m2 ≳ d^4 ι^{2p+4} and n ≳ d^4 ι^{2p+4}, we have (1/√m2)|⟨w,h(1)⟩| ≲ κ2 ι^5/d^6. But plugging m2 = d^4 ι^{2p+4} into the first term gives ι^{p+2}/(d^3 √m2) = 1/d^5, which is a factor d κ2^{-1} ι^{-5} larger than the claimed d^{-6} bound. The assertion only becomes valid when m2 ≳ d^6. This is not a cosmetic issue: the subsequent choice η = C m2^{-1/2} κ2^{-1} ι^{-5} d^6 is explicitly designed to make |η⟨w,h(1)⟩| ≤ 1, a precondition for the polynomial construction of the outer layer (Lemma 33), for Proposition 2, and for the Rademacher complexity analysis. Under the theorem's stated assumption m2 = eΩ(d^4), that precondition fails, so the proof of Theorem 1 as written does not go through. The fix is straightforward — strengthen the condition to m2 = eΩ(d^6), which matches the authors' own discussion after Theorem 1, where m2 = eΩ(d^6 r^{p+1}) is stated as the regime for full feature capture. Thus the conceptual claim that n1 samples of order d^4 and polynomial width suffice is likely salvageable, but the formal statement needs correction.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":71772,"tokens_out":12504,"duration_ms":112384,"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":[{"comment":"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.","section":"Appendix B.2 (Proposition 4) and Theorem 1 (Section 3)"}],"minor_comments":[{"comment":"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\".","section":"Abstract"},{"comment":"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":"Appendix C.1, Proposition 6"},{"comment":"The heading contains the typo \"Prepocessed target function\"; it should be \"Preprocessed target function\".","section":"Section 2.2, Assumption 3"},{"comment":"The sentence contains the duplicate phrase \"representations presentations\" and should be corrected.","section":"Section 4.1"},{"comment":"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.","section":"Appendix C"}],"recommendation":"major_revision","confidential_remarks":"The core idea appears salvageable, and the d^6 threshold that is needed for the proof already appears in the discussion after Theorem 1. I would ask the authors to fix the parameter regime in the theorem and in Proposition 4, and to re-check every place where the m2 threshold is quoted. The advertised O~(d^4) sample complexity may still be defensible after the correction, but the theorem as currently stated is not supported by the proof."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nThat said, the proof as written has a parameter inconsistency. The corollary of Proposition 4 that controls |<w,h^(1)>|/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 η|<w,h^(1)>| ≈ 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.\n\nSmaller 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.\n\nNet: 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.","headline":"Real advance on multiple quadratic features, but the formal width assumption needs repair before the theorem as stated goes through.","tokens_in":72293,"tokens_out":6216,"would_cite":true,"duration_ms":63220,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68T07","68Q32"],"pacs":[],"model":"deepseek-v4-flash","headline":"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…","keywords":["three-layer neural networks","feature learning","hierarchical polynomials","quadratic features","multi-index model","layerwise gradient descent","sample complexity","universality"],"falsifier":"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.","tokens_in":95,"feed_emoji":"🧠","tokens_out":12033,"duration_ms":161360,"temperature":0.7,"pith_summary":"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.","feed_headline":"Three-layer nets learn multiple hidden features in ~d^4 samples","feed_subtitle":"Layerwise training provably beats the d^{2p} samples kernels need for hierarchical polynomials.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Defines the multi-index model and layerwise GD framework this paper generalizes; supplies the preprocessing projection onto low spherical harmonics and the tensor moment factorization used throughout the proof.","marker":"[Damian et al., 2022]"},{"why":"Establishes three-layer learning of a single quadratic feature with $\\widetilde{\\Theta}(d^4)$ samples; the training algorithm, target class, and Gegenbauer activation choice are the single-feature predecessor extended here to $r$ features.","marker":"[Nichani et al., 2023]"},{"why":"Extends single-feature learning to degree-$k$ polynomials with $\\widetilde{\\mathcal{O}}(d^k)$ samples; provides the comparison cases that this paper's multi-feature result supersedes.","marker":"[Wang et al., 2023]"},{"why":"Supplies the Stein-method inequalities, including the Wasserstein-1 characterization and covariance identity, on which the new multivariate universality lemma is built.","marker":"[van Handel, 2016]"},{"why":"Gives the $\\widetilde{\\Omega}(d^k)$ sample lower bound for kernel methods on degree-$k$ polynomials, the benchmark that the $\\widetilde{\\mathcal{O}}(d^4)$ feature-learning bound is compared against.","marker":"[Ghorbani et al., 2021]"},{"why":"Provides the leap-index lower bound used to argue that any single-gradient-step feature-learning algorithm needs $\\Omega(d^4)$ samples for the degree-4 terms, supporting near-optimality.","marker":"[Dandi et al., 2023b]"},{"why":"Identifies the second-stage architecture as a random-feature model; the Rademacher complexity bounds for this model close the generalization argument in the theorem proof.","marker":"[Rahimi and Recht, 2007]"},{"why":"Supplies hypercontractivity bounds for polynomials on the sphere, used to truncate the targets and control the concentration errors in the first-stage analysis.","marker":"[Mei et al., 2021]"}],"fun_headline_variants":["Three-layer nets master multiple nonlinear features in ~d^4 samples","Layerwise training beats kernel d^(2p) bound for hierarchical polynomials","Provable d^4 sample complexity for three-layer feature learning","Three-layer networks efficiently learn multi-feature polynomial hierarchies","Beyond single features: three-layer nets learn multiple quadratic features"],"cache_read_input_tokens":74240,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Three-layer nets master multiple nonlinear features in ~d^4 samples","Layerwise training beats kernel d^(2p) bound for hierarchical polynomials","Provable d^4 sample complexity for three-layer feature learning","Three-layer networks efficiently learn multi-feature polynomial hierarchies","Beyond single features: three-layer nets learn multiple quadratic features"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000236,"raw_usage":{"total_tokens":1648,"prompt_tokens":1233,"completion_tokens":415,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":849,"completion_tokens_details":{"reasoning_tokens":329}},"tokens_in":849,"tokens_out":415,"duration_ms":4418,"temperature":1.0,"reasoning_tokens":329,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T12:23:42.955159+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Probability in high dimensions","cited_arxiv_id":null,"evidence_quote":"Supplies the Stein-method inequalities, including the Wasserstein-1 characterization and covariance identity, on which the new multivariate universality lemma is built."},{"cited_title":"Random features for large-scale kernel machines","cited_arxiv_id":null,"evidence_quote":"Identifies the second-stage architecture as a random-feature model; the Rademacher complexity bounds for this model close the generalization argument in the theorem proof."}],"review_version":1}