Consider a regression problem where the learner is given a large collection
of $d$-dimensional data points, but can only query a small subset of the
real-valued labels. How many queries are needed to obtain a $1+\epsilon$
relative error approximation of the optimum? While this problem has been
extensively studied for least squares regression, little is known for other
losses. An important example is least absolute deviation regression ($\ell_1$
regression) which enjoys superior robustness to outliers compared to least
squares. We develop a new framework for analyzing importance sampling methods
in regression problems, which enables us to show that the query complexity of
least absolute deviation regression is $\Theta(d/\epsilon^2)$ up to logarithmic
factors. We further extend our techniques to show the first bounds on the query
complexity for any $\ell_p$ loss with $p\in(1,2)$. As a key novelty in our
analysis, we introduce the notion of robust uniform convergence, which is a new
approximation guarantee for the empirical loss. While it is inspired by uniform
convergence in statistical learning, our approach additionally incorporates a
correction term to avoid unnecessary variance due to outliers. This can be
viewed as a new connection between statistical learning theory and variance
reduction techniques in stochastic optimization, which should be of independent
interest.

本文提出了一个新框架来分析回归问题中的重要抽样方法，证明了最小绝对偏差回归的查询复杂度为 $\Theta (d/\epsilon^2)$，并拓展了技术来展示任何 $ \ell_p$ 损失（$p\in (1,2)$）的查询复杂度的第一个下界以及引入了鲁棒均匀收敛的概念，建立了统计学习理论和随机优化中方差降低技术之间的新联系。

通过鲁棒均匀收敛研究最小绝对偏差回归的查询复杂度

Query Complexity of Least Absolute Deviation Regression via Robust  Uniform Convergence

Many of the ordinal regression models that have been proposed in the
literature can be seen as methods that minimize a convex surrogate of the
zero-one, absolute, or squared loss functions. A key property that allows to
study the statistical implications of such approximations is that of Fisher
consistency. Fisher consistency is a desirable property for surrogate loss
functions and implies that in the population setting, i.e., if the probability
distribution that generates the data were available, then optimization of the
surrogate would yield the best possible model. In this paper we will
characterize the Fisher consistency of a rich family of surrogate loss
functions used in the context of ordinal regression, including support vector
ordinal regression, ORBoosting and least absolute deviation. We will see that,
for a family of surrogate loss functions that subsumes support vector ordinal
regression and ORBoosting, consistency can be fully characterized by the
derivative of a real-valued function at zero, as happens for convex
margin-based surrogates in binary classification. We also derive excess risk
bounds for a surrogate of the absolute error that generalize existing risk
bounds for binary classification. Finally, our analysis suggests a novel
surrogate of the squared error loss. We compare this novel surrogate with
competing approaches on 9 different datasets. Our method shows to be highly
competitive in practice, outperforming the least squares loss on 7 out of 9
datasets.

通过特征函数的导数在 0 处的刻画，给一类替代性损失函数提供 Fisher Consistency 特性的证明。