Coordinate Methods for Matrix Games

We develop primal-dual coordinate methods for solving bilinear saddle-point problems of the form minx ∈ Xmaxy ∈ Yy T Ax which contain linear programming, classification, and regression as special cases. Our methods push existing fully stochastic sublinear methods and variance-reduced methods towards their limits in terms of per-iteration complexity and sample complexity. We obtain nearly-constant per-iteration complexity by designing efficient data structures leveraging Taylor approximations to the exponential and a binomial heap. We improve sample complexity via low-variance gradient estimators using dynamic sampling distributions that depend on both the iterates and the magnitude of the matrix entries. Our runtime bounds improve upon those of existing primal-dual methods by a factor depending on sparsity measures of the m by n matrix A. For example, when rows and columns have constant l1/l2 norm ratios, we offer improvements by a factor of m+n in the fully stochastic setting and √{m+n} in the variance-reduced setting. We apply our methods to computational geometry problems, i. e. minimum enclosing ball, maximum inscribed ball, and linear regression, and obtain improved complexity bounds. For linear regression with an elementwise nonnegative matrix, our guarantees improve on exact gradient methods by a factor of √{nnz(A)/(m+n)}.

Authors

• Yair Carmon
• Yujia Jin
• Aaron Sidford
• Kevin Tian

Keywords

• Runtime
• Stochastic processes
• Complexity theory
• Gradient methods
• Linear regression
• Data structures
• Sparse matrices
• Matrix Game
• Data Structure
• Sample Distribution
• Linear Programming
• Taylor Series
• Gradient Approximation
• Gradient Method
• Exact Method
• Linear Classifier
• Stochastic Method
• Interior Point Method
• Sublinear
• Computational Geometry
• Geometry Of The Problem
• Sparse Measurements
• Simplex
• Linear System
• Singular Value
• Stochastic Gradient
• Time Iteration
• Variance Reduction
• Stochastic Approximation
• Standard Basis Vector
• Gradient Calculation
• Euclidean Geometry
• Iteration Cost
• Local Norms
• Iteration Count
• Matrix-vector Product
• minimax optimization
• stochastic gradient methods
• matrix games