Pareto Frontiers in Deep Feature Learning: Data, Compute, Width, and Luck

Benjamin L. Edelman, Surbhi Goel, Sham M. Kakade, eran malach, Cyril Zhang

Overview

This paper explores the complex tradeoffs between data, compute, network width, and initialization ("luck") in deep learning. Using the mathematically rigorous sparse parity problem, the authors prove and empirically demonstrate that increasing network width and using sparse initialization acts as a parallel search for "lottery ticket" neurons, drastically improving sample efficiency. These insights translate to real-world tabular data, where wide, sparsely-initialized neural networks become highly competitive with tree-based models like Random Forests.

The Challenge of Algorithmic Tradeoffs

Algorithm design in deep learning often feels more like "hacking" than engineering because hyperparameters—like network width, dataset size, and training time—interact in unpredictable ways. The authors want to formally understand if this heterogeneity of methods is necessary, particularly in the presence of computational-statistical gaps (problems that are statistically solvable with little data but computationally intractable).

To study this, they use the offline sparse parity learning problem. In this task, a model must identify a target that depends on the XOR of a small subset ($k$) of a larger number ($n$) of binary features. It is a pure "feature learning" problem because lower-order correlations give zero information about the target; the data looks like pure noise until the exact interaction is found. While Statistical Query (SQ) lower bounds prove this problem is incredibly hard for gradient-based methods, the authors investigate how different combinations of resources (data, width, time, and luck) can be traded off to overcome this barrier.

Methodology

The authors combine theoretical computer science with large-scale empirical deep learning:

  • Theoretical Analysis: They formulate a "data × width × time × luck" lower bound using the SQ framework. They then prove upper bounds for 2-layer ReLU MLPs, showing that specific scaling of network width and sparse initialization can overcome the sample complexity barrier.
  • Synthetic Experiments: They conducted ~200K GPU training runs on the sparse parity problem, systematically varying dataset size ($m$), network width ($r$), and initialization sparsity ($s$) to map out the empirical "success frontier."
Empirical success frontier showing the tradeoff between network width and dataset size.
  • Real-World Transfer: Recognizing that tabular data shares key traits with sparse parity (axis-aligned features, uninformative variables, non-smooth patterns), they applied their insights—specifically wide networks and sparse initialization—to 16 real-world tabular classification benchmarks from OpenML.

Key Insights

  • Width acts as a parallel search: Overparameterization isn't just about increasing a model's capacity to memorize; it provides more "lottery tickets." A wider network has a higher probability of initializing a "lucky" neuron whose initial weights align well with the target features. Once found, this lucky neuron requires drastically less data to learn the target.
  • Width buys data, time, and luck: Contrary to classical uniform convergence theories (which suggest bigger models overfit small datasets), increasing width monotonically improved success probability, sample efficiency, and convergence speed in these feature-learning tasks.
  • Sparse initialization is a cheat code for axis-aligned problems: Initializing hidden neurons with sparse weights (e.g., setting only a few random coordinates to 1 and the rest to 0) significantly boosts the chance of finding the right features. This acts as a strong inductive bias for problems where only a few specific features matter.
Comparison of dense vs. sparse initialization on convergence thresholds and computation time.
  • Grokking and Double Descent: The empirical frontier revealed complex optimization dynamics. At the edge of feasibility, the network exhibits "grokking" (requiring massive compute time to suddenly generalize) and "sample-wise double descent" (where adding slightly more data temporarily hurts performance before helping again).

Main Results

  • Theoretical: The authors proved that for a 2-layer MLP with initialization sparsity $s > \Omega(k)$, a width of $\Theta((n/s)^k)$ allows the network to learn the parity with only $\Theta(n^2(s/k)^{k-1})$ samples, smoothly interpolating between the need for large data vs. large width.
  • Synthetic: The ~200K GPU runs demonstrated a clear "success frontier." For example, a network of width $10^5$ can perfectly learn a parity task with an order of magnitude less data than a network of width $10^2$.
  • Tabular Data: On the 16 tabular benchmarks (especially in artificially downsampled, low-data regimes), wide MLPs with sparse initialization generalized significantly better than standard dense MLPs. In several cases, these modified MLPs outperformed heavily tuned Random Forests, helping bridge the notorious gap between deep learning and tree-based models on tabular data.

Limitations and Future Directions

While the theoretical analysis is robust, the "exact-sparsity" regime (where initialization sparsity exactly matches the target sparsity) lacks an end-to-end proof of global convergence, though the authors outline its expected mechanics. Furthermore, while the tabular data experiments are promising, they remain preliminary. The authors acknowledge the perennial methodological difficulty of creating perfectly fair comparisons between neural networks and tree-based paradigms, suggesting that a more exhaustive study of algorithmic improvements for MLPs on tabular data could definitively close the performance gap.

Summary updated

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.
BibTeX
@inproceedings{edelman2023pareto,
  author = {Benjamin L. Edelman and Surbhi Goel and Sham M. Kakade and eran malach and Cyril Zhang},
  title = {{Pareto Frontiers in Deep Feature Learning: Data, Compute, Width, and Luck}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2023},
  url = {https://openreview.net/forum?id=Ypbke6biDm},
}
Figure