基于逆回归方法的分布式特征筛选

Distributed Feature Screening via Inverse Regression

摘要: 本文我们提出了一个通过逆回归估计实现大数据设置的分布式筛选框架。本着分而治之的思想，本文提出的框架可用分布估计条件方差的逆回归模型来表达相关关系。通过分量估计的聚合，我们得到了一个最终的逆条件方差估计，可以很容易地用于筛选特征。该框架支持分布式存储和并行计算，因此在计算上具有吸引力。由于分量参数的无偏分布估计，最终的聚合估计具有较高的精度，且对数据段数量m不敏感。在一般条件下，我们证明了聚合估计器在概率收敛界和均方误差率方面与集中估计器一样有效；相应的筛选过程对广泛的相关度量具有一定的筛选特性。

Abstract: In this paper, we propose a distributed screening framework for big data setup via inverse regression estimator. In the spirit of divide-and-conquer, the proposed framework expresses the dependent relative by inverse regression model in which can be distributively estimated inverse conditional variance. With the component estimates aggregated, we obtain a final inverse conditional variance estimator that can be readily used for screening features. This framework enables distributed storage and parallel computing and thus is computationally attractive. Due to the unbiased distributive estimation of the component parameters, the final aggregated estimate achieves a high accuracy that is insensitive to the number of data segments m. Under mild conditions, we show that the aggregated estimator is as efficient as the centralized estimator in terms of the probability convergence bound and the mean squared error rate; the corresponding screening procedure enjoys sure screening property for a wide range of correlation measures.

1. 引言

随着数据生成和采集技术的快速发展，在许多科学领域经常会遇到具有大量特征的海量数据。对于经典的统计方法，高维性同时对计算成本、统计准确性和算法稳定性提出了挑战[1] [2]。为了简化计算过程，一种自然的策略是在详细分析之前筛选出最不相关的特征。这个过程被称为特征筛选。随着维数从高降至低，分析难度大大降低。在文献中，这方面已经做了大量的工作；其中，基于相关性的筛选方法引起了学者们的广泛关注。这些方法基于特征与响应之间的某种关联度量进行筛选，弱相关性的特征被视为不相关的特征，将被删除。这种类型的方法可以在没有强模型假设(甚至无模型)下方便地实现。因此，它们通常用于分析具有复杂结构的高维数据，例如，Fan和Lv (2008)提出了基于皮尔逊相关的确定独立性筛选(SIS) [3]，随后他们又把SIS方法进一步推广到广义线性模型和非参数可加模型中[4] [5]。Zhu等(2011)提出了一种基于效用度量的确定独立排序和筛选(SIRS)，该度量与给定预测因子的响应的整个条件分布有关[6]。Li等(2012)提出了基于Kendall秩相关的鲁棒秩相关筛选(RRCS) [7]。Li等(2012)开发了一种基于距离相关的无模型确定独立筛选程序(DC-SIS) [8]。Wu和Yin (2015)提出了一种分布函数确定独立性筛选(DF-SIS)方法，该方法使用一种度量来检验两个变量之间的独立性[9]。Zhou等(2019)提出了一种鲁棒相关度量来筛选包含极值的特征[10]。

特征筛选[11]在许多应用中已被证明是一个有吸引力的策略。现有的方法大多是在特征数p较大，但样本量N为中等的情况下开发的。然而，在现代科学研究中，数据分析师不得不处理大数据集(其中p和N都是巨大的)的情况越来越普遍，例如，在现代全基因组基因研究[12]中，对数十万名参与者进行了数以百万计的SNP基因分型。在互联网研究中，一个杀毒软件每分钟可以扫描数百万个URL中的数万个关键字。当面对大p大N的数据时，由于存储瓶颈和算法可行性，直接采用经典筛选方法在数值上效率低下，例如，对于N = p = 10,000的数据集，众所周知的DC-SIS需要大约60小时才能在具有3.2 GHz CPU和32 GB内存的计算机上进行全面筛选。因此，在实践中开发方便计算的大数据筛选方法[13]-[15]是可取的。

当数据集太大而无法在一台计算机上处理时，考虑使用分而治之策略是很自然的。在该策略中，先将一个大问题分解为较小的可管理子问题，然后将相应的子输出组合得到最终输出。本着这种思想，许多机器学习和统计方法都已经被重建用于处理大数据(例如，Chen和Xie，2014 [16]；Xu et al.，2016 [17]；Jordan等人，2019 [18]；Banerjee et al.，2019 [19])。这些鼓舞人心的工作激励我们探索利用这种有前景的策略进行大数据特征筛选的可行性。

