# The informativeness of the gradient revisited

arXiv: https://arxiv.org/abs/2505.22158 · HTML: https://mlsanity.com/paper/2505.22158/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 38 references that are in the map.
- First posted on arXiv 28 May 2025.

## Builds on (most cited first, 16 of 16)

- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [A Survey on Evaluation of Large Language Models](https://mlsanity.com/paper/2307.03109/) (2023)
- [Benchmarking Graph Neural Networks](https://mlsanity.com/paper/2003.00982/) (2020)
- [Barren plateaus in quantum neural network training landscapes](https://mlsanity.com/paper/1803.11173/) (2018)
- [Learning to Search Feasible and Infeasible Regions of Routing Problems with Flexible Neural k-Opt](https://mlsanity.com/paper/2310.18264/) (2023)
- [Failures of Gradient-Based Deep Learning](https://mlsanity.com/paper/1703.07950/) (2017)
- [Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization](https://mlsanity.com/paper/1512.09170/) (2015)
- [Transformers Meet Directed Graphs](https://mlsanity.com/paper/2302.00049/) (2023)
- [Sobolev GAN](https://mlsanity.com/paper/1711.04894/) (2017)
- [SALSA: Attacking Lattice Cryptography with Transformers](https://mlsanity.com/paper/2207.04785/) (2022)
- [Distribution-Specific Hardness of Learning Neural Networks](https://mlsanity.com/paper/1609.01037/) (2016)
- [Fisher GAN](https://mlsanity.com/paper/1705.09675/) (2017)
- [Classical Hardness of Learning with Errors](https://mlsanity.com/paper/1306.0281/) (2013)
- [SALSA PICANTE: a machine learning attack on LWE with binary secrets](https://mlsanity.com/paper/2303.04178/) (2023)
- [SALSA VERDE: a machine learning attack on Learning With Errors with sparse small secrets](https://mlsanity.com/paper/2306.11641/) (2023)
- [Gradient Descent Fails to Learn High-frequency Functions and Modular Arithmetic](https://mlsanity.com/paper/2310.12660/) (2023)

## Abstract (arXiv)

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  tildeO(varepsilon+e^-frac12Ec) , where  tildeO  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 Ec 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.