Differentially Private High-dimensional Variable Selection via Integer Programming

AI summary

Overview

• Research area: High-dimensional statistics and machine learning, specifically sparse variable selection under Differential Privacy (DP), with a connection to mixed integer programming (MIP) optimization.
• Technical level: Advanced. It assumes familiarity with differential privacy, the exponential mechanism, high-dimensional statistics concepts (Sparse Riesz Condition, identifiability margins), and mixed integer programming.
• Scope: The paper introduces two pure-DP estimators for sparse support selection, proves support-recovery guarantees for Best Subset Selection (BSS), and reports numerical experiments using least squares and hinge loss with dimension up to p = 10,000.

What This Paper Is About

Selecting a small, interpretable set of informative features from a huge pool of candidate variables is a classic high-dimensional problem, but when the data is sensitive it must be done without leaking private information. The paper asks whether modern mixed integer programming (MIP) techniques—which have recently made non-private Best Subset Selection tractable at scale—can be adapted to deliver strong differential privacy guarantees without enumerating all possible supports. The goal is to produce estimators that are provably private, statistically accurate in recovering the true support, and computationally scalable to thousands of variables.

Key Contributions

1. Top-R method: A new pure differentially private estimator built by modifying the exponential mechanism. It satisfies pure DP under only a standard boundedness assumption on the data (achievable via clipping). For BSS, it recovers the true support with high probability whenever β_min ≳ sqrt(max{1, s²/ε}(log p)/n), matching the non-private minimax-optimal sqrt((log p)/n) threshold in the low-privacy regime.
2. Mistakes method: A second pure-DP estimator that partitions supports by the number of "mistakes" from the optimum. Its pure-DP guarantee requires an additional separation assumption on the objective gap, which holds with high probability in BSS under β_min ≳ sqrt(s log p/n); its support-recovery condition is β_min ≳ sqrt(max{1, 1/ε}(s log p)/n), aligning with prior work in the high-privacy regime.
3. Empirical state-of-the-art performance: The authors report that their methods outperform other DP variable selection methods, including the state-of-the-art approximate DP MCMC approach, across a wide range of parameter values and up to p = 10,000, and also perform well on sparse classification with hinge loss.
4. Scalable MIP-based computation: The paper shows how the top-R supports can be obtained by solving a sequence of mixed integer programs, and provides a tailored algorithm—including a ridge-penalized formulation solved via Danskin's theorem—to reach dimensions such as p = 10,000, beyond the reach of off-the-shelf solvers alone.

Main Findings

• Top-R is always private under boundedness: Theorem 1 shows the top-R procedure is (ε′, 0)-DP with ε′ = log(e^ε + q^T/δ_0) − log(1 − q^T), where δ_0 = exp(−nεb_y²/(2Δ))/(p choose s) and q = R/(p choose s). As T → ∞, ε′ → ε, giving pure (ε, 0)-DP.
• Privacy cost grows with R: The paper shows analytically that ε′ increases with R, so a larger R means more privacy loss—but intuitively better support recovery, creating a privacy/accuracy tradeoff.
• Global sensitivity bound: For least squares, Assumption 1 yields Δ ≤ 2b_y² + 2b_x²r²s.
• Mistakes method privacy condition: Theorem 2 shows the mistakes method is (ε, 0)-DP provided R(Ŝ₂(D), D) − R(Ŝ₁(D), D) > 2Δ; the paper shows this inequality holds with high probability under τ ≳ s log p/n plus Assumptions 2–4.
• Support recovery for top-R: Theorem 3 gives τ ≥ max{Cσ², 8Δ/ε · s} log p / n and P(ℳ̂(D) = S*) ≥ (1 − 10sp⁻²)/(1 + p⁻ˢ).
• Support recovery for mistakes: Theorem 4 gives τ ≥ max{Cσ²s, 16Δ/ε} log p / n and P(ℳ̃(D) = S*) ≥ (1 − 18sp⁻²)/(1 + 2p⁻²).
• Comparison to prior work: The top-R condition is τ ≳ max{log p/n, s² log p/(nε)}, versus τ ≳ max{log p/n, s log p/(nε)} for the exponential mechanism as in Theorem 3.5 of prior work; the mistakes condition τ ≳ max{s log p/n, s log p/(nε)} matches that prior work in high-privacy regimes.
• Reduced computational requirement: Unlike the exponential mechanism, which needs ℛ(S, D) for all (p choose s) supports, the mistakes method only needs the s+1 supports that minimize ℛ over each partition.
• General loss functions: Pure DP guarantees hold for general loss functions, not just least squares; the MIP approach works for any convex loss, with hinge-loss modifications discussed in the appendix.
• Non-private baseline condition: Prior work shows τ ≳ log p/n suffices for S* to be the unique BSS minimizer with high probability; this is the non-private benchmark the authors compare against.

