Privacy-Computation Trade-Offs in Private Repetition and Metaselection

Randomized algorithms have probabilistic guarantees. Often one designs an algorithm that succeeds (for an appropriate notion of success) with constant probability. A standard approach to boosting the success probability of a randomized algorithm is to run the algorithm with fresh randomness multiple times and take the best of the results of individual runs. Standard tail inequalities then allow for proving bounds on the success probability of the resulting algorithm. Suppose that an algorithm $𝒜$ produces an output with quality score at least $m$ with probability at least $\frac{1}{2}$.¹¹1Without loss of generality, we assume our goal is to maximize a quality score; our results can be translated immediately to a setting where want to minimize a quality score. The constant $\frac{1}{2}$ can be replaced by any other constant. As an example, the algorithm of [13] for finding a maximum cut in the graph finds a cut with value within a small constant factor of the optimum with constant probability. Let ${𝒜}_{\max }^T$ be the algorithm that runs $𝒜$ $T$ times to get outputs $o_1,\mathrm{\dots },o_T$ and releases the $o_i$ with the highest quality score. The basic repetition theorem says that ${𝒜}_{\max }^T$ produces an output with quality score at least $m$ except with probability $\frac{1}{2^T}$. An important aspect of this result is the relationship between the failure probability and the number of repetitions: logarithmically many repetitions suffice to make the failure probability polynomially small. In the example above, repeating the maximum cut algorithm 20 times ensures that the best cut amongst these is approximately optimal except with probability ${10}^{-6}$. Various versions of repetition theorems have been studied in literature, e.g. improving on the amount of randomness needed [19], or allowing for parallelizability in case of multiple round protocols [27, 18].

In this work, we are interested in this question when the algorithm $𝒜$ is differentially private (see Section 2 for a precise definition). We assume we have a differentially private algorithm that outputs an object (e.g. an ML model) and a score (e.g. approximate accuracy on a test dataset), where the score is “high” with constant probability. Private Repetition theorems allow for boosting the success probability, while controlling the privacy cost. A simple repetition theorem uses the ${𝒜}_{\max }^T$ above. To get failure probability below $\gamma$, it would suffice to set $T={\log }_2\frac{1}{\gamma }$. This increases the privacy parameters (e.g. the $\epsilon$ in $(\epsilon ,\delta )$-DP) of the algorithm by a factor of $T$ which may be undesirable. Liu and Talwar [20] designed and analyzed a different algorithm for private repetition that we will refer to as ${𝒜}_{LT}$  for the rest of introduction. The algorithm ${𝒜}_{LT}$  allows for a constant ($3\times$) increase in the privacy cost, while allowing an arbitrarily small failure probability $\gamma$. However, it requires running the algorithm $𝒜$ about $O(\frac{1}{\gamma })$ times, instead of the logarithmic dependence on ${\gamma }^{-1}$ in the naive repetition theorem.

In other words, existing private repetition theorems either pay a $\log \frac{1}{\gamma }$ overhead in the privacy cost, or a $\text{poly}(\frac{1}{\gamma })$ overhead in the run time. A similar dichotomy exists for private hyperparameter selection, where one wants to privately select the best model amongst those resulting from different hyperparameter choices. Indeed private hyperparameter tuning is one of the standard uses of private repetition theorems  [20, 26] and the ${𝒜}_{LT}$  algorithm has been used in practice recently by Israel’s Ministry of Health in their release of 2014 live births microdata [17]. The private learning algorithms for a single hyperparameter setting can can be computationally expensive to run. As an example, in Hod and Canetti [17], the algorithm $𝒜$ can involve training a CTGAN [33, 34, 28] using DPSGD [1] or PATE [24, 25] for a certain set of hyperparameters. In such cases, the $\text{poly}(\frac{1}{\gamma })$ run time overhead can be quite significant.