本文提出了一种基于聚合相关测度的分布式特征筛选框架，并将其称为聚合相关筛选(ACS)。在ACS中，我们将相关度量表示为几个组成参数的函数，每个组成参数都可以使用来自数据段的自然U统计量进行分布估计。将无偏分量估计结合在一起，我们得到了一个聚合的相关估计，可以很容易地用于特征筛选。在本文提出的ACS框架中，将海量数据集分成m个可管理的数据段进行处理，这些数据段可存储在多台计算机中，并通过并行计算完成相应的局部估计。因此，它为大p大N数据的特征筛选提供了一条计算上有吸引力的途径。此框架也适用于数据自然存储在不同位置的设置(例如，医院级别的医疗数据)。分量参数的U统计量估计作为一种有效、方便的降阶技术，保证了聚合相关估计量的高精度和相应筛选过程的可靠性。在一般条件下，我们证明了在概率收敛界和均方误差(MSE)率方面，聚合相关估计器与经典的集中估计器一样有效。这种全效率对m的选择不敏感，m的选择可以由问题本身指定，也可以由用户决定。对于广泛的相关度量，我们进一步证明了ACS在不需要指定参数模型(无模型)的情况下具有确定的筛选特性。

本文所提出的ACS植根于分量估计。在文献中，该思想已被用于分布式恢复由数据段中可分离的光滑估计方程定义的集中估计量(例如，Chen等人，2008 [20]；Lin and Xi，2011 [21])。不幸的是，这些工作不能直接适用于基于相关性的筛选，因为许多常用的相关度量的集中估计量通常不是由估计方程定义的，并且在数据段(例如，SIRS和DC)中不可分离。本文所提出的ACS来自于集中相关估计量的自然组合；它并不寻求完全恢复集中式估计器，而是提供一种有效且计算负担得起的替代方案。我们的研究结果为使用这种自然策略进行分布式特征筛选提供了理论支持。

2. 核估计中的筛选方法

2.1. 大数据特征筛选

设$D={\left\{\left(Y_i,X_i\right)\right\}}_{i=1}^N$ 是$\left\{Y,X\right\}$ 的N个独立同分布的样本，其中Y是一个支持${\varphi }_y$ 的响应变量， $X={\left(X_1,\cdots ,X_p\right)}^{\text{T}}$ 是一个p维协变量向量。我们感兴趣的是p和N都很大的情况。当一个数据集是大量的且高维时，通常可以合理地假设只有少数的协变量(特征)与响应相关。设$F\left(x_j|Y\right)$ 是Y给定条件下$X_j$ 的条件分布函数。如果$F\left(x_j|Y\right)$ 依赖于Y，则认为这个特征$X_j$ 是相关的。我们使用M来表示相关特征的索引集，并定义$M^c=\left\{1,\cdots ,p\right\}\backslash M$ 。特征筛选的目标是在详细分析之前，用$j\in M^c$ 去除大多数不相关的特征$X_j$ 。

具体来说，设$w_j\ge 0$ 是Y和$X_j$ 之间相关性强度的一个度量。设${\widehat{w}}_j$ 是基于D的$w_j$ 的集中估计。预先设定阈值$r_n>0$ ，则可以保留在

$\widehat{M}=\left\{j:{\widehat{w}}_j>r_n,j=1,2,\cdots ,p\right\}.$

中的特征并把其他的去除。当样本量N适中时，这种经典方法是有效的。然而，当p和N都很大时，基于完整数据集D计算${\left\{{\widehat{w}}_j\right\}}_{j=1}^p$ 在数值上可能是昂贵的。

2.2. 逆回归聚合筛选法

受近期分布式学习工作的启发，我们考虑采用分而治之的思想[22]来解决大数据特征筛选问题。不失一般性，假设初始完整数据集D被相等地划分为m个可管理的片段${\left\{D_l\right\}}_{l=1}^m$ ，每个片段包含$n=N/m$ 个观测值。根据计算环境的不同，这些数据段可以分布地存储在多台计算机上并进行处理，也可以由单台计算机按顺序进行处理。

