mlsanityData to 7 Oct 2026

Variance Reduction for Matrix Games

arXiv 1907.02056 ↗First posted 3 Jul 2019math.OC cs.DS cs.LGcited by 37

Not on the map. Why?

Abstract (arXiv)

We present a randomized primal-dual algorithm that solves the problem minx maxy y^top A x to additive error ε in time nnz(A) + √nnz(A)n/ε, for matrix A with larger dimension n and nnz(A) nonzero entries. This improves the best known exact gradient methods by a factor of √nnz(A)/n and is faster than fully stochastic gradient methods in the accurate and/or sparse regime ε ≤ √n/nnz(A). Our results hold for x,y in the simplex (matrix games, linear programming) and for x in an ℓ2 ball and y in the simplex (perceptron / SVM, minimum enclosing ball). Our algorithm combines Nemirovski's "conceptual prox-method" and a novel reduced-variance gradient estimator based on "sampling from the difference" between the current iterate and a reference point.

Key facts. Cited by 37 papers in the map (data through 7 Oct 2026). First posted on arXiv 3 Jul 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 14; 2022: 8; 2023: 6; 2024: 3; 2025: 3; 2026: 3.

37 papers.

Sort:

By area:

  1. 2021Stochastic Variance Reduction for Variational Inequality Methodscited by 46
  2. 2021The Complexity of Nonconvex-Strongly-Concave Minimax Optimizationcited by 44
  3. 2021Extragradient Method: O(1/K) Last-Iterate Convergence for Monotone Variational Inequalities and Connections With Cocoercivitycited by 39
  4. 2022Stochastic Gradient Descent-Ascent: Unified Theory and New Efficient Methodscited by 37
  5. 2022Proximal Point Imitation Learningcited by 25
  6. 2021Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results and Constructioncited by 22
  7. 2021Efficient Algorithms for Federated Saddle Point Optimizationcited by 20
  8. 2021Fast Distributionally Robust Learning with Variance Reduced Min-Max Optimizationcited by 19
  9. 2021Thinking Inside the Ball: Near-Optimal Minimization of the Maximal Losscited by 17
  10. 2022Stochastic Halpern Iteration with Variance Reduction for Stochastic Monotone Inclusionscited by 17
  11. 2023ReSQueing Parallel and Private Stochastic Convex Optimizationcited by 17
  12. 2022Optimal Algorithms for Decentralized Stochastic Variational Inequalitiescited by 14
25 more
  1. 2022Sharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methodscited by 14
  2. 2024Efficient Algorithms for Empirical Group Distributionally Robust Optimization and Beyondcited by 11
  3. 2021Variance Reduction via Primal-Dual Accelerated Dual Averaging for Nonsmooth Convex Finite-Sumscited by 10
  4. 2021Coordinate Linear Variance Reduction for Generalized Linear Programmingcited by 10
  5. 2022Smooth Monotone Stochastic Variational Inequalities and Saddle Point Problems: A Surveycited by 10
  6. 2023Variance Reduced Halpern Iteration for Finite-Sum Monotone Inclusionscited by 10
  7. 2021Efficient Performance Bounds for Primal-Dual Reinforcement Learning from Demonstrationscited by 9
  8. 2021Long-Term Resource Allocation Fairness in Average Markov Decision Process (AMDP) Environmentcited by 6
  9. 2021DIPPA: An improved Method for Bilinear Saddle Point Problemscited by 6
  10. 2022On the Complexity of a Practical Primal-Dual Coordinate Methodcited by 6
  11. 2023Logarithmic-Regret Quantum Learning Algorithms for Zero-Sum Gamescited by 6
  12. 2023Faster Stochastic Algorithms for Minimax Optimization under Polyak--Lojasiewicz Conditionscited by 4
  13. 2024The Oracle Complexity of Simplex-based Matrix Gamescited by 4
  14. 2021Cyclic Coordinate Dual Averaging with Extrapolationcited by 3
  15. 2023A Whole New Ball Game: A Primal Accelerated Method for Matrix Games and Minimizing the Maximum of Smooth Functionscited by 3
  16. 2024Variance-Reduced Fast Krasnoselkii-Mann Methods for Finite-Sum Root-Finding Problemscited by 2
  17. 2026Swap Regret Minimization Through Response-Based Approachabilitycited by 2
  18. 2026Unbiased and Biased Variance-Reduced Forward-Reflected-Backward Splitting Methods for Stochastic Composite Inclusionscited by 2
  19. 2021Nearly Optimal Linear Convergence of Stochastic Primal-Dual Methods for Linear Programmingcited by 1
  20. 2023Multiplicative Updates for Online Convex Optimization over Symmetric Conescited by 1
  21. 2022Explicit Second-Order Min-Max Optimization: Practical Algorithms and Complexity Analysiscited by 0
  22. 2025Apprenticeship learning with prior beliefs using inverse optimizationcited by 0
  23. 2025Solving Convex-Concave Problems with tildeO(ε-4/7) Second-Order Oracle Complexitycited by 0
  24. 2025Shuffling Heuristic in Variational Inequalities: Establishing New Convergence Guaranteescited by 0
  25. 2026Fast, Parallel, Query-Efficient Binary Classificationcited by 0