mlsanityData to 7 Oct 2026

DIPPA: An improved Method for Bilinear Saddle Point Problems

arXiv 2103.08270 ↗First posted 15 Mar 2021cs.LG math.OCcited by 6

Not on the map. Why?

Abstract (arXiv)

This paper studies bilinear saddle point problems min_bfx max_bfy g(bfx) + bfxtop bfA bfy - h(bfy), where the functions g, h are smooth and strongly-convex. When the gradient and proximal oracle related to g and h are accessible, optimal algorithms have already been developed in the literature citechambolle2011first, palaniappan2016stochastic. However, the proximal operator is not always easy to compute, especially in constraint zero-sum matrix games citezhang2020sparsified. This work proposes a new algorithm which only requires the access to the gradients of g, h. Our algorithm achieves a complexity upper bound tildeOleft( frac|bfA|2√μx μy + √[4]kappax kappay (kappax + kappay) right) which has optimal dependency on the coupling condition number frac|bfA|2√μx μy up to logarithmic factors.

Key facts. Cited by 6 papers in the map (data through 7 Oct 2026). Builds on 21 of its 42 references that are in the map. First posted on arXiv 15 Mar 2021.

Builds on

21 of 42 references.

References · 21

  1. 2017Training GANs with Optimismcited by 217
  2. 2013Optimization, Learning, and Games with Predictable Sequencescited by 187
  3. 2018A Variational Inequality Perspective on Generative Adversarial Networkscited by 144
  4. 2019A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approachcited by 142
  5. 2018Optimistic mirror descent in saddle-point problems: Going the extra (gradient) milecited by 132
  6. 2020Near-Optimal Algorithms for Minimax Optimizationcited by 119
  7. 2016Stochastic Variance Reduction Methods for Saddle-Point Problemscited by 57
  8. 2017Stochastic Variance Reduction Methods for Policy Evaluationcited by 56
  9. 2017Catalyst Acceleration for First-order Convex Optimization: from Theory to Practicecited by 39
  10. 2019Variance Reduction for Matrix Gamescited by 37
  11. 2020Improved Algorithms for Convex-Concave Minimax Optimizationcited by 34
  12. 2014Accelerated Schemes For A Class of Variational Inequalitiescited by 30
9 more
  1. 2014Stochastic Primal-Dual Coordinate Method for Regularized Empirical Risk Minimizationcited by 30
  2. 2015Projected Reflected Gradient Methods for Monotone Variational Inequalitiescited by 27
  3. 2013Optimal Primal-Dual Methods for a Class of Saddle Point Problemscited by 19
  4. 2020Coordinate Methods for Matrix Gamescited by 15
  5. 2017Stabilizing Adversarial Nets With Prediction Methodscited by 14
  6. 2018Towards More Efficient Stochastic Decentralized Learning: Faster Convergence and Sparse Communicationcited by 13
  7. 2018Stochastic Primal-Dual Method for Empirical Risk Minimization with O(1) Per-Iteration Complexitycited by 7
  8. 2020Sparsified Linear Programming for Zero-Sum Equilibrium Findingcited by 4
  9. 2018Augmented Lagrangian Methods for the Solution of Generalized Nash Equilibrium Problemscited by 3

Built on by

Cited by year

Citing papers per year: 2021: 2; 2022: 4.

6 papers.

  1. 2021Accelerated Primal-Dual Gradient Method for Smooth and Convex-Concave Saddle-Point Problems with Bilinear Couplingcited by 16
  2. 2021Near Optimal Stochastic Algorithms for Finite-Sum Unbalanced Convex-Concave Minimax Optimizationcited by 15
  3. 2022Lifted Primal-Dual Method for Bilinearly Coupled Smooth Minimax Optimizationcited by 13
  4. 2022Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimizationcited by 4
  5. 2022A Survey of Decision Making in Adversarial Gamescited by 3
  6. 2022Nesterov Meets Optimism: Rate-Optimal Separable Minimax Optimizationcited by 2