Robust and Differentially Private Mean Estimation

Introduction

When releasing database statistics on a collection of entries from individuals, we would ideally like to make it impossible to reverse-engineer each individual’s potentially sensitive information. Privacy-preserving techniques add just enough randomness tailored to the statistical task to guarantee protection. At the same time, it is becoming increasingly common to apply such techniques to databases collected from multiple sources, not all of which can be trusted. Emerging data access frameworks, such as federated analyses across users’ devices or data silos , make it easier to temper with such collected datasets, leaving private statistical analyses vulnerable to a malicious corruption of a fraction of the data.

Differential privacy has emerged as a widely accepted de facto measure of privacy, which is now a standard in releasing the statistics of the U.S. Census data statistics and also deployed in real-world commercial systems . A statistical analysis is said to be differentially private (DP) if the likelihood of the (randomized) outcome does not change significantly when a single arbitrary entry is added/removed (formally defined in §1.2). This provides a strong privacy guarantee: even a powerful adversary who knows all the other entries in the database cannot confidently identify whether a particular individual is participating in the database based on the outcome of the analysis. This ensures plausible deniability, central to protecting an individual’s privacy.

In this paper, we focus on one of the most canonical problems in statistics: estimating the mean of a distribution from i.i.d. samples. For distributions with unbounded support, such as sub-Gaussian and heavy-tailed distributions, fundamental trade-offs between accuracy, sample size, and privacy have only recently been identified and efficient private estimators proposed. However, these approaches are brittle when a fraction of the data is corrupted, posing a real threat, referred to as data poisoning attacks . In defense of such attacks, robust (but not necessarily private) statistics has emerged as a popular setting of recent algorithmic and mathematical breakthroughs .

One might be misled into thinking that privacy ensures robustness since DP guarantees that a single outlier cannot change the estimation too much. This intuition is true only in a low dimension; each sample has to be an obvious outlier to significantly change the mean. However, in a high dimension, each corrupted data point can look perfectly uncorrupted but still shift the mean significant when colluding together (e.g., see Fig. 1). Focusing on the canonical problem of mean estimation, we introduce novel algorithms that achieve robustness and privacy simultaneously even when a fraction of data is corrupted arbitrarily. For such algorithms, there is a fundamental question of interest: do we need more samples to make private mean estimation also robust against adversarial corruption?

Algorithm 2 is $(\varepsilon,\delta)$-DP. When $\alpha$ fraction of the data is arbitrarily corrupted from $n$ samples from a $d$-dimensional sub-Gaussian distribution with mean $\mu$ and an identity sub-Gaussian parameter, if $n=\widetilde{\Omega}(d/\alpha^{2}+(d+d^{1/2}\log(1/\delta))/(\alpha\varepsilon))$ then Algorithm 2 achieves $\|\hat{\mu}-\mu\|_{2}=O(\alpha\sqrt{\log(1/\alpha)})$ w.h.p.

PRIME is $(\varepsilon,\delta)$-DP and under the assumption of Thm.1, if $n=\widetilde{\Omega}(d/\alpha^{2}+(d^{3/2}\log(1/\delta))/(\alpha\varepsilon))$, achieves $\|\hat{\mu}-\mu\|_{2}=O(\alpha\sqrt{\log(1/\alpha)})$ w.h.p.

Heavy-tailed distributions. When samples are drawn from a distribution with a bounded covariance, parameters of Algorithm 2 can be modified to nearly match the optimal sample complexity of (non-robust) private mean estimation in Table 2. This algorithm also matches the fundamental limit on the accuracy of (non-private) robust estimation, which in this case is $\Omega(\alpha^{1/2})$.

The proposed PRIME-ht for covariance bounded distributions achieve computational efficiency at the cost of an extra factor of $d^{1/2}$ in sample size. This bottleneck is also due to DP PCA, and it remains open whether this gap can be closed by an efficient estimator.

PRIME-ht is $(\varepsilon,\delta)$-DP and if $n=\widetilde{\Omega}((d^{3/2}\log(1/\delta))/(\alpha\varepsilon))$ achieves $\|\hat{\mu}-\mu\|_{2}=O(\alpha^{1/2})$ w.h.p. under the assumptions of Thm. 3.

We introduce PRIME which simultaneously achieves $(\varepsilon,\delta)$-DP and robustness against $\alpha$-fraction of corruption. A major challenge in making a standard filter-based robust estimation algorithm (e.g., ) private is the high sensitivity of the filtered set that we pass from one iteration to the next. We propose a new framework which makes private only the statistics of the set, hence significantly reducing the sensitivity. Our major innovation is a tight analysis of the end-to-end sensitivity of this multiple interactive accesses to the database. This is critical in achieving robustness while preserving privacy and is also of independent interest in making general iterative filtering algorithms private.

The classical filter approach (see, e.g. ) needs to access the database $O(d)$ times, which brings an extra $O(\sqrt{d})$ factor in the sample complexity due to DP composition. In order to reduce the iteration complexity, following the approach in , we propose filtering multiple directions simultaneously using a new score based on the matrix multiplicative weights (MMW). In order to privatize the MMW filter, our major innovation is a novel adaptive filtering algorithm DPthreshold($\cdot$) that outputs a single private threshold which guarantees sufficient progress at every iteration. This brings the number of database accesses from $O(d)$ to $O((\log d)^{2})$.

One downside of PRIME is that it requires an extra $d^{1/2}$ factor in the sample complexity, compared to known lower bounds for (non-robust) DP mean estimation. To investigate whether this is also necessary, we propose a sample optimal exponential time robust mean estimation algorithm in §4 and prove that there is no extra statistical cost to jointly requiring privacy and robustness. Our major technical innovations is in using resilience property of the dataset to not only find robust mean (which is the typical use case of resilience) but also bound sensitivity of that robust mean.

2 Preliminary on differential privacy (DP)

DP is a formal metric for measuring privacy leakage when a dataset is accessed with a query .

Let $z\sim{\rm Lap}(b)$ be a random vector with entries i.i.d. sampled from Laplace distribution with pdf $(1/2b)e^{-|z|/b}$. Let $z\sim{\cal N}(\mu,\Sigma)$ denote a Gaussian random vector with mean $\mu$ and covariance $\Sigma$.

We use these output perturbation mechanisms along with the exponential mechanism as building blocks. Appendix A provides detailed survey of privacy and robust estimation.

3 Problem formulation

Similarly, we consider the same problem for heavy-tailed distributions with a bounded covariance. We present the assumption and main results for covariance bounded distributions in Appendix B.

Outline. We present PRIME for sub-Gaussian distribution in §2, and present theoretical analysis in §3. We then introduce an exponential time algorithm with near optimal guarantee in §4. Due to space constraints, analogous results for heavy-tailed distributions are presented in Appendix B.

PRIME: efficient algorithm for robust and DP mean estimation

In order to describe the proposed algorithm PRIME, we need to first describe a standard (non-private) iterative filtering algorithm for robust mean estimation.

