Robust Nonparametric Regression under Poisoning Attack

Summary

The paper studies robust nonparametric regression under poisoning attacks. The input is samples from some fixed distribution and the goal is to approximate some unknown function on the input space. It is assumed that the values observed in q of the samples are adversarial. In this setting, classical approaches such as k-NN estimators can fail. This is because a single adversarial sample can affect the prediction on many points. In order to avoid this issue, the paper proposes robust variants of nonparametric regression. The first result is a bound on the convergence rate of an M-estimator based on Huber loss minimization: the initial estimator has minimal optimal ell_infinity risk. When the number of adversarial samples is not too big, the ell_2 risk is optimal. It is also shown that the estimator can suffer when many of the adversarial samples are concentrated within a small region. In order to resolve this issue, the paper proposes a correction step that projects the estimator into the space of Lipschitz functions. Upper bounds on the rate of convergence of the corrected estimator are established. Numerical results show that both estimators outperform standard methods in a simple low-dimensional synthetic scenario.

Strengths

Nonparametric regression is a fundamental problem. The paper studies a natural adversarial setting where a small number of input samples are corrupted adversarially. This research direction can produce more robust useful data-analytic methods. The upper and lower bounds match up to polylogarithmic factors when the number of adversarial samples is not too large.

Weaknesses

The experimental evaluation is very limited. This is unclear whether the proposed methods can lead to significant robustness improvements in real-world scenarios. No runtime analysis is given for the corrected estimator. This is a continuous optimization problem, so it is not clear how easy it is to solve in practice, especially in high or moderately-high dimensions.

Questions

Assumption 1, c: The quantifier for x is missing. In line 253, I don't quite understand the justification for using ell_1 norm in the optimization problem. Since ell_2 imposes a larger cost in the error region, it would seem that this makes it easier to remove spikes. Definition 1 (3): One of the two floors should be a ceiling.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

3 good

Contribution

2 fair

Limitations

The authors have adequately addressed the limitations of their work.

Summary

A robust version of the classic non-parametric problem is studied, when the training data is under an adversarial poisoning attack. The work is primarily theoretical, and makes assumptions on Lipschitzness and boundedness of the underlying function, boundedness of the data density, restrictions on sharpness of the data domain boundary, sub exponential noise. With some restrictions on the kernel, and appropriate parameters, upper bounds are shown on the $\ell_2$ and $\ell_\infty$ loss for the robust regression fit using Huber loss minimization. Lower bounds are obtained under the same assumptions, which match asymptotically with the upper bounds for $\ell_\infty$ and a correction is presented to match the upper bound for $\ell_2$ loss as well. Numerical simulations show usefulness of the algorithms on simulated one and two dimensional data.

Strengths

1. The authors study robust nonparametric regression under poisoning attacks for smooth underlying functions under certain assumptions on the data and domain, under which asymptotically tight rates are obtained for $\ell_\infty$ loss by suitably parameterized Huber loss. 2. A novel correction method is proposed for which tight rates are obtained for $\ell_2$ loss as well. Together with above, the optimal algorithms under the given assumptions are obtained for both losses. 3. Numerical simulations are performed to verify the theoretical results.

Weaknesses

1. The assumption needed for proving the theoretical result, specifically assumption 1(b) is too strong. Effectively, it reduces the possible test distributions to "near-uniform" distributions since there is both an upper and a lower bound on the probability density function. This assumption is too strong to make the results useful in most practical situations. 2. No insights is provided into the proofs of the theoretical results; in particular there are no proof sketches in the main body. This makes it challenging to understand the contributions, given the work is primarily theoretical. 3. Experiments only involve very specific numerical simulations. How does the approach work on real regression datasets? The effect of changing the hyperparameters is not studied and how they are selected is not described. 4. Huber loss is already known as a technique for robust nonparametric regression [1] and is not novel, the paper should mention that only the analysis under the present assumptions is new. The novel correction method is computationally intractable. [1] Maronna, R. A., Martin, R. D., Yohai, V. J., & Salibián-Barrera, M. (2019). Robust statistics: theory and methods (with R). John Wiley & Sons.

Questions

1. What is the intuitive behind needing assumption (c)? Do sharp corners make the model more susceptible to attack by a poisoning adversary? 2. Line 190-191 looks like notational overload for $h$? 3. How do T/M/h settings in the numerical simulations compare to theory?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

2 fair

Limitations

The authors note several limitations of their work in a dedicated section.

Summary

