arXiv:2510.10690math.OCcs.LG2025-10NeurIPS被引 4

提出应对重尾噪声的二阶优化方法,实现稳定高效训练。

Second-order Optimization under Heavy-Tailed Noise: Hessian Clipping and Sample Complexity Limits

  • 通过梯度与海森矩阵裁剪提升算法鲁棒性
  • 证明了样本复杂度下界并设计逼近最优的算法
  • 适合处理含异常值或非平稳数据的机器学习场景

重尾噪声广泛存在于现代机器学习应用中,源于数据异质性、异常值及非平稳随机环境。尽管二阶方法在轻尾或有界噪声下可显著加速收敛,但在重尾噪声下往往不稳定且缺乏理论保证——这恰恰是鲁棒性最需关注的场景。本文首次从理论上研究重尾噪声下的二阶优化问题,考虑随机梯度与海森矩阵仅具有有界 $p$-阶矩($p ∈ (1,2]$)的情形,建立了任意二阶方法的紧致样本复杂度下界。随后提出一种利用二阶信息的归一化随机梯度下降变体,理论上匹配该下界。为应对大偏差导致的不稳定性,引入基于梯度与海森矩阵裁剪的新算法,并证明其高概率上界几乎达到根本极限。结果首次给出了重尾噪声下二阶优化的完整样本复杂度刻画,确立了海森裁剪作为重尾环境下稳健且理论可信的算法设计策略。

原文摘要 · Abstract (English)

Heavy-tailed noise is pervasive in modern machine learning applications, arising from data heterogeneity, outliers, and non-stationary stochastic environments. While second-order methods can significantly accelerate convergence in light-tailed or bounded-noise settings, such algorithms are often brittle and lack guarantees under heavy-tailed noise -- precisely the regimes where robustness is most critical. In this work, we take a first step toward a theoretical understanding of second-order optimization under heavy-tailed noise. We consider a setting where stochastic gradients and Hessians have only bounded $p$-th moments, for some $p\in (1,2]$, and establish tight lower bounds on the sample complexity of any second-order method. We then develop a variant of normalized stochastic gradient descent that leverages second-order information and provably matches these lower bounds. To address the instability caused by large deviations, we introduce a novel algorithm based on gradient and Hessian clipping, and prove high-probability upper bounds that nearly match the fundamental limits. Our results provide the first comprehensive sample complexity characterization for second-order optimization under heavy-tailed noise. This positions Hessian clipping as a robust and theoretically sound strategy for second-order algorithm design in heavy-tailed regimes.

二阶优化重尾噪声鲁棒学习

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