Smooth globally PLI functions are nonlinear least-squares, and so are their gradient-dominated cousins

Technical Summary: Smooth Globally PŁ Functions are Nonlinear Least-Squares, and So Are Their Gradient-Dominated Cousins

Problem Statement
The paper addresses a limitation in the structural theory of smooth optimization developed by Boumal, Criscitiello, and Rebjock (BCR) [1]. BCR proved that a smooth function $f$ on a contractible, complete Riemannian manifold satisfying the global Polyak–Łojasiewicz (PŁ) inequality, $\|\nabla f(x)\|^2 \geq 2\mu(f(x) - f^*)$, is necessarily of the form $f = f^* + \|\phi\|^2$ for a smooth submersion $\phi$. This implies the function is a "nonlinear least-squares" problem with a manifold of minimizers $S$ that is a smooth, properly embedded submanifold.

However, the global PŁ inequality fails in several critical control and learning problems, notably continuous-time Linear Quadratic Regulator (LQR) policy optimization and logistic regression. In these cases, the gradient remains bounded while the loss grows unbounded, violating the requirement that the gradient lower bound $\alpha(r)$ be unbounded (specifically, $\alpha(r) \sim \sqrt{r}$ as $r \to \infty$). This paper investigates whether the profound structural conclusions of BCR depend on the global strength of the PŁ inequality or merely on its local behavior near the minimizers and its uniformity on level sets.

Methodology
The author introduces a relaxed condition, termed $s_{gl}$-PŁI (semi-global PŁ inequality), which corresponds to the condition $(GD_\alpha)$ with a witness $\alpha$ that is positive definite and satisfies a local quadratic growth condition (Condition A) near the origin. Specifically, the paper replaces the global inequality $\|\nabla f\| \geq \sqrt{2\mu h}$ with:
$$\|\nabla f(x)\| \geq \alpha(h(x))$$
where $\alpha$ is positive definite and satisfies $\alpha(s)^2 \geq 2\mu s$ for small $s$ (near the minimizer set $S$).

The methodology proceeds in two parallel tracks:

1. Direct Proof: The author re-examines the proofs in [1] to identify exactly which steps rely on the global PŁ inequality. It is shown that the structural results (manifold structure of $S$, existence of a fiber bundle structure, and the normal form) rely only on:

   • Local Behavior (J1): The Łojasiewicz exponent being $1/2$ near $S$ (ensuring $S$ is a manifold and the Hessian is non-degenerate in normal directions).
   • Uniformity (J2): The gradient being bounded away from zero on every level set $h(x) = c > 0$ (ensuring trajectories do not escape to infinity).
   • The global quantitative bound (J3) is shown to be unnecessary for structural conclusions.
     The author constructs a "desingularizer" $\Psi(h) = \int_0^h ds/\alpha(s)$ to bound trajectory lengths and prove convergence, replacing the quadratic growth estimates used in [1].

2. Reparametrization Proof: A shorter route demonstrates that for any function satisfying the relaxed condition, one can construct a companion function $g = \theta(f - f^*)$ that satisfies the global PŁ inequality with respect to a new metric. Applying BCR's theorems to $g$ and transporting the results back to $f$ yields the same structural conclusions.

Key Contributions and Results

• Generalization of Structural Theorems: The paper proves that all structural conclusions of [1] hold verbatim under the weaker $s_{gl}$-PŁI condition (equivalently, under the condition that $f$ is $\alpha$-gradient dominated with $\alpha$ satisfying Condition A).

  • Manifold Structure: The set of minimizers $S$ is a smooth, properly embedded submanifold.
  • Normal Form: If the domain $M$ is contractible, $f$ is globally diffeomorphic to a sum of squares: $f(x) = f^* + \|\phi(x)\|^2$, where $\phi: M \to \mathbb{R}^k$ is a smooth submersion.
  • Fiber Bundle Structure: The end-point map of the gradient flow is a smooth fiber bundle over $S$ with fibers diffeomorphic to $\mathbb{R}^k$.
  • Hidden Convexity: On a contractible manifold, there exists a complete Riemannian metric (dependent on $f$) with respect to which $f$ is geodesically convex and globally 1-PŁ.

• Sharpness and Necessity: The paper provides elementary counterexamples to show that the two components of the hypothesis are indispensable:

  • Dropping the local quadratic growth (Condition A) allows for degenerate minimizers where $S$ is not a manifold (e.g., $f(x,y)=x^2y^2$).
  • Dropping the uniform positivity of the gradient on level sets (allowing $\alpha \to 0$ at infinity) allows trajectories to have infinite length or fail to converge to a minimizer, even if the function is invex.

• Quantitative Loss: The paper explicitly identifies what is lost by weakening the hypothesis: the global quadratic growth estimate ($h(x) \geq c \cdot \text{dist}(x, S)^2$). Under $s_{gl}$-PŁI, this growth is only guaranteed locally near $S$. Globally, the growth can be sub-quadratic (e.g., linear or logarithmic), and the convergence rate of gradient flow is no longer globally exponential.

• Transversality of Robustness and Structure: A significant conceptual contribution is the demonstration that "structure" (the normal form) and "robustness" (Input-to-State Stability, ISS) are governed by opposite ends of the comparison function $\alpha$.

  • Structure depends on $\alpha$ near the origin (Condition A).
  • Robustness (ISS/NSS) depends on $\alpha$ at infinity (e.g., $\alpha \in \mathcal{K}_\infty$).
  • The paper shows these properties are logically independent; a function can have a perfect nonlinear least-squares structure but fail to be robust (if $\alpha \to 0$ at infinity), or be robust but lack a minimizer (if $\alpha$ is large at infinity but fails near zero).

Applications to Specific Problems
The paper applies these results to two motivating problems where global PŁ fails:

1. Continuous-Time LQR: The paper confirms that the LQR loss satisfies $s_{gl}$-PŁI (and the stronger $sat$-PŁI). Consequently, the set of stabilizing gains $D$ is diffeomorphic to $\mathbb{R}^{mn}$, and the loss function admits a global normal form $L = L^* + \|\phi(k)\|^2$. This resolves the topological question of the shape of the stabilizing set without relying on the global PŁ inequality.
2. Logistic Regression: For non-linearly separable data, the cross-entropy loss satisfies $s_{gl}$-PŁI. The paper concludes that the loss landscape is globally diffeomorphic to a standard paraboloid, reinforcing that the landscape has no "hidden" topological obstructions, even though the gradient saturates at infinity.

Significance and Claims
The paper claims that the global PŁ inequality in [1] is "stronger than what the proofs require." The structural theory of nonlinear least-squares functions is robust to the global size of the gradient, provided the gradient does not vanish on level sets and behaves quadratically near the minimizers.

The author is modest about the scope of the generalization:

• The generalization is "apparent" in a precise geometric sense: by Theorem 4.8, any function in this class becomes globally PŁ with respect to some complete metric (dependent on the function). Thus, the class of realizable minimizer sets (geometry) is unchanged; only the class of functions representable under a fixed metric is enlarged.
• The paper does not claim to improve convergence rates or robustness guarantees; those remain the domain of the comparison-function hierarchy (e.g., $sat$-PŁI,$K$-PŁ) as established in [13, 4, 5].
• The primary contribution is clarifying the logical dependencies of the structural theorems in [1] and extending their applicability to important control and learning problems that were previously excluded by the strict global PŁ requirement.