Near-Optimal Decentralized Stochastic Nonconvex Optimization with Heavy-Tailed Noise
This addresses optimization in distributed networks with realistic heavy-tailed noise, providing efficient algorithms for applications like machine learning, but it is incremental as it builds on existing decentralized methods.
The paper tackles decentralized stochastic nonconvex optimization with heavy-tailed noise by proposing a decentralized normalized stochastic gradient descent method with Pull-Diag gradient tracking, achieving optimal sample complexity and near-optimal communication complexity for approximate stationary points.
This paper studies decentralized stochastic nonconvex optimization problem over row-stochastic networks. We consider the heavy-tailed gradient noise which is empirically observed in many popular real-world applications. Specifically, we propose a decentralized normalized stochastic gradient descent with Pull-Diag gradient tracking, which achieves approximate stationary points with the optimal sample complexity and the near-optimal communication complexity. We further follow our framework to study the setting of undirected networks, also achieving the nearly tight upper complexity bounds. Moreover, we conduct empirical studies to show the practical superiority of the proposed methods.