跳转至

Algorithms for adaptive and heteroskedastic linear regression at the computational threshold

作者: Spencer Compton, Tselil Schramm
主题: 高维统计 / 随机矩阵
相关性: 8/10
链接: https://arxiv.org/abs/2608.18402

一、领域脉络与小综述

  • 这个方向是什么：本文研究的核心问题是有限样本线性回归在标签噪声分布未知且异质时的估计问题。具体分为两个模型：(1) 异方差线性回归：每个样本的噪声方差 \(\sigma_i^2\) 未知且可能不同，只知道其中至少 \(m\) 个样本的方差不超过 1；(2) 自适应线性回归：噪声独立同分布于某个未知的对称分布 \(p\)，目标是在不知道 \(p\) 的情况下，达到与"知道 \(p\) 的最优估计器"相当的误差。该方向处于统计与计算交叉的前沿：它不仅要刻画统计上可达到的最优误差（minimax rate），还要回答"在多项式时间内能达到什么误差"这一计算问题，即信息-计算间隙（information-computation gap）的存在性。

  • 发展脉络（history）：

    • 奠基工作：异方差问题的系统性研究始于 Chierichetti, Dasgupta, Kumar, Lattanzi [CDKL14] 对异方差均值估计的探讨，他们提出了"Subset-of-Signals"模型：至少 \(m\) 个样本的方差有界，其余样本方差任意大。后续工作（如 [Xia19, YL20, PJL22, DLLZ23, Lou25]）研究了中位数、截断、众数等估计器在该模型下的表现。Liang 和 Yuan [LY20] 提出了一个可解释的基准："若至少 \(m\) 个样本满足 \(\sigma_i \le 1\)，估计器能达到多小的误差？"并给出了信息论下界。
    • 主要进展：Compton 和 Valiant [CV24] 在 STOC 2024 上设计了"平衡寻找"（balance-finding）算法，在均值估计中达到了近乎最优的 Subset-of-Signals 误差，且只需 \(m \ge n^{1/4+o(1)}\) 个有界方差样本。这一结果突破了此前需要 \(m \ge \Omega(n^{1/2})\) 的限制。本文是 [CV24] 从均值估计向线性回归的自然延伸。
    • 当前 frontier：自适应估计方面，Kao, Xu, Zhang [KXZ24] 系统研究了 \(L_q\) 回归（数据依赖地选择 \(q\)）在对称分布下的表现，但其分析未能覆盖所有对称 log-concave 分布（例如"平滑均匀分布"）。Compton 和 Valiant [CV26] 在均值估计中证明了：对 \(k\) 个对称 log-concave 分布的混合，存在（计算上低效的）自适应估计器达到 Hellinger 模量给出的最优误差。本文将其推广到线性回归。
    • 本文的位置：本文填补了两个关键空白：(a) 在异方差回归中，首次给出多项式时间算法，在 \(m \gg d^{3/4}n^{1/4}\) 时达到误差 \(\tilde{O}((nd^3/m^4)^{1/6})\)，并证明该误差在 minimax 意义下近乎最优；(b) 在自适应回归中，将 [CV26] 的均值估计结果推广到高维线性回归，并证明对 \(k=1\)（单个对称 log-concave 分布），\(L_q\) 回归（\(q\) 数据依赖）是多项式时间最优的。

  • 子线索聚类：被引文献大致落在三条子线索上：

    1. 异方差/重尾均值估计（[CDKL14, Xia19, YL20, PJL22, DLLZ23, Lou25, CV24, HSS26]）：核心问题是"在部分样本方差极大时如何估计均值"，Subset-of-Signals 模型是主要 benchmark。本文的 RB-DESC 算法是这条线索的回归版本。
    2. 自适应/分布鲁棒估计（[Ber78, Sto75, Sac75, Bic82, LL23, KXZ24, FKQX26]）：核心问题是"如何在不了解噪声分布的情况下达到最优误差"。\(L_q\) 回归、得分匹配、Hellinger 模量是主要工具。本文的 \(L_q\) 估计器属于此线索。
    3. 信息-计算间隙与 SQ 下界（[FGR+17, BBH+21, DGK+25, MW25]）：核心问题是"哪些统计上可达到的误差在计算上不可达"。本文的 planted 线性回归问题和 SQ 下界属于此线索，它连接了统计与理论计算机科学。

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

    1. 统计最优性：在 Subset-of-Signals 模型下，给定 \(m\) 个有界方差样本，最优估计误差的精确阶是什么？本文回答：\(\tilde{\Theta}((nd^3/m^4)^{1/6})\)（当 \(m \gg d^{3/4}n^{1/4}\)）。
    2. 计算可行性：这个最优误差能否在多项式时间内达到？本文回答：能（RB-DESC 算法），但仅在 \(m \gg d^{3/4}n^{1/4}\) 时。当 \(m\) 更小时，存在 SQ 下界暗示计算困难。
    3. 自适应能力：是否存在一个估计器，对一大类噪声分布 \(p\) 都能达到"知道 \(p\) 的最优误差"？本文回答：对 \(k=1\)（对称 log-concave），\(L_q\) 回归可以；对 \(k \ge 2\)，存在（计算低效的）估计器可以，但多项式时间版本未知。

  • ⚠️ 作者的 framing（必须明确标注成"这是作者的说法"）：作者将缺口 frame 成"有限样本、非渐近、且噪声分布可任意选择"的设定。他们强调，经典渐近理论（\(n \to \infty\)，\(p\) 固定）无法处理"噪声分布依赖 \(n\)"的情形（如平滑均匀分布），而他们的框架能给出非渐近的、对任意 \(n\) 成立的界。作者淡化了以下竞争路线：(a) 渐近自适应估计（如 [Bic82]），认为其假设（有限 Fisher 信息）过强；(b) 凸 M-估计（如 Huber 回归），认为其在 planted 问题中无法达到最优（Theorem 4.7 证明其失败）；(c) 贝叶斯/经验贝叶斯方法，未在文中讨论。作者将"计算效率"作为核心卖点，但回避了一个关键问题：RB-DESC 的常数因子可能很大（依赖 \(\log\) 的幂次），而 SQ 下界只给出了 \(m \ll d^{3/4}n^{1/4}\) 时的困难性，中间区域（\(d^{3/4}n^{1/4} \ll m \ll \sqrt{nd}\)）的计算复杂度仍是开放的。

  • 张力：被引文献之间存在一个明显的张力：[CV24] 的均值估计结果（\(m \ge n^{1/4}\) 即可）与本文的回归结果（需要 \(m \gg d^{3/4}n^{1/4}\)）之间的差距。作者将这一差距归因于高维回归的额外困难（需要同时估计 \(d\) 个参数），但并未给出一个统一的框架来解释为何维度 \(d\) 会以 \(d^{3/4}\) 的指数进入阈值。此外，[KXZ24] 的 \(L_q\) 回归分析与本文的 \(L_q\) 分析在技术上不兼容：KXZ24 的界依赖于 \(p\) 的矩条件，而本文的界依赖于 Hellinger 模量；作者声称他们的分析更精细，但未在文中直接比较两种方法的适用范围。未见明显对立引用。

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

