一类高维多响应变量误差模型的极小极大下界

李欣, 吴东亚

(1. 西北大学数学学院, 陕西 西安 710127;2. 西北大学信息科学与技术学院, 陕西 西安 710127)

1 引言

近几十年来, 高维统计学在理论和应用上都取得了丰硕的成果[1-2]; 为了应对维度灾难, 研究者们提出了不同的具有低维结构的统计模型, 如稀疏线性回归, 低秩矩阵回归, 以及近几年的高阶张量回归等等. 例如, 文献[3-4] 研究了低秩矩阵回归, 提出了核范数正则化估计量, 在一定的正规条件下证明了估计量的统计一致性. Chen 等人考虑了多变量广义线性模型, 通过块稀疏回归技巧建立了特征选择一致性和参数估计的最优性[5]. 文献[6-9] 采用凸或非凸优化方法研究了高维多响应张量回归. 在合适的低维结构化假设下, 研究者们给出了关于统计和计算层面的理论保证. 具体地, 文献[7] 提出了一般的凸优化方法并在协变量相依的情况下得到了估计量的统计误差上界. 文献[8] 进一步考虑了计算效率, 提出的非凸估计方法取得了较凸方法更优的收敛速率, 并应用近端梯度算法实现了问题的求解. 文献[9] 采用极大似然估计方法, 得到了参数的估计和预测误差以及渐进性质. 文献[6] 考虑了非凸估计方法, 建立了统计误差界和近端梯度算法的线性收敛速率, 并证明了非凸估计量的极小极大最优性.

特别地, 多响应回归模型作为矩阵回归的一个重要实例, 在理论层面得到了深入研究[3,10], 并被广泛应用于实际问题,如神经影像分析等[11-12]. 考虑如下多响应回归模型

其中Θ∗∈Rd1×d2是未知的参数矩阵,Y∈Rn×d2是响应矩阵,X∈Rn×d1是协变量矩阵,ϵ∈Rn×d2是噪音矩阵. 为了获得相合的估计, 参数矩阵Θ∗通常被赋予某些结构约束如低秩性.

高维统计学通常分为两个研究方向. 一方面, 研究者们致力于构造具有快速收敛率的估计量. 另一方面, 探索估计量的本质或信息理论极限进而评价其性能也具有十分重要的意义. 前一目标可以通过一些统计技巧如集中不等式等建立估计误差的上界实现,而后者通常需要借助信息理论工具以推导基于某些定量标准的下界.

给定真实未知参数的一个任意估计量, 存在很多标准可以用于评价估计的质量. 从决策理论的框架而言, 通常是引入一个损失函数用以表示估计过程所带来的损失. 然后根据极小极大法则, 构造一个最坏情况损失函数并极小化之, 以刻画最优收敛率. 在推导最坏情况损失函数下界的过程中, 经常需要用到假设检验不等式和Fano 不等式以及估计一些信息理论参量, 如互信息, Kullback-Leibler(KL) 散度以及全变差距离等; 详细的讨论见文献[13-14].

注意在模型(1) 中, 当d2= 1 且未知参数Θ∗被赋予向量稀疏性约束时, 模型(1)退化为稀疏线性回归, 并得到了大量关于极小极大估计的研究. 例如, 文献[15-16] 采用标准的信息理论技巧, 给出了估计的极小极大收敛率. 文献[17] 提出一种聚合策略, 借此建立了极小极大最优收敛率, 进一步构造了一个自适应的最优估计量. 转到低秩估计问题, 研究者们主要关注矩阵补全问题进而建立极小极大最优收敛率[18-20]; 文献[21]则考虑了一类一般的低秩矩阵恢复问题, 利用有限维Schatten 空间中某些恒等映射的Gelfand 宽度, 给出了最坏情况误差界的估计.

上述提到的工作都基于协变量是干净数据的假设, 这在理论分析中是很标准的. 然而, 实际问题中由于实验仪器的限制或观测的不完全, 这一假设总是会被违背. 也就是说, 收集得到的协变量数据通常带有一定的测量误差. 那么如果忽略测量误差, 直接应用针对干净协变量数据建立的方法呢? 答案令人沮丧, 因为已经有文献[22] 通过模拟指出这一操作只会带来错误的结果. 因此, 在协变量数据带有误差扰动的情形下, 研究统计模型并建立方法更加必要且具有现实意义.

