Riemannian Zeroth-Order Gradient Estimation with Structure-Preserving Metrics for Geodesically Incomplete Manifolds

This paper proposes a framework for Riemannian zeroth-order optimization on geodesically incomplete manifolds by constructing structure-preserving complete metrics and developing an intrinsic error analysis for the symmetric two-point estimator, thereby achieving convergence guarantees comparable to the complete setting while ensuring stability in practical applications like mesh optimization.

The Gist

The Big Picture: Navigating a Broken Map

Imagine you are a hiker trying to find the lowest point in a valley (the optimal solution) to set up camp. You have a map (the manifold) and a compass (the gradient).

In the world of standard math, the ground is flat and infinite (Euclidean space). But in complex real-world problems—like designing a mesh for a video game or optimizing a sprinkler system—the "ground" is curved, like the surface of a sphere or a complex shape. This is called a Riemannian Manifold.

Usually, hikers use a compass that points in the direction of steepest descent. But in this paper, the authors face two specific problems:

1. The "Black Box" Problem: The hiker cannot see the compass. The terrain is controlled by a "black box" (like a complex physics simulator) that won't tell them the slope. They can only ask, "How high is the ground if I take one step here?" and "How high is it if I take one step there?" This is Zeroth-Order Optimization.
2. The "Broken Map" Problem: The map they are using has holes or edges. If they try to walk in a certain direction, they might fall off the edge of the world (the exponential map becomes undefined). In math terms, the map is geodesically incomplete.

The authors' goal was to build a new navigation system that works even when the map has holes and the compass is broken.

---

The Three-Step Solution

The paper proposes a clever three-step strategy to solve this.

1. The "Stretchy Rubber Sheet" (Structure-Preserving Metric)

The Problem: Your current map has edges. If you try to walk straight, you might fall off.
The Analogy: Imagine your map is a piece of paper with a hole in the middle. If you try to walk through the hole, you fall.
The Solution: The authors invent a new way of measuring distance, like stretching the paper into a rubber sheet. They stretch the space near the edges so that no matter which direction you walk, you never actually reach the "edge" or fall off.

• Key Feature: They stretch it in a very specific way (Conformal Equivalence) so that the "lowest points" (the stationary points) stay exactly where they were. It's like stretching a rubber sheet with a marble on it; the marble might roll a tiny bit, but it stays in the same "valley." This ensures that finding the bottom of the new, stretched map is the same as finding the bottom of the original, broken map.

2. The "Fair Dice Roll" (Intrinsic Sampling)

The Problem: To guess the direction of the slope without a compass, you need to take random steps in all directions. On a flat table, you can roll a die easily. But on a curved, stretched rubber sheet, rolling a die is tricky. If you just stretch a standard die roll, you end up stepping more often in some directions than others (bias).
The Analogy: Imagine trying to pick a random direction on a distorted, warped surface. If you just "stretch" a normal circle, it becomes an oval, and you'll accidentally pick points near the short ends more often.
The Solution: The authors created a new method called Rejection Sampling.

• How it works: Imagine you are throwing darts at a target. You throw a dart. If it lands in a "bad" spot (where the distortion is too strong), you throw it away and try again. If it lands in a "good" spot, you keep it.
• The Result: This ensures that every direction on the warped rubber sheet has an equal chance of being chosen. This is crucial because if your random steps are biased, your guess about the slope will be wrong, and you'll never find the bottom of the valley.

3. The "Curvature Check" (Intrinsic Error Analysis)

The Problem: How do we know our random steps are good enough? Does the shape of the hill matter?
The Analogy: If you are walking on a flat floor, a small step gives you a good idea of the slope. If you are walking on a bumpy, curved hill, a small step might mislead you because the ground curves away quickly.
The Solution: The authors proved mathematically that the accuracy of their "random step" method depends on the curvature of the hill.

• If the hill is flat, the error is small.
• If the hill is very curved, the error is larger.
• They derived a formula that tells you exactly how much error to expect based on how "curvy" the terrain is. This allows them to guarantee that, even with a broken map and no compass, they will eventually find the bottom of the valley.

---

Real-World Examples (Why should we care?)

The paper tests this on three real-world scenarios where the "map" is naturally broken:

1. Mesh Optimization (Video Games & Physics):

   • Scenario: You are adjusting the vertices of a 3D mesh (like a character's skin) to make it look better.
   • The Issue: If a vertex moves too far, it might cross a line and break the 3D model (the "edge" of the map).
   • The Fix: The authors' method keeps the vertices moving within the safe zone without needing to calculate complex gradients, ensuring the model never breaks.

2. Irrigation System Design:

   • Scenario: You want to place sprinklers to water a field perfectly.
   • The Issue: You can't put a sprinkler on the fence line (the boundary). The "map" of valid positions is an open area with no edges.
   • The Fix: The method finds the best spots without ever trying to place a sprinkler on the fence.

3. Covariance Matrix Estimation (Statistics):

   • Scenario: Analyzing data to find patterns.
   • The Issue: The math requires matrices that must be "positive definite." If a number gets too close to zero, the matrix breaks.
   • The Fix: The method navigates this "open cone" of valid matrices safely, avoiding the breaking point.

The Takeaway

This paper is like building a GPS for a world with no roads and no signs.

• Old Way: "We can't go there because the road ends." (Geodesic Incompleteness).
• New Way: "Let's stretch the road so it never ends, but keep the destination in the same place." (Structure-Preserving Metric).
• The Navigation: "Let's take random steps, but make sure we don't favor one direction over another, even on the warped road." (Unbiased Rejection Sampling).

By doing this, they proved that you can still find the best solution efficiently, even when the mathematical terrain is messy, broken, or curved. This opens the door to solving complex optimization problems in physics, engineering, and machine learning that were previously too difficult to tackle.

Technical Summary

1. Problem Statement

The paper addresses Riemannian zeroth-order optimization in scenarios where the underlying Riemannian metric $g$ is geodesically incomplete.

• Context: Many practical optimization problems (e.g., mesh optimization, irrigation layout, covariance estimation) occur on manifolds where the natural Euclidean metric inherited from an ambient space is incomplete. This means the exponential map $\exp_p(v)$ is not globally defined; random perturbations $v$ in the tangent space $T_pM$ may map outside the manifold's domain, causing the optimization algorithm to fail.
• Challenge: Existing convergence guarantees for Riemannian zeroth-order methods typically assume geodesic completeness. When the metric is incomplete, standard gradient estimators (which rely on evaluating $f(\exp_p(\pm \mu v))$) become undefined or unstable. Furthermore, simply embedding the manifold into a larger space to force completeness is often numerically infeasible (due to the complexity of Nash embedding constructions).
• Goal: Develop a framework to perform zeroth-order optimization on geodesically incomplete manifolds while ensuring convergence to stationary points that are valid under the original metric.

2. Methodology

The authors propose a three-pronged approach: constructing a new metric, developing an intrinsic estimator, and designing a robust sampling scheme.

A. Structure-Preserving Metric Construction

To overcome geodesic incompleteness, the authors construct a new metric $g'$ that is geodesically complete but preserves the optimization landscape of the original metric $g$.

• Definition: A metric $g'$ is structure-preserving if:
  1. It is geodesically complete (the exponential map is globally defined).
  2. It is conformally equivalent to $g$ (i.e., $g'_p = h(p)g_p$ for some smooth positive function $h$).
  3. It preserves $\epsilon$-stationarity: Any point that is $\epsilon$-stationary under $g$ remains $\epsilon$-stationary under $g'$.
• Construction: Based on the Nomizu-Ozeki theorem, they define a conformal factor $h(p)$ derived from a proper smooth function $\rho(p)$ (e.g., related to the distance to the boundary). This ensures that geodesics under $g'$ never escape the manifold, effectively "stretching" the geometry near boundaries to infinity.

B. Intrinsic Zeroth-Order Gradient Estimation

Instead of relying on an ambient Euclidean embedding (which may not exist or be compatible with $g'$), the authors derive an intrinsic analysis of the gradient estimator.

• Estimator: They use the classical symmetric two-point estimator:
  $$\hat{\nabla}f(p) = \frac{f(\text{Ret}_p(\mu v)) - f(\text{Ret}_p(-\mu v))}{2\mu} v$$
  where $\text{Ret}$ is a retraction (approximation of the exponential map) and $v$ is sampled from the unit sphere defined by $g'$.
• Error Analysis: They derive a mean-squared error (MSE) bound that depends purely on the intrinsic geometry (sectional curvature $\kappa$) rather than the embedding:
  $$\mathbb{E}[\|\hat{\nabla}f(p) - \frac{1}{d}\nabla f(p)\|_p^2] \leq \frac{1 + \mu^2 \kappa^2}{d} \|\nabla f(p)\|_p^2 + O(\mu^2)$$
  This reveals that estimation error is directly influenced by the manifold's curvature.

C. Unbiased Sampling via Rejection Sampling

Sampling uniformly from the unit sphere $S^{d-1}$ induced by a general Riemannian metric $g'$ is non-trivial.

• Problem: Naive "rescaling" (sampling a Gaussian vector and normalizing) introduces significant bias under non-Euclidean metrics, leading to unstable convergence.
• Solution: The authors propose an unbiased rejection sampling algorithm (Algorithm 1).
  1. Compute the eigen-decomposition of the metric matrix $A$.
  2. Transform a standard Gaussian vector to the ellipsoid defined by $A$.
  3. Apply a rejection step based on the ratio of the quadratic form to the maximum eigenvalue to ensure the output distribution is exactly uniform over the Riemannian unit sphere.

D. Convergence Analysis

The paper establishes convergence for Stochastic Gradient Descent (SGD) using the proposed estimator and metric.

• Result: Under standard smoothness and boundedness assumptions, the algorithm converges to an $\epsilon$-stationary point.
• Complexity: The iteration complexity matches the best-known bounds for geodesically complete settings ($O(d/\epsilon^4)$), provided the set of stationary points is compact or the original metric is already complete.

3. Key Contributions

1. Structure-Preserving Metrics: Introduced a theoretical framework to convert any Riemannian metric into a geodesically complete, conformally equivalent metric that preserves the set of stationary points, enabling optimization on incomplete manifolds.
2. Intrinsic Error Bounds: Provided the first purely intrinsic analysis of the two-point zeroth-order gradient estimator, linking approximation error directly to the manifold's sectional curvature without relying on ambient embeddings.
3. Unbiased Sampling: Developed a rejection sampling method to generate unbiased perturbation directions on general Riemannian manifolds, correcting the bias inherent in standard rescaling techniques.
4. Convergence Guarantees: Extended the convergence theory of Riemannian zeroth-order SGD to the general case of geodesically incomplete manifolds, matching the complexity of the complete case under mild conditions.

4. Experimental Results

The authors validated their theory through synthetic and real-world experiments:

• Sampling Bias: Synthetic experiments on quadratic and logistic loss functions demonstrated that the proposed rejection sampling method leads to stable convergence, whereas the naive rescaling method caused divergence or poor performance due to sampling bias.
• Curvature Impact: Experiments on the probability simplex showed that gradient estimation error (MSE) increases with sectional curvature, confirming the theoretical bound in Theorem 2.7.
• Mesh Optimization: A practical application involving the optimization of mesh nodes for solving the Helmholtz equation (a black-box PDE solver problem).
  • Baseline: Unconstrained methods failed due to invalid steps (crossing boundaries). Reversion and Soft Projection methods were unstable or slow.
  • Proposed Method: The structure-preserving approach maintained feasibility (nodes stayed within the valid domain) and achieved the lowest Mean Squared Error (MSE) with stable, efficient convergence.

5. Significance

• Bridging Theory and Practice: This work resolves a fundamental gap between theoretical Riemannian optimization (which assumes completeness) and practical applications (where manifolds are often open sets or incomplete).
• Black-Box Optimization: It provides a robust tool for optimizing systems with non-differentiable external solvers (e.g., CFD, physics engines) where gradients are unavailable and the search space has hard boundaries.
• Geometric Insight: By decoupling the analysis from ambient embeddings, the paper offers a deeper understanding of how intrinsic geometric properties (like curvature) fundamentally limit or influence zeroth-order optimization performance.
• Generalizability: The framework is applicable to a wide range of problems including covariance matrix estimation, irrigation design, and neural physical simulations, extending the reach of derivative-free optimization to complex, constrained geometric domains.