跳转至

Knockoffs Inference under Privacy Constraints

讲者: Lan Gao
会场: Trustworthy and Privacy-Preserving Statistical Learning
报告题目: Knockoffs Inference under Privacy Constraints
链接: arXiv
来源: JCSDS 2026 · 返回会议总览

一、领域脉络与小综述

这个方向是什么

这个子方向要解决的根本问题是：如何在保护数据隐私（差分隐私）的前提下，进行高维变量选择，并同时控制错误发现率（FDR）。其核心张力在于：差分隐私要求向输出中添加噪声以掩盖个体信息，而FDR控制方法（如Benjamini-Hochberg、Knockoffs）通常依赖于统计量的精确分布或对称性，噪声的加入会破坏这些性质，导致FDR失控或功效严重下降。当前该方向的成熟度处于快速发展期：已有若干工作解决了特定设定下的DP-FDR问题（如基于p-value的BH过程、线性模型下的镜像统计量），但在非线性、模型无关（model-free）的高维设定下，如何同时实现精确FDR控制与隐私保护，仍是一个开放问题。本文正是针对这一缺口，将Model-X Knockoffs框架与差分隐私结合。

发展脉络（history）

  1. 奠基工作：

    • Dwork et al. (2006)：提出差分隐私（DP）的数学定义，为隐私保护提供了严格框架。
    • Barber & Candès (2015)：提出Knockoffs方法，首次实现在有限样本下对变量选择的FDR控制，但最初版本要求已知协变量X的分布（Model-X）。
    • Candès et al. (2018)：将Knockoffs推广为“Model-X”框架，使其在已知X分布时，对Y的依赖关系（模型）完全自由，实现了模型无关的FDR控制。这是本文的直接基础。

  2. 主要进展（DP + FDR）：

    • Dwork, Su & Zhang (2021)：首次将DP与FDR控制结合，基于Benjamini-Hochberg (BH) 过程。其核心思路是直接向p-value添加噪声，但只能提供保守的FDR上界（即实际FDR远低于目标水平q），因为噪声破坏了p-value在零假设下的均匀性。
    • Xia & Cai (2023)：改进了DP-BH方法，通过向变换后的p-value添加噪声，实现了精确的有限样本FDR控制。但该方法仍依赖于p-value的存在，不适用于模型无关的设定。
    • Cai et al. (2023)：针对高维线性模型，提出了基于样本分裂和镜像统计量的DP-FDR控制方法。该方法将问题限制在线性模型内。

  3. 当前Frontier与本文位置：

    • 上述DP-FDR方法要么是保守的（Dwork et al. 2021），要么依赖于p-value（Xia & Cai 2023），要么局限于线性模型（Cai et al. 2023）。如何在非线性、模型无关的设定下，实现DP下的精确FDR控制，是文献中的一个明确缺口。
    • 本文（Cai, Fan & Gao, 2025） 正是填补这一缺口：它首次将Model-X Knockoffs框架与差分隐私结合，提出了DP-Knockoff方法。其核心贡献在于：证明了通过“镜像剥离”（mirror peeling）算法加噪，可以保留Knockoffs的“抛硬币”性质，从而在DP下实现精确的有限样本FDR控制。同时，本文还进行了功效分析，给出了噪声不损害渐近功效的充分条件。

