关于鲁棒线性回归的高效算法及下界
研究了高维稳健线性回归问题,在受到对抗性破坏的情况下提出了估计方法,包括样本复杂度,恢复保证,运行时间等关键指标,并利用近期算法发展的加速算法和高斯舍入技术等方法来优化估计器的运行时间和统计样本复杂性。
Jul, 2020
我们研究了在存在 Huber 污染时,高斯均值估计和具有高斯协变量的线性回归的基本问题。我们的主要贡献是设计出了第一个样本近优且几乎具有线性时间算法,其具有最佳的误差保证,可以解决这两个问题。
Dec, 2023
本文研究了协方差矩阵的估计问题,当仅有小部分样本被恶意更改时,我们提出了一种运行时间接近计算经验协方差且具有最佳误差保证的算法,该算法适用于高维分布,能处理高斯分布等深度分布结构及矩阵乘法指数中的病态情形。
Jun, 2019
本文针对高维高斯分布参数学习问题进行了研究,提出了鲁棒估计算法,在拥有少量恶意样本的情况下实现了 $O (ε)$ 精度的估计,同时也证明了算法的多项式时间复杂度和多项式数量样本要求。
Apr, 2017
本文首次给出了一个多项式时间算法,用于在示例和标签中对抗性堕落下执行线性或多项式回归,并基于 SoS 方法提出了一种自然的凸松弛方法来解决非凸优化问题。
Mar, 2018
研究怎样在不假设样本的基础分布为高斯分布的前提下,只假定有限个矩的情况下,有效地进行线性回归和协方差估计,并关注能用多少样本来实现高精度和指数级成功概率。使用八阶圆当量半定规划提供算法,预备性的证据表明在我们的算法使用的平均中位数框架中无法在多项式时间内改善这些误差率。
Dec, 2019
本文针对高维下平均数估计的稳健模型、对抗性污染和相应算法进行研究,提出了一种基于当前猜测值参数化的 SDP 族的自然算法,并经证明该算法在次线性时间内逼近真实平均数并达到了理论误差的信息论最优解,同时认为该算法还能进一步实现高维稳健学习问题的次线性时间算法。
Nov, 2018
针对模型类如何拟合标记数据的问题,我们提出了一种计算学习能力的方法,可以使用较小的数据量得出精确结果。该方法也适用于二元分类问题,并在多种真实和合成数据集上得到了验证。
May, 2018
本文提出了一种在数据为超收缩分布、存在不可避免的敌对噪声情况下,基于平方和框架的线性模型学习算法,该算法的收敛速度与扰动的比例成幂率关系,能达到理论最优收敛速度且在先前研究中未被发现。
Jun, 2020