PaperlayerView exact revision on arXiv

Source-linked AI summary

Private Selection from Private Candidates

Jingcheng Liu, Kunal Talwar

arXiv:1811.07971v1cs.DScs.CRcs.LGstat.ML

TL;DR

The paper addresses private selection when classical Lipschitz stability of candidate scores is too strong. It models candidates as differentially private mechanisms, develops near-optimal selection and online threshold algorithms, and applies them to private hyperparameter tuning and adaptive data analysis.

  • Problem

    Private selection traditionally assumes score functions change little when one person’s data changes, but this Lipschitz condition is too strong for applications such as hyperparameter optimization.

  • Method

    The paper selects among differentially private randomized candidate mechanisms and develops threshold, unknown-target, and online sparse-vector-style algorithms.

  • Results

    The algorithms are near-optimal in privacy, utility, and computational cost, including a 2ε1-DP threshold algorithm and applications to private hyperparameter selection and adaptive data analysis.

  • Takeaways & Limitations

    Private candidate mechanisms can be selected with small privacy and computational overhead, enabling private hyperparameter tuning and adaptive analysis beyond low-sensitivity queries.

  • Takeaways & Limitations

    The setting assumes oracle access to randomized private candidates with bounded scores and leaves improving the threshold algorithm’s runtime constants open.

Abstract

from arXiv · show

Differentially Private algorithms often need to select the best amongst many candidate options. Classical works on this selection problem require that the candidates' goodness, measured as a real-valued score function, does not change by much when one person's data changes. In many applications such as hyperparameter optimization, this stability assumption is much too strong. In this work, we consider the selection problem under a much weaker stability assumption on the candidates, namely that the score functions are differentially private. Under this assumption, we present algorithms that are near-optimal along the three relevant dimensions: privacy, utility and computational efficiency. Our result can be seen as a generalization of the exponential mechanism and its existing generalizations. We also develop an online version of our algorithm, that can be seen as a generalization of the sparse vector technique to this weaker stability assumption. We show how our results imply better algorithms for hyperparameter selection in differentially private machine learning, as well as for adaptive data analysis.

1. Introduction

The paper studies private selection when candidate scores are themselves differentially private rather than Lipschitz, and develops near-optimal algorithms for privacy, utility, and oracle efficiency. It also extends the approach to online threshold search and applications in private hyperparameter tuning and adaptive data analysis.

  • 1. Introduction: Differential privacy of candidate mechanisms replaces the usual Lipschitz stability assumption, enabling private selection under a weaker condition.Each candidate is accessed as a randomized mechanism producing a sample and bounded score, with neighboring output distributions required to satisfy differential privacy.
  • 1. Introduction: The threshold algorithm outputs a sample scoring at least τ when some candidate has median score at least τ, while using near-linear oracle calls and near-optimal privacy, utility, and efficiency.Its privacy guarantee is 2ε1-DP, and the algorithm improves over a quadratic oracle-call bound.
  • 1. Introduction: An online variant generalizes sparse vector by stopping at the first private mechanism whose score distribution exceeds its threshold.It identifies an above-threshold candidate with probability 1−β when one candidate succeeds with probability at least p∗.
  • 1. Introduction: The algorithms incur an essentially unavoidable factor-two privacy loss and use Õ(K) oracle calls, matching the non-private order up to logarithmic factors.The paper states that the factor-two privacy loss is unavoidable even in simple settings.
  • 1. Introduction: Applications include differentially private hyperparameter selection and adaptive data analysis, where selection can avoid paying separately for every candidate option.The paper claims O(ε)-DP hyperparameter competition with small computational overhead and an adaptivity cost essentially independent of K.

2. Preliminary and Notations

The paper introduces notation for distributions, max-divergence, approximate max-divergence, differential privacy, and Lipschitz functions.

  • Random-variable notation X ∼ Q means that X is distributed according to Q.
  • Max-divergence and approximate max-divergence compare two random variables or distributions, with the latter incorporating δ.
  • A dataset-dependent distribution Q(D) is ε-DP, or (ε, δ)-DP, when its divergence across every neighboring-dataset pair is bounded accordingly.
  • A dataset function f is t-Lipschitz when neighboring datasets change its value by at most t.

3. Private selection

Private selection chooses high-scoring outputs from differentially private candidates without exposing the dataset through naive maximization. The paper uses thresholding and random stopping to obtain utility guarantees while controlling privacy and query complexity.

  • Naively selecting the highest-scoring sample from private candidates is not private, motivating algorithms that compete with the best candidate under privacy constraints.
  • The framework samples a candidate uniformly, runs its mechanism, evaluates the output score, and treats the resulting scored sample as a private oracle distribution Q(D).
  • 3.1. Thresholding with a known threshold: Thresholding repeatedly samples until obtaining a score at least τ, while random stopping limits iterations and preserves privacy when Q is differentially private.
  • 3.2. Random stopping without thresholding: The random-stopping algorithm without a threshold outputs the highest-scored sample observed before stopping and is (3ε1)-DP when Q is ε1-DP.
  • 3.2. Random stopping without thresholding: The output score is at least the p-quantile Q(p)(D), except with probability γ/p.
  • 3.2. Random stopping without thresholding: For approximate-DP Q, hard stopping yields (3ε1 + 3√2δ1, δ)-DP with δ = √2δ1T + δ2.

