# Gradient Descent Fails to Learn High-frequency Functions and Modular Arithmetic

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 30 references that are in the map.
- First posted on arXiv 19 Oct 2023.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Barren plateaus in quantum neural network training landscapes](https://mlsanity.com/paper/1803.11173/) (2018)
- [Grokking: Generalization Beyond Overfitting on Small Algorithmic Datasets](https://mlsanity.com/paper/2201.02177/) (2022)
- [Omnigrok: Grokking Beyond Algorithmic Data](https://mlsanity.com/paper/2210.01117/) (2022)
- [Identity Matters in Deep Learning](https://mlsanity.com/paper/1611.04231/) (2016)
- [Grokking modular arithmetic](https://mlsanity.com/paper/2301.02679/) (2023)
- [Failures of Gradient-Based Deep Learning](https://mlsanity.com/paper/1703.07950/) (2017)
- [On the Computational Efficiency of Training Neural Networks](https://mlsanity.com/paper/1410.1141/) (2014)
- [Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization](https://mlsanity.com/paper/1512.09170/) (2015)
- [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)
- [Reusing Weights in Subword-aware Neural Language Models](https://mlsanity.com/paper/1802.08375/) (2018)
- [Reducing the dimensionality of data using tempered distributions](https://mlsanity.com/paper/1903.05083/) (2019)
- [Autoencoders for a manifold learning problem with a Jacobian rank constraint](https://mlsanity.com/paper/2306.14194/) (2023)
- [Intractability of Learning the Discrete Logarithm with Gradient-Based Methods](https://mlsanity.com/paper/2310.01611/) (2023)

## Built on by (most cited first, 2 of 2)

- [Machine learning for modular multiplication](https://mlsanity.com/paper/2402.19254/) (2024)
- [The informativeness of the gradient revisited](https://mlsanity.com/paper/2505.22158/) (2025)

## Abstract (arXiv)

Classes of target functions containing a large number of approximately orthogonal elements are known to be hard to learn by the Statistical Query algorithms. Recently this classical fact re-emerged in a theory of gradient-based optimization of neural networks. In the novel framework, the hardness of a class is usually quantified by the variance of the gradient with respect to a random choice of a target function. A set of functions of the form x→ ax bmod p, where a is taken from mathbb Zp, has attracted some attention from deep learning theorists and cryptographers recently. This class can be understood as a subset of p-periodic functions on mathbb Z and is tightly connected with a class of high-frequency periodic functions on the real line. We present a mathematical analysis of limitations and challenges associated with using gradient-based learning techniques to train a high-frequency periodic function or modular multiplication from examples. We highlight that the variance of the gradient is negligibly small in both cases when either a frequency or the prime base p is large. This in turn prevents such a learning algorithm from being successful.