GRAND: A Gradient-Related Ascent and Descent Algorithmic Framework for Minimax Problems

Xiaochun Niu; Ermin Wei

doi:10.1109/Allerton49937.2022.9929389

GRAND: A Gradient-Related Ascent and Descent Algorithmic Framework for Minimax Problems

Xiaochun Niu, Ermin Wei

Electrical and Computer Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

1 Scopus citations

Abstract

In this work, we study the minimax optimization problems, which model many distributed and centralized optimization problems. Existing works mainly focus on the design and analysis of specific methods, such as gradient-type methods, including gradient descent ascent method (GDA) and its variants such as extra-gradient (EG) and optimistic gradient descent ascent (OGDA) methods, and Newton-type methods. In this work, we propose GRAND as a gradient-related ascent and descent algorithmic framework for finding global minimax points. It allows updates within acute angles to the partial gradient directions. GRAND covers and motivates gradient-type, Newton-type, and other general descent ascent methods as special cases. It also enables flexible methods' designs for distributed consensus optimization problems to utilize heterogeneous agents. To the best of our knowledge, GRAND is the first generalized framework for minimax problems with convergence guarantees.

Original language	English (US)
Title of host publication	2022 58th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2022
Publisher	Institute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)	9798350399981
DOIs	https://doi.org/10.1109/Allerton49937.2022.9929389
State	Published - 2022
Event	58th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2022 - Monticello, United States Duration: Sep 27 2022 → Sep 30 2022

Publication series

Name	2022 58th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2022

Conference

Conference	58th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2022
Country/Territory	United States
City	Monticello
Period	9/27/22 → 9/30/22

Funding

This work was supported in part by the National Science Foundation (NSF) under Grant ECCS-2030251 and CMMI-2024774.

ASJC Scopus subject areas

Artificial Intelligence
Computer Networks and Communications
Computer Science Applications
Computer Vision and Pattern Recognition
Signal Processing
Control and Optimization

Access to Document

10.1109/Allerton49937.2022.9929389

Cite this

Niu, X., & Wei, E. (2022). GRAND: A Gradient-Related Ascent and Descent Algorithmic Framework for Minimax Problems. In 2022 58th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2022 (2022 58th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2022). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/Allerton49937.2022.9929389

Niu, Xiaochun ; Wei, Ermin. / GRAND : A Gradient-Related Ascent and Descent Algorithmic Framework for Minimax Problems. 2022 58th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2022. Institute of Electrical and Electronics Engineers Inc., 2022. (2022 58th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2022).

@inproceedings{0e76ea4d55ed4434b28a979ae22bd459,

title = "GRAND: A Gradient-Related Ascent and Descent Algorithmic Framework for Minimax Problems",

abstract = "In this work, we study the minimax optimization problems, which model many distributed and centralized optimization problems. Existing works mainly focus on the design and analysis of specific methods, such as gradient-type methods, including gradient descent ascent method (GDA) and its variants such as extra-gradient (EG) and optimistic gradient descent ascent (OGDA) methods, and Newton-type methods. In this work, we propose GRAND as a gradient-related ascent and descent algorithmic framework for finding global minimax points. It allows updates within acute angles to the partial gradient directions. GRAND covers and motivates gradient-type, Newton-type, and other general descent ascent methods as special cases. It also enables flexible methods' designs for distributed consensus optimization problems to utilize heterogeneous agents. To the best of our knowledge, GRAND is the first generalized framework for minimax problems with convergence guarantees.",

author = "Xiaochun Niu and Ermin Wei",

note = "Publisher Copyright: {\textcopyright} 2022 IEEE.; 58th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2022 ; Conference date: 27-09-2022 Through 30-09-2022",

year = "2022",

doi = "10.1109/Allerton49937.2022.9929389",

language = "English (US)",

series = "2022 58th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2022",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

booktitle = "2022 58th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2022",

address = "United States",

}

Niu, X & Wei, E 2022, GRAND: A Gradient-Related Ascent and Descent Algorithmic Framework for Minimax Problems. in 2022 58th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2022. 2022 58th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2022, Institute of Electrical and Electronics Engineers Inc., 58th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2022, Monticello, United States, 9/27/22. https://doi.org/10.1109/Allerton49937.2022.9929389

GRAND: A Gradient-Related Ascent and Descent Algorithmic Framework for Minimax Problems. / Niu, Xiaochun; Wei, Ermin.
2022 58th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2022. Institute of Electrical and Electronics Engineers Inc., 2022. (2022 58th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2022).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - GRAND

T2 - 58th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2022

AU - Niu, Xiaochun

AU - Wei, Ermin

PY - 2022

Y1 - 2022

N2 - In this work, we study the minimax optimization problems, which model many distributed and centralized optimization problems. Existing works mainly focus on the design and analysis of specific methods, such as gradient-type methods, including gradient descent ascent method (GDA) and its variants such as extra-gradient (EG) and optimistic gradient descent ascent (OGDA) methods, and Newton-type methods. In this work, we propose GRAND as a gradient-related ascent and descent algorithmic framework for finding global minimax points. It allows updates within acute angles to the partial gradient directions. GRAND covers and motivates gradient-type, Newton-type, and other general descent ascent methods as special cases. It also enables flexible methods' designs for distributed consensus optimization problems to utilize heterogeneous agents. To the best of our knowledge, GRAND is the first generalized framework for minimax problems with convergence guarantees.

AB - In this work, we study the minimax optimization problems, which model many distributed and centralized optimization problems. Existing works mainly focus on the design and analysis of specific methods, such as gradient-type methods, including gradient descent ascent method (GDA) and its variants such as extra-gradient (EG) and optimistic gradient descent ascent (OGDA) methods, and Newton-type methods. In this work, we propose GRAND as a gradient-related ascent and descent algorithmic framework for finding global minimax points. It allows updates within acute angles to the partial gradient directions. GRAND covers and motivates gradient-type, Newton-type, and other general descent ascent methods as special cases. It also enables flexible methods' designs for distributed consensus optimization problems to utilize heterogeneous agents. To the best of our knowledge, GRAND is the first generalized framework for minimax problems with convergence guarantees.

UR - http://www.scopus.com/inward/record.url?scp=85142615333&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85142615333&partnerID=8YFLogxK

U2 - 10.1109/Allerton49937.2022.9929389

DO - 10.1109/Allerton49937.2022.9929389

M3 - Conference contribution

AN - SCOPUS:85142615333

T3 - 2022 58th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2022

BT - 2022 58th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2022

PB - Institute of Electrical and Electronics Engineers Inc.

Y2 - 27 September 2022 through 30 September 2022

ER -

Niu X, Wei E. GRAND: A Gradient-Related Ascent and Descent Algorithmic Framework for Minimax Problems. In 2022 58th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2022. Institute of Electrical and Electronics Engineers Inc. 2022. (2022 58th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2022). doi: 10.1109/Allerton49937.2022.9929389

GRAND: A Gradient-Related Ascent and Descent Algorithmic Framework for Minimax Problems

Abstract

Publication series

Conference

Funding

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this