A note on the minimax risk of sparse linear regression¶
作者: Yilin Guo, Shubhangi Ghosh, Haolei Weng, Arian Maleki
来源: Electronic Journal of Statistics
主题: 高维统计 / 随机矩阵
相关性: 8/10
机构绿灯: Columbia University(US News 前 50,免分进入精读)
链接: 期刊页 · arXiv
一、领域脉络与小综述¶
这个方向是什么¶
稀疏线性回归的极小极大风险研究,回答的是一个非常根本的问题:当我们假设真实回归系数 β 是 k-稀疏的(即最多 k 个非零分量),在观测数据 y = Xβ + z 下,无论使用何种估计器,均方误差 ∥β̂ − β∥₂² 的最坏情况(worst-case)下界是多少?这个问题的核心张力在于:率(rate) 层面的答案早已清楚——在稀疏线性回归中,极小极大率是 σ²·(k/n)·log(p/k),但常数(constant) 层面的精确刻画却长期悬而未决。本文正是在这个"率已知、常数未知"的缝隙中切入,试图回答:当 (k log(p/k))/n → 0 时,极小极大风险的渐近常数是否恰好等于 2?
这个子方向的成熟度处于"经典问题的新进展"阶段:它不涉及新的模型或新的估计器,而是对一个已有几十年历史的问题给出更精确的答案。其难度不在于概念的创新,而在于技术上的精细控制——如何在期望意义下(而非高概率意义下)同时获得常数精确的上界和下界。
发展脉络¶
奠基工作:率最优性的确立。 这一问题的现代研究起点可以追溯到 Donoho 和 Johnstone 在正交设计(orthogonal design,即 (1/n)XᵀX = I_p)下的工作 [16, 15, 24]。他们证明了在正交设计中,极小极大风险满足 R_F(X, Θ_k, σ) = (2 + o(1))σ²(k/n)log(p/k)。这个 2 的常数来源于一个基本事实:在正交设计中,稀疏估计问题退化为 p 个独立的单变量高斯均值估计问题,而每个非零坐标的估计误差下界是 2σ²/n·log(p/k)(这本质上是软阈值估计器在"几乎稀疏"情形下的偏差-方差权衡)。正交设计之所以关键,是因为它消除了设计矩阵相关性带来的复杂性,使得问题分解为独立的坐标估计。
主要进展:从正交到一般设计的跨越。 将正交设计的结果推广到一般设计矩阵并非易事。这里的关键障碍是:当设计矩阵 X 的列之间存在相关性时,不同坐标的估计误差不再独立,且稀疏结构的利用变得更加复杂。这一方向的代表性工作包括:
- Raskutti, Wainwright 和 Yu (2009) [18] 在 ℓq-ball(q ∈ [0,1])上建立了极小极大率,证明了率 σ²·(k/n)·log(p/k) 在一般设计下依然成立,但常数并未精确化。
- Candès 和 Davenport (2011) [22] 给出了一个不依赖于设计矩阵的下界,证明了无论设计矩阵如何、无论估计器如何,均方误差都存在一个下界,且这个下界与随机投影 + ℓ1 估计的上界几乎匹配。这个结果的意义在于:它表明压缩感知技术本质上无法被改进——但同样,常数并未精确化。
- Verzelen (2012) [36] 在超高维情形下研究了极小极大风险,发现了"elbow effect":当 (k log(p/k))/n 超过某个阈值时,风险会急剧增大。这个工作为本文提供了重要的下界技术基础(本文的 Theorem 2 直接引用了 [36] 的 Proposition 6.2)。
常数精确化的尝试:SLOPE 与高概率上界。 在率最优性确立之后,研究者的注意力转向常数的精确化。这里的关键进展来自:
- Bellec, Lecué 和 Tsybakov (2018) [3] 证明了 SLOPE 估计器在预测误差意义上达到常数精确的率,但结果是在高概率意义下(即对大多数设计矩阵成立),而非期望意义下。
- Su 和 Candès (2016) [32] 进一步证明了 SLOPE 的渐近极小最优性,同样是在高概率意义下。
- Bellec (2018) [2] 和 Bellec 与 Zhang (2021) [4] 引入了"噪声屏障"(noise barrier)的概念,揭示了凸估计器在稀疏回归中的固有局限,并提供了二阶 Stein 方法这一技术工具。
这些工作的共同特点是:它们证明了特定估计器(SLOPE、Lasso 等)在高概率意义下达到常数精确的上界,但未能回答期望意义下的极小极大风险是否恰好等于 2。高概率与期望之间的差距在于:高概率上界允许在概率极小的坏事件上付出任意大的代价,而期望上界要求对坏事件上的代价进行精细控制。
本文的位置。 本文填补的正是这个"高概率到期望"的鸿沟。作者证明:在各项同性高斯随机设计下,极小极大风险满足 R_R(Θ_k, σ) = (2 + o(1))σ²(k/n)log(p/k)。这个结果的关键贡献在于:(1) 将上界从高概率意义提升到期望意义;(2) 证明了下界在期望意义下也恰好是 2,从而完成了常数的精确刻画。值得注意的是,本文的证明策略结合了 [3] 和 [4] 的技术,但需要处理期望意义下的精细控制——这是本文技术上的核心难点。
子线索聚类¶
被引文献大致落在三条子线索上:
线索一:极小极大率的确定(2009-2012)。 代表工作:Raskutti-Wainwright-Yu [18]、Candès-Davenport [22]、Verzelen [36]。这条线索的核心贡献是确定了稀疏线性回归在一般设计下的极小极大率,并发现了超高位维下的相变现象。这条线索的局限在于:只关心率的阶,不关心常数。
线索二:常数精确的估计器构造(2014-2021)。 代表工作:Bellec-Lecué-Tsybakov [3]、Su-Candès [32]、Bellec [2]、Bellec-Zhang [4]、Feng-Zhang [7]。这条线索的核心贡献是构造了在高概率意义下达到常数精确的估计器(SLOPE、Lasso 的变体等),并发展了相应的分析工具(噪声屏障、二阶 Stein)。这条线索的局限在于:高概率意义下的结果无法直接转化为期望意义下的极小极大风险。
线索三:极小极大风险的常数精确刻画(本文)。 这条线索的目标是回答:期望意义下的极小极大风险常数是否恰好等于 2?本文是这条线索的第一个完整结果。
这个方向在追问的核心问题¶
- 期望意义下的极小极大常数是否等于 2? 这是本文直接回答的问题。在高概率意义下,SLOPE 和 Lasso 都达到常数 2,但期望意义下的答案需要更精细的分析。
- 一般设计矩阵下的常数是多少? 本文只处理了各项同性高斯设计。对于相关设计(如 Toeplitz 设计、有界相关性设计),常数是否仍然是 2?这是一个自然但尚未解决的问题。
- 非高斯噪声下的常数是否改变? 本文假设高斯噪声。对于亚高斯噪声或重尾噪声,常数是否会变化?
- 其他损失函数下的常数刻画。 本文关注 ℓ₂ 损失。对于 ℓ₁ 损失、预测损失或 Hamming 损失(变量选择),常数是否也有类似的精确刻画?
⚠️ 作者的 framing¶
作者在引言中将这个问题的缺口 frame 成:"尽管已有大量文献研究了稀疏线性回归的极小极大风险,但精确的常数刻画仍然缺失。" 作者特别指出,已有的上界结果(如 [3, 4])是在高概率意义下成立的,而极小极大风险的定义(期望意义下)要求对坏事件进行控制。因此,作者将本文的贡献定位为"将高概率结果提升为期望结果,从而完成常数 2 的精确刻画"。
值得注意的是,作者在引言中淡化了以下竞争路线:(1) 非凸方法(如 ℓ0 约束最小二乘)虽然在理论上可以达到更好的常数,但计算上不可行;(2) 贝叶斯方法虽然在某些先验下可以达到常数 2,但依赖于先验的选择。作者通过聚焦于"极小极大风险本身"而非"某个特定估计器的风险",巧妙地回避了这些竞争路线的比较。
值得研究者去查的问题:作者声称"这是第一个在期望意义下精确刻画稀疏回归极小极大常数的工作",但这一声称是否成立?[36] 的 Theorem 3 给出了期望意义下的率最优结果,但常数并未精确化。是否存在其他未引用的工作(如 Donoho 和 Johnstone 在正交设计之外的推广)已经部分回答了这个问题?建议检索 2015-2023 年间关于"minimax risk sparse regression exact constant"的文献,确认这一声称的准确性。
张力¶
被引文献之间未见明显对立结论。但存在一个微妙的张力:高概率上界与期望上界之间的差距。Bellec 等人 [3, 4] 的结果在高概率意义下达到常数 2,但他们的证明技术(基于噪声屏障和二阶 Stein)是否可以直接推广到期望意义?本文的回答是"可以,但需要额外的精细控制"——这暗示了高概率结果到期望结果的转化并非自动的,而是需要新的技术洞见。这一张力是本文的核心贡献点,也是读者理解本文技术难点的关键。
二、最核心、最简单的例子 / 数学问题¶
第一步:符号、模型、可观测数据¶
在展开本文的技术细节之前,先把记号一次性立清楚。本文的核心记号如下:
- 观测数据:{(xᵢ, yᵢ)}ᵢ₌₁ⁿ,其中 xᵢ ∈ ℝᵖ 是第 i 个样本的特征向量,yᵢ ∈ ℝ 是响应。将 n 个样本堆叠成矩阵形式:X ∈ ℝⁿˣᵖ(行是 xᵢᵀ),y ∈ ℝⁿ。
- 模型:y = Xβ + z,其中 β ∈ ℝᵖ 是未知的回归系数向量,z = (z₁, ..., zₙ)ᵀ ~ N(0, σ²Iₙ) 是高斯噪声。注意:X 是随机设计,其行独立同分布地服从 N(0, I_p)(各项同性高斯设计)。
- 参数空间:Θ_k = {β ∈ ℝᵖ : ∥β∥₀ ≤ k},即 k-稀疏向量集合。这里 ∥β∥₀ 表示 β 中非零分量的个数。k 是稀疏度参数,p 是维度,n 是样本量。本文的渐近框架是:k, p, n 同时趋于无穷,且满足 (k log(p/k))/n → 0。
- 目标量(estimand):极小极大风险 R_R(Θ_k, σ) := inf_{β̂} sup_{β∈Θ_k} E_β∥β̂ − β∥₂²。这里 inf 取遍所有估计器 β̂(可依赖于数据 (X, y)),sup 取遍所有 k-稀疏向量 β。注意:期望 E_β 同时关于 X 和 z 取(随机设计),这是与固定设计情形的关键区别。
- 辅助记号:g = (1/n)Xᵀz ∈ ℝᵖ,这是噪声与设计的交互项,在本文的分析中扮演核心角色。注意 g|X ~ N(0, σ²n⁻²XᵀX),其协方差矩阵与设计矩阵的 Gram 矩阵相关。
- 估计器:本文主要分析两个估计器——Lasso(ℓ₁ 惩罚最小二乘)和 MLE(ℓ₀ 约束最小二乘,即穷举所有 k-稀疏子集的最小二乘)。本文构造的聚合估计器 β̂ = β̂_L·1_A + β̂M·1{Aᶜ} 是二者的混合。
可观测与不可观测的区分:研究者实际能观测到的是 (X, y),即设计矩阵和响应向量。不可观测的是:真实系数 β、噪声 z、以及 β 的支撑集 S = supp(β)。本文的所有分析都建立在这些可观测量的分布性质之上。
第二步:最小内核¶
现在剥去所有技术细节,找出支撑整篇论文的那个最小内核。本文的核心数学问题可以归结为以下这个最简情形:
最简设定:考虑 p = 2, k = 1 的情形。即只有两个特征,真实系数 β 只有一个非零分量。假设 β = (β₁, 0)ᵀ,其中 β₁ ≠ 0。观测数据 y = Xβ + z,X 的行独立同分布地服从 N(0, I₂),z ~ N(0, σ²Iₙ)。
要回答的问题:在期望意义下,极小极大风险 inf_{β̂} sup_{β∈Θ₁} E∥β̂ − β∥₂² 的渐近常数是多少?
为什么这个例子是核心:虽然 p = 2 的情形过于简单(因为 p 不随 n 增长),但它揭示了本文所有技术的关键思想——稀疏估计的误差主要来自"错误选择支撑集"的事件。具体来说:
-
支撑集正确的情形:如果估计器正确识别了支撑集 S = {1},那么问题退化为一个一维高斯均值估计问题。此时最优估计器的均方误差是 σ²/n(即 Cramér-Rao 下界),这个量是 o((k/n)log(p/k)) 的,因为 log(p/k) → ∞。
-
支撑集错误的情形:如果估计器错误地选择了支撑集(例如选择了 {2} 而不是 {1}),那么估计误差会很大。但关键在于,这种错误事件的概率可以被控制。在 p = 2, k = 1 的情形下,错误选择支撑集的概率大约是 exp(−c·n·β₁²/σ²)(即信噪比足够大时,错误概率指数衰减)。
-
核心权衡:极小极大风险的常数 2 来源于一个更精细的权衡——即使支撑集选择正确,估计器在"几乎稀疏"方向上的误差也不是 σ²/n,而是 2σ²/n·log(p/k)。这个 2 的常数来源于软阈值估计器在"阈值附近"的偏差-方差权衡:当真实系数 β₁ 的量级恰好与噪声标准差 σ·√(log(p/k)/n) 相当时,软阈值估计器会以不可忽略的概率将 β₁ 收缩到 0,从而产生一个与 β₁² 相当的偏差项。这个偏差项与方差项 σ²/n·log(p/k) 的权衡,恰好给出了常数 2。
为什么这个权衡是本文的核心:本文的证明策略(Proposition 2)正是将 Lasso 的估计误差分解为两部分——支撑集正确时的"精细误差"(由软阈值近似控制)和支撑集错误时的"粗糙误差"(由稀疏特征值条件控制)。前者给出常数 2 的上界,后者给出可忽略的贡献。而下界(Theorem 5 的下界部分)则通过构造一个"最难估计"的稀疏向量 β*(其非零分量的大小恰好落在阈值附近),使得任何估计器都无法避免这个 2σ²/n·log(p/k) 的误差。
一句话总结本文的数学贡献:在各项同性高斯随机设计下,稀疏线性回归的极小极大风险满足 R_R(Θ_k, σ) = (2 + o(1))σ²(k/n)log(p/k),其中常数 2 来源于软阈值估计器在阈值附近的偏差-方差权衡,且这个常数在期望意义下是精确的。
三、这篇论文做了什么¶
三句话¶
- 研究了什么问题:在各项同性高斯随机设计下,稀疏线性回归的极小极大风险(期望意义下的均方误差)的渐近常数是否恰好等于 2?
- 核心工具 / 方法:构造了一个聚合估计器(Lasso 与 MLE 的混合),利用 Lasso 在"好事件"上的精细误差分析(基于二阶 Stein 方法和噪声屏障)和 MLE 在"坏事件"上的粗糙误差控制,证明了上界;同时利用信息论下界技术(Fano 不等式 / 假设检验)证明了下界。
- 主要结论:当 (k log(p/k))/n → 0 且 k/p → 0 时,极小极大风险满足 R_R(Θ_k, σ) = (2 + o(1))σ²(k/n)log(p/k),即常数精确等于 2。
关键设定与假设¶
本文的核心设定如下:
- 设计矩阵:X 的行独立同分布地服从 N(0, I_p)(各项同性高斯设计)。这是本文最关键的假设——它保证了设计矩阵的稀疏特征值条件以高概率成立,且 Gram 矩阵 (1/n)XᵀX 的谱性质可以被精确控制。
- 稀疏参数空间:Θ_k = {β ∈ ℝᵖ : ∥β∥₀ ≤ k},其中 k 可以随 n 增长,但满足 (k log(p/k))/n → 0。这个条件保证了稀疏回归问题是"可估计的"——当这个量趋于无穷时,极小极大率会急剧恶化(elbow effect,见 [36])。
- 噪声:z ~ N(0, σ²Iₙ),高斯噪声。σ 可以是未知的,但本文的证明假设 σ 已知(或可通过标准方法估计)。
- 渐近框架:k, p, n 同时趋于无穷,且满足 (k log(p/k))/n → 0 和 k/p → 0。前者是稀疏性条件,后者保证了 p 远大于 k(高维但稀疏)。
相比已有文献的放宽或强化: - 相比 [3](Bellec-Lecué-Tsybakov),本文的假设更弱——[3] 要求 (k log p)/n → 0,而本文只要求 (k log(p/k))/n → 0,后者在 k 远小于 p 时更宽松。 - 相比 [36](Verzelen),本文的结论更强——[36] 只给出了率的刻画,本文给出了常数的精确值。 - 相比 [32](Su-Candès),本文的证明是在期望意义下进行的,而非高概率意义下——这是本文的核心技术贡献。
主要结果¶
Theorem 5(本文主定理):在模型 (1) 中,假设 X 的行独立同分布地服从 N(0, I_p),且 k/p → 0、(k log(p/k))/n → 0。则极小极大风险满足:
R_R(Θ_k, σ) = (2 + o(1))σ²(k/n)log(p/k)。
这个结果包含两个方向: - 上界:存在一个估计器(本文构造的聚合估计器 β̂),使得 sup_{β∈Θ_k} E∥β̂ − β∥₂² ≤ (2 + o(1))σ²(k/n)log(p/k)。 - 下界:对任意估计器 β̂,sup_{β∈Θ_k} E∥β̂ − β∥₂² ≥ (2 − o(1))σ²(k/n)log(p/k)。
上界的证明路线(对应 Proposition 2 和 Section 4.2):
- 构造聚合估计器:β̂ = β̂_L·1_A + β̂M·1{Aᶜ},其中 A 是设计矩阵满足"好条件"的事件(即稀疏特征值条件成立且列范数有界)。在事件 A 上使用 Lasso,在事件 Aᶜ 上使用 MLE。
- Lasso 的精细误差分析:这是证明的核心。利用 [4] 的二阶 Stein 方法,将 Lasso 的估计误差分解为:
- 支撑集 S 上的误差:∑_{j∈S} (β̂_Lⱼ − βⱼ)²,这可以进一步分解为"偏差项"和"方差项"。
- 支撑集补集 Sᶜ 上的误差:∑_{j∈Sᶜ} β̂_Lⱼ²,这由 Lasso 的稀疏性(阈值效应)控制。
关键的技术步骤是证明:在事件 A 上,Lasso 的误差可以被一个"软阈值估计器"的误差所控制。这个软阈值估计器在支撑集 S 上的每个坐标独立地执行软阈值操作,其阈值恰好是 λ = (1+ε)σ√(2 log(p/k)/n)。这个分解使得误差的计算转化为一个一维积分问题,最终给出常数 2。
-
MLE 的粗糙误差控制:在事件 Aᶜ 上,MLE 的误差虽然可能很大,但事件 Aᶜ 的概率是指数小的(由稀疏特征值条件的概率界保证),因此对期望的贡献是 o((k/n)log(p/k))。
-
期望的分解:E∥β̂ − β∥² = E[∥β̂_L − β∥²·1_A] + E[∥β̂M − β∥²·1{Aᶜ}]。第一项由 Lasso 的精细分析控制,第二项由 MLE 的粗糙控制和事件 Aᶜ 的小概率控制。
下界的证明路线(对应 Section 4.1 和 Proposition 1):
-
构造最难的稀疏向量:选择一个 β* ∈ Θ_k,其非零分量的大小恰好落在"阈值附近",即 |β*ⱼ| ≈ σ√(log(p/k)/n)。这个选择使得任何估计器都无法区分"真实信号"和"噪声"。
-
利用 Fano 不等式 / 假设检验:将估计问题转化为一个假设检验问题。构造一组候选向量 {β⁽¹⁾, ..., β⁽ᴹ⁾} ⊂ Θ_k,使得这些向量两两之间的 Kullback-Leibler 散度有界,但它们的支撑集互不相同。Fano 不等式给出:如果候选向量的数量足够大,任何估计器的误差都至少是某个常数乘以 σ²(k/n)log(p/k)。
-
常数 2 的来源:下界的常数 2 来源于一个更精细的分析——不是简单地利用 Fano 不等式,而是利用"局部"的假设检验(即候选向量之间的差异只在一个坐标上)。这允许将下界分解为 k 个独立的一维问题,每个一维问题的下界是 2σ²/n·log(p/k),总和给出 2σ²(k/n)log(p/k)。
技术技巧点名:
- 二阶 Stein 方法([4]):用于计算 Lasso 估计器的期望误差。Stein 引理将期望 E[(β̂ⱼ − βⱼ)²] 转化为关于噪声分布的一个积分,使得计算可以在高斯假设下精确进行。
- 噪声屏障(noise barrier,[2]):用于刻画凸估计器在稀疏回归中的固有局限。本文利用这一概念来证明 Lasso 的误差下界,从而说明常数 2 是凸方法的极限。
- 稀疏特征值条件:用于控制设计矩阵的谱性质。在各项同性高斯设计下,这个条件以高概率成立,且常数可以被精确计算。
- 软阈值估计器的等价性:本文的关键洞察是,Lasso 在"好事件"上的行为与软阈值估计器几乎相同。这个等价性使得误差计算从高维问题退化为一维问题。
- 截断 / 局部化技术:在证明下界时,将全局的估计问题分解为局部的假设检验问题,每个局部问题只涉及一个坐标。这种"局部化"技术是高维统计下界证明的标准工具。
真实例子与应用¶
本文为纯理论论文,无真实数据例子或模拟实验。 论文的结构是:引言 → 记号与设定 → 主定理 → 上界证明 → 下界证明 → 附录(技术引理)。没有任何数值实验或数据应用。
🔎 结论是否比证明窄¶
是的,存在几处值得注意的"证明窄于结论"的地方:
-
上界仅对聚合估计器证明,而非对 Lasso 本身:Theorem 5 的上界是通过构造聚合估计器 β̂ = β̂_L·1_A + β̂M·1{Aᶜ} 证明的。在事件 A 上使用 Lasso,在事件 Aᶜ 上使用 MLE。这意味着论文并没有证明 Lasso 本身 在期望意义下达到常数 2,而是证明了一个"知道何时使用 Lasso、何时使用 MLE"的估计器达到常数 2。虽然事件 A 的概率趋于 1,但 Lasso 在事件 Aᶜ 上的行为并未被直接控制。作者在 Section 4.2 中暗示"Lasso 本身也可能达到这个常数",但并未给出严格证明。
-
下界仅对各项同性高斯设计证明:Theorem 5 的下界依赖于各项同性高斯设计的特殊结构(特别是稀疏特征值条件的精确常数)。对于一般的高斯设计(如相关设计),下界的常数是否仍然是 2 并未被证明。作者在结论部分提到"推广到相关设计是一个有趣的问题",但并未给出任何具体结果。
-
期望的收敛速度未明确:Theorem 5 的陈述是 R_R(Θ_k, σ) = (2 + o(1))σ²(k/n)log(p/k),但 o(1) 的收敛速度没有明确给出。从证明过程看,上界的收敛速度至少是 (log(p/k))⁻¹/² 的量级(由 Lasso 的偏差项控制),但作者没有明确陈述这一点。
-
k 的增长速度限制:虽然论文假设 (k log(p/k))/n → 0,但证明过程中可能隐含了更强的条件(如 k 不能增长太快)。作者在附录中给出了一些技术条件,但主定理的陈述中没有明确列出这些条件。
四、开放问题¶
以下问题均扎根于本文的具体陈述或证明中的缝隙,供研究者自行判断其价值与可行性:
-
Lasso 本身是否在期望意义下达到常数 2? 本文的上界是通过聚合估计器证明的,而非 Lasso 本身。虽然作者暗示 Lasso 可能也达到这个常数,但并未给出严格证明。要确认这一点,需要直接分析 Lasso 在事件 Aᶜ 上的期望误差,这可能需要更精细的尾部概率控制。(扎根于 Section 4.2 的聚合估计器构造。)
-
相关设计下的常数是否仍然是 2? 本文只处理了各项同性高斯设计。对于相关设计(如 Toeplitz 设计、有界相关性设计),下界的常数是否仍然是 2?这需要重新分析稀疏特征值条件的常数,以及噪声屏障在相关设计下的行为。(扎根于 Theorem 5 的设定和 Section 2.3 对相关设计的讨论。)
-
非高斯噪声下的常数是否改变? 本文假设高斯噪声。对于亚高斯噪声或重尾噪声,常数 2 是否仍然成立?这需要重新计算 Stein 方法中的积分,以及噪声屏障的刻画。(扎根于模型 (1) 的高斯噪声假设。)
-
其他损失函数下的常数刻画。 本文关注 ℓ₂ 损失。对于 ℓ₁ 损失、预测损失或 Hamming 损失(变量选择),常数是否也有类似的精确刻画?特别是 Hamming 损失下的变量选择问题,其极小极大常数可能与 ℓ₂ 损失下的常数有本质区别。(扎根于 Section 2 对 ℓq 损失和 Hamming 损失的文献综述。)
-
o(1) 的收敛速度是否可以改进? 本文的 o(1) 项没有明确给出收敛速度。从证明过程看,上界的收敛速度至少是 (log(p/k))⁻¹/² 的量级,但这是否是最优的?是否存在更快的收敛速度?(扎根于 Theorem 5 的陈述和证明过程。)
-
有限样本下的非渐近界。 本文的结果是渐近的。是否存在有限样本下的非渐近界,使得常数 2 在有限样本下也近似成立?这需要更精细的尾部概率控制,可能涉及 Berry-Esseen 类型的界。(扎根于 Theorem 5 的渐近陈述。)
提示:要确认上述问题是否是真 gap,建议去读以下近期文献的引言部分(约 5 篇):Bellec-Lecué-Tsybakov (2018)、Su-Candès (2016)、Verzelen (2012)、Bellec-Zhang (2021)、以及 2020 年后关于"minimax risk sparse regression"的最新工作。如果这些文献的引言都指向同一个未解决问题,那很可能是一个共识性的 gap;如果它们各说各话,那可能是一个尚待厘清的领域。
Maintained by 陈星宇 · Homepage · Source on GitHub