Nov, 2018

近线性时间高维鲁棒均值估计

PDF
TL;DR本文针对高维下平均数估计的稳健模型、对抗性污染和相应算法进行研究，提出了一种基于当前猜测值参数化的 SDP 族的自然算法，并经证明该算法在次线性时间内逼近真实平均数并达到了理论误差的信息论最优解，同时认为该算法还能进一步实现高维稳健学习问题的次线性时间算法。
发现论文，激发创造
  • 鲁棒均值估计有多难？

    该论文阐述了在自然情况下改善多项式算法稳健均值估计误差率在计算上可能是不可行的，并探索了改善现有算法的错误率的自然方法，并证明了这将意味着小集合扩展问题的有效算法。

    Mar, 2019

  • 高维稳健协方差估计的快速算法

    本文研究了协方差矩阵的估计问题，当仅有小部分样本被恶意更改时，我们提出了一种运行时间接近计算经验协方差且具有最佳误差保证的算法，该算法适用于高维分布，能处理高斯分布等深度分布结构及矩阵乘法指数中的病态情形。

    Jun, 2019

  • 稳健稀疏均值估计的次二次时间算法

    稀疏均值估计算法在存在对抗性异常值的情况下的研究，提出了一种在次二次时间内运行的鲁棒稀疏均值估计算法，并在检测弱相关性方面取得了算法进展。

    Mar, 2024

  • 高斯健壮学习：高效获得最优误差

    本文针对高维高斯分布参数学习问题进行了研究，提出了鲁棒估计算法，在拥有少量恶意样本的情况下实现了 $O (ε)$ 精度的估计，同时也证明了算法的多项式时间复杂度和多项式数量样本要求。

    Apr, 2017

  • 近线性时间内的最优鲁棒线性回归

    研究了高维稳健线性回归问题，在受到对抗性破坏的情况下提出了估计方法，包括样本复杂度，恢复保证，运行时间等关键指标，并利用近期算法发展的加速算法和高斯舍入技术等方法来优化估计器的运行时间和统计样本复杂性。

    Jul, 2020

  • 具有亚高斯速率的均值估计的快速谱算法

    研究估计具有有界平均值和协方差的重尾随机向量均值的算法问题，提供了一种基于谱方法的算法来解决该问题，并且只需要计算近似特征向量，取得了最优的统计性能和更快的运行速度。

    Aug, 2019

  • 高维度下的鲁棒性对实际应用有益

    该论文介绍了一种通过使用分布模型以及多项式时间算法在高维数据中实现鲁棒性估计的方法，并且提出了优化方法，以使算法能够适应更多的数据异常值，实现更高效的鲁棒性估计。

    Mar, 2017

  • 关于鲁棒线性回归的高效算法及下界

    研究了高维线性回归在对抗性污染下的稳健模型问题，并针对从高斯分布生成的未被修正的样本的基本情况给出了几乎最紧的上界和计算下界。

    May, 2018

  • 在线稳健均值估计

    在线高维健壮均值估计问题的研究，讨论传感器在在线环境下的独立采样和恶意行为，给出了一个高效算法以及附加假设下的低效算法。

    Oct, 2023

  • 稳定凸松弛法私有鲁棒估计

    提出了一种新的框架，以将鲁棒性的凸松弛算法修改为满足适当参数规范的强最坏情况稳定性保证。通过这一框架，提出了一个可以在存在恶意数据干扰下实现微分隐私的高阶矩的鲁棒估计的算法，包括均值和协方差的估计。该算法成功地应用于成族分布，并在适当参数范数下提供恢复和维度参数的从容保证。

    Dec, 2021