Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper argues that the standard robust learning method ignores the data heterogeneity: the robustness radius is fixed as some artificial value r for all the examples. The authors then propose a new neighborhood optimal classifier to address this problem, and theoretically studies the convergence condition for a class of non-parametric methods, including histogram classifiers, nearest neighbors, and kernel classifiers. Synthetic experiments are provided to verify their theoretical results.
main_review: The proposed robustness framework is well motivated and clearly defined. At a high level, introducing heterogeneous robustness regions for different examples seems to be a promising direction for a better robustness definition. The theoretical results are also clearly presented and easy to follow. Nevertheless, my main concern of this paper is the practicability of the proposed framework: the proposed definition of neighborhood optimal classifier requires the knowledge of the support of the conditional distribution, which seems to be not practical for typical classification problem. More specifically, I have the following questions:

1.	How to apply Definition 3 to a more typical finite-sample classification problem? Are there ways to estimate the support of the ground-truth conditional distribution? 

2.	What does the theoretical results suggest for robust learning using non-parametric methods? How can these results generalize beyond non-parametric methods?

3.	The dataset of overlayed circles considered in Section 5 seems to be too artificial to me. Including the experimental results on other datasets, such as Gaussian mixtures or even some image benchmarks, will strength the paper.

limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies classification rules that are "astute", that is, those that are accurate and robust. Importantly, the authors note that common definitions of robust classifiers, which are given in terms of a fixed parameter (typically a size of a perturbation set) are not astute, as they do not fully exploit the fact that margins are not uniform across the data distribution. This paper first studies conditions under their so-called "neighborhood optimal classifier" maximizes robustness while retaining the Bayes classifier accuracy in the unperturbed distribution. Furthermore, the authors show that several popular non-parametric classifier provide consistent estimates for this classifier. Finally, this is demonstrated numerically in a simple experimental setting.
main_review: This paper is very interesting, and a pleasure to read. The limitation of current approaches to study adversarial robustness is clear from the presented concepts, and the proposed solutions are intuitive and elegant. I have a few minor comments:

Main comments:
- While the authors present results of consistency of certain non-parametric classifiers, their finite-sample performance is only evaluated numerically. Can the authors comment, at least briefly, on the potential of extending the analysis of convergence rates of non-parametric classifiers (such as those in [Doring et al, 2018]) to the setting presented here?

- In the paragraph on line 154, the authors motivate their definition of "neighborhood preserving robustness regions". To do so, they explain that they seek for regions U_x so that the astute accuracy of g_max equals the accuracy of the Bayes classifier. However, it's not totally clear what g_max is. Is it the one that maximizes the measure of U_x? A clarification would be appreciated.

- On the paragraph following Theorem 5, the authors comment that g_neighbor can be thought of a local maximum to a constrained optimization problem. However, it is not clear why this is not a global maximum - how could one obtain a classifier with larger robustness constrained to having equal accuracy as the Bayes?

Minor comments:
- Lines 57: space missing on "Instead [3]"
- The paragraphs on line 71 and 78 feel a bit repetitive, given that the preceding paragraphs just gave a summary of the presented contributions.
- Line 96: coma instead of semicolon?
- Line 137: principal -> principle
- Line 144: "the the"
- Line 171: the authors write "max-margin Bayes" classifier, but I believe they mean the neighborhood preserving Bayes classifier? This might be equivalent, but has not been defined as "max-margin" explicitely.
- The notation of algorithm (A_S) and Accuracy is slightly confusing.
- Line 222 "consistnecy" -> consistency
- Line 222: "needed accuracy" -> "needed for accuracy"
- On Corollary 12, the authors use the notation k_n^\infty_1. There's a parenthesis that seems out of place. But also, this notation has not been defined?
- On Corollary 13, the authors use h_n, but this seems undefined. Do they simply refer to the rule k_nn on the computed features?
- Line 293: "The answer this" -> the answer to this
- Figure 3 seems to have some strange gray edges on its bottom and left sides.
- Line 335: "performs will" -> performs well.

limitations_and_societal_impact: Adequately addressed.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper aims to give a new robust learning framework where the radius of adversarial attacks at different points can adaptively change. The main purpose is "to increase robustness, without sacrificing accuracy", as claimed by the author(s). In order to achieve this goal, author(s) have utilized a number of consistent non-parametric learning algorithms which are already proved to converge to an *optimal* classifier as the sample size increases (optimality could be defined in any certain sense, however, in this paper Bayes optimality has been mostly focused). Then, a new modification has been proposed in order to help such learning techniques to preserve as much adversarial robustness as they can, while still converge to the Bayes optimal classifier.

The main results are (most probably) solid, and maybe even interesting specially when we look at them from a pure theoretical standpoint. Moreover, I checked all the theoretical results and some of their proofs, and didn't find any notable technical mistakes or counter-intuitive conclusions. However, paper suffers from uninformative writing (specially in the introduction section) and lack of proper justification for some of the core ideas in real-world applications. The above problems, in addition to the fact that results are mostly asymptotic and centered around "consistency" of classifiers rather than their finite-sample performance, are the main weaknesses of the paper.

