We develop primal-dual coordinate methods for solving bilinear saddle-point
problems of the form $\min_{x \in \mathcal{X}} \max_{y\in\mathcal{Y}} y^\top A
x$ 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 $\ell_1/\ell_2$ norm ratios, we
offer improvements by a factor of $m+n$ in the fully stochastic setting and
$\sqrt{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 $\sqrt{\mathrm{nnz}(A)/(m+n)}$.

本文提出基于 primal-dual coordinate 方法，并应用于解决包含线性规划、分类和回归问题的双线性鞍点问题。通过设计高效的数据结构和低方差梯度估计器，我们获得了近乎恒定的每次迭代复杂度，并且在采样复杂度上实现了改进。同时，我们应用该方法到最小圆覆盖，最大内接圆和线性回归的计算几何问题中，并获得了改善的计算复杂度。