As we show in Section 4, the two algorithms above can be combined to give a smooth trade-off between the privacy cost overhead and the computational overhead. It is natural to ask however if such a trade-off is necessary: is there a way to keep the privacy overhead to constant while paying only logarithmically in the run time?

In this work, we give a negative answer to this question. We show that for any algorithm with constant privacy overhead, the run time must necessarily be polynomial in $\frac{1}{\gamma }$. More generally, our lower bound shows that the trade-off between the computational overhead (denoted by $T$ below) and the privacy overhead (denoted by $c$ below) is nearly tight.

These results are shown pictorially in Figure 1 (left). The two green filled dots denote the trade-offs achieved by ${𝒜}_{LT}$  and ${𝒜}_{\max }^T$. The blue dashed line is the upper bound achieved by combining these algorithms (Section 4). The grey shaded region can be excluded by straightforward arguments. The lower bound above excludes the red striped region. In particular, it shows that for any constant $c$, $T$ must be at least $\text{poly}(\frac{1}{\gamma })$. At the other extreme, any $T$ that is polylogarithmic in $\frac{1}{\gamma }$ requires $c\ge \mathrm{\Omega }(\frac{\ln \frac{1}{\gamma }}{\ln \ln \frac{1}{\gamma }})$. These results hold even when the target value $m$ is public.

We extend our results to the setting where the target value $m$ is achieved by the mechanism $ℳ$ with a probability that is different from $\frac{1}{2}$. More generally, in the hyperparameter tuning setting, there are $K$ possible settings of hyperparameters, and our utility bound asks that the algorithm be competitive with the median value of the best hyperparameter setting.

We show these results in  Figure 1 (right). As before, the two green filled dots denote the trade-offs achieved by ${𝒜}_{LT}$  and ${𝒜}_{\max }^T$. Note the here ${𝒜}_{\max }^T$ is significantly worse, and the better upper bounds is achieved by combining ${𝒜}_{LT}$  with ${𝒜}_{\max }^T$. As before the grey shaded region is excluded by straightforward arguments, and the new lower bound exclude the red striped region. In particular, it shows that for any constant $c$, $T$ must be at least $K\cdot \text{poly}(\frac{1}{\gamma })$. At the other extreme, making $T/K$ polylogarithmic in $\frac{1}{\gamma }$ requires $c\ge \mathrm{\Omega }(\frac{\ln \frac{1}{\gamma }}{\ln \ln \frac{1}{\gamma }})$. As before, the lower bound holds for known target value $m$.

This has strong implications for private hyperparameter tuning. Indeed our results imply that any private hyperparameter tuning algorithm that boosts the success probability to $(1-\gamma )$ while paying only a constant overhead in privacy cost must pay a $K\cdot \text{poly}({\gamma }^{-1})$ computational overhead.

We remark that both the upper bounds translate $\epsilon$-DP algorithms to $c\epsilon$-DP algorithms, and $(\epsilon ,\delta )$-DP algorithms to $(c\epsilon ,T\delta )$-DP algorithms; similar results hold for Renyi DP algorithms as well [26]. Our lower bounds apply even when the input algorithm is $\epsilon$-DP, and the output algorithm is allowed to be $(\epsilon ,\delta )$-DP (or Renyi DP).

Differential Privacy [9] constrains the distribution of outcomes on neighboring datasets to be close. The Hamming distance ${|d-d^{\prime }|}_H$ between two datasets $d,d^{\prime }\in {𝒟}^n$ is the number of entries in which they differ. For our purposes, two datasets $d,d^{\prime }\in {𝒟}^n$ are neighboring if they differ in one entry, i.e. if their Hamming distance is 1.

Sometimes it is convenient to define a mechanism on a subset of inputs, and establish its privacy properties on this restricted subset. The following extension lemma due to Borgs et al. [4] shows that any such partial specification can be extended to the set of all datasets at a small increase in the privacy cost.

