Summary
This paper studies the problem of classification under found different kinds of adversarial loss functions:
1) ST which I think is by far the most popular adversarial loss. This is same as the expected sup loss of [Madry et al. 2018](https://arxiv.org/abs/1706.06083).
2) TL which is equivalent to the the "exact in the ball" risk of [Gordeau et al](https://www.jmlr.org/papers/volume22/20-285/20-285.pdf) or the "error region risk" of [Diochnos et al](https://proceedings.neurips.cc/paper_files/paper/2018/file/3483e5ec0489e5c394b028ec4e81f3e1-Paper.pdf)
3) IA which is the same as ST but where the adversary only perturbs points belonging to one of the two labels
4) CA loss which is the same as TL with the additional constraint that the true label does not change at the perturbed point.
For each type of loss, the paper establishes the "optimal robustly reliable region". Here, the classification is deemed reliable if the the classification is correct on the _perturbed ppoint_. The papers shows that these regions can be computed efficiently for simple hypothesis classes like linear classifiers. The paper also proves lower bounds on "safely-reliable region" for linear separators under log-concave distributions, where a point is classified safely reliably at $\eta_1, \eta_2$ levels if it can be reliably classified at $\eta_2$ level, even when perturbed in a ball of radius $\eta_1$.
Finally, the paper also lower bounds the amount by which the reliability region can change under a distribution shift from P to Q in terms of a $P\to Q$ disagreement coefficient.
Strengths
- Generality: The results of the paper hold for 4 kinds of adversarial loss functions, each with different use-cases.
- Nice result on reliable learning under distribution shift: Theorem 5.3 proves a connection between reliable learning under distribution shift, and a previously studied notion called the disagreement coefficient. This connection appears interesting and non-trivial.
Weaknesses
- Writing: The paper is very difficult to read. There are many new definitions but very few illustrations / examples. The paper seems to be written in a hurry. Some of the results that are listed under main contributions in section 1.1 only appear in the appendix. Section 6 is super short - it only presents one new definition, followed by an example satisfying the definition the details of which are relegated to the appendix.
- Limited contributions: The paper makes limited contributions on the "safely-reliable" notion of classification (Definition 6), which I think is much more important than the notion of "reliable" classification (Definition 3, 4). Theorem 3.3 on probability mass on reliable region only holds for the special case of linear separators with isotropic log-concave distributions. Section 6 on safely-reliable correctness under distribution shift establishes the safely-reliable correctness again only for the special case of linear separators with isotropic log-concave distributions. Further, the shifted distribution is also assumed to only shift in mean, while the covariance matrix remains as Identity matrix. Section 4 also focuses on simple settings like linear separators.
- Limited applicability of the notion of "reliability": I want to stress again that the "safely-reliable" notion is more important than the "reliable" notion. The importance of safely-reliable region over the reliable-region is stated by the authors themselves in lines 216-218: "...we note that the probability mass of the robustly-reliable region may not be a meaningful way to quantify the overall reliability of a learner because a perturbation may lie outside of the support of the natural data distribution and have zero probability mass." Basically, a classifier can be robustly reliable at z with level $\eta$ even if predicts a different label at a slightly perturbed point x such that d(x, z) < $\eta$. Hence, reliability does not ensure robustness against adversarial attacks. Literature on certified robustness (for example, randomized smoothing, interval bound propagation) all focus on something like the "safely-reliable" notion rather than reliable. In lines 91-94, the paper says "Prior works have examined pointwise consistency guarantees [SKL17, CRK19, WLF22], i.e. the classifier’s prediction is guaranteed not to have changed under an attack. In contrast, we study a much more desirable property of reliability—guaranteeing that the prediction of the algorithm is correct." I would like to see the paper make a stronger case advocating for the study of reliability than the one given here.
Questions
- Definition 7 is unclear: What is z in line 296? I think it should be any x' in U(x).
- I would recommend cutting down on the size of section 1.1: summary of contributions.
- It would be good to have more examples to accompany the definitions, for instance contrasting the reliable vs safely-reliable notions.
I would also like the authors to comment on my view of the paper in the "weaknesses" section.
Rating
4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good 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.