跳转至

Nonparametric classification with missing data

作者: Torben Sell, Thomas B. Berrett, Timothy I. Cannings
来源: Annals of Statistics
主题: 非参数 / 半参数
相关性: 8/10
链接: 期刊页 · arXiv

一、领域脉络与小综述

这个方向是什么

本子方向研究的是在特征存在缺失（missing data）的情况下，如何进行非参数分类（nonparametric classification）。核心统计问题是：当部分协变量（features）的值未被观测到时，如何估计最优分类器（Bayes classifier），并刻画其 excess risk 的 minimax 收敛速率。该问题的根本挑战在于：缺失机制（missing mechanism）可能非常复杂（如非随机缺失 MNAR），且非参数方法本身受维度诅咒（curse of dimensionality）困扰。当前成熟度：非参数分类在完全数据下已有成熟理论（minimax 率由光滑度、维度和 margin condition 刻画），但缺失数据下的非参数分类理论仍不完整，尤其是当缺失机制允许 MNAR 且回归函数具有结构（如 ANOVA 分解）时。

发展脉络（history）

根据本文 introduction 的引用，该方向的发展可串成以下线索：

  1. 奠基工作：非参数分类的 minimax 理论

    • Audibert & Tsybakov (2007)：建立了非参数分类中 excess risk 的 minimax 率，该率由回归函数的光滑度（smoothness）、特征分布的尾部行为（tail behavior）和 margin condition（描述决策边界附近的不确定性）共同决定。留下口子：该理论假设数据完全观测，未考虑缺失数据。
    • Tsybakov (2004)：引入了 margin condition 的概念，这是分类问题中刻画 minimax 率的关键参数。留下口子：同样基于完全数据。

  2. 主要进展：缺失数据下的非参数估计

    • Robins et al. (1994) 及 van der Laan & Robins (2003)：在因果推断和缺失数据领域，发展了基于倾向得分（propensity score）和逆概率加权（IPW）的半参数方法。留下口子：这些方法通常假设缺失机制是 MAR（随机缺失）或可忽略的，且主要关注均值或回归函数的估计，而非分类的 excess risk。
    • D’Attilio & Sen (2022)：在缺失数据下研究了非参数回归的 minimax 率，假设回归函数具有稀疏的 ANOVA 结构。留下口子：他们关注的是回归（L2 损失），而非分类（0-1 损失 / excess risk）。分类问题需要 margin condition，且 excess risk 的率与回归的率不同。

  3. 当前 frontier：缺失数据下的非参数分类

    • 本文 (Sell, Berrett & Cannings, 2024)：将上述两条线索结合——在缺失数据下，假设回归函数具有 ANOVA 结构，推导 excess risk 的 minimax 率，并提出一个达到该率的分类器（HAM）。本文的位置：这是首次在缺失数据下，针对非参数分类问题，给出完整的 minimax 理论，且允许 MNAR 缺失机制。

子线索聚类

这些被引文献大致落在两条子线索上：

  • 线索 A：完全数据下的非参数分类 minimax 理论

    • 代表工作：Audibert & Tsybakov (2007), Tsybakov (2004)。
    • 核心内容：刻画了 excess risk 的 minimax 率，参数包括光滑度（β）、维度（d）、margin condition（γ）和尾部行为（κ）。率通常为 \( n^{-\frac{\beta(1+\gamma)}{2\beta + d(1+\gamma)}} \) 形式，维度 d 出现在分母中，导致维度诅咒。
    • 当前瓶颈：无法处理缺失数据。

  • 线索 B：缺失数据下的非参数回归 / 估计

    • 代表工作：Robins et al. (1994), van der Laan & Robins (2003), D’Attilio & Sen (2022)。
    • 核心内容：发展处理缺失数据的统计方法（IPW, doubly robust），并研究回归函数的 minimax 率。D’Attilio & Sen (2022) 特别关注了 ANOVA 结构如何打破维度诅咒。
    • 当前瓶颈：未涉及分类问题的 excess risk 和 margin condition。

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

  1. 缺失数据下，分类的 minimax 率是什么？ 它如何依赖于缺失机制、回归函数结构、光滑度、margin condition 和尾部行为？维度诅咒是否仍然存在？
  2. 如何构造一个实际可行的分类器，使其达到该 minimax 率？ 该分类器需要同时处理缺失数据、非参数估计和结构假设（如 ANOVA 分解）。
  3. 缺失机制（MNAR vs. MAR）对 minimax 率有何影响？ 在 MNAR 下，识别和估计是否仍然可能？率是否会变慢？

