The Barzilai-Borwein (BB) method has demonstrated great empirical success in nonlinear optimization. However, the convergence speed of BB method is not well understood, as the known convergence rate of BB method for quadratic problems is much worse than the steepest descent (SD) method. Therefore, there is a large discrepancy between theory and practice. To shrink this gap, we prove that the BB method converges $R$-linearly at a rate of $1-1/\kappa$, where $\kappa$ is the condition number, for strongly convex quadratic problems. In addition, an example with the theoretical rate of convergence is constructed, indicating the tightness of our bound.


翻译:Barzilai-Borwein (BB) 方法在非线性优化方面表现出巨大的经验成功,但是,BB方法的趋同速度没有很好地理解,因为已知的BB方法对二次曲线问题的趋同速度比最陡峭的下降(SD)方法要差得多,因此,理论与实践之间有很大的差异。为了缩小这一差距,我们证明BB方法以1-1美元/kappa美元(美元是严重二次曲线问题的条件数)的汇率,即1-1美元/kappa美元(卡帕美元)为线性趋同速度。此外,还树立了一个理论趋同速度的例子,表明我们的界限很紧。

0
下载
关闭预览

相关内容

Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
【Google】平滑对抗训练,Smooth Adversarial Training
专知会员服务
48+阅读 · 2020年7月4日
阿里巴巴达摩院发布「2020十大科技趋势」
专知会员服务
106+阅读 · 2020年1月2日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
已删除
将门创投
3+阅读 · 2019年1月15日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
【SIGIR2018】五篇对抗训练文章
专知
12+阅读 · 2018年7月9日
Arxiv
0+阅读 · 2021年3月16日
Arxiv
0+阅读 · 2021年3月14日
VIP会员
相关资讯
已删除
将门创投
3+阅读 · 2019年1月15日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
【SIGIR2018】五篇对抗训练文章
专知
12+阅读 · 2018年7月9日
Top
微信扫码咨询专知VIP会员