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

This paper asks how scaling computational resources affects gradient-based learning, using sparse parity as a statistically easy but computationally difficult test case. Empirical and theoretical analyses show that SGD exhibits phase transitions and gradually amplifies sparse features, approaching sparsity-dependent SQ lower bounds rather than randomly searching.

  • Problem

    How scaling data, model size, and training time affects gradient-based optimization remains less understood than their effect on statistical capacity.

    Source: §1 · p. 1

  • Method

    The paper combines empirical scaling analyses across neural architectures with theoretical analysis of sparse-parity learning and an idealized disjoint-PolyNet.

    Source: §1 · p. 1, §1.1 · p. 3

  • Results

    SGD learns sparse parities in phase-transition regimes, with runtime near the sparsity-dependent SQ lower bound and progress explained by gradual hidden-feature amplification.

    Source: §1 · p. 2, §6 · p. 10

  • Takeaways & Limitations

    Sparse parity learning shows that abrupt loss and accuracy transitions can arise from continual SGD progress that remains invisible to those metrics.

    Source: §6 · p. 10

    The analyses are conducted in a heavily idealized synthetic problem setting, and some theoretical results require restrictive initialization and batch-size assumptions.

    Source: §4.1 · p. 8, §6 · p. 11

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

This work studies how scaling training resources affects gradient-based optimization through sparse parity learning, a statistically easy but computationally difficult task. It shows that SGD exhibits discontinuous transitions and learns sparse representations near computational limits through hidden progress rather than random search.

1 Introduction

  • Across models and resources, the results reject random-search explanations: convergence scales as n^O(k), and phase transitions occur when varying data, model size, and training time.The hidden progress is invisible in loss and error for much of training, while the runtime approaches the natural statistical-query limit.Source: §1 · p. 2

1.1 Our contributions

  • For n ≤30 and k ≤4, SGD solves sparse parities across MLPs, Transformers, sinusoidal neurons, PolyNets, three initializations, and batch sizes 1–1024 within c · n^αk steps with probability at least 0.2.These results hold across the listed architectures and training choices, with small constants c and α.Source: §1.1 · p. 2
  • The theory shows that SGD identifies influential coordinates without an explicit sparse prior: width-2^Θ(k) MLPs reach ε error in at most 2^O(k) · poly(1/ε) iterations with batch size n^O(k).The analysis validates sparse feature emergence near the statistical-query computational limit.Source: §1.1 · p. 3
  • On disjoint-PolyNets, SGD supports any batch size and reaches ε error in n^O(k) · log(1/ε) iterations, while gradient flow remains above 49% error for 1 − o(1) of its time.This idealized architecture captures the phase transitions observed in error curves.Source: §1.1 · p. 3
  • The findings hold in non-overparameterized regimes, including a width-1 sinusoidal neuron, where fixed kernels such as the NTK cannot fit all sparse parities with large margin.Successful optimization therefore requires learning a low-width sparse representation through combinatorial feature learning.Source: §1.1 · p. 3

1.2 Related work

  • Related work establishes that feature learning can be essential beyond NTK dynamics, while prior parity results either identify gradient-based hardness or rely on favorable input distributions and extreme overparameterization.This work instead uses a uniform hard benchmark to probe deep learning near a known computational limit.Source: §1.2 · pp. 3–4

2 Preliminaries

This section defines sparse parity learning, explains its statistical-query hardness despite statistical easiness, and introduces the online gradient-based neural-network training setting.

Sparse parities

  • Sparse parity labels are products of selected input bits, and learning requires recovering the relevant subset S from examples drawn under uniform random inputs.The (n,k)-parity problem randomly selects S and labels each input by the product of its relevant features.Source: §2 · p. 4
  • Parity hypotheses are correlation-orthogonal, so incorrect subsets provide no partial feedback; consequently, SQ learning requires Ω(n^k) constant-noise queries despite a statistical limit of approximately k log n samples.Noiseless parity can nevertheless be learned in polynomial time by Gaussian elimination, whereas sparse noisy parity is believed to require n^Ω(k) computation.Source: §2 · p. 4