第一步：把符号、模型、可观测数据交代清楚

  • 符号：
  • \(n\)：样本总数；\(d\)：特征维度；\(m\)：噪声方差 \(\le 1\) 的样本数（未知具体是哪些）。
  • \(\beta \in \mathbb{R}^d\)：未知的回归系数向量（参数/estimand）。
  • \(X_i \in \mathbb{R}^d\)：第 \(i\) 个样本的特征向量（随机变量，假设独立同分布，均值为 0，协方差矩阵 \(\Sigma\) 满足 \(\kappa^{-1} I \preceq \Sigma \preceq \kappa I\)，且 \(K\)-次高斯）。
  • \(Y_i \in \mathbb{R}\)：第 \(i\) 个样本的标签（随机变量）。
  • \(\varepsilon_i\)：第 \(i\) 个样本的噪声（随机变量，与 \(X_i\) 独立）。
  • \(\sigma_i^2\)：第 \(i\) 个样本的噪声方差（未知参数，异方差模型中每个样本不同）。
  • \(p\)：自适应模型中噪声的分布（未知分布，对称且 log-concave）。
  • \(\hat{\beta}\)：估计器输出的估计值（随机变量）。
  • \(\|\cdot\|_2\)：欧几里得范数；\(\|\cdot\|_\Sigma\)：由 \(\Sigma\) 诱导的范数。
  • \(\omega_p(\varepsilon)\)：Hellinger 模量，定义为 \(\sup\{t : H^2(p, p_t) \le \varepsilon\}\)，其中 \(H^2\) 是平方 Hellinger 距离，\(p_t\) 是 \(p\) 平移 \(t\) 后的分布。它刻画了"用 \(n\) 个样本区分 \(p\) 和 \(p_t\) 所需的最小 \(t\)"。
  • \(B_2(B)\)：半径为 \(B\) 的欧几里得球。

  • \(\tilde{O}(\cdot)\)：忽略 \(\log\) 因子的 \(O(\cdot)\)。

  • 模型：

  • 异方差模型：\(Y_i = X_i^\top \beta + \varepsilon_i\)，其中 \(\varepsilon_i \sim N(0, \sigma_i^2)\)，\(\sigma_i\) 未知，且至少 \(m\) 个 \(\sigma_i \le 1\)，其余 \(\sigma_i\) 可以任意大（甚至无穷大）。
  • 自适应模型：\(Y_i = X_i^\top \beta + \varepsilon_i\)，其中 \(\varepsilon_i \overset{\text{i.i.d.}}{\sim} p\)，\(p\) 是未知的对称 log-concave 分布。

  • planted 模型：\(Y_i = X_i^\top \beta + \varepsilon_i\)，其中 \(m\) 个样本的 \(\varepsilon_i = 0\)（无噪声），其余样本的 \(\varepsilon_i \sim N(0,1)\)。

  • 可观测数据：\((X_i, Y_i)_{i=1}^n\)，即 \(n\) 对特征-标签样本。不可观测：\(\beta\)、\(\sigma_i\)（异方差）、\(p\)（自适应）、以及哪些样本是"好"的（方差 \(\le 1\) 或零噪声）。

