Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: Summary:
This paper considers the estimation of the concentration of measures, which possibly causes of the vulnerability of machine learning models to adversarial attacks. Towards such a goal, the authors first extend the Gaussian Isoperimetric Inequality to non-spherical Gaussian measures and arbitrary l_p norm. An algorithm that uses half-spaces as feasible set in the concentration of measure problem is then proposed. Empirical studies are conducted to show the efficiency as well as the efficacy of the proposed method when compared to [Mahloujifar et al. (2019b)].

Comment:
The paper is overall well written and the presentation is clear. While I am not an expert in this domain, I can easily follow the paper and understand the problem. While I cannot judge the novelty of Theorem 3.3, I very much appreciate Remark 3.4 which describes the limitations of Theorem 3.3 and clarifies the implication of such a result in several important special cases. In terms of the algorithm design, the choice of half spaces as feasible set in the concentration of measure problem seems natural given Lemma 3.2/Theorem 3.3 and is amenable to the generalization analysis. 
review_title: Official Blind Review

final_score: rating: 7: Good paper, accept
review_content: Summary: The authors consider the problem of estimating intrinsic robustness using data samples. At a high level, intrinsic robustness is a measure that indicates the probability that a noisy version of a covariate would not be mislabeled. Mahloujifar et al. (2019a) have shown that estimating intrinsic robustness is closely related to the problem of estimating the concentration of measure. This problem focuses on finding a region such that it has the least likely epsilon neighborhood. In this work, the authors provide an efficient algorithm for measuring concentration empirically, which yields a more accurate estimation of the intrinsic robustness compared to the previous results.  
One of the key technical components was generalizing the Gaussian Isoperimetric Inequality to non-spherical gaussian distributions (with distance metric being ell_p for p >2). This result leads to an optimal concentration result for special gaussian spaces. 
Another utilized technique was using half spaces to estimate the intrinsic robustness. Basically, for estimating the intrinsic robustness, instead of solving an optimization problem over all possible regions, they only consider half-space regions. This approach yields a new formulation of the problem in the form of a linear program which can be solved efficiently.
In the end, the authors provide an empirical evaluation of their results.

Overall evaluation: The authors consider an important problem (understanding the robustness of a set of classifiers) from an interesting angle. The paper has substantial theoretical contributions that are empirically evaluated as well. The paper seems well-written. 

Question: What is the main advantage of half-spaces (compared to hyperrectangles or balls), which results in a more efficient algorithm? Where does the improvement come from the generalization part (bounded VC-dimension of the extensions)? Or is it because using half-spaces, the problem can be nicely stated as an LP? 
review_title: Review1

final_score: rating: 6: Marginally above acceptance threshold
review_content: Review
The authors generalized the Gaussian Isoperimetric Inequality to non-spherical Gaussian measures with $\ell_p$ metric structures $p\geq 2$. Building on the generalized inequality, they propose a sample-based algorithm to estimate the concentration of measure using half-spaces. The main contribution is Theorem 3.3 followed by the empirical sample based algorithm for half-spaces that requires $\Omega(n\log(n) /\delta^2)$ samples.


#### Reason for score
Overall, I vote for weak accept. The paper is very well written and it was a pleasure to go through it. Since I am not an expert in this research area, I have a low confidence in my decision. I would like to share a few minor concerns below to the authors that could improve further their submission.

#### Strong points:
- Paper is very well written and it was easy to go through the main contributions.
- A lot of effort is put in having a consistent,clear notation and formalism.

#### Minor Concerns
- I would expect that Theorem 3.3 to be already known in the literature, since Lemma 3.2 and Gaussian stability could probably derive such a result. At least, I believe that there might be tools that could make the proof of Theorem 3.3 shorter ( I had a quick look at it).
- Theorem 4.2: Why is this theorem stronger than the Mahloujifar et al. 2019? Both require $O(n\log(n) / \delta)$ samples but in footnote 3 you mention a parameter T. Is T a constant?
- I would suggest to move your algorithm from the appendix to the main text.
- Please make the argument stronger in the text on why "concentration of measure is not the main reason for the adversarial vulnerability of classifiers". Is this a definite conclusion?
 
#### Minor comments
- Abstract: Please rephrase the last sentence. "is not the main reason" could be rephrased.
- Sentence before "Contribution" : fix "to date to find"
- Why 8/255 in contribution? It looks like a magic number here.
- Notation: introduce square root of a matrix here.
- Notation: $\Delta$ mention that is a metric.
- Lemma 2.3 looks likea direct consequence of Defn. 2.1. Do you really need it?
- Defn. 3.1: do you need to define halfspaces? You can simply put it in text.
- All sets related should be measurable, i.e., Lemma 3.2, to avoid pathological cases.
- Theorem 4.2: is it true for $p\geq 1$ or $p\geq 2$?
- Footnote 3: Is T a constant or not? Please be specific. It is important since it compares with Theorem 4.2.
review_title: Generalized Gaussian Concentration for Adversarial Robustness

