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 language | English (US) |
---|---|
Title of host publication | 36th International Conference on Machine Learning, ICML 2019 |
Publisher | International Machine Learning Society (IMLS) |
Pages | 7301-7327 |
Number of pages | 27 |
ISBN (Electronic) | 9781510886988 |
State | Published - 2019 |
Event | 36th International Conference on Machine Learning, ICML 2019 - Long Beach, United States Duration: Jun 9 2019 → Jun 15 2019 |
Publication series
Name | 36th International Conference on Machine Learning, ICML 2019 |
---|---|
Volume | 2019-June |
Conference
Conference | 36th International Conference on Machine Learning, ICML 2019 |
---|---|
Country/Territory | United States |
City | Long Beach |
Period | 6/9/19 → 6/15/19 |
Bibliographical note
Publisher Copyright:© 36th International Conference on Machine Learning, ICML 2019. All rights reserved.