We propose a remarkably general variance-reduced method suitable for solving
regularized empirical risk minimization problems with either a large number of
training examples, or a large model dimension, or both. In special cases, our
method reduces to several known and previously thought to be unrelated methods,
such as {\tt SAGA}, {\tt LSVRG}, {\tt JacSketch}, {\tt SEGA} and {\tt ISEGA},
and their arbitrary sampling and proximal generalizations. However, we also
highlight a large number of new specific algorithms with interesting
properties. We provide a single theorem establishing linear convergence of the
method under smoothness and quasi strong convexity assumptions. With this
theorem we recover best-known and sometimes improved rates for known methods
arising in special cases. As a by-product, we provide the first unified method
and theory for stochastic gradient and stochastic coordinate descent type
methods.

提出了一种通用的降方差的方法，适用于解决带有大量训练样例或大型模型维度或两者都有的正则化经验风险最小化问题。该方法可以减少已知的多种方法，同时提供了一种单一的定理，该定理可以证明在平滑和拟强凸性假设下的线性收敛性。此外，该方法还为随机梯度和随机坐标下降等方法提供了首个统一的方法和理论。

一种支配所有的方法：用于数据、参数和多种新方法的方差缩减

One Method to Rule Them All: Variance Reduction for Data, Parameters and  Many New Methods

We propose a new stochastic coordinate descent method for minimizing the sum
of convex functions each of which depends on a small number of coordinates
only. Our method (APPROX) is simultaneously Accelerated, Parallel and PROXimal;
this is the first time such a method is proposed. In the special case when the
number of processors is equal to the number of coordinates, the method
converges at the rate $2\bar{\omega}\bar{L} R^2/(k+1)^2 $, where $k$ is the
iteration counter, $\bar{\omega}$ is an average degree of separability of the
loss function, $\bar{L}$ is the average of Lipschitz constants associated with
the coordinates and individual functions in the sum, and $R$ is the distance of
the initial point from the minimizer. We show that the method can be
implemented without the need to perform full-dimensional vector operations,
which is the major bottleneck of existing accelerated coordinate descent
methods. The fact that the method depends on the average degree of
separability, and not on the maximum degree of separability, can be attributed
to the use of new safe large stepsizes, leading to improved expected separable
overapproximation (ESO). These are of independent interest and can be utilized
in all existing parallel stochastic coordinate descent algorithms based on the
concept of ESO.

本篇论文提出了一种新的随机坐标下降方法，能够并行、加速和提高期望可分超逼近，此方法能够同时最小化依赖于少数坐标的多个凸函数的和，通过使用新的安全且大的步长，使得该方法不需要执行完整的矢量运算。