This paper focuses on stochastic methods for solving smooth non-convex strongly-concave min-max problems, which have received increasing attention due to their potential applications in deep learning (e.g., deep AUC maximization, distributionally robust optimization). However, most of the existing algorithms are slow in practice, and their analysis revolves around the convergence to a nearly stationary point. We consider leveraging the Polyak-\L ojasiewicz (PL) condition to design faster stochastic algorithms with stronger convergence guarantee. Although PL condition has been utilized for designing many stochastic minimization algorithms, their applications for non-convex min-max optimization remain rare. In this paper, we propose and analyze a generic framework of proximal epoch-based method with many well-known stochastic updates embeddable. Fast convergence is established in terms of both {\bf the primal objective gap and the duality gap}. Compared with existing studies, (i) our analysis is based on a novel Lyapunov function consisting of the primal objective gap and the duality gap of a regularized function, and (ii) the results are more comprehensive with improved rates that have better dependence on the condition number under different assumptions. We also conduct deep and non-deep learning experiments to verify the effectiveness of our methods.


翻译:本文侧重于解决平滑的非混凝土强凝固的微轴问题的随机方法,这些问题因其在深层学习中的潜在应用而日益受到重视(如深层AUC最大化、分布强力优化等),然而,大多数现有算法在实践中进展缓慢,其分析围绕接近固定点的趋同点。我们考虑利用Polyak-Lojasiewicz(PL)条件来设计更快的随机算法,并有更强的趋同保证。尽管PL条件被用于设计许多随机最小化算法,但非对混凝土微轴优化的应用仍然很少。在本文件中,我们提出和分析一个基于准亚氏法方法的通用框架,许多众所周知的随机化更新可以嵌入其中。我们从原始目标差距和双重性差距的角度建立了快速的趋同点。与现有的研究相比,(i)我们的分析基于由原始目标差距和二元性优化法组成的新型Lyapunov功能,而原始目标差距和二元性优化的双重性假设在常规性实验中也存在更好的可靠性差距。

0
下载
关闭预览

相关内容

FAST:Conference on File and Storage Technologies。 Explanation:文件和存储技术会议。 Publisher:USENIX。 SIT:http://dblp.uni-trier.de/db/conf/fast/
专知会员服务
50+阅读 · 2020年12月14日
商业数据分析,39页ppt
专知会员服务
159+阅读 · 2020年6月2日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
已删除
将门创投
7+阅读 · 2019年10月10日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
逆强化学习几篇论文笔记
CreateAMind
9+阅读 · 2018年12月13日
【SIGIR2018】五篇对抗训练文章
专知
12+阅读 · 2018年7月9日
Soft-NMS – Improving Object Detection With One Line of Code
统计学习与视觉计算组
6+阅读 · 2018年3月30日
强化学习族谱
CreateAMind
26+阅读 · 2017年8月2日
Optimality and Stability in Non-Convex Smooth Games
Arxiv
0+阅读 · 2022年2月3日
VIP会员
相关VIP内容
专知会员服务
50+阅读 · 2020年12月14日
商业数据分析,39页ppt
专知会员服务
159+阅读 · 2020年6月2日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
相关资讯
已删除
将门创投
7+阅读 · 2019年10月10日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
逆强化学习几篇论文笔记
CreateAMind
9+阅读 · 2018年12月13日
【SIGIR2018】五篇对抗训练文章
专知
12+阅读 · 2018年7月9日
Soft-NMS – Improving Object Detection With One Line of Code
统计学习与视觉计算组
6+阅读 · 2018年3月30日
强化学习族谱
CreateAMind
26+阅读 · 2017年8月2日
Top
微信扫码咨询专知VIP会员