我们考虑通过逆回归(Li, 1991) [23]基于核矩阵$\mathrm{cov}\left(E\left(X|Y\right)\right)$ 进行特征筛选，不失一般性，假定 $E\left(X\right)=0$ ，$E\left(Y\right)=0$ ，令$G_j\left(Y\right)=E\left(X_j|Y\right)$ ，$R=\mathrm{cov}\left(E\left(X|Y\right)\right)={\left(r_{i,j}\right)}_{p\times p}$ ，$r_{i,j}=\mathrm{cov}\left[E\left(X_i|Y\right),E\left(X_j|Y\right)\right]$ 。

设$w_j^l=r_{j,j}^l=\mathrm{var}\left(E\left(X_j|Y\in D_l\right)\right)$ ，$w_j=\frac{1}{m}{\displaystyle {\sum }_{l=1}^m{w}_j^l}$ ，对于$j=1,2,\cdots ,p$ ，$w_j^l>0$ ，若$X_j$ 与Y独立，则有

$w_j^l=0\left(j=1,2,\cdots ,p,l=1,2,\cdots ,m\right)$ 。因此，重写活动集$M=\left\{j:w_j>0,j=1,2,\cdots ,p\right\}$ 。

现在我们通过核方法估计$w_j$ 。令$g\left(y\right)$ 表示Y的密度函数，$X_i=\left(X_{i1},X_{i2},\cdots ,X_{ip}\right)$ 为$X$ 的副本，定义

$G\left(Y\right)\triangleq {\left(G_1\left(Y\right),\cdots ,G_p\left(Y\right)\right)}^{\text{T}}={\left(E\left(X_1|Y\right),\cdots ,E\left(X_p|Y\right)\right)}^{\text{T}}\triangleq E{\left(X|Y\right)}^{\text{T}},$

$h\left(Y\right)={\left(h_1\left(Y\right),\cdots ,h_p\left(Y\right)\right)}^{\text{T}}={\left(G_1\left(Y\right)g\left(Y\right),\cdots ,G_p\left(Y\right)g\left(Y\right)\right)}^{\text{T}}.$

用核平滑方法[1]估计$w_j$ 如下：

${\widehat{h}}_j^l\left(Y\right)=\frac{m}{hN}{\displaystyle \sum _{\left\{X_{ij},Y_i\right\}\in D_l}{X}_{ij}K}\left(\left(Y-Y_i\right)/h\right),$

${\widehat{g}}^l\left(Y\right)=\frac{m}{Nh}{\displaystyle \sum _{Y_i\in D_l}K}\left(\left(Y-Y_i\right)/h\right).$

${\widehat{G}}_j^l\left(Y\right)={\widehat{h}}_j^l\left(Y\right)/{\widehat{g}}^l\left(Y\right),{\widehat{R}}^l=\frac{m}{N}{\displaystyle \sum _{Y_h\in D_l}{\widehat{G}}^l\left(Y_h\right){\widehat{G}}^l{\left(Y_h\right)}^{\text{T}}},$

${\widehat{w}}_j^l\triangleq {\widehat{R}}_j^l=\frac{m}{N}{\displaystyle \sum _{Y_h\in D_l}{\left({\widehat{G}}_j^l\left(Y_h\right)\right)}^2}$

且

${\widehat{w}}_j=\frac{1}{m}{\displaystyle \sum _{l=1}^m{\widehat{w}}_j^l},$ (1)

这里h表示带宽，$K(·)$ 为核函数，对于带宽的选择按照plug-in方法(Ruppert et al., 1996 [24])。

本文所提出的分布式筛选采用了逆回归方法和核估计器。我们首先进行组件初始化${\widehat{w}}_j^l$ ，然后将它们组合在一起，得到一个很容易用于特征筛选的聚合估计。我们将该方法命名为AIK (聚合逆回归方法和核估计)。

2.3. 理论分析

现在，我们提供一些使用AIK方法的理论证明。显然，AIK的筛选性能依赖于聚合相关估计${\widehat{w}}_j$ 的准确性。我们表明，${\widehat{w}}_j$ 是一种有效的估计$w_j$ 的工具；这是AIK的理论基础。我们的理论研究基于以下技术条件：