Methodology in Plain English

The starting point is the exponential mechanism, a standard way to make a selection differentially private by sampling outcomes with probability proportional to exp(−εℛ/2Δ), where ℛ is the quality of an outcome (here, the fit of a candidate support) and Δ bounds how much any single data point can change ℛ.

The obstacle is that the exponential mechanism normally requires a score for every possible support, and there are (p choose s) of them—an astronomically large set. The authors' insight is that supports far from optimal almost certainly have much worse objective values, and so carry negligible probability. Instead of scoring all supports, they solve for the R best supports using mixed integer programming, then sample among just these R options plus one "everything else" bucket. When the bucket is chosen, the algorithm samples uniformly from the remaining supports, using a rejection-style loop.

The mistakes method takes a different tack: it groups all supports by how many coordinates they differ from the best support, keeping only the best representative of each group. This makes the outcome set small enough to sample from directly (only s+1 groups), and the resulting probabilities depend on the group sizes (p−s choose i)(s choose i).

To actually find the best supports at scale, the authors write the problem as a mixed integer program with binary selection variables z, linear constraints forcing exactly s nonzero coordinates, a ridge-like bound on the coefficients, and constraints that exclude previously found solutions. For large p they add a ridge penalty to make the problem strongly convex, use Danskin's theorem to compute gradients with respect to the relaxed selection variables, and solve the resulting sequence of problems with a specialized algorithm rather than a general-purpose solver.

Why This Matters

• Research impact: The paper is described as the first to incorporate MIP techniques into differentially private variable selection, and it achieves pure DP guarantees for general loss functions rather than only least squares. It connects two previously separate literatures—discrete optimization for sparse regression and private statistical estimation—and provides both support-recovery theory and practical scaling to p = 10,000.
• Real-world applications:
  • Private medical research, where patient records must remain confidential while researchers identify which clinical variables matter.
  • Financial modeling, where transaction or customer data is sensitive and institutions want interpretable sparse models.
  • Genomics and other high-dimensional biological studies, where feature counts are enormous and samples are few.
  • Any organization that must publish or share derived statistics about individuals while complying with privacy regulations.
• Industry relevance: The authors include an industry co-author, and the code is publicly released, which lowers the barrier for practitioners to apply DP variable selection in production settings. The scalability to p = 10,000 and support for losses such as hinge loss makes the methods applicable to classification tasks, not just regression.

Future Directions

• Characterizing the precise interplay between the choice of R, privacy loss ε′, and support recovery—the paper notes larger R should improve recovery but increases privacy loss and computation time, and formalizing the optimal tradeoff remains open.
• Reducing or removing the extra separation assumption required for the privacy of the mistakes method, since the top-R method avoids such a condition.
• Extending and empirically validating the framework on additional convex losses (Huber, quantile) mentioned as compatible but not evaluated in the provided content.
• Scaling further beyond p = 10,000 and testing on larger real-world datasets, since the abstract notes BSS has been solved non-privately with millions of variables in minutes.

Target Audience

Researchers and graduate students in differential privacy, high-dimensional statistics, and discrete optimization, as well as machine learning practitioners at organizations that need privacy-preserving, interpretable models on sensitive high-dimensional data. Readers should have background in DP definitions and exponential mechanisms, plus some familiarity with sparse regression theory and integer programming.

Authors’ abstract

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$.