Non-private robust mean estimation approaches recursively apply the following filter, whose framework is first proposed in . Given a dataset $S=\{x_{i}\}_{i=1}^{n}$, the current set $S_{0}\subseteq[n]$ of data points is updated starting with $S_{1}=[n]$. At each step, the following filter (Algorithm 1 in ) attempts to detect the corrupted data points and remove them.

Compute the top eigenvector $v_{t}\leftarrow\argmax_{v:\|v\|_{2}=1}v^{\top}{\rm Cov}(S_{t-1})v$ of the covariance of the current data set $\{x_{i}\}_{i\in S_{t-1}}$ ;

Compute scores for all data points $j\in S_{t-1}$: $\tau_{j}\leftarrow\left(v_{t}^{\top}\left(x_{j}-{\rm Mean}(S_{t-1})\right)\right)^{2}$ ;

Draw a random threshold: $Z_{t}\leftarrow{\rm Unif}()$ ;

Remove outliers from $S_{t-1}$ defined as $\{i\in S_{t-1}\,:\,\tau_{i}$ is in the largest $2\alpha$-tail of $\{\tau_{j}\}_{j\in S_{t-1}}$ and $\tau_{i}\geq Z_{t}\,\tau_{\rm max}\}$, where $\tau_{\rm max}=\max_{j\in S_{t-1}}\tau_{j}$

This is repeated until the empirical covariance is sufficiently small and the empirical mean $\hat{\mu}$ is output. At a high level, the correctness of this algorithm relies on the key observation that the $\alpha$-fraction of adversarial corruption can not significantly change the mean of the dataset without introducing large eigenvalues in the empirical covariance. Therefore, the algorithm finds top eigenvector of the empirical covariance in step $1$, and tries to correct the empirical covariance by removing corrupted data points. Each data point is assigned a score in step 2 which indicates the “badness” of the data points, and a threshold $Z_{t}$ in step 3 is carefully designed such that step 4 guarantees to remove more corrupted data points than good data points (in expectation). This guarantees the following bound achieving the near-optimal sample complexity shown in the second row of Table 1. A formal description of this algorithm is in Algorithm 4 in Appendix C.

Under assumption 1, the above filtering algorithm achieves accuracy $\|\hat{\mu}-\mu\|_{2}\leq O(\alpha\sqrt{\log(1/\alpha)})$ w.p. $0.9$ if $n\geq\widetilde{\Omega}(d/\alpha^{2})$ .

Challenges in making robust mean estimation private. To get a DP and robust mean, a naive attempt is to apply a standard output perturbation mechanism to $\hat{\mu}$. However, this is obviously challenging since the end-to-end sensitivity is intractable. The standard recipe to circumvent this is to make the current “state” $S_{t}$ private at every iteration. Once $S_{t-1}$ is private (hence, public knowledge), making the next “state” $S_{t}$ private is simpler. We only need to analyze the sensitivity of a single step and apply some output perturbation mechanism with $(\varepsilon_{t},\delta_{t})$. End-to-end privacy is guaranteed by accounting for all these $(\varepsilon_{t},\delta_{t})$’s using the advanced composition . This recipe has been quite successful, for example, in training neural networks with (stochastic) gradient descent , where the current state can be the optimization variable $\mathbf{x}_{t}$. However, for the above (non-private) filtering algorithm, this standard recipe fails, since the state $S_{t}$ is a set and has large sensitivity. Changing a single data point in $S_{t}$ can significantly alter which (and how many) samples are filtered out.

2 A new framework for private iterative filtering

Instead of making the (highly sensitive) $S_{t}$ itself private, we propose a new framework which makes private only the statistics of $S_{t}$: the mean $\mu_{t}$ and the top principal direction $v_{t}$. There are two versions of this algorithm, which output the exactly same $\hat{\mu}$ with the exactly same privacy guarantees, but are written from two different perspectives. We present here the interactive version from the perspective of an analyst accessing the dataset via DP queries ($q_{\rm range},q_{\rm size},q_{\rm mean},q_{\rm norm}$ and $q_{\rm PCA}$), because this version makes clear the inner operations of each private mechanisms, hence making $(i)$ the sensitivity analysis transparent, $(ii)$ checking the correctness of privacy guarantees easy, and $(iii)$ tracking privacy accountant simple. In practice, one should implement the centralized version (Algorithm 7 in Appendix D), which is significantly more efficient.

We give a high-level explanation of each step of Algorithm 1 here and give the formal definitions of all the queries in Appendix D. First, $q_{\rm range}$ returns (the parameters of) a hypercube $\bar{x}+[-B/2,B/2]^{d}$ that is guaranteed to include all uncorrupted samples while preserving privacy. This is achieved by running $d$ coordinate-wise private histograms and selecting $\bar{x}_{j}$ as the center of the largest bin for the $j$-th coordinate. Since covariance is ${\bf I}$, $q_{\rm range}$ returns a fixed $B=8\sigma\sqrt{\log(dn/\zeta)}$. Such an adaptive estimate of the support is critical in tightly bounding the sensitivity of all subsequent queries, which operate on the clipped dataset; all data points are projected as ${\cal P}_{\bar{x}+[-B/2,B/2]^{d}}(x)=\arg\min_{y\in\bar{x}+[-B/2,B/2]^{d}}\|y-x\|_{2}$ in all the queries that follow. With clipping, a single data point can now change at most by $B\sqrt{d}$.

The subsequent steps perform the non-private filtering algorithm of §2.1, but with private statistics $\mu_{t}$ and $v_{t}$. As the set $S_{t}$ changes over time, we lower bound its size (which we choose to be $|S_{t}|>n/2$) to upper bound the sensitivity of other queries $q_{\rm mean},q_{\rm norm}$ and $q_{\rm PCA}$.

Recall that two datasets are neighboring, i.e., ${\cal S}\sim{\cal S}^{\prime}$, iff $d_{\triangle}({\cal S},{\cal S}^{\prime})\leq 1$. This lemma implies that if two datasets are neighboring, then they are still neighboring after filtering with the same parameters, no matter how many times we filter them. Hence, this lemma allows us to use the standard output-perturbation mechanisms with $(\varepsilon_{1},\delta_{1})$-DP. Advanced composition ensures that end-to-end guarantee of $4T$ such queries is $(0.99\varepsilon,0.99\delta)$-DP. Together with $(0.01\varepsilon,0.01\delta)$-DP budget used in $q_{\rm range}$, this satisfied the target privacy. Analyzing the utility of this algorithm, we get the following guarantee.

Algorithm 1 is $(\varepsilon,\delta)$-DP. Under Assumption 1, there exists a universal constant $c\in(0,0.1)$ such that if $\alpha\leq c$ and $n=\widetilde{\Omega}\left((d/\alpha^{2})+{d^{2}(\log(1/\delta))^{3/2}}/({\varepsilon\alpha})\right)$ then Algorithm 1 achieves $\|\hat{\mu}-\mu\|_{2}\leq O(\alpha\sqrt{\log(1/\alpha)})$ with probability $0.9$.

