Privacy Induces Robustness: Information-Computation Gaps and Sparse Mean Estimation
Authors: Kristian Georgiev
Samuel B. Hopkins
Venue: NeurIPS 2022 Accept (2022)
Keywords: differential privacy
robustness
high-dimensional statistics
sparse mean estimation
sum-of-squares method
information-computation gaps
computational complexity of statistics
learning theory

Abstract: We establish a simple connection between robust and differentially-private algorithms: private mechanisms *which perform well with very high probability* are automatically robust in the sense that they retain accuracy even if a constant fraction of the samples they receive are adversarially corrupted. Since optimal mechanisms typically achieve these high success probabilities, our results imply that optimal private mechanisms for many basic statistics problems are robust. 

We investigate the consequences of this observation for both algorithms and computational complexity across different statistical problems. Assuming the Brennan-Bresler secret-leakage planted clique conjecture, we demonstrate a fundamental tradeoff between computational efficiency, privacy leakage, and success probability for sparse mean estimation. Private algorithms which match this tradeoff are not yet known -- we achieve that (up to polylogarithmic factors) in a polynomially-large range of parameters via the
Sum-of-Squares method.

To establish an information-computation gap for sparse mean estimation, we also design new (exponential-time) mechanisms using fewer samples than efficient algorithms must use. Finally, we give evidence for privacy-induced information-computation gaps for several other statistics and learning problems, including PAC learning parity functions and estimation of the mean of a multivariate Gaussian. 