子线索聚类

  1. DP下的FDR控制（基于p-value/BH）：Dwork et al. (2021), Xia & Cai (2023)。这类方法依赖于p-value的可用性，核心是处理噪声对p-value分布的影响。
  2. Knockoffs方法的扩展与稳健性：Barber & Candès (2015), Candès et al. (2018), Fan et al. (2020, 2025a, 2025b), Barber et al. (2020)。这类方法致力于提升Knockoffs的功效、稳健性或适用范围，但未考虑隐私。
  3. 高维DP变量选择：Cai et al. (2023)。这类方法针对高维线性模型，使用样本分裂和镜像统计量。本文的“两步骤策略”（Algorithm 3）也属于此类，但将其推广到了更一般的模型。

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

  1. 如何在DP下保持FDR控制的精确性？ 噪声的加入会破坏统计量的对称性或分布假设，导致FDR控制失效或变得保守。
  2. 如何最小化DP对变量选择功效的损害？ 隐私保护与统计功效之间存在根本性权衡。需要找到噪声水平与功效损失之间的定量关系。
  3. 如何处理高维（p >> n）带来的挑战？ 高维下，统计量的敏感性（sensitivity）可能随维度p增长，导致所需噪声过大，完全摧毁功效。需要设计降维或筛选策略。
  4. 如何实现模型无关（model-free）的DP变量选择？ 现有DP-FDR方法多依赖于特定模型（如线性模型）或p-value。Model-X Knockoffs提供了一个模型无关的框架，但将其与DP结合面临新的技术挑战（如Knockoffs生成的随机性如何影响敏感性）。

⚠️ 作者的framing

  • 作者把缺口frame成什么？ 作者在引言中明确指出：“How to control the FDR for high-dimensional data in general nonlinear models while ensuring privacy protection remains an open question in the literature.” 他们将这个“开放问题”作为自己工作的直接动机，并将本文定位为“首次”将Model-X Knockoffs与DP结合，从而填补了这一空白。
  • 哪些竞争路线被他淡化或回避了？
    • 基于p-value的DP-FDR方法（Dwork et al., 2021; Xia & Cai, 2023）：作者承认这些方法存在，但指出它们“only applicable when the p-values for each hypothesis are available”，即不适用于模型无关的设定。这实际上是将自己的方法与它们区分开，强调自己方法的“model-free”优势。
    • 高维线性模型下的DP-FDR（Cai et al., 2023）：作者将其作为背景提及，但指出其局限于线性模型。本文的“两步骤策略”（Algorithm 3）在精神上与Cai et al. (2023)的样本分裂+镜像统计量有相似之处，但作者将其推广到了更一般的Knockoffs框架下。
  • 什么明显该被引/该存在、却没出现在intro里？ 未见明显缺失。intro的引用覆盖了DP、Knockoffs和DP-FDR三个子领域的关键文献。

张力

未见明显对立引用。各工作之间是互补关系，分别解决了不同设定下的DP-FDR问题。

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

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

  • 符号：

    • \(Y\): 响应变量（随机变量）。
    • \(X = (X_1, \dots, X_p)^T\): \(p\)维协变量向量（随机变量）。
    • \(S_0 \subset \{1, \dots, p\}\): 真正的相关变量集合（非空集）。
    • \(H_0 = S_0^c\): 零变量（null features）集合。
    • \(n\): 样本量。
    • \(p\): 变量维度。
    • \(q \in (0,1)\): 目标FDR水平。
    • \(\mu > 0\): 隐私预算参数（\(\mu\)-GDP）。\(\mu\)越小，隐私保护越强。
    • \(\Delta_n\): 统计量的\(l_1\)敏感性（sensitivity）。
    • \(m\): 镜像剥离算法中的“剥离大小”（peeling size），即最终披露的统计量个数。
    • \(\widetilde{X}\): Knockoffs变量矩阵（\(n \times p\)）。
    • \(W_j\): 第\(j\)个变量的Knockoffs统计量。正值表示变量重要，负值表示不重要。
    • \(\widetilde{W}_j\): 加噪后的Knockoffs统计量。
    • \(T^*\): 原始Knockoffs过程的选择阈值。
    • \(\widetilde{T}\): DP-Knockoffs过程的选择阈值。
    • \(\widehat{S}\): 最终选出的变量集合。

  • 模型：

    • 数据生成机制：\((X_i, Y_i) \overset{i.i.d.}{\sim} P_{X,Y}\)，其中\(P_X\)已知（Model-X假设），\(P_{Y|X}\)完全未知（模型无关）。
    • 目标：识别最小的变量子集\(S_0\)，使得\(Y \perp\!\!\!\perp X_{S_0^c} | X_{S_0}\)。
    • 已知量：\(P_X\)（用于生成Knockoffs）。
    • 待估对象：\(S_0\)。

  • 可观测数据：

    • 可观测：\(\{(x_i, y_i)\}_{i=1}^n\)，即\(n\)个独立同分布的样本。
    • 潜在/不可观测：
      1. \(S_0\)本身。
      2. Knockoffs变量\(\widetilde{X}\)：它们不是数据的一部分，而是由研究者根据已知的\(P_X\)和观测到的\(X\)生成出来的。生成过程引入了额外的随机性（记为\(R_i\)）。
      3. “真正的”变量重要性：我们只能通过\(W_j\)来推断。

