Projected Gradient Descent Accumulates at Bouligand Stationary Points

Guillaume Olikier, Irène Waldspurger

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.

  1. Mordukhovich (M-) stationarity is the weakest; it's easy to satisfy but often includes points that are clearly not optimal.
  2. Bouligand (B-) stationarity is stronger and is a necessary condition for local optimality.
  3. 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

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},
}

Loading related content...

Figure