跳转至

Understanding best subset selection: A tale of two c(omplex)ities

作者: Saptarshi Roy, Ambuj Tewari, Ziwei Zhu
来源: Electronic Journal of Statistics
主题: 高维统计 / 随机矩阵
相关性: 6/10
链接: 期刊页 · arXiv

一、领域脉络与小综述

这个方向是什么

高维稀疏回归中的模型选择一致性（model selection consistency）问题：给定一个线性模型 \(y = X\beta + \varepsilon\)，其中 \(p \gg n\)，真实回归系数 \(\beta\) 仅有 \(s\) 个非零分量（\(s \ll n\)），问何种条件下，最佳子集选择（BSS）能够以趋于1的概率精确恢复真实活跃变量集 \(S_0\)。这个子方向是统计模型选择理论中最原始也最困难的问题之一——它的成熟度在理论刻画上远落后于Lasso等凸松弛方法，直到近年计算突破才重新获得系统性的理论关注。

发展脉络

  1. 奠基工作（1970s–2008）：经典信息准则（AIC, BIC, Cp）使用 \(\ell_0\) 范数作为惩罚项，但其计算在 \(p > n\) 时被认为不可行。早期理论结果集中在它们的大样本性质（Barron et al., 1999; Zhang & Zhang, 2012），但未处理高维相关设计。与此同时，Lasso 被提出并迅速获得完整的理论：Bickel, Ritov & Tsybakov (2008) 建立了 Lasso 在预测风险上的 oracle 不等式，依赖受限特征值条件（restricted eigenvalue, RE）；Geer & Bühlmann (2009) 进一步证实 RE 或稍弱的兼容性条件足以保证 Lasso 的 oracle 性质。然而，Lasso 的模型选择一致性需要更强的强不可表示条件（strong irrepresentable condition, Zhao & Yu, 2006; Zhang & Huang, 2008）。

  2. 非凸惩罚的兴起（2010–2015）：为克服 Lasso 的偏差和不可表示条件的限制，Zhang (2010) 提出 MC+（MCP 惩罚），Zhang & Zhang (2011) 给出凹正则化的统一理论，证明在稀疏 Riesz 条件下，非凸惩罚的全局解可恢复真实模型，且计算可通过局部优化实现。这一阶段的关键认知是：\(\ell_0\) 正则化虽然统计上最优，但计算上 NP-hard（Foster et al., 2015; Zhang et al., 2014），而凸松弛（Lasso）的模型选择一致性受限，非凸方法则介于两者之间。

  3. BSS 的计算突破（2015–2020）：Bertsimas, King & Mazumder (2016) 利用混合整数优化（MIO）将 BSS 在 \(p\) 达数百、\(n\) 达数千的规模上求解到可证明最优；Bertsimas & Parys (2020) 进一步扩展至 \(p\) 达数十万，并观察到相位转移现象；Zhu et al. (2020) 提出 ABESS 算法，通过序列拼接（splicing）在多项式时间内以高概率获得全局最优解。这些进展彻底改变了“BSS 不可行”的共识，驱动了其统计性质的重新审视。

  4. BSS 的模型选择理论（2020–至今）：Guo, Zhu & Fan (2020) 首次系统研究 BSS 的模型一致性，引入可识别性边际（identifiability margin）概念——一个与设计矩阵谱性质无关、仅依赖模型辨识力的度量。他们证明：该条件几乎必要且充分，且可传播到任何“近最佳子集”（即 RSS 接近最优的子集）。这揭示了 BSS 对设计依赖的稳健性，与 Lasso 的 RE/不可表示条件形成鲜明对比。Roy, Tewari & Zhu (2022) 在独立高斯设计和弱异质信号下进一步证明 BSS 的信息论最优性（精确常数）。本文则在此基础上，将充要条件分解为三个可解释量——可识别性边际、残差化信号的复杂度、虚假投影的复杂度——并部分延伸至广义线性模型（GLM）。