第二步：讲最小内核

本文的核心思路可以用一个最简特例来理解：假设只有两个变量（\(p=2\)），且我们只关心其中一个（\(m=1\)）。

  • 设定：

    • \(p=2\)，变量为\(X_1, X_2\)。真实相关集\(S_0 = \{1\}\)（即\(X_1\)重要，\(X_2\)不重要）。
    • 我们使用边际相关系数作为Knockoffs统计量：\(W_j = n^{-1}(|X_j^T y| - |\widetilde{X}_j^T y|)\)。
    • 根据Lemma 2，边际相关系数的敏感性\(\Delta_n = O(n^{-1})\)，是维度无关的。
    • 我们设定镜像剥离大小\(m=1\)，即最终只披露一个统计量。

  • 核心问题：如何在保护隐私（\(\mu\)-GDP）的前提下，仍然能选出\(X_1\)并控制FDR？

  • 核心思路（镜像剥离 + 加噪）：

    1. 计算原始统计量：计算\(W_1\)和\(W_2\)。由于\(X_1\)重要，我们期望\(|W_1|\)很大（正值），而\(|W_2|\)很小（接近0）。
    2. 镜像剥离（Mirror Peeling）：我们不直接披露\(W_1\)和\(W_2\)，而是先找出绝对值最大的那个。在这个例子中，应该是\(W_1\)。我们只“剥离”出这个最大的统计量，并丢弃另一个（\(W_2\)）。这一步的关键是：选择“剥离”哪个统计量，只依赖于统计量的绝对值\(|W_j|\)和独立噪声\(Z_{k,j}\)，而不依赖于其符号。
    3. 加噪：对被选中的统计量\(W_1\)，添加一个独立的高斯噪声\(\widetilde{Z}_1\)，得到\(\widetilde{W}_1 = W_1 + \widetilde{Z}_1\)。噪声的方差与敏感性\(\Delta_n\)和隐私预算\(\mu\)有关。
    4. FDR控制：现在，我们只基于\(\widetilde{W}_1\)来做决策。由于：
      • \(W_2\)被丢弃了，我们永远不会错误地选择它。
      • 对于被选中的\(W_1\)，如果\(X_1\)是零变量（null），那么\(W_1\)的分布是对称的（正负等概率）。加上对称的高斯噪声\(\widetilde{Z}_1\)后，\(\widetilde{W}_1\)的分布仍然是对称的。这就是“抛硬币性质”（coin-flip property）。
      • 利用这个抛硬币性质，我们可以证明，基于\(\widetilde{W}_1\)的FDR控制仍然是精确的（Theorem 2）。

  • 为什么这个特例能说明问题？

    • 隐私保护：我们只披露了\(\widetilde{W}_1\)，而不是原始的\(W_1, W_2\)。通过控制噪声大小，可以保证\(\widetilde{W}_1\)满足\(\mu\)-GDP。
    • FDR控制：因为只披露了“最大”的统计量，且噪声是对称的，所以零变量的统计量（如果它不幸被选中）的符号仍然是随机的，从而保证了FDR控制。
    • 功效：如果\(W_1\)的信号足够强，那么即使加了噪声，\(\widetilde{W}_1\)仍然大概率是正的且大于阈值，从而被选中。功效损失主要来自于噪声可能将\(W_1\)“拉”到阈值以下。

