Sharper Concentration Inequalities for Median-of-Mean Processes

Abstract

The Median-of-Mean (MoM) estimation is an efficient statistical method for handling data with contamination. In this paper, we propose a variance-dependent MoM estimation method using the tail probability of a binomial distribution. The bound of this method is better than the classical Hoeffding method under mild conditions. This method is then used to study the concentration of variance-dependent MoM empirical processes and sub-Gaussian intrinsic moment norm. Finally, we give the bound of the variance-dependent MoM estimator with distribution-free contaminated data.

1. Introduction

Nowadays, there is a huge amount of data in information processing, and the data are varied. With the rapid expansion of data volume, traditional centralized data processing has gradually become unable to adapt to the current needs, which makes it possible to distribute processing power to all computers on the network.

When dealing with large amounts of data, it is inevitable to produce contaminated data which we generally call outliers. The outliers will result in low accuracy or high sensitivity of data processing tasks. Naturally, inferring probability density functions from contaminated samples is an important problem. Correspondingly, when there are no outliers in a dataset, we call such a dataset sane.

The Median-of-Mean (MoM) method is an effective way to deal with contaminated data, which divides the original data into several blocks, calculates the mean for each block, and then takes the median of these means. The literature on MoM methods can be traced back to Ref. [1]. In recent years, MoM methods have been widely used in the field of machine learning. For example, Ref. [2] used the MoM method to design estimators for kernel mean embedding and maximum mean discrepancy with excessive resistance properties to outliers; Ref. [3] applied the MoM method to achieve the optimal trade-off between accuracy and confidence under minimal assumptions in the classical statistical learning/regression problem; Ref. [4] introduced an MoM method for robust machine learning without deteriorating the estimation properties of a given estimator which is also easily computable in practice; Ref. [5] introduced a robust nonparametric density estimator combining the popular Kernel Density Estimation method and the Median-of-Means principle.

When using MoM methods to deal with contaminated data, these data often do not have obvious normal distribution characteristics but have more extensive sub-Gaussian properties; thus, non-asymptotic techniques are needed. Non-asymptotic inference can give full play to its advantages in the case of finite samples. Especially in the field of machine learning, non-asymptotic inference can establish strict error boundaries for the desired learning program (see Refs. [6,7,8]). Sometimes when working with data, it is difficult to know the exact distribution; this calls for a more general study such as sub-Gaussian, sub-exponential, heavy-tailed, and bounded distributions. For example, Ref. [9] studied the non-asymptotic concentration of the heteroskedastic Wishart-type matrices; Ref. [10] constructed sub-Gaussian estimators of a mean vector under adversarial contamination and heavy-tailed data by Median-of-Mean versions of the Stahel–Donoho outlyingness and of Median Absolute Deviation functions; Ref. [11] obtained the deconvolution for some singular density errors via a combinatorial Median-of-Mean approach and assessed the estimator quality by establishing non-asymptotic risk bounds.

To obtain a clear picture of robust estimation from a non-asymptotic viewpoint, variance-dependent MoM methods based on binomial tail probability are mainly studied, including uncontaminated and contaminated cases. The paper proceeds as follows. We first provide a variance-dependent MoM-estimator bias inequality by using bounds on binomial tails with unbounded samples, whose bias bound is tighter than the classical Hoeffding’s bound (see Section 2). Then, by the variance-dependent MoM inequality, we obtain the generalization bound via entropic complexity (see Section 3.1) and the non-asymptotic property via Sub-Gaussian intrinsic moment norm (see Section 3.2). Finally, the variance-dependent MoM inequality with contamination data is illustrated in Section 4.

2. Variance-Dependent Median-of-Mean Estimator without Outliers

The MoM method was originally introduced on page 242 of Ref. [1]; it reinforces the effect of the empirical mean on the heavy-tail distribution while inheriting its efficiency on the light-tail distribution. The MoM estimator is derived as follows.

Without loss of generality, suppose that the sample data $X_1,X_2,\dots ,X_n$ are decomposed into K blocks, with each block including B observations, that is to say, $n=KB$. We first compute the mean of each block, which leads to estimators ${\widehat{\mu }}_1,\cdots ,{\widehat{\mu }}_K$ and each estimator is based on B observations. Then, the MoM estimator is given by the median of all these estimators, i.e.,

$$\begin{array}{c}\hfill {\mathrm{MoM}}_K\left[\mu \right]=median\left({\widehat{\mu }}_1,\cdots ,{\widehat{\mu }}_K\right).\end{array}$$

It turns out that, even with a very mild condition $Var\left(X\right)={\sigma }^2<\infty$, the MoM estimator has a nice concentration inequality under finite sample case.

Given the i.i.d. sample $X_1,X_2,\dots ,X_n$ with mean ${\mu }_0$ and finite variance ${\sigma }^2$, using Hoeffding’s inequality, Proposition 1 in Ref. [12] produces the following concentration inequality:

$$\mathbb{P}\left(\left|{\mathrm{MoM}}_K\left[\mu \right]-{\mu }_0\right|>t\right)\le exp\left(-\frac{n{t}^2}{27{\sigma }^2}\right)$$

where $t=\sigma \sqrt{(2+\delta )/B}\ge \sigma \sqrt{\frac{2\sqrt{\pi }-\sqrt{2}}{B}}$—see detailed description in Remark 1.

When additional conditions are applied to the distribution under consideration, stricter boundaries can be obtained, such as our results on binomial tails (Theorem 1), which can be better.

In fact, sometimes we need to block the data, but the minimum number of samples per block is often a concern, because it involves efficiency and robustness issues, and, from a statistical point of view, the effect of variance is taken into account. The following theorem takes into account the partitioning of variance effects and yields the variance-dependent MoM inequality.

Theorem 1. 

Given the i.i.d. samples $X_1,X_2,\dots ,X_n$ with mean ${\mu }_0$ and finite variance ${\sigma }^2$, for $\forall \delta \ge \frac{\sqrt{2}}{\sqrt{\pi }-\sqrt{2}}$, there exists $B\in \mathbb{N}$ and $\epsilon >0$, such that $B{\epsilon }^2\ge (2+\delta ){\sigma }^2$. Then, the MoM estimator has the following concentration inequality:

$$\mathbb{P}\left(\left|{\mathrm{MoM}}_K\left[\mu \right]-{\mu }_0\right|>t\right)\le exp\left(-\frac{0.0976n{t}^2}{{\sigma }^2}\right)$$

(1)

where $t=\sigma \sqrt{(2+\delta )/B}.$

A powerful feature of Theorem 1 is that $X_i$s can be unbounded in this case. In addition, finite sample exponential concentration is not easy to obtain if only variance exists (see Ref. [13]). And Theorem 1 provides the basis for further obtaining the inequality with outliers. In the process of proving the theorem, we used the following lemma.

