In this paper, we aim at unifying, simplifying, and improving the convergence rate analysis of Lagrangian-based methods for convex optimization problems. We first introduce the notion of nice primal algorithmic map, which plays a central role in the unification and in the simplification of the analysis of all Lagrangian-based methods. Equipped with a nice primal algorithmic map, we then introduce a versatile generic scheme, which allows for the design and analysis of Faster LAGrangian (FLAG) methods with a new provably sublinear rate of convergence expressed in terms of functions values and feasibility violation of the original (non-ergodic) generated sequence. To demonstrate the power and versatility of our approach and results, we show that all well-known iconic Lagrangian-based schemes admit a nice primal algorithmic map, and hence share the new faster rate of convergence results within their corresponding FLAG.


翻译:在本文中,我们的目标是统一、简化和改进对基于拉格朗日法的方法的趋同率分析,以便解决锥形优化问题。我们首先引入了精美原始算法图的概念,该图在统一和简化分析所有基于拉格朗日法的方法方面发挥着核心作用。我们用一个精美原始算法图,然后引入一个多功能通用方案,以便设计和分析快速拉格朗日法(FLAG)方法,其新的可辨的次线性趋同率表现在功能值和违反原始(非电子)生成序列的可行性方面。为了展示我们的方法和结果的力量和多功能,我们展示出所有著名的标志性拉格朗日法办法都接受一个良好的原始算法图,从而在相应的FLAG中分享新的更快的趋同率。

0
下载
关闭预览

相关内容

【干货书】机器学习速查手册,135页pdf
专知会员服务
125+阅读 · 2020年11月20日
专知会员服务
52+阅读 · 2020年11月3日
专知会员服务
161+阅读 · 2020年1月16日
17种深度强化学习算法用Pytorch实现
新智元
30+阅读 · 2019年9月16日
Transferring Knowledge across Learning Processes
CreateAMind
28+阅读 · 2019年5月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
RL 真经
CreateAMind
5+阅读 · 2018年12月28日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
17+阅读 · 2018年12月24日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
计算机视觉近一年进展综述
机器学习研究会
9+阅读 · 2017年11月25日
gan生成图像at 1024² 的 代码 论文
CreateAMind
4+阅读 · 2017年10月31日
Arxiv
0+阅读 · 2020年11月28日
Arxiv
5+阅读 · 2017年12月14日
VIP会员
相关资讯
17种深度强化学习算法用Pytorch实现
新智元
30+阅读 · 2019年9月16日
Transferring Knowledge across Learning Processes
CreateAMind
28+阅读 · 2019年5月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
RL 真经
CreateAMind
5+阅读 · 2018年12月28日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
17+阅读 · 2018年12月24日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
计算机视觉近一年进展综述
机器学习研究会
9+阅读 · 2017年11月25日
gan生成图像at 1024² 的 代码 论文
CreateAMind
4+阅读 · 2017年10月31日
Top
微信扫码咨询专知VIP会员