The authors propose two new nonparametric regression methods that and study their resilience under poisoning attacks. The baseline for comparing the performance of the proposed methods is kernel regression (aka Nadaraya-Watson estimator). The proposed methods are two, since the initial idea that the authors have, turns out to be vulnerable to poisoning attacks that are concentrated in small regions and a large budget is spent there. Hence, the authors arrive at a `corrected' estimator which behaves better and is closer to optimal behavior. After rebuttal: For the largest part I believe that the authors have provided sufficient clarifications to various issues that were raised and moreover are willing to integrate comments and clarifications that came up during the discussion period in the final version of the manuscript. Therefore, I am increasing my score from reject to borderline accept; I am also increasing the soundness from fair to good as well as the presentation from poor to fair.

Strengths

+ New methods for regression that are resilient to poisoning attacks. + Both theoretical and practical results.

Weaknesses

+ Missing a section with preliminaries or background knowledge, where notions and notation that the authors use in the paper is well-defined. For example, in the section for preliminaries you can give information such as: - define loss functions, - discuss kernel regression and separate the presentation from your initial estimator, - discuss notions that you use when it is unclear what these things are; e.g., "bandwidth". - define functions that you use without explanations at the moment; e.g., in (18) we see Clip and med; what are the arguments and what do these functions do? + References not in alphabetical order. + In line 52-54, you indicate that your approach is similar to a combination of an $\ell_1$ and $\ell_2$ loss functions. At that point in the text, I was expecting a comparison with "elastic nets"; you may want to consider adding a small comment, or consider rephrasing and avoid such expectations from the readers. + The order by which some things are presented should probably change. For example, in lines 115-124, I think you need to give a slightly better explanation so that the reader can get better intuition, and moreover, this discussion should come up before you lay out the equations of the method that you propose. + You cannot start sentences with as in lines 167 or 168. You could add a word like "Part" or "Parts" in the beginning and make it read more naturally even if it takes a bit more space. + Larger font size in Figure 1 is expected. + It would be nice to see some commentary on the bounds and argue how they compare against each other and potentially compared to other methods that you cite in the literature. + In general, you have no comparison with parametric methods, either in theory, or in the experiments. Alternatively, provide an explanation as to why you don't have such comparisons. + It is unfortunate and normally it should not be an issue, but the authors need help on writing a paper that has fewer spelling or expression mistakes. The additional problem here is that the authors also have a big appendix, which I suspect is written similarly along the main text. So, fixing the main text is not enough. The paper needs to be proofread by someone in its entirety, including the appendix of the authors. I think that you have a very interesting story to tell, but the paper needs restructuring and better presentation of what you have accomplished.

Questions

Q1. In line 152, you define $D$ but this parameter does not show up anywhere. Q2. In line 243, what is a "linear filter"? Q3. In line 276, what do you mean by "optimal bandwidth"? Q4. In line 308, what do you mean by "number of grids"? Q5. What is $m$ in (18)? Q6. Why don't you have some comparisons with parametric methods?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

N/A

Summary

This paper studies nonparametric regression, where an adversary can corrupt $q$ samples from the training set. The paper proposes robust estimators for this problem.

Strengths

The paper studied the Huber loss minimization approach under adversarial noise, giving theoretical upper bounds and lower bounds.

Weaknesses

The organization could be improved, e.g. the last two paragraphs of section 3 could conceivably be placed elsewhere. Some aspects of this paper are not really my area, so I cannot provide many helpful comments.

Questions

Equation 2 and 3, what is expectation taken over?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

The author addressed limitations.

Thank you for the response

**References not in alphabetical order** I have always interpreted the quoted text as not mixing citation styles (e.g., in some parts one says "Hasselmo et al. (1995), while in other parts says [3]). In the .tex file that is provided as an example by NeurIPS, indeed, [3] is cited first and all the references are in alphabetical order. So, alphabetical order seems to be the right approach; not the order by which you cite the papers in the main text. **Elastic net** All I am saying is that some clarification should appear in the text, which is non-existent in the current form. **Comparison with parametric methods** One could identify the cases/domains where parametric/non-parametric methods are more suitable on real-world datasets and nevertheless compare the methods to see how far off their estimates are. I think it is still interesting to understand how much the results differ in various cases and the extent to which various assumptions hold on real datasets. I appreciate all your responses. Indeed, my opinion for the paper has improved, but I still cannot recommend acceptance.

Reply to rebuttal

Thanks for the detailed response. In particular, thank you for answering my questions and highlighting the difference relative to prior work. Regarding the "strong density assumption", as I suspected it is a relatively _strong_ assumption to study. For example, Audibert et al. 2007 also study the "mild density assumption" and also obtain optimal learning rates under it, which is more interesting. It would be good to include a discussion of the related work (thanks for providing it!) on the "strong density assumption" and mention that going beyond this assumption (potentially using the adaptivity techniques you mention) would be interesting. Despite the relatively strong assumption, the techniques could still be interesting to researchers. However, the lack of any proof sketches makes it harder to glean the technical novelties. It would be great to include proof sketches and more experiments (e.g. including real regression data) in your revision. `We are not sure about the meaning of 'notational overload'. ` Regarding the notational overload in lines 190-191, note that $h$ is also the bandwidth parameter in equation (5).