Over-parametrization via Lifting for Low-rank Matrix Sensing: Conversion of Spurious Solutions to Strict Saddle Points
This addresses a fundamental issue in non-convex optimization for researchers and practitioners, offering a novel theoretical insight into escaping spurious solutions, though it is incremental in building on existing over-parametrization techniques.
The paper tackles the problem of spurious solutions in non-convex optimization for low-rank matrix sensing by proposing an infinite hierarchy of over-parametrized problems, showing that spurious solutions become strict saddle points that can be escaped via local search methods, with a derived bound on the required over-parametrization.
This paper studies the role of over-parametrization in solving non-convex optimization problems. The focus is on the important class of low-rank matrix sensing, where we propose an infinite hierarchy of non-convex problems via the lifting technique and the Burer-Monteiro factorization. This contrasts with the existing over-parametrization technique where the search rank is limited by the dimension of the matrix and it does not allow a rich over-parametrization of an arbitrary degree. We show that although the spurious solutions of the problem remain stationary points through the hierarchy, they will be transformed into strict saddle points (under some technical conditions) and can be escaped via local search methods. This is the first result in the literature showing that over-parametrization creates a negative curvature for escaping spurious solutions. We also derive a bound on how much over-parametrization is requited to enable the elimination of spurious solutions.