Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper studies the problem of differentially private linear regression with potentially corrupted labels. To handle the corrupted labels, the authors proposed a new private adaptive clipping technique. The proposed method can deal with both privacy concerns and corrupted labels. The experiment results validate the effectiveness of the proposed method in the corrupted setting. Furthermore, the authors claim that the proposed method can also improve the sample complexity requirements to achieve a certain level of accuracy in the noncorrupted case compared with existing methods.
strength_and_weaknesses: The strength of the paper:
1. The proposed method is able to handle corrupted labels.
2. Experiments validate the effectiveness of the proposed method.

The weaknesses of the paper:
1. In the noncorrupted setting, it is unclear to me why it can improve the sample complexity requirement compared with Varshney et al. 2022. For the minibatch method proposed by Varshney et al. 2022, it seems that the minibatch size is chosen in the order of the full batch size. Thus it is unclear to me why using the full gradient as suggested in this paper can improve the sample complexity? Whether the improvement comes from Algorithm 2? These need to be further clarified.
2. The requirements on $S_1$, $S_2$ and $S_3$ are not clear.
3. Why the requirement of $n$ in equation (5) is independent of $\kappa$? According to the last inequality on Page 16, it seems that the $\bar \alpha$ depends on $\kappa$, and thus $n$ should also depend on $\kappa$.
4. Although the proposed method is able to handle label corruption, the corruption level is so small that it should be less than the desired accuracy level. Can you relax this requirement?
clarity,_quality,_novelty_and_reproducibility: The presentation is OK, and the proposed method looks novel, but it needs further clarification on the improvements.
summary_of_the_review: The author proposed an efficient, robust, and differentially private algorithm for solving the linear regression problem. The proposed method seems to be promising. However, it suffers from the low corruption level and the improvements over the previous method in the noncorrupted setting are unclear.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: Authors study linear regression from a differential privacy perspective. They propose a variant of the differentially private stochastic gradient descent (DP-SGD) algorithm with two innovations: a full-batch gradient descent to improve sample complexity and an adaptive clipping to guarantee robustness. Some theoretical results and empirical evidence are presented.

strength_and_weaknesses: Strengths:


Authors have a good grasp of some of the challenges of differentially private computations in the linear regression context. The paper is well-written. Section~4 on adaptive clipping is an interesting contribution, where I think the results can be improved, but the approach of using a a robust approach and trying to enforce differential privacy on it is interesting. 


Weakness:

A few of the weaknesses are technical and can possibly be easily corrected. However, some of the weaknesses are probably not adjustable with minor changes. 

1) The use of sub-Weibull distributions is more of a distraction. This is primarily because we would want the differentially private estimator to have consistency and other desirable statistical properties, for which sub-Gaussian conditions are often necessary. It is not clear what sub-Weibull adds to either the robustness or differential privacy components of this paper. Also, this assumption does not seem verifiable. 

2) The requirement that $\bar{\alpha}$ is known in Assumption 2, and the complex bound for it seem unverifiable and not very practical. 

3) For high-dimensional regression, it is not clear that the proposed scheme can achieve sparsistency. 

4) Along the same lines, it is entirely possible that the norm or non-zero elements of a sparse $w^{*}$ may not have any relation with the leading eigen values/vectors of $\Sigma$. Hence it is not clear the bounds for the weighted loss function considered here relate to the sparsity of $w^{*}$ or the noise variance.

4) Also, it is not clear what additional complexity is arising from the corruption in the labels arising from an adversarial framework. This would only make sense if an oracle knew the original observations (indexed by $S_{r}$), and the proposed algorithm achieved some kind of a risk bound with respect to this oracle. Since the corruption can be arbitrary, it seems a standard robust statistics approach would have been sufficient here. 


clarity,_quality,_novelty_and_reproducibility: The paper is clearly written, the quality of the empirical work seems fine but there is a lack of adequate theoretical developments. The algorithm may have some elements of novelty, and the results look reproducible.

summary_of_the_review: This is an interesting paper overall, but when we dig a little deeper there are several unanswered questions.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies the problem of linear regression under DP constraint and adversarial corruption. The authors propose a kind of variant of DP-SGD with a full-batch GD to improve sample complexity and adaptive clipping to guarantee robustness. Their theoretical results can improve the SOTA sample complexity without adversarial corruption. Under label corruption, they give the first provably linear regression algorithm to guarantee both DP and robustness. They also give experimental results on synthetic data to verify their theoretical results.


