提出新算法，让更多设备在有限梯度样本下实现最优分布式优化
Near-Optimal Decentralized Stochastic Convex Optimization over Networks
- 采用延迟加速机制，让各节点边通信边用小批量梯度优化
- 可在不超过√ρ·N³⁄⁴个节点时保持最优1/√N收敛速度
- 适用于大规模分布式学习，尤其适合网络连接受限的场景
研究去中心化随机光滑凸优化问题，即M个工作者在固定消息传递网络上，仅通过与邻居通信和局部随机梯度来最小化平均目标函数。核心问题是：在总梯度采样数为N的预算下，最多可使用多少个工作节点仍保持集中式优化的统计率O(1/√N)？本文提出一种加速去中心化方法，可在最多M≲√ρ·N³⁄⁴个工作节点时保持该速率，优于先前最优的M≲ρ√N。该方法基于一步延迟的随机加速机制，使节点能交错进行小批量计算与加速消息传播，同时控制分歧残差；其理论保证仅对最优值局部异质性呈对数依赖。此外，我们建立了线性空间内去中心化一阶方法的匹配下界，证明该方法在对数因子意义下是紧的。
原文摘要 · Abstract (English)
We study decentralized stochastic smooth convex optimization, where $M$ workers minimize an average objective using local stochastic gradients and neighbor-only communication over a fixed gossip network. A central question in this setting is to determine the largest number of workers that can be used under a total budget of $N$ gradient samples while still preserving the centralized $O(1/\sqrt N)$ statistical rate. We introduce an accelerated decentralized method that preserves this rate for up to $\smash{M\lesssim \sqrtρ\,N^{3/4}}$ workers, where $ρ$ is the spectral gap of the gossip network, improving the best prior maximal scaling of $\smash{M\lesssim ρ\sqrt N}$. The method is based on a one-step-delayed stochastic acceleration scheme that enables workers to interleave minibatching with accelerated gossip while controlling residual disagreement, and its guarantee depends only logarithmically on the optimum-local heterogeneity. We also establish a matching lower bound for linear-span decentralized first-order methods, showing that the method is optimal up to logarithmic factors.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。