Sketching for M -Estimators: A Unified Approach to Robust Regression
Kenneth L. Clarkson, David P. Woodruff · 2014
We give algorithms for the M-estimators minx ‖Ax — b‖G, where A ∊ ℝn×d and b ∊ ℝn, and ‖y‖G for y ∊ ℝn is specified by a cost function G: ℝ → ℝ≥0, with ‖y‖G ≡ ∑i G(yi). The M-estimators generalize ℓp regression, for which G(x) = We first show that the Huber measure can be computed up to relative error ε in O(nnz(A)log n + poly(d(log n)/ε)) time, where nnz(A) denotes the number of non-zero entries of the matrix A. Huber is arguably the most widely used M-estimator, enjoying the robustness properties of ℓ1 as well as the smoothness properties of ℓ2. We next develop algorithms for general M-estimators. We analyze the M-sketch, which is a variation of a sketch introduced by Verbin and Zhang in the context of estimating the earthmover distance. We show that the M-sketch can be used much more generally for sketching any M- estimator provided G has growth that is at least linear and at most quadratic. Using the M-sketch we solve the M-estimation problem in O(nnz(A) + poly(d log n)) time for any such G that is convex, making a single pass over the matrix and finding a solution whose residual error is within a constant factor of optimal, with high probability.