Lower Bound of Locally Differentially Private Sparse Covariance Matrix Estimation

1 Introduction

Machine Learning and Statistical Estimation have made profound impacts in recent years to many applied domains such as social sciences, genomics, and medicine. A frequently encountered challenge in such applications is how to deal with the high dimensionality of the datasets, especially for those in genomics, educational and psychological research. A commonly adopted strategy is to assume that the underlying structure of the parameter space is sparse.

Another often encountered challenge is how to handle sensitive data, such as those in social science, biomedicine and genomics. A promising approach is to use some private mechanisms for the statistical inference and learning tasks. Differential Privacy (DP) and its distributed version, Local Differential Privacy (LDP) [Dwork et al., 2006], are widely-accepted models that provide provable protection against identification and are resilient to arbitrary auxiliary information that might be available to attackers. Since its introduction over a decade ago, a rich line of works are now available, which have made (local) differential privacy compelling privacy enhancing technologies for many organizations, such as Uber [Near, 2018], Google [Erlingsson et al., 2014], Apple [Tang et al., 2017].

<The research of this work was supported in part by NSF through grant CCF-1716400.

£Contact Author; Part of the work was done when Di Wang was visiting the Simons Institute of the Theory for Computing.

While differentially private high dimensional estimation is quite promising, such as sparse linear regression [Cai et al., 2019] and selection problem [Steinke and Ullman, 2017], estimating high dimensional datasets in a locally differentially private manner could be quite challenging for many problems, such as sparse linear regression [Wang and Xu, 2019b], sparse mean estimation [Duchi and Ruan, 2018] and selection problem [Ullman, 2018]. Fortunately, recent research has shown that the loss of some problems caused by the local differential privacy constraints can be quite small compared to their non-private counterparts. Examples of this phenomenon include high dimensional sparse PCA [Ge et al., 2018]. Recently, [Wang and Xu, 2019a] studied the locally differentially private high dimensional sparse covariance estimation problem and proposed an algorithm which achieves an upper bound of O. s2 log p n�2 / measured by the squared spectral norm, i.e., æ�priv * �<æ22 , where s is the row sparsity of the underlying covariance matrix, p is the dimensionality, and n is the sample size. With the above upper bound, a natural question is the follows.

Is the upper bound of O. s2 log p n�2 / in the LDP high dimensional sparse covariance estimation tight?

In this paper, we give an affirmative answer to the above question. Specifically, we have the following contributions.

1. We show that in the non-interactive local differnetial privacy model, the private minimax risk (in the metric of squared spectral norm) of high dimensional sparse covariance matrix estimation is lower bounded by �. s2 log p n�2 /. Moreover, we show that the same lower bound also holds, even if the metric is generalized from the squared spectral norm to the general squared lw norm for any w ¸ [1;�]. Combining these with previous upper bounds, it indicates that these lower bounds are tight.
2. To prove the above lower bounds, we propose a framework, called General Private Assouad Lemma, for lower bounding the private minimax risk in the noninteractive or sequential differential privacy model. Our lemma is a generalization of the private Assoud lemma in [Duchi et al., 2018], and can be viewed as a general method for locally differentially private matrix estimation problems. We believe that it has the potential to be

used in other matrix-related estimation problems.

2 RelatedWork

Recently, there are several papers studying the private covariance matrix estimation problem [Kamath et al., 2018; Joseph et al., 2018; Karwa and Vadhan, 2017; Gaboardi et al., 2018; Amin et al., 2018; Wang and Xu, 2019a]. For covariance matrix estimation in the central differential privacy model, [Karwa and Vadhan, 2017] considered the 1dimensional Gaussian distribution estimation with (un)known variance. [Kamath et al., 2018] studied the problem of privately learning a multivariate Gaussian and product distributions in the total variation distance and showed that it is privacy-free for these problems. [Amin et al., 2018] recently also investigated the low dimensional case of the problem in Frobenious norm and proposed an iterative eigenvector sampling method. The work that is the most related to ours is probably the one in [Wang and Xu, 2019a], where the authors studied the problem in the high dimensional sparse case and proposed a method based on the idea of thresholding the private empirical covariance matrix. A missing ingredient in all the above works is that no lower bound is given, which makes it difficult to tell how far their solutions are away from the optimal.

