Easy Differentially Private Linear Regression
Authors: Kareem Amin
Matthew Joseph
Mónica Ribero
Sergei Vassilvitskii
Venue: ICLR 2023 poster (2023)
Keywords: differential privacy
linear regression

Abstract: Linear regression is a fundamental tool for statistical analysis. This has motivated the development of linear regression methods that also satisfy differential privacy and thus guarantee that the learned model reveals little about any one data point used to construct it. However, existing differentially private solutions assume that the end user can easily specify good data bounds and hyperparameters. Both present significant practical obstacles. In this paper, we study an algorithm which uses the exponential mechanism to select a model with high Tukey depth from a collection of non-private regression models. Given $n$ samples of $d$-dimensional data used to train $m$ models, we construct an efficient analogue using an approximate Tukey depth that runs in time $O(d^2n + dm\log(m))$. We find that this algorithm obtains strong empirical performance in the data-rich setting with no data bounds or hyperparameter selection required.

Published as a conference paper at ICLR 2023
EASY DIFFERENTIALLY PRIVATE LINEAR REGRESSION
Kareem Amin
Matthew Joseph
Mónica Ribero
Sergei Vassilvitskii
ABSTRACT
Linear regression is a fundamental tool for statistical analysis. This has motivated the development of linear regression methods that also satisfy differential privacy and thus guarantee that the learned model reveals little about any one data point used to construct it. However, existing differentially private solutions assume that the end user can easily specify good data bounds and hyperparameters. Both present significant practical obstacles. In this paper, we study an algorithm which uses the exponential mechanism to select a model with high Tukey depth from a collection of non-private regression models. Given n samples of d-dimensional data used to train m models, we construct an efficient analogue using an approximate Tukey depth that runs in time Oddn + dm log(m)). We find that this algorithm obtains strong empirical performance in the data-rich setting with no data bounds hyperparameter selection required.
INTRODUCTION
Existing methods for differentially private linear regression include objective perturbation (Kifer et al., 2012), ordinary least squares (OLS) using noisy sufficient statistics (Dwork et al., 2014; Wang, 2018; Sheffet, 2019), and DP-SGD (Abadi al., 2016). Carefully applied, these methods can obtain high utility in certain settings. However, each method also has its drawbacks. Objective perturbation and sufficient statistics require the user to provide bounds on the feature and label norms, and DP-SGD requires extensive hyperparameter tuning (of clipping norm, learning rate, batch size, and so on).
In practice, users differentially private algorithms struggle to provide instance-specific inputs like feature and label norms without looking at the private data (Sarathy et al., 2022). Unfortunately, looking at the private data also nullifies the desired differential privacy guarantee. Similarly, while recent work has advanced the state of the art of private hyperparameter tuning (Liu & Talwar, 2019; Papernot & Steinke, 2022), non- non-private hyperparameter tuning remains the most common and highest utility approach in practice. Even ignoring its (typically elided) privacy cost, this tuning adds significant time and implementation overhead. Both considerations present obstacles to differentially private linear regression in practice.
With these challenges in mind, the goal of this work is to provide an easy differentially private linear regression algorithm that works quickly and with no user input beyond the data itself. Here, "ease" refers to the experience of end users. The algorithm we propose requires care to construct and implement, but it only requires an end user to specify their dataset and desired level of privacy. We also emphasize that ease of use, while nice to have, is not itself the primary goal. Ease of use affects both privacy and utility, as an algorithm that is difficult use will sacrifice one or both when data bounds and hyperparameters are imperfectly set.
1.1 CONTRIBUTIONS
Our algorithm generalizes previous work by Alabi et al. (2022), which proposes differentially private variant of the Theil-Sen estimator for one-dimensional linear regression (Theil, 1992). The core idea is to partition the data into m subsets, non-privately estimate a regression model on each, and then apply the exponential mechanism with some notion depth to privately estimate high-depth model from restricted domain that the end user specifies. In the simple one-dimensional case (Alabi et al.,
(kamin, mijoseph, mrihero, sergeiv) ) @google.com. Part of this work done while Mónica was UT Austin.

---

