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