跳转至

Differentially Private High-dimensional Variable Selection via Integer Programming

会议: NeurIPS 2025
arXiv: 2510.22062
代码: github.com/petrosprastakos/DP-variable-selection
领域: AI安全 / 差分隐私
关键词: 差分隐私, 稀疏变量选择, 混合整数规划, 指数机制, 最佳子集选择

一句话总结

本文提出两种纯差分隐私的稀疏变量选择方法 (top-R 和 mistakes)，利用现代混合整数规划 (MIP) 技术高效探索非凸目标景观，在高维设置（p 达 10000）下实现 SOTA 支撑集恢复率，同时提供理论恢复保证。

研究背景与动机

  1. 领域现状：高维稀疏变量选择 (Best Subset Selection, BSS) 是统计学经典问题，目标为最小化一个损失函数使得系数零范数不超过 s。近年来 MIP 技术使得非私有 BSS 可在百万变量规模下高效求解。
  2. 现有痛点：现有 DP 变量选择方法要么基于 Lasso（支撑恢复概率不趋于 0）、要么需枚举所有 C(p,s) 个可行支撑集（指数级复杂度不可扩展）、要么仅提供近似 DP 保证。
  3. 核心矛盾：指数机制在变量选择中需要遍历指数级大的输出空间，计算和采样都不可行。
  4. 本文要解决什么？ 设计可扩展的纯 DP 变量选择算法，利用 MIP 技术避免穷举所有支撑集。
  5. 切入角度：观察到远离最优支撑的候选集目标值很大，在指数机制中概率质量极小，因此只需精确计算前 R 个最优支撑集的目标值，其余用下界替代。
  6. 核心idea一句话：用 MIP 求解器高效找到前 R 个最优支撑集，对其余支撑集用第 R 个的目标值作为下界，构造截断版指数机制实现纯 DP。

方法详解

整体框架

输入为数据矩阵 X 和观测 y、隐私参数 epsilon。两种方法均基于指数机制的修改版本，输出一个大小为 s 的特征子集 S。

关键设计

  1. Top-R 方法 (Algorithm 1):
  2. 做什么：从修改后的指数机制中采样支撑集
  3. 核心思路：先用 MIP 求解器找到目标值最小的前 R 个支撑集，对 k <= R 使用真实目标值，对 k > R 统一用第 R 个的目标值作下界
  4. 采样分布：P_0(k) 正比于 exp(-eps * R(S_k, D)/(2Delta)) 对 k <= R；P_0(R+1) 正比于 (C(p,s)-R)exp(-epsR(S_R, D)/(2Delta))

  5. 隐私保证：当 T -> inf 时为纯 eps-DP（Theorem 1），仅需标准数据有界假设

  6. Mistakes 方法:

  7. 做什么：按与最优支撑集的"错误数"分组采样
  8. 核心思路：将支撑集按与最优支撑不同的特征数 t 分为 s+1 组，每组内只计算最优支撑集的目标值
  9. 隐私保证：在目标间隔条件下为纯 eps-DP

  10. 设计动机：只需 s+1 个 MIP 求解（vs top-R 的 R 个），且理论恢复条件更弱

  11. MIP 求解 — 外近似算法 (Algorithm 2):

  12. 做什么：高效求解 top-R 支撑集
  13. 核心思路：对加了岭惩罚的目标构造切平面近似（利用 Danskin 定理计算梯度），通过外近似迭代求解 MIP
  14. 支持任意凸损失函数（最小二乘、Hinge loss、Huber loss 等），算法框架不变

损失函数 / 训练策略

  • 全局灵敏度 Delta = 2b_y^2 + 2b_x^2r^2s（由数据有界假设推导）
  • 实验中设置 R = 2 + (p-s)*s，b_x = b_y = 0.5，r = 1.1

实验关键数据

主实验：支撑集恢复率 (p=10000, s=5, SNR=5, rho=0.1, eps=1)

方法 n=200 n=400 n=600 n=800 DP 类型
Top-R (本文) ~15% ~55% ~85% ~95% 纯 eps-DP
Mistakes (本文) ~25% ~70% ~92% ~98% 纯 eps-DP
MCMC (Roy & Tewari) ~5% ~20% ~45% ~60% 近似 DP
Samp-Agg (Lasso) <5% ~10% ~15% ~20% 纯 eps-DP

理论恢复条件对比

方法 tau 充分条件 额外假设
非私有 BSS tau >> log(p)/n 无
指数机制 (枚举) tau >> max(log(p)/n, slog(p)/(neps)) 需枚举 C(p,s)
Top-R (本文) tau >> max(log(p)/n, s^2log(p)/(neps)) 仅需有界数据
Mistakes (本文) tau >> max(slog(p)/n, slog(p)/(n*eps)) 需目标间隔条件

关键发现

  • Mistakes 方法在所有参数设置下数值上优于 top-R，与理论一致
  • 两种方法显著优于 MCMC 和 Samp-Agg 基线，尤其在 n 较大时几乎完美恢复
  • 低隐私场景中 top-R 的 log(p)/n 项主导，匹配非私有最优率
  • 扩展到 Hinge loss 做稀疏分类同样有效

亮点与洞察

  • 将 MIP 求解器引入 DP 采样，巧妙地将指数级枚举问题转化为有限次 MIP 调用。这一思路可迁移到任何 DP 组合优化问题
  • Mistakes 方法将指数级支撑空间压缩为 s+1 个分区，每组只需一次 MIP 求解
  • 外近似算法利用 Danskin 定理使得子问题梯度可解析计算，避免数值微分
  • R 的选择体现了隐私-精度-计算量的三方权衡，R 越大精度越高但计算成本增加且隐私损失也增大
  • 纯 DP 保证比近似 DP 更强，在医疗、金融等高敏感领域更受信任

局限性 / 可改进方向

  • Mistakes 方法的隐私保证依赖额外的目标间隔假设
  • 理论恢复保证仅限于 BSS (最小二乘)，尽管实验证明对 Hinge loss 也有效
  • Top-R 的恢复条件比完整指数机制多一个因子 s
  • MIP 求解器在超大规模 (p > 10^5) 时可能遇到扩展性瓶颈

相关工作与启发

  • vs Roy & Tewari (2024, MCMC): 他们用 MCMC 近似指数机制，只提供近似 DP；本文提供纯 DP，且实验表现显著更好
  • vs Lei et al. (2024): 他们直接枚举所有支撑集使用指数机制，不可扩展；本文通过 MIP 避免枚举
  • vs Kifer & Smith (2011, propose-test-release): 他们的方法有非零失败概率且不随 n 趋于 0；本文方法在足够大 n 时高概率恢复
  • 本文的截断指数机制思路可推广到 DP 子集选择、DP 特征工程等组合优化场景
  • 对实际应用（医疗、金融、推荐系统中的敏感数据特征选择）有直接意义
  • 所有实验均在 20 核 64GB RAM 集群上完成，使用 Gurobi 求解器，实际运行时间与 MCMC 方法可比

评分

  • 新颖性: ⭐⭐⭐⭐ MIP + DP 的结合是全新方向，两种截断指数机制设计巧妙
  • 实验充分度: ⭐⭐⭐⭐ 多参数消融、p 达 10000、包含 Hinge loss 扩展
  • 写作质量: ⭐⭐⭐⭐ 理论结果陈述清晰，算法伪代码完整
  • 价值: ⭐⭐⭐⭐ 为 DP 变量选择提供了首个实用且有理论保证的纯 DP 方案