Complexities in Projection-Free Stochastic Non-convex Minimization

Zebang Shen, Cong Fang, Peilin Zhao, Junzhou Huang, Hui Qian
Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, PMLR 89:2868-2876, 2019.

Abstract

For constrained nonconvex minimization problems, we propose a meta stochastic projection-free optimization algorithm, named Normalized Frank Wolfe Updating, that can take any Gradient Estimator (GE) as input. For this algorithm, we prove its convergence rate, regardless of the choice of GE. Using a sophisticated GE, this algorithm can significantly improve the Stochastic First order Oracle (SFO) complexity. Further, a new second order GE strategy is proposed to incorporate curvature information, which enjoys theoretical advantage over the first order ones. Besides, this paper also provides a lower bound of Linear-optimization Oracle (LO) queried to achieve an approximate stationary point. Simulation studies validate our analysis under various parameter settings.

Cite this Paper

BibTeX
@InProceedings{pmlr-v89-shen19b, title = {Complexities in Projection-Free Stochastic Non-convex Minimization}, author = {Shen, Zebang and Fang, Cong and Zhao, Peilin and Huang, Junzhou and Qian, Hui}, booktitle = {Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics}, pages = {2868--2876}, 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/shen19b/shen19b.pdf}, url = {https://proceedings.mlr.press/v89/shen19b.html}, abstract = {For constrained nonconvex minimization problems, we propose a meta stochastic projection-free optimization algorithm, named Normalized Frank Wolfe Updating, that can take any Gradient Estimator (GE) as input. For this algorithm, we prove its convergence rate, regardless of the choice of GE. Using a sophisticated GE, this algorithm can significantly improve the Stochastic First order Oracle (SFO) complexity. Further, a new second order GE strategy is proposed to incorporate curvature information, which enjoys theoretical advantage over the first order ones. Besides, this paper also provides a lower bound of Linear-optimization Oracle (LO) queried to achieve an approximate stationary point. Simulation studies validate our analysis under various parameter settings.} }
Endnote
%0 Conference Paper %T Complexities in Projection-Free Stochastic Non-convex Minimization %A Zebang Shen %A Cong Fang %A Peilin Zhao %A Junzhou Huang %A Hui Qian %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-shen19b %I PMLR %P 2868--2876 %U https://proceedings.mlr.press/v89/shen19b.html %V 89 %X For constrained nonconvex minimization problems, we propose a meta stochastic projection-free optimization algorithm, named Normalized Frank Wolfe Updating, that can take any Gradient Estimator (GE) as input. For this algorithm, we prove its convergence rate, regardless of the choice of GE. Using a sophisticated GE, this algorithm can significantly improve the Stochastic First order Oracle (SFO) complexity. Further, a new second order GE strategy is proposed to incorporate curvature information, which enjoys theoretical advantage over the first order ones. Besides, this paper also provides a lower bound of Linear-optimization Oracle (LO) queried to achieve an approximate stationary point. Simulation studies validate our analysis under various parameter settings.
APA
Shen, Z., Fang, C., Zhao, P., Huang, J. & Qian, H.. (2019). Complexities in Projection-Free Stochastic Non-convex Minimization. Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 89:2868-2876 Available from https://proceedings.mlr.press/v89/shen19b.html.

Related Material