PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Boaz Barak, Benjamin L. Edelman, Surbhi Goel, Sham Kakade, Eran Malach, Cyril Zhang

arXiv:2207.08799v3cs.LGcs.NEmath.OCstat.ML

TL;DR

The paper studies how scaling computational resources affects gradient-based optimization, using sparse parity as a statistically easy but computationally hard benchmark. It combines empirical experiments across neural architectures with theoretical analysis of SGD dynamics. The results show abrupt phase transitions and near-SQ-limit runtimes, explained by gradual hidden amplification of sparse features rather than random search.

  • Problem

    The paper addresses the limited understanding of how scaling data, model size, and training time affects the computational success of gradient-based optimization.

  • Method

    The paper analyzes sparse parity learning through extensive experiments across architectures and resources together with theoretical analyses of SGD and an idealized disjoint-PolyNet.

  • Results

    A variety of neural networks learn sparse parities with abrupt phase transitions, while SGD gradually amplifies sparse features and achieves runtimes nearly matching the sparsity-dependent SQ lower bound.

  • Takeaways & Limitations

    Sparse parity is an elementary test case showing that deep-learning optimization can make hidden computational progress despite uninformative loss and accuracy curves.

  • Takeaways & Limitations

    The theoretical and empirical analyses use a heavily idealized synthetic setting, and broader Fourier-gap results for other initializations and small batches remain open.

Abstract

from arXiv · show

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.

1 Introduction

The paper studies computational scaling in deep learning using sparse parity learning, finding abrupt training phase transitions across diverse networks and evidence of hidden progress rather than random search.

  • Motivation: Sparse parity learning provides a statistically easy but computationally difficult test case for studying how scaling resources affect gradient-based optimization.The task asks models to recover k relevant bits among n inputs, probing computational rather than merely statistical capacity.
  • Hidden progress: SGD’s convergence time scales as n^O(k) on small instances, contradicting a random-search explanation and approaching the sparsity-dependent SQ limit.The observed rate adapts to sparsity k rather than requiring 2^Ω(n) search.
  • Hidden progress: Empirical and theoretical analyses indicate that SGD steadily amplifies sparse features through hidden progress, even while loss and accuracy remain uninformative.The results hold in non-overparameterized regimes, where successful convergence requires learning a low-width sparse representation rather than relying on a fixed kernel.
  • Empirical findings: Training curves typically show long plateaus followed by rapid error decreases, revealing phase transitions in running time and, for online learning, dataset size.Some architectures instead show an initially linear decrease in error.
  • Empirical findings: A variety of architectures and hyperparameters solve small sparse parity instances, including 2-layer MLPs, Transformers, sinusoidal neurons, and PolyNets.The reported settings include multiple initialization schemes and batch sizes, with success probability at least 0.2 within c · n^αk steps.
  • Additional experiments: Additional experiments examine resource scaling, grokking, and deeper networks, including cases where deep polynomial-activation MLPs succeed although greedy layer-wise training remains trivial.Convergence times empirically plateau at large model sizes, indicating that width does not provide simple parallel speedups.

2 Preliminaries

The preliminaries define sparse parity learning, explain its statistical-query hardness, and specify the neural-network training setting used for analysis and experiments.

  • Sparse parities: A sparse parity computes the product of the input bits indexed by a hidden nonempty subset S of [n].The associated learning problem recovers S from examples whose inputs are uniformly random sign vectors and whose labels equal the parity.
  • Sparse parities: Parity functions are orthogonal under correlation, so guessing an incorrect subset provides no correlation feedback unless it exactly matches S.This indistinguishability underlies the computational hardness of the problem.
  • Computational hardness: Learning sparse noisy parities is believed to require n^Ω(k) computational steps, despite a statistical sample limit of approximately k log n.Noiseless parities remain learnable in polynomial time by Gaussian elimination, distinguishing computational from statistical difficulty.
  • Training setup: The main results use online learning, where SGD receives fresh i.i.d. minibatches at each iteration and updates a continuously parameterized network.The classifier is represented as sign(f(x; θ_t)), with parameters initialized randomly and trained using a loss and learning-rate schedule.
  • Assumptions: The main presentation uses noiseless parities, while the theoretical analyses and experiments can tolerate randomly flipped labels.The paper states the noiseless setting for ease of presentation and discusses noisy parities separately.
  • Training dynamics: Figure 2 summarizes convergence-time distributions, initialization sensitivity, and the eventual worsening of power-law exponents on larger instances.Its center panel uses B = 128 and η = 0.01.

3 Empirical findings

