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

Randomized-subspace methods use low-dimensional projected stochastic gradients, offering potential savings in directional-derivative queries and communication volume. However, theoretical guarantees for such methods under heavy-tailed noise remain limited. We propose randomized subspace normalized SGD (RS-NSGD), which normalizes using only the projected stochastic gradient and thereby preserves the low-dimensional update structure. Because the random subspace also enters the normalization denominator, existing analyses of randomized subspace SGD do not directly apply. We overcome this difficulty by exploiting distributional properties specific to Haar-random projections. Under a bounded $p$-th-moment assumption commonly used in analyses of heavy-tailed stochastic-gradient noise, with $p\in (1,2]$, we establish convergence guarantees both in expectation and with high probability. Our oracle-complexity bounds characterize regimes in which RS-NSGD improves over full-dimensional normalized SGD.