用整数规划实现高维变量选择的差分隐私方法，兼顾精准与安全。
Differentially Private High-dimensional Variable Selection via Integer Programming
- 基于现代整数规划技术，设计差分隐私下的稀疏变量选择算法。
- 在高达10^4个变量的场景下，支持集恢复准确率超越现有方法。
- 适合关注隐私保护与模型可解释性的机器学习研究者使用。
稀疏变量选择通过筛选少量信息特征，提升高维学习中的可解释性与泛化能力。近年来，混合整数规划（MIP）技术已使大规模非私有稀疏回归——即最优子集选择（BSS）——在数百万变量规模下分钟级求解成为可能。然而，将此类算法进展拓展至差分隐私（DP）场景仍鲜有探索。本文提出两种新的纯差分隐私估计器用于稀疏变量选择，利用现代MIP技术。该框架具有通用性，适用于稀疏回归或分类等任务，并在BSS情形下提供理论支持恢复保证。受指数机制启发，我们设计了结构化采样方法，高效探索非凸目标函数空间，避免指数机制中耗时的组合穷举搜索。通过大量数值实验，采用最小二乘与铰链损失作为目标函数，结果表明，所提方法在高达p=10^4的设定下，实现当前最优的实证支持集恢复性能。
原文摘要 · Abstract (English)
Sparse variable selection improves interpretability and generalization in high-dimensional learning by selecting a small subset of informative features. Recent advances in Mixed Integer Programming (MIP) have enabled solving large-scale non-private sparse regression - known as Best Subset Selection (BSS) - with millions of variables in minutes. However, extending these algorithmic advances to the setting of Differential Privacy (DP) has remained largely unexplored. In this paper, we introduce two new pure differentially private estimators for sparse variable selection, levering modern MIP techniques. Our framework is general and applies broadly to problems like sparse regression or classification, and we provide theoretical support recovery guarantees in the case of BSS. Inspired by the exponential mechanism, we develop structured sampling procedures that efficiently explore the non-convex objective landscape, avoiding the exhaustive combinatorial search in the exponential mechanism. We complement our theoretical findings with extensive numerical experiments, using both least squares and hinge loss for our objective function, and demonstrate that our methods achieve state-of-the-art empirical support recovery, outperforming competing algorithms in settings with up to $p=10^4$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。