Optimization over bounded-rank matrices through a desingularization enables joint global and local guarantees
For researchers in optimization and machine learning, this work provides a principled framework that simultaneously guarantees global and local convergence for bounded-rank matrix optimization, addressing a known gap in existing methods.
The paper addresses the challenge of optimization over bounded-rank matrices, which is difficult due to the nonsmooth and nonconvex nature of the feasible set. By developing a Riemannian geometry based on a desingularization, they achieve both global convergence to stationary points and fast local convergence, with performance comparable to existing methods on matrix completion tasks.
Convergence guarantees for optimization over bounded-rank matrices are delicate to obtain because the feasible set is a nonsmooth and nonconvex algebraic variety. Existing techniques include direct optimization over bounded-rank matrices (e.g., projected gradient descent), fixed-rank optimization (over the maximal-rank stratum), and the LR parameterization. They all lack either global guarantees (the ability to accumulate only at stationary points) or fast local convergence (e.g., if the limit has non-maximal rank). We study a lifted geometry that allows algorithms to enjoy both. Khrulkov and Oseledets [2018] parameterize the bounded-rank variety via a desingularization to recast the optimization problem onto a smooth manifold. Building on their ideas, we develop a Riemannian geometry for this desingularization, also with care for numerical considerations. We use it to ensure conditions that, for many standard algorithms, yield global convergence to stationary points with fast local rates. On matrix completion tasks, we find that this approach is comparable to others.