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:
- Draw a random integer $J$ from a geometric distribution.
- Compute the difference between the outputs of the ODC algorithm with budgets $2^J$ and $2^{J-1}$.
- 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.
- 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.
- 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.
- 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$.
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