Regularized empirical risk minimization (R-ERM) is an important branch of
machine learning, since it constrains the capacity of the hypothesis space and
guarantees the generalization ability of the learning algorithm. Two classic
proximal optimization algorithms, i.e., proximal stochastic gradient descent
(ProxSGD) and proximal stochastic coordinate descent (ProxSCD) have been widely
used to solve the R-ERM problem. Recently, variance reduction technique was
proposed to improve ProxSGD and ProxSCD, and the corresponding ProxSVRG and
ProxSVRCD have better convergence rate. These proximal algorithms with variance
reduction technique have also achieved great success in applications at small
and moderate scales. However, in order to solve large-scale R-ERM problems and
make more practical impacts, the parallel version of these algorithms are
sorely needed. In this paper, we propose asynchronous ProxSVRG (Async-ProxSVRG)
and asynchronous ProxSVRCD (Async-ProxSVRCD) algorithms, and prove that
Async-ProxSVRG can achieve near linear speedup when the training data is
sparse, while Async-ProxSVRCD can achieve near linear speedup regardless of the
sparse condition, as long as the number of block partitions are appropriately
set. We have conducted experiments on a regularized logistic regression task.
The results verified our theoretical findings and demonstrated the practical
efficiency of the asynchronous stochastic proximal algorithms with variance
reduction.

本文提出异步 ProxSVRG 和异步 ProxSVRCD 算法，证明当训练数据为稀疏矩阵时，异步 ProxSVRG 可以达到近似线性加速，而异步 ProxSVRCD 无论稠密还是稀疏数据，只要区块数目适当，就可以实现近似线性加速。通过实验证实了异步随机近端算法与方差规约技术的实践效率。

具有方差缩减的异步随机近端优化算法

Asynchronous Stochastic Proximal Optimization Algorithms with Variance  Reduction

Many machine learning techniques sacrifice convenient computational
structures to gain estimation robustness and modeling flexibility. However, by
exploring the modeling structures, we find these "sacrifices" do not always
require more computational efforts. To shed light on such a "free-lunch"
phenomenon, we study the square-root-Lasso (SQRT-Lasso) type regression
problem. Specifically, we show that the nonsmooth loss functions of SQRT-Lasso
type regression ease tuning effort and gain adaptivity to inhomogeneous noise,
but is not necessarily more challenging than Lasso in computation. We can
directly apply proximal algorithms (e.g. proximal gradient descent, proximal
Newton, and proximal Quasi-Newton algorithms) without worrying the
nonsmoothness of the loss function. Theoretically, we prove that the proximal
algorithms combined with the pathwise optimization scheme enjoy fast
convergence guarantees with high probability. Numerical results are provided to
support our theory.

本研究针对机器学习中使用的 Square-root-Lasso（SQRT-Lasso）回归问题，发现通过研究建模结构，这种方法可以同时获得效率和准确性，同时提出使用 proximal 算法（如 proximal gradient descent，proximal Newton 和 proximal quasi-Newton）进一步地提高效率。