RATE OF CONVERGENCE OF THE NESTEROV ACCELERATED GRADIENT METHOD IN THE SUBCRITICAL CASE α ≤ 3
RATE OF CONVERGENCE OF THE NESTEROV ACCELERATED GRADIENT METHOD IN THE SUBCRITICAL CASE α ≤ 3
复制标题
DOI：
10.1051/cocv/2017083
复制
发表时间：
2019-04-08
影响因子：
1.4
通讯作者：
Riahi, Hassan
中科院分区：
文献类型：
--
作者：
Attouch, Hedy;Chbani, Zaki;Riahi, Hassan
在希尔伯特空间中，给定φ：H -> R为凸连续可微函数，α为正参数，考虑具有渐近消失阻尼（AVD）（α）（sic）（t）+ α/t（x）over dot（t）+delPhi（x（t））= 0的惯性动力系统.我们给出了（AVD）（alpha）生成的轨迹在t -> +无穷大时的收敛性质以及相应算法的迭代过程。实际上，如苏-博伊德-坎迪斯所示，α = 3的情况对应于内斯特罗夫的加速梯度法的连续版本，其中对于α>= 3，收敛速率Phi（x（t））- min Phi = O（t（-2））。我们的主要结果涉及亚临界情况α 0：当α从0到3时，系数p（α）线性增加到2，然后显示一个平台。然后，我们研究的轨迹收敛到最优解。作为一个新的结果，在一维框架下，对于临界值α = 3，我们证明了轨迹的收敛性。在本文的第二部分，我们研究了相关的前向后惯性算法的收敛性。他们的目标是解决结构化凸极小化问题的形式min {Theta：= Phi + Psi}，Phi光滑和Psi非光滑。连续动力学作为本研究的指导方针。对于迭代序列（x（k）），我们得到了类似的收敛速度：对于alpha 3 Theta（x（k））- min Theta = o（k（-2））.最后，我们表明，结果是强大的外部扰动。
In a Hilbert space setting H, given Phi : H -> R a convex continuously differentiable function, and alpha a positive parameter, we consider the inertial dynamic system with Asymptotic Vanishing Damping(AVD)(alpha) (sic)(t) + alpha/t(x) over dot (t) + del Phi(x(t)) = 0.Depending on the value of alpha with respect to 3, we give a complete picture of the convergence properties as t -> +infinity of the trajectories generated by (AVD)(alpha), as well as iterations of the corresponding algorithms. Indeed, as shown by Su-Boyd-Candes, the case alpha = 3 corresponds to a continuous version of the accelerated gradient method of Nesterov, with the rate of convergence Phi(x(t)) - min Phi = O(t(-2)) for alpha >= 3. Our main result concerns the subcritical case alpha 0: the coefficient p(alpha) increases linearly up to 2 when alpha goes from 0 to 3, then displays a plateau. Then we examine the convergence of trajectories to optimal solutions. As a new result, in the one-dimensional framework, for the critical value alpha = 3, we prove the convergence of the trajectories. In the second part of this paper, we study the convergence properties of the associated forward-backward inertial algorithms. They aim to solve structured convex minimization problems of the form min {Theta := Phi + Psi}, with Phi smooth and Psi nonsmooth. The continuous dynamics serves as a guideline for this study. We obtain a similar rate of convergence for the sequence of iterates (x(k)): for alpha 3 Theta(x(k)) - min Theta = o(k(-2)). Finally, we show that the results are robust with respect to external perturbations.