We study a new aggregation operator for gradients coming from a mini-batch for stochastic gradient (SG) methods that allows a significant speed-up in the case of sparse optimization problems. We call this method AdaBatch and it only requires a few lines of code change compared to regular mini-batch SGD algorithms. We provide a theoretical insight to understand how this new class of algorithms is performing and show that it is equivalent to an implicit per-coordinate rescaling of the gradients, similarly to what Adagrad methods can do. In theory and in practice, this new aggregation allows to keep the same sample efficiency of SG methods while increasing the batch size. Experimentally, we also show that in the case of smooth convex optimization, our procedure can even obtain a better loss when increasing the batch size for a fixed number of samples. We then apply this new algorithm to obtain a parallelizable stochastic gradient method that is synchronous but allows speed-up on par with Hogwild! methods as convergence does not deteriorate with the increase of the batch size. The same approach can be used to make mini-batch provably efficient for variance-reduced SG methods such as SVRG.

本文研究一种用于 mini-batch 的梯度聚合算子，名为 AdaBatch。该算子可用于随机梯度方法，并在稀疏优化问题中大大加速训练过程，同时在保持样本效率的前提下增加批处理大小。实验显示，在光滑凸优化中，该方法甚至可以在固定样本数量的情况下，通过增加批处理大小获得更低的损失。

AdaBatch：基于有效渐进聚合规则的序列和并行随机梯度方法