We present and analyze statistically optimal, communication and memory efficient distributed stochastic optimization algorithms with near-linear speedups (up to $\log$-factors). This improves over prior work which includes methods with near-linear speedups but polynomial communication requirements (accelerated minibatch SGD) and communication efficient methods which do not exhibit any runtime speedups over a naive single-machine approach. We first analyze a distributed SVRG variant as a distributed stochastic optimization method and show that it can achieve near-linear speedups with logarithmic rounds of communication, at the cost of high memory requirements. We then present a novel method, stochastic DANE, which trades off memory for communication and still allows for optimization with communication which scales only logarithmically with the desired accuracy while also being memory efficient. Stochastic DANE is based on a minibatch prox procedure, solving a non-linearized subproblem on a minibatch at each iteration. We provide a novel analysis for this procedure which achieves the statistical optimal rate regardless of minibatch size and smoothness, and thus significantly improving on prior work.

提出一种分布式随机优化的方法，该方法具有统计上的最优性并且可以实现近线性的加速（达到对数级因子）。该方法允许通信-内存权衡，具有对数级通信但线性内存或多项式通信和相应的多项式内存降低。 通过使用小批量相对迭代（小批量被动-侵略性更新），在每次迭代时解决小批量的子问题实现了这种通信-内存权衡。对此类小批量相对逼近程序的新型分析可以实现统计上的最优速率，而不管小批量的大小和平滑度，因此在之前的工作中得到了显着的改进。

小批量Prox分布式随机优化的高效内存和通信