Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper studies the problem of robust linear regression and demonstrates two algorithms which improves the breakdown point for this algorithm under adversarial attacks compared to prior work.

The main contribution is the observation that, with some prior information, even if it is far from the truth, it is possible to improve the breakdown point and find a consistent estimator for the problem. Prior work was able to find consistent estimators only in the setting where the corruption vector was chosen oblivious to the measurements. 

The authors consider the Adaptive Adversarial Attacks (AAA)  setting where the observations are given by $(X, y)$, where $X \in \mathbb{R}^{d \times n}$ and $y \in \mathbb{R}^n$. The observations satisfy $y = Xw^* + b^* + \epsilon$ where $w^*$ is the true regression coefficient, $\epsilon$ is the dense noise and $b^*$ is an arbitrary $k^*$-sparse vector. The goal is to recover $(\hat{w}, \hat{S})$ where $\hat{w}$ is close to $w^*$ and $\hat{S}$ is an estimate of the uncorrupted sample set.  The authors assume that the variance of the noise $\epsilon$ can be controlled by the algorithm designer and be set to $\sigma$, or can be estimated independently to a high degree of accuracy. 

The first algorithm (TRIP) assumes the prior on $w*$ is $\mathcal N(w_0, \Sigma_0)$ for some $w_0$ and $\Sigma_0$ determined in advance. This essentially leads to the problem being transformed into a regularised least squares problem, which they solve by a hard-thresholding approach similar to [1]. The second algorithm is more complicated and assumes a prior also on the local weight assigned to specific samples and uses variational Bayesian expectation maximization to solve a reweighted probabilistic model for linear regression. 

strengths_and_weaknesses: Strengths: 

It is qualitatively interesting that bayesian updates can lead to consistent estimators in the AAA setting. I like the result. 


Weaknesses: 

1. I feel that the authors need to place the result in the context of the surrounding literature a little better. This paper considers the model where only the labels are corrupted (i.e. only $y$) while the result by Diakonikolas et al. [6] (mentioned on line 53) is for the setting where both the $X$ as well as $y$ values might be corrupted. 

2. Additionally, further comparison with [2] would be helpful, since the goal of this paper seems to be to achieve a good breakdown point for the AAA setting, which I feel [2] also addresses, as opposed to [1] which only deals with the oblivious setting (with the additional goal of being a consistent estimator, i.e. if the dense additive noise is mean 0, the goal here is for the estimator to achieve error going to 0 as the number of samples tends to infinity). 

3. Another paper to cite might be https://arxiv.org/abs/1809.08055, which attempts to solve the problem using L1-regression but it appears this is not a consistent estimator. 

4. I found the paper a little hard to understand. Clearer motivation and a description of the algorithm would have been helpful. I would also have liked there to be more intuition and a comparison of the difference in terms of the algorithms and updates from [1] and [2] that would help the reader better understand how the assumption of the prior helps. 

[1] Kush Bhatia, Prateek Jain, Parameswaran Kamalaruban, and Purushottam Kar. Consistent robust regression. Advances in Neural Information Processing Systems, 30, 2017.

[2] Kush Bhatia, Prateek Jain, and Purushottam Kar. Robust regression via hard thresholding. Advances in Neural Information Processing Systems, 28, 2015.

questions: 1. It would be good to explicitly write down the breakdown point achieved in the case of a Gaussian. For instance [2] explicitly says that one lower bound for the breakdown point is 1/65. 
2. I would be curious to see how this algorithm performs with the following noise model from [3]: Samples $(x, y)$ where $x \sim N(0, 1)$ and $y = 100 x$, where the adversary looks at the $\epsilon$ fraction of the $x_i$ such that $|x_i|$ is maximized, and then sets the corresponding $y$ to 0. The plot of the error $\| \widehat w - w^* \|$ vs $\epsilon$ might shed light on the comparison between breakdown points in the case of a Gaussian. While I understand that the goal is to provide a consistent estimator, It might be clearer to see the performance of the algorithm and the breakdown point for an example with no additive error. 
3. Could the authors please explain for my understanding, intuitively, why the existence of the prior allows one to solve the problem in the harder adversarial setting? Somehow this has still escaped me. 

