Accelerated gradient methods for nonconvex nonlinear and stochastic programming
Accelerated gradient methods for nonconvex nonlinear and stochastic programming
复制标题
DOI：
10.1007/s10107-015-0871-8
复制
发表时间：
2016-03-01
影响因子：
2.7
通讯作者：
Lan, Guanghui
中科院分区：
文献类型：
--
作者：
Ghadimi, Saeed;Lan, Guanghui
在本文中，我们将著名的涅斯捷罗夫加速梯度（AG）方法进行了推广，该方法最初是为凸光滑优化而设计的，用于解决非凸且可能是随机的优化问题。我们证明，通过恰当地指定步长策略，AG方法在利用一阶信息解决一般非凸光滑优化问题时，展现出了与梯度下降法类似的已知最佳收敛速度。然后，我们考虑一类重要的复合优化问题，并表明AG方法能够统一地解决它们，即，即使问题是非凸的，也能像在凸情形下一样使用相同的积极步长策略。我们证明，如果复合问题是凸的，AG方法呈现出最优收敛速度，如果问题是非凸的，则改进了已知的最佳收敛速度。基于AG方法，我们还提出了新的非凸随机逼近方法，并表明它们能够改进一些现有的非凸随机优化收敛速度。据我们所知，这是文献中首次确立AG方法在解决非凸非线性规划问题时的收敛性。
In this paper, we generalize the well-known Nesterov's accelerated gradient (AG) method, originally designed for convex smooth optimization, to solve nonconvex and possibly stochastic optimization problems. We demonstrate that by properly specifying the stepsize policy, the AG method exhibits the best known rate of convergence for solving general nonconvex smooth optimization problems by using first-order information, similarly to the gradient descent method. We then consider an important class of composite optimization problems and show that the AG method can solve them uniformly, i.e., by using the same aggressive stepsize policy as in the convex case, even if the problem turns out to be nonconvex. We demonstrate that the AG method exhibits an optimal rate of convergence if the composite problem is convex, and improves the best known rate of convergence if the problem is nonconvex. Based on the AG method, we also present new nonconvex stochastic approximation methods and show that they can improve a few existing rates of convergence for nonconvex stochastic optimization. To the best of our knowledge, this is the first time that the convergence of the AG method has been established for solving nonconvex nonlinear programming in the literature.