arXiv:2504.08178stat.MLcs.LG2025-04被引 4

提出分段李雅普诺夫函数分析子二次梯度下降,提升鲁棒与分位数回归的理论保障

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

  • 设计分段李雅普诺夫函数,处理仅一阶可导的损失函数
  • 在衰减和恒定步长下均获有限时间矩界,首次实现几何收敛性
  • 适用于在线统计方法,尤其改进了鲁棒与分位数回归的分析条件

针对鲁棒与分位数回归问题,研究目标函数 $f$ 局部强凸且尾部为子二次的随机梯度下降(SGD)算法。该设定涵盖多种常用在线统计方法。本文提出一种新型分段李雅普诺夫函数,可处理仅一阶可导的函数,包含Huber损失等广泛使用的损失函数。借助该函数,在一般递减步长及恒定步长下,我们推导出有限时间矩界;并建立了恒定步长下的弱收敛、中心极限定理与偏差刻画,首次获得子二次SGD的几何收敛结果。结果具有广泛应用价值,特别在:1)在线鲁棒回归中,针对亚指数协变量与重尾噪声的污染线性模型,收敛率媲美高斯情形;2)在线分位数回归中,放宽了以往对条件密度连续性的假设,实现更精细的矩界分析。

原文摘要 · Abstract (English)

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.

优化理论鲁棒回归分位数回归随机梯度

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。