Adaptive restart of accelerated gradient methods under local quadratic growth condition
Adaptive restart of accelerated gradient methods under local quadratic growth condition
复制标题
局部二次增长条件下加速梯度法的自适应重启
DOI：
10.1093/imanum/drz007
复制
发表时间：
2019
影响因子：
2.1
通讯作者：
Fercoq O
中科院分区：
文献类型：
--
作者：
Fercoq O
通过分析局部二次增长条件下的加速近邻梯度算法，我们证明了在任何频率下重新启动这些算法都会得到一个全局线性收敛的算法。这一结果以前只在足够长的频率下才为人所知。然后，由于收敛速度依赖于频率和二次误差界之间的匹配，我们设计了一种方案，根据观察到的梯度映射范数的下降来自动调整重新启动的频率。与以前提出的方法相比，我们的算法具有更好的理论界来适应目标的二次误差界。在Lasso、正则化Logistic回归和全变差去噪问题上证明了该算法的有效性。
By analyzing accelerated proximal gradient methods under a local quadratic growth condition, we show that restarting these algorithms at any frequency gives a globally linearly convergent algorithm. This result was previously known only for long enough frequencies. Then as the rate of convergence depends on the match between the frequency and the quadratic error bound, we design a scheme to automatically adapt the frequency of restart from the observed decrease of the norm of the gradient mapping. Our algorithm has a better theoretical bound than previously proposed methods for the adaptation to the quadratic error bound of the objective. We illustrate the efficiency of the algorithm on Lasso, regularized logistic regression and total variation denoising problems.
登录
查看更多内容
DOI：
10.1137/130949993
发表时间：
2013-12
期刊：
SIAM J. Optim.
影响因子：
--
作者：
Olivier Fercoq;Peter Richtárik
通讯作者：
Olivier Fercoq;Peter Richtárik
影响因子：
2.1
作者：
Beck, Amir;Teboulle, Marc
通讯作者：
Teboulle, Marc
DOI：
10.1287/moor.2017.0889
发表时间：
2016-02
期刊：
Math. Oper. Res.
影响因子：
--
作者：
D. Drusvyatskiy;A. Lewis
通讯作者：
D. Drusvyatskiy;A. Lewis
使用粗略的强凸性估计重新启动加速梯度方法
DOI：
10.48550/arxiv.1609.07358
发表时间：
2016
期刊：
--
影响因子：
--
作者：
Fercoq O
通讯作者：
Fercoq O