# Shuffling Gradient-Based Methods for Nonconvex-Concave Minimax Optimization

arXiv: https://arxiv.org/abs/2410.22297 · HTML: https://mlsanity.com/paper/2410.22297/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 28 of its 44 references that are in the map.
- First posted on arXiv 29 Oct 2024.

## Builds on (most cited first, 28 of 28)

- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms](https://mlsanity.com/paper/1911.10635/) (2019)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [A Variational Inequality Perspective on Generative Adversarial Networks](https://mlsanity.com/paper/1802.10551/) (2018)
- [Random Reshuffling: Simple Analysis with Vast Improvements](https://mlsanity.com/paper/2006.05988/) (2020)
- [A Survey on Generative Adversarial Networks: Variants, Applications, and Training](https://mlsanity.com/paper/2006.05132/) (2020)
- [Stochastic Compositional Gradient Descent: Algorithms for Minimizing Compositions of Expected-Value Functions](https://mlsanity.com/paper/1411.3803/) (2014)
- [Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problems](https://mlsanity.com/paper/2001.03724/) (2020)
- [Random Shuffling Beats SGD after Finite Epochs](https://mlsanity.com/paper/1806.10077/) (2018)
- [Stochastic Variance Reduction Methods for Saddle-Point Problems](https://mlsanity.com/paper/1605.06398/) (2016)
- [A Unified Convergence Analysis for Shuffling-Type Gradient Methods](https://mlsanity.com/paper/2002.08246/) (2020)
- [Explore Aggressively, Update Conservatively: Stochastic Extragradient Methods with Variable Stepsize Scaling](https://mlsanity.com/paper/2003.10162/) (2020)
- [Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity](https://mlsanity.com/paper/2107.00052/) (2021)
- [Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problems](https://mlsanity.com/paper/2002.09621/) (2020)
- [Stochastic Gradient Descent-Ascent: Unified Theory and New Efficient Methods](https://mlsanity.com/paper/2202.07262/) (2022)
- [Proximal and Federated Random Reshuffling](https://mlsanity.com/paper/2102.06704/) (2021)
- [Adversarial Attack Generation Empowered by Min-Max Optimization](https://mlsanity.com/paper/1906.03563/) (2019)
- [Stochastic Extragradient: General Analysis and Improved Rates](https://mlsanity.com/paper/2111.08611/) (2021)
- [Convergence Analysis of Distributed Stochastic Gradient Descent with Shuffling](https://mlsanity.com/paper/1709.10432/) (2017)
- [On Biased Stochastic Gradient Estimation](https://mlsanity.com/paper/1906.01133/) (2019)
- [Sampling without Replacement Leads to Faster Rates in Finite-Sum Minimax Optimization](https://mlsanity.com/paper/2206.02953/) (2022)
- [Online learning with dynamics: A minimax perspective](https://mlsanity.com/paper/2012.01705/) (2020)
- [SGDA with shuffling: faster convergence for nonconvex-PL minimax optimization](https://mlsanity.com/paper/2210.05995/) (2022)
- [Stochastic Variance-Reduced Prox-Linear Algorithms for Nonconvex Composite Optimization](https://mlsanity.com/paper/2004.04357/) (2020)
- [Game Theory in defence applications: a review](https://mlsanity.com/paper/2111.01876/) (2021)
- [Stochastic Extragradient with Random Reshuffling: Improved Convergence for Variational Inequalities](https://mlsanity.com/paper/2403.07148/) (2024)
- [Hybrid Variance-Reduced SGD Algorithms For Nonconvex-Concave Minimax Problems](https://mlsanity.com/paper/2006.15266/) (2020)
- [Variance-Reduced Stochastic Learning under Random Reshuffling](https://mlsanity.com/paper/1708.01383/) (2017)

## Abstract (arXiv)

This paper aims at developing novel shuffling gradient-based methods for tackling two classes of minimax problems: nonconvex-linear and nonconvex-strongly concave settings. The first algorithm addresses the nonconvex-linear minimax model and achieves the state-of-the-art oracle complexity typically observed in nonconvex optimization. It also employs a new shuffling estimator for the "hyper-gradient", departing from standard shuffling techniques in optimization. The second method consists of two variants: semi-shuffling and full-shuffling schemes. These variants tackle the nonconvex-strongly concave minimax setting. We establish their oracle complexity bounds under standard assumptions, which, to our best knowledge, are the best-known for this specific setting. Numerical examples demonstrate the performance of our algorithms and compare them with two other methods. Our results show that the new methods achieve comparable performance with SGD, supporting the potential of incorporating shuffling strategies into minimax algorithms.