Differentially Private Linear Regression via Medians
Authors: Alexander Knop
Thomas Steinke
Venue: NeurIPS 2022 Submitted (2022)
Keywords: differential privacy
linear regression
robust statistics

Abstract: Linear regression is one of the simplest machine learning tasks. Despite much work, differentially private linear regression still lacks effective algorithms.
We propose a new approach based on a multivariate extension of the Theil-Sen estimator.
The theoretical advantage of our approach is that we do not directly rely on noise addition, which requires bounding the sensitivity. Instead we compute differentially private medians as a subroutine, which are more robust.
We also show experimentally that our approach compares favourably to prior work.

29 bounds are loose, we must add more noise than necessary. If the bounds too tight, the clipping Differentially Private Linear Regression via Medians
Anonymous Author(s) Affiliation Address email
Abstract
Linear regression is of the simplest machine learning tasks. Despite much work, differentially private linear regression still lacks effective algorithms. We propose new approach based multivariate extension of the Theil-Sen esti- mator. The theoretical advantage of our approach is that we do not directly rely on noise addition, which requires bounding the sensitivity. Instead we compute differentially private medians as a subroutine, which are more robust. We also show experimentally that our approach compares favourably to prior work.
2
Introduction
Background & Motivation Differential Privacy [DMNS06] is standard for ensuring that the 10 output (i.e., trained model) machine learning system does not leak sensitive details about its 11 input (i.e., training data, which could contain private information about individual people). Differ- 12 entially private machine learning has been the topic of considerable research, both theoretical and empirical, and is also used in practice [MT22].
14 Arguably, the simplest machine learning task is linear regression. That we are given dataset
15 (I1, W1), (I2, M2),... (In, Mnd) E Ra x IR and our goal is to fit linear model of the form y/ Ro
16 (0, r.) for some E Rd. More precisely, ordinary least squares linear regression minimizes the squared error ((0 .r)) - y:)². This objective corresponds to assuming that the errors (i.e., the
18
deviations from a perfect linear relationship) are Gaussian. This objective is particularly nice, as X where X (I1, .., J.,) E Raxd and
it has closed-form solution:
xX"x)-1X
20
(y1, V2.
R".
Given the practical importance of linear regression, there has been lot of work on differentially private linear regression. (We discuss the related work more detail in Section 1.3.) However, these prior works all suffer from the same limitation: To guarantee differential privacy they add noise to some quantity- either to the raw data and y, to the sufficient statistics x and X the gradients E. 2. (40, vx) 3R) encountered when optimizing the least squares objective. This noise addition approach requires bounding the sensitivity, which essentially means we must provide a priori bounds ||ar:|| and ly: or, rather, we must scale/clip the quantities of interest to enforce these bounds. The clipping hyperparameter induces a harsh privacy-utility tradeoff: the
22
24
25
26
28
30 distorts the data. This raises the question: Can we perform differentially private linear regression in way that is (nearly) agnostic the sensitivity?
31
32 Inspiration for Our Approach To gain some intuition, consider the even simpler task of mean
33 estimation, i.e. computing the average n Σ. z;- Here we face the same difficulty terms of
34 clipping the data to bound the sensitivity. Numerous approaches to mean estimation have been
35 studied [c.g.: KV17: BS19; KSU20: BDKU20; LKKO21; LK0211,
Submitted to 36th Conference on Neural Information Processing Systems (NeurIPS 2022). Do not distribute.

---

10a
1012
10a0
10-0.2
10
10
10-0.4
10a
10a
10-0.0
109
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
number samples
-10
number samples
-10
10a
10aa
10"1
10
107
10
10a
10a
10
10
10
10
Private Theil-Sen estimator (Algorithm 1)
Gaussian Mechanism Regressor DP-GD Regressor
DP Functional Mechanism Regressor
Figure I: Comparison of DP linear regression algorithms. Mean square error (i.e., (i( -) on vertical axis in logarithmic scale) as a function of the number samples (i.e., n on horizontal axis) for dimensions d 10 (left) and d 30 (right); and function of for = 10a and dimensions 10 (left) and 30 (right). The line show the median and the semitransparent shadow shows the 0.1 and 0.9 quantiles of the error; values computed over 20 runs. Privacy parameters e 1 and = 10 6; and 1. Data is synthetic, see Section 2.1 for details.
One way to sidestep this sensitivity issue is to look the median instead of the mean. Under reasonable distributional assumptions, the median is a good approximation to the mean, with the advantage that the sensitivity of the median usually much lower than the mean. Thus the median 39 can be a good tool for differentially private mean estimation.
37
38
The key innovation of our approach is to carry this median- instead---eee of-m idea over to the setting of linear regression. But this is far from straightforward we are interested in the multidimennional setting and even defining multi multi-dimmensonal median is nontrivial.
41
43 We draw further inspiration from the literature on robust statistics intuitively, the median a robust
44 replacement for the mean. In particular, the Theil-Sen estimator [The50;; Sen68] uses the median
45 to perform robust simple linear regression (i.e., d 1). Indeed, differentially private Theil-Sen estimator has been studied by Dwork and Lei [DL09] and Alabi, McMillan, Sarathy, Smith, and
47 Vadhan [AMSSV22]. We extend this multivariate linear regression using variant of the (non- private) approach of Dang, Peng, Wang, and Zhang [DPWZ08].

---

Algorithm Private efficient multivariate Theil-Sen estimator.
1: Input: 91), (12, y2).....
... (# Un) IRd x IR.
2: Parameters: Privacy parameter > 0. Number of partitions 2 1. Output range R. C IR.
3: Let mmnn/d].
4: Initialize empty multiset G R
5: for E [e] do > Generate e m subproblems S5,6 such that each input appears in at most l.
6: Randomly choose m disjoint sets Si,k, S2.k...,, Sm,k C [m]] each of size d.
7: for j E [m]] do
8: Compute 0g E Rd such that (0),0, = yi for
Sy 9: Project fJ,& E Rd into 8g -ie, 0g. arg minger 11@ 83.a1l-
Add 0, to O.
11: end for
end for
13:
> Compute an approximate median 0 E Rd of the set θ in DP manner.
14: for
i E [d] do b Independently sample i-th coordinate of á using the exponential mechanism.
15: Sample 0g R with probability proportional
P|0,] exp (- 26d
max {[[0
θ 0 < < 0: >..
end for 17: return
1.1
Our Algorithm
50
Our private linear regression algorithm is described Algorithm 1. We proceed with some remarks about our algorithm.
51
52
The high-level idea of the Theil-Ser -en estimator is that, rather than trying to solve the global objective (i.c.. ming Σ; (10, x.) ))) we solve e m subproblems and then combine these solutions into a single solution via a median. Each subproblem consists of a subset of d out of n of the input points (which is enough to uniquely specify the weights 0j.A E Rd, assuming the are linearly
53
54
55
56
independent).
57
The standard Theil-Sen estimator considers all (a) possible subproblems. This is computationally prohibitive for realistic values of and d: hence randomly select subset of & m subproblems. We will consider small numbers of repetitions, such as
58
59
From differential privacy perspective, changing input point (x,, 8/) can change subproblems and hence l clements é. our method for computing the median is (e/E))diiffreeniaal)) private with respect changing element of O, then by group privacy it is e-differrntially private with respect to changing one input point (I,, yi), as required." This is a straightforward extension of the and-pl--nnd-ggrgaaalt framework [NRS07].
81
69
65 There are many ways to defube and compute multivariate median (even non-privately). For sim- plicity, we compute a marginal median: we simply compute the univariate median for each coor- dinate i... 0 x median 0, for each i E [d]. Privately approximating the univariate median is well-studied problem [NRS07; Smi08; DI09; Smill: BNSV15; KV17; FS18; KLSU19; BS19; AD20; KLMNS20; GJK21; ABEC22]. We compute the median by simple application the expo- nential mechanism [MT07a]: although this doesn't achieve optimal asymptotic bounds, it performs remarkably well in practice. To be specific, following Smith [Smill [mmill I] and Feldman and Steinke
69
70
71
72
[FS88], we sample each coordinate 6 from probability distribution that decays exponentially with how far away it from the median. This ensures that the overall algorithm satisfies c-DP and
73
For simplicity, in this discussion, we restrict ourselves to pure differential privacy, but, to obtain better com- position bounds in the righ-dimensional setting, we will work with concentrated differential privacy [DR16; BS16] approximate differential privacy [DKMMN06).

