arXiv：cs.LG· Anna van Elst, Olivier Fercoq, Igor Colin, Stephan Cl\'emen\c{c}on·· 7 小时前AI 评分35
Goal-PD：面向鲁棒非光滑凸去中心化学习的快速异步 Gossip 算法
Fast and Efficient Asynchronous Gossip Algorithm for Robust and Non-Smooth Convex Decentralized Learning
AI 导读
研究者提出异步 gossip 原始-对偶算法 Goal-PD，每个节点无论度数高低都只维护两个变量，显著降低去中心化学习的显存占用。该算法被证明几乎必然收敛到最优解，并在目标函数为分段线性二次时具有线性收敛速度。在多种网络拓扑下的合成与真实数据集（含中位数估计等非光滑目标）实验中，Goal-PD 收敛快于现有异步基线且内存需求更低。
正文
Abstract:Asynchronous primal-dual methods for decentralized non-smooth convex optimization often require each node to maintain $\mathcal{O}(d)$ auxiliary variables, where $d$ is its degree. This dependence on degree increases memory requirements and can amplify the effects of stale information, especially in dense networks. Motivated by the challenge of frugal memory management in decentralized learning, we introduce Goal-PD, an asynchronous gossip-based primal-dual algorithm that maintains only two variables per node, regardless of the node's degree. We establish almost-sure convergence of Goal-PD to a minimizer of the underlying optimization problem, and prove linear convergence when the objective functions are piecewise linear-quadratic. For decentralized mean estimation, we show that pairwise averaging is a special case of Goal-PD, which establishes a direct link between the proposed primal-dual framework and classical gossip. Experiments on synthetic and real datasets over various network topologies, with non-smooth objectives including median estimation, show that Goal-PD converges faster than existing asynchronous baselines while requiring significantly less memory by design.
| Subjects: | Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Machine Learning (stat.ML) |
| Cite as: | arXiv:2601.20571 [cs.LG] |
| (or arXiv:2601.20571v3 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2601.20571 arXiv-issued DOI via DataCite |
Submission history
From: Anna Van Elst [view email]
[v1]
Wed, 28 Jan 2026 13:09:10 UTC (1,735 KB)
[v2]
Thu, 7 May 2026 15:40:35 UTC (1,895 KB)
[v3]
Tue, 6 Oct 2026 12:17:10 UTC (1,648 KB)
来源：arXiv：cs.LG · arxiv.org