We study robust linear regression in high-dimension, when both the dimension
$d$ and the number of data points $n$ diverge with a fixed ratio $\alpha=n/d$,
and study a data model that includes outliers. We provide exact asymptotics for
the performances of the empirical risk minimisation (ERM) using
$\ell_2$-regularised $\ell_2$, $\ell_1$, and Huber loss, which are the standard
approach to such problems. We focus on two metrics for the performance: the
generalisation error to similar datasets with outliers, and the estimation
error of the original, unpolluted function. Our results are compared with the
information theoretic Bayes-optimal estimation bound. For the generalization
error, we find that optimally-regularised ERM is asymptotically consistent in
the large sample complexity limit if one perform a simple calibration, and
compute the rates of convergence. For the estimation error however, we show
that due to a norm calibration mismatch, the consistency of the estimator
requires an oracle estimate of the optimal norm, or the presence of a
cross-validation set not corrupted by the outliers. We examine in detail how
performance depends on the loss function and on the degree of outlier
corruption in the training set and identify a region of parameters where the
optimal performance of the Huber loss is identical to that of the $\ell_2$
loss, offering insights into the use cases of different loss functions.

本文研究高维度的鲁棒线性回归，包括离群值和使用标准损失函数的经验风险最小化（ERMs）方法。结果显示，在相似数据集上，经过最优正则化的 ERM 在大样本复杂性极限下是渐近一致的，但在评估误差方面，由于规范标定的失配，估计器的一致性要求完美计算最优规范的预估值或存在未受离群值污染的交叉验证集。不同的损失函数在最优性能的使用情况下提供了有关使用情况的见解。

在存在异常值的情况下，鲁棒性经验风险最小化性能的渐近特征

Asymptotic Characterisation of Robust Empirical Risk Minimisation  Performance in the Presence of Outliers

We consider the robust linear regression problem in the online setting where
we have access to the data in a streaming manner, one data point after the
other. More specifically, for a true parameter $\theta^*$, we consider the
corrupted Gaussian linear model $y = \langle x , \ \theta^* \rangle +
\varepsilon + b$ where the adversarial noise $b$ can take any value with
probability $\eta$ and equals zero otherwise. We consider this adversary to be
oblivious (i.e., $b$ independent of the data) since this is the only
contamination model under which consistency is possible. Current algorithms
rely on having the whole data at hand in order to identify and remove the
outliers. In contrast, we show in this work that stochastic gradient descent on
the $\ell_1$ loss converges to the true parameter vector at a $\tilde{O}( 1 /
(1 - \eta)^2 n )$ rate which is independent of the values of the contaminated
measurements. Our proof relies on the elegant smoothing of the non-smooth
$\ell_1$ loss by the Gaussian data and a classical non-asymptotic analysis of
Polyak-Ruppert averaged SGD. In addition, we provide experimental evidence of
the efficiency of this simple and highly scalable algorithm.

本文研究了在线情况下健壮线性回归问题，提出了一种基于随机梯度下降方法和 L1 损失函数的高效算法，能够在存在污染数据情况下有效检测和去除异常值，算法复杂度与污染比例相关。

基于 SGD 的 l1 损失在线鲁棒回归

Online Robust Regression via SGD on the l1 loss

We study the problem of robust linear regression with response variable
corruptions. We consider the oblivious adversary model, where the adversary
corrupts a fraction of the responses in complete ignorance of the data. We
provide a nearly linear time estimator which consistently estimates the true
regression vector, even with $1-o(1)$ fraction of corruptions. Existing results
in this setting either don't guarantee consistent estimates or can only handle
a small fraction of corruptions. We also extend our estimator to robust sparse
linear regression and show that similar guarantees hold in this setting.
Finally, we apply our estimator to the problem of linear regression with
heavy-tailed noise and show that our estimator consistently estimates the
regression vector even when the noise has unbounded variance (e.g., Cauchy
distribution), for which most existing results don't even apply. Our estimator
is based on a novel variant of outlier removal via hard thresholding in which
the threshold is chosen adaptively and crucially relies on randomness to escape
bad fixed points of the non-convex hard thresholding operation.

通过使用硬阈值化的新颖变体，本文提出了一种快速的鲁棒估计器，可以有效地解决使用响应变量损坏的鲁棒线性回归问题，并通过应用于不同的扰动模型，展示了其估计能力的稳健性。