Privacy-Computation trade-offs in Private Repetition and Metaselection
This addresses privacy-computation trade-offs in private repetition and metaselection, with incremental improvements in algorithm design.
The paper tackles the problem of boosting differentially private algorithms' success probability while preserving privacy cost, showing that failure probability decreases only polynomially with computational overhead, unlike the exponential decrease in non-private settings, and provides near-matching tradeoffs.
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.