Characterizing Parametric and Convergence Stability in Nonconvex and Nonsmooth Optimizations: A Geometric Approach

Xiaotie Deng, Hanyu Li, Ningyuan Li

TL;DR

This paper provides a rigorous geometric foundation for understanding convergence in nonsmooth, nonconvex optimization—the kind typically found in deep learning. The authors prove a "Convergence Lemma" showing that approximate stationary points (where the "gradient" is nearly zero) must cluster around isolated local minima as numerical errors vanish, and they establish that isolated local minima are the only stationary points that remain stable under small numerical perturbations.

What Problem Does This Paper Address?

In classical smooth optimization, we have a clear intuition: if the gradient is small, you are close to a stationary point. If the function is strongly convex, you are close to the unique global minimum. However, deep learning involves functions that are both nonconvex and nonsmooth (due to operations like ReLU, max-pooling, and absolute values).

For these "messy" functions, standard intuition often fails. Subdifferentials (the nonsmooth version of gradients) can be discontinuous, meaning an "almost stationary" point might be nowhere near an actual stationary point. This creates a gap between theoretical optimization and practical implementation, where numerical errors are inevitable. The authors seek to answer: Under what conditions does an optimizer actually "stay" near a local minimum, and what is the geometric structure of these stationary points?

Methods

The authors employ tools from Real Algebraic Geometry, specifically the study of semi-analytic and sub-analytic sets.

  1. Canonical Representation: They first show that functions composed of analytic mappings (like convolutions or linear layers) and the maximum operator (like ReLU or pooling) can be rewritten in a canonical form using absolute value operators.
  2. Stratification: They use Whitney Stratification and Lojasiewicz’s theorems to partition the function's domain into a finite number of "well-behaved" regions (manifolds). This allows them to analyze the limit behavior of sequences of points by looking at how these manifolds fit together.
  3. Geometric Characterization: By treating the set of stationary points as a sub-analytic set, they prove it has a structured "backbone" composed of a finite union of connected manifolds.

Datasets

Not discussed in the paper. This is a theoretical mathematical study; no empirical datasets or benchmarks were used.

Key Insights and Ideas

  • The Necessity of Analyticity: One of the most striking findings is that being "infinitely differentiable" ($C^\infty$) is not enough. The authors provide counterexamples showing that for $C^\infty$ functions, approximate stationary points can stay far away from the actual minimum even as the error $\delta$ goes to zero. The "rigidity" of analytic functions (which are equal to their Taylor series) is the essential ingredient that makes the Convergence Lemma hold.
  • Stationary Points are Manifolds: Stationary points aren't just random dots; they form a finite union of connected analytic manifolds. On each of these connected components, the function value is constant.
  • Defining Convergence Stability: The authors introduce a formal definition of "convergence stability." It asks: if an algorithm is "reasonable" (it decreases the function value and limits step size), will it stay near a point $x^*$ despite small numerical errors?
  • The "Isolated Minimum" Rule: They prove that a stationary point is convergence-stable if and only if it is an isolated local minimum. Saddle points and non-isolated minima are inherently unstable in this nonsmooth regime.

Key Results

  • Theorem 1.1 (Convergence Lemma): For piecewise analytic functions, the set of $\delta$-stationary points in the neighborhood of an isolated local minimum $x^*$ shrinks to $\{x^*\}$ as $\delta \to 0$. This justifies using approximate gradients in practice.
  • Theorem 1.2 (Geometric Characterization): The set of all stationary points is a finite union of connected sub-analytic manifolds.
  • Theorem 1.3 (Stability Equivalence): A stationary point $x^*$ is convergence-stable if and only if it is an isolated local minimum. This provides a "where-to-converge" guarantee for nonsmooth nonconvex optimization.

Limitations and Future Work

  • Qualitative vs. Quantitative: The results are primarily qualitative. While the paper proves that the set of $\delta$-stationary points shrinks, it doesn't provide a specific rate (e.g., is it linear or exponential?) for how fast it shrinks relative to $\delta$.
  • Complexity of Calculation: While the paper provides a method to calculate stability parameters (Corollary 6.1), the authors admit that for most real-world functions, this calculation is currently "cumbersome."
  • Deterministic Focus: The current work focuses on deterministic algorithms. The authors suggest that incorporating probabilistic considerations (like Gaussian noise instead of a fixed radius error) would be a valuable next step to align with "smoothed analysis" in computer science.

Summary updated

Abstract

In this work, a convergence lemma for function $f$ being finite compositions of analytic mappings and the maximum operator is proved. The lemma shows that the set of $\delta$-stationary points near an isolated local minimum point $x^*$ is shrinking to $x^*$ as $\delta\to 0$. It is a natural extension of the version for strongly convex $C^1$ functions. However, the correctness of the lemma is subtle. Analytic mappings are necessary for the lemma in the sense that replacing it with differentiable or $C^\infty$ mappings makes the lemma false. The proof is based on stratification theorems of semi-analytic sets by {\L}ojasiewicz. An extension of this proof presents a geometric characterization of the set of stationary points of $f$. Finally, a notion of stability on stationary points, called convergence stability, is proposed. It asks, under small numerical errors, whether a reasonable convergent optimization method started near a stationary point should eventually converge to the same stationary point. The concept of convergence stability becomes nontrivial qualitatively only when the objective function is both nonsmooth and nonconvex. Via the convergence lemma, an intuitive equivalent condition for convergence stability of $f$ is proved. These results together provide a new geometric perspective to study the problem of "where-to-converge" in nonsmooth nonconvex optimization.
BibTeX
@misc{deng2022characterizing,
  author = {Xiaotie Deng and Hanyu Li and Ningyuan Li},
  title = {{Characterizing Parametric and Convergence Stability in Nonconvex and Nonsmooth Optimizations: A Geometric Approach}},
  year = {2022},
  eprint = {2204.01643},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2204.01643},
}
Figure