子线索聚类

  • 线索 A：BSS 的统计理论
    — Guo et al. (2020)：提出可识别性边际，证明其充分且近乎必要。
    — Roy et al. (2022)：独立设计下 BSS 的信息论最优精确常数。
    — 本文：引入残差化信号与虚假投影复杂度，建立完整充要条件体系。

  • 线索 B：BSS 的计算算法
    — Bertsimas et al. (2016, 2020)：MIO 求解，达到可证明最优。
    — Zhu et al. (2020, 2021)：ABESS 算法，多项式时间概率最优。
    — Jain et al. (2014)：迭代硬阈值（IHT）族近似求解 BSS。
    — She et al. (2023)：基于分位数的慢杀算法，实现模型一致性。

  • 线索 C：凸/非凸方法的条件与比较
    — Bickel et al. (2008)：Lasso 预测的受限特征值条件。
    — Geer & Bühlmann (2009)：兼容性条件。
    — Zhang (2010)、Zhang & Zhang (2011)：MCP 和非凸惩罚的稀疏 Riesz 条件。
    — Foster et al. (2015)：变量选择在多项式时间内的计算困难性结果（NP \(\not\subset\) P/poly 假设下）。
    — Zhang et al. (2014)：多项式时间算法与最优算法在 ill-conditioned 设计下的 minimax 预测风险差距。

  • 线索 D：经验比较与算法推荐
    — Hastie, Tibshirani & Tibshirani (2020)：通过大量模拟比较 BSS、前向逐步选择与 Lasso，发现 BSS 在高信噪比下更优，低信噪比下 Lasso 更优。

这个方向在追问的核心问题

  1. 设计矩阵的何种性质真正控制 BSS 的模型选择？ 是受限特征值、不可表示条件，还是更纯净的“可识别性边际”？
  2. BSS 的理论最优性（信息论下界）与计算可实现性之间的 gap 有多大？ 已知多项式时间算法（如 Lasso）需要强条件，而 BSS（尽管 NP-hard）在更弱条件下一致——这个 gap 的本质是什么？
  3. 如何将 BSS 的理论推广到广义线性模型、多响应、异方差等场景？ 目前 GLM 的结果仅部分完成。

⚠️ 作者的 framing

作者的说法：本文的出发点是“Guo et al. (2020) 仅用可识别性边际刻画了 BSS 的模型一致性，但该边际本身没有揭示设计几何的哪些具体方面驱动了选择性”。本文通过将 RSS 差分解构，发现残差化信号的复杂度（complexity of residualized signals）和虚假投影的复杂度（complexity of spurious projections）同样必要——三者一起构成完整的充要条件。

被淡化或回避的竞争路线： - 作者几乎不讨论 Lasso 等凸方法的结果（除了一两句关于 RE 和不可表示条件的提及），也未将本文的三个量直接与 Lasso 的条件（如不可表示系数）作比较。实际上，这些新量是否比 RE/不可表示条件更弱或更强，尚不明确。 - 作者回避了计算复杂性的角度：虽然 BSS 的理论条件很弱，但其计算代价（指数时间）在现实中仍是障碍。本文的条件能否被任何多项式时间算法利用？作者并未讨论。

明显该引但没引的工作： - 没有引用 Foster & George (1994) 关于风险的最小化与模型选择一致性的早期讨论（可能被认为非高维）。 - 没有引用 Chandrasekaran et al. (2012) 关于凸几何与信号恢复的锥体条件（可能与“虚假投影”复杂度有联系，但未被探讨）。 - 对于 GLM 部分，没有引用 van de Geer (2008) 关于高维 GLM 的 Lasso 理论（其使用不同的条件，如最大幅值条件）。

张力

未见明显对立的引用。各工作基本在各自设定下自洽，未出现同一问题在同等条件下结论相反的情况。但 BSS 的稳健性与 Lasso 的强条件之间的对比，本身构成了一个难以调和的“统计–计算”张力。

二、最核心、最简单的例子 / 数学问题

第一步：符号、模型、可观测数据

符号（按出现顺序定义）： - \(n\)：样本量；\(p\)：变量个数（特征维度）。 - \(y \in \mathbb{R}^n\)：可观测响应向量。 - \(X \in \mathbb{R}^{n \times p}\)：设计矩阵，列为特征变量。 - \(\beta \in \mathbb{R}^p\)：真实回归系数（参数/ estimand）。 - \(S_0 = \{j: \beta_j \neq 0\}\)：真实活跃变量集，大小 \(|S_0| = s\)（假设已知，且 \(s < n\)）。 - \(D\)：任意候选子集，大小 \(|D| = s\)（因为 BSS 的搜索限制在大小为 \(s\) 的子集上）。 - \(X_D\)：\(X\) 中列的索引为 \(D\) 的子矩阵（\(n \times s\)）。 - \(\widehat{\beta}_D\)：最小二乘估计 \(\arg\min_{\beta \in \mathbb{R}^s} \|y - X_D \beta\|^2\)。 - \(\mathsf{RSS}(D) = \|y - X_D \widehat{\beta}_D\|^2\)：子集 \(D\) 的残差平方和。 - \(D^*\)：满足 \(|D^*|=s\) 且使 \(\mathsf{RSS}(D^*)\) 最小的子集，即 BSS 的解。 - \(\Delta(D) = \mathsf{RSS}(D) - \mathsf{RSS}(S_0)\)：候选子集相对于真实子集的 RSS 差。BSS 正确当且仅当对任意 \(D \neq S_0\) 有 \(\Delta(D) > 0\)。

