Rennala NSGD: Asynchronous Stochastic Optimization Beyond Euclidean Geometry

Igor Sokolov; Alexander Tyurin; Peter Richtárik

cs.LGOct 28, 2026

Rennala NSGD: Asynchronous Stochastic Optimization Beyond Euclidean Geometry

Authors: Igor Sokolov, Alexander Tyurin, Peter Richtárik

Organizations: Center of Excellence for Generative AI, King Abdullah University of Science and Technology (KAUST), Thuwal, Saudi Arabia. · AXXX, Moscow, Russia. · Applied AI Institute, Moscow, Russia.

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.

Figures & tables

Space $(E^{}\mathchar 59\relax\left\\|\cdot\right\\|_{})$	Euclidean/Frobenius a	Geometry-native, Rademacher b	Geometry-native, Gaussian b
$(\mathbb{R}^{d}\mathchar 59\relax\left\\|\cdot\right\\|_{1})$	$\widetilde{{\cal O}}\left(\nicefrac{{d^{2}L\Delta}}{{{\varepsilon}^{2}}}\right)$	$\widetilde{{\cal O}}\left(\nicefrac{{d^{3}L\Delta}}{{{\varepsilon}^{2}}}\right)$	$\widetilde{{\cal O}}\left(\nicefrac{{d^{3}L\Delta}}{{{\varepsilon}^{2}}}\right)$
$(\mathbb{R}^{d}\mathchar 59\relax\left\\|\cdot\right\\|_{2})$	$\widetilde{{\cal O}}\left(\nicefrac{{dL\Delta}}{{{\varepsilon}^{2}}}\right)$	$\widetilde{{\cal O}}\left(\nicefrac{{dL\Delta}}{{{\varepsilon}^{2}}}\right)$	$\widetilde{{\cal O}}\left(\nicefrac{{dL\Delta}}{{{\varepsilon}^{2}}}\right)$
$(\mathbb{R}^{d}\mathchar 59\relax\left\\|\cdot\right\\|_{\infty})$	$\widetilde{{\cal O}}\left(\nicefrac{{dL\Delta}}{{{\varepsilon}^{2}}}\right)$	$\widetilde{{\cal O}}\left(\nicefrac{{\ln(ed)L\Delta}}{{{\varepsilon}^{2}}}\right)$	$\widetilde{{\cal O}}\left(\nicefrac{{(\ln(ed))^{2}L\Delta}}{{{\varepsilon}^{2}}}\right)$

Table 1: Statistical oracle-cost terms, omitting the factor

\nu^{2}

and the common leading term

\widetilde{{\cal O}}(L\Delta/{\varepsilon})

. Formulas hold for

d\geq 1

. Within each row, green and red mark smaller and larger asymptotic orders; blue marks agreement. Colours do not imply strict improvement in every finite dimension.

Figure 2

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Symbol	Meaning	Reference / scope
Spaces and norms
$E$ , $E^{*}$	Parameter space and its dual; $1\leq\dim(E)<\infty$ . Gradients belong to $E^{*}$ .	Appendix A
$E^{**}$	Bidual space, canonically identified with $E$ in finite dimensions.	Theorem 5
$x$ , $s$	Generic primal vector $x\in E$ and dual vector $s\in E^{*}$ .	Appendix A
$\left\langle s\mathchar 59\relax x\right\rangle$	Dual pairing: the value of the linear functional $s$ at $x$ .	Appendix A
$\left\\|\cdot\right\\|$	Primal norm, called the update norm.	Section 3.1

Appendix

Table 2: Notation reference. Definitions with a stated local scope do not replace the conventions used elsewhere.