My vote at the current stage is weak-reject.
main_review: As far as I have understood, the main contribution of this paper is as follows: When the number of samples $n$ goes toward infinity and consequently the true data distribution becomes known to the learner,  then "the most robust classifier which coincides with the Bayes optimal classifier inside the support" would be trivial and easy to achieve. This paper gives a methodical approach so that some classes of non-paramteric classifiers (like $k$-nearest neighbor) can be computed for finite $n$, while are also guaranteed to converge to the trivial robust classifiers of $n=\infty$ which are described above (The guarantees are all asymptotic in this work). There are some other contributions in proving the consistency of certain non-parametric classes of learners, which I assume to be additional results.

---------------------------------------------------------------------------

Main comments:

Paper can greatly benefit from an improved writing, specially for the Introduction section. Some terms, such as "accuracy and astuteness" have been carelessly used in this section without being properly defined (they are both defined later in subsequent sections). This has made the Intro part to be somehow uninformative. Also, some motivations in the beginning of the paper have become lost and buried under tones of theorems and definitions inside the manuscript. For example, the abstract of the paper gives some motivations w.r.t. varying radius of attacks $r$ for different regions of the distribution. However, I do not see the results to be that much aligned with this particular motif. Maybe the abstract and parts of the introduction section should be rewritten.

Another issue is that paper lacks real-world justification for its main idea: Having robustness to out-of-distribution samples (for example, off-manifold data points which are usually the result of adversarial attacks) is interesting, but the discussions around this issue in the paper is slim to none. In other words, why should any reader be concerned with samples like $x$ which are not in the support of data distribution, i.e. $x\notin\mathrm{supp}\left(\mu\right)$? One might assume the answer to be crystal clear for some well-informed audience, but that's not the case for general readers.

Another fundamental problem is that results in this work are asymptotic. No non-asymptotic bounds have been proposed to guarantee any type of performance measure when the number of samples $n$ is finite. Any type of guarantees on the adversarial robustness when $n$ is infinite and the true underlying data distribution (or at least the true data manifold) is revealed are not that much interesting. It would be nice if authors can give some certificate for robustness when $n$ is finite. Some of the cited works in this paper (Sinha et al., for example) have already done that for distributionally robust scenarios.

--------------------------------------------------

Minor comments:
-(Line 144): "the" has been repeated.
limitations_and_societal_impact: No problem here.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors argue that robustness regions should be larger in some regions of data, and smaller in others, and propose a new limit classifier, called the neighborhood optimal classifier, that extends the Bayes optimal classifier  outside its support by using the label of the closest in-support point. They argue that this classifier maximizes the size of its robustness regions subject to the constraint of having accuracy equal to the Bayes optimal, then present sufficient conditions under which general non-parametric methods that can be represented as weight functions converge towards this limit object, and show that both nearest neighbors and kernel classifiers (under certain assumptions) suffice.  
main_review: The authors propose an alternative formulation of robust classification that ensures that in the large sample limit, there is no robustness-accuracy tradeoff, and that regions of space with higher separation are classified more robustly. To this end, the authors introduce a new large-sample limit, the neighborhood preserving Bayes optimal (NPBO) classifier. For an input x, it outputs the prediction of the Bayes Optimal on the nearest neighbor (including itself) in the support of the data distribution D. 
 

They show that k_n-nearest neighbors converge to the NPBO provided k_n = ω(log n), and kernel classifiers converge to the NPBO provided certain conditions (the kernel function K has faster than polynomial decay, and the bandwidth parameter h_n decreases sufficiently slowly), but certain types of histogram classifiers do not converge to the NPBO, even if they do converge to the Bayes optimal. They also provide experiments to validate their claims.

I feel this work is novel in motivation and solid in theory.  

I have the following comments for improving the writing and organization: 
In Section 1, "astuteness" is used without any citation in the first paragraph.  
In Section 2, there are many conceptions that are existed in previous papers, but the authors did not mention or give references, 
for instance, Definition 1 "astute and astuteness", weight functions, histogram classfiers, etc.
Line 259: Conditions 2. and 3. are ..., conditions 2. and 3. of ... .  I think the period "." is not needed after 2 and 3.
Line 144: We call this the the neighborhood preserving ... 




limitations_and_societal_impact: The authors did not address the limitations and potential negative societal impact of their work.  A paragraph of discussion is needed.
review_title: null

Meta-review: The paper presents a novel and interesting idea to combine robustness and consistency.
It is well written and provides explicit examples how the general framework can be 
applied. On the negative side, only consistency is considered and more refined convergence
results such as learning rates or finite sample bounds are missing.
Decision: Accept (Poster)