PA-GD: On the convergence of perturbed alternating gradient descent to second-order stationary points for structured nonconvex optimization

Songtao Lu, Mingyi Hong, Zhengdao Wang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

Alternating gradient descent (A-GD) is a simple but popular algorithm in machine learning, which updates two blocks of variables in an alternating manner using gradient descent steps. In this paper, we consider a smooth unconstrained nonconvex optimization problem, and propose a perturbed A-GD (PA-GD) which is able to converge (with high probability) to the second-order stationary points (SOSPs) with a global sublinear rate. Existing analysis on A-GD type algorithm either only guarantees convergence to first-order solutions, or converges to second-order solutions asymptotically (without rates). To the best of our knowledge, this is the first alternating type algorithm that takes O(polylog(d)/∈#p2##p) iterations to achieve an (∈,√∈-SOSP with high probability, where polylog(d) denotes the polynomial of the logarithm with respect to problem dimension d.

Original languageEnglish (US)
Title of host publication36th International Conference on Machine Learning, ICML 2019
PublisherInternational Machine Learning Society (IMLS)
Pages7301-7327
Number of pages27
ISBN (Electronic)9781510886988
StatePublished - Jan 1 2019
Event36th International Conference on Machine Learning, ICML 2019 - Long Beach, United States
Duration: Jun 9 2019Jun 15 2019

Publication series

Name36th International Conference on Machine Learning, ICML 2019
Volume2019-June

Conference

Conference36th International Conference on Machine Learning, ICML 2019
CountryUnited States
CityLong Beach
Period6/9/196/15/19

Fingerprint Dive into the research topics of 'PA-GD: On the convergence of perturbed alternating gradient descent to second-order stationary points for structured nonconvex optimization'. Together they form a unique fingerprint.

  • Cite this

    Lu, S., Hong, M., & Wang, Z. (2019). PA-GD: On the convergence of perturbed alternating gradient descent to second-order stationary points for structured nonconvex optimization. In 36th International Conference on Machine Learning, ICML 2019 (pp. 7301-7327). (36th International Conference on Machine Learning, ICML 2019; Vol. 2019-June). International Machine Learning Society (IMLS).