Zeroth-order algorithms for nonconvex–strongly-concave minimax problems with improved complexities
Zeroth-order algorithms for nonconvex–strongly-concave minimax problems with improved complexities
复制标题
用于非凸强凹极小极大问题的零阶算法，并提高了复杂性
DOI：
10.1007/s10898-022-01160-0
复制
发表时间：
2022
影响因子：
1.8
通讯作者：
Razaviyayn, Meisam
中科院分区：
文献类型：
--
作者：
Wang, Zhongruo;Balasubramanian, Krishnakumar;Ma, Shiqian;Razaviyayn, Meisam
在本文中，我们研究零阶算法的极大极小优化问题是非凸的一个变量和强凹的其他变量。最近，由于它们在现代机器学习任务中的应用，这种极大极小优化问题引起了人们的极大关注。我们首先考虑一个确定性的版本的问题。我们设计和分析了零阶梯度下降上升（ZO-GDA）算法，并提供了改进的结果相比，现有的作品，在预言复杂度。我们还提出了零阶梯度下降多步上升（ZO-GDMSA）算法，显着改善了ZO-GDA的预言复杂度。然后，我们考虑随机版本的ZO-GDA和ZO-GDMSA，处理随机非凸极大极小问题。在这种情况下，我们在两个关于随机梯度的假设下提供了预言复杂性结果：（i）一致有界方差假设，这在传统的随机优化中很常见，以及（ii）强增长条件（SGC），这已经被现代过参数化机器学习模型所满足。我们建立的SGC假设下，随机算法的复杂性相匹配的确定性算法。数值实验支持我们的理论结果。
In this paper, we study zeroth-order algorithms for minimax optimization problems that are nonconvex in one variable and strongly-concave in the other variable. Such minimax optimization problems have attracted significant attention lately due to their applications in modern machine learning tasks. We first consider a deterministic version of the problem. We design and analyze the Zeroth-Order Gradient Descent Ascent (ZO-GDA) algorithm, and provide improved results compared to existing works, in terms of oracle complexity. We also propose the Zeroth-Order Gradient Descent Multi-Step Ascent (ZO-GDMSA) algorithm that significantly improves the oracle complexity ofZO-GDA. We then consider stochastic versions ofZO-GDAandZO-GDMSA, to handle stochastic nonconvex minimax problems. For this case, we provide oracle complexity results under two assumptions on the stochastic gradient: (i) the uniformly bounded variance assumption, which is common in traditional stochastic optimization, and (ii) the Strong Growth Condition (SGC), which has been known to be satisfied by modern over-parameterized machine learning models. We establish that under the SGC assumption, the complexities of the stochastic algorithms match that of deterministic algorithms. Numerical experiments are presented to support our theoretical results.
登录
查看更多内容
学习动态和有性竞争物种的共同进化
DOI：
--
发表时间：
2017
期刊：
Information Technology Convergence and Services
影响因子：
--
作者：
G. Piliouras;L. Schulman
通讯作者：
L. Schulman
Rényi 公平推理
DOI：
--
发表时间：
2019
期刊：
International Conference on Learning Representations
影响因子：
--
作者：
Sina Baharlouei;Maher Nouiehed;Meisam Razaviyayn
通讯作者：
Meisam Razaviyayn
影响因子：
1.8
作者：
D. Bertsimas;O. Nohadani
通讯作者：
D. Bertsimas;O. Nohadani
影响因子：
5.4
作者：
Songtao Lu;Ioannis C. Tsaknakis;Mingyi Hong;Yongxin Chen
通讯作者：
Songtao Lu;Ioannis C. Tsaknakis;Mingyi Hong;Yongxin Chen
影响因子：
3
作者：
K. Balasubramanian;Saeed Ghadimi
通讯作者：
K. Balasubramanian;Saeed Ghadimi