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

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

TL;DR

This paper characterizes deep learning success as a multi-resource tradeoff between data, model width, training time, and luck. The authors demonstrate that increasing network width acts as a "parallel search" for lucky feature-learning neurons, allowing wide, sparsely-initialized MLPs to overcome computational-statistical gaps and even outperform tuned random forests on tabular datasets.

What Problem Does This Paper Address?

Algorithm design in deep learning often feels more like "hacking" than engineering. We know that hyperparameters like width, depth, and learning rate interact in complex ways, but we lack a unified framework to understand these tradeoffs.

The authors focus on the computational-statistical gap: a regime where a problem is statistically "easy" (requires few samples) but computationally "hard" (requires massive search). They use the sparse parity problem—identifying a $k$-way interaction between $n$ Boolean variables—as a "maximally hard" toy task. In this setting, standard gradient-based methods typically fail unless provided with an exponential amount of data or time. The paper asks: can we "buy" our way out of this hardness using other resources like network width or initialization strategies?

Methods

The researchers combine theoretical analysis with large-scale empirical sweeps (~200k GPU training runs).

  • Theoretical Framework: They adapt Statistical Query (SQ) lower bounds to formulate a "data $\times$ width $\times$ time $\times$ luck" frontier. This proves that without a sufficient total allocation of these four resources, gradient descent will fail to learn sparse features.
  • Sparse Initialization: A key technique introduced is initializing the first layer of an MLP with $s$-sparse weights (setting only $s$ coordinates to non-zero). This imparts an axis-aligned inductive bias.
  • Parallel Search Mechanism: The authors propose that network width $r$ isn't just about capacity; it functions as a parallel search. A wider network is more likely to contain "lottery ticket" neurons that are initialized with a "lucky" subset of relevant features, allowing them to learn much more sample-efficiently.

Datasets

  • Synthetic: $(n, k)$-sparse parity tasks where $n$ (input dimension) ranges up to 300 and $k$ (interaction degree) is 3 or 4.
  • Tabular Benchmarks: A standardized suite of 16 real-world tabular classification tasks (e.g., healthcare, finance, physics) curated by Grinsztajn et al. (2022). These are specifically chosen because they are traditionally dominated by tree-based models like Random Forests.

Key Insights and Ideas

  • Width Buys Luck: The most striking insight is that overparameterization helps because it parallelizes the search for features. Instead of one neuron slowly finding the right coordinates, a wide network "guesses" many combinations at once.
  • The Success Frontier: There is a clear Pareto frontier where one resource can be traded for another. For example, if you have very little data, you can still succeed by using a much wider network.
  • Axis-Aligned Inductive Bias: Tabular data often relies on axis-aligned features. By using sparse initialization, MLPs gain an inductive bias similar to decision trees, which helps them ignore uninformative features and focus on sparse interactions.
  • Grokking as a Resource Tradeoff: The authors link the phenomenon of "grokking" (delayed generalization) to this frontier, showing it represents a tradeoff between dataset size and training time.

Key Results

The authors empirically confirm the existence of a "success frontier" in Figure 1.

Figure 1: The success frontier shows that increasing width (y-axis) allows the model to succeed with significantly less data (x-axis). The right panels show "grokking" behavior where generalization happens suddenly after many iterations.
  • Theoretical Upper Bound: Theorem 5 proves that with a width of $r = O((n/k)^s)$, a network can learn using only $m = O((n/k)^{k-s-1})$ samples. This mathematically formalizes how width reduces sample complexity.
  • Tabular Performance: On real-world tabular data, wide and sparsely-initialized MLPs showed monotonic improvements in sample efficiency. In several cases, these models outperformed tuned Random Forests, a significant result given that MLPs usually struggle in this domain.
  • Non-Monotonicity: Interestingly, they observed "sample-wise double descent," where increasing the dataset size can actually worsen success probability in certain marginal regimes (see Figure 2).
Figure 2: Detailed views of resource interactions. The center plot shows how width improves sample efficiency, while the right plot illustrates the data vs. time tradeoff (grokking).

Limitations and Future Work

  • End-to-End Theory: While the authors provide a "one-step" analysis for the under-sparse regime (Theorem 5), a full theoretical proof of global convergence for the entire training trajectory remains an open challenge.
  • Tabular Benchmarking: The tabular results are presented as a "preliminary investigation." The authors acknowledge that more exhaustive comparisons are needed to determine if these sparsely-initialized MLPs can consistently beat state-of-the-art tree ensembles across all tabular domains.
  • Optimal Sparsity: While $s=2$ worked best in their experiments, the theoretical reason for this specific value's optimality is not yet fully understood.

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 Kakade and Eran Malach and Cyril Zhang},
  title = {{Pareto Frontiers in Neural Feature Learning: Data, Compute, Width, and Luck}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2023},
  url = {https://openreview.net/forum?id=Ypbke6biDm},
}
Figure