Space $(E^{}\mathchar 59\relax\left\\|\cdot\right\\|_{})$	$\kappa$ scaling b	Auxiliary norm $\\|\cdot\\|_{*\mathchar 59\relax+}$	Upper bound	Lower bound
Any $d$ -dimensional normed space, $d\geq 1$ a	$\Theta(d)$	Inner-product norm whose unit ball is the maximum-volume ellipsoid contained in $\mathbb{B}_{}=\{s\in E^{}:\left\\|s\right\\|_{*}\leq 1\}$ (the John ellipsoid).	Prop. 10	Prop. 11
$(\mathbb{R}^{d}\mathchar 59\relax\\|\cdot\\|_{p})$ , $1\leq p<2$	$\Theta\!\left(d^{\frac{2}{p}-1}\right)$	$d^{\frac{1}{p}-\frac{1}{2}}\\|\cdot\\|_{2}$ (scaled Euclidean norm)	Prop. 12	Prop. 13
$(\mathbb{R}^{d}\mathchar 59\relax\\|\cdot\\|_{p})$ , $2\leq p\leq\infty$	$\Theta\!\bigl(\min\{p\mathchar 59\relax\ln(ed)\}\bigr)$	$\\|\cdot\\|_{\rho_{}}$ , where $\rho_{}=2$ for $1\leq d<8$ , and $\rho_{*}=\min\{p\mathchar 59\relax\hat{\rho}(d)\}$ for $d\geq 8$ . c
$(\mathbb{R}^{m\times n}\mathchar 59\relax\\|\cdot\\|_{S_{p}})$ , $1\leq p<2$ , $r:=\min\{m\mathchar 59\relax n\}$	$\Theta\!\left(r^{\frac{2}{p}-1}\right)$	$r^{\frac{1}{p}-\frac{1}{2}}\\|\cdot\\|_{S_{2}}$	Prop. 14	Prop. 15
$(\mathbb{R}^{m\times n}\mathchar 59\relax\\|\cdot\\|_{S_{p}})$ , $2\leq p\leq\infty$ , $r:=\min\{m\mathchar 59\relax n\}$	$\Theta\!\bigl(\min\{p\mathchar 59\relax\ln(er)\}\bigr)$	$\\|\cdot\\|_{S_{\rho_{}}}$ , where $\rho_{}=\min\{p\mathchar 59\relax 3\}$ for $1\leq r<8$ , and $\rho_{*}=\min\{p\mathchar 59\relax\max\{3\mathchar 59\relax\hat{\rho}(r)\}\}$ for $r\geq 8$ . d

Appendix

Table 3: Examples of

\kappa

-regular spaces for

V=E^{*}

with corresponding regularity parameters

\kappa

and auxiliary norm

\left\|\cdot\right\|_{*\mathord{\mathchar 59\relax}+}

Stochastic Optimization

Stochastic optimization studies how to find good decisions or model parameters when objectives, data, or feedback are random or noisy.

See all 212 papers

Non-Euclidean SGD for Structured Optimization: Unified Analysis and Improved Rates
Nov 14, 2025Dmitry Kovalev, Ekaterina BorodichNonconvex Stochastic Optimization Stochastic Optimization Convergence
Yandex Research
Adaptive Batch Sizes Using Non-Euclidean Gradient Noise Scales for Stochastic Sign and Spectral Descent
Feb 3, 2026Hiroki Naganuma, Shagun Gupta, Youssef Briki +4Stochastic Optimization Sign-Based Optimization
Mila, Montreal, Canada · Université de Montréal, Montreal, Canada · Meta Platforms, Menlo Park, California, USA
Free Heavy-Tailed Lunch for Muon: A Theoretical Justification of Empirical Success
Jun 12, 2026Florian Hübler, Thomas Pethick, Suvrit SraStochastic Optimization Nonconvex Stochastic Optimization
Department of Computer Science, ETH Zurich, Switzerland · Department of Mathematics, Technical University of Munich, Germany · Munich Center for Machine Learning (MCML)

Nov 14, 2025J/K move · Enter open · S save

Non-Euclidean SGD for Structured Optimization: Unified Analysis and Improved Rates

Dmitry Kovalev, Ekaterina Borodich

Yandex Research

Nonconvex Stochastic Optimization Stochastic Optimization Convergence Stochastic Gradient Descent

Open paper AskPDF arXiv

Recently, several instances of non-Euclidean SGD, including SignSGD, Lion, and Muon, have attracted significant interest from the optimization community due to their practical success in training deep neural networks. Consequently, a number of works have attempted to explain this success by developing theoretical convergence analyses. Unfortunately, these results cannot properly justify the superior performance of these methods, as they could not beat the convergence rate of vanilla Euclidean SGD. We resolve this important open problem by developing a new unified convergence analysis under the structured smoothness and gradient noise assumption. In particular, our results indicate that non-Euclidean SGD (i) can exploit the sparsity or low-rank structure of the upper bounds on the Hessian and gradient noise, (ii) can provably benefit from popular algorithmic tools such as extrapolation or momentum variance reduction, and (iii) can match the state-of-the-art convergence rates of adaptive and more complex optimization algorithms such as AdaGrad and Shampoo.

Abstract

Stochastic Optimization

Explore similar work

Non-Euclidean SGD for Structured Optimization: Unified Analysis and Improved Rates

Adaptive Batch Sizes Using Non-Euclidean Gradient Noise Scales for Stochastic Sign and Spectral Descent

Free Heavy-Tailed Lunch for Muon: A Theoretical Justification of Empirical Success