Lemma 1 

(Theorem 1 of [14]). Suppose $S_n\sim Bin(n,p),a>p\in (0,1)$, and $1⩽an⩽n-1.$ If $an\in \mathbb{N}$, then

$$\begin{array}{c}\hfill \mathbb{P}\left(S_n⩾an\right)⩽\frac{1}{1-r}\frac{1}{\sqrt{2\pi a(1-a)n}}{e}^{-nD(a\parallel p)}.\end{array}$$

where $r=r(a,p):=\frac{p(1-a)}{a(1-p)}$, and $D(a\parallel p):=alog\frac{a}{p}+(1-a)log\frac{1-a}{1-p}$ is the KL divergence between Bernoulli distributions with parameters a and p. If an $\notin \mathbb{N}$, the bound still holds, but it can be tightened by replacing a with $a^{*}:=\lceil an\rceil /n$.

Now, we give a detailed proof of Theorem 1.

Proof of Theorem 1. 

First, observe that the event

$$\begin{array}{c}\hfill \left\{\left|{\mathrm{MoM}}_K\left[\mu \right]-{\mu }_0\right|>ϵ\right\}\mathrm{for}\forall ϵ\ge 0\end{array}$$

implies that at least $K/2$ of ${\widehat{\mu }}_{\ell }(\ell =1,\dots ,K)$ has to be outside $ϵ$ distance to ${\mu }_0$ for $\forall ϵ\ge 0$. Namely,

$$\begin{array}{c}\hfill \left\{\left|{\mathrm{MoM}}_K\left[\mu \right]-{\mu }_0\right|>ϵ\right\}\subset \left\{\sum _{\ell =1}^K\mathbf{1}\left(\left|{\widehat{\mu }}_{\ell }-{\mu }_0\right|>ϵ\right)\ge \frac{K}{2}\right\}\mathrm{for}\forall ϵ\ge 0.\end{array}$$

Here, it is assumed that K is an even number. When K is an odd number, take at least $\lceil K/2\rceil$, and the same can be said. For the convenience of writing, the following process of proof only writes the case of at least $K/2$, while proving the case of $\lceil K/2\rceil$ is no difference.

Define $Z_{\ell }=\mathbf{1}\left(\left|{\widehat{\mu }}_{\ell }-{\mu }_0\right|>ϵ\right)$ and let $\overline{p}:={\tilde{p}}_{ϵ,B}=\mathbb{E}\left(Z_{\ell }\right)=\mathbb{P}\left(\left|{\widehat{\mu }}_{\ell }-{\mu }_0\right|>ϵ\right)$. Note the theorem condition and the Chebyshev’s inequality (see p. 239 in Ref. [15]), which imply that there exits $B\in \mathbb{N}$ and $\epsilon >0$ such that

$$\tilde{p}:={\tilde{p}}_{\epsilon ,B}=\mathbb{P}\left(\left|{\widehat{\mu }}_{\ell }-{\mu }_0\right|>\epsilon \right)\le \frac{{\sigma }^2}{B{\epsilon }^2}<\frac{1}{2}.$$

(2)

In fact, the detailed derivation process is as follows:

$$\begin{array}{cc}\hfill \mathbb{P}\left(\left|{\widehat{\mu }}_{\ell }-{\mu }_0\right|>\epsilon \right)& \le \frac{\mathrm{Var}\left({\widehat{\mu }}_{\ell }\right)}{{\epsilon }^2}\hfill \\ & =\frac{\mathrm{Var}\left(\frac{X_{l1}+\cdots +X_{lB}}{B}\right)}{{\epsilon }^2}\hfill \\ & =\frac{\frac{1}{B^2}\mathrm{Var}\left({\sum }_{i=1}^B{X}_{li}\right)}{{\epsilon }^2}\hfill \\ & =\frac{\frac{1}{B^2}{\sum }_{i=1}^B\mathrm{Var}\left(X_{li}\right)}{{\epsilon }^2}\hfill \\ & =\frac{\frac{1}{B^2}B{\sigma }^2}{{\epsilon }^2}\hfill \\ & =\frac{{\sigma }^2}{B{\epsilon }^2}.\hfill \end{array}$$

The random variables $Z_{\ell }\sim \mathrm{Bernoulli}\left(\tilde{p}\right)$ are i.i.d. because of the i.i.d. samples $X_1,X_2,\cdots ,X_n$. Applying Lemma 1 (with $a=1/2$, $n=K$, and $p=\tilde{p}$ in Lemma 1) to the summations gives

$$\begin{array}{c}\hfill \mathbb{P}\left(\left|{\mathrm{MoM}}_K\left[\mu \right]-{\mu }_0\right|>\epsilon \right)\le \mathbb{P}\left(\sum _{\ell =1}^K{Z}_{\ell }\ge \frac{K}{2}\right)\le \frac{1-\tilde{p}}{1-2\tilde{p}}\sqrt{\frac{2}{\pi K}}{e}^{-KD\left(\frac{1}{2}\left|\right|\tilde{p}\right)},\end{array}$$

where $D\left(\frac{1}{2}\left|\right|\tilde{p}\right)=\frac{1}{2}log\left(\frac{1}{4\tilde{p}(1-\tilde{p})}\right)$.

Setting $B\ge (2+\delta ){\sigma }^2/{\epsilon }^2>2{\sigma }^2/{\epsilon }^2$ for $\forall \delta >0$ satisfies Equation (2); then,

$$\begin{array}{cc}\hfill \mathbb{P}\left(\left|{\mathrm{MoM}}_K\left[\mu \right]-{\mu }_0\right|>\sigma \sqrt{\frac{(2+\delta )K}{n}}\right)& \le \frac{1-\tilde{p}}{1-2\tilde{p}}\sqrt{\frac{2}{\pi K}}{e}^{-KD\left(\frac{1}{2}\left|\right|\tilde{p}\right)}\hfill \\ \hfill & =\left(1+\frac{\tilde{p}}{1-2\tilde{p}}\right)\sqrt{\frac{2}{\pi K}}{e}^{-KD\left(\frac{1}{2}\left|\right|\tilde{p}\right)}\hfill \\ \hfill & \le \frac{\delta +1}{\delta }\sqrt{\frac{2}{\pi K}}{\left(1+\frac{{\delta }^2}{4+4\delta }\right)}^{-\frac{K}{2}}\hfill \end{array}$$

