Variance Reduction for Matrix Games

Abstract

We present a randomized primal-dual algorithm that solves the problem ${\min }_x{\max }_y{y}^{\top }Ax$ to additive error $\epsilon$ in time $\mathrm{nnz}(A)+\sqrt{\mathrm{nnz}(A)n}/\epsilon$, for matrix $A$ with larger dimension $n$ and $\mathrm{nnz}(A)$ nonzero entries. This improves the best known exact gradient methods by a factor of $\sqrt{\mathrm{nnz}(A)/n}$ and is faster than fully stochastic gradient methods in the accurate and/or sparse regime $\epsilon \le \sqrt{n/\mathrm{nnz}(A)}$. Our results hold for $x,y$ in the simplex (matrix games, linear programming) and for $x$ in an ${\ell }_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.

Cited by in corpus (11)

• Learning Imbalanced Datasets with Label-Distribution-Aware Margin Loss
• Stochastic Variance Reduction for Variational Inequality Methods
• Improved Algorithms for Convex-Concave Minimax Optimization
• Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results and Construction
• The Complexity of Nonconvex-Strongly-Concave Minimax Optimization
• Projection Efficient Subgradient Method and Optimal Nonsmooth Frank-Wolfe Method
• Extragradient Method: $O(1/K)$ Last-Iterate Convergence for Monotone Variational Inequalities and Connections With Cocoercivity
• DIPPA: An improved Method for Bilinear Saddle Point Problems
• Coordinate Linear Variance Reduction for Generalized Linear Programming
• Variance Reduction via Primal-Dual Accelerated Dual Averaging for Nonsmooth Convex Finite-Sums
• Coordinate Methods for Accelerating ${\ell }_{\infty }$ Regression and Faster Approximate Maximum Flow