Across architectures, initializations, losses, and batch sizes, SGD learns sparse parities on small instances, typically with phase-transition-like training curves. Several observations distinguish this behavior from random exhaustive search.

  • Robust space of positive results: SGD solved sparse parities across MLPs, specialized neurons, Transformers, and PolyNets, with varied activations and initializations.The tested architectures included 2-layer MLPs, 1-neuron networks, Transformers, and PolyNets.
  • Robust space of positive results: Across n ∈ {10, 20, 30}, k ∈ {2, 3, 4}, and many training settings, SGD reached 100% accuracy in at least 20% of 25 trials.Successful models converged within tc ≤ c · n^αk ≤ 10^5 steps for architecture-dependent constants.
  • Less robust configurations: Some minimally expressive MLPs and the Transformer configuration required batch sizes B ≥ 16 for the positive results to hold.The Transformer setting used Adam rather than SGD.
  • Phase transitions in training curves: Most architectures showed long plateaus followed by rapid validation-error decreases, although two architectures instead showed an initially linear error decline.In the online setting, running time and dataset size are coupled.
  • Random search or hidden progress: Convergence times adapt to sparsity k with n^O(k) scaling, whereas random search would predict 2^Ω(n)-type behavior and frequent unusually early successes.Success times also correlate strongly with initialization and exhibit elbows for larger n, unlike the random-search picture.
  • Random search or hidden progress: The paper therefore treats exhaustive search as insufficient: internal training-state changes precede the visible phase transition in loss and accuracy.Figure 3 presents gradual progress in SGD iterates despite black-box plateaus.

4 Theoretical analyses

The theoretical analysis explains parity learning through informative population gradients and tractable PolyNet dynamics rather than random search. It establishes convergence results while identifying assumptions that limit their coverage.

  • Provable emergence of the parity indices in high-precision gradients: At initialization, population-gradient coordinates can reveal the relevant parity subset when the gradient is estimated accurately enough.This provides a mechanism for extracting S before the network has visibly reduced loss.
  • Provable emergence of the parity indices in high-precision gradients: A Fourier gap separates relevant order-(k−1) coefficients from irrelevant order-(k+1) coefficients, enabling feature identification.The paper defines a γ-Fourier gap by requiring every relevant lower-order coefficient to exceed every enclosing higher-order coefficient by at least γ.
  • Provable emergence of the parity indices in high-precision gradients: For the majority-derived initialization, γ = Θ(n^−(k−1)/2), and the relevant coordinates can be recovered from e^O(n^(k−1)) samples.The gap follows from closed-form formulas for majority’s Fourier spectrum.
  • Provable emergence of the parity indices in high-precision gradients: SGD on a suitably initialized ReLU MLP reaches expected loss at most ϵ within O(k^3r^2n/ϵ^2) iterations under specified width, batch-size, and hinge-loss conditions.The theorem assumes even k, a particular ±1 initialization scheme, and B = Ω(n^k log(n/ϵ)).
  • Scope of the formal MLP result: The formal MLP theorem does not cover the broader empirical regime, including uniform or Gaussian initialization and small batches such as B = 1.Extending the argument requires Fourier anti-concentration results that the paper leaves open.
  • Disjoint-PolyNet trajectory analysis: Low-width learning lies outside the NTK regime because no fixed low-dimensional kernel can fit all sparse parities, whereas the analyzed PolyNet yields tractable trajectory dynamics.The disjoint-PolyNet analysis assumes one relevant coordinate per input partition.
  • Disjoint-PolyNet trajectory analysis: Disjoint-PolyNets exhibit a loss plateau and then rapid improvement, and online SGD learns disjoint parities within n^O(k) iterations.The architecture’s restricted parity family still contains (n/k)^k possible relevant sets.

5 Hidden progress: discussion and additional experiments

Additional experiments expose hidden progress and resource-dependent phenomena beyond black-box loss curves. They examine model width, finite-sample training, and depth as distinct aspects of parity learning.

  • Hidden progress measures: Weight movement and Fourier-gap measurements reveal gradual improvement even when training loss remains uninformative.The weight movement norm is motivated as a linearized estimate of the initial population gradient.
  • Roles of overparameterization vs. oversampling: Increasing width does not provide the 1/r speedup expected from parallel random search because SGD sequentially amplifies progress.The paper reports diminishing returns from running identical copies of SGD.
  • Emergence of grokking: With smaller finite samples and weight decay, minibatch SGD can learn sparse parities while exhibiting grokking: train error reaches zero well before test error.The main results instead use online learning with fresh minibatches.
  • Deeper networks: Deeper polynomial-activation MLPs can achieve near-perfect accuracy even when greedy layer-wise training remains at trivial performance.This supplies a counterexample to the stated “deep only works if shallow is good” principle.

