1. Abstract
基于variancereduction(VR)的SGD算法，比SGD更好，不论是theoretically and empirically，但是异步版本没有被研究。本文为很多VR算法提供了一个unifying framework，然后在这个框架中提出了一种异步算法，并证明了很快的收敛速度。对于通用的稀疏的机器学习问题，能够达到线性的加速。
2. Introduction
在强凸假设下，VR随机算法比SGD的期望收敛速度更快，VR分析了problem structure，做了一些space-time的trade-off，能够减少因为随机梯度带来的varince。需要将同步的VR算法扩展到异步的并行和分布式环境。
3. Related work:
3.1. Primal VR方法
SAG(Minimizing Finite Sums with the StochasticAverage Gradient)
SAGA(SAGA: A fast incremental gradient methodwith support for non-strongly convex composite objectives)
SVRG(Accelerating stochastic gradient descent using predictive variance reduction)
S2GD(Semi-Stochastic Gradient Descent Methods)
3.2. Dual VR方法
SDCA(Stochastic dual coordinate ascent methods for regularized loss)
Finito(Finito: A faster, permutable incremental gradientmethod for big data problems)
3.3. 分析Dual方法和VR随机方法之间关系
- New Optimization Methods for Machine Learning
3.4. VR的算法结构
VR的算法结构可以trace back to经典的非随机incremental梯度算法(Incremental gradient, subgradient, and proximal methods for convex optimization:A survey)，但是现在被公认的是，随机性帮助取得更快的收敛
3.5. Proximal方法
- A proximal stochastic gradient method with progressive variance reduction
3.6. 加速VR方法
Stochastic Proximal Gradient Descent with Acceleration Techniques
Accelerated mini-batch stochastic dual coordinate ascent)
3.7. 分析finite-sum问题lower-bound
- A lower bound for the optimization of finite sums
3.8. 异步SGD算法
并行variants
- Hogwild!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
分布式variants
Distributed delayed stochastic optimization
Distributed asynchronous incremental subgradient methods
3.9. Coordinate descent方法的并行和分布式variants
Asynchronous stochastic coordinate descent: Parallelism and convergence properties
An asynchronous parallel stochastic coordinate descent algorithm
An asynchronous parallel stochastic coordinate descent algorithm
Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function
3.10. mini-batch
- Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting. 将S2GD扩展到mini-batch上，因此允许并行运行，但是需要更多的同步，只能允许小的batch
4. VR随机算法的通用框架
4.1. 假设条件
- L-Lipschitz条件
- lamda-strongly凸函数（也可扩展到smooth convex函数）
4.2. 已有VR算法
x是参数，alpha是额外的参数，A是alpha的集合
- SVRG每m轮iteration更新一次完整的A
- SAGA每轮iteration更新A中的一个alpha
- SAG也是每轮iteration更新一个alpha
4.3. 空间时间开销分析
- m较大时，SVRG的计算开销小，但是收敛速度慢
- SAG和SAGA更频繁地更新A，因此收敛速度更快，但是存储开销大
4.4. 通用算法
HSAG：结合不同VR算法的调度策略
5. 异步VR算法
类似HogWild!，单机多核环境，稀疏机器学习问题
6. 实验
- l2-LR算法
- 无锁的SVRG对训练步长（学习速度）和线程数的变化鲁棒性更强
7. 总结
- a common platform
- an synchronous algorithm
