Sketching for M-estimators: A unified approach to robust regression

Abstract

We give algorithms for the M-estimators mimx ∥Ax-g-info∥G, where A ∈ ℝnxd and b ∈ℝn, and ∥y∥G for y ∈ ℝn is specified by a cost function G: ℝ → ℝ ≥0, with ∥y∥G=σiG (yi)-The M-estimators generalize ℓp regression, for which G (x)=|x|p. We first show that the Huber measure can be computed up to relative error ∈ in O (imz (A) logn + poly (d (1ogn)/∈)) time, where aaz (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 ℓ as well as the smoothness properties of ℓ. 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 (aaz (A) + poly (dlogn)) 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.