PaperlayerView exact revision on arXiv

Source-linked AI summary

Hyperparameter Tuning with Renyi Differential Privacy

Nicolas Papernot, Thomas Steinke

arXiv:2110.03620v2cs.LGcs.CRcs.DS

TL;DR

The paper studies privacy leakage from repeated training runs used for hyperparameter tuning. It develops Renyi differential privacy guarantees for randomized hyperparameter search and shows that tuning can have modest, but nonzero, additional privacy cost under suitable conditions.

  • Problem

    Hyperparameter tuning can leak private information even when individual training runs are private, while prior work provided limited analysis of this cumulative leakage.

  • Method

    The paper analyzes hyperparameter tuning that randomly selects the number of runs and candidate settings, then returns the best outcome using Renyi differential privacy.

  • Results

    Randomized repetition can incur much lower privacy cost than naive composition, with privacy-utility tradeoffs governed by the repetition distribution; under pure DP, the cost is ((2 + η)ε, 0)-DP.

  • Takeaways & Limitations

    Hyperparameter tuning is not privacy-free, but under the analyzed procedure and assumptions, its additional leakage can be modest when each candidate training run is differentially private.

  • Takeaways & Limitations

    The results are immediately applicable only to the hyperparameter tuning algorithm analyzed in Section 3.3, and tuning can double or triple the privacy parameter in the setting studied.

Abstract

from arXiv · show

For many differentially private algorithms, such as the prominent noisy stochastic gradient descent (DP-SGD), the analysis needed to bound the privacy leakage of a single training run is well understood. However, few studies have reasoned about the privacy leakage resulting from the multiple training runs needed to fine tune the value of the training algorithm's hyperparameters. In this work, we first illustrate how simply setting hyperparameters based on non-private training runs can leak private information. Motivated by this observation, we then provide privacy guarantees for hyperparameter search procedures within the framework of Renyi Differential Privacy. Our results improve and extend the work of Liu and Talwar (STOC 2019). Our analysis supports our previous observation that tuning hyperparameters does indeed leak private information, but we prove that, under certain assumptions, this leakage is modest, as long as each candidate training run needed to select hyperparameters is itself differentially private.

1 INTRODUCTION

Hyperparameter tuning adds privacy leakage beyond the leakage of individual differentially private training runs, and this issue has received limited attention. The paper studies when tuning leaks information and develops tighter privacy guarantees for randomized hyperparameter search in Rényi differential privacy.

  • Motivation: Repeatedly evaluating different hyperparameter settings requires accounting for the privacy leakage of the overall procedure, not only each training run.DP-SGD and related methods may use privacy-sensitive hyperparameters such as clipping bounds, noise scales, and stopping times.
  • Research question: Hyperparameter tuning can reveal private information, a question that has received remarkably little attention and is often ignored in practice.The paper gives both positive and negative answers to whether tuning can reveal private information.
  • Technical framework: The framework extends beyond pure DP because Rényi differential privacy provides sharp, simple composition for mechanisms such as Gaussian-noise DP-SGD.RDP tracks privacy as a function ε(λ), allowing analyses across multiple Rényi orders.
  • Related work: Naïve composition of private candidate runs gives valid but very loose privacy guarantees for hyperparameter tuning.Earlier tighter analyses required learning-algorithm stability, while Liu and Talwar provided a black-box approach based on randomized repetition.
  • Contributions: Replacing Liu and Talwar’s geometric repetition count with a logarithmic distribution yields (2ε, 0)-DP instead of their representative (3ε, 0)-DP result.The paper also analyzes other repetition distributions and extends the analysis to Rényi differential privacy.

2 MOTIVATION

A constructed SVM example shows that non-private hyperparameter tuning can expose information about training-set outliers. The selected regularization weight changes depending on whether the outliers are present, enabling a membership-inference variant.

  • Constructed example: The example uses a soft-margin SVM whose single hyperparameter α controls the importance assigned to hinge-loss slack variables.The training data are drawn from a synthetic two-dimensional Gaussian distribution.
  • Hyperparameter sensitivity: With eight added outliers, the best performance occurs around α = 8, whereas increasing α is detrimental without outliers.The two tuning curves are compared using training accuracy as a function of α.
  • Privacy leakage: The differing optimal α values can reveal whether the outlier points were included in the training set.This creates a variant of membership inference based on the selected hyperparameter.
  • Practical implication: Tuning hyperparameters non-privately and then performing one final private training run is not ideal because the selected values may already leak information.The paper instead studies privacy-preserving runs throughout tuning, with the number of runs chosen carefully.

3 OUR POSITIVE RESULTS

