Variance Reduction for Matrix Games
Variance Reduction for Matrix Games
复制标题
DOI：
--
复制
发表时间：
2019-07
期刊：
影响因子：
--
通讯作者：
Y. Carmon;Yujia Jin;Aaron Sidford;Kevin Tian
中科院分区：
文献类型：
--
作者：
Y. Carmon;Yujia Jin;Aaron Sidford;Kevin Tian
我们提出了一种随机原对偶算法，对于具有较大维度 $n$ 和 $\mathrm{nnz}(A)$ 非零项的矩阵 $A$，在 $\mathrm{nnz}(A) + \sqrt{\mathrm{nnz}(A)n}/\epsilon$ 时间内解决 $\min_{x} \max_{y} y^\top A x$ 到加性误差 $\epsilon$ 的问题。这将最著名的精确梯度方法提高了 $\sqrt{\mathrm{nnz}(A)/n}$ 倍，并且在精确和/或稀疏状态 $\epsilon \le \sqrt{n/\mathrm{nnz}(A)}$ 中比完全随机梯度方法更快。我们的结果适用于单纯形（矩阵游戏、线性规划）中的 $x,y$ 以及 $\ell_2$ 球中的 $x$ 和单纯形中的 $y$（感知器/SVM，最小包围球）。我们的算法结合了 Nemirovski 的“概念 prox 方法”和基于当前迭代与参考点之间“差异采样”的新颖的减少方差梯度估计器。
We present a randomized primal-dual algorithm that solves the problem $\min_{x} \max_{y} y^\top A x$ 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.