Notation for neural networks and training

  • The experiments use online learning: at each iteration, an algorithm receives an i.i.d. batch of B examples from the parity distribution and outputs a classifier.The main analysis focuses on classifiers of the form sign(f(x; θ_t)), with continuous parameters and a continuous scoring function.Source: §2 · p. 4
  • Training updates use gradient descent with a learning-rate schedule, starting from a randomly drawn initialization and optimizing a loss over successive batches.The framework permits noisy parities in the analyses and experiments, although the main presentation states the noiseless setting.Source: §2 · pp. 4–5

3 Empirical findings

Neural networks repeatedly learn k-sparse parities in n^O(k) iterations across diverse architectures and training settings, with abrupt phase transitions that can conceal gradual progress. Multiple observations indicate that SGD is not merely performing exhaustive random search, but follows initialization-dependent dynamics with another mechanism at work.

3.1 SGD on neural networks learns sparse parities

  • Positive results span wide 2-layer MLPs, specially activated one-neuron networks, Transformers, and PolyNets, showing that successful parity learning is not confined to one architecture.The MLPs use ReLU or polynomial activations with widths r ≥ k; one-neuron constructions include zigzag, polynomial, and sinusoidal activations, while PolyNets train stably and sample-efficiently.Source: §3.1 · p. 5
  • 100% accuracy was achieved in at least 20% of trials across n ∈ {10, 20, 30}, k ∈ {2, 3, 4}, batch sizes 1–1024, three initializations, three losses, and 15 architectures, within t_c ≤ c·n^αk ≤ 10^5 steps.The result held for at least one learning rate in {0.001, 0.01, 0.1, 1}, with validation on 2^13 samples.Source: §3.1 · p. 6
  • For almost all architectures, validation error shows long plateaus followed by rapid decreases, whereas architectures (v) and (vi) instead show an initially linear decline.The phase transitions occur in running time and therefore also in dataset size in online learning.Source: §3.1 · p. 6

3.2 Random search or hidden progress?

  • The convergence patterns contradict exhaustive random search: runtimes adapt to k without a sparse prior, no trials converge unusually early, and outcomes depend more on initialization than on SGD batches.For larger n, the power-law scaling develops elbows, while black-box losses and accuracies can hide gradual progress in the iterates.Source: §3.2 · pp. 6–7, Figure 3 · p. 7

4 Theoretical analyses

The theoretical analysis explains parity learning through informative population gradients and exact gradient-flow dynamics, showing both provable convergence and loss-plateau phase transitions under stated architectural and initialization conditions.

4.1 Provable emergence of the parity indices in high-precision gradients

  • High-precision population gradients reveal the hidden parity indices because relevant coordinates exhibit a Fourier gap over irrelevant coordinates.Relevant coordinates correspond to order-(k−1) Fourier coefficients, whereas irrelevant coordinates correspond to order-(k+1) coefficients.Source: §4.1 · p. 7
  • For ReLU MLPs with symmetric ±1 initialization, hinge-loss SGD reaches expected loss at most ϵ in O(k^3r^2n/ϵ^2) iterations under the theorem’s width, batch-size, and parity conditions.The guarantee applies for even k≥2, n=Ω(k^4 log(nk/ϵ)), width r=Ω(2^k k log(k/ϵ)), and batch size B=Ω(n^k log(n/ϵ)).Source: §4.1 · p. 8
  • The Fourier-gap analysis does not cover empirically successful uniform or Gaussian initialization, small batches including B=1, or broader activations and losses.Generalization requires Fourier gaps and degree-(k−1) anti-concentration bounds that the paper leaves as an open challenge.Source: §4.1 · p. 8
  • Low-width parity learning lies outside fixed-kernel regimes: no bounded low-dimensional embedding can fit every k-parity, while NTK expressivity requires models of size n^Ω(k).This establishes that the analyzed low-width results require feature learning rather than a fixed kernel.Source: §4.1 · p. 8

