跳转至

Influence as soft sparsity: Estimation of monotone functions on \(\{0,1\}^d\)

作者: Gérard Biau
主题: 非参数 / 半参数
相关性: 6/10
链接: https://arxiv.org/abs/2605.19648


一、领域脉络与小综述

这个方向是什么

本文研究的根本问题是:在高维离散空间(布尔超立方体 \(\{0,1\}^d\))上,如何利用"单调性"这一结构约束,在样本量远小于维度的情况下估计一个函数。这是"形状约束回归"(shape-constrained regression)与"高维非参数估计"的交叉地带。经典的多变量保序回归(isotonic regression)在 \([0,1]^d\) 上的 minimax 率为 \(n^{-1/d}\)(Han et al., 2019),当 \(d \gg \log n\) 时该率趋于常数——即"维度灾难"不可回避。本文的核心主张是:在布尔超立方体上,用"总 L1 影响"(total L1-influence)作为复杂度度量,可以绕过维度灾难,获得随 \(K/\sqrt{\log n}\) 衰减的率,且对维度 \(d\) 一致。这个方向当前处于"理论奠基"阶段——它首次将布尔函数分析(Boolean function analysis)中的谱工具系统引入统计估计问题,但离成熟还有距离(上下界之间仍有 \(\sqrt{\log n}\) 的 gap)。

发展脉络

奠基工作:布尔函数分析中的影响与谱工具。 Kahn–Kalai–Linial(1988)引入影响(influence)概念并证明 KKL 定理;Friedgut(1998)证明"低总影响 ⇒ 接近 junta"的谱集中定理,这是本文 Proposition 4.2 的直接前身。这些工作属于理论计算机科学,关注的是布尔函数的结构性而非统计可估性。

主要进展:从"精确稀疏"到"软稀疏"。 在高维非参数回归中,传统做法是假设"精确稀疏"——目标函数只依赖 \(s \ll d\) 个未知坐标(Yang & Barron, 1999; Kpotree, 2011; Comminges & Dalalyan, 2012)。这些工作的共同点是:稀疏性是一个离散的、先验的假设(要么依赖、要么不依赖)。本文的贡献在于提出"软稀疏"——用总 L1 影响 \(I(f) \le K\) 作为连续谱的复杂度度量,它不要求函数只依赖少数坐标(Tribes 函数依赖所有 \(d\) 个坐标,但 \(I(f) = \Theta(\log d)\)),却仍然保证可估性。这是从"结构假设"到"复杂度预算"的范式转换。

当前 frontier:形状约束与高维的张力。 多变量保序回归的 minimax 率 \(n^{-1/d}\)(Han et al., 2019)表明:在连续域 \([0,1]^d\) 上,单调性本身不足以对抗维度灾难。本文的定位是:在离散域 \(\{0,1\}^d\) 上,单调性 + 影响预算可以做到维度一致。这填补了一个空白——此前没有工作系统研究过"布尔超立方体上的单调函数估计"的 minimax 率。

本文的位置:它是"布尔函数分析 + 非参数估计"的首次系统结合。上界由 Fourier 阈值估计器达到,下界基于超立方体中层的 Varshamov–Gilbert 打包。它留下的口子(gap、开放问题)在 Section 7 中明确列出。

子线索聚类

被引文献大致落在三条子线索上:

  1. 布尔函数分析(Friedgut 1998; Kahn et al. 1988; Garban & Steif 2014; Kelman et al. 2021):提供谱集中、影响、噪声敏感性的理论工具。这条线关注结构,不涉及统计估计。
  2. 高维稀疏非参数回归(Yang & Barron 1999; Kpotufe 2011; Comminges & Dalalyan 2012):研究"函数只依赖少数坐标"时的估计率。这条线关注精确稀疏,不涉及单调性。
  3. 形状约束回归(Brunk 1955; Chatterjee et al. 2015; Han et al. 2019):研究单调函数在连续域上的估计。这条线关注单调性,但在高维下率退化严重。

本文是三条线的交汇:用线索 1 的工具,解决线索 2 和 3 共同留下的问题(高维 + 单调 + 无精确稀疏假设)。

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

  1. 如何用"软"复杂度度量替代"硬"稀疏假设? 总 L1 影响 \(I(f)\) 是否是正确的复杂度度量?它能否推广到其他离散结构(如一般乘积空间、图上的函数)?
  2. 单调性在离散域上能带来多少增益? 本文的率 \(K/\sqrt{\log n}\) 与无单调性假设下的率有何差距?单调性在证明中的关键作用是什么?
  3. 上下界之间的 gap 能否闭合? 上界 \(O(K/\sqrt{\log n})\) 与下界 \(\Omega(K^2/(\log n)^{3/2})\) 之间差 \(\sqrt{\log n}\) 因子。这是技术缺陷还是本质困难?

