提出随机局部协作机制，大幅降低分布式优化通信开销。
Decentralized Optimization with Topology-Independent Communication
- 节点随机选一个正则项协作，避免全局同步
- 图引导正则下每轮仅需2条消息，通信量降为常数
- 适合大规模分布式系统，尤其通信成本敏感场景
分布式优化需节点协调，但全同步难以扩展。当n个节点通过m个成对正则项协作时，标准方法每轮需$ ilde{ ext{O}}(m)$次通信。本文提出随机局部协调：每个节点独立均匀采样一个正则项，仅与共享该正则项的节点通信。该方法利用部分可分性——每个正则项$G_j$仅依赖于节点子集$S_j \\subseteq \{1,\ldots,n\}$。对于$|S_j|=2$的图引导正则项，期望通信量降至每轮恰好2条消息。该方法在凸目标下达到$ ilde{ ext{O}}(\ ext{\varepsilon}^{-2})$轮迭代，在强凸条件下，可在$ ext{O}(\text{\varepsilon}^{-1})$轮内收敛至$\text{\varepsilon}$-解，或在$ ext{O}(\log(1/\text{\varepsilon}))$轮内进入邻域。用单个随机选取的正则项$G_j$的近端算子替代总和$\sum_j G_j$的近端算子，不破坏收敛性且消除全局协调需求。实验验证了其在合成与真实数据集上的收敛速率与通信效率。
原文摘要 · Abstract (English)
Distributed optimization requires nodes to coordinate, yet full synchronization scales poorly. When $n$ nodes collaborate through $m$ pairwise regularizers, standard methods demand $\mathcal{O}(m)$ communications per iteration. This paper proposes randomized local coordination: each node independently samples one regularizer uniformly and coordinates only with nodes sharing that term. This exploits partial separability, where each regularizer $G_j$ depends on a subset $S_j \subseteq \{1,\ldots,n\}$ of nodes. For graph-guided regularizers where $|S_j|=2$, expected communication drops to exactly 2 messages per iteration. This method achieves $\tilde{\mathcal{O}}(\varepsilon^{-2})$ iterations for convex objectives and under strong convexity, $\mathcal{O}(\varepsilon^{-1})$ to an $\varepsilon$-solution and $\mathcal{O}(\log(1/\varepsilon))$ to a neighborhood. Replacing the proximal map of the sum $\sum_j G_j$ with the proximal map of a single randomly selected regularizer $G_j$ preserves convergence while eliminating global coordination. Experiments validate both convergence rates and communication efficiency across synthetic and real-world datasets.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。