Year: 2020

Abstract:
Privacy-preserving data analysis becomes prevailing in recent years. It is a common sense in privacy literature that strict differential privacy can only be obtained by imposing additional randomness in the algorithm. In this paper, we study the problem of private sign recovery for sparse mean estimation and sparse linear regression in a distributed setup. By taking a coordinate-wise median among the reported local sign-vectors, which can be referred to as a median divide-and-conquer (Med-DC) approach, we can recover the signs of the true parameter with a provable consistency guarantee. Moreover, without adding any extra randomness to the algorithm, our Med-DC method can protect data privacy with high probability. Simulation studies are conducted to demonstrate the effectiveness of our proposed method.

heading: 1 INTRODUCTION
text: With the development of technology for data acquisition and storage, the modern dataset has a larger scale, more complex structure, and more practical considerations, which addresses new challenges for data analysis. In recent years, large quantities of sensitive data are collected by individuals and companies. While one wants to extract more accurate statistical information from the distributed dataset, we must also beware of the leakage of this sensitive personal information during the training process. This calls for the study of distributed learning under privacy constraints (Pathak et al., 2010; Hamm et al., 2016; Jayaraman et al., 2018).
In privacy literature, differential privacy, which was firstly proposed in Dwork et al. (2006), has been the most widely adopted definition of privacy tailored to statistical data analysis. It has achieved tremendous success in real-world applications. Denote the data universe to be X , for the dataset X = {Xi}ni=1 ∈ Xn where Xi’s are the data observations. The ( , δ)-differentially privacy can be defined as follows.
Definition 1. (Differential Privacy in Dwork et al. (2006)) A randomized algorithm A : Xn → Θ gives ( , δ)-differentially private if for any pair of adjacent datasets X ∈ Xn and X′ ∈ Xn, there always holds
P { A(X1:n) ∈ U } ≤ e · P { A(X′1:n) ∈ U } + δ, (1)
for every subset U ⊆ Θ.
Here two datasets X and X′ are adjacent if and only if the Hamming distance (Lei, 2011) of these two datasets of same size H(X,X′) = 1. As we can see, the quantities and δ measure the level of privacy loss. There are also several relaxations of differential privacy (see, e.g., Bun & Steinke (2016); Dwork & Rothblum (2016); Mironov (2017); Dong et al. (2019)) designed for the ease of analysis. However, in these definitions, the dataset X is always assumed to be fixed, and the probability in (1) only takes over the randomness of the algorithm A. Therefore, it is impossible to achieve strict differential privacy without adding auxiliary perturbations in the algorithm. On the other hand, the statistical performance of the output is inevitably deteriorated by the additional randomness. This lead to a large body of works discussing the tradeoff between accuracy and privacy (Wasserman & Zhou, 2010; Bassily et al., 2014; Bun et al., 2018; Duchi et al., 2018; Cai et al., 2019).
In this paper, we consider the private sign recovery problem in the distributed system. To be more precise, assume the parameter of interest is a sparse vector, which has many zeros in its entries.
The task is to identify the signs of the parameter from the observations stored in multiple machines while protecting each individual’s privacy. The sign recovery problem, as an extension of sparsity pattern recovery, has found its significance in a broad variety of contexts, including variable selection (Tibshirani, 1996; Miller, 2002), graphical models (Meinshausen & Bühlmann, 2006; Cai et al., 2011), compressed sensing (Candes & Tao, 2005; Donoho, 2006), and signal denoising (Chen et al., 2001). However, this problem is rarely considered in the privacy community.
To address the sign recovery problem, we propose the Median Divide-and-Conquer (Med-DC) method, a simple two-step procedure. Firstly, each local machine estimates the sparse parameter and sends the sign-vectors back to the server; Secondly, the server aggregates these sign-vectors using coordinate-wise median and output the final sign estimator. While mean based divide-andconquer (also referred to as Mean-DC) approaches have been widely analyzed in distributed learning literature (Mcdonald et al., 2009; Zhang et al., 2013; Lee et al., 2017; Battey et al., 2018), the median-based counterpart has not yet been well explored. It is well-known that naively averaging the local estimators behaves badly for nonlinear and penalized optimization problems. This is because averaging cannot reduce the bias in the local sub-problems. In particular, for the distributed Lasso problem, as mentioned in Lee et al. (2017), the estimation error of averaged local Lasso estimator is of the same order as that of local estimators. However, when only considering the sign recovery problem, we found that the Med-DC method perfectly fits the nature of the distributed private setup. (See Section 2.2 for more detailed discussions) For the sake of clarity, we only consider the sign recovery problem for sparse mean estimation and sparse linear regression, the two fundamental models in statistics.
The proposed Med-DC method has the following advantages:
• Consistent recovery. For both sparse mean estimation and sparse linear regression, the Med-DC method consistently recovers the signs of the true parameter with theoretical guarantees. Under some constraints, we can prove that our approach can identify signals larger thanC √ log n/N for some constant C > 0 (where N is the full sample size and n is the local sample size), which coincides with the minimal signal level in the single machine setting (all data stored in one machine). • Efficient communication. To recover the signs of the parameter of interest in the distributed setup, a naive approach is to estimate the parameter using existing private distributed estimation methods and take the signs of the estimators. However, these methods usually involve multi-round aggregation of gradient information or local estimators, which seems costly for the simple sign recovery problem. Instead, our approach only aggregates the vectors of signs (bits information) in one shot, which is much more communicationally efficient. •Weak privacy. By relaxing the differential privacy to high-probability sense, our deterministic Med-DC method can be proved to be weakly ‘private’. We also extend this concept to group privacy. To the best of our knowledge, this is the first deterministic algorithm that has a provable high-probability privacy guarantee. Moreover, as each machine only needs to transmit the vectors of signs, instead of the local estimators or gradient vectors, our proposed method also protects the privacy of each local machine, since gradient sharing can also result in privacy leakage (Zhu et al., 2019). •Wide applicability. We believe the Med-DC approach deserves more attention due to its excellent practical performance and ease of implementation. For example, it is promising to apply the Med-DC method to wider classes of models, (e.g. , generalized linear model, M -estimation, etc.) or hybridize this method with many sophisticated distributed algorithms like averaged de-biased estimator in Lee et al. (2017) and Communication-Efficient Accurate Statistical Estimator (CEASE) in Fan et al. (2019).
Notations. For every vector v = (v1, ..., vp)T , denote |v|2 = √∑p l=1 v 2 l , |v|1 = ∑p l=1 |vl|, and |v|∞ = max1≤l≤p |vl|. Moreover, we use supp(v) = {1 ≤ l ≤ p | vl 6= 0} as the support of the vector v, and v−l = (v1, . . . , vl−1, vl+1, . . . , vp)T. For every matrix A ∈ Rp1×p2 , define ‖A‖ = sup|v|2=1 |Av|2, ‖A‖∞ = max1≤l1≤p1,1≤l2≤p2 |Al1,l2 |, ‖A‖L∞ = sup|v|∞=1 |Av|∞ as various matrix norms, Λmax(A) and Λmin(A) as the largest and smallest eigenvalues ofA respectively. We will use I(·) as the indicator function and sgn(·) as the sign function. For two sequences an, bn, we say an bn when an = O(bn) and bn = O(an) hold at the same time. For simplicity, we denote Sp−1 and Bp as the unit sphere and unit ball in Rp centered at 0. For a sequence of vectors {vi}ni=1 ⊆ Rp, we denote med(·) as the coordinate-wise median. Lastly, the generic constants are assumed to be independent of m,n, and p.

