Robust Sparsification via Sensitivity

Robustness to outliers is important in machine learning. Many classical problems, including subspace embedding, clustering, and low-rank approximation, lack scalable, outlier-resilient algorithms. This paper considers machine learning problems of the form min x∈R d F (x), where F (x) = n i=1 F i (x), and their robust counterparts min x∈R d F (m) (x), where F (m) (x) denotes the sum of all but the m largest F i (x) values. We develop a general framework for constructing ε-coresets for such robust problems, where an ε-coreset is a weighted subset of functions F 1 (x), . . . , F n (x) that provides a (1 + ε)approximation to F (x). Specifically, if the original problem F has total sensitivity T and admits a vanilla ε-coreset of size S, our algorithm constructs an ε-coreset of size Õ( mT ε ) + S for the robust objective F (m) . This coreset size can be shown to be near-tight for ℓ 2 subspace embeddings. Our coreset algorithm has scalable running time and, by employing a sensitivity flattening argument, leads to new or improved algorithms for robust optimization problems, including regression and PCA. Finally, empirical evaluations demonstrate that our coresets outperform uniform sampling on real-world data sets.