The first term $O(d/\alpha^{2})$ in the sample complexity is optimal (cf. Table 1), but there is a factor of $d$ gap in the second term. This is due to the fact that we need to run $O(d)$ iterations in the worst-case. Such numerous accesses to the database result in large noise to be added at each iteration, requiring large sample size to combat that extra noise. We introduce PRIME to reduce the number of iterations to $O((\log d)^{2})$ and significantly reduce the sample complexity.

3 PRIME: novel robust and private mean estimator

Algorithm 1 (specifically Filter($\cdot$) in Algorithm 1) accesses the database $O(d)$ times. This is necessary for two reasons. First, the filter checks only one direction $v_{t}$ at each iteration. In the worst case, the corrupted samples can be scattered in $\Omega(d)$ orthogonal directions such that the filter needs to be repeated $O(d)$ times. Secondly, even if the corrupted samples are clustered together in one direction, the filter still needs to be repeated $O(d)$ times. This is because we had to use a large (random) threshold of $dB^{2}Z_{t}=O(d)$ to make the threshold data-independent so that we can keep the sensitivity of Filter($\cdot$) low, which results in slow progress. We propose filtering multiple directions simultaneously using a new score $\{\tau_{i}\}$ based on the matrix multiplicative weights. Central to this approach is a novel adaptive filtering algorithm DPthreshold($\cdot$) that guarantees sufficient decrease in the total score at every iteration.

for some choice of $\alpha^{(s)}>0$. If we set the number of iterations to one, a choice of $\alpha^{(s)}=\infty$ recovers the previous score that relied on the top singular vector from §2.1 and a choice of $\alpha^{(s)}=0$ gives a simple norm based score $\tau_{i}=\|x_{i}\|^{2}_{2}$. An appropriate choice of $\alpha^{(s)}$ smoothly interpolates between these two extremes, which ensures that $O(\log d)$ iterations are sufficient for the spectral norm of the covariance to decrease strictly by a constant factor. This guarantees that after $O(\log d)$ epochs, we sufficiently decrease the covariance to ensure that the empirical mean is accurate enough. Critical in achieving this gain is our carefully designed filtering algorithm DPthreshold that uses the privately computed MMW-based scores using Gaussian mechanism on the covariance matrices as shown in Algorithm 11 in Appendix E.

Novelty. The corresponding non-private filtering of [36, Algorithm 9] for robust mean estimation takes advantage of an adaptive threshold, but filters out each sample independently resulting in a prohibitively large sensitivity; the coupling between each sample and the randomness used to filter it can change widely between two neighboring datasets. On the other hand, Algorithm 1 (i.e., Filter($\cdot$) in Algorithm 6) takes advantage of jointly filtering all points above a single threshold $B^{2}dZ_{t}$ with a single randomness $Z_{t}\sim{\rm Unif}$, but the non-adaptive (and hence large) choice of the range $B^{2}d$ results in a large number of iterations because each filtering only decrease the score by little. To sufficiently reduce the total score while maintaining a small sensitivity, we introduce a filter with a single and adaptive threshold.

Algorithm. Our goal here is to privately find a single scalar $\rho$ such that when a randomized filter is applied on the scores $\{\tau_{i}\}$ with a (random) threshold $\rho Z$ (with $Z$ drawn uniform in $$), we filter out enough samples to make progress in each iteration while ensuring that we do not remove too many uncorrupted samples. This is a slight generalization of the non-private algorithm in Section 2.1, which simply set$\rho=\max_{j\in S_{t}}\tau_{j}$. While this guarantees the filter removes more corrupted samples than good samples, it does not make sufficient progress in reducing the total score of the samples.

Ideally, we want the thresholding to decrease the total score by a constant multiplicative factor, which will in the end allow the algorithm to terminate within logarithmic iterations. To this end, we propose a new scheme of using the largest $\rho$ such that the following inequality holds:

We use a private histogram of the scores to approximate this threshold. Similar to , we use geometrically increasing bin sizes such that we use only $O(\log B^{2}d)$ bins while achieving a preferred multiplicative error in our quantization. At each epoch $s$ and iteration $t$, we run DPthreshold sketched in the following to approximate $\rho$ followed by a random filter. Step 3 replaces the non-private condition in Eq. (1). A complete description is provided in Algorithm 11.

Privately compute scores for all data points $i\in S_{t}^{(s)}:\,\tau_{i}\leftarrow(x_{i}-\mu_{t})^{\top}U_{t}^{(s)}(x_{i}-\mu_{t})$ ;

Analyses of PRIME

Building on the framework of Algorithm 1, PRIME (Algorithm 9) replaces the score with the MMW-based score presented in §2.3.1 and the filter with the adaptive DPthreshold. This reduces the number of iterations to $T=O((\log d)^{2})$ achieving the following bound.

PRIME is $(\varepsilon,\delta)$-differentially private. Under Assumption 1 there exists a universal constant $c\in(0,0.1)$ such that if $\alpha\leq c$ and $n=\widetilde{\Omega}((d/\alpha^{2})+(d^{3/2}/(\varepsilon\alpha))\log(1/\delta))$, then PRIME achieves $\|\hat{\mu}-\mu\|_{2}=O(\alpha\sqrt{\log(1/\alpha)})$ with probability $0.9$.

A proof is provided in Appendix F. The notation $\widetilde{\Omega}(\cdot)$ hides logarithmic terms in $d$, $R$, and $1/\alpha$. To achieve an error of $O(\alpha\sqrt{\log(1/\alpha)})$, the first term $\widetilde{\Omega}(d/\alpha^{2}\log(1/\alpha))$ is necessary even if there is no corruption. The accuracy of $O(\alpha\sqrt{\log(1/\alpha)})$ matches the lower bound shown in for any polynomial time statistical query algorithm, and it nearly matches the information theoretical lower bound on robust estimation of $\Omega(\alpha)$. On the other hand, the second term of $\widetilde{\Omega}(d^{3/2}/(\varepsilon\alpha\log(1/\alpha)))$ has an extra factor of $d^{1/2}$ compared to the optimal one achieved by exponential time Algorithm 2. It is an open question if this gap can be closed by a polynomial time algorithm.

The bottleneck is the private matrix multiplicative weights. Such spectral analyses are crucial in filter-based robust estimators. Even for a special case of privately computing the top principal component, the best polynomial time algorithm requires $O(d^{3/2})$ samples , and this sample complexity is also necessary as shown in [39, Corollary 25].

To boost the success probability to $1-\zeta$ for some small $\zeta>0$, we need an extra $\log(1/\zeta)$ factor in the sample complexity to make sure the dataset satisfies the regularity condition with probability $\zeta/2$. Then we can run PRIME $\log(1/\zeta)$ times and choose the output of a run that satisfies $n^{(s)}>n(1-10\alpha)$ and $\lambda^{(s)}\leq C\alpha\log(1/\alpha)$ at termination.