近年来, 研究者们开始致力于变量误差回归模型, 大部分结果建立在线性或广义线性模型上[23-26]; 在信息理论层面, 文献[27-28] 考虑了线性误差模型, 分别估计了不同向量集合的KL 散度, 建立了稀疏向量估计的极小极大下界.

然而迄今为止, 研究者们对带有测量误差的多响应回归模型(1) 的关注相对较少.尽管一个自然而简单的想法是将协变量矩阵和响应变量矩阵同时向量化, 这时原始的多响应模型退化为单响应变量情形, 进而可以直接应用上述关于单响应变量，亦即线性回归的结果. 但是由于更为复杂的流形结构, 矩阵的低秩性与向量的稀疏性截然不同[4].更进一步, 响应变量的多元性使得人们可以建立更为复杂的模型用于现代大规模关联分析, 如fMRI 影像分析等[12], 因而相比于单响应变量模型具有更为广泛的应用.

本文研究了多响应变量误差模型的信息理论极限. 首先将对下界的估计转换为一个多重假设检验问题, 然后应用Fano 不等式[14]估计错误概率的下界. 本文的主要贡献如下. 首先借助随机矩阵乘法的集中不等式, 得到互信息中涉及的KL 散度的估计. 然后对一类低秩矩阵, 以平方Frobenius 范数的形式建立了极小极大损失函数的下界. 更进一步, 这一下界达到了文献[18,20-21] 在干净协变量假设下的收敛率, 表明即使在更具实际意义的变量误差模型中, 仍然不需要更多的样本以获得收敛率最优的估计.

本文的结构安排如下. 在第2 节, 给出关于多响应变量误差模型和极小极大估计问题的背景知识. 在第3 节, 建立了关于极小极大下界的主要结果. 结论和未来工作在第4 节讨论.

在此, 先介绍一些符号以供接下来参考. 所有向量都是遵从经典数学惯例的列向量.对d≥1, 令Id表示d×d维恒等矩阵. 对矩阵X∈Rn×d, 令Xij(i= 1,··· ,n,j=1,2,··· ,d) 表示其第ij个元素,Xi·(i=1,··· ,n) 表示其第i行,X·j(j=1,2,··· ,d)表示其第j列. 当X是方阵, 即n=d时, 用diag(X) 表示一个对角矩阵, 其对角元分别等于X11,X22,··· ,Xdd. 用λmin(X) 和λmax(X) 分别表示矩阵X的最小和最大特征值. 对矩阵Θ ∈Rd1×d2, 定义d= min{d1,d2}, 并将其按降序排列的奇异值记为σ1(Θ) ≥σ2(Θ) ≥···σd(Θ) ≥0. 用|||·||| 表示基于奇异值的不同矩阵范数, 包括核范数|||Θ|||∗= ∑dj=1σj(Θ), 谱或算子范数|||Θ|||op=σ1(Θ), 以及Frobenius 范数

2 问题建立

本节将给出多响应回归变量误差模型的详细描述并介绍极小极大估计问题.

考虑如下高维多响应回归模型, 表达了响应向量Yi·∈Rd2与协变量向量Xi·∈Rd1之间的关系

其中Θ∗∈Rd1×d2是未知的参数矩阵,ϵi·∈Rd2是响应向量的观测误差, 且∀i,j,ϵi·与Xj·独立. 模型(1) 可以更紧凑的矩阵形式表达. 具体而言, 定义多响应矩阵Y=(Y1·,Y2·,··· ,Yn·)⊤∈Rn×d2, 类似的, 以向量的形式分别定义协变量矩阵X∈Rn×d1和噪音矩阵ϵ∈Rn×d2. 那么模型(2) 可重新写作

本文主要研究高维情形, 其中协变量或响应变量的数量(即d1或d2) 可能超过样本数量n. 众所周知, 在这一情形下, 除非参数空间被赋予额外的低维结构(如矩阵估计问题中的低秩性) , 否则无法实现估计的相合性. 特别地, 假设R0≪min{d1,d2}, 在本文中将考虑如下的低秩矩阵集合