⚠️ 作者的 framing(这是作者的说法)

作者在 Section 3 中明确将 \(I(f) \le K\) 类比为"软稀疏性"(soft sparsity),并声称它与 LASSO 中 \(\ell_1\) 球的作用平行:约束 \(\|f\|_1 \le K\) 同时实现"近似稀疏"和"可估性",约束 \(I(f) \le K\) 同时实现"近似 junta"和"可估性"。这个类比是作者的核心叙事,但它回避了一个问题:\(\ell_1\) 约束在计算上有高效的凸优化算法(LASSO),而本文的 Fourier 阈值估计器需要枚举 \(\hat{S}\) 中的所有子集(虽然作者证明了 \(\log|\hat{S}| = O(\log n)\),但常数可能很大)。计算可行性是作者淡化的一条线——他在 Section 7 中承认"计算成本是 \(O(n^c)\),常数 \(c\) 可能很大"。

什么明显该被引 / 该存在、却没出现在 intro 里? 作者没有引用任何关于"计算复杂度与统计率之间权衡"的文献(如 Agarwal et al. 2012 关于统计-计算间隙的工作),也没有引用关于"离散域上形状约束回归"的其他工作(如 Han et al. 2019 的后续研究)。这暗示作者有意将本文定位为"纯信息论/统计率"的结果,回避计算复杂度的讨论。这是一个值得研究者去查的问题:是否存在计算上更高效、但统计率稍差的估计器?

张力

未见明显对立引用。但有一个微妙的张力:Friedgut 定理(1998)本身是非构造性的——它保证"存在"一个 junta 逼近,但没有给出如何找到它。本文的估计器通过枚举所有低度子集来绕过这个问题,但代价是计算复杂度。"结构定理的构造性"与"统计可估性"之间的张力是本文隐含的主题,作者没有正面处理。


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

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

先交代记号(这是读后面所有技术节的地基):

记号 含义 类型
\(d\) 维度(特征数) 已知常数
\(n\) 样本量 已知常数
\(X \sim \mu = \text{Unif}(\{0,1\}^d)\) 均匀随机采样的布尔向量 可观测随机变量
\(Y = f(X) + \varepsilon\) 带噪观测 可观测随机变量
\(f: \{0,1\}^d \to [0,1]\) 目标函数(单调) 待估参数(非参数)
\(\varepsilon\) 次高斯噪声,参数 \(\sigma\) 不可观测
\(M_d\) 所有单调函数 \(\{0,1\}^d \to [0,1]\) 函数类
\(F_K = \{f \in M_d : I(f) \le K\}\) 影响预算约束下的函数类 参数空间
\(I_i(f) = E[f(X) \mid X_i=1] - E[f(X) \mid X_i=0]\) 第 \(i\) 个坐标的 L1 影响 函数 \(f\) 的泛函
\(I(f) = \sum_{i=1}^d I_i(f)\) 总 L1 影响 函数 \(f\) 的泛函(复杂度度量)
\(I^{(2)}(f) = \sum_{i=1}^d E[(\Delta_i f(X))^2]\) 总 L2 影响 函数 \(f\) 的泛函
\(\hat{f}\) 估计器 数据到函数的映射
\(R(\hat{f}, f) = E[\|\hat{f} - f\|_2^2]\) 积分均方误差 风险(评估标准)
\(\|g\|_2^2 = E_\mu[g(X)^2]\) L2 范数(关于 \(\mu\)) 度量
\(\hat{I}_i\) \(I_i(f)\) 的样本估计 估计量
\(\hat{J}\) 选出的"重要"坐标集合 数据驱动的选择
\(\hat{S}\) 选出的 Fourier 子集 数据驱动的选择
\(\chi_S(x) = \prod_{i \in S}(2x_i - 1)\) Fourier 基函数 基函数
\(\hat{f}(S)\) Fourier 系数的样本估计 估计量
\(d_0\) 截断维度参数 调参(依赖 \(n\))
\(\delta\) 影响阈值 调参(依赖 \(n\))
\(s = \lfloor 2\log_2 n \rfloor\) 下界构造中的子空间维度 构造参数
\(\Omega \subseteq \{0,1\}^N\) Varshamov–Gilbert 打包 下界构造

