本文针对高维下平均数估计的稳健模型、对抗性污染和相应算法进行研究,提出了一种基于当前猜测值参数化的 SDP 族的自然算法,并经证明该算法在次线性时间内逼近真实平均数并达到了理论误差的信息论最优解,同时认为该算法还能进一步实现高维稳健学习问题的次线性时间算法。
Nov, 2018
本文研究了协方差矩阵的估计问题,当仅有小部分样本被恶意更改时,我们提出了一种运行时间接近计算经验协方差且具有最佳误差保证的算法,该算法适用于高维分布,能处理高斯分布等深度分布结构及矩阵乘法指数中的病态情形。
Jun, 2019
高斯稀疏估计在 Huber 污染模型中研究,针对均值估计、主成分分析和线性回归三个任务,提出了第一个样本和计算高效的鲁棒估计器,保证了较小的误差,并且在常数因子内达到最优。之前针对这些任务的高效算法都产生了数量上次优的误差。具体而言,对于高斯的鲁棒 k 稀疏均值估计在具有污染率为 ε>0 的 R^d 上,我们的算法具有样本复杂度为 (k^2/ε^2)・polylog (d/ε),在多项式时间内运行,并且在 L2 误差为 O (ε) 的范围内逼近目标均值。之前的高效算法固有地产生了误差 Ω(ε√log (1/ε))。在技术层面上,我们开发了一种在稀疏情况下的新型多维过滤方法,可能具有其他应用。
Mar, 2024
研究估计具有有界平均值和协方差的重尾随机向量均值的算法问题,提供了一种基于谱方法的算法来解决该问题,并且只需要计算近似特征向量,取得了最优的统计性能和更快的运行速度。
Aug, 2019
该论文阐述了在自然情况下改善多项式算法稳健均值估计误差率在计算上可能是不可行的,并探索了改善现有算法的错误率的自然方法,并证明了这将意味着小集合扩展问题的有效算法。
Mar, 2019
研究了高维线性回归在对抗性污染下的稳健模型问题,并针对从高斯分布生成的未被修正的样本的基本情况给出了几乎最紧的上界和计算下界。
May, 2018
本文研究在高维度及受到恶意破坏性干扰情况下,稀疏估计任务能否有效地完成,并提供了一些在存在噪音的情况下,提供非平凡误差保证的有效算法。研究表明,在这些问题上存在着计算与统计之间的差距。
Feb, 2017
本文提出了一种简单的平均值估计方法,可以在 moderate 条件下克服现有估计器面临的计算和统计问题,并基于增量学习现象推导出匹配信息理论下界。
May, 2023
本文介绍了一种基于 Median-of-Means 方法和 Semi-definite Programming 的算法,使用时并不需要先验知识,能够高效处理大数据,包含异常值和重尾数据等,稳定性强,能达到次高斯速率
本论文研究线性回归问题并提出了一种新的算法,它能够在存在离群值的情况下,对有限矩(至 $L_4$)的样本进行最佳的次高斯误差边界估计,并且通过使用谱方法研究了线性回归问题与最远超平面问题之间的关系,同时引入了第三个经验过程进行统计学属性的研究。
Jul, 2020