在下面定理3.1 的证明中, 将看到关于Stiefel 流形的结果将被用于分析目标低秩矩阵集合

在标准多响应回归模型(3) 中, 通常假设协变量矩阵X是准确获得的. 然而在实际应用中, 协变量经常受到噪音的干扰. 在这一更为现实的情形下, 人们只能观测到带有扰动的协变量矩阵Z而不是真实协变量矩阵X, 这也将是本文关注的情形. 详细而言, 本文考虑如下的带有加性噪音的变量误差模型：对每个i= 1,2,··· ,n, 观测到Zi·=Xi·+Wi·, 其中Wi·∈Rd1是一个与Xi·独立的随机噪音向量, 均值为0, 协方差矩阵已知为Σw. 当噪音协方差矩阵Σw未知时, 可尝试以统计方法从观测数据中进行估计, 见文献[29]. 举例而言, 一个简单的方法是从空白控制观测组中估计Σw. 具体来说, 假设矩阵W0∈Rn×d1是空白观测组中的数据, 由n个独立同分布的测量误差向量组成, 那么矩阵可被用于Σw的估计量. 基于此方法的更加复杂的方法见文献[29].

本文对加性变量误差模型施加如下的Gaussian 随机假设.

假设2.1对i=1,2,··· ,n, 向量Xi·,Wi·和ϵi·是独立同分布的Gaussian 随机向量, 均值为0, 协方差矩阵分别为

注2.1上述Gaussian 随机假设在研究者可以根据目标设计实验的领域, 如信号处理和压缩感知中, 具有特殊的重要意义而被广泛使用[30]. 其中零均值假设很容易通过列归一化得到满足. 但值得注意的是, 在某些统计领域, 这一独立Gaussian 假设仍然有一定局限性. 进一步的研究将推广当前结果至更一般的协变量数据, 如具有非对角协方差矩阵的次- Gaussian 分布.

因为对每个i=1,2,··· ,n,Zi·=Xi·+Wi·,所以扰动协变量向量Zi也是Gaussian的, 均值为0, 协方差矩阵为(σ2x+σ2w)Id1. 为了简单起见, 令σ2z=σ2x+σ2w, 并将Zi的协方差矩阵记为Σz=σ2zId1.

从统计学的角度, 为了估计未知参数Θ∗, 研究者们试图构造一个估计量:Rn×d1×Rn×d2→Rd1×d2, 它是观测数据(Z,Y) 的可测函数. 而信息理论的任务是评估估计量的性能. 标准做法是引入一个损失函数L(,Θ∗), 其表达了当真实参数属于某个特定集合(即本文中的Θ∗∈) 时, 由估计量所引入的损失. 在极小极大法则中, 本文目标是找到下述以平方Frobenius 范数形式给出的最坏情况损失函数的下界

其中下确界inf 取遍观测数据(Z,Y) 的所有可测函数. 由于对噪音W和ϵ的依赖,M() 是随机的. 因此, 所要得到的下界应该以期望或概率的形式给出.

3 主要结果

本节中将以很高的概率建立极小极大下界. 为清晰起见, 下面给出一些有用的定义.

定义3.1(次- Gaussian 矩阵) 随机矩阵Γ ∈Rn×d1称为是参数为(Σγ,σ2γ) 的次- Gaussian 矩阵, 如果它满足如下条件:

(i) 每一行Γi·都是独立同分布的随机向量, 均值为0, 协方差矩阵为Σγ;

(ii) 对任意单位向量u∈Rd1, 随机变量u⊤Γi·是次- Gaussian 的, 参数最大为σγ.

注3.1回忆本文施加在加性噪音模型上的假设2.1. 由定义3.1 易见矩阵X,W和ϵ都是次- Gaussian 矩阵, 参数分别为(Σx,σ2x), (Σw,σ2w) 和(Σϵ,σ2ϵ). 又因为Z=X+W,Z也是次- Gaussian 矩阵, 参数为(Σz,σ2z).

