Gradient descent with nonconvex constraints: local concavity determines convergence
arXiv:1703.07755
Abstract
Many problems in high-dimensional statistics and optimization involve minimization over nonconvex 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 nonconvex 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 govern 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.
References in corpus (6)
- Nearly unbiased variable selection under minimax concave penalty
- Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees
- Regularized M-estimators with nonconvexity: Statistical and algorithmic theory for local optima
- Low-rank Solutions of Linear Matrix Equations via Procrustes Flow
- Global Optimality in Low-rank Matrix Optimization
- Guaranteed Rank Minimization via Singular Value Projection