Stochastic Zeroth-Order Riemannian Derivative Estimation and Optimization
Stochastic Zeroth-Order Riemannian Derivative Estimation and Optimization
复制标题
DOI：
10.1287/moor.2022.1302
复制
发表时间：
2022-09
期刊：
影响因子：
--
通讯作者：
Jiaxiang Li;K. Balasubramanian;Shiqian Ma
中科院分区：
文献类型：
--
作者：
Jiaxiang Li;K. Balasubramanian;Shiqian Ma
我们考虑嵌入欧氏空间的黎曼子流形上的随机零阶优化问题，其中的任务是解决仅具有噪声目标函数赋值的黎曼子流形上的优化问题。为此，我们的主要贡献是基于黎曼版本的高斯平滑技术，从噪声目标函数评估中提出黎曼梯度和海森的估计器。当函数仅在流形上定义时，所提出的估计器克服了流形约束的非线性的困难和使用欧几里得高斯平滑技术时出现的问题。我们使用所提出的估计量来解决目标函数在以下设置下的黎曼优化问题：(I)随机和梯度-Lipschitz(在非凸和测地线凸设置下)，(Ii)梯度-Lipschitz和非光滑函数的和，以及(Iii)Hessian-Lipschitz。对于这些设置，我们分析了算法的先验复杂性，得到了适当定义的ϵ-平稳点或ϵ-近似局部极小点的概念。值得注意的是，我们的复杂性与环境欧几里德空间的维度无关，并且仅取决于所考虑的流形的内在维度。通过仿真结果和机器人黑箱刚度控制和神经网络黑箱攻击的实际应用，验证了算法的适用性。
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.