Robust Regression on MapReduce

Abstract

Although the MapReduce framework is now the \emphde facto standard for analyzing massive data sets, many algorithms (in particular, many iterative algorithms popular in machine learning, optimization, and linear algebra) are hard to fit into MapReduce. Consider, \emphe.g., the \ell_p regression problem: given a matrix A ∈\mathbb{R}^m \times n and a vector b ∈\mathbb{R}^m, find a vector x^* ∈\mathbb{R}^n that minimizes f(x) = \|A x - b\|_p. The widely-used \ell_2 regression, \emphi.e., linear least-squares, is known to be highly sensitive to outliers; and choosing p ∈[1, 2) can help improve robustness. In this work, we propose an efficient algorithm for solving strongly over-determined (m ≫n) robust \ell_p regression problems to moderate precision on MapReduce. Our empirical results on data up to the terabyte scale demonstrate that our algorithm is a significant improvement over traditional iterative algorithms on MapReduce for \ell_1 regression, even for a fairly small number of iterations. In addition, our proposed interior-point cutting-plane method can also be extended to solving more general convex problems on MapReduce.