4.2 Disjoint-PolyNet: exact trajectory analysis for an idealized architecture

  • For disjoint-PolyNets, the population gradient is nonzero only on relevant coordinates, enabling exact gradient-flow analysis without proving Fourier gaps.The architecture assumes one relevant index per equal-sized input partition and uses all-ones initialization for the trajectory analysis.Source: §4.2 · pp. 8–9
  • Disjoint-PolyNet gradient flow exhibits a loss plateau and phase-transition-like dynamics, while online SGD learns disjoint parities within n^O(k) iterations with an adaptive schedule.For k≥3, reaching slightly-better-than-trivial accuracy takes much longer than progressing from there to perfect accuracy; Theorem 7 gives probability 0.99 for error below ϵ.Source: §4.2 · p. 9

5 Hidden progress: discussion and additional experiments

Additional experiments support hidden progress in sparse-parity learning and reveal how it interacts with model width, finite-sample training, and network depth. These preliminary findings are deferred to Appendix C and motivate broader study of learning dynamics.

Hidden progress measures

  • Fourier gaps and weight movement grow gradually, supporting hidden progress measures beyond training loss as predictors of successful parity learning.Population-gradient Fourier gaps are large in practice, within a small constant factor of majority, while weight movement exposes progress hidden by discontinuous curves.Source: §5 · p. 10

Roles of overparameterization vs. oversampling

  • Convergence times plateau at large widths, showing that overparameterization does not provide the 1/r speedup expected from parallel random search.The sharp lower tails in Figure 2 imply that running r identical SGD copies does not yield 1/r speedups, consistent with sequential amplification.Source: §5 · p. 10

Emergence of grokking in the finite-sample (multi-pass) setting

  • With weight decay, minibatch SGD learns sparse parities from m ≪ n^k samples and exhibits grokking: overfitting precedes a delayed generalization transition.This complements and corroborates Nanda and Lieberum (2022), while the observed phenomenon is identified as grokking by Power et al. (2022).Source: §5 · p. 10

Deeper networks

  • Deeper polynomial-activation MLPs reach near-perfect accuracy even when greedy layer-wise training cannot exceed trivial performance, contradicting the principle of Malach and Shalev-Shwartz (2019).The comparison also concerns greedy layer-wise methods such as Belilovsky et al. (2019).Source: §5 · p. 10

6 Conclusion … A.1 Parities: orthogonality and computational hardness

The paper establishes sparse parity learning as a test case for computational scaling in deep learning: neural networks solve it near sparsity-dependent SQ limits while SGD gradually amplifies sparse features beneath abrupt loss and accuracy transitions. The appendix frames parity as statistically easy but computationally hard, with orthogonality limiting correlation-based feedback and motivating exhaustive search.

6 Conclusion

  • Neural architectures solve sparse parity learning in computational steps nearly matching the sparsity-dependent SQ lower bound, while SGD gradually amplifies sparse features beneath abrupt loss and accuracy transitions.The conclusion presents sparse parity learning as an elementary test case for computational, rather than statistical, resources in deep learning.Source: §6 · p. 10
  • The study’s online-learning focus leaves separate scaling of samples, time, and model size, small-batch theory, and broader architecture and loss coverage as open questions.Progress on these questions requires better understanding of anti-concentration in Boolean Fourier coefficients.Source: §6 · pp. 10–11
  • Extending these insights to real-world combinatorial problems and identifying parity-like exhaustive-search subtasks in non-synthetic domains are proposed directions.The authors connect this agenda to improving optimization dynamics behind empirical successes in deep learning.Source: §6 · p. 11
  • The work’s theoretical and empirical analyses use a heavily idealized synthetic setting, and the authors identify no direct societal impacts.Its stated broader-impact goal is foundational understanding of computational scaling behaviors in deep learning.Source: §6 · p. 11