When $K=1$, we set $\delta \ge \frac{\sqrt{2}}{\sqrt{\pi }-\sqrt{2}}\approx 3.95$ so that $\frac{\delta +1}{\delta }\sqrt{\frac{2}{\pi K}}\le \frac{\delta +1}{\delta }\sqrt{\frac{2}{\pi }}\le 1(K=1,\cdots ,n)$. Then, it follows that

$$\begin{array}{c}\hfill \mathbb{P}\left(\left|{\mathrm{MoM}}_K\left[\mu \right]-{\mu }_0\right|>\sigma \sqrt{\frac{(2+\delta )K}{n}}\right)\le {\left(1+\frac{{\delta }^2}{4+4\delta }\right)}^{-\frac{K}{2}}\end{array}$$

for $1\le K\le n$ and $\delta \ge \sqrt{2}/(\sqrt{\pi }-\sqrt{2})$.

Now, taking $t:=\sigma \sqrt{(2+\delta )K/n}$ gives

$$\begin{array}{c}\hfill \mathbb{P}\left(\left|{\mathrm{MoM}}_K\left[\mu \right]-{\mu }_0\right|>t\right)\le exp\left(-\frac{n{t}^2}{2(2+\delta ){\sigma }^2}ln\left(1+\frac{{\delta }^2}{4+4\delta }\right)\right)\end{array}$$

The function $g\left(\delta \right)=-\frac{1}{2+\delta }ln\left(1+\frac{{\delta }^2}{4+4\delta }\right)(\delta \ge \frac{\sqrt{2}}{\sqrt{\pi }-\sqrt{2}})$ is a monotonically decreasing function, so its maximum is $g\left(\sqrt{2}/(\sqrt{\pi }-\sqrt{2})\right)\approx -0.0976$.

This then leads to the final result:

$$\begin{array}{c}\hfill \mathbb{P}\left(\left|{\mathrm{MoM}}_K\left[\mu \right]-{\mu }_0\right|>t\right)\le exp\left(-\frac{0.0976n{t}^2}{{\sigma }^2}\right).\end{array}$$

□

Remark 1. 

The classical result by Hoeffding inequality shows that (see Proposition 1 in Ref. [12])

$$\begin{array}{c}\hfill \mathbb{P}\left(\left|{\mathrm{MoM}}_K\left[\mu \right]-{\mu }_0\right|>\sigma \sqrt{(2+\delta )K/n}\right)\le e^{-K\frac{{\delta }^2}{2{(2+\delta )}^2}}\end{array}$$

Similarily, to obtain a sharp constant, one can consider $t:=\sigma \sqrt{(2+\delta )K/n}$; then,

$$\begin{array}{c}\hfill \mathbb{P}\left(\left|{\mathrm{MoM}}_K\left[\mu \right]-{\mu }_0\right|>t\right)\le exp\left(-\frac{n{t}^2{\delta }^2}{2{\sigma }^2{(2+\delta )}^3}\right)\end{array}$$

and the function

$$\begin{array}{c}\hfill g\left(\delta \right)=\frac{{\delta }^2}{{(2+\delta )}^3}\end{array}$$

achieve the unique maximum point at $\delta =4$ with $g\left(4\right)=2/27$. It follows that

$$\begin{array}{c}\hfill \mathbb{P}\left(\left|{\mathrm{MoM}}_K\left[\mu \right]-{\mu }_0\right|>t\right)\le exp\left(-\frac{n{t}^2}{27{\sigma }^2}\right).\end{array}$$

Remark 2. 

The efficient interval of t is an interesting issue. By the construction of $t=\sigma \sqrt{(2+\delta )K/n}$, it follows that $\sqrt{(2+\delta )/n}\le t/\sigma \le \sqrt{2+\delta }$ since $1\le K\le n$.

Remark 3. 

In Theorem 1, we substitute $t=\sigma \sqrt{(2+\delta )/B}$ into inequality (1) to produce

$$\mathbb{P}\left(\left|{\mathrm{MoM}}_K\left[\mu \right]-{\mu }_0\right|>\sigma \sqrt{\frac{2+\delta }{B}}\right)\le exp\left(-\frac{0.0976n{\sigma }^2(2+\delta )}{B{\sigma }^2}\right)$$

Since $\delta \ge \frac{\sqrt{2}}{\sqrt{\pi }-\sqrt{2}}\approx 3.95>2$, we have

$$\mathbb{P}\left(\left|{\mathrm{MoM}}_K\left[\mu \right]-{\mu }_0\right|>2\sigma \sqrt{\frac{K}{n}}\right)\le e^{-0.5807K}.$$

This result is better than the bound $e^{-K/8}$ of level-dependent sub-Gaussian estimators. Of course, our conditions are more stringent (see Proposition 12 in Ref. [16]).

3. Applications

In this section, we use the proposed sharper concentration inequalities for MoM estimators to perform two applications in statistical machine learning.

3.1. Concentration for Supremum of Variance-Dependent MoM Empirical Processes

Let $\psi \left(x\right)\in {\mathcal{B}}_L$ and $\left|\psi \left(x\right)\right|\le M_0<\infty$, where ${\mathcal{B}}_L$ is a ball of the Lipschitz functions space and $M_0$ is a constant. Let $\mathrm{P}\psi =\mathbb{E}\psi =\int \psi dP$.

To derive the concentration inequality for the supremum of variance-dependent MoM empirical processes, the following auxiliary Lemma 2 is necessary, whose proof is trivial and thus omitted.

Lemma 2. 

$|med\left(a\right)-med\left(b\right)|\le {\parallel a-b\parallel }_{\infty }$ for $a,b\in B_{\mathcal{L}}$ where $med\left(a\right)$ means the value of the function $a\left(x\right)$ at the midpoint of the domain, and the same is true for $med\left(b\right)$.

By Lemma 2, for $\forall \varphi \in {\mathcal{B}}_L$, we have

$$\begin{array}{cc}\hfill \left|{MoM}_K\left[\varphi \right]-\mathrm{P}\varphi \right|& \le \left|{MoM}_K\left[\varphi \right]-{MoM}_K\left[\psi \right]\right|+\left|\mathrm{P}(\varphi -\psi )\right|+\left|{MoM}_K\left[\psi \right]-\mathrm{P}\psi \right|\hfill \\ \hfill & \le {\parallel \varphi -\psi \parallel }_{\infty }+{\parallel \varphi -\psi \parallel }_{\infty }+\left|{MoM}_K\left[\psi \right]-\mathrm{P}\psi \right|\hfill \\ \hfill & ={2\parallel \varphi -\psi \parallel }_{\infty }+\left|{MoM}_K\left[\psi \right]-\mathrm{P}\psi \right|\hfill \end{array}$$

(3)