Published as a conference paper at ICLR 2023
2022) each model is slope, the natural notion of high depth is the median, and the user provides an interval for candidate slopes.
We generalize this in two ways obtain our algorithm, TukeyEM. The first step is to replace the median with multidimensional analogue based on Tukey depth. Second, we adapt a technique based on propose-test-rele testrreaase (PTR), originally introduced by Brown et al. (2021) ) for private estimation of unbounded Gaussians, to construct an algorithm which does not require bounds on the domain for the overall exponential mechanism. We find that a version of TukeyEM using an approximate and efficiently computable notion of Tukey depth achieves empirical performance competitive with (and often exceeding) that of non-priivately tuned baseline private linear regression algorithms, across several synthetic and real datasets. We highlight that the approximation only affects utility and efficiency; TukeyEM still differentially private. Given an instance where TukeyEM constructs m models from n samples of d-dimensional data, the main guarantee for our algorithm is the following:
Theorem 1.1. TukeyEM is (e, 6D- and takes time (d + dm log(m)).
Two caveats apply. First, our use of PTR comes at the cost of approximate (c. 6)DD guarantee as well as a failure probability: depending on the dataset, it is possible that the PTR step fails, and no regression model is output. Second, the algorithm technically has one hyperparameter, the number m of models trained. Our mitigation of both issues is empirical. Across several datasets, we observe that a simple heuristic about the relationship between the number of samples n and the number of features d, derived from synthetic experiments, typically suffices to ensure that the PTR step passes and specifies high-utility choice of m. For the bulk of our experiments, the required relationship on the order of n 2 1000 d. We emphasize that this heuristic is based only on the data dimensions and d and does not require further knowledge of the data itself.
1.2 RELATED WORK
Linear regression is a specific instance of the more general problem of convex optimization. Ignoring dependence on the parameter and input space diameter for brevity, DP-SGD (Bassily et al., 2014) and objective perturbation (Kifer et al., 2012) obtain the optimal ((v//s) error for empirical risk minimization. AdaOPS and AdaSSP also match this bound (Wang, 2018). Similar results are known for population loss (Bassily et al., 2019), and still stronger results using additional statistical assumptions on the data (Cai et al., 2020; Varshney et al., 2022). Recent work provides theoretical guarantees with no boundedness assumptions on the features or labels (Milionis et al., 2022) but requires bounds on the data's s covariance matrix to use an efficient subroutine for private Gaussian estimation and does not include an empirical evaluation. The main difference between these works and ours is empirical utility without data bounds and hyperparameter tuning.
Another relevant work is that of Liu et al. (2022), which also composes PTR step adapted from Brown et al. (2021) with a call to a restricted exponential mechanism. The main drawback of this work is that, with the previous work (Brown al., 2021), neither the PTR step the restricted exponential mechanism step is efficient. This applies to other works that have applied Tukey depth private estimation as well (Beimel et al., 2019; Kaplan et al., 2020; Liu al., 2021; Ramsay & Chenouri, 2021). The main difference between these works and ours is that our approach produces efficient, implemented mechanism.
Finally, concurrent independent work by Cumings-Ment (2022) also studies the usage of Tukey depth, as well as the separate notion of regression depth, privately select from a collection of non-private regression models. A few differences exist between their work and ours. First, they rely on additive noise scaled to smooth sensitivity to construct private estimate of a high-depth point. Second, their methods are not computationally efficient beyond small d, and are only evaluated for < Third, their methods require the end user to specify bounds on the parameter space.
2 PRELIMINARIES
We start with the definition of differential privacy, using the "add-remove" variant.
Definition 2.1 (Dwork et al. (2006)). Databases D, D' from data domain X are neighbors, denoted D D'. if they differ in the presence or absence of single record. A randomized mechanism
2

---

Published as a conference paper at ICLR 2023
M: - - (E,, private (DP) ffr all D D' X and any S S
P. (M(D) S) PM [M(D') E 5) +
When d = 0, MM is E-DP. One general c-DP algorithm is the exponential mechanism.
Definition 2.2 (McSherry & Talwar (2007)). Given database and utility function : xxxx) y - R
mapping (database, output) pairs scores with sensitivity
A
max D yEy
(u(D,y) u(D',y)l.
the exponential mechanism selects item y E y with probability proportional to exp ( (cu(D.v)) We say the utility function is monotonic for D1 C D2. for any u(D1. S u(D2.y). Given monotonic u, the 2 inside the exponent denominator can be dropped.
Lemma 2.3 (McSherry Talwar (2007)). The exponential mechanism is e-DP.
Finally, we define Tukey depth.
Definition 2.4 (Tukey (1975)). A halfspace he is defined by vector v E R', hy = {v E Rd (v, 2 0}. Let D C R be collection of n points. The Tukey depth TD( of (ppint RR with respect to D is the minimum number of points in D in any halfspace containing y.
Tn(w)= = min Elech
holyche RED
Note that for a collection of n points, the maximum possible Tukey depth is n/2. We will prove theoretical utility result for version of our algorithm that uses exact Tukey depth. However, Tukey depth is NP-hard to compute for arbitrary d (Johnson & Preparata, 1978), so experiments instead use a notion of approximate Tukey depth that can be computed efficiently. The approximate notion of Tukey depth only takes minimum
the 2d halfspaces corresponding the canonical basis.
Definition 2.5. Let E = {eI,...,ed] be the canonical basis for IR and let D C Rd. The approximate Tukey depth of a point E IR with respect to D, denoted TD(y). is the minimum number of points D any of the 2d halfspaces determined by E. containing y.
Tn(y) eg esjccEEE.nEEhee
Σ 1athypey'
min
RED
Stated more plainly, approximate Tukey depth only evaluates depth with respect to the axis-aligned directions. A simple illustration of the difference between exact and approximate Tukey depth appears Figure the Appendix's 's Section 7.1. For both exact and approximate Tukey depth, when D clear from context, we omit it for neatness.
3 MAIN ALGORITHM
Our algorithm, TukeyEM, consists of four steps:
Randomly partition dataset into m subsets, non-privately compute the OLS estimator on each subset, and collect the estimators into set 1
2. Compute the volumes of regions of different approximate Tukey depths with respect to (8
3. Run a propose-testeeeeeeeeeeeeeee testrrelase (PTR) algorithm using these volumes. If it passes, set B to be the region of &d with approximate Tukey depth at least m/4 in {8, )m and proceed to the next step. If not, release 1. (failure).
4. If the previous step succeeds, apply the exponential mechanism, using approximate Tukey depth as the utility function, to privately select point from B.
A basic utility result for the version of TukeyEM using exact Tukey depth appears below. The result a direct application of work from Brown et al. (2021), and the (short) proof appears in the Appendix's Section 7.2..
3

---

Published as a conference paper at ICLR 2023
Theorem 3.1 (Brown et al. (2021)). Let O < aa,y < 1 and let S {Be.... 3m be an i.i.d. sample from the multivariate normal distribution N(3", Σ) with covariance Σ E Rddd and mean
E [3:]] = 3 E Rd Given 3 E IRd with Tukey depth at least with respect to S, there exists a constant e >> O such that when m 2 c.
(d+log(/m)) with probability 1 - II 8 11x I + (1 p/ m + a),
a²
where & denotes the CDF of of the standard univariate Gaussian.
In practice, we observe that empirical distributions models for real data often feature Gaussian-like concentration, fast tail decay, and symmetry. Plots of histograms for the the models learned by TukeyEM on experiment datasets appear in the Appendix's 's Section 7.7. Nonetheless, we empha- size that Theorem 3.1 is a statement of sufficiency, not necessity. TukeyEM does not require any distributional assumption to be private, nor does non-Gaussianity preclude accurate estimation.
The remaining subsections elaborate the details of our version using approximate Tukey depth, culminating in the full pseudocode in Algorithm 2 and overall result, Theorem 1.1.
3.1 COMPUTING VOLUMES
We start by describing how compute volumes corresponding to different Tukey depths. As shown in the next subsection, these volumes will be necessary for the PTR subroutine.
Definition 3.2. Given database D, define Vi,D = vol((y E Id and (D) 2 i)), the volume of the region of points in Idd with approximate Tukey depth at least i in D. When is clear from context, we write for brevity.
Since our notion of approximate Tukey depth uses the canonical basis (Definition 2.5), it follows form a sequence of nested (hyper)rectangles, as shown in Figure 3. With
that V1, Ve..... .i........,, V/ this observation, computing a given V; is simple. For each axis, project the non-private models {. onto the axis and compute the distance between the two points of exact Tukey depth i (from the "left" and "right"" in the one-dimensional sorted array. This yields one side length for the hyperrectangle. Repeating this d times in total and taking the product then yields the total volume of the hyperrectangle, as formalized next. The simple proof appears in the Appendix's 's Section 7.2.
Lemma 3.3. Lines 5 to 10 of Algorithm 2 compute [Vi)e
m/2 in time (dm log(m)).
3.2 APPLYING PROPOSE-
The next step of TukeyEM employs PTR restrict the output region eventually used by the exponen- tial mechanism. We collect this process into a subroutine PTRCheck.
The overall strategy applies work done by Brown et al. (2021). Their algorithm privately checks if the given database has a large Hamming distance to any "unsafe" database and then, if this PTR check passes, runs an exponential mechanism restricted "safe" database is defined as one where the restricted exponential mechanism has similar output distribution on any neighboring database, the overall algorithm is DP. As part of their utility analysis, they prove lemma translating volume condition on regions of different Tukey depths to lower bound on the Hamming distance to an unsafe database (Lemma 3.8 (Brown et al., 2021)). This enables them to argue that the PTR check typically passes if it receives enough Gaussian data, and the utility guarantee follows. However, their algorithm requires computing both exact Tukey depths of the samples and the current database's ' exact Hamming distance unsafety. The given runtimes for both computations are exponential in the dimension d (see their Section C.2 (Brown et al., 2021)).
domain of high Tukey depth. Since a
We rely on approximate Tukey depth (Definition 2.5) to resolve both issues. First, as the previous section demonstrated, computing the approximate Tukey depths of a collection of m d-dimensional points only takes time Odm log(m)). Second, we adapt their lower bound to give I-sensitive lower bound on the Hamming distance between the current database and any unsafe database. This yields an efficient replacement for the exact Hamming distance calculation used by Brown et al. (2021).
The overall structure of PTRCheck is therefore as follows: use the volume condition to compute a 1 senssiiiee lower bound on the given database's distance to unsafety; add noise to the lower bound
WWe assume is even for simplicity. The algorithm and its guarantees are essentially the same when is odd, and our implementation handles both cases.
4

---

Published as a conference paper at ICLR 2023
Algorithm PTRCheck
Input: Tukey depth region volumes V, privacy parameters e and 6
2: Use Lemma 3.6 with t = and See to compute lower bound for distance to unsafe database
3: if Lap (1/e) 2 log(1/26) then
4: Return True
5: else
6:
Return False
and compare a threshold calibrated so that an unsafe dataset has probability I passing; and if the check passes, run the exponential mechanism to pick a point of high approximate Tukey depth from the domain of points with moderately high approximate Tukey depth. Before proceeding to the details of the algorithm,
first define few necessary terms.
Definition 3.4 (Definition 2.1 Brown et al. (2021)). Two distributions P. Q over domain W are (c, (). -iidisstinguishable, denoted P e_6 Q, for any measurable subset W C W,
P Pwwp [w E W] < e & [w E W| + 5 and IadFaa F [w E W] S P'PPw [w E W] +
Note that (s, DD is equivalent to (s, 8) iiidisitinuuishabbityy between output distributions arbitrary neighboring databases. Given database D, let A denote the exponential mechanism with utility function TD (see Definition 2.5). Given nonnegative integer t, let A, denote the same mechanism that assigns score -oo to any point with score < f, i.e., only samples from points of score 2 t. We will say a database "safe" if A, is indistinguishable between neighbors.
Definition 3.5 (Definition 3.1 Brown et al. (2021)). Database D is (e, 8, t)-safe for all neighboring D' D, we have (D) Re,8 AD(D"). Let Safe the set of safe databases, and let (n.afe be its complement.
We now state the main result of this section, Lemma 3.6. Briefly, it modifies Lemma 3.8 from Brown al. (2021) to construct I-sensitive lower bound distance to unsafety.
Lemma 3.6. Define M(D) to be mechanism that receives as input database D and computes the largest k (0,... .0....,t- 1} such that there exists g O where, for volumes V defined using monotonic utility function,
Vi-K-1,D
rg/2 <8
Ve+k+g+1,D
or outputs -1 if the inequality does not hold for any such k. Then for arbitrary D
1. .M I-sensitive, and
2. for all Unsafe(e. dn M(D).
The proof of Lemma 3.6 appears in the Appendix's Section 7.2. Our implementation of the algorithm described by Lemma 3.6 randomly perturbs the models with small amount of noise to avoid having regions with 0 volume. We note that this does not affect the overall privacy guarantee.
PTRCheck therefore runs the mechanism defined by Lemma 3.6, add Laplace noise to the result, and proceeds to the restricted exponential mechanism if the noisy statistic crosses threshold. Pseudocode appears in Algorithm 1, and we now state its guarantee as proved in the Appendix's 's Section 7.2.
Lemma 3.7. Given the depth volumes V computed in Lines PVR is e-DP and takes time Om log(m)).
10 of Algorithm
3.3 SAMPLING
PTRCheck passes, TukeyEM then calls the exponential mechanism restricted to points of ap- proximate Tukey depth at least f m/4, subroutine denoted EearrittedTukkyEEE (Line 12 in Algorithm 2). Note that the passage of PTR ensures that with probability at least 1 - 8, running RestrictedTukkyEM. TukeyEM is OD We use common two step process for sampling from an exponen- tial mechanism over continuous space: 1) sample depth using the exponential mechanism, then 2) return uniform sample from the region corresponding the sampled depth.
5

---

Published as a conference paper at ICLR 2023
3.3.1 SAMPLING DEPTH
We first define slight moditication W of the volumes introduced earlier.
Definition 3.8. Given database D, define Wi = vol({y y E R and Tb(y) = i}). ). the volume of the region of points in R with approximate Tukey depth exactly i D.
To execute the first step of sampling, for E {m/4, m/4 ..... , m/2), WT.D = VID V++.DD so we can compute ) from the V computed earlier in time (m). The restricted exponential mechanism then selects approximate Tukey depth i {m/4, m/4 + 1,...,,.. m/2) with probability
P P x WiDD exp(e i).
Note that this expression drops the 2 in the standard exponential mechanism because approximate Tukey depth is monotonic; see Appendix Section 7.3 for details. For numerical stability, racing sampling Medina & Gillenwater (2020) can sample from this distribution using logarithmic quantities.
3.3.2 UNIFORMLY SAMPLING FROM A REGION
Having sampled depth ž, it remains to return uniform random point of approximate Tukey depth i. By construction, W a is the volume of the set of points = (vi...., yd) such that the depth along every dimension j least i, and the depth along at least one dimension j' is exactly i. The result is straightforward when d = 1: draw a uniform sample from the union of the two intervals of points of depth exactly à (depth from the "left" and "right").
For d > 1, the basic idea of the sampling process is to partition the overall volume into disjoint subsets, compute each subset volume, sample subset according to its proportion in the whole volume, and then sample uniformly from that subset. Our partition will split the overall region of depth exactly according to the first dimension with dimension-spedie point in the overall region has at least one such dimension, this produces a valid partition, and we will see that computing the volumes of these partitions is straightforward using the S computed earlier. Finally, the last sampling step will be easy because the final subset will simply be a pair of (hyper)rectangles. Since space is constrained and the details are relatively straightforward from the sketch above, full specification and proofs for this process SamplePointWithDege Section 7.4. For immediate purposes, it suffices record the following guarantee:
depth exactly i. Since any
i) appear in
Lemma 3.9. SamplePointWithDepphiSSS i) returns uniform random sample from the region of points with approximate Tukey depth i in S in time (dd)
3.4 OVERALL ALGORITHM
We now have all of the necessary material for the main result, Theorem 1.1, restated below. The proof essentially collects the results so far into a concise summary.
Theorem 3.10. TukeyEM, given in Algorithm 2, is (EP and takes time O (d + dm log(m)).
Proof. Line 11 of the TukeyEM pseudocode in Algorithm calls the check with privacy parameters e/2 and 8/[8c=]. By the sensitivity guarantee of Lemma 3.6, the check itself is e/2-DP. By the safety guarantee of Lemma 3.6 and our choice of threshold, if it passes, with probability at least - 8/2. the given database lies in Saff A passing check therefore ensures that the sampling step in Line 12 is (e/2,0) -DP By composition, the overall privacy guarantee (e, 8)- Turning to runtime, the m OLS computations inside Line each multiply x n. and n X d matrices, for (d) time overall. From Lemma 3.3, Lines 5 to 10 take time ((dm log(m)). Lemma 3.7 gives the (m log(m)) time for Line 11, and Lemma 3.9 gives the (dd) time for Line 12.
EXPERIMENTS
4.1 BASELINES
1. No computes the standard non-private OLS estimator 3* -XXX

---

Published as a conference paper at ICLR 2023
Algorithm 2 TukeyEM
1: Input: Features matrix X E Rnxd, label vector y E IR", number of models m, privacy
parameters and
2: Evenly and randomly partition X and y into subsets {(X,, Y: 1
3: for L........11 do
4: Compute OLS estimator B: <- (x)
5: for dimension j [d] do
6: {Br.)== - projection of { k onto dimension j
7: (S j.m) - { sorted nondecreasing order
8: Collect projected estimators into S E Rdxm, where each row nondecreasing
9: for [m/2] do
Compute volume of region of depth 2 i, V2 (S S.,i)
11: if PTRCheck(V, then
12:
3 + Restricted TueyyEct S, 3//4e/2/
13:
Return 3
else
15:
Return T
2. AdaSSP (Wang, 2018) computes DP OLS estimator based noisy versions of X and X This requires the end user to supply bounds on both || ||2 and l/alle. Our implementation uses these values non-privately for each dataset. The implementation is therefore not private and represents an artificially strong version of AdaSSP. As specified by Wang (2018), AdaSSP (privately) selects ridge parameter and runs ridge regression.
3. DPSGD (Abadi et al., 2016) uses DP-SGD, as implemented in TensorFlow Privacy and Keras (Chollet et al., 2015), to optimize mean squared eтror using single linear layer. The layer's s weights are regression coefficients. A discussion of hyperparameter selection appears in Section 4.4. As we will see, appropriate choices of these hyperparameters is both dataset-specific and crucial to DPSGD's performance. Since we allow DPSGD to tune these non-privately for each dataset, our implementation of DPSGD is also artificially strong.
All experiment code be found Github (Google, 2022).
4.2 DATASETS
We evaluate all four algorithms on the following datasets. The first dataset is synthetic, and the rest are real. The datasets are intentionally selected to be relatively casy use cases for linear regression, as reflected by the consistent high R² for NonDP. However, we emphasize that, beyond the constraints on d and n suggested by Section 4.3, they have not been selected to favor TukeyEM: all feature selection occurred before running any of the algorithms, and we include all datasets evaluated where NonDP achieved a positive R². A complete description of the datasets appears both in the public code and the Appendix's Section 7.5. For each dataset, we additionally add intercept feature.
Synthetic (d 11,
22,000, Pedregosa al. (201 1)). This dataset uses and ((0, label noise with = 10.
2. California (d = 9. n 20,433, Nugent (2017)) predicting house price.
3. Diamonds (d = 10, = 53,940, Agarwal (2017)), predicting diamond price.
4. Traffic (d = 3, n = 7,909, NYSDOT (2013)), predicting number of passenger vehicles.
5. NBA (d 6, n = 21,613, Lauga (2022)), predicting home team score.
6. Beijing (d 25, 159,375, ruiqurm (2018)), predicting house price.
7. Garbage 8, n = 18,810, DSNY (2022)), predicting tons of garbage collected.
8. MLB (d 11. n 140,657, Samaniego (2018)), predicting home team score.
2 R² measures the variation in labels accounted for by the features. R² = 1 is perfect, R O is the trivial baseline achieved by simply predicting the average lahel, and R² 0 is worse than the trivial haseline.
7

---

Published as a conference paper at ICLR 2023
4.3 CHOOSING THE NUMBER OF MODELS
Before turning to the results of this comparison, recall from Section 3 that TukeyEM privately aggregates non-private OLS models. If m is too low, PTRCheck will probably fail; if mn is too high, and each model is trained on only a small number of points, even a non-private aggregation of inaccurate models will be an inaccurate model as well.
Experiments on synthetic data support this intuition. In the left plot in Figure 2, each solid line represents synthetic data with different number of features, generated by the same process as the Synthetic dataset described in the previous section. We vary the number of models m on the r--axis and plot the distance computed by Lemma 3.6. As grows, the number of models required to pass the PTRCheck threshold, demarcated by the dashed horizontal line, grows well.
To select the value of R2 used for TukeyEM, we ran on each dataset using m = 250, 500.... 2000 and selected the smallest where all PTR checks passed. We give additional details in Section 7.6 but note here that the resulting choices closely track those given by Figure 2. Furthermore, across 1000 typically produces nearly optimal R2, with several
many datasets, simply selecting datasets exhibiting little dependence on the exact choice of m.
4.4 ACCURACY COMPARISON
Our main experiments compare the four methods (In(3), 10 -DD... A concise summary of the experiment results appears in Figure 1. For every method other than NonDP (which is deterministic), we report the median R values across the trials. For each dataset, the methods with interquartile ranges overlapping that of the method with the highest median R² are bolded. Extended plots recording R² for various m appear in Section 7.6. All datasets use 10 trials, except for California and Diamonds, which use 50.
Dataset
NonDP
AdaSSP
Tu
DPSGD (unned)
DPSGD (90% tuned)
Synthetic
0.997
0.991
0.997
0.997
0.997
California
0.637
-1.285
0.099
0.085
-1.03
Diamonds
0.907
0.216
0.307
0.828
0.371
Traffic
0.966
0.944
0.965
0.938
0.765
NBA
0.621
0.018
0.618
0.531
0.344
Beijing
0.702
0.209
0.698
0.475
0.302
Garbage 0.542
0.119
0.534
0.215
0.152
MLB 0.722
0.519
0.721
0.718
0.712
For each dataset, the DP methods with interquartile ranges overlapping that of the DP method with the highest median R² are bolded.
Figure 1:
few takeaways are immediate. First, on most datasets TukeyEM obtains R22 exceeding or matching that of both AdaSSP and DPSGD. TukeyEM achieves this even though AdaSSP receives non-private access to the true feature and label norms, and DPSGD receives non-private access to extensive hyperparameter tuning.
We briefly elaborate on the latter. Our experiments tune DPSGD over a large grid consisting of 2.184 joint hyperparameter settings, over learning rateeraaeeeee {10-6 10 ,..., 1]. clip clip_norm
{10-8, 10 ".r,,,,.....,,. 10 microbatches E {25, ..... 20, and epochs E {1,5, 10, 20}. Ignoring the extensive computational resources required to do so at this scale (100 trials of each of the 2, 188 hyperparameter combinations, for each dataset), we highlight that even mildly suboptimal hyperparameters are sufficient to significantly decrease DPSGD's utility. Figure/ quantifies this by recording the R² obtained by the hyperparameters that achieved the highest and 90th percentile median R² during tuning. While the optimal hyperparameters consistently produce results competitive with sometimes exceeding that of TukeyEM, even the mildly suboptimal hyperparameters nearly always produce results significantly worse than those of EM. The exact hyperparameters used appear in Section 7.6.
We conclude our discussion of DPSGD by noting that has so far omitted any attempt at differentially private hyperparameter tuning. We suggest that the results here indicate that any such method will
8

---

Published as a conference paper at ICLR 2023
lower bounnd on distance to unse dabover
100
synthetic time
maan (s) from triass
20
750
# models mm)
1000
1200
1600
1800
2000
8.0
20.0
d= 35.0
d= 50.0 threshold
10.0
d
d
Non-DP
DPSGD-OP
Tukey
Figure 2: Left: plot of Hamming distance to unsafety using Lemma 3.6 the feature dimension d and number of models m varies, using (In(3), 10-9)-DP and n (d + 1 )m throughout. Right: plot of average time in seconds as the number of models used by TukeyEM varies
need to select hyperparameters with high accuracy while using little privacy budget, and emphasize that the presentation of DPSGD in our experiments is generous.
Overall, TukeyEM's overall performance on the eight datasets is strong. We propose that the empirical evidence is enough justify TukeyEM first-cut method for linear regression problems whose data dimensions satisfy its heuristic requirements (n 2 1000 dd).
4.5 TIME COMPARISON
We conclude with a brief discussion of runtime. The rightmost plot in Figure records the average runtime in seconds over 10 trials of each method. TukeyEM is slower than the covariance matrix- based methods NonDP and AdaSSP, but it still runs under one second, and it is substantially faster than DPSGD. TukeyEM's runtime also, expected, depends linearly models m. Since the plots are essentially identical across datasets, we only include results for the Synthetic dataset here. Finally, we note that, for most reasonable settings of m, TukeyEM has runtime a consequence of the relatively unoptimized nature of implementation.
the number of
asymptotically identical to that of NonDP (Theorem 1.1). The gap in practical performance is likely
FUTURE DIRECTIONS
An immediate natural extension of TukeyEM would generalize the approach similar problems such as logistic regression. More broadly, while this work focused on linear regression for the sake of simplicity and wide applicability, the basic idea of TukeyEM can in principle be applied select from arbitrary non-private models that admit expression as vectors in Rd Part of our analysis observed that TukeyEM may benefit from algorithms and data that lead to Gaussian-lit like distributions over similar
models; describing the characteristics of algorithms and data that induce this property property that better characterizes performance of TukeyEM - an open question.
ACKNOWLEDGMENTS
We thank Gavin Brown helpful discussion of Brown al. (2021), and we thank Jenny Gillenwater for useful feedback early draft. We also thank attendees of the Fields Institute Workshop Differential Privacy and Statistical Data Analysis for helpful general discussions.

---

Published as a conference paper at ICLR 2023
REFERENCES
Martin Abadi, Andy Chu, Ian Goodfellow, Н Brendan McMahan, Ilya Mironov, Kunal Talwar, and Zhang. Deep learning with differential privacy, Conference on Computer and Communications Security (CCS), 2016.
Shivam Agarwal.
Diamonds dataset. https: /ttp:://wwwwkaao kaggle cet.ee..tatmeaettaa.aaa shi shivam2503/dt dianndds, 2017. Accessed: 2022-7-6.
Daniel Alabi, Audra McMillan, Jayshree Sarathy, Adam Smith, and Salil Vadhan. Differentially private simple linear regression. In Privacy Enhancing Technologies Sympostum (PETS), 2022.
Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In Foundations of Computer Science (FOCS), 2014.
Raef Bassily, Vitaly Feldman, Kunal Talwar, and Abhradeep Guha Thakurta. Private stochastic convex optimization with optimal rates. In Neural Information Processing Systems (NeurIPS), 2019.
Amos Beimel, Shay Moran, Kobbi Nissim, and Uri Stemmer. Private center points and learning of halfspaces. Conference on Learning Theory (COLT), 2019.
Gavin Brown, Marco Gaboardi, Adam Smith, Jonathan Ullman, and Lydia Zakynthinou. Covariance- aware private mean estimation without private covariance estimation. In Neural Information Processing Systems (NeurIPS), 2021.
T Tony Cai, Yichen Wang, and Linjun Zhang. The cost of privacy: Optimal rates of convergence for parameter estimation with differential privacy. Annals of Statistics, 2020.
François Chollet et al. Keras. https: / //terakkeessee 2015.
Ryan Cunings-Menon. Differentially private estimation via statistical depth. arXiv:2207.12602, 2022.
arXiv preprint
DSNY. Dsny monthly tonnage data. https://data.cityyo City- 2022-7-28.
us/ Accessed:
2022.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryplography Conference (TCC), 2006.
Cynthia Dwork, Kunal Talwar, Abhradeep Thakurta, and Li Zhang. Analyze gauss: optimal bounds for privacy-pie preeeeviig principal component analysis. In Symposium on the Theory of Computing (STOC), 2014.
Google.
https://github. com/ hamm/google-esearccee google research/ wwwperchch/eeeeeeeeeeeee http:///eeeeeeeeeeeeeeeeeeeeeeee 2022.
regression.
David S. Johnson and Franco P Preparata. The densest hemisphere problem. Theoretical Computer Science, 1978.
Haim Kaplan, Micha Sharir, and Uri Stemmer. How to find point in the convex hull privately. In Symposium on Computational Geometry (SoCG), 2020.
Daniel Kifer, Adam Smith, and Abhradeep Thakurta. Private convex empirical risk minimization and high-dimensional regression. Conference on Learning Theory (COLT), 2012.
Nathan Lauga. Nba games dataset. https:/ /wwww/wwwww..////////////...// .kggle , com datasets/ csv, 2022. Accessed: 2022-7-6.
nathanlauga nbba- games?selecte
Jingcheng Liu and Kunal Talwar. Private selection from private candidates. In Symposium the Theory of Computing (STOC), 2019.
Xiyang Liu, Weihao Kong. Sham Kakade, and Sewoong Oh. Robust and differentially private mean estimation. arXiv preprint arXiv:2102.099159 2021.
10

---

Published as a conference paper at ICLR 2023
Xiyang Liu, Weihao Kong, and Sewoong Oh. Differential privacy and robust statisties in high dimensions. In Conference on Learning Theory (COLT), 2022.
Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In Foundations of Computer Science (FOCS), 2007.
Andrés Muñoz Medina and Jenny Gillenwater. Duff: dataset- based utility function family
for the exponential mechanism. arXiv preprint arXiv:2010.04233: 2020,
Jason Milionis, Alkis Kalavasis, Dimitris Fotakis, and Stratis loannidis. Differentially private
regression with unbounded covariates. Artificial Intelligence and Statistics (AISTATS), 2022.
Cam Nugent. California housing prices dataset. https: /tt::://wwww www. kaggle eeaaggll.... wwwpgggg....ooooooooommmmmmmoooo demm/datsst////// coamuugnt//aliforrttee soriiaa-housngg h---hhuuuuuiissss...--.--------- 2017. Accessed: 2022-7-6.
NYSDOT. counts
New
york
weigh-in-motion
station
vehicle
traffic
dataset.
https://datae ny http://///.aaaaaa.ooooooaaerrrr wty.so//raasppotatiio..
Weigh- Weigh-In-Mot on-
Cowefffic-Contt-20000 -ownttt2000ggggg1160011 ottp::/raaiaaaaaaaaaoooooooooorr 2013. Accessed: 2022-7-6.
Nicolas Papernot and Thomas Steinke. Hyperparameter tuning with renyi differential privacy. In International Conference on Learning Representations (ICLR), 2022.
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research
(JMLR), 2011.
Kelly Ramsay and Shoja' eddin Chenouri. Differentially private depth functions and their associated medians. arXiv preprint arXiv:2101.02800, 2021.
ruiqurm. Housing price in beijing. https: // /wwwwwwwwwk// http:///wwww.ggggl....../aaaaa/s lianjia, 2018. Accessed: 2022-7-28.
Antonio Samaniego. Mlb games data from retroshect.
datasets sattis//mmmas stts//aaaaaaccccceaeeeoo hett/mmllggamss-eeee dats-data-aa cesta-from-zeee -aw-aaaaooo--eeetoeeeeeeeeeeee-e -ew..oeeeeeeeeeeeeeeeeeeee--oom log. csv, 2018. 2018. Accessed: 2022-7-28.
Jayshree Sarathy, Sophia Song, Audrey Emma Haque, Tania Schlatter, and Salil Vadhan. Don't look at the data! how differential privacy reconfigures data subjects, data analysts, and the practices of data science. In Theory and Practice of Differential Privacy (TPDP), 2022.
Or Sheffet. Old techniques in differentially private linear regression. In Algorithmic Learning Theory (ALT), 2019. 2019.
method of linear and polynomial regression analysis, 1992. John W Tukey. Mathematics and the picturing of data. In International Congress of Mathematicians (IMC), 1975.
Henri Theil. A
Prateck Varshney, Abhradeep Thakurta, and Prateck Jain. (nearly) optimal private linear regression for sub-gaussian data via adaptive clipping. In Conference Learning Theory (COL.T), 2022.
Yu-Xiang Wang. Revisiting differentially private linear regression: optimal and adaptive prediction & estimation in unbounded domain. In Uncertainty in Artificial Intelligence (UAI), 2018.
11

---

Published as a conference paper at ICLR 2023
7
APPENDIX
7.1 ILLUSTRATION OF EXACT AND APPROXIMATE TUKEY DEPTH
3
2
5
An illustrated comparison between exact (left) and approximate (right) Tukey depth. In both figures, the of points is {(1, 1), (7,3), (5, 7), (3. 3), (5, 5), (6, 3)}. the region of depth 0 is white, the region of depth is light gray, and the region of depth 2 dark gray. Note that for exact Tukey depth, the regions of different depths form a sequence of nested convex polygons; for approximate Tukey depth, they form a sequence nested rectangles.
Figure 3:
7.2 OMITTED PROOFS
We start with the proof of our utility result for exact Tukey depth, Theorem 3.1.
Proof of Theorem 3.1. This is direct application of the results of Brown et al. (2021). They analyzed a notion of probabilistic (and normalized) Tukey depth over samples from a distribution: TN(a)) (y) min, I x [X, v) 2 (y, ui]- Their Proposition 3.3 shows that Ty xy(()) (v) can be characterized in terms of d, the CDF of the standard one-dimensional Gaussian distribution. d+ (++og(1/7))
Specifically, they show TN((,,)) (v) Φ Illlyyyv =l|s)) From their Lemma 3.5, if m
then with probability 1 1 7, lp/m TN( ( S a. Thus
-a S Tv (3) p/m
p/m- - क <-118 3 8r (1)))
p/m- a S (11 3 B" 11))
& (11 11)1) < p/m +
|| 30> < $ -- p/m +mm+0 +
where the third inequality used the symmetry of Φ.
Next, we prove our result about computing the volumes associated with different approximate Tukey depths, Lemma 3.3.
Proof of Lemma 3.3. By the definition of approximate Tukey depth, for arbitrary (v), Da) of Tukey depth at least each of 2d halfspaces ey / .... .t..er.................... Mygaes hyg--es at least i points from D, where dimension j E [d]. Since min ( n DI, [hy n DI) 2 i, Yy E [S,, Sg.m- Sy,s). The computation of starting in Line 5 sorts d arrays of length m and so takes time ((mm log (m)). Line 9 iterates over m/2 depths and computes quantities, each in constant time, so its total time is ((d)).
contains denotes multiplication of a scalar and vector. Fix some Thus
ViD ( (i-mm-(t-1)
The next result is our I-sensitive and efficient adaptation the lower bound from Brown et al. (2021). We first restate that result. While their paper uses swap DP, the same result holds for add-remove DP.
12

---

Published as a conference paper at ICLR 2023
Lemma 7.1 (Lemmaa 3.8 (Brown et al., 2021)). For any k 2 0, if there exists g such that Vi-k-1.D -9- 6, then for every database z in (e dg 2) k, where dæ Vi4keg+1,D
denotes Hamming distance.
We now prove its adaptation, Lemma 3.6.
Proof of Lemma 3.6. We first prove item 1. Let D and D' be neighboring databases, D' D {x}, and let kD and ky denote the mechanism's outputs on the respective databases. It suffices show 11% k - 1.
Consider some Vp for nonnegative integer p. I has depth less than p in D, then V 2 Vg 2 Vr > PD Otherwise, Vp+ID < VDD Vn < Vp-1,D. In either case,
VD+ID < PpD V,D S Vp-1,D
Now suppose there exist kb, 2 0 and ghr > 0 such that Vi-Noo-1.D' c9 86. Then by Vetag. "2141.0' -
V Ve-K5..D
Equation
-0- 5, KD kb - Similarly, if there exist kb 0 and Velki kp..D
V1- -960 < 8, then by Equation 1, Ve+*5 -o
Vi-47, -gh. < so
SD such that Ve4e7, +oh+10
kn. 2 hn 1. Thus if ki 2 0 or kb 2 0, Ik - h S 1. The result then follows since k* 2 -1.
We now prove item 2. This holds for k 2 0 by Lemma 7.1; for l: = 1, the lower bound on distance to unsafety the trivial one, dæ (D, 2 0.
The next proof is for Lemma 3.7, which verifies the overall privacy and runtime of PTRCheck.
Proof of Lemma 3.7. The privacy guarantee follows from the I-sensitivity of computing k (Lemma 3.6). For the runtime guarantee, we perform a binary search over the distance lower bound & starting from the maximum possible m/s and, for each k, an exhaustive search over g. Note that if some k, 9 pair satisfies the inequality in Lemma 7. there exists some g' for every < k that satisfies it well. Thus since both have range < me/4, the total time is Om log(m)).
7.3 USING MONOTONICITY
This section discusses our use of monotonicity in the restricted exponential mechanism. Definition 2.2 states that, if is monotonic, the exponential mechanism can sample an output y with probability proportional to exp A.
sm((,w) and satisfy s-DP. Approximate Tukey depth is monotonic,
application can also sample from this distribution. It remains to incorporate monotonicity into the PTR step.
suffices to show that Lemma 7.1 also holds for a restricted exponential mechanism using a monotonic score function. Turning the proof of Lemma 7.1 given by Brown et al. (2021), it suffices to prove their Lemma 3.7 using wz (S) = Ss exp(ey(x; ddy. Note that their we, (S) differs by the in its denominator inside the exponent term; this modification is where incorporate monotonicity. This difference shows up in two places in their argument. First, we can replace their bound
P (x) v] P [M,')("') = yl
War WY
e/2
Se
(Y
We (Ye,e)
with the two cases that arise in add-remove differential privacy. The first considers x' C and yields
F (M) = vl PP (M)x(x') v] S Wy (Ye,')
(Ye,rr
S e
w. (Yr.))
since the mechanism on & never assigns a lower score to an output than on x'. Using the same logic, the second considers ç x', and get
IP [Mc, (x) = y) (M.)(a') = wx (Yt.))
War (Yy,x)
W> (...(.))))) Wy (Yt,))
<
S e
13

---

Published as a conference paper at ICLR 2023
The second application in their argument, which bounds M
((M,,(z) uses the same logic. As result, their Lemma 3.7 also holds for monotonic restricted exponential mechanism, and we can drop the 2 in the sampling distribution as desired.
7.4 SAMPLING FROM REGION DETAILS
We start by formally defining our partition.
Definition 7.2. Given d-dimensional database D and dimension j E [d] for E R let Tp. (1)) denote the exact one-dimmnsional) Tukey depth of point y with respect to dimension j in database D. Let B₁ denote the region of points with approximate Tukey depth i. Define the partition {Czs}}=1 of B, as the volume of points where depth occurs dimension j for the first time, i.e.,
== ty R
min TD. > i and (D) = =innd minTD.. T (1) 2 i}. Jecj
The partition is well defined because any point with approximate Tukey depth is in exactly one of the C3,s volumes. Each C2. is also the Cartesian product of three sets: any C₁,4 must have 1) depth strictly greater than in dimensions 1, j.... - 1, 2) depth in dimension j. and 3) depth at least in dimensions
1, ..... d. Being the Cartesian product of three sets, the total volume of Cj.5 be computed as the product of the three corresponding volumes in lower dimensions. We will denote these by Vejaa Wj V2jai formalized below.
Definition 7.3. Given d-dimensional database D, dimension [d]. and depth i, define
1. V,,D = vol(fy, yy E IRd, (e,,TD(y) 2 i}), the total length in dimension j of the region with approximate Tukey depth least i.
2. WJa.n = vol(ty; E Rd, (T.Tpij(i = and Ty) 2 i)), the total length in dimension j of the region with depth exactly dimension j and approximate Tukey depth least
3. Veji. vol((ungj1 y Rdd Tn(y) 2 it), the volume of the projection onto the first j j- dimensions of points with approximate Tukey depth least Define V235,D analogously.
When D is clear from context, we drop it from the subscript.
The next lemma shows how to compute these and other relevant volumes. We again note that we fix m be even for neatness. The odd case is similar.
Lemma 7.4. Given matrix S E Rdxm of projected and sorted models, in Line 8 of Algorithm
1. Vy, Sjm--(i11) S3..
2. W Vj Vj,+1.
3. Veja1 = 1T Vy,s and V23,5
II =f++ Vjs
Proof. The proofs of the first item uses essentially the same reasoning the proof of Lemma 3.3. For the second item, any point contributing to Vg, but not Vj.+11 has depth exactly i dimension j. For the third item, a point contributes to Vej.a if and only if it has depth at least in all d dimensions; since the resulting region is rectangle, its volume is the product of its side lengths.
With Lemma 7.4, now prove that SamplePointWithhDepthh works as intended.
Proof of Lemma 3.9. Given d define B, and {C as in Definition 7.2. To show the outcome of SamplePointWitDDepttiSS
is uniformly distributed over points with approximate Tukey depth it suffices to show the algorithm samples C₁, with probability proportional to its
volume. Recall that Cj, is the set of points with depth greater than in dimensions ....... - exactly i in dimension j, and at least i in the remaining dimensions. With this interpretation, Cj,5 is
14

---

Published as a conference paper at ICLR 2023
Algorithm 3 TesstricteTTukeyEE
Input: Tukey depth region volumes sorted collection of estimators S, depth restriction
privacy parameter
2: for - L....,.. [V]
do
3: Compute volume of region of Tukey depth exactly i, W, t V; - V4+1
4: Sample depth from distribution where IP [i] x W; exp (5)
5: Return y - SamppePonttiihhDpppss.....
Algorithm SamplePointWithhDephhh
1: Input: Sorted collection of estimators S, depth i
2: d, m + number of rows and columns in
3: Compute 12 using Lemma 7.4
4: for =r.j=..... d do
5: Compute V Vej,++1, W j.d. and Vija using Lemma 7.4
6: Compute vol(C), = Veja+t W VV3a
7: Sample index jr [d] with probability vol(Cra)
V21
8: for j' = =..... ) do
9: By' uniform random sample from [Sy Sy
10: Uj- uniform random sample from Si (S m- Syr m-(111)
11: for J' = +,, l..... d do
By' uniform random sample from [Sy 5 Sy m (i-
13: Return
the Cartesian product of three lower dimensional regions, and thus its volume is the product of the corresponding volumes,
vol(C),.) = Vej.++1 W V
These quantities, along with the normalizing constant V2 can be computed using Lemma 7.4.
Since is fixed, computing the full set of Vj. and W takes time O(d), and by tracking partial sums and using logarithms, step is sampling the final point y, which takes time (d) using the previously computed S.
compute the full set of Vej.a and Vij,a in time O(d) well. The last
7.5 DATASET FEATURE SELECTION DETAILS
This section provides details for each the real datasets evaluated in our experiments.
1. California Housing Nugent (2017): The label is ical ocean-proximity dropped.
and the categor-
2. Diamonds Agarwal (2017): The label is price. Ordinal categorical features (carat, color, clarity) are replaced with integers 1,2.
3. Traffic NYSDOT (2013): The label is passenger vehicle count (Class 2), and the remain-
ing features are motorcycles (Class 1) and pickups, panels, and vans (Class 3).
4. NBA Lauga (2022): The label is "TS_home, and the features are FT.PCT.home, FG3 PCT home, FG PCT home, AST home, and REB home.
5. Beijing Housing ruiqurm (2018): The label is totalPrice. Features are days on market (DOM), followers, area of house in meters (square), num- ber of kitchens (kitchen), buildingType, renovationConditiie ing material (buildingstructure) ladders per residence (ladderRatio), el- evator presence elevator, whether previous owner owned for least five years (tiveYearsPropertty) proximity to subway (subway), district, and Categorical buildi buildingType. and bui buildingStructurz are encoded as one-hot vari- ables. We additionally removed single outlier row (60422) whose norm is more than two
build-
nearby average housing price (communityAverarge renovationConde
15

---

Published as a conference paper at ICLR 2023
orders of magnitude larger than that of other points; none of the DP algorithms achieved positive R2 with the row included.
6. New York Garbage DSNY (2022): The label REPUSSTTONSCOLLECEED. The features are PAPERTONSCOLLECTED ED and MPGTONSCOLLECTED. The categorical BORCUGH is encoded as one-hot variables.
7. MLB Samaniego (2018): The label is home team rums (h.score) and the features are stzikeouts, walks, v pitchers used, errors, h at bats, h hits, h doubles, h triples, homeruns, and h stolen bases.
7.6 EXTENDED EXPERIMENT RESULTS
Figure 4 records. respectively, the number of epochs, the clipping norm, the learning rate, and the number of microbatches for both the best and 90th percentile hyperparameter settings on each dataset.
Dataset
DPSGD (tuned)
DPSGD (90% tuned)
Synthetic
(20, 1,
(20, 10 10-3,00-00000 0.1, 64)
California
(20, 100, 1, 64)
(10, 10,0,000000, 64)
Diamonds
(20, 100, 1, 128)
(10, 10%, (1)
Traffic
(1, 11, 1,
(10,10", 10 0.1, 1.0,1, 512)
NBA
(20, 100, 512)
(20, 10 32)
Beijing
(20, 100, 0.01, 512)
(20, 2.100.1..000 0.001,
Garbage
(20, 1, 1, 32)
(5, 1000, 1, 64)
MLB
(10, 100, 0.01, 512)
(10, 10010000, 128)
Figure 4: Hyperparameter settings used by DPSGD on each dataset.
7.7 DISTRIBUTION OF MODELS FOR ALL DATASETS
Figures through 13 display histograms of models trained on each dataset. For each plot, we train 2,000 standard OLS models disjoint partitions of the data and plot the resulting histograms for each coefficient. The red curve plots a Gaussian distribution with the same mean and standard deviation as the underlying data.
16

---

7.7 Distribution of models for all datasets
17
synthetic
housing
0.996
0.995
0.0
R3 from 50 trial
0.994
005
0.993
0.992
-1.0
0.991
0.990
1000
1200
1400
1600
1800
2000
800
1000
1200
1400
1600
1800
2000
models m
models
Non-DF
DPSGD-Opt
Subopt
Subopt
diamonds
1.00
0.975
0.75
0.950
0.50
0.925
0.25
Trom
0.850
0.825
-0.75
0.800
-1.00
1000
16.00
1800
2000
1200
1400
1600
18000
models
Non DP
DPSGD Opt
Tukey
Non DP
DPSGD Opt
Tukey
Ads3SP
DPSG0 Subopt
AdaSSP
DPSGD Subopt
nba
beijing
At frum
800
1000
1200
1400
1600
1800
2000
1300
1400
1500
1600
1700
1800
1900
2000
models
models
Opt
Tukey
DPS6D Opt
Tukey
.... AdaS5P
DPSGD-S. bopt
....
AduSSP
DPSCO-Subopt
garbage
mil
0.5
0.70
0 from 10trais
from 10trols
0.3
0.1
0.55
800
1000
1200
1400
1000
1800
2000
800
1000
1200
1000
3000
18:00
2000
models
models m
Nor-DP
DPS
Non-DP
DPSGD--0 Subept
Tukey
Subopt
Figure 5: Plots of R2 as the number of models m used by TukeyEM varies. The lines mark medians and the shaded regions span the first and third quartiles. All datasets except Housing and Diamonds 10 trials. Housing and Diamonds use 50 trials due to the variance of TukeyEM. Methods other than TukeyEM appear as flat lines because they do not vary with m. Each plot varies the number of models m in increments of 250, starting with the sufficient pass PTR in all trials.

---

7.7 Distribution of models for all datasets
18
0.0000
0.30
0.11
1000000
-10009
2000
1.9
0. 5935
0130122
1.09
8932
0.00055
15:0
0,03000
Figure 6: Histograms of models on the California dataset.
Figure 7: Histograms of models on Synthetic.
0.006
0.0014
0.005
0.30
0.25
0.004
0.20
0.0008
0.15
0.0006
0.002
0.0004
0.001
0.000
0.00
0.0000
-1000
1000
-10
10
-7500
-5000
-2500
2500
Figure 8: Histograms models on Traffic.

---

7.7 Distribution of models for all datasets
19
0.900
5930
6.0055
0.00235
0.002
8932
0.0000
8332
0.820
8993
0.0059
0,005
0.0035
2-0303
0.305
3900
4003
3006
B800
-2000
-500
500
3000
-500
306
3090
560
1008
-750
-500
-20
250
0.0335
0.00153
0. 0.001-
0.0014
0.0030
0.00125
0.0012
0.0025
0.00103
0.0008
0.0006
0.00353
0.0005
0.00325
8.0009
0,00303
0.0000
0,0000
-500
-250
250
1.000
2000
-1000
1.000
2000
2003
Figure 9: Histograms of models on Diamonds.
322
3.5
3.54
0.02
Figure 10: Histograms of models on NBA.

---

7.7 Distribution of models for all datasets
20
2000
65-
0.00
1.89
0,00
022
0.03
-208
206
-250
259
549
0,07
8.032
0.82
0.02
0.000
0322
6:03
0.55
200
2322
200
4.31
-220
253
+200
-200
382
0.422
3.33
3.30
0.812
0.012
0,712
3.30
3.003
6:005
3.00
0.000
3.53
6:00
3:55
0/04
0.000
0:23
0.004
0.22
6.032
2.14
2010
8:033
039
6.044
0.044
0.004
0.30
0.32
0480
-208
0.17
8:033
0.00
2:04
3.53
3.40
EC05
6.22
6,06
0375
2744
516
0.30
0:02
0.00
3300
0:00
0.00
0.000
Figure 11: Histograms of models on Beijing.
6.035 012
n12
0.00
E.085
0.00
0.04
0.22
-00
-10
0.00
-22
212--102
-1085
-16
120
6.0033
8837%
88320
60015
6204
00084
1930
6102
159.0
60000
5180
19:0
E4092
Figure 12: Histograms of models on Garbage.

---

7.7 Distribution of models for all datasets
21
3.75
1.59
3.00
0:35
12
Figure 13: Histograms of models on MLB.


Reviews:
[{"review_id": "ZNHygd4oK8", "reviewer": "Reviewer_Ndnv", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "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": "This paper presents a (eps, delta)-differentially private linear regression algorithm using the concept of Tukey depth. A primary goal of the paper is to reduce the amount of effort required of the end-user. In particular, the algorithm here simply requires the user to input the dataset, specify eps and delta, and additionally input a single additional parameter m. The authors give a heuristic for what a good choice of m might be; however if m is not chosen well, then the algorithm is liable to give an overly inaccurate model and take very long to compute, or fail.\n\nThe algorithm run time is O(d^2 n + dm log(m))---where generally m << n. \n\nThe algorithm is also justified by experiments.\n", "summary_of_the_review": "The paper's goal is to design a user friendly differentially private linear regression algorithm. The solution provided seems to strike a good balance between user-friendliness and accuracy according to theoretical results and experiments. I don't think this algorithm will be the definitive word on user-friendly DP LR, but it is a good step forward in an area that addresses a question at the intersection of theory and practice.\n\nNOTE: I have not verified the correctness of all the claims and I did not read the appendix. In \"Correctness\" below, I am indicating that I believe the theorems and they seem to be well justified in the appendix (which I did not read).\n", "strength_and_weaknesses": "Strengths:\n(1) The motivation and goal are clear and compelling.\n(2) The algorithm is indeed easy to use for the end-user. The only remaining trouble is the need for this parameter m.\n(3) The paper is generally well written, and gives the reader intuition along with technical definitions and theorems.\n(4) The experimental evaluation shows that the algorithm produces, for many data sets, good models (that are comparable to the non-DP baseline) in a reasonable amount of time.\n\nWeakness: \n(1) Specifying m may be difficult for an end user. (although, the authors give a heuristic for how one might choose m that seems to work well in their experiments) \n(2) The possibility that the algorithm fails to return a model for some reasonable specifications of m seems annoying.\n(3) The time complexity suggests that the method is not well suited for high-dimensional data.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "YhMjg0Sv3f", "reviewer": "Reviewer_3oJ7", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "The authors have developed a (non-parametric) algorithm for Differentially Private Linear Regression problem. The model works without hyperparameters and privacy bounds using \"Tukey depth\". They call this method as TukeyEM. TukeyEM works in four steps: (i) splitting data into subsets, (ii) computing columns using approximate Turkey depths of given OLS estimators, (iii) adding noise after finding the maximum of the lower-bound, (iv) sampling solutions. With several numerical experiments using real-datasets, they show that TukeyEM performs well compared against several state-of-the-art methods, and it is computationally efficient.", "summary_of_the_review": "A well-written paper on a novel differentially private linear regression. The authors have provided a detailed analysis along with a sufficient numerical experiments.", "strength_and_weaknesses": "Strengths: \n\nThe proposed method  is parameter-free and it does not need for pre distributional assumptions.. TukeyEM performs well compared against other competing models although some of them are allowed to have non-private information (for ex. DP-SGD has access to the non-private parameter tuning, adaSSP has access to the non-private data bounds). \n\nWeaknesses: \n\n1. The method needs a pre-defined m (number of subsets of to divide whole data), and this may be problematic as small m leads failures in PTR check, and larger m means not enough data to learn in step 1 of the algorithm (this issue is also partly acknowledged by the authors). They provide a method for choosing m in Section 4.3 (run the models with various m's and choose the smallest one that leads all pass in PTR check). However is this a part of the main algorithm? Otherwise, how does an end-user decide on m without a detailed understanding of the method? The authors state that m=1000 is enough for most of the cases but it is hard to assess whether it is guaranteed for all real-life scenarios. Indeed, in some cases, number of models (m) may be large (such as 1250 as in Beijing data), and as they note this may result in poor performance for TukeyEM. Hence, this may lead the reader to the fact that TukeyEM works well when the data size is large, indeed they state n>=1000d. Can this equation be relaxed? That is, can TukeyEM work well with small datasets? \n\n2. The authors present Theorem 3.1, which works with exact Tukey depth. But their algorithm is based on approximate Tukey depth. I could not assess what are the consequences of using approximate Tukey depth on the analysis?\n\n3. The paragraph after Theorem 3.1 ends with the statement \"[...] nor does non-Gaussianity preclude accurate estimation.\" Can you please elaborate as Gaussianity assumption is already in Theorem 3.1? \n\n4. In Algorithm 2, line 2 the authors partition X not only \"randomly,\" but also \"evenly.\" Is there a particular reason for even partitioning?\n\n5. How about the prediction performance of TukeyEM? If I am not mistaken, the authors have not provided any discussion on this part.\n\n6. In the first step of the main algorithm, the subsets are partitioned randomly. Would it help to consider these subsets consisting of points that are close to each other (something similar to a nearest neighbour calculation)?\n\n7. The Turkey dept can be written as an optimization problem with binary variables. Thus, when dataset size is reasonable (~10000), an exact optimal solution can be obtained. Then, this exact optimal can be compared against the approximate Turkey depth to empirically discuss the performance of the approximate algorithm. This is just a suggestion for the authors, and I do not expect them to do this for this submission.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "6dDCGbZWXw", "reviewer": "Reviewer_fjWP", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "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": "The current paper under submission studies linear regression and gives an algorithm that is \"more practical\" than the previous approaches. It is based on the approach of Alabi et al. to a large degree and uses known techniques in DP literature to achieve its objective.", "summary_of_the_review": "Please see above. \n\nI have not read the proof so I am not judging whether the claims of the papers are right or wrong. That part of my review is subject to change. ", "strength_and_weaknesses": "The algorithm is more efficient, does not require hyperparameters and does not requirement feedback from the user on the label norm or feature norms. \n\nThe paper seems to natural generalization of known results. In particular, they achieve the polynomial running time by approximating Tukey depth, whose exact computation is NP-hard. Moreover, the paper does not compare its utility guarantee with the known previous works. As such, it is not clear to me what is the advantage of this algorithm? Is it just in the terms of running time, but what about other parameters, like utility? Isn't practical applications would be more concerned with the utility of the algorithm over a run time improvement? \n\nThe paper is overall well written-- I did not get to check the proofs, but I would love to see them over the next month. I really would like to understand what is the technical challenges faced in this paper? Like, how does considering approximate Tukey depth changes the utility guarantee. What is the sensitivity of the approximate Tukey depth? I can understand that Tukey depth is 1-sensitive function, but why is the approximate version the same? I believe the approximation in multiplicative. In general, some care has to be taken when considering approximate functions (see the recent paper https://arxiv.org/abs/2210.03831 for some discussion on this front and their use of smooth sensitivity). \n\nThe proper credit of DP-SGD should go to this paper https://cseweb.ucsd.edu/~kamalika/pubs/scs13.pdf or BST paper. Abadi et al. just did the moment accountancy which was new. DP-SGD was known before. Likewise, Sheffet's paper gave the first analysis of statistical inference for OLS using differentially private estimators; however, it was not the first to study OLS. \n\nPage 3. The last sentence has two full stops.\n\nI am not sure how the authors can claim that the empirical distribution of models has fast tail decay! I would argue it is more heavy-tailed. \n\nThe first sentence of the second paragraph in Sec 3.2 does not make any sense. \n\nI am surprised that the authors have used dataset that has very very small dimension when their central claim is that the algorithm is practical. No one is going a linear regression model for d=25. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "4rBSw4gKbn", "reviewer": "Reviewer_Nbxy", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "This paper provides a practical algorithm for differentially private linear regression. Algorithmically, this proposed method is a combination of Theil-Sen estimator for linear regression and private mean estimator using Tukey median appeared in (Brown at el 2021) and (Liu at el 2021). Prior works have provable guarantees for gaussian data but are exponential time. The proposed method computes the median of OLS solutions using approximate Tukey depth and exponential mechanism. This paper does not have theoretical utility guarantees for gaussian data. But this paper provides extensive experiments to demonstrate the effectiveness. ", "summary_of_the_review": "This paper provides a practical algorithm for DP linear regression, which can be seen as the most fundamental task for learning with differential privacy. Unlike prior works in this domain, this paper also provides extensive experiments on real data.", "strength_and_weaknesses": "Strengths: 1. This paper provides the first practical algorithm for DP linear regression based on high dimensional median. The emprical experiments justified the effectiveness of the proposed algorithm\n2. It is kind of surprising to see that this type of algorithm works well on real data. For example, the theoretical results in Brown at el 2021 assume that the data is exactly Gaussian and not able to generalize to sub-gaussian. This paper provides strong evidence and shows that this type of approach could be used for real data.\nWeaknesses: 1. Unlike prior works, no utility guarantees are provided here for Gaussian data using approximate tukey depth.\n2. A better DP-SGD baseline would be (Varshney at el 2022). The difference is that the clipping threshold is adaptively estimated from the data, which is also easy to implement. Theoretically, (Varshney at el 2022) gives near-optimal rates for sub-gaussian-like data. \n\n\n\nQuestions:\n1. I guess the proposed approach could be first used for mean estimation directly.  Is this true? If this is true, how is the empirical performance?\n2. To my understanding, this approximate tukey depth is similar as coordinate-wise median. Is there any hope to provide theoretical analysis for gaussian data under $\\ell_\\infty$-norm? \n3. I guess the proposed method could also provide some robustness against the corruption of the datasets as a side product of using high dimensional median (as in Liu at el 2021 or Liu at el 2022). Can this be verified through experiments or theoretical justifications?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster