Sketchy Polytopes

Geometric Median & Robust Estimation

Stanislav Minsker addresses the following question:

Problem: Given X1,…,Xk that are i.i.d. random variables, how can we estimate the mean of the distribution so that the confidence interval still has a coverage probability ≥1−O(e−t)? Note: the smaller the confidence interval, the better the estimator.

  1. Assuming the variables from normal distribution N(μ,σ2). If the estimator is constructed as ˆμn=ΣiXi/n, then:
Pr(|μn−ˆμn|≥σ√2t/n)≤e−t

For non-normal distribution, the confidence interval is much different:

Pr(|μn−ˆμn|≥σ√et/n)≤e−t

Since the length of this interval depends on et, can we do better?

  1. If we split the sample into k=floor(t)+1 groups G1,…,Gk each of size approximate fracnt, then median-of-means estimator has the following confidence interval (result due to Nemirovskii and Yudin, 1983):
ˆμn,k=median(ˆμ1,...,ˆμk)
Pr(‖μn−ˆμn‖≥σC√tn)≤e−t

Where C is a constant. The length of confidence interval for median-of-means is much smaller than for the naive mean estimator.

  1. Minsker’s work extends this to multi-dimensional distributions in Banach space using geometric median to obtain confidence intervals of sub-exponential length with high coverage.

More in the paper here. See also, Fermat-Weber problem.

geometric_proof