Rennala NSGD: Asynchronous Stochastic Optimization Beyond Euclidean Geometry
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.
Related
- Adaptive Restart under Unknown KL Geometry in Stochastic Weakly-Convex Optimization
- Stochastic Geometry Meets Optimization: Data-Driven Cellular Planning
- Asynchronous Parallel Computation of Lagrangian Bounds for Mixed-Integer Stochastic Programs by Frank-Wolfe Methods within Projective Hedging
- Technical Report: Partially Asynchronous Distributed Optimization on Riemannian Manifolds
- Bridging the Gap Between Homogeneous and Heterogeneous Asynchronous Optimization Is Surprisingly Difficult
BibTeX
@misc{sokolov2026rennala,
title = {{Rennala NSGD: Asynchronous Stochastic Optimization Beyond Euclidean Geometry}},
author = {Igor Sokolov and Alexander Tyurin and Peter Richtárik},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.38773},
eprint = {2610.38773},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.38773},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Rennala NSGD: Asynchronous Stochastic Optimization Beyond Euclidean Geometry
AU - Igor Sokolov
AU - Alexander Tyurin
AU - Peter Richtárik
PY - 2026
DA - 2026/10/28
PB - arXiv
DO - 10.48550/arxiv.2610.38773
UR - https://arxiv.org/abs/2610.38773
AB - 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.
ER -