Numerical experiments support our theoretical claims. The left figure with $(\alpha,\varepsilon,\delta,n)=(0.05,20,0.01,10^{6})$ is in the large $\alpha$ regime where the DP Mean error is dominates by $\alpha\sqrt{d}$ and PRIME error by $\alpha\sqrt{\log(1/\alpha)}$. Hence, PRIME error is constant whereas DP Mean error increases with the dimension $d$. The second figure with $(\alpha,\varepsilon,\delta,n)=(0.001,20,0.01,10^{6})$ is in the small $\alpha$ regime when DP Mean error consists of $\alpha\sqrt{d}+\sqrt{d/n}$ and PRIME is dominated by $\sqrt{d/n}$. Both increase with the dimension $d$, and the gap can be made large by increasing $\alpha$. The right figure with $(\alpha,\delta,d,n)=(0.1,0.01,10,10^{6})$ is when DP Mean error is dominated by $\alpha\sqrt{d}$ and PRIME by $\alpha\sqrt{\log(1/\alpha)}$ when $\varepsilon>cd^{1.5}/(\alpha n)$. Below this threshold, which happens in this example around $\varepsilon=0.05$, the added noise in the private mechanism starts to dominate with decreasing $\varepsilon$. Both algorithms have respective thresholds below which the error increases with decreasing $\varepsilon$. This threshold is larger for PRIME because it uses the privacy budget to perform multiple operations and hence the noise added to the final output is larger compared to DP Mean. Below this threshold, which can be easily determined based on the known parameters $(\varepsilon,\delta,n,\alpha)$, we should either collect more data (which will decrease the threshold) or give up filtering and spend all privacy budget on $q_{\rm range}$ and the empirical mean (which will reduce the error). Details of the experiments are in Appendix L.

Exponential time algorithm with near-optimal sample complexity

Novelty. An existing exponential time algorithm for robust and private mean estimation in strictly requires the uncorrupted samples to be drawn from a Gaussian distribution. We also provide a similar algorithm based on private Tukey median in Appendix I and its analysis in Appendix J. In this section, we introduce a novel estimator that achieves near-optimal guarantees for more general sub-Gaussian distributions (and also covariance bounded distributions) but takes an exponential run-time. Its innovation is in leveraging on the resilience property of well-behaved distributions not only to estimate the mean robustly (which is the standard use of the property) but also to adaptively bound the sensitivity of the estimator, thus achieving optimal privacy-accuracy tradeoff.

Algorithm. As data is corrupted, we define $R(S)$ as a surrogate for resilience of the uncorrupted part of the set. If $S$ indeed consists of a $1-\alpha$ fraction of independent samples from the promised class of distributions, the goodness score $R(S)$ will be close to the resilience property of the good data.

For $\mu(S)=(1/|S|)\sum_{i\in S}x_{i}$, let us define

Algorithm 2 first checks if the resilience matches that of the promised distribution. The data is pre-processed with $q_{\rm range}$ to ensure we can check $R(S)$ privately. Once resilience is cleared, we can safely use the exponential mechanism based on the score function $d(\hat{\mu},S)$ in Definition 4.3 to select an approximate robust mean $\hat{\mu}$ privately. The choice of the sensitivity critically relies on the fact that resilient datasets have small sensitivity of $O((1/n)\sqrt{\log(1/\alpha)})$. Without the resilience check, the sensitivity is $O(d^{1/2}/n)$ resulting in an extra factor of $\sqrt{d}$ in the sample complexity.

We propose the score function $d(\hat{\mu},S)$ in the following definition, which is a robust estimator of the distance between the mean and the candidate $\hat{\mu}$.

Analysis. For any direction $v$, the truncated mean estimator $\mu({\cal M}^{v})$ provides a robust estimation of the true mean along the direction $v$, thus the distance can be simply defined by taking the maximum over all directions $v$. We show the sensitivity of this simple estimator is bounded by the resilience property $\sigma$ divided by $n$, which is $O((1/n)\sqrt{\log(1/\alpha)})$ once the resilience check is passed. This leads to the following near-optimal sample complexity. We provide a proof in Appendix H.2.

Algorithm 2 is $(\varepsilon,\delta)$-DP. Under Assumption 1, this algorithm achieves $\|\hat{\mu}-\mu\|_{2}=O(\alpha\sqrt{\log(1/\alpha)})$ with probability $1-\zeta$ if

Run-time. Computing $R(S)$ exactly can take $O(de^{\Theta(n)})$ operations. The exponential mechanism implemented with $\alpha$-covering for $\hat{\mu}$ and a constant covering for $v$ can take $O(nd(\sqrt{\log(dn/\zeta)}/\alpha)^{d})$ operations.

Conclusion

There are several directions for improving our results further and applying the framework to solve other problems. PRIME provides a new design principle for private and robust estimation. This can be more broadly applied to fundamental statistical analyses such as robust covariance estimation robust PCA , and robust linear regression .

PRIME could be improved in a few directions. First, the sample complexity of $\widetilde{\Omega}((d/(\alpha^{2}\log(1/\alpha)))+(d^{3/2}/(\varepsilon\alpha\log(1/\alpha)))\log(1/\delta))$ in Theorem 6 is suboptimal in the second term. Improving the $d^{3/2}$ factor requires bypassing differentially private singular value decomposition, which seems to be a challenging task. However, it might be possible to separate the $\log(1/\delta)$ factor from the rest of the terms and get an additive error of the form $\widetilde{\Omega}((d/(\alpha^{2}\log(1/\alpha)))+(d^{3/2}/(\varepsilon\alpha\log(1/\alpha)))+(1/\varepsilon)\log(1/\delta))$. This requires using Laplace mechanism in private MMW (line 10 Algortihm 10). Secondly, the time complexity of PRIME is dominated by computation time of the matrix exponential in (line 10 Algortihm 10). Total number of operations scale as $\widetilde{O}(d^{3}+nd^{2})$. One might hope to achieve $\widetilde{O}(nd)$ time complexity using approximate computations of $\tau_{j}$’s using techniques from . This does not improve the sample complexity, as the number of times the dataset is accessed remains the same. Finally, for (non-robust) private mean estimation, CoinPress provides a practical improvement in the small sample regime by progressively refining the search space . The same principle could be applied to PRIME to design a robust version of CoinPress. One important question remains open; how are differential privacy and robust statistics fundamentally related? We believe our exponential time algorithm hints on a fundamental connection between robust statistics of a data projected onto one-dimensional subspace and sensitivity of resulting score function for the exponential mechanism. It is an interesting direction to pursue this connection further to design novel algorithms that bridge privacy and robustness.

Acknowledgement

Sham Kakade acknowledges funding from the National Science Foundation under award CCF-1703574. Sewoong Oh acknowledges funding from Google faculty research award, NSF grants IIS-1929955, CCF-1705007, CNS-2002664, CCF 2019844 as a part of Institute for Foundation of Machine Learning, and CNS-2112471 as a part of Institute for Future Edge Networks and Distributed Intelligence.

References

Appendix

