The Gaussian Hare and the Laplacian Tortoise: Computability of Squared- Error versus Absolute-Error Estimators

@article{citeulike:2918684, abstract = {Since the time of Gauss, it has been generally accepted that \$\ell\_2\$-methods of combining observations by minimizing sums of squared errors have significant computational advantages over earlier \$\ell\_1\$-methods based on minimization of absolute errors advocated by Boscovich, Laplace and others. However, \$\ell\_1\$-methods are known to have significant robustness advantages over \$\ell\_2\$-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 \$\ell\_1\$-type problems, we obtain a 10- to 100-fold improvement in computational speeds over current (simplex-based) \$\ell\_1\$-algorithms in large problems, demonstrating that \$\ell\_1\$-methods can be made competitive with \$\ell\_2\$-methods in terms of computational speed throughout the entire range of problem sizes. Formal complexity results suggest that \$\ell\_1\$-regression can be made faster than least-squares regression for \$n\$ sufficiently large and \$p\$ modest.}, author = {Portnoy, Stephen and Koenker, Roger }, citeulike-article-id = {2918684}, doi = {10.2307/2246216}, journal = {Statistical Science}, keywords = {least-squares, lp}, number = {4}, pages = {279--296}, posted-at = {2008-06-23 13:06:40}, priority = {2}, publisher = {Institute of Mathematical Statistics}, title = {The Gaussian Hare and the Laplacian Tortoise: Computability of Squared- Error versus Absolute-Error Estimators}, url = {http://dx.doi.org/10.2307/2246216}, volume = {12}, year = {1997} }

TY - JOUR ID - citeulike:2918684 L3 - citeulike-article-id:2918684 TI - The Gaussian Hare and the Laplacian Tortoise: Computability of Squared- Error versus Absolute-Error Estimators JF - Statistical Science VL - 12 IS - 4 SP - 279 EP - 296 PB - Institute of Mathematical Statistics N2 - Since the time of Gauss, it has been generally accepted that $\ell_2$-methods of combining observations by minimizing sums of squared errors have significant computational advantages over earlier $\ell_1$-methods based on minimization of absolute errors advocated by Boscovich, Laplace and others. However, $\ell_1$-methods are known to have significant robustness advantages over $\ell_2$-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 $\ell_1$-type problems, we obtain a 10- to 100-fold improvement in computational speeds over current (simplex-based) $\ell_1$-algorithms in large problems, demonstrating that $\ell_1$-methods can be made competitive with $\ell_2$-methods in terms of computational speed throughout the entire range of problem sizes. Formal complexity results suggest that $\ell_1$-regression can be made faster than least-squares regression for $n$ sufficiently large and $p$ modest. KW - least-squares KW - lp AU - Portnoy, Stephen AU - Koenker, Roger PY - 1997/// UR - http://dx.doi.org/10.2307/2246216 ER -