A.1 Parities: orthogonality and computational hardness

  • The (n,k)-parity problem asks learners to identify an unknown size-k subset S from uniformly random bits labeled by the parity over S.The statistical limit is Θ(k log n) samples, as stated in the background discussion.Source: §A.1 · p. 17
  • Parity orthogonality prevents correlations from revealing partially correct feature sets, so correlation-based learners must effectively search over subsets.Incorrect guesses are indistinguishable unless the guessed subset exactly matches the target.Source: §A.1 · p. 17
  • SQ algorithms solving (n,k)-parity with T queries of tolerance τ satisfy T/τ^2 ≥ Ω(n^k), making them essentially no better than exhaustive search.Gaussian elimination can solve the example-access problem efficiently, while insufficiently accurate GD remains subject to the SQ lower bound; specialized architectures and accurate gradients can evade it (Abbe and Sandon (2020); Abbe et al. (2021)).Source: §A.1 · p. 17
  • Sparse noisy parities are believed computationally hard, underpinning cryptographic schemes, while the paper reports robustness of its empirical and theoretical results to Θ(1) noise.Prior work includes Alekhnovich (2003), Applebaum et al. (2009, 2010), Ishai et al. (2008), and Kol et al. (2017).Source: §A.1 · p. 17

A.2 Neural networks and standard training … B.3 Global convergence for disjoint-PolyNets

This section formalizes online SGD and analyzes neural-network methods for sparse-parity learning, including ReLU MLPs and disjoint-PolyNets. It establishes global convergence and exact recovery results, attributing progress to Fourier gaps in population gradients.

A.2 Neural networks and standard training

  • The standard formulation studies online i.i.d.-batch learning of parity with continuous, potentially improper hypotheses, defining convergence by the first iteration reaching error ϵ.The framework includes GD/SGD updates, multilayer perceptrons including single neurons, layer-specific learning-rate and weight-decay schedules, and permutation-symmetric architectures with S = [k] chosen canonically.Source: §A.2 · pp. 17–18

A.3 Additional related work

  • Prior neural-network parity analyses rely on input or label structure, whereas this work studies uniformly distributed Boolean inputs whose labels are uncorrelated with features.Related approaches exploit spread conditions, leaked relevant bits, class-specific patterns, or first-step correlations; the paper notes that these assumptions do not apply to its parity setting.Source: §A.3 · pp. 18–19
  • Unlike prior statistical-mechanics work, the paper claims that k-sparse parities can be learned near known lower bounds and exhibit gradient-descent phase transitions.It introduces real-valued PolyNets and analyzes disjoint-PolyNets, while stating that prior work had not shown near-lower-bound learning of k-sparse parities or phase transitions during gradient descent.Source: §A.3 · p. 19

B.1 Global convergence for SGD on MLPs

  • For majority, when n ≥ 4k, there is a γ_k-Fourier gap at a size-k set, with γ_k = 0.03(n − 1)^−k−1.Source: §B.1 · p. 21
  • SGD on randomly initialized MLPs learns even-sparse parities under a specified learning-rate and weight-decay schedule.The theorem uses unbiased initialization, a first-step update, subsequent optimization of later-layer weights, and unregularized biases.Source: §B.1 · pp. 25–26

B.2 Recoverability of the parity indices from Fourier gaps

  • A γ-Fourier gap guarantees that the k largest absolute entries of an estimated population gradient identify exactly the k indices in the target sparse parity.The result applies to a one-neuron predictor with a general activation and an (n, k)-sparse parity distribution.Source: §B.2 · p. 27

B.3 Global convergence for disjoint-PolyNets

  • The disjoint-PolyNet analysis develops correlation-loss optimization theory, treating gradient flow separately from SGD at arbitrary batch size B ≥1.The architecture partitions the n input coordinates into k groups of equal size when n/k is an integer.Source: §B.3 · p. 27

B.3.1 Gradient flow analysis · B.4 Global convergence and phase transition for gradient flow on disjoint-PolyNets

The analysis shows that disjoint-PolyNet gradient flow leaves irrelevant weights fixed while relevant weights amplify, producing a long near-trivial-accuracy plateau followed by rapid convergence. For SGD, an adaptive learning-rate schedule yields convergence to low 0-1 error within a polynomial iteration bound under the stated initialization and probability conditions.

