检索结果-内蒙古大学图书馆

An alternating gradient projection algorithm with Momentum for Nonconvex-Concave Minimax Problems

JOURNAL OF THE OPERATIONS RESEARCH SOCIETY OF CHINA 2024年 1-21页

作者： Li, Jue-You Xie, Tao Chongqing Normal Univ Sch Math Sci Chongqing 401331 Peoples R China Chongqing Coll Int Business & Econ Big Data & Intelligence Engn Sch Chongqing 401520 Peoples R China

The growing interest in addressing minimax optimization problem has been fueled by recent applications in machine learning. Although extensively studied in the convex-concave regime, where a global solution can be efficiently computed, this paper delves into the minimax problem within the nonconvex-concave setup. We propose an alternating gradient projection algorithm with momentum (M-AGP), belonging to single-loop algorithms that not only are easier to implement but also require only the computation of gradient projection updates. We demonstrate that the proposed algorithm identifies an epsilon\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varepsilon $$\end{document}-stationary point of the nonconvex-strongly concave minimax problem in O(epsilon-2)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(\varepsilon <^>{-2})$$\end{document} iterations, representing the best-known rate in the literature. Finally, we utilize two test problems, namely robust nonlinear regression and an image classification problem, to showcase the efficacy of the proposed algorithm.

关键词： Minimax optimization alternating gradient projection algorithm gradient descent-ascent algorithm Iteration complexity

来源：评论

学校读者我要写书评

暂无评论

A unified single-loop alternating gradient projection algorithm for nonconvex-concave and convex-nonconcave minimax problems

引用

MATHEMATICAL PROGRAMMING 2023年第1-2期201卷 635-706页

作者： Xu, Zi Zhang, Huiling Xu, Yang Lan, Guanghui Shanghai Univ Coll Sci Dept Math Shanghai 200444 Peoples R China Georgia Inst Technol Ind & Syst Engn Atlanta GA 30332 USA

Much recent research effort has been directed to the development of efficient algo-rithms for solving minimax problems with theoretical convergence guarantees due to the relevance of these problems to a few emergent applications. In this paper, we propose a unified single-loop alternating gradient projection (AGP) algorithm for solving smooth nonconvex-(strongly) concave and (strongly) convex-nonconcave minimax problems. AGP employs simple gradient projection steps for updating the primal and dual variables alternatively at each iteration. We show that it can find an epsilon-stationary point of the objective function in O (epsilon(-2)) (resp. O (epsilon(-4))) iterations under nonconvex-strongly concave (resp. nonconvex-concave) setting. Moreover, its gradi-by O (epsilon(-2)) (resp., O (epsilon(-4))) under the strongly convex-nonconcave (resp., convex- ent complexity to obtain an epsilon-stationary point of the objective function is bounded nonconcave) setting. To the best of our knowledge, this is the first time that a simple and unified single-loop algorithm is developed for solving both nonconvex-(strongly) concave and (strongly) convex-nonconcave minimax problems. Moreover, the complexity results for solving the latter (strongly) convex-nonconcave minimax problems have never been obtained before in the literature. Numerical results show the efficiency of the proposed AGP algorithm. Furthermore, we extend the AGP algorithm by presenting a block alternating proximal gradient (BAPG) algorithm for solving more general multi-block nonsmooth nonconvex-(strongly) concave and (strongly) convex-nonconcave minimax problems. We can similarly establish the gradient complexity of the proposed algorithm under these four different settings.

关键词： Minimax optimization problem alternating gradient projection algorithm Iteration complexity Single-loop algorithm Machine learning

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：