{"id":"e10a75ab-55f3-409d-a7d5-9052ce5de07c","arxiv_id":"2501.00817","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Any fixed parity of size at least logarithmic in the dimension requires exponentially many perturbed-gradient steps before the expected correlation loss moves away from its trivial value.","lead":"Gradient descent with Gaussian noise cannot learn any fixed parity function, including the full parity over all bits, using one-hidden-layer ReLU networks, even though such networks can express the parity. The proof rests on a new bound showing that Fourier coefficients of weighted majority functions are exponentially small on average.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 2's proof applies Lemma 2 to N(0,(j+2)σ²I) iterates; scale invariance introduces a √(j+2) factor, so the union bound gives ≈T^{3/2}ε, not (T+1)ε, unless the |S| condition is strengthened.","rationale":"The reader's weakest-assumption pinpoints the reliance on near-spherical Gaussian marginals, which is indeed the structural engine of the proof, but the more immediate and concrete problem is that the proof applies a variance-specific Markov bound to iterates with growing variance without accounting for scale. This is a genuine internal gap in the proof of the central theorem, not merely a scope limitation. It is load-bearing because it affects the explicit probability bound and the stated condition on |S|: the proof as written does not establish Theorem 2 in the parameter regime claimed. The gap is likely repairable by strengthening the min-size assumption to include 72 ln(6ndσ√(T+1)) or by tracking the √(j+2) factor in the failure probability, so the overall qualitative hardness claim (super-polynomial iterations in |S|) may survive; this warrants a conditional accept pending correction rather than a rejection. The paper's independent Fourier result (Theorem 3/6) appears substantively correct and may be of independent value, but the main hardness theorem's proof needs revision.","tokens_in":30971,"tokens_out":12293,"duration_ms":111896,"concrete_test":"Recompute the union-bound step in the proof of Theorem 2 (Eq. (6)-(7)) without invoking Lemma 2 directly on N(0,(j+2)σ²I). Instead, use the scale identity ∇F(cθ)=c∇F(θ) to express each summand as P(‖∇F(θ')‖≥ε/√(j+2)) with θ'∼N(0,σ²I). If the corrected bound is ∑_{j=1}^{T+1}√j·ε, verify numerically whether the theorem's stated assumption on |S| covers the required condition 72 ln(6ndσ√(T+1)) for, say, σ=0.1, T=100, d=30, n=10. If it does not, the proof has a gap and the theorem's min-size condition must be strengthened.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"In the proof of Theorem 2 (Section 3.3), the union bound over j in Eq. (6) is bounded by (T+1)ε, with the justification that ∑_{t=-1}^j ξ_t ∼ N(0,(j+2)σ²I) and Lemma 2 applies. But Lemma 2 is stated and proved for θ ∼ N(0,σ²I), and its Markov bound depends on the variance scale through E‖∇F_S‖ ≤ 6ndσ e^{-|S|/8}. For a partial sum S_j := ∑_{t=-1}^j ξ_t, scale invariance of the ReLU network gives ∇F_S(cθ) = c∇F_S(θ), so S_j = √(j+2)·θ' with θ' ∼ N(0,σ²I), and ‖∇F_S(S_j)‖ = √(j+2)‖∇F_S(θ')‖. Consequently, P(‖∇F_S(S_j)‖ ≥ ε) = P(‖∇F_S(θ')‖ ≥ ε/√(j+2)) ≤ √(j+2) e^{-|S|/18}, i.e., √(j+2)ε, not ε. Summing over j gives Θ(T^{3/2})ε, not (T+1)ε. The theorem's assumption |S| ≥ 72 max{ln(6ndσ), ln(5ndσ²(T+1))} does not always imply the stronger requirement |S| ≥ 72 ln(6ndσ√(T+1)); e.g., σ=0.1, T=100, d=30, n=10 gives a gap. Thus the proof of the main theorem, as written, has a missing factor in the failure-probability bound; the conclusion may survive with a strengthened min-size condition, but the displayed chain is incorrect.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies hardness of learning fixed parity functions p_S by perturbed gradient descent (PGD) on one-hidden-layer ReLU networks. After showing (Theorem 1) that such networks can express p_S exactly with O(|S|) neurons and polynomially bounded weights, the main result (Theorem 2) states that for |S| at least logarithmic in the problem parameters, PGD with Gaussian initialization and zero-mean Gaussian perturbations leaves the expected correlation loss exponentially close to zero unless the number of iterations is exponential in |S|. A parallel result (Theorem 5) is proved for the squared loss with a single ReLU neuron, complementing a weak-learnability construction (Theorem 4). The key new analytic ingredient is Theorem 3 (and its biased variant Theorem 6): the Fourier coefficient of a linear threshold function corresponding to S decays exponentially in |S| in expectation over spherically symmetric weights. The proofs couple the PGD process to a clipped process whose updates are pure Gaussian steps, and use the smallness of gradients almost everywhere to show that the coupling is close in total variation.","tokens_in":31346,"tokens_out":19304,"duration_ms":170498,"significance":"If the technical gaps identified below are repaired, the paper would make a solid and appropriately scoped contribution. Its main value is conceptual: it replaces a worst-case-over-parities SQ statement with a fixed-parity hardness statement in a concrete, standard model (PGD, ReLU networks, population loss), and it covers the full parity function, which was explicitly left open by Abbe and Boix-Adsera. The Fourier-coefficient theorem (Theorem 3/6) is an independent contribution with explicit constants. The paper also carefully proves expressibility and weak learnability (Theorems 1 and 4), so the hardness is not due to lack of capacity. The limitations—population loss, PGD rather than SGD, and reliance on spherical symmetry—are stated honestly in Section 5.","major_comments":[{"comment":"The union bound over j applies Lemma 2 to S_j = \\sum_{t=-1}^j \\xi_t, invoking only that S_j ~ N(0,(j+2)\\sigma^2 I). Lemma 2 is proved for \\theta ~ N(0,\\sigma^2 I), and because the gradient is positively homogeneous in the full parameter vector, the correct bound is P(||\\nabla F_S(S_j)|| \\ge \\varepsilon) \\le \\sqrt{j+2}\\,e^{-|S|/18}, not \\varepsilon. Hence the displayed '(T+1)\\varepsilon' should be \\Theta(T^{3/2})\\varepsilon, and the theorem's stated failure probability (\\eta\\sqrt{T}/(2\\sigma)+T+2)e^{-|S|/18} is not established as written. The qualitative exponential-hardness claim survives after replacing the probability bound by a polynomial-in-T factor or strengthening the minimal-size condition by an extra log T term, but the proof needs this correction.","section":"Section 3.3, Eq. (6) and following paragraph"},{"comment":"The chain P(||\\nabla F_lin(v_t)|| \\ge \\varepsilon) = P(||\\nabla F_lin(v_t)||^2 \\ge \\varepsilon^2) \\le E||\\nabla F_lin(v_t)||^2/\\varepsilon^2 \\le \\varepsilon is invalid, since the second-moment bound E||\\nabla F_lin(v_t)||^2 \\le \\varepsilon (established a few lines later) yields E/\\varepsilon^2 = 1/\\varepsilon after Markov, not \\varepsilon. A correct proof would need a first-moment bound such as E||\\nabla F_lin(v_t)|| \\le C\\sqrt{d}\\,e^{-|S|/8} (obtainable from Theorem 6 and Jensen) and then a Markov step giving e^{-5|S|/72} per term, which requires a stronger |S| condition than the one stated, or a different arrangement of constants. The displayed derivation does not go through.","section":"Section 4, Eq. (34)"},{"comment":"The theorem asserts that with probability at least 1-\\varepsilon, F_S(\\theta_T) > 1-C\\varepsilon, where C=2+T+\\eta\\sqrt{T}/\\sigma. The proof instead concludes P(F_S(\\theta_T) \\le 1-\\varepsilon) \\le C\\varepsilon. These statements are incomparable as written: the latter gives a weaker probability for a stronger threshold and does not imply the former. The theorem should either be restated in the same format as Theorem 2 (failure probability C\\varepsilon, threshold \\varepsilon) or the proof must establish the stated probability with the weaker threshold.","section":"Section 4, Theorem 5 statement and proof"}],"minor_comments":[{"comment":"The statement uses F_S(w_t,b_t) but the bound refers to the final iterate; replace t by T, or write \\theta_T.","section":"Section 4, Theorem 5 statement"},{"comment":"The expression \\theta_{t-1}+\\Delta_{t-1} appears in the KL computation, but with the convention \\theta_{t+1}=\\theta_t-\\Delta_t in Eq. (3) it should be \\theta_{t-1}-\\Delta_{t-1}. The subsequent Gaussian means use the correct sign, so this is a typographical issue.","section":"Appendix A.2.1, Lemma 1 proof"},{"comment":"The constants imported from Theorem 6 are not fully consistent: the bound for E(\\partial_{b_j}F)^2 uses 4e^{-|S|/4}, while Theorem 6 states a constant smaller than 8e^{-|S|/4}; later lines use 6e^{2.55}\\sqrt{2\\pi}/\\sqrt{\\pi}. The inequalities are loose enough, but the constants should be reconciled for a clean proof.","section":"Appendix A.2.2, Lemma 2 proof"},{"comment":"The notation [z]_\\varepsilon = z\\cdot 1\\{z>\\varepsilon\\} is used for vectors as well as scalars; clarify that the clipping is applied to the norm, as in the definition used for Theorem 2.","section":"Section 4, Eq. (28)"},{"comment":"The Taylor expansion of arccos is evaluated at x^Ty/d values that can equal \\pm 1; since the coefficients satisfy \\alpha_j = O(j^{-3/2}), the endpoint convergence is absolute and easily justified, but this should be stated explicitly.","section":"Section 3.2, proof of Theorem 3"}],"recommendation":"major_revision","confidential_remarks":"The reader's conditional assessment is accurate. I share the view that the paper's core idea is sound and the proof gaps are local, but the current text should not be accepted until Theorems 2 and 5 are corrected. There is no evidence of circularity, fitted parameters, or an invented-entity problem."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Worth a careful read. The paper proves something genuinely new: for any fixed parity of size above logarithmic, perturbed GD on a one-hidden-layer ReLU network with the expected linear loss fails to reduce the loss below exp(-Ω(|S|)), and there is a single-neuron analogue for squared loss. This resolves the Abbe-Boix-Adsera open problem for the full parity and all large subsets, not just |S|≈d/2. The Fourier result behind it—average-case exponential decay of the |S|-th Fourier coefficient of weighted majority functions under a spherically symmetric weight distribution—is clean and likely to be used independently. The proof structure is sound: a TV coupling of PGD to a clipped process, then a bound on the chance that the clipped process's Gaussian walk ever visits a large-gradient point, then a small-loss bound for a plain random walk.\n\nI checked the stress-test note's alleged missing √(j+2) factor in Theorem 2's union bound. It does not land. For the linear loss, F_S is homogeneous of degree 1 in the parameters, so the gradient is scale-invariant, ∇F_S(cθ)=∇F_S(θ), not scale-linear. Therefore the partial sums ∑_{t=-1}^j ξ_t have the same gradient norm distribution as a single σ-scale Gaussian draw, and Lemma 2 applies without strengthening the |S| condition. The displayed justification in the paper is telegraphic, but the step is correct. The reader's other flagged issues are real: Lemma 2's display misstates the expectation (it is E|E_x[...]|, not |E_x[...]|), and there is a sign/index slip in the Theorem 5 appendix and a constants-line slip in the Theorem 3 appendix. None of these appears to break the argument.\n\nThe limitations are genuine but acknowledged. The spherical-symmetry machinery requires zero-mean Gaussian perturbations and the population loss; SGD and multi-neuron squared loss are left open, exactly as Section 5 states. The theorem needs |S| ≥ 72 ln(...) so very small parities are not covered, which is fine—those are learnable by other means. Theorem 1 and Theorem 4 do the necessary work, so the failure is dynamical, not representational.\n\nWho is this for: anyone working on gradient-based learning of parities, Boolean function Fourier analysis, or implicit bias/hardness of neural optimization. I would send it to a serious theory venue after a copyedit pass; the typos are fixable and the core is in good shape.","headline":"Solid resolution of the fixed-parity hardness question for a narrow but clean setting; the main theorems hold up, the stress-test's scale factor is a red herring, but the appendix needs a serious copyedit.","tokens_in":31909,"tokens_out":5236,"would_cite":true,"duration_ms":49442,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q32","68T07","06E30"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that for any fixed parity of size |S|, perturbed gradient descent on a one-hidden-layer ReLU network leaves the loss exponentially close to its trivial value unless the number of iterations is exponential in |S|, even…","keywords":["parity functions","gradient descent hardness","one-hidden-layer ReLU networks","perturbed gradient descent","Fourier coefficients","linear threshold functions","Boolean function learning","statistical queries"],"falsifier":"Sample w from a standard d-dimensional Gaussian, estimate E[f_S(w)^2] numerically for several subsets S, and compare the averages to 6 exp(-|S|/4); consistent violation of that bound would refute the Fourier-coefficient engine. A direct PGD experiment on a fixed parity with |S| = 100 should also show every gradient norm staying below exp(-|S|/18) for sub-exponential T, with the linear loss never dropping below exp(-|S|/18); observing a larger gradient or a meaningful loss reduction would refute the theorem's mechanism.","tokens_in":30749,"feed_emoji":"🧠","tokens_out":7060,"duration_ms":70437,"temperature":0.7,"pith_summary":"The paper shows that the difficulty of learning a fixed parity function with gradient methods is a real dynamic phenomenon, not merely a worst-case artifact of statistical-query lower bounds. For any subset S of coordinates of size |S| at least logarithmic in the relevant parameters, perturbed gradient descent (PGD) on a one-hidden-layer ReLU network with the linear/correlation loss leaves the objective exponentially close to zero, and for a single ReLU neuron with squared loss leaves the loss exponentially close to the trivial value 1, unless the iteration count is exponential in |S|. This holds even though a small ReLU network represents p_S exactly and a single neuron weakly approximates it. The engine is a new average-case bound: the Fourier coefficient of a Gaussian-weighted linear threshold function on S decays like exp(-$\\Omega$(|S|)), which makes the gradient exponentially small almost everywhere.","feed_headline":"Gradient descent provably fails to learn any fixed parity","feed_subtitle":"Even when an exact ReLU network exists, perturbed gradient descent leaves the loss exponentially close to trivial.","key_machinery":"The load-bearing object is the Fourier coefficient of a linear threshold (weighted majority) function, f_S(w,b) = E_{x in {±1}^d}[p_S(x) 1{w^T x + b > 0}], which appears in the gradient of the loss with respect to the hidden weights. The paper proves an average-case exponential decay of this coefficient: over Gaussian w, E[$f_S^{2}$] < 6 exp(-|S|/4). The proof expresses E[$f_S^{2}$] as an expected intersection volume of two random hemispheres, expands that volume as a Taylor series in (x^T y)/d, and observes that the first |S|-1 terms vanish by orthogonality of parity characters, leaving a rapidly decaying tail controlled by Stirling and Hoeffding bounds. On the optimization side, a clipped-gradient coupling argument bounds the total variation distance between true PGD and a plain Gaussian random walk, using Markov's inequality on the gradient norm, so the failure follows from the random walk being unable to reduce the loss.","core_discovery":"On its own terms, the paper establishes a general hardness theorem for fixed parities: with d >= 30 and |S| >= 72 * max{ln(6nd $\\sigma$), ln(5nd $sigma^{2}$ (T+1))}, after T PGD steps with Gaussian initialization and Gaussian perturbations, with probability at least 1 - (eta $\\sqrt$(T)/(2 $\\sigma$) + T + 2) exp(-|S|/18) the objective satisfies |F_S(theta_T)| < exp(-|S|/18). Because an exact width-(|S|+1) network exists (Theorem 1), the failure is dynamic, not expressive. For the squared loss and one ReLU neuron, the same phenomenon appears: although parameters achieve squared loss at most 1 - 1/(8|S|^2), PGD outputs loss larger than 1 - (2 + T + eta $\\sqrt$(T)/$\\sigma$) exp(-|S|/18). The technical root is a Fourier-analysis result (Theorem 3): for w drawn from a spherical Gaussian, the Fourier coefficient f_S(w,0) = E_{x in {±1}^d}[p_S(x) 1{w^T x > 0}] has second moment less than 6 exp(-|S|/4), and a bias-inclusive version (Theorem 6) extends this. This smallness makes PGD updates nearly a plain Gaussian random walk, which cannot reach meaningful solutions.","pith_inferences":["If the mechanism is as generic as the proof suggests, the empirical failure of ordinary SGD on parities may share the same cause: gradients are exponentially small as long as the iterates' distribution stays nearly spherically symmetric, and SGD's example-dependent noise is the main barrier to making this rigorous.","A testable extension would be to run PGD on small parities while tracking the empirical distribution of weight directions; the proof predicts the marginal remains nearly spherical and gradients stay below the exponential threshold, whereas an anisotropic initialization or noise should quickly produce larger gradients.","A deterministic version of the Fourier-decay bound for weights far from majority-like structured vectors would imply hardness for more general training dynamics, including those whose iterates concentrate on non-spherical directions.","The deliberately contrived architectures that implement Gaussian elimination stand as the known exception, so the result should not be read as proving parities are unlearnable by all differentiable models."],"forward_implications":["For |S| = omega(log d), reaching any meaningful reduction of the linear loss requires a number of iterations super-polynomial in d; the full parity function S = {1,...,d} is covered, which prior parity-hardness results did not cover.","The failure mechanism is small gradients under spherically symmetric parameter distributions, so the theorem transfers to any one-hidden-layer ReLU network and linear loss with spherically symmetric perturbations and appropriately bounded step sizes.","The single-neuron squared-loss result shows the obstruction is not an artifact of the unusual linear loss: weak learnability exists, yet PGD cannot exploit it in sub-exponential time.","The Fourier-coefficient bound stands on its own as a statement about the Boolean spectrum of weighted majority functions, beyond the well-studied plain majority case.","The results delimit what gradient-based methods can do for parity learning: any success requires either a contrived architecture or an algorithmic noise structure that breaks near-spherical symmetry."],"supporting_citations":[{"why":"Supplies the statistical-query lower bound that is worst-case over parities and motivates the paper's fixed-parity question.","marker":"[Kearns, 1998]"},{"why":"Previous symmetry-based hardness for parities with |S| near d/2; explicitly leaves the full parity and other sizes open.","marker":"[Abbe and Boix-Adsera, 2022]"},{"why":"Provides the majority-function Fourier result (polynomial decay) that the paper contrasts and uses Theorem 5.19 in the single-neuron weak-learning proof.","marker":"[O'Donnell, 2021]"},{"why":"Shows contrived architectures can learn any parity with SGD, imposing the need for architecture and algorithm restrictions that the paper formalizes.","marker":"[Abbe and Sandon, 2020b]"},{"why":"Extends the universality result to differentiable learning, sharpening why any hardness claim must be model- and algorithm-dependent.","marker":"[Abbe et al., 2021]"},{"why":"Empirical evidence that gradient methods fail on parities, the practical phenomenon being explained.","marker":"[Shalev-Shwartz et al., 2017]"}],"fun_headline_variants":["Gradient descent provably fails on every fixed parity","Fixed parities: gradient descent cannot learn them","Provable failure: gradient descent misses fixed parities","Why gradient descent can't learn any fixed parity","GD provably fails for all fixed parity functions"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole argument rests on the parameters' probability distribution staying nearly spherically symmetric while training runs; the Gaussian perturbations and the linear loss enforce that, and if the noise or the loss changes, the proof does not go through.","fun_headline_variants_meta":{"raw":{"variants":["Gradient descent provably fails on every fixed parity","Fixed parities: gradient descent cannot learn them","Provable failure: gradient descent misses fixed parities","Why gradient descent can't learn any fixed parity","GD provably fails for all fixed parity functions"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00028,"raw_usage":{"total_tokens":1696,"prompt_tokens":1016,"completion_tokens":680,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":632,"completion_tokens_details":{"reasoning_tokens":607}},"tokens_in":632,"tokens_out":680,"duration_ms":6473,"temperature":1.0,"reasoning_tokens":607,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T22:42:41.349014+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Sample w from a standard d-dimensional Gaussian, estimate E[f_S(w)^2] numerically for several subsets S, and compare the averages to 6 exp(-|S|/4); consistent violation of that bound would refute the Fourier-coefficient engine. A direct PGD experiment on a fixed parity with |S| = 100 should also show every gradient norm staying below exp(-|S|/18) for sub-exponential T, with the linear loss never dropping below exp(-|S|/18); observing a larger gradient or a meaningful loss reduction would refute the theorem's mechanism.","supporting_citations":[{"cited_title":"Efficient noise-tolerant learning from statistical queries","cited_arxiv_id":null,"evidence_quote":"Supplies the statistical-query lower bound that is worst-case over parities and motivates the paper's fixed-parity question."},{"cited_title":"On the non-universality of deep learning: quantifying the cost of symmetry","cited_arxiv_id":null,"evidence_quote":"Previous symmetry-based hardness for parities with |S| near d/2; explicitly leaves the full parity and other sizes open."},{"cited_title":"On the power of differentiable learning versus pac and sq learning","cited_arxiv_id":null,"evidence_quote":"Extends the universality result to differentiable learning, sharpening why any hardness claim must be model- and algorithm-dependent."},{"cited_title":"Failures of gradient-based deep learning","cited_arxiv_id":null,"evidence_quote":"Empirical evidence that gradient methods fail on parities, the practical phenomenon being explained."}],"review_version":1}