B.3.1 Gradient flow analysis

  • Gradient flow keeps irrelevant weights fixed at initialization, while the relevant weights evolve through coupled differential equations.The analysis tracks the relevant-weight product and shows it is non-decreasing when the relevant-weight product is initially positive.Source: §B.3.1 · pp. 27–28
  • The squared relevant weights follow a common trajectory shifted by their initializations, enabling inverse-function and Maclaurin-inequality bounds on their growth time.The common trajectory is represented by q(t) := (v_i(t))^2 − (v_i(0))^2, which is strictly increasing.Source: §B.3.1 · p. 28
  • For k > 2, the relevant weights reach infinity in finite bounded time after the growth threshold, and once they explode the network attains zero error.The time remaining after a weight reaches magnitude b is bounded by a term proportional to (b^2 − v_i(0)^2)^{1−k/2}.Source: §B.3.1 · pp. 29, 31
  • For random ±1 initialization and k ≥ 3, the time to reach error 1/2 − γ is 1/(k−2) · (1 − O((n′)^{1−k/2} · γ^{2/k−1})).The result follows from combining the relevant-weight growth bound with the error characterization.Source: §B.3.1 · p. 31
  • With all weights initialized ∼N(0, 1) and k ≥3, gradient flow with high probability spends much longer training with error above 1/2 −γ than the subsequent period until perfect accuracy.Source: §B.3.1 · pp. 31–32

B.4 Global convergence and phase transition for gradient flow on disjoint-PolyNets

  • SGD learns disjoint parities after T ≥ 6 log(2nT/δ) log(2k/ϵ)(3n′ − 2)^{2k−1} iterations for any batch size B ≥ 1, with probability 1/2 over initialization and 1 − δ over sampling.The guarantee uses an adaptive learning-rate schedule and applies for uniformly random ±1 initialization.Source: §B.4 · p. 33
  • The SGD proof controls stochastic-gradient deviations uniformly over time using martingale concentration and Azuma-Hoeffding bounds.With the resulting high-probability control, the proof establishes bounds on irrelevant and relevant weights throughout the training horizon.Source: §B.4 · p. 33
  • The empirical training curves show the same architecture and algorithm adapt to n and k without an explicit sparse prior, while positive results persist across batch sizes including B = 1.Very large and very small batch sizes produce more unstable outliers, whereas larger models are robust across batch sizes.Source: Figure 6 · p. 35

C Additional figures, experiments, and discussion

Appendix C expands the empirical evidence for hidden progress, showing convergence scaling across architectures and robustness of feature amplification. It also examines finite-data, noisy, wide-model, and layer-wise-learning settings, revealing both extensions and limitations of the mechanism.

Convergence times, success probabilities, and scaling laws

  • For small n, convergence times follow tc ∝ n^(α·k) across architecture configurations, while larger n increases the log-log slope under standard training.The appendix reports 10th-percentile convergence times because unlucky initializations create high variance, and sufficiently large batches make training highly robust.Source: C Additional figures, experiments, and… · p. 35, Figure 7 · p. 36, Figure 8 · p. 36

Appendix C.1–C.2

  • Fourier gaps persist beyond sign-vector iterates and ReLU activations, while activation functions, biases, initializations, learning rates, and batch sizes can play conflicting roles.These observations support robustness of feature amplification while motivating stronger theoretical analysis of how training components interact.Source: C Additional figures, experiments, and… · p. 38

Appendix C.3

Appendix C.4

  • Unlike random search, increasing model width does not provide parallel speedups under the feature amplification mechanism.This result connects the mechanism to implications for scaling model size.Source: C Additional figures, experiments, and… · p. 38

Appendix C.5

Appendix C.6

Appendix C.7

  • A counterexample challenges layer-by-layer learning for parity degrees exceeding individual layers’ polynomial-activation degrees, although preliminary experiments show standard training succeeds.The appendix uses this setting to test a proposed explanation of how layers learn.Source: C Additional figures, experiments, and… · p. 38

Appendix C.8

C.1 Fourier gaps at initialization and SGD iterates

The section studies Fourier gaps as the mechanism by which SGD identifies sparse-parity features, extending evidence beyond the ReLU/sign-initialization setting analyzed theoretically. Numerical results show comparable gaps for alternative initializations and sinusoidal activations, while SGD can amplify the initial gap along its path.

