Better Private Linear Regression Through Better Private Feature Selection
Authors: Travis Dick
Jennifer Gillenwater
Matthew Joseph
Venue: NeurIPS 2023 poster (2023)
Keywords: differential privacy
linear regression
sparse
feature selection
kendall
TL;DR: We introduce a private feature selection algorithm based on Kendall rank correlation and show that it improves practical private linear regression.

Abstract: Existing work on differentially private linear regression typically assumes that end users can precisely set data bounds or algorithmic hyperparameters. End users often struggle to meet these requirements without directly examining the data (and violating privacy). Recent work has attempted to develop solutions that shift these burdens from users to algorithms, but they struggle to provide utility as the feature dimension grows. This work extends these algorithms to higher-dimensional problems by introducing a differentially private feature selection method based on Kendall rank correlation. We prove a utility guarantee for the setting where features are normally distributed and conduct experiments across 25 datasets. We find that adding this private feature selection step before regression significantly broadens the applicability of ``plug-and-play'' private linear regression algorithms at little additional cost to privacy, computation, or decision-making by the end user.

Better Private Linear Regression Through Better Private Feature Selection
Travis Dick
Jennifer Gillenwater!
Matthew Joseph?
Abstract
Existing work on differentially private linear regression typically assumes that end users can precisely set data bounds or algorithmic hyperparameters. End users often struggle to meet these requirements without directly examining the data (and violating privacy). Recent work has attempted to develop solutions that shift these burdens from users to algorithms, but they struggle to provide utility as the feature dimension grows. This work extends these algorithms to higher-dimensional problems by introducing a differentially private feature selection method based on Kendall rank correlation. We prove utility guarantee for the setting where features are normally distributed and conduct experiments across 25 datasets. We find that adding this private feature selection step before regression significantly broadens the applicability of "plug-and-2" aand---ndppa"" private linear regression algorithms at little additional cost to privacy, computation, or decision-making by the end user.
Introduction
Differentially private [10] algorithms employ carefully calibrated randomness obscure the effect of any single data point. Doing so typically requires an end user to provide bounds on input data to ensure the correct scale of noise. However, end users often struggle to provide such bounds without looking at the data itself [27], thus nullifying the intended privacy guarantee. This has motivated the development of differentially private algorithms that do not require these choices from users.
To the best of our knowledge, two existing differentially private linear regression algorithms satisfy this "plug-and-pe aouggand-play" requirement: 1) the Tukey mechanism [2], which combines propose-test- rest--elett-eeee with an exponential mechanism based on Tukey depth, and 2) Boosted AdaSSP [30], which applies gradient boosting to the AdaSSP algorithm introduced by Wang [34]. We refer to these methods as, respectively, Tukey and BAS. Neither algorithm requires data bounds, and both feature essentially one chosen parameter (the number of models for Tukey, and the number of boosting rounds T for BAS) which admits simple heuristics without tuning. contrast, AdaSSP requires a user to provide bounds on the data's iata's feature and label norms, and DPSGD requires user to configure hyperparameters including learning rate, clipping norms, batch size, and number of epochs. Both algorithms produce much weaker utility when these parameters are moderately misconfigured [2].
Tukey obtains strong empirical results when the number of data points n greatly exceeds the feature dimension d [2], while BAS obtains somewhat weaker utility on larger class of datasets [30]. Nonetheless, neither algorithm provides generally strong performance on its own. Evaluated over collection of 25 linear regression datasets taken from Tang et al. [30], Tukey and BAS obtain coefficient of determination R² > 0 on only four (see Section 4); for context, baseline R² = is achieved by the trivial constant predictor, which simply outputs the mean label. These results suggest room for improvement for practical private linear regression.
"tdick@ google.com, Google Research jigilleww@ @ gom, work done while at Google Research "mtjoseph @ google.com, Google Research
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

1.1 Our Contributions
We extend existing work on private linear regression by adding a preprocessing step that applies private feature selection. At high level, this strategy circumvents the challenges of large feature dimension d by restricting attention to < carefully selected features. We initiate the study of private feature selection in the context of "plug-and-play" private linear regression and make two concrete contributions:
1. We introduce a practical algorithm, DPKendall, for differentially private feature selection (Section 3). DPKendall uses Kendall rank correlation [20] and only requires the user to choose the number & of features to select. It satisfies e-DP and, given n samples with d-dimensional features, runs in time O(dkn log(n)) (Theorem 3.4). We also provide a utility guarantee when the features normally distributed (Theorem 3.8).
2. We conduct experiments across 25 datasets (Section 4), with fixed at 5 and 10. These compare Tukey and BAS without feature selection, with SubLasso feature selection [21], and with DPKendall feature selection. Using (In(3), 10 10-5)-DD to cover both private feature selection and private regression, find at k = 5 that adding DPKendall yields R² on 56% of the datasets. Replacing DPKendall with SubLasso drops the rate to 40% of datasets, and omitting feature selection entirely drops it further to 16%.
In summary, we suggest that DPKendall significantly expands the applicability and utility practical private linear regression.
1.2 Related Work
The focus of this work practical private feature selection applied to private linear regression. We therefore refer readers interested in more general overview of the private linear regression literature to the discussions of Amin et al. [2] and Tang et al. [30].
Several works have studied private sparse linear regression [21, 31, 17, 29). However, Jain and Thakurta [17] and Talwar et al. [29] require fxc bound on the input data, and the stability test that powers the feature selection algorithm of Thakurta and Smith [31] requires the end user to provide granular details about the optimal Lasso model. These requirements are significant practical obstacles. An exception is the work of Kifer et al. [21]. Their algorithm first performs feature selection using subsampling and aggregation of non-private Lasso models. This feature selection method, which we call SubLasso, only requires the end user to select the number of features k. To the selected features, Kifer et al. [21] then apply objective perturbation to privately optimize the Lasso objective. As objective perturbation requires the end user to choose parameter ranges and provides a somewhat brittle privacy guarantee contingent on the convergence the optimization, we do not consider here. Instead, our experiments combine SubLasso feature selection with the Tukey and BAS private regression algorithms. An expanded description of SubLasso appears Section 4.2.
We now turn to the general problem of private feature selection. There is a significant literature studying private analogues of the general technique of principal component analysis (PCA) [25, 15, 8, 19, 11, I]. Unfortunately, all of these algorithms assume some variant of a bound on the row norm of the input data. Stoddard et al. [28] studied private feature selection in the setting where features and labels are binary, but it is not clear how to extend their methods to the non- con-binary setting that we consider in this work. SubLasso is therefore the primary comparison private feature selection method in this paper. We are not aware of existing work that studies private feature selection in the specific context of "plug-and-play" private linear regression.
Finally, private rank correlation has previously been studied by Kusner et al. [23]. They derived a different, normalized sensitivity bound appropriate for their "swap" privacy setting and applied it to privately determine the causal relationship between two random variables.
Preliminaries
Throughout this paper, a database D is a collection of labelled points (æ. y) where x E TRdd y E R. and each user contributes single point. We use the "add-remove" form of differential privacy.

---

Definition 2.1 ((1O)), Databases D. D' from data domain DD are neighbors D ~ D' if they differ in the presence or absence of single record. A randomized mechanism M D - +0 is (E,
differentially private (DP) if for all D) D' E 'D and any S C O
PM (M( S) SMP (M'') E
We use basic composition to reason about the privacy guarantee obtained from repeated application of a private algorithm. More sophisticated notions of composition exist, but for our setting of relatively few compositions, basic composition is simpler and suffers negligible utility loss.
Lemma 2.2 ([10)). Suppose that for j E [K], algorithm Ag is (,)D,,)DPP. Then running all k algorithms is (1)=1 Ey,, E
Both SubLasso and DPKendall use private subroutine for identifying the highest count item(s) from a collection, known as private top-k. Several algorithms for this problem exist [4. 9, 13]. We use the pure DP "peeling mechanism" based Gumbel noise [9], its analysis is relatively simple, and its performance is essentially identical to other variants for the relatively small is used in this paper.
Definition 2.3 (19)). A Gumbel distribution with parameter is defined over x' by [x;; exp (- - -//b). Given
N, and privacy parameter Peel(c, k. =)) adds independent Gumbel (2kAa) noise to each count oj and outputs the or- dered sequence of indices with the largest noisy counts.
(cty...,, Cd) E Rd,
Lemma 2.4 (19)). Given c (ct....... E Rd with Eo sensitivity Ax.. Peel(c, ki Ax,, E) is E-DP.
The primary ad advantage of Peel over generic noise addition is that, although users may contribute to d counts, the added noise only scales with k. We note that while Peel requires an foo bound, neither DPKendall nor SubLasso needs user imput set it: regardless of the dataset, DPKendall's use of Peel has lo = 3 and SubLasso's 's use has for = 1 (see Algorithms 1 and 2).
Feature Selection Algorithm
This section describes our feature selection algorithm, DPKendall, and formally analyzes its utility. Section 3.1 introduces and discusses Kendall rank correlation, Section 3.2 describes the full algorithm, and the utility result appears in Section 3.3.
3.1 Kendall Rank Correlation
The core statistic behind our algorithm is Kendall rank correlation. Informally, Kendall rank correla- tion measures the strength of a monotonic relationship between two variables.
Definition 3.1 ([20). Given a collection of data points (X, Y) = {(,,, Yi).... (Xn, Yr)) and
i < i', pair of observations (X,, Y.), (Xe, Ye) ) is discordant if (X, (1,--x))00 Xx)(X, -YY, < O. Given data (X, Y), let dx,y denote the number of discordant pairs. Then the empirical Kendall rank correlation is
+(X,)) = n 2dx,y
7-11
For real random variables X and Y, we can also define the population Kendall rank correlation by =
-((x - X') Y') 0J P P X')(Y -Y) < 0].
Kendall rank correlation is therefore high when an increase in X or Y tyyically accompanies increase in the other, low when an increase in one typically accompanies a decrease in the other, and close to 0 when a change in one implies little about the other. We typically focus empirical Kendall rank correlation, but the population definition will be useful in the proof of our utility result.
Before discussing Kendall rank correlation in the context of privacy, we note two straightforward propertics. First, for simplicity, we use a version of Kendall rank correlation that does not account for ties. We ensure this in practice by perturbing data by small amount of continuous random noise. Second, T has range [-1, 1], but (this paper's version of) 7 has range [-n/2, This scaling does not affect the qualitative interpretation and ensures that f has low sensitivity*.
In particular, without scaling, would be -ennsitivee but is private information in add-remove privacy.
3

---

Lemma 3.2. A(F) 3/2.
Proof. At a high level, the proof verifies that the addition or removal of user changes the first term of f by at most 1/2, and the second term by at most 1.
In more detail, consider two neighboring databases (X and (X,Y), Without loss (I),, "X,,,,,,,, Ya)}
and (X'Y")) {(X1, YI),-.., (X2+1; Y1=1) where for all i [r] we have that X = X, and Y = Y, First, we argue that the number of discordant pairs in (X', .Y) cannot be much larger than in (X,Y). By definition, we have that ,x dx,y Eÿ=1 (x,,-xx x ,,,, 10, 1)) In particular, this implies that y dx,y E [0. n].
of generality, we may assume that (x, Y)
We can rewrite the difference in Kendall correlation between (X, Y) and (X)Y") as follows:
2
+
1
2dxry
= 2 f(X,Y) - -(X,,))
+
2
dx
dx,x
1
2
2
dx -dx,x
+ dx,y
dx,y
1
2
n
2
dx dx,x
1
1
1
2
+ +2dx,
n
n1
1
2 dx - dx.y dxy
(
2
where the final equality follows from the fact that 2(, n-1
-1((2). Using our previous
calculation, the first term is in the range [0, 2] and, since dx E [0, (+)), the second term is in the range [-1, 0j. It follows that
3 0 00
1
1 3 2 2
2 S ((X,Y) - 2
2
and therefore |+(X, Y) -(XXX(XX) 3/2.
To show that the sensitivity is not smaller than 3/2, consider neighboring databases (X, Y) and (X', Y") such that dx,y and (X',Y") contains new point that is discordant with all points in
(X, Then y = n while dx = Then F(X,Y) - f(X', Y") = 2 - 0 - 1/2 = 3/2. O
Turning to privacy, Kendall rank correlation has two notable strengths. First, because it is computed entirely from information about the relative ordering of data, it does not require an end user to provide data bounds. This makes it natural complement to private regression methods that also operate without user-provided data bounds. Second, Kendall rank correlation's 's sensitivity is constant, but its range scales linearly with n. This makes it easy compute privately. A contrasting example is Pearson correlation, which requires data bounds to compute covariances and has sensitivity identical to its range. An extended discussion of alternative notions of correlation appears in Section 6.
Finally, Kendall rank correlation can be computed relatively quickly using a variant of merge sort. Lemma 3.3 ([22)). Given collection of data points (X,Y) = {(X,, Yi),... (Xn, Y,)), F(,Y)) can be computed in time O(n log(n)).
3.2 DPKendall
Having defined Kendall rank correlation, we now describe our private feature selection algorithm, DPKendall. Informally, DPKendall balances two desiderata: 1) selecting features that correlate with the label, and 2) selecting features that do not correlate with previously selected features. Prioritizing only the former selects for redundant copies of a single informative feature, while prioritizing only the latter selects for features that are pure noise.
In more detail, DPKendall consists of applications of Peel to select a feature that correlated with the label and relatively uncorrelated with the features already chosen. Thus, letting S, denote the set

---

of features already chosen in round t, each round attempts to compute
max JES,
[((
Σ J'ES,
|((X, X,)1
(I)
t t-
The 1_ scaling ensures that the sensitivity of the overall quantity remains fixed at 1-I
2 in the first round and in the remaining rounds. Note that the first round we take second term to be O, and only label correlation is considered.
Algorithm (D, D,
1: Input: Examples D {(X,, Y.) number of selected features k. privacy parameter
2: for j -......... d
3: Compute f) [x Y)
4: Initialize S
0
5: Initialize F = RV E Rd
6: Initialize ,* 0 E Rd
7: for = 1......k do
8: Set 2 3
1,
9: Set 5t Peel ( + T-T Doo
xx
10:
Expand 5 = SU8t
Update 4Y -00
12:
for j & do
13:
Update tjx = tj (x.)).X..))
14:
Return S
Pseudocode for DPKendall appears in Algorithm 1. Its runtime and privacy are easy to verify. Theorem 3.4. DPKendall runs in time (ddnn log(n)) and satisfies E-DP.
Proof. By Lemma 3.3, each computation of Kendall rank correlation takes time O log(()),, so Line 2's loop takes time (dn In)(n)), as does each execution of Line 12's loop. Each call to Peel requires Odd) samples of Gumbel noise and thus contributes (dk)) time overall. The loop in Line therefore takes time Oddn log(n)). The privacy guarantee follows from Lemmas 2.4 and 3.2. D
For comparison, standard OLS on samples of data with d features requires time O(Pn): DPKendall is asymptotically slower long < O(24/k). Since typically take h < d, DPKendall is computationally "free" in many realistic data settings.
3.3 Utility Guarantee
The proof of DPKendall's utility guarantec combines results about population Kendall rank correla- tion (Lemma 3.5), empirical Kendall rank correlation concentration (Lemma 3,6), and the accuracy of Peel (Lemma 3.7). The final guarantee (Theorem 3.8) demonstrates that DPKendall selects useful features even the presence of redundant features.
We start with the population Kendall rank correlation guarantee. Its proof, and all proofs for uncited results in this section, appears in Section in the Appendix.
X2, are independent random variables where Xj N(1,, 03). Let & N (0, o.) be independent noise. Then if the label is generated by Y Σ/ 3,X, for any jr E [k].
Lemma 3.5. Suppose that
2 π
35-0.-
TX,,,
arctan
V Einny 830 o²
To interpret this result, recall that E [- and arctan has domain IR is odd, and has lom arctan x = x/2. Lemma 3.5 thus says that we fix the other o, and a. and take a,- - oc, T(y), sign (3y-) ) as expected. The next step is to verify that f concentrates around
5

---

Lemma 3.6 (Lemma [3]). Given observations each of random variables X and Y, with proba- bility 7
F(X,Y) nt -(X,Y) Sn ln(2/n).
Finally, we state a basic accuracy result for the Gumbel noise employed by Peel. Lemma 3.7. Given i.i.d random variables X1,.... X2 Gumbel (b), with probability "p
2d
max jEld
X S blm
now have the tools necessary for the final result.
Theorem 3.8. Suppose that XI....,X, .x are independent random variables where each Xj ~
N (ug of). Suppose additionally that of the remaining d - k random variables, for each j E [k], nj are copies of X,, where -i=in
n2y S d k. For each j E [k], let Sj denote the set of indices consisting of and the indices of copies. Then if the label is generated by = ン Ej= where & ~ N(0, o²) ) is independent random noise, if
k (I(ndk/f)))
n Ω
8 miinn+eaa arctan VEits* By 73
then with probability 1 (n), DPKendall correctly selects exactly one index fnom each of Si...., Sk-
Proof. The proof reduces to applying the preceding lemmas with appropriate union bounds. Dropping the constant scaling of 1 for neatness, with probability 1 1 -
1. Feature-label correlations are large for informative features and small for uninformative features: by Lemma 3.5 and Lemma 3.6, each feature in j U) has
B,
+(X s Y) π
arctan
V 8n In(d/n))
E0 880 + o²
and any jr & S has
Y) Y) /8nIn(d/)) In(d/n).
Feature-feature correlations are large between copies feature and small between independent features: by Lemma 3.5 and Lemma 3.6, for any E [k] and J1, E Sj,
+ +(X, X
n
/ 8n In(d/n)
2
and for any ji, j2 such that there exists no Sy containing both, f F(X,, Xjz) S (8nin(//n)
3. The at most dk draws of Gumbel noise have absolute value bounded by A In dk (4t)
Combining these results, to ensure that DPKendall's calls to Peel produce exactly one index from each of Si...., Sg. it suffices to have
= (Ivn+ + mm((())))
n min ElM
arctan
Virr 8803 oz
which rearranges to yield the claim.
Experiments
This section collects experimental evaluations of DPKendall and other methods on 25 of the 33 ' Descriptions of the relevant algorithms appear in Section 4.1 and Section 4.2. Section 4.3 discusses the results. Experiment code may be found on Github [14].
'We omit the datasets with OpenML task IDs 13108003610844 as they are restricted versions of other included datasets. We also exclude 361090 and 361097 as non ooniviivate OLS obtained R² & 0 on both. Details for the remaining datasets appear in Figure in the Appendix.

---

4.1 Feature Selection Baseline
Our experiments use SubLasso [21] as a baseline pplug-and-plan private feature selection method. At high level, the algorithm randomly partitions its data into m subsets, computes a non non-private Lasso regression model on each, and then privately aggregates these models to select It significant features. The private aggregation process is simple; for each subset's ss learned model, choose the k features with largest absolute coefficient, then apply private top-k to compute the & features most selected by the models. Kifer et al. [21] introduced and analyzed SubLasso; we collect its relevant properties in Lemma 4. 1. Pseudocode appears in Algorithm
Algorithm 2 SubLasso k, m,,)
Input: Examples
{(X,, Y.) number of selected features k, number of models m,
privacy parameter
2: Randomly partition D into m equal-size subsets Si...., , Sm
3: for 1, . do
4: Compute Lasso model 0, on S;
5: Compute set C; of the k indices of 0g with largest absolute value
6: Compute binary vector v E {0, 1]d where Vi = 1ieC:
7: Compute V E _ = 2i=1
8:
Return Peel(V, k, 1,6)
Lemma 4.1. SubLasso is 6-DP and runs in time (dFr)).
Proof. The privacy guarantee is immediate from that of Peel (Lemma 2.4). Solving Lasso on n/m data points with d-dimensional features takes time O ((L [12]. Multiplying through by produces the final result, since Peel only takes time (dk).
Finally, we briefly discuss the role of the intercept feature in SubLasso. As with all algorithms in our experiments, we add an intercept feature (with a constant value of I) to each vector of features. Each Lasso model is trained private voting step, & features are chosen from the remaining features, and the intercept added back afterward. This ensures that privacy is not wasted on the intercept feature, which we always include.
data with this intercept. However, the intercept is removed before the
4.2 Comparison Algorithms
We evaluate seven algorithms:
1. NonDP is non-private baseline rumning generic ordinary least-squares regression.
2. BAS runs Boosted AdaSSP [30] without feature selection. We imitate the parameter settings used by Tang et al. [30] and set feature and gradient clipping norms and the number of boosting rounds to 100 throughout.
3. Tukey runs the Tukey mechanism [2] without feature selection. We introduce and a tighter version of the trellse-tes-rellesse (PTR) check given by Amin et al. [2]. This reduces the number of models needed for PTR pass. The proof appears in Section 9 in the Appendix and may be of independent interest. To privately choose the number of models m used by the Tukey mechanism, first privately estimate
7 probability lower bound
the number of points n using the Laplace CDF, = n + Lap (+) In(1/2g) and then set the number of models m [//d]. Tukey spends 5% of its privacy budget estimating m and the remainder on the Tukey mechanism.
4. L-BAS runs spends 5% of its privacy budget choosing m = [n/k k for SubLasso, 5% of running SubLasso, and then spends the remainder to run BAS on the selected features.
5. L-Tukey spends 5% of its e privacy budget choosing m = j for SubLasso, 5% running SubLasso, and the remainder running Tukey on the selected features using the same m.
6. K-BAS spends 5% of its e privacy budget running DPKendall and then spends the remainder running BAS on the selected features.
7. K-Tukey spends 5% of its e privacy budget choosing m = [ā/k], 5% running DPKendall, and then spends the remainder running the Tukey mechanism the selected features.
7

---

16-
10-
number of datasats
12-
10-
number
Tukey
L-BAS
L-Tukey
K-AS
K-ukkyy
BAS
Tukey
L-BA5
L-Tukey
K-AA
K-lukey
rank
Figure I: Plots of rank data for each private method.
10
10
10
03l3326 with
dabasts with
BAS
Tukey
L-BAS
L-uaeyy
K-BAS
KTakey
BAS
Tukey
L-AS
LTikey
KBAS
K.Tikay
method
Figure 2: Plots of the number of datasets with positive R² for each private method.
4.3
Results
All experiments use (Im(3), 10 DD-P. Where applicable, 5% of the privacy budget is spent private feature selection, 5% on choosing the number of models, and the remainder is spent on private regression. Throughout, we use = 10 as the failure probability for the lower bound used to choose the number of models. For each algorithm and dataset, we run 10 trials using random 90-10 train-test splits and record the resulting test R² values. Tables of the results at & and h = 10 appear in Section 10 in the Appendix. condensed presentation appears below. At a high level, summarize the results in terms of relative and absolute performance.
4.3.1 Relative Performance
First, for each dataset and method, we compute the median R2 of the final model across the 10 trials and then rank the methods, with the best method receiving a rank of Figure plots the number of times each method is ranked first or second.
At 5 (left), K- K-Tukey performs best by significant margin: it ranks first on 48% of datasets, twice the fraction of any other method. It also ranks first second on the largest fraction of datasets (68%). In some contrast, L-BAS obtains the top ranking on 24% of datasets, whereas K-BAS only does on 8%; nonetheless, the two have nearly the same number of total first or second rankings. At l: 10 (right), no clear winner emerges among the feature selecting methods, as L-BAS, K-BAS, and K- K-Tukey are all first second on around half the datasets". though the methods using SubLasso have a higher share datasets ranked first.
"Note that & 10 only uses 21 datasets. This is because of the 25 datasets used for & have d 10.

---

4.3.2 Absolute Performance
Second, we count the number of datasets on which the method achieves positive median R (Figure 2), recalling that R 0 is achieved by the trivial model that always predicts the mean label. The k = 5 (left) setting again demonstrates clear trends: K-Tukey attains It² > 0 on 56% of datasets, L-Tukey does so on 40%, K-BAS does so on 28%, and L-BAS on 20%. DPKendall therefore consistently demonstrates stronger performance than SubLasso. As in the rank data, at 10 the picture is less clear. However, K-Tukey is still best by some margin, with the remaining feature selecting methods all performing roughly equally well.
4.4 Discussion
few trends are apparent from Section 4.3. First, DPKendall generally achieves stronger final utility than SubLasso, particularly for the Tukey mechanism; the effect is similar but smaller for k = 10; and feature selection generally improves the performance of private linear regression.
Comparing Feature Selection Algorithms. A possible reason for DPKendall's improvement over SubLasso is that, while SubLasso takes advantage of the stability properties that Lasso exhibits in certain data regimes [21]. this stability does not always hold in practice. Another possible explanation that the feature coefficients passed to Peel scale with (n) for DPKendall and m - or
m = O h ) for SubLasso. Both algorithm's 's invocations of Peel add noise scaling with O so DPKendall's larger scale makes it more robust to
noise. Finally, we emphasize that DPKendall achieves this even though its (dkn log(n)) runtime is asymptotically smaller than the (d?n)) runtime of SubLasso in most settings.
10. Conceptually, past a certain point adding marginally less informative features to private model may worsen utility due to the privacy cost of considering these features. Moving from k = 5 to = 10 may cross this threshold for many of our datasets; note from Figure 4 and Figure 5 in the Appendix that, of the 21 datasets used for k- = 10, 86% witness their highest private R² in the = setting'. Morcover, from k 5 to k 10 the total number of positive R datasets across methods declines by more than 50%, from 41 to 19, with all methods achieving positive R less frequently at = 10 than h = We therefore suggest &o 5 as the more relevant setting, and good choice in practice.
Choosing Next, we examine the decrease in performance from
The Effect of Private Feature Selection. Much work aims to circumvent generic lower bounds for privately answering queries by taking advantage of instance-spedd specific structure [6, 16, 33, 5]. Similar works exist for private optimization, either by explicitly incorporating problem information [35, 18] or showing that problem-agnostic algorithms can, under certain conditions, take advantage of problem structure organically [24]. We suggest that this paper makes a similar contribution: feature selection reduces the need for algorithms like Boosted AdaSSP and the Tukey mechanism to "waste" privacy on computations over irrelevant features. This enables them to apply less obscuring noise to the signal contained in the selected features. The result is the significant increase in utility shown here.
5 Conclusion
We briefly discuss DPKendall's limitations. First, it requires an end user to choose the number of features k to select; we suggest k = 5 as reasonable first cut. Second, DPKendall's use of Kendall rank correlation may struggle when ties are intrinsic to the data's structure, e.g., when the data is categorical, as monotonic relationship between feature and label becomes less applicable. Finally, Kendall rank correlation may fail to distinguish between linear and nonlinear monotonic feature-label relationships, even though the former is more likely to be useful for linear regression. Unfortunately, is not obvious how to incorporate relationships more sophisticated than simple monotonicity without sacrificing rank correlation' 's low sensitivity. Answering these questions may be an interesting avenue for future work.
Nonetheless, the results of this paper demonstrate that DPKendall expands the applicability of plug- and-play private linear regression algorithms while providing more utility in less time than the current state of the art. We therefore suggest that DPKendall presents step forward for practical private linear regression.
The exceptions datasets 361075, 361091, and 361103.

---

References
[1] Karcem Amin, Travis Dick, Alex Kulesza, Andres Munoz Medina, and Sergei Vassilvitskii. Differentially private covariance estimation. Neural Information Processing Systems (NeurIPS), 2019.
[2] Kareem Amin, Matthew Joseph, Mónica Ribero, and Sergei Vassitvitskii. Easy differentially private linear regression. In International Conference on Learning Representations (ICLR), 2023.
[3] Youssef Anzarmou, Abdallah Mkhadri, and Karim Oualkacha. The Kendall interaction filter for variable interaction screening in high dimensional classification problems. Journal of Applied Statistics, 2022.
[4] Raghav Bhaskar, Srivatsan Laxman, Adam Smith, and Abhradeep Thakurta. Discovering frequent patterns in sensitive data. In Knowledge Discovery and Data Mining (KDD), 2010.
[5] Jaroslaw Blasiok, Mark Bun, Aleksandar Nikolov, and Thomas Steinke. Towards instance- optimal private query release. In Symposium on Discrete Algorithms (SODA), 2019.
[6] Avrim Blum, Katrina Ligett, and Aaron Roth. A learning theory approach to non-interactive database privacy. In Symposium on the Theory of Computing (STOC), 2008.
[7] Gavin Brown, Marco Gaboardi, Adam Smith, Jonathan Ullman, and Lydia Zakynthinou. Covariance- Private Mean Estimation Without Private Covariance Estimation. In Neural Information Processing Systems (NeurIPS), 2021.
[8] Kamalika Chaudhuri, Anand Sarwate, and Kaushik Sinha. Near-optimal differentially private principal components. Neural Information Processing Systems (NIPS), 2012.
[9] David Durfee and Ryan M Rogers. Practical differentially private top-k selection with pay- what-you-get composition. Neural Information Processing Systems (NeurIPS), 2019.
[10] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity private data analysis. In Theory of Cryptography Conference (TCC), 2006.
[11] Cynthia Dwork, Kunal Talwar, Abhradeep Thakurta, and Li Zhang, Analyze gauss: optimal bounds for Computing (STOC), 2014.
principal component analysis. In Symposium on Theory of
[12] Bradley Efron, Trevor Hastie, Iain Johnstone, and Robert Tibshirani. Least angle regression. Annals of Statistics, 2004.
[13] Jennifer Gillenwater, Matthew Joseph, Andres Munoz Medina, and Monica Ribero Diaz. A Joint Exponential Mechanism For Differentially Private Top-k. In International Conference on Machine Learning (ICML), 2022.
[14] Google.
private kendall https: /ttps://github. http://gghhhuuu.cooogggeeeeeeeee hwtp:////gggg.e.eerrrrrr/oggeeee
[15] Moritz Hardt and Aaron Roth. Beating randomized response on incoherent matrices. In Symposium Theory of Computing (ICMI), 2012.
[16] Moritz Hardt and Guy N Rothblum. A multiplicative weights mechanism for privacy--reserving data analysis. In Foundations of Computer Science (FOCS), 2010.
[17] Prateek Jain and Abhradeep Guha Thakurta. (Near) dimension independent risk bounds for differentially private learning. International Conference on Machine Learning (ICML), 2014.
[18] Peter Kairouz, Monica Ribero Diaz, Keith Rush, and Abhradeep Thakurta. (Nearly) Dimension Independent Private ERM with AdaGrad Rates via Publicly Estimated Subspaces. In Conference on Learning Theory (COLT), 2021.
[19] Michael Kapralov and Kunal Talwar. On differentially private low rank approximation. In Symposium Discrete Algorithms (SODA), 2013.
10

---

[20] Maurice G Kendall. A new measure of rank correlation. Biometrika, 1938.
[21] Daniel Kifer, Adam Smith, and Abhradeep Thakurta. Private convex empirical risk minimization and high-dimensional regression. In Conference on Learning Theory (COLT), 2012.
[22] William R Knight. A computer method for calculating Kendall's tau with ungrouped data. Journal of the American Statistical Association, 1966.
[23] Matt J Kusner, Yu Sun, Karthik Sridharan, and Kilian Q Weinherger. Private causal inference. In Artificial Intelligence and Statistics (AISTATS), 2016.
[24] Xuechen Li, Daogao Liu, Tatsunori B Hashimoto, Huseyin A Inan, Janardhan Kulkarni, Yin-Tat Lee, and Abhradeep Guha Thakurta. When Does Differentially Private Learning Not Suffer in High Dimensions? Neural Information Processing Systems (NeurIPS), 2022.
[25] Frank McSherry and Ilya Mironov. Differentially private recommender systems: Building privacy into the netflix prize contenders. In Knowledge Discovery and Data Mining (KDD), 2009.
[26] Donald Bruce Owen. A table of normal integrals. Communications in Computation, 1980.
and
[27] Jayshree Sarathy, Sophia Song, Audrey Emma Haque, Tania Schlatter, and Salil Vadhan. Don't t look the data! How differential privacy reconfigures data subjects, data analysts, and the practices of data science. In Conference on Human Factors in Computing Systems (CHI), 2023,
(28) Ben Stoddard, Yan Chen, and Ashwin Machanavajjhala. Differentially private algorithms for empirical machine learning. arXiv preprint arXiv: /41 2014.
[29] Kunal Talwar, Abhradeep Guha Thakurta, and Li Zhang. Nearly optimal private lasso. Neural Information Processing Systems (NIPS), 2015.
[30] Shuai Tang. Sergul Aydore, Michael Kearns, Saeyoung Rho, Aaron Roth, Yichen Wang, Yu- Xiang Wang, and Zhiwei Steven Wu. Improved Differentially Private Regression via Gradient Boosting. arXiv preprint arXiv:2303.03455 2023.
[31] Abhradeep Guha Thakurta and Adam Smith. Differentially private feature selection via stability arguments, and the robustness of the lasso. In Conference on Learning Theory (COLT), 2013.
[32] John W Tukey. Mathematics and the picturing of data. In International Congress of Mathemati- cians (IMC), 1975.
[33] Jonathan Ullman. Private multiplicative weights beyond linear queries. Database Systems (PODS), 2015.
Principles of
[34] Yu-Xiang Wang. Revisiting differentially private linear regression: optimal and adaptive prediction & estimation in unbounded domain. In Uncertainty in Artificial Intelligence (UAI), 2018.
[35] Yingxue Zhou, Zhiwei Steven Wu, and Arindam Banerjee. Bypassing the ambient dimension: Private sgd with gradient subspace identification. International Conference on Learning Representations (ICLR), 2021.

---

Alternative Notions of Correlation
6.1 Pearson
The Pearson correlation between some feature X and the label Y is defined by
Cov (X,Y)
r(,Y)== /Var (X) Var (Y)
Evaluated sample of points, this becomes
E (X; 8)(Vi -V)
(X,Y))
EX: (X: - Ei=1 10 YY2
where X and are sample means.
Lemma 6.1. r E [-1,1].
Proof. This immediate from Cauchy-Schwarz.
Note that value of -1 is perfect anticorrelation and value of 1 is perfect correlation. A downside of Pearson correlation is that it is not robust. In particular, its sensitivity is the same as its range.
Lemma 6.2. Pearson correlation has l --sesiiiiyvyyy A(r) =
Proof. Consider neighboring databases ((-1.-1), (1, c)), r(D) = 1, but
D
f(-1,-1),
and D'
r(D') = (-1+ (1+ +
(1+ -1- (- 39
9) 22))
(2)
(2
where the approximation is increasingly accurate grows.
6.2 Spearman
Spearman rank correlation is Pearson correlation applied to rank variables.
Definition 6.3. Given data points X1....,X, X,, R. the corresponding rank variables
R(X1),...,R( R(X,) are defined by setting R(X;) to the position X, when X1 X,...., X,, are sorted in descending order. Given data (X,Y), the Spearman rank correlation is p(X, Y) = rr(((X), R(Y)).
For example, given database D = {(0, (1, 3)). its Spearman rank correlation is
p(D) r(((1(((3)))))) 2), (2, (1,))
useful privacy property of rank that it does not depend data scale. Moreover, if there ties then Spearman rank correlation admits a simple closed form.
Lemma 6.4. p(X,Y) = 6E (R(X,)-
n(=²-1)
we consider adding a "perfectly unsorted" data point with rank variables (1, n + 1) to perfectly sorted database with rank variables {(1, 1), (2,2)...., (n, n)}, P changes from The sensitivity's dependence on n complicates its usage with add-remove privacy. Nonetheless, both Spearman and Kendall correlation's 's use of rank makes them relatively easy to compute privately, and as the two methods are often used interchangeably in practice, we opt for Kendall rank correlation for simplicity.
6(a+z²)
n(x²-1)
12

---

7 Deferred Proofs From Section 3.3
We first restate and prove Lemma 3.5.
Lemma 3.5. Suppose that .,...., Xx are independent random variables where X, ~ (H,,,
Let ę ~ N(, o.)) be independent noise. Then if the label is generated by Y = -== 8,X, for any j E [k].
2 π
B5.0.
T(X,,
arrctan
Viis 8303 + 0
Proof. Recall from Definition 3.1 the population formulation of T,
T(X,Y) = P [[X - XY Y") 0] [[X x (Y <0]
(3)
where X and X' are i.i.d., as are Y and y In our case, we can define 7= EEEfj 83 + and rewrite the first term of Equation 3 for our setting as
Jo (x).-x;((t)11 (1--))11----- +
fx,- "_
Fz- 22 (4)
where fA and FA denote densities and cumulative distribution functions of random variable A, respectively. Since the relevant distributions are all Gaussian, Xy. -X,- ~ (0,0 20 and Z ~ N (0, و 3 + oz)). For neatness, shorthand o² = 20 and o²1 2|E 3 + o
Then if we let e denote the PDF of a standard Gaussian and & the CDF of a standard Gaussian, Equation 4 becomes
(t/o)) 1 1- ,)] + /
1
(3/0))(33.110-1100 + [ ol (--110)0(83--1/--)00
2 (3,0))(3,-11/)))
We can similarly analyze the second term of Equation 3 to get
[ fx,--x((11) 11
fxy-xx, (t) (---)(-B-t))tt +
(11/a)0(-3 (0:0000(33--/// 1----11--111111 1/0-1)d0 1) [ _ (1)
0 1
Jo
Using both results, get
2
1
(1100)((33110-))))
((10))((3--1/0-)))d
0
2
((t/o)((3,-
Φ(t/o)[1 D(3--t/0
4
(1/0)0(
1/0
4
0
35.0
+ arctan
2T
0-1
arctan
T-1
where the third equality uses f ((l/a)dl z and the fourth equality comes from Equation 1,010.4 of Owen [26]. Substituting in the values of and σ-1 yields the claim.
13

---

Next is Lemma 3.7.
Lemma 3.7. Given i..dd random variables Xi..... X2 ~ Gumbel (6), with probability 1 77.
2d
max
X I blm
jeld]
Proof. Recall from Definition 2.3 that Gumbel (b) has density f(z) f(x)
exp (- -E-
Then
exp (-g - -//b + e=/b). For = 2 0, by e²
g" 2 n!.
1-
2²
2² S 6
22 + x= s 2z +1 1
1
f(-z) so since b 2 f()) for 2 0. Letting F(z) = exp(-ees (xp(-exp(-z/b) denote the CDF for
Gumbel (b), follows that for 2 1 F()) 2 F(-2). Thus the probability that maxje(e] [Xy]
exceeds t is upper bounded by 2d(1 F(t)). The claim then follows from rearranging the inequality
2d(1 F(!) Σ
" F())
2d
"
< exp( exp(-t/b)
2d
In
1
1
S exp(-t/b)
2d
(1
-bln
In
2d
bln
St
Inn1
m// ///2dd))
and using In(1 -2) x) Ein
x//121.
8 Datasets
A summary of the datasets used in our experiments appears in Figure 3.
We briefly discuss the role of the intercept in these datasets. Throughout, explicitly add an intercept feature (constant 1) to each vector. Where feature selection is applied, we explicitly remove the intercept feature during feature selection and then add it back to the selected features afterward. The resulting regression problem therefore has dimension + 1. We do this to avoid spending privacy budget selecting the intercept feature.
Modified PTR Lemma
This section describes a simple tightening of Lemma 3.6 from Amin et al. [2] (which is itself the result its propose-test-
small modification of Lemma 3.8 from Brown al. [7]). Tukey release (PTR) check, so tightening it makes the check easier to pass. Proving the result will require introducing details of the Tukey algorithm. The following exposition aims to keep this document both self-contained and brief; the interested reader should consult the expanded treatment given by Amin al. [2] for further details.
Tukey depth was introduced by Tukey [32]. Amin et al. [2] used an approximation for efficiency. Roughly, Tukey depth is notion of depth for collection of points in space. (Exact) Tukey depth is evaluated over all possible directions Rdd, while approximate Tukey depth is evaluated only over axis-aligned directions.
Definition 9.1 ([32, 2)). A halfspace h, is defined by vector Rd, h. ly Rd (v, 2 0). Let E {e1, ..., ea} be the canonical basis for & and let D C. Rd The approximate Tukey depth of
14

---

OpenML Task ID
d
n/d
n/5
n/ 1//10
361072
8192
22
372
1638
819
361073
15000
27
555
3000
1500
361074
16599
17
976
3319
1659
361075
7797
614
1559
779
361076
6497
12
541
1299
649
361077
13750
34
404
2750
1375
361078
20640
9
2293
4128
2064
361079
22784
17
1340
4556
2278
361085
10081
7
1440
2016
1008
361087
13932
14
995
2786
1393
361088
21263
80
265
4252
2126
361089
20640
9
2293
4128
2064
361091
515345
91
5663
103069
51534
361092
8885
83
107
1777
888
361093
4052
13
311
810
405
361094
8641
6
1440
1728
864
361095
166821
24
6950
33364
16682
361096
53940
27
1997
10788
5394
361098
10692
18
594
2138
1069
361099
17379
21
827
3475
1737
361100
39644
74
535
7928
3964
361101
581835
32
18182
116367
58183
361102
21613
20
1080
4322
2161
361
394299
27
14603
78859
39429
361104
241600
16
15100
48320
24160
Figure 3: Parameters of the 25 datasets used in our experiments.
point E RRd with respect to D, denoted Tyly), is the minimum number of points in D) in any of the 2d halfspaces determined by E containing y.
Tn(y)
min VE s.f. yEtu
Σ 1neh,
RED
At high level, Lemma 3.6 from Amin et al. [2] is statement about the volumes of regions of different depths. The next step to formally define these volumes.
Definition 9.2 ([2]). Given database D, define St,D { E Rd TD(y) 2 i be the set of points with approximate Tukey depth at least in D and V.D vol(S..)) to be the volume of that set. When D clear from context, we write S, and V: for brevity. We also use wD((a. Ssa. exple TD dy))dy to denote the weight assigned to Va,D by an exponential mechanism whose score function Tp-
Amin al. [2] define family of mechanisms AI, A2.... where A, runs the exponential mechanism to choose a point of approximately maximal Tukey depth, but restricted to the domain of points with Tukey depth least t. Since this domain is data-dependent quantity, they use the PTR framework to select a safe depth t. We briefly recall the definitions of "safe" and "unsafe" databases given by Brown et al. [7], together with the key PTR result from Amin al. [2].
Definition 9.3 (Definitions 2.1 and 3.1 [7]. Two distributions P, Q over domain W are (e, 0)- indistinguishable, denoted P Re, Q. for any measurable subset W C.W
Pump [w W] S TP TP [w E W] + 8 and TP PP (w E W] S P [w E W] + 8.
Database is (E, 5, -a-e if for all neighboring D' D, we have A₂(D) Re, A(DD). Let
(afe() be the of safe databases, and let Unsafe(;,6.) be its complement.
can now restate Lemma 3.6 from Amin al. [2]. Informally, states that if the volume of an "outer" region of Tukey depth is not much larger than the volume of an "inner" region, the difference
15

---

in depth between the two is a lower bound on the distance to an unsafe database. For the purpose of this paper, Tukey applies this result by finding such a k. adding noise for privacy, and checking that the resulting distance to unsafery is large enough that subsequent steps will be privacy-safe.
Lemma 9.4. Define (D) to be a mechanism that receives as input database D and computes the largest & E { }} such that there exists g where
Vi-k-1,D
-5// <
V1+
or outputs -1 if the inequality does not hold for any such k. Then for arbitrary
1. M is I-sensitive, and
2. for all E Unsafe (D, > M(D).
We provide drop-in replacement for Lemma 9.4 that slightly weakens the requirement placed on Lemma 9.5. Define (D) to be mechanism that receives as input database D and computes the largest & E (o....,t 1} such that
Vi-K-1D
(((++t--)) 1) <
WD (V(+k--L,
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 = E (nsaafe(g, (D,2)) M(D).
The new result therefore replaces the denominator + I. ef9/2 with denominator "n (D(V++s-1.D) Every point in VI+R-1,D of depth at least L + k + g + 1 has score at least / + k + + 1, so up((i+e-110) 2 VV+*+g+1.D c so Vi+*+g+1,D e wp(Vi+stg11.0) and the check for the es(c=++1))
c
ec(++++13
new result is no harder to pass. To see that it may be easier, note that only the new result takes advantage of the higher scores of deeper points in Vi+k-1.D-
Proof of Lemma 9.5. First we prove item 1. Let D and D' be any neighboring databases and suppose WLOG that D' D U (z). We want to show that [MD M(D)) 1.
First we prove relationships between the points with approximate Tukey depth at least p and p in datasets D and D'. From the definition of approximate Tukey depth, together with the fact that D' contains one additional point, for any point y, we guaranteed that TD(y) TD (y) S TD(y) 1. Recall that Sp.D is the set of points with approximate Tukey depth at least in D. This implies that Sp+ID C Sp.D. Next, since for every point we have (D) 2 TD(y), we have that Sp. C Sp, Finally, since Tb(y) 2 (v)
have that Sp. C Sp-DDD Taken together, we have Sp+1DD C Sp.D C CSp C Sp-I.D.
follows that
V1+ID S Vv S V.D < Vv--1,
(5)
Next, since the unnormalized exponential mechanism density y + exp(yIn(v)) is nen-negative. we have that wp(Vpt1,p = ITyI. exp(eTn(w)) dy S Isp. exp(eTn(v)) dy = (V,.))) SS exp(eTn(w)) dy S
Using the fact that Tn()) s (u),), we have that wp(V,,)) SS..r exp(<TD((v)) dy = wD (Vp.D)) Finally, using the fact that Tb-(v) $ TT((y) + 1, we have wD (V,.r) = Is exp(eTr dy S JS...D exp(eTn(v) + + dy e'n (Vp- Together,
this gives
WD(V < wD wD (V,,)) m) S wD (V S wDlVV-V e
6
Vi Vi- 1.0 WD +2
Now suppose there exists ki. such that
(1(t/r +1) s 8. Then by Equa-
tion 5, V1,D 2 Vi-Ky. and by Equation 6 wD (V++ S <WD(V+Hg++1,)) e
16

---

Do- cllthhr)) _ and then k 2 kn. - 1. Similarly, if there exists kn 2 0 such that "D(Vuiggr1DD) V-bb11
(e(l++b+1) S 6, then by Equation 5 Vi VD -1. 1,D 2 VD and by Equation
"D(Vitbbt2.D)
S wp (V ++,0'++ so W ((+tk))))) < 8, and kb 2 kn - 1. Thus
if ) 2 or D 2 0, D kb - 1. The result then follows since h- -1.
As in Lemma 9.4, item 2 is consequence of Lemma 3.8 from Brown et al. [7] and the fact that k* = -1 a trivial lower bound on distance. The only change made to the proof of Lemma 3.8 of Brown al. [7] is, in its notation, replace its denominator lower bound with
(V 2 Wr (V++6+111,0))
This uses the fact that æ: and differ in most the addition removal of data points. Thus V S V, and no point's score increases by more than k from V to V++*-i.- Since their numerator upper bound is Vi-k-1,z - (+++1) (note that the is dropped here because approximate Tukey depth is monotonic; see Section 7.3 of [2] for details), the result follows.
10
Extended Experiment Results
Task ID
NonDP
BAS
Tukey
L-BAS
L- L-Tukey
K-BAS
K- K-Tukey
361072
7.3e-01
7.8c-01
-OG
-2.7e-02
1.0e-01
2.1e-01
1.0e-01
361073
4.6e-01
-3.4c+00
-00
-4.6e-01
-2.3e-02
-488-01
-4.ee-01
361074
8.0c-01
4.5e+04
-6.6c+02
-8.2c+02
-1.e++02
-5.ee405
3.1e-01
361075
6.2e-01
-3.6e+02
3.2e-003
2.2e-02
5.2e-03
7.1e-02
361076
2.8c-01
-3,4c+00
-00
-5
-2.5e-01
-4.3e+00
8.5e-02
361077
8.2e-01
-2.le+08
-00
-..e+00
3.7e-01
-1.9e408
6.6e-01
361078
6.5e-01
-1.ee+03
6.4e+00
-7.4e-01
-1.ec+00
-6.le+02
-9.5e-01
361079
2.6e-01
-5,4c000
110c+01
-13c+01
-2.+00
-9.4e+00
-6.8e-01
361085
3.3e-01
-2.e+01
3.3e-01
-1.7e+01
2.8e-01
-1.3e+01
3.7e-01
361087
7.2e-01
-3.1e+03
8.8e404
-4.7c+00
-1.e+00
-2.8c+00
6.6c-01
36 361088
71
5,4e-02
-oo
1.4e-01
3.e-01
2.1e-01
3.6e-01
361089
6.2e-01
33.+00
-1.5e+01
-1.3++00
-5.9e+00
-5.9et04
-2.6e-01
361091
2.4e-01
-3.0e+04
-1.9c+00
-3.0e+04
3.8e-02
-3.le+04
4.9e-02
361092
2.0e-02
4.7e+05
0c
-4.1e+04
-1.4e+08
-1.3e+05
-9.e+088
361093
4.3e-01
-5.6e-02
00
-4.6e-02
-00
-4.9--2
-00
361094
8.3e-01
4.2e-01
-3.8e+05
-1.c+00
-4.e+005
-2.4e+00
-3.0e+05
361095
2.2e-01
-1.0e+00
-1.2++09
-8.0e-01
2.e-01
1.5e-01
2.1e-01
361096
9.7e-01
-9.1e+02
-le+08
-4.9c+00
9.1e-01
7.1e-01
8.8e-01
361098
8.6e-01
-2.9e+01
-3.9e+00
-3.1e+00
-2.2e-01
-5.6e+00
361099
4.0c-01
-4.4c-01
-4,8c110
-4,8e-01
-9.8e-03
-4.2e-01
3.2e-01
361100
1.2e-01
-6.3e+01
-1.1e+00
-2.8e-02
-4.6e-01
-1.7e-01
361101
3.3e-01
.9.3e+01
-5.9e+08
3.6e-01
2.e-01
3.0e-01
2.1e-01
361102
7.6e-01
-4.e++22
-1.4e+15
6,8e-02
-2.6e-01
-4.0e+00
-5.3e+00
361103
5.3e-01
4.3e-01
-6.3e407
5.c-01
4.9e-01
3.3e-01
4.8e-01
361 104
6.8e-01
-3.7e+03
-6.4e+07
-1.5e+02
-2.6e+05
-8.3e-01
-2.9++01
Figure 4: R² values for = 5. Each entry median test value from trials. The top two private values for each dataset are bolded.
17

---

Task ID
NonDP
BAS
Tukey
L-BAS
L- Tukey
K-BAS
K- K-Tukey
361072
7.4e-01
5.3e-01
0C
3.5e-01
1.8e-01
7.3e-01
8.2e-02
361073
4.6e-01
-8.2e-01
0C
4,4e-01
-1.7e+00
-4.8e-01
-1.6e+01
361074
8.1e-01
-2.ee006
-1.3e+03
-5.6e+06
-3.4c+02
-7.2++04
-1.4e+02
361075
6.2e-01
-1.7e+02
-00
7.5e-02
-9.7e-01
3.1e-02
-2.8++00
361076
2.8e-01
-2.4c+02
-8.2c+04
-27e+01
-3.5c+03
-2.4e+01
-1.4e+03
361077
7.9e-01
-1.1e+08
-1.4e+07
-3.1e+01
-2.le+08
-1.7e+02
361079
2.4e-01
-1 1.8e+00
-3.7e+01
-1.2e+01
-8.1e-01
-..e+00
-1.5e+00
361087
7.le-01
-3.7e+01
-1.5e+04
-7.2++00
-488+033
-8,5++01
-2.++01
361088
7.3e-01
-1.9e+00
1.2e-01
9.2e-02
1.2e-01
7.1e-02
361091
214c-01
-3. 3.0e+04
-3.4e+00
-3.0e+04
6.8e-02
-3.1e+04
5,7e-02
361092
4.0e-02
-2.4e+06
-c
-8.7e405
-7.6e+09
-7.5e+05
-3.7e+10
361093
4.3e-01
-322e-02
-5.e-01
00
-1.ee-01
-o0
361095
2.2c-01
1.9e+01
-1.ce+09
-8,6e-01
-2.4c+07
-1.e++00
2.1e-01
361096
9.8e-01
-3.7e+02
-1.0e488
-3.4e+03
-18e+00
-1.0+403
4.2c-01
361098
8.6e-01
-1.8e+02
-0
.4.1e-01
-1.3e+07
-9.5e-11
-5.8e-01
361099
4.0e-01
-4.3e-01
-2.3e+10
-4.9e-01
-2.4++09
-4.8e-01
-2.5e+08
361 361100
1.2e-01
-9.2e+01
-C
-1.6e+00
-8.2e-02
-3.5e+00
-5.2e-01
361101
3.4e-01
-3.3e+03
-1.7e408
-8.1e-01
-1.4++02
-9.5e-01
-4.7e+05
361102
7.5e-01
-9,5++02
-1.7e+15
-1.3e+00
-1,5e+15
-2.5e+01
-1.4++05
361103
5.4e-01
-2.6++00
-1.2e+08
4.9e-01
5.1e-01
3.5e-01
4.9e-01
361104
6.8e-01
-9.c+02
-1.0e+08
-2.9e+03
-3.5e+07
-1.4c+03
-6.6e+05
Figure 5: This figure records the same information as Figure 4, but for k = 10.
18


Reviews:
[{"review_id": "xdbaU7ymuI", "reviewer": "Reviewer_8Qm2", "summary": "This paper studies the problem of feature selection for linear regression subject to differential privacy constraints.  One of the benefits of this work is that the feature selection does not require setting bounds on features a priori, thus allowing for fewer hyper-parameters which are difficult to set in practice.  By developing a DP version of the Kendall rank correlation, they show that first doing DP feature selection can significantly improve the quality of the DP linear regression model.  Existing DP linear regression also do not require bounds on features, so together with this DP feature selection, it provides a practical way to do DP linear regression with feature selection.", "questions": "How important is the \"add-remove\" neighboring relation compared with \"swap\"?\n\nRather than using “basic” DP composition to compare the various $k$ parameters in the feature selection, can you instead frame this part under zCDP?  In the end you are quoting an approximate DP guarantee, due to the Tukey mechanism being approximate DP, so framing the feature selection as zCDP should be straightforward.  The reason is because as you increase $k$, you are suffering a larger impact on privacy loss than necessary, due to basic composition, which can also influence the general guidance you gave of using $k = 5$.  I would be interested to see the performance of the various tests using zCDP composition with $k$ being swept over several choices.", "limitations": "Limitations were stated in the paper.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Linear regression is a fundamental problem in data analytics, so having a simple DP version of it will help practitioners in various applications.  Feature selection is an important subroutine in linear regression and reducing the hyper parameters can be beneficial.  The application of the exponential mechanism which balances the two desiderata (features that correlate with label and features that do not correlate with already selected features) is nice.  Can other works for feature selection (e.g. PCA) be summarized in a similar way?", "weaknesses": "This work claims that their approach will help expand the applicability of private linear regression, but it does not seem like existing approaches were too bad without feature selection.  Was a better private linear regression really the bottleneck for deploying DP linear regression in practice, especially when DP parameters are typically large in practice?  Although this is a nice result, it seems incremental.  The main contributions that I see include a sensitivity analysis of the empirical Kendall rank correlation and a utility guarantee under certain assumptions that I am not sure how the result would be used in practice as it depends on the population parameters.  I think that developing DP algorithms with as few hyper parameters is important, but the feature selection still introduces the $k$ parameter without a clear way to set it.  \n\nFurther, I would like to better understand the connection between Kusner et al [22] and this work.  Is the neighboring relation between “swap” and”add-remove” technically important?  Seems like there are a few nuisances with the “add-remove” neighboring relation, e.g. the scaling of $\\hat{\\tau}$ and the estimation of $\\tilde{n}$ in the comparison of algorithms.  I would be interested in how the various approaches in the experiments compare with as few hyper parameters as possible.  For instance, there is some budget allocated for computing $\\tilde{n}$ and an $\\eta$ parameter which seem arbitrary and can be avoided with the “swap” neighboring relation.  \n\nMinor:\n- is the $R^2 = 0$ approach really trivial?  Don’t you need to set some bound on the labels to compute the mean?\n\n- Line 297 “alls”\n\n- Line 7 in Algorithm 2, should the sum be to $m$ not $n$?\n\n- I might be misunderstanding the pseudocode in Algorithm 1, but it seems like $\\hat{\\tau}^X$ will always be negative.\nThe sensitivity of the rank correlation reminds me of work from DP non-parametric hypothesis testing from Couch, Kazan, Shi, Bray, Grace ’19.  How does the Kendal rank correlation compare with the Kruskal-Wallis rank statistic? \n\n- In the introduction, it is not clear what is meant by “plug-and-play” requirement.  Maybe there is a missing paragraph or sentence?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> The application of the exponential mechanism which balances the two desiderata (features that correlate with label and features that do not correlate with already selected features) is nice. Can other works for feature selection (e.g. PCA) be summarized in a similar way?\n\nIn some sense, yes. For example, Kaprolov and Talwar's private PCA algorithm (\"On differentially private low rank approximation\", Kaprolov Talwar 12) uses the following process: privately estimate a rank-1 approximation, subtract the corresponding matrix from the original, and recurse on the resulting matrix. The first step is analogous to label correlation, and the second step is analogous to subtracting the influence of previous approximations. However, we note that this similarity is largely conceptual and informal.\n\n> Was a better private linear regression really the bottleneck for deploying DP linear regression in practice, especially when DP parameters are typically large in practice?\n\nSee the response to Comment 1 in the general response. Briefly, we suggest that DP linear regression has, in practice, been far from a solved problem. Previous solutions can yield reasonable utility with large privacy parameters and non-private tuning, but this is still unsatisfying if we want meaningful privacy guarantees. In contrast, our methods yield good utility without large privacy parameters or non-private tuning.\n\n> Is the neighboring relation between “swap” and ”add-remove” technically important? … [f]or instance, there is some budget allocated for computing $\\tilde n$ and an $\\eta$ parameter which seem arbitrary and can be avoided with the “swap” neighboring relation\n\nWe agree that the distinction between swap and add-remove privacy is not technically significant, and we do not suggest that the proof of Kendall rank's low sensitivity in the add-remove model is a major contribution of the paper (briefly, we frame the paper's major contributions as observing that Kendall rank correlation can be used for private feature selection, constructing a private algorithm to balance correlation and uncorrelation, proving a formal utility guarantee, and demonstrating strong empirical performance across many datasets). Nonetheless, we opted to use add-remove privacy because, for example, swap privacy allows the release of a database's size in the clear, and this can itself constitute a privacy violation in many practical settings.\n\n> Is the $R^2 = 0$ approach really trivial? Don’t you need to set some bound on the labels to compute the mean?\n\nIt is trivial in the sense that it discards the features entirely. However, you are correct that privately approximating this algorithm is not trivial. We therefore suggest that the increase in $R^2 > 0$ datasets obtained via our feature selection algorithm (from 16% to 56% of all datasets) is a meaningful improvement.\n\n> Line 7 in Algorithm 2, should the sum be to $m$ not $n$? … I might be misunderstanding the pseudocode in Algorithm 1, but it seems like $\\hat \\tau^X$ will always be negative.\n\nYes. Furthermore, the term $\\hat Y - \\frac{\\hat \\tau^X}{t-1}$ in Line 9 of Algorithm 1 should be a sum, not a difference. We will correct these typos in the next version.\n\n> The sensitivity of the rank correlation reminds me of work from DP non-parametric hypothesis testing from Couch, Kazan, Shi, Bray, Grace ’19. How does the Kendall rank correlation compare with the Kruskal-Wallis rank statistic?\n\nFrom the given paper, Kruskal-Wallis \"is used to determine if several groups share the same distribution in a continuous variable\". In contrast, rank correlation measures the strength of a monotonic relationship between two variables (or, in the language of Kruskal-Wallis, groups). The latter seems better suited to regression, as, for example, a feature and label typically won't have the same distribution in an OLS setup, but will have a (roughly) monotonic relationship. \n\n> In the introduction, it is not clear what is meant by “plug-and-play” requirement. Maybe there is a missing paragraph or sentence?\n\nThanks for pointing this out. We will revise the paper to clarify. See the response to Comment 1 in the general response.\n\n> Rather than using “basic” DP composition to compare the various parameters in the feature selection, can you instead frame this part under zCDP? … as you increase $k$, you are suffering a larger impact on privacy loss than necessary, due to basic composition, which can also influence the general guidance you gave of using $k=5$.\n\nWhile zCDP composition technically enables better composition, this difference happens to be negligible at the parameter ranges used in our experiments. For example, we spend $\\varepsilon = 0.05 \\cdot \\ln(3) \\approx 0.06$ on feature selection. Applying basic composition with $k=10$, each call uses $\\varepsilon \\approx 0.006$. Applying zCDP composition and generously using half the full $\\delta = 10^{-5}$ budget only results in a per-call increase in the $\\varepsilon$ budget to $\\varepsilon \\approx 0.007$, and the change is even smaller for smaller $k$."}, {"review_id": "HnDEi70ZVo", "reviewer": "Reviewer_yU7m", "summary": "The paper under consideration delves into the challenge of performing linear regression under differential privacy, especially in scenarios where the data is unbounded. This issue arises primarily due to the current private linear regression mechanisms that require tuning a set of hyperparameters for unbounded data, thereby degrading data privacy. To navigate this, the paper utilizes two \"plug-and-play\" mechanisms—namely the Turkey and the BoostedAda (BAS) mechanisms—which circumvent the necessity of parameter tuning. Nonetheless, their limitation lies in their inadequate scalability for high-dimensional data.\n\nTo address this, the paper innovates a differentially private technique for feature selection, DPKendall, intended for high dimensional unbounded data. It’s goal is to choose the most important features—those significantly correlated to the dependent variable in linear regression. These features can then be used with either the Turkey or BAS mechanism.\n\nThe distinctiveness of DPKendall lies in its utilization of Kendall rank correlation to identify correlations between features. The advantages of this method is that it does not require knowledge of data range—relying solely on the relative ordering of the data—and its bounded sensitivity, which is the measure of how much the correlation computation changes in response to a single individual's input data changing. Bounded sensitivity is crucial for upholding differential privacy.  Then, the DPKendall method privately selects k features, seeking to optimize the Kendall rank correlation with the dependent variable while minimizing its correlation with previously chosen features. The latter objective aids in eliminating redundancy.\n\n\nAlthough principal component analysis (PCA) is a prevalent approach for dimension reduction, its applicability is restricted due to most DP methods' necessity for bounded data. Therefore, the paper compares DPKendall with another private feature selection technique, SubLasso.\n\nThe paper substantiates the efficacy of the DPKendall method through experiments on 25 datasets, each comparing different settings that apportion the privacy budget between a private feature selection method and a private linear regression method. The experimental results lend credence to the superiority of DPKendall over SubLasso in performing private linear regression, thereby highlighting its promise for this task. Moreover, the paper provides theoretical claims that the DPKendall methods is able to choose good features in the presence of many redundant features. ", "questions": "1) Could you provide a precise definition of what constitutes a \"plug-and-play\" algorithm? The proposed method necessitates the selection of parameter k, and also the budget split. How does this aspect impact the method's practical applicability?\n\n2) In Section 4.2, could you elucidate how the number of gradient boosting rounds T was determined for the BAS method? Were there instances where baselines had to allocate privacy budget for determining the parameter T for the BAS method?\n\n3) Would you clarify the execution of the K-BAS method, specifically referring to bullet 6 under Section 4.2? It is mentioned that 5% of the privacy budget was allocated to DPKendall and 95% to private linear regression. Is this accurate, or was there an allocation of 5% for model selection in this method as well?\n\n4) Has the Kendall rank correlation been employed in previous differential privacy-related work?\n\n5_ Are there any other potential downstream applications for private rank correlations? For instance, could it be utilized for Principal Component Analysis (PCA)?\n\n6) How does the optimal selection of k vary depending on the dataset?\n\n7) Could you explain the rationale behind the chosen split (5%) of the privacy budget in the conducted experiments?\n", "limitations": "yes.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper demonstrates the applicability of the Kendall rank correlation statistical technique under differential privacy, enabling the computation of correlations within unbounded data in a privacy-preserving manner, which is of significant utility. This approach is leveraged for private feature selection, serving as a dimension reduction technique aimed at facilitating private linear regression.\n\nThe paper offers both theoretical insights and empirical evidence for their proposed method. Theoretically, it presents a novel contribution by proving that DPKendall effectively identifies features that are correlated with the dependent variable. Empirically, it substantiates the practicality of DPKendall, demonstrating that its application for feature selection culminates in superior outcomes in linear regression.\n", "weaknesses": "The experimental outcomes indicate that the DPKendall approach exhibits enhanced performance compared to the alternative SubLasso method. However, DPKendall does not invariably outperform, and the experimental specifications remain somewhat ambiguous. Consequently, it would help to discern under which conditions DPKendall delivers superior results. Addressing questions such as the impact on performance as data dimensions escalate, or which method excels at varying parameter levels could provide valuable insights.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> Could you provide a precise definition of what constitutes a \"plug-and-play\" algorithm?\n\nSee the response to Comment 1 in the general response.\n\n> The proposed method necessitates the selection of parameter k, and also the budget split. How does this aspect impact the method's practical applicability? … How does the optimal selection of k vary depending on the dataset? Could you explain the rationale behind the chosen split (5%) of the privacy budget in the conducted experiments?\n\nSee the response to Comment 2 in the general response. We view the budget split as a still less important hyperparameter; the choice of 5% budget for each non-regression subroutine is meant to demonstrate that only a \"small\" budget is necessary for them.\n\n> In Section 4.2, could you elucidate how the number of gradient boosting rounds T was determined for the BAS method? Were there instances where baselines had to allocate privacy budget for determining the parameter T for the BAS method?\n\nWe always set the number of gradient boosting rounds $T$ to 100, so this choice did not consume any privacy budget. We chose $T = 100$ based on our reading of the experiments done by Tang et al.; note that the most recent Arxiv version of their paper also uses $T = 100$ for its experiments featuring fixed hyperparameters for BAS (see their Section A.1).\n\n> Would you clarify the execution of the K-BAS method, specifically referring to bullet 6 under Section 4.2? It is mentioned that 5% of the privacy budget was allocated to DPKendall and 95% to private linear regression. Is this accurate, or was there an allocation of 5% for model selection in this method as well?\n\nWe did not allocate 5% budget for model selection for K-BAS. This is because model selection only occurs when we use at least one of SubLasso or Tukey.\n\n> Has the Kendall rank correlation been employed in previous differential privacy-related work?\n\nTo the best of our knowledge, the only previous DP application is by KSSW16, as mentioned in the last paragraph of the Related Work section.\n\n> Are there any other potential downstream applications for private rank correlations? For instance, could it be utilized for Principal Component Analysis (PCA)?\n\nPrivate rank correlation is plausibly applicable in any setting where feature selection may be useful. It is not obvious to us how it could be applied to PCA, as private rank correlation relies on the existence of discrete candidate features to evaluate against labels; in contrast, PCA (informally) identifies high-variance directions from an infinite set of candidates.\n"}, {"review_id": "ITBHpW95w4", "reviewer": "Reviewer_itk8", "summary": "This work studies a differentially private feature selection method based on Kendall rank correlation as plug-and-play to make differentially private linear regression more suitable to high-dimensional problems without requiring users to set data bounds or algorithmic hyperparameters. This work provides e a utility guarantee for such private feature selection when features are normally distributed. This work conducts experiments across 25 datasets by applying DP-Kendall to Turkey and BAS to show the effectiveness of DP-Kendall.", "questions": "1. The current version of the paper provides the computation cost of DP-Kendall, DP-Lasso, and standard OLS. I wonder if it is possible to compare the utility guarantee with previous works.\n\n2. For the experiment part, it seems that the value of $k$ should not change the performance of baseline BAS and Turkey as these two do not include the feature selection step. Is the difference between these two methods in Figure 2 for $k=5$ and $k=10$ a result of random runs?\n", "limitations": "The paper states the following limitations:\n\n1. DPKendall requires an end user to choose the number of features k to select. \n\n2. DPKendall's use of Kendall rank correlation may struggle when ties are intrinsic to the data’s structure.\n\n3. Kendall rank correlation may fail to distinguish between a feature with a strong linear monotonic relationship with the label and a feature with a strong nonlinear monotonic relationship with the label.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This work makes the existing differentially private linear regression more suitable for high-dimension problems by a feature selection based on Kendall rank correlation. This work provides an analysis of how to make Kendall rank correlation DP and is also well-motivated why choosing Kendall rank correlation. \n\n2. DP-Kendall only incurs a little additional cost to privacy and computation.\n\n3. This work provides the utility guarantee for such DP feature selection when features are normally distributed. \n\n4. The experiments across 25 datasets show that DP-Kendall is necessary when the low-dimension assumption does not hold.  \n\n5. The paper is well-organized and easy to follow.", "weaknesses": "1. DPKendall requires an end user to choose the number of features k to select. The experiment result of $k=5$ and $k=10$ shows that the value of $k$ significantly changes the results, which indicates that it may not be easy to select a proper $k$.\n\n2. DPKendall's use of Kendall rank correlation may struggle when ties are intrinsic to the data’s structure.\n\nMinor:\n1. The experiment set-up considers $(\\epsilon, \\delta)=(\\ln 3, 1e-5)$, while some evaluated datasets have $n>100,000$ samples, and $1e-5$ is not smaller than such $1/n$. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> The current version of the paper provides the computation cost of DP-Kendall, DP-Lasso, and standard OLS. I wonder if it is possible to compare the utility guarantee with previous works.\n\nIdeally we would have a more direct comparison between DPKendall and SubLasso, but this is difficult, as the utility analysis provided in the SubLasso paper relies on several additional assumptions (see Assumption 1 and Assumption 2 in \"Private Convex Empirical Risk Minimization and High-dimensional Regression\", Kifer Smith Thakurta 12). \n\n> For the experiment part, it seems that the value of $k$ should not change the performance of baseline BAS and Tukey as these two do not include the feature selection step. Is the difference between these two methods in Figure 2 for $k=5$ and $k=10$ a result of random runs?\n\nThis is partially due to random runs, and partially due to the $k=10$ experiment omitting some of the $k=5$ datasets for having fewer than 10 features (see the footnote in Section 4.3.1). For example, BAS obtains $R^2 > 0$ on dataset 361094, but this dataset only has 6 features and is omitted for $k=10$.\n"}, {"review_id": "zpfP7fxcWT", "reviewer": "Reviewer_1cAJ", "summary": "the submission proposed a private feature selection algorithm that can be directly applied as a preprocessing step before any private linear regression algorithm. The algorithm itself is based on private top-k selection with the Kendall rank correlation, which has a constant sensitivity. Further experiments on 25 regression datasets demonstrate the effectiveness of the proposed algorithm compared to a different feature selection algorithm.", "questions": "please see the weaknesses above.", "limitations": "please see the weaknesses above.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. the choice of using Kendall rank correlation as the scoring function for features is smart, and it has a constant sensitivity. With an increasing number of data samples, the algorithm becomes more and more accurate.\n\n2. the experimental execution is thorough, and experimental results strongly supports the effectiveness of the algorithm.", "weaknesses": "1. the proposed private feature selection indeed improves both algorithms, but it also introduces a new hyperparameter. It would be great if the authors could provide recommendations on when to use the proposed feature selection and how to set the number of features to maintain (the submission indeed points out that 5 would be a good starting point, but I wonder if the authors could comment more).\n\n2. it seems that the performance of BAS by itself is worse than what Tang et al reported in their work. Perhaps the authors implemented the algorithm themselves, but since BAS is based on AdaSSP, I do recommend the authors check the implementation provided by Yu-Xiang Wang here: https://github.com/yuxiangw/autodp/blob/master/tutorials/tutorial_AdaSSP_vs_noisyGD.ipynb. A few additional cares are taken in the AdaSSP's implementation.\n\n3. Tukey itself is based on subsample and aggregate, so I think it might be interesting to integrate the feature selection step into Tukey as a whole algorithm rather than having two parts.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> It would be great if the authors could provide recommendations on when to use the proposed feature selection and how to set the number of features to maintain\n\nWe agree that more nuanced guidance for applying DPKendall would be useful. As a first cut, a reasonable heuristic may be to use it whenever the number of features is more than 5. This suggestion is based on two considerations. First, it is uncommon for feature selection to make utility worse (see Figure 4 in the Supplement, which shows that on ⅔ of databases K-BAS is better than BAS, and on all databases K-Tukey is better than Tukey). Second, DPKendall is \"cheap\" in terms of both privacy and computation, as we needed only 5% of the privacy budget and (asymptotically) no more computation over OLS in most settings (see discussion at the end of Section 3.2).\n\n> It seems that the performance of BAS by itself is worse than what Tang et al reported in their work. Perhaps the authors implemented the algorithm themselves, but since BAS is based on AdaSSP, I do recommend the authors check the implementation provided by Yu-Xiang Wang … [a] few additional cares are taken in the AdaSSP's implementation.\n\nIt is not obvious to us that the performance of BAS shown here is worse than that reported by Tang et al+. The only comparison present in both works is between BAS and Tukey, and both works find that BAS outperforms Tukey on a clear majority of datasets. We note that an author of the Tang et al paper examined our experiment code and pointed out that it does not add symmetric noise (as mentioned in the proof of Theorem 5.5 in Appendix A.6.3 in the first version of their paper). However, modifying our code to use symmetric noise did not noticeably affect the performance of BAS when we re-computed the median $R^2$ values, so we view this as a minor change.\n\n> Tukey itself is based on subsample and aggregate, so I think it might be interesting to integrate the feature selection step into Tukey as a whole algorithm rather than having two parts.\n\nWe experimented with a similar idea while writing this paper. In the approach we tried, we run (non-private) feature selection and regression on each model, and then run the (private) Tukey mechanism on the collection of models. This enables all of the privacy budget to be spent on the Tukey mechanism. However, the downside is that the features selected differ between models, so we end up with a collection of points (models) living in different subspaces of $\\mathbb{R}^d$. This worsens the performance of the Tukey mechanism, which is best when a sufficient number of models concentrate in a small volume in $\\mathbb{R}^d$. Overall, we found that integrating feature selection in this way produced poor utility. Moreover, since the additional privacy cost of feature selection is small in our experiments, we suggest that the hypothetical cost of omitting this integration is small anyway.\n"}]

Author rebuttal:
We thank the reviewers for their comments. A few comments appeared in multiple reviews, so we address them in this "global" response; we would be happy to add similar clarifying language to the next version of the paper. Other specific comments are addressed in the responses to individual reviews.

> Comment 1 (Reviewer 8Qm2, yU7m): Can you elaborate on what a plug-and-play private algorithm means and why it matters in the context of regression?

The phrase plug-and-play was originally used to describe computing devices that do not require extensive user setup. We borrow this phrase to describe private algorithms with similarly low requirements for user setup. Two classic private regression algorithms help illustrate this distinction.

AdaSSP ("Revisiting differentially private linear regression: optimal and adaptive prediction & estimation in unbounded domain", Wang 18) requires a user to provide bounds on the data's feature and label norms. Users often struggle to do this, as observed in empirical user studies by SSHSV+23 ("[s]everal depositors and analysts were unsure how to fill in the lower and upper bounds of numerical variables and resorted to educated guesses that ended up being far off from the actual bounds, causing the corresponding releases to be minimally informative"; "Don't Look at the Data! How Differential Privacy Reconfigures the Practices of Data Science", Sarathy Song Haque Schlatter Vadhan 23). AdaSSP's required user bounds are therefore a meaningful setup cost that impacts utility.

A second classic private regression algorithm, DPSGD, requires a user to configure hyperparameters including learning rate, clipping norms, batch size, and number of epochs. As observed by AJRV23, "[w]hile the optimal hyperparameters [for DPSGD] consistently produce results competitive with or sometimes exceeding that of [Tukey], even the mildly suboptimal hyperparameters nearly always produce results significantly worse than those of [Tukey]" ("Easy Differential Private Linear Regression", Amin Joseph Ribero Vassilvitskii 23). This demonstrates that significant per-dataset configuration is required for DPSGD to provide good utility, even if we ignore the privacy cost of configuration. 

For the reasons above, plug-and-play algorithms are important not only for ease of use but for overall utility, as careful and private tuning is often difficult for end users. This is why we suggest that this work, which broadens the applicability of existing plug-and-play private regression algorithms, is a meaningful contribution.

> Comment 2 (Reviewer yU7m, itk8, 1cAJ): What is the role of the choice of $k$?

We agree that the best possible version of our proposed algorithm would automatically choose $k$. However, we suggest that the provided experiments demonstrate that the application of DP-Kendall is relatively insensitive to the choice of $k$, in the sense that a single choice ($k=5$) yields good performance ($R^2 > 0$) on the majority of datasets. In contrast, private regression algorithms like AdaSSP and DPSGD require much more dataset-specific choices for their parameters. We note that $k=5$ and $k=10$ are the only parameters for $k$ that we evaluated, so $k=5$ is not a consequence of overfitting to the featured datasets. Finally, we also note that the comparison algorithm for plug-and-play DP feature selection, SubLasso, also requires the end user to choose $k$.


Meta-review: This paper studies the problem of private linear regression. The authors propose a preprocessing DP feature selection method for two “plug-and-play" private linear regression algorithms, which is useful for data with large feature dimensions. 

The reviewers are positive and agree that it is an interesting work, and easy to follow. To my understanding, this work is a good add-on to the “plug-and-play" private linear regression algorithms. However, as the reviewer point out the proposed method does not itself "solve" DP linear regression, especially for high-dimensional DP linear regression. 

In light of this, I recommend acceptance and encourage the authors to incorporate the discussion about other DP linear regression methods into the revision.
Decision: Accept (poster)