Elamur Research⌕
☰
home / papers / 2022 / Grokking: Generalization Beyond Overfitting on Small Algorithmic Datasets

Grokking: Generalization Beyond Overfitting on Small Algorithmic Datasets

Paper · 2022 · Alethea Power, Yuri Burda, Harri Edwards et al.

Summary

Why heavily overparameterized networks generalize instead of simply memorizing their training data is still poorly understood. With natural datasets, the effect is also hard to isolate. Power and colleagues offer a controlled testbed: small synthetic binary-operation tables of the form a ◦ b = c. Each element is an opaque token, so the model gets no digits, permutation notation or other internal structure. A small transformer is trained on part of a table and must fill in the missing cells. The tasks include modular arithmetic mod 97, composition in the permutation group S5 and various polynomials. The main finding, which the authors call "grokking," is that validation accuracy can stay at chance level long after the training set is fit perfectly, then suddenly climb to 100%. As the training fraction shrinks, the number of optimization steps needed to generalize grows steeply. Weight decay is the most effective intervention for data efficiency. The experiments run on a single GPU, which makes them a cheap testbed for theories of generalization, such as the link between flat minima and good generalization.

Key points

  • On division mod 97 with half the table used for training, training accuracy is near-perfect within 10^3 steps. Validation accuracy barely moves until about 10^5 steps and reaches near-perfect only around 10^6.
  • For the S5 product, at about 25–30% training data, removing 1% more data raises the median steps to 99% validation accuracy by 40–50%. Training accuracy still reaches 99% within 10^3–10^4 steps.
  • Weight decay cuts the data needed by more than half compared with most other interventions. Decay toward zero works better than decay toward the initial weights. Optimization noise also helps, and the learning rate only works within about one order of magnitude.
  • Operations that are symmetric in their operands (x+y, x·y) need less data than asymmetric ones. x−y and x/y need similar amounts of data because they are the same task up to relabeling. x³+xy²+y mod 97 never generalized, even with 95% of the data.
  • t-SNE plots of the output-layer weights show circular structure for modular addition and coset clusters for S5. Sharpness of the minimum is negatively correlated with validation accuracy on S5 (Spearman ≈ −0.80).

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Fields, topics and concepts

📚 Shelves 2The field of science this work belongs to (OpenAlex fields).Computer Science · 18,614 worksArtificial Intelligence · 17,965 works

Cite

Cite as Alethea Power, Yuri Burda, Harri Edwards, Igor Babuschkin and Vedant Misra. 2022. Grokking: Generalization Beyond Overfitting on Small Algorithmic Datasets. arXiv:2201.02177.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.48550/arxiv.2201.02177 · arXiv 2201.02177

@misc{power2022grokking,
  title = {{Grokking: Generalization Beyond Overfitting on Small Algorithmic Datasets}},
  author = {Alethea Power, Yuri Burda, Harri Edwards, Igor Babuschkin and Vedant Misra},
  year = {2022},
  doi = {10.48550/arxiv.2201.02177},
  eprint = {2201.02177},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.2201.02177}
}

References

20 references, 4 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine learning practice and the bias-variance trade-off. arXiv preprint arXiv:1812.11118, 2018. — [arXiv:1812.11118](https://arxiv.org/abs/1812.11118) find
  2. Stéphane d’Ascoli, Levent Sagun, and Giulio Biroli. Triple descent and the two kinds of overfitting: Where & why do they appear? arXiv preprint arXiv:2006.03509, 2020. — [arXiv:2006.03509](https://arxiv.org/abs/2006.03509) find
  3. Mostafa Dehghani, Stephan Gouws, Oriol Vinyals, Jakob Uszkoreit, and Łukasz Kaiser. Universal transformers. arXiv preprint arXiv:1807.03819, 2018. find
  4. Alex Graves. Adaptive computation time for recurrent neural networks. arXiv:1603.08983, 2016. find
  5. Alex Graves, Greg Wayne, and Ivo Danihelka. arXiv:1410.5401, 2014. find
  6. Edward Grefenstette, Karl Moritz Hermann, Mustafa Suleyman, and Phil Blunsom. Learning to transduce with unbounded memory. Advances in neural information processing systems, 28: 1828–1836, 2015. find
  7. Sepp Hochreiter and Jürgen Schmidhuber. Flat minima. Neural computation, 9(1):1–42, 1997. find
  8. Yiding Jiang, Behnam Neyshabur, Hossein Mobahi, Dilip Krishnan, and Samy Bengio. Fantastic generalization measures and where to find them. arXiv preprint arXiv:1912.02178, 2019. — [arXiv:1912.02178](https://arxiv.org/abs/1912.02178) find
  9. Łukasz Kaiser and Ilya Sutskever. Neural gpus learn algorithms. arXiv preprint arXiv:1511.08228, 2015. find
  10. Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Peter Tang. On large-batch training for deep learning: Generalization gap and sharp minima. CoRR, abs/1609.04836, 2016. URL http://arxiv.org/abs/1609.04836. ↗
  11. Ilya Loshchilov and Frank Hutter. arXiv:1711.05101, 2017. find
  12. Decoupled weight decay regularization. Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and Ilya Sutskever. Deep double descent: Where bigger models and more data hurt. arXiv preprint arXiv:1912.02292, 2019. find
  13. Arvind Neelakantan, Luke Vilnis, Quoc V Le, Ilya Sutskever, Lukasz Kaiser, Karol Kurach, and James Martens. Adding gradient noise improves learning for very deep networks. arXiv preprint arXiv:1511.06807, 2015. find
  14. Scott Reed and Nando De Freitas. Neural programmer-interpreters. arXiv preprint arXiv:1511.06279, 2015. find
  15. David Saxton, Edward Grefenstette, Felix Hill, and Pushmeet Kohli. Analysing mathematical reasoning abilities of neural models. arXiv preprint arXiv:1904.01557, 2019.
  16. Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: a simple way to prevent neural networks from overfitting. The journal of machine learning research, 15(1):1929–1958, 2014.
  17. Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. arXiv preprint arXiv:1706.03762, 2017.
  18. Jason Weston, Sumit Chopra, and Antoine Bordes. arXiv:1410.3916, 2014. arXiv preprint Neural turing machines. arXiv preprint arXiv preprint Memory networks. arXiv preprint Jason Weston, Antoine Bordes, Sumit Chopra, Alexander M Rush, Bart van Merriënboer, Armand Joulin, and Tomas Mikolov. Towards a… find
  19. Wojciech Zaremba and Ilya Sutskever. Reinforcement learning neural turing machines-revised. arXiv preprint arXiv:1505.00521, 2015.
  20. Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint arXiv:1611.03530, 2016. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/power-2022-grokking-generalization-overfitting-small-algorithmic/