Optimal Asynchronous Stochastic Nonconvex Optimization under Heavy-Tailed Noise

Abstract

This paper considers the problem of asynchronous stochastic nonconvex optimization with heavy-tailed gradient noise and arbitrarily heterogeneous computation times across workers. We propose an asynchronous normalized stochastic gradient descent algorithm with momentum. The analysis show that our method achieves the optimal time complexity under the assumption of bounded $p$th-order central moment with $p\in (1,2]$. We also provide numerical experiments to show the effectiveness of proposed method.