Technical Summary: Metric-Free Riemannian Optimization

1. Problem Statement

Riemannian optimization is a powerful framework for constrained optimization, particularly on matrix manifolds found in computer vision, signal processing, and quantum computing. It treats constraints as intrinsic geometric properties, avoiding the need for Lagrange multipliers or explicit projections. However, a significant practical bottleneck exists: the explicit evaluation or application of the Riemannian metric can be computationally expensive or numerically unstable.

In specific applications, such as energy-adaptive frameworks for nonlinear eigenvalue problems, applying the metric is equivalent to applying a Hamiltonian, which is costly. Furthermore, standard algorithms like Riemannian Conjugate Gradient (RCG) often require multiple applications of the metric to calculate step sizes and CG parameters. This work investigates the extent to which classical Riemannian optimization algorithms can be reformulated to avoid explicit metric application, thereby improving efficiency without sacrificing mathematical rigor.

2. Methodology

The core methodology relies on the observation that many first-order quantities in Riemannian optimization depend only on the differential of the objective function ($Df(x)$) and access to the Riemannian gradient ($\text{grad}f(x)$), rather than the explicit application of the metric tensor.

2.1. The Metric-Free Principle

The paper establishes a general principle for reformulating optimization quantities. While the Riemannian gradient is defined via the Riesz representation theorem ($\langle \text{grad}f(x), v \rangle_x = Df(x)[v]$), quantities typically expressed as inner products involving the gradient can often be rewritten as directional derivatives.

• Euclidean vs. Riemannian: In Euclidean space, minimizing inner product applications is a standard optimization. In Riemannian space, the "naive" generalization often requires transporting vectors to a common tangent space and applying the metric there.
• Metric-Free Formulation: The paper proposes expressing these quantities directly via the differential $Df(x)$. For instance, instead of calculating $\langle g, d \rangle$, one calculates $Df(x)[d]$. This approach minimizes the number of vector transports required and completely circumvents the explicit application of the metric tensor.

2.2. Preconditioning Analogy

The paper draws a parallel with the Euclidean Preconditioned Conjugate Gradient (PCG) method. In PCG, solving a system with matrix $A$ using a preconditioner $M$ is mathematically equivalent to performing conjugate gradients with respect to the inner product $\langle \cdot, \cdot \rangle_M$. The paper demonstrates that just as PCG can be implemented without explicitly forming the $M$-inner product (by using $M^{-1}$ on residuals), Riemannian optimization can be performed using a "cheap" metric for step-size calculations while relying on a "cheap" differential evaluation for gradient-related terms, avoiding the "expensive" metric application entirely.

2.3. Reformulation of Key Components

The author systematically reformulates standard Riemannian optimization components into metric-free versions:

• Search Direction Conditions: Descent and sufficient descent conditions are reformulated using $Df(x)[d] < 0$ rather than inner products.
• Line Search Conditions:
  • Armijo & Goldstein: Reformulated using $Df(x)[d]$ instead of inner products.
  • Curvature Conditions: The weak and strong Wolfe conditions are expressed using the differentiated retraction transport ($T_{td_k}(d_k)$) and the differential, avoiding the need to compute gradients at trial points if they are not strictly necessary for the condition check.
• Step Size Strategies:
  • Polyak Step Size: Reformulated using $Df(x)[\text{grad}f(x)]$.
  • Barzilai-Borwein (BB): The metric-free formulation splits expressions to minimize vector transports, utilizing differentials rather than transported gradients and inner products.
• Conjugate Gradient Parameters: The paper provides metric-free formulations for Hestenes-Stiefel (HS), Fletcher-Reeves (FR), Polak-Ribiere-Polyak (PRP), and Dai-Yuan (DY) parameters. For example, the FR parameter, typically $\|\text{grad}f(x_k)\|^2 / \|\text{grad}f(x_{k+1})\|^2$, is reformulated as $Df(x_k)[\text{grad}f(x_k)] / Df(x_{k+1})[\text{grad}f(x_{k+1})]$.

2.4. Extensions to Non-Riemannian Manifolds

The paper explores the applicability of these metric-free strategies to manifolds without a Riemannian metric:

• Banach Manifolds: While the Riemannian Hessian is undefined, Newton-like methods can be constructed using the derivative map $Df: M \to T^*M$ and vector-back transports. Descent conditions and line search strategies remain valid.
• Finsler Manifolds: Using the Golomb-Tapia definition, a "Finsler gradient" is defined as the maximizer of the differential over the unit ball in the tangent space. The paper argues that all previously discussed metric-free quantities (descent conditions, line searches, CG parameters) are well-defined in this setting, allowing for gradient descent and conjugate gradient methods on Finsler manifolds.

3. Key Contributions

1. Metric-Free Reformulations: The paper provides explicit, mathematically equivalent reformulations for a wide range of Riemannian optimization components (descent conditions, line searches, step sizes, and CG parameters) that eliminate the explicit application of the Riemannian metric.
2. Generalization to Finsler/Banach Settings: It demonstrates that these reformulations naturally extend to Finsler and Banach manifolds, suggesting that a substantial portion of Riemannian optimization is independent of the specific metric structure.
3. Algorithmic Efficiency: The methodology reduces computational overhead by avoiding expensive metric applications and matrix inversions associated with gradient calculations in the "expensive" metric, replacing them with cheaper differential evaluations.
4. Numerical Stability: By avoiding explicit metric application and unnecessary vector transports, the approach reduces potential sources of numerical error.

4. Numerical Results

The effectiveness of the proposed strategy was demonstrated through numerical experiments on a 2D Laplace eigenvalue problem on the unit sphere ($S^{n-1}$) with a non-standard, expensive metric defined by a preconditioner $M \approx A$.

• Setup: The problem involved minimizing $E(x) = \frac{1}{2}x^T Ax$ on the sphere. The "expensive" metric involved an $LDL^T$ decomposition.
• Comparison: The study compared three methods:
  1. Standard Euclidean metric RCG (2-RCG).
  2. Standard "expensive" metric RCG (M-RCG).
  3. Metric-free "expensive" metric RCG (M-RCG-mf).
• Performance:
  • Convergence: M-RCG and M-RCG-mf were mathematically equivalent, converging in the same number of iterations (230).
  • Efficiency: The metric-free variant (M-RCG-mf) achieved a ~82% reduction in CPU time and a ~78% reduction in total matrix-vector multiplications compared to the standard M-RCG.
  • Mechanism: The speedup was primarily due to eliminating the explicit application of the metric $M$ and the calculation of the expensive gradient $\text{grad}_M f(x)$ during line search checks, relying instead on the cheaper differential $Df(x)$ and the Euclidean metric for step-size calculations.

5. Significance and Claims

The paper claims that a substantial portion of Riemannian optimization can be carried out independently of explicit metric application. The significance lies in:

• Broadened Applicability: The approach makes Riemannian optimization viable for problems where the metric is implicitly defined, expensive to evaluate, or numerically unstable (e.g., nonlinear eigenvalue problems).
• Computational Efficiency: It offers a direct path to significant performance gains without altering the convergence properties of the underlying algorithms.
• Theoretical Insight: It highlights that many "Riemannian" quantities are actually metric-independent first-order properties, suggesting that the framework is more robust and generalizable (to Finsler/Banach spaces) than previously utilized in practice.

The author notes that while second-order methods (like Riemannian Newton) generally cannot be made metric-free due to their dependence on curvature, the first-order methods discussed here represent a large and practically important subset of optimization algorithms.