Let ${\psi }_1,\cdots ,{\psi }_{\mathcal{N}\left(\xi ,{\mathcal{B}}_L,{\parallel ·\parallel }_{\infty }\right)}$ be a $\xi$-covering of ${\mathcal{B}}_L$ w.r.t. ${\parallel ·\parallel }_{\infty }$. It is well-known that there exist constants $C_L>0$ and $r\ge 1$, such that

$$log\left(\mathcal{N}\left(\xi ,{\mathcal{B}}_L,{\parallel ·\parallel }_{\infty }\right)\right)\le C_L{\left(\frac{1}{\xi }\right)}^r,\forall \xi >0$$

(4)

where $\mathcal{N}\left(\xi ,{\mathcal{B}}_L,{\parallel ·\parallel }_{\infty }\right)$ denotes the number of ${\parallel ·\parallel }_{\infty }$-balls of radius $\xi >0$ needed to cover class ${\mathcal{B}}_L$, and $C_L$ is a universal constant depending only on ${\mathcal{B}}_L$.

Put $\mathcal{N}=\mathcal{N}\left(\xi ,{\mathcal{B}}_L,{\parallel ·\parallel }_{\infty }\right)$ for simplicity. By definition of $\mathcal{N}$, for $\forall i\in \{1,\cdots ,\mathcal{N}\}$, s.t.

$${∥\varphi -{\psi }_i∥}_{\infty }\le \xi$$

Then, (3) becomes

$$\left|{MoM}_K\left[\varphi \right]-\mathrm{P}\varphi \right|\le 2\tilde{\xi }+\left|{MoM}_K\left[{\psi }_i\right]-\mathrm{P}{\psi }_i\right|$$

(5)

Then, by Theorem 1, the union bound for ${\left\{{\psi }_i\right\}}_{i=1}^{\mathcal{N}}$ gives that

$$\mathbb{P}\left(\underset{1\le i\le \mathcal{N}}{max}\left|{MoM}_K\left[{\psi }_i\right]-\mathrm{P}{\psi }_i\right|\le \sigma \sqrt{\frac{-ln\delta }{0.0976\mathcal{N}}}\right)\ge 1-\delta .$$

(6)

Together, (4)–(6) give

$$\mathbb{P}\left(\underset{\varphi \in {\mathcal{B}}_L}{sup}\left|{MoM}_K\left[\varphi \right]-\mathrm{P}\varphi \right|\le 2\xi +\sigma \sqrt{\frac{-ln\delta }{0.0976\mathcal{N}}}\right)\ge 1-\delta .$$

Put $\xi =\sqrt{\frac{C_L}{\mathcal{N}\xi }}$, i.e., $\xi ={\left(\frac{C_L}{\mathcal{N}}\right)}^{\frac{1}{r+2}}$; then, for $\forall \varphi \in {\mathcal{B}}_L$ and $\delta \in (0,1)$, we have

$$\mathbb{P}\left(\underset{\varphi \in {\mathcal{B}}_L}{sup}\left|{MoM}_K\left[\varphi \right]-\mathrm{P}\varphi \right|\le 2{\left(\frac{C_L}{\mathcal{N}}\right)}^{\frac{1}{r+2}}+\sigma \sqrt{\frac{-ln\delta }{0.0976\mathcal{N}}}\right)\ge 1-\delta .$$

3.2. Concentration for Variance-Dependent MoM Intrinsic Moment Norm

A centered random variable X is called sub-Gaussian if

$$\mathrm{E}{e}^{sX}\le e^{s^2{\sigma }_G^2/2}\mathrm{for}\forall s\in \mathbb{R},$$

where the quantity ${\sigma }_G>0$ is named as the sub-Gaussian parameter. In non-asymptotic statistics, because the collected sub-Gaussian data is often unstable, sometimes it is not possible to directly use the empirical moment-generating function to estimate the sub-Gaussian parameter such as variance-type parameters of sub-Gaussian distributions (see Ref. [17]). This requires us to use the sub-Gaussian intrinsic moment norm for estimation. The definition of intrinsic moment norm is as follows.

Definition 1 

(Intrinsic moment norm, see Definition 2 in Ref. [17]). The sub-Gaussian intrinsic moment norm is defined as

$${\parallel X\parallel }_G:=\underset{k\ge 1}{max}{\left[\frac{2^{k}k!}{\left(2k\right)!}\mathrm{E}{X}^{2k}\right]}^{1/\left(2k\right)}=\underset{k\ge 1}{max}{\left[\frac{1}{(2k-1)!!}\mathrm{E}{X}^{2k}\right]}^{1/\left(2k\right)},$$

where $n!!={\prod }_{j=0}^{\left[\frac{n}{2}\right]-1}(n-2j)=n(n-2)(n-4)\cdots$ for $n\in \mathbb{N}$.

As the amount of computation increases, so does the importance of the distributed MoM approach, with the corresponding intrinsic moment norm estimator defined below.

Definition 2 

(see Equation (7) in Ref. [17]). Let $\left[K\right]=\{1,\cdots ,K\}$ and $B_s$ be the number of samples in the s-th block. The MOM estimator for sub-Gaussian intrinsic moment norm is given by

$${\widehat{\parallel X\parallel }}_{b,G}:=\underset{1\le k\le {\kappa }_n}{max}\underset{s\in \left[K\right]}{median}\left\{{\left[{\left[(2k-1)!!\right]}^{-1}{\mathrm{P}}_B^{B_s}{X}^{2k}\right]}^{1/\left(2k\right)}\right\}$$

where ${\mathrm{P}}_B^{B_s}X=B^{-1}{\sum }_{i\in B_s}{X}_i(s=1,\cdots ,K)$.

Definition 3. 

For any $B\in \mathbb{N}$ and $1\le k\le {\kappa }_n$,

$${\overline{g}}_{k,B}\left({\sigma }_k\right):=1-{\left[E{X}^{2k}/(2k-1)!!\right]}^{-\frac{1}{2k}}\underset{1\le j\le {\kappa }_n}{max}{\left[-2B^{-\frac{1}{2}}{\sigma }_j^j/(E{X}^{2j})+E{X}^{2j}/(2j-1)!!\right]}^{\frac{1}{2j}}$$

and ${\underline{g}}_{k,B}\left({\sigma }_k\right):={\left[2B^{-1/2}{\sigma }_k^k/(E{X}^{2k})+1\right]}^{1/\left(2k\right)}-1$.

Theorem 2. 

Suppose, for $\forall \epsilon >0$ and $\forall n\in \mathbb{N}$, there exits $B\in \mathbb{N}$, such that $\sqrt{\mathrm{Var}{X}^{2k}}<\epsilon \sqrt{B/2}\le {\sigma }_k^k$ where ${\left\{{\sigma }_k\right\}}_{k=1}^{{\kappa }_n}$ is a finite constant sequence. Then, we have

