A Piecewise Lyapunov Analysis of Sub-quadratic SGD: Applications to Robust and Quantile Regression
ACM SIGMETRICS Performance Evaluation Review · 16.06.2025 · 53 (1) · 85-87
DOI: 10.1145/3744970.3727269 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM SIGMETRICS Performance Evaluation Review, online erschienen am 17.06.2025. Verfasst von Yixuan Zhang und 3 weiteren Autor:innen. Die Arbeit wurde bisher 4-mal zitiert (Crossref) und nennt 25 Literaturangaben. Gefördert von: National Science Foundation.
Abstract (Originalsprache)
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.
Förderung
- National Science Foundation
Zitieren
APA
Zhang, Y., Huo, D. L., Chen, Y., & Xie, Q. (2025). A Piecewise Lyapunov Analysis of Sub-quadratic SGD: Applications to Robust and Quantile Regression. ACM SIGMETRICS Performance Evaluation Review, 53(1), 85-87. https://doi.org/10.1145/3744970.3727269
Vancouver
Zhang Y, Huo DL, Chen Y, Xie Q. A Piecewise Lyapunov Analysis of Sub-quadratic SGD: Applications to Robust and Quantile Regression. ACM SIGMETRICS Performance Evaluation Review. 2025;53(1):85-87. doi:10.1145/3744970.3727269
BibTeX
@article{Zhang2025,
author = {Zhang, Yixuan and Huo, Dongyan (Lucy) and Chen, Yudong and Xie, Qiaomin},
title = {A Piecewise Lyapunov Analysis of Sub-quadratic SGD: Applications to Robust and Quantile Regression},
journal = {ACM SIGMETRICS Performance Evaluation Review},
year = {2025},
volume = {53},
number = {1},
pages = {85--87},
doi = {10.1145/3744970.3727269}
}
EUVIMED