Finite-variance Hilbert mean bound for geometric medians of means

The map $X_1$ is strongly measurable: by [F13], fix a countable dense sequence $(h_j)$ in $H$ and approximate each $x\in H$ by the nearest of $h_1,\dots ,h_m$, breaking finite ties by the least index. The cells defining these finite-valued simple Borel maps are Borel because they are finite intersections of strict or weak comparisons of continuous distance functions, and the maps converge pointwise to $x$. Since $\mathrm{\parallel }{X}_1\mathrm{\parallel }\le 1+\mathrm{\parallel }{X}_1{\mathrm{\parallel }}^2$, $E\mathrm{\parallel }{X}_1\mathrm{\parallel }<\mathrm{\infty }$, so [F1] defines $\mu =E_B{X}_1$.

If the geometric median is farther than $C_a{r}_0$ from $\mu$, [F9] forces more than $ak$ bad block means. For $W$ the number of bad blocks, independence and $P(\text{bad block }j)\le p$ give $E{e}^{\lambda W}\le (1-p+p{e}^{\lambda }{)}^k$ for $\lambda >0$. Markov's inequality with $\lambda =\log (a(1-p)\mathrm{/}(p(1-a)))>0$ gives $P(W\ge ak)\le e^{-k\psi (a;p)}<\delta$, after substituting this $\lambda$ and simplifying.

For the rank-one operator $x\otimes y$, [F10] gives $\mathrm{\parallel }x\otimes y\mathrm{\parallel }\le \mathrm{\parallel }x\mathrm{\parallel }\mathrm{\parallel }y\mathrm{\parallel }$, with equality by testing $y\mathrm{/}\mathrm{\parallel }y\mathrm{\parallel }$ when $y\mathrm{\ne }0$; its only possible nonzero singular value is this operator norm, so $\mathrm{\parallel }x\otimes y{\mathrm{\parallel }}_1=\mathrm{\parallel }x\mathrm{\parallel }\mathrm{\parallel }y\mathrm{\parallel }$. Apply the rank-one map to the finite-valued simple approximants from step 1.1: the resulting $S_1(H)$-valued functions are simple and converge pointwise in trace norm, because $\mathrm{\parallel }u\otimes u-v\otimes v{\mathrm{\parallel }}_1\le (\mathrm{\parallel }u\mathrm{\parallel }+\mathrm{\parallel }v\mathrm{\parallel })\mathrm{\parallel }u-v\mathrm{\parallel }$. Hence $(X_1-\mu )\otimes (X_1-\mu )$ is strongly measurable; its trace norm is $\mathrm{\parallel }{X}_1-\mu {\mathrm{\parallel }}^2$, which is integrable since $E\mathrm{\parallel }{X}_1-\mu {\mathrm{\parallel }}^2\le 2E\mathrm{\parallel }{X}_1{\mathrm{\parallel }}^2+2\mathrm{\parallel }\mu {\mathrm{\parallel }}^2$. The Bochner integrability criterion gives its Bochner expectation $\mathrm{\Sigma }$ in $S_1(H)$. The bounded trace functional commutes with this integral by [F3], and [F2] gives $\mathrm{tr}\mathrm{\Sigma }=E\mathrm{\parallel }{X}_1-\mu {\mathrm{\parallel }}^2=V$. For $h,g\in H$, bounded evaluation maps commute with the integral and give $⟨\mathrm{\Sigma }h,g⟩=E[⟨h,X_1-\mu ⟩⟨X_1-\mu ,g⟩]$; this is symmetric in $h,g$ and is nonnegative when $h=g$. If $V=0$, [F11] gives $X_1=\mu$ almost surely. Identical distribution and a finite union of null events imply that all $X_i=\mu$ simultaneously almost surely; hence every block mean is $\mu$. The objective in [F12] is then $k\mathrm{\parallel }z-\mu \mathrm{\parallel }$, uniquely minimized at $\mu$, so $\widehat{\mu }=\mu$ almost surely. Thus the strict-tail event in the Statement is empty when its threshold is zero. Assume $V>0$ below.

Let $m_j^{\circ }$ be a block size. For centered $Y_i=X_i-\mu$, expand $E\mathrm{\parallel }{\sum }_{i\in B_j}{Y}_i{\mathrm{\parallel }}^2$ into diagonal and cross terms. Each diagonal term is $V$; for $i\mathrm{\ne }l$, product-law independence [F4] and scalar Fubini [F6] give $E⟨Y_i,Y_l⟩=\int \text{\hspace{0.17em}⁣}\int ⟨x,y⟩d{P}_Y(x)d{P}_Y(y)=0$. The integrand is integrable because [F10] gives $\mathrm{\mid }⟨x,y⟩\mathrm{\mid }\le \mathrm{\parallel }x\mathrm{\parallel }\mathrm{\parallel }y\mathrm{\parallel }$ and $E\mathrm{\parallel }{Y}_i\mathrm{\parallel }<\mathrm{\infty }$; the inner integral is zero by [F3] and $E_B{Y}_l=0$. Dividing by $(m_j^{\circ }{)}^2$ yields $E\mathrm{\parallel }{m}_j-\mu {\mathrm{\parallel }}^2=V\mathrm{/}{m}_j^{\circ }$.

Since $k\le n\mathrm{/}2$, every block has size at least $\lfloor n\mathrm{/}k\rfloor \ge n\mathrm{/}(2k)$. Put $r_0=\sqrt{2kV\mathrm{/}(pn)}$. By [F5] and step 3.1, $P(\mathrm{\parallel }{m}_j-\mu \mathrm{\parallel }>r_0)\le p$ for each block. The block means are independent by [F4], and [F12] makes their geometric-median aggregate a Borel random element.

The same Chernoff calculation as step 1.2 applies to every $q<a$. For each sufficiently large integer $s$, use radius $(1-1\mathrm{/}s)r_0$ in step 4.1, so the bad-block probability is at most $p_s=p\mathrm{/}(1-1\mathrm{/}s{)}^2<a$. The event $\{\mathrm{\parallel }\widehat{\mu }-\mu \mathrm{\parallel }\ge C_a{r}_0\}$ is contained in the corresponding strict-radius event, whose probability is at most $e^{-k\psi (a;p_s)}$. Let $s\to \mathrm{\infty }$; continuity gives $e^{-k\psi (a;p)}<\delta$.

For $a=7\mathrm{/}18$ and $p=1\mathrm{/}10$, $C_a=(1-a)\mathrm{/}\sqrt{1-2a}$; applying [L1] with $M=50$ and $t=-13\mathrm{/}68,13\mathrm{/}22,1\mathrm{/}6$ gives $2915\mathrm{/}10000<\psi (a;p)<2916\mathrm{/}10000$ and $3364\mathrm{/}10000<\log (7\mathrm{/}5)$. Hence $5\mathrm{/}18<\psi (a;p)<\log (7\mathrm{/}5)$ and $C_a\sqrt{2\mathrm{/}(p\psi (a;p))}\le 11$. From $k=\lfloor \log (1\mathrm{/}\delta )\mathrm{/}\psi (a;p)\rfloor +1$ we have $k\psi (a;p)\le \log (1\mathrm{/}\delta )+\psi (a;p)<\log (7\mathrm{/}(5\delta ))$. Step 4.1 therefore gives the asserted nonstrict-tail bound for $V>0$ after replacing $r_0$ by its expression; the strict-tail event is a subset, so its bound follows as well. When $V=0$, exact recovery in step 2.1 gives the strict-tail bound. No nonstrict-tail assertion at zero threshold is made.