We will be interested in private mechanisms that output a tuple $(o,v)\in ℛ\subset {ℛ}_o\times ℝ$ where ${ℛ}_o$ is some arbitrary output space. For example, if the mechanism is computing an approximate maximum cut in a graph, $o$ could be a subset of vertices of a graph and $v$ the (approximate) number of edges in the input graph that leave this subset $o$. In the case of hyperparameter tuning, $o$ would be a model and $v$ an estimate of its accuracy. We denote by $\text{val}(ℳ(d))$ the real value $v$ when $ℳ(d)=(o,v)$. For a mechanism $ℳ:D^n\to {ℛ}_o\times ℝ$, we let $Median(ℳ(d))=sup\{z:{\mathrm{Pr}}_{(o,v)\sim ℳ(d)}[v\ge z]\ge \frac{1}{2}\}$ denote the median of $v$ when $(o,v)\sim ℳ(d)$. A private amplification algorithm takes as input a dataset $d$ and a failure probability $\gamma$, and given oracle access to a mechanism $ℳ$, outputs an $(o,v)\in ℛ$ such that $v\ge Median(ℳ(d))$ with probability $(1-\gamma )$. Here this probability is taken over both the internal randomness of the amplification algorithm as well as the randomness in $ℳ$. A private amplification algorithm may need to make $T$ oracle calls to $ℳ$, and may be $c\epsilon$-DP whenever $ℳ$ is $\epsilon$-DP. Our goal is to understand the trade-off between the computational overhead $T$ and the privacy overhead $c$.

We will assume that $𝒜$ can only output an $(o,v)$ tuple that is produced by a run of $ℳ$ on some input. This is a natural restriction in all settings, and is needed to make the problem meaningful.²²2E.g., a trivial algorithm that computes $(o,v)\sim ℳ(d)$ and outputs $(o,\mathrm{\infty })$ would not be useful in any application. Thus in this paper, we will always make the assumption that the oracle algorithm $𝒜$ selects a tuple $(o,v)$ from the outputs it receives from calls to $ℳ$.

A private metaselection algorithm operates on a set of $K$ private algorithms ${ℳ}_1,\mathrm{\dots },{ℳ}_K$, where each ${ℳ}_i:{𝒟}^n\to ℛ\subset {ℛ}_o\times ℝ$. It takes as input a dataset $d$ and a failure probability $\gamma$, and given oracle access to mechanisms ${ℳ}_i$, outputs an $(o,v)\in ℛ$ such that $v\ge {\max }_{i}Median({ℳ}_i(d))$ with probability $(1-\gamma )$. As above, the probability is taken over both the internal randomness of the metaselection algorithm as well as the randomness in ${ℳ}_i$’s. The metaselection algorithm may need to make $T$ oracle calls to the ${ℳ}_i$’s, and may be $c\epsilon$-DP whenever each ${ℳ}_i$ is $\epsilon$-DP. Our goal as before is to understand the trade-off between the computational overhead $T$ and the privacy overhead $c$. Note that hyperparameter tuning can be phrased as metaselection, by treating the private training algorithm for each setting of hyperaprameters as a separate algorithm amongst $K$ options. More generally, we can phrase metaselection and hyperparameter tuning as special cases of repetition, where the target value is the $(1-\frac{1}{2K})$th quantile of the distribution, instead of the median. This variant can handle the case when the set of hyperparameter settings may be large (or even unbounded) but we expect a non-trivial measure of the hyperparameter settings to be good.

As mentioned earlier, two extreme points on the trade-off between the privacy overhead and the run time overhead are known. We show next the trade-off that is achievable by a simple combination of the basic approaches. We consider the goal of matching the median score, that is the common case for private repetition (labeled Repetition below), as well as the goal of matching the $(1-\frac{1}{K})$th quantile, which is the case for metaselection and hyperparameter tuning (labeled Metaselection below). We first state the results one gets from simple repetition.