In an attempt to design efficient algorithms for robust and private mean estimation, proposed an algorithm with a mis-calculated sensitivity, which can result in violating the privacy guarantee. This can be corrected by pre-processing with our approach of checking the resilience (as in Algorithm 2), but this requires a run-time exponential in the dimension.

However, under $\alpha$-corruption, shows that achieving an error better than $O(\alpha^{1/2})$ under $k$-th moment bound is as computationally hard as the small-set expansion problem, even without requiring DP. Hence, under the assumption of ${\rm P}\neq{\rm NP}$, no polynomial-time algorithm exists that can outperform our PRIME-ht even if we have stronger assumptions of $k$-th moment bound. On the other hand, there exists an exponential time algorithm for non-private robust mean estimation that achieves $\|\mu-\hat{\mu}\|_{2}=O(\alpha^{(k-1)/k})$ . Combining it with the bound of , an interesting open question is whether there is an (exponential time) algorithm that achieves $\|\mu-\hat{\mu}\|_{2}=O(\alpha^{(k-1)/k})$ with sample complexity $n=\widetilde{O}((d/\alpha^{2(k-1)/k})+(d\log^{1/2}(1/\delta)/(\varepsilon\alpha)))$ under $\alpha$-corruption and $(\varepsilon,\delta)$-DP.

Robust estimation. Designing robust estimators under the presence of outliers has been considered by statistics community since 1960s . Recently, give the first polynomial time algorithm for mean and covariance estimation with no (or very weak) dependency on the dimensionality in the estimation error. Since then, there has been a flurry of research on robust estimation problems, including mean estimation , covariance estimation , linear regression and sparse regression , principal component analysis , mixture models and list-decodable learning . See for a survey of recent work.

One line of work that is particularly related to our algorithm PRIME is , which leverage the ideas from matrix multiplicative weight and fast SDP solver to achieve faster, sometimes nearly linear time, algorithms for mean and covariance estimation. In PRIME, we use a matrix multiplicative weight approach similar to to reduce the iteration complexity to logarithmic, which enables us to achieve the $d^{3/2}$ dependency in the sample complexity.

The concept of resilience is introduced in as a sufficient condition such that learning in the presence of adversarial corruption is information-theoretically possible. The idea of resilience is later generalized in for a wider range of adversarial corruption models. While there exists simple exponential time robust estimation algorithm under resilience condition, it is challenging to achieve differential privacy due to high sensitivity. We propose a novel approach to leverage the resilience property in our exponential time algorithm for sub-gaussian and heavy-tailed distributions.

Appendix B Main results under heavy-tailed distributions

We consider distributions with bounded covariance as defined as follows.

Under these assumptions, Algorithm 2 achieves near optimal guarantees but takes exponential time. The dominant term in the sample complexity $\widetilde{\Omega}(d/(\varepsilon\alpha))$ cannot be improved as it matches that of the optimal non-robust private estimation . The accuracy $O(\sqrt{\alpha})$ cannot be improved as it matches that of the optimal non-private robust estimation . We provide a proof in Appendix H.1.

Algorithm 2 is $(\varepsilon,\delta)$-differentially private. Under Assumption 2, if

this algorithm achieves $\|\hat{\mu}-\mu\|_{2}=O(\sqrt{\alpha})$ with probability $0.9$.

PRIME-ht is $(\varepsilon,\delta)$-differentially private. Under Assumption 2 there exists a universal constant $c\in(0,0.1)$ such that if $\alpha\leq c$, and $n=\widetilde{\Omega}((d^{3/2}/(\varepsilon\alpha))\log(1/\delta))$, then PRIME-ht achieves $\|\hat{\mu}-\mu\|_{2}=O(\alpha^{1/2})$ with probability $0.9$. The notation $\widetilde{\Omega}(\cdot)$ hides logarithmic terms in $d$, and $1/\alpha$.

Remark 1. To boost the success probability to $1-\zeta$ for some small $\zeta>0$, we will randomly split the data into $O(\log(1/\zeta))$ subsets of equal sizes, and run Algorithm 3 to obtain a mean estimation from each of the subset. Then we can apply multivariate “mean-of-means” type estimator to get $\|\hat{\mu}-\mu\|_{2}=O(\alpha^{1/2})$ with probability $1-\zeta$. This is efficient as we only have $O(\log 1/\zeta)$ trials and run-time of mean-of-means is dominated by the time it takes to find all pairwise distances, which is only $O(d\,({\rm log}(1/\zeta))^{2})$. There are $({\rm log}(1/\zeta))^{2}$ pairs, and for each pair we compute the distance between means in $d$ operations.

Appendix C Background on (non-private) robust mean estimation

The following tie-breaking rule is not essential for robust estimation, but is critical for proving differential privacy, as shown later in Appendix F.1.

Given a set of scalar values $\{\tau_{i}=\langle V,(x_{i}-\mu)(x_{i}-\mu)^{\top}\rangle\}_{i\in S^{\prime}}$ for a subset $S^{\prime}\subseteq[n]$, define the sorted list $\pi$ of $S^{\prime}$ such that $\tau_{\pi(i)}\geq\tau_{\pi(i+1)}$ for all $i\in[|S^{\prime}|-1]$. When there is a tie such that $\tau_{i}=\tau_{j}$, it is broken by $\pi^{-1}(i)\leq\pi^{-1}(j)\Leftrightarrow x_{i,1}\geq x_{j,1}$. Further ties are broken by comparing the remaining entries of $x_{i}$ and $x_{j}$, in an increasing order of the coordinate. If $x_{i}=x_{j}$ ,then the tie is broken arbitrarily. We define ${\cal T}_{\alpha}=\{\pi(1),\ldots,\pi(\lceil n\alpha\rceil)\}$ to be the set of largest $\lceil n\alpha\rceil$ valued samples.

With this definition of $\alpha$-tail, we can now provide a complete description of the robust mean estimation that achieves the guarantee provided in Proposition 2.1.

Appendix D A new framework for private iterative filtering

We provide complete descriptions of all algorithms used in private iterative filtering. We present the interactive version first, followed by the centralized version.

Adaptive estimation of the range of the dataset is essential in computing private statistics of data. We use the following algorithm proposed in . It computes a private histogram of a set of 1-dimensional points and select the largest bin as the one potentially containing the mean of the data. Note that $B$ does not need not be chosen adaptively to include all the uncorrupted data with a high probability.

The following guarantee (and the algorithm description) is used in the analysis (and the implementation) of the query $q_{\rm range}$.

$\hat{p}_{k}=\frac{1}{n}\sum_{X_{i}\in B_{k}}1$

This is an intermediate result in the proof of Lemma 2.3 in . Note that, conceptually, we are applying the private histogram algorithm to an infinite number of bins in the intervals $\{\cdots,(-4\sigma,-2\sigma],(-2\sigma,0],(0,2\sigma],(2\sigma,4\sigma],(4\sigma,6\sigma]\cdots\}$ each of length $2\sigma$. This is possible because the algorithm only changes the bins that are occupied by at least on sample. Practically, we only need to add noise to those bins that are occupied, and hence we limit the range from $R_{\rm min}^{(j)}$ to $R_{\rm max}^{(j)}$ without loss of generality and without any changes to the privacy guarantee of the algorithm.

