Stochastic Bias-Reduced Gradient Methods

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

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. By applying a multilevel Monte-Carlo (MLMC) approach, we transform optimal stochastic gradient methods 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. This primitive enables nearly unbiased gradient estimators for the Moreau-Yoshida envelope, facilitating dimension-free randomized smoothing. We demonstrate the utility of this approach through four applications: minimizing the maximum of $N$ functions, projection-efficient optimization, gradient-efficient composite optimization, and potential improvements in differentially-private non-smooth stochastic optimization.

Introduction

In the realm of stochastic optimization, Stochastic Gradient Descent (SGD) is the workhorse for finding the minimizer $x_\star$ of a function $f$. However, a fundamental limitation of standard SGD is the persistence of bias. After $T$ iterations, the distance between the current estimate and the true minimizer typically scales as $O(1/\sqrt{T})$. Achieving a very small bias requires a prohibitively large number of iterations, creating a computational bottleneck for high-precision applications.

While "de-biasing" techniques are well-established for estimating expected values (integrals), applying them to the output of an iterative optimization process is significantly more challenging. This paper introduces OptEst, a new primitive that leverages Multilevel Monte Carlo (MLMC) to produce a nearly unbiased estimator of the minimizer $x_\star$ with minimal computational overhead.

The OptEst Primitive: De-biasing Optimization

The core innovation lies in the application of the MLMC technique, specifically a variant proposed by Blanchet and Glynn, to stochastic optimization. The authors assume access to an "Optimal-Distance-Convergence" (ODC) algorithm—such as a variant of EpochSGD—which, given a budget $T$, returns an estimate $x_T$ such that $\mathbb{E}[\|x_T - x_\star\|^2] = O(1/T)$.

The OptEst procedure works as follows:

  1. Draw a random integer $J$ from a geometric distribution.
  2. Compute the difference between the outputs of the ODC algorithm with budgets $2^J$ and $2^{J-1}$.
  3. Weight these differences correctly to form a telescoping sum that, in expectation, converges to the true minimizer $x_\star$.

The breakthrough is that this estimator achieves a bias of $\delta$ with an expected cost and variance that grow only logarithmically with $1/\delta$. This "nearly unbiased" property allows practitioners to drive bias toward zero with negligible extra work compared to standard methods.

Moreau-Yoshida Smoothing and Proximal Points

A key application of OptEst is the estimation of the gradient of the Moreau-Yoshida envelope. For a Lipschitz convex function $f$, the envelope is defined as: $$f_\lambda(x) = \min_y \left\{ f(y) + \frac{1}{2\lambda} \|x-y\|^2 \right\}$$ The gradient of this smooth envelope is given by $\nabla f_\lambda(x) = \frac{1}{\lambda}(x - \text{prox}_{\lambda f}(x))$, where $\text{prox}_{\lambda f}(x)$ is the minimizer of the strongly convex objective inside the brackets. Since OptEst can efficiently estimate this minimizer, it provides a nearly unbiased gradient estimator for the envelope. This allows for the use of accelerated methods (like Nesterov's AGD) on non-smooth problems without the dimension-dependent penalties usually associated with randomized smoothing.

Applications and Complexity Results

The authors demonstrate the power of the OptEst primitive through several classical optimization problems, summarized in the table below.

  1. Minimizing the Maximal Loss: For the problem $\max_{i \in [N]} f_i(x)$, the proposed method achieves a complexity of $\tilde{O}(N\epsilon^{-2/3} + \epsilon^{-2})$. This matches the known lower bound up to logarithmic factors and significantly improves upon previous state-of-the-art methods when $N$ is large.
  2. Projection-Efficient Optimization: In scenarios where projecting onto a constraint set $\mathcal{X}$ is the dominant cost (e.g., semidefinite programming), the method recovers optimal rates ($O(\epsilon^{-1})$ projections) using a transparent analysis that simplifies previous "gradient sliding" techniques.
  3. Gradient-Efficient Composite Optimization: For objectives of the form $\Lambda(x) + f(x)$, where $\nabla \Lambda$ is expensive to compute, the method provides a simple alternative to complex sliding algorithms, achieving $O(\sqrt{L/\epsilon})$ evaluations of $\nabla \Lambda$.
Summary of complexity results for various optimization objectives using the proposed bias-reduced gradient methods.

Theoretical Implications for Differential Privacy

The paper also explores a potential breakthrough in differentially private (DP) non-smooth stochastic optimization. Currently, achieving optimal utility in this setting is computationally expensive. The authors show that if a version of their estimator existed with bounded outputs (rather than just bounded variance), it would yield a nearly linear-time, optimal-utility DP method. While the current MLMC estimator is "heavy-tailed" (unbounded higher moments), this result points toward a promising research direction.

Conclusion and Limitations

While the OptEst primitive provides a powerful theoretical tool for establishing complexity bounds, the authors note several limitations. The estimator's heavy-tailed nature makes it sensitive to outliers, and its practical performance compared to tuned heuristics remains to be explored. Furthermore, the analysis is strictly confined to the convex setting. Nonetheless, by treating optimization as a functional of an expectation, this work opens new avenues for applying statistical de-biasing tools to the most challenging problems in optimization.

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. 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-Yoshida envelope of any Lipschitz convex function, allowing us to perform dimension-free randomized smoothing. 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