Fourier-gap mechanism

  • Fourier concentration above and anti-concentration below the target degree create a gap that lets a batch population gradient identify a parity coordinate.The end-to-end theorem requires ReLU activations and sign-vector initialization because these conditions arise from exact majority-function Fourier formulas.Source: §C.1 · p. 38

Open theoretical scope

  • The broader open question is which Boolean functions besides majority satisfy a γ-Fourier gap with γ ≥ n^-Ω(k).Numerical evidence for other activation-gradient settings suggests that the property may extend beyond the cases covered by the present theory.Source: §C.1 · p. 38

Random LTFs

  • For ReLU networks with random sign initialization, Fourier gaps satisfy γ ≥ n^-Ω(k) at every target set S, while random uniform or Gaussian initializations yield comparable gaps with non-negligible probability for small n and k.The sign-initialization result follows because the Fourier coefficients match those of majority; Figure 11 provides the alternative-initialization evidence.Source: §C.1 · p. 39, Figure 11 · p. 39

Random non-LTFs

  • Large Fourier gaps also appear in population gradients for sinusoidal activations, indicating that feature emergence is empirically robust beyond LTFs and ReLU MLPs.The corresponding theoretical guarantees remain open but could strengthen global-convergence results for MLPs and other architectures.Source: §C.1 · pp. 38–39

Boolean functions along the SGD path

  • When training a sinusoidal neuron, SGD amplifies the initial Fourier gap rather than merely accumulating gradients at a fixed initialization.This addresses a limitation of the current analysis, which approximates time-varying SGD iterates using a large-batch gradient at a static w0.Source: §C.1 · p. 39

C.2 Counterintuitive roles of the building blocks of deep learning · C.3 Hidden progress measures · C.4 Convergence time vs. width

Across these sections, deep-learning components shape parity learning through Fourier-gap amplification rather than generic representational considerations, while hidden progress measures expose optimization progress before loss or accuracy changes. Increasing width does not provide the expected random-search parallel speedup, instead mainly reducing variance in convergence times.

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

  • ReLU-like non-smooth activations strengthen Fourier-gap feature emergence, revealing a sharpness-smoothness tradeoff distinct from representational capacity and local-minimum considerations.Activation choice also affects whether plateaus disappear at large widths and batch sizes.Source: §C.2 · pp. 39–40
  • Biases are necessary to break the even-Fourier-coefficient symmetry that makes some odd-k setups fail, while also shifting the loss surface.This applies to the majority function and all unbiased linear threshold functions.Source: §C.2 · p. 39
  • Initialization must balance proximity to the desired solution with conditions that let SGD amplify the Fourier gap, while drifting iterates can either bias progress or amplify the gap.Multiple randomly initialized neurons may learn correct features at different times, producing symmetry breaking and staircase-like training curves.Source: §C.2 · pp. 39–40
  • Batch size and learning rate govern how SGD accumulates independent-sample evidence: staying near initialization could clarify relevant indices, whereas standard drifting updates introduce bias.Theoretical and empirical results suggest that movement can also help by amplifying the Fourier gap.Source: §C.2 · p. 40

C.3 Hidden progress measures

  • Hidden progress measures are state-dependent quantities predictive of convergence time, introduced to distinguish SGD from memoryless random search and quantify progress while loss and accuracy remain flat.Fourier gaps, relevant-coordinate weight movement, and optimization-path measurements provide such signals.Source: §C.3 · pp. 40–41
  • Relevant-coordinate weights reveal progress before loss changes, and the ∞-norm path length from initialization distinguishes SGD drift from the maximum of n unbiased random walks.Loss becomes visibly improved only after relevant weights exceed irrelevant weights; the path-length measure tracks the predicted drift contribution.Source: §C.3 · p. 41

