The Gaussian hare and the Laplacian tortoise: computability of squared-error versus absolute-error estimators
The Gaussian hare and the Laplacian tortoise: computability of squared-error versus absolute-error estimators
复制标题
DOI：
10.1214/ss/1030037960
复制
发表时间：
1997-11
影响因子：
5.7
通讯作者：
S. Portnoy;R. Koenker
中科院分区：
文献类型：
--
作者：
S. Portnoy;R. Koenker
自高斯时代以来，人们普遍认为？通过最小化误差平方和来组合观测值的方法比以前的方法具有显著的计算优势。1 . Boscovich、Laplace等人提倡的基于绝对误差最小化的方法。然而,?众所周知，在许多应用中，1-方法比2-方法具有显著的鲁棒性优势，相关的分位数回归方法为统计模型的经典最小二乘估计提供了一种有用的补充方法。将求解线性规划的内点法的最新进展与新的统计预处理方法相结合。1类型的问题，我们获得了10到100倍的计算速度比目前（基于simplex） ？大问题中的1个算法，证明这一点？就整个问题规模范围内的计算速度而言，1-方法可以与2-方法竞争。形式复杂性结果表明？当n足够大且p适中时，1-回归可以比最小二乘回归更快。
Since the time of Gauss, it has been generally accepted that ?2-methods of combining observations by minimizing sums of squared errors have significant computational advantages over earlier ?1-methods based on minimization of absolute errors advocated by Boscovich, Laplace and others. However, ?1-methods are known to have significant robustness advantages over f2-methods in many applications, and related quantile regression methods provide a useful, complementary approach to classical least-squares estimation of statistical models. Combining recent advances in interior point methods for solving linear programs with a new statistical preprocessing approach for ?1-type problems, we obtain a 10to 100-fold improvement in computational speeds over current (simplex-based) ?1-algorithms in large problems, demonstrating that ?1-methods can be made competitive with f2-methods in terms of computational speed throughout the entire range of problem sizes. Formal complexity results suggest that ?1-regression can be made faster than least-squares regression for n sufficiently large and p modest.