The paper formalizes non-adaptive random hyperparameter search by repeatedly running randomly selected candidate algorithms and returning the best outcome, then derives Rényi-DP guarantees for several repetition distributions. These guarantees improve prior bounds, expose privacy–utility tradeoffs, and are evaluated on a private CNN hyperparameter search.

  • Problem formulation and algorithm: The search samples a random number of runs, uniformly selects a candidate hyperparameter setting for each run, and returns the best outcome.The framework assumes a total order over outputs and includes both the trained model and its hyperparameter values in the output.
  • Problem formulation and algorithm: The analysis assumes candidate algorithms satisfy a uniform Rényi-DP bound, so random candidate selection preserves those parameters before repetition is analyzed.The privacy guarantee additionally depends on the distribution of the repetition count K.
  • Main privacy results: The truncated negative binomial family yields a privacy–utility tradeoff: privacy improves as η decreases and γ increases, but the expected number of repetitions and success probability decrease.Its η = 0 member is the logarithmic distribution, while η = 1 gives the geometric distribution.
  • Main privacy results: For pure DP, the repeated algorithm satisfies ((2 + η)ε, 0)-DP, recovering the prior 3ε geometric-distribution result when η = 1 and improving it when η < 1.This generalizes Liu and Talwar’s result from geometric repetition to the broader truncated negative binomial family.
  • Main privacy results: For ρ-zCDP base algorithms, Corollary 4 provides an RDP bound involving ρ, the Rényi order, η, and log(E[K]); the resulting guarantee improves over naïve linear composition.The paper converts these RDP guarantees to approximate DP with δ = 10^-6 for comparison.
  • Generic repetition analysis: A generic lemma bounds repetition privacy for any distribution on K through the base algorithm’s RDP and the probability generating function of K.This supports comparisons among distributions using expected repetitions, utility, success probability, and privacy.
  • Experimental evaluation: In the CNN experiment, the authors privately fine-tune a logarithmically varied learning rate for an MNIST convolutional network while fixing the remaining training hyperparameters.The experiment reports maximal accuracy over 500 trials for the considered distributions on K.

4 CONCLUSION

The paper shows that private hyperparameter tuning can substantially reduce the privacy cost relative to naïve composition, but the benefit depends on randomized repetition and the tuning setting.

  • Randomizing the number of repetitions lets returning only the best output incur much lower privacy cost than naïve composition suggests.The analyzed repetition distributions induce different privacy-utility tradeoffs.
  • Tuning architecture details without privacy can produce suboptimal utility-privacy tradeoffs because the optimal activation function may differ under DP.This conclusion echoes prior observations about privacy-aware architecture tuning.
  • Hyperparameter tuning is not free: the privacy parameter may double or triple after accounting for tuning.The authors suggest reporting both the base-algorithm guarantee and the overall-system guarantee when this increase is prohibitive.
  • The best privacy-utility tradeoff among analyzed repetition distributions depends on the setting.The differences appear relatively small, so the choice is unlikely to be critical.

REPRODUCIBILITY & ETHICS STATEMENTS

The paper provides detailed materials for reproducing its theory and experiments, while emphasizing that applications to real-world sensitive data require careful consideration of potential harms.

  • Reproducibility: The paper provides precise theorems, complete proofs, plotting calculations, experimental hyperparameters, and a fully specified implementation.The authors state that the algorithm is simple and can be easily implemented.
  • Ethics: The work does not directly use real-world sensitive data; experiments use synthetic data or MNIST, a standard non-private dataset.The authors nevertheless stress that potential harms must be considered when DP algorithms are applied to sensitive data.

ACKNOWLEGMENTS

This material supplies acknowledgments and background definitions and properties for differential privacy, Rényi differential privacy, probability generating functions, and repetition-count distributions.

  • Acknowledgments: The paper thanks reviewers and colleagues for feedback, discussions, and comments on early drafts.
  • Background: Rényi divergence has standard properties including monotonicity, postprocessing, composition, finite-range sufficiency, and convexity.
  • Background: RDP supports composition-based privacy analysis, including analysis of individual DP-SGD steps followed by composition.Gaussian mechanisms often yield linear ε(λ) bounds associated with zero-concentrated DP.
  • Background: Rényi DP bounds the Rényi divergence between outputs on neighboring datasets by ε at order λ.The paper also notes that RDP is commonly tracked as a function ε(λ).
  • Repetition distributions: The probability generating function characterizes a repetition-count random variable and can recover its probabilities and moments.The paper relates PGFs to moment generating functions and Poisson mixtures.
  • Repetition distributions: The truncated negative binomial distribution excludes zero repetitions, with η = 1 giving the geometric distribution and η = 0 giving the logarithmic distribution.Its limiting behavior also connects large η to a Poisson distribution when the mean remains fixed.

