Research map / Federated learning and privacy / Differential privacy
Instance-Specific Asymmetric Sensitivity in Differential Privacy
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes the asymmetric sensitivity mechanism, which applies sparse vector technique to a reflective inverse sensitivity to get private estimates that exploit asymmetric sensitivities, with O(n) instantiations for variance and ML evaluation metrics.
Problem
Differentially private estimation of general functions (variance, cross-entropy, MSE, MAE) with low error that adapts to dataset hardness, including unbounded data where local sensitivity can be infinite.
Approach
Replaces the exponential mechanism in the inverse sensitivity mechanism with sparse vector technique over a reflective inverse sensitivity (signed distance around f(x)), deliberately introducing a small bias toward early stopping to exploit asymmetric upper/lower sensitivities and reduce variance.
Key results
- Asymmetric sensitivity mechanism shows substantially less absolute error than inverse sensitivity mechanism for private variance estimation across privacy parameters and datasets (per paper's empirical study).
- Unbounded upper output bounds (U=infinity) cause only slim performance loss versus bounded-range variance estimation.
- Simulations show error ratio (ISM error / ASM error) increases with asymmetry of sensitivities.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the asymmetric sensitivity mechanism instead of the inverse sensitivity mechanism | Private variance estimation · Variance estimation across the studied datasets and privacy parameters | average absolute error | Helped |
| Use the asymmetric sensitivity mechanism instead of the inverse sensitivity mechanism | Private model evaluation · Cross-entropy loss estimation | average absolute error | Helped |
| Use the asymmetric sensitivity mechanism instead of the inverse sensitivity mechanism | Private model evaluation · Regression MSE and MAE estimation | average absolute error | Helped |
| Allow unbounded upper output bounds instead of using reasonable finite bounds | Asymmetric sensitivity mechanism for variance estimation · Variance estimation across the studied datasets | absolute error | No clear effect |
Surprising findings
- Adding a small bias from early stopping of sparse vector technique reduces variance enough to beat unbiased inverse sensitivity.
Limitations
- Current instantiations are one-dimensional; higher dimensions are computationally inefficient and asymmetry is less inherent.
- Requires a data-independent stream of potential outputs whose choice (beta parameter) matters.
- Approximate bounds reduce accuracy slightly relative to exact inverse sensitivity.
Experimental setup
Datasets: Adult Diabetes MNIST CIFAR-10 Diamonds Abalone Bike
Benchmarks: Adult Diabetes MNIST CIFAR-10 Diamonds Abalone Bike
Metrics: average absolute error error ratio ISM/ASM 0.9 confidence intervals
Baselines: inverse sensitivity mechanism
Builds on: inverse sensitivity mechanism smooth sensitivity AboveThreshold / sparse vector technique exponential mechanism
Closest papers by meaning
- Instance-optimality in differential privacy via approximate inverse sensitivity mechanisms (NeurIPS 2020 · similarity 0.94)
- Subset-Based Instance Optimality in Private Estimation (ICML 2023 · similarity 0.90)
- Minimax Optimal Estimation of Approximate Differential Privacy on Neighboring Databases (NeurIPS 2019 · similarity 0.90)
- Certification for Differentially Private Prediction in Gradient-Based Training (ICML 2025 · similarity 0.89)
- Auditing $f$-differential privacy in one run (ICML 2025 · similarity 0.88)
- Private Adaptive Covariance Estimation via Gaussian Graphical Models (NeurIPS 2026 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.