Skip to main content

Stabilized SVRG: Simple Variance Reduction for Nonconvex Optimization

Publication ,  Conference
Ge, R; Li, Z; Wang, W; Wang, X
Published in: Proceedings of Machine Learning Research
January 1, 2019

Variance reduction techniques like SVRG (Johnson and Zhang, 2013) provide simple and fast algorithms for optimizing a convex finite-sum objective. For nonconvex objectives, these techniques can also find a first-order stationary point (with small gradient). However, in nonconvex optimization it is often crucial to find a second-order stationary point (with small gradient and almost PSD hessian). In this paper, we show that Stabilized SVRG – a simple variant of SVRG – can find an ε-second-order stationary point using only Oe(n2/3/ε2 + n/ε1.5) stochastic gradients. To our best knowledge, this is the first second-order guarantee for a simple variant of SVRG. The running time almost matches the known guarantees for finding ε-first-order stationary points.

Duke Scholars

Published In

Proceedings of Machine Learning Research

EISSN

2640-3498

Publication Date

January 1, 2019

Volume

99

Start / End Page

1394 / 1448
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Ge, R., Li, Z., Wang, W., & Wang, X. (2019). Stabilized SVRG: Simple Variance Reduction for Nonconvex Optimization. In Proceedings of Machine Learning Research (Vol. 99, pp. 1394–1448).
Ge, R., Z. Li, W. Wang, and X. Wang. “Stabilized SVRG: Simple Variance Reduction for Nonconvex Optimization.” In Proceedings of Machine Learning Research, 99:1394–1448, 2019.
Ge R, Li Z, Wang W, Wang X. Stabilized SVRG: Simple Variance Reduction for Nonconvex Optimization. In: Proceedings of Machine Learning Research. 2019. p. 1394–448.
Ge, R., et al. “Stabilized SVRG: Simple Variance Reduction for Nonconvex Optimization.” Proceedings of Machine Learning Research, vol. 99, 2019, pp. 1394–448.
Ge R, Li Z, Wang W, Wang X. Stabilized SVRG: Simple Variance Reduction for Nonconvex Optimization. Proceedings of Machine Learning Research. 2019. p. 1394–1448.

Published In

Proceedings of Machine Learning Research

EISSN

2640-3498

Publication Date

January 1, 2019

Volume

99

Start / End Page

1394 / 1448