heading: 2 PRIVATE SIGN RECOVERY OF MEAN VECTOR

heading: 2.1 MEDIAN BASED DIVIDE-AND-CONQUER
text: Let µ∗ = (µ∗1, . . . , µ ∗ p) T be the true parameter of interest. We assume the vector is sparse in the sense that many entries µ∗l are zero. There are N i.i.d. observations Xi’s satisfying E[Xi] = µ∗, and they are evenly stored in m different machines Hj (where 1 ≤ j ≤ m). Denote X = {X1, . . . ,XN} as the full dataset. For simplicity we assume N = mn so that each machine has equally n samples. Our task is to identify the signs of µ∗ on all coordinates (denoted as sgn(µ∗)) in this distributed setup while protecting the privacy of every elementXi on each machineHj . To recover the signs of the true mean vector µ∗ privately, the most direct way is to estimate the mean by some existing differentially private algorithms and take the signs of the estimator coordinatewisely. By post-processing property of differential privacy (Proposition 2.1 in Dwork & Roth (2014)), we know this sign recovery method is also differentially private. Private mean estimation is a fundamental problem in private statistical analysis and has been studied intensively (Dwork et al., 2006; Lei, 2011; Bassily et al., 2014; Cai et al., 2019). The standard approach is to project the data onto a known bounded domain, and then apply the noises according to the diameter of the feasible domain and the privacy level. However, this method requires input data or the true parameter lies in a known bounded domain, which seems unsatisfactory in practice. Moreover, since we only want to estimate the signs, which take value in the discrete set {−1, 0, 1}, it seems unnecessary to perturb the mean directly.
Indeed, to recover the signs of the true parameter, there is no need to obtain an accurate mean with all data. Instead, we propose a Median based Divide-and-Conquer (Med-DC) approach. To be more precise, we can estimate the signs on each local machine Hj , and aggregate these vectors of signs by taking median to produce a more accurate sign estimator.
To present our method more clearly, we define the following quantization function Qλ(·),
Qλ(x) = sgn {
sgn(x) · (|x| − λ)+︸ ︷︷ ︸ shrinkage operator
} = { sgn(x) if |x| > λ, 0 if |x| ≤ λ. (2)
Here λ is a thresholding parameter. When x is a vector, Qλ(x) performs the above operation coordinate-wisely. In particular, when λ = 0, the function Q0(·) acts the same as the sign function sgn(·). Then we present our method in Algorithm 1.
Algorithm 1 Median divide-and-conquer (Med-DC) for sparse mean estimator. Input: Dataset X = {X1, . . . ,XN} evenly divided into m local machines Hj (where j = 1, . . . ,m), the universal thresholding parameter λN .
1: for j = 1, . . . ,m do 2: The j-th machine Hj computes the local sample mean X̄j = n−1 ∑ i∈Hj Xi. Then Hj sendsQj = QλN (X̄j) to the server. 3: end for 4: The server takes coordinate-wise median
Q̂(X) = med(QλN (X̄j) | 1 ≤ j ≤ m), (3)
Output: The vector of signs Q̂(X).
The choice of thresholding parameter will be discussed after Theorem 1 in Section 2.3. Especially mention that there are some cases when the median is not uniquely determined. For example, it is possible that there are the same numbers of 0’s and 1’s, then the median can be arbitrary value in [0, 1]. To avoid ambiguity, we simply take Q̂l(X) = 0 (where l denotes the coordinate index) whenever the median Q̂l(X) is not unique.
Another important remark is that, the proposed sign recovery algorithm Q̂(·) is deterministic. More precisely, as there is no additional random perturbation in Algorithm 1, the output Q̂(X) is completely determined by the input dataset X. It is able to protect data privacy in a weaker sense.

heading: 2.2 INTUITION BEHIND MED-DC
text: Before presenting the theoretical results of our Med-DC method, we briefly illustrate the intuition behind it. The median mechanism among the collection of discrete values in {−1, 0, 1} can be equivalently regarded as a voting game. At each coordinate, we take the element which gets more than half of the votes, and we take it as 0 when there is no such element. The mechanism of the Med-DC method can be visualized in Figure 1.
Recovery Consistency. The key insight of the Med-DC method is that, according to Berry-Essen theorem, the distribution of sample means on local machines is close to normal distribution centered at the true parameter µ∗. Therefore, on each coordinate l, the local sample means {X̄1,l, . . . , X̄m,l} are approximately symmetrically distributed around µ∗l . Based on this observation, the sign recovery consistency of the median mechanism becomes clear: For µ∗l > λN (µ ∗ l < −λN ), it is likely to have at least m/2 elements larger than λN (smaller than −λN ), which makes the median of local signs more inclined to be 1 (−1). For µ∗l = 0, by the approximate symmetry of local sample means, the numbers of 1’s and −1’s are likely to be equal. Thus the median tends to be 0. Weak Privacy. Given the dataset X and the adjacent datasets X′, when applying Algorithm 1 to X′, there would be at most one element among the set of signs {QλN (X̄j)}mj=1 change. With high probability, the change of one element would not affect the median value of Q̂(X). This interpretation is conceptually coincident with the idea of differential privacy in Definition 1. However, this ‘privacy’ guarantee does not hold for all data. For instance, in one-dimensional case, it is possible that X produces (m/2) positives and m/2 negatives (Q̂(X) = 0), and the adjacent dataset X′ produces m/2 + 1 positives and m/2 − 1 negatives (Q̂(X′) = 1), which contradict with standard definition of differential privacy. However, by Proposition 1, we can show that the Med-DC method guarantees privacy in a weaker sense with probability tending to 1, which implies that the aforementioned unpleasant case only appears with a small probability.
Connection with Robust Statistics. Our Med-DC method has an intimate connection with the median-of-means (MOM) estimator, a robust mean estimator which has attracted considerable recent interests in statistics and machine learning communities (Nemirovsky & Yudin, 1983; Yin et al., 2018; Minsker, 2019; Lecué & Lerasle, 2020). To estimate the mean, the MOM estimator takes the median among the local sample means. Both the MOM estimator and our Med-DC method use the
symmetrization effect of the local average. As our task is to find the signs of µ∗, we only aggregate the signs of each local estimator.
Robust statistics studies the estimator that is not much influenced by a small portion of data, which is conceptually similar to differential privacy. Indeed, the connection between robustness and privacy has been pointed out in Dwork & Lei (2009); Smith (2011); Avella-Medina (2019); Brunel & AvellaMedina (2020). In particular, Brunel & Avella-Medina (2020) leverages the MOM estimator and “Propose-Test-Release” (PTR) framework in Dwork & Lei (2009) to develop private mean estimator without any boundedness assumptions on the data and parameter. It is worthwhile noting that, we can also combine the PTR-framework with our Med-DC approach to develop a strictly differentially private sign estimator.

heading: 2.3 THEORY OF MEAN VECTOR SIGN RECOVERY
text: To discuss the theoretical properties of our method, we introduce the distribution space P ofX
P(µ∗, C) = { P ∣∣∣EP[X] = µ∗, max 1≤l≤p EP [ |Xl − µ∗l |3 ] ≤ C } , (4)
where C > 0 is some constant. This is a rather weak condition on the distribution of X . At each coordinate, we assume Xl has a finite third-order moment, which is common in median-of-mean literature (Minsker, 2019). Then we have the sign consistency of the proposed estimator Q̂(X).
Theorem 1. (Sign consistency of Med-DC) Let N = mn i.i.d. random vectors {X1, . . . ,XN} sampled from P(µ∗, C) be evenly distributed in m subsets H1, . . . ,Hm. Moreover, there are sufficiently large constants C1, C2, γ0 > 0, such that
(a) The dimension p satisfies p = O(nγ0), and take λN = C1( √
log n/N + 1/n); (b) Denote S = supp(µ∗), then there is minl∈S |µ∗l | ≥ C2λN .
Then Q̂(X) defined in Algorithm 1 satisfies that, for some large γ1 depends on C1, C2, γ0, there is
P ( Q̂(X) = sgn(µ∗) ) ≥ 1− n−γ1 .
As we can see from assumptions (a) and (b), when m = O(n), the thresholding parameter λN can be chosen to be C1 √ log n/N , which means our algorithm can identify the signal above the order of
O( √
log n/N). This is coincident with the optimal signal-to-noise ratio in a single machine setting (all N data are stored in one machine). Moreover, we note that the assumptions in Theorem 1 does not really require the true parameter to be ‘sparse’ in the sense that s p. Instead, we only assume there is a fixed gap (at the level ofO( √ log n/N)) between zeros and those nonzero elements. In the following proposition, we show that our algorithm can protect data privacy with high probability.
Proposition 1. (Privacy of Med-DC) Under the same assumptions as Theorem 1, denote D(X) as the collection of datasets X′ adjacent to X, then for some large γ2 > 0, there is
P ( Q̂(X) = Q̂(X′), for all X′ ∈ D(X) ) ≥ 1− n−γ2 . (5)
It is worth noting that, the privacy guarantee formulated in equation (5) differs with the standard definition of differential privacy (see Definition 1) in several aspects. Firstly, as the algorithm Q̂(·) is deterministic, the randomness in (5) comes from the data generating mechanism. It implies that this algorithm preserves data privacy with probability tending to 1, and precludes some extreme cases, which may happen with a small probability. This is essentially different from the standard definition of differential privacy and its variants, which always assume the dataset is fixed, and the randomness comes from the algorithm itself. Secondly, combining Theorem 1 and Proposition 1, we know that with probability tending to 1, this algorithm recovers the true signs, and the modification of a single entry of X does not affect the output at all (0 privacy loss). Therefore, this method can be roughly regarded as a (0, 0)-differentially private algorithm.

heading: 3 PRIVATE SIGN RECOVERY OF LINEAR REGRESSION

heading: 3.1 MED-DC OF REGRESSION PARAMETER
text: Let (Xi, Yi) (where i = 1, . . . , N ) be i.i.d. observations from the model
Y = XTθ∗ + z, (6)
where θ∗ = (θ∗1 , . . . , θ ∗ p) T is the true sparse regression parameter, and z is the noise independent with the covariate X . Denote the full dataset as X = {(X1, Y1), . . . , (XN , YN )}, and X is evenly divided into m local machinesHj (where 1 ≤ j ≤ m). Similarly, we attempt to recovery the vector of signs sgn(θ∗) = (sgn(θ∗1), . . . , sgn(θ ∗ p)) T.
Sparse linear regression is an important topic in the statistical literature. The least absolute shrinkage and selection operator (Lasso), which was firstly introduced in Tibshirani (1996), has been one of the most popular approaches because of its benign theoretical guarantee and excellent empirical performance. Recently, a private iteratively hard thresholding pursuit algorithm was developed in Cai et al. (2019) to solve Lasso problem in the differential privacy framework. To deal with the private sign recovery problem in the distributed setup, a naive approach is to solve the private Lasso problem on each local machine and take the signs of the average of all local estimators. However, this method also requires the boundedness assumption on the covariates, and it is too complicated for sign recovery. More importantly, the average of the local Lasso estimators is likely to cause more non-zero elements because the coordinate will become non-zero as long as one of these local estimators is non-zero at this coordinate.
By leveraging the idea of Med-DC, we present Algorithm 2 for sign recovery of sparse regression.
Algorithm 2 Median divide-and-conquer for sparse linear regression (Med-DC Lasso) Input: Data on local machines {(Xi, Yi) | i ∈ Hj} for j = 1, . . . ,m, the universal regularization parameter λN .
1: for j = 1, . . . ,m do 2: The j-th partHj computes the local sample mean
θ̂j = argmin θ∈Rp
1
2n ∑ i∈Hj (Yi −XTi θ)2 + λN |θ|1. (7)
Then the j-th local machine sends Q0(θ̂j) to the server. 3: end for 4: The server takes coordinate-wise median Q̂(X) = med(Q0(θ̂j) | 1 ≤ j ≤ m).
Output: The vector of signs Q̂(X).
Similarly as Algorithm 1, every step of the Med-DC Lasso method is deterministic. Therefore, we can solve each local subproblem (7) efficiently by many well-developed algorithms like FISTA in Beck & Teboulle (2009), ADMM in Boyd et al. (2011), etc.

heading: 3.2 THEORY OF REGRESSION PARAMETER SIGN RECOVERY
text: For linear regression, we consider the following distribution space PX,Y (θ∗, η1, C1, η2, C2) = { P ∣∣∣ sup |v|2=1 EP { exp(η1|vTX|2) } ≤ C1,
z = Y −XTθ∗, z ⊥X,EP { exp(η2|z|2) } ≤ C2 } ,
(8)
where C1, C2, η1, η2 are some positive constants. This implies that both the covariate vectorX and the noise z are sub-Gaussian. Then we have the following result of sign recovery consistency.
Theorem 2. (Sign consistency of Med-DC Lasso) Let N = mn samples X = {(X1, Y1), . . . , (XN , YN )} from PX,Y (θ∗, η1, C1, η2, C2) be evenly distributed in m subsets
H1, . . . ,Hm. Moreover, there are some sufficient large constants C3, C4,∆0 > 0 such that (a) The dimension p is fixed, and take λN = C3( √ log n/N + log n/n);
(b) Denote S = supp(µ∗), the minimal signal satisfies minl∈S |µ∗l | ≥ C4λN ; (c) The covariance matrix Σ = EXXT is positive definite. Let Σ−1 = (ω1, . . . ,ωp), there is
max l∈Sc |ω−l|1 ωl,l ≤ 1−∆0.
Then Q̂(X) defined in Algorithm 2 satisfies that, for some large γ1 depends on C3, C4,∆0, there is P ( Q̂(X) = sgn(θ∗) ) ≥ 1− n−γ1 . From the assumption (b), whenm log n = O(n), the minimal signal has the order ofO( √
log n/N), which meets the “beta-min” condition (Wainwright, 2009) of standard Lasso problem for full sample case (all N samples stored in a single machine). Note that the regularization parameter λN is a universal constant among all local machines. By assumption (a), the regularization parameter satisfies λN √ log n/N , which is smaller than the standard setting O( √ log n/n) (Lee et al.,
2017). Therefore, the local estimators θ̂j is not very sparse because the regularization parameter λN is unable to annihilate the noises brought by the local data. However, by taking the median among the local signs, the noises are canceled out and the signals become detectable. Owing to the smaller scale, it helps to identify the smaller magnitude of signals. The assumption (c) implies that, for l ∈ Sc, the l-th row of the precision machine Σ−1 is dominated by the diagonal entry ωl,l. It can be regarded as a more strict irrepresentability condition (Zhao & Yu, 2006; Wainwright, 2009). Proposition 2. (Privacy of Med-DC Lasso) Under the same assumptions as Theorem 2, denote D(X) as the collection of datasets X′ adjacent to X, then for some large γ2 > 0, there is
P ( Q̂(X) = Q̂(X′), for all X′ ∈ D(X) ) ≥ 1− n−γ2 . (9)
Similar as (5), equation (9) is a weakened privacy guarantee, which can protect data privacy with high probability. In addition, follow the proofs of Proposition 1 and 2, our proposed methods also guarantee group privacy with high probability (Section 10.1 in Dwork & Roth (2014)). Corollary 1. (Group Privacy) Under the same assumptions as Theorem 2, denote Dk(X) as the collection of datasets X′ have at most k elements differing with X, then for some large γ3 > 0, then
P ( Q̂(X) = Q̂(X′), for all X′ ∈ Dk(X) ) ≥ 1− n−γ3 .

heading: 4 SIMULATION STUDY

heading: 4.1 RESULTS FOR SPARSE MEAN ESTIMATION
text: In the first experiments, we consider the sparse mean estimation problem, observations {X1, . . . ,XN} are sampled from the model
Xi = µ ∗ + zi,
where the noises zi’s are drawn from the multivariate normal distribution N (0, Ip). We fix the dimension p as 200. The parameter of interest is defined as
µ∗ = ( 1, 0.8, · · · , 0.2, 0,−0.2, · · · ,−0.8,−1,0Tp−11 )T, (10) which means the sparsity level s is fixed as 10. The data is divided into 100 local machines H1, . . .H100, each local sample size is n = 200. Therefore, the entire sample size isN = 200×100. For the choice of regularization parameter λN in each local machine, we first choose λ′N based on the dataset in the first local machine H1 by five-fold cross-validation. Moreover, motivated by the theoretical scale difference in Theorem 1, we further divide λn by √ m, namely, λN = λn/ √ m. We compare with the following three methods:
(a) Mean-DC: Replace the aggregator median in Med-DC by taking average; (b) CWZ: Perform the method proposed in Cai et al. (2019) on all samples in a single machine.
Same as Cai et al. (2019), we adopt the oracle T = 2 √
logN , s = 10, and ( , δ) = (0.5, 10/N1.1); (c) Pooled-Mean: Take average among all samples and take quantization function QλN (X̄).
Note that Mean-DC and CWZ need to transmit the local estimators to the server, which is more communication costly. The performance of sign recovery is measured by the following four criteria:
• Positive and Negative False Discovery Rate.
PFDR =
∑p l/∈S+ I{Q̂l(X) = 1}
max[ ∑p l=1 I{Q̂l(X) = 1}, 1] , NFDR =
∑p l/∈S− I{Q̂l(X) = −1}
max[ ∑p l=1 I{Q̂l(X) = −1}, 1] .
• Total False Discovery Rate and Power.
FDR =
∑p l/∈S I{Q̂l(X) 6= 0}
max[ ∑p l=1 I{Q̂l(X) 6= 0}, 1] , Power =
∑p l∈S I{Q̂l(X) 6= 0}
max[ ∑p l=1 I{Q̂l(X) 6= 0}, 1] .
From Table 1, our Med-DC approach clearly outperforms the non-private Mean-DC and private CWZ method. Comparing with the pooled-mean estimator, our method has higher power.

heading: 4.2 RESULTS FOR SPARSE LINEAR REGRESSION
text: In the second experiments, we consider the linear model defined in (6). Let the noises are i.i.d. from N (0, 1) and assume the i.i.d. covariate vectors XTi = (Xi,1, . . . , Xi,p) (i = 1, . . . , N ) are drawn from a multivariate normal distributionN (0,Σ). The covariance matrix Σ is a p×p Toeplitz matrix with its (i, j)-th entry Σij = 0.5|i−j|, where 1 ≤ i, j ≤ p. We fix the dimension p = 200. Moreover, we set the true coefficient θ∗ the same as µ∗ in (10). Similarly, we set m = 100, n = 200. For the choice of regularization parameter λN in each local machine, we first choose λ′N based on the dataset in the first local machineH1 by five-fold cross-validation. As suggested in classical literatures (Wainwright, 2009), motivated by the theoretical scale difference in Theorem 2, and further divide it by √ m. In addition to Mean-DC, we mainly compare with other two methods:
(d) CSL: Use the Communication-efficient Surrogate Likelihood (CSL) framework in Jordan et al. (2019) to obtain an estimator θ̂CSL for the true parameter and take the signs of it.
(e) Pooled-Lasso: Solve the Lasso problem on all data in a single machine and take the signs.
Note that all the above-mentioned methods are not private. Both the Mean-DC method and the CSL method require to transmit information of local parameters or multi-round gradients, which is more communication-costly than ours. In particular, we note that the CSL method includes an iterative refinement of the estimator. In our simulation study, we present the results of the five-step CSL method. For each experiment, we repeat 500 independent simulations and report the number of PFDR, NFDR, FDR, and power.
It can be observed from Table 2, while all these methods can select the true support set, the Med-DC Lasso method has apparently smaller false discovery rate than others.

heading: A TECHNICAL LEMMAS
text: Lemma 1. (Berry-Esseen Theorem, Theorem 9.1.3 in Chow & Teicher (2012)) If {Xi, i ≥ 1} are i.i.d. mean-zero random variables with E[X2i ] = σ2,E|Xi|3 < ∞. Then there exists a constant CB > 0 such that
sup −∞<x<∞ ∣∣∣∣∣P ( n∑ i=1 Xi < √ nσx ) − Φ(x) ∣∣∣∣∣ ≤ CB√n. Lemma 2. (Exponential Inequality, Lemma 1 in Cai & Liu (2011)) Let X1, ..., Xn be i.i.d. random variables with zero mean. Suppose that there exist some η > 0 and C > 0 such that E[X2i eη|Xi|] ≤ C. Then uniformly for 0 < x ≤ C and n ≥ 1, there is
P
{ 1
n n∑ i=1 Xi ≥ (η + η−1)x
} ≤ exp ( −nx 2
C
) .
Lemma 3. Let N (= mn) i.i.d. random variables X1, ..., XN evenly distributed in m subsets H1, ...,Hm. Suppose E[Xi] = 0,E[X2i ] = σ2,E|Xi|3 < ∞. Denote X̄j = ∑ i∈Hj Xi/n as the local sample mean onHj . For every γ > 1, denote
cγ = C̃
( 1
n +
k
m √ n +
√ γ log n
mn
) ,
where C̃ > 0 is sufficiently large enough. Then for every fixed non-negative constant k, there is
P  m∑ j=1 I ( X̄j < cγ ) ≤ m 2 + k + P  m∑ j=1 I ( X̄j > −cγ ) ≤ m 2 + k  = O(n−γ). (11) Proof. For every x > 0, there is
P  m∑ j=1 I ( X̄j < x ) ≤ m 2 + k  =P
 1m m∑ j=1 I ( X̄j < x ) − P ( X̄1 < x ) ≤ 1 2 + k m − P ( X̄1 < x ) ≤P
 1m m∑ j=1 I ( X̄j < x ) − P ( X̄1 < x ) ≤ 1 2 + k m + CB√ n − Φ (√ nx σ ) =P
 1m m∑ j=1 I ( X̄j < x ) − P ( X̄1 < x ) ≤ − √ Cγ log n m  , where the last line uses Berry-Esseen Theorem (Lemma 1), and x is given by
x = σ√ n Φ−1
( 1
2 + k m + CB√ n +
√ Cγ log n
m
) .
Applying Lemma 2 to the i.i.d. sequence I ( X̄j < x ) − P ( X̄1 < x ) , we have
P  1m m∑ j=1 I ( X̄j < x ) − P ( X̄1 < x ) ≤ − √ Cγ log n m  = O(n−γ), for some C large enough. Moreover, we have the following elementary facts∣∣Φ−1(x0)∣∣ = ∣∣Φ−1(x0)− Φ−1 (1/2) ∣∣ ≤ |x0 − 1/2| (Φ−1)′ (x0) ≤ |x0 − 1/2|
ψ {Φ−1(3/4)} ,
holds for any 1/4 ≤ x0 < 3/4. On the other hand, we know that 1/4 ≤ Φ( √ nx/σ) < 3/4 holds for m,n sufficiently large. Denote Cδ = 1/ψ{Φ−1(3/4)}, then there is
P  m∑ j=1 I ( X̄j < Cδσ√ n ( CB√ n + k m + √ Cγ log n m )) ≤ m 2  ≤P
 1m m∑ j=1 I ( X̄j < x ) − P ( X̄1 < x ) ≤ − √ Cγ log n m  ≤ n−γ . Therefore, if we choose C̃ ≥ max{CδCBσ,Cδ √ Cσ}, the bound of the first term in the left hand side of (11) is proved. By repeating the same procedure, we can prove the bound of the second term, which yields the desired result.
Lemma 4. Let X1, . . . ,Xn be i.i.d. random vectors sampled from the distribution in (8). Denote its covariance matrix as Σ, and the sample covariance matrix as Σ̂. Then for every γ > 1, there exists a constant C̃ > 0 such that
P (∥∥∥Σ−1Σ̂− I∥∥∥
∞ ≥ C̃
√ log n
n
) = O(n−γ).
Proof. Recall that the inverse covariance matrix is denoted as Σ−1 = (ω1, . . . ,ωp), and el as the l-th coordinate vector. Then the (l1, l2)-entry of the matrix Σ−1Σ̂− I is
(Σ−1Σ̂− I)l1,l2 = 1
n n∑ i=1 ωTl1Xi · e T l2Xi − δl1,l2 .
Since the dimension p is assumed to be bounded, and the covariance matrix is positive definite, there exist a constant ρ ∈ (0, 1) such that
ρ ≤ Λmin(Σ) ≤ Λmax(Σ) ≤ ρ−1.
Then we have max 1≤l≤p
|ωl|2 ≤ ∥∥Σ−1∥∥ ≤ ρ−1.
SinceX is sub-Gaussain in (8), we obtain
max 1≤l1,l2≤p
E { exp η1ρ ∣∣ωTl1Xi · eTl2Xi − δl1,l2∣∣}
≤eη1ρ · sup |v|2≤1
E { η1|vTX|2 } ≤ eη1ρC1.
Therefore, we can apply Lemma 2 to each coordinate and yield
P (∥∥∥Σ−1Σ̂− I∥∥∥
∞ ≥ C̃
√ log n
n ) ≤p2 max 1≤l1,l2≤p P (∣∣∣ 1 n n∑ i=1 ωTl1Xi · e T l2Xi − δl1,l2 ∣∣∣ ≥ C̃√ log n n
) =O(p2n−γ−2) = O(n−γ),
for some C̃ sufficiently large. Therefore, the lemma is proved.

heading: B PROOF OF MAIN RESULTS
text: Proof of Theorem 1. If we can show that
max 1≤l≤p
P ( Q̂l(X) 6= sgn(µ∗l ) ) = O(n−γ), (12)
where γ > 0 is large enough. Then this theorem is proved as follows 1− P ( Q̂(X) = sgn(µ∗) ) ≤p max 1≤l≤p P ( Q̂l(X) 6= sgn(µ∗l ) ) = O(pn−γ) = O(n−γ+γ0),
provided that γ > γ0. For the l-th coordinate, we firstly suppose that µ∗l = 0. Since Xi’s are sampled from the distribution (4), by Lemma 3 with k = 0, if
λN = C0
(√ log n
mn +
1
n
) ≥ cγ ,
we have P ( Q̂l(X) 6= sgn(µ∗l ) ) ≤P { m∑ j=1 I ( X̄j,l < λN ) ≤ m 2 } + P { m∑ j=1 I ( X̄j,l > −λN ) ≤ m 2 } = O(n−γ).
Next we assume µ∗l > 0. We use Lemma 3 again, if
µ∗l ≥ C1 (√ log n
mn +
1
n
) ≥ cγ + λN ,
then there is
P ( Q̂l(X) 6= sgn(µ∗l ) ) ≤ P { m∑ j=1 I ( X̄j,l > λN ) ≤ m 2 } ≤P { m∑ j=1 I ( X̄j,l − µ∗l > −cγ ) ≤ m 2 } = O(n−γ).
Lastly, when µ∗l < 0, the proof is the same as above. Therefore (12) is proved.
Proof of Proposition 1. For X′ ∈ D(X), denote the elements in X′ as X ′i (where 1 ≤ i ≤ N ), where
N∑ i=1 I(X ′i 6= Xi) = 1.
Moreover, since these data are stored in m different machinesH1, . . . ,Hm, we have
0 ≤ m∑ j=1 I(X̄ ′j 6= X̄j) ≤ 1. (13)
Noticing that P ( Q̂(X) 6= Q̂(X′), for all X′ ∈ D(X) ) ≤P ( Q̂(X′) 6= sgn(µ∗), for all X′ ∈ D(X); Q̂(X) = sgn(µ∗) ) + P ( Q̂(X) 6= sgn(µ∗)
) ≤P ( Q̂(X′) 6= sgn(µ∗), for all X′ ∈ D(X) ) +O(n−γ1).
Therefore, we only need to show that P ( Q̂(X′) 6= sgn(µ∗), for all X′ ∈ D(X) ) = O(n−γ2). (14)
For the l-th coordinate, we firstly suppose that µ∗l = 0. Then there is P ( Q̂l(X′) 6= 0, for all X′ ∈ D(X) ) ≤P { m∑ j=1 I ( X̄ ′j,l < λN ) ≤ m 2 , for all X′ ∈ D(X)
} + P
{ m∑ j=1 I ( X̄ ′j,l > −λN ) ≤ m 2 , for all X′ ∈ D(X) } ≤P { m∑ j=1 I ( X̄j,l < λN ) ≤ m 2 + 1 } + P { m∑ j=1 I ( X̄j,l > −λN ) ≤ m 2 + 1 } ,
where the last inequality uses (13). Using Lemma 3 with k = 1, with λN properly chosen, there is P { m∑ j=1 I ( X̄j,l < λN ) ≤ m 2 + 1 } + P { m∑ j=1 I ( X̄j,l > −λN ) ≤ m 2 + 1 } = O(n−γ),
for some γ > 0. Similarly, if µ∗l > 0, there is P ( Q̂l(X′) 6= 1, for all X′ ∈ D(X) ) ≤P { m∑ j=1 I ( X̄ ′j,l > λN ) ≤ m 2 , for all X′ ∈ D(X)
} ≤P { m∑ j=1 I ( X̄j,l > λN ) ≤ m 2 + 1 }
≤P { m∑ j=1 I ( X̄j,l − µ∗l > λN − µ∗l ) ≤ m 2 + 1 } = O(n−γ),
where the penultimate line uses (13) and the last line uses Lemma 3 with k = 1. The proof when µ∗l < 0 is similar, therefore
P ( Q̂(X′) 6= sgn(µ∗), for all X′ ∈ D(X) ) ≤pP ( Q̂l(X′) 6= sgn(µ∗l ), for all X′ ∈ D(X) ) = O(pn−γ) = O(n−γ2),
which proves (14). Therefore the proposition is proved.
Proof of Theorem 2. For each j ∈ {1, . . . ,m}, taking sub-gradient of (7) at θ̂j , we have that 1
n ∑ i∈Hj (Yi −XTi θ̂j)Xi + λNZj = 0,
where Zj is the sub-gradient satisfying |Zj |∞ ≤ 1. Rearranging the terms and multiplying Σ−1 on the both sides, we have
θ̂j − θ∗ = (I −Σ−1 1
n ∑ i∈Hj XiX T i )(θ̂j − θ ∗) + 1 n ∑ i∈Hj Σ−1Xizi + λNΣ −1Zj . (15)
Taking η̃ = min{η1ρ, η2}, since the noise and covariates are assumed to be sub-Gaussian in (8), for each coordinate l ∈ {1, . . . , p}, we have
max 1≤l≤p
E { exp η̃|ωlX · z| }
≤ max 1≤l≤p
E { exp (1
2 ηρ|ωlX|2 +
1 2 η2|z|2 )} ≤ max
1≤l≤p
[ E { exp ηρ|ωlX|2 } · E { exp η2|z|2 }]1/2 ≤ √ C1C2.
Therefore by Lemma 2, we know that there exists a constant C̃1 > 0 such that
max 1≤j≤m ∣∣∣ 1 n ∑ i∈Hj Σ−1Xizi ∣∣∣ ∞ ≤ C̃1 √ log n n , (16)
with probability larger than 1−O(n−γ). On the other hand, by the fact that |Zj |∞ ≤ 1, we have |λNΣ−1Zj |∞ ≤ λN ∥∥Σ−1∥∥
L∞ . (17)
Moreover, by Lemma 4, we know
max 1≤j≤m ∥∥∥I −Σ−1 1 n ∑ i∈Hj XiX T i ∥∥∥ L∞ = OP (√ log n n ) (18)
Substitute (16) (17) (18) into (15), we have
|θ̂j − θ∗|∞ ≤ 2λN ∥∥Σ−1∥∥
L∞ + 2C̃1
√ log n
n .
From (15), the l-th coordinate can be written in the following form
θ̂j,l − θ∗l = λNωl,lZj,l + λNωl,−lZj,−l + 1
n ∑ i∈Hj ωTl Xizi + oP ( log n n ) . (19)
It left to rehash the argument in the proof of Theorem 1. From Lemma 5 below we have that 1− P ( Q̂(X) = sgn(θ∗) ) ≤ p · max 1≤l≤p P ( Q̂l(X) 6= sgn(θ∗l ) ) = O(n−γ+1).
Therefore we proved Theorem 2.
Lemma 5. Assume the same assumptions in Theorem 2. For every 1 ≤ l ≤ p, we have P ( Q̂l(X) 6= sgn(θ∗l ) ) = O(n−γ),
for arbitrarily fixed γ > 1.
Proof. When θ∗l = 0, we know that
P ( Q̂l(X) 6= sgn(θ∗l ) ) ≤ P { m∑ j=1 I ( θ̂j,l ≤ 0 ) ≤ m 2 } + P { m∑ j=1 I ( θ̂j,l ≥ 0 ) ≤ m 2 } .
By symmetry of the formulation, it is enough to prove
P { m∑ j=1 I ( θ̂j,l > 0 ) ≥ m 2 } = O(n−γ). (20)
When θ̂j,l > 0, we know that Zj,l = 1 (see (19)). Moreover, by assumption (c), we have
λNωl,lZj,l + λNωl,−lZj,−l ≥ λNωl,l − λN |ωl,−l|1 ≥ ∆0λNωl,l.
Therefore from (19) we have that
P { m∑ j=1 I ( θ̂j,l > 0 ) ≥ m 2 } ≤ P { m∑ j=1 I ( 1 n ∑ i∈Hj ωTl Xizi ≤ 1 2 ∆0λNωl,l ) ≤ m 2 } .
Applying Lemma 3 with k = 0 to the i.i.d. random variables ωTl Xizi we can prove (20) by taking
λN = 2C̃1
∆0ωl,l
(√ log n mn + log n n ) , (21)
with C̃ sufficiently large. Repeat the argument for the other half, we can prove the case for θ∗l = 0.
When θ∗l > 0, again from equation (19), we have
θ̂j,l ≥ θ∗l + 1
n ∑ i∈Hj ωTl Xizi − ∥∥Σ−1∥∥ L∞ λN + oP ( log n n ) .
Therefore
P ( Q̂l(X) 6= sgn(θ∗l ) ) ≤ P { m∑ j=1 I ( θ̂j,l ≤ 0 ) ≥ m 2 } ≤P { m∑ j=1 I ( 1 n ∑ i∈Hj ωTl Xizi ≤ θ∗l − 2 ∥∥Σ−1∥∥ L∞ λN ) ≥ m 2 } .
Applying Lemma 3 we can show that P { m∑ j=1 I ( 1 n ∑ i∈Hj ωTl Xizi ≤ θ∗l − 2 ∥∥Σ−1∥∥ L∞ λN ) ≥ m 2 } = O(n−γ),
provided that
θ∗l − 2 ∥∥Σ−1∥∥
L∞ λN ≥ C̃2 (√ log n mn + log n n ) ,
with C̃2 sufficiently large. Combining with (21) we know θ∗l ≥ C̃3λN , for some C̃3 > 0. When θ∗l < 0, the prove is essentially the same as above, hence we omit it for brevity. Thus the lemma is proved.
Proof of Proposition 2. The proof is similar as that of Proposition 1. For X′ ∈ D(X), denote the elements in X′ as (X ′i, Y ′i ) (where 1 ≤ i ≤ N ), where
N∑ i=1 I ( (X ′i, Yi) 6= (Xi, Yi) ) = 1.
Since these data are stored in m machines, we denote θ̂ ′ j as the local estimator given by data {(X ′i, Y ′i ) | i ∈ Hj}, then there is
0 ≤ m∑ j=1 I ( θ̂ ′ j 6= θ̂j ) ≤ 1. (22)
Noticing that P ( Q̂(X) 6= Q̂(X′), for all X′ ∈ D(X) ) ≤P ( Q̂(X′) 6= sgn(θ∗), for all X′ ∈ D(X); Q̂(X) = sgn(θ∗) ) + P ( Q̂(X) 6= sgn(θ∗)
) ≤P ( Q̂(X′) 6= sgn(θ∗), for all X′ ∈ D(X) ) +O(n−γ1).
Therefore we only need to prove P ( Q̂(X′) 6= sgn(θ∗), for all X′ ∈ D(X) ) = O(n−γ2). (23)
When θ∗l = 0, we have P ( Q̂l(X′) 6= 0, for all X′ ∈ D(X) ) ≤P { m∑ j=1 I ( θ̂′j,l ≤ 0 ) ≤ m 2 , for all X′ ∈ D(X)
} + P
{ m∑ j=1 I ( θ̂′j,l ≥ 0 ) ≤ m 2 , for all X′ ∈ D(X) } ≤P { m∑ j=1 I ( θ̂j,l ≤ 0 ) ≤ m 2 + 1 } + P { m∑ j=1 I ( θ̂j,l ≥ 0 ) ≤ m 2 + 1 } ,
where the last line uses (22). Using the expansion (19) and rehash the proof in Lemma 5, we can show that
P { m∑ j=1 I ( θ̂j,l ≤ 0 ) ≤ m 2 + 1 } + P { m∑ j=1 I ( θ̂j,l ≥ 0 ) ≤ m 2 + 1 } = O(n−γ).
When θ∗l > 0, similarly we have that P ( Q̂l(X′) 6= 1, for all X′ ∈ D(X) ) ≤P { m∑ j=1 I ( θ̂′j,l ≤ 0 ) ≥ m 2 , for all X′ ∈ D(X)
} ≤P { m∑ j=1 I ( θ̂j,l ≤ 0 ) ≥ m 2 − 1 } = O(n−γ).
Similar argument can be applied for the case when θ∗l < 0, which concludes the proof of (23). Therefore, Proposition 2 is proved.

Review summaries:
The paper gives "almost private" algorithms for problem of sign recovery of mean vector and of linear regression. The techniques follow their general framework of Median DC, which is similar to the well-known median-of-means approach. They give theoretical guarantees for the same, along with empirical results comparing with known differentially private algorithms and their non-private counterparts.

The paper considers the sign recovery problem in a distributed setting with privacy constraints. The paper proposes an algorithm “median divide-and-conquer (Med-DC)” which takes the sign locally in each machine and then takes the median globally. The paper shows that in the sparse mean estimation setting, Med-DC is correct with high probability under some assumptions and Med-DC satisfies a weaker notion of differential privacy proposed by the paper. The paper then extends this algorithm to the sparse linear regression setting.