final_score: rating: 6: Marginally above acceptance threshold
review_content: $\{\\bf \{Problem\~ setting\~ and\~ summary\~ of\~ results\}\}$:

This paper gives a theoretical analysis on the fundamental limits of adversarial robustness under general $\\ell_{p}$-norm attacks. It basically builds upon a series of recent  works, mainly by Mahloujifar et al. (2019a and 2019b), which establish a fundamental relation between the  concentration function of input distribution, denoted by  $h^{\\left(\\ell_p\\right)}_{\\mu}\\left(\\epsilon,\\alpha\\right)$, and its intrinsic robustness, i.e., maximum possible adversarial robustness for any model class in a robust learning problem. The paper's main contribution is to propose a new way for approximating the empirical value of $h^\{\\left(\\ell_p\\right)\}_\{\\mu\}\\left(\\epsilon,\\alpha\\right)$ for a given input dataset of $m$ samples. Approximation is based on replacing the true input measure by its empirical version, and also limiting the error regions in Eq. (2.1) by a more manageable class (in this work: Half-spaces). In this regard, authors have investigated the two following issues: 1) consistency of the approximation and corresponding generalization bounds, and 2) tightness of the final bounds on intrinsic robustness.

$\{\\bf \{On\~the\~generalization\~aspect\}\}$: Authors have shown that estimating the concentration function $h^{\\left(\\ell_p\\right)}_{\\mu}\\left(\\epsilon,\\alpha\\right)$, for any $p\\in\\left(1,\\infty\\right\]$, through minimizing over the set of all half-spaces converges to its statistical value (i.e., when $m\\rightarrow\\infty$). The corresponding generalization bounds are given in Theorem 4.2, where a sample complexity similar to that of Mahloujifar et al., 2019, has been derived (authors claim that sample complexity has been improved w.r.t. prior works). Also, it should be noted that based on authors' claims in p.5, Mahloujifar et al. have only considered $\\ell_2$ and $\\ell_{\\infty}$-bounded attacks in their work while in this work $p$ is not restricted. Also, paper claims that the new proposed method converges to the optimal solution faster than previous works, however, no theoretical guarantees are given for this claim.

$\{\\bf \{On\~the\~tightness\~aspect\}\}$: Paper shows that when input data distribution is set to $\\mathcal{N}\\left(\\boldsymbol\{\\theta\},\\boldsymbol\{\\Sigma\}\\right)$, the concentration function becomes optimal and bounds are tight, if

a) $\\boldsymbol\{\\Sigma\}=\\boldsymbol\{I\}_n$ and $p>2$, or

b) $\\boldsymbol\{\\Sigma\}\\neq\\boldsymbol\{I\}_n$ and $p=2$.

For other cases, a novel and interesting bound is given (by extending the Gaussian Isoperimetric Inequality to $\\ell_p$ norms). However, achievability of bounds in these cases are not guaranteed in this paper.

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

$\{\\bf \{Comments\}\}$:

Paper is very well-motivated and fairly well-written. Mathematical notations are carefully crafted and results seem to be solid and understandable (I have not checked all of the proofs in Appendix). However, the contribution of the paper on the generalization aspect of the problem looks incremental and is similar to the prior works by Mahloujifar et al. (2019), however, in a relatively different setting. The main additions and improvements in this part are mostly heuristic and are backed solely through experiments.
The only exception is the sample complexity bound given in Theorem 4.2, where authors claim a substantial improvement has happened. However, this part need more explanation: How large parameter $T$ needs to be in (Mahloujifar et al., 2019) to guarantee the same error bound as this work? If $T$ is $O\\left(1\\right)$ w.r.t. dimension $n$, then I cannot see any considerable improvement (at least order-wise).

On the tightness issue, results are more novel and promising (in particular, Lemma 3.2). Again, the lack of theoretical guarantee for the achievability of Eq. (3.1) for the majority of cases has hampered the significance of the results in this part.

Overall, I believe this paper could potentially make a breakthrough if authors can provide further solid theoretical guarantees for any of the above issues. Still, I think the paper is publishable even in its current form.
review_title: A good theory paper. Some parts of its contribution are more or less incremental, while some other parts look novel and promising.

Meta-review: High-quality theoretical paper that studies the connection between concentration of the data distribution and adversarial robustness. It contributes a method for more accurate estimation of concentration, which allows drawing stronger conclusions about adversarial robustness compared to previous work. The paper is highly technical, but written clearly and precisely. All reviewers give positive scores, with only minor negative comments.

One minor concern I have is that the potential audience of the paper might be small, given its highly technical nature and very specialized line of research it follows. Still, I believe it's a solid contribution, so I'm happy to recommend acceptance.
Decision: Accept (Poster)