# Gradient descent with nonconvex constraints: local concavity determines convergence

arXiv: https://arxiv.org/abs/1703.07755 · HTML: https://mlsanity.com/paper/1703.07755/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Mar 2017.

## Built on by (most cited first, 7 of 7)

- [Self-Stabilization: The Implicit Bias of Gradient Descent at the Edge of Stability](https://mlsanity.com/paper/2209.15594/) (2022)
- [Preferential Mixture-of-Experts: Interpretable Models that Rely on Human Expertise as much as Possible](https://mlsanity.com/paper/2101.05360/) (2021)
- [Tensor-on-Tensor Regression: Riemannian Optimization, Over-parameterization, Statistical-computational Gap, and Their Interplay](https://mlsanity.com/paper/2206.08756/) (2022)
- [Strictly Constrained Generative Modeling via Split Augmented Langevin Sampling](https://mlsanity.com/paper/2505.18017/) (2025)
- [Stochastic Mirror Descent for Large-Scale Sparse Recovery](https://mlsanity.com/paper/2210.12882/) (2022)
- [Adaptive Iterative Soft-Thresholding Algorithm with the Median Absolute Deviation](https://mlsanity.com/paper/2507.02084/) (2025)
- [An Automated Tip-and-Cue Framework for Optimized Satellite Tasking and Visual Intelligence](https://mlsanity.com/paper/2512.09670/) (2025)

## Abstract (arXiv)

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.