Modern large-scale machine learning, in particular the training of large language models (LLMs), is increasingly carried out by many agents that collaborate through a server (federated learning) or through a peer-to-peer network (decentralized learning). Empirical evidence shows that the stochastic gradients in such tasks are *heavy-tailed*: their noise has only a bounded $p$-th moment with $p\in(1,2]$, and the variance may be infinite. Most existing distributed optimization theory assumes bounded variance and therefore does not apply. Heavy-tailed noise makes standard distributed methods unstable, and it is unclear which algorithmic mechanisms (clipping, normalization) are needed to obtain reliable and communication-efficient training in federated and decentralized systems.
This project develops algorithms and theory for distributed optimization under heavy-tailed noise, for the problem $\min_x \frac1n\sum_{i=1}^n f_i(x)$ with heterogeneous data across $n$ agents. As a first step, we propose two normalized momentum tracking methods: FMT (Federated Momentum Tracking) for the federated setting and NLMT (Normalized Local Momentum Tracking) for the decentralized setting. Through a unified convergence analysis, we show that both methods attain the communication complexity $\mathcal{O}\big(L\Delta_f\sigma^{p/(p-1)} / (nQ\varepsilon^{(3p-2)/(p-1)})\big)$ for finding an $\varepsilon$-stationary point of an $L$-smooth nonconvex function. This is linear speedup in both the number of agents $n$ and the number of local updates $Q$, and it matches a lower bound that we also establish. The project goes beyond this result and studies further questions of distributed optimization under heavy-tailed noise, such as the role of the network topology, data heterogeneity, and the choice between clipping and normalization.
The requested resources are used to evaluate the proposed methods and their theory on the training of modern machine learning models, in particular large language models. The experiments compare FMT and NLMT against previous methods and centralized baselines, and they study the effects of the number of agents, local updates, network topology, and data heterogeneity.