On the Bias-Variance-Cost Tradeoff of Stochastic Optimization

Yifan Hu, Xin Chen, Niao HeNeurIPS 2021 · OpenReview

TL;DR

In many modern machine learning applications, obtaining an unbiased gradient is either impossible or prohibitively expensive. This paper provides a rigorous framework for navigating the "bias-variance-cost" tradeoff, proving that Multi-Level Monte Carlo (MLMC) gradient methods can significantly outperform naive biased SGD and even achieve the gold-standard complexity of unbiased optimization in specific regimes.

What Problem Does This Paper Address?

Standard Stochastic Gradient Descent (SGD) relies on a crucial assumption: we have access to an unbiased estimate of the gradient. However, in emerging fields like distributionally robust optimization (DRO), bilevel optimization, and conditional stochastic optimization (CSO), we often only have access to biased oracles.

While we can usually reduce this bias by using more samples or more computation (e.g., in a nested simulation), the cost of doing so grows rapidly. The fundamental challenge is: How do we allocate our limited computational budget between many cheap, high-bias estimates and a few expensive, low-bias estimates?

Existing work often ignored the possibility of "refining" oracles at different costs. This paper fills that gap by providing a systematic study of how to exploit this tradeoff to achieve faster convergence with lower total computational complexity.

Methods

The authors analyze a family of Multi-Level Monte Carlo (MLMC) gradient methods. The core idea of MLMC is to estimate the gradient of a high-accuracy (but expensive) level by using a "telescoping sum" of differences between successive levels of approximation.

Properties of MLMC Estimators

The paper compares several variants:

  • L-SGD (The Baseline): A naive approach that simply picks a single high-accuracy level and performs standard SGD.
  • V-MLMC (Vanilla MLMC): A deterministic approach that queries all levels up to a fixed depth $L$ and averages them.
  • RT-MLMC (Randomized Truncation): A randomized approach that samples a level $\ell$ from a distribution and only queries that level, introducing bias but keeping per-iteration costs low.
  • RU-MLMC / RR-MLMC: Randomized versions that use infinite telescoping sums to produce unbiased estimators, though these are only feasible when the variance of the differences decays faster than the cost increases.

The authors provide a non-asymptotic analysis across three settings: strongly convex, convex, and nonconvex objectives.

Datasets

As a theoretical optimization paper, the authors evaluate their methods using controlled simulations rather than large-scale static datasets:

  • Synthetic Quadratic Problem: A problem designed with controllable bias to verify the theoretical convergence rates.
  • Invariant Least Square: A specific case of Conditional Stochastic Optimization (CSO) using 2,000 generated feature-label pairs.
  • Invariant Absolute Regression: Used to test the robustness of the methods under different loss functions.

Key Insights and Ideas

  • The "Unbiased" Trap: Surprisingly, an unbiased estimator is not always the best choice. When the cost of removing bias is too high ($b \le c$), trying to force an unbiased estimator causes the variance or the expected cost per iteration to explode. In these "hard" regimes, the biased RT-MLMC method is the most versatile and effective.
  • Matching the Gold Standard: The authors show that when the variance of the difference between levels decays faster than the cost increases ($b > c$), MLMC methods can match the complexity of classical unbiased SGD ($\mathcal{O}(1/\epsilon)$ for strongly convex). This implies that for these problems, the presence of bias doesn't actually make the problem "harder" if handled correctly.
  • CSO Breakthrough: By applying MLMC to Conditional Stochastic Optimization, the authors improved the best-known sample complexity for nonconvex problems from $\tilde{\mathcal{O}}(\epsilon^{-5})$ to $\tilde{\mathcal{O}}(\epsilon^{-4})$.
  • The Importance of $a, b, c$: The paper characterizes the problem using three rates: $a$ (bias decay), $b$ (variance decay of differences), and $c$ (cost increase). The relationship between these constants determines which algorithm is optimal.

Key Results

Complexity Comparison of Algorithms
  • Superiority over L-SGD: In all tested regimes, MLMC methods were strictly better than the naive L-SGD approach. For example, in the strongly convex case with $c < b$, RT-MLMC achieves a total cost of $\mathcal{O}(\epsilon^{-1})$, while L-SGD requires $\mathcal{O}(\epsilon^{-1-c/a})$.
  • Stability vs. Speed: Numerical experiments showed that while V-MLMC has the lowest variance and most stable path, RT-MLMC often converges faster in the early stages of training.
  • Theoretical Tightness: The paper provides the first systematic comparison that accounts for the "oracle cost," moving beyond simple iteration complexity to "total work" complexity.

Limitations and Future Work

  • Constant Bias Levels: Currently, the MLMC estimators maintain the same bias level at each iteration. The authors suggest that adaptive bias reduction (changing the truncation level $L$ as the algorithm progresses) could be a promising future direction.
  • Variance Reduction: While this paper focuses on the bias-variance-cost tradeoff, combining these MLMC techniques with modern variance reduction methods (like SPIDER or SARAH) could further lower the complexity for nonconvex smooth optimization.
  • Real-world Scaling: The numerical results are on synthetic/small-scale problems. Testing these tradeoffs in massive-scale bilevel problems (like hyperparameter optimization for LLMs) remains an open challenge.

Summary updated

Abstract

We consider stochastic optimization when one only has access to biased stochastic oracles of the objective, and obtaining stochastic gradients with low biases comes at high costs. This setting captures a variety of optimization paradigms widely used in machine learning, such as conditional stochastic optimization, bilevel optimization, and distributionally robust optimization. We examine a family of multi-level Monte Carlo (MLMC) gradient methods that exploit a delicate trade-off among the bias, the variance, and the oracle cost. We provide a systematic study of their convergences and total computation complexities for strongly convex, convex, and nonconvex objectives, and demonstrate their superiority over the naive biased stochastic gradient method. Moreover, when applied to conditional stochastic optimization, the MLMC gradient methods significantly improve the best-known sample complexity in the literature.
BibTeX
@inproceedings{hu2021bias,
  author = {Yifan Hu and Xin Chen and Niao He},
  title = {{On the Bias-Variance-Cost Tradeoff of Stochastic Optimization}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=I5f4e3udn2},
}
Figure