strength_and_weaknesses: Strength:
The paper is well-motivated since privacy and robustness become more and more important in ML model. This is the first efficient linear regression algorithm to provably guarantee both DP and robustness. The authors propose a private norm estimator and a robust private distance estimator by using private histogram mechanism for adaptive clipping and also give theoretical results for this algorithm. Based on this algorithm, they propose their DP-SGD method. The authors give both theoretical sample complexity and experimental results for the method. The proofs seem to be correct, and the experimental results also accord with their analysis.

Weaknesses:
1. The lower bound in Section 3.3 is not clear.
2.  The ‘n’ in equation (1) should be B_t.
3.  The step 1 of algorithm 1 should be three subsets.


clarity,_quality,_novelty_and_reproducibility: I found the problem statement of the paper interesting and important. The authors nicely combine literatures from the DP linear regression and Robust linear regression to produce useful algorithms for the proposed setting. The authors have adequately cited related work as well as honestly commented on differences and similarities with existing literature. I think the paper is well-written. It would be good to bring the experiments in the main body. The submission looks technically sound and makes a solid theoretical contribution.  I didn't completely go through proofs but the intuition of breaking gradient update into contraction, noise from data and DP, bias introduced by clipping and corruption makes sense. I think the algorithms and the provided guarantees are important because the work can be applied in fields where adversary emerges and where there is a also a need of privacy and robustness like networks and finance.


summary_of_the_review: The lower bound is not clear.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies linear regression from i.i.d. examples under $(\epsilon, \delta)$-differential privacy in the settings (i) where there is no adversary and (ii) when a fraction of response variables are adversarially corrupted. While there exists a clear understanding about the optimal (inefficient) private and robust algorithm that solves this problem (namely the HPTR algorithm), it is not known whether this optimal sample complexity can be attained by a computationally efficient algorithm. Hence, this paper aims to improve on the number of samples required by the previous best-known algorithm by Varshney et al. (2022). This improvement is obtained by DP-SGD with some additional ideas.

strength_and_weaknesses: At a technical level, the authors analyze DP-SGD for the linear regression problem (without an adversary) using two additional ideas. First, the work of Varshney et al. (2022) proposes a single pass approach while, in this work, a full-batch gradient descent algorithm is employed. This gives an improvement in the sample complexity. Second, adaptive clipping is used in order to ensure robustness against label-corruption. 

In general, the paper is interesting and the result is nice. The  proposed private algorithm attains an improved sample complexity guarantee while being computationally efficient and robust to label noise. My main concern deals with the issue of technical novelty; the paper relies on standard techniques for achieving privacy (e.g., private histograms) and robustness (e.g., resilience). While the clipping idea is nice, it is essentially ad-hoc for label noise and cannot handle corruption in the covariates. Nevertheless, I believe that the contribution is sufficient for acceptance.

The paper is mostly well-written (there are various typos that can be fixed) and the results and previous work are clearly presented. 

clarity,_quality,_novelty_and_reproducibility: The result is clear and well-presented. There are various typos in the text which should be fixed.
summary_of_the_review: The authors provide an efficient private and robust algorithm for linear regression, improving on the previous sample complexity bound. I believe that the contribution is beyond the acceptance threshold.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: In this work, the authors study the problem of linear regression under $(\varepsilon,\delta)$-differential privacy when a fraction of response variables are adversarially corrupted. They propose a variant of the differentially private stochastic gradient descent (DP-SGD) algorithm that uses a full-batch gradient descent along with an adaptive clipping to guarantee robustness. When there is no adversarial corruption, the algorithm achieves near-optimal sample complexity and improves upon the existing state-of-the-art approach. The authors claim that under label corruption, it is the first efficient linear regression algorithm to provably guarantee both $(\epsilon,\delta)$-DP and robustness. 

The reviewers liked the fact that the proposed method is able to handle corrupted labels and thought the experiments somewhat validated the effectiveness of the method. The reviewers raised a variety of issues including. (1) lack of clarity that sample complexity can be improved compared to Varshney et al in the non-corrupted setting, (2) equation (5) being a restrictive requirement (3) corruption level too restrictive (3) impracticality of Assumption 2. The authors provided a thorough response. This response however does not address all of the issues raised. My own reading is that this paper studies an interesting problem but in its current form is not ready for prime time and therefore I can not recommend acceptance.





justification_for_why_not_higher_score: The paper has a few technical issues and does not merit acceptance
Decision: Reject