这个特例揭示了本文的核心机制：通过“镜像剥离”只披露少数“候选”统计量，再通过“加噪”来保护隐私，同时利用Knockoffs统计量固有的对称性来维持FDR控制。论文的一般情形（\(m>1\)，任意\(p\)）只是这个特例的推广：剥离出\(m\)个最大的统计量，对每个都加噪，然后基于这\(m\)个加噪后的统计量进行Knockoffs过程。

三、这篇论文做了什么

三句话

  1. 研究了什么问题：在差分隐私（DP）约束下，如何对高维数据进行模型无关（model-free）的变量选择，并同时保证精确的有限样本FDR控制。
  2. 核心工具/方法：提出了一个名为“镜像剥离”（Mirror Peeling）的算法，将其与Model-X Knockoffs框架结合，通过只披露部分加噪后的Knockoffs统计量来实现隐私保护，同时保留FDR控制性质。
  3. 主要结论：提出的DP-Knockoff方法（Algorithm 1）满足\(\mu\)-GDP，并能实现精确的有限样本FDR控制（Theorem 2）。在敏感性足够小、剥离大小足够大的条件下，DP-Knockoff的渐近功效损失可以忽略不计（Theorem 3 & 4）。对于高维设定，提出了一个两步骤策略（Algorithm 3），通过先进行DP特征筛选再应用DP-Knockoff，也能实现无条件FDR控制（Theorem 7）。

关键设定与假设

  • Model-X假设：协变量\(X\)的分布\(P_X\)是已知的。这是Knockoffs方法的基础。
  • 有界性假设：协变量和响应变量几乎必然有界：\(\|X\|_\infty \leq C_x, |Y| \leq C_y\)。这是为了分析统计量的敏感性（sensitivity），是DP分析的标准要求。
  • 稀疏性假设：真正相关变量的数量\(s = |S_0| = o(n \wedge p)\)。这是高维统计的常见假设，用于保证变量选择的可识别性和方法的有效性。
  • Knockoffs生成函数的确定性形式：假设Knockoffs变量\(\widetilde{X}_{i,\cdot}\)是原始数据\(X_{i,\cdot}\)和独立随机变量\(R_i\)的确定性函数（式7）。通过固定随机种子，可以确保相邻数据集生成的Knockoffs矩阵只在对应行不同，从而简化敏感性分析。这是一个技术性假设，用于处理Knockoffs生成过程中的随机性。
  • 相比已有文献：
    • 放宽：相比Dwork et al. (2021)和Xia & Cai (2023)，本文不依赖于p-value，实现了模型无关的FDR控制。相比Cai et al. (2023)，本文不局限于线性模型。
    • 强化：相比原始的Model-X Knockoffs (Candès et al., 2018)，本文额外施加了DP约束，并引入了镜像剥离算法。

