Gradient descent with nonconvex constraints: local concavity determines convergence

Understand

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.