Pith. sign in

REVIEW 2 major objections 4 minor 40 references

The informativeness of the gradient revisited

T0 review · 2 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read A general bound ties gradient informativeness to the input distribution's collision entropy, explaining when deep learning can learn LWE and high-frequency targets.

desk verdict 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. read the letter →

arxiv 2505.22158 v1 pith:WBDGKQUA submitted 2025-05-28 cs.LG

Rustem Takhanov This is my paper · ORCID
classification cs.LG MSC 68T0768Q3294A60
keywords varianceofthegradientbarrenplateauinformativenesslearningwitherrorspairwiseindependencecollisionentropyhigh-frequencyfunctionsgradient-based
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 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

What carries the argument

The load-bearing object is the pair $(\mathcal{H},\chi)$ made almost pairwise independent with respect to the Integral Probability Metric, quantified by $\varepsilon_F(x,x')$ from Eq. (1), together with the collision entropy $\mathcal{E}_c(\mu_X)$ of the input distribution. The proof of Theorem 2 combines a Hilbert-Schmidt operator argument (Lemma 1) that converts the gradient variance into an inner-product expectation over pairs of hypotheses, a decomposition (Lemma 2) of that expectation into an off-diagonal term controlled by $\varepsilon_F$ and a diagonal term controlled by the collision probability $\mathbb{P}[X=Y]$, and the boundedness assumptions on the loss and its derivatives. The resulting inequality (3), simplified in (4) as $$\mathrm{Var}_{h\sim\chi}[\partial_{w_i}C_h(w)] \lesssim \mathbb{E}_{\mu_X}\left[\left(\frac{\partial p(w,X)}{\partial w_i}\right)^2\right]\left(\mathbb{E}[\$varepsilon_F^{2}$]^{1/2} + $e^{{-\frac12\mathcal{E}}$_c(\mu_X)}\right),$$ is what carries the argument to LWE and to high-frequency functions, since in both cases the two data-dependent factors are computable.

What would settle it

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.

Watch

Extended reading notes

Core claim

The central claim is Theorem 2: for a random target $h\sim\chi$, the variance of the partial derivative of the expected loss satisfies $$\mathrm{Var}_{h\sim\chi}[\partial_{w_i}\mathbb{E}_{X\sim\mu_X} L(p(w,X),h(X))] \le \|\partial_{w_i} p(w,\cdot)\|^2_{\mu_X}\left(\sqrt{\mathbb{E}[\varepsilon_F(X,Y)^2\|\phi_{X,Y}\|^2_{F_2}]} + \sqrt{\gamma}\right),$$ where $\varepsilon_F$ is the almost pairwise independence error in the Integral Probability Metric and $\gamma$ contains the collision probability $e^{-\mathcal{E}_c(\mu_X)}$ of the input distribution. In the simplified $L^\infty$ form, the variance is at most the regularity factor times $(\mathbb{E}[\varepsilon^2]^{1/2} + e^{-\frac12\mathcal{E}_c(\mu_X)})$. Applied to the LWE hypothesis class $\{x\mapsto \langle k,x\rangle\}$ with inputs uniform on $(\mathbb{Z}\cap[0,a))^n\setminus\{0\}$, Theorem 3 yields a bound proportional to $(a^n-1)^{-1/2}$, so that for $a=q$ and realistic sizes ($\log_2 q\approx 10$, $n\approx 544$) the gradient variance is on the order of $10^{-800}$, while for $a<q$ the hardness parameter drops from $n\log q$ to $n\log a$. The paper presents this as the first theoretical analysis of gradient-based LWE attacks and shows the same structure controls high-frequency function classes.

Load-bearing premise

The proof assumes the loss $L(p(w,x),h(x))$ is bounded over all parameters, inputs, and hypotheses, with bounded derivatives; for a standard squared loss with unbounded network parameters this boundedness is not automatic, and the paper gives no argument that it holds for the networks used in LWE attacks.

Editorial extensions

If this is right

  • For LWE with uniform secrets and inputs uniform on $(\mathbb{Z}\cap[0,a))^n\setminus\{0\}$, the gradient variance is at most a constant times $(a^n-1)^{-1/2}$; with $a=q$ and realistic parameters this is about $10^{-800}$, so the gradient is uninformative.
  • With $a<q$ the relevant hardness parameter becomes $n\log a$ rather than $n\log q$, so the same mapping can become learnable by gradient methods, matching the preprocessing in recent attacks.
  • For any almost pairwise independent target class, any regular network, any regular loss, and any gradient-based optimizer, the gradient is uninformative unless the input distribution is tuned.
  • For high-frequency functions with frequency variance $R^2$, the variance decays as $1/R^2$ for $n\ge 2$ and as $\log^2(R)/\sqrt{R}$ for $n=1$, so large-frequency targets are difficult for gradient methods.
  • The bound certifies hardness only for a specific input distribution; changing the distribution can restore gradient informativeness.

Reading between the lines

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

  • Editorial inference: because the bound is an upper bound, small gradient variance is only a necessary condition for hardness; the framework cannot prove that any particular attack fails, only that straightforward gradient training should fail under the assumed distributions.
  • Editorial inference: the $1/R^2$ decay for high-frequency functions is likely an artifact of the pairwise-independence route, since Fourier-based analysis in the squared-error case gives exponential decay; closing this gap may reveal whether squared error is special.
  • Editorial inference: the results suggest a concrete design principle for machine-learning cryptanalysis: a successful LWE attack must effectively map the uniform input distribution to one with far lower collision entropy, which is precisely what the preprocessing steps of recent attacks appear to do.
  • Editorial inference: a direct experimental check would measure gradient variance over random secrets for small LWE parameters and compare with the right-hand side of (6); a systematic mismatch would localize which regularity assumption fails for practical losses and architectures.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 4 minor

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.

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 (2)
  1. [Section 3, Assumption (c); Theorem 3, Eq. (6)] 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.
  2. [Theorem 4 and Remark 7] 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.
minor comments (4)
  1. [Section 1 and Section 2] 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."
  2. [Section 6, Table 1] 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.
  3. [Theorem 3] 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.
  4. [Appendix D] 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.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the variance bound is proved from the defining IPM and collision entropy, with no fitted inputs; self-citations are non-load-bearing.

full rationale

Theorem 2 is derived completely in Appendix A, starting from the definitions of the integral probability metric ε_F and the collision entropy, and it does not fit any parameter to data or use the conclusion as an assumption. The bound's ε term is the same pairwise-independence deviation the paper defines in Section 2, but that is not circular: the theorem proves a nontrivial inequality between the gradient variance and that independently defined quantity. Theorem 3 for LWE follows by explicitly computing ε_F for uniform secrets and plugging into Theorem 2, giving the (a^n−1)^{-1/2} factor algebraically; no 'prediction' is obtained by fitting. Section 6 uses exact computations and linear regression only as an empirical illustration of a previously derived inequality, not as evidence for the theorem itself. The framework of gradient informativeness is cited from Shamir [8], which is an external prior result, and the author's own citations [31] and [35] appear only in contextual remarks and applications, not as load-bearing steps in the derivation. The boundedness assumption (c) on the loss may limit the theorem's applicability to unbounded losses used in practical LWE attacks, but this is a scope or correctness concern, not circularity. Overall, the central derivation is self-contained and its conclusions do not reduce to their inputs by construction.

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

The central derivation has no fitted parameters; its inputs are the hypothesis class (H,chi), the input distribution muX, and the regularity of the model and loss. The main assumptions are stated in Section 3 and the standard analytic tools are used in the appendices.

assumptions (6)
  • domain assumption Theorem 1 of Shamir (2018): if Var[grad C_h(w)] <= delta^3, then a delta-accurate gradient oracle makes any algorithm's output independent of h after O(1/delta) iterations.
    Used in Section 3 to translate the variance bound into a claim about the number of iterations needed to learn; not proved in this paper.
  • domain assumption Boundedness and measurability: L(p(w,x),h(x)) bounded on O x X x H, dL/dp exists and is bounded, grad_w p exists a.e. and is bounded.
    Assumption (c) in Section 3; required for Fubini-Tonelli and the Leibniz rule in Appendix A. The paper calls it 'non-restrictive' but it excludes unbounded squared losses unless p is uniformly bounded.
  • domain assumption The chosen IPM function spaces F1 and F2 contain the products r_w(x,.)r_w(x',.) and squares r_w(x,.)^2.
    Lemma 2 and Theorem 2 require these products to lie in F2/F1; for L-infinity this holds under boundedness, for C^{1,1} it requires additional smoothness of L.
  • domain assumption For LWE: q is prime, X = Z_q^n \ {0}, muX uniform on (Z cap [0,a))^n \ {0}, muY uniform on Z_q, chi uniform on secrets.
    Theorem 3 definition; standard LWE setup with noiseless linear functions.
  • domain assumption For high-frequency functions: psi is 1-periodic, A ~ N(0,R^2 I_n), muX absolutely continuous, and the integral on the RHS of Theorem 4 is finite (n>=5 conditions given in Remark 7).
    Theorems 4-5; Theorem 4 as stated is vacuous unless the displayed expectation is finite.
  • standard math Standard analytic tools: Hilbert-Schmidt norm bounds operator norm, Poincare-Wirtinger, Koksma-Hlawka, Erdos-Turan-Koksma.
    Used in Appendices A and C; accepted results, not reproved.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The informativeness of the gradient revisited." pith.science (2026). https://pith.science/paper/WBDGKQUA

@misc{pith2026250522158,
  author       = {Pith},
  title        = {Pith review of: The informativeness of the gradient revisited},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/WBDGKQUA}},
  note         = {Machine review of arXiv:2505.22158}
}
abstract