6 Conclusion

The paper presents sparse parity learning as a synthetic test case for computational scaling in deep learning, combining near-lower-bound runtimes with hidden progress behind abrupt training curves. It also emphasizes that broader applicability and separately scaling samples, time, and model size remain open questions.

  • Conclusion: A variety of neural architectures solve sparse parity with iteration counts nearly matching the sparsity-dependent SQ lower bound.The conclusion frames this as evidence that computational resources affect optimization beyond statistical capacity.
  • Conclusion: SGD’s abrupt loss and accuracy transitions conceal continual progress toward the sparse solution.This conclusion is consistent with the paper’s hidden-progress measurements and theoretical mechanism.
  • Limitations and open questions: The work primarily studies online learning, where fresh i.i.d. samples couple training iterations with sample usage.The authors call for experiments that scale samples, time, and model size separately.
  • Limitations and open questions: Extending the insights to complex or real-world combinatorial tasks, including NLP and program synthesis, remains an open direction.The paper specifically asks whether such tasks contain parity-like exhaustive-search subtasks.
  • Scope: The theoretical and empirical analyses use a heavily idealized synthetic setting, with no direct societal impacts claimed by the authors.This scope boundary limits direct interpretation beyond the synthetic problem.

A.2 Neural networks and standard training

The paper formalizes parity learning within the standard online neural-network training pipeline and situates its results among feature-learning, statistical-mechanics, and NTK analyses.

  • Standard training pipeline: The learner receives i.i.d. batches and is evaluated by convergence time, the first iteration reaching error at most ϵ.The formulation permits improper continuous hypothesis classes and defines convergence time in iterations, equivalently tB samples.
  • Standard training pipeline: Gradient descent updates neural-network parameters using a chosen loss, initialization, learning-rate schedule, and weight-decay schedule.Online and stochastic gradient descent are treated as equivalent names for the update rule in this setting.
  • Neural architectures: The analysis includes MLPs ranging from single neurons to wider networks, with layer-specific optimization schedules allowed theoretically.The paper focuses on continuous functions whose signs produce classifiers.
  • Related analyses: Prior work studies feature learning beyond the NTK regime, but several results rely on structured input distributions or assumptions that do not hold for Boolean-hypercube parity.Related parity analyses also differ by leaking label information, requiring linear components, or restricting the sparsity level.
  • Related analyses: The paper distinguishes its setting from NTK results requiring model size Ω(n^k), while analyzing networks whose hidden-neuron count does not depend on the input dimension.Other work obtains O(n) sample complexity outside NTK using networks of size O(n^n), which are much larger than those considered here.

B.1 Global convergence for SGD on MLPs

This section proves that appropriately initialized and scheduled MLPs can learn sparse parities through a gradient signal that identifies relevant coordinates, yielding high-probability convergence guarantees.

  • Convergence guarantee: The theorem uses an unbiased random initialization and a schedule that updates all weights initially, then freezes first-layer weights while continuing output-layer optimization.The stated schedule also regularizes weights only during the first step and never regularizes biases.
  • Feature recovery: The proof constructs ReLU neurons whose first updates align relevant coordinates while controlling irrelevant weights, biases, activations, and stochastic-gradient deviations.The argument uses Fourier coefficients of majority and concentration bounds to obtain a suitable neuron subset with high probability.
  • Convergence guarantee: The analysis combines a good output-layer solution, convex optimization of the remaining objective, and bounded stochastic gradients to establish the final expected guarantee.The proof explicitly uses conditional unbiasedness of stochastic gradients and a standard SGD convergence result.
  • Feature recovery: A Fourier gap in the neuron’s population gradient makes the k largest gradient coordinates exactly the coordinates in the sparse parity.This establishes feature recoverability from an estimated correlation-loss gradient.

B.3.1 Gradient flow analysis

