高斯健壮学习:高效获得最优误差
本文提出了一种统计查询下限技术,用于解决高维学习问题中高斯分布的学习和鲁棒性学习问题,并得出了样本复杂度和计算复杂度之间存在的超多项式差距,同时提供了一个新的方法来解决一些相关的无监督估计和测试问题。
Nov, 2016
该论文介绍了一种通过使用分布模型以及多项式时间算法在高维数据中实现鲁棒性估计的方法,并且提出了优化方法,以使算法能够适应更多的数据异常值,实现更高效的鲁棒性估计。
Mar, 2017
本文针对高维下平均数估计的稳健模型、对抗性污染和相应算法进行研究,提出了一种基于当前猜测值参数化的SDP族的自然算法,并经证明该算法在次线性时间内逼近真实平均数并达到了理论误差的信息论最优解,同时认为该算法还能进一步实现高维稳健学习问题的次线性时间算法。
Nov, 2018
本文研究了协方差矩阵的估计问题,当仅有小部分样本被恶意更改时,我们提出了一种运行时间接近计算经验协方差且具有最佳误差保证的算法,该算法适用于高维分布,能处理高斯分布等深度分布结构及矩阵乘法指数中的病态情形。
Jun, 2019
研究了在高维高斯混合假设下,少量数据受到对手损坏的情况下的高效可学习性,提出了一种多项式算法并证明了在成分经过配对后在总变异距离上分离时,该问题是可多项式学习的;这种算法是第一个可处理$k=2$的高斯混合问题的多项式时间算法,并使用基于Sum-of-Squares证明算法的技术,提出了一种新的用于高斯混合的鲁棒可辨识性证明方法和使用SoS可证明的反集中方法和新的特征距离度量组来解决问题。
May, 2020
研究了高维稳健线性回归问题,在受到对抗性破坏的情况下提出了估计方法,包括样本复杂度,恢复保证,运行时间等关键指标,并利用近期算法发展的加速算法和高斯舍入技术等方法来优化估计器的运行时间和统计样本复杂性。
Jul, 2020
本文介绍了学习高斯混合分布和算法鲁棒性统计的自然融合,提出了第一个可靠的算法,用于学习任意数量的高斯混合物,且仅需要混合权重(有界分数性)和成分之间的总变差距离与零保持一定距离的温和假设条件。算法的核心是一种新的方法,通过对某些生成函数应用一系列精心选择的微分运算来证明维度无关的多项式可辨识性,这些生成函数不仅编码了我们想要学习的参数,还编码了我们想要解决的多项式方程系统。我们展示了如何直接使用我们推导出的符号身份来分析自然的平方和松弛问题。
Nov, 2020
提出了一个将差分隐私统计估计转化为无差分隐私的框架,并给出了用于学习高斯分布和鲁棒学习高斯分布的多项式时间差分隐私算法,该方法中学习高斯分布的样本复杂度和已知的信息论样本复杂度的上限相匹配,并且还证明了相似的结果,其中鲁棒学习高斯分布的样本复杂度更低。
Nov, 2021