Median DC for Sign Recovery: Privacy can be Achieved by Deterministic Algorithms
Authors: Jiyuan Tu
Weidong Liu
Xiaojun Mao
Venue:  (2021)
Keywords: Median-of-means
divide-and-conquer
privacy
sign recovery

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.

Under review as a conference paper at ICLR 2021
MEDIAN DC FOR SIGN RECOVERY: PRIVACY CAN BE ACHIEVED BY DETERMINISTIC ALGORITTMSS
Anonymous authors Paper under double-blind review
ABSTRACT
Privacy-rreeevving data analysis becomes prevailing in recent years. It is com- mon sense privacy literature that strict differential privacy can only obtained by imposing additional randomness in the algorithm. In this paper, study the problem of private sign recovery for sparse mean estimation and sparse linear re- gression in distributed setup. By taking a coordinate- wise median among the re- ported local sign-vectors, which can be referred to as a median divide-and-come -nn-cuuurr (Med-DC) approach, we can recover the signs of the true parameter with prov- able 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.
INTRODUCTION
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 al. 2010 Hamm et al.) 2016 Jayaraman et al. (018)).
In privacy literature, differential privacy, which was firstly proposed in Dwork 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 be X, for the dataset X = {X {_, E X where X; 's are the data observations. The (c, 6) differrreetllll privacy can be defined as follows.
Definition 1. (Differential Privacy in Dwork et al. (2006)) A randomized algorithm A X" + θ gives (c. diffffeernttially private if for any pair of adjacent datasets X E X" and X' E X", there always holds
Pe| ((A(Xim)) E U} S e P(A(Z).)) EU}++ +
for every subset U C.
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 e and ò measure the level of privacy loss. There are also several relaxations of differential privacy (see, e.g., Bun Steinke (2016); [Doork & Rothblum (0016): Mironov| (2017); Dong et al. (2019) designed for the ease of analysis. However, in these definitions, the dataset is always assumed to fixed, and the probability in (I) only takes over the randomness of the algorithm A. Therefore, it is impossible to achieve strict differential privacy without adding auxiliary perturbations 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 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 sparse vector, which has many zeros in its entries.

---

Under review as a conference paper at ICLR 2021
The task is to identify the signs of the parameter from the observations stored in multiple machines while protecting each individual's '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 & Bühlmann, [0066] Caa et al.
2011). compressed sensing (Candes & Tao 2005 [Dnohoo] 2006), and signal denoising (Chen 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-wiss median and output the final sign estimator. While mean based divide-and- conquer (also referred to as Mean-DC) approaches have been widely analyzed in distributed learn- ing literature (Medonald et al. 2009; Zhang et al., 2013 Lee et al.) 2017 BBttty et al., 2018), the median-based counterpart has not yet been well explored. is 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, mentioned in Lee 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 recov- ery 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 than C n/N for some constant C' > 0 (where N is the full sample size and is the local sample size), which co- incides 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 re- covery 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- gigh-probability sense, our determin- istic 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 provable nigh-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 ex- cellent 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- le-biased esti- Efficient Accurate Statistical Estimator (CEASE) in mator in Lee et al. (2017) and Communication -atttiiicatioo--ffiinntt
Fan et al. (2019).
Notations. For every vector v = (V1, ..., TT, denote /u/2 = VL of 1/ |111
= Σl_ |ur). and |o/00 = maxisiso /1).. Moreover, we use supp(v) (151 S p UI + 0} as the support of the vector v, and -- (VI,.... 12-1, ................................ "² For every matrix A E Rp Xp2, define |||| s1P|1),=1 Av || = maxi5h Spa |A A|A = sup ==1 | as various matrix norms, Amax (A) and Amin as the largest and smallest eigenvalues of A respectively. We will use I(-) as the indicator function and s-n(-) as the sign function. For two sequences an, b,. we say a₂ x bn when a = O(b,,) and b, = O(a,) hold at the same time. For simplicity, we denote Sr-1 and BP as the unit sphere and unit ball in R centered at O. For sequence of vectors (r C RP, we denote med(.) as the coordinate-wise median. Lastly, the generic constants are assumed be independent of m, n, and p.
2

---

Under review as a conference paper at ICLR 2021
2 PRIVATE SIGN RECOVERY OF MEAN VECTOR
2.1 MEDIAN BASED DIVIDE-AND-CONQUEE
Let n² = (-i,-... 18)) be the true parameter of interest. We assume the vector is sparse in the sense that many entries oi zero. There are N i..d. observations X;'s satisfying E[X;] y², and they are evenly stored in m different machines Hj (where I I m). Denote X = (Xi, 1,...., ) the full dataset. For simplicity we assume N mm so that each machine has equally n samples, Our task is to identify the signs of Ju" on all coordinates (denoted as sgn(z²)) in this distributed setup while protecting the privacy of every element X, on each machine H.y.
To recover the signs of the true mean vector μe' privately, the most direct way is to estimate the mean by some existing differentially private algorithms and take the signs of the estimator coordinate- wisely. 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 estima- tion is fundamental problem in private statistical analysis and has been studied intensively (Dwork) et al. 2006: Lei 201 Bassily et al. 2014; Cai et al. 2019). The standard approach to project the data onto a known bounded domain, and then apply the noises according to the diameter of the fea- sible 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-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, propose Median based Divide-and-Conque (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 @x(-),
(sgn(x)) (x))
if [ac X,
2x (3) sgnn sgn(t) (1ar) - -))+
(
if a S A.
shrinkage operator
Here À is thresholding parameter. When is a vector, @x(x)) performs the above operation coordinate-wisely, In particular, when = 0, the function Qa(-) acts the same as the sign func- tion sgn(-). Then present our method in Algorithm
Algorithm Median divide-and and conquer (Med-DC) for sparse mcan estimator.
Input: Dataset X (X i...., X Nv) evenly divided into local machines H, (where j
1,..., m), the universal thresholding parameter Ax.
1: for j 1,.... do
2: The j-th machine H, computes the local sample mean X, n --IEiEn, X.. Then Hj
sends Q, Qx (X,) to the server.
3: end for
4: The server takes coordinate-wise median
(x) med (X₂) S S m),
Output: The vector signs (%).
The choice of thresholding parameter will be discussed after Theorem in Section 2.3 Especially mention that there are some cases when the median is not uniquely determined. For example, 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 (x) O (where I denotes the coordinate index) whenever the median Q)( 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 | the output Q(X) is com- pletely determined by the input dataset X. It is able protect data privacy in weaker sense.
3

---

Under review as a conference paper at ICLR 2021
Med-DC
H1
H2
Hm
Figure 1: This figure visualizes the mechanism the median divide-and-conquer (Med-DC) ap- proach. Denote S and S as the sets of positives, negatives, and zeros of the true parameter μ respectively. The black dots and white dots on each column represent the estimated positive and negative locations on each local machine.
2.2 INTUITION BEHIND MED-DC
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, 0, 1} can be cquivalently regarded as voting game. At each coordinate, we take the clement which gets more than half of the votes, and take it when there is such element. The mechanism of the Med-DC method can be visualized Figure I
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 the true parameter 14" Therefore, on each coordinate the local sample means (X1,)..... Xm.)) are approximately symmetrically distributed around μf Based on this observation, the sign recovery consistency the median mechanism becomes clear: For μt AN (1² -Ax). is likely have at least m elements larger than Av (smaller than ), which makes the median of local signs more inclined be (-1). For μr O, by the approximate symmetry of local sample means, the numbers of I'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 I Io X', there would be at most one element among the set of signs [QaN (X,) })]je change. With high prob-
ability, the change of one element would not affect the median value of (X).. This interpretation is conceptually coincident with the idea of differential privacy in Definition I 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(%) 0), and the adjacent dataset X' produces m/2 + positives and m/2 negatives (Q(X") 1). which contradict with standard definition of differential privacy. However, by Proposition
[ we can show that the Med-DC method guaran- tees privacy in 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 intimate connection with the median-of ofiian-oo-mmeee -eans (MOM) estimator, robust mean estimator which has attracted considerable recent interests in statistics and machine learning communities (Nemirovsky & Yudin 1983 Yin et al. 2018 Minsker 2019 Lecué & Lerasle, 2020). To estimate the mean, the MOM estimator takes the median among the local sample means. Both the MOM estimator and Med-DC method use the

---

Under review as a conference paper at ICLR 2021
symmetrization effect of the local average. As our task is to find the signs of ye", only aggregate the signs of each local estimator.
Robust statistics studies the estimator that is not much influenced by 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 3 (2011): Avella-Medina (20T9); (Bunel & Avella- Medima 2020). In particular, Brunel & Avella-Medine (2020) leverages the MOM estimator and Tesposs-Test-Releaaae
(PTR) framework Dwork & (2009) develop private mean estimator
without any boundedness assumptions on the data and parameter. It is worthwhile noting that, we can also combine the fra-framework with our Med-DC approach to develop strictly differentially private sign estimator.
2.3 THEORY OF MEAN VECTOR SIGN RECOVERY
To discuss the theoretical properties of our method, we introduce the distribution space P of
P(u,,) = P Rx X
14", max Ep [[x nfl S J
(4)
ISISP
where C' > 0 is some constant. This is rather weak condition on the distribution of X. At each coordinate, we assume X₁ has a finite third-order moment, which is common in median-ot oaa---f--maltt 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..dd random vectors 1X..... X sampled P(u", C") be evenly distributed in m subsets ; Hm. Moreover there are suffi- ciently large constants C1, C2 70 > 0, such that
(a) The dimension p satisfies p Onn)) ), and take AN = Ci(Vlogn/N + 1/m);
(b) Denote S = supp( then there mines |uî] 2 C2AN. Then Q(X) defined in Algoritim satisfies that, for some large 7/1 depends on C1, C2, To, there is
P P(((2) = sgu(p²)) 21-n
As we can see from assumptions (a) and (b), when m = O(n), the thresholding parameter An can be chosen to be C1 /log//, which means our algorithm can identify the signal above the order of O( O(Vlog 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 [ does not really require the true parameter to be 'sparse" in the sense that s < p. Instead, we only assume there a fixed gap (at the level of O 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 denote D(X) as the collection of datasets X! adjacent X, then for some large 722 O, there is
PP (0(x)=((x)) for all X' D(X)) 11-1
(5)
It is worth noting that, the privacy guarantee formulated in equation (5) differs with the standard definition of differential privacy (see Definition in several aspects. Firstly, as the algorithm Q-)) deterministic, the randomness (5) comes from the data generating mechanism. implies that this algorithm preserves data privacy with probability tending to 1, and precludes some extreme cases, which may happen with small probability. This 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 I and Proposition [] 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 (0, d)-iifferentially private algorithm.
5

---

Under review as a conference paper at ICLR 2021
3 PRIVATE SIGN RECOVERY OF LINEAR REGRESSION
3.1 MED-DC OF REGRESSION PARAMETER
Let (X,, Yi) (where ,,.., N) be i.i.d. observations from the model
= x +
(6)
where 0* = (Of,...,,0 0z)²² is the true sparse regression parameter, and = is the noise independent
with the covariate X. Denote the full dataset as = {(X,, V.),..., (X Yv)], and X is evenly divided into m local machines H, (where j S m). Similarly, attempt to recovery the vector ..... of signs sgn(@) (*) = sggn(()).....s(((())) sgn((;)))
Sparse linear regression an important topic in the statistical literature. The least absolute shrinkage and selection operator (Lasso), which was firstly introduced in [Tibsiirani (1996), has been 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 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 Med-DC, we present Algorithm 2 for sign recovery of sparse regression.
Algorithm Median divide-and and-cuquer for sparse linear regression (Med-DC Lasso)
Input: Data on local machines {(X,, Y.) H₂} for 1,..., m, the universal regularization parameter Ay.
I: for j = l...., m do
2: The j-th part H, computes the local sample mean
0,
argmmin
1
Σ (Y- - XT-xT002 Ax10
OER"
2n
ieH;
Then the j-th local machine sends 2o(0,) to the server.
3: end for
4: The server takes coordinate- wise median (x) = med Qo 11 S m))
Output: The vector signs (XX..
Similarly as Algorithm I every step of the Med-DC Lasso method is deterministic. Therefore, we solve each local subproblem efficiently by many well-developed algorithms like FISTA in Beck & Teboulle 2009). ADMM in Boyd et al. (201T). etc.
3.2 THEORY OF REGRESSION PARAMETER SIGN RECOVERY
For linear regression, we consider the following distribution space
P0, Mh, 12, C2) = { sup 1/2-1
Ep exp(m TT [ < Ct.
(8)
X = , 1 x, Er exp(1a|2|3)) s c.).
where Cı, C2, M1, 1/2 are some positive constants. This implies that both the covariate vector X and the noise 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
((X1, 1, Vi), .i), (X N, YN)) from P (0" m, Cr, 12, C2) be evenly distributed in m subsets

---

Under review as a conference paper at ICLR 2021
H1..... ,mm, Moreover, there are some sufficient large constants C3, C2. Do such that
(a) The dimension p is fixed, and take Ax Cs(vlog n/N llg n/n);
(b) Denote = supp( }. the minimal signal satisfies minyes |41| 2 CaANi
(c) The covariance mairix E = EXx" is positive definite. Lei Σ (W1...., wp) there is
W-1l1
max
11- Do.
LES"
WI,
Then Q(X) defined in Algorithm
2 satisfies that, for some large " depends on C3. Ca, Do, there is IP ((((()) = -gn(("))
21-n
From the assumption (b), when log On),, the minimal signal has the order of O( ( log n/ N), which meets the "beta-min" condition (Wainwright 2009) of standard I Lasso problem for full sample case (all N samples stored in single machine). Note that the regularization parameter AN is a universal constant among all local machines. By assumption (a), the regularization parameter satisfies Ay x Vlog n/N, which is smaller than the standard setting Olooog n/n) (Lee et al,, 2017). Therefore, the local estimators 0, is not very sparse because the regularization parameter An 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 I E St, the 1-th row of the precision machine Σ-1 is dominated by the diagonal entry w1,1- can be regarded as 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 X. then for some large 7/2 there is
PP ( ((x))=(XX)) for all X E (D(X)) 11-n
(9)
Similar as (5), equation (9) 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 Theorem [ denote (xx( the collection of datasets X! have at most elements differing with X, then for some large 7/3 > 0, then
P2 (()))) (xx'),)))))))))))))) for all X' &Dx(X)) 2 21-1 73
4 SIMULATION STUDY
4.1 RESULTS FOR SPARSE MEAN ESTIMATION
In the first experiments, we consider the sparse mean estimation problem, observations (X....,XN
X are sampled from the model
X; +
where the noises z, 's are drawn from the multivariate normal distribution N( Ip). We fix the dimension p as 200. The parameter of interest defined as
(1,0.8, .... 0, -0.2.
0.8, -,,
(10)
which means the sparsity level & fixed as 10. The data divided into 100 local machines HI.... 1100 each local sample size is n 200. Therefore, the entire sample size is N 200 x 100. For the choice of regularization parameter AN in each local machine, we first choose Xy based on
the dataset in the first local machine H4 by five-fold cross-validation. Moreover, motivated by the theoretical scale difference in Theorem | we further divide X, by /m, namely, Av Xn /mm 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) all samples in single machine.

---

Under review as a conference paper at ICLR 2021
Same Cai et al. (2019), adopt the oracle T = 22llgg,, N, 10, and (c, 10/ (c) Pooled-Mean: Take average among all samples and take quantization function Qx (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.
Eiest (1) = 1}
[[Q1(X)) =Q(x))1 = NFDR max 1a = -11.1
PFDR
max I 11 13 Total False Discovery Rate and Power.
FDR Eiss (X)) max I (1) + 03,
Eies (X) * 0}
Power
max 1 + 0},
Table 1: The PFDR, NFDR, FDR, power, and their standard errors (in parentheses) of different
methods under sample size N = 200 x 100, local sample size n = 200.
Med-DC
Mcan-DC
CWZ
Pooled-Mean
PFDR NFDR
0.0684 (0.1251)
0,9472 (0.0038)
0.6981 (0.2122)
0,0000 (0.0000)
0.0729 (0. (283)
0.9473 (0.0036)
0.6834 (0.2095)
0.0000 (0.0000)
FDR Power
0.0751 (0.1170)
0,9475 (0.0008)
0.6800 (0.1807)
0.0000 (0.0000)
1.0000 (0.0000)
1.0000 (0.0000) 0.3200 (0.1807)
0.7840 (0.0846)
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.
4.2 RESULTS FOR SPARSE LINEAR REGRESSION
In the second experiments, we consider the linear model defined in (6. Let the noises are i.i.d.
from (N0, 1) and assume the i.i.d. covariate vectors X (X.,1...., Xip) (i 11 1....,N N) are drawn from a multivariate normal distribution (0, E). The covariance matrix E p Toeplitz
matrix with its (i, entry Σ; = 0.516-5l, where S i, I p. We fix the dimension p 200. Moreover, we set the true coefficient 0" the same as μ in (TO). Similarly, we set m = 100. n = 200. For the choice of regularization parameter Ax in each local machine, we first choose X'y based on the dataset in the first local machine Hi by five-fold cross-validation. As suggested in classical literatures (Wainwright) (2009), motivated by the thcoretical scale difference in Theorem 2 and further divide it by vm. In addition to Mean-DC, we mainly compare with other methods:
Surrogate Likelihood (CSL) framework in Jordan et al. 2019) to obtain an estimator 0cst. for the true parameter and take the signs of it. (e) Pooled-Lasso: Solve the Lasso problem on all data in single machine and take the signs.
(d) CSL: Use the Communication-effccee
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-costi 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.
Table 2: The PFDR, NFDR, FDR, power and their standard errors (in parentheses) of different
methods under sample size 200 x 100, local sample size n 200.
Med-DCC
Mean-DC
CSL.
Pooled-Lasso
PFDR NEDR
0.0639 (0.1329)
0.9454 (0.0425)
0.4453 (0.3447)
0.5703 (0.1758)
0.0582 (0.1199)
0.9456 (0.0425)
0.4325 (0.3480)
0.5808 (0.1717)
FDR 0.0645 (0. 1184)
0.9457 (0.0424)
0,4466 (0.3397)
0,5896 (0. 1464)
Power
1.0000 (0.0000)
1.0000 (0.0000)
0.9998 (0.0045)
1.0000 (0.0000)
can be observed from Table while all these methods can select the true support set, the Med-DC Lasso method has apparently smaller false discovery rate than others.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Marco Avella-Medina. Privacy-presse preseviig parametric inference: A case for robust statistics, Journal of the American Statistical Association, 0(ja):1-45, 2019.
Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In Proceedings of the 2014 IEEE 55th Annual Symposium Foundations of Computer Science, FOCS '14, pp. 464-473. IEEE Computer Society, 2014. ISBN 9781479965175.
Heather Battey, Jianqing Fan, Han Liu, Junwei Lu, and Ziwei Zhu. Distributed estimation and inference with statistical guarantees. Annals of Statistics, 46(3):1352-1388 2018.
Amir Beck and Mare Teboulle. A fast iterative darinkage-threholddie algorithm for linear inverse problems. SIAM J. Imaging Sci., 113::183-20, 2009.
Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, and Jonathan Eckstein. Distributed optimiza- tion and statistical learning via the alternating direction method of multipliers. Foundations and Trendy in Machine Learning, 1-12: 2011. ISSN 1935-8237.
Victor-Emmanuel Brunel and Marco Avella-Medina. Propose, Test, Release: Differentially private estimation with high probability. arXiv e-prints, art. arXiv:2002.08774, February 2020.
Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In TCC (BI), pp. 635-658. Springer, 2016. doi: 10. (0007/97--3-662-3366
Mark Bun, Jonathan Ullman, and Salil Vadhan. Fingerprinting codes and the price of approximate differential privacy. SIAM Journal on Computing, 4885):188811938, 2018.
Tony Cai, Yichen Wang, and Linjun Zhang. The cost of privacy: Optimal rates of convergence for parameter estimation with differential privacy. arXiv e-prints, art. 1rXiv:1902.04495. February 2019.
Tony Cai and Weidong Liu. Adaptive thresholding for sparse covariance matrix estimation. Journal of the American Statistical Association, 106(494):672-684, 2011. ISSN 01621459.
Tony Cai, Weidong Liu, and Xi Luo. constrained & minimization approach to sparse precision matrix estimation. Journal of the American Staristical Association, 106(494):594-607, 2011.
E. Candes and T. Tao. Decoding by linear programming. IEEE Transactions on Information Theory, 51(11):4403-4211 2005.
Scott Shaobing Chen, David L. Donoho, and Michael A. Saunders. Atomic decomposition by basis pursuit. SIAM Review, 43(1):129-1535 2001.
Y.S. Chow and H. Teicher. Probability Theory: Independence, Interchangeabiliry Martingales. Springer Texts Statistics. Springer New York, 2012. ISBN 978 9781461219507.
Jinshuo Dong, Aaron Roth, and Weijie J. Su. Gaussian differential privacy. arXiv e-prints, art. arXiv:1905.02383, May 2019.
D. L. Donoho. Compressed sensing. IEEE Transactions on Information Theory, 1284):128-11366 2006.
John C. Duchi, Michael I. Jordan, and Martin J. Wainwright. Minimax optimal procedures for locally private estimation. Journal of the American Statistical Association, 113(521):122-201, 2018.
Cynthia Dwork and Jing Lei. Differential privacy and robust statistics. Proceedings of the Forty- First Annual ACM Symposium on Theory of Computing, STOC '09, pp. 371-380. Association for Computing Machinery, 2009. ISBN 9781 778165538562..
Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 9(3-4):21 1-407, August 2014. ISSN 1551-305X.

---

Under review as a conference paper at ICLR 2021
Cynthia Dwork and Guy N. Rothblum. Concentrated differential privacy. arXiv e-prints, art. 3xXiv:6603.01811 March 2016.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Shai Halevi and Tal Rabin (eds.). Theory of Cryplography, pp. 265-284. Springer Berlin Heidelberg, 2006. ISBN 978-3-540-32732-55.
Jianqing Fan, Yongyi Guo, and Kaizheng Wang. Communication-efiin accurate statistical esti- mation. arXiv e-prints, Jun 2019.
Jihun Hamm, Yingjun Cao, and Mikhail Belkin. Learning privately from multiparty data. In Maria Florina Balcan and Kilian Q. Weinberger (eds.), Proceedings of Machine Learning Re- search, volume 48, pp. 555-563. PMLR, 20-22 Jun 2016.
Bargav Jayaraman, Lingxiao Wang. David Evans, and Quanquan Gu. Distributed learning without distress: Privacy-preserving empirical risk minimization. In Advances in Neural Information Processing Systems 31, pp. 6343-6354, Curran Associates, Inc., 2018.
Michael I. Jordan, Jason D. Lee, and Yun Yang. Commumication--ffiiiiii distributed statistical
inference. Journal of the American Statistical Association, 114(526))668-681, 2019.
Guillaume Lecué and Matthieu Lerasle. Robust machine learning by median-of- ofann-ns:- Theory and
practice. Annals of Statistics, 48(2):906-931, 2020.
Jason D. Lee, Qiang Liu, Yuekai Sun, and Jonathan E. Taylor. Communication-effccieenn sparse regression. Journal of Machine Learning Research, 18(1): 144, January 2017. ISSN 1532- 4435.
Jing Lei. Differentially private m-estimators. In Advances in Neural Information Processing Systems
24, pp. 361-369. Curran Associates, Inc., 2011.
Ryan Mcdonald, Mehryar Mohri, Nathan Silberman, Dan Walker, and Gideon S. Mann. Efficient large-scale distributed training of conditional maximum entropy models. Advances in Neural Information Processing Systems 22, pp. 1231-1239. Curran Associates, Inc., 2009.
Nicolai Meinshausen and Peter Bühlmann. High-dimensional graphs and variable selection with the lasso. Annals of Statistics, 34(3):1436-13 1462, 06 2006.
A. Miller. Subset Selection Regression. New York: Chapman and Hall/CRC, 2002.
Stanislav Minsker. Distributed statistical estimation and rates of convergence in normal approxima- tion. Electronic Journal of Statistics, 13(2):5213-5252. 2019.
I. Mironov. Rényi diffcrential privacy. In 2017 IEEE 30th Computer Security Foundations Sympo- sium (CSF), pp. 263-275, 2017.
Arkadii Semenovich Nemirovsky and David Borisovich Yudin. Problem Complexity and Method Efficiency in Optimization. Wiley, 1983.
Manas Pathak, Shantanu Rane, and Bhiksha Raj. Multiparty differential privacy via aggregation of locally trained classifiers. In Advances in Neural Information Processing Systems 23, pp. 1876- 1884. Curran Associates, Inc., 2010.
Adam Smith. Privacy- preecy-pr statistical estimation with optimal convergence rates. In Pro- ceedings of the Sarty-Thidd Annual ACM Symposium on Theory of Computing, STOC '11, pp. 813-822. Association for Computing Machinery, 2011. ISBN 9781450306911.
Robert Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society: Series B (Statistical Methodology). 58(1):267-288, 1996.
Martin J Wainwright. Sharp thresholds for high- dinenssinn and noisy sparsity recovery using 4 constrained quadratic programming (lasso). IEEE Transactions on Information Theory, 55(5): 2183-2202, 2009.
10

