# Central Limit Theorems for Stochastic Gradient Descent Quantile Estimators

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 28 of its 82 references that are in the map.
- First posted on arXiv 4 Mar 2025.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysis](https://mlsanity.com/paper/1702.03849/) (2017)
- [SGD: General Analysis and Improved Rates](https://mlsanity.com/paper/1901.09401/) (2019)
- [Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence](https://mlsanity.com/paper/2002.10542/) (2020)
- [The Heavy-Tail Phenomenon in SGD](https://mlsanity.com/paper/2006.04740/) (2020)
- [Global Convergence of Langevin Dynamics Based Algorithms for Nonconvex Optimization](https://mlsanity.com/paper/1707.06618/) (2017)
- [Bridging the Gap between Constant Step Size Stochastic Gradient Descent and Markov Chains](https://mlsanity.com/paper/1707.06386/) (2017)
- [Statistical Inference for Model Parameters in Stochastic Gradient Descent](https://mlsanity.com/paper/1610.08637/) (2016)
- [The Step Decay Schedule: A Near Optimal, Geometrically Decaying Learning Rate Procedure For Least Squares](https://mlsanity.com/paper/1904.12838/) (2019)
- [Harder, Better, Faster, Stronger Convergence Rates for Least-Squares Regression](https://mlsanity.com/paper/1602.05419/) (2016)
- [An Analysis of Constant Step Size SGD in the Non-convex Regime: Asymptotic Normality and Bias](https://mlsanity.com/paper/2006.07904/) (2020)
- [Global Non-convex Optimization with Discretized Diffusions](https://mlsanity.com/paper/1810.12361/) (2018)
- [Online Covariance Matrix Estimation in Stochastic Gradient Descent](https://mlsanity.com/paper/2002.03979/) (2020)
- [Convergence Rates of Stochastic Gradient Descent under Infinite Noise Variance](https://mlsanity.com/paper/2102.10346/) (2021)
- [Bias and Extrapolation in Markovian Linear Stochastic Approximation with Constant Stepsizes](https://mlsanity.com/paper/2210.00953/) (2022)
- [Adaptive SGD with Polyak stepsize and Line-search: Robust Convergence and Variance Reduction](https://mlsanity.com/paper/2308.06058/) (2023)
- [Tight Dimension Independent Lower Bound on the Expected Convergence Rate for Diminishing Step Sizes in SGD](https://mlsanity.com/paper/1810.04723/) (2018)
- [Quantile Regression Under Memory Constraint](https://mlsanity.com/paper/1810.08264/) (2018)
- [Multiplicative noise and heavy tails in stochastic optimization](https://mlsanity.com/paper/2006.06293/) (2020)
- [Stationary Behavior of Constant Stepsize SGD Type Algorithms: An Asymptotic Characterization](https://mlsanity.com/paper/2111.06328/) (2021)
- [Online Bootstrap Inference with Nonconvex Stochastic Gradient Descent Estimator](https://mlsanity.com/paper/2306.02205/) (2023)
- [Distributed inference for quantile regression processes](https://mlsanity.com/paper/1701.06088/) (2017)
- [Convergence and concentration properties of constant step-size SGD through Markov chains](https://mlsanity.com/paper/2306.11497/) (2023)
- [On the Convergence of Stochastic Gradient Descent with Bandwidth-based Step Size](https://mlsanity.com/paper/2102.09031/) (2021)
- [Online Quantile Regression](https://mlsanity.com/paper/2402.04602/) (2024)
- [Asymptotics of Stochastic Gradient Descent with Dropout Regularization in Linear Models](https://mlsanity.com/paper/2409.07434/) (2024)
- [Convergence of Recursive Stochastic Algorithms using Wasserstein Divergence](https://mlsanity.com/paper/2003.11403/) (2020)
- [Probabilistic Guarantees of Stochastic Recursive Gradient in Non-Convex Finite Sum Problems](https://mlsanity.com/paper/2401.15890/) (2024)

## Abstract (arXiv)

This paper develops asymptotic theory for quantile estimation via stochastic gradient descent (SGD) with a constant learning rate. The quantile loss function is neither smooth nor strongly convex. Beyond conventional perspectives and techniques, we view quantile SGD iteration as an irreducible, periodic, and positive recurrent Markov chain, which cyclically converges to its unique stationary distribution regardless of the arbitrarily fixed initialization. To derive the exact form of the stationary distribution, we analyze the structure of its characteristic function by exploiting the stationary equation. We also derive tight bounds for its moment generating function (MGF) and tail probabilities. Synthesizing the aforementioned approaches, we prove that the centered and standardized stationary distribution converges to a Gaussian distribution as the learning rate ηrightarrow0. This finding provides the first central limit theorem (CLT)-type theoretical guarantees for the quantile SGD estimator with constant learning rates. We further propose a recursive algorithm to construct confidence intervals of the estimators with statistical guarantees. Numerical studies demonstrate the effective finite-sample performance of the online estimator and inference procedure. The theoretical tools developed in this study are of independent interest for investigating general SGD algorithms formulated as Markov chains, particularly in non-strongly convex and non-smooth settings.