In this work, we introduce two algorithmic frameworks, named Bregman extragradient method and Bregman extrapolation method, for solving saddle point problems. The proposed frameworks not only include the well-known extragradient and optimistic gradient methods as special cases, but also generate new variants such as sparse extragradient and extrapolation methods. With the help of the recent concept of relative Lipschitzness and some Bregman distance related tools, we are able to show certain upper bounds in terms of Bregman distances for gap-type measures. Further, we use those bounds to deduce the convergence rate of $\cO(1/k)$ for the Bregman extragradient and Bregman extrapolation methods applied to solving smooth convex-concave saddle point problems. Our theory recovers the main discovery made in [Mokhtari et al. (2020), SIAM J. Optim., 20, pp. 3230-3251] for more general algorithmic frameworks with weaker assumptions via a conceptually different approach.


翻译:在这项工作中,我们引入了两个算法框架,即Bregman 外增法和Bregman外加法,以解决马鞍问题。提议的框架不仅包括作为特殊情况的众所周知的远增法和乐观梯度方法,而且还产生新的变体,如稀疏的外增法和外加法方法。借助最近相对利普施特尼的概念和一些与布雷格曼距离有关的工具,我们能够用布雷格曼距离的某种上限来显示差距类型计量。此外,我们利用这些界限来推断布雷格曼外增法和布雷格曼外加法方法的趋同率为$\cO(1/k)美元,用于解决顺流的 convex-cavefart point 问题。我们的理论恢复了在[Mokhtari等人(202020年),SIAM J.Optim.,20,第3230-3251页]中发现的主要发现,通过概念不同的方法,较弱的一般算法框架。

0
下载
关闭预览

相关内容

在数学中,鞍点或极大极小点是函数图形表面上的一点,其正交方向上的斜率(导数)都为零,但它不是函数的局部极值。鞍点是在某一轴向(峰值之间)有一个相对最小的临界点,在交叉轴上有一个相对最大的临界点。
【Google】平滑对抗训练,Smooth Adversarial Training
专知会员服务
48+阅读 · 2020年7月4日
ExBert — 可视化分析Transformer学到的表示
专知会员服务
31+阅读 · 2019年10月16日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
RL 真经
CreateAMind
5+阅读 · 2018年12月28日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
【NIPS2018】接收论文列表
专知
5+阅读 · 2018年9月10日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
暗通沟渠:Multi-lingual Attention
我爱读PAMI
7+阅读 · 2018年2月24日
随波逐流:Similarity-Adaptive and Discrete Optimization
我爱读PAMI
5+阅读 · 2018年2月6日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
VIP会员
相关VIP内容
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
RL 真经
CreateAMind
5+阅读 · 2018年12月28日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
【NIPS2018】接收论文列表
专知
5+阅读 · 2018年9月10日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
暗通沟渠:Multi-lingual Attention
我爱读PAMI
7+阅读 · 2018年2月24日
随波逐流:Similarity-Adaptive and Discrete Optimization
我爱读PAMI
5+阅读 · 2018年2月6日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员