{"id":"dec4601d-aca9-4397-be2b-9876a7890b14","arxiv_id":"2505.22158","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The variance of the gradient is bounded by a pairwise-independence measure plus a collision-entropy term; for LWE and high-frequency targets this bound can be exponentially small.","lead":"This paper proves a general upper bound on how much a neural network's gradient can vary when the target function is drawn from an almost pairwise independent class, such as LWE encodings or high-frequency waves. It shows that unless the input distribution has low collision entropy, gradient-based learning of these targets is effectively blind, which helps explain recent machine-learning attacks on LWE.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Boundedness assumption (c) in Section 3 is not satisfied by the squared/cross-entropy losses used in the cited LWE attacks, so Theorem 3's applicability to those attacks is unsupported.","rationale":"After reading the full text and the proof of Theorem 2, the most load-bearing weakness is assumption (c) in Section 3, exactly as the reader identified. The proof in Appendix A uses the boundedness of L(p(w,x),h(x)) on O×X×H to justify the interchange of expectation and differentiation via Fubini and dominated convergence; without (c), that step is not justified. Theorem 3, the paper's key LWE application, does not restate any boundedness condition, and the losses used in recent gradient-based attacks on LWE (squared loss, cross-entropy) are unbounded when the network output is unbounded, which is the typical case in unconstrained optimization. The claim that (c) is 'essential but non-restrictive' is not supported: it is genuinely restrictive for standard setups. I found no internal inconsistency when (c) holds, and the LWE bound (6) is derived rather than fitted. The concern does not reject the paper; it narrows the domain of the central claim and requires a bridging argument or a relaxation of the assumption. Hence the reader's CONDITIONAL verdict is appropriate and I recommend no change.","tokens_in":29140,"tokens_out":28881,"duration_ms":289998,"concrete_test":"Analytically re-derive Theorem 3 without assumption (c), replacing it with the weaker condition that ∂L/∂p is bounded (which holds for squared error and cross-entropy). If the proof fails at the dominated-convergence step or the IPM bound, the paper must either restrict Theorem 3 to bounded losses or give an additional argument that the specific networks/losses in [19–21] satisfy (c). A complementary empirical check: train the SALSA model on a small LWE instance and record the maximum |L| encountered; if it grows during training, (c) is violated in practice.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 3 requires assumption (c): L(p(w,x),h(x)) bounded on O×X×H, and the proof of Theorem 2 (Appendix A) uses this with Fubini and dominated convergence to justify the interchange ∂wi E_X[L] = E_X[∂L/∂p · ∂p/∂wi]. Theorem 3, the key LWE application, is stated without repeating this condition. Standard losses for neural-network attacks on LWE — squared error and cross-entropy with unbounded logits — are unbounded on R×Z_q for unbounded network outputs p(w,x), so (c) fails for any unbounded parameter set O. The paper calls (c) 'essential but non-restrictive' but gives no argument that practical networks satisfy it; a constant network with squared loss on a bounded weight interval satisfies (c), but the actual attacks use unconstrained logits and weights. Consequently, the exponential bound (6) is not directly applicable to the attacks in [19–21]. This is load-bearing because the paper's headline conclusion — exponential gradient uninformativeness for realistic LWE — rests on applying Theorem 3 to those settings without verifying the theorem's hypotheses.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the \"informativeness of the gradient\" framework of Shamir: for a target h drawn from a hypothesis class H and a model p(w,·), one asks when Var_{h~χ}[∇_w E_{X~µ_X} L(p(w,X),h(X))] is small. After defining an almost-pairwise-independence measure via integral probability metrics (Section 2), the paper proves a general variance bound (Theorem 2, Eq. (3)) in terms of the IPM deviation ε, the collision entropy of µ_X, and regularity factors. It then derives an LWE corollary (Theorem 3, Eq. (6)) giving an O~((a^n−1)^−1/2) bound for uniform secrets and inputs uniform on (Z∩[0,a))^n, and two high-frequency corollaries (Theorems 4–5). The paper also computes the relevant ε exactly for small sparse binary/ternary secret sets (Section 6) and provides intuition and experiments on high-frequency targets.","tokens_in":29307,"tokens_out":9885,"duration_ms":106015,"significance":"The general bound is attractive: it is a clean distribution-specific hardness certificate, with no fitted constants, and it explicitly separates model regularity from the data distribution and the target class. The LWE application yields a concrete exponential-in-(n log a) suppression, and the paper is, to my knowledge, the first to connect this framework to the SALSA/SALSA PICANTE line of attacks. Exact computation of ε for small sparse-secret sets and the availability of reproduction code are strengths. The main caveat is that the transfer of the theorems to the actual unbounded losses and unconstrained networks used in those attacks is not justified by the stated assumptions; this is fixable but currently load-bearing.","major_comments":[{"comment":"The boundedness assumptions (a)–(c) in Section 3 are used in the proof of Theorem 2 (Appendix A) to justify Fubini and dominated convergence. Assumption (c), that L(p(w,x),h(x)) is bounded on O×X×H, is called \"essential but non-restrictive\" without support, and it is not verified for the standard losses used in the LWE attacks cited in Section 5. For squared error L(p,y)=(p−y)^2 with unbounded p(w,x), L and ∂L/∂p are unbounded; for cross-entropy on unbounded logits, L is unbounded above. Theorem 3 is stated without repeating these conditions and is used to draw the conclusion that the gradient variance is exponentially small for realistic LWE (a=q). Thus Eq. (6) is not directly applicable to the neural-network attacks in [19–21]. The revision should either (i) prove the bound under weaker integrability conditions that cover squared/cross-entropy losses, or (ii) state Theorem 3 with explicit boundedness hypotheses and explain how practical networks (e.g., bounded weights or clipped logits) satisfy them.","section":"Section 3, Assumption (c); Theorem 3, Eq. (6)"},{"comment":"Theorem 4 claims a bound for every n≥2 and every absolutely continuous µ_X, but the displayed expectation in the RHS can be infinite. Remark 7 only provides sufficient finiteness conditions for n≥5 (∫ r^{n−1}g(r)dr<∞ and ∫ r^{n−3}g(r)dr<∞); for n=2,3,4 no argument is given, and for heavy-tailed µ_X even with n≥5 the integral can diverge. As stated, the theorem is vacuous (RHS=∞) in exactly the cases not covered by Remark 7. Please move the finiteness conditions into the theorem statement and either prove the n=2,3,4 cases or explicitly exclude them. The same statement should also list the smoothness/boundedness assumptions on L needed for M_x and ∥φ∥_{F2} to be finite, since Theorem 4 is presented as a corollary of Theorem 2 but does not restate the Section 3 hypotheses.","section":"Theorem 4 and Remark 7"}],"minor_comments":[{"comment":"There are small typos: \"Intergal Probability Metric\" should be \"Integral Probability Metric,\" and \"We us a relaxed form\" should be \"We use a relaxed form.\"","section":"Section 1 and Section 2"},{"comment":"The claim that \"log a substantially improves R²\" is based on comparing raw R² values from two nested linear regressions, but R² is monotone nondecreasing when a predictor is added. Please report adjusted R², a nested-model test, or cross-validated R², and state the parameter ranges (n, l, and sample sizes) used for the exact computations.","section":"Section 6, Table 1"},{"comment":"The statement allows a=1, but for a=1 the domain (Z∩[0,1))^n\\{0} is empty and the factor (a^n−1)^−1/2 is undefined; the range of a should exclude a=1 or the empty-domain case should be handled separately.","section":"Theorem 3"},{"comment":"The appendix text describes Figure D.3, but no figure appears in the supplied manuscript; please ensure the figure is included in the published version.","section":"Appendix D"}],"recommendation":"major_revision","confidential_remarks":"The core theoretical contribution appears sound under the stated hypotheses, and the LWE-corollary calculation is clean. The main risk is that the paper's advertised applicability to practical LWE attacks requires an unbounded-loss setting that the current hypotheses exclude. This is fixable by adding explicit conditions or a relaxation argument, and I would not reject on this basis. The experimental section is supplementary; the R² comparison issue is minor but should be addressed."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The thing to know: the main theorem is real and the proof is in good shape. Theorem 2 bounds gradient variance by a regularity factor times (sqrt of mean squared pairwise-independence error plus sqrt of collision probability), and it genuinely covers parity, high-frequency, and LWE in one framework. No fitted constants, no circularity. The LWE corollary with a non-uniform input distribution is new, and it gives the first theoretical account of why small-collision-entropy inputs help the SALSA-style attacks. For that contribution alone the paper deserves a serious referee.\n\nWhere I agree with the skeptic: assumption (c) in Section 3 — L(p(w,x),h(x)) bounded on O×X×H — is load-bearing and is called \"non-restrictive\" without support. It is not satisfied by squared error or cross-entropy on unbounded weights and unbounded logits, which are exactly what the cited LWE attacks use. So Theorem 3 is a valid statement about the LWE hypothesis class under its hypotheses, but the paper's claim that it explains the practical attacks is not rigorously supported. That is an overreach, not a fatal flaw; the theorem survives, the applicability claim needs to be tempered or the assumptions verified for a specific model.\n\nTwo smaller things. Theorem 4 is stated for any absolutely continuous µX, but the integral on the RHS can diverge; the conditions in Remark 7 belong in the theorem statement itself. And the experiments in Section 6 are under-specified — the values of n and l for the R^2 fits are not given — though the code is on GitHub and this is supporting evidence, not the core result.\n\nThe relationship to the author's earlier paper [35] should be made explicit; the almost-pairwise-independence starting point appears there, and the reader should be able to see exactly which steps are new. That is a continuity, not a self-citation problem.\n\nBottom line: the central inequality and the LWE application are worth publishing after revision. I would send it to referees and ask them to focus on the boundedness assumption and on aligning Theorem 4's statement with its integrability conditions. A reader working on theoretical explanations for gradient-based attacks gets real value from this.","headline":"A clean general variance bound for almost pairwise independent classes, with an LWE corollary that is mathematically solid but whose practical reach is overstated because the required bounded-loss assumption fails for the losses used in real LWE attacks.","tokens_in":29868,"tokens_out":2381,"would_cite":true,"duration_ms":28010,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68T07","68Q32","94A60"],"pacs":[],"model":"deepseek-v4-flash","headline":"A general bound ties gradient informativeness to the input distribution's collision entropy, explaining when deep learning can learn LWE and high-frequency targets.","keywords":["variance of the gradient","barren plateau","informativeness of the gradient","learning with errors","pairwise independence","collision entropy","high-frequency functions","gradient-based learning"],"falsifier":"Solve small LWE instances exactly: for $n=3$, $q=5$ with uniform secrets and inputs uniform on $(\\mathbb{Z}\\cap[0,a))^3\\setminus\\{0\\}$, compute the left-hand side of (3) for a squared-error loss and an unrestricted linear network; if the measured variance ever exceeds the right-hand side (which should be possible only by violating the theorem's hypotheses), the boundedness assumption is not satisfied by this standard setup, and the practical applicability of the bound to common losses is refuted.","tokens_in":28880,"feed_emoji":"🔐","tokens_out":8075,"duration_ms":73286,"temperature":0.7,"pith_summary":"This paper tries to establish a general explanation of when gradient-based learning fails because the gradient carries almost no information about the target function. The measure is the variance of the gradient with respect to a random draw of the target from a hypothesis class, and the paper proves that for any almost pairwise independent class this variance is bounded by a model-regularity factor times the sum of a pairwise-independence error and the square root of the collision probability of the input distribution. Concretely, the bound scales as $\\tilde{\\mathcal{O}}(\\varepsilon + e^{-\\frac{1}{2}\\mathcal{E}_c(\\mu_X)})$, where $\\varepsilon$ measures pairwise independence and $\\mathcal{E}_c$ is the collision entropy of the inputs. The paper applies this to LWE mappings: with uniform secrets and inputs uniform on a small cube of side $a$, the variance is $O((a^n-1)^{-1/2})$, about $10^{-800}$ for realistic cryptographic parameters, and it becomes manageable when $a