ABSTRACT

We study decentralized optimization over a network of agents, modeled as graphs, with no central server. The goal is to minimize   $f+r$, where  $f$ represents a (strongly) convex function averaging the local agents' losses, and $r$ is a convex, extended-value function.We introduce DCatalyst, a unified black-box framework that integrates Nesterov acceleration into decentralized optimization algorithms. At its core, DCatalyst operates as an inexact, momentum-accelerated proximal method (forming the outer loop) that seamlessly incorporates any selected decentralized algorithm (as the inner loop).DCatalyst achieves optimal communication and computational complexity (up to log-factors) across various decentralized algorithms and problem instances.  Notably, it extends acceleration capabilities to problem classes  previously lacking accelerated solution methods, thereby broadening the effectiveness of decentralized methods.