模型(用直白语言写):

  1. 数据生成:独立采样 \(n\) 个点 \(X_j \sim \text{Unif}(\{0,1\}^d)\),观测 \(Y_j = f(X_j) + \varepsilon_j\),其中 \(\varepsilon_j\) 是次高斯噪声(参数 \(\sigma\))。
  2. 目标函数:\(f\) 是单调的(坐标wise 非降),取值在 \([0,1]\)。
  3. 复杂度约束:\(f\) 的总 L1 影响 \(I(f) \le K\)。这个约束是本文的核心创新——它不要求 \(f\) 只依赖少数坐标(精确稀疏),而是要求"平均而言,翻转一个坐标对 \(f\) 的影响之和有界"。
  4. 可观测数据:\(\{(X_j, Y_j)\}_{j=1}^n\)。不可观测:\(f\) 本身、\(\varepsilon_j\) 的具体值、\(K\) 的值(估计器需要自适应于未知的 \(K\))。

关键区分: - 可观测:\(X_j\)(均匀采样)、\(Y_j\)(带噪标签)。 - 想要但观测不到:\(f\) 在任意点 \(x\) 的值、\(I(f)\)、\(I^{(2)}(f)\)、\(K\)。 - 识别策略:\(f\) 的 Fourier 系数 \(\hat{f}(S) = E[f(X)\chi_S(X)]\) 可以通过样本均值 \(\frac{1}{n}\sum_j Y_j \chi_S(X_j)\) 直接估计(因为 \(\chi_S\) 是已知基函数,\(X_j\) 是均匀采样)。这是本文方法可行的根本原因——在均匀采样下,Fourier 系数估计是无偏的,不需要任何额外假设。

第二步:最小内核

剥掉所有技术假设后,本文的核心数学问题是:

在布尔超立方体上,给定 \(n\) 个带噪样本,估计一个单调函数 \(f\),已知 \(I(f) \le K\)。最优估计器的风险是多少?

最小例子:考虑 \(d\) 很大(比如 \(d = 10^6\)),\(n = 10^4\),\(K = 10\)。此时 \(d \gg n\),经典的非参数方法完全失效。但 \(I(f) \le 10\) 意味着 \(f\) 的 Fourier 谱集中在少数低度项上(Proposition 4.2)。关键直觉:\(I(f) \le K\) 的函数虽然可能依赖所有 \(d\) 个坐标(如 Tribes),但它的 Fourier 谱中,高阶项的权重衰减得很快。因此,只需要估计少数低度 Fourier 系数,就能逼近 \(f\)。

为什么这个例子是"最小内核": - 它展示了"软稀疏"如何工作:不要求 \(f\) 只依赖少数坐标,只要求谱集中。 - 它展示了估计器的结构:先估计每个坐标的影响(用样本均值差),选出重要坐标,再在这些坐标上做 Fourier 截断。 - 它展示了率的来源:\(K/\sqrt{\log n}\) 中的 \(\sqrt{\log n}\) 来自 Fourier 子集大小的对数,\(K\) 来自影响预算。

证明的核心步骤(用大白话): 1. 谱集中(Proposition 4.2):\(I(f) \le K\) 的单调函数的 Fourier 权重集中在低度项上。具体地,\(\sum_{|S|>d_0} \hat{f}(S)^2 \le I^{(2)}(f)/(4d_0) + K \cdot 3^{d_0} \delta^{1/2}/12\)。 2. 变量选择:用样本均值差 \(\hat{I}_i\) 估计每个坐标的影响,选出 \(\hat{J} = \{i : \hat{I}_i \ge \delta/2\}\)。在好的事件上,\(\hat{J}\) 包含所有"重要"坐标(\(I_i(f) \ge \delta\)),且 \(|\hat{J}| \le 4K/\delta\)。 3. Fourier 估计:在 \(\hat{S} = \{S \subseteq \hat{J} : |S| \le d_0\}\) 上估计 Fourier 系数,用样本均值 \(\frac{1}{n_2}\sum Y_j \chi_S(X_j)\)。 4. 偏差-方差权衡:偏差来自谱集中(截断掉的高阶项),方差来自 \(\hat{S}\) 的大小(\(|\hat{S}| \le e^{O(d_0^2)}\))。选择 \(d_0 \asymp \sqrt{\log n}\) 平衡两者。

