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
ICML 2019
Conference paper
Dimensionality reduction for Tukey regression
Abstract
We give the first dimensionality reduction methods for the overconstrained Tukey regression problem. The Tukey loss function ||y||M = Σi M(yi) has M(yi) ≈ |yi|p for residual errors yi smaller than a prescribed threshold τ, but M(yi) becomes constant for errors |yi| > τ. Our results depend on a new structural result, proven constructively, showing that for any d-dimensional sub-space L ⊆ℝn, there is a fixed bounded-size subset of coordinates containing, for every y ∈ L, all the large coordinates, with respect to the Tukey loss function, of y. Our methods reduce a given Tukey regression problem to a smaller weighted version, whose solution is a provably good approximate solution to the original problem. Our reductions are fast, simple and easy to implement, and we give empirical results demonstrating their practicality, using existing heuristic solvers for the small versions. We also give exponential-time algorithms giving provably good solutions, and hardness results suggesting that a significant speedup in the worst case is unlikely.