D.2 Centralized version of the algorithm

In practice, one should run the centralized version of the private iterative filtering, in order to avoid multiple redundant computations of the interactive version. The main difference is that the redundant filtering repeated every time a query is called in the interactive version is now merged into a single run. The resulting estimation and the privacy loss are exactly the same.

First, $q_{\rm range}$ introduced in , returns a hypercube $\bar{x}+[-B,B]^{d}$ that is guaranteed to include all uncorrupted samples, while preserving privacy. It is followed by a private filtering DPfilter in Algorithm 8.

D.3 The analysis of private iterative filtering (Algorithms 1 and 7) and a proof of Theorem 5

$q_{\rm range}$, introduced in , returns a hypercube $\bar{x}+[-B,B]^{d}$ that is guaranteed to include all uncorrupted samples, while preserving privacy. In the following lemma, we show that $q_{\rm range}$ is also robust to adversarial corruption. Such adaptive bounding of the support is critical in privacy analysis of the subsequent steps. We clip all data points by projecting all the points with ${\cal P}_{\bar{x}+[-B/2,B/2]^{d}}(x)=\arg\min_{y\in\bar{x}+[-B/2,B/2]^{d}}\|y-x\|_{2}$ to lie inside the hypercube and pass them to DPfilter for filtering. The algorithm and a proof are provided in §D.3.1.

$q_{\rm range}(S,\varepsilon,\delta)$ (Algorithm 5) is $(\varepsilon,\delta)$-differentially private. Under Assumption 1, $q_{\rm range}(S,\varepsilon,\delta)$ returns $(\bar{x},B)$ such that if $n=\Omega\left((\sqrt{d\log(1/\delta)}\log(d/(\zeta\delta))/\varepsilon)\right)$ and $\alpha<0.1$, then all uncorrupted samples in $S$ are in $\bar{x}+[-B,B]^{d}$ with probability $1-\zeta$.

In DPfilter, we make only the mean $\mu_{t}$ and the top principal direction $v_{t}$ private to decrease sensitivity. The analysis is now more challenging since $(\mu_{t},v_{t})$ depends on all past iterates $\{(\mu_{j},v_{j})\}_{j=1}^{t-1}$ and internal randomness $\{Z_{j}\}_{j=1}^{t-1}$. To decrease the sensitivity, we modify the filter in line 8 to use the maximum support $dB^{2}$ (which is data independent) instead of the maximum contribution $\max_{i}(v_{t}^{\top}(x_{i}-\mu_{t}))^{2}$ (which is data dependent and sensitive). While one data point can significantly change $\max_{i}(v_{t}^{\top}(x_{i}-\mu_{t}))^{2}$ and the output of one step of the filter in Algorithm 4, the sensitivity of the proposed filter is bounded conditioned on all past $\{(\mu_{j},v_{j})\}_{j=1}^{t-1}$, as we show in the following lemma. This follows from the fact that conditioned on $(\mu_{j},v_{j})$, the proposed filter is a contraction. We provide a proof in Appendix D.3.3 and Appendix D.3.4. Putting together Lemmas D.2 and D.3, we get the desired result in Theorem 5.

DPfilter$(S,\alpha,T,\varepsilon,\delta)$ is $(\varepsilon,\delta)$-differentially private. Under the hypotheses of Theorem 5, DPfilter$(S,\alpha,T=\widetilde{\Theta}(B^{2}d),\varepsilon,\delta)$ achieves $\|\hat{\mu}-\mu\|_{2}=O(\alpha\sqrt{\log(1/\alpha)})$ with probability $0.9$, if $n=\widetilde{\Omega}(d/\alpha^{2}+B^{3}d^{2}\log(1/\delta)/(\varepsilon\alpha))$ and $B$ is large enough such that the original uncorrupted samples are inside the hypercube $\bar{x}+[-B/2,B/2]^{d}$.

Differential privacy guarantee. To achieve $(\varepsilon_{0},\delta_{0})$ end-to-end target privacy guarantee, Algorithm 7 separates the privacy budget into two. The ($0.01\varepsilon_{0},0.01\delta_{0}$)-DP guarantee of $q_{\rm range}$ follows from Lemma D.2. The ($0.99\varepsilon_{0},0.99\delta_{0}$)-DP guarantee of DPfilter follows from Lemma D.3.

Accuracy. From Lemma D.2 $q_{\rm range}$ is guaranteed to return a hypercube that includes all clean data in the dataset. It follows from Lemma D.3 that when $n=\widetilde{\Omega}(d/\alpha^{2}+d^{2}\log(1/\delta)/(\varepsilon\alpha))$, we have $\|\mu-\hat{\mu}\|_{2}=O(\alpha\sqrt{\log(1/\alpha)})$.

Assuming that $n=\Omega\left(\frac{\sqrt{d\log(1/\delta)}}{\varepsilon\beta}\log(d/\zeta\delta)\right)$, we have that with probability $1-\zeta$, $\max_{j,l}(|{h}_{j,l}-\hat{h}_{j,l}|)\leq 0.01+\alpha$. Using the assumption that $\alpha\leq 0.1$, since $\min(h_{j,k-1},h_{j,k},h_{j,k+1})-0.11\geq 0.31\geq 0.04+0.11\geq\max_{l\neq k-1,k,k+1}h_{j,l}+0.11$. This implies that with probability $1-\zeta$, the algorithm choose the bin from $k-1,k,k+1$, which means the estimate $|\bar{x}_{j}-\mu|\leq 4\sigma$. By the tail bound of sub-Gaussian distribution and a union bound over $n,d$, we have that with probability $1-\zeta$, for all $x_{i}\in\mathcal{D}$ and $j\in[d]$, $x_{i,j}\in[\bar{x}_{j}-8\sigma\sqrt{\log(nd/\zeta)},\bar{x}_{j}+8\sigma\sqrt{\log(nd/\zeta)}]$.

Proof of Lemma 2.2. We only need to show that one step of the proposed filter is a contraction. To this end, we only need to show contraction for two datasets at distance 1, i.e., $d_{\triangle}({\cal D},{\cal D^{\prime}})=1$. For fixed $(\mu,v)$ and $Z$, we apply filter to set of scalars $(v^{\top}({\cal D}-\mu))^{2}$ and $(v^{\top}({\cal D^{\prime}}-\mu))^{2}$, whose distance is also one. If the entries that are different (say $a\in{\cal D}$ and $a^{\prime}\in{\cal D^{\prime}}$) are both below the subset of the top $2n\alpha$ points (as in Definition C.1), then the same set of points will be removed for both and the distance is preserved $d_{\triangle}(S({\cal D}),S({\cal D}^{\prime}))=1$. If they are both above the top $2n\alpha$ subset, then either both are removed, one of them is removed, or both remain. The rest of the points that are removed coincide in both sets. Hence, $d_{\triangle}(S({\cal D}),S({\cal D}^{\prime}))\leq 1$. If $a$ is below and $a^{\prime}$ is above the top $2n\alpha$ subset of respective datasets, then either $a^{\prime}$ is not removed (in which case $d_{\triangle}(S({\cal D}),S({\cal D}^{\prime}))=1$) or $a^{\prime}$ is removed (in which case $S({\cal D})=S({\cal D}^{\prime})\cup\{a\}$ and the distance remains one).

