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

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.

The arXiv version contains a few details omitted in the published version Math. Program. (2022)

References in corpus (10)

• A Riemannian rank-adaptive method for low-rank matrix completion
• Beyond Procrustes: Balancing-Free Gradient Descent for Asymmetric Low-Rank Matrix Sensing
• Finding stationary points on bounded-rank matrices: A geometric hurdle and a smooth remedy
• Fast Global Convergence for Low-rank Matrix Recovery via Riemannian Gradient Descent with Random Initialization
• An apocalypse-free first-order low-rank optimization algorithm with at most one rank reduction attempt per iteration
• On the continuity of the tangent cone to the determinantal variety
• Low-rank optimization methods based on projected projected-gradient descent that accumulate at Bouligand stationary points
• Asymptotic Escape of Spurious Critical Points on the Low-rank Matrix Manifold
• An Augmented Lagrangian Method for Optimization Problems with Structured Geometric Constraints
• Low-rank matrix recovery with non-quadratic loss: projected gradient method and regularity projection oracle

Cited by in corpus (7)

• Finding stationary points on bounded-rank matrices: A geometric hurdle and a smooth remedy
• The effect of smooth parametrizations on nonconvex optimization landscapes
• An apocalypse-free first-order low-rank optimization algorithm with at most one rank reduction attempt per iteration
• Projected gradient descent accumulates at Bouligand stationary points
• Low-rank optimization methods based on projected projected-gradient descent that accumulate at Bouligand stationary points
• A Proximal Variable Smoothing for Nonsmooth Minimization Involving Weakly Convex Composite with MIMO Application
• An Approximate Projection onto the Tangent Cone to the Variety of Third-Order Tensors of Bounded Tensor-Train Rank