当前位置: 首页 > 新闻中心 > 学术活动 > 正文

Nonsmooth Nonconvex-Nonconcave Minimax Optimization: Algorithm Design and Convergence Analysis

发布日期:2024-01-02点击数:

报告人:李佳锦(斯坦福大学)

时间:2024年01月08日 10:00-

腾讯会议ID:146 842 044


摘要:Nonsmooth, nonconvex-nonconcave minimax optimization has gained widespread interest in recent years in machine learning and data science. However, much of the existing work focuses on a variant of the gradient descent-ascent (GDA) algorithm, which exhibits several limitations:

 (1) They are only applicable to smooth problems, where gradient information is available. 

 (2) They may not converge globally, and they may suffer from limit cycles.

 (3) No single algorithm can be universally applied to all minimax optimization problems, such as nonconvex-concave and convex-nonconcave minimax settings.

In this talk, we will tackle these challenges for a class of structured nonsmooth, nonconvex-nonconcave minimax optimization problems. The main difficulty in algorithmic design for minimax optimization is balancing the primal decrease and dual increase in an efficient way. To overcome this difficulty, we develop a novel primal-dual error bound that serves as the foundation for both convergence analysis and algorithmic design. This gives rise to a new algorithm design principle known as optimal primal-dual balancing. Following this principle, we develop a single algorithm, doubly smoothed (prox-linear)/ gradient descent ascent, which universally works for all minimax optimization problems. Our algorithm finds an $\epsilon$-stationary point in $O(epsilon^-4)$ iterations. If additional regularity is assumed (weaker than standard assumptions imposed in the literature), we obtain sharper, even optimal, iteration complexity results. We showcase the effectiveness of our algorithm in getting rid of limit cycles in challenging nonconvex-nonconcave minimax optimization problems.


简介:Currently, Jiajin Li is a postdoctoral researcher in the Department of Management Science and Engineering (MS&E) at Stanford University, where she is working with Prof. Jose Blanchet and Prof. Yinyu Ye. Previously, Jiajin received her Ph.D. degree in the Department of Systems Engineering and Engineering Management from the Chinese University of Hong Kong (CUHK) in 2021, where she is advised by Prof. Anthony Man-Cho So. From August 2020 to March 2021, Jiajin worked as a visiting Ph.D. student in the Geometric Data Processing Group at the Massachusetts Institute of Technology (MIT) under the guidance of Prof. Justin Solomon. Before joining CUHK, Jiajin obtained her bachelor's degree in Statistics from Chongqing University in 2017. Her research interests lie in mathematical optimization and its applications in data-driven decision making, machine learning, and data science. Most of her research have been published in top machine learning conferences, e.g., ICML, NeurIPS, ICLR.


邀请人:夏小超


欢迎广大师生积极参与!


关于我们
太阳成集团tyc539的前身是始建于1929年的太阳成集团理学院和1937年建立的太阳成集团商学院,理学院是太阳成集团最早设立的三个学院之一,首任经理为数学家何鲁先生。