4. Searching for a percentile-threshold: privacy-preserving sparse vector

This section generalizes sparse vector to differentially private randomized queries by searching for percentile thresholds rather than relying on Lipschitz query answers. The resulting algorithms provide privacy, threshold-detection guarantees, and private selection of a high-quality candidate sample.

  • 4. Searching for a percentile-threshold: privacy-preserving sparse vector: Differentially private queries support a sparse-vector-style search for the first query whose score distribution exceeds a percentile threshold.The algorithm processes randomized queries Q_i and thresholds τ_i, reporting above or below threshold and halting at the first above-threshold query.
  • 4.1. Sparse vector for online private queries with the help of a percentile oracle.: For private queries, log p(τ_i,Q_i) and log(1−p(τ_i,Q_i)) are ε1-Lipschitz, making log Φ(p(τ_i,Q_i)) a 2ε1-Lipschitz sparse-vector query.The transformation Φ(x)=x/(1−x) enables the standard sparse-vector comparison against the percentile threshold.
  • 4.2. Sparse vector for online private queries.: A query sufficiently above threshold is likely to trigger halting, while the algorithm preserves differential privacy for the sequence of private queries.The theorem states privacy and conditional guarantees for avoiding premature or delayed stopping; the above-threshold halting failure probability is bounded by β in the stated result.
  • 4.2. Sparse vector for online private queries.: The exact percentile oracle can be replaced by an unbiased estimator from iid samples, yielding a private algorithm with probabilistic threshold guarantees.The estimator is formed from sampled query scores, and Laplace perturbations are used in the threshold test.
  • 4.3. A more efficient sparse vector for a one-sided guarantee.: Raising the threshold estimate improves selected-candidate quality but can reduce the percentile mass used to control computational cost.The one-sided guarantee makes this quality-versus-computational-cost trade-off explicit.
  • 4.3. A more efficient sparse vector for a one-sided guarantee.: The resulting selection algorithm is (2ε1+ε0,δ)-DP and returns a candidate sample with quality at least τ*−1/R except with probability β+δ/R.It may output ⊥ with probability at most β+δ, while its oracle-call complexity is separately bounded by the theorem.

5. Applications

The paper applies private selection to hyperparameter tuning, related private-selection mechanisms, and adaptive data analysis. Its framework preserves privacy across training and validation data while selecting among randomized private candidates.

  • Hyperparameter selection: For private hyperparameter selection, the framework samples a model from each private learner and seeks a model–hyperparameter pair with high validation score.Training data determine the randomized model, while validation data determine the score.
  • Hyperparameter selection: Adding Laplace noise to validation scores makes the score distribution ε2-DP for the validation dataset.The construction defines Q(D1,D2) as the distribution of noisy scores after sampling a model from a private learner.
  • Hyperparameter selection: If every learning algorithm is ε1-DP, the induced score distribution is ε1-DP for training data; the analogous (ε1,δ1)-DP guarantee also holds.These guarantees allow the main private-selection theorems to be applied jointly to the resulting score distribution.
  • Adaptive data analysis: The framework applies to adaptive data analysis because differential privacy supplies generalization bounds for intermediate private selection steps.The paper specifically identifies selecting among differentially private k-means or rank-k PCA runs as an application.
  • Related mechanisms: The main result recovers several private-selection mechanisms, including the exponential, generalized exponential, margin-based, and smooth-sensitivity variants.These mechanisms arise as corollaries by defining appropriate private score-function variants.

6. Conclusions

The paper presents private algorithms for selecting among differentially private algorithms and applies them to hyperparameter search and adaptive data analysis. It concludes that the algorithms are near-optimal across privacy overhead, computational cost, and utility loss, while leaving runtime constants open.

  • 6. Conclusions: The algorithms are near-optimal in privacy overhead, computational cost, and utility loss for selecting among differentially private algorithms.The conclusion identifies these three dimensions as the central performance criteria.
  • 6. Conclusions: The results apply to hyperparameter search and adaptive data analysis.The conclusion states both application areas directly.
  • 6. Conclusions: Improving the constants in the runtime of the threshold-finding algorithm remains open.This is the explicit open question identified in the conclusion.
  • 6. Conclusions: Random-search- or grid-search-based hyperparameter tuning can be made differentially private essentially for free, while more adaptive tuning remains an open direction.The paper distinguishes the supported privacy result for random or grid search from the question of privatizing more complex adaptive algorithms.

Appendix A. Deferred Proofs

