NIPS Poster Natasha 2: Faster Non-Convex Optimization Than SGD

Natasha 2: Faster Non-Convex Optimization Than SGD

[ Abstract ]

Abstract: We design a stochastic algorithm to find

ε

$\varepsilon$ -approximate local minima of any smooth nonconvex function in rate

O (ε^{- 3.25})

$O(\varepsilon^{-3.25})$ , with only oracle access to stochastic gradients. The best result before this work was

O (ε^{- 4})

$O(\varepsilon^{-4})$ by stochastic gradient descent (SGD).

Live content is unavailable. Log in and register to view live content