In the past decade gradient-based deep learning has revolutionized several applications. However, this rapid advancement has highlighted the need for a deeper theoretical understanding of its limitations. Research has shown that, in many practical learning tasks, the information contained in the gradient is so minimal that gradient-based methods require an exceedingly large number of iterations to achieve success. The informativeness of the gradient is typically measured by its variance with respect to the random selection of a target function from a hypothesis class. We use this framework and give a general bound on the variance in terms of a parameter related to the pairwise independence of the target function class and the collision entropy of the input distribution. Our bound scales as $ \tilde{\mathcal{O}}(\varepsilon+e^{-\frac{1}{2}\mathcal{E}_c}) $, where $ \tilde{\mathcal{O}} $ hides factors related to the regularity of the learning model and the loss function, $ \varepsilon $ measures the pairwise independence of the target function class and $\mathcal{E}_c$ is the collision entropy of the input distribution. To demonstrate the practical utility of our bound, we apply it to the class of Learning with Errors (LWE) mappings and high-frequency functions. In addition to the theoretical analysis, we present experiments to understand better the nature of recent deep learning-based attacks on LWE.

Figures

Figures reproduced from arXiv: 2505.22158 by the authors.

Figure 1
Figure 1. Scatter and linear regression plots for “ [PITH_FULL_IMAGE:figures/full_fig_p015_1.png] view at source ↗
Figure 2
Figure 2. The objective function Ch(ω) for ψ(x) = {x}, where {x} is a fractional part of x, and for frequencies w = 10 and w = 40. The latter objective represents the smoothed Fourier transform of h, i.e. Ch(ω) = Re Z 1 0 h(x)e −iωxdx = Re Z 1 0 X +∞ i=−∞ aie i2πiwxe −iωxdx = Re X +∞ i=−∞ aik(ω − 2πiw), where k(ω) = R 1 0 e −iωxdx = i ω (e −iω −1). Note that |k(ω)| = 2| sin( ω 2 )| |ω| . In other words, Ch(ω) = Re(bh ∗ k 2π )… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