This appendix section only points back to the statement of Theorem 3.1 for convenience, without supplying additional proof content in the provided passage.

  • Appendix A. Deferred Proofs: The appendix restates Theorem 3.1 for convenience.

A.1. Proof of Theorem 3.1.

The proof establishes that Algorithm 1 samples outputs proportionally to the candidate distribution while preserving differential privacy under the stated conditions.

  • Output distribution: Algorithm 1 outputs each pair (x, q) with probability proportional to its probability under Q(D).The threshold-dependent and coin-test factors are constant across (x, q), so they cancel in the output distribution.
  • Privacy guarantee: If Q is ε1-DP, Algorithm 1's output is (2ε1 + ε0)-DP.
  • Privacy guarantee: Increasing the iteration limit T does not degrade privacy.
  • Privacy proof: The proof bounds events excluding ⊥ and then handles events containing ⊥ by separating the ordinary output and stopping probabilities.
  • Runtime: The probability of halting in each iteration is p1(1 −γ) + γ, yielding a geometric bound on the expected number of trials.

A.2. Proof of Theorem 3.5.

The proof analyzes the finite-iteration candidate-selection variant using geometric stopping probabilities and concentration bounds to establish its privacy guarantee.

  • Privacy guarantee: The variant that outputs the highest-scored candidate when j reaches T is (3ε1 + 3ε0)-DP when Q is ε1-DP.
  • Output analysis: The proof decomposes the output probability by the stopping time j and the maximum score among the sampled candidates.
  • Probability bounds: The analysis represents non-stopping probabilities using a=(1−γ)(1−p0) and b=(1−γ)(1−p1), then bounds their powers.
  • Concentration bounds: Chernoff-style concentration bounds control sums of independent Bernoulli variables used in the privacy analysis.

Appendix B. Naive algorithms: tight examples and analysis

The appendix shows that naive selection can incur privacy costs proportional to the number of candidates or thresholds, while median-based selection can fail to preserve privacy.

  • Naive selection: Selecting the best of K ε-DP candidates has a tight (Kε)-DP bound under basic composition.
  • Tight examples: For pure and approximate privacy, neighboring datasets can produce sharply different probabilities of selecting a distinguished candidate under naive maximum selection.
  • Thresholding with decreasing thresholds: Trying R decreasing thresholds can amplify the privacy loss by a factor of R.
  • Median selection: The median of privately generated candidate scores is not necessarily private, even when the underlying distributions are O(ε)-close.

Appendix C. Improved analysis of the private amplification algorithm in [19]

The appendix analyzes a private amplification construction that clips candidate scores, adds dummy classes, and applies the exponential mechanism to obtain utility and privacy guarantees.

  • Amplification construction: The construction clips each ε1-DP score at threshold τ, adds 1 + 1/γ dummy classes with score τ, and applies the exponential mechanism.
  • Utility guarantee: The mechanism outputs a dummy class with probability γ+1 Npγ+1.
  • Privacy guarantee: The resulting exponential-mechanism output is (2ε1 + 8γ)-DP.
  • Privacy guarantee: The privacy guarantee for the training set does not depend on ε2, so ε2 can tend to infinity without compromising that privacy.
  • Proof strategy: The proof compares clipped score variables on neighboring datasets and uses concentration and moment inequalities to establish the bound.

Appendix D. Lower Bounds

Appendix D shows that the paper’s privacy loss is close to optimal: a factor-of-two loss is unavoidable under mild usefulness, while the algorithm uses near-linearly many oracle calls.

  • The algorithm makes only ˜O(K) oracle calls, matching the necessary Ω(K) cost up to logarithmic factors.
  • A final algorithm using ε-DP input mechanisms achieves privacy 2ε + ε′, with ε′ arbitrarily small.
  • Under γ-weak usefulness with γ = K^-α, no selection algorithm can guarantee privacy below (2 − 6α)ε for sufficiently small α.
  • The lower bound uses binary-output mechanisms and K + 1 carefully constructed datasets whose pairwise distances permit ε-DP extensions.
  • The proof’s probability comparison yields the lower-bound condition ˆε ≥ (1 − α) ln K / ⌈((0.5 + α) ln K)/ε⌉.

Appendix E. Useful Properties of Differential Privacy

Appendix E develops distributional closeness tools for differential privacy, including an approximate-to-exact conversion outside a low-probability event and its converse.

  • The appendix defines (ε, δ)-farness and symmetric closeness P ≡ε,δ Q through event-wise probability inequalities.
  • If P ≡ε,δ Q with δ < 1/10, removing a suitable event B gives P|Bc ≡ε′,0 Q|Bc for any ε′ > ε.
  • The exceptional event has probability at most δ/(1 − exp(ε − ε′)) under P.
  • The proof may assume densities after adding a uniform [0, 1] random variable to the mechanism output.
  • Conversely, exact symmetric closeness outside an event of probability at most δ implies (ε, δ)-farness in both directions.
Loading 1811.07971v1…