模型： - 线性模型：\(y = X\beta + \varepsilon\)，其中各元素 \(\varepsilon_i\) 独立同分布，均值为 0，子高斯（sub-Gaussian）方差 \(\sigma^2\)。 - 设计矩阵 \(X\) 可以是固定的也可以是随机的；若随机，假设行向量独立同分布，且子高斯行。无分布假设。 - 真实系数 \(\beta\) 的支撑 \(S_0\) 大小为 \(s\)；\(\beta_{S_0}\) 可以是任意非零向量（幅值可大可小）。

可观测数据与不可观测量： - 可观测：\((y, X)\)，即响应和全部设计矩阵。 - 不可直接观测：噪声 \(\varepsilon\)、真实支撑 \(S_0\)、真实系数 \(\beta_{S_0}\)（需要通过假设识别）。 - BSS 试图通过最小化 RSS 来估计 \(S_0\)。

第二步：最小内核

最简特例：\(p=2\)，真模型仅含变量 1（即 \(S_0 = \{1\}\)，\(s=1\)）。设计矩阵 \(X = [x_1, x_2]\)，其中 \(x_1, x_2 \in \mathbb{R}^n\)。假设 \(x_1, x_2\) 标准化（均值为 0，范数为 \(\sqrt{n}\)），并且 \(\rho = x_1^\top x_2 / n\) 为样本相关系数。真实系数 \(\beta_1 \neq 0\)，\(x_2\) 的系数为 0。

在这个特例下，BSS 需要比较两个候选： - \(D=\{1\}\)：RSS({1}) = \(\|y - \widehat{\beta}_1 x_1\|^2\)，其中 \(\widehat{\beta}_1 = x_1^\top y / n\)。 - \(D=\{2\}\)：RSS({2}) = \(\|y - \widehat{\beta}_2 x_2\|^2\)，其中 \(\widehat{\beta}_2 = x_2^\top y / n\)。

BSS 正确当且仅当 RSS({1}) < RSS({2})。

现在，我们可以将 RSS 差分解。记真实模型 \(y = \beta_1 x_1 + \varepsilon\)。那么：

\[\widehat{\beta}_2 = \frac{x_2^\top (\beta_1 x_1 + \varepsilon)}{n} = \beta_1 \rho + \frac{x_2^\top \varepsilon}{n}.\]
而 \(\widehat{\beta}_1 = \beta_1 + x_1^\top \varepsilon / n\)。

经过代数运算（可以跳过细节），关键发现是：

\[\Delta(\{2\}) = \mathsf{RSS}(\{2\}) - \mathsf{RSS}(S_0) = \text{(identifiability margin)} - \text{(噪声项)} + \text{(投影效应)}.\]

在这里： - 可识别性边际（identifiability margin）本质上是 \(\beta_1^2 (1 - \rho^2)\)——即信号部分在去除 \(x_2\) 对 \(x_1\) 线性依赖后的残留强度。若 \(\rho\) 接近 1，这个边际很小，难以区分变量 1 和变量 2。 - 残差化信号的复杂度（complexity of residualized signals）：对变量 2，“残差化信号”指将 \(x_2\) 投影到 \(x_1\) 正交补后剩余分量 \(x_{2\cdot1} = x_2 - \rho x_1\)。这个分量的范数（或更一般地，其与噪声的交互）会影响随机项的大小。在本特例中，其复杂度就是 \(\|x_{2\cdot1}\|^2 / n = 1 - \rho^2\)。 - 虚假投影的复杂度（complexity of spurious projections）：投影算子 \(P_1 = x_1 x_1^\top / n\) 作用于随机噪声的范数 \(\|P_1 \varepsilon\|^2\) 的期望，反映变量 1 的投影对噪声的“放大”。在本特例中，它是 \(1/n\) 阶的（因为 rank 1 投影的迹为 1）。

