mlsanityData to 7 Oct 2026

Convergence Analysis of Randomized Subspace Normalized SGD under Heavy-Tailed Noise

arXiv 2601.20399 ↗First posted 28 Jan 2026math.OC cs.LG stat.MLcited by 1

Not on the map. Why?

Abstract (arXiv)

Randomized subspace methods reduce per-iteration cost; however, in nonconvex optimization, most analyses are expectation-based, and high-probability bounds remain scarce even under sub-Gaussian noise. We first prove that randomized subspace SGD (RS-SGD) admits a high-probability convergence bound under sub-Gaussian noise, achieving the same order of oracle complexity as prior in-expectation results. Motivated by the prevalence of heavy-tailed gradients in modern machine learning, we then propose randomized subspace normalized SGD (RS-NSGD), which integrates direction normalization into subspace updates. Assuming the noise has bounded p-th moments, we establish both in-expectation and high-probability convergence guarantees, and show that RS-NSGD can achieve better oracle complexity than full-dimensional normalized SGD.

Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 21 of its 34 references that are in the map. First posted on arXiv 28 Jan 2026.

Builds on

21 of 34 references.

References · 21

  1. 2014Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translationcited by 4,016
  2. 2016Pointer Sentinel Mixture Modelscited by 2,992
  3. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 716
  4. 2019Error Feedback Fixes SignSGD and other Gradient Compression Schemescited by 306
  5. 2019PowerSGD: Practical Low-Rank Gradient Compression for Distributed Optimizationcited by 234
  6. 2015Coordinate Descent Algorithmscited by 218
  7. 2019A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networkscited by 213
  8. 2018Tight Analyses for Non-Smooth Stochastic Gradient Descentcited by 94
  9. 2023High Probability Convergence of Stochastic Gradient Methodscited by 48
  10. 2024From Gradient Clipping to Normalization for Heavy Tailed SGDcited by 48
  11. 2019First Exit Time Analysis of Stochastic Gradient Descent Under Heavy-Tailed Gradient Noisecited by 43
  12. 2024Nonconvex Stochastic Optimization under Heavy-Tailed Noises: Optimal Convergence without Gradient Clippingcited by 42
9 more
  1. 2020High Probability Convergence Bounds for Non-convex Stochastic Gradient Descent with Sub-Weibull Noisecited by 31
  2. 2024Subspace Optimization for Large Language Models with Convergence Guaranteescited by 31
  3. 2024Revisiting Gradient Normalization and Clipping for Nonconvex SGD under Heavy-Tailed Noise: Necessity, Sufficiency, and Accelerationcited by 18
  4. 2020A stochastic subspace approach to gradient-free optimization in high dimensionscited by 15
  5. 2025A Memory Efficient Randomized Subspace Optimization Method for Training Large Language Modelscited by 15
  6. 2025Greedy Low-Rank Gradient Compression for Distributed Learning with Convergence Guaranteescited by 9
  7. 2024Problem-dependent convergence bounds for randomized linear gradient compressioncited by 3
  8. 2025Efficient Optimization with Orthogonality Constraint: a Randomized Riemannian Submanifold Methodcited by 3
  9. 2024Sketched Adaptive Federated Deep Learning: A Sharp Convergence Analysiscited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Randomized Subspace Nesterov Accelerated Gradientcited by 0