针对异构方差的分布式优化，提出更优算法并证明其理论最优性。
Decentralized Non-convex Stochastic Optimization with Heterogeneous Variance
- 按节点特性设计采样策略，降低通信开销
- 样本复杂度依赖局部标准差的算术平均，优于传统方法
- 适用于方差差异大的真实分布式场景
去中心化优化在分布式网络中解决大规模机器学习问题至关重要，多个节点通过局部通信协作。实践中，各节点的随机梯度估计器方差常不一致，但其对算法设计与复杂度的影响尚不明确。为此，我们提出 D-NSS 算法，采用节点特异性采样，并建立其样本复杂度依赖于局部标准差的算术平均，优于依赖最坏情况或平方平均的现有方法。进一步在异方差条件下推导出匹配的样本复杂度下界，证明该依赖关系的最优性。此外，在均方光滑假设下引入方差缩减技术，构建 D-NSS-VR，实现更优的样本复杂度，同时保持算术平均依赖。数值实验验证了理论结果并展示了算法有效性。
原文摘要 · Abstract (English)
Decentralized optimization is critical for solving large-scale machine learning problems over distributed networks, where multiple nodes collaborate through local communication. In practice, the variances of stochastic gradient estimators often differ across nodes, yet their impact on algorithm design and complexity remains unclear. To address this issue, we propose D-NSS, a decentralized algorithm with node-specific sampling, and establish its sample complexity depending on the arithmetic mean of local standard deviations, achieving tighter bounds than existing methods that rely on the worst-case or quadratic mean. We further derive a matching sample complexity lower bound under heterogeneous variance, thereby proving the optimality of this dependence. Moreover, we extend the framework with a variance reduction technique and develop D-NSS-VR, which under the mean-squared smoothness assumption attains an improved sample complexity bound while preserving the arithmetic-mean dependence. Finally, numerical experiments validate the theoretical results and demonstrate the effectiveness of the proposed algorithms.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。