Covariance matrix estimation under local differential privacy has been studied in [Gaboardi et al., 2018; Joseph et al., 2018; Wang and Xu, 2019a]. Specifically, [Gaboardi et al., 2018; Joseph et al., 2018] comprehensively studied the 1-dimensional Gaussian distribution estimation and provided several lower bounds. However, none of these works can be extended to general distributions and to the high dimensional sparse case. For the high dimensional case of the problem, [Wang and Xu, 2019a] proposed a general method which achieves an upper bound of O. s2 log p n�2 / in the squared spectral norm. In this paper, we provide a lower bound which matches this upper bound.

Using information-theoretic techniques to prove lower bounds in the local differential privacy model has also been studied in many papers, such as [Duchi and Ruan, 2018; Duchi et al., 2018; 2013; Joseph et al., 2018; Duchi and Rogers, 2019]. [Duchi and Ruan, 2018; Duchi et al., 2018; 2013] proposed several general frameworks for bounding the private minimax risk, such as the private versions of Le Cam lemma, Fano lemma, and Assouad lemma. However, none of these methods can be applied to our problem since all the previous lemmas can only be used in the one-directional case (i.e., the underlying parameter is a vector), while it is a twodirectional case (i.e., the underlying parameter is a matrix) in our problem. Moreover, all of the previous methods need to obtain some upper bounds of some hard distribution instances under the total variation distance (or KL-divergence) while in our problem we use � 2 -divergence, which makes our method quite different from the previous ones. The method that is the most related to ours is the private Assouad lemma proposed in [Duchi et al., 2018] which can be seen as a special case of our general private Assoud lemma.

3 Preliminaries

In this section, we introduce some definitions that will be used throughout the paper. More details can be found in [Duchi et al., 2018].

Notation In this paper, we will always assume (except for Corollary 2) that �.x/ = x2 and �.�1; �2/ = æ�1 * �2æ2 is the spectral norm between two matrices �1 and �2.

3.1 Classical Minimax Risk

Since all of our lower bounds are in the form of private minimax risk, we first introduce the classical statistical minimax risk before discussing its locally differentially private version.

Let P be a class of distributions over a data universe X. For each distribution p ¸ P, there is a deterministic function �.p/ ¸ �, where � is the parameter space. Let � : � � � :› R+ be a semi-metric function on the space � and � : R+ › R+ be a non-decreasing function with �.0/ = 0. We further assume that ^Xi'ni=1 are n i.i.d observations drawn according to some distribution p ¸ P, and �� : X n › � be some estimator. Then the minimax risk in metric ��� is defined by the following saddle point problem:

where the supremum is taken over distributions p ¸ P and the infimum over all estimators ��.

3.2 Local Differential Privacy and Private Minimax Risk

Since we will consider the sequential interactive and noninteractive local models in this paper, we follow the definitions in [Duchi et al., 2013].

We assume that ^Zi'ni=1 are the private observations transformed from ^Xi'ni=1 through some privacy mechanisms. We say that the mechanism is sequentially interactive, when it has the following conditional independence structure:

for all j � i and i ¸ [n], where " means independent relation. The full conditional distribution can be specified in terms of conditionals Qi.Zi � Xi = xi;Z1:i = zi:i/. The full privacy mechanism can be specified by a collection Q = ^Qi'ni=1 .

When Zi is depending only on Xi, the mechanism is called non-interactive and in this case we have a simpler form for the conditional distributions Qi.Zi � Xi = xi/. We now define local differential privacy by restricting the conditional distribution Qi .

Definition 1 ([Duchi et al., 2013]). For a given privacy parameter � > 0, the random variable Zi is an � sequentially locally differentially private view of Xi if for all z1; z2;5; zi*1 and x; x¤ ¸ X we have the following for all the events S:

We say that the random variable Zi is an � non-interactively locally differentially private view of Xi if

We say that the privacy mechanism Q = ^Qi'ni=1 is �- sequentially (non-interactively) locally differentially private (LDP) if each Zi is a sequentially (non-interactively) locally differentially private view.

