Fast Rates for Empirical Risk Minimization of Strict Saddle Problems

Alon Gonen, Shai Shalev-Shwartz
Proceedings of the 2017 Conference on Learning Theory, PMLR 65:1043-1063, 2017.

Abstract

We derive bounds on the sample complexity of empirical risk minimization (ERM) in the context of minimizing non-convex risks that admit the strict saddle property. Recent progress in non-convex optimization has yielded efficient algorithms for minimizing such functions. Our results imply that these efficient algorithms are statistically stable and also generalize well. In particular, we derive fast rates which resemble the bounds that are often attained in the strongly convex setting. We specify our bounds to Principal Component Analysis and Independent Component Analysis. Our results and techniques may pave the way for statistical analyses of additional strict saddle problems.

Cite this Paper

BibTeX
@InProceedings{pmlr-v65-gonen17a, title = {Fast Rates for Empirical Risk Minimization of Strict Saddle Problems}, author = {Gonen, Alon and Shalev-Shwartz, Shai}, booktitle = {Proceedings of the 2017 Conference on Learning Theory}, pages = {1043--1063}, year = {2017}, editor = {Kale, Satyen and Shamir, Ohad}, volume = {65}, series = {Proceedings of Machine Learning Research}, month = {07--10 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v65/gonen17a/gonen17a.pdf}, url = {https://proceedings.mlr.press/v65/gonen17a.html}, abstract = {We derive bounds on the sample complexity of empirical risk minimization (ERM) in the context of minimizing non-convex risks that admit the strict saddle property. Recent progress in non-convex optimization has yielded efficient algorithms for minimizing such functions. Our results imply that these efficient algorithms are statistically stable and also generalize well. In particular, we derive fast rates which resemble the bounds that are often attained in the strongly convex setting. We specify our bounds to Principal Component Analysis and Independent Component Analysis. Our results and techniques may pave the way for statistical analyses of additional strict saddle problems.} }
Endnote
%0 Conference Paper %T Fast Rates for Empirical Risk Minimization of Strict Saddle Problems %A Alon Gonen %A Shai Shalev-Shwartz %B Proceedings of the 2017 Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2017 %E Satyen Kale %E Ohad Shamir %F pmlr-v65-gonen17a %I PMLR %P 1043--1063 %U https://proceedings.mlr.press/v65/gonen17a.html %V 65 %X We derive bounds on the sample complexity of empirical risk minimization (ERM) in the context of minimizing non-convex risks that admit the strict saddle property. Recent progress in non-convex optimization has yielded efficient algorithms for minimizing such functions. Our results imply that these efficient algorithms are statistically stable and also generalize well. In particular, we derive fast rates which resemble the bounds that are often attained in the strongly convex setting. We specify our bounds to Principal Component Analysis and Independent Component Analysis. Our results and techniques may pave the way for statistical analyses of additional strict saddle problems.
APA
Gonen, A. & Shalev-Shwartz, S.. (2017). Fast Rates for Empirical Risk Minimization of Strict Saddle Problems. Proceedings of the 2017 Conference on Learning Theory, in Proceedings of Machine Learning Research 65:1043-1063 Available from https://proceedings.mlr.press/v65/gonen17a.html.

Related Material