betaFeedback

WorksComputer Science

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κ=1), our bound matches the parameter dependence of classical Rennala SGD up to logarithmic factors.

Introduction

Modern optimizers are non-Euclidean in practice. Modern deep-learning training increasingly uses geometry-aware primitives, including matrix preconditioning and orthogonalized updates. Matrix-aware optimizers include Shampoo [32], which uses matrix preconditioning, and Muon [38] and Dion [1], which use orthogonalized matrix updates. Recent studies report improved training efficiency over AdamW for Muon [54] and Dion [1] in Transformer language-model experiments. Their empirical advantages are often interpreted through the connection between these matrix updates and steepest descent with respect to non-Euclidean norms, such as the spectral norm and related Schatten norms [9, 52]. These norms respect the matrix structure of neural-network parameters, including the weight matrices in Transformer attention and feed-forward layers. This geometric perspective motivates a stochastic theory developed directly in general normed spaces.

Theory gap: stochastic non-Euclidean SGD under the “right” noise model. A central modeling question in stochastic non-Euclidean optimization is how to quantify oracle noise. Most existing analyses [50, 30, 53, 71, 91, 80] assume Euclidean (or Frobenius) moment bounds or bounded variance and then transfer results to a target non-Euclidean norm via norm equivalence. Such conversions can introduce dimension-dependent inflation and may obscure the regimes in which a geometry-aware method should provably help. We therefore seek guarantees under a noise model stated in the native norm.

Our lens: dual-norm light tails and κ\kappa-regularity. We measure oracle noise directly in the dual norm ∥⋅∥∗\lVert\cdot\rVert_* induced by the chosen update norm ∥⋅∥\lVert\cdot\rVert (Assumption 3). Using the κ\kappa-regularity framework [40], we obtain high-probability guarantees with the additional geometric dependence captured by the dual-space regularity constant κ\kappa. Every nonzero finite-dimensional normed space admits such a constant, so this approach does not restrict the choice of update norm (Section 3.3). For suitable geometries and noise models, it yields sharper bounds than Euclidean/Frobenius conversions (§ 3.6.1).

Problem setup. Throughout the paper, EE denotes a finite-dimensional space with dim⁡(E)≥1\dim(E) \ge1. We consider the distributed, non-convex stochastic optimization problem expressed as a finite sum over NN workers:

min⁡x∈E{f(x):=1N∑i=1Nfi(x)}(1)\min_{x\in E}\left\{f(x) := \frac{1}{N}\sum_{i=1}^{N} f_i(x)\right\} \tag*{(1)}

where each fif_i is an expectation over a worker-specific data distribution Di\mathcal{D}_i:

fi(x):=Eξi∼Di[fi(x;ξi)].(2)f_i(x) := \mathbb{E}_{\xi_i\sim\mathcal{D}_i}[f_i(x;\xi_i)] . \tag*{(2)}

The space EE may represent, for instance, vectors in Rd\mathbb{R}^d or matrices in Rm×n\mathbb{R}^{m\times n}. For each worker ii, the function fi:E×Si→Rf_i:E\times S_i\to\mathbb{R} is defined over a sample space SiS_i, and ξi\xi_i is a random variable drawn from Di\mathcal{D}_i. The problem is unconstrained: the methods we analyze contain no projection, so nothing confines the iterates to a proper subset of EE, and every assumption below is stated on all of EE.

This formulation is particularly relevant to Federated Learning (FL) [48, 56, 42]. In this context, two primary forms of heterogeneity arise: device heterogeneity, which concerns variations in system capabilities, and statistical heterogeneity, where data distributions Di\mathcal{D}_i differ across workers. To isolate the effects of device heterogeneity, we assume that all workers share the same sample loss f(⋅;⋅)f(\cdot;\cdot) and sampling distribution D\mathcal{D}. Thus, fi(x;ξ)=f(x;ξ)f_i(x;\xi)=f(x;\xi) and Di=D\mathcal{D}_i=\mathcal{D} for every worker ii, so all local objectives coincide with f(x)=Eξ∼D[f(x;ξ)]f(x)=\mathbb{E}_{\xi\sim\mathcal{D}}[f(x;\xi)]. In this case, (1) reduces to

