Stochastic Bias-Reduced Gradient Methods
This work addresses stochastic optimization challenges for machine learning and AI practitioners, offering incremental improvements in efficiency and bias reduction.
The paper tackles the problem of stochastic optimization by developing a low-bias, low-cost estimator for the minimizer of Lipschitz strongly-convex functions, achieving bias δ with O(log(1/δ)) variance and expected sampling cost. It demonstrates applications including minimizing the maximum of N functions, matching a lower bound up to logarithmic factors, and recovering state-of-the-art rates for efficient optimization.
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 $δ$, variance $O(\log(1/δ))$, and an expected sampling cost of $O(\log(1/δ))$ 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.