⚠️ 作者的 framing

  • 作者把缺口 frame 成什么：作者将缺口 frame 为“在缺失数据下，非参数分类的 minimax 理论尚未建立”。他们声称，已有的工作要么只处理完全数据（Audibert & Tsybakov），要么只处理缺失数据下的回归（D’Attilio & Sen），而他们的工作首次将两者结合，并允许 MNAR 缺失机制。他们特别强调，通过假设回归函数具有ANOVA 结构，可以打破维度诅咒，使得 minimax 率中不出现 ambient data dimension \( d \)，从而可能比经典非参数设定更快。
  • 哪些竞争路线被他淡化或回避了：
    • 作者淡化了基于倾向得分（IPW）或双重稳健（doubly robust） 的方法。这些方法在缺失数据下很常见，但作者认为它们通常需要 MAR 假设或对缺失机制建模，而他们的方法通过直接对回归函数施加结构（ANOVA）来绕过对缺失机制的显式建模（尽管缺失机制仍通过观测概率 \( p(x) \) 影响率）。
    • 作者回避了参数化或半参数分类器（如 logistic regression with missing data）的讨论。这些方法在低维或特定结构下可能更高效，但作者专注于非参数框架。
  • 什么明显该被引 / 该存在、却没出现在 intro 里？
    • 关于缺失数据下的分类，特别是使用 k-NN 或树的方法：例如，处理缺失数据的 k-NN 方法（如加权 k-NN 或基于距离的插补）在应用文献中很常见，但本文的 intro 没有引用这些工作。这可能是因为这些工作缺乏 minimax 理论，但作为相关方法，它们的存在值得研究者去查。
    • 关于 ANOVA 分解在非参数估计中的其他应用：例如，在非参数回归中，ANOVA 分解被广泛用于处理高维问题（如 smoothing spline ANOVA）。本文引用了 D’Attilio & Sen (2022)，但可能忽略了更早的、关于 ANOVA 分解在 minimax 估计中的工作（如 Stone (1994) 关于 additive models 的工作）。这值得研究者去确认。

张力