40 extracted references · 30 canonical work pages

  1. [35]

    Takhanov, Almost pairwise independence and resilience to deep learning attacks, IACR Communications in Cryptology 1 (3) (2024)

    R. Takhanov, Almost pairwise independence and resilience to deep learning attacks, IACR Communications in Cryptology 1 (3) (2024). doi:10.62056/a3ksa69p1

    work page doi:10.62056/a3ksa69p1 2024

  2. [1]

    Chang, X

    Y. Chang, X. Wang, J. Wang, Y. Wu, L. Yang, K. Zhu, H. Chen, X. Yi, C. Wang, Y. Wang, W. Ye, Y. Zhang, Y. Chang, P. S. Yu, Q. Yang, X. Xie, A survey on evaluation of large language models, ACM Trans. Intell. Syst. Technol. 15 (3) (Mar. 2024).doi:10.1145/3641289. URL https://doi.org/10.1145/3641289

    doi:10.1145/3641289 2024

  3. [2]

    Abramson, J

    J. Abramson, J. Adler, J. Dunger, R. Evans, T. Green, A. Pritzel, O. Ronneberger, L. Willmore, A. J. Ballard, J. Bambrick, et al., Ac- curate structure prediction of biomolecular interactions with alphafold 3, Nature (2024) 1–3

    work page 2024

  4. [3]

    P. R. Wurman, S. Barrett, K. Kawamoto, J. MacGlashan, K. Subra- manian, T. J. Walsh, R. Capobianco, A. Devlic, F. Eckert, F. Fuchs, et al., Outracing champion gran turismo drivers with deep reinforce- ment learning, Nature 602 (7896) (2022) 223–228

    work page 2022

  5. [4]

    J. A. Keith, V. Vassilev-Galindo, B. Cheng, S. Chmiela, M. Gastegger, K.-R. Müller, A. Tkatchenko, Combining machine learning and compu- tational chemistry for predictive insights into chemical systems, Chem- ical Reviews 121 (16) (2021) 9816–9872. doi:10.1021/acs.chemrev. 22 1c00107. URL https://doi.org/10.1021/acs.chemrev.1c00107

    doi:10.1021/acs.chemrev 2021

  6. [5]

    V. P. Dwivedi, C. K. Joshi, A. T. Luu, T. Laurent, Y. Bengio, X. Bres- son, Benchmarking graph neural networks, Journal of Machine Learning Research 24 (43) (2023) 1–48. URL http://jmlr.org/papers/v24/22-0567.html

    work page 2023

  7. [6]

    Y. Ma, Z. Cao, Y. M. Chee, Learning to search feasible and infeasi- ble regions of routing problems with flexible neural k-opt, in: A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, S. Levine (Eds.), Advances in Neural Information Processing Systems, Vol. 36, Curran Associates, Inc., 2023, pp. 49555–49578. URL https://proceedings.neurips.cc/paper_file...

    work page 2023

  8. [7]

    Geisler, Y

    S. Geisler, Y. Li, D. J. Mankowitz, A. T. Cemgil, S. Günnemann, C. Paduraru, Transformers meet directed graphs, in: A. Krause, E. Brunskill, K. Cho, B. Engelhardt, S. Sabato, J. Scarlett (Eds.), Pro- ceedings of the 40th International Conference on Machine Learning, Vol. 202 of Proceedings of Machine Learning Research, PMLR, 2023, pp. 11144–11172. URL htt...

    work page 2023

