Stochastic Variance-Reduced Cubic Regularization for Nonconvex Optimization

Zhe Wang, Yi Zhou, Yingbin Liang, Guanghui Lan
Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, PMLR 89:2731-2740, 2019.

Abstract

Cubic regularization (CR) is an optimization method with emerging popularity due to its capability to escape saddle points and converge to second-order stationary solutions for nonconvex optimization. However, CR encounters a high sample complexity issue for finite-sum problems with a large data size. Various inexact variants of CR have been proposed to improve the sample complexity. In this paper, we propose a stochastic variance-reduced cubic-regularization (SVRC) method under random sampling, and study its convergence guarantee as well as sample complexity. We show that the iteration complexity of SVRC for achieving a second-order stationary solution within $\epsilon$ accuracy is $O(\epsilon^{-3/2})$, which matches the state-of-art result on CR types methods. Moreover, our proposed variance reduction scheme significantly reduces the per-iteration sample complexity. The resulting total Hessian sample complexity of our SVRC is $O(N^{2/3} \epsilon^{-3/2})$, which outperforms the state-of-art result by a factor of $O(N^{2/15})$. We also study our SVRC under random sampling without replacement scheme, which yields a lower per-iteration sample complexity, and hence justifies its practical applicability.

Cite this Paper

BibTeX
@InProceedings{pmlr-v89-wang19d, title = {Stochastic Variance-Reduced Cubic Regularization for Nonconvex Optimization}, author = {Wang, Zhe and Zhou, Yi and Liang, Yingbin and Lan, Guanghui}, booktitle = {Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics}, pages = {2731--2740}, year = {2019}, editor = {Chaudhuri, Kamalika and Sugiyama, Masashi}, volume = {89}, series = {Proceedings of Machine Learning Research}, month = {16--18 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v89/wang19d/wang19d.pdf}, url = {https://proceedings.mlr.press/v89/wang19d.html}, abstract = {Cubic regularization (CR) is an optimization method with emerging popularity due to its capability to escape saddle points and converge to second-order stationary solutions for nonconvex optimization. However, CR encounters a high sample complexity issue for finite-sum problems with a large data size. Various inexact variants of CR have been proposed to improve the sample complexity. In this paper, we propose a stochastic variance-reduced cubic-regularization (SVRC) method under random sampling, and study its convergence guarantee as well as sample complexity. We show that the iteration complexity of SVRC for achieving a second-order stationary solution within $\epsilon$ accuracy is $O(\epsilon^{-3/2})$, which matches the state-of-art result on CR types methods. Moreover, our proposed variance reduction scheme significantly reduces the per-iteration sample complexity. The resulting total Hessian sample complexity of our SVRC is $O(N^{2/3} \epsilon^{-3/2})$, which outperforms the state-of-art result by a factor of $O(N^{2/15})$. We also study our SVRC under random sampling without replacement scheme, which yields a lower per-iteration sample complexity, and hence justifies its practical applicability.} }
Endnote
%0 Conference Paper %T Stochastic Variance-Reduced Cubic Regularization for Nonconvex Optimization %A Zhe Wang %A Yi Zhou %A Yingbin Liang %A Guanghui Lan %B Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Masashi Sugiyama %F pmlr-v89-wang19d %I PMLR %P 2731--2740 %U https://proceedings.mlr.press/v89/wang19d.html %V 89 %X Cubic regularization (CR) is an optimization method with emerging popularity due to its capability to escape saddle points and converge to second-order stationary solutions for nonconvex optimization. However, CR encounters a high sample complexity issue for finite-sum problems with a large data size. Various inexact variants of CR have been proposed to improve the sample complexity. In this paper, we propose a stochastic variance-reduced cubic-regularization (SVRC) method under random sampling, and study its convergence guarantee as well as sample complexity. We show that the iteration complexity of SVRC for achieving a second-order stationary solution within $\epsilon$ accuracy is $O(\epsilon^{-3/2})$, which matches the state-of-art result on CR types methods. Moreover, our proposed variance reduction scheme significantly reduces the per-iteration sample complexity. The resulting total Hessian sample complexity of our SVRC is $O(N^{2/3} \epsilon^{-3/2})$, which outperforms the state-of-art result by a factor of $O(N^{2/15})$. We also study our SVRC under random sampling without replacement scheme, which yields a lower per-iteration sample complexity, and hence justifies its practical applicability.
APA
Wang, Z., Zhou, Y., Liang, Y. & Lan, G.. (2019). Stochastic Variance-Reduced Cubic Regularization for Nonconvex Optimization. Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 89:2731-2740 Available from https://proceedings.mlr.press/v89/wang19d.html.

Related Material