On Convergence Lemma and Convergence Stability for Piecewise Analytic Functions
This work addresses theoretical convergence issues in nonsmooth nonconvex optimization, providing foundational insights for algorithm design, though it is incremental as it extends prior results for strongly convex functions.
The authors proved a convergence lemma for piecewise analytic functions, showing that δ-stationary points shrink to an isolated local minimum as δ→0, and introduced convergence stability to characterize where optimization methods converge under small errors in nonsmooth nonconvex settings.
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.