TL;DR
This paper provides a major theoretical upgrade for the Projected Gradient Descent (PGD) algorithm. The authors prove that PGD accumulation points are Bouligand (B-) stationary—and even proximally (P-) stationary if the gradient is Lipschitz—which are the strongest stationarity conditions one can hope for when optimizing over non-convex sets.
What Problem Does This Paper Address?
In mathematical optimization, we often want to minimize a smooth function $f$ over a set $C$. When $C$ is non-convex (like the set of sparse vectors or low-rank matrices), finding a global or even a local minimum is often computationally intractable (NP-hard). Instead, we settle for finding a stationary point.
However, "stationarity" isn't a single definition; it's a spectrum.
- Mordukhovich (M-) stationarity is the weakest; it's easy to satisfy but often includes points that are clearly not optimal.
- Bouligand (B-) stationarity is stronger and is a necessary condition for local optimality.
- Proximal (P-) stationarity is the strongest of the three.
Until this paper, it was well-known that PGD converges to M-stationary points, but whether it reached the more desirable B-stationary points remained an open question for general non-convex sets. This paper closes that gap.
Methods
The authors analyze a standard version of the PGD algorithm that uses non-monotone backtracking. Unlike simple PGD, which requires the function value to decrease at every step, non-monotone versions allow the function value to increase slightly (based on a "max" or "average" of recent values) to help escape local hurdles, provided an Armijo-type condition is eventually met.
The core of the proof relies on variational analysis. The authors dissect the "PGD map"—the process of taking a step and projecting back onto the set. They prove that if an accumulation point is not B-stationary, the algorithm would be forced to take steps of a minimum "size" away from that point, contradicting the definition of an accumulation point.
Datasets
As a theoretical mathematics paper, no empirical datasets were used. The authors instead validate their findings through rigorous proofs and a comparative analytical example in Section 8.
Key Insights and Ideas
- The Power of the Projection: The paper shows that the simple act of projecting onto a closed set $C$ is "smart" enough to satisfy the regular normal cone conditions required for B-stationarity, even when the set $C$ is quite "nasty" (non-smooth and non-convex).
- PGD vs. $P^2GD$: The authors compare PGD with "Projected-Projected Gradient Descent" ($P^2GD$). Surprisingly, they show that $P^2GD$—which projects the gradient onto the tangent cone before projecting the result onto the set—can actually fail to reach B-stationary points where PGD succeeds. This highlights that "more complex" isn't always "better" in algorithm design.
- Practical Relevance: The results apply directly to sets used in modern machine learning and signal processing, such as:
- $s$-sparse vectors (used in compressed sensing).
- Low-rank matrices (used in matrix completion).
- Positive-semidefinite matrices of restricted rank.
Key Results
- Theorem 1.2 (The Main Result): For a $C^1$ function $f$ on a closed set $C$, every accumulation point of a sequence generated by PGD is B-stationary.
- Stronger Stationarity: If the gradient $\nabla f$ is locally Lipschitz continuous, these accumulation points are proven to be P-stationary.
- Apocalypse Avoidance: In optimization theory, an "apocalypse" occurs when an algorithm converges to a point that looks stationary according to standard measures but actually isn't. This paper proves that PGD is "apocalypse-proof" regarding B-stationarity.
Limitations and Future Work
- Convergence to a Single Point: The paper proves that accumulation points are stationary, but it does not guarantee that the algorithm converges to a single point. To prove that, one would typically need additional assumptions like the Kurdyka-Łojasiewicz (KŁ) property.
- Rate of Convergence: While the paper establishes where the algorithm goes, it doesn't analyze how fast it gets there. The authors note that rate characterization remains an important area for future research.
- Extension to Proximal Gradient: The authors suggest that extending these results to the general proximal gradient algorithm (where the objective is a sum of a smooth and a non-smooth function) would require significant new adaptations of their techniques.
Summary updated