第二步：讲最小内核

本文的数学内核可以归结为一个估计问题和一个计算问题：

  1. 统计估计问题（最小内核）：给定 \(n\) 个样本 \((X_i, Y_i)\)，其中 \(Y_i = X_i^\top \beta + \varepsilon_i\)，噪声 \(\varepsilon_i\) 的分布未知且可能异质（至少 \(m\) 个方差 \(\le 1\)），如何估计 \(\beta\) 使得误差 \(\|\hat{\beta} - \beta\|_2\) 尽可能小？

最简特例：\(d=1\)（一维），\(X_i \sim N(0,1)\)，\(\beta = \mu\)（均值）。此时问题退化为异方差均值估计： - 观测：\(Y_i = \mu + \varepsilon_i\)，其中至少 \(m\) 个 \(\varepsilon_i \sim N(0, \sigma_i^2)\) 且 \(\sigma_i \le 1\)，其余 \(\varepsilon_i\) 方差任意大。 - 目标：估计 \(\mu\)。 - 核心困难：不知道哪些样本是"好"的（方差 \(\le 1\)）。如果知道，直接用这些样本的均值即可，误差 \(\approx 1/\sqrt{m}\)。但不知道时，一个方差极大的样本会破坏均值估计。 - 关键思想：使用"平衡寻找"（balance-finding）——不是简单地取均值，而是寻找一个尺度 \(w\)，使得在 \([-w, w]\) 区间内的样本"平衡"（即正负样本数大致相等）。可以证明，当 \(m \gg n^{1/4}\) 时，这个方法的误差接近 \(1/\sqrt{m}\)，而传统方法（如中位数）需要 \(m \gg \sqrt{n}\)。 - 为什么这是内核：高维回归的 RB-DESC 算法正是将这个一维思想推广到 \(d\) 维：通过投影到某个方向 \(u\)，将高维问题转化为一维问题，然后用平衡寻找来估计投影值。因此，理解一维情形是理解全文的钥匙。

  1. 计算问题（planted 模型）：当 \(m\) 个样本完全无噪声（\(\varepsilon_i = 0\)）时，能否在多项式时间内找到 \(\beta\)？这个问题在 \(m \ge d+1\) 时信息论上平凡（任意 \(d+1\) 个无噪声样本即可确定 \(\beta\)），但作者猜想在 \(m \ll d^{3/4}n^{1/4}\) 时计算上困难。他们证明：
  2. 上界：RB-DESC 在 \(m \gg d^{3/4}n^{1/4}\) 时成功。
  3. 下界：任何凸 M-估计器（包括 Huber、\(L_q\) 等）在 \(m \ll \sqrt{nd}\) 时失败（Theorem 4.7）。
  4. SQ 下界：任何 SQ 算法在 \(m \ll d^{3/4}n^{1/4}\) 时失败（Theorem 4.3）。

这个问题的核心是信息-计算间隙：统计上可行（\(m \ge d+1\)）但计算上似乎不可行（\(m \ll d^{3/4}n^{1/4}\)）的区域是否存在。