• C1. 密度函数$g\left(y\right)$ 在$D_l,l=1,2,\cdots ,m$ 上有连续的二阶导数，且$f^{\prime }\left(y\right),f^{″}\left(y\right)$ 具有有限上界，即对于某正数$M_1,M_2$ ，$f^{\prime }\left(y\right)\le M_1$ ，$f^{″}\left(y\right)\le M_2$ [25] [26]。

• C2. 核函数$K(·)$ 一致有界，且${\displaystyle \int t^{2}K\left(t\right)\text{d}t}<\infty$ 。

• C3. 对于正的常数$\kappa ,c_3,\gamma >\kappa$ ，${\max }_{\left\{Y\in {\varphi }_Y\right\}}{\left[E\left(X_j|Y\right)\right]}^2<c_3{N}^{-\kappa }$ 。

基于上述条件，我们推导了所提方法AIK的统一筛选框架。

定理2.1 在条件C1~C3下，假定带宽$h=O\left(N^{-\gamma }\right)$ ，$\gamma$ 在条件C3中定义，对于一些正常数$C_2,c_5$ ，

$P\left(\underset{1\le j\le p}{\max }\left|{\widehat{w}}_j-w_j\right|\ge c_3{N}^{-\kappa }\right)\le C_2\exp \left(-c_5{N}^{\gamma -\kappa }\right),$

且若取$r_n=c_3{N}^{-\kappa }$ ，则

$P\left(M\subset \widehat{M}\right)\ge 1-C_2{s}_{n}N\exp \left(-c_5{N}^{\gamma -\kappa }\right),$

这里$c_5$ 为正常数。

3. 定理证明

引理1. 对任意随机变量X，下列两个语句等价：

• A. 存在$H>0$ 使得对于所有的$\left|t\right|<H$ ，有$E{\text{e}}^{tX}<\infty$ 。

• B. 存在$r>0$ 使得$E{\text{e}}^{s\left(X-EX\right)}<{\text{e}}^{r{s}^2}$ 。

引理2. 假定X是一个随机变量，对于某个$a>0$ 有$E\left({\text{e}}^{a\left|X\right|}\right)<\infty$ 。则对于任意$M>0$ ，存在正常数b和c使得

$P\left(\left|X\right|\ge M\right)\le b{\text{e}}^{-cM}.$

引理3. (霍丁夫不等式[27] [28])设独立随机变量$X_i,i=1,\cdots ,n$ 对于一些$a_i,b_i,i=1,\cdots ,n$ 满足 $P\left(X_i\in \left[a_i,b_i\right]\right)=1$ 。则对任意$\epsilon >0$ ，有

$P\left(\left|X-E\left(X\right)\right|\ge \epsilon \right)\le 2\exp \left(\frac{2{\epsilon }^2{n}^2}{{\displaystyle {\sum }_{i=1}^n{\left(b_i-a_i\right)}^2}}\right),$ (2)

这里$X=\left(X_1+\cdots +X_n\right)/n$ 。

引理4. 设$a\left(u\right)$ 和$b\left(u\right)$ 是u的两个一致有界函数，即存在$M_5>0$ ，$M_6>0$ ，使得${\sup }_{u\in U}\left|a\left(u\right)\right|\le M_5$ ，${\sup }_{u\in U}\left|b\left(u\right)\right|\le M_6$ 。对于给定的$u\in U$ ，$\widehat{A}\left(u\right)$ 和$\widehat{B}\left(u\right)$ 是基于大小为n的样本的$a\left(u\right)$ 和$b\left(u\right)$ 的估计。假定对任意小的$\epsilon \in \left(0,1\right)$ ，存在正常数$c_1,c_2$ 和s，使得[29]

${\sup }_{u\in U}P\left(\left|\widehat{A}\left(u\right)-a\left(u\right)\right|\ge \epsilon \right)\le c_1{\left(1-\frac{\epsilon s}{c_1}\right)}^n,$ (3)

${\sup }_{u\in U}P\left(\left|\widehat{B}\left(u\right)-b\left(u\right)\right|\ge \epsilon \right)\le c_2{\left(1-\frac{\epsilon s}{c_2}\right)}^n,$ (4)

则

${\sup }_{u\in U}P\left(\left|{\left(\widehat{A}\left(u\right)\right)}^2-{\left(a\left(u\right)\right)}^2\right|\ge \epsilon \right)\le C_7\exp \left(-\frac{\epsilon }{C_{7}h}\right),$ (5)

