Neighborhood Averaged Stationarity in Nonsmooth Optimization

33 concepts23 papers1 proposal

In classical optimization, we rely on a simple compass to find the bottom of a valley: the gradient. For a smooth function, if the gradient norm $\|\nabla f(x)\|$ is close to zero, we know we are near a stationary point (a local minimum, maximum, or saddle point). This metric forms the bedrock of convergence guarantees for nearly all standard first-order algorithms.

But modern machine learning frequently forces us into landscapes that are decidedly not smooth. Neural networks with ReLU activations, max-pooling layers, and robust control objectives introduce sharp "kinks" and discontinuities where gradients are either undefined or change abruptly.

If you try to apply standard stationarity metrics to these functions, the mathematics completely breaks down. This article explains why classical stationarity fails in nonsmooth landscapes and how a relaxed, neighborhood-based framework—known as Goldstein stationarity—provides a mathematically rigorous and algorithmically actionable way forward.


The Breakdown of Classical Stationarity

To understand why we need a new definition of stationarity, consider the simplest possible nonsmooth function: the absolute value function, $f(x) = |x|$.

The global minimum is at $x = 0$. However, at $x = 0$, the gradient does not exist. At any point arbitrarily close to zero, the gradient is either $+1$ (if $x > 0$) or $-1$ (if $x < 0$). If we set a target threshold of finding a point where $\|\nabla f(x)\| \le \epsilon$ for a small $\epsilon < 1$, an optimization algorithm will search forever. It can never satisfy this condition, even if it lands directly on or oscillates tightly around the true minimum.

As highlighted by Johansson et al. and Hu et al., this lack of a reliable, continuous stationarity measure makes it incredibly difficult to derive finite-time convergence rates or sample complexity bounds for nonconvex, nonsmooth problems. In fact, Kornowski et al. proved a fundamental impossibility result: for general nonsmooth functions, it is mathematically impossible for any finite-time deterministic algorithm to guarantee finding a point with a small subgradient.


Zooming Out: The Goldstein Subdifferential

If evaluating the gradient at a single point fails, the natural alternative is to look at a local neighborhood. This is the core intuition behind the Goldstein subdifferential.

Instead of asking, "Is the gradient small at this exact point?", we ask, "If I look at all the gradients in a small neighborhood around this point, can I combine them to cancel each other out?"

Formally, for a function $f$ and a neighborhood radius $\delta > 0$, the $\delta$-Goldstein subdifferential $\partial_\delta f(x)$ is the convex hull of all gradients computed at differentiable points within a distance $\delta$ of $x$:

$$\partial_\delta f(x) = \text{conv}\left\{ \nabla f(y) : \|y - x\| \le \delta \right\}$$

A point $x$ is said to be an $(\delta, \epsilon)$-Goldstein stationary point if the zero vector is within $\epsilon$-distance of this convex hull:

$$0 \in \partial_\delta f(x) + B_\epsilon(0)$$

Visualizing the Convex Hull

Let's return to $f(x) = |x|$ at the kink $x = 0$. If we choose any neighborhood radius $\delta > 0$, the neighborhood $[-\delta, \delta]$ contains points with gradient $-1$ and points with gradient $+1$.

The convex hull of the set $\{-1, 1\}$ is the entire interval $[-1, 1]$. Because the number $0$ lies squarely inside this interval, $x = 0$ is perfectly Goldstein stationary. The opposing gradients on either side of the kink "cancel out," certifying that the neighborhood as a whole has reached a stable equilibrium.

As So et al. note, this framework provides an algorithm-independent criterion for certifying approximate optimality in finite time, bypassing the need to land precisely on non-differentiable boundaries.


Why It Works: The Geometry of Smoothing

Goldstein stationarity is not just an abstract geometric definition; it is deeply tied to how algorithms practically smooth out jagged landscapes.

Imagine convolving a jagged function $f(x)$ with a uniform noise ball of radius $\delta$. This operation yields a smoothed function, $f_\delta(x)$. The gradient of this smoothed function, $\nabla f_\delta(x)$, is effectively a weighted average of the gradients of the original function within that $\delta$-neighborhood.

