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

arXiv: https://arxiv.org/abs/2601.20399 · HTML: https://mlsanity.com/paper/2601.20399/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 34 references that are in the map.
- First posted on arXiv 28 Jan 2026.

## Builds on (most cited first, 21 of 21)

- [Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation](https://mlsanity.com/paper/1406.1078/) (2014)
- [Pointer Sentinel Mixture Models](https://mlsanity.com/paper/1609.07843/) (2016)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Error Feedback Fixes SignSGD and other Gradient Compression Schemes](https://mlsanity.com/paper/1901.09847/) (2019)
- [PowerSGD: Practical Low-Rank Gradient Compression for Distributed Optimization](https://mlsanity.com/paper/1905.13727/) (2019)
- [Coordinate Descent Algorithms](https://mlsanity.com/paper/1502.04759/) (2015)
- [A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networks](https://mlsanity.com/paper/1901.06053/) (2019)
- [Tight Analyses for Non-Smooth Stochastic Gradient Descent](https://mlsanity.com/paper/1812.05217/) (2018)
- [High Probability Convergence of Stochastic Gradient Methods](https://mlsanity.com/paper/2302.14843/) (2023)
- [From Gradient Clipping to Normalization for Heavy Tailed SGD](https://mlsanity.com/paper/2410.13849/) (2024)
- [First Exit Time Analysis of Stochastic Gradient Descent Under Heavy-Tailed Gradient Noise](https://mlsanity.com/paper/1906.09069/) (2019)
- [Nonconvex Stochastic Optimization under Heavy-Tailed Noises: Optimal Convergence without Gradient Clipping](https://mlsanity.com/paper/2412.19529/) (2024)
- [Subspace Optimization for Large Language Models with Convergence Guarantees](https://mlsanity.com/paper/2410.11289/) (2024)
- [High Probability Convergence Bounds for Non-convex Stochastic Gradient Descent with Sub-Weibull Noise](https://mlsanity.com/paper/2006.05610/) (2020)
- [Revisiting Gradient Normalization and Clipping for Nonconvex SGD under Heavy-Tailed Noise: Necessity, Sufficiency, and Acceleration](https://mlsanity.com/paper/2410.16561/) (2024)
- [A stochastic subspace approach to gradient-free optimization in high dimensions](https://mlsanity.com/paper/2003.02684/) (2020)
- [A Memory Efficient Randomized Subspace Optimization Method for Training Large Language Models](https://mlsanity.com/paper/2502.07222/) (2025)
- [Greedy Low-Rank Gradient Compression for Distributed Learning with Convergence Guarantees](https://mlsanity.com/paper/2507.08784/) (2025)
- [Problem-dependent convergence bounds for randomized linear gradient compression](https://mlsanity.com/paper/2411.12898/) (2024)
- [Efficient Optimization with Orthogonality Constraint: a Randomized Riemannian Submanifold Method](https://mlsanity.com/paper/2505.12378/) (2025)
- [Sketched Adaptive Federated Deep Learning: A Sharp Convergence Analysis](https://mlsanity.com/paper/2411.06770/) (2024)

## Built on by (most cited first, 1 of 1)

- [Randomized Subspace Nesterov Accelerated Gradient](https://mlsanity.com/paper/2605.00740/) (2026)

## 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.