Abstract
Projected Gradient Descent (PGD) is a cornerstone algorithm for constrained optimization. While its convergence to Mordukhovich (M-) stationary points on non-convex sets is well-established, this paper proves a significantly stronger result: accumulation points of PGD are Bouligand (B-) stationary. Furthermore, if the objective's gradient is locally Lipschitz continuous, these points are proximally (P-) stationary. These findings establish PGD as a robust method for reaching the strongest stationarity conditions theoretically possible in non-convex constrained optimization.
The Challenge of Non-Convex Constraints
In many modern applications—such as compressed sensing ($s$-sparse vectors) or matrix completion (low-rank matrices)—we minimize a smooth function $f$ over a non-convex set $C$. Because finding global minima in these settings is often NP-hard, researchers focus on finding stationary points.
However, "stationarity" is not a monolithic concept. In non-convex analysis, there is a hierarchy of conditions:
- Mordukhovich (M-) stationarity: The weakest condition, often including points that are clearly suboptimal.
- Bouligand (B-) stationarity: A stronger, necessary condition for local optimality.
- Proximal (P-) stationarity: The strongest of the three.
Closing the Theoretical Gap
Prior to this work, it was known that PGD sequences accumulate at M-stationary points. Whether they reached B-stationary points remained an open question for general closed sets. This paper closes that gap using sophisticated variational analysis.
The authors analyze PGD with non-monotone backtracking. Unlike standard PGD, which enforces a strict decrease in function value, non-monotone variants allow for temporary increases to navigate local hurdles, provided an Armijo-type condition is satisfied over time.
The core proof demonstrates that if an accumulation point were not B-stationary, the PGD map would force the algorithm to take steps of a non-vanishing size away from that point. This contradiction ensures that all accumulation points must satisfy the B-stationarity condition.
Key Insights
- The "Intelligence" of Projections: The simple act of projecting onto a closed set $C$ is sufficient to satisfy the regular normal cone conditions required for B-stationarity, even for geometrically complex or "nasty" sets.
- PGD vs. $P^2GD$: The study compares PGD with "Projected-Projected Gradient Descent" ($P^2GD$), which projects the gradient onto the tangent cone before projecting onto the set. Surprisingly, $P^2GD$ can fail to reach B-stationary points where PGD succeeds, suggesting that simpler algorithmic structures can be more theoretically robust.
- Apocalypse-Proofing: In optimization, an "apocalypse" refers to an algorithm converging to a point that appears stationary but is not. This paper proves PGD is "apocalypse-proof" regarding B-stationarity.
Results and Implications
The main result (Theorem 1.2) guarantees B-stationarity for any $C^1$ function on a closed set. If the gradient is locally Lipschitz, the result strengthens to P-stationarity. This has immediate practical relevance for algorithms used in machine learning and signal processing involving sparse vectors and restricted-rank matrices.
While this work establishes the quality of accumulation points, it does not guarantee convergence to a single point—a property typically requiring additional assumptions like the Kurdyka-Łojasiewicz (KŁ) property. Future research will focus on characterizing the rate of convergence and extending these results to more general proximal gradient frameworks.
Summary updated