未见明显对立引用。所有被引工作都指向同一个方向：在更复杂的设定（缺失数据 + 分类）下建立 minimax 理论。D’Attilio & Sen (2022) 的工作是本文最直接的先导，两者在方法论（ANOVA 分解）上一致，只是从回归推广到了分类。

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

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

  • 符号：
    • \( (X, Y) \)：随机变量对。\( X \in \mathbb{R}^d \) 是 \( d \) 维特征向量（协变量），\( Y \in \{0, 1\} \) 是二值标签。
    • \( \eta(x) = \mathbb{P}(Y=1 | X=x) \)：回归函数（regression function），即给定特征 \( X=x \) 时标签为 1 的条件概率。这是分类问题的核心对象。
    • \( g(x) = \mathbb{I}\{\eta(x) > 1/2\} \)：Bayes 分类器（最优分类器），即最小化 0-1 风险的分类器。
    • \( R(f) = \mathbb{P}(Y \neq f(X)) \)：分类器 \( f \) 的 0-1 风险（误分类概率）。
    • \( R^* = R(g) \)：Bayes 风险（最小可能风险）。
    • \( \mathcal{E}(f) = R(f) - R^* \)：分类器 \( f \) 的 excess risk（超额风险）。这是本文要最小化的目标。
    • \( \Delta \)：缺失指示变量（missing indicator）。\( \Delta = (\Delta_1, \ldots, \Delta_d) \)，其中 \( \Delta_j = 1 \) 表示第 \( j \) 个特征 \( X_j \) 被观测到，\( \Delta_j = 0 \) 表示缺失。
    • \( X_{\text{obs}} = \{X_j : \Delta_j = 1\} \)：观测到的特征子集。
    • \( p(x) = \mathbb{P}(\Delta = \delta | X = x) \)：缺失机制（missing mechanism），即给定完整特征 \( X=x \) 时，观测模式为 \( \delta \) 的条件概率。本文允许 MNAR，即 \( p(x) \) 可以依赖于 \( x \) 的任意部分。
    • \( n \)：样本量。
    • \( \mathcal{D}_n = \{(X_{\text{obs}, i}, \Delta_i, Y_i)\}_{i=1}^n \)：可观测数据集。每个样本包含：观测到的特征子集、缺失指示变量、标签。
  • 模型：
    • 数据生成机制：\( (X, Y) \) 来自某个未知联合分布。给定 \( X \)，\( Y \) 服从 Bernoulli(\( \eta(X) \))。缺失机制 \( p(x) \) 是任意的（允许 MNAR），但假设缺失机制不依赖于标签 \( Y \)（即 \( Y \) 总是被观测到，且缺失只发生在特征上）。这是一个关键假设，简化了问题。
    • 回归函数 \( \eta(x) \) 具有ANOVA 型正交分解：\( \eta(x) = \sum_{S \subseteq [d]} \eta_S(x_S) \)，其中 \( \eta_S \) 是仅依赖于特征子集 \( x_S \) 的函数，且这些函数相互正交（在某个概率测度下）。许多 \( \eta_S \) 可能为零（稀疏性）。
  • 可观测数据：
    • 研究者实际能观测到的是：\( \mathcal{D}_n = \{(X_{\text{obs}, i}, \Delta_i, Y_i)\}_{i=1}^n \)。
    • 想要但观测不到的是：完整的特征向量 \( X_i \)（当 \( \Delta_{i,j}=0 \) 时，\( X_{i,j} \) 缺失）。回归函数 \( \eta(x) \) 本身也是未知的、需要估计的对象。

第二步：讲最小内核