Privacy Induces Robustness: Information-Computation Gaps and Sparse Mean Estimation
Kristian Georgiev MIT EECS Cambridge, MA 02139 krisgrgemit. edu
Samuel B. Hopkins MIT EECS Cambridge, MA 02139 samhop@mit edu
Abstract
We establish a simple connection between robust and differentialll--rivaan algo- rithms: private mechanisms which perform well with very high probability are automatically robust the sense that they retain accuracy even if constant fraction of the samples they receive are adversarially corrupted. Since optimal mechanisms typically achieve these high success probabilities, our results imply that optimal private mechanisms for many basic statistics problems are robust.
We investigate the consequences of this observation for both algorithms and com- putational complexity across different statistical problems. Assuming the Brennan- Bresler secret-leakage planted clique conjecture, we demonstrate a fundamental tradeoff between computational efficiency, privacy leakage, and success probability for sparse mean estimation. Private algorithms which match this tradeoff are not yet known we achieve that (up to polylogarithmic factors) a polynomially-Lar range of parameters via the Mimnoof-Suares method.
To establish an information-computatio gap for private sparse mean estimation, we also design new (exponential -imee) mechanisms using fewer samples than efficient algorithms must use. Finally, we give evidence for crivacy-induces information- computation gaps for several other statistics and learning problems, including PAC learning parity functions and estimation the mean multivariate Gaussian.
1 Introduction
Avoiding leakage of sensitive data and robustness to data corruption model misspecification often key goals for designers of statistical estimators. Both these properties admit mathematical formalizations, and great deal of recent work in (algorithmic) statistics has gone into designing and analyzing algorithms that satisfy them.
Differential privacy (DP) is the gold gold-standard formal definition of privacy for algorithms processing sensitive data [DMNS06]. DP requires that the distribution of outputs an algorithm (or "mecha- nism"" ) M is insensitive exchanging small number of individuals in its input dataset. It offers such strong guarantees against privacy leakage that in addition to its ongoing adoption in industry, the US Census Bureau employs DP to satisfy its legal mandate to protect privacy [AACM* 22).
The I-contamination model a stringent formalization of robustness against model misspecification. It generalizes the classical model of i.i.d. samples: dataset is cooorppted for some 17 > 0 if it is first drawn i.i.d, but then an fractiio of samples have been arbitrarily corrupted by a malicious adversary (who may look at the whole dataset) [Hub65, Tuk75, Hubl1]. 1]. An n-robuxt algorithm is one which maintains guarantees of accuracy when given cororrppe samples.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Both robustness and privacy demand that the output of some statistical method not "change too much" when one or few input samples are modified arbitrarily. This conceptual similarity has not gone unnoticed: [DI09] observe that "robust statistical estimators present an excellent starting point for differentially private estimators," " and recent works have even made good on this idea in high- dimensional settings, taking inspiration from robust statistics to design private mechanisms [LKKO21, HBK22J. However, a general account of which private algorithms can be made robust, or vice versa, remains an open problem. Here we take small step by tackling:
Question 1: When are private algorithms (also) robust?
While common wisdom holds that privacy and robustness are not formally comparable, we give meta-theerem Theorem 2.1 which quantifies the degree of robustness that private mechanisms exhibit: at high level, mechanisms satisfying quantitatively-stne strong versions of DP are automatically robust.
This connection between robustness and privacy gives us the tools to investigate a second basic question, concerning tradeoffs among computational resources, privacy, and statistical accuracy. Accuracy-privacy tradcoffs appear in even the most elementary statistical settings. For instance, estimating the mean of d-dimensional Gaussian to 6 error requires O(d/a") samples non- privately, but subject to e-DP" requires (roughly) O(d/a² + d/(ar)) samples [BKSW19], While important in their own right, these two-way tradeoffs are not the whole story. In numerous cases, even including the Gaussian mean estimation problem, computationally efficient algorithms which achieve the optimal privacy- accuracy tradeoffs are not known. This brings up the question:
Question 2: Does requiring differential privacy introduce computational barriers in statistics?
While computational barriers efficient private algorithms known in some settings [GHRU13, U1116, Bun20), these apply only to algorithms with worst-case accuracy guarantees - in statistical settings we are asking only for average-case accuracy guarantees (although privacy should still hold with respect to all possible datasets).
An archetypal problem for which computational barriers arise when estimators are required to satisfy criteria beyond accuracy is that of sparse mean estimation. The goal there is to estimate a k-sparse vector Il E Rd using independent samples from a distribution with mean μt. With no requirements on privacy or robustness, this can be accomplished with O(k log d) samples in polynomial time via simple thresholding-basee sample complexity and satisfy privacy and robustness (as we show in this paper), but in polynomial time (2k22) samples are required (under a variant of the planted clique conjecture) just to satisfy robustness [BB20]. Given the outlined connection between robustness and privacy, the existence of an information information-computatii computation gap for robust sparse mean estimation naturally leads to:
estimators. In exponential time, it is possible to retain O(k log d)
Question 3: How many samples do poly-time private algorithms for sparse mean estimation require?
1.1 Our Contributions
We make three main contributions: (a) a meta- theorem characterizing robustness of private mecha- nisms; (b) a case study of sparse mean estimation, including a computational lower bound arising from robustness, and new Sum-of- LooooSSuuresbbasee that lower bound in parameter regimes where no such algorithms were previously known; and (c) a collection of computational and anformmtiion-heorete lower bounds for private mechanisms, inherited from lower bounds for robust algorithms.
algorithm whose sample complexity matches
Robustness of Optimal Private Mechanisms Our first contribution a simple but useful observa- tion: mechanisms with strong group privacy guarantees are automatically robust! By "strong group privacy," we mean guarantees strong enough to retain privacy and accuracy when constant fraction of individuals in the dataset are exchanged with others. We capture this in Theorem 2.1.
In spite of its simplicity, robustness of strongly-rroup-privat mechanisms has significant con- sequences for simultancously robust and private mechanisms, a topic of much recent interest [KMV21, LKO21, LKKO21, UKRK22, CS22], because mechanisms with optimal privacy-accuracy tradeoff' often automatically satisfy strong group privacy.
"See Section 2 for formal definitions.

---

Table Algorithms for sparse mean estimation. In the input column, N signifies that the algorithm takes i.dd samples from N(u, I), and Σ < -- samples from a distribution with bounded covariance. The sample complexity column hides polylogarithmic factors in the ambient dimension d and a priori mean bound (in 6) R. In the auto-robust column we indicate whether our meta-theorem (Theorem 2.1) implies that the algorithm robust to corruptions of an r = 1/poly log(d, R) fraction of the samples.
Algorithm
Input
Runtime
Sample Complexity
Auto-robust
k+ (8))
(1/8 a²
Hypothesis Sel. [BKSW19]
N
exp
ab
k+/p
Subset Sel. [Theorem C.7]
Σ S I
exp
a+c * +log(1/8)
So5 [Theorem 1.2]
N
poly
a²g k2 log(1//)
Threshold [Theorem 4.1]
N
poly
x
a²e
1.1 log(1/$)
k log(1/9)
Peeling [CWZ21]
N
poly
R
x
Peeling is stated only for (e, 6)-DP [CWZ21]. We use (mildly) modified c-DP version, which we formally state in Appendix G.
The privacy guarantees needed for automatic robustness rely quantitatively-strong forms of differential privacy: either so-called pure DP, or approximate DP, but with the additive error parameter ō taken exponentially small, and high success probability. (By contrast, typical convention in the privacy literature is to take 0 only polynomially small in other parameters.) For this reason, we focus primarily mechanisms satisfying pure DP and achieving high success probability.
Sparse Mean Estimation Recall that in sparse mean estimation the goal is to estimate a k-sparse vector μ E Rd to f2-error a, succeeding with probability 1-B, using i.i.d. samples from distribution with mean μ.. We contribute (a) new exponential
E-DP mechanisms using Olk log d) samples, (b) evidence that poly-time DP algorithms with high success probabilities require i(k2) samples, and (c) new poly-time algorithms using Ö(k?) samples (in certain parameter regimes). One of these algorithms, using the SoS exponential mechanism of [HKM21], is our main technical contribution.
Information-theoreii bounds: First, as a baseline, we study sparse mean estimation without worrying about running time. We show that even subject to both privacy and robustness, O(k log d) samples suffice, with sample complexities differing in their dependence on a and on between the cases that the underlying distribution is assumed to be Gaussian versus allowing for heavy-tailed distributions (assuming only bounded covariance), as the case of non-sparse mean estimation. See the estimators Hypothesis Sel and Subset Sel in Table 1, and Appendix C for formal statements.
Next, we give evidence for a srivacy-sample--ee success probability tradeoff for efficient private algorithms: private algorithm for sparse mean estimation with high success probability will satisfy strong group privacy, and hence robustness, but efficient and robust algorithms for sparse mean estimation require (2k2) samples (assuming the planted clique conjecture).
Computational lower bound:
Corollary 1.1 (of Theorem 2.1 and [BB20], Theorem 3.1). Assume the secret-leakage planted clique conjecture [BB20]. For polynomially--elated n, k, and d, with k = o(Vd), B E (0, 1), and a, > O, assume B $ 2 2-eVi Let m(B,n, n, E) be the greatest value less than log(1/ (og()/))((En) in the set (n- U 11/(())) f E N 2 1}. Every polynomial-time e-DP algorithm which, for any k-sparse f E Rd with || s poly(d) can take n samples from N(u, I) and return P such that kmm²
|| - -uul S a with probability - B requires n 2 ac-ypoly log(d, e'a)
Pretending m (og(1 and ignoring logarithmic factors in d, 1, a the lower bound says n 2 1/3 samples are required by efficient e-DP algorithms for sparse mean estimation.
log(1/8)
This is the geometric mean of three terms:
and log(1/8) (twice). We conjecture that the max of log(1/8)
g2 a
these is actually lower bound: 2 12
3

---

Even if this stronger lower bound were true, existing efficient algorithms for sparse mean estimation would not match The state-of-the for sparse e-DP mean estimation using techniques in the literature is a modification (to achieve pure DP) of an algorithm by [CW721], whose sample complexity scales with k log(1 /B) (see Appendix G).
Efficient algorithms - SoS: Are there polynomial-ting algorithms which match the tradcoff' from Corollary 1.1, or the stronger conjectured one above? Our main algorithmic contribution is new algorithm for sparse mean estimation which matches the tradeoff' of Corollary 1.1 (up to polylog factors) under the conditions:
(1) a, E 2 1/poly log(d), (2) k² = log(1/8), and (3) k 2 d Of these conditions, (2) could be removed if the stronger conjectural lower bound above were true, while we believe that (1) and (3) are shortcomings of our algorithm, and might be removable. We are not aware of any previous efficient private algorithm which matches the above conjectured tradeoff for any simultaneously super-constant and lfg(1
Theorem 1.2. There exists C O such that for every E, R > O, , a E (0, 1), and large-enough
d, E N such that k d there is a polynomial-time E-DP algorithm SoS with the following guarantees. For every k-sparse il E Rd with || S R, given n-corrupted samples X1, X1: 1I,, with probability at least B. the algorithm outputs P R such that 1l all s
O (Vllg(Rd))CT) so long as n > (log(Rd))C. 1- (8))(1g) R
a-c
Our algorithm employs the Sum-of-Squares exponential mechanism invented by [HKM21] for a private mean estimation algorithm, but adapting this approach to the sparse setting requires overcoming several technical roadblocks (see Section 3 and Appendix D). Our approach hits a technical obstacle related to the volume of the d-dimensional &j ball when k & d044, and we leave as an open problem to match or approach the tradeoff in Corollary 1.1 for a wider range of parameters.
Linear-time coordinate selection: Finally, what can be accomplished with a "truly efficient" algorithm one which does not require solving large semidefinite programs as in the SoS exponential mecha- nism? The state-of of-thh-art private algorithm for sparse mean estimation, of [CWZ21], is a simple iterative ceardinate-selecttonn procedure. With a minor modification to achieve pure DP guarantee, that algorithm uses O (k log d) to estimate k-sparse mean vectors μ E with || s R, with probability 1 B. However, the (R(-) hides a linear, rather than logarithmic, dependence on R, which is very costly even for moderately-
values of R!
While it is now well understood how to obtain logarithmic-in- R sample complexity for non-sparse mean estimation, standard approaches introduce linear dependence on ambient dimension d. We improve over the algorithm of [CW721] while maintaining linear running time by designing a simple thresholding procedure for estimating the support of μ requiring number of samples which is independent of R. Once the support is known, the ambient dimension of the problem can be reduced from k. and a off-the-shelf private non-sparse mean estimation algorithm can be run. A formal statement is given in Section 4. We demonstrate with experiments on synthetic data (Section 3) that procedure Threshold, is substantially more accurate than that used by prior
the cordinate-selectiin state of the art [CWZ21].
By contrast to Sos, the linear-time algorithm Threshold has sample complexity that scales with k² log(1/B) rather than x² + log(1 1B)). While this difference might appear minor at first, it has significant consequences: the linear-time algorithm cannot match the computational lower bound in Corollary 1.1, and it does not have strong-enough privacy guarantees to be robust via Theorem 2.1. Note that our results do not preclude other tradeoffs between k and log(1/B). For instance, we leave it as an exciting open problem to design an efficient algorithm with sample complexity scaling with k log(1/B)
Cntemmation-Copptattinn Computation Gaps in Private Statisties A problem in private statistics has an rnformation-compptaae gap if the accuracy-privace tradeoffs achieved by optimal (exponential-timag mechanisms for that problem cannot be achieved by polynomial- algorithms. Our connection between privacy and robustness can be used to give evidence for several infornation--ompulatio gaps in private statistics beyond sparse mean estimation.
Information-
Gaussian mean estimation (Corollary B.2): Gaussian mean estimation, where the goal is to estimate μ Rd given i.i.d. samples from N(n I), arguably even simpler than sparse mean estimation. We give evidence for an information-cooppattio gap: polynomial-ting e-DP algorithms obtaining

---

accuracy a with probability at least 1 1-f B require ' 2 log(1/B) (log( 1 unless there exist robust polynomial-tin time algorithms for Gaussian mean estimation which would contradict known statistical query lower bounds [DKS17] this is a (og(1/a))/2200) factor gap.
samples,
Learning parities (Corollary B.3): We also consider one of the most fundamental supervised learning problems: privately PAC learning parity functions from labeled examples. For each S S [n]] we can define a parity function fs [=1]" - [+1} by fs(x) = sTis Xt. The goal is to take labeled examples (x, y) drawn from some distribution D and find a parity function fs such that Pf(x.y)-((fs(()) = y) = 1, assuming one exists. While polynomial-time private algorithms for learning parities are known [KLN' 11], we show, via Theorem 2.1 that the failure probabilities of any such algorithms must be larger than what can be achieved in exponential time, or else RP NP.
Information-Theoree Lower Bounds in Private Statistics Finally, we show that the connection robustness can provide coormatiionthhorree lower bounds for private mechanisms, As an example, we study private covariance testing (Corollary B. B.4), where the goal is to take samples from NO0, Σ) and detect whether = I E Rdxd or if || - Illr 2 y. Appealing to the lower bound of [DK21] for robust covariance testing, we give a lower bound for private covariance testing, showing that (2d²)) samples are required by private algorithms with high success probabilities, while (d)) suffice non-privately.
Formal statements for the results on Gaussian mean estimation, learning parities, and covariance testing can be found in Appendix B.
1.2 Related Work
Privacy and robustness. As mentioned in Section 1, there is a rich history of connections between DP and robustness, starting from the propose-test-relasee (PTR) framework of Dwork and Lei [DL09]. Building on top of PTR, a number of recent works tackle high-dimensional statisties problems by leveraging robust primitives [BGS+21, LKO21], themselves inspired by a recent revolution in high-dimensional robust statistics [DK19]. On the flip side, private algorithms for certain problems have been shown to "automatically" exhibit small amount of robustness [TS13, HKM21].
Sparse mean estimation. Without privacy or robustness requirements, is a folklore result that the truncated empirical mean achieves the iiformation-thoreticaalll optimal rate. In the approximate DP case, [TS13] show that the stability of LASSO can be leveraged for private support selection and private sparse regression via the sample-and-aggreg lower bounds for approximate DP (based on tracing attacks [HSR* [H])+ and computationally efficient algorithms that match those bounds with constant probability under additional assumptions on the too norm of the mean μ. In the presence of 1]- corruptions of the samples, [BDLS17] gives an Ô (I2 log(d)/17)) -smple algorithm matching SQ lower bounds from [DKS17].
framework [NRS07]. Cai, Wang, and
Zhang [CWZ21] show iiformatiinnthhoreee
Computational Roadblocks to Privucy. Several prior works investigate computational roadblocks to privacy arising from cryptographic considerations, e.g. [UI116. UV11]. The hard problem instances constructed in such works have a worst-case flavor. while we are interested in computational hardness for typical datasets/those drawn i.i.d. from underlying probability distribution.
Sum-of-Square Method. The SoS method for algorithm design in high-dimensional statistics has led to number recent of algorithmic advances see the survey [RSS18). [HKM21], which introduces the SoS exponential mechanism, most closely related, and provides the foundations for Theorem 1.2.
Lower bounds for private mechanisms There are multiple works leveraging group privacy to derive lower bounds for private algorithms, both for pure and approximate DP [HT10, Del2, SU15, 6S1 in nature, while we also provide computational hardness results.
They are all information-theoredt Additionally, to the best of our knowledge, there are no existing work relating lower bounds for privacy to ones for robustness.
2 Automatic Robustness Meta-Theorem and Private Robust Mechanisms
We formally define DP Appendix A. With this in hand, With this in hand, we are ready to state and prove meta- veeta-thcoremmoooo on automatic robustness of private algorithms.
5

---

O be an (ε, 8) pprivate Theorem 2.1 (Automatic Robustness Theoremm..... Let M : x map from datasets X' to outputs O. For every dataset X,,..., Xn. let Gx 0 be set of good outputs. Suppose that M(XI,.... Xn) E Gx with probability at least - B for some B = B(n). Then, for every n E N, on n-element datasets M is robust to adversarial corruption of any (faaffraction of inputs, where
log 1/B
log 1/6
7(1) = O min
En
En + log
meaning that for every XI,..., Xn and xi,..., ......,, X² differing only npn elements, M Gx with probability at least - -0(1)
...,,..................... .,,,,,,)),)))) E
Proof of Theorem 2.1. Consider nu intermediate datasets (XI,..., Xx) Xo.... X (X,,..., Xz), where a single coordinate X; is modified in passing from X, to X/+1. Let pj Pr(M(()) E G.......).. Then we have the following recurrence for (1 pj):
(1-p)) S ef (1 p1-1) + 8 for j 2 1, and (1 Pa) s B,
from which we obtain (1 - Ppn) s e=n + mnn). The conclusion follows.
An analogous statement for concentrated DP [BS16] is presented in Appendix H.
Theorem 2.1 can be applied broadly to show that optimal private mechanisms are automatically robust, frequently even with optimal dependence of the lost accuracy on the rate of corruption. This breadth is possible because, for many statistical problems, private mechanisms obtaining information-theon theoretically optimal privacy-accurace tradeoffs automatically have the strong group privacy guarantees needed to apply Theorem 2.1. This because strong group privacy for a mechanism M is implied by two other desirable properties of private mechanisms: (1) M satisfies pure DP (or, (e, DDD for small choices of ö), and (2) M produces accurate results with high probability over the randomness used internally by the mechanism. We give two examples of this phenomenon below.
On the success probabilities of private algorithms: Before turning to examples, we observe that Theorem 2.1 only gives robustness constant fraction of corrupted samples for private algorithms which have very high probability of succeeding to obtain 1j Q(11) requires f S 2 QQn). In most work on randomized algorithm design, the difference between succeeding with probability 2/3 versus 1 β for small can be treated as an afterthought, because algorithms can be repeated to amplify success probability. But this kind of naive repetition causes privacy leakage!
In spite of this, optimal private mechanisms in statistics often do succeed with high probability, using more sophisticated approaches than naive repetition: in fact, high success probability is generally implied by M's 's outputs having (asymptotically) optimal confidence intervals. Our work points to a need for algorithm designers to focus on the confidence intervals/success probabilities of private algorithms: the payoff is robustness for free.
On Black-Bol Robustification of Optimal Private Mechanisms: We observe that Theorem 2.1 can be used to automatically obtain robust and private mechanisms from private ones with high success probabilities. For instance, (1) Hypothesis selection: The private hypothesis selection procedure of [BKSW19], already proved robust against non-adaptive adversaries, is additionally robust to corruptions made by adaptive adversaries. (2) Affine-invarian mean estimation: [BGS+21, LKO21] study esttmmttti mechanisms which provide error guarantees in the Mahalanobis distance [| uill given samples from N N(1 Σ). [BGS+21] give private mechanism for this problem with high success probability, and [LKO21] give a simultaneously private and robust mechanism. In either case, because both mechanisms provide strong-enough privacy guarantees apply Theorem 2.1, robustness can be obtained in a black-box fashion knowing only the privacy guarantees.
From Theorem 2.1 to Lower Bounds for Private Statistics: As we discussed in Section 1.1, we use Theorem 2.1 to prove both computational and ieformmtionn-hhooeee bounds for private algorithms for sparse mean estimation (Corollary 1.1), non-sparse mean estimation, learning parities, and covariance testing. We prove Corollary 1.1 in the next section, and defer the remaining statements and proofs of lower bounds to the supplement.
sample-complexity lower

---

3 Sparse Private Mean Estimation: Techniques
In this section, we overview ideas which go into our results on sparse mean estimation, starting from the information-thcorrtie results, and moving on to computational barriers and polynomial-time algorithms.
Information-theoret bounds In the absence of computational considerations, the landscape for Gaussian sparse mean estimation can be understood via standard tools: packing-based lower bound, and a matching (exponential-tie time) mechanism can be constructed as a direct corollary of existing results in the literature on private hypothesis selection [BKSW19]. For completeness, we carry out those in Appendix C.
In the heavy-tailed case, assuming only that the samples X1, ....../ Xn are drawn from a distribution with k-sparse mean μ and with bounded covariance, one can no longer construct a small cover of the set of possible distributions; this precludes approach as general as hypothesis selection from directly applying. Instead, we design a mechanism which first selects a subset of k coordinates, then hands off non-sparse mean estimation mechanism run just on those coordinates.
To select the coordinates, we use the exponential mechanism. To define a score function, we take inspiration from recent ideas in high-dimensional statistics [LM19] using empirical quantiles of univariate projections of the samples. The key idea for coordinate selection is to restrict attention to projection in sparse directions. For samples XI, XI,.... Xn, we define the following score function on subsets of coordinates T S [d]:
Σ
S((Xi)isn T:L)= max
L),
DER [|
parametrized by a scalar threshold LT. Then we sample from the distribution Pr(T) exp(eS((X))isn, L). Since S has sensitivity A(S) = 1, the resulting mechanism satisfies E- DP. We show using standard concentration tools that if > O(k log(d)()) Iog(1/B)/(a2e)) then this mechanism identifies a subset T containing all but a of the fz-mass of μr, with probability at least 1-8. B. To do so, we choose the threshold L such that with high probability all "bad" subsets containing small portion of the &2 mass of ş have "low" score compared to "good" ones for which || ||||| finally, we use bucketing to control the variance of samples such that we can set L as close to zero as possible without allowing "bad" subsets to achieve high score.
We then delegate the mean estimation on the candidate set of coordinates to any information- theoretically optimal (non-sparse) mean estimation mechanism. For the matching lower bound, standard packing-basce based arguments suffice (see Proposition C. for a formal argument).
Computational barrier Now we turn to the landscape when we require polynomial Starting with barriers, we first show how get Corollary 1.1 from our meta-theorem.
Proof of Corollary I.I. First of all, since n 2 log(1/8)//2² there exists a value in in the given set. Now suppose polynomial-time private algorithm exists tolerating л S //m= poly log(d, I/E, 1/a)). By adjusting parameters B, to artificially weaken the guaran- tees as necessary, we may assume that m(f, E) = log(1/ (fs)/(enn......./ Now, Theorem 3.1 of [BB20] shows that no algorithm for sparse mean estimation under these parameters can tolerate n-fraction of adversarial corruptions with 12//²/ /aa 2 n, where 2 hides polylogarithmic factors. But from Theo- rem 2.1 our hypothesized private algorithm tolerates an r log( // (/n) fraction of adversarial corruptions, which is a contradiction.
Overview of SoS Algorithm for Sparse Mean Estimation (Theorem 1.2) We remain informal in this section and defer mathematical rigor to the supplement. For now, let a O(). A standard trick reduces from & < 1 to this case.
As with prior work on both private and robust mean estimation (e.g. [CFB19, HKM21J) our algorithm produces series of iterates xg, .1.....8 Xy for T O(log d), where xg is the origin, with the invariant
For sample X E Rdd let Xy to he the projection onto the basis vectors with indices the set S [d]. That is, it changes by most when any sample is exchanged for another.
7

---

that ||x; اll 1 0.9 ull. To accomplish this, given X/-1 with I| - xt-1ll > 1, and samples XI,..., ...,,, X, (H, I). we find unit vector v such that (v, fr xx-1) 2 0.9||=-xxe then we could take x2 x;-1 + Q -0]1l=x--11le.
Unlike prior works, for reasons we will see shortly, we also need the invariant that x, is k-sparse. So, we actually take x; to be x;-1 + -2 - xt-ille with all but the margest- k coordinates set to O; we show that this thresholding step cannot increase the distance şı by too much (Lemma D.4).
Picking a gradient in exponential time: To find such a gradient vector V, we use the SoS exponential mechanism [HKM21]] Let first see how we would pick a gradient vector using the (non-SoS) exponential mechanism, but allowing exponential running time. For a given dataset = XI,..., Xn. the goal is to find score function sx(v) E E which assigns each (2k)-sparse unit vector a score, such that for neighboring datasets X' we always have [sx(v) - 5xx(v) & 1 ("bounded differences"). Here choose 2k-sparse because μ X is itself 2k sparse. Then outputting a random ø, where each is chosen with probability x exp(esx(D)), gives an E-DP mechanism. The goal is that us with high scores are closer to μ X+-1-
good choice of score function turns out to be 5x(x) = Eiss (0 xt-1 2 -1xx----ul- O()) using standard concentration of measure one can show that as long as n > klog d. for v s.t. sx(v) 2 0.9n we will have (v, H - xt-1) 2 0.91| - xx-lll ("utility"") Furthermore, if one were to sample a uniformly random k-sparse unit vector, it would satisfy ( 0.9]|u - with probability d-O(k) (since μ - X,-1 2K-sparse). So, the distribution given by Pr(v) exp(esx(v)) puts 1 1-8 B probability on v with sx(x) 2 0.9n, so long as n > (k d + log(1//))/ since it "boosts" the probabilities of these high scoring vectors by a factor of exp( log k)) 2 d0(3)
Here we have crucially used the fact that X;-1, 1. and hence μ Xt-1, is sparse: otherwise, the gradient o we need to select would not be sparse, and we would need to use exponential mechanism to sample o from bigger set. This, in turn, would require us to draw more samples n. ensure that the score function is well-behaved for bigger set of vectors, because the probability of (o, - 2 0. - x1-1ll -1--|| for uniformly-random D would be < d
Of course, the major drawback of the above is that it is not clear how to sample from the necessary distribution of ps efficiently - in fact, doing so would violate the lower bound of Corollary 1.1. There is also a second drawback: to evaluate the score function given above, we would need to know ||I - x however, we are able to adapt the strategy of [HKM21] for this task to the sparse setting, re-using several of the ideas below.
From exponential to polynomial time with SoS exponential mechanism: The SoS exponential mechanism allows potentially sxponential-time instances of the exponential mechanism to be con- verted into polynomial time algorithms, so long as (a) the bounded-differencee and utility properties of the score function can be proved in certain restricted proof system (the SoS proof system), and (b) the set over which the exponential mechanism is run is convex.
Convexity: The 2k-sparse unit vectors- used by the above sxponential-time algorithm - do not form a convex set. A natural idea is to relax from the 2k-sparse vectors to the (scaled) & ball. This creates a substantial difficulty: the set (o : ||인||| s O (Vx) has much more volume near the origin than the set of 2k-sparse unit vectors. In particular, it is no longer true that (z, ---xx-)) 2 0.9]| x;-ill with probability d0O(k) for uniformly-random v; this probability will be exponentially small in d.
To fix this, we "fatten" the & ball: we use the exponential mechanism over the set C {o 3w s.t. ||l wil s 0.01, ||l||| < 1, 11 s o (VR)} While perhaps counterintuitive that adding vectors is helpful here, it is possible (Lemma E.5) to show roughly the following statement: over randomly-chosen v in this set, (-- 2 0- 2 -odd//RR). (004)) = d d
for k d0.4. To see this, note that all w with ||w --x=1 || < 0.01 are in C and have
--x;-1
(w, μ - x, .) 2 0.0]| - xt x(l and, using Sudakov minoration, can be covered by do(') bals of radius 1/Vk 0.01. So at least a d o(k))))
of the volume of C lies on such "good" ws. So, as long as n > (k2 log d + log( 1/p))/ and k 2 dd.4, the arguments we used for the exponential-time method will still work.
00VI-1/VE = =d o oxp(-
0.01
8

---

Utility and Bounded- Bounded-Differencee in SoS: Finally, we turn to (a), the need to capture the proof' of the and utility in the SoS proof system. Here we take "intuitively simple" as proxy for "expressible in SoS," deferring technical definitions to the supplement. The bounded-differene property for sum-of-threshold based score functions like sx above has a standard SoS proof [Hop20], so we won't It address it further here.
The concentration of measure arguments we referred to above establish utility are not captured by the SoS proof system! So we actually need to devise a new proof of utility for the score function sx- The key step is a proof that и > ()ogd)o())))2 + log(1/))) then with probability 1 1-B. for every unit
vector w with ||=|| vk, have Σisn 1((X; - μr, > 1) 0.1n. To see that this implies utility, note that if has Sx(v) 2 0.9n, then there exists some such that (v, X; Xx-1) 2 1| x -1- O(1) but (v, X; (d) O(1). Then (2 x (v, X; x₁-1) + (v, H X,) 1| x, 0(1).
By a standard bounded-diffeee differenceee argument, suffices to prove that E max Σisn 1((X; - u, w>) > 1) s 0.01n. Letting M Eisn( μ)( = by Cauchy- -chwwaz, the quantity on the left-hand side is at
0.01 vn (E max (M, ww 1) Splitting M Maing Moff-diag and applying Holder's inequality, (M, ww v Maiagl ||== [|3 + M| ||=||/ Il
where || Iloo is the entry-
wise foo norm. The important term here turns out to be the second one; it is possible to bound Mor-Mand ~o & (log d)0()) /nn for an overall bound of 0.01 3/4k (up to log factors), which gives the desired bound if n > 2.2. See Lemma E.3 and E.4 for the formal version of this argument.
4 Fast Algorithms and Experiments
In this section, describe practical algorithm Algorithm (Threshold in Table 1). We use standard DP tools to guarantee privacy and utility - the exponential mechanism [MT07] with sensitivity- score function in a coordinate-wise fashion, followed by black-box application of univariate mean estimator.
Algorithm The subroutine exp-mech refers the exponential mechanism [MT07], and KV-1D to the univariate sparse mean estimator of [KV17].
Input: (xilisns T, b, o². n: 0, selected
1: m; + $ Σ (i+1)
for j [[n/b]]
compute bucketed means
2: z; < Σ [n/b] 1((m)); 2 T) for [d].
coordinate-wise threshold
3: for k do
exp-mech (Zz)) 4: selected.inser((()
5:
6:
A KV-1D (((ma)))
univariate estimation
Output: mean estimate p
Theorem 4.1. Let XI,...,X,, Xn ~ N(H, o²). Algorithum is E-DP outputs an estimate fi s.t. I1
ulI2 with probability at least 1 B as long
2-22 (log dl log(1/B)) a²E
o log(2//B
Lk log(2k/B)
k klo((R)
x²
aE
E
support estimation
dense estimation bn l dimensions
(log + log(k/B)) k log(R)
Q
a²e
The proof is given in Appendix F. While the statement and proof are given for Gaussians, we only use the concentration properties of the Gaussian distribution; hence the proof automatically applies for sub-Gaussian distributions well.
Instead of the exponential mechanism, we could also use the peeling [DSZ18] algorithm, as is done for the lincar-in-R algorithm in [CWZ21].

---

4.1 Experimental details
Now we turn to empirically validating the performance of Algorithm To isolate the effects of each subroutine (support estimation and dense mean estimation), we plot (1) the performance of the corresponding support estimation steps alone (2) la error for both.
1.0
non-private
Cai-Wai-Zhang
0
Threshold (ours)
fraction loly in eninated
non-private Cai-Wai-Zhang
0.6
Threshold (ours)
crrer
0.2
0
priori estimate
priooii estimate
Figure I: Empirical evaluation of 0.5-DP algo- rithms (and a non-private baseline) for support estimation for 1500 samples from N(u, in ambient dimension d = 1000 with μ| = 20 (non-zero coordinates sampled uniformly from [-10, 10)) as function of R, the priori esti- mate of |||||2-
Figure 2: Empirical evaluation of Threshold
and the sparse mean estimation algorithm of [CWZ21] under e-DP with sults are shown for Gaussian data ,,, Xn N(u, 4- for k-sparse y in R for 20, d 1000, 1000. The & error of the estimates plotted against the priori mean estimate R. A non-privee non-private baseline is also presented to high- light the cost privacy.
0.5; re-
We address (1) in Fig. 1- we use the fraction (l)) mass of μ on the k coordinates the algorithms select as a metric of success, since it is well-suited for mean estimation. Fig. shows that (a) we significantly outperform the previous state of the as soon we introduce very mild uncertainty in the a priori estimate of ||l (b) our method does not introduce additional constant factors "hiding" in the asymptotics.
In Fig. we presented results for support estimation, in order to highlight the improvement coming from coordinate selection alone. In Fig. 2 we evaluate Algorithm 1 directly in terms of our metric of interest fz error.
As can be seen from Fig. 2, the performance of the sparse mean estimation algorithm of [CWZ21] degrades rapidly even for very mild levels uncertainty the range of the mean e.g. if we only know beforehand that the mean lies in the range [-20, 20], instead of the tight range |-10, 10). the fz error (expectedly) doubles when we use the [CWZ21] algorithm; in contrast, the performance of Algorithm 1 is effectively unchanged.
Finally, we highlight a weakness of Algorithm we gain the mild dependence on R at the cost of losing the ae + -like sub-Gaussian rate; instead we have heavy-tailed-style [ate -like rate. This comes with practical cost in scenarios where the standard deviation is much larger than the priori mean estimate R.
For all figures, we average results over 10 random seeds and report average results, together with 95% bootstrap confidence intervals. Code necessary to reproduce all experiments available For all experiments we use commodity hardware (CPU: Intel Core i7-9750H CPU @ 2.60GHz).
5
Acknowledgements
Work supported in part by the NSF grants CCF-1553428 and CNS-1815221. This material is based upon work supported by the Defense Advanced Research Projects Agency (DARPA) under Contract No. HR001 120C0015.
10

---

References
[AACM'22] John M Abowd, Robert Ashmead, Ryan Cumings-Menone Daniel Kifer, Philip Leclerc, Jeffrey Ocker, Michael Ratcliffe, and Pavel Zhuravlev. Geographic spines in the 2020 census disclosure avoidance system topdown algorithm. arXiv preprint MrXiv:2203.16654 2022. 1
[ADK x 19] Kareem Amin, Travis Dick, Alex Kulesza, Andres Munoz, and Sergei Vassilvitskii. Diffcrentially private covariance estimation. Advances in Neural Information Processing Systems, 32, 2019. 17
[AV19] Mehmet Eren Ahsen and Mathukumalli Vidyasagar. An approach to one-bit compressed sensing based on probably approximately correct learning theory. 2019.
19
[BB20] Matthew Brennan and Guy Bresler. Reducibility and statistical compuaatico gaps from secret leakage. Conference on Learning Theory, pages 648-847. PMLR, 2020.
3,
[BDLS17] Sivaraman Balakrishnan, Simon S Du, Jerry Li, and Aarti Singh. Computationally efficient robust sparse estimation in high dimensions. Conference on Learning Theory, pages 169-212. PMLR, 2017. 5
[BFR+00] Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D Smith, and Patrick White. Testing that distributions are close. In Proceedings s Annual Symposium on Foundations of Computer Science, pages 259 269. IEEE, 2000. 17
[BGS*21] Gavin Brown, Marco Gaboardi, Adam Smith, Jonathan Ullman, and Lydia Zakynthinou. Covariance- private mean estimation without private covariance estimation. Advances in Neural Information Processing Systems, 34, 2021. 5, 6
[BIPW10] Khanh Do Ba, Piotr Indyk, Eric Price, and David P Woodruff. Lower bounds for sparse recovery. In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms, pages 190--119. SIAM, 2010. 24
[BKSW19] Mark Bun, Gautam Kamath, Thomas Steinke, and Steven Z Wu. Private hypothesis selection. Advances in Neural Information Processing Systems, 32, 2019. 3, 6, 7, 16, 18, 20
[BS14] Boaz Barak and David Steurer. Sum-of-squares proofs and the quest toward optimal algorithms. arXiv preprint arXiv:1404.5236. 2014. 15
[BS16] Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Theory of Cryplography Conference, pages 635-658. Springer, 2016. 5, 6, 35
[Bun20] Mark Bun. A computational separation between private learning and online learning. Advances in Neural Information Processing Systems, 33:20732-20743, 2020. 2
[CFB19) Yeshwanth Cherapanamjeri, Nicolas Flammarion, and Peter L Bartlett. Fast mean estimation with sub-gaussian rates. In Conference Learning Theory, pages 786-806. PMLR, 2019.
[CM13] Tony Cai and Zongming Ma. Optimal hypothesis testing for high dimensional covariance matrices. Bernoulli, 19(5B):2359-23 -2888, 2013. 17
[CS22] Julien Chhor and Flore Sentenac. Robust estimation of discrete distributions under local differential privacy. arXiv preprint arXiv:2202.06822 2022.
[CWZ21] Tony Cai, Yichen Wang, and Linjun Zhang. The cost of privacy: Optimal rates of convergence for parameter estimation with differential privacy. The Annals of Statistics, 49(5):2825-288 2021. 3, 4, 5, 9, 10, 19, 34
[De12] Anindya De. Lower bounds in differential privacy. Theory of cryptography conference, pages 321-338. Springer, 2012. 5

---

[DK19] Ilas Diakonikolas and Daniel M Kane. Recent advances in algorithmic
nigh-dimensional robust statistics. arXiv preprint 1rXlv:1911.05911,0000 2019.
[DK21] Maas Diakonikolas and Daniel M Kane. The sample complexity of robust covariance testing. In Conference on Learning Theory, pages 1511-1521. PMLR,, 2021. 5, 17
[DKS17] Hias Diakonikolas, Daniel M Kane, and Alistair Stewart. Statistical query lower bounds for robust estimation of high-dimensional gaussians and gaussian mixtures, In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 73-84. IEEE, 2017. 5, 16
[DI009] Cynthia Dwork and Jing Lei. Differential privacy and robust statistics. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 371-380) 2009. 2,5
[DMNS06] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pages 265-284. Springer, 2006. 1, 15
[DMR18] Lue Devroye, Abbas Mehrabian, and Tommy Reddad. The total variation distance between high-dimensional gaussians. arXiv preprint arXiv: 2018. 19
[DSZ18] Cynthia Dwork, Weijie J Su, and Li Zhang. Differentially private false discovery rate control. arXiv preprint arXiv:1807. 00000000009..... 2018. 9
[GHRU13] Anupam Gupta, Moritz Hardt, Aaron Roth, and Jonathan Ullman. Privately releasing conjunctions and the statistical query barrier. SIAM Journal on Computing. 42(4):1494-1520 2013. 2
[Häs01] Johan Hästad. Some optimal inapproximability results. Journal of the ACM (JACM), 48(4):798-88) -55, 2001. 16, 17
[HBK22] Jamie Hayes, Borja Balle, and M Pawan Kumar. Learning to be adversarially robust and differentially private. arXiv preprint arXiv:2201.02266 022262, 2022. 2
[HKM21] Samuel B Hopkins, Gautam Kamath, and Mahbod Majid. Efficient mean estimation with pure differential privacy via -f-uuarrrss exponential mechanism. arXiv preprint arXiv:21 12981, 2021. 3, 4, 5, 7, 8, 15, 24, 27, 28, 29, 30, 31
[HLZ200 Sam Hopkins, Jerry Li, and Fred Zhang. Robust and heavy-tailed mean estimation made simple. via regret minimization. Advances in Neural Information Processing Systems, 1911192-11122,, 2020. 23
[Hop20] Samuel B Hopkins. Mean estimation with sub-gaussian rates in polynomial time. The Annals of Statistics, 48(2):1193-12133 2020. 9
[8] Nils Homer, Szaboles Szelinger. Margot Redman, David Duggan, Waibhav Tembe, Jill Muehling, John Pearson, Dietrich A Stephan, Stanley Nelson, and David W Craig. Resolving individuals contributing trace amounts of dna to highly complex mixtures using high-density snp genotyping microarrays. PLOS genetics, 4(8):e1000167, 2008.
[HT10] Moritz Hardt and Kunal Talwar. On the geometry of differential privacy. In Proceedings of the forty-second ACM symposium on Theory of computing, pages 705-714, 2010.
[Hub65] Peter J Huber. A robust version of the probability ratio test. The Annals of Mathematical Statistics, pages 1753-1758, 1965. 1
[Hubl1] Peter Huber. Robust statistics. In International encyclopedia of statistical science, pages 1248-1251. Springer, 2011. 1
[K] Shiva Prasad Kasiviswanathan, Homin K Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. What can we learn privately? SIAM Journal on Computing. 40(3):793-826, 2011. 5, 16
12

---

[KMV21] Pravesh K Kothari, Pasin Manurangsi, and Ameya Velingker. Private robust estimation by stabilizing convex relaxations. arXiv preprint arXiv:2112.03548, 2021.
[KSS94] Michael Kearns, Robert E Schapire, and Linda M Sellie. Toward efficient agnostic learning. Machine Learning. 17(2):115-141 1994.
[KSU20] Gautam Kamath, Vikrant Singhal, and Jonathan Ullman. Private mean estimation of heavy-tailed distributions. In Conference on Learning Theory, pages 2204 2235. PMLR, 2020. 24
[KV17] Vishesh Karwa and Salil Vadhan. Finite sample differentially private confidence intervals. arXiv preprint arXiv:/711.0333 2017. 9, 34
[LKKO21] Xiyang Liu, Weihao Kong, Sham Kakade, and Sewoong Oh. Robust and differentially private mean estimation. Advances in Neural Information Processing Systems, 34, 2021. 2
[LKO21] Xiyang Liu, Weihao Kong, and Sewoong Oh. Differential privacy and robust statistics in high dimensions. arXiv preprint arXiv:2111.06572 2021. 2, 6
[LM19] Gábor Lugosi and Shahar Mendelson. Sub-gaus bab-gaussian estimators of the mean of a random vector. The annals statistics, 47(2):783-794 2019. 22
[LT91] Michel Ledoux and Michel Talagrand. Probability in Banach Spaces: isoperimetry and processes, volume 23. Springer Science & Business Media, 1991. 33
[MT07] Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. 48th Annual IEEE Symposium Foundations of Computer Science (FOCS pages
103. IEEE, 2007. 9, 15, 20
[MV21] Oren Mangoubi and Nisheeth K Vishnoi. Sampling from log-concave distributions with infinity-distance guarantees and applications to differentially private optimization. arXiv preprint ar arXiv:2111.04089 2021. 31
[NRS07] Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. Smooth sensitivity and sampling in private data analysis. In Proceedings of the thirly-ninth annual ACM symposium on Theory of computing, pages 75-84, 2007. 5
[RSS18] Prasad Raghavendra, Tselil Schramm, and David Steurer. High dimensional estimation via sum-of-squares proofs. In Proceedings of the International Congress of Mathematicians: Rio de Janeiro 2018, pages 3389-3423. World Scientific, 2018. 5
[SU15] Thomas Steinke and Jonathan Ullman. Between pure and approximate differential privacy. arXiv preprint 1501:::5501.060 2015. 5
[TS13] Abhradeep Guha Thakurta and Adam Smith. Differentially private feature selection via stability arguments, and the robustness of the lasso. In Conference on Learning Theory, pages 819-850. PMIR, 2013.
[Tuk75] John W Tukey. Mathematics and the picturing of data. In Proceedings of the International Congress of Mathematicians, Vancouver, 1975, volume 2, pages 523-531, 1975.
[UKRK22] Dmitrii Usynin, Helena Klause, Daniel Rueckert, and Georgios Kaissis, Can collaborative learning be private, robust and scalable?, 2022. 2
[U1116] Jonathan Ullman. Answering n1)+ counting queries with differential privacy is hard. SIAM Journal on Computing, 45(2):473-496, 2016. 2,
[UV11] Jonathan Ullman and Salil Vadhan. Peps and the hardness of generating private synthetic data. In Theory of Cryptography Conference, pages 400-416. Springer, 2011.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A] We do envision any direct negative societal impacts of our work.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] Any omitted proofs can be found in the appendicies.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either the supplemental material or as URL)? [Yes] the supplement.
(b) Did you specify all the training details (c.g., data splits, hyperparameters, how they were chosen)? [Yes] In the supplement.
(c) Did you report error bars (e.g., with respect to the random seed after running experiments multiple times)? [Yes] Error bars are included for all figures in Section and the supplement
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] In the supplement.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either the supplemental material or as URL? [Yes]
A URL to codebase, together with implementation details needed to reproduce results, are given in the supplement
(d) Did you discuss whether and how consent was obtained from people whose data you're using/eurating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [Yes] All experiments done
synthetic data without relation to any individual's ''s private data.
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "wJTG1Q5wkbm", "reviewer": "Reviewer_4bHQ", "summary": "Summary\n\nThe paper studies the connection between robustness and privacy. The paper begins by observing that the group privacy implies robustness, and group privacy follows by the standard (eps)-pure privacy as long as the failure probability of the (eps,0)-pure DP mechanism is small. A corresponding argument for the (eps,delta)-approximate DP also holds as long as delta is exponentially small.\n\nThis observation/meta-theorem allows the paper to borrow both computational and/or information-theoretic lower bounds from recent advances in high-dimensional robust statistics. The paper then derives various results for important statistical problems of the following flavor:  Consider the task A, then there is no (eps,0)-pure DP algorithm for task A that succeeds with probability delta, unless it either takes n >> n_0(eps,delta) samples (which is much larger than the sample complexity), or it does not run in polynomial time (under widely believed conjectures).\n\nThe main focus of the paper is on the problem of (Gaussian) sparse mean estimation. From [DKS17,BB20] it is known that the efficient algorithms for robust (Gaussian) sparse mean estimation requires quadratically more samples than the sample complexity. Combining this with the proposed meta theorem, the paper derives computational lower bounds for (eps,0)-pure DP mechanism that succeeds with high probability.\n\nThe main technical result of the paper is an efficient algorithm for private sparse mean estimation that matches the given computational lower bounds in the regime k \\in [d^{0.4}, d^{0.5}]. The proposed algorithm is based on sum-of-squares and builds on the recent work of [HKM21]. ", "questions": " The computational lower bounds of this paper hold only for those private algorithms that admit an exponentially small failure probability. I understand that there might be problems that admit private and polynomial-time algorithms with optimal sample complexity in constant-failure-probability regime but not in exponential-failure-probability regime (as shown by the paper, sparse mean estimation). \nBut even if a problem was hard in the constant failure probability regime (if there is such a problem), the meta-theorem of the paper will not be applicable. Do the authors have any comments on this limitation of their framework? Are there any candidates for private estimation tasks that might be hard even in the constant failure probability regime?\n\n", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths \n\nI believe the paper makes important first steps in formalizing the connections between efficient algorithms for robustness and privacy. \n\nThe conceptual idea behind the meta theorem is simple and natural, which allows the paper to derive guarantees for many kinds of problems by borrowing results from algorithmic robust statistics.\n\nI liked the paper, and thus I recommend acceptance. \n\n# Weakness\n\n+ The polynomial time algorithm for private sparse mean estimation works in a restricted parameter of regime.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "rQ5vTohJIqP", "reviewer": "Reviewer_Wizm", "summary": "This paper initiates a study of how privacy, success probability and computation resources are trade-offed in DP sparse mean estimation problem. Firstly, the paper establishes a simple connection between robust and differentially-private algorithms: private mechanisms which perform well with very high probability are automatically robust in the sense that they retain accuracy even if a constant fraction of the samples they receive are adversarially corrupted. By this connection and assuming the Brennan Bresler secret-leakage planted clique conjecture, this paper has provided a lower bound for this problem given the computation constraints. Meanwhile, an efficient algorithm based on SOS is proposed in this work.", "questions": "1. line 221, $\\Omega$ should be $O$.\n2. line 306, $\\alpha <<1$.", "limitations": "NA", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The paper has revealed a connection between DP algorithms and robust algorithms. I think it is a simple but interesting observation which may lead to more information-theoretic bounds for both fields.\n2. The sparse mean estimation algorithm based on SOS seems to have made a sound algorithmic contribution to the community.\n\nWeakness:\n1. The constraints in the connection between DP and robustness is relatively stringent: it requires either the DP algorithm succeeding with a super high probability or the robust algorithm having theoretical guarantees for relatively low $\\eta$.\n2. The lower bound of sparse mean estimation depends on one conjecture, and meanwhile the upper bound only works for some range of parameters. There is still a non-trivial amount left before closing the gap for all parameter ranges.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "3mx5GBk-5hY", "reviewer": "Reviewer_5phx", "summary": "This paper works with differential privacy and a specific notion of robustness, namely the $\\eta$-contamination. The authors show that DP mechanisms can be robust as well, and characterize a trade-off between computational efficiency and privacy for sparse mean estimation. Furthermore, more efficient mechanisms are proposed.", "questions": "While I understand the goal of sparse mean estimation as described in line 58-60, could the authors elaborate what is the application of sparse mean estimation? If such an application is empirically verifiable, the authors should experiment on it.", "limitations": "The authors have adequately addressed the limitations.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is clearly organized and sound as far as I can tell. The problems are important to work with and the improvement (from Table 1) is significant in the sense of poly time and robustness.\n\nI think this paper is making a concrete contribution by proposing an actual mechanism that achieves the optimal tradeoff. However, my main concern is the motivation of the sparse mean estimation. See my questions below.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept