Stochastic Gradient Descent Ascent

Stochastic Gradient Descent Ascent (SGDA) is a family of algorithms designed to solve minimax optimization problems, which arise frequently in machine learning applications like Generative Adversarial Networks (GANs) and reinforcement learning. Current research focuses on improving the convergence rates and stability of SGDA, particularly addressing oscillatory behavior and the challenges posed by non-convex and non-concave objective functions. This involves developing novel algorithms like dissipative SGDA and variance-reduced methods, as well as analyzing the impact of alternating updates and adaptive step sizes. These advancements are crucial for enhancing the efficiency and reliability of training complex machine learning models.

Papers

April 18, 2024

A Mean-Field Analysis of Neural Stochastic Gradient Descent-Ascent for Functional Minimax Optimization
Yuchen Zhu, Yufeng Zhang, Zhaoran Wang, Zhuoran Yang, Xiaohong Chen
Stochastic Gradient Mean Field Wasserstein Gradient Flow Minimax Optimization Problem Stochastic Gradient Descent Ascent Functional Constrained Optimization Riesz Representer

March 14, 2024

Dissipative Gradient Descent Ascent Method: A Control Theory Inspired Algorithm for Min-max Optimization
Tianqi Zheng, Nicolas Loizou, Pengcheng You, Enrique Mallada
Practical Algorithm Saddle Point Min Max Gradient Descent Ascent Control Theory Stochastic Gradient Descent Ascent Optimistic Gradient

February 16, 2024

Fundamental Benefit of Alternating Updates in Minimax Optimization
Jaewook Lee, Hanseul Cho, Chulhee Yun
Complementary Benefit Minimax Optimization Gradient Descent Ascent Information System Update Stochastic Gradient Descent Ascent Lipschitz Gradient Efficient Gradient Extra Gradient Method

June 28, 2023

Stochastic Methods in Variational Inequalities: Ergodicity, Bias and Refinements
Emmanouil-Vasileios Vlatakis-Gkaragkounis, Angeliki Giannou, Yudong Chen, Qiaomin Xie
Absolute Stance Bias Variational Inequality Min Max Stochastic Gradient Descent Ascent Stochastic Approach Geometric Ergodicity Stochastic Extragradient

April 13, 2023

Sample Average Approximation for Black-Box VI
Javier Burroni, Justin Domke, Daniel Sheldon
Black Box Stochastic Optimization Problem Hyperparameter Selection Quasi Newton Method Stochastic Gradient Descent Ascent Deterministic Optimization

December 6, 2022

Decentralized Stochastic Gradient Descent Ascent for Finite-Sum Minimax Problems
Hongchang Gao
Minimax Optimization Problem Stochastic Gradient Descent Ascent Decentralized Stochastic Gradient Descent Variance Reduced Strongly Concave Minimax

December 3, 2022

Constrained Reinforcement Learning via Dissipative Saddle Flow Dynamics
Tianqi Zheng, Pengcheng You, Enrique Mallada
Primal Dual Constrained Reinforcement Learning Gradient Descent Ascent Stochastic Gradient Descent Ascent Saddle to Saddle Dynamic

October 31, 2022

TiAda: A Time-scale Adaptive Algorithm for Nonconvex Minimax Optimization
Xiang Li, Junchi Yang, Niao He
Faster Convergence Time Scale Adaptive Gradient Method Gradient Descent Ascent Stochastic Gradient Descent Ascent Nonconvex Minimax Optimization

October 2, 2022

SAGDA: Achieving $\mathcal{O}(\epsilon^{-2})$ Communication Complexity in Federated Min-Max Learning
Haibo Yang, Zhuqing Liu, Xin Zhang, Jia Liu
Communication Complexity Gradient Descent Ascent Stochastic Gradient Descent Ascent Federated Minimax Optimization

July 3, 2022

On Convergence of Gradient Descent Ascent: A Tight Local Analysis
Haochuan Li, Farzan Farnia, Subhro Das, Ali Jadbabaie
Generative Adversarial Network Early Stage Convergence Convergence Rate Gradient Descent Ascent GAN Algorithm Stochastic Gradient Descent Ascent Tight Analysis

March 9, 2022

Federated Minimax Optimization: Improved Convergence Analyses and Algorithms
Pranay Sharma, Rohan Panda, Gauri Joshi, Pramod K. Varshney
Practical Algorithm Minimax Optimization Minimax Problem Stochastic Gradient Descent Ascent Federated Minimax Optimization Nonconvex Minimax Optimization

February 28, 2022

Provably Efficient Convergence of Primal-Dual Actor-Critic with Nonlinear Function Approximation
Jing Dong, Li Shen, Yinggan Xu, Baoxiang Wang
Reinforcement Learning Primal Dual Actor Critic Algorithm Nonlinear Function Approximation Stochastic Gradient Descent Ascent Primal Dual Reinforcement Learning

February 19, 2022

A Variance-Reduced Stochastic Accelerated Primal Dual Algorithm
Bugra Can, Mert Gurbuzbalaban, Necdet Serhat Aybat
Empirical Risk Minimization Primal Dual Algorithm Stochastic Gradient Descent Ascent Unbiased Prediction Variance Reduced Stochastic

February 15, 2022

Stochastic Gradient Descent-Ascent: Unified Theory and New Efficient Methods
Aleksandr Beznosikov, Eduard Gorbunov, Hugo Berard, Nicolas Loizou
Convergence Analysis Unified Model Variational Inequality Efficient Method Stochastic Gradient Descent Ascent

January 22, 2022

Differentially Private SGDA for Minimax Problems
Zhenhuan Yang, Shu Hu, Yunwen Lei, Kush R. Varshney, Siwei Lyu, Yiming Ying
Gradient Descent Private Stochastic Gradient Descent Risk Minimization Minimax Optimization Problem Strongly Convex Stochastic Gradient Descent Ascent

November 25, 2021

Randomized Stochastic Gradient Descent Ascent
Othmane Sebbouh, Marco Cuturi, Gabriel Peyré
Robust Optimization Stochastic Gradient Descent Ascent SGDA Algorithm