Projected gradient descent accumulates at Bouligand stationary points

Guillaume Olikier, Irène Waldspurger

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:

  1. Mordukhovich (M-) stationarity: The weakest condition, often including points that are clearly suboptimal.
  2. Bouligand (B-) stationarity: A stronger, necessary condition for local optimality.
  3. Proximal (P-) stationarity: The strongest of the three.
Decomposition of the normal cone at a non-convex point $(0,0)$ on set $C$.

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

Abstract

This paper considers the projected gradient descent (PGD) algorithm for the problem of minimizing a continuously differentiable function on a nonempty closed subset of a Euclidean vector space. Without further assumptions, this problem is intractable and algorithms are only expected to find a stationary point. PGD generates a sequence in the set whose accumulation points are known to be Mordukhovich stationary. In this paper, these accumulation points are proven to be Bouligand stationary, and even proximally stationary if the gradient is locally Lipschitz continuous. These are the strongest stationarity properties that can be expected for the considered problem.
BibTeX
@article{olikier2025projected,
  author = {Guillaume Olikier and Irène Waldspurger},
  title = {{Projected gradient descent accumulates at Bouligand stationary points}},
  journal = {SIAM J. Optim.},
  year = {2025},
  doi = {10.1137/24m1692782},
}
Figure