DADAO: Decoupled Accelerated Decentralized Asynchronous Optimization

arXiv2208.00779MaRDI QIDQ6406636

Author name not available (Why is that?)

Publication date: 26 July 2022

Abstract: This work introduces DADAO: the first decentralized, accelerated, asynchronous, primal, first-order algorithm to minimize a sum of $L$-smooth and $mu$-strongly convex functions distributed over a given network of size $n$. Our key insight is based on modeling the local gradient updates and gossip communication procedures with separate independent Poisson Point Processes. This allows us to decouple the computation and communication steps, which can be run in parallel, while making the whole approach completely asynchronous, leading to communication acceleration compared to synchronous approaches. Our new method employs primal gradients and does not use a multi-consensus inner loop nor other ad-hoc mechanisms such as Error Feedback, Gradient Tracking, or a Proximal operator. By relating the inverse of the smallest positive eigenvalue of the Laplacian matrix $ch{i}_1$ and the maximal resistance $ch{i}_{2}leqch{i}_1$ of the graph to a sufficient minimal communication rate between the nodes of the network, we show that our algorithm requires $mathcalO(nsqrtfracLmulog(frac1epsilon))$ local gradients and only $mathcalO(nsqrtch{i}_{1}ch{i}_{2}sqrtfracLmulog(frac1epsilon))$ communications to reach a precision $epsilon$, up to logarithmic terms. Thus, we simultaneously obtain an accelerated rate for both computations and communications, leading to an improvement over state-of-the-art works, our simulations further validating the strength of our relatively unconstrained method. We also propose a SDP relaxation to find the optimal gossip rate of each edge minimizing the total number of communications for a given graph, resulting in faster convergence compared to standard approaches relying on uniform communication weights. Our source code is released on a public repository.

Has companion code repository: https://github.com/adelnabli/dadao

This page was built for publication: DADAO: Decoupled Accelerated Decentralized Asynchronous Optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6406636)