Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.
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. 

The 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? 

The 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). 

The 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. 

Page 3. The last sentence has two full stops.

I 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. 

The first sentence of the second paragraph in Sec 3.2 does not make any sense. 

I 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. 
clarity,_quality,_novelty_and_reproducibility: The quality of the writing is good with some (not so surprising) novel aspects. Also, I am a little worried about no comparison with the prior work with respect to the utility guarantee. The paper seems to have a more theoretical feel to it, hence I would like to see a comparison on that front. 
summary_of_the_review: Please see above. 

I 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.
review_title: null

final_score: rating: 8: accept, good paper
review_content: 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. 
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
2. 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.
Weaknesses: 1. Unlike prior works, no utility guarantees are provided here for Gaussian data using approximate tukey depth.
2. 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. 



Questions:
1. 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?
2. 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? 
3. 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?
clarity,_quality,_novelty_and_reproducibility: 1. This paper is written well.
2. The proposed method is technically novel.
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.
review_title: null

final_score: rating: 8: accept, good paper
review_content: 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.

The algorithm run time is O(d^2 n + dm log(m))---where generally m << n. 

The algorithm is also justified by experiments.

strength_and_weaknesses: Strengths:
(1) The motivation and goal are clear and compelling.
(2) The algorithm is indeed easy to use for the end-user. The only remaining trouble is the need for this parameter m.
(3) The paper is generally well written, and gives the reader intuition along with technical definitions and theorems.
(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.

Weakness: 
(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) 
(2) The possibility that the algorithm fails to return a model for some reasonable specifications of m seems annoying.
(3) The time complexity suggests that the method is not well suited for high-dimensional data.

clarity,_quality,_novelty_and_reproducibility: The paper is well written. The problem is interesting. The algorithm seems to be novel.

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.

NOTE: 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).
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
strength_and_weaknesses: Strengths: 

The 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). 

Weaknesses: 

1. 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? 

2. 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?

3. 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? 

4. In Algorithm 2, line 2 the authors partition X not only "randomly," but also "evenly." Is there a particular reason for even partitioning?

5. How about the prediction performance of TukeyEM? If I am not mistaken, the authors have not provided any discussion on this part.

6. 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)?

7. 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.
clarity,_quality,_novelty_and_reproducibility: This paper proposes a method for private linear regression setting. Their Tukey depth-based method generalizes the previous work and allows to work with datasets with larger feature size than the existing methods. Paper is well-designed and highly detailed as the authors provide proofs and details elaboratively throughout the paper. Also, they discuss several possible drawbacks of their method extensively.
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.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper gives a method for differentially private linear regression that is simpler and claimed to be more practical compared to previous approaches. A key idea is leveraging the Tukey median -- an intractable to compute multivariate generalization of the median with good robustness properties. The authors propose some heuristic approximations to the Tukey median that seem to give good practical performance, and use standard tools to privatize it. Overall, the reviewers considered this submission to be a solid contribution that is appropriate for ICLR. 
justification_for_why_not_higher_score: There are certain disadvantages to this work, including a heuristic selection of some parameters and the fact that the experimental results are in fairly low dimension. 
justification_for_why_not_lower_score: Based on the reviews, scores, and my own reading, the paper appears to be an interesting contribution.
Decision: Accept: poster