min⁡x∈E{f(x):=Eξ∼D[f(x;ξ)]}.(3)\min_{x\in E}\{f(x) := \mathbb{E}_{\xi\sim\mathcal{D}}[f(x;\xi)]\}. \tag*{(3)}

Our algorithms access ff through a stochastic first-order oracle: given a query point xx, it returns a random vector ∇f(x;ξ)∈E∗\nabla f(x;\xi)\in E^* that estimates ∇f(x)\nabla f(x). In the sample-loss setting above, this response is the gradient of f(x;ξ)f(x;\xi) with respect to xx. More generally, we allow stochastic estimates that need not be gradients of sample losses; the oracle assumptions are stated formally in § 3.2. In the parallel setting, all workers use the same oracle map and sampling distribution D\mathcal{D}.

Throughout the paper, we assume that ff is LL-smooth (Assumption 1) and bounded from below (Assumption 2), and that the oracle responses are unbiased and satisfy a light-tail condition in the induced dual norm ∥⋅∥∗\lVert\cdot\rVert_*. (Assumption 3).

We work in the following parallel computing setup:

  1. A fixed number of NN workers are available to perform computations in parallel.

  2. Worker ii requires a fixed time τi\tau_i seconds to compute one stochastic gradient after receiving a query point. These times remain fixed throughout the run, and we index the workers so that 0<τ1≤τ2≤⋯≤τN0 < \tau_1 \le\tau_2 \le\cdots\le\tau_N.

  3. Communication in both directions between the server and the workers, and server-side processing, including evaluation of the sharp update, are treated as instantaneous, as in the computation model of § 4.