${\sup }_{u\in U}P\left(\left|\widehat{A}\left(u\right)/\widehat{B}\left(u\right)-a\left(u\right)/b\left(u\right)\right|\ge \epsilon \right)\le C_9\exp \left(-\frac{\epsilon }{C_{9}h}\right),$ (6)

定理2.1的证明. 证明步骤如下：

步骤1：证明对任意的$\epsilon \in \left(0,1\right)$ ，$1\le j\le p$ ，可以找到一个正常数C使得

$P\left(\left|{\widehat{h}}_j^l\left(Y\right)-h{g}^l\left(Y\right)m_j^l\left(Y\right)\right|\ge \epsilon \right)\le C\exp \left(-\frac{\epsilon }{h}\right).$

注意到

$\begin{array}{l}P\left(\left|{\widehat{h}}_j^l\left(Y\right)-h{g}^l\left(Y\right)m_j^l\left(Y\right)\right|\ge \epsilon \right)\\ =P\left(\left|{\widehat{h}}_j^l\left(Y\right)-E\left[{\widehat{h}}_j^l\left(Y\right)\right]+E\left[{\widehat{h}}_j^l\left(Y\right)\right]-h{g}^l\left(Y\right)m_j^l\left(Y\right)\right|\ge \epsilon \right)\\ \le P\left(\left(\left|{\widehat{h}}_j^l\left(Y\right)-E\left[{\widehat{h}}_j^l\left(Y\right)\right]\right|+\left|E\left[{\widehat{h}}_j^l\left(Y\right)\right]-h{g}^l\left(Y\right)m_j^l\left(Y\right)\right|\right)\ge \epsilon \right)\end{array}$ (7)

$\begin{array}{c}E\left[{\widehat{h}}_j^l\left(Y\right)\right]-h{g}^l\left(Y\right)m_j^l\left(Y\right)=E\left(X_{ij}K\left(\frac{Y-Y_i}{h}\right)\right)-h{g}^l\left(Y\right)m_j^l\left(Y\right)\\ =E\left(m_j^l\left(Y_1\right)K\left(\frac{Y-Y_1}{h}\right)\right)-h{g}^l\left(Y\right)m_j^l\left(Y\right)\triangleq \Delta \left(Y,h\right).\end{array}$

上述第一个等式是表示$E\left(X_{ij}|Y_i\right)$ 为$m_j^l\left(Y_1\right)$ 。

又有

$h^{-1}\Delta \left(Y,h\right)={\displaystyle \int \left\{m_j^l\left(Y-th\right)g^l\left(Y-th\right)-m_j\left(Y\right)g^l\left(Y\right)\right\}K\left(t\right)\text{d}t.}$

因为$K\left(t\right)$ 是对称的，${\displaystyle \int K\left(t\right)\text{d}t}=0$ 。此外，

$\begin{array}{c}\underset{h\to 0}{\lim }{h}^{-2}\left\{m_j^l\left(Y-th\right)g^l\left(Y-th\right)-m_j^l\left(Y\right)g\left(Y\right)-\left[m_j^l{}^{\prime }\left(Y\right)g\left(Y\right)+m_j^l\left(Y\right)g^l{}^{\prime }\left(Y\right)\right]th\right\}\\ \to \left\{m_j^l{}^{\prime \text{}\prime }\left(Y\right)g\left(Y\right)+2m_j^l{}^{\prime }\left(Y\right)g^{\prime }\left(Y\right)+m_j\left(Y\right)g^l{}^{\prime \text{}\prime }\left(Y\right)\right\}{t}^2.\end{array}$ [26] (8)

因此通过控制收敛定理以及条件C1~C2，$m_j^l{}^{\prime \text{}\prime }\left(Y\right)g\left(Y\right)+2m_j^l{}^{\prime }\left(Y\right)g^{\prime }\left(Y\right)+m_j\left(Y\right)g^l{}^{\prime \text{}\prime }\left(Y\right)$ 一致有界，对于$Y\in {\varphi }_Y$ 及一些常数$C_0$ ，$h^{-3}\Delta \left(Y,h\right)$ 一致有界，也就是说，

$当h\to 0时,E\left[{\widehat{h}}_j^l\left(Y\right)\right]-h{g}^l\left(Y\right)m_j^l\left(Y\right)\le C_0{h}^3$

