高斯健壮学习:高效获得最优误差
本文针对高维下平均数估计的稳健模型、对抗性污染和相应算法进行研究,提出了一种基于当前猜测值参数化的 SDP 族的自然算法,并经证明该算法在次线性时间内逼近真实平均数并达到了理论误差的信息论最优解,同时认为该算法还能进一步实现高维稳健学习问题的次线性时间算法。
Nov, 2018
本文研究了协方差矩阵的估计问题,当仅有小部分样本被恶意更改时,我们提出了一种运行时间接近计算经验协方差且具有最佳误差保证的算法,该算法适用于高维分布,能处理高斯分布等深度分布结构及矩阵乘法指数中的病态情形。
Jun, 2019
该研究旨在解决高维分布学习中的拜占庭敌人问题,提出了面向单高斯、超立方体上的乘积分布及其混合分布和球形高斯的分布学习的算法,并为高维数据的拜占庭敌人问题提供了一种通用的检测与纠正方案。
Apr, 2016
高斯稀疏估计在 Huber 污染模型中研究,针对均值估计、主成分分析和线性回归三个任务,提出了第一个样本和计算高效的鲁棒估计器,保证了较小的误差,并且在常数因子内达到最优。之前针对这些任务的高效算法都产生了数量上次优的误差。具体而言,对于高斯的鲁棒 k 稀疏均值估计在具有污染率为 ε>0 的 R^d 上,我们的算法具有样本复杂度为 (k^2/ε^2)・polylog (d/ε),在多项式时间内运行,并且在 L2 误差为 O (ε) 的范围内逼近目标均值。之前的高效算法固有地产生了误差 Ω(ε√log (1/ε))。在技术层面上,我们开发了一种在稀疏情况下的新型多维过滤方法,可能具有其他应用。
Mar, 2024
研究了在高维高斯混合假设下,少量数据受到对手损坏的情况下的高效可学习性,提出了一种多项式算法并证明了在成分经过配对后在总变异距离上分离时,该问题是可多项式学习的;这种算法是第一个可处理 $k=2$ 的高斯混合问题的多项式时间算法,并使用基于 Sum-of-Squares 证明算法的技术,提出了一种新的用于高斯混合的鲁棒可辨识性证明方法和使用 SoS 可证明的反集中方法和新的特征距离度量组来解决问题。
May, 2020
提出了一个将差分隐私统计估计转化为无差分隐私的框架,并给出了用于学习高斯分布和鲁棒学习高斯分布的多项式时间差分隐私算法,该方法中学习高斯分布的样本复杂度和已知的信息论样本复杂度的上限相匹配,并且还证明了相似的结果,其中鲁棒学习高斯分布的样本复杂度更低。
Nov, 2021
该论文介绍了一种通过使用分布模型以及多项式时间算法在高维数据中实现鲁棒性估计的方法,并且提出了优化方法,以使算法能够适应更多的数据异常值,实现更高效的鲁棒性估计。
Mar, 2017
该论文阐述了在自然情况下改善多项式算法稳健均值估计误差率在计算上可能是不可行的,并探索了改善现有算法的错误率的自然方法,并证明了这将意味着小集合扩展问题的有效算法。
Mar, 2019