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.

本文提出一种新的随机优化原理，即使用 Blanchet 和 Glynn 的多级 Monte-Carlo 方法将任何最优随机梯度方法转换为 $x_*$ 的估计量，以此为基础获得了一种廉价且几乎无偏差的梯度估计器，可以应用于随机优化的多个领域，如随机优化，概率图形模型推理以及优化的机器学习等。