一類高維多響應變量誤差模型的極小極大下界

李欣, 吳東亞

(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, 有

根據制粒原料不同的力學特性，考慮到物料在喂料過程中的規律性和?？捉Y構的軸對稱性，可以將?？字械奈锪蟿澐譃闄M觀各向同性材料和各向同性材料。分別如圖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 集合的構尋找.