{"id":"d9cfe128-9177-40de-9184-f78d8cb4cbe1","arxiv_id":"2505.21475","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For well-behaved real-valued multi-index models, the paper gives PAC learners with d^{O(m)} complexity and nearly matching SQ lower bounds, plus a network-size-independent learner for homogeneous Lipschitz ReLU networks.","lead":"New algorithms and nearly matching lower bounds characterize the sample complexity of learning real-valued multi-index models under Gaussian inputs with square loss. The paper's main application removes the exponential dependence on network size in prior algorithms for Lipschitz homogeneous ReLU networks.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma D.7's cube-discretization step relies on an unjustified independence claim; without a correct averaging argument the main progress step (Proposition D.9) is unproven.","rationale":"The paper is a serious theoretical contribution with a detailed appendix, and the upper/lower bound structure is coherent. The reader's weakest assumption (Definition 1.3(2b)) points in the right direction, but the concern raised here is sharper: even granting condition (2b), the proof of Lemma D.7 contains a specific, checkable step that appears false as written. Since Proposition 2.2 / D.9 is the engine of the upper bound, this is load-bearing. The likely cross-reference typo (Fact D.32 vs Lemma D.25) is minor. The SQ lower bound and the homogeneous-Lipschitz application may still be correct, and the gap might be repairable by replacing the pointwise definition with a cube-averaged distinguishing-moments condition or by a more careful smoothness argument, but as submitted the main theorem's proof is incomplete. Hence the verdict should be CONDITIONAL: accept subject to a correct proof or equivalent restatement of the cube-discretization step.","tokens_in":73589,"tokens_out":11031,"duration_ms":121935,"concrete_test":"Independently re-derive the 'Existence of correlating polynomials' part of Lemma D.7 without invoking independence of y' and z_V. In particular, start from the pointwise guarantee and prove that for a cube S of width eta there exists a common degree-m polynomial p and interval I with E[p(x_U)1(y in I)|x_V in S] >= poly(sigma, epsilon, ...), or exhibit a function satisfying Definition 1.3 whose conditional moments are pointwise large but vanish on every cube of positive width. The second outcome would falsify the discretization step and require a strengthening of the well-behaved condition to a cube-level condition.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Lemma D.7 ('Cube-interval Discretization Suffices') is the bridge that lets FindDirection work with coarse cube-interval statistics. Its proof resamples x'_V from the Gaussian restricted to the cube S_x and defines y' to be the label of the resampled point, then asserts 'since y' is independent of z_V when conditioned on its cube S_{z_V}' to conclude E[p(x_U)1(y'=y0)|x_V in S] >= poly(...). This is not justified: y' is drawn from D_{y|x=(x'_V,x'_{V^perp})}, which depends on x'_V; conditioning on x'_V in S does not remove that dependence. The unconditional independence of x_U and x_V under N_d does not imply conditional independence given y'. Without a valid cube-averaging argument, there is no demonstrated reason that any single degree-m polynomial correlates with the label on a positive-mass cube, so Proposition D.9 (the progress guarantee used at every iteration of Algorithm 3) loses its basis. Since Theorem 1.4 is an iterative application of Proposition D.9, the central algorithmic claim is currently supported by this gap.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies PAC learning of real-valued multi-index models (MIMs) under Gaussian marginals with square loss, in the presence of adversarial label noise. The main algorithmic result, Theorem 1.4, claims a learner for a class of 'well-behaved' MIMs with sample complexity d^{O(m)} 2^{poly(K/(εσ))} and error τ + OPT + ε. The appendices develop an iterative subspace-finding algorithm (LearnMIMs / Algorithm 3), prove a progress lemma (Proposition D.9), and derive applications to positive-homogeneous Lipschitz MIMs, including homogeneous ReLU networks, and to low-rank polynomials. The paper also proves an SQ lower bound, Theorem 1.10 / Theorem C.19, based on a new relativized non-Gaussian component analysis (RNGCA) lower bound that avoids chi-squared finiteness assumptions.","tokens_in":73743,"tokens_out":10922,"duration_ms":129610,"significance":"If the main claims are correct, this is a substantial contribution: it would give the first polynomial-in-dimension learner for Lipschitz homogeneous K-MIMs with complexity independent of network width and depth, and a nearly matching SQ lower bound of d^{Ω(m)}. The SQ lower bound part appears technically substantial and self-contained: it extends [DKRS23] to a relativized setting without chi-squared assumptions, using truncation, reweighting, and Hermite/Fourier analysis. The applications are also well motivated and the structural lemmas for homogeneous Lipschitz functions (Lemma D.25 and Claim D.26) are plausible and interesting. However, the central algorithmic progress lemma contains a nontrivial gap in the cube-discretization argument, and the formal theorem statements do not match the advertised error guarantee. These issues affect the main algorithmic claim and require significant repair.","major_comments":[{"comment":"The error guarantee stated in the introduction and abstract, err_D(h) ≤ τ + OPT + ε, is not what is proved. Theorem D.5 establishes only err_D(h) ≤ (√τ + ε + √OPT)^2 + ε = τ + OPT + 2√(τ OPT) + 2(√τ+√OPT)ε + ε^2 + ε. When OPT is large relative to τ and ε, the extra cross terms can exceed ε by an unbounded factor, so the advertised bound does not follow by a constant rescaling of ε. The same squared-sum form appears in Proposition 2.2 and Proposition D.9. This is a load-bearing discrepancy between the paper's central claim and its formal algorithmic results; the statements and proof need to be aligned, or the stronger bound needs to be proved.","section":"Appendix D.1.3, Theorem D.5 versus Theorem 1.4"}],"minor_comments":[{"comment":"The proof says 'Fact D.32 and lemmas D.27 and D.28 together imply...' but Fact D.32 is stated later in Section D.3.2 for the class of low-rank polynomials P^α_{K,m}, not for the Lipschitz homogeneous class H_{K,L}. The correct structural ingredient for H_{K,L} appears to be Lemma D.25. Please correct the reference.","section":"Appendix D.3.1, Proof of Theorem D.22"},{"comment":"In the displayed chain after 'by expanding the square', the term 'E[(f^2(x)-y)^2]' appears to be a typo for 'E[(f(x)-y)^2]'.","section":"Appendix D.1.2, Lemma D.7"},{"comment":"The final sentence of the proof states 'Ex∼Nd[(f(x)−hS(x))2] = τ + ǫ' but the preceding argument only supports an inequality of the form '≤ τ + O(ǫ)'.","section":"Appendix D.1.2, Lemma D.6"},{"comment":"The notation 'Bm(B)' in Definition C.12 should be 'B_k(B)' or similar; as written it is confusing.","section":"Appendix C.1.1, Definition C.12"},{"comment":"The final line contains a stray bracket: 'completes the proof of Proposition C.7]' should be 'completes the proof of Proposition C.7.'","section":"Appendix C.1.2, Proof of Proposition C.7"}],"recommendation":"major_revision","confidential_remarks":"The SQ lower-bound section appears technically solid and likely publishable after revision. The main concern is the algorithmic side: the cube-averaging gap in Lemma D.7 is central, and the formal error bound in Theorem D.5 does not match the advertised guarantee of Theorem 1.4. These are fixable in principle, but they require real work, not just copy-editing."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Candid take: this is a substantial paper, but the main algorithmic theorem has a hole that needs to be fixed before it can be trusted. The SQ lower bound section is a genuine contribution, and the application to homogeneous Lipschitz MIMs is a good step if the algorithm is repaired.\n\nWhat's new: real-valued MIMs require conditioning on intervals rather than point labels, and the paper develops the L2-loss analysis and a relativized NGCA lower bound that works without a finite chi-squared assumption. That last item is real: Theorem 3.3 and its proof via the truncated and reweighted distribution appear careful. The application to positive-homogeneous L-Lipschitz K-MIMs, giving a ReLU-network learner with no dependence on network size, is the kind of fixed-parameter result people will care about.\n\nWhere the soft spots are: the stress-test concern about Lemma D.7 is legitimate. The proof resamples x'_V within a cube and defines y' as the label of the resampled point, then asserts that y' is independent of z_V conditioned on the cube. That does not follow: y' is drawn from D_{y|x=(x'_V, x'_{V^\\perp})}, which depends on the exact x'_V, and conditioning on the cube does not remove that dependence. The well-behaved condition only gives moments pointwise in z; the cube-averaged inequality needs a separate argument. Proposition D.9 rests on this lemma, so Theorem 1.4 is currently unsupported. This is not a minor typo. The other issue the reader flagged — Theorem D.22 cites Fact D.32, which is about low-rank polynomials and defined later — is cosmetic and should be Lemma D.25.\n\nThe rest of the appendix is unusually detailed and the high-level structure is coherent. The lower-bound reduction is sound in outline. This paper is for people working on computational-statistical gaps for Gaussian MIMs. It deserves a serious referee, but the referee should be asked to focus on the cube-averaging step first. I would not accept it as is; it needs a repaired Lemma D.7 or a revised progress lemma.","headline":"Strong SQ lower-bound paper; the main learner has a gap in the cube-discretization step that the authors need to close.","tokens_in":74355,"tokens_out":7177,"would_cite":false,"duration_ms":77229,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q32","68T05"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims that every well-behaved multi-index model is robustly learnable with polynomial-in-dimension sample complexity, backed by a nearly matching statistical-query lower bound.","keywords":["multi-index models","agnostic PAC learning","statistical query lower bounds","Gaussian marginals","robust regression","ReLU networks","conditional moments","subspace recovery"],"falsifier":"Take a concrete $K$-MIM $f$ with bounded variation and a proper subspace $V$ such that no function of $x_V$ approximates $f$ within $\\tau$, and numerically estimate every conditional moment $\\mathbb{E}[p(x_U) \\mid x_V = z,\\, y=f(x)]$ for degree-$\\le m$ polynomials $p$. If all such moments are below $\\sigma$ on almost all $z$ while the $L^2$ error of the best function of $x_V$ remains above $\\tau$, the well-behaved property fails, and the paper's own SQ theorem predicts that any SQ learner requires query tolerance $d^{-\\Omega(m)}$. One could settle the matter by simulating an SQ learner on this distribution and checking whether error $\\tau + \\mathrm{OPT} + \\epsilon$ is attainable with $d^{o(m)}$ query cost.","tokens_in":73321,"feed_emoji":"🧮","tokens_out":7814,"duration_ms":82548,"temperature":0.7,"pith_summary":"This paper tries to establish that real-valued multi-index models — functions of a Gaussian input that depend only on an unknown $K$-dimensional subspace — can be learned robustly under square loss and adversarial label noise at a cost that is a fixed polynomial in the ambient dimension $d$ once the model's order $m$ is fixed. The proposed algorithm is iterative: it grows a sequence of subspaces, and at each step either the current subspace already supports a good hypothesis or conditional moments in the still-missing directions reveal a new direction. The resulting sample complexity is $d^{O(m)} 2^{\\mathrm{poly}(K/(\\epsilon\\sigma))}$, and the returned hypothesis achieves error $\\tau + \\mathrm{OPT} + \\epsilon$ in the agnostic PAC model. A nearly matching SQ lower bound shows that when such distinguishing moments fail to exist for some subspace, any statistical-query learner must pay $d^{\\Omega(m)}$ complexity, making the algorithm qualitatively optimal in dimension. The concrete payoff is the first polynomial-in-$d$ learner for positive-homogeneous Lipschitz multi-index models, and hence a ReLU-network learner whose complexity is independent of network size.","feed_headline":"Robust multi-index learning now costs a fixed polynomial in dimension","feed_subtitle":"Same machinery yields a ReLU-network learner with no dependence on network size.","key_machinery":"The load-bearing mechanism is the iterative subspace-approximation loop of Algorithm 1 (LearnMIMs). At each iteration it holds a subspace $V$, partitions $V$ and the label line $\\mathbb{R}$ into cubes and intervals, and inside each cell runs degree-$m$ polynomial regression of the indicator $1(y\\in I)$ against the coordinates $x_{V^\\perp}$. The gradients of these regression polynomials are aggregated into an influence matrix $U = \\sum_{S,I} \\mathbb{E}[\\nabla p_{S,I}\\nabla p_{S,I}^\\top \\mid x\\in S] \\Pr[S]$. The progress step, Proposition 2.2, states that if the piecewise-constant hypothesis on $V$ has error above $\\tau + \\mathrm{OPT} + \\epsilon$, then some eigenvector of $U$ with eigenvalue above threshold has non-trivial projection onto the hidden subspace $W$; adding that vector decreases the potential $\\sum_i \\|w^{(i)}_{V^\\perp}\\|^2$. On the lower-bound side, the paper develops relativized non-Gaussian component analysis: the conditional distributions of $x_{V^\\perp}$ given $(x_V,y)$ are rotated by a random orthogonal map, and because they match $m$ moments of the standard Gaussian, a Fourier--Hermite analysis shows every bounded SQ query is almost unchanged under the rotation, forcing either a query of tolerance $d^{-\\Omega(m)}$ or exponentially many queries.","core_discovery":"At the center is Theorem 1.4: for any distribution with standard-Gaussian $x$-marginal and any well-behaved MIM $f$ in the class $\\mathcal{F}(K,m,\\zeta,\\tau,\\sigma)$ with $\\zeta \\ge \\mathrm{OPT}+\\epsilon$, there is an agnostic PAC learner that draws $d^{O(m)} 2^{\\mathrm{poly}(K/(\\epsilon\\sigma))}$ samples, runs in polynomial time, and returns $h$ with $\\mathrm{err}_D(h) \\le \\tau + \\mathrm{OPT} + \\epsilon$. The class is defined so that for every subspace $V$, either $f$ is already $\\tau$-close to a function of the projection $x_V$, or the joint distribution of $(x,y)$ has a degree-$m$ distinguishing moment in the directions of the hidden subspace outside $V$. The discovery is that this local, moment-based condition is both sufficient for a $d^{O(m)}$-sample robust learner and, in the SQ model, essentially necessary: if some subspace $V$ has no such distinguishing moments, any SQ learner requires roughly $d^{\\Omega(m)}$ query complexity. The paper then proves the well-behaved condition for concrete classes, most notably positive-homogeneous $L$-Lipschitz $K$-MIMs, obtaining a learner using $d^2 2^{O(K^3 L^2/\\epsilon^2)}$ samples and, as a corollary, a ReLU-network learner with complexity independent of the network size.","pith_inferences":["The guarantee is for square-loss PAC learning, not parameter recovery: two different hidden subspaces that induce the same labels are not separated, so the result leaves open whether this conditional-moment search can be sharpened into recovery guarantees for identifiable models.","For the special case $m=2$, the paper's own remark suggests that replacing polynomial regression by covariance estimation in operator norm could reduce the $d^2$ sample dependence to $O(d)$; validating that refinement would make the positive-homogeneous MIM learner nearly linear in dimension.","The SQ threshold being exactly the absence of distinguishing moments suggests that any algorithm that succeeds where this one fails would have to operate outside the statistical-query model, since the lower bound applies to all SQ learners for such classes.","Because the returned hypothesis is piecewise constant on the recovered subspace, the ReLU-network corollary does not assert that gradient-based training finds the network; it leaves open whether optimization over networks achieves the same sample bound."],"forward_implications":["Agnostic robust regression for well-behaved MIMs runs in $d^{O(m)} 2^{\\mathrm{poly}(K/(\\epsilon\\sigma))}$ samples and returns error $\\tau + \\mathrm{OPT} + \\epsilon$.","In the realizable and independent-noise settings, the same learner uses $d^{O(m)} 2^{\\mathrm{poly}(K)} (1/\\epsilon)^{O(K)}$ samples, with exponential dependence only on $K$.","If some subspace has no degree-$m$ distinguishing moments, any SQ learner for the corresponding MIM class requires queries of accuracy $d^{-\\Omega(m)}$ or exponentially many queries, so the upper bound is qualitatively tight in $m$.","Positive-homogeneous $L$-Lipschitz $K$-MIMs are learnable with $\\mathrm{poly}(d) 2^{\\mathrm{poly}(KL/\\epsilon)}$ samples, the first such guarantee for this nonparametric class.","As a direct corollary, Lipschitz homogeneous ReLU networks are PAC learnable with complexity independent of the network size $S$, removing the exponential dependence in $S$ of prior work."],"supporting_citations":[{"why":"Provides the iterative subspace-approximation framework for discrete-valued MIMs that this paper extends to real-valued labels and square loss.","marker":"[DIKZ25]"},{"why":"Gives the prior algorithm for homogeneous ReLU networks with exponential dependence on network size, which Corollary 1.7 improves upon.","marker":"[CKM22]"},{"why":"Supplies the SQ lower-bound technique that works with moment matching alone, which the paper generalizes to relativized non-Gaussian component analysis.","marker":"[DKRS23]"},{"why":"Establishes the foundational SQ-dimension framework for non-Gaussian component analysis that the RNGCA lower bound builds on.","marker":"[DKS17]"},{"why":"Gives the prior algorithm for low-rank polynomials, recovered as an application of the general learner in Appendix D.3.","marker":"[CM20]"},{"why":"Defines the generative exponent for single-index models that Definition 1.3 reduces to when $K=1$, and whose SQ lower bound is generalized here.","marker":"[DPLB24]"}],"fun_headline_variants":["Robust MIM learning: dimension-polynomial, SQ-tight","ReLU networks learnable independent of network size","SQ bounds match new d^{O(m)}-sample MIM learner","Multi-index models: efficient robust PAC, size-free ReLU","New learner for MIMs: d^{O(m)} samples, matches SQ lower bound"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"Everything hinges on condition (2b) of Definition 1.3: for every subspace $V$ reached, either the target is already $\\tau$-close to a function of the projection $x_V$, or the conditional law of $x$ in the missing directions, given $x_V$ and the label, has a degree-$m$ moment at least $\\sigma$ on a non-trivial fraction of inputs; if this fails for some $V$, no new direction is found and the argument stalls.","fun_headline_variants_meta":{"raw":{"variants":["Robust MIM learning: dimension-polynomial, SQ-tight","ReLU networks learnable independent of network size","SQ bounds match new d^{O(m)}-sample MIM learner","Multi-index models: efficient robust PAC, size-free ReLU","New learner for MIMs: d^{O(m)} samples, matches SQ lower bound"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001232,"raw_usage":{"total_tokens":5184,"prompt_tokens":1193,"completion_tokens":3991,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":809,"completion_tokens_details":{"reasoning_tokens":3899}},"tokens_in":809,"tokens_out":3991,"duration_ms":34027,"temperature":1.0,"reasoning_tokens":3899,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T13:26:31.708043+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a concrete $K$-MIM $f$ with bounded variation and a proper subspace $V$ such that no function of $x_V$ approximates $f$ within $\\tau$, and numerically estimate every conditional moment $\\mathbb{E}[p(x_U) \\mid x_V = z,\\, y=f(x)]$ for degree-$\\le m$ polynomials $p$. If all such moments are below $\\sigma$ on almost all $z$ while the $L^2$ error of the best function of $x_V$ remains above $\\tau$, the well-behaved property fails, and the paper's own SQ theorem predicts that any SQ learner requires query tolerance $d^{-\\Omega(m)}$. One could settle the matter by simulating an SQ learner on this distribution and checking whether error $\\tau + \\mathrm{OPT} + \\epsilon$ is attainable with $d^{o(m)}$ query cost.","supporting_citations":[],"review_version":1}