三、这篇论文做了什么

三句话： 1. 研究了什么问题：在有限样本、噪声分布未知且异质的线性回归中，刻画统计最优误差与计算可行误差之间的间隙。 2. 核心工具/方法：设计了"残差平衡下降"（RB-DESC）算法，利用"平衡寻找"思想处理异方差噪声；设计了数据依赖的 \(L_q\) 回归估计器处理自适应噪声；引入"planted 线性回归"问题，用 SQ 下界和凸 M-估计下界刻画计算困难。 3. 主要结论：(a) 异方差回归中，当 \(m \gg d^{3/4}n^{1/4}\) 时，RB-DESC 达到误差 \(\tilde{O}((nd^3/m^4)^{1/6})\)，且该误差是 minimax 最优的；(b) 自适应回归中，对单个对称 log-concave 分布，\(L_q\) 回归（\(q\) 数据依赖）达到 Hellinger 模量给出的最优误差，且是多项式时间的；(c) planted 回归中，凸 M-估计在 \(m \ll \sqrt{nd}\) 时失败，SQ 算法在 \(m \ll d^{3/4}n^{1/4}\) 时失败，暗示信息-计算间隙的存在。

关键设定与假设： - 异方差模型：假设 \(X_i\) 是 \(K\)-次高斯的，协方差 \(\Sigma\) 满足 \(\kappa^{-1} I \preceq \Sigma \preceq \kappa I\)（条件数有界）。噪声 \(\varepsilon_i\) 独立于 \(X_i\)，且至少 \(m\) 个满足 \(\sigma_i \le 1\)。不假设噪声方差的具体分布，也不假设知道哪些样本是"好"的。相比已有工作（如 [CDKL14]），本文允许 \(d > 1\)，且不要求噪声是高斯。 - 自适应模型：假设 \(p\) 是对称 log-concave 的，且 \(X_i\) 满足同样的条件。不假设 \(p\) 的 Fisher 信息有限（允许均匀分布等"非光滑"情形）。相比 [KXZ24]，本文的假设更弱（KXZ24 需要 \(p\) 的矩条件）。 - planted 模型：假设 \(m\) 个样本无噪声，其余噪声为 \(N(0,1)\)。这是异方差模型的一个极端特例，用于隔离计算困难。

主要结果： 1. Theorem 1.5（异方差回归上界）：若 \(m \ge C \log^5(ndB/\delta) \cdot d^{3/4} n^{1/4}\)，则 RB-DESC 以概率 \(1-\delta\) 输出 \(\hat{\beta}\) 满足 \(\|\hat{\beta} - \beta\|_2 \le C \log^5(ndB/\delta) \cdot (nd^3/m^4)^{1/6}\)。运行时间 \(O(n^2 d \log^2(ndB/\delta))\)。 2. Theorem A.1（异方差回归下界）：存在常数 \(c, c_0\)，使得对任意估计器（不要求计算效率），存在一个方差配置（至少 \(m\) 个 \(\sigma_i \le 1\)），使得误差至少为 \(c \cdot \min\{(nd^3/m^4)^{1/6}, \sqrt{d/n}\}\)。这证明 RB-DESC 的误差在 \(m \gg d^{3/4}n^{1/4}\) 时是 minimax 最优的（忽略 \(\log\) 因子）。 3. Theorem 1.6（自适应回归上界）：若 \(n \ge C d \log^4(64n/\delta)\)，则 \(L_q\) 回归（\(q\) 数据依赖）以概率 \(1-\delta\) 输出 \(\hat{\beta}\) 满足 \(\|\hat{\beta} - \beta\|_2 \le C \omega_p(C d \log^4(64n/\delta)/n) + \gamma\)。运行时间 \(\text{poly}(n,d) \cdot \text{polylog}(1/\delta, \|Y\|_\infty, 1/\gamma)\)。 4. Theorem 1.8（自适应回归下界）：对任意对称单峰分布 \(p\)，任意估计器（不要求计算效率）在 \(n\) 个样本下必须 incur 误差 \(\geq c \omega_p(c d/n)\)。这证明 \(L_q\) 回归的误差与最优误差只差 \(\log\) 因子。 5. Theorem 4.7（凸 M-估计下界）：对 planted 模型，当 \(m \le c \sqrt{nd}\) 时，任何凸 M-估计器（损失函数为凸函数）以高概率无法精确恢复 \(\beta\)。 6. Theorem 4.3（SQ 下界）：对 planted 模型，当 \(m \le c (nd^3)^{1/4}\) 时，任何 SQ 算法需要 \(\exp(\Omega(d))\) 次查询才能精确恢复 \(\beta\)。

