Adaptive Sample Size Optimization for Efficient Learning

This direction is merged into another direction: statistical precision floor. Its last version stays readable and citable here.

Version 1 of 129 papers36 conceptsfrozen 2026-10-04

In large-scale machine learning, the standard approach to Empirical Risk Minimization (ERM) is to treat the entire dataset as a single, massive optimization hurdle. Whether using Gradient Descent or more complex solvers, we typically iterate over the full $N$ samples from the very first step.

However, a growing body of research suggests this is computationally wasteful. When a model’s parameters are far from the global optimum, the high-precision gradient calculated from a million samples is often no more useful for progress than a rough estimate from a few hundred. By dynamically growing the training set size as the model improves, researchers have found they can reach the same "statistical accuracy" with a fraction of the total computation.

The Intuition of Starting Small

The core idea, pioneered by researchers like Pedro M. Domingos and Geoff Hulten in their work on Very Fast EM, is that we should only use as much data as necessary to guarantee a result nearly identical to what would be obtained with infinite data.

Early in training, the model is "dumb." It needs to learn coarse features and general directions. Using the full dataset here is like using a microscope to find a mountain range; the level of detail provided by the full data is drowned out by the model's own current imprecision. As Hadi Daneshmand and Thomas Hofmann argue in Starting Small - Learning with Adaptive Sample Sizes, we can reduce computational overhead by avoiding high-precision optimization on large datasets when the model is still far from the global minimum.

Geometric Growth and Warm Starting

The most common mechanism for this is geometric sample size scaling. The process follows a simple loop:

  1. Start with a very small subset of data.
  2. Solve the optimization problem on this subset.
  3. Double the sample size (or increase it by a geometric factor).
  4. Use the previous solution as a "warm start" for the new, larger problem.

Aryan Mokhtari and Alejandro Ribeiro formalized this in First-Order Adaptive Sample Size Methods. They showed that by solving a sequence of sub-problems on progressively larger subsets, you can reach the statistical accuracy of the full dataset in roughly two passes over the data. This is significantly faster than the $n \log n$ steps often required by fixed-sample stochastic methods.

Solving to Statistical Accuracy

A key insight of this research direction is the distinction between optimization error and statistical error.

  • Statistical error is the inherent uncertainty in a model because we only have a finite sample of the world.
  • Optimization error is how far our current parameters are from the best possible parameters for that specific sample.

In Adaptive Newton Method for Empirical Risk Minimization to Statistical Accuracy, Mokhtari and his colleagues explain that there is no point in reducing the optimization error far below the statistical error. If your 1,000-sample subset has a 1% margin of error, spending compute to reach 0.001% optimization precision is a waste. Instead, adaptive methods solve each sub-problem only until the optimization error matches the statistical accuracy of the current sample size before doubling the data.

Scaling Second-Order Methods

This "growing data" paradigm makes expensive second-order (Newton) methods viable for large datasets. Traditional Newton methods require calculating the Hessian (the matrix of second derivatives), which is prohibitively expensive on millions of samples.

Algorithms like DANCE (Distributed Accumulated Newton Conjugate gradiEnt), proposed by Majid Jahani and Dheevatsa Mudigere, use the accumulating sample strategy to make these methods scalable. By the time the algorithm reaches the full dataset, the "warm start" from the previous subset is so close to the optimum that only a single Newton iteration is often required to reach the final solution. This allows models to exploit the quadratic convergence of Newton methods without the heavy computational toll of full-dataset evaluations.

Applications Beyond Standard Training

The benefits of adaptive sampling extend beyond simple model training:

  • Hyperparameter Tuning: The ABC (Approximate Best Configuration) framework by Silu Huang and Chi Wang uses progressive sampling to prune poor model configurations early. By evaluating candidates on small data slices first, they achieve up to a 200x speedup in finding the best model.
  • Pairwise Learning: For tasks like AUC maximization where the number of pairs grows quadratically ($O(n^2)$), Bin Gu and Heng Huang showed that stagewise training can reduce the complexity to linear $O(n)$.
  • Synthetic Data: In the context of LLM bootstrapping, Pu Yang and colleagues found that an exponentially increasing data allocation is actually required to maximize gains under a fixed computational budget, as it compensates for the diminishing returns of early updates.

By treating the dataset size as a dynamic parameter rather than a static constraint, these methods align computational effort with the actual information needs of the model at each stage of its evolution.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_adaptive_sample_size_optimization_for_ef_9ecb350b,
  title = {Adaptive Sample Size Optimization for Efficient Learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/adaptive-sample-size-optimization-for-efficient-learning/rdr_9ecb350ba6d44a6c93f21a1ade36b6c0},
  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_adaptive_sample_size_optimization_for_ef_9ecb350b_v1,
  title = {Adaptive Sample Size Optimization for Efficient Learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/adaptive-sample-size-optimization-for-efficient-learning/rdr_9ecb350ba6d44a6c93f21a1ade36b6c0/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}