摘要
非凸极小极大问题是近期国际上优化与机器学习、信号处理等交叉领域的一个重要研究前沿和热点,包括对抗学习、强化学习、分布式非凸优化等前沿研究方向的一些关键科学问题都归结为该类问题。国际上凸-凹极小极大问题的研究已取得很好的成果,但非凸极小极大问题不同于凸-凹极小极大问题,是有其自身结构的非凸非光滑优化问题,理论研究和求解难度都更具挑战性,一般都是NP-难的。重点介绍非凸极小极大问题的优化算法和复杂度分析方面的最新进展。
The non-convex minimax problem is an important research front and hot spot in the cross-fields of optimization,machine learning,signal processing,etc.Some key scientific issues in frontier research directions such as adversarial learning,reinforcement learning,and distributed non-convex optimization,all belong to this type of problem.Internationally,the research on convex-concave minimax problems has achieved good results.However,the non-convex minimax problem is different from the convex-concave minimax problem,and it is a non-convex and non-smooth optimization problem with its own structure,for which,the theoretical analysis and the algorithm design are more challenging than that of the convex-concave minimax problem,and it is generally NPhard.This paper focuses on the latest developments in optimization algorithms and complexity analysis for non-convex minimax problems.
作者
徐姿
张慧灵
XU Zi;ZHANG Huiling(Department of Mathematics,College of Sciences,Shanghai University,Shanghai 200444,China)
出处
《运筹学学报》
CSCD
北大核心
2021年第3期74-86,共13页
Operations Research Transactions
基金
国家自然科学基金(Nos.12071279,11771208)
上海市自然科学基金(No.20ZR1420600)。
关键词
极小极大优化问题
复杂度分析
一阶算法
(随机)梯度下降上升算法
交替梯度投影算法
非凸优化
机器学习
minimax optimization problem
complexity analysis
first order method
(stochastic)gradient descent ascent algorithm
alternating gradient projection algorithm
nonconvex optimization
machine learning