Note that when there are ties, it is critical to resolve them in a consistent manner in both datasets ${\cal D}$ and ${\cal D^{\prime}}$. The tie breaking rule of Definition C.1 is critical in sorting those samples with the same score $\tau_{i}$’s in a consistent manner.

Proof of Lemma F.1. The analysis of contraction of the filtering step in DPMMWfilter is analogous to that of private iterative filtering in Lemma 2.2.

We explicitly write out how many times we access the database and how much privacy is lost each time in an interactive version of DPfilter in Algorithm 1, which performs the same operations as DPfilter. In order to apply Lemma G.13, we cap $\varepsilon$ at 0.9 in initializing $\varepsilon_{1}$. We call $q_{\rm mean}$, $q_{\rm PCA}$, $q_{\rm norm}$ and $q_{\rm size}$ $T$ times, each with $(\varepsilon_{1},\delta_{1})$ guarantee. In total this accounts for $(\varepsilon,\delta)$ privacy loss, using Lemma G.13 and our choice of $\varepsilon_{1}$ and $\delta_{1}$.

The following theorem analyzing DPfilter implies the desired Lemma D.3 when the good set is $\alpha$-subgaussian good, which follows from G.3 and the assumption that $n=\widetilde{\Omega}(d/\alpha^{2})$.

To prove this theorem, we use the following lemma to first show that we do not remove too many uncorrupted samples. The upper bound on the accuracy follows immediately from Lemma G.7 and the stopping criteria of the algorithm.

If $n\gtrsim\frac{B^{2}d^{3/2}}{\varepsilon_{1}\alpha\log 1/\alpha}\log(1/\delta)$, $\lambda_{t}\geq(C-0.01)\cdot\alpha\log 1/\alpha$ and $|S_{t}\cap S_{\rm good}|\geq(1-10\alpha)n$, then there exists constant $C>0$ such that for each iteration $t$, with probability $1-O(1/d)$, we have Eq. (4) holds. If this condition holds, we have

Now we bound the number of iterations under the conditions of Lemma D.5. Let $W_{t}=|S_{t}\setminus S_{t-1}|/n$. Since Eq. (5), we have

Let $T$ be the stopping time. We know $\sum_{t=1}^{T}W_{t}\leq 10\alpha$. By Wald’s equation, we have

Assuming we have $\|M(S_{t-1})-I\|_{2}\geq C\alpha\log 1/\alpha$ for some $C>0$ sufficiently large, it suffices to show

Lemma G.6 shows that the magnitude of the largest eigenvalue of $M(S_{t-1})-{\mathbf{I}}$ is positive since the magnitudes negative eigenvalues are all less than $c\alpha\log 1/\alpha$. So we have

where the first inequality follows from Lemma D.6, and the second inequality follows from our choice of large constant $C$. The next lemma regularity conditions for $\tau_{i}$’s for each iteration is satisfied.

If $n\gtrsim\frac{B^{2}d^{3/2}}{\varepsilon_{1}\alpha\log 1/\alpha}\log(1/\delta)$, then there exists a large constant $C>0$ such that, with probability $1-O(1/d)$, we have

Thus, by combining with Lemma D.5, we have

By our choice of sample complexity $n$, with probability $1-O(1/dB^{2})$, we have $\|\mu(S_{t-1})-\mu_{t}\|_{2}^{2}\lesssim\alpha\log 1/\alpha$, $v_{t}^{\top}\left(M(S_{t-1})-\mathbf{I}\right)v_{t}\gtrsim\|M(S_{t-1})-\mathbf{I}\|_{2}-\alpha\log 1/\alpha$ (Lemma D.6), and $\|M(S_{t-1})-\mathbf{I}\|_{2}\geq C\alpha\log 1/\alpha$ simultaneously hold before stopping.

We first consider the upper bound of the good points.

where the $(a)$ is implied by the fact that for any vector $x,y,z$, we have $(x-y)(x-y)^{\top}\preceq 2(x-z)(x-z)^{\top}+2(y-z)(y-z)^{\top}$, $(b)$ follows from Lemma G.7 and $c$ follows from our choice of large constant $C$.

Since $|S_{\rm bad}\cap{\cal T}_{2\alpha}|\leq\alpha n$, we know $|S_{\rm good}\cap{\cal T}_{2\alpha}|\geq\alpha n$, so we have for $i\notin{\cal T}_{2\alpha}$,

where $(a)$ follows from Lemma G.6, and $(b)$ follows from Lemma G.7, and $(c)$ follows from our choice of large constant $C$.

where the last inequality follows from Lemma G.6, which shows that the magnitude of the largest eigenvalue of $M(S_{t-1})-{\mathbf{I}}$ must be positive. ∎

Appendix E PRIME: efficient algorithm for private and robust mean estimation

We provide our main algorithms, Algorithm 9 and Algorithm 10, in Appendix E.1 and the corresponding proof in Appendix F. We provide our novel DPthreshold and its anlysis in Appendix E.2.

We define $S_{\rm good}$ as the original set of $n$ clean samples (as defined in Assumption 1 and 2) and $S_{\rm bad}$ as the set of corrupted samples that replace $\alpha n$ of the clean samples. The (rescaled) covariance is denoted by $M(S^{(s)})\triangleq(1/n)\sum_{i\in S^{(s)}}(x_{i}-\mu(S^{(s)}))(x_{i}-\mu(S^{(s)}))^{\top}$, where $\mu(S^{(s)})\triangleq(1/|S^{(s)}|)\sum_{i\in S^{(s)}}x_{i}$ denotes the mean.

E.2 Algorithm and analysis of DPthreshold

Algorithm DPthreshold($\mu,U,\alpha,\varepsilon,\delta,S$) running on a dataset $\{\tau_{i}=(x_{i}-\mu)^{\top}U(x_{i}-\mu)\}_{i\in S}$ is $(\varepsilon,\delta)$-DP. Define $\psi\triangleq\frac{1}{n}\sum_{i\in S}(\tau_{i}-1)$. If $\tau_{i}$’s satisfy

and $n\geq\widetilde{\Omega}\left(\frac{B^{2}d\sqrt{\log(1/\delta)}}{\varepsilon\alpha}\right)$, then DPthreshold outputs a threshold $\rho$ such that with probability $1-O(1/\log^{3}d)$,

E.3 Proof of Lemma E.1

1. Threshold $\rho$ sufficiently reduces the total score.

