An Interactive Framework for Finding the Optimal Trade-off in Differential Privacy

Yaohong Yang, Aki Rehn, Sammie Katt, Antti Honkela, Samuel KaskiarXiv 2025 · arXiv · OpenReview

Abstract

Differential privacy (DP) is the standard for privacy-preserving analysis, and introduces a fundamental trade-off between privacy guarantees and model performance. Selecting the optimal balance is a critical challenge that can be framed as a multi-objective optimization (MOO) problem where one first discovers the set of optimal trade-offs (the Pareto front) and then learns a decision-maker's preference over them. While a rich body of work on interactive MOO exists, the standard approach—modeling the objective functions with generic surrogates and learning preferences from simple pairwise feedback—is inefficient for DP because it fails to leverage the problem's unique structure. Motivated by this property, we first derive the shape of the trade-off theoretically, which allows us to model the Pareto front directly and efficiently. To address inefficiency in preference learning, we replace pairwise comparisons with a more informative interaction. In particular, we present the user with hypothetical trade-off curves and ask them to pick their preferred trade-off. Our experiments on differentially private logistic regression and deep transfer learning across six real-world datasets show that our method converges to the optimal privacy-accuracy trade-off with significantly less computational cost and user interaction than baselines.

Introduction: The Privacy-Utility Tension

In Differential Privacy (DP), practitioners face a fundamental tension: increasing individual data protection (higher privacy) requires adding more noise, which typically degrades model performance (lower accuracy). This creates two distinct hurdles. First, the technical hurdle requires expensive hyperparameter optimization (HPO) to find the best possible accuracy for any given privacy level ($\epsilon$). Second, the subjective hurdle involves choosing the "right" $\epsilon$, which is a context-dependent social problem rather than a purely technical one.

Standard Multi-Objective Optimization (MOO) attempts to map the entire "Pareto front" of optimal trade-offs, but this is computationally prohibitive for large-scale models. Furthermore, existing interactive methods rely on simple pairwise comparisons (asking a human "Is A better than B?"), which is an information-poor way to learn complex human preferences in a high-stakes domain.

Methodology: A DP-Aware Framework

This research introduces a framework that leverages the unique structure of the DP trade-off to improve efficiency. The approach is built on three main pillars:

1. S-Shaped Pareto Modeling

The core insight is that the privacy-accuracy trade-off follows a predictable S-shape. This was derived theoretically for logistic regression and demonstrated empirically for deep learning. By using Sigmoid and Gompertz functions as surrogate models, the system can estimate the entire trade-off curve after observing only a few data points, rather than using generic Gaussian Processes.

Empirical results confirm that the privacy-accuracy trade-off follows a predictable S-shaped curve, accurately modeled by Sigmoid functions.

2. Richer Human Interaction

Instead of binary "A vs. B" questions, the framework presents the user with a hypothetical trade-off curve and asks them to click their preferred point on it. This provides significantly more information about the user's latent utility function in a single interaction, reducing the cognitive burden of dozens of comparisons.

The proposed interactive framework replaces pairwise comparisons with curve-based selection, leading to faster preference inference and lower error.

3. Knowledge-Gradient (KG) Acquisition

The system uses a Bayesian approach to decide its next move. It calculates which privacy level to evaluate next to improve the model and which hypothetical curve to show the user to maximize the "expected improvement" in total utility. It utilizes a Chebyshev scalarization function to model preferences, which is capable of identifying nuanced trade-offs in the "middle" of the S-curve that linear utility functions often miss.

Experimental Evaluation

The framework was evaluated across two distinct machine learning scenarios:

  • DP Logistic Regression: Tested on the Adult and Dutch census datasets.
  • DP Deep Transfer Learning: Using a Vision Transformer (ViT) fine-tuned on four diverse image datasets: CIFAR-100, SVHN, SUN397, and PatchCamelyon.

Key Results

  • Sample Efficiency: The method reached the optimal trade-off with significantly fewer model evaluations and user queries than state-of-the-art baselines like BALD or qEUBO.
  • Lower Regret: The "regret" (the difference in utility between the chosen point and the true theoretical optimum) dropped much faster, particularly on complex datasets like CIFAR-100 and PatchCamelyon.
  • Robustness: The framework proved effective even when the trade-off curve was incomplete, showing it is practical for real-world scenarios where computational resources are limited.

Conclusion and Future Work

By modeling the specific geometry of the DP trade-off and utilizing richer user interactions, this framework identifies optimal privacy-utility balances with unprecedented efficiency. Future work will explore heteroscedastic models to account for the varying instability of training at high privacy levels (low $\epsilon$) and methods to automate the discovery of sensible $\epsilon$ ranges for new datasets.

Summary updated

Abstract

Differential privacy (DP) is the standard for privacy-preserving analysis, and introduces a fundamental trade-off between privacy guarantees and model performance. Selecting the optimal balance is a critical challenge that can be framed as a multi-objective optimization (MOO) problem where one first discovers the set of optimal trade-offs (the Pareto front) and then learns a decision-maker's preference over them. While a rich body of work on interactive MOO exists, the standard approach -- modeling the objective functions with generic surrogates and learning preferences from simple pairwise feedback -- is inefficient for DP because it fails to leverage the problem's unique structure: a point on the Pareto front can be generated directly by maximizing accuracy for a fixed privacy level. Motivated by this property, we first derive the shape of the trade-off theoretically, which allows us to model the Pareto front directly and efficiently. To address inefficiency in preference learning, we replace pairwise comparisons with a more informative interaction. In particular, we present the user with hypothetical trade-off curves and ask them to pick their preferred trade-off. Our experiments on differentially private logistic regression and deep transfer learning across six real-world datasets show that our method converges to the optimal privacy-accuracy trade-off with significantly less computational cost and user interaction than baselines.
BibTeX
@misc{yang2025interactive,
  author = {Yaohong Yang and Aki Rehn and Sammie Katt and Antti Honkela and Samuel Kaski},
  title = {{An Interactive Framework for Finding the Optimal Trade-off in Differential Privacy}},
  year = {2025},
  eprint = {2509.04290},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2509.04290},
}
Figure