Abstract
This short note gathers known results to state that the squared distance function to a (nonconvex) closed set of an Euclidean space is Polyak-Łojasiewicz. As a fuzzy reciprocate, we also recall that every Polyak-Łojasiewicz function can be bounded from below by the squared distance function to its set of minimizers.
Introduction
In optimization theory, convexity is often the gold standard for ensuring global convergence and fast algorithmic performance. However, modern machine learning landscapes are frequently non-convex. The Polyak-Łojasiewicz (PŁ) property has emerged as a critical "middle ground," allowing for linear convergence rates even in non-convex settings. Despite its utility, the library of known non-convex PŁ functions has remained limited. This paper addresses this gap by establishing a fundamental geometric link between optimization landscapes and distance functions.
Theoretical Framework: Variational Analysis
To handle the non-differentiability inherent in distance functions to non-convex sets, the author utilizes tools from variational analysis and nonsmooth optimization. Specifically, the paper relies on the Limiting subdifferential, a generalized gradient that remains robust for "kinky" or nonsmooth functions.
A key finding is that the choice of subdifferential is non-trivial. While the PŁ property holds under the Limiting subdifferential, it can fail under the Clarke subdifferential. This is because the Clarke subdifferential is often "too large" and may contain zero at local maxima, violating the PŁ requirement that zero gradients only occur at global minimizers.
The Geometry of Squared Distance
The primary insight of this work is that geometry and optimization are deeply intertwined. The squared distance to any closed set—regardless of how disconnected or non-convex it may be—inherently satisfies the PŁ inequality.
This provides a vast new class of non-convex functions that researchers can use to model and understand optimization behavior. For a non-empty closed set $\Omega$, the function $f(x) = \frac{\mu}{2} d_\Omega(x)^2$ is shown to be Polyak-Łojasiewicz with constant $\mu$.
Characterizing PŁ Functions: The "Fuzzy Reciprocate"
Conversely, the paper establishes that PŁ functions must exhibit specific growth patterns. Any continuous function satisfying the PŁ property is "globally 2-conditioned," meaning it must grow at least quadratically as one moves away from the set of minimizers:
$$f(x) - \inf f \geq \frac{\mu}{2} d_{\text{argmin } f}(x)^2$$
For smooth functions, this relationship becomes even tighter. An $L$-smooth PŁ function is effectively "sandwiched" between two squared distance functions, constrained by its PŁ constant $\mu$ and its smoothness constant $L$. This structural constraint explains why these functions, despite being non-convex, behave so predictably under gradient-based algorithms.
Conclusion and Future Directions
While this work provides a clear geometric characterization of global PŁ functions in Euclidean space, several avenues for future research remain. In many practical applications, such as deep learning, the PŁ property may only hold locally. Extending these geometric insights to local regions and non-Euclidean manifolds (like Hilbert spaces) would further bridge the gap between theoretical optimization and practical machine learning.
Summary updated