A.2.1 PROBABILITY GENERATING FUNCTIONS AND UTILITY

The section relates repeated-run utility to the probability generating function of the repetition count K, while also examining success probability and runtime. It shows that repetition distributions trade off utility, privacy-oriented success amplification, and runtime concentration.

  • Success probability: For one good outcome among m candidates, the first-order approximation gives success probability β≈E[K]/m when 1/m is small.The approximation applies for large m and therefore small overall success probabilities.
  • Success probability: When the target success probability is high, smaller η performs worse because its repetition distribution is more heavy-tailed, while Poisson performs best among the compared distributions.The Poisson distribution is described as almost as concentrated as naïve repetition.
  • Expected utility: Repeating the base algorithm K times yields utility Y=max{X_1,...,X_K}, whose distribution and expected value can be analyzed through K's probability generating function.The base-run utility X may represent accuracy, loss, AUC/AUROC, or output quantile.
  • Runtime: The probability generating function or moment generating function yields tail bounds for K; finiteness at some x=e^t>1 implies a subexponential tail bound.These bounds are used to control runtime and avoid heavy-tailed execution times.

B.2 PROOFS OF DISTRIBUTION-SPECIFIC BOUNDS

The distribution-specific proofs instantiate the generic Rényi-DP bound for truncated negative binomial and Poisson repetition counts, including concentrated-DP guarantees. These results expose privacy–repetition tradeoffs through the chosen distribution parameters.

  • Truncated negative binomial: The truncated negative binomial analysis applies monotonicity of Rényi DP after selecting an optimized order λ̂ under a condition involving log(E[K])/ρ.The resulting bound is obtained after substituting the optimal λ̂.
  • Concentrated-DP specialization: For concentrated DP, substituting ε=ρλ and ε̂=ρλ̂ into Theorem 2 yields an (λ, ε′)-RDP guarantee for the repeated algorithm.The corollary assumes the base algorithm satisfies ρ-zCDP and uses the distribution-specific theorem.
  • Poisson: For Poisson repetition, the probability generating function is f(x)=e^{μ(x−1)} and its derivative is f′(x)=μe^{μ(x−1)}.These expressions are inserted into the generic bound to derive the Poisson-specific privacy result.
  • Poisson: The Poisson proof bounds the repeated algorithm's Rényi divergence using the base divergence, μ, and the base algorithm's (ε̂,δ̂)-DP parameters.The displayed bound includes D_λ(Q∥Q′) and a logarithmic μ term.

C CONDITIONAL SAMPLING APPROACH

The conditional-sampling approach repeatedly runs a base algorithm until it produces an output in a designated good set S. Its geometric runtime and Rényi-DP analysis provide an alternative to selecting the best result after a random number of runs.

  • Algorithm: The conditional-sampling analysis extends Liu and Talwar's approach to Rényi differential privacy.The section presents the approach as an alternative to random-count repetition followed by best-output selection.
  • Runtime and failure: A modification can halt with output ⊥ when Q(S) is too small, avoiding privacy failure at the cost of sometimes failing to produce a good output.The modification introduces a small probability p of outputting ⊥.
  • Algorithm: The algorithm runs Q repeatedly until its output enters S, then returns that output; equivalently, it samples from Q conditioned on S.The number of runs follows a geometric distribution with mean 1/Q(S).

D.1 WHY A FIXED NUMBER OF REPETITIONS DOES NOT RESULT IN GOOD PRIVACY.

Fixed repetition followed by best-output selection can incur privacy loss linear in the number of runs, and this is inherent rather than merely an artifact of the analysis. Slightly randomizing the repetition count, such as using Poisson(k), can substantially tighten the guarantee.

  • Fixed repetition: The fixed-count analysis gives a bound slightly worse than naïve composition, D_λ(A∥A′)≤k·D_λ(Q∥Q′).The point-mass repetition distribution has PGF f(x)=x^k and derivative f′(x)=k·x^{k−1}.
  • Lower bound: For an ε-DP base algorithm, fixed k-fold repetition followed by selecting the best output is not ε̂-DP for any ε̂<kε.The proposition also gives a corresponding lower bound for Rényi DP.
  • Lower bound: For λ≥1+1/ε, the Rényi-DP privacy loss satisfies ε′(λ)=Ω(kε), demonstrating linear payment in k.The limitation is established for pure DP or RDP with sufficiently large orders.
  • Randomized repetition: The lower-bound example is brittle: replacing fixed k repetitions with Poisson(k) repetitions already yields significantly tighter privacy guarantees in general.The authors describe the adjustment as minor while retaining similar repetition behavior.
  • Scope: The fixed-count lower-bound argument does not straightforwardly extend to the low-order RDP or approximate-DP regime, where advanced composition becomes relevant.The text notes that tightness for advanced composition is non-trivial.

