Sharper asynchronous optimization method improves deep learning training

Rennala NSGD: Asynchronous Stochastic Optimization Beyond Euclidean Geometry

Machine LearningDistributed, Parallel, and Cluster Computing

Summary

Training large neural networks like language models involves adjusting millions of numbers efficiently, which often requires clever ways to handle the mathematical space they live in. This paper studies how an optimization technique called stochastic gradient descent works when it uses different types of geometry beyond the usual flat (Euclidean) space. The authors provide new mathematical guarantees for such methods, especially when computations happen across multiple computers working at different speeds. They also introduce Rennala NSGD, a new algorithm that speeds up training while ensuring reliable results under these distributed and non-standard geometric settings.

What this means in practice

  • For machine learning engineers: Optimize training of large models on distributed hardware with varying worker speeds using the new semi-asynchronous method and sharper convergence guarantees.
  • For high-performance computing teams: Design distributed optimization systems that incorporate non-Euclidean geometry for improved efficiency and reduced communication overhead in nonconvex problem settings.

A theory result. No direct application yet.

Authors

Igor Sokolov, Alexander Tyurin, Peter Richtárik

Abstract

The empirical success of matrix-aware optimizers, such as Muon (Jordan et al., 2024) and Shampoo (arXiv:1802.09568), highlights the potential of non-Euclidean geometry for deep learning, including large language model (LLM) training. Despite this progress, the theoretical understanding of stochastic optimization in general normed spaces remains limited, particularly in distributed settings. We analyze minibatch stochastic gradient descent (SGD) for smooth nonconvex optimization with respect to an arbitrary norm on a finite-dimensional space. Using the framework of $κ$-regular normed spaces (arXiv:0809.0813), we derive high-probability oracle complexity bounds under a light-tail condition stated directly in the dual norm induced by the update norm. The bounds make the dependence on geometry explicit through the regularity constant $κ$ of the dual space. In the Euclidean case, our bound recovers the standard minibatch SGD rate up to logarithmic factors. For some non-Euclidean geometries and noise models, it is sharper than bounds obtained by converting a Euclidean noise assumption, reducing a linear dimension dependence to a logarithmic one. Building on this framework, we introduce Rennala NSGD, a semi-asynchronous distributed algorithm, and establish wall-clock time complexity guarantees under fixed, heterogeneous worker computation times. In the Euclidean case ($κ=1$), our bound matches the parameter dependence of classical Rennala SGD up to logarithmic factors.