Gradient-flow analysis explains the apparent training plateau: relevant weights steadily amplify while prediction error remains near chance, followed by rapid convergence once those weights become dominant.

  • Weight dynamics: Irrelevant weights remain fixed at initialization, while each relevant weight follows the same increasing trajectory shifted by its initial value.The squared relevant-weight displacement q(t) is strictly increasing and provides the main time variable for the analysis.
  • Weight dynamics: The relevant weights eventually diverge under gradient flow, and the time required to reach a given magnitude can be bounded through q(t) and its inverse.The analysis separately bounds growth for k = 2 and k > 2.
  • Phase transition: For arbitrarily small γ, sufficiently long inputs make almost all training occur with error above 1/2 −γ before the final transition to zero error.The subsequent period from large finite weights to perfect accuracy is asymptotically much shorter than the near-chance phase.
  • Phase transition: With standard-normal initialization, the resulting long near-trivial-accuracy phase and short perfect-accuracy phase produce the loss plateau illustrated by Figure 5.The theorem conditions on a positive product of relevant initial weights and holds with probability 1 −1/poly(n′).
  • SGD extension: The same disjoint-PolyNet analysis extends to online SGD at any batch size B ≥1 through bounded stochastic deviations and an adaptive learning-rate schedule.The stated theorem gives an iteration bound proportional to log(2nT/δ) log(2k/ϵ)(3n′ −2)^2k−1 under specified initialization and probability conditions.

C Additional figures, experiments, and discussion

Appendix C expands the empirical picture with convergence, robustness, scaling, hidden-progress, finite-sample, and noisy-parity experiments. These results probe how architecture, resources, and data conditions shape parity learning.

  • Convergence times, success probabilities, and scaling laws: The appendix reports convergence times, success probabilities, and coarse scaling laws across many architecture configurations.Figures 7–10 summarize convergence behavior, including initialization-sensitive variance and small-instance scaling estimates.
  • Convergence times, success probabilities, and scaling laws: Large batch sizes make training extremely robust across the tested architecture settings.Figure 8 measures the percentage of runs converging within 10^5 iterations over 25 random trials.
  • Further empirical explorations: The appendix finds no parallel speedup from width, although wider models reduce the upper tail of long convergence times through variance reduction.This supports a deterministic and sequential interpretation rather than random search over size-k subsets.
  • Further empirical explorations: Finite-sample experiments show negligible generalization error above the statistical threshold, training failure with too little data, and grokking in an intermediate regime.Weight decay improves generalization but can also cause optimization failure at large values.
  • Further empirical explorations: The appendix extends the investigation to noisy parities and layer-wise-learning counterexamples, while polynomial-activation MLPs show no initial error plateau.These experiments broaden the testbed beyond the main noiseless and standard-architecture settings.

C.1 Fourier gaps at initialization and SGD iterates

Appendix C.1 examines Fourier gaps beyond the exact ReLU sign-initialization theory. Numerical evidence finds comparable gaps for other initializations and sinusoidal activations, while SGD can amplify the gap along its path.

  • Theoretical scope: The current end-to-end theorem requires ReLU activations and sign-vector initialization because its gap condition comes from exact majority-function Fourier formulas.Broader guarantees would require analogous gaps for more general population gradients.
  • Fourier-gap implications: A positive Fourier gap allows one parity coordinate to be identified from O(1/γ^2) gradient samples.The definition compares relevant and irrelevant Fourier contributions in the population gradient.
  • Random LTFs: ReLU random sign initialization yields a Fourier gap γ ≥ n^-Ω(k) at every target set S.For i.i.d. uniform and Gaussian initializations, Figure 11 indicates comparable gaps for small n and k.
  • Random non-LTFs: Sinusoidal activations also exhibit large Fourier gaps in their population gradients.This extends the empirical mechanism beyond linear threshold functions.
  • Boolean functions along the SGD path: Along sinusoidal-neuron SGD paths, the Fourier gap remains positive and is amplified by training.This helps connect static-initialization analysis with time-varying empirical iterates.

C.2 Counterintuitive roles of the building blocks of deep learning

The appendix shows that activations, biases, initialization, batch size, and learning rate have interacting computational roles in feature emergence. Hidden progress can occur through weight movement even when loss and accuracy remain uninformative.

  • Activation functions: Non-smooth activations such as ReLU strengthen Fourier-gap-based feature emergence, independently of representational capacity and local-minima considerations.The relevant mechanism depends on discontinuous derivatives rather than only on expressive power.
  • Biases: Biases are necessary in theory and practice for odd-k variants because unbiased majority has zero even-degree Fourier coefficients.Biases also shift the loss surface in the experiments.
  • Initializations: Initialization must both remain close to the desired solution and permit SGD to amplify the relevant Fourier-gap signal.This creates a twofold constraint on initialization distributions.
  • Batch sizes and learning rates: SGD’s movement can amplify the Fourier gap, but drifting iterates can also introduce bias relative to a static-initialization analysis.The appendix links this drift to degradations in some experiments while noting helpful movement in others.
  • Hidden progress measures: Weight movement and the ℓ∞ path length reveal hidden progress that loss and accuracy can miss.The progress measure ρ is defined as a state-dependent quantity predictive of time to convergence; its dynamics differ from the maximum of unbiased random walks.
  • Model size and neuron dynamics: Increasing width provides variance reduction rather than parallel speedups, consistent with sequential feature learning.Multiple neurons tend to learn the correct features at different times, producing staircase-like curves.

