Clarke Subgradients of Stratifiable Functions

By Jérôme Bolte, Aris Daniilidis, A. S. Lewis, Masahiro Shiota. SIAM Journal on Optimization, 2006

494 citations recorded by the source corpus.

We establish the following result: If the graph of a lower semicontinuous real-extended-valued function $f:\mathbb{R} ^{n}\rightarrow\mathbb{R}\cup\{+\infty\}$ admits a Whitney stratification (so in particular if $f$ is a semialgebraic function), then the norm of the gradient of $f$ at $x\in\mbox{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 a Morse-Sard type of theorem as well as a nonsmooth extension of the Kurdyka-Lojasiewicz inequality for functions definable in an arbitrary o-minimal structure. It is worthwhile pointing out that, even in a smooth setting, this last result generalizes the one given in [K. Kurdyka, Ann. Inst. Fourier (Grenoble), 48 (1998), pp. 769-783] by removing the boundedness assumption on the domain of the function.

Subfields: Computational Theory and Mathematics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/6f3677b0c680b8cd5b10c3ad395d168c54871e06

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Geometry and Topology

Citations in the corpus

From error bounds to the complexity of first-order descent methods for convex functions (2015, methodology): “3 KurdykaLojasiewicz inequality In this subsection, we present the nonsmooth KurdykaLojasiewicz inequality introduced in [17] (see also [19, 18], and the fundamental works [43, 38]).”
Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward–backward splitting, and regularized Gauss–Seidel methods (2013, background): “Among real-extended-valued lower-semicontinuous functions, typical KL functions are semi-algebraic functions or more generally functions definable in an o-minimal structure, see [15, 16, 17].”
Proximal Alternating Minimization and Projection Methods for Nonconvex Problems: An Approach Based on the Kurdyka-Lojasiewicz Inequality (2008, background): “The concavity of the function φ is not stated explicitly in [18].”
Proximal alternating linearized minimization for nonconvex and nonsmooth problems (2013, background): “These facts originates in the pioneering and fundamental works of Lojasiewicz [25] and Kurdyka [22]; works which were recently extended to nonsmooth functions in [16,17].”
A unifying framework for the analysis of projection-free first-order methods under a sufficient slope condition (2020, methodology): “We analyze convergence rates for non convex smooth objectives both in the general case and under the Kurdyka-Łojasiewicz property ([3], [8], [9]; see also Section 8.”
A Block Coordinate Descent Method for Regularized Multiconvex Optimization with Applications to Nonnegative Tensor Factorization and Completion (2013, background): “The second step, which is motivated by [4], assumes the KL inequality [13, 14] and improves the result to ∑ k ‖xk−xk+1‖ < ∞, which gives the algorithm’s global convergence, as well as asymptotic rates of convergence.”
Characterizations of Lojasiewicz inequalities and applications (2008, background): “Under a compactness assumption and a condition of Sard type (automatically satisfied in finite dimensions if f belongs to an o-minimal class), their lengths are uniformly bounded if and only if f satisfies the K L–inequality in its nonsmooth form (see [9]), that is, for all x ∈ [0 < f < r], ||∂(φ ◦ ”
Characterizations of Lojasiewicz inequalities: Subgradient flows, talweg, convexity (2009, background): “This was one of the motivations for the nonsmooth K L–inequalities developed in [8, 9].”
On damped second-order gradient systems (2014, unknown): “[9]).”