Geometric median and robust estimation in Banach spaces

By Stanislav Minsker. 2013

355 citations recorded by the source corpus.

In many real-world applications, collected data are contaminated by noise with heavy-tailed distribution and might contain outliers of large magnitude. In this situation, it is necessary to apply methods which produce reliable outcomes even if the input contains corrupted measurements. We describe a general method which allows one to obtain estimators with tight concentration around the true parameter of interest taking values in a Banach space. Suggested construction relies on the fact that the geometric median of a collection of independent "weakly concentrated" estimators satisfies a much stronger deviation bound than each individual element in the collection. Our approach is illustrated through several examples, including sparse linear regression and low-rank matrix recovery problems.

Subfields: Computational Mechanics, Statistics and Probability, Mathematical Optimization

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Statistics and Probability

In Mathematical Optimization

Citations in the corpus

Robust Aggregation for Federated Learning (2019, methodology): “Robust median-of-means were introduced in [70], with follow ups in [39, 53, 60, 61, 67].”
DETOX: A Redundancy-based Framework for Faster and More Robust Gradient Aggregation (2019, methodology): “Using the proof techniques similar to [20], we get the following.”
Generalized Byzantine-tolerant SGD (2018, methodology): “We use the following lemma (Minsker et al., 2015; Cohen et al., 2016) without proof to bound the geometric median.”
Distributed Robust Learning (2014, background): “The following lemma, straightforwardly derived from Lemma 2.1 in [15], characterizes the robustness of the geometric median.”
Sub-Gaussian estimators of the mean of a random matrix with heavy-tailed entries (2016, background): “An approach which often yields “dimension - free” bounds was proposed in [HS16] and [Min15] (using generalizations of the median in higher dimensions); however, to the best of our knowledge, results of these papers are still not sufficient to obtain deviation guarantees in the operator norm that we ”
A Case Study Competition Among Methods for Analyzing Large Spatial Data (2017, background): “Metakriging relies upon the unique geometric median (GM) of the subset posteriors (Minsker et al. 2014; Minsker 2015).”
Robust machine learning by median-of-means: Theory and practice (2017, background): “…tractable estimator satisfying optimal subgaussian concentration bounds [25], the other estimators are either suboptimal see for example [71] for the estimation of the mean of a vector in R d or [18] for more general learning frameworks, or completely untractable see for example [61,…”
Loss Minimization and Parameter Estimation with Heavy Tails (2013, methodology): “Results marked with (⋆) are due to Minsker (2013). Equality indicates matching upper and lower bounds.”
Sub-Gaussian estimators of the mean of a random vector (2017, background): “…multivariate case by replacing the median by its natural multivariate extension, the so-called “ge-ometric (or spatial) median” (i.e., the point that minimizes the sum of the Euclidean distances to the sample means within each block) see Lerasle and Oliveira [14], Hsu and Sabato [9], Minsker [16].”
Risk minimization by median-of-means tournaments (2016, methodology): “Devroye, Lerasle, Lugosi, and Oliveira [14] Hsu and Sabato [18], Lerasle and Oliveira [27], Minsker [34], Audibert and Catoni [3].”
Robust estimation via robust gradient estimation (2018, methodology): “…properties of using Median-SDP to design the gradient estimator g.θ;Dn, δ/ in the on-line appendix O but, given the focus on practicality, we use the geometric median-of-means estimator Gmom, which was originally proposed and analysed by Minsker (2015), to design the gradient estimator g.θ;Dn, δ/.”
Defending Against Saddle Point Attack in Byzantine-Robust Distributed Learning (2018, methodology): “The coordinatewise median aggregation subroutine that we consider is related to the median-of-means estimator [52, 31], which has been applied to various robust inference problems [51, 47, 50].”
Efficient and Robust Median-of-Means Algorithms for Location and Regression (2016, methodology): “It is similar to Theorem 3.1 in [15].”