证明路线与技术技巧： - RB-DESC 算法（Section 2）： 1. 整体路线：算法从 \(\hat{\beta} = 0\) 开始，迭代地计算残差 \(r_i(\hat{\beta}) = Y_i - X_i^\top \hat{\beta}\)。在每一轮，算法选择一个尺度 \(w\)，计算"残差平衡向量" \(S_w(\hat{\beta}) = \sum_{i=1}^n X_i \text{sgn}(r_i(\hat{\beta})) \mathbf{1}\{|r_i(\hat{\beta})| \le w\}\)。如果 \(\|S_w(\hat{\beta})\|_2\) 很大，说明 \(\hat{\beta}\) 离 \(\beta\) 很远，算法沿着 \(S_w(\hat{\beta})\) 的方向移动 \(\hat{\beta}\)。关键步骤是证明：当 \(\|\hat{\beta} - \beta\|_2\) 大于目标误差时，存在某个尺度 \(w\) 使得 \(S_w(\hat{\beta})\) 与 \(\beta - \hat{\beta}\) 强相关。 2. 关键引理（Lemma 2.1）：在期望上，\(\langle S_w(\hat{\beta}), \beta - \hat{\beta}\rangle \geq c m \eta(\|\hat{\beta} - \beta\|_\Sigma)\)，其中 \(\eta\) 是某个函数。这个引理将几何问题（\(\hat{\beta}\) 是否接近 \(\beta\)）转化为统计问题（\(S_w\) 是否与 \(\beta - \hat{\beta}\) 相关）。 3. 技术技巧：使用均匀收敛（Proposition 2.5）来保证经验量 \(S_w\) 接近期望量 \(\bar{S}_w\)。证明的关键是 VC 维数论证：残差集合 \(\{(x,y): |y - x^\top b| \le w\}\) 的 VC 维数为 \(O(d)\)，因此可以用标准的 VC 不等式控制。另一个技巧是尺度网格：算法在 \(\log\) 多个尺度 \(w\) 上测试，而不是连续地搜索。 4. 难点：处理 \(S_w\) 的方差。由于噪声方差可能很大，\(S_w\) 的方差可能很大。作者通过只使用 \(|r_i| \le w\) 的样本来控制方差，并证明这些样本的数量至少是 \(m\) 的常数倍（利用方差 \(\le 1\) 的样本）。

  • 自适应 \(L_q\) 估计器（Section 3）：
  • 整体路线：算法将数据分成 \(B\) 块，对每个块和每个 \(q \in \{2, 4, 8, \ldots\}\) 计算 \(L_q\) 回归估计量 \(\hat{\beta}_{q,i}\)。然后，对每个 \(q\)，计算这些估计量的中位数（或更精确的"有效半径"），选择有效半径最小的 \(q\)。
  • 关键命题（Proposition 3.5）：对于固定的 \(q\)，\(L_q\) 回归的误差由 \(V_p(q) = \frac{M_{2q-2}}{M_{q-2}^2}\) 控制，其中 \(M_k = \mathbb{E}|\varepsilon|^k\)。这个量是 \(p\) 的"矩比"，刻画了 \(L_q\) 损失对 \(p\) 的适应程度。
  • 技术技巧：使用Hellinger 模量 \(\omega_p(\varepsilon)\) 作为统一的度量。作者证明，对于对称 log-concave \(p\)，存在 \(q\) 使得 \(V_p(q)\) 与 \(\omega_p(d/n)\) 匹配。这需要精细的尾部估计（Lemma 3.8 和 3.9），核心是证明 log-concave 分布的尾部衰减可以用 Hellinger 模量控制。

  • 难点：证明"存在 \(q\)"是不够的，还需要"找到 \(q\)"。作者使用块方法：将数据分成块，对每个 \(q\) 计算多个估计量，然后选择"最一致"的 \(q\)。这需要证明估计量的分布是"集中"的，即大多数块给出的估计量都接近真实值。

  • SQ 下界（Section 4）：

  • 整体路线：将 planted 模型转化为一个"隐藏子集"问题：\(m\) 个无噪声样本对应一个未知子集 \(S\)，目标是找到 \(S\)。SQ 算法只能通过查询函数的期望值来获取信息。
  • 关键引理：证明任何 SQ 查询都无法有效区分"\(S\) 包含某个方向 \(u\)"和"\(S\) 不包含 \(u\)"，除非查询次数指数级大。这使用了低度多项式和傅里叶分析的技术。
  • 技术技巧：使用随机旋转不变性：将问题旋转后，\(S\) 的分布不变，但任何固定方向的查询都会失效。这类似于 planted clique 问题的 SQ 下界证明。