这个最小内核揭示了本文的数学本质:将函数估计问题转化为"稀疏 Fourier 系数估计"问题,用影响预算控制谱集中性,用样本均值估计系数。下界则通过 Varshamov–Gilbert 打包构造大量"难以区分"的函数对,用 Fano 不等式证明任何估计器都必然犯错。


三、这篇论文做了什么

三句话

  1. 研究了什么问题:在布尔超立方体 \(\{0,1\}^d\) 上,从 \(n\) 个带噪样本估计单调函数 \(f\),以总 L1 影响 \(I(f) \le K\) 为复杂度度量,确定 minimax 风险率。
  2. 核心工具/方法:Fourier 分析 + Friedgut 型谱集中定理 + 影响阈值变量选择 + 样本均值 Fourier 系数估计;下界用 Varshamov–Gilbert 打包 + Fano 不等式。
  3. 主要结论:上界 \(O(K/\sqrt{\log n})\)(对所有 \(K \ge 1\),维度 \(d\) 一致,条件 \(\log d \le n^{1-\varepsilon}\)),下界 \(\Omega(K^2/(\log n)^{3/2})\),gap 为 \(\sqrt{\log n}\) 因子;在 L2 影响分层下 gap 缩小为 \(\sqrt{\log n}\)。

关键设定与假设

完整设定(在最小记号基础上补全):

  • 函数类:\(F_K = \{f: \{0,1\}^d \to [0,1], f \text{ 单调}, I(f) \le K\}\),其中 \(I(f) = \sum_{i=1}^d I_i(f)\),\(I_i(f) = E[f(X) \mid X_i=1] - E[f(X) \mid X_i=0]\)。
  • 噪声:\(\varepsilon_j\) 独立、中心化、次高斯,参数 \(\sigma\)(即 \(E[e^{t\varepsilon}] \le e^{\sigma^2 t^2/2}\))。
  • 采样:\(X_j \sim \text{Unif}(\{0,1\}^d)\),独立同分布。
  • 风险:\(R(\hat{f}, f) = E[\|\hat{f} - f\|_2^2]\),其中 \(\|g\|_2^2 = E_\mu[g(X)^2]\)。
  • 维度条件:\(\log d \le n^{1-\varepsilon}\)(上界),\(d \ge c^{-1}\log n\)(下界)。

假设的统计含义:

假设 含义 相比已有文献
单调性 坐标wise 非降 经典形状约束,但此前未在布尔超立方体上研究
\(I(f) \le K\) 总 L1 影响有界 本文核心创新——"软稀疏"替代"精确稀疏"
次高斯噪声 尾部条件 标准假设,比有界噪声略宽
均匀采样 \(\mu = \text{Unif}\) 关键假设——保证 Fourier 系数可无偏估计;推广到非均匀测度是开放问题
\(K \ge 1\) 影响预算至少为 1 归一化条件;\(K < 1\) 时问题退化(\(f\) 接近常数)

相比已有文献的放宽/强化: - 放宽:不要求精确稀疏(\(f\) 可依赖所有 \(d\) 个坐标);不要求 \(K\) 已知(估计器自适应)。 - 强化:要求单调性(比一般 junta 类更窄);要求均匀采样(比一般乘积测度更窄)。

主要结果

定理 2.1(Minimax 界):

\[\frac{cK^2}{(\log n)^{3/2}} \le \inf_{\hat{f}} \sup_{f \in F_K} R(\hat{f}, f) \le \frac{CK}{\sqrt{\log n}}\]
  • 上界:\(O(K/\sqrt{\log n})\),对所有 \(K \ge 1\) 成立,维度 \(d\) 一致(条件 \(\log d \le n^{1-\varepsilon}\))。由 Fourier 阈值估计器达到,不依赖 \(K\)。
  • 下界:\(\Omega(K^2/(\log n)^{3/2})\),条件 \(K \le c\sqrt{\log n}\),\(d \ge c^{-1}\log n\)。基于 Varshamov–Gilbert 打包 + Fano 不等式。

定理 2.2(自适应 Minimax 界):在子类 \(F_{K,B} = \{f \in F_K : I^{(2)}(f) \le B\}\) 上: - 上界:\(O(B/\sqrt{\log n})\) - 下界:\(\Omega(B/\log n)\) - gap 缩小为 \(\sqrt{\log n}\)。

