稳健且计算效率高的基于梯度的估计方法

《Journal of Statistical Planning and Inference》:Robust and computationally efficient gradient-based estimation

【字体: 大 中 小 】 时间:2026年02月11日 来源:Journal of Statistical Planning and Inference 1.1

编辑推荐:

  严一博|王晓洲|张日权 中国上海华东师范大学统计学院,统计与数据科学高级理论及应用重点实验室,邮编200062 摘要 本文提出了一类基于稳健且计算效率高的梯度估计的估计量,适用于低维和高维风险最小化框架。该文中的梯度估计是通过一系列新提出的单变量稳健高效均值估计量构建的。我们所提

  严一博|王晓洲|张日权 中国上海华东师范大学统计学院,统计与数据科学高级理论及应用重点实验室,邮编200062 摘要 本文提出了一类基于稳健且计算效率高的梯度估计的估计量,适用于低维和高维风险最小化框架。该文中的梯度估计是通过一系列新提出的单变量稳健高效均值估计量构建的。我们所提出的估计量是通过梯度下降法的变体迭代得到的,其更新方向由稳健且计算高效的梯度决定。这些估计量不仅具有明确的表达式,可通过算术运算得到,而且对常见统计模型中的任意异常值都具有稳健性。从理论上讲,我们证明了这些算法的收敛性,并为这些迭代估计量给出了非渐近误差界。具体而言,我们将方法应用于线性回归和逻辑回归模型,得到了稳健的参数估计值以及相应的超额风险界。与以往的研究不同,我们的理论结果依赖于异常值的幅度函数,该函数能够反映异常值与正常值的偏离程度。最后,我们在低维和高维线性模型上进行了大量仿真实验,证明了所提估计量相比几种基线方法具有更优的性能。引言 近年来,稳健性在机器学习和统计学领域都发挥着重要作用,越来越多的人致力于开发稳健算法以减轻异常值和数据污染的影响。尽管现代预处理技术能够检测并过滤部分异常值,但识别所有异常值仍是一项重大挑战。当将机器学习方法应用于不熟悉的数据集时,从业者力求避免丢弃有价值的数据。因此,未经稳健修改的流行机器学习算法在受到污染的数据集上可能会表现不佳。本研究旨在引入一类新的稳健估计量,使其在低维和高维受污染的数据框架中仍能保持优异性能。此外,我们所提出的估计量具有较高的计算效率,可通过简单的算术运算直接实现。稳健统计的起源可追溯到Box(1953)、Huber(1964)和Hampel(1971)的开创性工作。在这些概念和思想的基础上,稳健估计量的发展以及稳健且计算高效算法的设计已成为统计学中的重要课题。为了获得这类估计量,我们聚焦于经验风险最小化框架,这是一种广泛用于各种机器学习问题的基本方法。例如,Chaudhuri等人(2011)通过正则化的经验风险最小化方法设计了具有隐私保护功能的分类器近似算法。一些统计学家系统地研究了非凸损失下的经验风险性质,并将其结果推广到高维场景,见Mei等人(2018)的研究。Taheri等人(2021)则探讨了高维广义线性模型中凸岭回归正则化经验风险最小化的统计精度极限。考虑一个一般的风险最小化问题:β?=argminβ∈ΘEz~PL(β;z),其中L为损失函数,z表示来自概率测度P的随机向量,β∈Θ为参数。这里,我们通常用R(β)=Ez~PL(β;z)表示风险函数。风险最小化框架的目标是找到真实参数β?。由于底层分布P通常是未知的,基于独立同分布的观测值DN={z1,…,zN},可以使用经验风险函数?RN(β)?(1/N)∑i=1NL(β;zi)来替代R(β),进而通过经验风险最小化得到估计量β?N: β?N=argminβ∈Θ1N∑i=1NL(β;zi)。当观测值中没有异常值时,估计量β?N具有优异的性质,是理想的选择。但如果DN被异常值污染,经验风险最小化器的性能就会下降,从而成为不可靠的估计量。通常,有两种方法可以将原始的经验风险最小化扩展为稳健版本:一种是通过用稳健的替代损失函数来修改损失函数,另一种则是采用稳健算法来寻找最小化器,从而得到稳健解。在本研究中,我们采用第二种方法,旨在为低维和高维数据场景推导出一类稳健估计量。假设损失函数是可微的,通常会使用梯度下降法及其变体来得到最终估计量。然而,这些基于经验梯度的估计量容易受到异常值的影响,因此在用于推断之前需要谨慎考虑。为了解决这个问题,我们遵循Holland和Ikeda(2019)以及Prasad等人(2020)的方法,在执行梯度下降法时使用稳健梯度估计量作为替代。要获得前两篇论文中提到的稳健梯度估计量,需要解决一个优化问题。虽然这两个优化问题是可计算的,但每次迭代都需要求解,这在处理大型数据集时可能会非常耗时。在本文中,我们没有使用上述稳健梯度,而是将Minsker和Ndaoud(2021)设计的单变量稳健高效均值估计法扩展到多变量情形,然后将其应用于一般的经验风险最小化问题中的梯度下降法。除了具备稳健性和计算效率外,这种单变量稳健高效均值估计量还被证明具有渐近效率。我们的最终估计量是迭代的,可通过简单算术运算直接得到,无需任何隐含表达式。对于一般的强凸且光滑的风险函数,我们研究了这些迭代估计量的非渐近收敛速率及其超额风险界,并将这些理论结果应用于几种典型的回归模型。主要贡献 我们提出了两种稳健且计算效率高的算法,用于在一般污染框架下估计低维和高维数据中的参数。具体如下:1. 我们考虑了一种一般的数据污染框架,其中的观测值DN由两部分组成:内点样本和异常值。内点样本是从分布P中抽取的独立同分布样本,而关于异常值,我们只知道它们与内点样本相互独立。2. 我们采用了一种新颖的稳健且计算效率高的梯度估计量。如Prasad等人(2020)所述,估计梯度本质上涉及估计多变量均值。在本研究中,我们将Minsker和Ndaoud(2021)的单变量均值估计法推广到多变量情形。为了得到稳健且计算效率高的梯度估计量,首先需要将数据集随机分成多个块,然后分别计算每个块的经验梯度。接着,对于每个块,计算对应经验梯度中每个坐标的标准差。最后,根据单变量稳健高效均值估计量的定义,为每个坐标计算目标梯度估计量,并将所有分量组合成一个向量。这样就得到了我们稳健且计算效率高的梯度估计量的偏差不等式,这对于确保后续算法的收敛性至关重要。3. 基于我们提出的稳健且计算效率高的梯度估计量,我们提出了所谓的稳健高效梯度下降算法(RCEGD),用于解决低维场景下的参数估计问题。对于高维场景,研究人员采用了迭代硬阈值算法进行稳健估计(Liu等人,2019)。类似地,我们将RCEGD与迭代硬阈值算法结合,设计了稳健高效硬阈值算法(RCEHT),用于高维参数估计。4. 我们验证了所提算法的收敛性,并为这些估计量给出了非渐近误差界。在低维场景下,我们的迭代估计量相对于次高斯误差界而言,能够达到次优的误差率。在高维场景下,我们证明了这些估计量能够达到近乎最优的统计误差率。除了理论分析之外,我们还进行了大量仿真实验,以验证所提估计量在典型统计模型下的可行性和优越性。在这些仿真中,我们使用基于均值中位数梯度估计的稳健估计量作为对比和评估的基准。实验结果表明,无论块数和污染程度如何,我们的稳健且计算效率高的估计量在大多数情况下都优于基准方法。此外,我们还提出了一种选择超参数的启发式方法,并通过仿真验证了该方法的有效性。近年来,关于稳健性的研究已成为统计机器学习领域最关键的课题之一,几乎涵盖了该领域的所有方面。在这里,我们主要回顾了与我们的工作相关的文献。重尾模型和Huber的?污染模型是近期文献中最常讨论的两种稳健性概念。(1) 重尾模型:在这种模型中,假设底层分布P具有重尾特性,而P的低阶矩被认为是有限的。Lerasle和Oliveira(2011)、Catoni(2012)、Minsker(2015)以及Lugosi和Mendelson(2019b)的研究目标是获得具有小误差且出现概率极高的稳健均值估计量。具体而言,Minsker将均值中位数估计量推广到了巴拿赫空间,并开发了一种建立浓度不等式的技巧(Minsker,2015)。Hsu和Sabato将均值中位数估计量与经验风险最小化方法结合,开发了一种用于近似最小化光滑和强凸损失的稳健算法(Hsu和Sabato,2016)。Catoni为均值设计了一种新的M估计量,并证明其在一维场景下能够达到次高斯误差界(Catoni,2012),Devroye等人(2016)也报告了类似的结果。随后,Brownlees等人(2015)利用这些稳健均值估计量解决了存在重尾噪声时的经验风险最小化问题。此外,Lugosi和Mendelson在多维场景下取得了突破性进展(Lugosi和Mendelson,2019b)。他们沿用了Lugosi和Mendelson(2019a)的方法,即引入“均值中位数竞赛”技术并提出了多变量均值中位数估计量,最终得到了最优的误差界。这些工作的核心思想是设计稳健均值估计量,并将其作为经验风险最小化框架中风险函数经验均值的替代品,从而获得通用的稳健估计量。然而,许多这类研究涉及优化复杂的客观函数,往往缺乏高效或易于计算的算法。因此,我们没有使用基于总体风险的稳健变体,而是将稳健高效均值估计量扩展到梯度上,并将其应用于梯度下降法,从而在经验风险最小化框架中获得最终的稳健高效估计量。(2) Huber的?污染模型:在这种模型中,假设观测值是从混合分布P?=(1??)P+?Q中独立同分布抽取的。这里,P代表真实分布,Q表示异常值的分布,?为混合比例。关于?污染模型的严格研究可以追溯到Huber在1964年和1965年的基础性工作。此外,Tukey的深度概念在研究?污染模型的估计量中也起着重要作用(Tukey,1975)。一些研究人员进一步发展了Tukey的概念(Donoho和Gasko,1992;Rousseeuw和Hubert,1999;Mizera,2002)。最近,Chen等人(2016)对与Huber的?污染模型相关的统计决策理论进行了系统研究,利用他们的方法为稳健估计量建立了一系列极小极大速率。此外,这些研究人员还将Tukey的深度概念扩展到多变量回归模型的协方差矩阵和回归参数的估计上,从而在Huber模型下得到了相应的极小极大误差界(Chen等人,2018;Gao,2020)。虽然大多数基于Tukey深度的估计量在计算上较为复杂,但一些研究人员已经取得了重大进展,解决了这一难题。他们开发出了既稳健又易于计算的估计量,同时还具有出色的统计性质(Lai等人,2016;Charikar等人,2017;Kothari等人,2018;Diakonikolas等人,2019b)。另一方面,许多人在处理一般的?污染模型时,采用了平方和法来设计稳健估计量(Kothari和Steurer,2017;Klivans等人,2018;Hopkins和Li,2018)。与Huber的?污染模型不同,我们的工作不对异常值的分布施加任何额外条件,仅假设它们与内点样本相互独立。这为我们得到了关于异常值行为的更为一般的理论结果。在高维场景中,稳健性尤为重要。Chen等人(2013)研究了在对抗性污染条件下的稳健稀疏问题,并提出了第一个多项式时间算法。一些研究者将硬阈值法应用于稳健回归,首次提出了高效且一致的估计量(Bhatia等人,2017年)。Loh(2017年)的工作确立了高维稳健M估计的统计一致性和渐近正态性。此外,Liu等人(2020年)运用迭代硬阈值法来处理稳健稀疏回归问题,后来他们进一步发展了这一方法,引入了稳健硬阈值法以解决一般的稀疏约束M估计问题(Liu等人,2019年)。Diakonikolas等人(2019a年)的计算机科学家们开发出了首批具有维度无关误差保证的高效算法,用于高维稳健估计量。更多相关研究可见Balakrishnan等人(2017年)、Li(2017年)以及Diakonikolas等人(2017年)的著作。本文的其余部分结构如下:第2节介绍在受污染数据集背景下风险最小化问题的背景,以及用于解决ERM问题的经典梯度下降法及其变体。第3节提出RCEGD算法,并对其对应的估计量进行理论分析。第4节我们提出了专为高维数据设计的RCEHT算法,同时验证了迭代估计量的非渐近误差界。第5节我们在模拟数据和真实数据集上进行了多种数值实验,第6节对整个工作进行总结。所有技术细节均放在附录中。