🔎 结论是否比证明窄： - Theorem 1.5 的常数依赖：定理中的误差界 \(\tilde{O}((nd^3/m^4)^{1/6})\) 依赖 \(\log^5(ndB/\delta)\) 因子，但作者没有给出 \(\log\) 因子的具体指数。在 Section 5 的模拟中，他们使用了修改后的算法（"aggressive"变体），其理论保证不如定理中的版本强。这意味着：定理保证的算法可能不是模拟中表现最好的算法。 - Theorem 1.6 的适用范围：定理假设 \(p\) 是对称 log-concave 的。对于非对称分布，作者在 Section 3.3 的讨论中承认他们的方法不适用，但未给出反例。结论比证明窄：定理的证明依赖于对称性（用于构造对称化预处理），但结论可能对更广的分布成立。 - Theorem 4.3 的 SQ 下界：下界只针对精确恢复（误差为 0），而非近似恢复（误差 \(\ll \sqrt{d/n}\)）。作者在 Section 4.2 的讨论中承认，对于近似恢复，SQ 下界可能不成立。结论比证明窄：下界只排除了精确恢复，不排除近似恢复。 - Theorem 4.7 的凸 M-估计下界：下界只针对凸损失函数，不排除非凸方法（如 \(L_0\) 回归）。作者在 Section 4.3 的讨论中承认，非凸方法可能成功。结论比证明窄：下界只针对凸方法。

四、开放问题

  1. 异方差回归的常数优化：RB-DESC 的误差界包含 \(\log^5\) 因子，且模拟中使用的"aggressive"变体缺乏理论保证。要证什么：能否设计一个更简单的算法，在 \(m \gg d^{3/4}n^{1/4}\) 时达到误差 \(\tilde{O}((nd^3/m^4)^{1/6})\)，且 \(\log\) 因子的指数更小？（扎根于 Section 5 的模拟讨论和 Theorem 1.5 的陈述）

  2. planted 模型的近似恢复：SQ 下界只排除了精确恢复，但近似恢复（误差 \(\ll \sqrt{d/n}\)）是否也可能计算困难？要证什么：能否证明在 \(m \ll d^{3/4}n^{1/4}\) 时，任何多项式时间算法都无法达到误差 \(o(\sqrt{d/n})\)？（扎根于 Section 4.2 的讨论："we do not rule out approximate recovery"）

  3. 非凸方法的可能性：Theorem 4.7 排除了凸 M-估计，但非凸方法（如 \(L_0\) 回归、稀疏回归）是否能在 \(m \ll \sqrt{nd}\) 时成功？要证什么：能否设计一个非凸算法，在 \(m \gg d \log n\) 时精确恢复 \(\beta\)？（扎根于 Section 4.3 的讨论："we do not rule out non-convex methods"）

  4. 自适应估计的推广：Theorem 1.6 只覆盖对称 log-concave 分布。对于非对称分布（如偏态分布），最优误差是什么？要证什么：能否将 Hellinger 模量方法推广到非对称分布，或者证明其不可能？（扎根于 Section 3.3 的讨论："we leave the case of non-symmetric \(p\) as an open problem"）

  5. 信息-计算间隙的统一框架：本文展示了异方差、自适应、planted 三个问题之间的紧密联系，但未给出一个统一的框架来解释为何 \(m \sim d^{3/4}n^{1/4}\) 是计算阈值。要证什么：能否将这三个问题归约为一个更一般的问题，并证明其计算阈值？（扎根于 Section 1.4 的讨论："we conjecture that this is an information-computation gap"）

提醒：要确认上述问题是否是真 gap，建议去读同子领域近期约 5 篇论文的引言（如 [CV24, CV26, KXZ24, HSS26, DGK+25]）。如果多篇论文都指向同一个开放问题，那它很可能是共识性的真 gap；如果各论文的开放问题互相矛盾，那可能意味着该领域尚未形成清晰的问题意识。

Maintained by 陈星宇 · Homepage · Source on GitHub

评论