$$\mathbb{P}\left\{{\parallel X\parallel }_G\le {\left[1-\underset{1\le k\le {\kappa }_n}{max}{\overline{g}}_{k,B}\left({\sigma }_k\right)\right]}^{-1}{\widehat{\parallel X\parallel }}_{b,G}\right\}>1-{\kappa }_n{e}^{-0.3904K}$$

and

$$\mathbb{P}\left\{{\parallel X\parallel }_G>{\left[1+\underset{1\le k\le {\kappa }_n}{max}{\underline{g}}_{k,B}\left({\sigma }_k\right)\right]}^{-1}{\widehat{\parallel X\parallel }}_{b,G}\right\}>1-{\kappa }_n{e}^{-0.3904K}.$$

Remark 4. 

Let $K=n/B$; we then obtain distributed samples that satisfy Theorem 2.

Remark 5. 

The key coefficient $-0.3904<-0.125$. In fact, the key coefficient of Theorem 3 in Ref. [17] without outliers is −0.125, as long as $\eta \left(\epsilon \right)=1$ is taken. This means that our boundary is better than the boundary in Ref. [17].

Proof of Theorem 2. 

From Definitions 1 and 2, we have

$${\parallel X\parallel }_G=\underset{1\le k\le {\kappa }_n}{max}{\left[\frac{\mathrm{E}{X}^{2k}}{(2k-1)!!}\right]}^{1/\left(2k\right)}$$

(7)

and

$${\widehat{\parallel X\parallel }}_{b,G}=\underset{1\le k\le {\kappa }_n}{max}{median}_{s\in \left[K\right]}\left\{{\left[\frac{1}{(2k-1)!!}·{\mathrm{P}}_B^{B_s}{X}^{2k}\right]}^{1/\left(2k\right)}\right\}.$$

(8)

Recall that ${\underline{g}}_{k,B}\left({\sigma }_k\right)$ and ${\overline{g}}_{k,B}\left({\sigma }_k\right)$ are the sequences s.t.

$$\begin{array}{cc}\hfill & {\left[\mathrm{E}{X}^{2k}/(2k-1)!!\right]}^{1/\left(2k\right)}\left(1-{\overline{g}}_{k,B}\left({\sigma }_k\right)\right)\hfill \\ \hfill & =\underset{1\le k\le {\kappa }_n}{max}{\left[-2B^{-1/2}{\sigma }_k^k/\left(\mathrm{E}{X}^{2k}\right)+\mathrm{E}{X}^{2k}/(2k-1)!!\right]}^{1/\left(2k\right)}\hfill \end{array}$$

(9)

and

$${\left[2B^{-1/2}{\sigma }_k^k/\left(\mathrm{E}{X}^{2k}\right)+1\right]}^{1/\left(2k\right)}=1+{\underline{g}}_{k,B}\left({\sigma }_k\right)$$

(10)

for any $B\in \mathbb{N}$ and $1\le k\le {\kappa }_n$.

For the first inequality of Theorem 2, we have, by (7),

$$\begin{array}{cc}& \mathbb{P}\left\{{\widehat{\parallel X\parallel }}_{b,G}\le \left[1-\underset{1\le k\le {\kappa }_n}{max}{\overline{g}}_{k,B}\left({\sigma }_k\right)\right]{\parallel X\parallel }_G\right\}\hfill \\ & =\mathbb{P}\left\{{\widehat{\parallel X\parallel }}_{b,G}\le \underset{1\le k\le {\kappa }_n}{max}{\left[\frac{\mathrm{E}{X}^{2k}}{(2k-1)!!}\right]}^{1/\left(2k\right)}\left(1-\underset{1\le k\le {\kappa }_n}{max}{\overline{g}}_{k,B}\left({\sigma }_k\right)\right)\right\}\hfill \\ & \le \mathbb{P}\left\{{\widehat{\parallel X\parallel }}_{b,G}\le \underset{1\le k\le {\kappa }_n}{max}{\left[\frac{\mathrm{E}{X}^{2k}}{(2k-1)!!}\right]}^{1/\left(2k\right)}\left(1-{\overline{g}}_{k,B}\left({\sigma }_k\right)\right)\right\}\hfill \\ \hfill [\mathrm{By}(9\left)\right]& =\mathbb{P}\left\{\widehat{\parallel X}{\parallel }_{b,G}\le {\left[-\frac{{\sigma }_k^k}{(2k-1)!!}·\frac{2}{B^{1/2}}+\frac{\mathrm{E}{X}^{2k}}{(2k-1)!!}\right]}^{1/\left(2k\right)}\right\}\hfill \\ & \le \sum _{k=1}^{{\kappa }_n}\mathbb{P}\{{median}_{s\in \left[K\right]}\left\{{\left[\frac{1}{(2k-1)!!}·{\mathrm{P}}_B^{B_s}{X}^{2k}\right]}^{1/\left(2k\right)}\right\}\le \hfill \\ & {\left[-\frac{{\sigma }_k^k}{(2k-1)!!}·\frac{2}{B^{1/2}}+\frac{\mathrm{E}{X}^{2k}}{(2k-1)!!}\right]}^{1/\left(2k\right)}\}\hfill \\ & =\sum _{k=1}^{{\kappa }_n}\mathbb{P}\{{median}_{s\in \left[K\right]}\left\{\frac{1}{(2k-1)!!}·{\mathrm{P}}_B^{B_s}{X}^{2k}\right\}\le \hfill \\ & \frac{\mathrm{E}{X}^{2k}}{(2k-1)!!}-\frac{{\sigma }_k^k}{(2k-1)!!}·\frac{2}{B^{1/2}}\}\hfill \\ & =\sum _{k=1}^{{\kappa }_n}\mathbb{P}\{{median}_{s\in \left[K\right]}\left\{\frac{1}{(2k-1)!!}·\left[{\mathrm{P}}_B^{B_s}{X}^{2k}-\mathrm{E}{X}^{2k}\right]\right\}\le \hfill \\ & -\frac{{\sigma }_k^k}{(2k-1)!!}·\frac{2}{B^{1/2}}\}\hfill \\ & <\sum _{k=1}^{{\kappa }_n}\mathbb{P}\left\{\left|{median}_{s\in \left[K\right]}\left\{{\mathrm{P}}_B^{B_s}\left[X^{2k}-{\mathrm{E}}^{2k}\right]\right\}\right|\ge {\sigma }_k^k·\frac{2}{B^{1/2}}\right\}\hfill \\ & \le {\kappa }_n{e}^{-0.3904K},\hfill \end{array}$$

where the last inequality is by Theorem 1 and the assumption in Theorem 2.