定义3.2(KL 散度) 对两个分布P 和Q, 其概率密度关于某个基础测度µ分别是dP 和dQ, 这两个分布之间的KL散度定义为

定义3.3(互信息) 对两个随机变量B和B′, 其分布函数分别是PB和PB′, 这两个随机变量之间的互信息定义为I(B;B′)=EB′[D(PB|B′||PB)], 其中PB|B′是B关于B′的条件分布.

定义3.4(∆- packing 集合) 令(V,ρ) 是一个赋范线性空间, 范数为ρ:V×V→R+,S⊆V. {Θ1,Θ2,··· ,ΘN} 称为是S的一个∆- packing 集合, 如果满足对任意i≠j, 都有ρ(Θi,Θj)>∆. ∆称为S的这个packing 集合的半径.

在给出定理3.1 之前, 需要如下三个引理. 引理3.1 来自文献[25] 的补充材料的引理14, 给出了一般的次- Gaussian 随机矩阵与固定向量乘法的偏离界. 引理3.2 同样是统计意义上的, 反映了一般的次- Gaussian 随机矩阵与固定矩阵乘法的集中不等式. 引理3.3 是信息理论层面的, 利用了引理3.2 的结果, 并且专门针对本文考虑的Gaussian随机模型(见假设2.1). 引理3.3 估计了由不同参数Θ,Θ′∈所导出的响应变量Y的两个分布之间的KL 散度. 令PΘ表示多响应加性变量误差模型中, 当给定参数矩阵Θ和观测协变量矩阵Z时, 响应变量Y的分布.

引理3.2令t> 0 是任意常数, Γ ∈Rn×d1是一个零均值的次- Gaussian 矩阵,参数为(Σγ,σ2γ). 那么对任意固定矩阵Θ ∈Rd1×d2, 存在一个普适正常数c0使得

证明根据矩阵Frobenius 范数的定义, 有

然后根据基本概率理论得到

另一方面, 由题设Γ 是参数为(Σγ,σ2γ) 的次- Gaussian 矩阵, 应用引理3.1 可得, 存在一个普适正常数c0使得

引理3.3在加性变量误差模型中, 令假设2.1 成立. 那么存在一个普适正常数c0, 使得至少以概率1-2 exp(-c0n+logd2) 保证如下结果成立, 其表示不同参数所导出Y的两个分布的KL 散度的上界

证明对每个固定的i= 1,2,··· ,n, 根据模型设置, (Yi·,Zi·) 服从均值为0 的联合Gaussian 分布. 通过计算协方差矩阵可以得到

然后由关于Gaussian 随机向量条件分布的标准结果可得

假设σϵ和σw不同时为0, 因为否则的话, 结论自然成立. 对不同参数定义采用类似的方式定义. 回忆假设2.1中并注意到Σz=σ2zId1, 有

根据制粒原料不同的力学特性，考虑到物料在喂料过程中的规律性和模孔结构的轴对称性，可以将模孔中的物料划分为横观各向同性材料和各向同性材料。分别如图2和图3所示。

由(9) 式可知ΣΘ= ΣΘ′, 因此(10) 式中的前两项均等于0. 再根据(9) 式得到也是对角矩阵, 其前R0个对角元等于, 后d2-R0个对角元等于由于, 将这些讨论与(10) 式联合, 得到

现在只需应用引理3.2 估计(11) 式中|||Z(Θ-Θ′)|||2F的界. 由假设2.1 可知, 矩阵Z是由服从N(0,σ2zId1) 的独立同分布的行组成的. 根据定义3.1 可得矩阵Z是参数为(σ2zId1,σ2z) 的次- Gaussian 矩阵. 那么在引理3.2 中用(11) 式的矩阵Z替换矩阵Γ, 并令t=d2σ2z, 可得存在一个普适正常数c0使得

这表明

将上式带入(11) 式, 得到存在一个普适正常数c0, 使得下式至少以概率1 -2 exp(-c0n+logd2) 成立

定理3.1在加性变量误差模型中, 令2 ≤R0≤d1-R0以及假设2.1 成立. 那么存在普适正常数(c0,c1) 使得, 至少以概率1/2(1-2 exp(-c0n+logd2)) 成立如下极小极大下界

