About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
SODA 2015
Conference paper
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.