Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: The paper studies the problem of differentially private linear regression and develops a new algorithm for this problem based on privately calculating 1-dimensional medians. The algorithm is based on the Theil-Sen estimator and uses the exponential mechanism to privately estimate the medians required for this estimator. The authors present a utility guarantee for their algorithm with Gaussian features and Gaussian noise. Moreover, they provide some experiments over synthetic datasets that compare their algorithm to existing algorithms.
strengths_and_weaknesses: The paper studies an important problem (private linear regression). However, I think the authors need to present more theoretical results, comparison to prior work, and experimental evidence to make this paper more compelling.

Weaknesses
1.	The main (and only) theoretical result in the paper provides utility guarantees for the proposed algorithm only when the features and noise are Gaussian. This is a strong requirement on the data, especially given that previous algorithms don’t need this assumption as well. Moreover, the authors should compare the rates achieved by their procedure to existing rates in the literature.
2.	Experiments: the experimental results in the paper don’t provide a convincing argument for their algorithms. First, all of the experiments are done over synthetic data. Moreover, the authors only consider low-dimensional datasets where d<30 and therefore it is not clear if the same improvements hold for high-dimensional problems. Finally, it is not clear whether the authors used any hyper-parameter tuning for DP-GD (or DP-SGD); this could result in significantly better results for DP-GD.
3.	Writing: I encourage the authors to improve the writing in this paper. For example, the introduction could use more work on setting up the problem, stating the main results and comparing to previous work, before moving on to present the algorithm (which is done too soon in the current version). 


More:

1.	Typo (first sentence): “is a standard”
2.	First paragraph in page 4 has m. What is m? Should that be n?


questions: No
limitations: Yes
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper addresses the problem of differentially private linear regression. Specifically, current DP methods need access to the sensitivity of the query which is in practice hard to compute. Alternative methods clip the data, harming performance. This paper proposes a method that relies on privately computing a multidimensional “median”, a good estimator for the mean under certain assumptions and that has smaller sensitivity. 
strengths_and_weaknesses: *Strengths*
- Nice analysis and intuition for Gaussian data.
- Very clear and organized. 
- Good related work and comparison section.


*Weaknesses*: 
- Missing relevant recent work on DP-medians/quantiles. 
- Experiments only test on synthetic data that meets the assumption. However, finding a reasonable r (even in small settings) could be hard. 
- Data complexity could be rather large, and prohibitive in real settings where linear regression datasets are rather small.
- The high dimensional median proposed in step 15 may not even be an interior point in the convex closure of the data points. 

questions: - How to compute range R in real applications? if R is set too large, then the exponential mechanism will add too much mass to small depth points, and if it is too small, the range may not even contain the real model. 
- How does the restriction in line 80 compares to clipping?
- Why use the max instead of the min in the score function? Wouldn't this assign very high utility to a point in the boundary?
- Why is $\sigma$ described as a parameter? I don’t see it used for any pre-processing or actual algorithm step. 
- Can you discuss the choice of hyperparameters for DP-GD?
- Can you discuss the results in figure 5? why does the Widened Exponential from [AMSSV22] degrade in lower dimensions?

limitations: - The paper motivates well the use of a "high dimensional private median" for DP linear regression. However, it is not clear how this will overcome the challenges that current methods face, like clipping, since setting a range R is basically finding a clipping rate. 
- Step 15 for calculating the median could result in a point outside the closure of datapoints. A common example for this is having points (1,0,0), (0,1,0), and (0,0,1). Taking the median along each axis results in (0,0,0) which is outside the plane defined by the three points. 
- Experimental section is based on synthetic data that follows the assumptions on theorem and thus provides guidance on how to select the parameters, however, realistic datasets may behave very differently.
- Experimental section only compares to one set of fixed parameters of DP-SGD. Perhaps following guidance from theory or discussing the choice of hyperparameters for DP-GD could justify this choice. 

In general, the paper proposes an alternative approach but that still requires an equivalent to clipping, and this is not addressed neither theoretically nor empirically.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper studies differentially private linear regression with known covariance for isotropic Gaussian data. The algorithm is based on the median-of-mean scheme and Theil-Sen estimator. It first splits the data into different partitions, then solves the solutions for each partition, and computes the univariate median for each coordinate of the solutions using the exponential mechanism. For approximate DP, the extra cost of privacy in terms of infinity norm is $O(d^{1.5}/\varepsilon n)$, which has a $O(d^{0.5})$ gap to the lower bound. The primary advantage of this algorithm is that it does not need any clipping, which is more practical. Empirically, this paper provides extensive experiments and shows better performance for d=10, 20, 30 compared to a few baselines. 
strengths_and_weaknesses: Strengths: 1. This algorithm is simple and practical. 
2. The presentation of this paper is clear. The structure is easy to follow.


Limitations: 1. Compared to prior works, for example [VJT22], this algorithm is not optimal. 1) Under the euclidian norm and gaussian data, the algorithm in [VJT22] has extra privacy cost $O(d/(\varepsilon n))$. The extra cost here is $O(d^{1.5}/\varepsilon n)$ in infinity norm. 2) This paper requires prior knowledge of the covariance of the Gaussian. 3) The loss is for infinity norm, which has $d^{0.5}$ gap to the euclidean norm. 4) In the experiments, this paper does not compare the algorithm with [VJT22], which shouldn't be too hard to implement.

2. Similar ideas have been used for mean estimation with sub-gaussian rates [1], DP mean estimation [2], linear regression[3]. It seems that, as a byproduct of the median of mean scheme, these types of algorithms could also provide provable robustness guarantees against corruption of the data. This is not discussed in this paper. Also, it would be better if the authors could add some related works in these topics.


[1] Hopkins, S. B. (2020). Mean estimation with sub-Gaussian rates in polynomial time. The Annals of Statistics, 48(2), 1193-1213. 
[2] Hopkins, S. B., Kamath, G., & Majid, M. (2022, June). Efficient mean estimation with pure differential privacy via a sum-of-squares exponential mechanism. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (pp. 1406-1417).
[3] Depersin, J. (2020). A spectral algorithm for robust regression with subgaussian rates. arXiv preprint arXiv:2007.06072.

questions: 1. Why is the size of each partition chosen as d?

2. Theorem 1 runs algorithm 1.1 with $\ell=1$. How does different choices of $\ell$ affect the utility guarantees?
limitations: This paper is theoretical and does not have a direct negative societal impact.
review_title: null

Meta-review: metareview: Though the reviewers appreciate the contribution overall, and the application of median methods to regression for the purpose of avoiding/circumventing clipping is novel, the strength of the contributions remains limited in light of other existing work that achieves more favorable bounds and/or uses fewer assumptions. This is certainly the case for  (unpublished) [VJT22], but it is also the case for [MKFI22], which also assumes Gaussian inputs but, crucially, does not rely on prior knowledge of the distribution's covariance. Moreover, in light of the effort required to perform DP covariance estimation via [KLSU19], it is not clear that, as stated in the rebuttal, an error proportional to condition number is non-trivial. For example, it is not clear that, allowing for such error, processes like [KLSU19], do not become trivial.

A reorganization of the paper, that brings related work earlier, and explains what is known regarding regression in the unbounded regime (especially in light of [VJT22],[MKFI22]) but also on DP for other settings in the unbounded regime, and where the current work is placed/what the contributions beyond these works are, would strengthen the paper. 


confidence: Certain
Decision: Reject