EUVIMEDEUVIMED entdecken
Crossref

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

Yixuan Zhang, Dongyan (Lucy) Huo, Yudong Chen, Qiaomin Xie

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →