CaltechAUTHORS
  A Caltech Library Service

Finding stationary points on bounded-rank matrices: a geometric hurdle and a smooth remedy

Levin, Eitan and Kileel, Joe and Boumal, Nicolas (2022) Finding stationary points on bounded-rank matrices: a geometric hurdle and a smooth remedy. Mathematical Programming . ISSN 0025-5610. doi:10.1007/s10107-022-01851-2. (In Press) https://resolver.caltech.edu/CaltechAUTHORS:20220722-768747000

[img] PDF - Accepted Version
See Usage Policy.

522kB

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20220722-768747000

Abstract

We consider the problem of provably finding a stationary point of a smooth function to be minimized on the variety of bounded-rank matrices. This turns out to be unexpectedly delicate. We trace the difficulty back to a geometric obstacle: On a nonsmooth set, there may be sequences of points along which standard measures of stationarity tend to zero, but whose limit points are not stationary. We name such events apocalypses, as they can cause optimization algorithms to converge to non-stationary points. We illustrate this explicitly for an existing optimization algorithm on bounded-rank matrices. To provably find stationary points, we modify a trust-region method on a standard smooth parameterization of the variety. The method relies on the known fact that second-order stationary points on the parameter space map to stationary points on the variety. Our geometric observations and proposed algorithm generalize beyond bounded-rank matrices. We give a geometric characterization of apocalypses on general constraint sets, which implies that Clarke-regular sets do not admit apocalypses. Such sets include smooth manifolds, manifolds with boundaries, and convex sets. Our trust-region method supports parameterization by any complete Riemannian manifold.


Item Type:Article
Related URLs:
URLURL TypeDescription
https://doi.org/10.1007/s10107-022-01851-2DOIArticle
https://rdcu.be/cSdX8PublisherFree ReadCube access
https://arxiv.org/abs/2107.03877arXivDiscussion Paper
Additional Information:© Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society 2022. Received: 15 July 2021 / Accepted: 5 June 2022. Part of this work was conducted while all three authors were affiliated with the mathematics department and PACM at Princeton University.
DOI:10.1007/s10107-022-01851-2
Record Number:CaltechAUTHORS:20220722-768747000
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20220722-768747000
Official Citation:Levin, E., Kileel, J. & Boumal, N. Finding stationary points on bounded-rank matrices: a geometric hurdle and a smooth remedy. Math. Program. (2022). https://doi.org/10.1007/s10107-022-01851-2
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:115766
Collection:CaltechAUTHORS
Deposited By: George Porter
Deposited On:25 Jul 2022 22:44
Last Modified:25 Jul 2022 22:44

Repository Staff Only: item control page