Hidden Progress in Deep Learning: SGD Learns Parities Near the Computational Limit
Authors: Boaz Barak
Benjamin L. Edelman
Surbhi Goel
Sham M. Kakade
eran malach
Cyril Zhang
Venue: NeurIPS 2022 Accept (2022)
Keywords: deep learning
feature learning
parity
emergence
phase transitions

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.

Hidden Progress in Deep Learning:
SGD Learns Parities Near the Computational Limit
Boaz Barak Harvard University
Benjamin L. Edelman
Surbhi Goel Microsoft Research & University of Pennsylvania
Harvard University
Sham Kakade Harvard University
Eran Malach Hebrew University of Jerusalem
Cyril Zhang Microsoft Research
biboazbarak. org,
bedelmandg. edu,
surbhig@cis srrbbiggcis.upen edu
sham@seas harvard. edu,
eran. eran. mww.mmmmaallllmmmmmmmmmmmmmmmmmm hujii
cyrilzhangdnicroosftt..
Abstract
There is mounting evidence of emergent phenomena in the capabilities of deep learning methods 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 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 sparse prior. Our theoretical analysis shows that these observations explained by Langevin-like mechanism, whereby SGD "stumbles in the dark" until finds the hidden set features (a natural algorithm which also runs n. (kk) time). Instead, Fourier gap in the population gradient, making continual progress that is invisible loss and error metrics.
scale up datasets, model sizes, and training times. While
show that SGD gradually amplifies the sparse solution via
Introduction
In deep learning, performance improvements frequently observed upon simply scaling up re- sources (such as data, model size, and training time). While these improvements are often continuous in terms of these resources, some of the most surprising recent advances in the field have been emer- gent capabilities: at a certain threshold, behavior changes qualitatively and discontinuously. Through statistical lens, it is well-understood that larger models, trained with more data, can fit more complex and expressive functions. However, far less is known about the analogous computational question: how does the scaling these resources influence the success of gradient- optimizaaion?
These phase transitions cannot be explained via statistical capacity alone: they can appear even when the amount of data remains fixed, with only model size or training time increasing. A timely example the emergence of reasoning and few-shot learning capabilities when scaling up language models
(Radford et al. 2019 Brown et al. 2020 Chowdhery al. 2022 Hoffmann et al. 2022); Srivastaval et al. (2022) identify various tasks which language models are only able to solve if they are larger
than critical scale. Power et al. (2022) give examples of discontinuous improvements in population accuracy ("grokking" when running time increases, while dataset and model sizes remain fixed.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Hell MLP (Bm32)
ReLL MUP (5-1924)
RaLU MU (5=1)
activation MLP
width 100 ReLu MLP
Wisth- xr MLP
Itrration to conuargence
vaidation over
2.5
23
36
widhh-1 AV activation
width-1 sindw x xm)
Trasformer
PolWet NEW, x b)
Width 11hWW X
PolyNit Fiw:
331
1me
164
online Draining examples
parity dimersion B
Figure 1: Main empirical findings glance. A variety of neural networks, with standard training and initialization, can solve the (n,, k)-parity learning problem, with a number of iterations scaling as n ((00 Left: Training curves under various algorithmic choices (architecture, batch size, learning rate) the (n- 50, k- = 3) 3)-parity problem. Right: Median convergence times for small (n, k).
In this work, we analyze the computational aspects of scaling in deep learning, in an elementary synthetic setting which already exhibits discontinuous improvements. Specifically, we consider the supervised learning problem of learning sparse parity: the label is the parity (XOR) of k < n bits in random length-n binary string. This problem computationally difficult for range of algorithms, including gradient- based (Kearns) 1998) and streaming (Kol et al., 2017) algorithms. We focus on analyzing the resource measure of training time, and demonstrate that the loss curves for sparse parities display phase transition across a variety of architectures and hyperparameters (see Figure T left). Strikingly, we observe that SGD finds the sparse subset (and hence, reaches error) with variety of activation functions and initialization schemes, even with no peeeparrameteiization.
natural hypothesis to explain SGD's success learning parities, with no visible progress in error and loss for most of training, would be that it simply "stumbles in the dark", performing random search for the unknown target (e.g. via stochastic gradient Langevin dynamics). If that were the case, might expect observe convergence time of 20(m), like naive search over parameters or subsets of indices. However, Figure [ right), already provides some evidence against this "random search" hypothesis: the convergence time adapts to the sparsity parameter k. with a scaling of n ((k) on small instances. Notably, such a convergence rate implies that SGD is closer to achieving the optimal computation time among natural class of algorithms (namely, statistical query algorithms).
Through an extensive empirical analysis of the scaling behavior of a variety of models, as well as theoretical analysis, we give strong evidence against the "stumbling in the dark" viewpoint. Instead, there is a hidden progress measure under which SGD is steadily improving. Furthermore, and perhaps surprisingly, we show that SGD achieves a computational runtime much closer to the optimal SQ lower bound than simply doing (non-sparse) parameter search. More generally, our investigations reveal number of notable phenomena regarding the dependence of SGD's performance on resources: we identify phase transitions when varying data, model size, and training time.
1.1 Our contributions
SGD learns sparse parities. known from SQ lower bounds that with a constant noise level, gradient descent any architecture requires at least n R(k)) computational steps to learn k-sparse n-dimensional parities (for background, see Appendix A). We first show a wide variety of positive empirical results, in which neural networks successfully solve the parity problem in a number of iterations which scales near this computational limit:
Empirical Finding 1. For all small instances (n 30, < 4) of the sparse parity problem, architectures A E {2-layer MLPs, Transformer sinusoidalloscillaing
neurons, PolyNet Ph. initial- izations in {uniform, Gaussian, Bernoulli), and batch sizes 1 < B S 1024, SGD on solves the (n, k) sparse parity problem (w.p. 2 0.2) within most ok steps, for small constants c,
I With a smaller range of hyperparameters.
A non-stame standardd architecture introduced in this work; see Section 3 for the definition.

---

Theoretical analyses of sparse feature emergence. Our empirical results suggest that, in number of computational steps matching the SQ limit, SGD is able solve the parity problem and identify the influential coordinates, without an explicit sparse prior. We give theoretical analysis which validates this claim.
On 2-layer MLPs of width )0(,), and with batch size n nO(, SGD converges with high probability to a solution with at most e eeror on the (n, kapiiir problem in at most 20(2) (1/y(1/c) iterations.
Informal Theorem 2.
We also present a stronger analysis for an idealized architecture (which we call the disjoint-PolyNae which allows for any batch size, and captures the phase transitions observed in the error curves.
Informal Theorem 3. On disjoint-PolyNer probability to a solution with at most e error on the (n, k) parity problem in at most n ((k) Log(1/d) iterations. Continuous maninuuuss-ime gradient flow exhibits a phase transition: it spends 1 o(1) fraction of its time before convergence with error 2 49%.
SGD (with any batch size B 2 1) converges with high
Our theoretical and empirical results hold in non-overparamettriied regimes (including with width-1 1 sinusoidal neuron), in which no fixed kernel, including the neural tangent kernel (NTK) (Jacot et al. 2018). is sufficiently expressive to fit all sparse parities with a large margin. Thus, our findings comprise an elementary example of combinatorial feature learning: SGD can only successfully converge by learning a low-width sparse representation.
Further empirical explorations. Building upon our positive results, we provide wide variety of preliminary experiments, showing sparse parity learning to be a versatile testhed for understanding the challenges and surprises in solving combinatorial problems with neural networks. These include quantities which reveal the continual hidden progress behind uninformative training curves (as predicted by the theory), experiments at small sample sizes which exhibit grokking (Power al., 2022), as well as an example where greedy layer-wise learning is impossible but end-to-end SGD can learn the layers jointly.
1.2 Related work
We present the most directly related work on feature learning, and learning parities with neural nets. broader discussion can be found in Appendix A.3
SGD and feature learning. Theoretical analysis of gradient descent on neural networks no- toriously hard, due to the non-convex nature of the optimization problem. That said, it has been established that in some settings, the dynamics of GD keep the weights close their initialization. thus behaving like convex optimization over the Neural Tangent Kernel (see, for example, <Jacot et al.) 2018 Allen- et al. 2019 Du et al. 2018)). In contrast, it has been shown that in various tasks, moving away from the fixed features of the NTK is essential for the success of neural networks trained with GD (for example (Yehudai and Shamir
Allen- and Li 2019 Wei et al., 2019) and the review in (Malach et al. 2021p. These results demonstrate that feature learning is an important part of the GD optimization process. Our work also focuses on a setting where feature learning is essential for the target task. In our theoretical analysis, we show that the initial population gradient encodes the relevant features for the problem. The importance of the first gradient step for feature learning has been recently studied in
(Ba et al. 2022).
Learning parities with neural networks. The problem of learning parities using neural networks has been investigated in prior works from various perspectives. It has been demonstrated that parities are hard for gradient-based algorithms, using similar arguments as in the SQ analysis (Shalev-Shwartz al. 2017 Abbe and Sandon 2020). One possible approach for overcoming the computational hardness is to make favorable assumptions on the input distribution. Indeed, recent works show that under various assumptions on the input distribution, neural networks can be efficiently trained to learn parities (XORs) (Daniely and Malach 2020; Shi et al. 2021 Frei et al. 2022] Malach et al. 202T). In contrast to these results, this work takes the approach of intentionally focusing on a hard benchmark task, without assuming that the distribution has some favorable (namely, non-uniform) structure. This setting allows us to probe the performance of deep learning at known computational limit. Notably, the work of Andoni et al. (2014) provides analysis for learning polynomials (and in
3

---

particular, parities) under the uniform distribution. However, their main results require a network of size n (kk) (i.e., extremely overparameterizee network), and provides only partial theoretical and empirical evidence for the success of smaller networks. Studying a related subject, some works have shown that neural networks display a spectral bias, learning to fit low-frequency coefficients before high-frrqueecy ones (Rahaman et al. 2019 Cao et al. 2019).
2 Preliminaries
We provide an expanded discussion of background and related work in Appendix A
Sparse parities. For integer n > and non-empty set S S [m], the (n, -)-pritty function Xs {=1}" + }+1} is defined as Xs (z) = Ilie 24. We define the ppariyy distribution Ds as the joint distribution over (a, y where x is drawn from Uni"({+1)"), the uniform distribution over random length-n sign vectors, and y := (x) is the product of the inputs at the indices given by the "relevant features" S (thus, =1, depending on whether the number of relevant -1 inputs is even or odd). We define the (n, -pprriy learning problem as the task of recovering the S using samples from Ds, where S is chosen at random from ((x)).
A key fact about parities is that they are orthogonal under the correlation inner product: for S S [n].
E (x) = {1 S' (a.0)~Ds
E
(x)
(+))")
otherwise
That is, a learner who guesses indices S" cannot use correlations (equivalently, the accuracy of the hypothesis X.s)) as feedback reveal which indices in S' correct, unless S' is exactly the correct subset. This notion of indistinguishabilit leads to a computational lower bound in the statistical query (SQ) model (Kearns 1998): (nn²) constant-noise queries are necessary. which is far greater than the statistical limit of (log (2) 1 log n samples. The hardness of parity has been used to derive computational hardness results for other settings, like agnostically learning halfspaces (Klivans and Kothari 2014) and MLPs (Goel et al. 2019). Beyond the restricted computational model of statistical queries, noiseless parities can be learned in (nly(n) time via Gaussian elimination.
However, learning sparse noisy parities, even at a very small noise level (i.c., o(1) or n "), is believed
to inherently require ((())) computational steps In all, learning sparse parities is a well-studied combinatorial problem which exemplifies the computational difficulty of learning joint dependence on multiple relevant features.
Notation for neural networks and training. Our main results are presented in the online learning setting, with a stream of i.i.d. batches of examples. At each iteration t 1,..., T, a learning algorithm A receives batch of B examples { st.:)) drawn i..dd from Ds, then outputs classifier De {=1}" + [=]]. We say that A solves the parity task in f steps (with error e) if
Pr (x
(e(x)) = vl 2 1 1-
We will focus the case that 0. sign( f (z: B,)) for some parameters 9e in continuous domain θ and for continuous function f [=1}" x θ + F updated with the ubiquitous online learning algorithm of gradient descent (GD), whose update rule is given by
B
4.11 t -1- (1-A,) - T7t V
Cyy,,s, f(x,,;;
(I)
B
for loss function é: (+1) + F. learning rate schedule (n:) and weight decay schedule {A. 17
The initialization On is drawn randomly from chosen distribution.
Our theoretical analyses and experiments can tolerate noisy parities, that is. random flipping of the label; Appendix C.6 For ease of presentation. state the noiseless setting in the main paper.
'This was first explicitly conjectured by Alekhnovich (2003), and has been the basis for several cryptographic
schemes (e.g.. [Ishai et al. 2008 Applebaum et al. 2009 2010 Bogdanov et al.) 2019)).
'When f(x; = 0 in practice (e.g. with sign initialization), we break the tie arbitrarily. We ensure in the thcoretical analysis that this does not happen.
We allow different layers to have different learning rate and weight decay schedules.

---

PolyNitt convergance time distributions
PolyNet training shared Inits
ReLU MLP convergence times
0.5
10*
terstbin to cenvereene
noma bol frquuny
04-
033
10'
250 500
1000
ronvergence
1500 1750 2002
520
5GD Itaration
1500
2000 3000
parity dimeesioon
Figure 2: Black-box observations on the training dynamics. Left: Histograms of convergence times over 10th random trials, with heavy upper tails but no observed successes near 0 (unlike random search). Center:
Loss curves (and thus, convergence time) depend heavily on initialization, not the randomness of SGD; B 128. 17 = 0.01 are shown here. Right: The power-law exponent (a such that t. & n²) eventually worsens on larger problem instances.
Empirical findings
3.1 SGD on neural networks learns sparse parities
The central phenomenon of study in this work is the empirical observation that neural networks, with standard initialization and training, can solve the (n, -parity problem in a number of iterations scaling as ((k) on small instances. We observed robust positive results for randomly-initializz SGD on the following architectures, indexed by Roman numerals:
2-layer MLPs: ReLU (a(z) = (z)+) or polynomial (a(2) = **) activation, in a wide variety of width regimes r 2 k. Settings (i), (ii), (iii) (resp. (iv). (v), (vi)) use r {10, 100, 1000) ReLU (resp. polynomial) activations. We also consider r = k (exceptional settings (*1), (*ii) ). the minimum width for representing a k-wise parity for both activations.
Next, we consider non-standard activation functions a which allow a one-neuron architecture [1;; w) = a (w To))) x)) to realize k-wise parities. The constructions stem from letting w² = Eies Cx and constructing (-) to interpolate (the appropriate scaling of) k-w" 2 mod 2 with a piecewise linear k-zigzag activation (vii), or a degree-k polynomial (viii). Going step further, single co-zigzag (ix) or sinusoidal (x) neuron represent all k-wise parities. In settings (xi). (xii), (xiii., (xiv), we remove the second trainable layer (setting u = 1). We find that wider architectures with these activations also train successfully.
1-meuron networks:
2
There is growing interest in using parity as a benchmark for combinatorial function learning, long-ran -ragg dependency learning, and length generalization in Transformers (Lu et al. 202T: Edelman et al. 202T Hahn 2020 Anil et al. 2022 Liu et al.) (022). Motivated by these recent theoretical and empirical works, we consider a simplified specialization of the Transformer architecture to this sequence classification problem. This the less-robust setting
Transformers:
(+ii);; the architecture and optimizer are described in Appendix D.1.3]
PolyNets: Our final setting (xv) is the PolyNet, a slightly modified version of the parity machine architecture. Parity machines have been studied extensively in the statistical mechanics of ML literature (see the related work section) as well as in line of work on 'neural cryptography' (Rosen-Zvi et al. 2002). A parity machine outputs the sign of the product of & linear functions of the input. A PolyNet simply outputs the product itself. Both architectures can clearly realize k- sparse parities. The PolyNet architecture was originally motivated by the search for an idealized setting where an end-to-end optimization trajectory analysis is tractable (see Section 4.1 we found in these experiments that this architecture trains very stably and sample-effiiienlyy.
Robust space of positive results. All of the networks listed above were observed to successfully learn sparse parities in a variety of settings. We summarize our findings as follows: for all com- binations of n E {10, 20, 303. 3. l E 3243,4) batch sizes B E (1, 2, 4...,, 1024). initializations (uniform, Gaussian, Bernoulli), loss functions (hinge, square, cross entropy), and architecture configurations {()), (ii, ..., (xv)), SGD solved the parity problem (with 100% accuracy, validated
5

---

on batch of 2 samples) in at least 20% of 25 random trials, for at least one choice of learn- ing rate 77 {0.001, 0.01, 0.1, 1}. The models converged in t I c- na < 10 steps, for small architecture-eeenddeer constants o (see Appendix Figure (left) shows some representative training eurves.
Less robust configurations. Settings (+i) and (fii), where the MLP just barely represents k-sparse parity, and the Transformer setting (fii), are less robust to small batch sizes. In these settings, the same positive results above only held for sufficiently large batch sizes: B > 16. Also, setting (*iii) used the Adam optimizer (which is standard for Transformers); see Appendix D.1.3 for details.
Phase transitions in training curves. For almost all of the architectures, find that that the training curves exhibit phase transitions in terms of running time (and thus, in the online learning setting, dataset size well): long durations of seemingly no progress. followed by periods of rapid decrease in the validation error. Strikingly, for architectures (v) and (vi), this plateau is absent: the error in the initial phase appears to decrease with a linear slope. See Appendix C.8 for more plots.
3.2 Random search hidden progress?
The remainder of this paper seeks to answer the question: "By what mechanism does deep learning solve these emblematic computationally
optimization problems?"
natural hypothesis would be that SGD somehow implicitly performs Monte Carlo random search, "bouncing around" the loss landscape in the absence of useful gradient signal. Upon closer inspection, several empirical observations clash with this hypothesis:
Without an explicit sparsity prior in the architecture or initializa- tion, it is unclear how to account for the runtimes observed in experiments, which adapt the sparsity k. The initializations, which certainly do not prefer sparse functions are close to the correct solutions with probability 22((m) < n
Scaling of convergence times:
No early convergence: Over a large number of random trials, no copies of this randomized algorithm get "lucky" (i.e. solve the problem in significantly fewer than the median number of iterations); see Figure 2 (left.. The success times of random exhaustive search would be distributed Geom(1/ (2))), whose probability mass is highest at t 0 and decreases monotonically with t.
Running these training setups over multiple stochastic batches from a common initialization, we find that loss curves and convergence times are highly correlated with the architecture's 's random initialization, and are quite concentrated conditioned initialization; see Figure D (center).
Sensitivity to initialization, not SGD samples:
Elbows in the scaling curves: For larger the power-law scaling ceases to hold: the exponent worsens (see Figure 2 (right), as well as the discussion in Appendix C.2) This would not be true for random exhaustive search.
Even these observations, which do not probe the internal state of the algorithm, suggest that exhaustive search an insufficient picture of the training dynamics, and different mechanism is at play.
Theoretical analyses
4.1 Provable emergence of the parity indices in nigh-precision gradients
We now provide theoretical account for the success of SGD in solving the (n, ke (-)-parity problem. Our main theoretical observation is that, in many cases, the population gradient of the weights at initialization contains enough "information" for solving the parity problem. That is, given an accurate enough estimate of the initial gradient (by e.g. computing the gradient over a large enough batch size), the relevant subset S can be found.
Indeed, under all standard architectures and initialization, the probability that random network is ((1)- correlated with a sparse parity would be 2 -f(m) since with that probability - o(1 of the total influence would be accounted by the n irrelevant features.

---

sihusolds
Sinusoidal neuren: 50, 50, 3, 1024
parity vs. nolse
2.00
0.6
0.50
0.4
0.23
batch
0.2
pop
pop ertrr
0.0
100
400
600
1000
1200
500
1500
1500
2000
2500
1000
1020
2000
3020
Shuzods neusin weight
0.6
1.0
0.8
8.00
0.6
0.4
-2.23
0.2
prog mossure
-0.50
0.0
200
400
600
800
1000
1200
500
1000
1500
2000
2500
3000
2000
2005
3000
Retulian
Haration:
llaration
Figure 3: Hidden progress when learning parities with neural networks. Left, center: Black-box box losses and accuracies exhibit long plateau and sharp phase transition (top), hiding gradual progress in the SGD iterates (bottom). Right: A hidden progress measure which distinguishes gradual feature amplification (top) from training on noise (bottom).
As a warm-up example, consider training a single ReLUU neuron f(x; w) = (w (wTx) x) with the correlation loss E(y, 77 = yÿ over Ds, from an all-ones initialization = ... 1] R While single neuron cannot express the parity, we observe that the correct subset can be extracted from the population gradient at initialization:
E Ww (y, D(2; w))) (x.y)~Dz
=
E (r.g)~Ds
[- V an; (w x)+]
E (x.D)~~Dz
Xs 1
Σ 3.
2
0
The key insight is that each coordinate in the above expression is correlation between a parity and the function r +> -1 2y 2 0]. and thus Fourier coefficient of this Boolean function. At each relevant coordinate (i E 5), the population gradient is the order-(k: 1) Fourier coefficient S (i]; for the irrelevant features (i g S), is instead the order- (k: + 1) coefficient S U (i}. All we require detectable gap between these quantities. Formally, letting f(r; w) = aw x), letting f(S) == E [f (z) denote the Fourier coefficient of f at S, we isolate the desired property:
Definition 1 (Fourier gap). For a function {+1)* + R and S C [m] of size k, we say that f has --Fuurier gap at S if. for every (k- 1)-element subset S S and (k + 1)-element superset S+ 3 S, holds that f((-) 2 f(S+) +
For the all-ones initialization, observe 1 0] 1+sign(E,. is just an affine transformation of the majority function of xr for which Fourier gap can be established, with 7 (n-n(k11)) 1))2). This arises from closed-form formulas for the Fourier spectrum of majority (see Lemma 2 in Appendix B. landmark result from the harmonic analysis of Boolean functions (Titsworth 1962
O'Donnell 2 Thus, the coordinates S can be recovered from Ö(1/?2) = Ö(n R samples; see Proposition 9 in Appendix B.2 for a formal argument.
Carefully extending this insight, obtain an end-to-end convergence result for ReL.U-activation MLP networks with a particular symmetric choice of +1 initialization, trained with the hinge loss:
Theorem 4 (SGD on MIPs learns sparse parities). Let e E (0, 1). Let 2 2 an even integer, and let Q(k' log(nkfe)) be an odd integer. Then, there exist random initialization scheme, Th and for
X such that for every S S [n] of size k. SGD ReLU MLP of width 52(2*k k log log(k/c)), with
butch size B = (nx log(n/e)) on Ds with the hinge loss, outputs network ʃ (x; 0t) with expected loss E [x[[(x;; 0t), v)] S e in at most 0(k3)2n/e iterations.
B
This does not capture the full range of settings in which we empirically observe successful conver- gence. First, it requires a sign vector initialization, while we observe convergence with other random initialization schemes (namely, uniform and Gaussian). Second. it requires the batch size to scale with
'The expectation is over the randomness of initialization, training and sampling (s. y) Ds.
7

---

n a(k while we also obtain positive results when B is small (even B = 1). Analogous statements for these cases well as other activations and losses) would require Fourier gaps for population gradient functions other than majority; lower bounds on the degree- (k- 1) coefficients ("Fourier anti-concentrationn)) ") are particularly elusive in the literature, and we leave it as an open challenge to establish them in more general settings. We provide preliminary empiries in Appendix CA suggesting that the Fourier gaps in our empirical settings are sufficiently large 10
Low width necessitates feature learning. We note that in the low-width (emn---eeprrameteriieed regimes considered in this work, no fixed kernel (including the neural tangent kernel (Jacot al. 2018). whose dimensionality is the network's 's parameter count) can solve the sparse parity problem.
The following is consequence of results in (Kamath al.) 2020; Malach and Shalev-Shwarke 2022):
Theorem (Low-width NTK cannot fit all parities). Let V ; {+1}" + RD be any D-dimensional embedding with sup, (x)]l2 1. Let R, O, and let é denote the 0-1 loss hinge loss.
DR e -W).
then there exists some S S [ml] of size l such that inf | (Z.y)>Ds
E
(((((()) (w,y)] > >1-6.
Thus, our low-width results lie outside the NTK regime, which requires far larger models (size n ((K)) to express parities. However, we note that better sample complexity bounds are possible in the NTK
regime, with an algorithm more similar to standard SGD (see (Telgarsky 2022) and Appendix A.3
4.2 Posyoett exact trajectory analysis for an idcalized architecture
In this section, we present an architecture (a version of PolyNets (xv)) which empirically exhibits similar behavior to MLPs and bypasses the difficulty of analyzing Fourier gaps. The disjoint- PolyNer takes product over k linear functions of an equal-sized partition Pı....; Ps of the input coordinates: fa; w1:k) == I (W., pp.). As noted the Section 1.2 this equivalent to a tree parity machine, with real-valued (instead of 11) outputs.
This architecture also requires us to assume that the set of size the (n, k) ki)-parity problem is selected such that exactly one index belongs to each disjoint partition, that is, for all i E [k], Sn P. 1. We refer to this problem as the (n.::j-ddsooint parity problem. Note that there are still (n')* (n/k)* different possibilities for S under this restriction. For fixed these represent
constant fraction of the (w) ss (ne/k)* (by Stirling's approximation) possibilities for S in the general non-disjoint case.
Consider training a DisjointPPolyNe w.r.t. the correlation loss. Without loss of generality, assume that each relevant coordinate in S is the first element P.. Then, the population gradient is non-zero only at indices i e S:
gi(wi=x)= = E V ((((;; (1+))) = -E
(w), jut
TP. =
II
W3a1
C1.
This allows us analyze the gradient flow dynamics of the disjoint-PolyNet, without needing to establish Fourier gaps. For each e [k]] in this section we treat wy as a function from Rzo + R= For clarity of exposition, Then, of the relevant weights {w;,1 :
which satisfies the following differential equation: vi; = -gi -9:(wi=
assume all-ones initialization same trajectory. By analyzing the resulting differential equations. we can formally exhibit "phase transition" " -like behavior in the fully deterministic gradient flow setting.
[}]] follow the
Theorem (Loss platcau for gradient flow on Poolonttt.oyNssss... Suppose k 2 3. Let T(c) denote the smallest time at which the error is at most e. Then,
T(0.49) T(0)
2 1 - O 0000(0( ((n')--R/2)
IIn fact, this batch size, the correct parity indices emerge in single SGD step.
10 IIteresstingly we observe that the Fourier gap tends to increase over the course of training. This is not captured by our current thcoretical analysis. 11 We assume for simplicity that n divisible by
Results for Bernoulli and Gaussian initializations are similar, and can be found in the appendix.
8

---

Time selve 40. parpariyy width
m
10000
m 1800
m 1000
700
101
codice ransom tearch
ario
comerrgnee time
underpanmeetnng en (1
0.4
307
0.2
traih
val
0.0
164
iteration
Figure 4: Parity sandbox for understanding the effects of model size and dataset size. Left: Success times vs. network width r on a fixed (40, 3) -ppaiiy task: in accordance with the theory, parallelization experiences diminishing returns (unlike expected success times for random search, shown in green). Underparameterized models (r = 2, were considered successful upon reaching 55% accuracy. Right: Training curves where only the sample size m is varied. The center panels display "grokking" : a large gap between the time to zero train error vs. zero test error.
Informally, the network takes much longer to reach slightly- better- better-than--eeeeeeeeeeee thhnnttriiial accuracy than it takes to go from slightly better than trivial to perfect accuracy. Returning to discrete time, we also analyze the trajectory of disjoint-PolyNetss trained with online SGD at any batch size, confirming that a neural network can learn k-sparse disjoint parities within n (k) iterations.
learns disjoint parities). Suppose we train a Eisjoint-Polylie initialized above, with online SGD. Then there exists adaptive learning rate schedule such that for any > 0, with probability 0.99, the error falls below within Ô ((n')(2k-1) log(1/e)) steps.
Theorem 7 (SGD on disjoint-Polyye
Extended versions of these theorems, along with proofs, can be found in Appendix B.3
Hidden progress: discussion and additional experiments
So far, have shown that sparse parity learning provides an idealized setting in which neural networks successfully learn sparse combinatorial features, with a mechanism of continual progress hiding behind discontinuous training curves. In this section, we outline preliminary explorations on broader range of interesting phenomena which arise in this setting. Details are provided in Appendix C while more systematic investigations are deferred future work.
Hidden progress measures for learning parities. The theoretical and (black-box) empirical results suggest that SGD does not learn parities via the memoryless process of random exhaustive search. This suggests the existence of progress measures: scalar quantities which are functions of the training algorithm's 's state (i.e. the model weights wx) and are predictive of the time successful convergence. We provide some white-box investigations which further support the hypothesis of hidden progress, by examining the gradual improvement in quantities other than the training loss. Appendix C.] we directly plot the Fourier gaps of the population gradient, as function of t. finding that they are large (within small constant factor of those of majority) in practice. In Figure and Appendix + we examine the weight movement norm p(wo:) := ||w, wolloc to reveal hidden progress, motivated by the fact that ut wn a linearized estimate for the initial population gradient.
Roles of overparameterizzatio vs. oversampling. An interesting consequence of our analysis that it illuminates scaling behaviors with respect to third fundamental resource parameter: model size, which we study in terms of network width r. If SGD operated by a "random search" mechanism, one would expect width to provide parallel speedup. Instead, we find that SGD) sequentially amplifies progress. The sharp lower tails in Figure (left) imply that running identical copies of SGD does not give (1/r)x x speedups; more directly, Appendix C.4 (previewed in Figure (left)), we find that convergence times for sparse parities empirically plateau at large model sizes.
Emergence of grokking in the finite-sample (multi-pass) setting. Our main results are presented in the online learning setting (fresh minibatches from Ds at each iteration). While this mitigates the confounding factor of overfitting, it couples the resources training time and independent samples in suboptimal way, due to the computationallstaan statssssial gap for parity learning. In Appendix C.S

---

we find empirically that minibatch SGD (with weight decay) can learn sparse parities. even with s smaller sample sizes m < n². We reliably observe the grokking phenomenon (Power al. 2022): an initial overfitting phase, then delayed phase transition in the generalization error; see the two center panels of Figure (ightt) These results complement and corroborate the findings of Nanda and Lieberum 2022)) who analyze the hidden progress of Transformers trained on arithmetic tasks (a setting which also exhibits grokking).
Deeper networks. It is significant challenge (and generally outside the scope of this work) to understand the interactions between network depth and computationnalssatissiiall efficiency. In Appendix C.7 we show that learning parities with deeper polynomiil--cttivtion MLPs comprises a simple counterexample to the "deep only works if shallow is good" principle of Malach and Shalev-Shwartz (2019) ; deep network
get near-perfect accuracy, even when greedy layer- wiscr training (e.g. (Belilovsky et al. 2019 cannot beat trivial performance. By providing positive theory and empirics which elude these simplified explanations of SGD, we hope to point the way more complete understanding of learning dynamics in the challenging cases where no apparent progress is made for extended periods of time.
6 Conclusion
This work puts forward sparse parity learning as an elementary test case to explore the puzzling features the role of computational (as opposed to statistical) resources in deep learning. In particular, we have shown that a variety of neural architectures solve this combinatorial search problem, with a number of computational steps nearly matching the sparsity-dependees SQ lower bound. Furthermore, we have shown that despite abrupt phase transitions in the loss and accuracy curves, SGD works by gradually amplifying the sparse features "under the hood".
Even in this simple setting, there are several open experimental and theoretical questions. This work largely focuses on the online learning case, which couples training iterations with fresh i.i.d. samples. We believe it would be instructive to investigate parity learning when the three resources of samples, time, and model size are scaled separately. Some very preliminary findings along these lines are presented in Section S It is an open problem to extend our theoretical results to the small-batch setting, as well as the full range of architectures and losses in our experiments. Resolving these questions would require better understanding of the anti-concentratiin behavior of Boolcan Fourier coefficients, which much less studied than the analogous concentration phenomena.
Another important follow-up direction is understanding the extent to which these insights extend from parity learning to more complex (including real-world) combinatorial problem settings, as well as the extent to which non-synthetic tasks (in. e.g., natural language processing and program synthesis) embed within them parity-like subtasks of exhaustive combinatorial search. We hope that our results will lead to further progress towards understanding and improving the optimization dynamics behind the recent slew of dramatic empirical successes of deep learning in these types of domains.
Broader impact. This work seeks to contribute to the foundational understanding of computational scaling behaviors in deep learning. Our theoretical and empirical analyses are in a heavily-idea synthetic problem setting. Hence, we see no direct societal impacts of the results in this study.
Acknowledgements. We would like to thank Lenka Zdeborová for providing us with references to the statistical physics literature on phase transitions in the learning curves of neural networks, and Matus Telgarsky for bringing to our attention the better sample complexity guarantees of 2-sparse parity learning in the NTK regime. Sham Kakade acknowledges funding from the Office of Naval Research under award N00014-22-1-2377.
10

---

References
Emmanuel Abbe and Colin Sandon. Poly-time universality and limitations of deep learning. arXiv preprint arXiv:2001.0 N0i::2001.02992,, 2020.
Emmanuel Abbe, Pritish Kamath, Eran Malach, Colin Sandon, and Nathan Srebro. On the power of differentiable learning versus PAC and SQ learning. Advances in Neural Information Processing Systems, 34, 2021.
Emmanuel Abbe, Elisabetta Cornacchia, Jan Hazła, and Christopher Marquis. An initial align- ment between neural network and target is needed for gradient descent to learn. arXiv preprint UrXiv:2202.12886 2022.
Naman Agarwal, Rohan Anil, Elad Hazan, Tomer Koren, and Cyril Zhang. Disentangling adaptive gradient methods from learning rates. arXiv preprint arXiv:2002. / /803, 2020.
Michael Alekhnovich. More on average case vs approximation complexity. In 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings. pages 298-307. IEEE, 2003.
Zeyuan Allen-Zhu and Yuanzhi Li. What can ResNet learn efficiently, going beyond kernels? Advances in Neural Information Processing Systems. 32, 2019.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. In International Conference on Machine Learning, pages 242-252. PMLR.
2019.
Alexandr Andoni, Rina Panigrahy, Gregory Valiant, and Li Zhang. Learning polynomials with neural networks. In International Conference on Machine Learning, pages 1908-1916. PMLR, 2014.
Cem Anil, Yuhuai Wu, Anders Andreassen, Aitor Lewkowycz, Vedant Misra, Vinay Ramasesh, Ambrose Slone, Guy Gur-Ari, Ethan Dyer, and Behnam Neyshabur, Exploring length generalization in large language models. arXiv preprint arXiv:2207.04990 2022.
Benny Applebaum, David Cash, Chris Peikert, and Amit Sahai. Fast cryptographic primitives and circular-secure encryption based on hard learning problems. In Anmual International Cryptology Conference, pages 595-618, Springer, 2009.
Benny Applebaum, Boaz Barak, and Avi Wigderson. Public-key cryptography from different assumptions. In Proceedings of the forty-second ACM symposium on Theory of computing, pages 171-180, 2010.
Gerard Ben Arous, Reza Gheissari, and Aukosh Jagannath. Online stochastic gradient descent on non-convex losses from high- dimeeniiinii inference. J. Mach. Learn. Res., 22:106-1, 2021.
Jimmy Ba, Murat A Erdogdu, Taiji Suzuki, Zhichao Wang, Denny Wu, and Greg Yang. High- dimensional asymptotics of feature learning: How one gradient step improves the representation. arXiv preprint arXiv:2205.0/445 2022.
Eugene Belilovsky, Michael Eickenberg, and Edouard Oyallon. Greedy layerwise learning can scale to imagenet. In International conference on machine learning, pages 583-593. PMLR, 2019.
Andrew C Berry. The accuracy of the gaussian approximation to the sum of independent variates. Transactions of the American Mathematical Society, 49(1):122-136 1941.
Andrej Bogdanov, Manuel Sabin, and Prashant Nalini Vasudevan. Xor codes and sparse learning parity with noise. Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 986-1004, 2019.
Tom B Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. arXiv preprint arXiv:2005. 11.220005..111... 2020.
Yuan Cao, Zhiying Fang, Yue Wu, Ding-Xuan Zhou, and Quanquan Gu. Towards understanding the spectral bias of deep learning. arXiv preprint arXiv: 1912.01 198, 2019.
Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, et al. Palm: Scaling language modeling with pathways. arXiv preprint arXiv:2204.022 02311, 2022.
Alexandru Damian, Jason Lee, and Mahdi Soltanolkotabi. Neural networks can learn representations with gradient descent. In Conference on Learning Theory, pages 5413-5452. PMLR, 2022.

---

Amit Daniely and Eran Malach. Learning parities with neural networks. Advances in Neural Information Processing Systems, 33:20356-20365, 2020.
Ilias Diakonikolas, Surbhi Goel, Sushrut Karmalkar, Adam Klivans, and Mahdi Soltanolkotabi. Approximation schemes for relu regression. In Conference Learning Theory, pages 1452-1485. PMLR, 2020.
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. arXiv preprint arXiv:1810.02090 2018.
Benjamin L Edelman, Surbhi Goel, Sham Kakade, and Cyril Zhang. Inductive biases and variable
creation in self-attention mechanisms. arXiv preprint arXiv:2110.100990 2021.
Andreas Engel and Christian Van den Broeck. Statistical mechanics of learning. Cambridge University Press, 2001.
Carl-Gustav Esseen. On the Liapunov limit error in the theory of probability. Ark. Mat. Astr. Fys., 28: 1-19, 1942.
Spencer Frei, Yuan Cao, and Quanquan Gu. Agnostic learning of single neuron with gradient descent. Advances in Neural Information Processing Systems, 33:5417-5428, 2020.
Spencer Frei, Niladri S Chatterji, and Peter I. Bartlett. Random feature amplification: Feature learning and generalization in neural networks. arXiv preprint arXiv:220..07626, 2022.
Elizabeth Gardner and Bernard Derrida. Three unfinished works on the optimal storage capacity of networks. Journal of Physics A: Mathematical and General, 22(12):1983, 1989.
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the thirteenth international conference on artificial intelligence and statistics, pages 249-256. JMLR Workshop and Conference Proceedings. 2010.
Surbhi Goel, Sushrut Karmalkar, and Adam Klivans. Time/accuracy tradeoffs for learning a ReLU with respect to Gaussian marginals. Advances in Neural Information Processing Systems, 32, 2019.
Oded Goldreich and Leonid A Levin. A hard-core predicate for all one-way functions. In Proceedings of the twenty-first annual ACM symposium on Theory of computing, pages 25-32, 1989.
Sebastian Goldt, Madhu Advani, Andrew M Saxe, Florent Krzakala, and Lenka Zdeborová. Dynamics of stochastic gradient descent for two-layer neural networks in the teacher-student setup. Advances in neural information processing systems, 32, 2019.
Michael Hahn. Theoretical limitations of self-attention in neural sequence models. Transactions of the Association for Computational Linguistics, 8:156-171, 2020.
Hansel, Mato, and C Meunier. Memorization without generalization in a multilayered neural network. EPL (Europhysics Letters), 20(5):471, 1992.
Godfrey Harold Hardy, John Edensor Littlewood, George Pólya, György Pólya, et al. Inequalities. Cambridge University Press, 1952.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. In Proceedings of the IEEE international conference on computer vision, pages 1026-1034, 2015.
Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendricks, Johannes Welbl, Aidan Clark, et al. Training compute-optimal large language models. arXiv preprint arXiv:2203. 2022.
Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, and Amit Sahai. Cryptography with constant computational overhead. In Proceedings of the 40th Annual ACM Symposium on the Theory of Computing, pages 433-443 2008
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems, 31, 2018.
Ziwei Ji and Matus Telgarsky. Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow relu networks. arXiv preprint 1rXiv:1909.12292 2019.
Kabashima. Perfect loss of generalization due to noise in k= parity machines. Journal of Physics A: Mathematical and General, 1917, 1994.
12

---

Pritish Kamath, Omar Montasser, and Nathan Srebro. Approximate is good enough: Probabilistic variants of dimensional and margin complexity. In Conference on Learning Theory, pages 2236- 2262. PMLR, 2020.
Michael Kearns. Efficient noise-tolerant learning from statistical queries. Journal of the ACM (JACM), 45(6):983-1006, 1998.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.69880 2014.
Adam Klivans and Pravesh Kothari. Embedding hard learning problems into gaussian space. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANOOM 2014). Schloss Bogstuhl-Leibniz-Zeeenn
fuer Informatik, 2014.
Adam R Klivans, Ryan O' Donnell, and Rocco A Servedio. Learning intersections and thresholds of halfspaces. Journal of Computer and System Sciences, 68(4):808-84) 2004.
Gillat Kol, Ran Raz, and Avishay Tal. Time-space hardness of learning sparse parities. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 1067-1080, 2017.
Eyal Kushilevitz and Yishay Mansour. Learning decision trees using the fourier spectrum. SIAM Journal on Computing, 22(6): 1331-1344,, 1993.
Beatrice Laurent and Pascal Massart. Adaptive estimation of quadratic functional by model selection. Annals of Statistics, pages 1302-1338, 2000.
Bingbin Liu, Jordan T Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. Transformers learn shortcuts to automata. arXiv preprint arXiv:2210. 10749, 2022.
Kevin Lu, Aditya Grover, Pieter Abbeel, and Igor Mordatch. Pretrained transformers as universal computation engines. arXiv preprint
2021.
Eran Malach and Shai
Is deeper better only when shallow is good? Advances in Neural Information Processing Systems, 32, 2019.
Eran Malach and Shai Shalev-Shwartz. When hardness of approximation meets hardness of learning. Journal of Machine Learning Research, 23(91):: 1-2,, 2022.
Eran Malach, Pritish Kamath, Emmanuel Abbe, and Nathan Srebro. Quantifying the benefit of using differentiable learning over tangent kernels. In International Conference on Machine Learning.
pages 7379-7389. PMLR, 2021.
GJ Mitchison and RM Durbin. Bounds on the learning capacity of some multi-layer networks. Biological Cybernetics, 6055):345-36,, 1989.
Neel Nanda and Tom Lieberum. A mechanistic interpretabiliity analysis of grokking. Align- ment Forum, 2022. URL http::t/t:///ww wwwp:/wwwwww.....o...oooom...
Ryan O'Donnell Analysis of Boolean fincctions Cambridge University Press, 2014.
Manfred Opper. Learning and generalization in two-layer neural network: The role of the vapnik-
chervonvenkis dimension. Physical review letters, 72(13):2113, 1994.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang. Junjie Bai, and Soumith Chintala. PyTorch: An imperative style, high-performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché- Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 8024 8035. Curran Associates, Inc., 2019. URL http: pdf
Alethea Power, Yuri Burda, Harri Edwards. Igor Babuschkin, and Vedant Misra. Grokking: Gen- cralization beyond overfitting on small algorithmic datasets. arXiv preprint arXiv:2201.02117 2022.
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, llya Sutskever, et al. Language models are unsupervised multitask learners. OpenAl blog, 1(8):9, 2019.
13

---

Nasim Rahaman, Aristide Baratin, Devansh Arpit, Felix Draxler, Min Lin, Fred Hamprecht, Yoshua Bengio, and Aaron Courville. On the spectral bias of neural networks. International Conference on Machine Learning, pages 5301-5310. PMLR, 2019.
Maria Refinetti, Sebastian Goldt, Florent Krzakala, and Lenka Zdeborová. Classifying high- dimensional gaussian mixtures: Where kernel methods fail and neural networks succeed. In International Conference on Machine Learning, pages 8936-8947. PMLR, 2021.
Michal Rosen-Zvi, Einat Klein, Ido Kanter, and Wolfgang Kinzel. Mutual learning in a tree parity machine and its application to cryptography. Physical Review E, 66(6):066135, 2002.
David Saad and Sara Solla. Dynamics of on-line gradient descent learning for multilayer neural networks. Advances in neural information processing systems, 8, 1995a.
David Saad and Sara A Solla. On-line learning in soft committee machines. Physical Review E, 52 (4):4225, 1995b.
Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
Shai Shalev-Shwartz, Ohad Shamir, and Shaked Shammah. Failures of gradient- based deep learning. In International Conference on Machine Learning, pages 3067-3075. PMLR, 2017.
Zhenmei Shi, Junyi Wei, and Yingyu Liang. A theoretical analysis on feature learning in neural networks: Emergence from inputs and advantage over fixed features. In International Conference on Learning Representutions, 2021.
Roberta Simonetti and Nestor Caticha. On-line learning in parity machines. Journal of Physics A: Mathematical and General, 29(16):485, 1996.
Aarohi Srivastava, Abhinav Rastogi. Abhishek Rao, Abu Awal Md Shoeb, Abubakar Abid, Adam Fisch, Adam Brown, Adam Santoro, Aditya Gupta, Adrià Garriga- Alonso, et al. Beyond the imitation game: Quantifying and extrapolating the capabilities of language models. arXiv preprint arXiv:2206.0m 04615, 2022.
Matus Telgarsky. Feature selection with gradient descent on two-layer networks in low-rotation regimes. arXiv preprint arXiv:2208.0277 2022.
Robert C Titsworth. Correlation properties of cyclic sequences. PhD thesis, California Institute of Technology, 1962.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. Advances in neural information processing systems, 30, 2017.
Martin J Wainwright, High-dimensional statistics: A non-asymptotic viewpoint, volume 48. Cam- bridge University Press, 2019.
Timothy LH Watkin, Albrecht Rau, and Michael Bichl. The statistical mechanics of learning rule. Reviews of Modern Physics, 65(2):499, 1993.
Colin Wei, Jason D Lee, Qiang Liu, and Tengyu Ma. Regularization matters: generalization and optimization of neural nets vs their induced kernel. Advances in Neural Information Processing Systems, 32, 2019.
Gilad Yehudai and Shamir Ohad. Learning single neuron with gradient methods. In Conference on Learning Theory, pages 3756-3786. PMLR, 2020.
Gilad Yehudai and Ohad Shamir. On the power and limitations of random features for understanding neural networks. Advances in Neural Information Processing Systems, 32, 2019.
Jingzhao Zhang, Sai Praneeth Karimireddy, Andreas Veit, Seungyeon Kim, Sashank Reddi, Sanjiv Kumar, and Suvrit Sra. Why are adaptive methods good for attention models? Advances in Neural Information Processing Systems, 33:15383-15393, 2020.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
14

---

(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
(d) Have you read the ethics review guidelines and ensured that your paper conforms them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you eite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you're rr using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "reta-Mx0ncm", "reviewer": "Reviewer_3q9X", "summary": "This paper studies the problem of learning k-sparse parties using SGD on neural network models. In particular, standard deep learning approaches (running gradient-based methods from random initialization) exhibit discontinuous improvement in performance with increasing training time. Importantly, this kind of phase transition is quite robust and SGD can robustly find the sparse subset in a number of iterations that nearly matches optimal lower bounds without sparsity prior. This is strongly against the \"random search\" hypothesis. Theoretically, the authors show that the first gradient step contains important information to solve the parity problem and feature learning is crucial (as no kernel can solve the sparse parity problem). Finally, the authors argue there is a hidden progress measure which under SGD is steadily improving.", "questions": "See some of my comments on the weaknesses.\n\nOther questions:\n- I wonder if the authors tried different batch sizes in solving the problem. An empirical batch size scaling curve may provide some insights into the learning dynamics. Also, experiments with SGLD could also be interesting.\n", "limitations": "The authors discussed some of the limitations and broad impact at the end of the paper. I don't see any negative societal impact of this work.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The idea of applying deep learning methods to solve the sparse parity problem is novel and inspiring.\n- The authors conducted comprehensive empirical studies and many results are quite interesting. For example, the results are robust w.r.t the architectures, data subsampling, and initialization schemes, but sensitive to particular initialization.\n- The finding that SGD could solve the problem in a number of iterations that matches the lower bounds is surprising and interesting. I believe this would inspire many other follow-up works.\n- The authors further proved that feature learning is important and the first gradient step can learn features that contain enough information for solving the problem, even though under a restricted setting.\n\nWeaknesses:\n- The authors made the argument that random search is the most natural hypothesis to explain the success of SGD in learning parities. I don't really buy this argument. To me, gradient-based methods have little to do with random search. It is known in the community that SGD uses only local information and is very different from random search. In my opinion, it is not surprising that SGD can do better than random search, instead it is surprising that it can match the optimal lower bound.\n- The hidden progress measure looks quite arbitrary to me. The authors argue gradual weight movement is a potential measure. However, it is unclear how the weight movement connects with \"real\" progress. There are many problems that one can observe weight movement but no improvement in performance.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "pjWCFKx1f3q", "reviewer": "Reviewer_hMvu", "summary": "UPDATED SCORE AFTER REBUTTAL.\n\nThe authors study parity functions of size k on n bits. Since there are $2^n$ subsets of the literals, sampling from them uniformly at random would take time exponential in n to find a specific parity function. In addition to this naive approach, there are standard lower bounds for learning parity functions in the SQ model (as opposed to the more general PAC model). The authors claim, using experiments, that training neural networks with SGD (without any sparsity penalty) matches this lower bound. Finally the authors suggest a \"hidden progress measure\" that changes smoothly despite loss and accuracy plateauing.", "questions": "- What is D for the NTK in Theorem 6? Is this the size of the training set?\n- What does it mean for f to be continuous in line 150 on a discrete space?\n- Figure 2 right: Why are these curves not straight if there is power-law scaling?\n- Does the argument in lines 201-203 assume initialization samples uniformly from all subsets? Can you provide more detail.\n- Please provide a citation for the Fourier spectrum of Majority.\n- How can you distinguish between computational and sample resources in online learning where they are linked?\n", "limitations": "No concerns about negative societal impact.\n\n", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- The problem proposed by the authors is interesting and potentially a useful model for \"grokking.\" \n- The paper considers a variety of different architectures ranging from more realistic to more idealized.\n\nWeaknesses\n- Many of the claims lack clarity or seem overstated.\n- \"Empirical Finding 1\": I'm confused by the quantifiers in this statement. Restricting to small n and k is odd as the lower bound from the SQ model is asymptotic in n. Even the empirical evidence is not convincing. In Figure 2 the lines are clearly not straight, undercutting the claim.\n- The motivation for the progress measure is weak and no explanation for the infinity-norm is given. This progress measure also does not seem to distinguish between the \"stumbling in the dark\" model as surely the progress measure would also increase in this case.\n- Theorem 6 states there exists some distribution over $(x,y)$ that cannot be learned. This seems quite different than the experiments performed for neural networks, which I believe used the uniform distribution rather than asking whether they can learn any distribution over the literals.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "1aFv0hl8jU", "reviewer": "Reviewer_5wtH", "summary": "Inspired by the discontinuous phase transition of running time, this paper studies the computation issue of k-sparse parities of n bits via deep learning method. It shows two main results: 1. With standard initialization and training, SGD can solve the k-sparse n-dimensional parities problem at optimal computation time n^(Ω(k)) steps in statistical query (SQ) model, which is much faster than the convergence time of random search 2^(Ω(n)) as previous conjecture. Additionally, it comes up with a “progress measure”, which can indicate when the sudden increasing of loss and accuracy happens. 2. It empirically and theoretically shows that SGD can do feature learning for parity problem even without sparse prior. ", "questions": "1. I don’t know whether the input from uniform {+1,-1}^n is practical setting in k-sparse n-dimensional parities problem. If not, I think it is a too strong assumption to understand the process of training deep learning.\n2. In theoretical part, the author extends the theoretical part from large batch size n^(Ο(k)) to number of steps n^(Ο(k)) , I don’t understand why we can do such extension and I think it would be helpful if there is an intuitive explanation.\n3. From my understanding, does the convergence time of this parity problem only work for the special network structure “PolyNet”? If so, I think it is far from practice and its impact may be limited.\n4. It was mentioned in Section 2 that  the results are based on online setting. But it is not clearly mentioned in Theorem 4. Does each iteration in Theorem 4 requires new i.i.d. samples? If so, this seems a very strong assumption to hold in practice.\n5. Theorem 4 only requires ploy(k,r) iterations, which is much smaller than the number of iterations n^{O(k)} observed in experiments . While Theorem 4 and experiments have different batch sizes, this discrepancy needs more explanation in order to make Theorem 4 as a supporting result for the experiments.\n6. I am curious about whether there is more naïve explanation to explain why progress measure can indicate the phase transition once the measure passes the certain threshold.", "limitations": "This paper does not have the limitations and potential negative societal impact.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n1. Under specific setting, the author empirically demonstrates an interesting phenomenon under that SGD can solve k-sparse b-dimensional parities problem at optimal computation time in SQ algorithms, which contrasts to random search process as previously thought. Apart from empirical results, this paper provides theoretical analysis of why SGD is successful in solving the parity problem.\n2. This paper has good structure. It starts from the phase transition phenomenon, and then it shows a theoretically analysis with a simple warm-up example as the introduction, which gives me an intuition.  \n3. The proposed progress measure seems to be a useful indicator and correlated with the performance (loss and accuracy).\n\nWeakness\n1. There is lack of explanation forsome theorems, which may make reader confused. For example, the author says that there exist a (n, k) parity distribution and satisfies some inequality constraint with an embedding in theorem 6, but I don’t know how do we get this D-dimensional embedding, is it the output of the network? And how can we use this theorem in practice?\n2. There is lack of explanation for some notations. For example, what “e” denotes in line 281 and what “v(t)” is in theorem 7 (line 291).\n3. The purpose of investigating the parity problem needs to further explain.  If the purpose is to understand deep networks,  why we should start from this parity problem? ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept