Gradient Norm Regularization Second-Order Algorithms for Solving Nonconvex-Strongly Concave Minimax Problems

报告摘要：In this talk, we study second-order algorithms for the convex-concave minimax problem, which has attracted much attention in many fields such as machine learning in recent years. We propose a Lipschitz-free cubic regularization (LF-CR) algorithm for solving the convex-concave minimax optimization problem without knowing the Lipschitz constant. It can be shown that the iteration complexity of the LF-CR algorithm to obtain an $\epsilon$-optimal solution with respect to the restricted primal-dual gap is upper bounded by $\mathcal{O}(\rho^{2/3}\|z_0-z^*\|^2\epsilon^{-2/3})$ , where $z_0=(x_0,y_0)$ is a pair of initial points, $z^*=(x^*,y^*)$ is a pair of optimal solutions, and $\rho$ is the Lipschitz constant. We further propose a fully parameter-free cubic regularization (FF-CR) algorithm that does not require any parameters of the problem, including the Lipschitz constant and the upper bound of the distance from the initial point to the optimal solution. We also prove that the iteration complexity of the FF-CR algorithm to obtain an $\epsilon$-optimal solution with respect to the gradient norm is upper bounded by $\mathcal{O}(\rho^{2/3}\|z_0-z^*\|^{4/3}\epsilon^{-2/3}) $. Numerical experiments show the efficiency of both algorithms. {\color{blue}To the best of our knowledge, the proposed FF-CR algorithm is a completely parameter-free second-order algorithm, and its iteration complexity is currently the best in terms of $\epsilon$ under the termination criterion of the gradient norm.

报告人简介：徐姿，上海大学理学院教授、博士生导师。主要研究方向是最优化理论与方法及在机器学习等领域中的应用，成果在Mathematical Programming，SIAM Journal on Optimization、Journal of Machine Learning Research、IEEE JSAC等国际著名期刊上发表论文 40余篇。主持国家自然科学基金项目4项和上海市自然基金项目1项。担任中国运筹学会数学规划分会常务理事、上海市运筹学会理事。现任Springer 旗下优化期刊J. Global Optim.客座编委（Guest Editor）；担任国际期刊 JORSC、PLOS One和Numerical Algebra, Control & Optimization编委。曾应邀赴美国明尼苏达大学、香港中文大学、香港理工大学等机构学术访问和交流。2020年获得中国运筹学会科学技术奖青年科技奖。2024年入选上海市东方英才计划拔尖项目。