Show all 40 references
  1. [8]

    Shamir, Distribution-specific hardness of learning neural networks, J

    O. Shamir, Distribution-specific hardness of learning neural networks, J. Mach. Learn. Res. 19 (2018) 32:1–32:29

    2018

  2. [9]

    Shalev-Shwartz, O

    S. Shalev-Shwartz, O. Shamir, S. Shammah, Failures of gradient-based deep learning, in: D. Precup, Y. W. Teh (Eds.), Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, Vol. 70 of Proceedings of Machine Lea...

    2017

  3. [10]

    J. R. McClean, S. Boixo, V. N. Smelyanskiy, R. Babbush, H. Neven, Barren plateaus in quantum neural network training land- scapes, Nature Communications 9 (1) (2018) 4812. doi:10.1038/ s41467-018-07090-4. URL https://doi.org/10.1038/s41467-018-07090-4 23

    2018 doi

  4. [11]

    Liu, L.-W

    Z. Liu, L.-W. Yu, L.-M. Duan, D.-L. Deng, Presence and absence of barren plateaus in tensor-network based machine learning, Phys. Rev. Lett. 129 (2022) 270501.doi:10.1103/PhysRevLett.129.270501. URL https://link.aps.org/doi/10.1103/PhysRevLett.129. 270501

    2022 doi

  5. [12]

    Carter, M

    J. Carter, M. N. Wegman, Universal classes of hash functions, Journal of Computer and System Sciences 18 (2) (1979) 143–154. doi:https://doi.org/10.1016/0022-0000(79)90044-8. URL https://www.sciencedirect.com/science/article/pii/ 0022000079900448

    1979 doi

  6. [13]

    Ghosh, P

    K. Ghosh, P. A. Eliasi, J. Daemen, Multimixer-128: Universal keyed hashing based on integer multiplication, IACR Transactions on Sym- metric Cryptology 2023 (3) (2023) 1–24. URL https://doi.org/10.46586/tosc.v2023.i3.1-24

    2023 doi

  7. [14]

    S. P. Vadhan, Pseudorandomness, Foundations and Trends® in The- oretical Computer Science 7 (1–3) (2012) 1–336. doi:10.1561/ 0400000010. URL http://dx.doi.org/10.1561/0400000010

    2012 doi

  8. [15]

    O. Regev, On lattices, learning with errors, random linear codes, and cryptography, in: Proceedings of the Thirty-Seventh Annual ACM Sym- posium on Theory of Computing, STOC ’05, Association for Comput- ing Machinery, New York, NY, USA, 2005, p. 84–93. doi:10.1145/ 1060590.106...

    2005

  9. [16]

    Brakerski, A

    Z. Brakerski, A. Langlois, C. Peikert, O. Regev, D. Stehlé, Classical hardness of learning with errors, in: Proceedings of the Forty-Fifth An- nual ACM Symposium on Theory of Computing, STOC ’13, Associa- tion for Computing Machinery, New York, NY, USA, 2013, p. 575–584. doi:1...

    2013

  10. [17]

    Q. Guo, E. Mårtensson, P. Stankovski Wagner, Modeling and sim- ulating the sample complexity of solving lwe using bkw-style algo- rithms, Cryptography and Communications 15 (2) (2023) 331–350. 24 doi:10.1007/s12095-022-00597-0. URL https://doi.org/10.1007/s12095-022-00597-0

    2023 doi

  11. [18]

    L. Chen, D. Moody, Y.-K. Liu, et al, Announcing four candidates to be standardized, plus fourth round candidates,https://csrc.nist.gov/ News/2022/pqc-candidates-to-be-standardized-and-round-4 , ac- cessed: 2023-12-12 (2022)

    2022

  12. [19]

    Wenger, M

    E. Wenger, M. Chen, F. Charton, K. E. Lauter, SALSA: attacking lattice cryptography with transformers, in: NeurIPS, 2022. URL http://papers.nips.cc/paper_files/paper/2022/hash/ e28b3369186459f57c94a9ec9137fac9-Abstract-Conference.html

    2022

  13. [20]

    C. Y. Li, J. Sotáková, E. Wenger, Z. Allen-Zhu, F. Charton, K. E. Lauter, SALSA VERDE: a machine learning attack on learning with errors with sparse small secrets, IACR Cryptol. ePrint Arch. (2023) 968. URL https://eprint.iacr.org/2023/968

    2023

  14. [21]

    C. Y. Li, J. Sotáková, E. Wenger, M. Malhou, E. Garcelon, F. Char- ton, K. Lauter, Salsapicante: A machine learning attack on lwe with binary secrets, in: Proceedings of the 2023 ACM SIGSAC Confer- ence on Computer and Communications Security, CCS ’23, Association for Computin...

    2023

  15. [22]

    Shoup, A computational introduction to number theory and algebra, Cambridge University Press, USA, 2005

    V. Shoup, A computational introduction to number theory and algebra, Cambridge University Press, USA, 2005

    2005

  16. [23]

    Müller, Integral probability metrics and their generating classes of functions, Advances in Applied Probability 29 (2) (1997) 429–443

    A. Müller, Integral probability metrics and their generating classes of functions, Advances in Applied Probability 29 (2) (1997) 429–443. URL http://www.jstor.org/stable/1428011

    1997

  17. [24]

    B. K. Sriperumbudur, K. Fukumizu, A. Gretton, B. Schölkopf, G. R. G. Lanckriet, On the empirical estimation of integral probability metrics, Electronic Journal of Statistics 6 (none) (2012) 1550 – 1599.doi:10. 1214/12-EJS722. URL https://doi.org/10.1214/12-EJS722 25

    2012 doi

  18. [25]

    Mroueh, T

    Y. Mroueh, T. Sercu, Fisher gan, in: Proceedings of the 31st Interna- tional Conference on Neural Information Processing Systems, NIPS’17, Curran Associates Inc., Red Hook, NY, USA, 2017, p. 2510–2520

    2017

  19. [26]

    Mroueh, C.-L

    Y. Mroueh, C.-L. Li, T. Sercu, A. Raj, Y. Cheng, Sobolev GAN, in: International Conference on Learning Representations, 2018. URL https://openreview.net/forum?id=SJA7xfb0b

    2018

  20. [27]

    J. Bos, C. Costello, L. Ducas, I. Mironov, M. Naehrig, V. Nikolaenko, A. Raghunathan, D. Stebila, Frodo: Take off the ring! practical, quantum-secure key exchange from lwe, in: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, CCS ’16, Asso...

    2016

  21. [28]

    Albrecht, M

    M. Albrecht, M. Chase, H. Chen, J. Ding, S. Goldwasser, S. Gorbunov, S. Halevi, J. Hoffstein, K. Laine, K. Lauter, et al., Homomorphic en- cryption standard, Protecting privacy through homomorphic encryption (2021) 31–62

    2021

  22. [29]

    Or-tools, https://developers.google.com/optimization, accessed: 2024-09-19

    2024

  23. [30]

    Ambrosio, N

    L. Ambrosio, N. Fusco, D. Pallara, Functions of bounded variation and free discontinuity problems, Oxford Math. Monogr., Oxford: Clarendon Press, 2000

    2000

  24. [31]

    Takhanov, M

    R. Takhanov, M. Tezekbayev, A. Pak, A. Bolatov, Z. Assylbekov, Gradient descent fails to learn high-frequency functions and modu- lar arithmetic, Machine Learning 114 (4) (2025) 117. doi:10.1007/ s10994-025-06747-8. URL https://doi.org/10.1007/s10994-025-06747-8

    2025 doi

  25. [32]

    Feldman, C

    V. Feldman, C. Guzmán, S. S. Vempala, Statistical query algorithms for mean vector estimation and stochastic convex optimization, in: P. N. Klein (Ed.), Proceedings of the Twenty-Eighth Annual ACM- SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta...

    2017 doi

  26. [33]

    Jacot, F

    A. Jacot, F. Gabriel, C. Hongler, Neural tangent kernel: Conver- gence and generalization in neural networks, in: Proceedings of the 32nd International Conference on Neural Information Processing Sys- tems, NIPS’18, Curran Associates Inc., Red Hook, NY, USA, 2018, p. 8580–8589

    2018

  27. [34]

    Vaudenay, Decorrelation: A theory for block cipher security, Journal of Cryptology 16 (4) (2003) 249–286

    S. Vaudenay, Decorrelation: A theory for block cipher security, Journal of Cryptology 16 (4) (2003) 249–286. doi:10.1007/ s00145-003-0220-6. URL https://doi.org/10.1007/s00145-003-0220-6

    2003 doi

  28. [36]

    J. B. Conway, Operators on Hilbert Space, Springer New York, New York, NY, 2007, pp. 26–62.doi:10.1007/978-1-4757-4383-8_2. URL https://doi.org/10.1007/978-1-4757-4383-8_2

    2007 doi

  29. [37]

    W. P. Ziemer, Poincaré Inequalities—A Unified Approach, Springer New York, New York, NY, 1989, pp. 177–219. doi:10.1007/ 978-1-4612-1015-3_4. URL https://doi.org/10.1007/978-1-4612-1015-3_4

    1989 doi

  30. [38]

    Z X fh1(x)fh2(x)dµX (x) 2 # = E(h1,h2)∼χ2

    L. Kuipers, H. Niederreiter, Uniform Distribution of Sequences, Dover Books on Mathematics, Dover Publications, 2012. URL https://books.google.kz/books?id=mnY8LpyXHM0C Appendix A. Proof of Theorem 2 Since p : O × X →R and idY : Y → Y, idY(y) = y are measurable functions, (w, x...

    2012

  31. [39]

    Since VC dimension of the set of concepts{[0, u1) × · · · × [0, us) | 0 ≤ u1, · · ·, us ≤ 1} is O(s), we obtain that the latter expression is O( q log N N )

    Using the notion of the Rademacher complexity and Massart lemma, we obtain Exi sup 0≤u1,u2≤1 | 1 N NX i=1 1xi∈[0,u1)×[0,u2) − PX∼ν X ∈ [0, u1) × [0, u2) | ≤ 4 N ExiEσi sup 0≤u1,u2≤1 NX i=1 σi1xi∈[0,u1)×[0,u2) ≤ 4Exi r 2 logG N , where Gisthenumberofdistinctvectorsin {z ∈ {0, 1...

  32. [40]

    As can be seen there is not much gain in adding more parameters to a model

    For the first picture and the second pictures the number of neurons on layers are[1, 64, 128, 1] and [1, 640, 1280, 1] (over-parameterized model) respectively. As can be seen there is not much gain in adding more parameters to a model. 44

Pith tools

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