Stochastic Bias-Reduced Gradient Methods

Hilal Asi, Yair Carmon, Arun Jambulapati, Yujia Jin, Aaron Sidford

The Challenge of Bias in Stochastic Optimization

In stochastic optimization, finding the minimizer $x_*$ of a function $F(x)$ is a foundational task. Standard tools like Stochastic Gradient Descent (SGD) produce estimates whose distance from the true minimizer—the bias—shrinks relatively slowly, typically at a rate of $O(1/\sqrt{T})$ after $T$ iterations.

While this is sufficient for simple minimization, many advanced algorithms require an unbiased (or extremely low-bias) estimate of a minimizer to function correctly. For instance, "smoothing" a jagged, non-smooth function using the Moreau-Yoshida envelope requires finding a proximal point. If the estimate of that point is biased, errors compound, leading to slow convergence or necessitating expensive, high-precision computations. The core challenge addressed by this research is obtaining a nearly unbiased estimate of $x_*$ without incurring a massive computational penalty.

The Multilevel Monte Carlo (MLMC) Estimator

To solve this, the authors introduce a new primitive: the Multilevel Monte Carlo (MLMC) optimum estimator. Instead of running an optimization algorithm for a fixed number of steps, they employ a "doubling trick" combined with random sampling:

  1. The Doubling Trick: An existing "Optimal Distance-Convergence" (ODC) algorithm (like a variant of SGD) is run for $2^j$ iterations.
  2. The MLMC Estimator: A random integer $J$ is sampled from a geometric distribution. The estimator is constructed by taking the scaled difference between the algorithm's output at $2^J$ steps and $2^{J-1}$ steps.
  3. De-biasing: Mathematically, this telescoping sum structure cancels out the bias from earlier iterations.

The result is an estimator $\hat{x}_*$ where the bias can be made arbitrarily small ($\delta$) while the variance and the expected number of gradient evaluations grow only logarithmically with $1/\delta$. This yields a "nearly unbiased" and "nearly linear-time" estimator.

Key Insights and Theoretical Breakthroughs

  • Optimization as a Primitive: The paper treats the output of an optimizer as a random variable that can be manipulated using statistical techniques (MLMC) typically reserved for integration or differential equations.
  • Dimension-Free Smoothing: By using their estimator to approximate the gradient of the Moreau-Yoshida envelope, the authors perform "randomized smoothing" where the smoothness parameter is independent of the problem's dimension—a significant advantage for high-dimensional machine learning.
  • Min-Max Complexity: For a specific range of $N$ functions, minimizing the maximum of $N$ functions is shown to be no harder than minimizing their average, settling a known complexity gap.
  • Bridging Theory and Privacy: The research establishes a direct link between low-bias estimators and Differentially Private (DP) optimization, suggesting that better estimators could resolve long-standing efficiency bottlenecks in private non-smooth optimization.

Key Results and Applications

The authors demonstrate the power of their estimator across several major applications, establishing improved upper bounds on computational complexity. As this is a theoretical paper, these results are mathematical proofs rather than empirical benchmarks.

Summary of complexity bounds for various optimization objectives.
  1. Minimizing the Maximum of $N$ Functions: They achieved a complexity of $\tilde{O}(N\epsilon^{-2/3} + \epsilon^{-2})$, matching a known lower bound and improving upon previous state-of-the-art methods for large $N$.
  2. Projection Efficiency: For problems where projecting onto a constraint set is computationally expensive (e.g., semidefinite programming), they reduced the required number of projections to $O(\epsilon^{-1})$ for non-smooth functions.
  3. Gradient Efficiency: They recovered state-of-the-art rates for "gradient sliding" (where one part of a composite function is much smoother than the other) using a significantly simpler and more transparent analysis.
  4. Differential Privacy: They proved that if a "bounded" version of their estimator exists, it would enable an optimal-utility, nearly linear-time algorithm for non-smooth private stochastic optimization.

Limitations and Future Directions

  • Theoretical Proof Device: The authors explicitly position this paper as a "proof device" to establish theoretical upper bounds, without investigating practical performance or real-world software implementation.
  • Heavy Tails: While the estimator has a bounded variance, its higher moments are unbounded. This "heavy-tailed" nature complicates its use in settings requiring high-probability guarantees, such as current Differential Privacy frameworks.
  • Sequential Nature: The MLMC estimator is inherently sequential and does not naturally benefit from parallelization in its current form.
  • Convexity Requirement: The analysis is strictly limited to convex functions. Extending these de-biasing techniques to non-convex or weakly-convex landscapes remains an open challenge for future work.

Summary updated

Abstract

We develop a new primitive for stochastic optimization: a low-bias, low-cost estimator of the minimizer $x_\star$ of any Lipschitz strongly-convex function $f$. In particular, we use a multilevel Monte-Carlo approach due to Blanchet and Glynn to turn any optimal stochastic gradient method into an estimator of $x_\star$ with bias $\delta$, variance $O(\log(1/\delta))$, and an expected sampling cost of $O(\log(1/\delta))$ stochastic gradient evaluations. As an immediate consequence, we obtain cheap and nearly unbiased gradient estimators for the Moreau envelope of any Lipschitz convex function. We demonstrate the potential of our estimator through four applications. First, we develop a method for minimizing the maximum of $N$ functions, improving on recent results and matching a lower bound up to logarithmic factors. Second and third, we recover state-of-the-art rates for projection-efficient and gradient-efficient optimization using simple algorithms with a transparent analysis. Finally, we show that an improved version of our estimator would yield a nearly linear-time, optimal-utility, differentially-private non-smooth stochastic optimization method.
BibTeX
@inproceedings{asi2021stochastic,
  author = {Hilal Asi and Yair Carmon and Arun Jambulapati and Yujia Jin and Aaron Sidford},
  title = {{Stochastic Bias-Reduced Gradient Methods}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=gFTGepEImmX},
}
Figure