C.4 Convergence time vs. width

  • No evidence of r× parallel speedups appeared across 1000 runs, supporting a deterministic, sequential parity-learning mechanism; large width instead mitigated long-convergence-time outliers.The experiment used 3 parity instances with n ∈ {30, 40, 50}, k = 3, and widths up to 3 × 10^6.Source: §C.4 · p. 41, Figure 14 · p. 43

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

In finite-sample training, weight decay controls a computational-statistical tradeoff: it can enable eventual generalization and grokking, but excessive decay prevents training.

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

  • The experiments use a fixed width-100 ReLU MLP trained with minibatch SGD, hinge loss, learning rate η = 0.1, batch size B = 32, and varied weight decay λ.Source: §C.5 · p. 43
  • Weight decay λ improves generalization by expanding the range of training-sample sizes m where training eventually finds the correct solution, but large λ prevents training.For small m and appropriately tuned λ, the model initially overfits before eventually finding a classifier that generalizes.Source: §C.5 · p. 43

C.6 Learning noisy parities

The section shows that parity-learning phenomena persist under random classification noise: neural networks can achieve nontrivial, sometimes perfect, accuracy, while the Fourier-gap theory degrades predictably with noise. Finite-sample results further expose a tradeoff between statistical generalization and optimization failure.

Motivations

  • Noisy parity learning is computationally emblematic because noiseless parities admit Gaussian elimination in O(n3) time, whereas noise removes that efficient non-SQ route.The section uses robustness to label noise to test whether the observed deep-learning phenomenon depends on the noiseless setting.Source: §C.6 · p. 43

Finite-sample setting

  • When sample size exceeds Θ(k log n), generalization error is negligible; with too few samples, training fails, while intermediate regimes show grokking and weight decay trades generalization against optimization.Larger weight decay improves generalization but can cause optimization failure.Source: Figure 15 · p. 44, §C.6 · p. 44

Theory

  • A Fourier gap with parameter γ in the noiseless case becomes a gap with parameter ϵ · γ under label noise.Thus, the theoretical analysis extends by scaling the gradient-correlation signal with the noise parameter.Source: §C.6 · p. 45

Experiments

  • Models remain able to learn noisy parities, achieving nontrivial and sometimes 100% accuracy, although constant-rate SGD does not always converge to perfect solutions.These results argue against learning noiseless parities by implicitly simulating efficient algorithms such as Gaussian elimination.Source: §C.6 · p. 45

C.7 Counterexample for layer-by-layer learning … D.1.7 Details for Figure 10

This section presents a counterexample to layer-by-layer learning through end-to-end SGD and documents the activation, architecture, and hyperparameter configurations used in related experiments, including those in Figure 10.

C.7 Counterexample for layer-by-layer learning

  • End-to-end SGD reaches 100% accuracy on sparse parities that individual quadratic-activation layers cannot represent and whose population gradients are zero, demonstrating a counterexample to layer-by-layer learning.Three-layer networks with widths (2, 1) converge through k = 4, while four-layer networks with widths (10, 10, 1) converge through k = 8; convergence fails when k > 2L−1.Source: §C.7 · pp. 45, 47

C.8 Lack of plateaus for wide polynomial-activation MLPs

  • Wide polynomial-activation MLPs exhibit continuous, increasingly visible validation-error descent as width and batch size grow, unlike ReLU networks’ sharp plateau transitions.This is described as an exception to hidden progress and appears specific to polynomial activations rather than ReLU.Source: §C.8 · p. 47, Figure 17 · p. 48

D.1 Deep learning configurations

  • The experiments primarily use hinge loss with Xavier-style uniform initialization, while correlation loss is used in the theoretical analysis and square loss is an alternative empirical loss.Hinge and square losses permit finite-weight zero-loss solutions for architectures representing parity.Source: §D.1 · pp. 47–48

D.1.1 2-layer MLPs

  • The architecture suite includes ReLU and polynomial MLPs, single-neuron zigzag, oscillating-polynomial, triangle-wave, and sinusoidal activations, a simplified Transformer, and PolyNet.Suitable width or activation choices can represent sparse parities, including arbitrary-degree parity for the infinite-zigzag and sinusoidal neurons; PolyNet realizes parity with zero biases.Source: §D.1.1 · p. 48, §D.1.2 · p. 49, §D.1.4 · p. 50