From oracle complexity to wall-clock time: heterogeneous parallelism. On the systems side, asynchronous SGD has been shown to improve wall-clock convergence guarantees over synchronous minibatch [57] that waits for all workers, in settings with heterogeneous worker speeds. This line of work emphasizes time complexity—the wall-clock time needed to reach a prescribed accuracy—as a natural measure of parallel performance. In the Euclidean setting, Tyurin and Richtárik [ [84] establish a lower bound for their zero-respecting algorithm class and a matching upper bound, up to constants, for Rennala SGD under their specified unbiased bounded-variance oracle model with fixed worker computation times. On the optimization side, non-Euclidean methods are motivated by modern matrix-aware updates, yet their interaction with computational heterogeneity remains poorly understood. Bridging these two directions requires (i) tight control of stochastic gradient noise in the induced dual norm ∥⋅∥∗\|\cdot\|_{*} associated with the chosen update norm ∥⋅∥\|\cdot\| and (ii) a wall-clock analysis that accounts for heterogeneous worker speeds under non-Euclidean updates. Together, these two directions motivate the following question:

Should stochastic gradient noise be controlled in a Euclidean or Frobenius norm and then converted, via norm equivalence, to the dual norm ∥⋅∥∗\|\cdot\|_{*} induced by the update norm ∥⋅∥\|\cdot\|? Or can a noise condition stated directly in ∥⋅∥∗\|\cdot\|_{*} yield sharper oracle and wall-clock guarantees?

Notation. The notation used throughout the paper is collected in Section A, which gives the main definitions followed by a consolidated reference table.

Our contributions. We study non-convex stochastic optimization in a normed space (E,∥⋅∥)(E,\|\cdot\|) and focus on the statistically homogeneous but computationally heterogeneous parallel regime. Our goal is to characterize both (i) the number of stochastic gradients needed to reach an ε\varepsilon-stationary point and (ii) the wall-clock time needed when workers have different speeds.

Our contributions are threefold:

(i) Minibatch non-Euclidean SGD under a dual-norm light-tail oracle. We establish high-probability oracle-complexity bounds for minibatch SGD under the stated smoothness, lower-boundedness, and unbiased dual-norm light-tail assumptions. The key ingredient is a minibatch concentration inequality for fresh i.i.d. samples in regular dual spaces (Lemma 1). Combining it with non-Euclidean descent, we show that an ε\varepsilon-stationary point is reached with probability at least 1−δ1-\delta using

O~(LΔε+κLΔσ2ε2)(4)\widetilde{O}\left(\frac{L\Delta}{\varepsilon}+\frac{\kappa L\Delta\sigma^{2}}{\varepsilon^{2}}\right) \tag*{(4)}

stochastic gradient evaluations (Theorem 1 and Corollary 1), where Δ=f(x0)−finf⁡\Delta=f(x^{0})-f^{\inf} is the initial functional gap and κ\kappa is a regularity constant of the dual space (E∗,∥⋅∥∗)(E^{*},\|\cdot\|_{*}). In the Euclidean case, where κ=1\kappa=1, this matches the optimal oracle complexity up to logarithmic factors for general unbiased light-tail oracles, in the regime described in § 3.6.

(ii) Sharp regularity bounds and improvements over norm-equivalence conversions. We establish matching upper and lower bounds on the optimal κ\kappa-regularity parameter for ℓpd\ell_{p}^{d} and Schatten-pp spaces, exact for 1≤p<21\leq p<2 and up to absolute constants for 2≤p≤∞2\leq p\leq\infty (Table 3 and Section L). For some non-Euclidean geometries and noise models, the native-norm analysis yields significantly smaller oracle-complexity bounds than those obtained by converting a Euclidean/Frobenius noise assumption. In particular, for the ℓ1\ell_{1} update norm under dense Rademacher perturbations, the statistical coefficient grows logarithmically rather than linearly with the dimension. We quantify these comparisons for ℓpd\ell_{p}^{d} and Schatten-pp dual geometries in § 3.6.1 and Section J.

Space (E∗,∣⋅∣∗)(E^*,|\cdot|_*)κ\kappa scalingb^bAuxiliary norm ∣⋅∣∗,+|\cdot|_{*,+}Upper boundLower bound
Any dd-dimensional normed space, d≥1ad\ge1^aΘ(d)\Theta(d)Inner-product norm whose unit ball is the maximum-volume ellipsoid contained in B∗={s∈E∗:∣s∣∗≤1}B_*=\{s\in E^*:|s|_*\le1\} (the John ellipsoid).Prop. 10Prop. 11
(Rd,∣⋅∣p)(\mathbb{R}^d,|\cdot|_p), 1≤p<21\le p<2Θ(d2p−1)\Theta\left(d^{\frac{2}{p}-1}\right)d1p−12∣⋅∣2d^{\frac{1}{p}-\frac{1}{2}}|\cdot|_2 (scaled Euclidean norm)Prop. 12Prop. 13
(Rd,∣⋅∣p)(\mathbb{R}^d,|\cdot|_p), 2≤p≤∞2\le p\le\inftyΘ(min⁡{p,ln⁡(ed)})\Theta(\min\{p,\ln(ed)\})∣⋅∣ρ∗|\cdot|_{\rho_*}, where ρ∗=2\rho_*=2 for 1≤d<81\le d<8, and ρ∗=min⁡{p,ρ^(d)}\rho_*=\min\{p,\hat{\rho}(d)\} for d≥8d\ge8
(Rm×n,∣⋅∣Sp)(\mathbb{R}^{m\times n},|\cdot|_{S_p}), 1≤p<21\le p<2, r:=min⁡{m,n}r:=\min\{m,n\}Θ(r2p−1)\Theta\left(r^{\frac{2}{p}-1}\right)r1p−12∣⋅∣S2r^{\frac{1}{p}-\frac{1}{2}}|\cdot|_{S_2}Prop. 14Prop. 15
(Rm×n,∣⋅∣Sp)(\mathbb{R}^{m\times n},|\cdot|_{S_p}), 2≤p≤∞2\le p\le\infty, r:=min⁡{m,n}r:=\min\{m,n\}Θ(min⁡{p,ln⁡(er)})\Theta(\min\{p,\ln(er)\})∣⋅∣Sρ∗|\cdot|_{S_{\rho_*}}, where ρ∗=min⁡{p,3}\rho_*=\min\{p,3\} for 1≤r<81\le r<8, and ρ∗=min⁡{p,max⁡{3,ρ^(r)}}\rho_*=\min\{p,\max\{3,\hat{\rho}(r)\}\} for r≥8r\ge8

Table 3. Examples of κ\kappa-regular spaces for V=E∗V=E^* with corresponding regularity parameters κ\kappa and auxiliary norm ∥⋅∥∗,+\|\cdot\|_{*,+}.

References

  1. [1]Kwangjun Ahn, Byron Xu, Natalie Abreu, and John Langford. Dion: Distributed orthonormalized updates. arXiv preprint arXiv:2504.05295, 2025.arxiv.org/abs/2504.05295
  2. [2]Ahmad Ajalloeian and Sebastian U Stich. On the convergence of SGD with biased gradients. arXiv preprint arXiv:2008.00051, 2020.arxiv.org/abs/2008.00051
  3. [3]Dan Alistarh, Demian Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. QSGD: Communication-efficient SGD via gradient quantization and encoding. Advances in neural information processing systems, 30, 2017.
  4. [4]Dan Alistarh, Torsten Hoefler, Mikael Johansson, Nikola Konstantinov, Sarit Khirirat, and Cédric Renggli. The convergence of sparsified gradient methods. Advances in Neural Information Processing Systems, 31, 2018.
  5. [5]Noah Amsel, David Persson, Christopher Musco, and Robert M Gower. The polar express: Optimal matrix sign methods and their application to the Muon algorithm. arXiv preprint arXiv:2505.16932, 2025.arxiv.org/abs/2505.16932
  6. [6]Kang An, Yuxing Liu, Rui Pan, Yi Ren, Shiqian Ma, Donald Goldfarb, and Tong Zhang. ASGO: Adaptive structured gradient optimization. arXiv preprint arXiv:2503.20762, 2025.arxiv.org/abs/2503.20762
  7. [7]Yossi Arjevani, Ohad Shamir, and Nathan Srebro. A tight convergence analysis for stochastic gradient descent with delayed updates. In Algorithmic Learning Theory, pages 111–132. PMLR, 2020.
  8. [8]Amir Beck. First-order methods in optimization. SIAM, 2017.DOI
  9. [9]Jeremy Bernstein and Laker Newhouse. Old optimizer, new norm: An anthology. arXiv preprint arXiv:2409.20325, 2024.arxiv.org/abs/2409.20325
  10. [10]Jeremy Bernstein, Yu-Xiang Wang, Kamyar Aziz zadene sheli, and Animashree Anandkumar. signSGD: Compressed optimisation for non-convex problems. In International conference on machine learning, pages 560–569. PMLR, 2018.arxiv.org/abs/1802.04434
  11. [11]Aleksandr Beznosikov, Samuel Horváth, Peter Richtárik, and Mher Safaryan. On biased compression for distributed learning. Journal of Machine Learning Research, 24(276):1–50, 2023.
  12. [12]Jianmin Chen, Xinghao Pan, Rajat Monga, Samy Bengio, and Rafal Jozefowicz. Revisiting distributed synchronous SGD. arXiv preprint arXiv:1604.00981, 2016.arxiv.org/abs/1604.00981
  13. [13]Alon Cohen, Amit Daniely, Yoel Drori, Tomer Koren, and Mariano Schain. Asynchronous stochastic optimization robust to arbitrary delays. Advances in Neural Information Processing Systems, 34: 9024–9035, 2021.arxiv.org/abs/2106.11879
  14. [14]Andrew Cotter, Ohad Shamir, Nati Srebro, and Karthik Sridharan. Better mini-batch algorithms via accelerated gradient methods. Advances in neural information processing systems, 24, 2011.arxiv.org/abs/1106.4574
  15. [15]Yury Demidovich, Grigory Malinovsky, Igor Sokolov, and Peter Richtárik. A guide through the zoo of biased SGD. Advances in Neural Information Processing Systems, 36:23158–23171, 2023.arxiv.org/abs/2305.16296
  16. [16]Yury Demidovich, Petr Ostroukhov, Grigory Malinovsky, Samuel Horváth, Martin Takáč, Peter Richtárik, and Eduard Gorbunov. Methods with local steps and random reshuffling for generally smooth non-convex federated optimization, 2024. URL https://arxiv.org/abs/2412.02781.
  17. [17]Olivier Devolder, François Glineur, and Yurii Nesterov. First-order methods of smooth convex optimization with inexact oracle. Mathematica Programming, 146(1):37–75, 2014.
  18. [18]John Duchi, Michael I Jordan, and Brendan McMahan. Estimation, optimization, and parallelism when data is sparse. Advances in Neural Information Processing Systems, 26, 2013.
  19. [19]Lutz Dümbgen, Sara A van de Geer, Marc K Veraar, and Jon A Wellner. Nemirovski’s inequalities revisited. The American Mathematical Monthly, 117(2):138–160, 2010.
  20. [20]Sanghamitra Dutta, Gauri Joshi, Soumyadip Ghosh, Parijat Dube, and Priya Nagpurkar. Slow and stale gradients can win the race: Error-runtime trade-offs in distributed SGD. In International conference on artificial intelligence and statistics, pages 803–812. PMLR, 2018.arxiv.org/abs/1803.01113
  21. [21]Ilyas Fatkhullin, Igor Sokolov, Eduard Gorbunov, Zhize Li, and Peter Richtárik. EF21 with bells & whistles: Practical algorithmic extensions of modern error feedback. arXiv preprint arXiv:2110.03294, 2021.arxiv.org/abs/2110.03294
  22. [22]Hamid Reza Feyzmahdavian, Arda Aytekin, and Mikael Johansson. An asynchronous mini-batch algorithm for regularized stochastic optimization. IEEE Transactions on Automatic Control, 61 (12):3740–3754, 2016.
  23. [23]Alexander Gasnikov. Universal gradient descent. arXiv preprint arXiv:1711.00394, 2017.arxiv.org/abs/1711.00394
  24. [24]Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM journal on optimization, 23(4):2341–2368, 2013.arxiv.org/abs/1309.5549
  25. [25]Eduard Gorbunov, Filip Hanzely, and Peter Richtárik. A unified theory of SGD: Variance reduction, sampling, quantization and coordinate descent. In International Conference on Artificial Intelligence and Statistics, pages 680–690. PMLR, 2020.arxiv.org/abs/1905.11261
  26. [26]Robert Mansel Gower, Nicolas Loiou, Xun Qian, Alibek Sailanbayev, Egor Shulgin, and Peter Richtárik. SGD: General analysis and improved rates. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 5200–5209. PMLR, 09–15 Jun 2019. URL https://proceedings.mlr.press/v97/qian19b.html.arxiv.org/abs/1901.09401
  27. [27]Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large minibatch SGD: Training ImageNet in 1 hour. arXiv preprint arXiv:1706.02677, 2017.arxiv.org/abs/1706.02677
  28. [28]Ekaterina Grishina, Matvey Smirnov, and Maxim Rakhuba. Accelerating Newton-Schulz iteration for orthogonalization via Chebyshev-type polynomials. arXiv preprint arXiv:2506.10935, 2025.arxiv.org/abs/2506.10935
  29. [29]Kaja Gruntkowska, Alexander Tyurin, and Peter Richtárik. EF21-P and friends: Improved theoretical communication complexity for distributed optimization with bidirectional compression. In International Conference on Machine Learning, pages 11761–11807. PMLR, 2023.arxiv.org/abs/2209.15218
  30. [30]Kaja Gruntkowska, Alexander Gaponov, Zhirayr Tovmasyan, and Peter Richtárik. Error feedback for Muon and friends. arXiv preprint arXiv:2510.00643, 2025.arxiv.org/abs/2510.00643
  31. [31]Vincent Guigues, Anatoli Juditsky, and Arkadi Nemirovski. Non-asymptotic confidence bounds for the optimal value of a stochastic program. Optimization Methods and Software, 32(5):1033–1058, 2017.arxiv.org/abs/1601.07592
  32. [32]Vineet Gupta, Tomer Koren, and Yoram Singer. Shampoo: Preconditioned stochastic tensor optimization. In International Conference on Machine Learning, pages 1842–1850. PMLR, 2018.arxiv.org/abs/1802.09568
  33. [33]Samuel Horváth, Chen-Yu Ho, Ludovit Horváth, Atal Narayan Sahu, Marco Canini, and Peter Richtárik. Natural compression for distributed deep learning. In Mathematical and Scientific Machine Learning, pages 129–141. PMLR, 2022.
  34. [34]Edward J. Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, and Weizhu Chen. LoRA: Low-rank adaptation of large language models, 2021. URL https://arxiv.org/abs/2106.09685.
  35. [35]Xinmeng Huang, Yiming Chen, Wotao Yin, and Kun Yuan. Lower bounds and nearly optimal algorithms in distributed learning with communication compression. Advances in Neural Information Processing Systems, 35:18955–18969, 2022.arxiv.org/abs/2206.03665
  36. [36]Jikai Jin. A tight lower bound for smooth nonconvex stochastic optimization with bounded gradient noise. arXiv preprint arXiv:2608.09004, 2026.arxiv.org/abs/2608.09004
  37. [37]Fritz John. Extremum problems with inequalities as subsidiary conditions, studies and essays presented to r. Courant on his 60th birthday, January 8, 1948, 1948.
  38. [38]Keller Jordan, Yuchen Jin, Vlado Boza, Jiacheng You, Franz Cesista, Laker Newhouse, and Jeremy Bernstein. Muon: An optimizer for hidden layers in neural networks, 2024. URL https://kellerjordan.github.io/posts/muon/.
  39. [39]Pooria Joulani, András György, and Csaba Szepesvári. Think out of the "box": Generically-constrained asynchronous composite optimization and hedging. Advances in Neural Information Processing Systems, 32, 2019.
  40. [40]Anatoli Juditsky and Arkadii S Nemirovski. Large deviations of vector-valued martingales in 2-smooth normed spaces. arXiv preprint arXiv:0809.0813, 2008.arxiv.org/abs/0809.0813
  41. [42]Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Federated learning: Strategies for improving communication efficiency. Foundations and trends® in machine learning, 14(1–2):1–210, 2021.
  42. [43]Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian Stich, and Martin Jaggi. Error feedback fixes signSGD and other gradient compression schemes. In International Conference on Machine Learning, pages 3252–3261. PMLR, 2019.arxiv.org/abs/1901.09847
  43. [44]Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. SCAFFOLD: Stochastic controlled averaging for federated learning. In International conference on machine learning, pages 5132–5143. PMLR, 2020.arxiv.org/abs/1910.06378
  44. [45]Gyu Yeol Kim and Min-hwan Oh. Convergence of Muon with Newton-Schulz. arXiv preprint arXiv:2601.19156, 2026.arxiv.org/abs/2601.19156
  45. [46]Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian Stich. A unified theory of decentralized SGD with changing topology and local updates. In International Conference on Machine Learning, pages 5381–5393. PMLR, 2020.arxiv.org/abs/2003.10422
  46. [47]Anastasiia Koloskova, Sebastian U Stich, and Martin Jaggi. Sharper convergence guarantees for asynchronous SGD for distributed and federated learning. Advances in Neural Information Processing Systems, 35:17202–17215, 2022.
  47. [48]Jakub Konečný, H. B. McMahan, Felix X. Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. ArXiv, abs/1610.05492, 2016.arxiv.org/abs/1610.05492
  48. [50]Dmitry Kovalev and Ekaterina Borodich. Non-Euclidean SGD for structured optimization: Unified analysis and improved rates. arXiv preprint arXiv:2511.11466, 2025.arxiv.org/abs/2511.11466
  49. [52]Tim Tsz-Kit Lau, Qi Long, and Weijie Su. PolarGrad: A class of matrix-gradient optimizers from a unifying preconditioning perspective. arXiv preprint arXiv:2505.21799, 2025.arxiv.org/abs/2505.21799
  50. [53]Jiaxiang Li and Mingyi Hong. A note on the convergence of Muon. arXiv preprint arXiv:2502.02900, 2025.arxiv.org/abs/2502.02900
  51. [54]Jingyuan Liu, Jianlin Su, Xingcheng Yao, Zhejun Jiang, Guokun Lai, Yulun Du, Yidao Qin, Weixin Xu, Enzhe Lu, Junjie Yan, et al. Muon is scalable for LLM training. arXiv preprint arXiv:2502.16982, 2025.arxiv.org/abs/2502.16982
  52. [55]Grigory Malinovsky, Kai Yi, and Peter Richtárik. Variance reduced ProxSkip: Algorithm, theory and application to federated learning. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022. URL https://openreview.net/forum?id=edkno3SvKo.arxiv.org/abs/2207.04338
  53. [56]Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-efficient learning of deep networks from decentralized data. In Artificial intelligence and statistics, pages 1273–1282. PMLR, 2017.arxiv.org/abs/1602.05629
  54. [57]Konstantin Mishchenko, Francis Bach, Mathieu Even, and Blake E Woodworth. Asynchronous SGD beats minibatch SGD under arbitrary delays. Advances in Neural Information Processing Systems, 35:420–433, 2022.
  55. [58]Shuntaro Nagashima and Hideaki Iiduka. Improved convergence rates of Muon optimizer for nonconvex optimization. arXiv preprint arXiv:2601.19400, 2026.arxiv.org/abs/2601.19400
  56. [59]Lam Nguyen, Phuong Ha Nguyen, Marten van Dijk, Peter Richtárik, Katya Scheinberg, and Martin Takáč. SGD and Hogwild! convergence without the bounded gradients assumption. In International Conference on Machine Learning, pages 3750–3758. PMLR, 2018.arxiv.org/abs/1802.03801
  57. [60]Julie Nutini, Mark Schmidt, Issam Laradji, Michael Friedlander, and Hoyt Koepke. Coordinate descent converges faster with the Gauss–Southwell rule than random selection. In International Conference on Machine Learning, pages 1632–1641. PMLR, 2015.arxiv.org/abs/1506.00552
  58. [61]Benjamin Recht, Christopher Re, Stephen Wright, and Feng Niu. Hogwild: A lock-free approach to parallelizing stochastic gradient descent. In Advances in Neural Information Processing Systems, 2011.
  59. [62]Yehonathan Refael, Guy Smorodinsky, Tom Tírer, and Ofir Lindenbaum. SUMO: Subspace-aware moment-orthogonalization for accelerating memory-efficient LLM training. arXiv preprint arXiv:2505.24749, 2025.arxiv.org/abs/2505.24749
  60. [63]Peter Richtárik, Igor Sokolov, and Ilyas Fatkhullin. EF21: A new, simpler, theoretically better, and practically faster error feedback. Advances in Neural Information Processing Systems, 34: 4384–4396, 2021.arxiv.org/abs/2106.05203
  61. [64]Peter Richtárik, Igor Sokolov, Elnur Gasanov, Ilyas Fatkhullin, Zhize Li, and Eduard Gorbunov. 3PC: Three point compressors for communication-efficient distributed training and a better theory for lazy aggregation. In International Conference on Machine Learning, pages 18596–18648. PMLR, 2022.arxiv.org/abs/2202.00998
  62. [65]Abdurakhmon Sadiev, Grigory Malinovsky, Eduard Gorbunov, Igor Sokolov, Ahmed Khaled, Konstantin Burlachenko, and Peter Richtárik. Federated optimization algorithms with random reshuffling and gradient compression. arXiv preprint arXiv:2206.07021, 2022.arxiv.org/abs/2206.07021
  63. [66]Abdurakhmon Sadiev, Grigory Malinovsky, Eduard Gorbunov, Igor Sokolov, Ahmed Khaled, Konstantin Pavlovich Burlachenko, and Peter Richtárik. Don’t compress gradients in random reshuffling: Compress gradient differences. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. URL https://openreview.net/forum?id=CzPtBzgfae.DOI
  64. [67]Abdurakhmon Sadiev, Yury Demidovich, Igor Sokolov, Grigory Malinovsky, Sarit Khirirat, and Peter Richtárik. Improved convergence in parameter-agnostic error feedback through momentum. arXiv preprint arXiv:2511.14501, 2025.arxiv.org/abs/2511.14501
  65. [68]Abdurakhmon Sadiev, Artavazd Maranjyan, Ivan Ilin, and Peter Richtárik. Ringmaster LMO: Asynchronous linear minimization oracle momentum method. arXiv preprint arXiv:2605.18174, 2026.arxiv.org/abs/2605.18174
  66. [69]Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu. 1-bit stochastic gradient descent and its application to data-parallel distributed training of speech DNNs. In Fifteenth Annual Conference of the International Speech Communication Association, 2014.DOI
  67. [70]Ishaan Shah, Anthony M Pollarono, Karl Stratos, Philip Monk, Adarsh Chaluvaraju, Andrew Hojel, Andrew Ma, Anil Thomas, Ashish Tanwer, Darsh J Shah, et al. Practical efficiency of Muon for pretraining. arXiv preprint arXiv:2505.02222, 2025.arxiv.org/abs/2505.02222
  68. [71]Wei Shen, Ruichuan Huang, Minhui Huang, Cong Shen, and Jiawei Zhang. On the convergence analysis of Muon. arXiv preprint arXiv:2505.23737, 2025.arxiv.org/abs/2505.23737
  69. [72]Igor Sokolov. Non-convex stochastic optimization with biased gradient estimators. MS thesis, King Abdullah University of Science and Technology, 2022. URL https://doi.org/10.25781/KAUST-5EAM7.
  70. [73]Igor Sokolov and Peter Richtárik. MARINA-p: Superior performance in non-smooth federated optimization with adaptive stepsizes, 2024. URL https://arxiv.org/abs/2412.17082.
  71. [74]Igor Sokolov, Abdurakhmon Sadiev, Yury Demidovich, Fawaz S Al-Qahtani, and Peter Richtárik. Bernoulli-LoRA: A theoretical framework for randomized low-rank adaptation. arXiv preprint arXiv:2508.03820, 2025.arxiv.org/abs/2508.03820
  72. [75]Igor Sokolov, Laurent Condat, and Peter Richtárik. SILAGE: Memory-efficient, full-gradient-free nonconvex optimization for nested finite sums. arXiv preprint arXiv:2606.15832, 2026.arxiv.org/abs/2606.15832
  73. [76]Sebastian U Stich and Sai Praneeth Karimireddy. The error-feedback framework: Better rates for SGD with delayed gradients and compressed communication. arXiv preprint arXiv:1909.05350, 2019.arxiv.org/abs/1909.05350
  74. [77]Sebastian U Stich, Jean-Baptiste Cordonnier, and Martin Jaggi. Sparsified SGD with memory. Advances in neural information processing systems, 31, 2018.arxiv.org/abs/1809.07599
  75. [78]Fedor Stonyakin, Ilya Kuruzov, and Boris Polyak. Stopping rules for gradient methods for non-convex problems with additive noise in gradient. Journal of Optimization Theory and Applications, 198 (2):531–551, 2023.arxiv.org/abs/2205.07544
  76. [79]Tao Sun, Qingsong Wang, Dongsheng Li, and Bao Wang. Momentum ensures convergence of signSGD under weaker assumptions. In International Conference on Machine Learning, pages 33077–33099. PMLR, 2023.
  77. [80]Yuki Takezawa, Anastasia Koloskova, Xiaowen Jiang, and Sebastian U Stich. FedMuon: Federated learning with bias-corrected LMO-based optimization. arXiv preprint arXiv:2509.26337, 2025.arxiv.org/abs/2509.26337
  78. [81]Paul Tseng and Dimitri P Bertsekas. Relaxation methods for problems with strictly convex costs and linear constraints. Mathematics of operations research, 16(3):462–481, 1991.
  79. [82]Paul Tseng and Sangwoon Yun. Block-coordinate gradient descent method for linearly constrained nonsmooth separable optimization. Journal of optimization theory and applications, 140(3):513–535, 2009.DOI
  80. [83]Alexander Tyurin. Toward a unified theory of gradient descent under generalized smoothness. arXiv preprint arXiv:2412.11773, 2024.arxiv.org/abs/2412.11773
  81. [84]Alexander Tyurin and Peter Richtárik. Optimal time complexities of parallel stochastic optimization methods under a fixed computation model. Advances in Neural Information Processing Systems, 36:16515–16577, 2023.
  82. [85]Thijs Vogels, Sai Praneeth Karimireddy, and Martin Jaggi. PowerSGD: Practical low-rank gradient compression for distributed optimization. Advances in Neural Information Processing Systems, 32, 2019.arxiv.org/abs/1905.13727
  83. [88]Shuo Xie, Tianhao Wang, Beining Wu, and Zhiyuan Li. A tale of two geometries: Adaptive optimizers and non-Euclidean descent. arXiv preprint arXiv:2511.20584, 2025.arxiv.org/abs/2511.20584
  84. [89]Kai Yi, Timur Kharisov, Igor Sokolov, and Peter Richtárik. Cohort squeeze: Beyond a single communication round per cohort in cross-device federated learning. arXiv preprint arXiv:2406.01115, 2024.arxiv.org/abs/2406.01115
  85. [90]Xiaotong Yuan and Ping Li. On convergence of FedProx: Local dissimilarity invariant bounds, nonsmoothness and beyond. Advances in Neural Information Processing Systems, 35:10752–10765, 2022.arxiv.org/abs/2206.05187
  86. [91]Xinwen Zhang and Hongchang Gao. On provable benefits of Muon in federated learning. arXiv preprint arXiv:2510.03866, 2025.arxiv.org/abs/2510.03866

Paper details

vlnc:W_sz5bumth
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 2

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents