Diffusion Stochastic Optimization for Min-Max Problems
Not on the map. Why?
Abstract (arXiv)
The optimistic gradient method is useful in addressing minimax optimization problems. Motivated by the observation that the conventional stochastic version suffers from the need for a large batch size on the order of O(varepsilon-2) to achieve an varepsilon-stationary solution, we introduce and analyze a new formulation termed Diffusion Stochastic Same-Sample Optimistic Gradient (DSS-OG). We prove its convergence and resolve the large batch issue by establishing a tighter upper bound, under the more general setting of nonconvex Polyak-Lojasiewicz (PL) risk functions. We also extend the applicability of the proposed method to the distributed scenario, where agents communicate with their neighbors via a left-stochastic protocol. To implement DSS-OG, we can query the stochastic gradient oracles in parallel with some extra memory overhead, resulting in a complexity comparable to its conventional counterpart. To demonstrate the efficacy of the proposed algorithm, we conduct tests by training generative adversarial networks.
Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 45 of its 62 references that are in the map. First posted on arXiv 26 Jan 2024.
Builds on
45 of 62 references.
References · 45
- 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,326
- 2015Unsupervised Representation Learning with Deep Convolutional Generative Adversarial Networkscited by 2,048
- 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 526
- 2020A Unified Theory of Decentralized SGD with Changing Topology and Local Updatescited by 361
- 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 303
- 2019Momentum-Based Variance Reduction in Non-Convex SGDcited by 302
- 2019On Gradient Descent Ascent for Nonconvex-Concave Minimax Problemscited by 266
- 2017Training GANs with Optimismcited by 217
- 2019Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methodscited by 148
- 2020Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimizationcited by 94
- 2019On the convergence of single-call stochastic extra-gradient methodscited by 88
- 2020The Complexity of Constrained Min-Max Optimizationcited by 81
33 more
- 2020Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problemscited by 75
- 2021Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with O(1/k2) Rate on Squared Gradient Normcited by 71
- 2019Reducing Noise in GAN Training with Variance Reduced Extragradientcited by 61
- 2018Negative Momentum for Improved Game Dynamicscited by 59
- 2020Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problemscited by 59
- 2019Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applicationscited by 55
- 2017Exact Diffusion for Distributed Optimization and Learning --- Part I: Algorithm Developmentcited by 50
- 2021Faster Single-loop Algorithms for Minimax Optimization without Strong Concavitycited by 47
- 2019A Decentralized Parallel Algorithm for Training Generative Adversarial Netscited by 43
- 2021A Unified and Refined Convergence Analysis for Non-Convex Decentralized Learningcited by 43
- 2020Non-convex Min-Max Optimization: Applications, Challenges, and Recent Theoretical Advancescited by 37
- 2018A Forward-Backward Splitting Method for Monotone Inclusions Without Cocoercivitycited by 35
- 2019Revisiting Stochastic Extragradientcited by 35
- 2022Last-Iterate Convergence of Optimistic Gradient Method for Monotone Variational Inequalitiescited by 33
- 2021Near-optimal Local Convergence of Alternating Gradient Descent-Ascent for Minimax Optimizationcited by 31
- 2019On Lower Iteration Complexity Bounds for the Saddle Point Problemscited by 28
- 2022Solving Nonconvex-Nonconcave Min-Max Problems exhibiting Weak Minty Solutionscited by 27
- 2021Decentralized Local Stochastic Extra-Gradient for Variational Inequalitiescited by 25
- 2019Distributed Learning in Non-Convex Environments -- Part I: Agreement at a Linear Ratecited by 22
- 2023Solving stochastic weak Minty variational inequalities without increasing batch sizecited by 21
- 2022The First Optimal Algorithm for Smooth and Strongly-Convex-Strongly-Concave Minimax Optimizationcited by 20
- 2019Decentralized Proximal Gradient Algorithms with Linear Convergence Ratescited by 19
- 2021On the Convergence of Stochastic Extragradient for Bilinear Games using Restarted Iteration Averagingcited by 18
- 2019ODE Analysis of Stochastic Gradient Methods with Optimism and Anchoring for Minimax Problemscited by 16
- 2019Subsampling Generative Adversarial Networks: Density Ratio Estimation in Feature Space with Softplus Losscited by 11
- 2022Decentralized Stochastic Gradient Descent Ascent for Finite-Sum Minimax Problemscited by 11
- 2021Quasi-Newton Methods for Saddle Point Problems and Beyondcited by 10
- 2021On the One-sided Convergence of Adam-type Algorithms in Non-convex Non-concave Min-max Optimizationcited by 9
- 2022Extra-Newton: A First Approach to Noise-Adaptive Accelerated Second-Order Methodscited by 8
- 2022Tight Analysis of Extra-gradient and Optimistic Gradient Methods For Nonconvex Minimax Problemscited by 7
- 2022Fairness-aware Regression Robust to Adversarial Attackscited by 4
- 2023Near-Optimal Decentralized Momentum Method for Nonconvex-PL Minimax Problemscited by 4
- 2019Annealing for Distributed Global Optimizationcited by 3
Built on by
Citing papers per year: 2024: 1; 2025: 1.
2 papers.