In classical learning theory, data is often viewed as a scarce resource. We ask: "What is the minimum number of samples needed to achieve a certain accuracy?" Under this lens, more data is typically seen as a computational burden—more examples to store, more gradients to compute, and more iterations to run.
However, a growing body of research suggests a more provocative relationship: data can be used as a computational resource. By increasing the volume of data beyond the information-theoretic minimum, we can often simplify the learning problem itself, trading "extra" samples for significantly faster training times.
The Sample-Computation Tradeoff
The core intuition behind this direction is that the difficulty of a learning task is not fixed; it is a function of the available data. As Michael Jordan argues in On statistics, computation and scalability, we should treat computational constraints as first-class citizens alongside statistical goals. In this framework, the increased statistical power of a large dataset can compensate for the lower precision of a faster, simpler algorithm.
This relationship defines a risk-computation frontier. As explored by Daniel L. Sussman and Alexander Volfovsky in Analyzing statistical and computational tradeoffs of estimation procedures, there exists a set of Pareto-optimal estimators where one can choose to spend more time to get better accuracy from few samples, or use a surplus of samples to achieve that same accuracy in a fraction of the time.
Bypassing NP-Hardness
Perhaps the most striking evidence for this tradeoff is that data abundance can turn mathematically "impossible" (NP-hard) problems into tractable ones.
In Using More Data to Speed-up Training Time, Shai Shalev-Shwartz, Ohad Shamir, and Eran Tromer demonstrate that certain learning tasks are only computationally hard because they are analyzed at the "sample limit." When provided with a polynomial increase in data, these tasks can transition from exponential-time complexity to polynomial-time complexity.
Recent work by Guy Blanc and colleagues in Computational-Statistical Tradeoffs from NP-hardness formalizes this by linking the RP vs. NP question to sample complexity. They show that for specific concept classes, providing more data points exponentially reduces the time required to find a valid hypothesis, effectively using samples to "buy" the nondeterministic bits that would otherwise make the problem intractable.
Smoothing the Optimization Landscape
Why does more data make things easier? One mechanism is the "smoothing" of the objective function.
In many structured prediction tasks, solving for the optimal parameters requires a global "inference" step that is NP-hard. David Sontag and his co-authors in More data means less inference: A pseudo-max approach to structured learning show that with enough data, one can replace this global inference with a "pseudo-max" approach—a cheap, local heuristic that only looks at single-variable changes. As data volume increases, this local approach converges to the same optimal parameters as the expensive global one.
Similarly, John J. Bruer and Joel A. Tropp demonstrate in Time-Data Tradeoffs by Aggressive Smoothing that extra data allows for more "aggressive smoothing" of non-smooth optimization problems. This reduces the number of iterations needed for convergence, directly trading samples for clock cycles without sacrificing statistical accuracy.
Data-Assisted Efficiency
The principle extends beyond optimization to robust estimation and unsupervised learning:
- Robust Estimation: Ankit Pensia shows in A Sub-Quadratic Time Algorithm for Robust Sparse Mean Estimation that increasing the number of samples allows for sub-quadratic algorithms that bypass traditional bottlenecks like computing full covariance matrices.
- Coresets: In Tradeoffs for Space, Time, Data and Risk in Unsupervised Learning, Mario Lučić and Andreas Krause use a surplus of data to build "coresets"—highly representative summaries. Because these summaries are smaller and more accurate when drawn from a larger pool, they accelerate the convergence of learning algorithms.
- Quantum vs. Classical: Even in the comparison between quantum and classical computing, Vedran Dunjko and Casper Gyurik note in On establishing learning separations between classical and quantum machine learning with classical data that access to data can bridge computational gaps. A function that is classically hard to compute from a formula may become easy to learn once a model can observe enough input-output pairs.
Summary
The shift from "data as a burden" to "data as a resource" suggests that the most efficient way to solve a hard problem may not be a better algorithm, but simply more data. By leveraging the statistical redundancy of large datasets, we can utilize simpler, faster, and more robust computational methods that would fail in data-starved regimes.