Let $\rho$ be the threshold picked by the algorithm. Let $\hat{\tau}_{i}$ denote the minimum value of the interval of the bin that $\tau_{i}$ belongs to. It holds that

2. Threshold $\rho$ removes more bad data points than good data points.

Define $C_{2}$ to be the threshold such that $\frac{1}{n}\sum_{\tau_{i}>C_{2}}(\tau_{i}-C_{2})=(2/3)\psi$. Suppose $2^{b}\leq C_{2}\leq 2^{b+1}$, $\frac{1}{n}\sum_{\hat{\tau}_{i}\geq 2^{b-1}}(\hat{\tau}_{i}-2^{b-1})\geq(1/3)\psi$ because $\forall\tau_{i}\geq C_{2}$, $(\hat{\tau}_{i}-2^{b-1})\geq\frac{1}{2}(\tau_{i}-C_{2})$. Trivially $C_{2}\geq 1$ due to the fact that $\frac{1}{n}\sum_{\tau_{i}\geq 1}\tau_{i}-1\geq\psi$. Then we have the threshold picked by the algorithm $\rho\geq 2^{b-1}$, which implies $\rho\geq\frac{1}{4}C_{2}$. Suppose $\rho<C_{2}$, since $\rho\geq\frac{1}{4}C_{2}$, we have

where (a) holds by Lemma E.3, and (b) holds since $\rho\leq C_{2}$. If $\rho\geq C_{2}$, the statement of the Lemma E.3 directly implies Equation (13).

Since $|S_{\rm good}\cap{\cal T}_{2\alpha}|\geq\alpha n$, it holds

Assuming that the conditions in Lemma E.2 holds, and for any $C$ such that

First we show an upper bound on $S_{\rm good}\cap{\cal T}_{2\alpha}$:

Then we show an lower bound on $S_{\rm bad}\cap{\cal T}_{2\alpha}$:

Combing the lower bound and the upper bound yields the desired statement ∎

Appendix F The analysis of PRIME and the proof of Theorem 6

Let $(\varepsilon_{0},\delta_{0})$ be the end-to-end target privacy guarantee. The ($0.01\varepsilon_{0},0.01\delta_{0}$)-DP guarantee of $q_{\rm range}$ follows from Lemma D.2. We are left to show that DPMMWfilter in Algorithm 10 satisfy $(0.99\varepsilon_{0},0.99\delta_{0})$-DP. To this end, we explicitly write out how many times we access the database and how much privacy is lost each time in an interactive version of DPMMWfilter in Algorithm 13, which performs the same operations as DPMMWfilter.

In order to apply Lemma G.13, we cap $\varepsilon$ at 0.9 in initializing $\varepsilon_{2}$. We call $q_{\rm spectral}$ and $q_{\rm size}$ $T_{1}$ times, each with $(\varepsilon_{1},\delta_{1})$ guarantee. In total this accounts for $(0.5\varepsilon,0.5\delta)$ privacy loss. The rest of the mechanisms are called $5T_{1}T_{2}$ times ($q_{\rm spectral}(\cdot)$ and $q_{\rm MMW}(\cdot)$ each call two DP mechanisms internally), each with $(\varepsilon_{2},\delta_{2})$ guarantee. In total this accounts for $(0.5\varepsilon,0.5\delta)$ privacy loss. Altogether, this is within the privacy budget of $(\varepsilon=0.99\varepsilon_{0},\delta=0.99\delta_{0})$.

This is a powerful tool for designing private mechanisms, as it guarantees that we can safely simulate the filtering process with privatized parameters and preserve the neighborhood of the dataset; if ${\cal D}_{n}\sim{\cal D}^{\prime}_{n}$ are neighboring (i.e., $d_{\Delta}({\cal D}_{n},{\cal D}_{n}^{\prime})\leq 1$) then so are the filtered pair $S({\cal D}_{n})$ and $S({\cal D}_{n}^{\prime})$ (i.e., $d_{\Delta}(S({\cal D}_{n}),S({\cal D}_{n}^{\prime}))\leq 1$). Note that in all the interactive mechanisms in Algorithm 12, the noise we need to add is proportional to the set sensitivity of Filter$(\cdot)$ defined as $\Delta_{\rm set}\triangleq\max_{{\cal D}_{n}\sim{\cal D}^{\prime}_{n}}d_{\Delta}(S({\cal D}_{n}),S({\cal D}_{n}^{\prime}))$. If the repeated application of the Filter$(\cdot)$ is not a contraction in $d_{\Delta}(\cdot,\cdot)$, this results in a sensitivity blow-up. Fortunately, the above lemma ensures contraction of the filtering, proving that $\Delta_{\rm set}=1$. Hence, it is sufficient for us to prove privacy for two neighboring filtered sets $S\sim S^{\prime}$ (as opposed to proving privacy for two neighboring original datasets before filtering ${\cal D}_{n}\sim{\cal D}_{n}^{\prime}$).

In $q_{\rm spectral}$, $\lambda$ satisfy $(\varepsilon,0)$-DP as the $L_{1}$ sensitivity is $\Delta_{1}=(1/n)B^{2}d$ (Definition 1.2) and we add ${\rm Lap}(\Delta_{1}/\varepsilon)$. The release of $\mu$ also satisfy $(\varepsilon,\delta)$-DP as the $L_{2}$ sensitivity is $\Delta_{2}=2B\sqrt{d}/n$, assuming $|S|\geq n/2$ as ensured by the stopping criteria, and we add ${\cal N}(0,\Delta_{2}(2\log(1.25/\delta))/\varepsilon)^{2}{\mathbf{I}})$. Note that in the outer loop call of $q_{\rm spectral}$, we only release $\mu$ once in the end, and hence we count $q_{\rm spectral}$ as one access. On the other hand, in the inner loop, we use both $\mu$ and $\lambda$ from $q_{\rm spectral}$ so we count it as two accesses.

In $q_{\rm MMW}$, $\Sigma$ is $(\varepsilon,\delta)$-DP as the $L_{2}$ sensitivity is $\Delta_{2}=B^{2}d/n$, and we add ${\cal N}(0,\Delta_{2}(2\log(1.25/\delta))/\varepsilon)^{2}{\mathbf{I}})$. $\psi$ is $(\varepsilon,0)$-DP as the $L_{1}$ sensitivity is $\Delta_{1}=2B^{2}d/n$ and we add ${\rm Lap}(\Delta_{1}/\varepsilon)$. This is made formal in the following theorem with a proof. in Appendix F.1.1. This algorithm is identical to the MOD-SULQ algorithm introduced in and analyzed in [18, Theorem 5], up to the choice of the noise variance. But a tighter analysis improves over the MOD-SULQ analysis from by a factor of $d$ in the variance of added Gaussian noise as noted in .

with $Z_{i,j}\sim{\cal N}(0,(\,(1/(n\varepsilon))\sqrt{2\log(1.25/\delta)}\,)^{2})$ for $i\geq j$ and $Z_{i,j}=Z_{j,i}$ for $i<j$.