# DIPPA: An improved Method for Bilinear Saddle Point Problems

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

## Key facts

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

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

- [Training GANs with Optimism](https://mlsanity.com/paper/1711.00141/) (2017)
- [Optimization, Learning, and Games with Predictable Sequences](https://mlsanity.com/paper/1311.1869/) (2013)
- [A Variational Inequality Perspective on Generative Adversarial Networks](https://mlsanity.com/paper/1802.10551/) (2018)
- [A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach](https://mlsanity.com/paper/1901.08511/) (2019)
- [Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile](https://mlsanity.com/paper/1807.02629/) (2018)
- [Near-Optimal Algorithms for Minimax Optimization](https://mlsanity.com/paper/2002.02417/) (2020)
- [Stochastic Variance Reduction Methods for Saddle-Point Problems](https://mlsanity.com/paper/1605.06398/) (2016)
- [Stochastic Variance Reduction Methods for Policy Evaluation](https://mlsanity.com/paper/1702.07944/) (2017)
- [Catalyst Acceleration for First-order Convex Optimization: from Theory to Practice](https://mlsanity.com/paper/1712.05654/) (2017)
- [Variance Reduction for Matrix Games](https://mlsanity.com/paper/1907.02056/) (2019)
- [Improved Algorithms for Convex-Concave Minimax Optimization](https://mlsanity.com/paper/2006.06359/) (2020)
- [Stochastic Primal-Dual Coordinate Method for Regularized Empirical Risk Minimization](https://mlsanity.com/paper/1409.3257/) (2014)
- [Accelerated Schemes For A Class of Variational Inequalities](https://mlsanity.com/paper/1403.4164/) (2014)
- [Projected Reflected Gradient Methods for Monotone Variational Inequalities](https://mlsanity.com/paper/1502.04968/) (2015)
- [Optimal Primal-Dual Methods for a Class of Saddle Point Problems](https://mlsanity.com/paper/1309.5548/) (2013)
- [Coordinate Methods for Matrix Games](https://mlsanity.com/paper/2009.08447/) (2020)
- [Stabilizing Adversarial Nets With Prediction Methods](https://mlsanity.com/paper/1705.07364/) (2017)
- [Towards More Efficient Stochastic Decentralized Learning: Faster Convergence and Sparse Communication](https://mlsanity.com/paper/1805.09969/) (2018)
- [Stochastic Primal-Dual Method for Empirical Risk Minimization with O(1) Per-Iteration Complexity](https://mlsanity.com/paper/1811.01182/) (2018)
- [Sparsified Linear Programming for Zero-Sum Equilibrium Finding](https://mlsanity.com/paper/2006.03451/) (2020)
- [Augmented Lagrangian Methods for the Solution of Generalized Nash Equilibrium Problems](https://mlsanity.com/paper/1807.04474/) (2018)

## Built on by (most cited first, 6 of 6)

- [Near Optimal Stochastic Algorithms for Finite-Sum Unbalanced Convex-Concave Minimax Optimization](https://mlsanity.com/paper/2106.01761/) (2021)
- [Accelerated Primal-Dual Gradient Method for Smooth and Convex-Concave Saddle-Point Problems with Bilinear Coupling](https://mlsanity.com/paper/2112.15199/) (2021)
- [Lifted Primal-Dual Method for Bilinearly Coupled Smooth Minimax Optimization](https://mlsanity.com/paper/2201.07427/) (2022)
- [Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization](https://mlsanity.com/paper/2206.08573/) (2022)
- [A Survey of Decision Making in Adversarial Games](https://mlsanity.com/paper/2207.07971/) (2022)
- [Nesterov Meets Optimism: Rate-Optimal Separable Minimax Optimization](https://mlsanity.com/paper/2210.17550/) (2022)

## 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.