Clarke subgradients of stratifiable functions

Jérôme Bolte, Aris Daniilidis, Adrian S. Lewis, Masahiro Shiota

In the landscape of modern optimization, many objective functions are "nonsmooth," possessing kinks, jumps, or sharp corners where traditional derivatives fail to exist. This paper provides a foundational bridge between the "wild" world of nonsmooth analysis and the "tame" world of differential geometry. By leveraging Whitney stratifications, the authors demonstrate that even when a function lacks a traditional gradient, its subgradients behave predictably relative to the smooth manifolds (strata) that constitute its underlying structure.

The Challenge of Nonsmoothness

Classical optimization relies on the gradient ($\nabla f$) to navigate toward minima. However, modern applications—ranging from machine learning with ReLU activations to compressed sensing—frequently involve functions like $|x|$ that are not differentiable everywhere. In these cases, researchers use subgradients (specifically Clarke subdifferentials) to characterize the function's local behavior.

The difficulty lies in the potential for nonsmooth functions to be pathologically "messy." Without a governing structure, it is nearly impossible to guarantee that an optimization algorithm, such as gradient descent, will not oscillate indefinitely or become trapped in non-optimal regions. This paper addresses this by focusing on stratifiable functions: functions whose graphs can be decomposed into a collection of smooth "pieces" (strata) that meet according to specific regularity conditions.

Methodology: Variational Analysis Meets Differential Geometry

The authors' approach combines several sophisticated mathematical frameworks:

  1. Whitney Stratification: The function's graph is partitioned into a finite number of smooth manifolds (points, lines, and surfaces). This ensures that the function is locally smooth if one restricts their view to a single stratum.
  2. O-minimal Structures: To prevent "infinite wiggling" (such as the behavior of $x^2 \sin(1/x)$ near the origin), the authors work within o-minimal structures. This framework from mathematical logic describes "tame" geometry, encompassing semialgebraic and subanalytic functions.
  3. The Projection Formula: The core technical innovation is a formula demonstrating that projecting a Clarke subgradient onto the tangent space of the stratum containing a point recovers the standard Riemannian gradient along that stratum.

Key Insights: The Steepness Bound

The most significant insight of the work is the establishment of a steepness bound. The authors prove that the norm of the gradient of $f$ relative to the stratum containing a point $x$ serves as a lower bound for the norms of all Clarke subgradients at that point.

Essentially, the "steepness" of a nonsmooth function (measured by its subgradients) is always at least as great as the steepness of the smooth manifold it resides upon. This geometric-variational link ensures that the analytical concept of a "critical point" in nonsmooth analysis aligns perfectly with the geometric concept of a point where the gradient along a stratum is zero.

Major Results

Nonsmooth Morse-Sard Theorem

The authors establish that for stratifiable functions, the set of "critical values"—the function values at which the slope is zero—is small (specifically, it has Lebesgue measure zero). This implies that an optimizer is unlikely to be "stuck" at an arbitrary height without a geometric reason.

Nonsmooth Kurdyka-Łojasiewicz (KL) Inequality

Perhaps the paper's most influential result is the extension of the KL inequality to the nonsmooth, definable setting. The KL inequality relates a function's value to the magnitude of its gradient (or subgradient). In modern optimization, this inequality is the standard tool used to prove that algorithms like Proximal Gradient Descent converge to a single point rather than oscillating or diverging.

Limitations and Scope

While the results are robust, they rely on the function being "definable" in an o-minimal structure. While this covers the vast majority of functions used in engineering and machine learning (including polynomials, absolute values, and ReLUs), it excludes functions with essential singularities or infinite oscillations. Additionally, the authors note that these results do not necessarily extend to broader "convex-stable" subdifferentials unless the function is locally Lipschitz continuous, suggesting a boundary to how far these geometric techniques can be pushed into more exotic nonsmooth domains.

Summary updated

Abstract

We establish the following result: if the graph of a (nonsmooth) real-extended-valued function $f:\mathbb{R}^{n}\to \mathbb{R}\cup\{+\infty\}$ is closed and admits a Whitney stratification, then the norm of the gradient of $f$ at $x\in{dom}f$ relative to the stratum containing $x$ bounds from below all norms of Clarke subgradients of $f$ at $x$. As a consequence, we obtain some Morse-Sard type theorems as well as a nonsmooth Kurdyka-Łojasiewicz inequality for functions definable in an arbitrary o-minimal structure.
BibTeX
@article{bolte2007clarke,
  author = {Jérôme Bolte and Aris Daniilidis and Adrian S. Lewis and Masahiro Shiota},
  title = {{Clarke subgradients of stratifiable functions}},
  journal = {SIAM J. Optim.},
  year = {2007},
  doi = {10.1137/060670080},
}
Figure