For a given privacy parameter � > 0, let Q� be the set of conditional distributions that have the �-LDP property. For a given set of samples ^Xi'ni=1 , let ^Zi'ni=1 be the set of observations produced by any distribution Q ¸ Q�. Then, our estimator will be based on ^Zi'ni=1 , that is, ��.Z1;5;Zn/. This yields a modified version of the minimax risk:

From the above definition, it is natural for us to seek the mechanism Q ¸ Q� that has the smallest value for the minimax risk. This allows us to define functions that characterize the optimal rate of estimation in terms of privacy parameter �.

Definition 2. Given a family of distributions �.P/ and a privacy parameter � > 0, the � sequential private minimax risk in the metric ��� is:

where Q� is the set of all � sequentially locally differentially private mechanisms. Moreover, the � non-interactive private minimax risk in the metric ��� is:

where Q� is the set of all � non-interactively locally differentially private mechanisms.

4 General Private Assouad Lemma

In this section we introduce our general framework for lower bounding. Before that, we first review the classical Assouad lemma [Tsybakov, 2008] and its two-directional generalization [Cai et al., 2012].

Assouad's method works with a hypercube V = ^*1; +1'r for some r ¸ N. It transforms an estimation problem into multiple hypothesis testing problems using the structure of the problem in an essential way. Let ^Pv'v¸V ¸ P be a family of distributions with its corresponding parameters ^�v'v¸V indexed by the hypercube. Similar to the standard reduction from estimation to testing, we consider the following random process. Let V be a random vector uniformly chosen from the hypercube ^*1; +1'r . After that, the samples X1;X2;5;Xn are drawn from the distribution Pv conditioned on V = v. For each j ¸ [r], we define the mixture of distributions

where P n v is the product distribution of X1;5;Xn. Then, Assouad lemma can be stated as follows.

Lemma 1 (Assouad Lemma). Under the conditions stated in the above paragraph,

where æ � æTV is the total variation distance, � = minH.v;v¤/g1;v;v¤¸V �.�.�v;�v¤ // 2H.v;v¤/ , and H.v; v¤ / is the hamming distance between � and �¤ , i.e., H.v; v¤ / = ‡rj=1 1^vj � v¤j '.

Instead of restricting to a hypercube V, the general Assouad lemma in [Cai et al., 2012] works with the Cartesian product of a hypercube and the r-th power of a finite set of vectors. Specifically, for a given r ¸ N and a finite set of p-dimensional vectors B ˇ Rp\^01�p', let V = ^*1; +1'r and � � Br . Define T = V � � = ^� = .v; �/ : v ¸ V and � ¸ �': This means that one can view an element � ¸ � as an r � p matrix with each row coming from set B, and V as a set of parameters with each row indicating whether a given row of � is present or not. Similar to Assouad lemma, we assume that there is a family of distributions in the class P, ^P�'�¸T indexed by T and its corresponding parameters ^��'�¸T .

Let D� = ���. For a given a ¸ ^*1; +1' and j ¸ [r], we let Ti;a = ^� : �i.�/ = a', where �i.�/ is the i-th coordinate of the first component of �. It is easy to see that �Ti;a� = 2r*1D�. We have the following mixture of distributions

Lemma 2 (General Assouad's Lemma [Cai et al., 2016]). Under the conditions stated in above paragraph, we have the following

where � satisfies

and �.�/ is the first component of �.

Now, we present the locally private version of Lemma 2. Suppose that we draw samples Z1; 5 ; Zn according to �-LDP channel Q.��X1:n/. Then, conditioned on V = �, the private sample is distributed according to the marginal distribution Mn � :

Specifically, when Q is non-interactive, we have Mn � = .� Q.��x/dP� .x//�n . Similarly to (3), we can define Mn j;a and Mj;a for a ¸ ^*1; +1' and j ¸ [r]. Thus, combining the above with Lemma 2, we have the following theorem:

Theorem 1. Under the conditions given in Lemma 2, the � private minimax risk satisfies:

For the sequential private minimax risk, we have the following general lower bound.

Theorem 2. Under the conditions given in Theorem 1 and further assuming that � ¸ .0; 12 ], the � sequential private minimax risk in the metric ��� satisfies

where B� is the 1-ball of supremum norm B� = ^� ¸ L�.X/ � æ�æ� f 1', and L�.X/ = ^f : X › R � æf æ� < �' is the space of uniformly bounded functions with the supremum norm æfæ� = supx �f .x/�.

