Hidden Progress in Deep Learning: SGD Learns Parities Near the Computational Limit

2022/07/18 by Boaz Barak, Barak, Boaz, Benjamin L. Edelman +11 · 1 voice · 30 citations
Computer Science · Materials Science · Mathematics · #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Machine Learning in Materials Science #Neural and Evolutionary Computing (cs.NE) #Optimization and Control (math.OC) #Stochastic Gradient Optimization Techniques #cs.LG #cs.NE #math.OC #stat.ML

paper · pdf · doi:10.48550/arxiv.2207.08799

openalex publication_date 2022/07/18 · arxiv published 2022/07/18 · arxiv updated 2023/01/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

There is mounting evidence of emergent phenomena in the capabilities of deep learning methods as we scale up datasets, model sizes, and training times. While there are some accounts of how these resources modulate statistical capacity, far less is known about their effect on the computational problem of model training. This work conducts such an exploration through the lens of learning a k-sparse parity of n bits, a canonical discrete search problem which is statistically easy but computationally hard. Empirically, we find that a variety of neural networks successfully learn sparse parities, with discontinuous phase transitions in the training curves. On small instances, learning abruptly occurs at approximately n^O(k) iterations; this nearly matches SQ lower bounds, despite the apparent lack of a sparse prior. Our theoretical analysis shows that these observations are not explained by a Langevin-like mechanism, whereby SGD "stumbles in the dark" until it finds the hidden set of features (a natural algorithm which also runs in n^O(k) time). Instead, we show that SGD gradually amplifies the sparse solution via a Fourier gap in the population gradient, making continual progress that is invisible to loss and error metrics.

Cited by

• From Shortcut to Induction Head: How Data Diversity Shapes Algorithm Selection in Transformers
• Understanding the Staged Dynamics of Transformers in Learning Latent Structure
• When Data Falls Short: Grokking Below the Critical Threshold
• A Derandomization Framework for Structure Discovery: Applications in Neural Networks and Beyond
• A simple mean field model of feature learning
• LLM Priors for ERM over Programs
• Adam or Gauss-Newton? A Comparative Study In Terms of Basis Alignment and SGD Noise
• Mamba Can Learn Low-Dimensional Targets In-Context via Test-Time Feature Learning
• Egalitarian Gradient Descent: A Simple Approach to Accelerated Grokking
• Improved Search-to-Decision Reduction for Random Local Functions
• The Kinetics of Training: A Driven-Nucleation Rate Law for Emergence, Plasticity Loss, and Circuit Control in Language Models
• Learning words in groups: fusion algebras, tensor ranks and grokking
• Tracing the Path to Grokking: Embeddings, Dropout, and Network Activation
• Asymptotic theory of in-context learning by linear attention
• The Features at Convergence Theorem: a first-principles alternative to the Neural Feature Ansatz for how networks learn representations
• RL for Reasoning by Adaptively Revealing Rationales
• What Happens During the Loss Plateau? Understanding Abrupt Learning in Transformers
• Alternating Gradient Flows: A Theory of Feature Learning in Two-layer Neural Networks
• Sample Complexity and Representation Ability of Test-time Scaling Paradigms
• Quiet Feature Learning in Algorithmic Tasks
• A Theoretical Framework for Grokking: Interpolation followed by Riemannian Norm Minimisation
• On the creation of narrow AI: hierarchy and nonlocality of neural network skills
• The Power of Random Features and the Limits of Distribution-Free Gradient Descent
• Optimal Regret for Single Index Bandits
• New Statistical and Computational Results for Learning Junta Distributions
• The Norm-Separation Delay Law of Grokking: A First-Principles Theory of Delayed Generalization
• When Is Compositional Reasoning Learnable from Verifiable Rewards?
• Let Me Grok for You: Accelerating Grokking via Embedding Transfer from a Weaker Model
• A Two-Phase Perspective on Deep Learning Dynamics
• Beyond Progress Measures: Theoretical Insights into the Mechanism of Grokking

Discussions

• Progress in Deep Learning: SGD Learns Parities Near the Computational Limit [hn, 2 points, 0 comments]

Related

• Provable limitations of deep learning
• Pareto Frontiers in Neural Feature Learning: Data, Compute, Width, and Luck
• Theory of Deep Learning IIb: Optimization Properties of SGD
• SGD with Large Step Sizes Learns Sparse Features
• Repetita Iuvant: Data Repetition Allows SGD to Learn High-Dimensional Multi-Index Functions