Communication-Efficient Distributed Coordinate-Descent Methods

We propose a distributed block-coordinate method, where coordinates are partitioned across clients and communication is the main bottleneck. Each client performs multiple local updates between communication rounds to approximately solve a local problem, using Gradient Descent or an accelerated version as local solvers for efficiently minimizing the gradient norm of the local problem. We introduce cross-coupling $M$, which measures how far $f$ is from a fully separable function, with $M=0$ when $f$ is fully separable. For nonconvex but coordinate-wise convex functions and for convex functions, we establish communication complexity bounds proportional to $M$. Under a Polyak–Łojasiewicz condition, our method converges linearly. We compare our method with baselines and explain when it is more communication efficient. We also develop an accelerated version; for convex objectives, it achieves a communication complexity bound proportional to $\sqrt{M}$. Alongside communication complexity, we bound local computation for each problem class. We also introduce a line search method that automatically estimates the constant $M$ in an efficient way resulting in strong practical performance. Finally, we show that the proposed accelerated method is optimal (in terms of communication complexity) by establishing a lower bound valid for any first-order oracle distributed coordinate-descent method.