Stochastic Zeroth-Order Riemannian Derivative Estimation and Optimization

Jiaxiang Li (), Krishnakumar Balasubramanian () and Shiqian Ma ()
Additional contact information
Jiaxiang Li: Department of Mathematics, University of California, Davis, California 95616
Krishnakumar Balasubramanian: Department of Statistics, University of California, Davis, California 95616
Shiqian Ma: Department of Mathematics, University of California, Davis, California 95616; Department of Computational Applied Mathematics and Operations Research, Rice University, Houston, Texas 77005

Mathematics of Operations Research, 2023, vol. 48, issue 2, 1183-1211

Abstract: We consider stochastic zeroth-order optimization over Riemannian submanifolds embedded in Euclidean space, where the task is to solve Riemannian optimization problems with only noisy objective function evaluations. Toward 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 nonlinearity of the manifold constraint and 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 nonsmooth functions, and (iii) Hessian-Lipschitz. For these settings, we analyze the oracle complexity of our algorithms to obtain appropriately defined notions of ϵ -stationary point or ϵ -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.

Keywords: 90C30; Riemannian optimization; manifold optimization; zeroth-order optimization; black-box attack (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2022.1302 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:48:y:2023:i:2:p:1183-1211

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().