Timezone: »

 
Poster
Stochastic Bias-Reduced Gradient Methods
Hilal Asi · Yair Carmon · Arun Jambulapati · Yujia Jin · Aaron Sidford

Thu Dec 09 08:30 AM -- 10:00 AM (PST) @
in Poster Session 6 »
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.
Keywords: Theory · Optimization · Privacy

Author Information

Hilal Asi (Stanford University)
Yair Carmon (Stanford University)
Arun Jambulapati (Stanford University)
Yujia Jin (Stanford University)
Aaron Sidford (Stanford)

More from the Same Authors