Because any average is a convex combination, the smoothed gradient $\nabla f_\delta(x)$ is guaranteed to lie inside the Goldstein subdifferential $\partial_\delta f(x)$. Lin et al. established a rigorous theoretical link showing that minimizing a uniformly smoothed function is mathematically equivalent to hunting for Goldstein stationary points.

Nonsmooth Landscape [f(x)]  ───(Randomized Smoothing)───>  Smoothed Landscape [f_δ(x)]
         │                                                              │
         ▼                                                              ▼
Goldstein Stationarity      <───────────────────────────────   Standard Stationarity
(Zero in local convex hull)                                    (Small smoothed gradient)

This geometric link explains why zeroth-order (derivative-free) optimization methods are so effective for nonsmooth functions. In black-box settings where gradients are unavailable or ill-defined, algorithms can estimate gradients by perturbing the inputs with local random noise.

Papers by Lei et al. and Liu et al. leverage this exact mechanism. By evaluating function values in a local neighborhood, their algorithms implicitly track the gradient of the smoothed function, steering the iterates directly toward Goldstein stationary regions.


The Necessity of Randomization

Why do so many algorithms targeting Goldstein stationarity rely on randomness?

Jordan et al. proved that randomization is a fundamental necessity for dimension-free nonsmooth optimization. If an algorithm is purely deterministic, an adversary can always construct a nonsmooth landscape where the algorithm gets trapped or requires an exponential number of queries relative to the dimension $d$. To escape this curse of dimensionality deterministically, an algorithm must possess explicit "white-box" knowledge of the function's internal structure—such as the exact polyhedral geometry of a two-layer ReLU network explored by Yun et al..

By introducing randomness (e.g., randomized line searches or stochastic perturbations), algorithms can blindly sample the neighborhood, ensuring they capture a representative set of gradients to form the convex hull without paying a steep dimension-dependent price.


Modern Applications and Frontiers

By providing a tractable convergence target, Goldstein stationarity has unlocked finite-time guarantees across several complex domains:

  • Optimal Sample Complexity: By framing nonconvex optimization as a sequence of online learning problems with shifting regret bounds, Cutkosky et al. and Sahinoglu et al. proved that algorithms can find Goldstein stationary points with an optimal sample complexity of $O(\epsilon^{-3})$, matching the best-known rates for smooth optimization.
  • Robust Control: In structured $\mathcal{H}_\infty$ control, the objective functions are notoriously nonconvex and nonsmooth. Guo et al. and the authors utilized randomized smoothing to provide the first model-free policy optimization guarantees for these systems.
  • Privacy and Constraints: Goldstein stationarity has been adapted to handle Differential Privacy (DP), where Kornowski et al. and Zhang et al. used neighborhood averaging to inject privacy-preserving noise safely. It has also been extended to constrained tasks via projection-free Frank-Wolfe variants (Liu et al.), bilevel optimization (Kornowski et al.), and even quantum optimization settings (Guan et al.).
  • Manifold Optimization: When optimizing nonsmooth functions over curved spaces, tangent spaces change from point to point. Sahinoglu et al. extended Goldstein stationarity to Riemannian manifolds by using parallel transport to pull gradients from a local neighborhood back to a single tangent space, proving that curved geometries can still achieve Euclidean-level convergence rates.

Conclusion

Goldstein stationarity shifts our perspective from a single, hyper-local point to a broader, neighborhood-based view. By defining stability as the ability of surrounding gradients to collectively balance one another out, it provides the mathematical foundation required to analyze and optimize the complex, nonsmooth models that dominate modern machine learning.

Key Foundational Work

Anderson Acceleration of Proximal Gradient Methods (2020) — contributed 1 concept elements to this direction.
Efficiently testing local optimality and escaping saddles for ReLU networks (2019) — contributed 1 concept elements to this direction.
Perturbed Proximal Descent to Escape Saddle Points for Non-convex and Non-smooth Objective Functions (2019) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_goldstein_stationarity_a7e85482,
  title = {Goldstein stationarity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/goldstein-stationarity/rdr_a7e85482e9e4461996bdc1d2c7a30509},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_goldstein_stationarity_a7e85482_v1,
  title = {Goldstein stationarity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/goldstein-stationarity/rdr_a7e85482e9e4461996bdc1d2c7a30509/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake