Introduction
As machine learning increasingly moves beyond Euclidean domains to handle data structured on curved spaces—such as graphs, 3D shapes, and symmetric positive definite (SPD) matrices—the need for robust optimization tools on Riemannian manifolds has become paramount. A significant challenge in this field is optimizing functions when exact gradients are unavailable, a scenario common in reinforcement learning and online learning known as zeroth-order optimization or bandit feedback.
In these settings, gradients must be estimated through function smoothing. While the Greene-Wu (GW) convolution has long been a theoretical cornerstone for smoothing on manifolds, its practical utility and the influence of underlying geometry on optimization have remained poorly understood. This paper bridges that gap by providing a new decomposition of the GW convolution, proposing a novel intrinsic gradient estimator, and demonstrating how the curvature of a space can actually facilitate optimization.
The Greene-Wu Convolution and the Decomposition Trick
The Greene-Wu convolution is a mathematical operation used to smooth functions on Riemannian manifolds. Traditionally, its complexity made it difficult to analyze and implement. The authors simplify this by introducing a "decomposition trick." They demonstrate that the GW convolution can be broken down into two manageable steps:
- A one-dimensional convolution along a specific tangent direction.
- An averaging step over a sphere within the local tangent space.
This decomposition globalizes the definition of the convolution, making it computationally tractable and allowing for a deeper analysis of how smoothing interacts with the manifold's intrinsic geometry.
Intrinsic Spherical Gradient Estimation
Existing gradient estimation methods often rely on embedding a manifold into a higher-dimensional Euclidean space and sampling Gaussian noise. This "ambient" approach is often inefficient, as it ignores the natural geometry of the space and scales poorly with dimension.
To address this, the authors propose a purely intrinsic Spherical Gradient Estimator. Instead of sampling from an ambient space, the estimator samples perturbation directions uniformly from a sphere within the local tangent space. It then uses the manifold’s exponential map to evaluate the function at these perturbed points. This approach ensures that the estimator is independent of any specific embedding, making it more robust and theoretically sound for high-dimensional manifolds.
One notable finding is that the manifold's injectivity radius—the distance at which the local geometry ceases to behave like flat space—is not a fundamental bottleneck for this method. The authors prove that as long as the function is geodesically $L_1$-smooth, finite-difference gradient estimation remains effective regardless of the injectivity radius.
The Geometric Advantage: Curvature and Convexity
A central insight of this research is that curvature is not merely a hurdle to be cleared; it can be an asset. The authors prove that the GW convolution interacts with the underlying curvature of the space in a way that can enhance the "optimizability" of a function. Specifically, on certain curved spaces, adding noise via the GW convolution can increase the minimum eigenvalue of the function’s Hessian. In practical terms, the geometry of the space can make a noisy function more convex, and therefore easier for optimization algorithms to navigate.
Theoretical Bounds and Empirical Results
The paper validates these concepts through both theoretical proofs and synthetic benchmarks on manifolds such as the unit sphere ($\mathbb{S}^n$), Hadamard manifolds, and SPD matrices.
Theoretical Improvements
The new spherical gradient estimator provides tighter theoretical error bounds compared to previous state-of-the-art methods. While traditional Gaussian estimators scale at $O((n+3)^{3/2})$, the proposed spherical estimator improves this to $O(n^{3/2})$. Furthermore, when integrated into an online gradient descent framework for Hadamard manifolds, the algorithm achieves a sublinear regret bound of $O(T^{3/4})$, ensuring convergence in stochastic environments.
Empirical Robustness
In experiments involving the calculation of the Riemannian center of mass for SPD matrices and optimization on saddle-like surfaces, the spherical estimator demonstrated superior robustness. While it maintained a similar bias to Gaussian baselines, it exhibited a much tighter distribution of errors (measured via the 4th moment of the gradient estimate). This leads to more stable updates and fewer divergent iterations in high-dimensional settings ($n=10$ to $30$).
Conclusion and Future Directions
This work advances the field of Riemannian optimization by providing a practical and theoretically grounded framework for gradient estimation. By leveraging the intrinsic geometry of the manifold and the smoothing properties of the Greene-Wu convolution, the authors show that optimization on curved spaces can be made more efficient and robust than previously thought.
Future research may involve scaling these methods to deep learning tasks, such as optimizing hyperbolic embeddings for hierarchical data, or refining the online learning regret bounds toward the theoretical optimum of $O(\sqrt{T})$. As machine learning continues to embrace non-Euclidean structures, these geometric insights will be essential for developing the next generation of optimization algorithms.
Summary updated