Distributed Stochastic Optimization Under Heavy-Tailed Noises

This paper studies the distributed optimization problem in the presence of heavy-tailed gradient noises. Here, a heavy-tailed noise <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\xi$</tex-math></inline-formula> does not necessarily adhere to the bounded variance assumption, i.e., <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$ {\mathbb {E}}[\Vert \xi \Vert ^{2}]\leq \nu ^{2}$</tex-math></inline-formula> for some positive constant <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\nu$</tex-math></inline-formula>. Instead, it satisfies a more general condition <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$ {\mathbb {E}}[\Vert \xi \Vert ^\delta ]\leq \nu ^\delta$</tex-math></inline-formula> for some <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$1&lt; \delta \leq 2$</tex-math></inline-formula>. The commonly-used bounded variance assumption is a special case of the considered noise assumption. While several distributed optimization algorithms have been proposed for scenarios involving heavy-tailed noise, these algorithms need a centralized server in the network which collects the information of all clients. Different from these algorithms, this paper considers a scenario where there is no centralized server and the agents can only exchange information with neighbors within a communication graph. A distributed method combining gradient clipping and distributed stochastic gradient projection is proposed. It is proven that when the gradient descent step-size and the gradient clipping step-size meet certain conditions, the state of each agent converges to an optimal solution of the distributed optimization problem with probability 1. The simulation results validate the algorithm.