Let ${\underline{g}}_B\left(\sigma \right):={max}_{1\le k\le {\kappa }_n}{\underline{g}}_{k,B}\left({\sigma }_k\right)$. For the second inequality of Theorem 2, the definition of ${\underline{g}}_{k,B}\left({\sigma }_k\right)$ implies

$$\begin{array}{cc}& \mathbb{P}\left\{{\parallel X\parallel }_G\le \frac{{\widehat{\parallel X\parallel }}_{b,G}}{1+{\underline{g}}_B\left(\sigma \right)}\right\}\hfill \\ & =\mathbb{P}\left\{{\widehat{\parallel X\parallel }}_{b,G}\ge \underset{1\le k\le {\kappa }_n}{max}{\left[\frac{{\sigma }_k^k}{(2k-1)!!}·\frac{2}{B^{1/2}}+\frac{\mathrm{E}{X}^{2k}}{(2k-1)!!}\right]}^{1/\left(2k\right)}\right\}\hfill \\ & \le \mathbb{P}\{\underset{1\le k\le {\kappa }_n}{max}{median}_{s\in \left[K\right]}\left\{{\left[\frac{1}{(2k-1)!!}·{\mathrm{P}}_B^{B_s}{X}^{2k}\right]}^{1/\left(2k\right)}\right\}\ge \hfill \\ & {\left[\frac{{\sigma }_k^k}{(2k-1)!!}·\frac{2}{B^{1/2}}+\frac{\mathrm{E}{X}^{2k}}{(2k-1)!!}\right]}^{1/\left(2k\right)}\}\hfill \\ & \le \sum _{k=1}^{{\kappa }_n}\mathbb{P}\{{median}_{s\in \left[K\right]}\left\{{\left[\frac{1}{(2k-1)!!}·{\mathrm{P}}_B^{B_s}{X}^{2k}\right]}^{1/\left(2k\right)}\right\}\ge \hfill \end{array}$$

$$\begin{array}{cc}& {\left[\frac{{\sigma }_k^k}{(2k-1)!!}·\frac{2}{B^{1/2}}+\frac{\mathrm{E}{X}^{2k}}{(2k-1)!!}\right]}^{1/\left(2k\right)}\}\hfill \\ & =\sum _{k=1}^{{\kappa }_n}\mathbb{P}\left\{{median}_{s\in \left[K\right]}\left\{\frac{1}{(2k-1)!!}·{\mathrm{P}}_B^{B_s}{X}^{2k}\right\}\ge \left[\frac{{\sigma }_k^k}{(2k-1)!!}·\frac{2}{B^{1/2}}+\frac{\mathrm{E}{X}^{2k}}{(2k-1)!!}\right]\right\}\hfill \\ & =\sum _{k=1}^{{\kappa }_n}\mathbb{P}\left\{{median}_{s\in \left[K\right]}\left\{{\mathrm{P}}_B^{B_s}{X}^{2k}\right\}\ge \left[\frac{2{\sigma }_k^k}{B^{1/2}}+\mathrm{E}{X}^{2k}\right]\right\}\hfill \\ & =\sum _{k=1}^{{\kappa }_n}\mathbb{P}\left\{{median}_{s\in \left[K\right]}\left\{{\mathrm{P}}_B^{B_s}\left[X^{2k}-\mathrm{E}{X}^{2k}\right]\right\}\ge \frac{2{\sigma }_k^k}{B^{1/2}}\right\}\hfill \\ & <\sum _{k=1}^{{\kappa }_n}\mathbb{P}\left\{\left|{median}_{s\in \left[K\right]}\left\{{\mathrm{P}}_B^{B_s}\left[X^{2k}-\mathrm{E}{X}^{2k}\right]\right\}\right|\ge \frac{2{\sigma }_k^k}{B^{1/2}}\right\}\hfill \\ & \le {\kappa }_n{e}^{-0.3904K},\hfill \end{array}$$

where the last inequality is by Theorem 1 and the assumption in Theorem 2. □

4. Concentration for Variance-Dependent MoM with Distribution-Free Outliers

In the field of big data and artificial intelligence, most work involves dealing with abnormal data. Sometimes we cannot find each outlier directly, but we can obtain a rough idea of the total number of outliers. For example, sometimes there may be abnormal economic activities in a certain region, but the specific company or person who is abnormal may not be known for the time being; however, the total number of companies and the total population in the region are still known.

Based on such information, how to accurately estimate the characteristics of all samples containing outliers is an important problem. In this section, we introduce the concept of variance-dependent MoM estimator with outliers as the following theorem.

Theorem 3. 

Suppose that

(H.1) Sample $\left[n\right]=\{X_1,X_2,\dots ,X_n\}$ contains $n-n_{\mathcal{O}}$ i.i.d. inliers with finite mean ${\mu }_0$ and finite variance ${\sigma }^2$. And $n_{\mathcal{O}}$ outliers, upon which no assumption is made.

(H.2) Set $K=K_{\mathcal{O}}+K_{\mathcal{S}}$, where $K_{\mathcal{O}}$ is the number of blocks containing at least one outlier and $K_{\mathcal{S}}$ is the number of sane blocks containing no outlier. For $\forall t>0$, there exists a function $\eta \left({\epsilon }_{\mathcal{O}}\right)\in (1/2,1)$, such that $K\ge max\left(2,⌈\frac{1}{2\eta \left({\epsilon }_{\mathcal{O}}\right)-1}⌉,⌈\frac{(2\eta \left({\epsilon }_{\mathcal{O}}\right)-1)n{t}^2}{2\eta \left({\epsilon }_{\mathcal{O}}\right){\sigma }^2}⌉\right)$ and $K_{\mathcal{S}}\ge \eta \left({\epsilon }_{\mathcal{O}}\right)K$, where ${\epsilon }_{\mathcal{O}}:=n_{\mathcal{O}}/n$.

Then, for $\forall t>0$, we have

$$\begin{array}{cc}& \mathbb{P}\left\{\left|{\mathrm{MoM}}_K\left[\mu \right]-{\mu }_0\right|\le t\right\}\hfill \\ & \ge 1-exp\left(-\left(\frac{(2\eta \left({\epsilon }_{\mathcal{O}}\right)-1)n{t}^2}{2\eta \left({\epsilon }_{\mathcal{O}}\right){\sigma }^2}-1\right)\frac{2\eta \left({\epsilon }_{\mathcal{O}}\right)-1}{2\eta \left({\epsilon }_{\mathcal{O}}\right)}log\frac{(2\eta \left({\epsilon }_{\mathcal{O}}\right)-1)}{2\eta \left({\epsilon }_{\mathcal{O}}\right)}\right).\hfill \end{array}$$