D.1.3 Parity Transformer

  • The simplified Parity Transformer omits several standard components without materially changing preliminary results, but standard SGD rarely converges beyond small problems, motivating Adam experiments.Adam uses β1 = 0.9, β2 = 0.999, ϵ = 10^-8, with only its learning rate tuned.Source: §D.1.3 · pp. 49–50

D.1.5 Details for Figure 1 (left)

  • Figures 1, 6, and 10 vary architectures, widths, activations, batch sizes, learning rates, task difficulty, and optimizer settings, with Figure 10 measuring median convergence time using batch size 32 and hinge loss.The reported configurations include ReLU MLPs, PolyNet, non-standard activations, and Adam for the Transformer setting.Source: §D.1.5 · p. 51, §D.1.6 · p. 51, §D.1.7 · p. 51

D.1.7 Details for Figure 10

  • The figure includes width-1000 ReLU MLPs with η = 1 and width-10, width-100, and width-1000 σ(z) = z^k MLPs with η = 0.01.These are listed as settings (iii), (iv), (v), and (vi).Source: §D.1.7 · p. 51
  • Miscellaneous settings include a width-1 degree-k oscillating-polynomial MLP, a single sinusoidal neuron, a Parity Transformer, and a degree-k PolyNet.The Transformer uses d_emb = 1024, d_attn = 8, H = 128, B = 32, and η = 3 × 10^-4; the other listed learning rates are η = 0.01 and η = 0.05.Source: §D.1.7 · p. 52
  • Additional plots use a width-100 ReLU MLP with η = 1 and a width-100 σ(z) = z^k MLP with η = 1, both extending n for smaller k.These are identified as settings (ii) and (xv).Source: §D.1.7 · p. 52

D.2 Training curves and convergence time plots · D.3 Implementation, hardware, and compute time

Training-curve evaluations used standardized sampling, seeds, convergence criteria, and uncertainty estimates, while extensive CPU and GPU experiments supported robust scaling analyses. Implementation details included PyTorch and compute allocations across experiment types.

D.2 Training curves and convergence time plots

  • Training curves estimated population loss and accuracy from an 8192-example batch sampled once from D_S, using fixed or sequential random seeds.Representative runs used torch.manual_seed(0), while R-run experiments used seeds 0 through R−1.Source: §D.2 · p. 52
  • Figures 7 and 8 recorded validation accuracy every 10 iterations and defined convergence as reaching 100% accuracy within 10^5 iterations.Reported convergence times were the 10th percentile over 25 random seeds.Source: §D.2 · p. 52
  • Figure 9 estimated convergence-time scaling using the smallest α satisfying t_c ≤ c·(n−n_0)^α for n ∈ {10,20,30} and n_0=9.These estimates provide quantitative order-of-magnitude upper bounds and do not extrapolate at constant learning rate.Source: §D.2 · p. 52
  • Larger-scale convergence probes checked accuracy on 128 examples, using ten consecutive batches at least 55% accurate for underparameterized networks.For parity, a weak learner with 1/2+ε accuracy can be efficiently converted into a strong learner that outputs S with high probability (Goldreich and Levin, 1989, Kushilevitz and Mansour, 1993).Source: §D.2 · p. 52
  • Median convergence-time plots used 95% bootstrap confidence intervals from 100 samples, with each curve point based on 1000 random trials.Curves halted when more than half of runs failed to converge within T=10^5 iterations, yielding infinite medians.Source: §D.2 · p. 52

D.3 Implementation, hardware, and compute time

  • All training experiments were implemented in PyTorch (Paszke et al., 2019).Source: §D.3 · p. 52
  • Approximately 10^8 models were trained to certify robust results and precise scaling curves, consuming about 1500 CPU hours and 200 GPU hours.GPU experiments covered width r≥100 MLPs, n≥100 scaling, and Transformers on NVIDIA Tesla P100, Tesla P40, and RTX A6000 hardware.Source: §D.3 · p. 52

Related papers

Loading 2207.08799v3…