Low-rank optimization methods based on projected projected-gradient descent that accumulate at Bouligand stationary points

Abstract

This paper considers the problem of minimizing a differentiable function with locally Lipschitz continuous gradient on the algebraic variety of real matrices of upper-bounded rank. This problem is known to enable the formulation of various machine learning or signal processing tasks such as dimensionality reduction, collaborative filtering, and signal recovery. Several definitions of stationarity exist for this nonconvex problem. Among them, Bouligand stationarity is the strongest necessary condition for local optimality. This paper proposes two first-order methods that generate a sequence in the variety whose accumulation points are Bouligand stationary. The first method combines the well-known projected projected-gradient descent map with a rank reduction mechanism. The second method is a hybrid of projected gradient descent and projected projected-gradient descent. Both methods stand out in the field of low-rank optimization methods when considering their convergence properties, their streamlined design, their typical computational cost per iteration, and their empirically observed numerical performance. The theoretical framework used to analyze the proposed methods is of independent interest.

The main changes with respect to the first version are listed in section 1.3

References in corpus (17)

• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Global convergence of splitting methods for nonconvex composite optimization
• Low-rank optimization for semidefinite convex problems
• A New Approach to Collaborative Filtering: Operator Estimation with Spectral Regularization
• Low-Rank Matrix Approximation with Weights or Missing Data is NP-hard
• A Geometric Approach to Dynamical Model-Order Reduction
• Extrapolated Proximal Subgradient Algorithms for Nonconvex and Nonsmooth Fractional Programs
• A Riemannian rank-adaptive method for low-rank matrix completion
• 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
• 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
• Comparison of an Apocalypse-Free and an Apocalypse-Prone First-Order Low-Rank Optimization Algorithm
• Gauss-Southwell type descent methods for low-rank matrix optimization
• Optimization over bounded-rank matrices through a desingularization enables joint global and local guarantees

Cited by in corpus (2)

• Finding stationary points on bounded-rank matrices: A geometric hurdle and a smooth remedy
• Low-rank optimization methods based on projected projected-gradient descent that accumulate at Bouligand stationary points