本文的核心思路可以用一个最简特例来理解：\( d=2 \)（两个特征），且回归函数是加性的（additive）。

  • 最简特例设定：

    • 特征 \( X = (X_1, X_2) \)，每个特征边际分布已知（或可估计）。
    • 回归函数是加性的：\( \eta(x_1, x_2) = \eta_1(x_1) + \eta_2(x_2) \)。这里 \( \eta_1 \) 和 \( \eta_2 \) 是正交的（例如，在 \( X_1 \) 和 \( X_2 \) 独立的乘积测度下）。
    • 缺失机制：假设 \( X_1 \) 总是被观测到（\( \Delta_1 = 1 \) 恒成立），而 \( X_2 \) 可能缺失（\( \Delta_2 \in \{0, 1\} \)）。缺失机制是 MNAR：\( \mathbb{P}(\Delta_2 = 1 | X_1=x_1, X_2=x_2) = p(x_1, x_2) \)，可以依赖于 \( X_2 \) 本身。
    • 目标：估计 Bayes 分类器 \( g(x) = \mathbb{I}\{\eta_1(x_1) + \eta_2(x_2) > 1/2\} \)，并最小化 excess risk。

  • 核心思路（为什么维度诅咒被打破）：

    • 在经典非参数分类中，要估计 \( \eta(x_1, x_2) \)，我们需要在 \( \mathbb{R}^2 \) 中做局部平均（如 k-NN），这需要样本量随维度指数增长。
    • 但在加性结构下，我们可以分别估计 \( \eta_1 \) 和 \( \eta_2 \)。由于 \( \eta_1 \) 只依赖于 \( X_1 \)，它的估计只需要在 \( \mathbb{R}^1 \) 中做局部平均，收敛速率是 \( n^{-2/3} \)（假设 \( \eta_1 \) 是 Lipschitz 的）。同样，\( \eta_2 \) 的估计也只需要在 \( \mathbb{R}^1 \) 中做局部平均。
    • 关键跳跃：即使 \( X_2 \) 有缺失，我们仍然可以估计 \( \eta_2 \)。如何做到？利用可观测数据中的“完整子集”。对于 \( \Delta_2 = 1 \) 的样本，我们观测到了 \( (X_1, X_2, Y) \)，因此可以直接用这些样本在 \( \mathbb{R}^1 \) 上估计 \( \eta_2 \)。由于 \( \eta_2 \) 是正交的，我们可以通过某种方式（如积分变换）从 \( \eta(x_1, x_2) \) 中“提取”出 \( \eta_2 \)，而不需要 \( X_2 \) 总是被观测到。
    • 结果：估计 \( \eta \) 的困难度从 \( d=2 \) 维问题降为两个 \( d=1 \) 维问题。因此，minimax 率中不会出现 \( d=2 \)，而只依赖于每个一维子问题的光滑度。这就是“维度诅咒被打破”的含义。

  • 这个特例下，要证的命题退化成什么：

    • 命题：存在一个分类器 \( \hat{g} \)，使得其 excess risk \( \mathcal{E}(\hat{g}) \) 以速率 \( n^{-\frac{\beta(1+\gamma)}{2\beta + (1+\gamma)}} \) 收敛到 0，其中 \( \beta \) 是 \( \eta_1 \) 和 \( \eta_2 \) 的光滑度，\( \gamma \) 是 margin condition 参数。这个速率与 \( d=2 \) 无关。
    • 证明思路：分别构造 \( \hat{\eta}_1 \) 和 \( \hat{\eta}_2 \)（例如，使用 k-NN 在各自的一维子空间上），然后令 \( \hat{g}(x) = \mathbb{I}\{\hat{\eta}_1(x_1) + \hat{\eta}_2(x_2) > 1/2\} \)。然后，利用分类问题的标准不等式（如 Tsybakov 的 margin condition 下的不等式）将 excess risk 与估计误差 \( \|\hat{\eta}_1 - \eta_1\|_\infty \) 和 \( \|\hat{\eta}_2 - \eta_2\|_\infty \) 联系起来。由于这些估计误差的速率是 \( n^{-\frac{\beta}{2\beta + 1}} \)（一维非参数回归的速率），结合 margin condition，即可得到 excess risk 的速率。

三、这篇论文做了什么

三句话

  1. 研究了什么问题：在特征可能非随机缺失（MNAR）的情况下，研究非参数二分类问题，目标是推导 excess risk 的 minimax 率，并构造一个达到该率的分类器。
  2. 核心工具 / 方法：假设回归函数具有稀疏的 ANOVA 型正交分解结构；提出 HAM（Hard-thresholding Anova Missing data）分类器，它结合了 k-NN 算法和 hard-thresholding 步骤，以自适应地选择重要的 ANOVA 成分。
  3. 主要结论：推导了 excess risk 的 minimax 率，该率依赖于回归函数的光滑度、ANOVA 成分的稀疏性、margin condition 和尾部行为，但不依赖于 ambient data dimension \( d \)。HAM 分类器在温和条件下达到该 minimax 率（至多 polylogarithmic 因子）。

关键设定与假设

