Zeroth-order Optimization on Riemannian Manifolds

Jiaxiang Li, Krishnakumar Balasubramanian, Shiqian MaarXiv 2020 · arXiv · OpenReview

TL;DR

This paper introduces novel methods for optimizing functions defined on curved spaces (Riemannian manifolds) when you can only get noisy evaluations of the function, not its exact gradient. This is crucial for real-world problems in robotics and AI where direct gradient computation is impossible. The key innovation is a way to estimate the "Riemannian gradient" and "Hessian" using only these noisy function values, leading to algorithms that are efficient and independent of the ambient space's dimension.

What Problem Does This Paper Address?

Many optimization problems in machine learning and engineering involve finding the best parameters within a constrained space. Often, these spaces aren't simple flat Euclidean spaces but have inherent curvature, like the set of all possible rotation matrices or positive definite matrices. These are called Riemannian manifolds. Furthermore, in many practical scenarios, we can't analytically compute the gradient (the direction of steepest ascent) of our objective function. Instead, we can only get noisy measurements of the function's value at different points. This is known as zeroth-order optimization.

Combining these challenges, the paper addresses stochastic zeroth-order optimization on Riemannian manifolds. This means optimizing a function on a curved space using only noisy function evaluations, which is a significant hurdle because standard optimization techniques rely on gradients and are designed for flat spaces. Existing methods for zeroth-order optimization struggle when applied to manifolds due to the complex geometry, and existing Riemannian optimization methods typically require exact gradients.

Methods

The core contribution of this paper is the development of zeroth-order Riemannian gradient and Hessian estimators. These estimators are inspired by the "Gaussian smoothing" technique used in Euclidean zeroth-order optimization but are adapted for the manifold setting.

Here's a breakdown of the key methodological aspects:

  • Riemannian Gaussian Smoothing: Instead of sampling from a standard Gaussian in the ambient Euclidean space, the authors sample Gaussian random vectors on the tangent space of the manifold at the current point. This ensures that the sampled directions are relevant to the manifold's geometry.
  • Retraction Operator: To evaluate the function at points perturbed by these tangent space vectors, they use a "retraction" operator. This is a way to map a tangent vector back onto the manifold, respecting its curved structure. This is crucial because standard Euclidean addition (x + u) might lead outside the manifold.
  • Zeroth-Order Gradient Estimator: The proposed gradient estimator, $g_\mu(x)$, is derived from the difference between function evaluations at a perturbed point (using the retraction) and the current point, scaled by a smoothing parameter $\mu$.
  • Zeroth-Order Hessian Estimator: Similarly, a Hessian estimator, $H_\mu(x)$, is developed using function evaluations at points perturbed in two opposite directions along the manifold, again leveraging the retraction and smoothing parameter.
  • Optimization Algorithms: These estimators are then integrated into standard optimization algorithms adapted for manifolds:
  • Zeroth-Order Riemannian Gradient Descent (ZO-RGD): For smooth objective functions.
  • Zeroth-Order Riemannian Stochastic Gradient Descent (ZO-RSGD): For stochastic objective functions (where the function is an expectation).
  • Zeroth-Order Stochastic Riemannian Proximal Gradient Method (ZO-SManPG): For problems with non-smooth but convex components.
  • Zeroth-Order Riemannian Stochastic Cubic Regularized Newton's Method (ZO-RSCRN): For escaping saddle points and achieving faster convergence.

A key theoretical result is that the oracle complexities (number of function evaluations needed) of these algorithms depend only on the intrinsic dimension of the manifold, not the dimension of the ambient Euclidean space, which is a significant advantage for high-dimensional problems with low-dimensional manifold structures.

Datasets

The paper does not introduce new datasets. Instead, it uses:

  • Simulated data: For various experiments to evaluate the performance of the proposed algorithms.
  • Real-world applications:
    • Robotics: Optimizing stiffness matrices for a 7-DOF Franka Emika Panda robot.
  • Deep Neural Networks (DNNs): Developing black-box adversarial attacks on DNNs.