这一下界的证明遵循信息理论分析的标准步骤. 从全局角度而言, 证明基本分为以下三步. 首先, 对极小极大下界的估计转化为一个合适的packing 集合上的多重假设检验问题. 这个packing 集合在目前被当做已知, 其具体形式将在最后一步确定. 然后, 应用Fano 不等式[14]来估计错误概率的下界, 即(14) 式的右端(见(15) 式). 在这一步, 需要估计(15) 式中涉及到的互信息的上界, 这将通过其与KL 散度的联系实现(见定义3.3 和(16) 式). 最后, 找到前述packing 集合. 为此需要确定三个与这一特定packing 集合相关的参数, 分别为(14) 式中的packing 半径∆, (14) 式中的基数N,以及(17) 式中任意两个不同元素间距离的上界(即, 对所有j≠k). 此外, 选择的packing 集合还必须确保(15) 式的概率严格大于0. 将通过选取合适的常数, 借助Stiefel 流形Vd1,R0(见(5) 式) 的packing 集合来构造目标集合(见(4)式) 的packing 集合.

证明对正数∆> 0, 令{Θ1,Θ2,··· ,ΘNF(∆)} 表示按Frobenius 范数意义的最大∆- packing 集合, 其中NF(∆) 表示这一packing 集合的基数. 后续用N作为NF(∆) 的简写. 直接由文献[14] 中的标准技巧将对下界的估计转化为如下多重假设检验问题

其中∆> 0 是packing 集合{Θ1,Θ2,··· ,ΘN} 的半径,B∈Rd1×d2是一个均匀分布于这一packing 集合的矩阵随机变量,是取值于这一packing 集合的B的估计量.由(14) 式可见需要估计概率P(≠B) 的下界. 根据Fano 不等式, 有

其中I(Y;B) 表示随机分布参数矩阵B∈Rd1×d2与观测响应矩阵Y∈Rn×d2的互信息. 由(15) 式可知需要估计互信息I(Y;B) 的上界. 令PΘj表示当给定B= Θj和噪音协变量矩阵Z时,Y的分布. 由于B均匀分布在packing 集合上,Y具有混合分布, 进而可得

其中最后一个不等式由KL 散度的凸性得到. 将这一不等式与引理3.3 联立可得, 存在一个普适正常数c0, 使得至少以概率1-2 exp(-c0n+logd2), (16) 式具有如下上界

定义随机事件A={(17) 成立}. 那么有P(A)≥1-2 exp(-c0n+logd2). 接下来, 将找到的一个合适的packing 集合, 并据此估计(17) 式中|||Θ-Θ′|||2F的上界, 以及确保(15) 式严格大于0. 根据假设2 ≤R0≤d1-R0以及文献[31] 中的引理A.6 与公式(A.16) 可得对正数δ>0, 存在集合使得对任意j≠k,都有并且logN≥R0(d1-R0)log(c2/δ), 其中c2是一个普适正常数. 也就是说是Vd1,R0的一个δ- packing 集合. 接下来对所有j=1,··· ,N, 令

其中0 表示d1×(d2-R0) 维零子矩阵. 容易验证{Θ1,Θ2,··· ,ΘN} ⊆并且是的一个这是因为对任意j≠k都有进一步可得那么由(18) 式定义的集合{Θ1,Θ2,··· ,ΘN} 正是要寻找的的∆-packing 集合. ∆的具体值稍后给出. 将不等式带入(17) 式, 得到在事件上A成立

将(19) 式和(15) 式联立并注意到logN≥R0(d1-R0)log(c2/δ), 可得

对普适正常数c3, 令因此那么只需选取合适的常数, (20) 式一定严格大于0, 并且可以1/2 为下界. 具体而言, 容易验证只要选择常数c2,c3满足

那么(20) 式以1/2 为下界. 事实上, 由2 ≤R0≤d1-R0可得R0(d1-R0) ≥4.因此只要一定有(21) 式成立. 并且如果选取合适常数c2,c3满足(22) 式也成立. 将P(≠B|A) ≥1/2 和P(A) ≥1-2 exp(-c0n+logd2) 带入(14) 式, 最终得到存在普适正常数(c0,c1)(其中c1=c23) 使得