符号说明:在本文中,我们用Rd表示d维欧几里得空间。对于任意w=w1,w2,…,wd?∈Rd,定义‖w‖2=(∑i=1dwi2)1/2,‖w‖∞=max1≤i≤d|wi|,‖w‖0=∑i=1dI(wi≠0),其中I(?)为指示函数。对于对称矩阵A∈Rd×d,‖A‖2=sup‖w‖2=1‖Aw‖2,我们用λmax(A)和λmin(A)分别表示它的最大和最小特征值。

背景与问题阐述
在本节中,在介绍所提出的算法之前,我们首先在一般受污染数据集的背景下构建风险最小化问题。

稳健且高效的梯度下降法
在本节中,我们介绍主要算法并分析其收敛性质,同时探讨其在几种典型回归模型中的性能表现。

稳健且高效的硬阈值法
在本节中,我们通过引入稳健且高效的硬阈值法(RCEHT)将算法扩展到稀疏估计问题。该算法在每次经过稳健且高效的梯度更新后应用硬阈值处理。同样,我们也在高维一般污染框架下的线性回归和逻辑回归中实现了该算法。

许多研究者致力于研究相关算法

实验部分
在本节中,我们通过大量的模拟实验,展示了所提出的稳健且高效算法在低维和高维数据环境下,针对线性回归模型和逻辑回归模型的性能。这里我们将所提出的估计量分别用算法1和算法2表示为RCEGD和RCEHT。我们将这些估计量与基于MOM方法的稳健梯度下降估计量进行比较,后者被称为RGD(Prasad等人,2020年)。我们采用了

讨论部分
在本项工作中,我们提出并分析了两种在一般污染框架下适用于低维和高维参数估计问题的稳健且高效算法。我们的算法是梯度下降法的稳健变体,它们在ERM-GD中采用稳健且高效的梯度来替代经验梯度。与基于以往稳健梯度下降算法的估计量相比,我们所提出的估计量具有明确的表达式。

致谢
我们衷心感谢责任编辑和两位匿名审稿人提出的富有洞察力且具有建设性的意见。严一博的研究得到了中国国家自然科学基金(12401390)和中国博士后科学基金会(2024M750916)的支持。王晓洲的研究则得到了中国国家自然科学基金(12101240)、上海教育发展基金会成光计划以及上海市教育委员会的资助。
相关新闻
生物通微信公众号
微信
新浪微博

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号