Remark 6. 

For the number $n_{\mathcal{O}}$ and $K_{\mathcal{O}}$, when one divides n samples evenly into K blocks, an extreme case is to assume that the blocks that do not conform to one’s preferences are full of outliers, such as $K_{\mathcal{O}}$ blocks, and the blocks that conform to one’s preferences have no outliers, such as $K_{\mathcal{S}}$ blocks; then, one has ${\epsilon }_{\mathcal{O}}=n_{\mathcal{O}}/n=K_{\mathcal{O}}/K$.

Remark 7. 

For the function $\eta \left({\epsilon }_{\mathcal{O}}\right)$, we can write a concrete expression to show that such a function exists, for example, $\eta \left({\epsilon }_{\mathcal{O}}\right)=(1+2{\epsilon }_{\mathcal{O}})/2\in (1/2,1)$, where ${\epsilon }_{\mathcal{O}}\in (0,1/2)$. But there must be more than one expression, so the non-concrete function $\eta \left({\epsilon }_{\mathcal{O}}\right)$ is more appropriate for this theorem.

In fact, there is an adaptive way to generate block number K, but we do not show the specific calculation here; see Ref. [18] for more detail. Now, we give a detailed proof of Theorem 3.

Proof of Theorem 3. 

In the sane blocks, in the number of blocks whose sample mean is no more than t from the population mean ${\mu }_0$ is at least $K/2$, the distance between the population MoM and the population mean ${\mu }_0$ is no more than t, which is mathematically expressed as follows: for $\forall t>0$, we have

$$\begin{array}{cc}\hfill \left\{\left|{\mathrm{MoM}}_K\left[\mu \right]-{\mu }_0\right|\le t\right\}& \supset \left\{\sum _{i\in \left[K_{\mathcal{S}}\right]}{\mathbf{1}}_{\left\{\left|{\widehat{\mu }}_i-{\mu }_0\right|\le t\right\}}\ge \frac{K}{2}\right\}\hfill \\ & \supset \left\{\sum _{i\in \left[K_{\mathcal{S}}\right]}{\mathbf{1}}_{\left\{\left|{\widehat{\mu }}_i-{\mu }_0\right|\le t\right\}}\ge \frac{K_{\mathcal{S}}}{2\eta \left({\epsilon }_{\mathcal{O}}\right)}\right\}.\hfill \end{array}$$

Further, the following formula is established:

$$\mathbb{P}\left\{\left|{\mathrm{MoM}}_K\left[\mu \right]-{\mu }_0\right|\le t\right\}\ge \mathbb{P}\left\{\sum _{i\in \left[K_{\mathcal{S}}\right]}{\mathbf{1}}_{\left\{\left|{\widehat{\mu }}_i-{\mu }_0\right|\le t\right\}}\ge \frac{K_{\mathcal{S}}}{2\eta \left({\epsilon }_{\mathcal{O}}\right)}\right\}.$$

(11)

From the condition (H.4), we have $1\le \frac{K_{\mathcal{S}}}{2\eta \left({\epsilon }_{\mathcal{O}}\right)}\le K_{\mathcal{S}}-1$ and

$$K-1\ge K_{\mathcal{S}}\ge \eta \left({\epsilon }_{\mathcal{O}}\right)K\ge 2\eta \left({\epsilon }_{\mathcal{O}}\right)\ge 1+\frac{1}{K_{\mathcal{S}}-1}>1\mathrm{when}K\ge 2.$$

(12)

Applying Theorem 2 in Ref. [14], we can obtain the lower bound of Formula (11), i.e.,

$$\begin{array}{cc}\hfill & \mathbb{P}\left\{\sum _{i\in \left[K_{\mathcal{S}}\right]}{\mathbf{1}}_{\left\{\left|{\widehat{\mu }}_i-{\mu }_0\right|\le t\right\}}\ge \frac{K_{\mathcal{S}}}{2\eta \left({\epsilon }_{\mathcal{O}}\right)}\right\}\hfill \\ & \ge \frac{1-\frac{c}{K_{\mathcal{S}}}}{1-r}\eta \left({\epsilon }_{\mathcal{O}}\right)\sqrt{\frac{2}{\pi K_{\mathcal{S}}(2\eta \left({\epsilon }_{\mathcal{O}}\right)-1)}}{e}^{-K_{\mathcal{S}}D\left(\frac{1}{2\eta \left({\epsilon }_{\mathcal{O}}\right)}\left|\right|{\tilde{p}}_{\mathcal{S}}\right)}\hfill \end{array}$$

(13)

where $c=c\left(r\right)=\frac{4{\eta }^2\left({\epsilon }_{\mathcal{O}}\right)}{2\eta \left({\epsilon }_{\mathcal{O}}\right)-1}\left[1+\frac{r(1+r)}{{(1-r)}^2}\right]$, $r=r\left(\frac{1}{2\eta \left({\epsilon }_{\mathcal{O}}\right)},{\tilde{p}}_{\mathcal{S}}\right)=\frac{{\tilde{p}}_{\mathcal{S}}(2\eta \left({\epsilon }_{\mathcal{O}}\right)-1)}{1-{\tilde{p}}_{\mathcal{S}}}$ and

$$D\left(\frac{1}{2\eta \left({\epsilon }_{\mathcal{O}}\right)}\left|\right|{\tilde{p}}_{\mathcal{S}}\right)=\frac{1}{2\eta \left({\epsilon }_{\mathcal{O}}\right)}log\frac{1}{2\eta \left({\epsilon }_{\mathcal{O}}\right){\tilde{p}}_{\mathcal{S}}}+\frac{2\eta \left({\epsilon }_{\mathcal{O}}\right)-1}{2\eta \left({\epsilon }_{\mathcal{O}}\right)}log\frac{2\eta \left({\epsilon }_{\mathcal{O}}\right)-1}{2\eta \left({\epsilon }_{\mathcal{O}}\right)(1-{\tilde{p}}_{\mathcal{S}})}.$$

On the other hand, by Chebyshev’s inequality (see p. 239 in Ref. [15]), we have

$$1-\frac{1}{2\eta \left({\epsilon }_{\mathcal{O}}\right)}<1-{\tilde{p}}_{\mathcal{S}}=\mathbb{P}\left(\left|{\widehat{\mu }}_i-{\mu }_0\right|>t\right)\le \frac{{\sigma }^2}{B{t}^2}=\frac{K{\sigma }^2}{n{t}^2}\le 1\mathrm{for}\forall t>0(i=1,\cdots ,K_{\mathcal{S}}).$$

(14)