在第二节最小记号的基础上，补全完整设定：

  • ANOVA 分解：假设回归函数 \( \eta(x) \) 可以分解为 \( \eta(x) = \sum_{S \subseteq [d]} \eta_S(x_S) \)，其中 \( \eta_S \) 是仅依赖于特征子集 \( x_S \) 的函数，且这些函数在某个乘积测度 \( \mu = \otimes_{j=1}^d \mu_j \) 下相互正交。稀疏性假设：只有少数 \( S \) 对应的 \( \eta_S \) 非零。具体地，定义 \( \mathcal{S} = \{S \subseteq [d] : \eta_S \not\equiv 0\} \)，假设 \( |\mathcal{S}| = M < \infty \)，且 \( M \) 可能远小于 \( 2^d \)。每个非零 \( \eta_S \) 的光滑度为 \( \beta_S \)（属于某个 Hölder 类）。
  • 缺失机制：允许 MNAR，但假设缺失机制不依赖于标签 \( Y \)（即 \( Y \) 总是被观测到）。缺失模式 \( \Delta \) 的分布 \( p(x) = \mathbb{P}(\Delta = \delta | X=x) \) 是任意的，但需要满足一个可识别性条件：对于每个非零的 ANOVA 成分 \( S \in \mathcal{S} \)，存在一个观测模式 \( \delta \) 使得 \( \delta_j = 1 \) 对所有 \( j \in S \) 成立，且 \( \mathbb{P}(\Delta = \delta | X=x) > 0 \) 对所有 \( x \) 成立。这意味着，对于每个重要的特征子集，总有一些样本能完整观测到该子集的所有特征。这是一个比 MAR 更弱的条件，但仍然是必要的。
  • 尾部行为：每个特征 \( X_j \) 的边际分布 \( \mu_j \) 的尾部行为由一个参数 \( \kappa_j \) 控制（例如，\( \mu_j \) 是 \( \kappa_j \)-次指数或 \( \kappa_j \)-次高斯）。这影响 k-NN 的邻域大小。
  • Margin Condition：存在常数 \( \gamma \ge 0 \) 和 \( C_0 > 0 \)，使得对于所有 \( t > 0 \)，有 \( \mathbb{P}(|\eta(X) - 1/2| \le t) \le C_0 t^\gamma \)。这刻画了决策边界附近的不确定性程度。\( \gamma \) 越大，问题越容易（边界附近样本少）。
  • 与已有文献的比较：相比 Audibert & Tsybakov (2007)，本文增加了缺失数据和 ANOVA 结构假设；相比 D’Attilio & Sen (2022)，本文从回归问题推广到分类问题，引入了 margin condition，并允许更一般的缺失机制（MNAR vs. MAR）。

主要结果

  • 定理 1（Minimax 下界）：在给定假设下，excess risk 的 minimax 率的下界为 \( n^{-\frac{\beta_*(1+\gamma)}{2\beta_* + (1+\gamma)}} \)，其中 \( \beta_* = \min_{S \in \mathcal{S}} \beta_S \) 是最小光滑度。这个率中不包含 ambient dimension \( d \)，只依赖于最重要的 ANOVA 成分的光滑度和 margin condition。直觉：因为每个 ANOVA 成分只依赖于一个低维子集，所以估计困难度由最粗糙的那个成分决定。
  • 定理 2（HAM 分类器的上界）：HAM 分类器 \( \hat{g}_{\text{HAM}} \) 的 excess risk 满足：
    \[\mathbb{E}[\mathcal{E}(\hat{g}_{\text{HAM}})] \le C \cdot (\log n)^\alpha \cdot n^{-\frac{\beta_*(1+\gamma)}{2\beta_* + (1+\gamma)}},\]
    其中 \( C \) 是常数，\( \alpha \) 是某个 polylogarithmic 指数。这意味着 HAM 分类器达到了 minimax 下界（至多对数因子）。
    • 必要条件：需要知道或能估计出每个 ANOVA 成分的光滑度 \( \beta_S \) 和稀疏模式 \( \mathcal{S} \)。在实际中，HAM 通过 hard-thresholding 自适应地选择重要成分。
    • 解决的技术难点：如何同时处理缺失数据、非参数估计和结构选择。HAM 通过两步法解决：① 对每个可能的特征子集 \( S \)，使用 k-NN 估计 \( \eta_S \)（仅使用完整观测到 \( S \) 中所有特征的样本）；② 对估计出的 \( \hat{\eta}_S \) 进行 hard-thresholding，只保留那些“显著”非零的成分。

