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
下载
关闭预览

相关内容

【新书】Python编程基础,669页pdf
专知会员服务
196+阅读 · 2019年10月10日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
105+阅读 · 2019年10月9日
MIT新书《强化学习与最优控制》
专知会员服务
280+阅读 · 2019年10月9日
图机器学习 2.2-2.4 Properties of Networks, Random Graph
图与推荐
10+阅读 · 2020年3月28日
鲁棒机器学习相关文献集
专知
8+阅读 · 2019年8月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
18+阅读 · 2019年1月7日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
【泡泡一分钟】用于平面环境的线性RGBD-SLAM
泡泡机器人SLAM
6+阅读 · 2018年12月18日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
随波逐流:Similarity-Adaptive and Discrete Optimization
我爱读PAMI
5+阅读 · 2018年2月6日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
【推荐】图像分类必读开创性论文汇总
机器学习研究会
14+阅读 · 2017年8月15日
强化学习族谱
CreateAMind
26+阅读 · 2017年8月2日
Arxiv
0+阅读 · 2020年12月16日
Arxiv
0+阅读 · 2020年12月15日
Arxiv
5+阅读 · 2017年12月14日
VIP会员
相关VIP内容
相关资讯
图机器学习 2.2-2.4 Properties of Networks, Random Graph
图与推荐
10+阅读 · 2020年3月28日
鲁棒机器学习相关文献集
专知
8+阅读 · 2019年8月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
18+阅读 · 2019年1月7日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
【泡泡一分钟】用于平面环境的线性RGBD-SLAM
泡泡机器人SLAM
6+阅读 · 2018年12月18日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
随波逐流:Similarity-Adaptive and Discrete Optimization
我爱读PAMI
5+阅读 · 2018年2月6日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
【推荐】图像分类必读开创性论文汇总
机器学习研究会
14+阅读 · 2017年8月15日
强化学习族谱
CreateAMind
26+阅读 · 2017年8月2日
Top
微信扫码咨询专知VIP会员