Gradient descent with non-convex constraints: local concavity determines convergence

• Published in: Information and inference 2018-12, Vol.7 (4), p.755-806
• Main Authors: Barber, Rina Foygel, Ha, Wooseok
• Format: Article
• Language: English
• ISSN: 2049-8764; 2049-8772
• DOI: 10.1093/imaiai/iay002

Many problems in high-dimensional statistics and optimization involve minimization over non-convex constraints—for instance, a rank constraint for a matrix estimation problem—but little is known about the theoretical properties of such optimization problems for a general non-convex constraint set. In this paper we study the interplay between the geometric properties of the constraint set and the convergence behavior of gradient descent for minimization over this set. We develop the notion of local concavity coefficients of the constraint set, measuring the extent to which convexity is violated, which governs the behavior of projected gradient descent over this set. We demonstrate the versatility of these concavity coefficients by computing them for a range of problems in low-rank estimation, sparse estimation and other examples. Through our understanding of the role of these geometric properties in optimization, we then provide a convergence analysis when projections are calculated only approximately, leading to a more efficient method for projected gradient descent in low-rank estimation problems.