---

accurate under reasonable conditions. Each coordinate 8; is computed in a way that is e/d-DP. Composing over the d coordinates yields the final E-DP bound.
74
75
76
Note that we restrict the range of the coordinates to R. C R. This can either be an interval (e.g.,
R [a, b)) or discrete set (e.g., R {a + (b a) (i - 1)/r E [r 1J}). For the exponential mechanism to be well-defined, it is necessary to ensure that R has finite measure (i.e., bounded finite set with the counting measure). Regardless of our choice 80 of algorithm, it is known that some such restriction is necessary in the worst case [ALMM19]. In most cases, the exact choice of R not particularly critical for our algorithm, so we do not dwell
78
79
interval with Lebesgue measure
81
82 on this issue.
There is subtlety of our choice of loss function for the exponential mechanism: If 0, # 0g for all
84
E θ we have
max {| 0, < 8. 100..K000 [0e0 o 00, [>>8
max { a < 0.]
10EE 0, 0.
[ 0, <
1 -
+ 1 1
The final expression is more natural than the first expression. The quantity {(0 = θ 0, 8.}
a5
86
gives the rank (i.e., rescaled quantile) of the value 6; in the multiset {0; A E θ). The true median has rank 2 [0), so the loss measures how far the rank is from this ideal. When everything has a con- tinuous distribution, the above equality between the expressions holds with probability 1. However, we have a discrete distribution (such as when is a discrete set), the above equality does not hold. Consider the extreme case where the multiset O consists of a single point 0* repeated many times.
87
88
89
90
When O2 0r our loss function takes value 0 and, for 0; * 0f, loss function takes value |+]. 92 In contrast, the final expression above would yield a constant function taking value [0] everywhere.
93
Thus our loss function performs better in the discrete case.
94
1.2
Our Results
85
We provide a theoretical privacy and utility analysis of our algorithm, as well as an experimental evaluation of algorithm. Our theoretical guarantee is helpful to build understanding. However, our experimental results give a clearer comparison to prior work. See Figure for an experimental comparison of algorithms. Next state the main accuracy result:
96
97
98
99
Theorem 1.1 (Main Result). For any ε, > O and d,r r E N, Algorithm with appropriate settings of parameters provides (E, and the following accuracy guarantee.
Fix 0* E [-rr--ri] and a > O. Assume the inputs (I1, v1), (I2, y2)..... (In, yn) Rd x R are each i each 103 on IG, we have ys + NN00", o²))
101
drawn i..dd as follows. Independently
[rl], we have x; +- No 1) and then, conditioned
If 0 is the output of Algorithm with the above inputs and parameters, then, all B > O, we have
104
P 10 - 00 50.0 ( d. (d.Vd-log(LA (og_//()
dr
+ d log(d/3)
1
log
+
2 1 B.
En
B
We now make some remarks about the meaning of our theoretical result.
106
Pure DP vs. Approximate DP Algorithm offers both pure and approximate DP guarantees (and concentrated DP); see Proposition A. for details. The parameter & of the algorithm corresponds to the pure (e, O)-DP guarantee. In high dimensional settings (i.e., large d), we can apply advanced
107
108
composition results to obtain better guarantees. Specifically, the approximate (ž, 8D- guarantee
109
110
of Theorem 1.1 is achieved by setting E. V Tog(1/8)

---

111 Accuracy Guarantee The error bound of Theorem 1.1 has three terms:
log
dr
is the
Em
error due to privacy; o.V log log(d/8) is the non non-private statistical estimation error (a.k.a. generalization error); and + is the error from rounding to the discrete set R of size (1r²).
113
Our accuracy guarantee bounds ||0 -0'| This is particularly useful if our goal is to estimate some parameter Or. as it provides a confidence interval. We can course also use this to bound the Euclidean norm: ||0 0- ll2 I vd- 110 - 0 llo. It is also common to provide bounds on the mean
115
118
117
squared error. Under our distributional assumptions, this is equivalent to bounding the Euclidean
norm: If x + N(0 1) and y +- NN((0, ;²), then, for all Ô Rd
118
(10 - ) = E [((0r, wi²| + 110 0-113 - 0² +0 0-13.
Distributional Assumptions We emphasize that our privacy guarantee is worst-case and the dis- tributional assumptions are only for the accuracy analysis. Thus the maxim "all models are wrong, but some are useful" (attributed to George Box) applies. That is, we don't expect real data to per- fectly follow a Gaussian distribution. Our algorithm still works even if these assumptions fail, but believe that the theorem is useful indication that our algorithm provides useful accuracy.
120
121
122
123
124
There is also some ficxibility in the Gaussian assumption: If the x,s are drawn from (0, 2) instead of (0, !) then we can apply a transformation (I,, y4) + 13-1/22,, M4) to make the distribution of 2,s spherical, run our algorithm to obtain 0, and then map this back to solution to the original problem Σ- 1/2..
125
128
Our assumption that the data comes from a mulivariate Gaussian is reasonably standard. Assuming that ||0 S. is less standard. In the non-private setting we don't 't' need to make any assumption on 8*, but it is necessary in the private case [ALMM19]. Note that we can arbitrarily rescale this
129
130
constraint: If instead we assume |10* 1% I b r for some b >> O, then can simply transform the data (zi, w)) + (zi, 5 (w: (0", .)))), run our algorithm to obtain Ō E [-r, and then map this back to a solution to the original problem 6 6-0 0 + 0 The accuracy guarantee will be rescaled accordingly. Similarly, the infinity norm can be replaced by the Euclidean norm by transforming the problem with a random unitary matrix [e.g., KLS21, 54.2].
132
133
134
135
136
The sample size n, dimension d, noise variance o², and privacy parameters È and are all standard parameters. The only non-standard parameter of Theorem 1.1 r. This determines both the size and granularity of the restricted range R in Algorithm 1. This parameter should be thought of as capturing how uncertain we are about 6 E [-r, and how precise our final answer should be - i.e. the granularity of R is 1/r (which should ideally scale with σ). Theorem 1.1 runs Algorithm with
Parameters
137
138
139
141
142
1.3
Related Work
143
Linear regression has been well studied in the non-private setting; we do not discuss this setting except to mention the connection to robust statistics. Robust statisties seeks to develop estimators that are resistant to small fraction of the dataset being corrupted. This kind of robustness turns out to be useful for designing DP algorithms [NRS07; DL09; BS19] and our work extends this connection. In particular, the standard approach to linear regression is not robust, which led to the development of the robust Theil-Sen estimator [The50; Sen68] and its multivariate extension [DPW008], which are the basis for our work.
144
146
148
150
DP linear regression has also been well-studied. Most similar our work that of Alabi, McMillan, Sarathy, Smith, and Vadhan [AMSSV22]. which studies the Theil-Sen estimator in the setting of simple linear regression. This is essentially our algorithm restricted to the case of d 1, although they also add constant intercept, i.e., an affine relationship = Ar + b. Adding an intercept is equivalent to adding an extra feature to x that is always and adding a corresponding dimension to
151
152
153
154
0. Dwork and Lei [DI.09] propose two DP robust regression methods. The first is, like ours, based 155
156
on the Theil-Sen estimator, although with a different method for computing the median. The second
changes the loss function to one with bounded gradients, namely Σ, (0, 21) v.l/|<z 112, and
5

---

158
analyzes the robustness of the solution to this new problem. Unfortunately, Dwork and Lei [DL09] provide very limited theoretical results and no experimental results for us to compare against.
159
160
Our algorithmic approach of analyzing several subproblems and then privately combining the an- swers is based on the sample-and-aggregate framework of Nissim, Raskhodnikova, and Smith [NRS07]. Similar algorithms have appeared in other works. In particular, Feldman and Steinke [FS use a median-of-means approach compute a univariate mean. Singhal and Steinke [SS21] propose an algorithm that is similar to ours, but for the different (but related) problem of finding a low- oiw-dimesioonal subspace that captures the data.
162
163
184
165
186 A natural approach to DP linear regression is to apply seneral-purposs optimization tools to the ob- jective function f()) = Σ. ((8, - 3² Noisy gradient descent (DP-GD) [SCS13; BST14; ACGMMTZ16] is a widely-used tool for private optimization. It adds noise to the gradients V (()) = 2 E. (10, mi;) y) I, encountered during the optimization procedure. To ensure that the gradients are bounded, we must clip them before addoing noise. That is, we add noise to min / f(0) (() instead of f(),, which could be unbounded. This approach works remarkably well, but it requires carefully setting the clipping parameter c. The larger e is, the more noise we add. But if e is too small we distort the gradients and the optimization procedure may not even converge in time. We use this approach as a comparison point in our experiments, but we find that setting the parameters (c, number of steps, and learning rate) to be highly non-trivial In an unpublished work, Varshney, Jain, and Thakurta [VJT22] propose variant of DP-GD where the clipping parameter is chosen in data-dependent manner each step of the optimization. They show that this adaptive clipping can achieve asymptotically optimal results. Kamath, Li, Singhal, and Ullman [KISSU1]] apply a similar adaptive clipping approach to learning the parameters of a Gaussian distribution; linear regression can be reduced to this task [MKF122). Another general- purpose optimization tool is Objective Perturbation (CMS11J, which was applied to linear regression by Wang [Wan18], but objective perturbation requires stronger assumptions than DP-GD (such as convexity ans smoothness) which means we also need additional assumptions to apply it to linear regression. Finally, we mention that, under the right assumptions, it is possible to apply the expo- nential mechanism [MT07b] to the linear regression objective, which can be viewed as a form of bayesian sampling [Wan18].
168
169
170
171
172
173
174
175
178
177
178
179
180
181
182
185
185
186
Since there is a closed-form solution in the non-private setting namelyy 0 = (X=X) y where each example (I,, V1) is a row of X and the corresponding row of y - another natural approach to the problem is to perturb X"X = Σ. xaoo E Rddd and X y Σ. y;æ, E Rd, which are known as the sufficient statistics. This requires us to bound the sensitivity of these terms, which boils down to bounding ||æ|l2 and lysl- For our experimental comparison, we add Gaussian noise to both X X and XTy. y. One downside of adding Gaussian noise to X X is that it may cease to be positive semidefinite. Thus it has also been suggested add noise drawn from Wishart distribution 19]. (We note that analyzing Wishart noise is difficult and incorrect analyses of this approach have been published [JXZ16; 1S16).) Wang [Wan18] also studied an adaptive form of sufficient statistics perturbation.
187
188
189
190
191
192
193
195
197
is also possible to add noise directly to the data [DTTZ14; She17: She19]. That is, we perturb X and y. which also requires bounding ||æı||2 and [/.]. This tends to yield worse results than perturbing the sufficient statistics. Intuitively, this approach adds noise to each of the n rows of X and y. so the amount of noise grows with n. In contrast, the amount of noise added to X and XT, does not grow with n. However, adding noise to the data is desirable if we are in the setting of local DP [ our results are for the central DP setting.
198
199
200
201
202
203 As mentioned earlier, of the key advantages of our algorithm over the optimization and perturbation approaches is that we do not need to clip or bound the data (x,, y:), which can be quite detrimental accuracy in practice. Our use of a median-based algorithm means we have much lower sensitivity to these bounds (logarithmic instead of linear).
204
205
208
2
Experiments
208
We now perform an empirical evaluation of our algorithm using synthetic data. We compare to state- of-the-art approaches and, since our algorithm has several moving parts, we also consider variants
209
210
of our algorithm.

---

10
10t6
10
10
10
107
10*
10
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
number of samples
-10*
number of samples
-10
Private Theil-Sen estimator (Algorithm 1)
Gaussian Mechanism Regressor
DP Functional Mechanism Regressor
DP-GD Regressor
Figure 2: Comparison of DP linear regression algorithms for features sampled from (0 Z). Mean square error (i.e., (0) y) vertical axis in logarithmic scale) function of the number of samples (i.e., n on horizontal axis) for dimensions d = 10 (left) and = 30 (right); and a function 10 (left) and d 30 (right). The line show the median and
of for n 10a and dimensions the semitransparent shadow shows the 0.1 and 0.9 quantiles of the error; values are computed over 20 Privacy parameters for details.
1 and 5 10 and f 1. Data synthetic, see Section 2.1
2.1 Synthetic Data
212 We perform our experiments using synthetic data, as this allows us to be precise about what assump- tions we and
making. In all these experiments 0 is sampled uniformly from [-1, 1j4, features 21, .... En sampled independently and uniformly from [0, 1] and each y; is sampled from (1(0, (i), o²) independently (conditioned on æ.), where o = 0.1.
213
215
Note that the features are sampled from bounded distribution, rather than Gaussian as in Theo- rem 1.1. We make this choice order to be generous to the algorithms we compare against. The algorithms we compare against clip the data gradients before adding noise,
217
make the prob- lem easier for them by ensuring that the data is fact bounded i.c., we ensure that the clipping does not distort the data. Our algorithm does not require this kind of assumption the features: Figure shows the errors if the features are sampled from ((, I).
219
221
2.2
Private Algorithms
223
We run Algorithm 1 with é - and R = [-1, 1). For comparison, we run the following state-of- the-art regression algorithms:
224
DP-GD based regressor: This algorithm applics noisy gradient descent to minimize the
loss Ei=1 (0, - v.) The learning rate 0.1, the number of epochs is 100, and the clipping rate 8d. (Our implementation of private GD gives result similar the results obtained by running DP-SGD provided by TensorFlow Privacy.)
226
228
Gaussian covariate matrix perturbation regressor: This algorithm outputs Å (X"X + A) A)' + b), where A is an appropriately scaled Gaussian matrix of size d x and is Gaussian vector of size d.
229
231
This algorithm represents the loss func- tion Σ ((0.z)) v1) polynomial in d, å₂ add appropriately scaled Laplacian noise to each coefficient of the polynomial to obtain ý and uses the Broy-
Functional mechanism based regressor:
233

---

-10-2
-10-2
4.5
4
3.5
0.4
0.2
0.8
number of samples
numher of samples
-10
Ordinary least squares
Theil-Sen estimator (L 1)
Theil-Sen estimator (L 10)
Figure 3: Mean square error as a function the number of samples for d = 10 and 30. The semitransparent shadow shows values between 0.1 and 0.9 quantiles of the accuracy.
algorithm to find & minimizing 9ú; we use the implementa- tion provided by Holohan et [HBMAL19]..
296
Figure 1 shows that the emror of our algorithm is lower that of the other algorithms compare against.
238
239
2.3
Non-private Algorithms
240
Before analyzing performance of private algorithms let us study performance on the non non-private ver- sion of the private efficient Theil-Sen estimator: non-private can be obtained from Algorithm by re-
241
placing Line 15 by line that sets ô such that max { θ A 6. { : 0 }
243
m
2
Figure shows that for reasonably large values of f, efficient multivariate Theil-Sen estimator per- forms as well as ordinary least squares estimator.
245
246
2.4
Values of
This section analyses relative performance of é-partition DP Theil-Sen for different values of é: considered & E {1, 10, 203. Figure 4 shows that their convergence rates are comparable in contrast with the non private setting where increasing improves the accuracy: this effect can be explained by the fact that the median heuristic uses amount budget proportional to 1/6 so increasing improves the true median, but adds more noise.
248
250
252
Because of this observation we only consider
2.5
Algorithms for Median
254
This section is analysing relative performance of efficient private Theil-Sen estimator for two choices of differentially private median heuristics: private median based exponential mechanism that is used in Algorithm and private median based on widened exponential mechanism defined [AMSSV22]. Figure 5 shows that like case of d [AMSSV22], private median based on exponential mechanism performs better on synthetic data.
256
258

---

-10-2
d= 10
d= 30
4.2
3.8
3.6
3.4
3.2
3
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
number samples
-105
number of samples
-10*
Private Theil-Sen estimator (E 1)
Private Theil-Sen estimator = 10)
Private Theil-Sen estimator (& 20)
Figure 4: Mean square function of the number of samples for d 10 and d 30. The semitransparent shadow shows values between 0.1 and 0.9 quantiles the error.
d 10
d = 30
12
10
8
6
4
2
0
0.2
0.4
0.6
0.8
0.2
0.6
0.8
number samples
-104
number of samples
-104
Exponential Mechanism Median
Widened Exponential Mechanism Median
Figure 5: Mean square error function of the number of samples for d 10 and d 30. The semitransparent shadow shows values between 0. and 0.9 quantiles the error.

---

References
259
280
[ABEC22]
D. Alabi, O. Ben-Eliezer, and A. Chaturvedi. "Bounded Space Differentially Pri- vate Quantiles". In: arXiv preprint arXiv:2201.0330 (2022) (cit. on p. 3). M. Abadi, A. Chu, I. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and L. Zhang. "Deep learning with differential privacy". In: Proceedings of the 2016 ACM SIGSAC conference on computer and communications security. 2016, Pp. 308-318 (cit. on p. 6).
262
[ACGMMTZ16]
263
284
285
[AD20]
H. Asi and J. C. Duchi. "Near instance-optimality in differential privacy". In: arXiv preprint arXiv:2005. 10630 (2020) (cit. on p. 3).
267
268
[ALMM19]
N. Alon, R. Livni, M. Malliaris, and S. Moran. "Private PAC learning implies finite Littlestone dimension". In: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. 2019, pp. 852-860 (cit. on pp. 5)
269
270
[AMSSV22]
D. Alabi, A. McMillan, J. Sarathy, A. Smith, and S. Vadhan. "Differentially Pri- vate Simple Linear Regression" ". In: Proceedings on Privacy Enhancing Tech- nologies 2022.2 (2022), pp. 184-204. URL:: httpp::// //doi org/10. 10. / popets- Sestta-2022--e 2022-0041 (cit. on pp. 2, 5, 8).
272
273
274
275
[BDKU20]
S. Biswas, Y. Dong, G. Kamath, and J. Ullman. "Coinpress: Practical private mean and covariance estimation". In: Advances in Neural Information Process- ing Systems 33 (2020), pp. 14475-14485 (cit. on p- 1).
276
277
278
[BNSV15]
M. Bun, K. Nissim, U. Stemmer, and S. Vadhan. "Differeniallly private release and learning of threshold functions". In: 2015 IEEE 56th Annual Symposium on Foundations of Computer Science. IEEE. 2015, pp. 334-649 (cit. on p- 3).
279
280
[BS16]
M. Bun and T. Steinke. "Concentrated differential privacy: Simplifications, ex- tensions, and lower bounds". In: Theory of Cryptography Conference. Springer. 2016, pp. 335-658 (cit. on pp. 3, 13, 14).
282
204
[BS19]
M. Bun and T. Steinke. "Average-case averages: Private algorithms for smooth sensitivity and mcan estimation", In: Advances in Neural Information Processing Systems 32 (2019) (cit. on pp. 3,
285
286
287
[BST14]
R. Bassily, A. Smith, and A. Thakurta. "Private empirical risk minimization: Effi- cient algorithms and tight error bounds". In: 2014 IEEE 55th Annual Symposium on Foundations of Computer Science. IEEE. 2014, pp. 464-473 (cit. on p. 6).
289
290
[CKS20]
C. L. Canonne, G. Kamath, and T. Steinke. "The discrete gaussian for differen- tial privacy". In: Advances in Neural Information Processing Systems 33 (2020), pp. 15676-15688 (cit. on p. 13).
291
292
[CMS11]
K. Chaudhuri, C. Monteleoni, and A. D. Sarwate. "Differentially private empir- ical risk minimization." " In: Journal of Machine Learning Research 12.3 (2011) (cit. on p. 6).
294
[DKMMN06]
Dwork, K. Kenthapadi, F. McSherry, I. Mironov, and M. Naor. "Our data, our- selves: Privacy via distributed noise generation". In: Annual international con- ference the theory and applications of cryptographic techniques. Springer. 2006, pp. 486-503 (cit. on p. 3).
297
298
299
300
[DK
A. Dvoretzky, J. Kiefer, and J. Wolfowitz. "Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator". In: The Annals of Mathematical Statistics (1956), pp. 642-669 (cit. on p. 15).
301
303
[DL09]
C. Dwork and J. Lei. "Differential privacy and robust statistics". In: Proceed- ings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 June 2, 2009. Ed. by M. Mitzenmacher. ACM, 2009, pp. 371-380 URL: https:/ / //d///do3. /doi. org/ / 10. 1145/ 10445/136414... 1536466 (cit. on pp. 2, 5. 5)
304
306
307
308
[DMNS06]
C. Dwork, F. McSherry, K. Nissim, and Smith. "Calibrating noise to sensi- tivity in private data analysis". In: Theory of cryptography conference. Springer. 2006, pp. 265 (65-284 (cit. on p. 1).
309
310
311
[DPW208]
X. Dang, H. Peng, X. Wang, and H. Zhang. "Theil-sen estimators in a multiple linear regression model". In: Olemiss Edu (2008) (cit. on pp. 2, 5).
10

---

313
[DR14]
C. Dwork and A. Roth. "The algorithmic foundations of differential privacy." In: Found. Trends Theor. Compur. Sci. 9.3-4 (2014), pp. 211-407. URL: https: pdf (cit. on p. 14). C. Dwork and G. N. Rothblum. "Concentrated differential privacy". In: arXiv preprint XrXiv: 100:1600 603301887 (2016) (cit. on p. 3).
314
315
//www cis upenn. edu/ httpr/rrtthaaapppppprrieeeeee
[DR16]
317
318
[TTZZ14]
C. Dwork, K. Talwar, A. Thakurta, and L. Zhang. "Analyze gauss: optimal bounds for privacy-rreeevvngg principal component analysis", In: Proceedings of forty-siii annual ACM symposium on Theory of computing. 2014, pp. 11-20 (cit. on p. 6).
319
320
321
322
[FS18]
V. Feldman and T. Steinke. "Calibrating noise to variance in adaptive data anal- ysis". In: Conference On Learning Theory. PMLR. 2018, pp. 535-544 (cit. on pp. 3, 6).
324
325
[GJK21]
J. Gillenwater, M. Joseph, and A. Kulesza. "Differentially private quantiles". In: International Conference on Machine Learning. PMLR. 2021, pp. 3713-3722
328
327
(cit. on P. 3).
328
[HBMALI9]
N. Holohan, S. Braghin, P. Mac Aonghusa, and K. Levacher. "Diffprivlib: the IBM differential privacy library". In: ArXiv e-prints 1907.02444 [cs.CR] (July 2019) (cit. on p. 8).
329
[1S16]
H. Imtiaz and A. D. Sarwate. "Symmetric matrix perturbation for differentially- private principal component analysis". In: 2016 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE, 2016, pp. 2339-
332
338
334
2343 (cit. on p. 6).
[JXZ16]
W. Jiang, C. Xie, and Z. Zhang. "Wishart mechanism for differentially private principal components analysis". In: Proceedings of the AAAI Conference on Ar- tificial Intelligence. Vol. 30. 1. 2016 (cit, on 6).
336
337
[KLMNS20]
H. Kaplan, K. Ligett, Y. Mansour, M. Naor, and U. Stemmer. "Privately learning thresholds: Closing the exponential gap". In: Conference on Learning Theory. PMLR. 2020, pp. 2263-2285 (cit. on p. p)
339
340
341
[KLNRSII]
P. Kasiviswanathan, H. K. Lee, K. Nissim, S. Raskhodnikova, and A. Smith. "What can we learn privately?" In: SIAM Journal on Computing 40.3 (2011), pp. 793- 826 (cit. on p. 6).
342
343
344
[LS21]]
P. Kairouz, Z. Liu, and T. Steinke. "The distributed discrete gaussian mechanism for federated learning with secure aggregation". In: International Conference
346
Machine Learning. PMLR. 2021, pp. 5221-5212 (cit. on p. 5).
347
[KLSU19]
G. Kamath, J. Li, V. Singhal, and J. Ullman. "Privately learning high- dimensional distributions". In: Conference on Learning Theory. PMLR. 2019, pp. 1853-1902 (cit. on pp. 3, 6).
348
349
[KSU20]
G. Kamath, V. Singhal, and J. Ullman. "Private mean estimation of heavy-tailed distributions". In: Conference on Learning Theory. PMLR. 2020, pp. 2204-2235 (cit. on p. 1).
351
353
[KV17]
V. Karwa and S. Vadhan. "Finite sample differentially private confidence inter- vals". In: arXiv preprint arXiv:1711.0333 (2017) (cit. on pp. 1,
354
355
[LKKO21]
X. Liu, W. Kong, S. Kakade, and S. Oh. "Robust and differentially private mean estimation".. In: Advances Neural Information Processing Systems. Ed. by M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan. Vol. 34. Curran Associates, Inc., 2021, pp. 3887-3901. URL:: /ttpss//prroceedinggs neurips.
356
358
http://///............coo///a/// Paper .df (cit. on p. 1).
360
351
[LKO21]
X. Liu, W. Kong, and S. Oh. "Differential privacy and robust statistics dimensions". In: arXiv preprini urXiv:2111.0657. (2021) (cit. on p. 1).
in high inequality".
382
363
[Mas90]
Massart. "The tight constant in the Beeerky--iiee--Wooo
364
In: The annals of Probability (1990), pp. 1269 1269-1283 (cit. on p. 15).
11

---

385
[MKF122]
J. Milionis, A. Kalavasis, D. Fotakis, and S. Ioannidis. "Differentially Private Regression with Unbounded Covariates". In: Proceedings of The 25th Interna- tional Conference on Artificial Intelligence and Statistics. Ed. by G. Camps- Valls, F. J. R. Ruiz, and I. Valera. Vol. 151. Proceedings of Machine Learning Research. PMLR, Mar. 2022, pp. 3242-3273. URI.: https: prw.eeddiccee.g... mlr. wrw.aeeeesv11111 wtt////mmmmiiiii/. F. McSherry and K. Talwar. "Mechanism design via differential privacy". In: 48th Annual IEEE Symposium on Foundations of Computer Science (7)CS'07).
386
368
369
370
html (cit. on p. 6).
[MT07a]
372
373
IEEE. 2007, pp. 94-103 (cit. on p. 3).
[MT07b]
F. McSherry and K. Talwar. "Mechanism Design via Differential Privacy". In: 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), October 20-23, 2007, Providence, RI, USA, Proceedings. IEEE Computer Society, 2007, pp. 94-103, URI.: https::/t/////tt //doii:///..i. http:///ooooooo/////oo/////////e 1109/FOCS. .207 .41 (cit. on p. 6).
375
378
377
378
379
[MT22]
B. McMahan and A. Thakurta, Federated Learning with Formal Differential Pri- vacy Guarantees. https / ai googleblog com 2022/ / 02/ federated- Shariing-wtth-frree
381
html. 2022 (cit. on l).
382
[NRS07]
K. Nissim, S. Raskhodnikova, and A. Smith. "Smooth sensitivity and sampling private data analysis". In: Proceedings of the thirty-ninth annual ACM sympo- sium on Theory of computing. 2007, pp. 75-84 (cit. on pp. 5, 6).
383
384
[RS21]
R. Rogers and T. Steinke. A Better Privacy Analysis of the Exponential Mech- anism. DiffcrentialPrivaccoorg https / differentiain aettiiiiiiiiayyyyy org / ronnde
386
387
exponential-mecchaeee
2021 (cit. on p. 14).
388
[SCS13]
Song, K. Chaudhuri, and A. D. Sarwate. "Stochastic gradient descent with differentially private updates". In: 2013 IEEE Global Conference on Signal and Information Processing. IEEE. 2013, pp. 245-248 (cit. on p. 6).
390
391
[Sen68]
P. K. Sen. "Estimates of the regression coefficient based on Kendall's tau". In: Journal of the American statistical association 63.324 (1968), pp. 1379-1389 (cit. on pp. 5).
382
394
[She17]
O. Sheffet. "Differentially Private Ordinary Least Squares". In: Proceedings of the 34th International Conference on Machine Learning. Ed. by D. Precup and Y. W. Teh. Vol. 70. Proceedings of Machine Learning Research. PMLR, Aug. 2017, pp. 14.. URL: https: / proceedings..... mlr press / v70 / sheffet17a. html (cit. on p. 6).
385
396
397
398
399
[She19]
O. Sheffet. "Old techniques in differentially private linear regression". In: Algo- rithmiic Learning Theory. PMLR. 2019, pp. 789-827 (cit. on p. 6).
401
[Smi08]
A. Smith. "Efficient, differentially private point estimators". In: arXiv preprint arXiv:0809.4794 (2008) (cit. on 3).
402
[Smil1]
A. D. Smith. "Privacy-preservin rates". In: Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011. Ed. by L. Fortnow and S. Vad- han. ACM, 2011 1, pp. 813-822, URL: https: / /oii org/ 10. 1145 0011111/99000 1993636. 1993743 (cit. on p. 3).
statistical estimation with optimal convergence
404
405
408
407
408
[SS21]
V. Singhal and T. Steinke, "Privately learning subspaces". In: Advances in Neural Information Processing Systems 34 (2021) (cit. on p. 6).
410
[Sza91]
J. Szarek. "Condition numbers of random matrices". In: Journal of Com-
plexity 7.2 (1991), pp. 131-149, ISSN: 0885-064X. URL: https www sciencedirect com/ coom/sciences httpe//rttlleeeeeeeeeeeeeeeeeeee cttpe//c////ceeeeeeaaerttlle/eee
412
httpa//eeeeeeeeeeeaea/e///////a/ /1000///0/00000000000000000 (cit. on
p. 15).
414
[The50]
H. Theil. "A rank-invariant method of linear and polynomial regression analy- sis". In: Indagationes mathematicae 12.85 (1950), p. 173 (cit. on pp. 2, 5).
415
[VJT22]
P. Varshney, P. Jain, and A. Thakurta. (Nearly) Optimal Private Linear Regres- sion via Adaptive Clipping. (personal communication). 2022 (cit. on p. 6).
417
[Wan18]
Y.X. Wang. "Revisiting differentially private linear regression: optimal and adaptive prediction estimation in unbounded domain". In: arXiv preprint arXiv: 02259 2018) (cit. on p. 6).
419
12

---

Checklist
421
422
1. For all authors...
423
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
424
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
426
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
427
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
431
(b) Did you include complete proofs of all theoretical results? [Yes]
432
3. If you ran experiments..
438
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [No]
434
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
436
437
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
438
439
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [No]
4. If you using existing assets (c.g., code, data, models) curating/relcasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
443
(b) Did you mention the license of the assets? [No]
444
(c) Did you include any new assets either in the supplemental material or as a URL? [No]
445
446
(d) Did you discuss whether and how consent was obtained from people whose data you're re using/curating? [N/A]
447
(e) Did you discuss whether the data you are using/curating contains personally identifi- able information or offensive content? [N/A]
449
450
5. If you used crowdsourcing or conducted research with human subjects...
451
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
453
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
454
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
456
457
A
Proof of Main Result
458
In this section, we prove Theorem 1.1. The proof is split into two parts: Proposition A. analyzes the privacy (which is a worst case property). Proposition A.2 analyzes the accuracy (which requires distributional assumptions).
460
Proposition A.I (Privacy). Algorithm satisfies cDDP and also
e² ed -CDD [BS16].
462
Our privacy proof follows the standard template of using the properties of the exponential mecha- nism along with the composition property of differential privacy.
463
464 In addition to a pure DP guarantee, we provide a concentrated DP guarantee. In high dimensional settings, concentrated DP is preferrable. To achieve p-zCDP, we would set /8dp. Note that
CDD can be converted to (e. DDD for any e 2 0 and = infa>1 ela-1)(ap-s) (1 1) 10-01
486
Je.g., CKS20, Cor. 13]. Asymptotically, achieve approximate (E, 0)DP it suffices set p
13

---

468
+
g2 log(1/6)
[BS16, Lem. 3.5]. The privacy claim of Theorem 1.1 follows by substituting
Sdp= O( V v ///log(1//) into Proposition A.I.
470
Proof of Proposition A.I. Algorithm invokes the exponential mechanism d times. We analyze one invocation and then apply composition.
471
The loss function max { = = (. 0,
(020) 8 has sensitivity 1 in terms of changing an element of the multiset θ. This is because it is the maximum of two counts. Each count naturally has sensitivity 1 and the maximum does not increase the sensitivity. Changing input
472
473
475
(Ig, ys) can change elements of θ as that input may appear in up to subproblems Sj,k- Thus the loss function has sensitivity in terms of changing one input.
477
The distribution we sample from
P[A.] & exp (- (-2ed max ([
8.) 0.)
22d
Note that the multiplier zra is e/d divided by twice the sensitivity. Thus [DRI4, Thm. 3.10] tells us that this sampling procedure is O)-D. Since we invoke this exponential mechanism indepen- dently d times (for all the coordinates of 0), we can apply basic composition [DR14, Thm. 3.14] to show that the overall algorithm (e, -D.
479
480
481
482
For the concentrated DP analysis, we can use an improved analysis of the exponential mechanism [RS21] that show that, in addition to (s/d, D), each invocation of the exponential mechanism satisfies [e/ (CDDP. Finally, we can apply composition for concentrated DP [BS16] over the invocations to show that the overall algorithm is p-zCDP with 8 (e/d)² == s
484
485
Next we provide theoretical utility guarantee. However,the proof of the pudding is in the eating, so we direct the reader to the experimental results in Section to see how our algorithm performs in practice.
487
|n/d], and E [ri] of Algorithm Let us also fix O" [[], and a > O. Assume the imputs (11, (Iz,
Proposition A.2 (Accuracy). Fix the parameters E O, n,d,r E E E = =
R = -1+
480
(Ii, Mn) E TRd x R are drawn i.dd as follows. Independently for each i [n), we have x; + NO, T) and then, conditioned on YAs we have y/i c (N( [[(00,.xi 2x4), o²). If
y2), (12,32),
482
493 is the output of Algorithm with the above inputs and parameters, then, for all B > 0, we have
]
1
log(d/3)
P P0-00 10 1x
-- to
log Em
21-
2 1-33,
494
where the probability is over both the randomness of the algorithm and the inputs.
495
The proof consists of three steps: First, we use the properties of the exponential mechanism to show that Algorithm 1 outputs a point with low empirical loss. Second, we use a generalization result to
496
437
show that the output also has low population loss. Third, we use the distributional assumptions in the theorem to show that low population loss implies that the output is indeed close to the desired value.
499
500
The first lemma shows that, with high probability, the empirical loss is low.
Lemma A.3. Let e, m, R. θ, and Ô be as in Algorithm 1. Assume | < co. Independently. for each and all 3 > 0, we have
502
Pa max {EEDE o, < < 0, 8.}} <
O 2
2dd
| 3
)]
log
2 1 1-
503 Proof. First, we note that the empirical median of (0, A E θ) has loss at most ||0]/2]. Combining
504 this with the standard utility analysis of the exponential mechanism [DR14, Thm. 3.11] yields the result. Finally, remark that Algorithm I samples each coordinate of 0 independently.
D
14

---

506
Our second lemma helps us relate the empirical loss to the population loss. That is, it is general- ization result.
507
Lemma A.4 (DKW inequality (DKW56; Mas90J). There exists universal finite constant C
509
such that the following holds. Let F be the cumulative distribution function (CDF) of probability
510
distribution on R and let X1, X2..,....,
be independent samples from that distribution i.e.
= S for all E [m]. Then
1 Σ S -F((()
log (C/3) 2m
BB > 0 Px
sup ZER
2 1 - B
512
Now we bring the distributional assumptions of Proposition A.2 into the analysis. For each of the subproblems,
given X E Ruxd and y IR.. The assumption is that X consists of i..d. standard Gaussian entries and that y X + 2, where + (0,0, o²1) is noise. Our goal is to estimate the unknown true parameters 8 E R The estimate for the subproblem is == x 0 X 2. Thus need to understand the distribution of X We begin by bounding the norm of X- Then, in Lemma A.6, we use this bound to show that the distribution of x- is sufficiently concentrated around zero, which necessary to ensure the median is well-behaved.
514
515
517
Lemma A.S. Let X E Iaxd have entries which are all independent standard Gaussians. There exists a universal constant such that for all r E (0.3/4) 3/4).
620
P 1 = (irace((xxx"=="
C d//d/ 2 21-7
Proof. Let X1 S xxXX) .... S xxXx denote the eigenvalues of X X in sorted order with multiplicities. Then (racce(Xx"") Σ 1/A,(Xx").
522
523 Szarek [Sza91] (Thm. 1.2, eq. 1.2) shows that, for all j E [d] and all a 2 0.
[x(XXT)
a.j Vd S (v2e (v2e-a)².
524
By a union bound, for all a [0,1/4], we have
a² .².
P VjE [d] 1x(x²))
2 Σ 2e a)}² 2
d
V2e
/2e a) 13((j-1]
2 1 3a.
(V2e a))
j=1
If Xxx) 2 x².² for all j E [4]. then
525
20 n2d
trace (X = Σ 1/A,(XX²)
5 a2.
> j=1
6a
To complete the proof, a = 7/3 1/4 and C 3n 2 < 15
527 Lemma A.6. Let X E Rdxd and E Rd have entries which are all independent standard Gaus- sians. Letuu Rdd be an arbitrary unit vector that is independent from X and y. Then the distribution 529 of u² X-1 is continuous and symmetric around 0. Furthermore, for all I. 2 0,
P Plu"xx
S 2
8V0
530 where is a standard Gaussian and C is the univeral constant from Lemma A.5.
531 Proof. The distribution of nf X a mixture centered univariate Gaussians. Specifically, and X are fixed, then u² X --y ~ NV (u"² - The randomness of u and X induces
15

---

533
mixture. From this it is immediate that the distribution is symmetric about 0 and that it is continuous (as (illll"'x-"""
534
0] 0).
Since the distribution of X is spherically symmetric, so too that of X-1, This means that the choice of is irrelevant. In particular, we can assume that is uniformly random unit vector (independent from everything else).
535
537
Fix t 0 and else). Then
0. Let g denote standard univariate Gaussian (independent from everything
539
Pluu x- v1 s = B [Plllu' x yl S !]]
u.X
w.x (Poll(uu" x 12 |g| s t]]
2 Pollgl s t/s] P. xxxll xxxxIl('"xxx""" - s].
540 Now we need bound X(u"X-1))' We can express this quantity in terms of the Frobenius
541 matrix inner product:
11 x u² (xx") - un²)
542 We have E [un")
-11. Thus, by linearity of expectation,
x 1 = ((xxT)- 4 (xxcc((X -1p. -1
Fix 1/vd. By Markov's inequality,
Pu [[[[[xxx x 1l2 11| [|]
1 1 P. [1(x2xx1) > 11 2
E |||
-1
du
5M
Thus
Fu,x xxxxxx1120 12 S 8
Fu 50px-111 Px ||X 1| S s/u0 2
( (1- du
Px ||x 1| s s/u].
545 Lemma A.5 bounds || namely |x||XX=1|| 2 s/ul 1 CCd v/s 2 1/4 for some universal constant C. Putting everything together gives
p|lu"x xir-x-yl-- vl s
2 PP [b1 s t/s]
(1-
1
( 1
VCdu
dud
We set v == 2/Vd and SVC, which gives
547
P[lu" p|lu"x1' x-1 vl s pg [bl st/svc]
3 3
4 4
548
549
Now is time to assemble the proof:
To see this, imagine u 21 is generated by taking a column of a uniformly random unitary matrix
U (wn, u2.... ua) E ddd By symmetry. E [ur']]] E [uau]] =... [uau]]- Since Σ u.u,"" U = I. we have E [uuu]] $1.
16

---

550
Proof of Proposition A.2. Fix i E [d] and let e, E Rd be the i-th standard basis vector. For jt, E R, define a distribution D on as μ + a of x y where X E Rexd and y E IRd consist of
551
independent standard Gaussians. We will denote the CDF as Du.o t) - P [u+o- - X < 1 and its complement as ( 1) = PP [u- ju= a _e,"ee'' x-xyy y > 1] for all E TR. (By Lemma A.6, 'D Du.o continuous (if Ø > 0), so we do not need to worry about the strictness of the inequality.) Define HoRR to be D Du.a projected to R i.e. to sample + D....R. we sample 0 + D Du,e and let 556
552
553
554
555
arg gingeR 0 - 0/. We will denote the CDF similarly as before (although now the strictness of the inequality may matter).
{{ -1 : iE [rl]. we have
558
We must reason about the impact of rounding to R. Since R =
<t (st-
1 r-1 S D ())
if > 1, then DuAa
and
if / < 1, then Du.e (>1+ 1 1
S D Pp. 1).
This is because the rounding can only move points by - (unless those points are outside the
560
interval [-1,+1]) Note that, if t S Hr, then Du (< t) S 2 and, similarly, if t 2 μ4, then
561
Du (> 5-
582
We run Algorithm I with the parameters E, d = 1, and R. We assume the input has the distribution given in the statement of Theorem 1.1. That is, independently for each i, we have Ty + (O,
563
564
and yi = (0", .2,) + 2; for 2; < NO(0 1).
585
Let θ be as constructed in Algorithm 1. Then the multiset θ {0: 0 Q consists of m
586
n /d] independent samples from the distribution Doj,0,0 defined above.
567
By Lemma A.3, with probability at least 1 - 3, we have
max { 0 0: 0, < 2 1.0000000000000 0.31
O 2
2ld
R
S
+
log
B
568
Note |0] = E. m = m. By Lemma A.4, with probability at least
8, we have
1 m
| Do <. 0.)
log(C/B 2m
5
589 and, similarly, with probability at least 1 B
1 m
00 [ > 8:}1 Deg, 0.))
log(C/B)
=
2m
570 where some universal constant. Applying a union bound, we have, for all /3 > O,
P max
D,),Da; a 0.) s
1 2
2d em
log
R
+
log (C/3)
> 1 - 1-38.
B
2m
571 It follows that
P max { Do (< )
(<0:-r-)) Doy.o
1
2d
log (og(C/B) 2m
> 0, +
+
log
+
2 1-33.
2
em
3
The last step in the proof to convert this bound on the quantile into an accuracy bound. Lemma A.6 tells us that the center of the distribution is at 8 2 -i..., Doj (< 0,) Dø (> 8,) 1/2 and that the distribution is roughly concentrated around this point Gaussian with variance O(a). In 575 particular, if 2 0z, then
572
1 Dop o (< 2 +
0 S 5 8
1 +0 +2
2" 2g-1(0.1)
8/Co_
2
17

---

578
where C' is the universal constant from Lemma A.5. Similarly, if t - 6% then
1 + P PB--rro.1 5 Do ( 1) (> 2
0f -
1
-
0
+
8vCo
-2 2
577
Combining these inequalities gives
max { (o0900 (< - r r- (<):---)) 1--11 Doç.a (> 0i + r-
10: 0-
2 +
-
S 5 0
r-1
2 2
8vCo
10:
071
+ +
r-1
2
578
This rearranges to
10--01 -
-
r- + t
1
max Do (<
Doj.o
> + r-
} 2
579
Combining with the high probability bound establishes
1 +o. O
2d
(og(C/3)
P 0, - 071
log
33.
em
2m
To obtain the stated result, we simply take a union bound over all [d] and simplify the constants.
581
18


Reviews:
[{"review_id": "yA_d2z92QIm", "reviewer": "Reviewer_bc18", "summary": "The paper studies the problem of differentially private linear regression and develops a new algorithm for this problem based on privately calculating 1-dimensional medians. The algorithm is based on the Theil-Sen estimator and uses the exponential mechanism to privately estimate the medians required for this estimator. The authors present a utility guarantee for their algorithm with Gaussian features and Gaussian noise. Moreover, they provide some experiments over synthetic datasets that compare their algorithm to existing algorithms.", "questions": "No", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper studies an important problem (private linear regression). However, I think the authors need to present more theoretical results, comparison to prior work, and experimental evidence to make this paper more compelling.\n\nWeaknesses\n1.\tThe main (and only) theoretical result in the paper provides utility guarantees for the proposed algorithm only when the features and noise are Gaussian. This is a strong requirement on the data, especially given that previous algorithms don’t need this assumption as well. Moreover, the authors should compare the rates achieved by their procedure to existing rates in the literature.\n2.\tExperiments: the experimental results in the paper don’t provide a convincing argument for their algorithms. First, all of the experiments are done over synthetic data. Moreover, the authors only consider low-dimensional datasets where d<30 and therefore it is not clear if the same improvements hold for high-dimensional problems. Finally, it is not clear whether the authors used any hyper-parameter tuning for DP-GD (or DP-SGD); this could result in significantly better results for DP-GD.\n3.\tWriting: I encourage the authors to improve the writing in this paper. For example, the introduction could use more work on setting up the problem, stating the main results and comparing to previous work, before moving on to present the algorithm (which is done too soon in the current version). \n\n\nMore:\n\n1.\tTypo (first sentence): “is a standard”\n2.\tFirst paragraph in page 4 has m. What is m? Should that be n?\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "vw8fvwkWYW", "reviewer": "Reviewer_qDNE", "summary": "This paper studies differentially private linear regression with known covariance for isotropic Gaussian data. The algorithm is based on the median-of-mean scheme and Theil-Sen estimator. It first splits the data into different partitions, then solves the solutions for each partition, and computes the univariate median for each coordinate of the solutions using the exponential mechanism. For approximate DP, the extra cost of privacy in terms of infinity norm is $O(d^{1.5}/\\varepsilon n)$, which has a $O(d^{0.5})$ gap to the lower bound. The primary advantage of this algorithm is that it does not need any clipping, which is more practical. Empirically, this paper provides extensive experiments and shows better performance for d=10, 20, 30 compared to a few baselines. ", "questions": "1. Why is the size of each partition chosen as d?\n\n2. Theorem 1 runs algorithm 1.1 with $\\ell=1$. How does different choices of $\\ell$ affect the utility guarantees?", "limitations": "This paper is theoretical and does not have a direct negative societal impact.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: 1. This algorithm is simple and practical. \n2. The presentation of this paper is clear. The structure is easy to follow.\n\n\nLimitations: 1. Compared to prior works, for example [VJT22], this algorithm is not optimal. 1) Under the euclidian norm and gaussian data, the algorithm in [VJT22] has extra privacy cost $O(d/(\\varepsilon n))$. The extra cost here is $O(d^{1.5}/\\varepsilon n)$ in infinity norm. 2) This paper requires prior knowledge of the covariance of the Gaussian. 3) The loss is for infinity norm, which has $d^{0.5}$ gap to the euclidean norm. 4) In the experiments, this paper does not compare the algorithm with [VJT22], which shouldn't be too hard to implement.\n\n2. Similar ideas have been used for mean estimation with sub-gaussian rates [1], DP mean estimation [2], linear regression[3]. It seems that, as a byproduct of the median of mean scheme, these types of algorithms could also provide provable robustness guarantees against corruption of the data. This is not discussed in this paper. Also, it would be better if the authors could add some related works in these topics.\n\n\n[1] Hopkins, S. B. (2020). Mean estimation with sub-Gaussian rates in polynomial time. The Annals of Statistics, 48(2), 1193-1213. \n[2] Hopkins, S. B., Kamath, G., & Majid, M. (2022, June). Efficient mean estimation with pure differential privacy via a sum-of-squares exponential mechanism. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (pp. 1406-1417).\n[3] Depersin, J. (2020). A spectral algorithm for robust regression with subgaussian rates. arXiv preprint arXiv:2007.06072.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "khIXIC4UfA3", "reviewer": "Reviewer_mEFt", "summary": "This paper addresses the problem of differentially private linear regression. Specifically, current DP methods need access to the sensitivity of the query which is in practice hard to compute. Alternative methods clip the data, harming performance. This paper proposes a method that relies on privately computing a multidimensional “median”, a good estimator for the mean under certain assumptions and that has smaller sensitivity. ", "questions": "- How to compute range R in real applications? if R is set too large, then the exponential mechanism will add too much mass to small depth points, and if it is too small, the range may not even contain the real model. \n- How does the restriction in line 80 compares to clipping?\n- Why use the max instead of the min in the score function? Wouldn't this assign very high utility to a point in the boundary?\n- Why is $\\sigma$ described as a parameter? I don’t see it used for any pre-processing or actual algorithm step. \n- Can you discuss the choice of hyperparameters for DP-GD?\n- Can you discuss the results in figure 5? why does the Widened Exponential from [AMSSV22] degrade in lower dimensions?\n", "limitations": "- The paper motivates well the use of a \"high dimensional private median\" for DP linear regression. However, it is not clear how this will overcome the challenges that current methods face, like clipping, since setting a range R is basically finding a clipping rate. \n- Step 15 for calculating the median could result in a point outside the closure of datapoints. A common example for this is having points (1,0,0), (0,1,0), and (0,0,1). Taking the median along each axis results in (0,0,0) which is outside the plane defined by the three points. \n- Experimental section is based on synthetic data that follows the assumptions on theorem and thus provides guidance on how to select the parameters, however, realistic datasets may behave very differently.\n- Experimental section only compares to one set of fixed parameters of DP-SGD. Perhaps following guidance from theory or discussing the choice of hyperparameters for DP-GD could justify this choice. \n\nIn general, the paper proposes an alternative approach but that still requires an equivalent to clipping, and this is not addressed neither theoretically nor empirically. ", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "*Strengths*\n- Nice analysis and intuition for Gaussian data.\n- Very clear and organized. \n- Good related work and comparison section.\n\n\n*Weaknesses*: \n- Missing relevant recent work on DP-medians/quantiles. \n- Experiments only test on synthetic data that meets the assumption. However, finding a reasonable r (even in small settings) could be hard. \n- Data complexity could be rather large, and prohibitive in real settings where linear regression datasets are rather small.\n- The high dimensional median proposed in step 15 may not even be an interior point in the convex closure of the data points. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Reject