Manifold Geometry and Local Linear Convergence Rates

21 concepts13 papers1 proposal

When optimizing complex, non-smooth, or non-convex functions, algorithms often undergo a dramatic phase transition. They may begin with slow, sublinear progress, but suddenly accelerate into a highly efficient local linear convergence regime, where the distance to the optimal solution decreases exponentially.

Why does this acceleration happen? The answer lies in geometry. Whether an optimization problem is explicitly constrained to a curved surface (such as a Stiefel or Grassmannian manifold) or implicitly unconstrained but governed by a non-smooth regularizer, the local geometry of an underlying manifold dictates the speed and stability of the final convergence phase.


The Emergent Geometry of Non-Smooth Optimization

In non-smooth optimization—such as minimizing objectives with $\ell_1$ or nuclear norm regularizers—the objective function possesses sharp "kinks" or boundaries. Intuitively, one might expect these non-smooth points to slow down first-order methods like Forward-Backward (FB) or Douglas-Rachford splitting. In practice, however, these algorithms routinely achieve fast linear convergence.

This phenomenon occurs because the algorithms perform implicit activity identification. As the optimization trajectory approaches a solution, it identifies the underlying smooth structure of the problem in finite time and drops into a lower-dimensional "active manifold." Once the trajectory is confined to this manifold, the problem effectively becomes smooth.

Euclidean Space (Non-smooth landscape)
       │
       ▼  (Finite-time identification)
┌──────────────────────────────┐
│       Active Manifold        │ ◄─── Curvature here determines 
└──────────────────────────────┘      linear convergence rate

The precise rate of this local linear convergence depends entirely on the geometry of the identified manifold. In Local Linear Convergence of Forward-Backward under Partial Smoothness, Jingwei Liang et al. demonstrated that the curvature of the active manifold acts as a fundamental limit on stability and speed. Specifically, they showed a structural split:

  • Linear Subspaces: If the active manifold is flat (a linear subspace), the algorithm exhibits R-linear convergence (the error is bounded by a geometrically decaying sequence).
  • Curved Surfaces: If the active manifold is curved, the algorithm exhibits Q-linear convergence (the error decreases by at least a constant factor at every single step).

This geometric dependency means that the step size and the local curvature of the objective function interact directly to determine the final convergence rate. As explored by Jingwei Liang et al. in Activity Identification and Local Linear Convergence of Forward-Backward-type Methods, characterizing this rate requires analyzing how the algorithm behaves once it is restricted to this emergent geometric structure. This adaptive convergence behavior is not unique to Forward-Backward methods; in Convergence Rates of Forward-Douglas-Rachford Splitting Method, Cesare Molinari et al. proved that the Forward-Douglas-Rachford splitting method transitions to an identical local linear regime once the underlying smooth manifold is identified.


Extending Regularity Conditions to Riemannian Manifolds

When an optimization problem is explicitly defined on a curved space—such as a Riemannian manifold—we lose the global properties of Euclidean space, like standard convexity. To guarantee local linear convergence in these settings, researchers generalize Euclidean regularity conditions to curved geometries.

Sharpness and Weak Convexity

In Euclidean optimization, a function is "sharp" if it grows at least linearly with the distance away from the set of minima. To analyze non-smooth, non-convex problems on manifolds, this concept must be translated to respect the manifold's intrinsic metric.

For example, in A Linearly Convergent Method for Non-Smooth Non-Convex Optimization on the Grassmannian with Applications to Robust Subspace and Dictionary Learning, Zhihui Zhu et al. introduced a Riemannian regularity condition that extends sharpness and weak convexity to curved spaces. This condition mathematically guarantees that within a specific neighborhood, the negative subgradients consistently point toward the optimal solution, enabling projected Riemannian subgradient descent to achieve linear convergence. This framework was leveraged by Tianyu Ding et al. in Dual Principal Component Pursuit for Robust Subspace Learning: Theory and Algorithms for a Holistic Approach to prove that high-dimensional subspaces can be recovered exponentially fast from heavily corrupted data on the Grassmannian.

Similarly, for problems constrained to the Stiefel manifold, Xiao Li 0009 et al. in Weakly Convex Optimization over Stiefel Manifold Using Riemannian Subgradient-Type Methods established that a manifold-adapted sharpness property ensures the level sets of the objective function remain well-behaved near a minimum, yielding local linear convergence for subgradient and incremental subgradient methods.

The Riemannian Kurdyka-Łojasiewicz Property

For broader classes of non-convex problems where sharpness might not hold, the Kurdyka-Łojasiewicz (KL) property serves as the primary mathematical tool for bounding convergence rates. The KL property bounds the subgradient norm from below by a function of the objective value, ensuring the function doesn't flatten out too much around stationary points.

Euclidean Property                  Riemannian Generalization
──────────────────                  ─────────────────────────
Convexity             ───────►      Strong Retraction-Convexity
Sharpness             ───────►      Riemannian Regularity / Sharpness
Kurdyka-Łojasiewicz   ───────►      Riemannian KL Property

In Riemannian proximal gradient methods, Wen Huang et al. extended the KL property to the Riemannian framework, providing a unified approach to prove convergence to a single stationary point for both convex and non-convex manifold optimization. By extending this to an inexact setting in An inexact Riemannian proximal gradient method, the authors demonstrated that even when subproblems are solved approximately to save computational cost, the Riemannian KL property preserves the local linear convergence guarantees.


Guaranteeing Sufficient Descent on Curved Spaces

Even when a landscape possesses favorable local regularity, an algorithm can fail to converge linearly if its search directions deviate too far from the true path to the minimum. In Euclidean space, line search methods use standard descent conditions to prevent this. On a manifold, however, moving along a search direction requires mapping a tangent vector back down to the manifold via a retraction, and comparing vectors across different points requires vector transport.

To prevent stagnation or divergence on curved surfaces, algorithms must satisfy a sufficient descent condition adapted to the manifold. This condition ensures that the optimization search directions maintain a guaranteed, quantifiable slope toward the minimum rather than merely pointing downhill.

Tangent Space (at point x) ───► [Compute Search Direction]
                                       │
                                       │  Vector Transport / Retraction
                                       ▼
Manifold Surface           ───► [Guaranteed Sufficient Descent Step]

In Sufficient Descent Riemannian Conjugate Gradient Methods, Hiroyuki Sakai et al. proved that extending this condition to Riemannian manifolds provides significantly stronger convergence guarantees for non-Euclidean conjugate gradient methods. By pairing specific parameter selection rules with scaled vector transport, Hideaki Iiduka et al. in Hybrid Riemannian Conjugate Gradient Methods with Global Convergence Properties showed how to rigorously guarantee that every generated search direction remains a valid descent direction, preventing the solver from drifting due to curvature.

For second-order and multiplier-based methods, this geometric alignment is captured through stability conditions under external perturbations. In On the robust isolated calmness of a class of nonsmooth optimizations on Riemannian manifolds and its applications, Chao Ding et al. characterized a property known as "robust isolated calmness" on manifolds. They proved that satisfying manifold-specific strict Robinson constraint qualifications and second-order sufficient conditions is exactly what allows the Riemannian Augmented Lagrangian Method (RALM) to achieve local linear convergence on non-smooth problems.

Finally, the underlying global structure of the manifold itself can alter how these algorithms behave. While classical splitting methods rely on the nonexpansiveness of operators, Ronny Bergmann et al. in A Parallel Douglas-Rachford Algorithm for Minimizing ROF-like Functionals on Images with Values in Symmetric Hadamard Manifolds showed that on symmetric Hadamard manifolds (which feature non-positive curvature), the global geometric structure allows Douglas-Rachford algorithms to converge reliably even when standard Euclidean operator properties do not universally hold. Similarly, in the context of quasi-Newton methods, Wen Huang et al. in A Broyden Class of Quasi-Newton Methods for Riemannian Optimization demonstrated that local convergence to a minimizer can be theoretically guaranteed by assuming a property termed strong retraction-convexity, providing a solid foundation for generalizing classical Broyden-class updates to curved spaces.

Key Foundational Work

Local Linear Convergence of Forward-Backward under Partial Smoothness (2014) — contributed 2 concept elements to this direction.
A Broyden Class of Quasi-Newton Methods for Riemannian Optimization (2015) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_sufficient_descent_condition_geometric_c_599302f4,
  title = {sufficient descent condition (geometric convergence analysis)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sufficient-descent-condition-geometric-convergence-analysis/rdr_599302f4dc264a3e871a3783b20edb41},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_sufficient_descent_condition_geometric_c_599302f4_v1,
  title = {sufficient descent condition (geometric convergence analysis)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sufficient-descent-condition-geometric-convergence-analysis/rdr_599302f4dc264a3e871a3783b20edb41/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake