Trading computation for communication: Distributed stochastic dual coordinate ascent

We present and study a distributed optimization algorithm by employing a stochas-tic dual coordinate ascent method. Stochastic dual coordinate ascent methods en-joy strong theoretical guarantees and often have better performances than stochas-tic gradient descent methods in optimizing regularized loss minimization prob-lems. It still lacks of efforts in studying them in a distributed framework. We make a progress along the line by presenting a distributed stochastic dual coor-dinate ascent algorithm in a star network, with an analysis of the tradeoff be-tween computation and communication. We verify our analysis by experiments on real data sets. Moreover, we compare the proposed algorithm with distributed stochastic gradient descent methods and distributed alternating direction methods of multipliers for optimizing SVMs in the same distributed framework, and ob-serve competitive performances.