关键对比: - 经典多变量保序回归(Han et al., 2019):\(n^{-1/d}\),\(d \gg \log n\) 时失效。 - 本文:\(K/\sqrt{\log n}\),维度一致。这是本质改进——但代价是更强的结构假设(影响预算)。

证明路线与技术技巧

上界证明(定理 5.4):

  1. 谱集中(Proposition 4.2):核心引理。证明思路:
  2. 对单调函数,利用 Fourier 系数与影响的联系:\(I_i(f) = 2\sum_{S \ni i} \hat{f}(S)^2 / |S|\)(由 (5) 和 (6) 推出)。
  3. 将 \(\sum_{|S|>d_0} \hat{f}(S)^2\) 分解为"高影响坐标"和"低影响坐标"两部分。
  4. 对高影响坐标部分,用 \(I(f) \le K\) 控制;对低影响坐标部分,用超压缩不等式(Bonami–Beckner)控制。
  5. 关键技巧:将 L1 影响转化为 L2 影响的上界,再利用超压缩性。

  6. 变量选择(Proposition 5.3):用样本均值差 \(\hat{I}_i\) 估计影响。关键技巧:阈值 \(\delta/2\) 的选择保证在好的事件上 \(\hat{J}\) 包含所有"重要"坐标(\(I_i(f) \ge \delta\)),且 \(|\hat{J}| \le 4K/\delta\)。这里用到了 Hoeffding 不等式和次高斯尾界。

  7. Fourier 估计:在 \(\hat{S}\) 上估计系数。关键技巧:样本分割(sample splitting)保证变量选择和系数估计的独立性;\(\hat{S}\) 的大小控制方差。

  8. 偏差-方差权衡:选择 \(d_0 \asymp \sqrt{\log n}\)。偏差 \(\le I^{(2)}(f)/(4d_0) + K \cdot 3^{d_0}\delta^{1/2}/12\),方差 \(\le |\hat{S}|/n \le e^{O(d_0^2)}/n\)。平衡得 \(d_0 \asymp \sqrt{\log n}\)。

