Pareto Frontiers in Deep Feature Learning: Data, Compute, Width, and Luck
Authors: Benjamin L. Edelman
Surbhi Goel
Sham M. Kakade
eran malach
Cyril Zhang
Venue: NeurIPS 2023 spotlight (2023)
Keywords: deep learning
feature learning
parity
grokking
lottery tickets
scaling
TL;DR: To learn sparse parities from offline samples, one must be rich, knowledgeable, patient, or lucky. Deep learning naturally interpolates along this tradeoff frontier.

Abstract: In modern deep learning, algorithmic choices (such as width, depth, and learning rate) are known to modulate nuanced resource tradeoffs. This work investigates how these complexities necessarily arise for feature learning in the presence of computational-statistical gaps. We begin by considering offline sparse parity learning, a supervised classification problem which admits a statistical query lower bound for gradient-based training of a multilayer perceptron. This lower bound can be interpreted as a *multi-resource tradeoff frontier*: 
successful learning can only occur if one is sufficiently rich (large model), knowledgeable (large dataset), patient (many training iterations), or lucky (many random guesses). We show, theoretically and experimentally, that sparse initialization and increasing network width yield significant improvements in sample efficiency in this setting. Here, width plays the role of parallel search: it amplifies the probability of finding "lottery ticket" neurons, which learn sparse features more sample-efficiently. Finally, we show that the synthetic sparse parity task can be useful as a proxy for real problems requiring axis-aligned feature learning. We demonstrate improved sample efficiency on tabular classification benchmarks by using wide, sparsely-initialized MLP models; these networks sometimes outperform tuned random forests.

Pareto Frontiers in Deep Feature Learning: Data, Compute, Width, and Luck
Benjamin L, Edelman'
Surbhi Goel?
Sham Kakade
Eran Malach
Cyril Zhang*
Harvard University
University of Pennsylvania
Hebrew University of Jerusalem *Microsoft Research NYC
bedelman@g. harvard. surbhigecis. upenn edu, sham@seas harvard. edu, www.mmallaaalla.mmmmmmmmmmmm htwpchhmmmillui....... il, cyrilzhangimlcroosfft.cco
Abstract
In modern deep learning, algorithmic choices (such as width, depth, and learning rate) are known to modulate nuanced resource tradeoffs. This work investigates how these complexities necessarily arise for feature learning in the presence of computational -tattiiinnl-ttttttiiaalll gaps. We begin by considering offline sparse parity learning, supervised classification problem which admits statistical query lower bound for gradient-based training a multilayer perceptron. This lower bound can be interpreted multi-resource tradeoff frontier: successful learning can only occur if one sufficiently rich (large model), knowledgeable (large dataset), patient (many training iterations), or lucky (many random guesses). We show, theoretically and experimentally, that sparse initialization and increasing network width yield significant improvements in sample efficiency in this setting. Here, width plays the role of parallel search: it amplifies the probability of finding "lottery ticket" neurons, which learn sparse features more sample-efficiently Finally, we show that the synthetic sparse parity task can be useful as a proxy for real problems requiring axis-aligned feature learning. We demonstrate improved sample efficiency on tabular classification benchmarks by using wide, these networks sometimes outperform tuned random forests.
MLP models;
1 Introduction
Algorithm design in deep learning appear to be more like "hacking" than engineering practice. Numerous architectural choices and training heuristics can affect various performance criteria and resource costs in unpredictable ways. Moreover, it is understood that these multifarious hyperparame- ters all interact with each other; as a result, the task of finding the "best" deep learning algorithm for particular scenario is foremost empirically-driven When this delicate balance of considerations is achieved (i.e. when deep learning works well), learning is enabled by phenomena which cannot be explained by statistics or optimization in isolation. natural to ask: this heterogeneity of methods and mechanisms necessary?
This work studies single synthetic binary classification task in which the above complications recognizable, and, in fact, provable. This is the problem of offline (i.e. small-sample) sparse parity learning: identify k-way multiplicative interaction between Boolean variables, given random examples. We begin by interpreting the standard statistical query lower bound for this problem as multi-resource tradeoff frontier for deep learning, balancing between the heterogeneous resources of dataset size, network size, number of iterations, and success probability. We show that in different regimes of simultaneous resource constraints (data, parallel computation, sequential computation.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

% of corverged runs (n-100, k-3, ReLU MLP, unit. Init)
Example train od16,,n)66 rele,moled
109
F
44
6
4
1-led, m-les roted, molet
m-lee ralel, motec
4
4
8
4
4
6
109
46
6
NLF w10th
1
4
4
1
4
6
4
r-16) melel r-10) n-ies
m-lee retelmmole 1-3e mole
r-16), m-
65
8.8
4
3
3
6
6
4
64
4
6
1
6
4
W
300
6
15
99
95
6
16
03
3
05
207
121
107
20
10 12
10
107
10
10
cotapct size m
Beradons
Figure 1: "More data or larger network?" Effects of jointly scaling the dataset and model sizes, for 2-layer MLPs trained to learn sparse parities. Left: A success frontier, where the computational challenge of feature learning can be surmounted by increasing sample size or model size. Each point shows the percentage of successful training runs (out 50 trials) for each (dataset size m, width r); (V) denotes 100% successful trials. Right: 10 example training curves (gray training error; colored test error) for each of the boxed (m, r) pairs. See main text and Section for further details.
and random trials), the standard algorithmic choices in deep learning can succeed by diverse and entangled mechanisms. Specifically, contributions are as follows:
Multi-resource lower and upper bounds. We formulate a "data x width time x luck" lower bound for offline sparse parity learning with feedforward neural nets (Theorem 33. This barrier arises from the classic statistical query (SQ) lower bound for this problem. We show that under different resource constraints, the tractability of learning can be "bought" with varied mixtures of these resources. particular, in Theorems 4 5 prove that by tuning the width and initialization scheme, we can populate this frontier with spectrum of successful models ranging from narrow networks requiring many training samples to sample-efficien networks requiring many neurons, as summarized by the following informal theorem statement:
Informal Theorem 1. Consider the problem of learning (n. k) pariitiss from m i.i.d. samples with 2- 2-yyyer width-r ReLU MLP, whose first-layer neurons initialized with sparsity s. After (I) steps of gradient descent, the l relevant coordinates are identified with probability 0.99 when (1) (2k), r (n/s)) and m (s/k)+=))1)) and when (2) 8 < k; (((nk)(())))))) and (((nkk))=~
Intuitively, this analysis reveals feature learning mechanism by which overparameterization (i.e. large network width) plays a role of parallel search over randomized subnetworks. Each individual hidden-layer neuron has its own sample complexity for identifying the relevant coordinates, based on its Fourier gap (Barak et al. 2022) at initialization. Trained with parallel gradient updates, the full network implicitly acts as an ensemble model over these neurons, whose overall sample complexity is determined by the "winning lottery tickets" (Frankle and Carbin 2018) (i.e. the lucky neurons initialized to have the lowest sample complexity). This departs significantly from the neural tangent kernel (Jacot et al. 2018) regime of function approximation with wide networks, in which overparameterizatioo removes data-dependent feature selection (rather than parallelizing across subnetworks).
Empirical study of neural nets' statistical thresholds for sparse parity learning. We corroborate the theoretical analysis with a systematic empirical study of offline sparse parity learning using SGD on MLPs, demonstrating some of the (perhaps) counterintuitive effects of width, data, and initialization. For example, Figure T highlights our empirical investigation into the interactions between data, width, and success probability. The left figure shows the fractions of successful training runs as a function of dataset size (x-axis) and width (y-axis). Roughly, we see a "success frontier". where having a larger width can be traded off with smaller sample sizes. The right figure depicts some training curves (for various widths and sample sizes). Grokking (Power et al. 2022 Liu et al.) 2022) (discontinuous and delayed generalization behavior induced by optimization dynamics) is evident in some of these figures.

---

"Parity2ree transfer of algorithmic improvements. It is often observed that deep learning methods underperform tree-based methods (e.g. random forests) on tabular datasets, particularly those where the target function depends on a few of the input features in potentially non-smooth manner, see Grrnsstajj et al.] (2022) for recent discussion. Motivated by our findings in the synthetic parity setting (and the observation that the sparse parity task possesses a number of the same properties of these problematic real-world datasets), we then turn to experimentally determine the extent to which our findings also hold for real tabular data. We evaluate MLPs of various depths and initialization sparsities on 16 tabular classification tasks, which were standardized by Grinsstaajn et al. (2022) to compare neural tree-based methods. Figure shows that wider networks and sparse initialization yield improved performance, as in the parity setting. In some cases, our MLPs outperform tuned random forests.
1.1 Related work
In the nascent empirical science of large-scale deep learning, scaling laws (Kaplan al., 2020, Hoff mann et al. 2022) have been shown to extrapolate model performance with remarkable consistency. revealing flexible tradeoff's and Pareto frontiers between the heterogeneous resources of data and computation. The present work reveals that in the simple synthetic setting of parity learning, the same intricacies can studied theoretically and experimentally. In particular, viewing model size x training iterations x random restarts single "total FLOPs" resource, our study explains why data X compute can be a necessary and sufficient resource, through the lens of SQ complexity.
Analyses of deep feature learning. Formally characterizing the representation learning mecha- nisms of neural networks is core research program of deep learning theory. Many recent works have analyzed gradient-based feature learning (Wei et al. [2019] Barak et al. 2022 Zhenmei et al. 2022 Abbe et al. [0222] Damian et al. 2022 Telgarsky 2022), escaping the "lazy" neural tangent kernel
(NTK) regime (Jacot et al. 2018 Chizat al. 2019), in which features are fixed at initialization.
Learning parities with neural networks. The XOR function has been studied as an elementary challenging example since the dawn of artificial neural networks (Minsky and Papert 1969). and has been revisited at various times: e.g. neural cryptography (Rosen-Zvi et al.] 2002); learning interactions via hints in the input distribution (Daniely and Malach, 2020); hard case for self- attention architectures (Hahn 2020). Closest to this work, Barak et al. (2022) find that in the case of online (infinite-dae parity learning, SGD provides feature learning signal for single neuron, and can thus converge at a near-optimal computational rate for non-overpan aan--vrrprramterizeee networks. tradcoff's and grokking in the offline setting, which we address systematically. MMrrill et al. 2023) examine the same problem setting empirically, investigating a mechanism of competing sparse and dense sub-networks. Abbe et al. (2023) provide evidence that the time complexity required by an MLP to learn an arbitrary sparse Boolean function is governed by the largest "leap" in the staircase of its monomials, each of which is a sparse parity. (Tllarskyy (2022) gives margin-based analysis of gradient flow on a two-layer neural network that achieves improved sample complexity (Ó(n/e) for the 2-sparse parity problem, at the cost of exponential width.
They note computational-statiiie
Neural nets and axis-aligned tabular data. Decision tree ensembles such random forests 2016) remain more popular among practitioners than neural networks tabular data (Kaggle) 2021 despite many recent attempts to design special- ized deep learning methods (Borisov et al.) 2022). Some of these employ sparse networks (Yang)
(Breiman 2001) and XGBoost (Chen and Guestrin
et al. 2022b Lutz et al. 2022) similar to those considered in our theory and experiments.
We refer the reader to Appendix A for additional related work.
Background
2.1 Parities, and parity learning algorithms
light bulb controlled by k out of n. binary switches; each the l: influential switches can toggle the light bulb's 's state from any configuration. The task in parity learning is to identify the subset of k important switches, given access to m i.i.d. uniform samples of the state of all n switches. Formally, for any 1 k n and S C [n] such that |S| = k. the parity function Xs : {+1]" + +1 is
3

