Data as a Computational Resource for Faster Learning

This direction is no longer present in the current build. Its last version stays readable and citable here.

Version 1 of 121 papers46 conceptsfrozen 2026-10-04

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:

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.

Papers in this version

History & citationVersion 1 · 2026-10-04

No longer present in the current build · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_data_as_a_computational_resource_for_fas_f2e2521b,
  title = {Data as a Computational Resource for Faster Learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/data-as-a-computational-resource-for-faster-learning/rdr_f2e2521b8915492cae7aa6944e936c5b},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_data_as_a_computational_resource_for_fas_f2e2521b_v1,
  title = {Data as a Computational Resource for Faster Learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/data-as-a-computational-resource-for-faster-learning/rdr_f2e2521b8915492cae7aa6944e936c5b/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}