即取$C_0{h}^3=\epsilon /2$ 时，$E\left[{\widehat{h}}_j^l\left(Y\right)\right]-h{g}^l\left(Y\right)m_j^l\left(Y\right)\le \epsilon /2$ 。因此，(7)式变为

$\begin{array}{l}P\left(\left|{\widehat{h}}_j^l\left(Y\right)-h{g}^l\left(Y\right)m_j^l\left(Y\right)\right|\ge \epsilon \right)\le P\left(\left|{\widehat{h}}_j^l\left(Y\right)-E\left[{\widehat{h}}_j^l\left(Y\right)\right]\right|\ge \epsilon /2\right)\\ \le P\left(\left|{\widehat{h}}_j^l\left(Y\right)-E\left[{\widehat{h}}_j^l\left(Y\right)\right]\right|\ge \epsilon /2,\max \left\{\left|X_{ij}\right|\right\}\le T\right)+P\left(\left|{\widehat{h}}_j^l\left(Y\right)-E\left[{\widehat{h}}_j^l\left(Y\right)\right]\right|\ge \epsilon /2,\max \left\{\left|X_{ij}\right|\right\}\ge T\right)\\ \le P\left(\left|{\widehat{h}}_j^l\left(Y\right)-E\left[{\widehat{h}}_j^l\left(Y\right)\right]\right|\ge \epsilon /2\right)+P\left(\max \left\{\left|X_{ij}\right|\right\}\ge T\right)=S_1+S_2,\end{array}$ (9)

其中$S_1=P\left(\left|{\widehat{h}}_j^l\left(Y\right)-E\left[{\widehat{h}}_j^l\left(Y\right)\right]\right|\ge \epsilon /2\right)$ ，$S_2=P\left(\max \left\{\left|X_{ij}\right|\right\}\ge T\right)$ 。

根据引理3可知$S_1\le 2\exp \left(\frac{-2{\epsilon }^{2}N}{m{T}^2}\right)$ ，再由引理2可知$S_2\le C_{1}N/m\exp \left(-c_{1}T\right)$ 。则

$\begin{array}{l}P\left(\left|{\widehat{h}}_j^l\left(Y\right)-h{g}^l\left(Y\right)m_j^l\left(Y\right)\right|\ge \epsilon \right)\le 2\exp \left(\frac{-2{\epsilon }^{2}N}{m{T}^2}\right)+C_{1}N/m\exp \left(-c_{1}T\right)\\ =2\exp \left(-\frac{\epsilon }{h}\cdot \frac{-2\epsilon hN}{m{T}^2}\right)+C_1\exp \left(-\frac{\epsilon }{h}\cdot c_{1}h\log \left(N/m\right)T/\epsilon \right).\end{array}$ (10)

又因为$h=O\left({\left(\frac{N}{m}\right)}^{-\gamma }\right)$ ，$T=O\left({\left(N/m\right)}^{\tau }\right)$ ，这里$\gamma <\tau <\left(1-\gamma \right)/2$ ，对于大的N，

$\frac{2\epsilon hN}{m{T}^2}=C\cdot {\left(\frac{N}{m}\right)}^{1-\gamma -2\tau }>1,c_{1}h\log \left(N/m\right)T/\epsilon =C\cdot {\left(\frac{N}{m}\right)}^{\tau -\gamma }\log \left(N/m\right)>1$

因此，(10)式变为

$P\left(\left|{\widehat{h}}_j^l\left(Y\right)-h{g}^l\left(Y\right)m_j^l\left(Y\right)\right|\ge \epsilon \right)\le C\exp \left(-\frac{\epsilon }{h}\right).$

相似地，我们也可以证得对于正常数$C_2$ ，

$P\left(\left|{\left({\widehat{G}}_j^l\left(Y_i\right)\right)}^2-{\left(m_j^l\left(Y_i\right)\right)}^2\right|\ge \epsilon \right)\le C_2\exp \left(-\frac{\epsilon }{h}\right).$

步骤2：证明对任意的$\epsilon \in \left(0,1\right)$ ，推导出$P\left({\max }_{1\le j\le p}\left|{\widehat{w}}_j-w_j\right|>\epsilon \right)$ 的上界。

注意到

