Computational Privacy Trade-offs in Secret Replication and Meta-selection

The Secret Iteration Algorithm takes as input a different secret algorithm with a constant probability of success and expands it to one that succeeds with a high probability. These algorithms are closely related to private metaselection algorithms that compete with the best private algorithms, and private hyperparameter tuning algorithms that compete with the best hyperparameter settings of a private learning algorithm. Existing algorithms for these tasks pay a large overhead in privacy costs, or a large overhead in computational costs. In this work, we show strong lower bounds for problems of this type, showing in particular that for any algorithm that keeps the privacy cost to a constant factor, the probability of failure can only fall polynomially on the computational overhead. This is in stark contrast to the non-confidential setting, where the probability of failure drops significantly from the computational overhead. By carefully combining existing metaselection algorithms, we prove a computational privacy tradeoff that approximates our lower bounds.