Acceleration in Distributed Optimization under Similarity
This work addresses communication efficiency in distributed optimization for networks with similar data, offering incremental improvements over existing accelerated methods.
The paper tackles the problem of reducing communication overhead in distributed optimization over networks with similar agent loss functions, achieving an ε-solution in Õ(√(β/μ/(1-ρ)) log(1/ε)) communication steps, which matches lower bounds up to poly-log factors and shows significant savings in numerical experiments, especially for ill-conditioned problems.
We study distributed (strongly convex) optimization problems over a network of agents, with no centralized nodes. The loss functions of the agents are assumed to be \textit{similar}, due to statistical data similarity or otherwise. In order to reduce the number of communications to reach a solution accuracy, we proposed a {\it preconditioned, accelerated} distributed method. An $\varepsilon$-solution is achieved in $\tilde{\mathcal{O}}\big(\sqrt{\frac{β/μ}{1-ρ}}\log1/\varepsilon\big)$ number of communications steps, where $β/μ$ is the relative condition number between the global and local loss functions, and $ρ$ characterizes the connectivity of the network. This rate matches (up to poly-log factors) lower complexity communication bounds of distributed gossip-algorithms applied to the class of problems of interest. Numerical results show significant communication savings with respect to existing accelerated distributed schemes, especially when solving ill-conditioned problems.