Abstract

Although the MapReduce framework is now the de 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, e.g., the regression problem: given a matrix and a vector , find a vector that minimizes The widely-used regression, i.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 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 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.