论文标题
DOCOM：具有接近最佳样品复杂性的压缩分散优化
DoCoM: Compressed Decentralized Optimization with Near-Optimal Sample Complexity
论文作者
论文摘要
本文提出了双重压缩的动量辅助随机梯度跟踪算法$ \ texttt {docom} $，用于通信效率高效的分散优化。该算法具有两种主要成分，以达到近乎最佳的样本复杂性，同时允许进行通信压缩。首先，该算法使用压缩的八卦共识跟踪平均迭代和随机梯度。其次，通过局部梯度估计，将动量步骤纳入以减少自适应方差。我们表明，$ \ texttt {docom} $在所有参与的代理上找到了一个近乎安装的解决方案，满足$ \ mathbb {e} [\ | \ nabla f（θ）\ |^2] = \ Mathcal {o}（1 / t^{2/3}）$中的$ t $迭代中，其中$ f（θ）$是平稳的（可能是非convex）目标函数。请注意，该证明是通过分析设计的新潜在功能来实现的，该功能紧紧地跟踪$ \ texttt {docom} $的单读进度。作为推论，我们的分析还建立了$ \ texttt {docom} $的线性融合到具有Polyak-łojasiewicz条件的目标函数的全局最佳解决方案。数值实验表明，我们的算法在实践中优于几种最先进的算法。
This paper proposes the Doubly Compressed Momentum-assisted stochastic gradient tracking algorithm $\texttt{DoCoM}$ for communication-efficient decentralized optimization. The algorithm features two main ingredients to achieve a near-optimal sample complexity while allowing for communication compression. First, the algorithm tracks both the averaged iterate and stochastic gradient using compressed gossiping consensus. Second, a momentum step is incorporated for adaptive variance reduction with the local gradient estimates. We show that $\texttt{DoCoM}$ finds a near-stationary solution at all participating agents satisfying $\mathbb{E}[ \| \nabla f( θ) \|^2 ] = \mathcal{O}( 1 / T^{2/3} )$ in $T$ iterations, where $f(θ)$ is a smooth (possibly non-convex) objective function. Notice that the proof is achieved via analytically designing a new potential function that tightly tracks the one-iteration progress of $\texttt{DoCoM}$. As a corollary, our analysis also established the linear convergence of $\texttt{DoCoM}$ to a global optimal solution for objective functions with the Polyak-Łojasiewicz condition. Numerical experiments demonstrate that our algorithm outperforms several state-of-the-art algorithms in practice.