主要结果

  • Theorem 1 (隐私保证)：Algorithm 1（DP-Knockoff）是\(\mu\)-GDP的。这意味着整个算法满足\(\mu\)-高斯差分隐私。
  • Theorem 2 (精确FDR控制)：对于任意样本量\(n\)、剥离大小\(m\)、敏感性\(\Delta_n\)和隐私预算\(\mu\)，Algorithm 1的输出\(\widehat{S}\)满足\(\text{FDR}(\widehat{S}) \leq q\)。这是一个非渐近的、精确的结果，不依赖于任何模型假设。其证明依赖于加噪后统计量的“抛硬币性质”。
  • Theorem 3 (功效损失上界)：给出了DP-Knockoff相对于原始Knockoff的相对功效损失的一个上界（式11）。这个上界由三项组成：
    1. 信号变量统计量落在“噪声区间”\((t, t+b_n)\)内的期望个数。
    2. 原始Knockoff阈值\(T^*\)过大的概率。
    3. 零变量统计量分布不均匀的概率。 这个定理将功效分析转化为对这三项的控制。
  • Theorem 4 (强信号下的功效)：如果大部分相关变量都是“强信号”（即其统计量远大于噪声水平），那么只要剥离大小\(m\)略大于信号个数\(s\)，功效损失就可以忽略不计。这放松了Theorem 3中对\(m\)的下界要求。
  • Theorem 7 (高维下的FDR控制)：对于高维设定，Algorithm 3（两步骤策略）的输出\(\widehat{S}_1\)满足\(\text{FDR}(\widehat{S}_1) \leq q\)。这是一个无条件的FDR控制结果，不依赖于第一步筛选是否完美。

证明路线与技术技巧

  • 整体路线（以Theorem 2为例）：

    1. 条件化：将FDR的期望分解，并条件于统计量的绝对值\(\{|W_j|\}\)和用于剥离的独立噪声\(\{Z_{k,j}\}\)。在这个条件下，被剥离出的索引集\(D_m\)是确定的。
    2. 抛硬币性质：证明对于\(D_m\)中的零变量（\(j \in H_0 \cap D_m\)），其加噪后的统计量\(\widetilde{W}_j = W_j + \widetilde{Z}_j\)的符号是等概率的（即“抛硬币”）。这是因为\(W_j\)本身对称，且\(\widetilde{Z}_j\)是独立对称噪声。
    3. 鞅方法：利用抛硬币性质，构造一个关于“反向时间”的鞅（super-martingale）\(M(k) = V^+(k) / (1 + V^-(k))\)，其中\(V^+(k)\)和\(V^-(k)\)分别是前\(k\)个被剥离的零变量中，\(\widetilde{W}_j\)为正和为负的个数。
    4. 可选停时定理：证明选择阈值\(\widetilde{T}\)对应的索引是一个停时。应用可选停时定理，得到条件期望的上界为1。
    5. 完成证明：将条件期望代入FDR表达式，得到\(\text{FDR} \leq q\)。

  • 关键跳跃点：

    • 如何保证“抛硬币性质”在加噪后仍然成立？ 这是整个证明的基石。作者巧妙地利用了“镜像剥离”只依赖于绝对值这一事实，使得被选中的零变量统计量\(W_j\)的分布仍然是关于0对称的。加上对称噪声后，对称性得以保留。
    • 如何将“镜像剥离”与“鞅方法”结合？ 原始Knockoffs的FDR控制证明依赖于所有统计量的“抛硬币性质”。在DP-Knockoff中，只有被剥离出的\(m\)个统计量被披露。作者证明，在这\(m\)个统计量上，鞅方法仍然适用，因为它们的符号条件独立且等概率。

  • 技术技巧点名：

    • 镜像剥离（Mirror Peeling）：核心算法技巧，用于选择性地披露统计量，控制敏感性。
    • 高斯机制（Gaussian Mechanism）：用于向统计量添加噪声以实现\(\mu\)-GDP。
    • 鞅方法（Martingale Method）：用于证明FDR控制，是Knockoffs文献中的标准技术。
    • 敏感性分析（Sensitivity Analysis）：对四种不同的Knockoffs统计量（边际相关、HSIC、岭回归、SGD）进行了详细的敏感性分析，这是DP分析的关键步骤。
    • 样本分裂（Sample Splitting）：在高维两步骤策略中，将数据分为两部分，一部分用于筛选，一部分用于Knockoffs推断，以实现无条件FDR控制。

