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

Jul, 2020

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

Optimal Robust Linear Regression in Nearly Linear Time

Yeshwanth Cherapanamjeri, Efe Aras, Nilesh Tripuraneni, Michael I. Jordan, Nicolas Flammarion...

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

Abstract

We study the problem of high-dimensional robust linear regression where a learner is given access to $n$ samples from the generative model $Y = \langle X,w^* \rangle + \epsilon$ (with $X \in \mathbb{R}^d$ and $\epsilon$ independent), in which an $\eta$ fraction of the samples have been

high-dimensional robust linear regression adversarial corruption estimators sample complexities runtimes

发现论文，激发创造

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

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

May, 2018

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

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

Nov, 2018

高斯分布中具有 Huber 污染的近最优算法：均值估计与线性回归

我们研究了在存在 Huber 污染时，高斯均值估计和具有高斯协变量的线性回归的基本问题。我们的主要贡献是设计出了第一个样本近优且几乎具有线性时间算法，其具有最佳的误差保证，可以解决这两个问题。

Dec, 2023

当没有预警的异常值压倒时的连贯回归

研究了具有重尾噪声分布的健壮线性回归模型，提出了 Huber 损失估计器，证明其在样本量近线性和异常值分数倒数多项式情况下具有一致性。

Sep, 2020

鲁棒线性回归：多项式时间内的最优速率

本文提出了一种在数据为超收缩分布、存在不可避免的敌对噪声情况下，基于平方和框架的线性模型学习算法，该算法的收敛速度与扰动的比例成幂率关系，能达到理论最优收敛速度且在先前研究中未被发现。

Jun, 2020

对异常数据鲁棒的回归的高效算法

本文首次给出了一个多项式时间算法，用于在示例和标签中对抗性堕落下执行线性或多项式回归，并基于 SoS 方法提出了一种自然的凸松弛方法来解决非凸优化问题。

Mar, 2018

使用亚高斯率的光谱算法进行稳健回归

本论文研究线性回归问题并提出了一种新的算法，它能够在存在离群值的情况下，对有限矩（至 $L_4$）的样本进行最佳的次高斯误差边界估计，并且通过使用谱方法研究了线性回归问题与最远超平面问题之间的关系，同时引入了第三个经验过程进行统计学属性的研究。

Jul, 2020

鲁棒线性最小二乘回归

针对在普通最小二乘法回归中预测的偏差问题，我们提出了一个更好的估算方法 —— 基于截断误差差值的极小 - 极大框架，其期望和差距都为 d/n。

Oct, 2010

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

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

Apr, 2017

在亚线性数据范围内估计可学习性

针对模型类如何拟合标记数据的问题，我们提出了一种计算学习能力的方法，可以使用较小的数据量得出精确结果。该方法也适用于二元分类问题，并在多种真实和合成数据集上得到了验证。

May, 2018