---

defined as (=(x) = es 24 The (n, k) -parity learning problem is to identify S from samples (xc ~ Unif([+1]" = Xs (z) i.e. output a classifier with 100% accuracy on this distribution, without prior knowledge of S.
This problem has a rich bistory theoretical computer science, information theory, and cryptography. There several pertinent ways to think about the fundamental role of parity learning:
Monomial basis elements: A k-sparse parity is a degree-k monomial, and thus the analogue of Fourier coefficient with "frequency" k in the harmonic analysis of Boolean functions O'DDneell 2014). Parities form an important basis for polynomial learning algorithms (e.g.
Andoni (2014)).
(ii) Computational hardness: There is widely conjectured compulational-statistttt gap for this problem (Applebaum et al., 2009. 2010), which has been proven in restricted models such as SQ (Kearns) 1998) and streaming (Kol al., 2017) algorithms. The statistical limit is ((log(number [number of possibilities for S)) = O log n samples, but the amount of computation needed (for an algorithm that can tolerate an ((1) fraction of noise) is believed to scale as (((ck) for some constant 0 i... there is significant improvement over trying all subsets.
(iii)
Feature learning: This setting captures the learning of a concept which depends jointly on multiple attributes of the inputs, where the lower-order interactions (i.e. correlations with degree-k' < k parities) give no information about S. Intuitively, samples from the sparse parity distribution look like random noise until the learner has identified the sparse interaction. This notion of feature learning complexity is also captured by the more general information exponent Ben Arous al. 2021).
2.2 Notation for neural networks
For single-output regression, a 2-layer multi-layer perceptron (MLP) is a function class, parameterized by matrix W Brxx, vectors v. b E IK" and scalar 3 E IR, defined by
7 xxz+o v o (Wxx + b) + B,
where a is an activation function, usually a scalar function applied identically to each input. For rows wi of W, the intermediate variables a (w, x + b.) are thought of as hidden layer activations or neurons. The number of parallel neurons is often called the width.
Theory
In this section we theoretically study the interactions between data, width, time, and luck the sparse parity problem. We begin by rehashing Statistical Query (SQ) lower bounds for parity learning in the context of brddee optimization, showing that without sufficient resources sparse parities cannot be learned. Then, we prove upper bounds showing that parity learning is possible with correctly scaling either width (keeping sample size small), sample size (keeping width small), or mixture of the two.
Statistical query algorithms. A seminal work by Kearns (9988) introduced the statistical query (SQ) algorithm framework, which provides a means of analyzing noise-tolerant algorithms. Unlike traditional learning algorithms, SQ algorithms lack access to individual examples but can instead make queries to SQ oracle, which responds with noisy estimates of the queries over the population. Notably, many common learning algorithms, including noisy variants gradient descent, can be implemented within this framework. While SQ learning offers robust guarantees for learning in the presence of noise, there exist certain problems that are learnable from examples but not efficiently learnable from statistical queries (Blum et al., [1994] 2003). One notable example of such problem is the parity learning problem, which possesses an SQ lower bound. This lower bound can be leveraged to demonstrate the computational hardness of learning parities with gradient- based algorithms (e.g.. et al. (2017)).
"Equivalently, parity can be represented a function of bit string à E (0, 1)", which computes the XOR of the influential subset of indices S: xs (bim.) = Biesbi

---

3.1 Lower bound: a multi-resource hardness frontier
We show a version of the SQ lower bound in this section. Assume we optimize some model hgg where 0 E IR' (i.e.. parameters). Let e be some loss function satisfying: f' ((...) (y)( for example, one can choose (z y) = 2 (v - o)². Fix some hypothesis h, target f. a sample S C [+1)" and distribution D over {= We denote the empirical loss by Ls(h, = [i| Σxes {(h(x), and the population loss by I.D (h. f) EXDD [e(h(x), [x))] We consider SGD updates of the form:
0e+1 8, 7/ (Vo (Ls, (ho,, f) R(O,)) + Ez),
for some sample St, step size ?/. regularizer R(.), and adversarial noise & E [--,,]]". For normal- ization, we assume that [x)olx)] I for all 0 and x E X.
Denote by 0 the constant function, mapping all inputs to O. Let 8; be the following trajectory of SGD that is independent of the target. Define 02 recursively s.t. 0g = 0, and
+ : 7a Ve (Lo : 0) + R(#)))
Assumption (Bounded emror for gradient estimator). For all suppose that
V Ls, (ho; 0) VLD(ho; 0) T/2
Remark: If m = Ō Assumption is satisfied w.h.p. for: 1) St ~ Dm ("online" SGD), 2) S₁ S for some S ~~ th ("offliiee" GD) and 3) S, batch of size m sampled uniformly at random from S, where S ~ D'M and M 2 m ("offline" SGD). Indeed, in all these cases we have Es, [VLs, (ho: 0)] = (TDD(ho: ; 0), and the above follows from standard concentration bounds.
The lower bound in this section uses standard statistical query arguments to show that gradient-based algorithms, without sufficient resources, will fail learn (n, k:a-aariis We therefore start by stating the four types of resources that impact learnability:
The number of parameters r re-uivaalently the number of parallel "queries".
The number of gradient updates T i.e. the serial running time of the training algorithm.
The gradient precision T- i.c. how close the empirical gradient is to the population gradient. As discussed above, Ö(1/7)) samples suffice to obtain such an estimator.
The probability of success 6.
The following theorem ties these four resources together, showing that without a sufficient allocation of these resources, gradient descent will fail to learn:
Proposition 3. Assume that Og is randomly drawn from some distribution. For every r, T, 8, if rT
7og < (1). then there exists some (n, k)-parity s.t. with probability at least - å over the choice of fo the first T iterates of SGD are statistically independent of the vargetfunctio
The proof follows standard SQ lower bound arguments (Kearns) 1998 Feldman 2008), and for completeness is given in Appendix B The core idea of the proof is the observation that any gradient step has very little correlation (roughly n -k with most sparse-parity functions, and so there exists a parity function that has small correlation with all steps. In this case, the noise can force the gradient ...,. iterates to follow the trajectory ...... 87, which is independent of the true target. We note that, while the focus of this paper is sparse parities, similar analysis applies for broader class of functions that are characterized by large SQ dimension (see Blum et al. 1994)).
Observe that there are various ways for an algorithm to escape the lower bound of Theorem 3 We can scale a single resource with (*). keeping the rest small, e.g. by training a network of size n² or using a sample size of size = Crucially, we note the possibility of interpolating between these extremes: one can spread this homogenized "cost" across multiple resources, by (e.g.) training network of size k/2 using h/2 samples. In the next section, we show how neural networks can be tailored to solve the task in these interpolated resource scaling regimes.
We use the notation Ô to hide logarithmic factors.
5

---

3.2 Upper bounds: many ways to frade off the terms
As warmup, we discuss some simple SQ algorithms that succeed in learning parities by properly scaling the different resources. First, consider deterministic exhaustive search, which computes the error of all possible (n, k) --parittsss choosing the one with smallest error. This can be done with constant 7 (thus, sample complexity logarithmic in n), but takes T (n²* time. Since querying different parities can be done in parallel, we can reduce the number of steps I' by increasing the number of parallel queries r. Alternatively, is possible to query only randomly selected subset of parities, which reduces the overall number of queries but increases the probability of failure.
The above algorithms give rough understanding of the frontier of algorithms that succeed at learning parities. However, at first glance, they do not seem to reflect algorithms used in deep learning, and specialized to the parity problem. In this section, we will explore the ability of neural networks to achieve similar tradeoffs between the different resources. In particular, we focus on the interaction between sample complexity and network size, establishing learning guarantees with interpolatable mixtures of these resources.
Before introducing our main positive theoretical results, we discuss some prior theoretical results on learning with neural networks, and their limitations in the context of learning parities. Positive results learning with neural networks can generally be classified into two categories: those that reduce the problem to convex learning of linear predictors over a predefined set of features (e.g. the NTK), and those that involve neural networks departing from the kernel regime by modifying the fixed features of the initialization, known as the feature learning regime.
Kernel regime. When neural networks trained with gradient descent stay close to their initial weights, optimization behaves like kernel regression on the neural tangent kernel (Jacot et al. 2018 Du et al. 2018): the resulting function is approximately of the form + (v)(x), w), where + is a data-indeeendee infinite-dimensional embedding of the input, and w is some weighting of the features. However, it has been shown that the NTK (more generally, any fixed kernel) cannot achieve low Eg error on the (n, -)-partty problem. unless the sample complexity grows as 2(n²*) ) (see Kamath matter how we scale the network size or training time, neural networks
ct al. )) Thus, trained in the NTT regime cannot learn parities with low sample complexity, and thus do not enjoy the flexibility of resource allocation discussed above.
Feature learning regime. Due to the limitation of neural networks trained in the kernel regime, some works study learning in the "rich" regime, quantifying how hidden-layer features adapt to the data. Among these, Barak et al. 2022) analyze a feature learning mechanism requiring exceptionally small network width: SGD on 2- 2-layer MLPs can solve the online sparse parity learning problem with network width independent of n (dependent only on k), at the expense of requiring a suboptimal (<s n²) number of examples. This mechanism is Fourier gap amplification, by which SGD through a single neuron a ow x) can perform feature selection in this setting, via exploiting a small gap between the relevant and irrelevant coordinates in the population gradient. The proof of Theorem 4 below relies on similar analysis, extended to the offline regime (i.e., multiple passes over a dataset of limited size).
3.2.1 "Data x model size" success frontier for -inttall-ni MLPs
In this section, we analyze a 2-layer MLP with ReLU (a = max(0, x)) activation, trained with batch ("offline") gradient-descem over sample S with &g fy-regularized updates
g(++1) = (1 - X0))0(0 - " (hgu))))
We allow learning rates and weight decay coefficients À to differ between layers and iterations. For simplicity, we analyze the case where no additional noise added to each update; however, we believe that similar results can be obtained in the noisy case (c.g., using the techniques in Feldman et al. (017)). Finally, we focus on ReLU networks with s-sparse initialization of the first layer: every weight w; has s randomly chosen coordinates set to 1, and the rest set to O. Note that after initialization, all of the network's 's weights are allowed to move, so sparsity is not necessarily preserved during training.
For simplicity. we do not assume ad adversarial noise in the gradients as in the lower bound. However, similar results can be shown under bounded noise.

---

Over-sparse initialization (s > ((k)), The following theorem demonstrates a "data x width" success frontier when learning (n, k) parritiss with sparsely initialized ReLU MLPs sparsity levels > ((kk).
Theorem 4. Let k be an even integer, and E (0,1/2). Assume that n 2 (11/c2). For constants
C1 C2 Ca, Ca depending only on k. choose the following: (1) sparsity level: 8 2 c1/c. for some odd s, (2) width of the network: r = (2(n/s)* (3) sample size: m 2 cg(8/k){=1nn² log n. and (4) number of iterations: T 2 ca/e.. Then, for every (n, k) k)-parity distribution D, with probability at least 0.99 over the random samples and initialization, gradient descent with these parameter settings returns function bT s.t. LD(hr)= S.
Intuitively, by varying the sparsity parameter in Theorem we obtain a family of algorithms which smoothly interpolate between the small-datallarge-iinnn
and large-data/small width regimes of tractability. First, consider a sparsity level linear in 72 (i.e. 8 = a - n1). In this case, a small network (with width independent of the input dimension) is sufficient for solving the problem, but the sample size must be large (12nn++))) I)) for successful learning: this recovers the result of Barak et al. (2022), At the other extreme. if the sparsity is independent of n. the sample complexity grows only as On log n. but the requisite width becomes s((n)).
Proof sketch. The proof of Theorem 4 rellees on establishing Fourier anti-concentration condition, separating the relevant (i.e. indices in S) and irrelevant weights in the initial population gradient, similarly as the main result in Barak et al. (2022). When we initialize an s-sparse neuron, there is probability of 2 (s/n)* that the subset of activated weights contains the "correct" subset S. In this case, to detect the subset via the Fourier gap, it is sufficient to observe sk-1 examples instead of n =-i Initializing the neurons more sparsely makes it less probable to draw a lucky neuron, but once we draw a lucky neuron, it requires fewer samples to find the right features. Thus, increasing the width reduces overall sample complexity, by sampling a large number of "lottery tickets".
Under-sparse initialization (s < k). The sparsity parameter modulate similar data vs. width tradeoffss for feature learning in the "under-sparse" regime. We provide partial analysis for this more challenging case, showing that one step of gradient descent can recover a correct subnetwork. Appendix B.3 discusses the mathematical obstructions towards obtaining an end-to-end guarantee of global convergence.
Theorem 5. For even k, s, sparsity level s < k, network width r = ((n/k))"" and s-perturbed s-sparse random initialization scheme s.I. for every (n, k)-parity distribution D, with probability at least 0.99 over the choice of sample and initialization after one step of batch gradient descent (with gradient clipping) with sample size m = (((n/k))===> and appropriate learning rate, there is subnetwork in the ReLU MLP that approximately computes the parity function.
Here, the sample complexity can be improved by a factor of nz" at the cost of requiring the width to be n² times larger. The proof of Theorem reliee on a novel analysis of improved Fourier gaps with "partial progress": intuitively, if neuron randomly initialized with subset of the relevant indices S, it only needs to identify A - s more coordinates, inheriting the improved sample complexity for the (n s. k- - s) s)-parity problem. Note that the probability of finding such lucky neuron scales as (n/k) ", which governs how wide (number of lottery tickets) the network needs to be.
Remarks on the exact-sparsity regime. Our theoretical analyses do not extend straightforwardly to the case of s O(k). Observe that if the value of l is known, initializing a network of size = 0 with sparsity & = k gives w.h.p. a subnetwork with good first-layer features at initialization. We believe that with a proper choice of regularization and training scheme, it is possible to show that such a network learns to select this subnetwork with low sample complexity. We leave the exact details of this construction and end-to-end proofs for future work.
Analogous results for dense initialization schemes? We believe that the principle of "parallel search with randomized per-subnetwork sample complexities" extends to other initialization schemes
"We note that the additional n² factor in the sample complexity can be removed if we apply gradient in the small-sample case.
truncation, thus allowing only logarithmic dependence
'For ease of analysis, we use a close variant of the sparse initialization scheme: s coordinates out of the n coordinates are chosen randomly and set to 1, and the rest of the coordinates are set to < (n - -))-+ s)_ Without the small norm dense component in the initialization, the population gradient will be 0 initialization.
7

---

Computation width+init
Empirical stalistical threshold width+init
n=1d0 k-1 denne mt!
Iw110 led, denne It!
modday # hor Horratinn 10 convora www.rrgeecoo 120
fraction commangee
MLP WERR
1291 vil
250 1291
100 kod sparse FI1
Toe kod, 503152 V91
100 km3 sparse Ht
120
1+22000
/M000
190 301
1291 302 151 1999
1900 3000 1293 2011 N00 1999
227
Ilinear
dataset (log stale!
Figure 2: Zoomed-in views of the interactions between width, data, time, and luck. Left: Locations of these runs the larger parameter space. Center: Success probability vs. dataset size. In accordance with our theory, width buys luck, and improves end-to-end sample efficiency, despite increasing the network's capacity. Right: Number of iterations to convergence vs. dataset size. We observe data time tradeoff in the grokking regime (at the edge of feasibility). as well as "sample- wise double descent" performance drop with more data (which can also be seen in Figure and disappears with larger widths). Comparing dense vs. sparse initializations (upper vs. lower plots; sparse inits are colored more brightly). we see computational and statistical benefits of the sparse initialization scheme from Section
(including those more commonly used in practice), and leads to analogous success frontiers. To support this, our experiments investigate both sparse and uniform initialization, with qualitatively similar findings. For dense initializations, the mathematical challenge lies in analyzing the Fourier anti-concentration of general halfspaces (see the discussion and experiments in Appendix C.1 of (Barak et al., 2.222). The axis-aligned inductive biases imparted by sparse initialization may also be of independent practical interest.
4 Experiments
A high-level takeaway from Section 3 is that when a learning problem is computationally difficult but statistically easy, a complex frontier of resource tradeoffs can emerge; moreover, it is possible to interpolate between extremes along this frontier using ubiquitous algorithmic choices in deep learning, such as overparameterrizaton,, random initialization, and weight decay. In this section, we explore the nature of the frontier with empirical lens-first with end-to-end sparse parity learning, then with natural tabular datasets.
4.1 Empirical Pareto frontiers for offline sparse parity learning
We launch large-scale (~200K GPU training runs) exploration of resource tradeoff's when training neural networks to solve the offline sparse parity problem. While Section B analyzes idcalized variants of SGD on MLPs which interpolate along the problem's resource tradeoff frontier, in this section ask whether the same can be observed end-to-end with standard training and regularization.
On various instances of the (n, -spsars parity leamingg problem, we train 2-layer MLP with identical hyperparameters, varying the network width E (10, 30, 100, .., 100} and the dataset size m E (100, 200, 300, 600, 1000, .... 10%). Alongside standard algorithmic choices, we consider one non non-standard augmentation of SGD: the under-sparse initialization scheme from Section 3.2.1 we have proven that these give rise to "lottery ticket" neurons which learn the influential coordinates more samplc-efficiently. [iguree[(nn the introduction) and Figure Sequreeilluterrr illustrate our findings at a high level; details and additional discussion in Appendix C.I We list our key findings below:
(1) A "success frontier": large width can compensate for small datasets. We observe conver- gence and perfect generalization when m < nt. In such regimes, which are far outside the
8

---

online setting considered by Barak et al. (2022), high- probbbbbbbyiltty sample-efficient learning is enabled by large width. This can be seen in Figure (left), and analogous plots in Appendix [C.]]
(2) Width is monotonically beneficial, and buys data, time, and luck. In this setting, increasing the model size yields exclusively positive effects on success probability, sample efficiency, and the number of serial steps to convergence (see Figure 2) This is striking example where end-to-end generalization behavior runs opposite to uniform convergence- upper bounds, which predict that enlarging the model's capacity worsens generalization.
(3) Sparse axis-aligned initialization buys data, time, and luck. Used in conjunction with wide network, we observe that a sparse, axis-aligned initialization scheme yields strong improvements on all of these axes; see Figure (bottom row). In smaller hyperparameter sweeps, we find that (i.e. initialize every hidden-layed neuron with a random 2-hot weight vector) works best.
(4) Intriguing effects of dataset size. As we vary the sample size m, we note two interesting phenomena; see Figure 2 (right). The first is grokking (Power et al. 2022), which has been previously documented in this setting (Barak et al.) [022] Merrill al. [2023). This entails data vs. time tradeoff: for small m where learning is marginally feasible, optimization requires significantly more training iterations T. Our second observation is "sample-wise double descent" (Nakkiran el al. 202T); success probability and convergence times can worsen with increasing data. Both of these effects are also evident in Figure
Lottery ticket neurons. The above findings are consistent with the viewpoint taken by the theoret- ical analysis, where randomly-initializze SGD plays the role of parallel search, and a large width increases the number of random subnetworks available for this process-in particular, the "winning lottery ticket" neurons, for which feature learning occurs more sample-efficienll. To provide further evidence that sparse subnetworks are responsible for learning the parities, we perform a smaller-scale study of network prunability in Appendix C.2.
4.2 Sample-efficient deep learning on natural tabular datasets
Sparse parity learning is a toy problem, in that it is defined by an idcalized distribution, averting the ambiguities inherent in reasoning about real-life datasets. However, due to its provable hardness (Theorem 3, as well as the discussion in Section 2. . it is a maximally hard toy problem in a rigorous sense 0 In this section, we perform preliminary investigation of how the empirical and algorithmic insights gleaned from Section 4.1 can be transferred to more realistic learning scenarios.
To this end, we use the benchmark assembled by Grinsztajn et al. (2022). work which specifically investigates the performance gap between neural networks and tree- rese classifiers (e.g. random forests, gradient-booste trees), and includes a standardized suite of 16 classification benchmarks with numerical input features. The authors identify three common aspects of tabular tasks which present difficulties for neural networks, especially vanilla MLPs:
The feature spaces are not rotationally invariant. In state-of-ther oftte-of-the-art deep learning, ML.ss are often tasked with function representation in rotation-invarian domains (token embedding spaces, convolutional channels, etc.).
(ii) Many of the features are uninformative. In order to generalize effectively, especially from limited amount of data, it is essential to avoid overfitting to these features.
(ii) There are meaningful highhffrquenccynoo--mmoe bined with property (i), decision tree-based methods (which typically split on axis-aligned features) can appear to have the ideal inductive bias for tabular modalities of data.
patterns in the target function. Com-
Noting that the sparse parity task possesses all three of the above qualities, we conduct a preliminary investigation on whether our empirical findings in the synthetic case carry over to natural tabular data, In order to study the impact of algorithmic choices (mainly width and sparse initialization) on sample efficiency, we create low-data problem instances by subsampling varying fractions of each dataset for training. Figure 3 provides a selection of our results. We note the following empirical findings, which are the tabular data counterparts of results (2) and (3) in Section 4.1
Namely, its SQ dimension is equal to the number hypotheses. which what leads to Theorem 3 "Tabular data" refers to the satch-all term for data sources where each coordinate has a distinct semantic meaning which is consistent across points.

---

MLPs (varying width init sparsity) on tabular data
denee m=120
Ta
dence rw350
Garee nt: re1280
Lost arror (nwedan 100 rursal
denne
dase re12000
epares 1-00
12
18
121
121
20
searse (e2t0)
szarse Inll r=2003
searse re-100
sparaa r=10022
abore/eebww
Laal ML*
[GOV22) bont MLF
JooNzel bust
fraction
Figure 3: Analogous investigation MLP width and sparse initialization for real-world tabular datasets (OpenML benchmarks assembled by Grinsztajn et al. (2022)), varying the dataset size via downsampling. Large width and sparse initialization tend to improve generalization, in accordance with the theory and experiments for synthetic parity tasks. In some settings, our best MLPs outperform tuned random forests. Dotted lines denote the test errors reported by Grinsztajn et al. (022) of tuned MLPs and RFs on the full datasets. Full results all 16 tasks are in Appendix C.3
(2T) Wide networks generalize on small tabular datasets. Like in the synthetic experiments, width yields nearly monotonic end-to-end benefits for learning. This suggests that the "parallel search + pruning" mechanisms analyzed in our paper are also at play these settings. In some (but not all) cases, these MLPs perform competitively with tuned tree-based classifiers.
(3T) Sparse axis-aligned initialization sometimes improves end-to-end performance. This effect is especially pronounced on datasets which are downsampled be orders of magnitude smaller. We believe that this class of drop-in replacements for standard initialization merits further investigation, and may contribute closing the remaining performance gap between deep learning and tree ensembles on small tabular datasets.
5 Conclusion
We have presented a theoretical and empirical study of offline sparse parity learning with neural networks; this is a provably hard problem which admits a multi-resource lower bound in the SQ model. We have shown that the lower bound can be surmounted using varied mixtures of these resources, which correspond to natural algorithmic choices and scaling axes in deep learning. By investigating how these choices influence the empirical "success frontier" for this hard synthetic problem, we have arrived at some promising improvements for MLP models of tabular data (namely, large width and sparse initialization). These preliminary experiments suggest that more intensive, exhaustive study of algorithmic improvements for MLPs on tabular data has a chance of reaping significant rewards, perhaps even surpassing the performance of decision tree ensembles.
Broader impacts and limitations. The nature of this work is foundational; the aim of our theoretical and empirical investigations is contribute the fundamental understanding of neural feature learning, and the influences of scaling relevant resources. A key limitation is that our benchmarks on tabular data are only preliminary; a significant and perennial methodological challenge to devise fair and comprehensive comparisons between neural networks and tree-based learning paradigms.
Acknowledgements
We are grateful to Boaz Barak for helpful discussions and Matthew Salganik for helpful comments on draft version. This work has been made possible in part by gift from the Chan Zuckerberg Initiative Foundation to establish the Kempner Institute for Study of Natural and Artificial Intelligence. Sham Kakade acknowledges funding from the Office of Naval Research under award N00014-22-1-2377.. Ben Edelman acknowledges funding from the National Science Foundation Graduate Research Fellowship Program under award #DGE 2140743.
10

---

References
Abbe, E., Adsera, E. B., and Misiakiewicz, T. (2022). The merged-stairease property: a necessary and nearly sufficient condition for sgd learning of sparse functions two-layer neural networks. In Conference on Learning Theory, pages 4782-4887. PMLR.
Abbe, E., Boix-Adsera, E., and Misiakiewicz, T. (2023). Sgd learning neural networks: leap complexity and saddle-to-sadee dynamics. arXiv preprint arXiv:2302.1105:
Andoni, A., Panigrahy, R., Valiant, G., and Zhang, L. (2014). Learning polynomials with neural networks, In International Conference on Machine Learning, pages 1908-1916. PMLR.
Applebaum, B., Barak, B., and Wigderson, A. (2010). Public-key cryptography from different assumptions. In Proceedings of the forty-second ACM symposium on Theory of computing, pages 171-180.
Applehaum, B., Cash, D., Peikert, C., and Sahai, A. (2009). Fast cryptographic primitives and circular-secure encryption based on hard learning problems. In Anmual International Cryptology Conference, pages 998. Springer.
Ba, J., Erdogdu, M. A., Suzuki, T., Wang, Z., Wu, D., and Yang, G. (2022). High-dimensional asymptoties of feature learning: How one gradient step improves the representation. Advances in Neural Information Processing Systems, 35:37932-37944
Bachmann, G., Anagnostidis, S., and Hofmann, (2023). Scaling mips: tale of inductive bias. arXiv preprint arXiv:2306.13575.
Bahri, Y., Dyer, E., Kaplan, J., Lee, J., and Sharma, U. (2021). Explaining neural scaling laws. arXiv preprint arxiv:2
Barak, B., Edelman, B., Goel, S., Kakade, S., Malach, E., and Zhang, C. (2022). Hidden progress in deep learning: Sgd learns parities near the computational limit. Advances in Neural Information Processing Systems, 35:21750-21764.
Ben Arous, G., Gheissari, R., and Jagannath, A. (2021). Online stochastic gradient descent on non-convex losses from high-dimensional inference. The Journal of Machine Learning Research, 22(1):4788-45) 4838.
Bietti, A., Bruna, J., Sanford, C., and Song. M. (2022). Learning singlc-index models with shallow neural networks. Advances in Neural Information Processing Systems, 35:9768-9783.
Blum, A., Furst, M., Jackson, J., Kearns, M., Mansour, Y., and Rudich, S. (1994). Weakly learning dnf and characterizing statistical query learning using fourier analysis. In Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, pages 253-262.
Blum, A., Kalai, A., and Wasserman, H. (2003). Noise-tolerant learning, the parity problem, and the statistical query model. Journal of the ACM (JACM), 50(4):506-519
Borisov, V., Leemann, T., Seßler, K., Haug, J.. Pawelczyk, M., and Kasneci, G. (2022). Deep neural networks and tabular data: A survey, IEEE Transactions on Neural Networks and Learning Systems.
Breiman, L.. (2001). Random forests. Machine learning, 45:5-32.
Chen, S. and Meka, R. (2020). Learning polynomials in few relevant dimensions. In Conference Learning Theory, pages 1161-1227. PMLR.
Chen, T. and Guestrin, C. (2016). Xgboost: A scalable tree boosting system. In Proceedings of the 22nd aem sigkdd international conference on knowledge discovery and data mining, pages 785-794.
Chizat, L., Oyallon, E., and Bach, F. (2019). On lazy training in differentiable programming. Advances in neural information processing systems, 32.

---

Damian, A., Lee, J., and Soltanolkotabi, M. (2022). Neural networks can learn representations with gradient descent. In Conference on Learning Theory, pages 5413-5452. PMLR.
Damian, A., Nichani, E., Ge, R., and Lee, J. D. (2023). Smoothing the landscape boosts the signal for sgd: Optimal sample complexity for learning single index models. arXiv preprini arXiv:2305.1063::
Daniely, A. and Malach, E. (2020). Learning parities with neural networks. Advances in Neural Information Processing Systems, 33:20356-20365.
Dosovitskiy, A., Beyer, L., Kolesnikov, A., Weissenborn, D., Zhai, X., Unterthiner, T., Dehghani, M., Minderer, M., Heigold, G., Gelly, S., et al. (2020). An image is worth 16x16 words: Transformers for image recognition scale. arXiv preprint arXh::2010.11929
Du, S., Zhai, X., Poczos, B., and Singh, A. (2018). Gradient descent provably optimizes over- parameterized neural networks. arXiv preprini arXiv:/810.022) 1810.02054
Feldman, V. (2008). Evolvability from learning algorithms. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 619-628.
Feldman, V., Guzman, C., and Vempala, (2017). Statistical query algorithms for mean vector estimation and stochastic convex optimization. In Proceedings of the Twenty-Lighth Annual ACM-SIAM Symposium Discrete Algorithms, pages 1265-1277 SIAM.
Frankle, J. and Carbin, M. (2018). The lottery ticket hypothesis: Finding sparse, trainable neural networks. arXiv preprint 1803.0333
Frei, S., Chatterji, N. S., and Bartlett, L. (2022). Random feature amplification: Feature learning and generalization in neural networks. arXiv preprint arXiv:2202.07626
Gorishniy, Y., Rubachev, I., Khrulkov, V., and Babenko, A. (2021). Revisiting deep learning models for tabular data. Advances in Neural Information Processing Systems, 34:18932-18943
Grinsztajn, L., Oyallon, E., and Varoquaux, G. (2022). Why do tree-based models still outperform deep learning on typical tabular data? In Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., and Oh, A., editors, Advances in Neural Information Processing Systems, volume 35, pages 507-520. Curran Associates, Inc.
Hahn, M. (2020). Theoretical limitations of self-attention in neural sequence models. Transactions of the Association for Computational Linguistics, 8:156-171.
Henighan, T., Kaplan, J., Katz, M., Chen, M., Hesse, C., Jackson, Jun, H., Brown, T. B., Dhariwal, P., Gray, S., et al. (2020). Scaling laws for autoregressive generative modeling. arXiv preprint arXiv:2010.14: 14701..
Hoffmann, J., Borgeaud, S., Mensch, A., Buchatskaya, E., Cai, T., Rutherford, E., Casas, D. d. L., Hendricks, L. A., Welbl, J., Clark, A., et al. (2022). Training compute-optimal large language models. Xiviv preprint arXhv:2203.15556.
Hutter, M. (2021). Learning curve theory. arXiv preprint arXiv:2102.04074.
Jacot, A., Gabriel, and Hongler, (2018). Neural tangent kernel:
Convergence and generalization in neural networks. Advances in neural information processing systems, 31.
Kaggle (2021). State of data science and machine learning 2021.
Kamath, P., Montasser, O., and Srebro, N. (2020), Approximate is good enough: Probabilistic variants of dimensional and margin complexity. In Conference Learning Theory, pages PMLR.
Kaplan, J., McCandlish, S., Henighan, T., Brown, T. B., Chess, B., Child, R., Gray, S., Radford, A., Wu, J., and Amodei, D. (2020). Scaling laws for neural language models. arXiv preprint 2rXiv:2001.08361.
12

---

Kearns, M. (1998). Efficient noise-tolerant learning from statistical queries. Journal of the ACM (JACM), 45(6))933-1066
Kol, G., Raz, R., and Tal, A. (2017). Time-space hardness of learning sparse parities. Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 1067-1080.
Liu, Z., Michaud, E. J., and Tegmark, M. (2022). Omnigrok: Grokking beyond algorithmic data. arXiv preprint 2rXiv:2210.01111
Lutz, P., Amould, L., Boyer, C., and Scornet, (2022). Sparse tree-based initialization for neural networks. arXiv preprint arXi::2009.12283.
Malach, E., Kamath, P., Abbe, E., and Srebro, N. (2021). Quantifying the benefit of using differ- entiable learning over tangent kernels. In International Conference on Machine Learning, pages 7379. PMLR.
Merrill, W., Tsilivis, N., and Shukla, A. (2023). A tale of two circuits: Grokking as competition of sparse and dense subnetworks. arXiv preprint arXiv:2303. 1873.
Michaud, E. J., Liu, Z., Girit, U., and Tegmark, M. (2023). The quantization model of neural scaling, arXiv preprint arXiv:2303.
Minsky, M. and Papert, S. (1969). Perceptrons: an introduction to computational geometry. MIT Press.
Nakkiran, P. Kaplun, G., Bansal, Y., Yang, T., Barak, B., and Sutskever, (2021). Deep double descent: Where bigger models and more data hurt. Journal of Statistical Mechanics: Theory and Experiment, 2121(12)
O' O'Donnell, R. (2014). Analysis of Boolean functions. Cambridge University Press.
Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J.. Chanan, G., Killeen, T., Lin, Z., Gimelshein, N.. Antiga, L., Desmaison, A., Kopf, A., Yang. E., De Z., Raison, M., Tejani, A., Chilamkurthy, S., Steiner, B., Fang. L., Bai, J., and Chintala, S. (2019). PyTorch: An imperative style, high- performance deep learning library. In Wallach, H., Larochelle, H., Beygelzimer, A., d'Alché-Bun Buc, F., Fox, E., and Garnett, R., editors, Advances Neural Information Processing Systems 32, pages 8024 8035. Curran Associates, Inc.
Pedregosa, F,, Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhoferr, P., Weiss, R., Dubourg, V., Vanderplas, J., Passos, A., Cournapeau, D., Brucher, M., Perrot, M., and Duchesmay, F. (2011). Seikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2830.
Power, A., Burda, Y., Edwards, H., Babuschkin, I., and Misra, (2022). Grokking: Generalization beyond overfitting small algorithmic datasets. arXiv preprini arXivv2201.02177
Rosen-Zvi, M., Klein, E., Kanter, I., and Kinzel, W. (2002). Mutual learning in tree parity machine and its application to cryptography. Physical Review E, 66(6):066135.
Shalev-Shwartz, S. and Ben-David, (2014). Understanding machine learning: From theory to algorithms. Cambridge university press.
Shalev-Shwartz. S., Shamir, O., and Shammah, S. (2017). Failures of gradient-based deep learning.
In International Conference on Machine Learning, pages 3067-3075. PMLR.
Shamir, O. and Zhang, (2013). Stochastic gradient descent for smothh optimization: Conver- gence results and optimal averaging schemes. In International conference machine learning, pages 71-79. PMLR.
Shi, Z.., Wei, J., and Liang. Y. (2021). A theoretical analysis on feature learning in neural networks: Emergence from inputs and advantage over fixed features. In International Conference Learning Representations.
Telgarsky, M. (2022). Feature selection with gradient descent on two-layer networks low-rotation regimes, arXiv preprint arXiv:2208.091 2208.0278.
13

---

Tolstikhin, I. O., Houlsby, N., Kolesnikov, A., Beyer, L., Zhai, X., Unterthiner, T., Yung, J., Steiner, A.. Keysers, D., Uszkoreit, J., et (2021). MLP-Mixer: An all-MLP architecture for vision. Advances in neural information processing systems, 34:24261-24272.
Wei, C., Lee, J. D., Liu, Q. and Ma, T. (2019). Regularization matters: Generalization and optimization of neural nets vs their induced kernel. Advances in Neural Information Processing Systems, 32.
Yang, G., Hu, J., Babuschinn,, I., Sidor, S., Liu, X., Farhi, D., Ryder, N., Pachocki, J., Chen, W., and Gao, J. (2022a). Tensor programs v: Tuning large neural networks via zero-shot hyperparameter transfer. arXiv preprint arXiv:2203.03466
Yang, Lindenbaum, O., and Kluger, (2022b). Locally sparse neural networks for tabular biomedical data. In International Conference on Machine Learning, pages
PMLR.
Zhai, X., Kolesnikov, A., Houlsby, N., and Beyer, L. (2022). Scaling vision transformers. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 12104-12113.
Zhenmei, S., Wei, J., and Liang, Y. (2022). A theoretical analysis on feature learning in neural networks: Emergence from inputs and advantage over fixed features, In International Conference Learning Representations.
14


Reviews:
[{"review_id": "X824Ts5Fe3", "reviewer": "Reviewer_XFsj", "summary": "In an attempt to explore the mechanisms behind generalization and training of neural networks and different elements that play a role in it,  this paper investigates the impact of four resources of training MLPs on the famous and well-studied (n, k)-parity learning problem. The authors conduct a massive grid of experiments to analyze the trade-offs between data, compute, width (model size) and luck (sparsity at initialization) when training MLPs on the mentioned problem. The experimental evaluation suggests existence of \"frontiers\" of resource trade-offs such that decrease any resource at the frontier would likely result in incomplete or non-existent generalization. They further theoretically analyze this frontier and prove that under the necessary assumptions, this frontier can be recovered (at least in the over-sparse initialization case) theoretically. Based on the observed patterns, the authors show that under correct combination of resources, neural networks are capable of achieving similar or in some cases superior performance than tree-based methods on small tabular tasks.", "questions": "I have mentioned my questions in the \"Weaknesses\" section.", "limitations": "The authors have discussed the limitations.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "* The diverse and large-scale experiments show clear patterns of existence of the trade-offs proposed by the authors, and provide thorough evaluation of different combinations of the four mentioned resources.\n* The theoretical results are supportive of the patterns present in the experiments and agree with the results from recent work.\n* Although the presented results may not seem novel, and arguably have been speculated before, a study that extensively studies the concept of \"success frontier\" was lacking.  \n* This work addresses an important aspect of using neural networks in practice: tabular data and suggests that further improvements can be made in applying neural networks on these kind of problems. This is in contrary to the popular belief that neural networks are inferior than tree-based models on these datasets.\n* The manuscript is well-presented, and to my knowledge, the authors have covered most related work and included necessary discussion and comparison with related work, which helps in conveying the importance of this setup and the findings.", "weaknesses": "I believe that this work has the potential to be very influential, but there are still some aspects that should be improved and some points that could be better justified.\n\n### Major concerns:\n* It's not clear if the study would apply to other problems or not. Hence, claiming that the results apply to \"deep feature learning in general\" sounds very exaggerated. It is definitely intuitive that the observed phenomena should extend to other problems to some extent, but we can't claim anything just based on intuition. For instance, it has been observed that width is not necessarily monotonically beneficial in all problems, and this could apply to other resources discussed in the paper as well. As a suggestion, a few ablation studies of smaller scale on other problems could be a better support for hypothesizing that the observations convey to other settings as well. \n* Section 3.1: Correct me if I'm getting this wrong, but based on Proposition 3 it seems like there \"exists\" settings in which SGD can't find the correct solution. If I'm right, this doesn't mean \"GD will fail\" at all, and it just means that GD is not guaranteed to converge. \n* In Theorem 4, setting error close to zero would result in $s \\to \\infty$, and $r \\to 0$. How is this possible? Isn't $r$ required to be at least as large as $s$? Could the authors clarify the setting of this theorem?\n* I'm not convinced about some references made to the lottery ticket hypothesis and \"good neurons\", and that width buys \"Luck\" in general. Although LTH could be a plausible explanation for the observations in the experiments, totally attributing the affect of width to LTH and \"good neurons\" would require thorough evidence, may it be theoretical or empirical.\n\n### Minor issues:\n* The authors have mentioned that they use bootsrapping for neural nets to solve the low-data problem. Have the authors used bootstrapping for other models that don't inherently perform it to have a fair comparison?\n* In theorem 5, and theorem 21 (the formal version), it is mentioned that the problem will be solved \"approximately\". Can the authors please clarify this approximation? ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thoughtful review. Here we address the main concerns raised by the reviewer.\n\n**(W1) “Deep feature learning” terminology**: (Copied from response to R3) Our intent for the shorthand “deep feature learning” in the title was to refer to gradient-based feature learning in neural networks, as opposed to the NTK regime. We understand the possible unintended interpretation of “deep” as “containing a many-layer hierarchy” (which we believe are currently clarified in the abstract and main body), and are considering minor adjustments to the title.\n\n**(W2) Quantifiers in Proposition 3**: Proposition 3 is phrased according to the standard convention in learning theory that learning a concept class requires probable success for all concepts in the class. The proof can easily be tweaked to show that the same result applies for a $1-\\epsilon$ fraction of all $(n,k)$-parities, if $\\frac{rT}{\\tau^2 \\delta} \\leq \\frac{\\epsilon}{2}\\binom{n}{k}$.\n\n**(W3) $\\epsilon$ in Theorem 4**: The statement of Theorem 4 only makes sense when $\\epsilon > c_1/\\sqrt{n}$, since sparsity $s$ cannot be greater than $n$. \n\n**(W4) Lottery ticket hypothesis**: We agree that our results and experiments establish that width buys “luck” in our specific setting, not necessarily in general. We will make the connection to LTH clearer in the revision. \n\n**(W5) Clarification on “bootstrapping”**: By “bootstrapping” the classification benchmark, we mean randomly downsampling the training data, inducing a distribution over harder supervised learning tasks. These smaller-sample tasks are not present in [GOV22]; hence, their reported numbers are only comparable with the rightmost points of the “error vs. sample size” curves. We will adjust the wording to minimize confusion.\n\n_[GOV22] Grinsztajn, Léo, Edouard Oyallon, and Gaël Varoquaux. \"Why do tree-based models still outperform deep learning on typical tabular data?.\" NeurIPS 2022._\n\n**(W6) Clarification on “approximate solution”**: As is standard in learning theory, approximation refers to the learned solution being $\\epsilon$-close in terms of error to the optimal solution."}, {"review_id": "WOPkOpsKVB", "reviewer": "Reviewer_T64v", "summary": "Disclaimer: My expertise in this domain is limited and understanding is highly superficial.\n\nThe manuscript presents a detailed take on addressing the tradeoffs on 4 axes, namely model size, dataset size, training epochs, and stochasticity. It offers a well-rounded analysis of the area and provides empirical and theoretical evidence for intuitive ideas, increasing network width leading to better sample efficiency. They use sparse parity learning as a proxy for real world feature learning problems which might be aligned on the above mentioned 4-axes. They also provide curious insights like the network width improves the possibility of “winning lottery ticket” neurons. The wide, sparsely initialized MLPs also outperform the very strong RFs.", "questions": "- See Weaknesses.\n- How is the work distinct from the previous works like [1], especially as theorem 4 seems like a trivial extension of informal theorems and analysis from [1]? A bit more formalization of the distinction would be helpful.\n- More comparisons on the nC2 combinations of data-width-time-luck would provide one-on-one insights on the interplay and could be a good addition to the work. Almost a matrix of sorts, highlighting the relationship between two axes and their effect overall on the network could summarize the findings well.\n\n[1] Barak, Boaz, et al. \"Hidden progress in deep learning: Sgd learns parities near the computational limit.\" Advances in Neural Information Processing Systems 35 (2022): 21750-21764.", "limitations": "N/A", "rating": 5, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Section 4.1 and C.1: The statements on interplay between width and dataset size for example are a good starting point for further focused research.\n- Section B: Detailed theoretical contributions in the supplementary section verify the experiments and intuition.\n- Highly exhaustive experiments, analyzing and investigating important questions.", "weaknesses": "- The paper, while having a good base, introduction and motivation, becomes hard to follow and the organization seems a bit unnatural. For example, in my opinion, moving the insight from Lines 823 to 853 to the main paper at the expense of the rather verbose Section 3.2, before the “actual” analysis starts in Line 223 might help pitch the paper better. \n- It’s not clear to me how this work is different from the rich vein of work in learning parities and providing a SQ learning bound. It might be worthwhile adding a section comparing against previous attempts and drawing focus to distinct contributions, or the work might seem incremental in several directions without making a significant difference in one direction.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the thoughtful comments and questions.\n\n**(W1) Paper organization**: Thanks for the feedback and suggestions. We will improve the presentation, and add intuitive overviews of the technical proofs.\n\n**(W2, Q2) Relation to other work on NN parity learning**: We have not seen following contributions in prior work on SQ parity learning with NNs: (1) a “success frontier”-- a parametric family of algorithms which trade off the heterogeneous resources of data & computation (2) experiments which corroborate these tradeoffs. We will add a more detailed quantitative comparison to Appendix A.1. The main points are below:\n- [BEGKMZ22] shows that one step of gradient descent on a single neuron is able to recover the indices corresponding to the parity with $n^{O(k)}$ samples/computation. The present work expands on this with the following: (1) extends consideration to the finite-sample setting, not just online learning, where the heterogeneous resource tradeoff frontier arises; (2) shows how increasing width improves sample efficiency; (3) introduces sparsity of initialization as a hyperparameter, which has interplay with width & sample-efficiency.\n- [ABM23] improves this bound to $O(n^{k-1})$ online SGD steps and generalizes the result to handle hierarchical staircases of parity functions which requires a multi-step analysis. \n- [Telgarsky23] studies the problem of 2-sparse parities with two-layer neural networks trained with vanilla SGD (unlike our restricted two-step training algorithm) and studies the margins achieved post training. They use the margins to get optimal sample complexity $\\tilde{O}(n^2/\\epsilon)$ in the NTK regime. Going beyond NTK, they analyze gradient flow (with certain additional modifications) on an exponentially ($n^n$) wide 2-layer network (making it computationally inefficient) to get the improved sample complexity of $\\tilde{O}(n/\\epsilon)$. \nIn contrast to these works, our theoretical contribution (Theorem 4) highlights the improvement in sample complexity while maintaining computational efficiency which we achieve using the sparse initialization.\n\n_[BEGKMZ22] Boaz Barak, Benjamin Edelman, Surbhi Goel, Sham Kakade, Eran Malach, and Cyril Zhang. \"Hidden progress in deep learning: Sgd learns parities near the computational limit.\" Advances in Neural Information Processing Systems 35 (2022): 21750-21764._\n\n_[ABM23] Emmanuel Abbe, Enric Boix-Adserà, and Theodor Misiakiewicz. SGD learning on neural networks: leap complexity and saddle-to-saddle dynamics. COLT 2023._\n\n_[Telgarsky23] Matus Telgarsky. Feature selection and low test error in shallow low-rotation ReLU networks. ICLR 2023._\n\n**(Q3) Additional pairwise tradeoffs**: We will attempt to provide further visualizations to elucidate the “${n \\choose 2}$ grid” of pairwise resource tradeoffs in the revision. There are some methodological considerations (high sensitivity to the choice of accuracy threshold; effect of optimizer hyperparameters and initialization scales on the precise convergence time, …) which make some of these comparisons hard to make quantitatively."}, {"review_id": "GZH44HqSRW", "reviewer": "Reviewer_qvgd", "summary": "In this paper, the authors study the tradeoff between various resources in feature learning---data, compute, width. The authors focus on the fundamental problem of learning parity functions using a two-layer MLP. The degree $k$ of a parity function of $n$ variables controls the hardness of the problem: generally a bigger $k$ means more difficult. Learning parity function is a fundamental problem which has been used to study deep learning in the literature. The authors consider learning $(n,k)$-parities using gradient descent (GD) sparsely initialized at sparsity level $s$.\n\nThe first main result shows that if $s > k$ (over-sparse initialization), then there is a tradeoff between network width $r$ and sample size $m$ required to learn a $(n,k)$-parity with high probability. This result interpolates existing feature-learning results as far as I know. The second main result shows that if $s<k$ (under-sparse initialization), there is a similar width vs. sample size tradeoff for one-step GD.\n\nExtensive simulations and experiments on natural tabular datasets are presented to complement the theory.\n", "questions": "I am curious (1) if the authors could comment on the role of depth in neural networks, and (2) how do the results connect to the staircase phenomenon?", "limitations": "NA", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "I find this paper impressive and enjoyable to read. Understanding the tradeoff of different resources (time, memory, data) is important for large-scale machine learning. Focusing on the fundamental problem of learning parity functions, the authors present solid theoretical results. I think both theoretical and empirical contributions are significant.\n\nThe theory also provides perspectives for the lottery ticket hypothesis, by showing that a large width is beneficial for finding the right \"lottery ticket\".\n\nThe writing is very clear. High-level ideas are well explained and figures are easy to understand.", "weaknesses": "I cannot evaluate the technical novelty of this paper as I do not claim expertise in learning parity functions, while some of the analytical strategies seem to be based on existing papers.\n\nOne minor comment is that theory is established for shallow networks, and it cannot reflect \"Deep Feature Learning\" in the title.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive feedback.\n\n**(W1) “Deep feature learning” terminology**: Our intent for the shorthand “deep feature learning” in the title was to refer to gradient-based feature learning in neural networks, as opposed to the NTK regime. We understand the possible unintended interpretation of “deep” as “containing a many-layer hierarchy” (which we believe are currently clarified in the abstract and main body), and are considering minor adjustments to the title.\n\n**(Q1) Role of depth**: How depth $>2$ changes the picture sketched in this paper is non-obvious due to the entanglements with optimization, and is an excellent direction for future work especially for tasks that (unlike the parity function) have hierarchical structure. For our paper, we focused on depth-2 because it is more tractable to analyze but still not well-understood, and the number of hyperparameter knobs we analyzed was expansive even without adding depth.\n\n**(Q2) Relation to staircase phenomenon**: Compared to the original staircase paper [ABBBN21]  where each staircase added a single variable, the sample/runtime is already polynomial in $n$ therefore this trade-off is not super interesting. In the more recent paper [ABM23] which quantifies the leap complexity, we speculate that the finite-sample tradeoffs we describe may apply to each leap in a staircase. This could be an interesting subject for future work.\n\n_[ABBBN21] Emmanuel Abbe, Enric Boix-Adsera, Matthew S. Brennan, Guy Bresler, and Dheeraj Nagaraj. The staircase property: How hierarchical structure can guide deep learning. NeurIPS 2021._\n\n_[ABM23] Emmanuel Abbe, Enric Boix-Adserà, and Theodor Misiakiewicz. SGD learning on neural networks: leap complexity and saddle-to-saddle dynamics. COLT 2023._"}, {"review_id": "DXHqOrLALU", "reviewer": "Reviewer_9731", "summary": "This paper considers learning parity functions with neural networks and particularly studies the tradeoff between size of the network and the sample size. The paper also explore a connection between the network size the lottery ticket hypothesis. The neural network studied in this paper has a sparse, specific, and symmetric structure. One step gradient arguments under the hinge loss have been used for the training. Finally, the paper proposes a promising direction for processing tabular datasets using neural networks. ", "questions": "The setting considered in the paper is quite specific (e.g., the initialization and the training of the network). So is it possible to theoretically/empirically discuss the limitations of this study. For example if we keep the parity function as the target, do we expect these result to generalize to other architecture with more standard training methods?\n\nSuggestion:\\\nThe appendix part for the proof of the positive part is a bit hard to read. Particularly, if would be great if the exact training algorithm is once explained and also there is an overview over the proof. ", "limitations": "This is a theoretical study and there is no negative societal impact. However, the potential limitations of the findings could be discussed more extensively.  ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper shows that with sparse initialization, one can decide between wide network and smaller number of samples, or narrower network and higher number of samples and basically move between the two regime. \n- The connection of width to the lottery ticket hypothesis in the sparse initialization setting. \n- The experiments are quite extensive for the 2-layer MLP model with sparse initialization. \n- Observation of grokking and sample-wise double descent in the experiments is also interesting. This shows a potential avenue for future theoretical research on grokking. ", "weaknesses": "- In the abstract, the lower-bound is stated for the number of training samples. However, the lower bound with SQ only contains the gradient precision. (Large number of samples gives is sufficient for the condition on gradient precision but not necessary). So to be exact, there is no bound on the number of samples. Moreover, the SQ bound does not give information about the SGD algorithm. \n- It would have been great if there were experiments checking the results of this paper beyond that particular setting of theoretical results. For example, it would have been nice to have the same experiments on Transformers and mean-field networks. Also the batch size is always 32 in the experiments; it would be nice to also try larger and smaller (maybe one sample at time) batch-sizes as well. Further, what happens if we do not have the initialization sparsity?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the feedback and suggestions!\n\n**(W1) Gap between SQ and SGD**: We agree with the reviewer that the SQ framework as stated only gives a lower bound dependent on total number of queries and the precision of the queries. This does not directly imply a lower bound on the sample complexity, and is a known gap between SQ and SGD. We note that there has been work extending the SQ model to the honest SQ model (HSQ) [Yang05] which evaluates each query by sampling $M$ samples independently and providing the empirical average as the answer to the query. In these settings, tolerance is replaced by the number of samples and there are results of the following style: SQ dimension $d$ implies a lower bound on the total number of samples used $\\Omega(d/\\log d)$. We will add a discussion about this in the paper.\n\n_[Yang05] Ke Yang. New lower bounds for statistical query learning. J. Comput. Syst. Sci., 2005._\n\n**(W2, Q1) Other settings**: We thought the more appropriate direction of \"beyond theory\" was to go from our synthetic parity setting to real tabular data. For the parity problem in particular, the effect of choice of architectures has been previously explored in [BEGKMZ‘22], and we believe similar results may hold here as well. As for initializations beyond sparsity, our experiments show similar results to the sparse initialization setting. However it is technically significantly challenging to analyze since it boils down to showing anti-concentration of higher-order Fourier coefficients of random halfspaces, which we do not currently know how to do. (The experiments in Appendix C.1 of [BEGKMZ22] provide empirical evidence that these halfspaces’ Fourier spectra behave like those of majority with high probability.)\n\n_[BEGKMZ22] Boaz Barak, Benjamin Edelman, Surbhi Goel, Sham Kakade, Eran Malach, and Cyril Zhang. \"Hidden progress in deep learning: Sgd learns parities near the computational limit.\" NeurIPS 2022._\n\n**(S1) Clarity of proofs in appendix**: We appreciate the feedback, and will add high-level intuitive sketches to the main paper and the appendix."}]

Author rebuttal:

Meta-review: This paper presents a theoretical and empirical study of the tradeoffs between computational resources and statistical efficiency in deep learning. The authors investigate the performance gap between neural networks and tree-based classifiers on tabular data and identify three common difficulties for neural networks in this domain. They also explore the benefits of increasing network width and using sparse axis-aligned initialization in sparse parity learning. 

The main strengths of this paper include its clear presentation of theoretical and empirical results, its thorough exploration of algorithm design choices in deep learning, and its practical insights for improving the performance of neural networks on tabular data. The authors provide a standardized suite of classification benchmarks with numerical input features, which can be used to evaluate the performance of different algorithms on tabular data. They also offer practical recommendations for improving the performance of neural networks on sparse parity learning tasks. Overall, this paper provides valuable insights for researchers and practitioners working in the field of (gradient-based) feature learning in neural networks.

Overall, this paper is a joy to read, and all four experts unanimously support this paper. While a few concerns were initially raised, they were subsequently clarified by authors during the rebuttal period. Overall, AC sees this paper as a clear accept case and a noteworthy NeurIPS contribution.
Decision: Accept (spotlight)