Key Insights and Ideas

  • Manifold Geometry Matters for Zeroth-Order: Simply applying Euclidean zeroth-order methods to manifolds doesn't work because standard operations like adding vectors can push you off the manifold. The paper shows how to correctly incorporate manifold geometry using retractions and tangent space sampling.
  • Gradient and Hessian Estimation is Key: The ability to reliably estimate Riemannian gradients and Hessians from noisy function evaluations is the linchpin for extending zeroth-order optimization to manifolds. The proposed estimators are the technical heart of the paper.
  • Dimension Independence is a Game-Changer: The fact that the algorithms' complexity depends on the manifold's intrinsic dimension ($d$) rather than the ambient Euclidean dimension ($n$) is a major theoretical breakthrough. This is crucial for problems where the data lies on a low-dimensional manifold embedded in a high-dimensional space.
  • Bridging Theory and Practice: The paper demonstrates the practical applicability of these theoretical advancements through simulations and real-world examples in robotics and adversarial attacks on DNNs, showing competitive performance against first-order methods.

Key Results

  • Novel Estimators: The paper proposes and analyzes novel zeroth-order estimators for Riemannian gradients and Hessians.
  • Theoretical Guarantees: The proposed algorithms (ZO-RGD, ZO-RSGD, ZO-SManPG, ZO-RSCRN) achieve theoretical convergence guarantees (e-stationary points or e-approximate local minimizers) for various problem settings.
  • Dimension-Independent Complexity: The oracle complexity of the algorithms is independent of the ambient dimension $n$ and depends only on the intrinsic manifold dimension $d$. For example, for smooth optimization, the complexity is $O(d/\epsilon^2)$.
  • Practical Performance: Numerical experiments show that the proposed zeroth-order methods are comparable to their first-order counterparts in terms of convergence speed and effectiveness, even though they use less information.
  • Real-World Applications: The methods are successfully applied to:
  • Robotics: Optimizing robot stiffness control.
  • Adversarial Attacks on DNNs: Generating more robust adversarial examples that respect manifold constraints.

Limitations and Future Work

  • Computational Cost of Estimators: While the theoretical complexity is good, the practical implementation of the estimators might still be computationally intensive, especially for complex manifolds or when many samples are needed.
  • Scalability to Higher Dimensions: The authors mention that scaling up the ZO-RSCRN method to work in higher dimensions, particularly using variance reduction techniques, is an interesting problem for future work.
  • General Manifolds: The current work focuses on embedded submanifolds. Extending the methodology to more general Riemannian manifolds where explicit embeddings are not available could be a future direction.
  • Hyperparameter Tuning: Like most optimization algorithms, the performance of these methods can be sensitive to hyperparameter choices (e.g., smoothing parameter $\mu$, step size $\eta$). Further research into adaptive methods for these parameters could be beneficial.

Summary updated

Abstract

We consider stochastic zeroth-order optimization over Riemannian submanifolds embedded in Euclidean space, where the task is to solve Riemannian optimization problem with only noisy objective function evaluations. Towards this, our main contribution is to propose estimators of the Riemannian gradient and Hessian from noisy objective function evaluations, based on a Riemannian version of the Gaussian smoothing technique. The proposed estimators overcome the difficulty of the non-linearity of the manifold constraint and the issues that arise in using Euclidean Gaussian smoothing techniques when the function is defined only over the manifold. We use the proposed estimators to solve Riemannian optimization problems in the following settings for the objective function: (i) stochastic and gradient-Lipschitz (in both nonconvex and geodesic convex settings), (ii) sum of gradient-Lipschitz and non-smooth functions, and (iii) Hessian-Lipschitz. For these settings, we analyze the oracle complexity of our algorithms to obtain appropriately defined notions of $\epsilon$-stationary point or $\epsilon$-approximate local minimizer. Notably, our complexities are independent of the dimension of the ambient Euclidean space and depend only on the intrinsic dimension of the manifold under consideration. We demonstrate the applicability of our algorithms by simulation results and real-world applications on black-box stiffness control for robotics and black-box attacks to neural networks.
BibTeX
@misc{li2020zeroth,
  author = {Jiaxiang Li and Krishnakumar Balasubramanian and Shiqian Ma},
  title = {{Zeroth-order Optimization on Riemannian Manifolds}},
  year = {2020},
  eprint = {2003.11238},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2003.11238},
}
Figure