$\begin{array}{c}P\left(\left|{\widehat{w}}_j^l-w_j^l\right|\ge \epsilon \right)=P\left(\left|\frac{m}{N}{\displaystyle \sum _{Y_i\in D_l}{\left(G_j^l\left(Y_i\right)\right)}^2}-\frac{m}{N}{\displaystyle \sum _{Y_i\in D_l}{\left(m_j^l\left(Y_i\right)\right)}^2}\right|\ge \epsilon \right)\\ =P\left(\left|{\displaystyle \sum _{Y_i\in D_l}{\left(G_j^l\left(Y_i\right)\right)}^2}-\frac{m}{N}{\displaystyle \sum _{Y_i\in D_l}{\left(m_j^l\left(Y_i\right)\right)}^2}\right|\ge \frac{N}{m}\epsilon \right)\\ \le {\displaystyle \sum _{Y_i\in D_l}P\left(\left|{\left(G_j^l\left(Y_i\right)\right)}^2-{\left(m_j^l\left(Y_i\right)\right)}^2\right|\ge \frac{N}{m}\epsilon \right)}\\ \le \frac{N}{m}\underset{Y_i\in D_l}{\max }P\left(\left|{\left(G_j^l\left(Y_i\right)\right)}^2-{\left(m_j^l\left(Y_i\right)\right)}^2\right|\ge \frac{N}{m}\epsilon \right)\\ \le \frac{N}{m}{C}_2\exp \left(-\frac{\epsilon }{h}\right).\end{array}$ (11)

利用同样的思想，我们可以证明$P\left(\left|{\widehat{w}}_j-w_j\right|\ge \epsilon \right)\le C_{2}N\exp \left(-\frac{\epsilon }{h}\right)$ 。又

$\begin{array}{c}P\left({\max }_{1\le j\le p}\left|{\widehat{w}}_j-w_j\right|\ge c_3{N}^{-\kappa }\right)\le {\displaystyle \sum _{j=1}^{p}P\left(\left|{\widehat{w}}_j-w_j\right|\ge c_3{N}^{-\kappa }\right)}\\ \le C_{2}N\exp \left(-c_4{N}^{-\kappa +\gamma }\right)\\ \le C_2\exp \left(-c_4{N}^{-\kappa +\gamma }+2\log p\right)\end{array}$

$h=O\left(N^{-\gamma }\right)$ ，$c_4$ 是一个正常数。取$\log p=O\left(N^{\gamma -\kappa }\right)$ ，即对正常数$\xi$ ，$c_4-2\xi >0$ ，有$\log p=\xi N^{\gamma -\kappa }$ 。则上式变为

$\begin{array}{c}P\left({\max }_{1\le j\le p}\left|{\widehat{w}}_j-w_j\right|\ge c_3{N}^{-\kappa }\right)\le C_2\exp \left(-\left(c_4-2\xi \right)N^{-\kappa +\gamma }\right)\\ =C_2\exp \left(-c_5{N}^{-\kappa +\gamma }\right),c_5=c_4-2\xi .\end{array}$

步骤3：取$r_n=2c_3{N}^{-\kappa }$ ，证明$P\left(M\subset \widehat{M}\right)\ge 1-C_2{s}_{n}N\exp \left(-c_5{N}^{\gamma -\kappa }\right)$ 。

$\begin{array}{c}P\left(M\subset \widehat{M}\right)=P\left(\underset{j\in M}{\min }{\widehat{w}}_j\ge c_3{N}^{-\kappa }\right)=P\left(\underset{j\in M}{\min }{w}_j-\underset{j\in M}{\min }{\widehat{w}}_j\le \underset{j\in M}{\min }{w}_j-c_3{N}^{-\kappa }\right)\\ \ge P\left(\underset{j\in M}{\min }{w}_j-\underset{j\in M}{\min }{\widehat{w}}_j\le 2c_3{N}^{-\kappa }-c_3{N}^{-\kappa }\right)\ge P\left(\underset{j\in M}{\max }\left|w_j-{\widehat{w}}_j\right|\le c_3{N}^{-\kappa }\right)\\ \ge 1-P\left(\underset{j\in M}{\max }\left|w_j-{\widehat{w}}_j\right|\ge c_3{N}^{-\kappa }\right)\ge 1-s_{n}P\left(\left|w_j-{\widehat{w}}_j\right|\ge c_3{N}^{-\kappa }\right)\\ \ge 1-C_2{s}_{n}N\exp \left(-c_5{N}^{\gamma -\kappa }\right).\end{array}$

以上就完成了定理2.1的证明。

NOTES

^*通讯作者。