Note that the lower bound in Theorem 2 reduces to the same one in the private Assouad lemma [Duchi et al., 2018] when � contains only one matrix which every row is non-zero. Thus, we call Theorem 1 as the General Private Assouad Lemma. Particularly, if we restrict our attention only to the non-interactive LDP mechanisms, we have the following theorem bounding the private minimax risk, which will be used to prove our lower bounds in this paper.

Theorem 3. Under the conditions given in Theorem 1 and further assuming that � ¸ .0; ln2 2 ], the � non-interactive private minimax risk in the metric ��� satisfies

where D�2.�æ�/ is the � 2 -divergence, that is, D�2.PæQ/ = � .dP*dQ/2 dQ for distributions P and Q.

Proof. By Theorem 1, we have

By the non-interactivity, we have Mn j;a = .� Q.��x/dPj;a/�n . Let Mj;a = � Q.��x/dPj;a. By Pinsker inequality, we have the following

where (8) is due to Pinsker inequality, (9) is by the relation between KL-divergence and � 2 -divergence Dkl .P æQ/ f log.1 + D�2.PæQ// f D�2.PæQ/ [Tsybakov, 2008], (10) is due to the non-interactivity, (12) is by Pinsker inequality and inequalities .e� *1/2 f 2�2 and e2� f 2. Next, we prove (11).

Lemma 3.

Proof. W.l.o.g, we can assume that the density function of Mj;a is mj;a.z/ = � q.z�x/dPj;a and q.��x/ is the density function of Q.��x/. By the definition, we have

where c� = min^2; e� ', (13) is by the definition of � 2 - divergence, (14) is by Lemma 3 in [Duchi et al., 2018] and (15) is due to the fact that � infx q.z�x/dz f 1.

The inequality in Lemma 3 is weaker than the one in Theorem 1 of [Duchi et al., 2018] in the sense that it becomes the later one if combining the inequality of æMj;+1*Mj;*1æT V f D� 2 .Mj ;+1æMj ;*1/.

Remark 1. We note that comparing to existing general lower bounding methods on the private minimax risk, such as [Duchi et al., 2018; Duchi and Ruan, 2018; Duchi and Rogers, 2019], Theorem 3 is quite different. Firstly, while all previous lower bounds depend only linearly on the sample size n, the lower bound in Theorem 3 depends exponentially on n. Secondly, due to the special structure of our indexing set T , Theorem 3 is more suitable for matrix estimation problems, while previous methods are more suitable for vector estimation problems. Thirdly, previous lower bounds are measured by (or derived from) the mutual information, the total variation distance, or the KL-divergence between the hard distribution instances, while in Theorem 3, the lower bound is measured by the � 2 - divergence between distributions. This indicates that although Theorem 3 is stronger than the previous ones, as it can be seen later in the sparse covariance estimation problem, it is easier to obtain a lower bound on the � 2 -divergence of the hard instances than other measurements. This is also the reason that existing methods cannot be applied to our problem.

From (7), we can see that, to obtain the lower bound, one needs to bound the terms of D�2 .Pj;+1æPj;*1/ for all j, which are quite complicated since they are mixture distributions. To simplify the task, we fix all the other terms and consider only the j-th term, which can be seen as an r � p matrix with all other rows fixed, except for the j-th one. Formally, for an element � ¸ T , we define the projection �A.�/ = .�i.�//i¸A for a set A � ^1; 25; r', and the set ^*j' = [r]\^j'. �A.�/ and �*i.�/.�i.�//i¸A can be defined similarly, where �i.�/ is the i-th coordinate of the second component of �. Denote by

�A the set �A = ^�A.�/ : � ¸ T'. For a ¸ ^+1; *1', b ¸ ^*1; +1'r*1 and c ¸ �*j � Br*1 , we let

and D�j .a;b;c/ = �T�j .a;b;c/�. Let � P n j;a;b;c denote the mixture distribution

and �Mn j;a;b;c be its corresponding marginal distribution. Similar to Theorem 3, we have the following corollary.

Corollary 1. Under the conditions given in Theorem 1 and further assuming that � ¸ .0; ln2 2 ], the � non-interactive private minimax risk in the metric ��� satisfies

