论文标题
DADAO：分散的分散异步优化的加速加速
DADAO: Decoupled Accelerated Decentralized Asynchronous Optimization
论文作者
论文摘要
这项工作介绍了DADAO：第一个分散，加速，异步，原始的，一阶算法，以最大程度地减少$ L $ -S-SMOTH和$μ$ $ $ - $ $ - 额外的凸函数，分布在给定尺寸$ n $的给定网络上。 我们的主要见解是基于对本地梯度更新和八卦通信过程进行建模，并使用单独的独立泊松点过程进行建模。这使我们能够将计算和通信步骤解除，这些步骤可以并行运行，同时使整个方法完全异步。与同步方法相比，这导致通信加速。我们的新方法采用了原始梯度，并且不使用多声音内部循环或其他临时机制，例如错误反馈，梯度跟踪或近端运算符。通过将Laplacian矩阵$χ_1$和图表的最大电阻$χ_2\ leqχ_1$的最小正征值与足够最小的沟通率与网络之间的足够最小的沟通速率联系起来，我们表明我们的algorithm需要我们的algorithm $ \ MATHCAL {o}（n \ sqrt {\ frac {l}μ} \ log（\ frac {1}ε））$ local梯度，只有$ \ MATHCAL {O}（N \ sqrt {χ_1χ_2} \ sqrt {\ frac {l} v {l}μ} \ log（\ frac {1}ε））$ commusications $ commusigations $ commusications以达到精确$ε$，以达到logarithmic enter。因此，我们同时获得了计算和通信的加速率，从而改善了对最先进的作品的改进，我们的模拟进一步验证了我们相对不受约束的方法的强度。
This work introduces DADAO: the first decentralized, accelerated, asynchronous, primal, first-order algorithm to minimize a sum of $L$-smooth and $μ$-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. This leads 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 $χ_1$ and the maximal resistance $χ_2\leq χ_1$ of the graph to a sufficient minimal communication rate between the nodes of the network, we show that our algorithm requires $\mathcal{O}(n\sqrt{\frac{L}μ}\log(\frac{1}ε))$ local gradients and only $\mathcal{O}(n\sqrt{χ_1χ_2}\sqrt{\frac{L}μ}\log(\frac{1}ε))$ communications to reach a precision $ε$, 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.