下界证明(定理 2.1(ii)):

  1. 构造:在 \(\{0,1\}^s\)(\(s = \lfloor 2\log_2 n \rfloor\))上构造函数族 \(\{f_\omega\}\),其中 \(\omega \in \Omega \subseteq \{0,1\}^N\) 是 Varshamov–Gilbert 打包。
  2. 嵌入:将 \(f_\omega\) 嵌入到 \(\{0,1\}^d\)(\(d \ge s\)),保持单调性和影响预算。
  3. 分离:证明 \(\|f_\omega - f_{\omega'}\|_2^2 \ge cK^2/(A^2 s^{3/2})\)。
  4. Fano:验证 KL 散度条件,得到下界 \(\Omega(K^2/(\log n)^{3/2})\)。

技术技巧清单: - 超压缩不等式(Bonami–Beckner 定理 4.1) - Varshamov–Gilbert 打包(下界构造) - Fano 不等式(下界证明) - 样本分割(上界证明) - 影响阈值变量选择(自适应于未知 \(K\))

真实例子与应用

本文为纯理论论文,无真实数据实验。 但作者在 Section 1.1 中给出了三个动机性应用场景:

  1. 临床医学:患者特征(吸烟、高血压、糖尿病等)为布尔变量,疾病风险随特征数量单调增加。此时 \(d\) 可达数十到数百,\(n\) 可能只有几千。
  2. 信用评分:借款人特征(就业、房产、历史违约等)为布尔变量,违约概率单调。
  3. 药物基因组学:基因变异的存在/缺失为布尔变量,药物反应可能单调依赖于变异数量(引用了 Weinreich et al., 2013 关于高阶上位性的工作)。

这些例子的作用:说明"单调 + 布尔"是实际场景中自然出现的结构,且 \(d\) 可以远大于 \(n\)。但作者没有在这些数据上做任何数值实验——这是一个明显的空缺:理论率 \(K/\sqrt{\log n}\) 是否在有限样本下可观测?常数因子多大?这些都没有回答。

🔎 结论是否比证明窄

是的,有多处。 具体点名:

  1. 定理 2.1(i) 的陈述:"存在一个估计器 \(\hat{f}_n\)(不依赖 \(K\))使得 \(\sup_{f \in F_K} R(\hat{f}_n, f) \le CK/\sqrt{\log n}\)"。但证明中(定理 5.4)实际证明的是更强的分层界 \(R(\hat{f}_n, f) \le C I^{(2)}(f)/\sqrt{\log n} + C'e^{-c\sqrt{\log n}}\)。这个更强的结论在定理陈述中被弱化了——作者没有在定理 2.1 中声明这个分层版本,而是把它放在定理 2.2 中作为"自适应"结果。这是一个"证明比结论强"的例子。

  2. 定理 2.2(ii) 的陈述:下界 \(\Omega(B/\log n)\) 只在 \(B \in (0, K^2/\sqrt{\log n}]\) 时成立。但上界 \(O(B/\sqrt{\log n})\) 对所有 \(B \in (0, K]\) 成立。这意味着在 \(B > K^2/\sqrt{\log n}\) 的区域,上下界之间的 gap 更大(\(\sqrt{\log n}\) 倍 vs \(\sqrt{\log n}\) 倍)。作者在 Section 7 中承认"closing the remaining \(\sqrt{\log n}\) gap on \(F_{K,B}\) is an open problem",但没有指出 gap 在 \(B\) 的不同区域可能不同。

  3. Section 7 的 Conjecture:"Our conjecture is that the upper bound \(CB/\sqrt{\log n}\) is the correct rate"。但没有给出任何支持这一猜想的证据——没有中间结果、没有数值实验、没有对下界构造为何不紧的分析。这是一个纯粹的猜测,作者没有提供任何理由。

  4. 计算复杂度:作者在 Section 7 中承认"computational cost is \(O(n^c)\) for a constant \(c\) depending on \(\gamma\)",但没有讨论这个常数有多大。从证明看,\(c\) 可能很大(因为 \(|\hat{S}| \le e^{O(d_0^2)}\) 且 \(d_0 \asymp \sqrt{\log n}\),所以 \(|\hat{S}| \le e^{O(\log n)} = n^{O(1)}\),但指数中的常数取决于 \(\gamma\) 和 \(\varepsilon\))。这是一个"结论比证明宽"的例子:定理声称"存在多项式时间估计器",但实际常数可能大到不可行。


四、开放问题

以下问题均扎根于论文的具体语句,只罗列、不判断可行性:

  1. 精确 minimax 率(扎根于 Section 7, "The lower bound bottleneck"):\(F_K\) 上的 minimax 率究竟是 \(K/\sqrt{\log n}\) 还是 \(K^2/(\log n)^{3/2}\)?作者猜测是前者,但没有证据。要确认这是否是真 gap:去读 Han et al. (2019) 之后关于形状约束回归的近期工作(约 5 篇),看是否有类似"影响预算"的复杂度度量被研究过。

  2. 高阶 Fourier 子集选择(扎根于 Open problem 7.1):能否从数据中识别"相关的 Fourier 子集 \(S\)"(而不仅仅是"相关的坐标 \(J\)"),使得估计成本正比于 \(|S|\) 而非 \(|\hat{S}|\)?这是一个统计-计算权衡问题:更精细的选择可能带来更快的率,但计算上更困难。

  3. L2 影响约束下的 minimax 率(扎根于 Section 7, "One might also consider the class \(\{f \in M_d : I^{(2)}(f) \le K\}\)"):如果直接用 L2 影响作为复杂度度量,率会如何变化?作者指出"estimation of \(I^{(2)}_i(f)\) from data is harder",但没有给出具体结果。

  4. 非均匀测度的推广(扎根于 Section 7, "Our results are stated for the uniform measure \(\mu\)"):当 \(X\) 服从非均匀乘积测度时,Fourier 系数估计不再是无偏的,谱集中定理也需要修正。这是一个自然的推广方向,但作者没有给出任何线索。

  5. 计算-统计之间的权衡(扎根于 Section 7, "Computational cost"):是否存在计算上更高效(比如 \(O(nd)\) 或 \(O(n \log n)\))的估计器,以略微牺牲统计率为代价?作者没有讨论这个问题。


提醒:要确认上述某条是否是真 gap,建议去读同一子领域近期约 5 篇论文的 introduction——如果多篇都指向同一个问题,说明是共识(真 gap);如果互相打架,说明是机会。特别值得查的是:"影响预算"这一复杂度度量是否已被其他作者独立提出过(例如在理论计算机科学的"属性测试"文献中),以及布尔超立方体上的单调函数估计是否已有其他方法(如基于排序的方法)。


Maintained by 陈星宇 · Homepage · Source on GitHub

评论