Robust Means under Heavy Tails — Examples

Given: Countable Choice and the five block means $0,0,0,0,M$ with $M>0$. Countable Choice is a prerequisite of the minimum-norm selector used by Geometric median of block means, through Measurable minimum-norm geometric-median selection.

A geometric median minimizes the sum of distances to the listed block means (Geometric median of block means).

With inner product $⟨x,y⟩=xy$, $\mathbb{R}$ is a real inner-product space: ordered-field arithmetic gives bilinearity, symmetry, and $x^2\ge 0$ with equality only for $x=0$ (The reals form a totally ordered field, Real and complex inner-product spaces and their induced length). Its induced norm is $\sqrt{x^2}=\mathrm{\mid }x\mathrm{\mid }$ (Square roots exist: a unique $\sqrt{a}\ge 0$ with $(\sqrt{a}{)}^2=a$; the positives are $\{x^2:x\mathrm{\ne }0\}$, Basic properties of the absolute value), so completeness of the real line makes it a Hilbert space (The reals are complete, Hilbert space). The embedded rationals are countable and dense, so this Hilbert space is separable ($\mathbb{Q}$ is countably infinite, The rationals embed densely in the reals, Separability: the existence of an at most countable dense subset).

Given: A sample size $2N$ and a replacement fraction $1\mathrm{/}2\le \eta \le 1$.

Under sample replacement, an adversary may change at most $\lfloor 2\eta N\rfloor$ coordinates of a clean iid sample; the observed vector need not be iid (Adversarial sample replacement).

Huber contamination instead makes each observed coordinate iid from $(1-\eta )P+\eta Q$, which is a different model from a data-dependent joint replacement coupling (Huber contamination model).

Given: Countable Choice, the density $f(x)=3\mathrm{/}(2(1+\mathrm{\mid }x\mathrm{\mid }{)}^4)$, and the definitions of sub-Gaussianity and variance. Fix $0<\delta <1$ and a positive integer $n$ for which $k=\lfloor \log (1\mathrm{/}\delta )\mathrm{/}\psi (7\mathrm{/}18;1\mathrm{/}10)\rfloor +1\le n\mathrm{/}2$, with $\psi$ as defined in Finite-variance Hilbert mean bound for geometric medians of means. Let $X_1,\dots ,X_n$ be iid Borel real-valued observations with this density, and let $\widehat{\mu }$ be their geometric-median-of-block-means output using $k$ blocks and the minimum-norm selection rule specified by that theorem. Countable Choice is an explicit hypothesis of Finite-variance Hilbert mean bound for geometric medians of means, whose selector uses Measurable minimum-norm geometric-median selection.

A centered real random variable is sub-Gaussian with proxy $s^2$ only if $E{e}^{\lambda X}\le e^{{\lambda }^2{s}^2\mathrm{/}2}$ for every real $\lambda$ (Sub-Gaussian variables and vectors, and sub-exponential variables).

For the density displayed in the Example, symmetry and finite second moment identify the mean and variance; the geometric-median theorem requires a separable Hilbert-valued iid sample with finite second moment (Finite-variance Hilbert mean bound for geometric medians of means).

With inner product $⟨x,y⟩=xy$, $\mathbb{R}$ is a real inner-product space: ordered-field arithmetic gives bilinearity, symmetry, and $x^2\ge 0$ with equality only for $x=0$ (The reals form a totally ordered field, Real and complex inner-product spaces and their induced length). Its induced norm is $\sqrt{x^2}=\mathrm{\mid }x\mathrm{\mid }$ (Square roots exist: a unique $\sqrt{a}\ge 0$ with $(\sqrt{a}{)}^2=a$; the positives are $\{x^2:x\mathrm{\ne }0\}$, Basic properties of the absolute value), so completeness of the real line makes it a Hilbert space (The reals are complete, Hilbert space). The embedded rationals are countable and dense, so this Hilbert space is separable ($\mathbb{Q}$ is countably infinite, The rationals embed densely in the reals, Separability: the existence of an at most countable dense subset).