C.5 Learning and grokking in the finite-sample case

Appendix C.5–C.6 studies finite samples and label noise, showing tradeoffs between generalization and optimization and extending the Fourier-gap mechanism to noisy parities.

  • Finite-sample setting: Weight decay improves generalization by expanding the sample-size range with eventual correct solutions, but large decay can prevent training.With small samples and tuned decay, the model initially overfits before later generalizing, exhibiting grokking.
  • Motivation: The noisy setting is important because noiseless parity admits Gaussian elimination, whereas noisy parity is presented as the emblematic computationally hard distribution.This motivates testing whether the observed training phenomenon survives label noise.
  • Finite-sample setting: When the sample size is much larger than Θ(k log n), generalization error is negligible; with too little data, the model fails to train.Intermediate sample sizes can still yield eventual convergence to the correct solution.
  • Noisy parities: A noiseless Fourier gap γ becomes ε · γ under the paper’s noisy-parity formulation.Thus, the theoretical signal weakens proportionally with the noise parameter.
  • Noisy parities: Label-noise experiments show nontrivial and sometimes 100% accuracy, although constant-learning-rate SGD does not always converge to 100% accuracy.The experiments use random label flipping in noisy parity distributions.

C.7 Counterexample for layer-by-layer learning

The section shows that end-to-end training can learn parities that layer-by-layer training cannot, and reports successful empirical convergence across several architectures and settings. It also documents an activation-dependent exception in which wide polynomial networks make continuous progress visible in the training curves.

  • Construction where layer-by-layer learning is impossible: A degree-2 polynomial L-layer MLP can represent parities up to degree 2L−1, but an individual layer cannot represent a parity of k > 2.This creates a gap between the representational ability of the composed network and that of each individual layer.
  • Construction where layer-by-layer learning is impossible: The population gradient is zero for an individual layer because each coordinate correlates a k-wise parity with a degree-2 polynomial.Layer-by-layer training therefore receives no information about the target parity in this setting.
  • Construction where layer-by-layer learning is impossible: End-to-end training provides a positive mechanism: downstream layers give earlier-layer gradients greater representation capacity in terms of polynomial degree.The experiments resolve positively whether end-to-end training works in this setting.
  • Results: end-to-end training works empirically: 100% accuracy was achieved empirically with small MLPs, including width (r1, r2) = (2, 1) for 3-layer networks across n ∈ {10, 20, 30} and k ∈ {1, 2, 3, 4}.Over 10 random seeds, all such models converged within 20000 iterations.
  • Results: end-to-end training works empirically: All tested 4-layer models converged within 50000 iterations for k ∈ {1, 2, 3, 4, 5, 6}, while selected larger-k settings converged within 500000 iterations.The tested models failed to converge when k > 2L−1.
  • Training-curve behavior: Wide polynomial-activation MLPs show continuous progress as width and batch size increase, unlike ReLU networks with sharp phase transitions between plateaus.With enough overparameterization and over-sampling, this progress becomes visible rather than hidden behind flat loss or error curves.

D.2 Training curves and convergence time plots

The paper estimates training behavior using fixed sampled evaluation batches and reports convergence and scaling statistics with procedures designed to reduce computational cost and variance. It also records substantial CPU and GPU expenditure across the broader experimental program.

  • Evaluation procedure: Population losses and accuracies are approximated with a single batch of size 8192 sampled at training start from the same distribution.Representative runs use seed 0, while displayed multi-run experiments use seeds 0 through R −1.
  • Convergence measurement: Figures 7 and 8 record validation accuracy every 10 iterations and define convergence as reaching 100% accuracy within 10^5 iterations.Reported values use the 10th percentile over 25 random seeds to reduce initialization-sensitive variance.
  • Convergence measurement: Larger-scale convergence probes use a validation sample of size 128 to reduce computational load.For underparameterized networks, convergence instead requires 10 consecutive batches with accuracy at least 55%.
  • Uncertainty and trial counts: Median convergence-time curves use 95% bootstrap confidence intervals from 100 bootstrap samples, with 1000 random trials per curve point.Halted curves indicate that more than 50% of runs failed to converge within 10^5 iterations.
  • Compute expenditure: The broader study trained approximately 10^8 models, consuming about 1500 CPU hours and 200 GPU hours.GPU experiments included width-r ≥ 100 MLPs, n ≥ 100 scaling studies, and Transformer experiments.
Loading 2207.08799v3…