真实例子与应用

  • 数据/场景：模拟数据。线性模型\(Y = X^T\beta + \varepsilon\)，其中\(X\)来自\(p\)维高斯分布，协方差矩阵为AR(1)结构。前10个\(\beta\)分量为1，其余为0。
  • 方法应用：
    • 低维/中等维度：直接应用Algorithm 1（DP-Knockoff），使用边际相关系数作为统计量。
    • 高维：应用Algorithm 3（两步骤策略）。第一步用DP特征筛选（Algorithm 2）将维度从\(p\)降到\(K_n=20\)。第二步在筛选后的变量上，使用岭回归系数差作为Knockoffs统计量，并加噪。
  • 结果：
    • FDR控制：在所有模拟设定下（不同\(n, p, \beta, \mu\)），DP-Knockoff的FDR都控制在目标水平\(q=0.2\)附近，验证了Theorem 2和7。
    • 功效：DP-Knockoff的功效低于非隐私版本（NP），但随着样本量\(n\)、信号强度\(\beta\)和隐私预算\(\mu\)的增加而提升。在高维设定下，维度\(p\)对功效影响不大，说明特征筛选有效。
  • 这个例子想说明什么：验证了DP-Knockoff方法在有限样本下的FDR控制性质和功效表现，展示了其在低维和高维设定下的有效性，并揭示了隐私预算、信号强度和样本量对功效的权衡。

🔎 结论是否比证明窄

  • 是。论文的主要理论结果（Theorem 2, 3, 4, 7）都是在特定假设下严格证明的。然而，在讨论部分（Section 7），作者提出了一些更泛化的claim或conjecture：
    • “the addition of noise enhances the stability of the knockoff process in controlling FDR.” 这是一个观察性结论，论文并未提供理论证明。作者将其作为未来研究方向（“It would be interesting to further investigate the algorithm stability”）。
    • “the DP-Knockoff framework accommodates certain inaccuracies in the estimation of knockoff statistics.” 作者指出，只要噪声足够大，就能“dominate”估计误差，从而保持FDR控制。但这只是一个定性讨论，没有给出具体的定量条件（例如，估计误差需要小于噪声的某个倍数）。作者将其与Fan et al. (2025a,b)的稳健性工作联系起来，作为未来方向。
    • 在高维两步骤策略（Algorithm 3）中，作者没有给出功效分析（“We leave the power analysis of this two-step DP knockoffs inference in high-dimensions to future study.”）。因此，Theorem 7只保证了FDR控制，但未说明其功效表现。

四、开放问题

  1. 算法稳定性（Algorithm Stability）：论文观察到加噪能提升Knockoffs过程的稳定性。能否从理论上证明DP-Knockoff的稳定性（如Luo & Barber, 2024）？这需要定义并分析一个DP算法在FDR控制上的稳定性度量。扎根点：Section 7, “It would be interesting to further investigate the algorithm stability (Luo and Barber, 2024).”

  2. 高维两步骤策略的功效分析：Algorithm 3在高维下实现了FDR控制，但其功效表现如何？能否建立类似于Theorem 3和4的功效损失上界？这需要分析第一步DP筛选的“遗漏概率”和第二步DP-Knockoff的“功效损失”之间的权衡。扎根点：Section 5, “We leave the power analysis of this two-step DP knockoffs inference in high-dimensions to future study.”

  3. 非参数Knockoffs生成下的DP分析：论文的敏感性分析依赖于Knockoffs生成函数的确定性形式（式7）。对于更复杂的非参数Knockoffs生成方法（如基于深度学习的），如何定义和分析其敏感性？这可能是将DP-Knockoff推广到更复杂数据分布的关键。扎根点：Section 2.3, 假设(7)是分析的基础。

  4. 最优的隐私-功效权衡：论文给出了DP-Knockoff功效损失的上界，但这是否是最优的？是否存在一个信息论下界，表明任何满足\(\mu\)-GDP的Knockoffs方法都必然遭受至少某个程度的功效损失？这需要结合信息论和统计决策理论。扎根点：Theorem 3和4给出了充分条件，但未讨论必要性。

Maintained by 陈星宇 · Homepage · Source on GitHub

评论