Thus, ${\tilde{p}}_{\mathcal{S}}\in [1-\frac{K{\sigma }^2}{n{t}^2},\frac{1}{2\eta \left({\epsilon }_{\mathcal{O}}\right)})$ and $r\in \left[\frac{(n{t}^2-K{\sigma }^2)(2\eta \left({\epsilon }_{\mathcal{O}}\right)-1)}{K{\sigma }^2},1\right)$. Because of $\eta \left({\epsilon }_{\mathcal{O}}\right)K\le K_{\mathcal{S}}\le K-1$ and $\eta \left({\epsilon }_{\mathcal{O}}\right)\in (1/2,1)$, the inequality (13) can be written as

$$\begin{array}{c}\hfill \mathbb{P}\left\{\sum _{i\in \left[K_{\mathcal{S}}\right]}{\mathbf{1}}_{\left\{\left|{\widehat{\mu }}_i-{\mu }_0\right|\le t\right\}}\ge \frac{K_{\mathcal{S}}}{2\eta \left({\epsilon }_{\mathcal{O}}\right)}\right\}\ge 1-e^{-K_{\mathcal{S}}D\left(\frac{1}{2\eta \left({\epsilon }_{\mathcal{O}}\right)}\left|\right|{\tilde{p}}_{\mathcal{S}}\right)}\ge 1-e^{-(K-1)D\left(\frac{1}{2\eta \left({\epsilon }_{\mathcal{O}}\right)}\left|\right|{\tilde{p}}_{\mathcal{S}}\right)}\end{array}$$

(15)

where

$$1+\frac{1-\frac{c}{K_{\mathcal{S}}}}{1-r}\eta \left({\epsilon }_{\mathcal{O}}\right)\sqrt{\frac{2}{\pi K_{\mathcal{S}}(2\eta \left({\epsilon }_{\mathcal{O}}\right)-1)}}\ge e^{K_{\mathcal{S}}D\left(\frac{1}{2\eta \left({\epsilon }_{\mathcal{O}}\right)}\left|\right|{\tilde{p}}_{\mathcal{S}}\right)}.$$

(16)

The inequality (16) can be valid, for example, if $\eta \left({\epsilon }_{\mathcal{O}}\right)$ is infinitely close to 1/2.

From ${\tilde{p}}_{\mathcal{S}}\in [1-\frac{K{\sigma }^2}{n{t}^2},\frac{1}{2\eta \left({\epsilon }_{\mathcal{O}}\right)})$, we have the minimum bound of $D\left(\frac{1}{2\eta \left({\epsilon }_{\mathcal{O}}\right)}\left|\right|{\tilde{p}}_{\mathcal{S}}\right)$, i.e.,

$$\begin{array}{cc}\hfill D\left(\frac{1}{2\eta \left({\epsilon }_{\mathcal{O}}\right)}\left|\right|{\tilde{p}}_{\mathcal{S}}\right)& >\frac{1}{2\eta \left({\epsilon }_{\mathcal{O}}\right)}log\frac{1}{2\eta \left({\epsilon }_{\mathcal{O}}\right)\frac{1}{2\eta \left({\epsilon }_{\mathcal{O}}\right)}}+\frac{2\eta \left({\epsilon }_{\mathcal{O}}\right)-1}{2\eta \left({\epsilon }_{\mathcal{O}}\right)}log\frac{2\eta \left({\epsilon }_{\mathcal{O}}\right)-1}{2\eta \left({\epsilon }_{\mathcal{O}}\right)(1-1+\frac{K{\sigma }^2}{n{t}^2})}\hfill \\ \hfill & =\frac{2\eta \left({\epsilon }_{\mathcal{O}}\right)-1}{2\eta \left({\epsilon }_{\mathcal{O}}\right)}log\frac{(2\eta \left({\epsilon }_{\mathcal{O}}\right)-1)n{t}^2}{2\eta \left({\epsilon }_{\mathcal{O}}\right)K{\sigma }^2}.\hfill \end{array}$$

(17)

Substituting Equation (17) into Equation (15), we have

$$\begin{array}{cc}\hfill & \mathbb{P}\left\{\sum _{i\in \left[K_{\mathcal{S}}\right]}{\mathbf{1}}_{\left\{\left|{\widehat{\mu }}_i-{\mu }_0\right|\le t\right\}}\ge \frac{K_{\mathcal{S}}}{2\eta \left({\epsilon }_{\mathcal{O}}\right)}\right\}\hfill \\ \hfill & >1-exp\left(-(K-1)\frac{2\eta \left({\epsilon }_{\mathcal{O}}\right)-1}{2\eta \left({\epsilon }_{\mathcal{O}}\right)}log\frac{(2\eta \left({\epsilon }_{\mathcal{O}}\right)-1)n{t}^2}{2\eta \left({\epsilon }_{\mathcal{O}}\right)K{\sigma }^2}\right)\hfill \end{array}$$

(18)

Further, due to Relation (14), we have $\frac{(2\eta \left({\epsilon }_{\mathcal{O}}\right)-1)n{t}^2}{2\eta \left({\epsilon }_{\mathcal{O}}\right){\sigma }^2}<K\le n$ and $\frac{K{\sigma }^2}{n{t}^2}\le 1$; then, the inequality (18) can be bounded as

$$\begin{array}{cc}& \mathbb{P}\left\{\sum _{i\in \left[K_{\mathcal{S}}\right]}{\mathbf{1}}_{\left\{\left|{\widehat{\mu }}_i-{\mu }_0\right|\le t\right\}}\ge \frac{K_{\mathcal{S}}}{2\eta \left({\epsilon }_{\mathcal{O}}\right)}\right\}\hfill \\ & >1-exp\left(-\left(\frac{(2\eta \left({\epsilon }_{\mathcal{O}}\right)-1)n{t}^2}{2\eta \left({\epsilon }_{\mathcal{O}}\right){\sigma }^2}-1\right)\frac{2\eta \left({\epsilon }_{\mathcal{O}}\right)-1}{2\eta \left({\epsilon }_{\mathcal{O}}\right)}log\frac{(2\eta \left({\epsilon }_{\mathcal{O}}\right)-1)}{2\eta \left({\epsilon }_{\mathcal{O}}\right)}\right)\hfill \end{array}$$

□

5. Conclusions

In this paper, we obtain the bounds of variance-dependen MoM estimation based on the binomial tail probability, including the case without pollution and the case with pollution. The nonasymptotic properties of nonpolluting MoM estimates have been shown to be superior to the existing traditional Hoeffding results. In the next step, we will also continue to investigate the bound of variance-dependen MoM estimation with outliers based on sub-Gaussian distribution or Weibull distribution. Compared with traditional exponential family distributions, it is more practical to study the inequalities of these distributions (see Refs. [19,20]). We further plan to study application problems with a practical background.