---

Under review as a conference paper at ICLR 2021
Larry Wasserman and Shuheng Zhou. A statistical framework for differential privacy. Journal of the American Statistical Association, 105(489):355388) 2010.
Dong Yin, Yudong Chen, Ramchandran Kannan, and Peter Bartlett. Byzantine-robust distributed learning: Towards optimal statistical rates. In Proceedings of the 35th International Conference on Machine Learning, volume 80, pp. 5650-5659, 10-15 Jul 2018.
Yuchen Zhang, John C. Duchi, and Martin J. Wainwright. Communication-effciennn algorithms for statistical optimization. Journal of Machine Learning Research, 14:3321-3365 2013.
Peng Zhao and Bin Yu. On model selection consistency of lasso. Journal of Machine Learning Research, 7(Nov):5541-2566 2006.
Ligeng Zhu, Zhijian Liu, and Song Han. Deep leakage from gradients. In Advances in Neural Information Processing Systems 32, pp. 14774-14784. Curran Associates, Inc., 2019.

---

Under review as a conference paper at ICLR 2021
A TECHNICAL LEMMAS
Lemma 1. (Berry-Esseen Theorem, Theorem 9.1.3 in Chow & Teicher
(2012) If (X,, i i2 1) are
i.dd mean-zero random variables with [[ =²²,
<0.. Then there exists constant
CB > 0 such that
n Σ X x Vnow {(x))
CB
sup CO0
IP
vn
Lemma 2. (Exponential Inequality, Lemma I in Cai & Liu (2111)) Let X1.... Xn be ii.d. random variables with zero mean. Suppose that there exist some 1) > O and > 0 such that B[X s C. Then uniformly for 0 < C and 2 1, there is
1
3 S exp (-rc)
)
na?
P
Σ 1=1
X 2
Lemma 3. Lei N(= mi) i...d random variables X1 X1, XN evenly distributed in m subsets H1,-... Hm. Suppose B[X,] 0 o², ,
co. Denote Xj = EiEn, Xz/n as
the local sample mean on Hz. For every > 1, denote
9 0
k
7 log
+
mvn
mn
where Ô > 0 is sufficiently large enough. Then for every fixed non-negative constant k, there is
m (X, Cr)
m
- 2
+ k
(X,
- m
+
O(n 7) (1I)
2
Proof. For every x > 0, there is
T [X3 <2) - 111
+ k
k
=P
I(X, < <x) - ( <
-
-
P
(82 <a)
2
m
j=1
k
CB
/vxx
188 <x)
-
+
+
2
Vn
1=1
Cy log
PP
<
<
2)
m
where the last line uses Berry-Esseen Theorem (Lemma)
1. and x is given by
k + m
CB Cry log
Vn
vn
m
Applying Lemma 2 to the i.i.d. sequence (X, x) P [x < x)
we have
m ~ (X < 2)
C7 C7 log
I
O(n
m
m
for some C large enough. Moreover, we have the following elementary facts
Iz0 1/2
x (zo)) = (xx) -- -(112)) < 2o - 1/21 (4 11 (xo) S 1/ (3/-()
12

---

Under review as a conference paper at ICLR 2021
holds for any 1/4 < for m, n sufficiently large. Denote Cs = 1/12(00 (3/4)), (3/4)) then there
3/4. On the other hand, we know that 1/4 & ((vnz/o) 3/4 holds
P
Xj <
Cg vn
CB
+
k
+ V
Cr log
S
m 2
m
m
m
Cr log n
<PP
(X, < σ) - P (Xx
< x
S
12
m
m
j=l
Therefore, if we choose C 2 max(C&CBo, C&v CovCo,, the bound of the first in the left hand side of (TT) is proved. By repeating the same procedure, we can prove the bound of the second term, which yields the desired result.
Lemma 4. Let XI,..., X be i..d random vectors sampled from the distribution in 8 Denote its covariance matrix as E, and the sample covariance matrix as E. Then for every > 1, there exists a constant C > 0 such that
(((=~11-1) CV log
O(n
Proof. Recall that the inverse covariance matrix is denoted as Σ-1 (Wi..... Wp). and el as the 1-th coordinate vector. Then the (11,4)) -entrry of the matrix E-1 5-1--
I is
Σ ho X; l X: -1
Since the dimension p is assumed to be bounded, and the covariance matrix is positive definite, there exist a constant p (0, 1) such that
p S Amiu Σ) I Amaxx Σ) S p-1
Then we have
max Wil2 S Σ |1 sp- ISISP
Since X is sub- Gabb-Guussinn in 8
obtain
Ef E(expmp w Xi et= x; o1
max 1gh
Sem sup E(mlu' x S e.. 1
Therefore, we can apply Lemma 2 to each coordinate and yield
P
M
1
2 C
log n
11
(11- Σ
log n
Sp² max
w
X; ett ex,x; 81,
2 0
15h.455p
n2
=0(p'n -- = On
for some Ò sufficiently large. Therefore, the lemma is proved.
B PROOF OF MAIN RESULTS
Proof of Theorem 7 If we can show that
max P ISTSp
(Q)((x) * sgn((i)) = O(n7))
(12)
13

---

Under review as a conference paper at ICLR 2021
where 7>> >> is large enough. Then this theorem is proved as follows
1 I-P(O(x) - sgn((())
Sp max P Qx(x) + sgn(47)) = Opp Onn>))))) ISTSP
provided that 7 70. For the 1-th coordinate, we firstly suppose that μi 0. Since X X,'s [ with k 0, if
sampled from the distribution (4. by Lemma
(v llgg mn
1 +
AN Co
2 cy.
n2
we have
P ((), + sgn(ur))
SP
Xi < An
- m
{5 -AN)
- - m1 = -Onn O(n
2
Next we assume fu > 0. We use Lemma 3 Jagainn if
logg logn mn + + 2 2,, c +NN,
Mi 2 ci((
then there is
I (((1(x) + sgn(mi))
SP
8z11 > AN)
s m
2
Ø=1
<P
m Xi 14 -c)) <
O(n
2
Lastly, when pf < 0. the proof is the same above. Therefore 12) is proved.
Proof of Proposition For X' E D(X,, denote the elements in X' as X (where S S N), where
Σ
+
Moreover, since these data are stored in different machines H1, Hyss have
5
Σ IX x,) 11
(13)
j=1
Noticing that
P (Q(x) (x'), for all X' e D(X))
Q(xx)) # (p"), for all x' D(X): QXX) = sgn(H²)) + +P(((X) & sgn(4²))
(Qx'') + sgn( for all x' E D(X)) + 0(n
Therefore, only need to show that
(x)) # sgn(""), for all X' E D(X)) = O(nn7²)
(14)
14

---

Under review as a conference paper at ICLR 2021
For the 1-th coordinate, we firstly suppose that pu 0. Then there is
P P(Qi(X)) + O, for all X E D(X))
I1 (Xjx < AN) $ 2. for all X' D(X)}
m
+ |
Σ
(211 > -AN)
-
m
for all X E D(x)) }
2
j=l
m
SP
Av)
- 2 + 1
m
+
X5 > - Axx)
- m
2 + +1}.
j=1
where the last inequality uses
13
Using Lemma
3 with 1, with 2N properly chosen, there is
m
m
Σ (X,I AN)
S m 2
P
[ -AN)
1 +1 On)
m
2
for some 7 O. Similarly, if μ > 0, there is
P (())(X)) + 1, for all X' E D(X))
12
<P
(X AN)
for all X E }
2
j=1
m
SP
(Xy. Ax)
- 2 + 1
m
j=1
<P
An 1ن
- m
+1 0(n
2
j=1
where the penultimate line uses 17 < O is similar, therefore
(3) and the last line uses Lemma with & 1. The proof when
P ((((x)) * sgu(H"), for all x' e D(X))
SplP (x')) # sgn( for all x' E D(x)) O(pn = O(n 72)),
which proves (14). Therefore the proposition is proved.
Proof of Theorem For each {l...., m)) taking sub- sub-gradient of 7 at 0,,, have that
(Y x, AN Z, =
where Zj is the uub-gradient satisfying Zyloo S 1. Rearranging the terms and multiplying Σ on the both sides, we have
0 -0=
Σ EEH;
x,x (0, 0*) +
(15)
NE
Taking ; = mmnmmmi 722 since the noise and covariates are assumed to be sub-Gaussian in for each coordinate 1 E {1,.....l p). we have
max E exp x =1}
1555p
mp + 1
< max 1
E exp
E exp xxpp (2] IE{ expml> 1/2
s V0,22
max s
15

---

Under review as a conference paper at ICLR 2021
Therefore by Lemma
know that there exists constant C1 0 such that
max mm
1
Σ
Σ
X
SC n
logn
(16)
n
iENL
with probability larger than O( 7). On the other hand, by the fact that Zyy S 1, we have
I AN -
(17)
Moreover, by Lemma
we know
max 1.7mm
-- E
I
X,X!
=Or(1
log m
(18)
1000
72
iEH,
Substitute 16
into
15 we have
log
00
2AN
E
+ +2011
n
From 15
the 1-th coordinate can written in the following form
0₂ 07 Zzw + ANWi,-12j,11
Σ
x +
log n
(19)
SEM,
left rehash the argument in the proof of Theorem
T From Lemma
below we have that
1- IP Qx)x sgn(0")) p max SSS
Onn
Therefore we proved Theorem
Lemma 5, Assume the same assumptions Theorem 2 For every 1 S L S p. we have
P P(Qi(Z)= * sgn(Bi)) On ")),
for arbitrarily fixed y
Proof.
When 0r = 0. we know that
m
( + sgn(O)) s IP
(0.1 20) S
P
Σ 11 10,1120) 20
s
j=1
1=1
By symmetry of the formulation, is enough to prove
P
M
(05
> 2
On
(20)
When 03 0, know that Zy,1 1 (see 19
Moreover, by assumption (c), have
AN Zy, + AN -1 Awai, Aw -11 2 Aodwwa.
Therefore from
19 we have that
Σ
(0 0)
P
Σ wt Xiz, < - Aodwwrs)
< m
iEN;
Applying Lemma 3 with & = 0 to the i.i.d. random variables wT. 22 we can prove (00 by taking
2c,
(V logn n
log
Av Aowi,
(21)
mn
with è sufficiently large. Repeat the argument for the other half, can prove the case for 07 0.
16

---

Under review as a conference paper at ICLR 2021
When B7 > 0, again from equation
(19
we have
0z 2 0f + 1 Σ
log
w/ Xiz -
11 10 AN + up
11 SEH,
n
Therefore
m P.
+ sgn(f() x
Σ j=l
(0)1 (0,115)) 50)= 2 2
m
Σ
Mt X S - 22/22
L:x0 AN
2 2 1
iEH;
Applying Lemma
3 we can show that
p
w x
- 2 2 '1len dv) 2 2 = O
m
iEH,
provided that
log n
log
07 2 Σ 1
L.0 Av 2 O2
V
mn
n
with C2 sufficiently large. Combining with 21 we know
07 OzAN,
for some C3 > O. When 07 < 0, the prove is essentially the same as above, hence we omit it for brevity. Thus the lemma is proved.
Proof of Proposition
The proof is similar as that of Proposition I For X' E D(X), denote the elements in X' as Y!) (where <is N), where
N
Σ
(X,,)) * (x.).))
Since these data are stored in m machines, we denote 0z, as the local estimator given by data {(X,, Y/) i E H, then there
0 j=1
1(0), + 0,) 1
(22)
Noticing that
PP ((((x)) + (x)), for all x' D(x))
<TP <T (Q(X')) + @g"( ) for all X' E D(X): Qxx) = sgn(0') + P(((X) * sgn(0*))
<T <T(2(())) + sgn(( (*), for all x e D(X) + O(n
Therefore we only need to prove
P (x((')) * sf") for all X' e D(X)) 72).
(23)
When 07 = 0, we have
IP
(xx) + 0, for X' E D(X))
(0%, S 0) s 2
for all X' D(X)}
m
Σ 11 105,, 20)
< m 2
for all X' E D(X))
j=1
m
<T
(0/s 50)
$ m
+
+ P
(, 2 0)
2/ m
+1}.
2
1=1
j=1
17

---

Under review as a conference paper at ICLR 2021
where the last line uses show that
Using the expansion 19 and rehash the proof in Lemma we
m P
Σ 1=1
5O
0)
- 2 +1 P
m
Σ (0A1
20) s m
2 + +11 On
When 07 > 0, similarly we have that
P (()) + 1, for all X' D(X))
(o,, s 0)
m
2
for all X' E D(X)
==1
<P
Σ TI (0,,1 =0) z
m
1 O(
2
1=1
Similar argument can be applied for the case when 0f which concludes the proof of 23 Therefore, Proposition 2 is proved.
18


Reviews:
[{"review_id": "yqApCLbSfA9", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Summary:\nThe 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. \n\nConcerns:\nThe main concern about the paper is whether the “weaker” differential privacy notion proposed by the paper makes sense. \n\nTo me, this modification on differential privacy is very big, but it is not well discussed in the paper. In my understanding, the main difference between this notion and the standard differential privacy is that the standard differential privacy considers the worst case of the input but the modified notion considers the average case when inputs are assumed to be sampled from a distribution. From a single user’s perspective, this new privacy notion makes sense only when the user trusts that other users will follow the mechanism.\n\nIn this new notion, if you simply take the median of n binary numbers sampled from Bernoulli half, the median (without any noise) is private because with high probability, a single number flip won’t flip the median. And this shows that it might be very easy to design deterministic algorithms under this new privacy notion. It seems to me that the main reason for Med-DC being both deterministic and private in this new notion is the weakness of the new privacy notion but not the well-design of Med-DC.\n\nReasons for score:\nI vote for rejection. As discussed in the concerns, the modification of the differential privacy notion makes the problem very different and this modification is not well justified in the paper.\n\nTypos and minor comments:\n(1) Page 2: the definition of the supp(v) is not very clear. It’s written as {condition 1 | condition 2}. What are the elements in the set?\n(2) Page 2: when a_n = O(b_n) and b_n = O(a_n), you can write a_n = \\Theta(b_n) as the standard notation.\n(3) Page 6, first paragraph of section 3.1, “recovery” -> “recover”\n(4) I find the name “divide-and-conquer” does not fit the algorithm very well. A divide-and-conquer algorithm breaks down a problem into many simpler sub-problems. The algorithm in the paper has data points partitioned because of the distributed setup of the problem.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "lrkzU3TYWIu", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper considers the problem of private sign recovery for sparse mean estimation and sparse linear regression in a distributed setting. The paper proposes taking a coordinate-wise median among the reported local sign-vectors and gives its theoretical guarantees. Furthermore, the paper states that this is the first deterministic algorithm with a provable high-probability privacy guarantee.\n\nI tend to vote for rejecting this paper for the following reasons:\n1.  The problem considered in this paper is neither exciting nor complex. Furthermore, the algorithm proposed is quite natural. I agree these are some good results, but maybe not good enough for ICLR.\n\n2. It is not appropriate to say this is the first deterministic algorithm with a provable high-probability privacy guarantee. In fact, utilizing robust estimators, as combined with propose-test-release (PTR) is a very basic technique in the literature of differential privacy. See Section 3.2 and 3.3 in the textbook (https://privacytools.seas.harvard.edu/files/privacytools/files/complexityprivacy_1.pdf). The intuition behind PTR is that for a robust estimator (like median), although the global sensitivity is huge, the local sensitivity is only large in some corner cases. And the local sensitivity is  negligible with high probability, where the randomness is drawn from the dataset's generation. Using robust estimators (which is deterministic), which gives privacy guarantees with high probability, is exactly the start point of these algorithms. Therefore, I do not find it appropriate to state it is a new observation. By the way, using the median is also a very classic idea in the robust estimation, for example, estimating high-dimensional Gaussians by utilizing Tukey median.", "extra_scores": {}, "extra_text": {}}, {"review_id": "W1cnkX6oFcP", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "==== Sumary of the problems considered and paper contribution\n\nThis paper studies the problem of sign recovery for sparse mean estimation and sparse linear regression. They show that a median based divide and conquer algorithm has high utility (as measured by power, false discovery rate, and positive and negative false discovery rates) and robustness properties. They discuss the privacy implications of these robustness properties, rigorously showing that the deterministic algorithm they define satisfies random differential privacy, where the probability (over the choice of dataset) of not satisfying privacy tends to 0. They show experimentally that their algorithm has low communication and performs well, even when compared to algorithms with no robustness properties.\n\n==== Comments \n\nThe paper touches on some interesting questions around robustness and privacy. They essentially design a robust algorithm, subdividing the data to produce averages, reducing the signal by reporting on the sign of each answer, then using the median to give the final answer. Their privacy guarantee amounts to showing that this process is very stable to outliers. The authors remark at one point that this stability implies that they could likely use a procedure like propose test release to give an actually differentially private version. I wonder why they didn’t do this? I’d be very interested to see how it performed.\n\nI think the strength of the stability statements Proposition 1, Proposition 2 and corollary 1 gets a bit lost in the vagueness of the wording. It should be made clear that the randomness is over X, and X’ is any worst case neighbouring dataset. This is significantly stronger than if the randomness was over the pair. This stronger version means that the algorithm is stable against outliers, including those caused by unclean data, or malicious participants. This is particularly interesting in Corollary 1, which discusses group privacy. Also “random differential privacy”, which has appeared in the literature previously, seems like the notion the authors are looking for. However, it seems like a little bit of a stretch to call this \"roughly (0,0)-DP”.\n\nThe paper is well written, it clearly states its theoretical guarantees and discusses intuition. In particular the privacy guarantees are clearly stated, and their difference to pure DP highlighted.  I thought Section 2.2 was especially well-written. I’m not an expert on sparse DP algorithms but it seemed to discuss prior work well, and highlight how this work is different, as well as why previous work did not immediately imply a solution. \n\nIt looks like the pooled mean does really well for false discovery rates, why is this? \n\n==== Presentation\n\nThe paper is well written. I think the privacy aspect would be more compelling if the authors ran the propose test release version, which would actually be DP. It seems like this experiment would be interesting whether or not the propose test release version did well. \n\nSmall comments:\nDefinition 1 should be all measureable subsets, not just all subsets. \nTypo: second sentence in intro: “large quantities of sensitive data are..” should be “large quantities of sensitive data have been..”\nIt would have been helpful to have the definition of the sgn of a sparse vecctor in the introduction, I was a little unsure exactly what was meant. \nWhen defining the distribution space in (4), I think it would be helpful to state why the condition is required, not just that it is mild. It’s for Berry Esseen, yes?\nIt would be nice to see a discussion of the privacy implications of the five-fold cross-validation.\nThe second sentence of the abstract: it is not just common sense that randomness is required, unless the function is constant, randomness is provably required.", "extra_scores": {}, "extra_text": {}}, {"review_id": "-rcll8AVSLQ", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "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.\n\nStrengths: Strong technical justifications in terms of proofs and experiments.\n\nWeaknesses: I don't totally understand the message of the paper. Why is loss of worst-case privacy acceptable? This is what happens in the paper, and without a good justification for that, I don't see why such a loss of privacy is okay. Even privacy has not been formally defined. Apart from group privacy, no other important properties of the \"definition\" have been proved.\n\nNitpicks:\n-The title is a bit misleading, even though it is obvious that DP cannot be achieved by deterministic algorithms.\n-You talk about certain papers doing mean estimation on page 3, but you forget to mention a recent result by Kamath et al on private mean estimation of heavy-tailed distributions, which also uses median of means framework, and may have connections to robustness.\n-At the bottom of page 5, you say that the method is roughly regarded as a (0,0)-DP algorithm. That's a very brave thing to say. I wouldn't claim things like that without formal justifications.\n\nScore justification: The weaknesses of this paper just outweigh the positives. A good motivation/justification of the privacy model could have helped to get a better score.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper considers a problem of weak mean estimation under a differential privacy like constraint. Specifically, estimating the signs of a (sparse) mean, and not the actual values. 

The reviewers brought up a number of concerns, including the weak privacy guarantee (a type of average-case privacy). Other lesser concerns include inaccuracies in comparisons with the literature and lack of interest in the algorithm/method itself.

As there was no response from the authors, there was little further discussion afterwards, and the reviewers remained in their opinion to reject the paper.
Decision: Reject