这个最小内核说明：即使只有一个错误变量，BSS 的判决不仅依赖信号强度（通过可识别性边际），还依赖设计矩阵的几何如何与噪声交互（通过两个复杂度量）。一般情形下，对于任意大小为 s 的子集 D，\(\Delta(D)\) 可以分解为三个对应项的和。本文的核心就是：这个分解在全一般性下依然成立，并且这三项完全刻画了 BSS 成功的充要条件。

三、这篇论文做了什么

三句话

  1. 研究了高维稀疏线性回归中最佳子集选择（BSS）的模型一致性，发现其充要条件依赖于三个量：可识别性边际、残差化信号的复杂度、虚假投影的复杂度。
  2. 核心工具是 RSS 差的精确分解（将 \(\Delta(D)\) 分解为定常信号项和随机性项，随机性项由两个复杂度度量控制的浓度不等式控制），以及 sub-Gaussian 浓度不等式（Hanson-Wright、Talagrand 复杂性）。
  3. 主要结论是：只要可识别性边际大于一个由两个复杂度量决定的阈值，BSS 即以高概率正确恢复；反之，若条件不满足，则存在设计使 BSS 失败。该充要条件也部分推广至高维稀疏广义线性模型。

关键设定与假设

完整设定（在符号基础上补充）： - 真实稀疏度 \(s\) 已知。 - 噪声 \(\varepsilon\) 是 sub-Gaussian 向量，方差参数 \(\sigma^2\)。 - 设计矩阵 \(X\) 的每列已标准化（\(\|x_j\|^2 = n\)），行独立且 sub-Gaussian，或固定设计满足某些谱条件。 - 真实系数 \(\beta_{S_0}\) 的最小幅值 \(\min_{j\in S_0} |\beta_j|\) 需足够大（具体由定理中的阈值控制）。

三个核心量的正式定义（基于原文，此处简述）： 1. 可识别性边际 \(\gamma_{\min}(S_0)\)：对于候选集 \(D \neq S_0\)，测量在设计 \(X\) 下“用 \(D\) 模仿 \(S_0\)”的最小误差。定义为

\[\gamma_{\min}(S_0) = \min_{D \neq S_0, |D|=s} \frac{1}{n} \|X_{S_0}\beta_{S_0} - X_D (X_D^\top X_D)^{-1} X_D^\top X_{S_0}\beta_{S_0}\|^2.\]
直觉上，它是没有被任何大小为 \(s\) 的错误子集“模拟掉”的最小信号能量。 2. 残差化信号的复杂度 \(C_{\mathrm{res}}\)：衡量 \(X\) 的列向量投影到 \(X_{S_0}\) 正交补后的最大范数，定义为
\[C_{\mathrm{res}} = \max_{D: |D|=s, D \neq S_0} \frac{1}{\sqrt{n}} \| (I - P_{S_0}) X_D \widehat{\beta}_{D; \mathrm{LS}}(S_0) \|,\]
其中 \(\widehat{\beta}_{D; \mathrm{LS}}(S_0)\) 是用 \(X_D\) 拟合信号 \(X_{S_0}\beta_{S_0}\) 的系数。它刻画了信号被错误子集“残余”后的复杂度。 3. 虚假投影的复杂度 \(C_{\mathrm{proj}}\)：衡量投影到大小为 \(s\) 的任意子集上的噪声方差的上确界，定义为
\[C_{\mathrm{proj}} = \max_{D: |D|=s} \frac{1}{\sqrt{n}} \| P_D \varepsilon \|_{\psi_2}\]
或其期望形式（依赖于噪声的分布）。

相比 Guo et al. (2020) 的差异： - Guo et al. 仅用可识别性边际一个量给出充分条件，并证明其近乎必要。本文将其分解为三个量，并指出：仅靠可识别性边际不足以刻画必要性（因为即使边际很大，如果 \(C_{\mathrm{res}}\) 或 \(C_{\mathrm{proj}}\) 很大，仍可能失败）。因此本文的条件是严格意义上充要的。

相比 Lasso 等方法的条件： - Lasso 需要 RE 或不可表示条件，涉及整个设计矩阵的稀疏特征值。BSS 的条件仅涉及大小为 \(s\) 的子集上的量，不涉及 \(p\) 的显式依赖。这正是 BSS “对设计依赖稳健”的体现——因为 BSS 只比较大小为 \(s\) 的子集，不需要控制所有 \((p-s)\) 个变量的交互。

主要结果

定理 1（充分性，线性模型）：假设存在常数 \(\delta, \eta > 0\)，使得

