Timezone: »

 
Poster
Momentum-Based Variance Reduction in Non-Convex SGD
Ashok Cutkosky · Francesco Orabona

Thu Dec 12 05:00 PM -- 07:00 PM (PST) @ East Exhibition Hall B + C #214
in Optimization -- Non-Convex Optimization »
Variance reduction has emerged in recent years as a strong competitor to stochastic gradient descent in non-convex problems, providing the first algorithms to improve upon the converge rate of stochastic gradient descent for finding first-order critical points. However, variance reduction techniques typically require carefully tuned learning rates and willingness to use excessively large "mega-batches" in order to achieve their improved results. We present a new algorithm, STORM, that does not require any batches and makes use of adaptive learning rates, enabling simpler implementation and less hyperparameter tuning. Our technique for removing the batches uses a variant of momentum to achieve variance reduction in non-convex optimization. On smooth losses $F$, STORM finds a point $x$ with $\mathbb{E}[\|\nabla F(x)\|]\le O(1/\sqrt{T}+\sigma^{1/3}/T^{1/3})$ in $T$ iterations with $\sigma^2$ variance in the gradients, matching the best-known rate but without requiring knowledge of $\sigma$.
Keywords: Non-Convex Optimization · Optimization · Stochastic Optimization
[ Paper]  [ Slides] 

Author Information

Ashok Cutkosky (Google Research)
Francesco Orabona (Boston University)

More from the Same Authors