On Convergence Lemma and Convergence Stability for Piecewise Analytic Functions

Xiaotie Deng, Hanyu Li, Ningyuan Li

Abstract

In the landscape of modern optimization, particularly within deep learning, functions are rarely smooth or convex. This paper establishes a rigorous theoretical foundation for optimization in these "messy" environments by focusing on piecewise analytic functions—those formed by the composition of analytic mappings and the maximum operator. The authors prove a fundamental Convergence Lemma, showing that for this class of functions, the set of $\delta$-stationary points near an isolated local minimum $x^*$ shrinks to $x^*$ as the tolerance $\delta$ approaches zero. This result is shown to be unique to analytic mappings; the lemma fails if the functions are merely $C^\infty$. Furthermore, the paper introduces the concept of convergence stability, proving that a stationary point is stable under numerical noise if and only if it is an isolated local minimum. These results provide a new geometric perspective on the "where-to-converge" problem in non-smooth, non-convex optimization.

Introduction

Classical optimization theory relies heavily on the well-behaved nature of smooth ($C^1$) or convex functions. However, the architectures driving modern artificial intelligence—utilizing ReLU activations, max-pooling, and attention mechanisms—are neither smooth nor convex. These functions are better described as "piecewise analytic." In such landscapes, traditional intuition often fails because the subdifferential (the non-smooth equivalent of a gradient) can be discontinuous. This creates a risk: an optimizer might find a point where the gradient is nearly zero (a $\delta$-stationary point), yet that point could be far from any actual local minimum. This paper seeks to determine whether such pathological behavior is possible for the specific types of functions used in neural networks.

The Convergence Lemma

The core contribution of this work is Theorem 1.1, the Convergence Lemma. It states that for a piecewise analytic function $f$, if $x^*$ is an isolated local minimum, then for any small distance $\epsilon$, there exists a gradient tolerance $\delta$ such that all $\delta$-stationary points in the neighborhood of $x^*$ are within $\epsilon$ distance of $x^*$.

This lemma is a natural extension of theories for strongly convex $C^1$ functions, but its application to non-smooth functions is subtle. The authors demonstrate that analyticity is a strict requirement. They provide counterexamples showing that if a function is infinitely smooth ($C^\infty$) but not analytic, the lemma can fail—the $\delta$-stationary points can "wiggle" away from the minimum even as the gradient tolerance shrinks to zero. The structural rigidity provided by analyticity prevents this behavior.

Methodology: Real Analytic Geometry

To prove these results, the authors move beyond standard calculus and employ tools from Real Analytic Geometry. The proof relies on the stratification theorems of Łojasiewicz and Whitney.

  1. Canonical Representation: The authors first demonstrate that any function composed of analytic maps and the max operator can be represented as a composition of analytic maps and the absolute value operator $|x|$.
  2. Domain Partitioning: The optimization domain is partitioned into a finite number of "strata"—regions that are both semi-analytic sets and smooth manifolds.
  3. Sub-analytic Analysis: By analyzing the function's behavior on these individual strata, the authors use the properties of sub-analytic sets to prove that the limit of a sequence of $\delta$-stationary points must be a true stationary point.

This geometric approach also allows the authors to characterize the set of all stationary points for these functions, showing they form a finite union of connected, smooth manifolds rather than a chaotic collection of points.

Convergence Stability

The paper introduces a new qualitative metric: convergence stability. This concept addresses whether a reasonable optimization method, when subjected to small numerical errors and gradient tolerances, will eventually converge to the same stationary point.

In the non-smooth, non-convex world, the authors prove that a stationary point is convergence stable if and only if it is an isolated local minimum. This provides a formal mathematical explanation for a common observation in deep learning: while numerical noise and stochasticity help optimizers escape unstable saddle points, they allow the algorithm to settle reliably into isolated minima.

Implications for Deep Learning

The theoretical framework presented here is directly applicable to modern neural network theory. The authors show that the following components all fall under the umbrella of piecewise analytic functions:

  • Convolutions and Residual Networks
  • Normalization layers (e.g., Batchnorm)
  • Pooling operations
  • Attention mechanisms

By proving that these architectures obey the Convergence Lemma, the paper provides a guarantee that "almost stationary" points in these networks are indeed close to true minima, justifying the use of gradient-based methods in these complex landscapes.

Conclusion and Future Work

While this work provides a robust qualitative foundation, it remains local in scope. The results focus on the behavior of functions near stationary points rather than global convergence from random initialization. Future research may extend these findings into quantitative bounds—calculating exactly how small $\delta$ must be for specific architectures—and incorporating probabilistic noise models to better reflect the stochastic nature of real-world SGD.

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 $δ$-stationary points near an isolated local minimum point $x^*$ is shrinking to $x^*$ as $δ\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 Ł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{deng2022convergence,
  author = {Xiaotie Deng and Hanyu Li and Ningyuan Li},
  title = {{On Convergence Lemma and Convergence Stability for Piecewise Analytic Functions}},
  year = {2022},
  eprint = {2204.01643},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2204.01643},
}
Figure