where the average over �*j ; �*j is induced by the uniform distribution over T .

Proof. The key observation is that the distributions P n j;a can be represented by a linear combination of ^ � P n j;a;b;c 'b;c¸T*j , where the set T*j is

That is, P n j;a = ‡.b;c/¸T*j wb;c � P n j;a;b;c , where wb;c = D�j .a;b;c/ 2r*1D� (note that since D�j .a;b;c/ is independent of a, we omit it). Also, ‡.b;c/¸T*j wb;c = 1. Thus, P n j;a can be seen as an average over .b; c/. The same also holds for Mn j;a .

By the convexity of total variation norm and Lemma 3, we have

By a similar argument given in the proof of Theorem 3, we get

Thus, by the inequality Averageb;cæ �Mn j;+1;b;c * �Mn j;*1;b;c æTV /2 f Averageb;cæ �Mn j;+1;b;c * �Mn j;*1;b;c æ2TV , we have the proof.

5 Lower Bound of Private Sparse Covariance Estimation

We follow the settings in [Cai et al., 2012; Wang and Xu, 2019a]. Let X1; 5 ; Xn be random samples from a zero-mean p-variate distribution with covariance matrix � = .�ij /1fi;jfp. The goal of sparse covariance matrix estimation is to estimate the unknown matrix � based on samples ^X1;5;Xn', and the locally private version is to determine a locally differentially private estimator. In this paper, we focus on the high dimensional case, that is, c1n� f p f exp.c2n/ for some � > 1; c1; c2 > 0. We assume that the underlying covariance is sparse. That is, � ¸ G.s/ with

G.s/ = ^� = .�ij/1fi;jfp : æ�*j;jæ0 f s; ¯j ¸ [p]'; (18) where �*j;j is the j-th column of � with �j;j removed, i.e., a matrix in G.s/ has at most s-nonzero off-diagonal elements on each column.

Moreover, we assume that each Xi is sampled from a �-subGaussian distribution. That is, for all t > 0 and ævæ2 = 1,

which means that all the one-dimensional marginals of X have sub-Gaussian tails.

Additionally, in private matrix-related estimation problems, it is always assumed that the l2 norm of each Xi are bounded by 1 [Dwork et al., 2014; Ge et al., 2018; Wang et al., 2018; Wang and Xu, 2019a]. In this paper, we relax the bounded norm assumption in the following way; for the random vector X ¸ Rp , we assume that æXæ2 f 1 with probability at least 1 * e*�.p/ . This leads us to the following class of distributions P.�; s/.

Before showing the lower bound, we first describe our construction of the hard indexing set T with their distributions ^P�'�¸T instances, which is motivated by the ones in [Cai et al., 2012].

We first construct the parameter set, which is the same as in [Cai et al., 2012]. Let r = � p2 ª and B be the collection of all row vectors b = .vj /1fjfp such that vj = 0 for all 1 f j f p*r and vj = 0 or 1 for p*r+1 f j f p under the constraint that æbæ0 = k (where the value of k will be specified later). We can view each .b1; 5 ; br/ as an r � p matrix with the i-th row being bi.

Then, we define the set T and its corresponding distributions. Define � ˇ Br to be the set of all elements in Br such that each column is less than or equal to 2k. For each matrix � = .�1; �2;5; �r/ ¸ �, define a p � p matrix Am.�m/ by making the m-th row and column of Am.�m/ be �m and the rest of entries be 0.

Next, we construct the distributions. Let T = V ��. For each � = .v; �/, we define a matrix P� = N.0; �.�/ with the matrix �.�/ having the following form

where c > 0 is some constant to be specified later and �n;p;� = �t log p n�2 for some universal small enough constant �. We first choose c, � and k to make the Gaussian distribution N.0; �.�// contained in the class (20).

Lemma 4. Under the assumption of n g C s2 logp �2 , if let c f min^ �2 ; 1 10p ' and k = max^� s2 �*1; 0', then there is a �, which depends only on C, such that N.0; �.�// ¸ P.�; s/ for every � ¸ T , where T is the set defined in the above paragraph.

