In traditional numerical optimization, the goal is to reach the highest possible precision—often seeking the exact point where the gradient is zero. However, in machine learning, we are not optimizing the "true" function (the population risk); we are optimizing a proxy (the empirical risk) built from a finite, noisy sample of data.
A growing body of research suggests that pursuing extreme numerical precision on this proxy is not just computationally expensive—it is statistically meaningless. Once the optimization error becomes smaller than the inherent noise in the data, further computation yields no improvement in generalization. This threshold is known as the statistical error floor.
The Precision vs. Accuracy Paradox
In a seminal review, Leon Bottou, Frank E. Curtis, and Jorge Nocedal argue in Optimization Methods for Large-Scale Machine Learning that machine learning optimization is fundamentally different from classical optimization. In classical settings, $10^{-10}$ precision is better than $10^{-5}$. In machine learning, if the statistical uncertainty of your dataset is $10^{-3}$, then $10^{-10}$ precision is simply wasting electricity to fit noise.
This concept of a "precision floor" was formalized by Alekh Agarwal, Sahand N. Negahban, and Martin J. Wainwright in Fast global convergence rates of gradient methods for high-dimensional statistical recovery. They demonstrated that first-order methods converge geometrically (linearly) until they hit this floor. Beyond this point, the algorithm continues to iterate, but the distance to the true population parameter stops decreasing.
Adaptive Sample Sizing: Growing into the Solution
If the statistical error floor is determined by the sample size, why use the whole dataset from the start? A powerful strategy to exploit this principle is to start with a small subset of data, solve it to its (relatively high) statistical noise floor, and then progressively add more data.
Aryan Mokhtari and Alejandro Ribeiro developed this into a rigorous framework in First-Order Adaptive Sample Size Methods to Reduce Complexity of Empirical Risk Minimization. By ensuring the optimization error never drops significantly below the sampling error of the current subset, they avoid "over-optimizing" on small batches.
This "starting small" philosophy has been applied to various algorithms:
- DYNASAGA: Hadi Daneshmand and Thomas Hofmann showed in Starting Small - Learning with Adaptive Sample Sizes that this approach can reach statistical accuracy in just two passes over the data, compared to the $n \log n$ passes required by standard methods.
- Ada Newton: In Adaptive Newton Method for Empirical Risk Minimization to Statistical Accuracy, Aryan Mokhtari and colleagues applied this to second-order methods, using a single Newton step per data-growth increment to maintain quadratic convergence without the usual computational overhead.
Distributed and Networked Efficiency
The statistical error floor is particularly useful in distributed settings, where communication is the primary bottleneck. If nodes in a network have "statistically similar" data, they don't need to communicate perfectly to reach the global optimum's neighborhood.
Amir Daneshmand and Gesualdo Scutari proved in Newton Method over Networks is Fast up to the Statistical Precision that distributed Newton methods can achieve the same statistical accuracy as a centralized solver while only communicating as much as a simple gradient descent. The key is recognizing that once the local models are "close enough" relative to the data's noise, further consensus is unnecessary.
Similarly, in Federated Learning, Amirhossein Reisizadeh and Hamed Hassani introduced FLANP in Straggler-Resilient Federated Learning, which stops local training once a device reaches its statistical accuracy floor. This prevents "stragglers" (slow devices) from wasting time on high-precision updates that don't help the global model.
Finding the Floor: Principled Stopping Rules
How do we know when we've hit the floor? Several researchers have proposed methods to estimate this intrinsic limit:
- Bayes Error Estimation: Morteza Noshad and Alfred O. Hero developed a framework in Learning to Benchmark to estimate the minimum possible error of a dataset. This provides a "performance ceiling" that tells practitioners when to stop training.
- Nyström Approximations: In kernel methods, Daniele Calandriello and Lorenzo Rosasco showed in Statistical and Computational Trade-Offs in Kernel K-Means that using only $\sqrt{n}$ landmark points is sufficient to reach the statistical error floor of the full dataset, effectively providing a "free lunch" in terms of complexity.
- Smoothing and Grids: For nonparametric density estimation, Rahul Mazumder and Richard J. Samworth demonstrated in A new computational framework for log-concave density estimation that aligning integration grid precision with statistical error can reduce computation time from hours to minutes.
Conclusion
The shift from "numerical convergence" to "statistical accuracy" represents a fundamental change in how we design algorithms. By treating optimization as a means to an end—rather than an end in itself—researchers are creating a new generation of solvers that are faster, more scalable, and more robust to the inherent noise of the real world. As Volkan Cevher and colleagues summarize in Convex Optimization for Big Data, in the era of big data, "sufficiently accurate" is the new "optimal."