Revisiting Differentially Private Hyper-parameter Tuning

Revisiting Differentially Private Hyper-parameter Tuning

Speakers: Zihang Xiang

Conference: NDSS Symposium 2026

YouTube: https://www.youtube.com/watch?v=XnY1XLA1ohk

Overview

When training machine learning models with differential privacy (DP), practitioners do not simply train once -- they run the training process multiple times with different hyperparameters (learning rates, clipping thresholds, batch sizes) and select the best model. This selection process itself can leak private information, but how much? This talk presents both a rigorous privacy audit and an improved theoretical analysis showing that previous upper bounds on the privacy cost of hyperparameter tuning were far too loose. The new analysis reduces the estimated privacy cost by more than 50%, allowing practitioners to explore significantly more hyperparameter configurations within the same privacy budget.

The research addresses a critical practical question: if you train K models using DPSGD (Differentially Private Stochastic Gradient Descent) and release only the best one, is the privacy cost equivalent to a single run, or does the selection process leak additional information? Through auditing experiments with increasingly powerful adversaries, the researchers confirm that selection does incur additional privacy cost beyond a single run -- but the previous state-of-the-art theoretical bounds vastly overestimated that cost.

Background

▶ Watch: Differential privacy refresher and DPSGD basics (0:00)

Differential privacy provides a mathematical framework for measuring privacy leakage. An algorithm is (epsilon, delta)-differentially private if its output distributions on any two adjacent datasets (differing by exactly one sample) are statistically indistinguishable, bounded by parameters epsilon and delta. Lower epsilon means stronger privacy.

DPSGD is the standard tool for training ML models with differential privacy. It modifies standard stochastic gradient descent in two ways: clipping per-example gradients to bound sensitivity, and adding Gaussian noise to the sum. While the privacy analysis for a single DPSGD run is well-studied, real-world ML pipelines require multiple runs for hyperparameter tuning.

The previous state-of-the-art approach, called privacy selection, treats the number of runs K as a random variable. By running DPSGD a random number of times and releasing only the single best model (selected by a score function like validation accuracy), the privacy cost is bounded more tightly than naive linear composition (which scales linearly with K). However, the question remained whether this bound was tight or whether it could be significantly improved.

Two key concepts frame the analysis: privacy upper bounds provide theoretical guarantees that no adversary can extract more than a certain amount of privacy leakage, while privacy lower bounds (established through auditing) demonstrate the minimum amount of leakage that can actually be extracted from the system. The true privacy parameter lies in the gap between these two bounds.

Key Findings

▶ Watch: Privacy upper bounds vs lower bounds explained (2:30)

The researchers designed three auditing scenarios with increasing adversarial power:

NTMV (Normal Training, Normal Validation): The most realistic setting using real data and standard validation accuracy as the score function. The audited privacy leakage was very low -- even lower than the theoretical cost of a single run. This suggests that hyperparameter tuning on real data leaks very limited additional privacy.

NTCV (Normal Training, Controlled Validation): The adversary manipulates the score function to select the model that leaks the most information. Even with this advantage, the empirical leakage remained far below the theoretical upper bound, implying that model selection itself is not the primary source of leakage.

ETCV (Empty Training, Controlled Validation): The worst-case scenario where the training dataset is empty except for canary records, maximizing the signal-to-noise ratio. Here the empirical leakage exceeded the cost of a single run, confirming that selection does incur additional privacy cost. However, the audited leakage was still substantially below the previous theoretical upper bound, confirming the bounds were loose.

Technical Deep Dive

▶ Watch: Key finding: realistic tuning leaks less than single-run cost (5:30)

The key theoretical innovation is replacing the (epsilon, delta)-DP formulation with f-DP (Functional Differential Privacy), also known as Gaussian Differential Privacy. While (epsilon, delta)-DP provides a single-point characterization of privacy, f-DP models the complete tradeoff curve between false positive and false negative rates an adversary can achieve.

