Zeroth-Order Nonconvex Stochastic Optimization: Handling Constraints, High Dimensionality, and Saddle Points
Zeroth-Order Nonconvex Stochastic Optimization: Handling Constraints, High Dimensionality, and Saddle Points
复制标题
DOI：
10.1007/s10208-021-09499-8
复制
发表时间：
2018-09
影响因子：
3
通讯作者：
K. Balasubramanian;Saeed Ghadimi
中科院分区：
文献类型：
--
作者：
K. Balasubramanian;Saeed Ghadimi
在本文中，我们提出并分析了非凸和凸优化的零阶随机逼近算法，重点是解决约束优化，高维设置和鞍点避免。为了处理约束优化，我们首先提出了条件梯度算法的推广，仅使用零阶信息实现与标准随机梯度算法类似的速率。为了便于零阶优化在高维，我们探讨了结构稀疏性假设的优点。具体来说，（i）我们强调了一个隐式正则化现象，其中零阶信息的标准随机梯度算法通过改变步长来适应手头问题的稀疏性，（ii）提出了一个零阶信息的截断随机梯度算法，其收敛速度仅依赖于多维。接下来我们重点讨论如何避免非凸设置中的鞍点。为此，我们解释高斯平滑技术的基础上估计梯度的零阶信息作为一个实例的一阶斯泰因的身份。在此基础上，我们提供了一个新的线性（在维）时间估计的Hessian矩阵的功能，仅使用零阶信息，这是基于二阶Stein的身份。然后，我们提供了一个零阶变体的三次正则化牛顿方法，以避免鞍点，并讨论其收敛到局部极小值的速度。
In this paper, we propose and analyze zeroth-order stochastic approximation algorithms for nonconvex and convex optimization, with a focus on addressing constrained optimization, high-dimensional setting, and saddle point avoiding. To handle constrained optimization, we first propose generalizations of the conditional gradient algorithm achieving rates similar to the standard stochastic gradient algorithm using only zeroth-order information. To facilitate zeroth-order optimization in high dimensions, we explore the advantages of structural sparsity assumptions. Specifically, (i) we highlight an implicit regularization phenomenon where the standard stochastic gradient algorithm with zeroth-order information adapts to the sparsity of the problem at hand by just varying the step size and (ii) propose a truncated stochastic gradient algorithm with zeroth-order information, whose rate of convergence depends only poly-logarithmically on the dimensionality. We next focus on avoiding saddle points in nonconvex setting. Toward that, we interpret the Gaussian smoothing technique for estimating gradient based on zeroth-order information as an instantiation of first-order Stein’s identity. Based on this, we provide a novel linear-(in dimension) time estimator of the Hessian matrix of a function using only zeroth-order information, which is based on second-order Stein’s identity. We then provide a zeroth-order variant of cubic regularized Newton method for avoiding saddle points and discuss its rate of convergence to local minima.