证明路线与技术技巧

  • 整体路线：

    1. 构造候选估计量：对于每个可能的特征子集 \( S \subseteq [d] \)，构造 \( \eta_S \) 的估计量 \( \hat{\eta}_S \)。这通过 k-NN 实现：对于给定的 \( x_S \)，找到训练集中那些完整观测到 \( S \) 中所有特征的样本，并基于这些样本的 \( Y \) 值在 \( x_S \) 的邻域内做平均。
    2. Hard-thresholding 选择：对每个 \( \hat{\eta}_S \)，计算其“范数”（如 \( L_2 \) 范数或 sup 范数），并与一个阈值 \( \tau_n \) 比较。如果 \( \|\hat{\eta}_S\| < \tau_n \)，则将其设为 0。这一步是为了自适应地识别稀疏模式 \( \mathcal{S} \)。
    3. 最终分类器：令 \( \hat{\eta}(x) = \sum_{S: \|\hat{\eta}_S\| \ge \tau_n} \hat{\eta}_S(x_S) \)，然后定义 \( \hat{g}_{\text{HAM}}(x) = \mathbb{I}\{\hat{\eta}(x) > 1/2\} \)。
    4. 误差分解：将 excess risk 分解为估计误差和选择误差。估计误差来自 k-NN 估计的方差和偏差；选择误差来自 hard-thresholding 可能错误地剔除重要成分或保留噪声成分。
    5. 控制误差：利用 k-NN 的收敛速率、ANOVA 成分的正交性、以及阈值 \( \tau_n \) 的适当选择，证明估计误差和选择误差都以目标速率收敛。

  • 关键跳跃点：

    • 如何利用缺失数据估计 \( \eta_S \)：这是最吃功夫的地方。对于给定的 \( S \)，我们只能使用那些 \( \Delta_j = 1 \) 对所有 \( j \in S \) 成立的样本。这些样本的数量可能远小于 \( n \)，且其分布可能因为缺失机制而偏离原始分布。作者通过条件化于观测模式来处理这个问题，并证明 k-NN 在这些“完整子集”上仍然有效，只要缺失机制满足可识别性条件。
    • Hard-thresholding 阈值的选取：阈值 \( \tau_n \) 必须足够大以剔除噪声，但又不能太大以至于剔除弱信号成分。作者利用 k-NN 估计的收敛速率和浓度不等式来设定 \( \tau_n \)，并证明其能正确识别稀疏模式。

  • 技术技巧点名：

    • k-NN 估计：用于非参数地估计每个 ANOVA 成分 \( \eta_S \)。利用了 k-NN 在低维空间（\( |S| \) 维）的良好收敛性质。
    • Hard-thresholding：用于自适应地选择重要的 ANOVA 成分。这是处理稀疏性的标准技巧。
    • 浓度不等式（Concentration inequalities）：用于控制 k-NN 估计的误差和 hard-thresholding 的误选概率。具体地，可能使用了 Bernstein 不等式或 Hoeffding 不等式来推导 \( \|\hat{\eta}_S - \eta_S\|_\infty \) 的界。
    • Tsybakov 的 margin condition 不等式：用于将 excess risk \( \mathcal{E}(\hat{g}) \) 与回归函数的估计误差 \( \|\hat{\eta} - \eta\|_\infty \) 联系起来。这是分类问题证明的标准工具。

真实例子与应用