I will reconsider my score depending on the answers to these questions. 

-----

Update: The authors have addressed all questions raised, and I have updated the score to reflect my new assessment. I still have some concern about the theoretical breakdown point, but the algorithms seem to perform well on noise models which previous algorithms fail on. 
limitations: This is a theoretical result with limited societal impact.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper works on robust least-squares regression of the form $\mathbf{y} = X^{T}\mathbf{w}^* + \mathbf{b}^* + \boldsymbol{\epsilon}$, where $\mathbf{b}^*$ represents a $k$-sparse adversarial perturbation. Specifically, it proposes a Bayesian extension of the Hard Thresholding method previously designed against oblivious adversarial attacks (OAAs), to make it resistant against (a stronger) adaptive adversarial attacks (AAAs), that assumes an adversary having an access to $X$, $\mathbf{w}^*$ and $\boldsymbol{\epsilon}$ before attacks. Two methods are proposed, namely TRIP and BRHT, that incorporate a Gaussian prior on weights $w$ and additionally on exponential weighting $r$, respectively. The paper provides both theoretical convergence analysis and empirical results showing that the proposed methods are more robust under AAAs while also improving under the prior setup of OAAs. 
strengths_and_weaknesses: **Strengths**

- The paper is clearly-written, e.g., it clearly presents the problem formulation and methodologies.
- The proposed methods are simple, and well-motivated.
- The paper conducts empirical analysis to support the claims and reports improved results. In the experiments, the paper designs an adaptive attack scheme ADCA in a similar manner to TRIP but in the opposite direction in optimization.

**Weaknesses** 

- Given that AAA is assumed to be an adversary, a more diverse attack methods could be considered - the current attack method of ADCA is designed to be quite close to TRIP, and it is likely that TRIP performs better than others under ADCA because it is just trained as an opposite of ADCA and may not generalize under other ways of attacks.
- Although it is still novel to me that the paper aims for adversarial robustness, Bayesian approaches on weights and loss coefficients have been quite known approaches in general so some readers may concern on the technical novelty on the method.
questions: - Section 3.1: Is the proposed hard-thresholding based method actually induced from assuming Gaussian weight prior, or they are just orthogonal, i.e., TRIP works without the prior? More explanation on the relationship between the prior assumption and TRIP may help.
- For TRIP, I feel it is a bit unclear why one should assume the Gaussian prior for robustness against AAAs, but perhaps not for others? If not, the paper could empirically explore the effect of using different priors on weights.
- Line 115: More discussions could be made on how mild the assumed SSC and SSS conditions in both theoretical and empirical senses?
limitations: The paper does not include discussions on potential negative societal impact.
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: The authors study the robust least-squares regression (RLSR). The main contribution of this paper is to propose an algorithm that achieves strong results in terms of resisting adaptive adversarial attacks. A theoretical convergence analysis is provided. Extensive experiments have illustrated that their algorithms outperform SOTA methods in terms of both robustness and efficiency.
strengths_and_weaknesses: Originality: The related works are adequately cited. The novelty of this paper is high. The results on robust least-squares regression in this paper, will certainly help us have a better understating of adversarial attacks and defenses from a theoretical way. I have checked the technique parts and find that the proofs are solid. I think this is a significant contribution to machine learning immunity. 

Quality: This paper is technically sound.

Clarity: This paper is clearly written and well organized. I find it easy to follow.

Significance: I think the results in this paper is significant, as explained above.  
questions: It is better to conduct more experiments in more complicated settings.
limitations: Yes, the authors have adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

Meta-review: metareview: The paper studies the problem of label-outlier robust regression with prior on the optimal parameter. The reviewers agree that the results are novel and significant. There is certainly a concern about the novelty of the method and about additional insights provided by the result. However, as the paper studies this relatively new problem and provides solid results for it, we  recommend accepting it for publication. 
confidence: Certain
Decision: Accept