For the Gaussian mechanism used in DPSGD, the (epsilon, delta)-DP formulation is a loose approximation of the true privacy guarantee. The gap between the actual Gaussian mechanism tradeoff curve and the (epsilon, delta) approximation represents wasted privacy budget. By switching to f-DP, the analysis reclaims this gap.

The researchers also derive a mathematical characterization of the worst-case score function. They prove in Theorem 2 that a one-to-one mapping score function (where every model output maps to a unique score) is the worst case for privacy -- it leaks the most information. Score functions that break ties randomly inherently hide information.

Combining f-DP modeling with the worst-case score function analysis yields Theorem 3: a general form of the privacy upper bound for hyperparameter tuning that depends on the base algorithm's trade-off function and the distribution of the number of runs. The upper bound deteriorates from the base algorithm by an additive factor, but because f-DP provides a tighter characterization of the Gaussian mechanism, the overall bound is significantly tighter than prior work.

The practical impact is demonstrated across standard benchmarks including MNIST and CIFAR-10, where the new analysis consistently provides better privacy accounting. For a given privacy budget, practitioners can now run substantially more hyperparameter trials, or equivalently, the same tuning process fits within a more than 50% smaller privacy budget.

Demo / Proof of Concept

▶ Watch: Worst-case ETCV confirms selection does leak extra privacy (6:00)

The auditing framework serves as the empirical validation. The adversary plays a distinguishing game: given two adjacent datasets X and X' (where X' contains a canary record), the trainer runs the full hyperparameter tuning protocol, and the adversary observes the selected model's output to guess which dataset was used. By measuring false positive and false negative rates across many trials, the researchers empirically estimate the privacy lower bound.

The results across all three scenarios are presented as bar charts comparing: the previous theoretical upper bound (gray), the single-run cost (blue), and the empirical audit results (orange/green). The visual comparison makes the looseness of previous bounds immediately apparent -- particularly in the ETCV worst-case scenario where the gap between the audit and the previous upper bound is dramatic.

Defensive Implications

▶ Watch: Results: 50%+ reduction in estimated privacy cost (9:00)

For organizations deploying privacy-preserving ML systems, this research has direct operational impact. Privacy budgets are finite resources -- every epsilon spent on hyperparameter tuning is unavailable for other operations. Previous analyses forced practitioners to either accept poor model quality (limited tuning) or large privacy budgets (weaker guarantees).

The tighter bounds mean that ML teams can now tune hyperparameters more extensively without violating privacy guarantees. This is particularly important for organizations subject to regulatory requirements around differential privacy, such as those governed by GDPR or deploying systems under US Census-style privacy frameworks. The improved accounting also reduces the gap between theoretical privacy guarantees and practical privacy leakage, giving organizations more confidence that their stated privacy guarantees are meaningful.

From a governance perspective, the audit results in the realistic NTMV setting -- showing leakage even below single-run cost -- suggest that practical privacy risk from hyperparameter tuning may be far lower than current compliance frameworks assume, potentially allowing more aggressive model optimization without increasing actual risk.

Key Takeaways

• Hyperparameter selection in DPSGD does leak additional privacy beyond a single run, confirmed through worst-case auditing (ETCV scenario)
• In realistic settings (real data, standard validation), the privacy leakage from tuning is extremely low -- even below single-run theoretical cost
• Previous state-of-the-art privacy upper bounds for hyperparameter tuning were far too loose
• Switching from (epsilon, delta)-DP to f-DP (Gaussian Differential Privacy) for modeling the base DPSGD algorithm reclaims substantial wasted privacy budget
• The new analysis reduces estimated privacy cost by more than 50% for the same setup
• Practitioners can now run significantly more hyperparameter trials within the same privacy budget, improving model quality without weakening privacy guarantees

About the Speaker(s)

Zihang Xiang presented on behalf of the lead author Zan, who was on a school visit and could not attend. The research team works at the intersection of differential privacy theory and practical machine learning privacy, with expertise in privacy auditing methodology and tight privacy accounting for iterative mechanisms. The work demonstrates both strong theoretical foundations (novel theorems on f-DP composition) and practical orientation (auditing experiments on real datasets).