\[\gamma_{\min}(S_0) > 4C_{\mathrm{res}} C_{\mathrm{proj}} \sqrt{\frac{\log p}{n}} + \eta \cdot \text{(其他因子)}.\]
则 BSS 以概率至少 \(1 - o(1)\) 恢复 \(S_0\)。这里右边项由两个复杂度量的乘积乘以一个 \(\log p / n\) 阶因子决定。直觉上，只要可识别性边际大于随机误差（由残差化信号和虚假投影的交互决定），BSS 就能成功。

定理 2（必要性，线性模型）：若 \(\gamma_{\min}(S_0)\) 小于某个由 \(C_{\mathrm{res}}, C_{\mathrm{proj}}\) 决定的阈值，则存在设计矩阵（满足正则条件）使得 BSS 以正概率失败。即该条件在不被进一步约束时也是几乎必要的。

定理 3（GLM 的充分性）：假设广义线性模型的依赖函数（如 logistic 链接）满足 Lipschitz 和单调性条件，且可识别性边际和两个复杂度量在“线性预测”空间上定义。则在类似的界下，BSS（以 logistic 负对数似然代替 RSS）能以高概率恢复真实支撑。

解决的技术难点： - 如何将 \(\Delta(D)\) 分解为可控的三部分？关键在于：\(\Delta(D) = \| \mu_{S_0} - \widehat{\mu}_D \|^2\)，其中 \(\mu_{S_0} = X_{S_0}\beta_{S_0}\)，\(\widehat{\mu}_D = X_D \widehat{\beta}_D\)。而 \(\widehat{\mu}_D\) 可写成 \(P_D y = P_D\mu_{S_0} + P_D\varepsilon\)。于是

\[\Delta(D) = \|\mu_{S_0} - P_D \mu_{S_0}\|^2 + \|P_D\varepsilon\|^2 - 2 (\mu_{S_0} - P_D\mu_{S_0})^\top P_D \varepsilon.\]
第一项是可识别性边际的体现（经适当变换），第二项是虚假投影的噪声项，第三项是交叉项，由残差化信号（\(\mu_{S_0} - P_D\mu_{S_0}\)）与噪声的投影（\(P_D\varepsilon\)）的内积控制。这两个量的复杂度则出现在浓度界中。

证明路线与技术技巧

整体路线（3–5 步）：

  1. RSS 差分解构：对任意候选 \(D\)，将 \(\Delta(D)\) 分解为信号项 \(+\) 噪声项 \(+\) 交叉项。
  2. 下界信号项：利用线性代数证明 \(\|\mu_{S_0} - P_D \mu_{S_0}\|^2 \ge n \cdot \gamma_{\min}(S_0)\)，对 \(D \neq S_0\) 一致成立。
  3. 上界交叉项与噪声项：使用浓度不等式对交叉项和噪声项进行均匀上界。交叉项的上界依赖 \(C_{\mathrm{res}}\)（控制 \(\|\mu_{S_0} - P_D \mu_{S_0}\|\) 的范数）和 \(C_{\mathrm{proj}}\)（控制 \(\|P_D\varepsilon\|\) 的 norm）。两者乘积的上界通过 Hanson-Wright 不等式或 Talagrand’s 复杂性的 chaining 来获得 \(\sqrt{\log p / n}\) 率的界。
  4. 联合边界：对 \(\Delta(D)\) 取所有 \(D \neq S_0\) 的最小值，将信号项的下界与随机项的上界比较。若信号项大于随机项的上确界，则 BSS 正确。
  5. 必要性的构造：构造一个反例设计，使得当可识别性边际小于阈值时，存在某个错误子集 \(D\) 使得 \(\Delta(D) < 0\) 以正概率发生。

关键跳跃点： - 证明交叉项能通过 \(C_{\mathrm{res}} \cdot \|P_D\varepsilon\|\) 控制，需要用到 Cauchy-Schwarz 以及一个事实：\(\mu_{S_0} - P_D\mu_{S_0}\) 正交于 \(X_D\) 的列空间，但 \(P_D\varepsilon\) 位于该空间内，因此内积可以被优化。 - 为了得到对所有 \(D\) 一致的界，需要 chaining 或覆盖数参数：对大小为 \(s\) 的子集族，其数量为 \(\binom{p}{s}\)，指数级大。使用高斯过程的极大值不等式，将 \(\|P_D\varepsilon\|\) 的极大值与 \(s \cdot \log(p)\) 关联，利用 sub-Gaussian 的 2-范数浓度（Hanson-Wright 不等式）或 Vershynin 的引理。