Proof. We first bound the term of æ�.�/æ2. Note that since �.�/ is symmetric, we have æ�.�/æ2 f æ�.�/æ1. By the construction of �.�/, we can see that the l1 norm of each column in �.�/ is less than 1 + 2k�n;p;� f 1 + s�t log p n�2 . Thus, we have æ�.�/æ2 f c + cs�t log p n�2 .

We need N.0; �.�// satisfying (19). By [Wellner and others, 2013], we know that it is sufficient to have æ�.�/æ2 f �. Let �.�/ = V T QV be the SVD decomposition and Q = diag.�1;5; �p/. Then, for X � N.0; �.�//, we have V X � N.0;Q/. Thus, æXæ22 = æVXæ22 f æ�.�/æ2Y , where Y is a � 2 p random variable. For the � 2 -distribution, we have the following concentration bound.

Lemma 5 ([Laurent and Massart, 2000]). If z � � 2 n , then

Thus, with probability at least 1*exp.*p/, we have Y f 5p. This means that, to ensure æXæ2 f 1, it is sufficient to have 5pæ�.�/æ2 f 1. Thus, we need that

Taking c = min^�_2; 1 10p ' and choosing a small enough � f øC 2 , we can get the proof.

In order to use Theorem 4, we need to bound the term � = minH.�.� /;�.� ¤ //>1;�.� /;�.� ¤ /¸V æ�.� /*�.� ¤ /æ22 2H.�.�/;�.�¤// , which is due to the following Lemma in [Cai et al., 2012].

Lemma 6. Under the conditions given in Lemma 4, we have � g .k�n;p;�/2 p :

The following key lemma gives a lower bound on the term Average�*j ;�*j .D�2. � Pj;+1;�*j ;�*j æ � Pj;*1;�*j ;�*j //n .

Lemma 7. Under the conditions on T , �.�/ and the conditions of given in Lemma 4, the following holds for every j ¸ [r], when � is sufficiently small and p is sufficiently large

Combining Lemmas 4, 6 and 7 with r = � p2 ª, by Corollary 1 we have the following lower bound theorem.

Theorem4. If � ¸ .0; ln2 2 ], n g C s2 logp �2 andp g c1n� for � > 1, then the � non-interactive private minimax risk in the metric of squared spectral norm satisfies the following inequality

For the upper bound, [Wang and Xu, 2019a] recently showed that if each æXiæ2 f 1 and ^Xi'ni=1 � P , where P ¸ P.s; �/, then by using a thresholding method on the perturbed empirical covariance matirx with some well-defined threshold, the output �� satisfies æ �� * �æ22 f O. s2 logp n�2 / with high probability. Combining this upper bound with Theorem 4, we can see that the bound �. s2 logp n�2 / is actually tight (i.e., optimal).

We note that for the non-private case, the optimal rate of minimax risk under the same measurement is �. s2 logp n / [Cai et al., 2012]. Thus, in this case, the impact of the local differential privacy is to change the number of efficient samples from n to n�2 . However, the collection of the considered distributions needs another assumption, which says that æXæ2 is bounded by 1 with high probability. This is not necessary in the non-private case [Cai et al., 2012], but needed for showing the upper bound.

Moreover, [Wang and Xu, 2019a] also show that there is an .�; �/ non-interactive LDP algorithm whose output �� satisfies æ �� * �æ2w f O. s2 log p n�2 / for every w ¸ [1;�] with high probability. One natural question is whether it is optimal. The following corollary provides an affirmative answer.

Corollary 2. Under the assumptions given in Theorem 4, for each w ¸ [1;�], the � non-interactive private minimax risk in the metric of squared lw norm satisfies the following

where the lw-norm of any matrix A is defined as æAæw = sup æAxæw æxæw .

6 Discussions

There are still some open problems. Firstly, both Theorem 3 and 4 are restricted to non-interactive LDP protocols. The first open question is whether they can be extended to the sequential LDP model. Secondly, from Theorem 3 we can see that the lower bound holds under the assumption of � ¸ .0; ln2 2 ]. Thus, the second open question is whether the range of � can be enlarged, or whether better result can be achieved when � is larger, such as those in [Ye and Barg, 2018]? The third open question is whether Theorem 2 and 3 can be used to other matrix-related estimation problems? We leave them for future research.