Distributed Proportional Stochastic Coordinate Descent With Social Sampling

We consider stochastic message passing algorithms that limit the communication required for decentralized and distributed convex optimization and provide convergence guarantees on the objective value. We first propose a centralized method that modifies the coordinate-sampling distribution for stochastic coordinate descent, which we call proportional stochastic coordinate descent. This method treats the gradient of the function as a probability distribution to sample the coordinates, and may be useful in so-called lock-free decentralized optimization schemes. For general distributed optimization in which agents jointly minimize the sum of local objectives, we propose treating the iterates as gradients and propose a stochastic coordinate-wise primal averaging algorithm for optimization.