Shuffling Gradient-Based Methods for Nonconvex-Concave Minimax Optimization
Not on the map. Why?
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.
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
28 of 44 references.
References · 28
- 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,415
- 2019Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithmscited by 567
- 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
- 2018A Variational Inequality Perspective on Generative Adversarial Networkscited by 144
- 2020Random Reshuffling: Simple Analysis with Vast Improvementscited by 115
- 2020A Survey on Generative Adversarial Networks: Variants, Applications, and Trainingcited by 97
- 2014Stochastic Compositional Gradient Descent: Algorithms for Minimizing Compositions of Expected-Value Functionscited by 95
- 2020Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problemscited by 77
- 2018Random Shuffling Beats SGD after Finite Epochscited by 67
- 2016Stochastic Variance Reduction Methods for Saddle-Point Problemscited by 60
- 2020A Unified Convergence Analysis for Shuffling-Type Gradient Methodscited by 58
- 2020Explore Aggressively, Update Conservatively: Stochastic Extragradient Methods with Variable Stepsize Scalingcited by 49
16 more
- 2021Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivitycited by 43
- 2020Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problemscited by 38
- 2022Stochastic Gradient Descent-Ascent: Unified Theory and New Efficient Methodscited by 37
- 2021Proximal and Federated Random Reshufflingcited by 33
- 2019Adversarial Attack Generation Empowered by Min-Max Optimizationcited by 32
- 2021Stochastic Extragradient: General Analysis and Improved Ratescited by 31
- 2017Convergence Analysis of Distributed Stochastic Gradient Descent with Shufflingcited by 23
- 2019On Biased Stochastic Gradient Estimationcited by 11
- 2022Sampling without Replacement Leads to Faster Rates in Finite-Sum Minimax Optimizationcited by 10
- 2020Online learning with dynamics: A minimax perspectivecited by 8
- 2022SGDA with shuffling: faster convergence for nonconvex-PL minimax optimizationcited by 8
- 2020Stochastic Variance-Reduced Prox-Linear Algorithms for Nonconvex Composite Optimizationcited by 7
- 2021Game Theory in defence applications: a reviewcited by 5
- 2024Stochastic Extragradient with Random Reshuffling: Improved Convergence for Variational Inequalitiescited by 5
- 2020Hybrid Variance-Reduced SGD Algorithms For Nonconvex-Concave Minimax Problemscited by 4
- 2017Variance-Reduced Stochastic Learning under Random Reshufflingcited by 1
Built on by
Not cited yet.