# A Piecewise Lyapunov Analysis of Sub-quadratic SGD: Applications to Robust and Quantile Regression

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 71 references that are in the map.
- First posted on arXiv 11 Apr 2025.

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

- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [A Simple Baseline for Bayesian Uncertainty in Deep Learning](https://mlsanity.com/paper/1902.02476/) (2019)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition](https://mlsanity.com/paper/1503.02101/) (2015)
- [A General and Adaptive Robust Loss Function](https://mlsanity.com/paper/1701.03077/) (2017)
- [Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/1902.00923/) (2019)
- [Non-convex Optimization for Machine Learning](https://mlsanity.com/paper/1712.07897/) (2017)
- [Matrix Completion has No Spurious Local Minimum](https://mlsanity.com/paper/1605.07272/) (2016)
- [Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)](https://mlsanity.com/paper/1306.2119/) (2013)
- [Bridging the Gap between Constant Step Size Stochastic Gradient Descent and Markov Chains](https://mlsanity.com/paper/1707.06386/) (2017)
- [On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration](https://mlsanity.com/paper/2004.04719/) (2020)
- [Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learning](https://mlsanity.com/paper/1905.11425/) (2019)
- [An Analysis of Constant Step Size SGD in the Non-convex Regime: Asymptotic Normality and Bias](https://mlsanity.com/paper/2006.07904/) (2020)
- [Outlier-robust estimation of a sparse linear model using ℓ1-penalized Huber's M-estimator](https://mlsanity.com/paper/1904.06288/) (2019)
- [Bias and Extrapolation in Markovian Linear Stochastic Approximation with Constant Stepsizes](https://mlsanity.com/paper/2210.00953/) (2022)
- [A Statistical Analysis of Polyak-Ruppert Averaged Q-learning](https://mlsanity.com/paper/2112.14582/) (2021)
- [Statistical consistency and asymptotic normality for high-dimensional robust M-estimators](https://mlsanity.com/paper/1501.00312/) (2015)
- [Statistically Optimal and Computationally Efficient Low Rank Tensor Completion from Noisy Entries](https://mlsanity.com/paper/1711.04934/) (2017)
- [Online Robust Regression via SGD on the l1 loss](https://mlsanity.com/paper/2007.00399/) (2020)
- [Finite-Sample Analysis of Stochastic Approximation Using Smooth Convex Envelopes](https://mlsanity.com/paper/2002.00874/) (2020)
- [Quantile Regression Under Memory Constraint](https://mlsanity.com/paper/1810.08264/) (2018)
- [Constant Stepsize Q-learning: Distributional Convergence, Bias and Extrapolation](https://mlsanity.com/paper/2401.13884/) (2024)
- [Smoothing quantile regressions](https://mlsanity.com/paper/1905.08535/) (2019)
- [Statistical Properties of the log-cosh Loss Function Used in Machine Learning](https://mlsanity.com/paper/2208.04564/) (2022)
- [Convergence and concentration properties of constant step-size SGD through Markov chains](https://mlsanity.com/paper/2306.11497/) (2023)
- [Scale calibration for high-dimensional robust regression](https://mlsanity.com/paper/1811.02096/) (2018)
- [The Collusion of Memory and Nonlinearity in Stochastic Approximation With Constant Stepsize](https://mlsanity.com/paper/2405.16732/) (2024)
- [Prelimit Coupling and Steady-State Convergence of Constant-stepsize Nonsmooth Contractive SA](https://mlsanity.com/paper/2404.06023/) (2024)

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

- [Pure Exploration via Frank-Wolfe Self-Play](https://mlsanity.com/paper/2509.19901/) (2025)
- [Wasserstein-p Central Limit Theorem Rates: From Local Dependence to Markov Chains](https://mlsanity.com/paper/2601.08184/) (2026)
- [Scaling Limits of Constant-Stepsize SGD at Flat Minima](https://mlsanity.com/paper/2607.16384/) (2026)

## Abstract (arXiv)

Motivated by robust and quantile regression problems, we investigate the stochastic gradient descent (SGD) algorithm for minimizing an objective function f that is locally strongly convex with a sub--quadratic tail. This setting covers many widely used online statistical methods. We introduce a novel piecewise Lyapunov function that enables us to handle functions f with only first-order differentiability, which includes a wide range of popular loss functions such as Huber loss. Leveraging our proposed Lyapunov function, we derive finite-time moment bounds under general diminishing stepsizes, as well as constant stepsizes. We further establish the weak convergence, central limit theorem and bias characterization under constant stepsize, providing the first geometrical convergence result for sub--quadratic SGD. Our results have wide applications, especially in online statistical methods. In particular, we discuss two applications of our results. 1) Online robust regression: We consider a corrupted linear model with sub--exponential covariates and heavy--tailed noise. Our analysis provides convergence rates comparable to those for corrupted models with Gaussian covariates and noise. 2) Online quantile regression: Importantly, our results relax the common assumption in prior work that the conditional density is continuous and provide a more fine-grained analysis for the moment bounds.