# Privacy-Computation trade-offs in Private Repetition and Metaselection

arXiv: https://arxiv.org/abs/2410.19012 · HTML: https://mlsanity.com/paper/2410.19012/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 34 references that are in the map.
- First posted on arXiv 22 Oct 2024.

## Builds on (most cited first, 15 of 15)

- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Modeling Tabular data using Conditional GAN](https://mlsanity.com/paper/1907.00503/) (2019)
- [Renyi Differential Privacy](https://mlsanity.com/paper/1702.07476/) (2017)
- [Semi-supervised Knowledge Transfer for Deep Learning from Private Training Data](https://mlsanity.com/paper/1610.05755/) (2016)
- [Scalable Private Learning with PATE](https://mlsanity.com/paper/1802.08908/) (2018)
- [Hyperparameter Tuning with Renyi Differential Privacy](https://mlsanity.com/paper/2110.03620/) (2021)
- [Private Selection from Private Candidates](https://mlsanity.com/paper/1811.07971/) (2018)
- [Differentially Private Synthetic Data: Applied Evaluations and Enhancements](https://mlsanity.com/paper/2011.05537/) (2020)
- [Practical Locally Private Heavy Hitters](https://mlsanity.com/paper/1707.04982/) (2017)
- [Hyperparameter Optimization: A Spectral Approach](https://mlsanity.com/paper/1706.00764/) (2017)
- [Differentially Private Release of Israel's National Registry of Live Births](https://mlsanity.com/paper/2405.00267/) (2024)
- [Revealing Network Structure, Confidentially: Improved Rates for Node-Private Graphon Estimation](https://mlsanity.com/paper/1810.02183/) (2018)
- [Instance-Optimal Private Density Estimation in the Wasserstein Distance](https://mlsanity.com/paper/2406.19566/) (2024)
- [Insufficient Statistics Perturbation: Stable Estimators for Private Least Squares](https://mlsanity.com/paper/2404.15409/) (2024)
- [Almost Tight Bounds for Differentially Private Densest Subgraph](https://mlsanity.com/paper/2308.10316/) (2023)

## Abstract (arXiv)

A Private Repetition algorithm takes as input a differentially private algorithm with constant success probability and boosts it to one that succeeds with high probability. These algorithms are closely related to private metaselection algorithms that compete with the best of many private algorithms, and private hyperparameter tuning algorithms that compete with the best hyperparameter settings for a private learning algorithm. Existing algorithms for these tasks pay either a large overhead in privacy cost, or a large overhead in computational cost. In this work, we show strong lower bounds for problems of this kind, showing in particular that for any algorithm that preserves the privacy cost up to a constant factor, the failure probability can only fall polynomially in the computational overhead. This is in stark contrast with the non-private setting, where the failure probability falls exponentially in the computational overhead. By carefully combining existing algorithms for metaselection, we prove computation-privacy tradeoffs that nearly match our lower bounds.