论文标题
代币算法设计和分析的原则框架
A principled framework for the design and analysis of token algorithms
论文作者
论文摘要
我们考虑了一个分散的优化问题，其中$ n $节点仅使用本地通信来优化全局目标函数。尽管许多分散的算法都集中在\ emph {八卦}通信（成对平均）上，但我们考虑了一个不同的方案，其中包含该模型当前估计的``代币''在网络上执行随机步行，并使用其位置的本地模型更新其网络。实际上，令牌算法通常受益于提高的沟通效率和隐私保证。我们将令牌算法作为概念图上的随机八卦算法构图，这使我们能够证明完整图的方差降低和加速令牌算法的一系列收敛结果。我们还通过调整通信过程来扩展概念图，将这些结果扩展到多个令牌的情况。从代币到经过良好研究的八卦算法的降低导致许多令牌算法的速度很高，我们从经验上说明了它们的性能。
We consider a decentralized optimization problem, in which $n$ nodes collaborate to optimize a global objective function using local communications only. While many decentralized algorithms focus on \emph{gossip} communications (pairwise averaging), we consider a different scheme, in which a ``token'' that contains the current estimate of the model performs a random walk over the network, and updates its model using the local model of the node it is at. Indeed, token algorithms generally benefit from improved communication efficiency and privacy guarantees. We frame the token algorithm as a randomized gossip algorithm on a conceptual graph, which allows us to prove a series of convergence results for variance-reduced and accelerated token algorithms for the complete graph. We also extend these results to the case of multiple tokens by extending the conceptual graph, and to general graphs by tweaking the communication procedure. The reduction from token to well-studied gossip algorithms leads to tight rates for many token algorithms, and we illustrate their performance empirically.
