In \citep{Yangnips13}, the author presented distributed stochastic dual coordinate ascent (DisDCA) algorithms for solving large-scale regularized loss minimization. Extraordinary performances have been observed and reported for the well-motivated updates, as referred to the practical updates, compared to the naive updates. However, no serious analysis has been provided to understand the updates and therefore the convergence rates. In the paper, we bridge the gap by providing a theoretical analysis of the convergence rates of the practical DisDCA algorithm. Our analysis helped by empirical studies has shown that it could yield an exponential speed-up in the convergence by increasing the number of dual updates at each iteration. This result justifies the superior performances of the practical DisDCA as compared to the naive variant. As a byproduct, our analysis also reveals the convergence behavior of the one-communication DisDCA.

本文提出了分布式随机双协调上升算法（DisDCA）以解决大规模正则化损失最小化问题，并通过理论分析和实证研究证明，通过增加每次迭代的双向更新次数，DisDCA算法可以实现指数级收敛加速，从而证明了实际DisDCA算法相对于基本算法具有卓越的性能。

分布式随机对偶协调上升分析