D.2 TIGHT EXAMPLE FOR CONDITIONAL SAMPLING.

The conditional-sampling construction provides a tight example for comparing the paper’s Rényi-DP upper bound with exact privacy loss. Conditioning on outputs with extreme privacy loss can amplify the remaining privacy loss through renormalization.

  • Construction: The conditional-sampling tight example uses neighboring-output distributions Q and Q′ supported on three points.The small output space represents a partition of a larger output space by privacy-loss behavior.
  • Construction: The conditioning set retains outputs with large or very negative privacy loss while excluding outputs with middling privacy loss.Renormalization increases the retained positive privacy loss because Q(S) and Q′(S) differ substantially.
  • Comparison: Figure 8 compares the exact conditional-sampling value Dλ(QS∥Q′) with the upper bound from the second inequality in Corollary 16.For each λ, s and t are selected so both baseline divergences equal 0.1 · λ.
  • Exact calculation: For all λ > 1, the example gives explicit expressions for Dλ(Q∥Q′) and Dλ(Q′∥Q).These expressions quantify the Rényi divergences of the two neighboring distributions before conditioning.
  • Conclusion: The upper bound is tight up to small factors arising from lower-order terms and λ−2 terms.The comparison is intended to show that the bound captures the example’s privacy behavior closely.

D.3 TIGHTNESS OF OUR GENERIC RESULT.

The paper tests whether its generic repeated-algorithm bound is tight by constructing three-point output distributions and comparing their exact behavior with the bound. The same framework also yields private-selection guarantees matching known lower bounds up to constants.

  • Repeated algorithm: The repeated algorithm runs a totally ordered base algorithm Q a random number K of times and returns the best output.Its probability generating function f determines the output probabilities after repetition.
  • Tight example: The tight example again uses distributions supported on three points, with the ordering preferring the first, then second, then third outcome.The resulting probabilities are expressed through f evaluated at sums of probability masses.
  • Tightness: The constructed example shows that Lemma 7’s generic upper bound is tight up to low-order terms.The comparison uses arbitrary postprocessings q and q′ of Q and Q′, with values chosen to match the relevant probability masses.
  • Private selection: Private hyperparameter tuning generalizes private selection, where a utility function is evaluated over m candidate choices and the goal is to privately approximate its maximizer.The standard exponential mechanism provides the comparison point for the selection guarantees.
  • Private selection: The repeated noisy-selection procedure obtains a utility guarantee based on the probability that the optimal index appears among the random candidate draws.With Laplace noise of scale 1/ε, the base selection algorithm is (ε, 0)-DP.
  • Private selection: The resulting selection guarantees are tight up to constants because they match the known exponential-mechanism lower bounds.The cited lower bound gives additive error Ω(log(m)/ε) for (ε, 0)-DP selection.

E EXTENDING OUR RESULTS TO APPROXIMATE DP

The paper extends its Rényi-DP analysis to approximate DP by decomposing approximate distributions into private and residual components, then applying the pure-RDP repeated-sampling analysis. The extension yields explicit approximate-RDP guarantees, including for Poisson-distributed repetition counts and truncated repetition distributions.

  • Approximate RDP: The approximate-DP extension converts a base algorithm with approximate RDP into an exactly RDP base algorithm plus a residual failure component.The resulting repeated algorithm has approximate RDP, with its δ parameter depending on the base δ0 and the repetition-count PGF.
  • Definitions: Approximate Rényi divergence represents distributions through convex decompositions with a shared weight on their private components.The definition takes the infimum of the Rényi divergence between the shared components.
  • Properties: Approximate RDP preserves postprocessing and composes by adding both the approximate-divergence parameters and the privacy parameters.The framework also contains standard approximate DP as a special case.
  • Poisson repetition: For Poisson repetition with mean μ, the residual approximate-RDP parameter satisfies δ′ = 1−e^−μ·δ0 ≤ μ·δ0.The algorithm draws K from a Poisson distribution, runs the base algorithm K times, and returns the best value.
  • Poisson repetition: The resulting approximate-RDP guarantee applies for λ ≤1 + 1/(e^ε−1), with ε′ determined by the theorem’s parameters.The admissible Rényi orders are restricted by the base approximate-DP privacy level.
  • Decomposition: Lemma 20 decomposes the best-of-K distribution into a private best-of-K component weighted by (1−δ0)^K and a residual distribution.This follows by separating the event that every one of the K samples comes from the private component.
  • Truncation: Truncating the repetition count produces nearly identical bounds when the tail probability and tail-weighted repetition count are negligible.The relevant conditions are P[K > m] ≪ 1 and E[K · I[K > m]] ≪ E[K].
Loading 2110.03620v2…