注3.2(i) 注意到Fano 不等式在定理3.1 的证明中至关重要. Fano 不等式在文献[32] 中首先被提出, 最初是为了反映多重假设检验的平均误差概率与随机样本和相应参数的联合分布之间的关系. 随后这一不等式被用于统计学研究, 用来估计的信息理论极小极大收敛率[33-34]. 为了应用这一技巧, 需要控制互信息并构造合适的packing集合. 这也是本文的工作之一.

(ii) 定理3.1 证明在加性变量误差情形下, 以很高的概率, 用任何方法都大约需要max{d1,d2}R0个样本以实现对秩为R0的d1×d2维矩阵相合的估计. 以往的研究也涉及到矩阵补全问题的信息理论极限[18,20]. 具体而言, 对一个秩为R0的d×d维方阵, 文献[18] 表明大约需要R0dlogd个样本去恢复, 而在文献[20] 中, 样本数的阶降为R0d, 这是因为施加了额外的“spikiness” 性质, 这是对低秩矩阵奇异值向量的特定条件. 文献[21] 利用有限维Schattenp- 空间之间恒等映射的Gelfand 宽度, 并证明对低秩矩阵恢复问题, 其最坏情况函数下界的阶为R0d/n. 本文的结果适用于更一般的多响应回归模型且不需要求未知参数矩阵是方阵, 在协变量带有测量误差的情形下, 建立的极小极大下界仍然达到了上述针对干净数据的阶. 这一结果进一步表明即使在加性变量误差模型中, 依然不需要更多的样本以实现收敛率最优的估计.

(iii)极小极大最优性一般通过两个方面进行分析,也就是关于最坏情况函数(见(6)式) 的信息理论下界和统计误差上界. 信息理论重点关注下界的理论性质, 定理3.1 建立的下界阶为(见(13) 式). 在统计层面, 上界的推导通常依赖于对特定估计量的构造性分析并进行数值模拟验证. 对加性误差模型而言, 已在另一篇文章中通过构造一个形式为∈arg minΘ{L(Θ)+λ|||Θ|||∗} 的纠偏估计量, 其中L(Θ) 表示模型拟合的纠偏损失函数,λ> 0 表示施加低秩约束的正则化参数, 从而得到了上界, 见文献[36] 的定理1. 注意当选择正则化参数时, 本文的下界(13)与文献[36] 的定理1 的上界同阶. 与此同时, 文献[36] 通过数值模拟验证了上界阶的合理性, 这也从另一方面验证了本文关于下界的极小极大最优收敛速率.

4 结论

本文关注了高维多响应变量误差模型中低秩估计问题的信息理论极限. 借助信息理论和统计学的技巧, 针对一类特殊的矩阵集合, 建立了以平方Frobenius 损失函数形式给出的极小极大下界. 结果表明在测量误差情形下, 估计的难度并没有增加, 仍然只需要与干净数据情形时相当的样本即可实现相合估计.

需要注意的是这一工作仍然存在一些局限性. 首先对模型施加的独立同分布Gaussian 假设(见假设2.1 式). Gaussian 随机矩阵在研究者们可以设计实验的领域,如信号处理和压缩感知[30], 具有特殊的意义和广泛的应用. 然而, 独立Gaussian 假设在其它统计领域中仍有一定的局限性, 尽管零均值假设很容易通过列归一化被满足. 下一步研究可以将现有结果推广至更一般的协变量类中, 如带有非对角元的次- Gaussian矩阵, 或者其它误差模型, 如乘性或相关噪音. 此外, 本文只考虑了一类相对局限的目标参数集(见(4) 式), 其与Stiefel 流形具有某种相似结构. 这一相似性在推导KL 散度以及构造合适的packing 集合中至关重要. Stiefel 流形上packing 集合的丰富性极大促进了定理3.1 的证明. 对其它矩阵类的分析将是未来一个很有前景的研究方向, 关键在于对KL 散度更精准的估计和适当packing 集合的构寻找.