本文包含数值实验，但没有真实数据例子。

  • 模拟实验：
    • 数据 / 场景：生成 \( d=10 \) 维特征，但回归函数只依赖于 2 个特征（即 \( M=1 \)，\( |S|=2 \)）。缺失机制是 MNAR：缺失概率依赖于特征本身。比较 HAM 与几个 baseline 方法：完整数据 k-NN（仅使用无缺失样本）、插补 k-NN（均值插补后使用 k-NN）、以及一个 oracle 方法（知道真实稀疏模式）。
    • 如何应用：HAM 被直接应用于模拟数据。它首先对所有可能的特征子集（最多 \( 2^d \) 个，但通过计算限制只考虑小规模子集）进行 k-NN 估计，然后进行 hard-thresholding。
    • 结果：HAM 的 excess risk 显著低于完整数据 k-NN 和插补 k-NN，且接近 oracle 方法。随着样本量增加，HAM 的收敛速率与理论预测一致。
    • 这个例子想说明什么：验证了 HAM 在有限样本下的实用性，并展示了其相对于简单处理缺失数据的方法的优势。它说明，即使缺失机制是 MNAR，通过利用 ANOVA 结构，仍然可以有效地进行分类。

🔎 结论是否比证明窄

  • 窄的地方：定理 2 的上界依赖于已知或能估计出每个 ANOVA 成分的光滑度 \( \beta_S \)。在实际中，HAM 通过 hard-thresholding 自适应地选择成分，但阈值 \( \tau_n \) 的选择依赖于对 k-NN 估计误差的界，而这个界又依赖于光滑度。作者在定理陈述中可能假设了光滑度是已知的，或者阈值选择依赖于光滑度的上界。在数值实验中，他们可能通过交叉验证来选择阈值，但这在理论上不一定能保证达到 minimax 率。具体语句：定理 2 的陈述中可能包含“假设 \( \beta_S \) 已知”或“假设阈值 \( \tau_n \) 以某种方式依赖于 \( \beta_S \)”。需要去原文确认。
  • 泛化的地方：作者在 intro 和结论中声称 HAM 可以处理“高维”数据，但模拟实验只用了 \( d=10 \)。理论上，ANOVA 结构假设确实打破了维度诅咒，但计算复杂度随着 \( d \) 增长而指数增长（因为需要枚举所有可能的特征子集 \( S \)）。作者在文中可能提到了通过限制子集大小（如只考虑 \( |S| \le k \)）来缓解计算问题，但这在理论上是否仍然能达到 minimax 率？这是一个潜在的 gap。

四、开放问题

  1. 计算复杂度与统计效率的 tradeoff：本文的 HAM 方法需要枚举所有可能的特征子集 \( S \subseteq [d] \)，这在 \( d \) 较大时计算上不可行。作者提到了可以通过限制子集大小来缓解，但这种限制是否会改变 minimax 率？ 是否存在一个计算上可行（如多项式时间）且统计上最优的分类器？这扎根于本文对计算复杂度的回避。
  2. 缺失机制依赖于标签 \( Y \)：本文假设缺失机制不依赖于 \( Y \)。如果 \( Y \) 也影响缺失概率（例如，患病的人更不愿意报告某些特征），问题会变得复杂得多。在这种情况下，minimax 率会如何变化？ 是否仍然可以通过 ANOVA 结构来缓解？这扎根于本文的假设 1（缺失机制不依赖于 Y）。
  3. 更一般的结构假设：ANOVA 分解假设成分是正交的。如果回归函数具有更一般的结构（如稀疏加性模型、或低维流形结构），本文的框架是否可以推广？ 相应的 minimax 率是什么？这扎根于本文对 ANOVA 结构的依赖。
  4. 与 higher-order U-statistics 的潜在联系：本文的 k-NN 估计本质上是一个 U-statistic（或 V-statistic）。ANOVA 分解与 U-statistics 的 Hoeffding 分解有深刻的联系。能否利用 higher-order U-statistics 的理论（如树宽 / tensor contraction）来更高效地计算 HAM 分类器？ 例如，对于复杂的 ANOVA 成分，其 k-NN 估计的计算成本可能很高，而 tensor-network 方法可能提供加速。这扎根于研究者自身的兴趣，以及本文对计算复杂度的回避。

Maintained by 陈星宇 · Homepage · Source on GitHub

评论