Faster Gradient-Free Proximal Stochastic Methods for Nonconvex Nonsmooth Optimization
Faster Gradient-Free Proximal Stochastic Methods for Nonconvex Nonsmooth Optimization
复制标题
DOI：
10.1609/aaai.v33i01.33011503
复制
发表时间：
2019-02
期刊：
影响因子：
--
通讯作者：
Feihu Huang;Bin Gu;Zhouyuan Huo;Songcan Chen;Heng Huang
中科院分区：
文献类型：
--
作者：
Feihu Huang;Bin Gu;Zhouyuan Huo;Songcan Chen;Heng Huang
近端梯度方法在解决许多机器学习任务中发挥着重要作用，特别是对于非光滑问题。然而，在一些机器学习问题中，例如强盗模型和黑盒学习问题，近端梯度法可能会失败，因为这些问题的显式梯度很难或不可行。无梯度（零阶）方法可以解决这些问题，因为优化时只需要目标函数值。最近，第一个零阶近端随机算法被提出来解决非凸非光滑问题。然而，对于非凸问题，其收敛速度为O(1/√T)，明显慢于零阶随机算法的最佳收敛速度O(T1)，其中T为迭代次数。为了填补这一空白，在本文中，我们提出了一类更快的零阶近端随机方法，采用 SVRG 和 SAGA 的方差减少技术，分别表示为 ZO-ProxSVRG 和 ZO-ProxSAGA。在理论分析中，我们解决了真实梯度的无偏估计在零阶情况下不成立的主要挑战，而这在之前的 SVRG 和 SAGA 理论分析中是必需的。此外，我们证明 ZO-ProxSVRG 和 ZO-ProxSAGA 算法都具有 O(T1) 收敛速度。最后，实验结果验证了我们的算法比现有的零阶近端随机算法具有更快的收敛速度。
Proximal gradient method has been playing an important role to solve many machine learning tasks, especially for the nonsmooth problems. However, in some machine learning problems such as the bandit model and the black-box learning problem, proximal gradient method could fail because the explicit gradients of these problems are difficult or infeasible to obtain. The gradient-free (zeroth-order) method can address these problems because only the objective function values are required in the optimization. Recently, the first zeroth-order proximal stochastic algorithm was proposed to solve the nonconvex nonsmooth problems. However, its convergence rate is O(1/√T) for the nonconvex problems, which is significantly slower than the best convergence rate O(T1) of the zerothorder stochastic algorithm, where T is the iteration number. To fill this gap, in the paper, we propose a class of faster zeroth-order proximal stochastic methods with the variance reduction techniques of SVRG and SAGA, which are denoted as ZO-ProxSVRG and ZO-ProxSAGA, respectively. In theoretical analysis, we address the main challenge that an unbiased estimate of the true gradient does not hold in the zerothorder case, which was required in previous theoretical analysis of both SVRG and SAGA. Moreover, we prove that both ZO-ProxSVRG and ZO-ProxSAGA algorithms have O(T1) convergence rates. Finally, the experimental results verify that our algorithms have a faster convergence rate than the existing zeroth-order proximal stochastic algorithm.