技术技巧点名： - Hanson-Wright 不等式：用于控制 \(\|P_D\varepsilon\|^2\)（二次型）的偏差，给出 \(\|P_D\varepsilon\|^2\) 偏离期望的上界，概率指数衰减。 - Talagrand’s 复杂性 / 高斯过程的 chaining：用在控制 \(C_{\mathrm{proj}}\) 的期望上，即 \(\mathbb{E} \max_{D} \|P_D\varepsilon\|\)，将其与核心的“高斯宽度”联系起来。 - Suprema of chaos processes（Krahmer et al., 2014）：用于处理残差化信号与噪声的交叉项的集中性。 - 分位数 / 截断技巧：在处理 sub-Gaussian 而非高斯分布时，使用 Adamczak (2015) 的依赖方差形式的 Hanson-Wright 改进。 - 对于 GLM 部分：使用经验过程（empirical process）和 M-估计的经典工具（如 Lipschitz loss 的局部收敛性），结合线性预测空间的近似。

真实例子与应用

本文为纯理论，无实证例子。 文中没有模拟或数据案例；所有结果都是关于充要条件的渐近定理。仅在引言末尾提及“使用 ABESS 作为 BSS 的快速计算代理”用于模拟，但该模拟（如果有）未在此文中展示（可能引用之前的实验）。

🔎 结论是否比证明窄

  • 充分性条件的证明依赖于对信号项的下界在所有错误子集上的一致下界 \(\gamma_{\min}(S_0)\)。这个下界是紧的，但需要假设 \(\beta_{S_0}\) 的信号幅值足够大，以避免“弱信号”情形。如果信号很弱，即使可识别性边际为正，也可能无法区分噪声主导的 RSS 差。定理陈述中明确要求最小信号强度（通过 \(\gamma_{\min}\) 隐式包含），这个条件可能比实际需要的更严格——但它已经被证明是紧的（必要性部分）。
  • GLM 的推广被明确标记为“部分”（partial）。作者在文末指出，他们仅考虑了 logit 等单调链接函数，且假定了设计的有界性。对于更一般的 GLM（如 Poisson、Gamma 链接），条件是否仍成立未被证明，是开放问题。
  • 必要性的证明是构造性的：它展示了存在一类设计使得条件松动时 BSS 失败。但在随机设计下，这类设计是否典型？未讨论。结论并不意味着实际中失败普遍发生。

四、开放问题（扎根具体语句）

  1. 未知真实稀疏度 \(s\) 的情形：本文假设 \(s\) 已知，但实际中需估计。作者在定理中明确限制 \(|D|=s\)。如何将充要条件扩展到需要同时选择 \(s\) 的设定（如使用 BIC 型准则）？扎根：文末未直接讨论 \(s\) 未知的情况，但所有结果依赖 \(s\) 已知。

  2. GLM 的完全推广：本文的充分性只涵盖了一类 GLM（logistic 型）。对于 Poisson 回归、负二项回归等，其对数似然函数不是 Lipschitz 的，需要不同的浓度工具。扎根：定理 3 的陈述之前注明“under certain conditions on the link function”，且引言末只称“partially extend”。

  3. 三个量的可计算性：\(C_{\mathrm{res}}\) 和 \(C_{\mathrm{proj}}\) 的定义涉及对子集的最大化（类似于 combinatorial complexity），本质上计算困难。是否存在可验证的替代条件（如某些谱条件）能间接保证它们有界？扎根：文中未提供闭合形式的等价条件，仅定义了量。

  4. 与计算复杂度的交互：本文的条件是否比 Lasso 的条件严格更弱？如果是，计算代价（指数时间）是否就是这个减弱的代价？作者在引言中提到“RE appears unavoidable for any polynomial-time method assuming standard conjecture (Zhang et al., 2014)”，但未将自己的条件与 RE 直接比较。扎根：引言第 2 页提及 “a condition which appears unavoidable for any polynomial-time method”，但本文的充分条件是否与 RE 耦合？未阐明。需要确认：BSS 的条件在多项式时间算法下是否也能达到？这可能是信息-计算 gap 的核心。

提示：欲确认第 4 点是否真 gap，建议阅读 Zhang et al. (2014) 以及 Foster et al. (2015) 的证明，看他们构造的硬实例中 BSS 的条件是否也失败。若 BSS 的条件仍然满足，则 gap 存在。

Maintained by 陈星宇 · Homepage · Source on GitHub

评论