Characterizing the Optimal $0-1$ Loss for Multi-class Classification with a Test-time Attacker
Authors: Sihui Dai
Wenxin Ding
Arjun Nitin Bhagoji
Daniel Cullina
Haitao Zheng
Ben Y. Zhao
Prateek Mittal
Venue: NeurIPS 2023 spotlight (2023)
Keywords: adversarial robustness
graph theory
fundamental bounds
TL;DR: Find and evaluate several methods to bound the loss of optimal multi-class classifiers against test-time attacks

Abstract: Finding classifiers robust to adversarial examples is critical for their safe
deployment. Determining the robustness of the best possible classifier under a
given threat model for a fixed data distribution and comparing it to that
achieved by state-of-the-art training methods is thus an important diagnostic
tool. In this paper, we find achievable information-theoretic lower bounds on
robust loss in the presence of a test-time attacker for *multi-class
classifiers on any discrete dataset*. We provide a general framework for finding
the optimal $0-1$ loss that revolves around the construction of a conflict
hypergraph from the data and adversarial constraints. The prohibitive cost of
this formulation in practice leads us to formulate other variants of the attacker-classifier
game that more efficiently determine the range of the optimal loss. Our
valuation shows, for the first time, an analysis of the gap to optimal
robustness for classifiers in the multi-class setting on benchmark datasets.

Characterizing the Optimal 0 1 Loss for Multi-class Classification with a Test-time Attacker
Sihui Dai
Wenxin Ding Arjun Nitin Bhagoji? Daniel Cullina
Ben Y. Zhao² Haitao Zheng*
Prateck M
Princeton University 2 University of Chicago PPennsylvania State University
{sihuid, pwwttall@prrineeeeeeeeeeeeeeeeee {wenxind, abhagoj in (atoojjeeucchhc cachiiacooooo..eeeeoeoeooooooaoe edu
edu
(ravenben, htzheng uchicago. edu cullina@psu.ed edu
Abstract
Finding classifiers robust to adversarial examples is critical for their safe deploy- ment. Determining the robustness of the best possible classifier under given threat model for fixed data distribution and comparing it to that achieved by state-of- the-art training methods is thus an important diagnostic tool. In this paper, find achievable cremmation-thoorete lower bounds on robust loss in the presence of a test-time attacker for multi-class classifiers on any discrete dataset. We provide a general framework for finding the optimal 0 loss that revolves around the construction of conflict hypergraph from the data and adversarial constraints. The prohibitive cost of this formulation in practice leads us to formulate other variants of the attacker-classifie game that more efficiently determine the range of the optimal loss. Our valuation shows, for the first time, an analysis of the gap to optimal robustness for classifiers in the multi-class setting benchmark datasets.
Introduction
Developing theoretical understanding of the vulnerability of classifiers adversarial examples (27 12 4 generated by a test-time attacker is critical to their safe deployment. Past work has largely taken of two approaches. The first has focused generalization bounds on learning in the presence of adversarial examples, by trying to determine the sample complexity of robust learning The second has been characterize the lowest possible loss achievable within specific hypothesis class (22) 5 () for binary classification for a specified data distribution and attacker. The hypothesis class of choice often the set of all possible classification functions. The optimal loss thus determined is a lower bound on robustness for classifiers used in practice, allowing practitioners measure progress for defenses and step away from the attack-defense arms race (19 3).
(10 25 21).
In this paper, we take on the second approach and propose methods to find the lowest possible loss attainable by any measurable classifier in the presence of test-time attacker in the multi-class setting. The loss thus obtained is referred to as the optimal loss and the corresponding classifier, the optimal classifier. We extend previous work (5) (6) which was restricted to the binary setting, allowing us to compare the robustness of multi-class classifiers used in practice to the optimal loss. Our first contribution is thus extending the conflict-grapp framework for computing lower bounds on robustness to the multi-class seiting. In this framework, given a dataset and attacker, we construct conflict hypergraph which contains vertices representing training examples in the dataset, and hyperedges representing overlaps between adversarial neighborhoods around each training example. Using this hypergraph. we construct linear program whose optimal value is lower bound on the 0 - 1 loss for all classifiers and whose solution is the optimal classifier. The lower bound on robustness is thus achievable.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

In practice, however, we find that the full multi-class formulation of the lower bound, although exact, can lead prohibitively large optimization problems. Thus. we vary the information available to either the attacker or classifier to find alternative lower bounds that are quicker to compute. Our second contribution the development and analysis of more efficient methods to determine the range of loss obtained by the optimal classifier. (see [T. We also interpret these methods as classifier-attacker games. In particular, we find lower bounds on the optimal loss by aggregating the set of all binary classifier-only lower bounds as well as by using truncated hypergraphs (hypergraphs with a restriction on the maximum hyperedge degree). We also upper bound the optimal loss with generalization of the Caro-We bound ① a graph's 's independent set size. The gap between the lower and upper bounds on the optimal loss allows us to determine the range within which the optimal loss lies.
To analyze the performance of classifiers obtained from adversarial training 19 31. we compare the loss obtained through adversarial training to that of the optimal classifier. We find a loss differential that is greatly exacerbated compared to the binary case (5) 22). In addition, we also determine the cases where, in practice, the bounds obtained from game variants are close to the optimal. We find that while the aggregation of binary classifier-only bounds leads to a very loose lower bound, the use of truncated hypergraphs can significantly speed up computation while achieving a loss value close to optimal. This is validated using the Caro-Wa upper bound, with the lower and upper bounds on the optimal loss closely matching for adversarial budgets used in practice. Thus, our final contribution is an extensive empirical analysis of the behavior of the optimal loss for a given attacker, along with its lower and upper bounds. This enables practitioners to utilize our methods even when the optimal loss is computationally challenging to determine.
The rest of the paper is organized as follows: 2 provides the characterization of the optimal loss; 3 proposes several upper and lower bounds on the optimal loss; computes and compares the optimal loss to these bounds, as well as the performance of robustly trained classifiers and cooncluee with a discussion of limitations and future work.
2 Characterizing Optimal 0-1 Loss
In this section, we characterize the optimal 0- 1 loss for any discrete distribution (e.g. training set) in the presence of a test-time attacker. This loss can be computed as the solution of a linear program (LP), which is defined based hypergraph constructed from the classification problem and attacker constraint specification. The solution to the LP can be used to construct a classifier achieving the optimal loss, and lower bounds the loss attainable by any particular learned classifier.
2.1 Problem Formulation
We consider a classification problem where inputs sampled from input space X, and labels belong to K classes: y E y = [K] = {1.... K}. Let P be the joint probability over X' x y. Let Haan denote the space of all soft classifiers; i.e. specifically, for all h Hoon have that X' > [o, 1] K and ΣK h(x); = for all x E X. Here, h(z)); represents the probability that the input x belongs to the 7th class. We use the natural extension of 1 loss to soft classifiers as our loss function: E(h, v)) = 11 h(z),- This reduces to 0 - 1 loss when h(r) E 10.
Notation.
The adversarial classification game. We interested in the setting where there exists test-time attacker that can modify any data point x to generate an adversarial example ă from the neighborhood ((x) of x. An instance of the game is specified by discrete probability distribution P hypothesii class H C Hon and neighborhood function N. We require that for all x E X. N(x) always contains x. The goal of the classifier player is minimize expected classification loss and the goal of the
'A soft classifier can be interpreted as randomized hard-decision classifier f with Pr[f(=) y = h()),. in which case ((h, (x. v)) Pr(f(x) A y). classification error probability of this randomized classifier. Prroperly extending this game to more general data distributions tricky due to issues with the measurability of the supremum of the loss. See Pydi and Jog for discussion of the multiple approaches taken in the literature and when various versions of the game are equivalent (23). These technicalities do not arise for discrete distributions, which are sufficient for our purposes.

---

attacker is to maximize it. The optimal loss is
H, inf ((aa)>
sup E(h, (i. (i, = sup E (a.s)~ BEN(a)
inf h(2)g] (1) (xN(x)
NER
hCH
Alternative hypothesis classes. In general, for H' C H. we have L' S ( H').
Two particular cases of this are relevant. First, the class of hard-decision classifiers is a subset of the class of soft classifiers (Hwn). Second, for any fixed model parameterization (ie. fixed NN architecture), the class of functions represented by that parameterization is another subset. Thus, optimal loss over Hao provides a lower bound on loss for these settings.
2.2 Optimal loss for distributions with finite support
Since we would like to compute the optimal loss for distributions P with finite support, we can rewrite the expectation in Equation [ as an inner product. Let be the support of P, i.e. the set of points (ar, y) E X' x y that have positive probability in P. Let p E 00, 1] be the probability mass vector for P: Pv P(fu3). For soft classifier h, let qN (h) E V be the vector of robustly correct classification probabilities for vertices v (2,8) E V, i.e. qN(h), == infzeN(x) h(())y Rewriting T with our notation, have 1 - (P, Hoont .N) Suup p" aN (h). This is the maximization of linear function over all possible vectors qN (h). In fact, the convex hull of all correct classification probability vectors is polytope and this optimization problem is linear program, as described next.
Definition For a soft classifier h, the correct- classfcccasssiicatiin probability achieved on an example (z, y) in the presence of an adversary with constraint N is qN (h)) =infaeN(a) h(ō),
The space of uchievable correct classification probabilities is PV.N. S [0, 10. defined as
Pv.N.
U (N, (h)
NEV
In other words we say that y' E [0, 1]V is achievable when there exists E H such that o' S (h)... The inequality appears because we will always take nonnegative linear combinations of correct classification probabilities.
Characterizing Pv,N. allows the minimum adversarial loss achievable to be expressed as an opti- mization problem with a linear objective 3
L (P,, Hoof) heHua
sup Eu-Plan
sup p (h)) sup pTg qEPo.M.R
heWoa
(6) characterized PV.N. in the two-class case and demonstrated that this space can be captured by linear incqualities. We now demonstrate that this also holds for the multi-class setting.
2.3 Linear Program to obtain Optimal Loss
In order to characterize Py,NHssoee we represent the structure of the classification problem with conflict hypergraph Gy.N = (V,E), which records intersections between neighborhoods of points in X. The set of vertices V of Gy.N is the support of P. denotes the set of hyperedges of the graph. For set C V, S & (i.e. S is hyperedge in Gv.N) )) if all vertices in S belong different classes and the neighborhoods of all vertices S overlap: N(wyEs N(x) # 0. Thus, the size of
each hyperedge is at most K, & is downward-closed (meaning if E & and e' C then e' C E), and every u E V is degree hyperedge.
Using the conflict hypergraph Gv.N, we can now describe Pv,N Hoott
Theorem 1 (Feasible output probabilities (Adapted from ()). The set of correct classification probability vectors for support points V, adversarial constraint N, and hypothesis class Hoofs is
Pv.N.Huefe = (g R² 2 0, Bq 1}
where B E B is the hyperedge incidence matrix of the conflict hypergraph Gy.N-
Forr any loss function that is a decreasing function of h(2),, the optimal loss can be specified as an optimization Pv.N. n. In fact (6) focused on cross-entropy loss, which has this property.
3

---

Summary of Method
Location
Optimal 0-1 loss
LP on conflict hypergraph
LP on truncated conflict hypergraph
Lower bounds for optimal 0-1 loss
Combining binary classification bounds Generalization of Caro- Wei bound
3.2
Upper bound for optimal 0-1 loss
3.5
Table 1: Summary of methods for computing the optimal 0 1 loss and efficient bounds on this value.
See Supplementary A for proof. This characterization of P..N.H..f1 allows us to express optimal loss as linear program for any dataset and attacker using Eq. Corollary (Optimal loss as an LP). For any distribution P with finite support,
- L Hoat) = maxp" p s.t 0, Bq 1. 1.
(4)
Duality and adversarial strategies.
The dual linear program is
min 1
220 B²2 p.
Feasible points in the dual linear program fractional coverings of the vertices by the hyperedges (24). (See Section 3.4 and Supplementary {B for more discussion of fractional packings and coverings.) An adversarial strategy can be constructed from feasible point hyperedge e, chose an example Z(e) such that ((e) E (xx) for all (I, y) E e. From the definition of the conflict hypergraph, a choice is always available. A randomized adversarial strategy consists of conditional distributions for the adversarial example ž given the natural example æ. When the adversary samples the natural example (z, y). the adversary can select i(e) with probability at B Be,uãe Note that Be is the amount of coverage of v coming from e. This nonzero only for that contain (æ, y). A conditional distribution satisfying these inequalities exists because Ee Be (B">)) 2), 2 Pu-
follows. For each
least
Thus for vertex such that (BT 2) Pu. there is only one choice for this distribution. For vertex v that is over-covered, i.e. z)² > Pa. the adversary has some flexibility. If is over-covered in some minimal cost covering, by complementary slackness qu 0 in every optimal g, so the optimal classifiers do not attempt to classify v correctly.
Three-class minimal examples. Corollary demonstrates that the optimal loss for the multi- class problem is influenced by hyperedges be- tween vertices which reflect higher order inter- actions between examples. Figure I shows an important distinction between two types of three- way interactions of examples.
V
"
u
w
w
We have 1
(P, Hooft, N)
=
max(pa, Pe. Pwr )) L' Haoft, N) max(p'u ph, p..). The
while
Figure 1: Two possible conffict structures involv- ing three examples, each from a different class. In the right case, all subsets of V {u', v' wo) are hyperedges in the conflict hypergraph Gv.N. In the left case, {u, u, w) is not hyperedge in GV.N. but all other subsets of V are.
presence or absence of the size-three hyperedge affects the optimal loss and only the example probabilities are close to balanced, i.e. all at most }.
It is instructive to consider the optimal classifiers and adversarial strategies the two cases. For V. when 2 S Pa. the classifier h with gx (h)
(1, 0, 0) is optimal. One such classifier is the constant classifier h(x:) = (1, 0, 0). The optimal cover satisfies [[,,r} 2(u,w) Pus 2uu,o} 2 Po. 2(u,w} Pws 2f2,0} = 0. Thus when the adversary
"We note that concurrent work by Trillos et al. (29) provides a general-purpose framework based on optimal transport to find lower bounds on robustness in the per-sample as well as distributional sense. They also independently construct the three-class minimal example from Figure]]

---

samples V or w, it always produces an adversarial example that could be confused for When max(pu. Pv. Pwo) I 3. any classifier h with qN (h) (5 2 is optimal. To achieve these correct
classification probabilities, we need h()) = 2 2 0) for I E (N() n (u),, h(ā) = ( 0, 2)
for ã E Nuu) n (w), etc.. The cover ={ = Pu + Po 2. [(u,w) = Pu + Pw 2. and
[(u,e) = Pr + Pwr all three edges.
1 is optimal and has cost 1
2. The adversary produces examples associated with
For V. things are simpler. The cover f(a,0.)) max(pu,Pu) Pu, Puo) is always optimal. When Ps 2 max(pu: (e))) the classifier that returns (1, 0, everywhere optimal.
Bounding the Optimal 0-1 Loss
While Corollary I characterizes the optimal loss, it may be computationally expensive to construct conflict hypergraphs practice for given dataset and to solve the linear program. Thus, we discuss several methods of bounding the optimal loss from the LP in Corollary [ faster practice (4.2).
which are computationally
3.1 Lower bounds multiclass optimal loss via truncated hypergraphs
The edge set of the hypergraph 9 can be very large: there are Ihe (1 + VVl) vertex sets that are potential hyperedges. Even when the size of the edge set is reasonable, it is not clear that higher order hyperedges hypergraphs with bounded size hyperedges: GSmh = (V, ESm) where &-m {e E E |el S m). We refer these hypergraphs truncated hypergraphs. In the corresponding relaxation of 4 B is replaced by BSm, the incidence matrix for g5m, Since Esm C E, this relaxation provides a lower bound on L (P( N, Hsoft).
be computed from V efficiently. To work around these issues,
consider
Classification with side-information. This relaxation has an interpretation as the optimal loss in a variation of the classification game with side information.
Definition In the example-depen dependent side information game with list length m, the adversary samples (z, y) ~ P, then selects ă and C S y such that C and |C| = m. We call C the side
information. The classifier receives both it and C, so the classifier is function h X (2)) - [0. 1]K
where (2) is the set of m-element subsets y. y. Let
(mm, P,H,N) = inf (m inf min (1- - 1(2, 07) VEC
bEH
(EE((a) (EEC)
be the minimum loss in this game.
To illustrate this, consider the distribution P' from Figure with m = 2. The adversary can select some ā E (u') n (u') n N(w'), but the classifier will use the side-information to eliminate one of the three classes. The classifier is in the same situation it would be the distribution were P and the size-the three hyperedge was absent.
Definition 3. For classifiers using class list side-information, the correct-clussfication probability is defined follows: Qm.N (x.a) = in) mince ((K) (yec l(ū, C)y- The set of achievable correct- serrec-classificattio probubilities is Pm.V.N.H = UnER Il (
When m K, the minimization over C is trivial and q (h) reduces to qN (h).
Theorem 2 (Feasible output probabilities in the side-information game). The set of correct classifica- tion probability vectors for side-informin iedeiinformation of size m, support points V, adversarial constraint N, and hypothesis class Hooft is
Pm.,NNHoott E :
8 a S 1}
(5)
where B5m E EXV is the hyperedge incidence matrix of the conflict hypergraph G.Sm
The proof can be found in Supplementary
A
Using the feasible correct classification probabilities in Theorem we can now write the I.P for obtaining the optimal loss for classification with ide-information
5

---

Corollary (Optimal loss for classification with side information / ttuncation lower bound),
1 1 (P,, = max p'x s.t 0, BS S 1.
3.2 Lower bounds on multiclass optimal loss via lower bounds for binary classification
For large training datasets and large perturbation sizes, it may still be computationally expensive to compute lower bounds via LP even when using truncated hypergraphs due to the large number of edge constraints. Prior works () proposed methods of computing lower bounds for 0 loss for binary classification problems and demonstrate that their algorithm is more efficient than generic LP solvers. We now ask the question: Can we use lower bounds for binary classification problems to efficiently compute lower bound for multi-clas classification?
Consider the setting where we obtain the optimal 0 0-1 1 loss for all one-versus-one binary classification tasks. Specifically, for each C' E ((K), the binary classification task for that class pair uses example distribution PIY E and the corresponding optimal loss (=P( E C), N, Hsoft). What can we say about L (P, N, Hsoft) given these (x) numbers?
This question turns about to be related to another variation of classification with side information. Definition 4. In the class-only side-information game, the adversary samples y ~ Py. then selects C ((K). then samples Ps and selects & E (x)).. Let [, P, H. N) be the minimum loss in this game.
In the example-dependen side-information game from Section 3.1 depend on both x and y. In the class-only variation it can only depend on For the class only game, we will focus on the m 2 case.
the adversary's 's choice of C can
To make the connection to the binary games, we need to add one more restriction on the adversary's choice of side information: for all y, y Pr[C = {y, v J = y] Pr[C (y, y',''ll ensures that the classifier's posterior for Y given C' is Pr[Y = -icc Pr|y = / Pr(y E E..
y'). This
Theorem 3. The optimal loss in the class-only iideinffrrmation game is L. P,N, N, H) = max, Eis Pr(V = iJas,5813 where dij = I,- (Pl( E (i.j)), N) and 8 E K] is symmetric doubly stochastic matrix: 0,0, s s", s1 1.
The proof in is Supplementary A The variable represents the attacker's strategy for selecting the class side information. When the classes are equally likely, we have maximum weight coupling problem: because the weights a are symmetric, the constraint that s be symmetric becomes irrelevant.
3.3 Relationships between games and bounds
The side information games provide a collection of lower bounds on (' N, Hoon). When m = 1, the side infomation game becomes trivial: C' = {y} and the side information contains the answer to the classification problem. Thus L (1, Hooft) 1o Ho )= = 0. When m = C y and both the cxample-dependen and class-only side information games are equivalent the original game, so (P, NN, H) = L (K, P, N, H) = L (K, P,N, , H). For each variation of the side- cede-information game, the game becomes more favorable for the adversary L 1'(m+ + P, N, H) and Le (m, N, H) & L (m fm++1 1, P, N, H). For each m, it is more favorable for the adversary to before selecting C, i.e. L (m, P, N, H) < L Lmmmm P, N, H).
increases: L Lmm,, P, n, H) <
3.4 Optimal Loss for Hard Classifiers
Since Hhard C Hsott T." (m,, P, N, Hoot) & (P, N, Hhad)) The optimal loss over hard classifiers is interesting both as a bound on the optimal loss over soft classifiers and as an independent quantity. Upper bounds on L (PP,, N, Hhard) can be combined with lower bounds from $3.1 and $3.2 using small values of to pin down L (m, P, N, Hsott) and establish that larger choices of m would not provide much additional information.
hard classifier h X - (0, 1][1] has 0, 1-valued correct classification probabilities. When we apply the classifier construction procedure from the proof of Theorem using an integer-valued

---

q vector, we obtain a hard classifier. Thus the possible correct classification probabilities for hard classifiers are PV,N. n {0, 1)(k], These are exactly the indicator vectors for the independent sets in g the vertices included in the independent set are classified correctly and the remainder are not. Formally, we can express hard classifier loss as:
1 (P. N, Haard)
max SCV:S independent in g
P(S).
(6)
Finding the maximum weight independent set is an NP hard problem, which makes it computationally inefficient compute optimal hard classifier loss.
Two-class versus Multi-class hard classification There are a number of related but distinct polytopes associated with the vertices of hypergraph (24). The distinctions between these concepts explain some key differences between two-class and multi-class adversarial classification. See Supplementary B for full definitions of these polytopes.
When K = 2, the conflict hypergraph is bipartite graph. For bipartite graphs, the fractional vertex packing polytope, which has constraint Exee qi < for each edge e, coincides with the independent set polytope, which is the convex hull of the independent set indicators. Due to this, in the two class setting, Hv.s, is the convex hull of Pv.N, Hhana hard classifiers achieve the optimal loss, and optimal hard classifiers can be found efficiently.
As seen in Theorem 1 for all K the fractional vertex packing polytope characterizes performance in soft classification problem. However, for K > 2, it becomes distinct from the independent set polytope. An independent set in hypergraph is a subset of vertices that induces no hyperedges. In other words, in each hyperedge of size m, at most m vertices can included in any independent set. Because the edge set of the conflict hypergraph is downward-closed, only the size-two hyperedges provide binding constraints: the independent sets G are the same as the independent sets GS² Thus the concept of hypergraph independent set is not truly relevant for application.
There is third related polytope: the fractional independent set polytope of gS², which has constraint Ess S. 1 for each clique S' in gS The fractional independent set polytope of GS² is contained the fractional vertex packing polytope of G: every hyperedge in produces a clique in g but not the reverse. This inclusion could be used to find an upper bound on optimal soft classification loss.
Furthermore, when K > the fractional vertex packing polytope of the conflict hypergraph, i.e. P can have non-integral extreme points and thus be strictly larger than the independent set polytope. The first configuration in Figure [ cation problems involve optimization over different spaces of correct classification probabilities. Furthermore, maximum weight or even approximately maximum weight independent sets cannot be efficiently found in general graphs: the independent set polytope not easy to optimize over.
illustrates this. Thus the soft and hard classifi-
In Section
3.5 we will use an efficiently computable lower bound on graph independence number.
3.5 Upper bounds on hard classifier loss via Caro-Wei bound on independent set probability
In $3.1 and 3.2 we discussed 2 ways of obtaining lower bounds for the loss of soft classifiers for the multi-class classification problem. In this section, we provide an upper bound on the loss of the optimal hard classifier (we note that this is also an upper bound for optimal loss for soft classifiers). In $3.4. we discussed the relationship between optimal loss achievable by hard classifiers and independent set size. We upper bound the optimal loss of hard classifiers by providing lower bound on the probability of independent set in the conflict graph.
The following theorem is generalization of the Caro- Wei theorem 1 and gives lower bound on the weight of the maximum weight independent set.
Theorem 4. Let G be graph on V with adjacency matrix A (0, 1jvxV and let P be a probability distribution on V. For any w E RV,, w 2 O, there is some independent set S C V with
P(S)
Σ
Wo
((A + l)w)
>0
The proof is in Supplementary
A
7

---

0.8
0.8
(2)
0.6
(3)
0.6
loss
0-1 loss
0.4
0.4
(2)
(T)
AT
0.0
0.0
2.0
2.5
3.0
3.5
4.0
4.5
5.0
3.0
3.5
4.0
4.5
5.0
5.5
6.0
6.5
7.0
(a) MNIST (1,4.7)
(b) CIFAR-10 (0.2.8)
Figure 2: Optimal error for MNIST and CIFAR-10 3-class problems (L" (3)). (2) a lower bound computed using only constraints from edges. AT is the loss for adversarially trained classifier under the strong APGD attack (9).
For comparison, the standard version of the Caro-Wee Wei theorem is simple lower bound on the indepen- dence number of a graph. It states that G contains an independent set S with |S| 2 E 1/(d, + where is the degree of vertex
Note that w the indicator vector for an independent set S', the bound becomes p" w = P(S"). In general, the proof of Theorem can be thought of as randomized procedure for rounding an arbitrary vector into an independent set indicator vector. Vectors w that are nearly independent set indicators yield better bounds.
Theorem provides a lower bound on the size of the maximum independent set in G and thus an upper bound on L (P,
[", n. Hhara), which we call Lew 1 P(S).
4 Empirical Results
In this section, compute optimal losses in the presence of an fg-constrained attacker (12) various strengths for benchmark computer vision datasets like MNIST and CIFAR-10 a 3-class setting, We compare these optimal losses those obtained by state-of-the-art adversarially trained classifiers, showing a large gap. We then compare the optimal loss in the 10-class setting to its upper and lower bounds ($3.), showing matching bounds lower In the Supplementary. C describes hyperedge finding in practice, $D details the experimental setup and $ contains additional results.
4.1 Optimal loss for 3-class problems
Corollary allows hypergraph). ) We compute the optimal loss for 3-way classification, due to the computational complexity of finding higher order hyperedges (see $D.4 of the Supp.). In Figure 2 we plot the optimal loss L (3) computed via the LP in Corollary against the loss obtained through TRADES (31) for 3-class MNIST (classes $1', '4' '7') and 3-class CIFAR-10 ('plane'. 'bird' and 'ship' classes) with 1000 samples per class F For MNIST, we train a 3 layer CNN for 20 epochs with TRADES regularization strength 3 = 1, and for CIFAR-10, we train a WRN-28- 10 model for 100 epochs with 6. We evaluate models using APGD-CE from AutoAttack (9).
compute the optimal loss given any dataset (and its corresponding conflict
B =
From Figure 2. we observe that this gap is quite large even lower values of This indicates that there is considerable progress to be made for current robust training methods, and this gap may be due either the expressiveness of the hypothesis class or problems with optimization. We find that for 100 TRADES is unable to achieve loss much better than 0.6 at an for which the optimal loss near O. This gap much larger than observed by prior work (5, 6) for binary classification. suggesting that current robust training techniques struggle more to fit training data with more classes. In $D.8 of the Supp., ablate over larger architectures, finding only small improvements at lower values of and none at higher.
'ee also used PGD adversarial training (19 but found its performance be worse (See Appendix D.6)

---

L (2)
(3(3)
L (4(4)
(g)(2)
Low
AT
1.00
0.75
0.73
0.50
0.25
0.25
0.00
2.0
2.5
3.0
3.5
4.0
4.5
5.0
2.5
3.0
3.5
4.0
4.5
5.0
535
6.0
(a) MNIST
(b) CIFAR-10
Figure 3: Lower bounds on the exact optimal 10-class loss using hyperedges up to degree (L (2)). 3 (L* (3)) and 4 (4), as well as maximum weight coupling of pairs of binary 0 loss lower bounds (L.,. (2)). Lew is an upper bound from the Caro- Wei approximation of the independent set number. The region in grey represents the range of values we would expect the true optimal loss (10) to fall under.
4.2 Bounds optimal loss for 10-class problems
As the number of classes and dataset size increases, the difficulty of solving the LP in Corollary T increases to the point of computational infeasibility (see $D.4 of the Supp.). We use the methods discussed in Section 3 to bound the optimal loss for 10-class problems MNIST and CIFAR-10 10 datasets on the full trainnn dataset. We present results for each approximation in Figure 3 with the limitation that for some methods, we are only able to obtain results for smaller values of due to runtime blowup. We provide truncated hypergraph bounds for CIFAR-106 in SD.2 of the Supp.
Lower bounding the optimal loss using truncated hypergraphs (.11) : In Figure we plot the loss lower bound obtained via by truncating the hypergraph to consider only edges (2)())), up to degree 3 hyperedges (L* (3)), and up degree 4 hyperedges (L* (4)). Computing the optimal loss would require computing degree 10 hyperedges. However, we find at small values
there is little
difference in these bounds despite the presence of many higher degree hyperedges. This indicates that the use of use of higher degree hyperedges may not be critical to get reasonable estimate of the optimal loss. For example, for CIFAR- 10M degree 4 hyperedges, but these constraints have no impact on the computed lower bound. To understand the impact of hyperedges, we provide the count of hyperedges for each value of and plots of the distribution of optimal classification probabilities per vertex in $D.3 of the Supp. From Figure 2 we find that the difference L (2) and L (3) does not occur until the loss reaches above 0.4 for the 3-class problem.
3. we observe 3M degree 3 hyperedges and
Takeaway: In practice, we do not lose information from computing lower bounds with only edges in the conflict hypergraph.
Lower bounding the optimal loss using the lv1 binary classification problems ($3.2) We can use the algorithm from Bhagoji et (6. to efficiently compute Iv1 pairwise optimal losses to find lower bound the 10-class optimal loss (2)) From Theorem 3, coupling over these optimal losses to find a lower bound. Optimal loss heatmaps for each pair of classes in MNIST and CIFAR-10 10 are in $D.5 of the Supp. The efficiency of the 1v1 computation allows us to compute lower bounds at larger values of e in Figure
maximum weight
Takeaway: From Figure 3 we find that while this lower bound is the most efficient to compute, the obtained bound is much looser compared to that from truncated hypergraphs. This arises from the weak attacker assumed while computing this bound.
Upper bounding optimal loss via Caro-Wei approximation ($3.5) : In Figure we also plot the upper bound on 0 1 loss for hard classifiers (denoted by Lcw) obtained via applying Theorem 4 with vertex weights obtained from the solution L (2). When becomes large (c 2 3.0 for MNIST and 2 4.5 for CIFAR-10, 10), the loss upper bound increases sharply. This indicates the lower bound on the independent set size becomes looser as the number of edges increases, due to the importance of higher-order interactions that are not captured by the approximation. At the small values of & used in practice however, the lower bounds obtained through truncated hypergraphs (I,",2), L (3), and L (4)) are close the value of this upper bound.

---

Takeaways: (i) We do not lose much information from not including all hyperedges at small e values as the upper and lower bounds are almost tight; (ii) At these small values of e, we do not expect much difference in performance between hard classifiers and soft classifiers.
Comparing loss of trained classifiers to optimal: In Figure 3 we also compare the loss obtained by a robustly trained classifier (AT) to our bounds on optimal loss. For both datasets, we see a large gap between the performance of adversarial training and our bounds (including the upper bound from the Caro- Wei approximation Lcw). even at small values of e. This suggests that current robust training techniques are currently unable to optimally fit the training data in multiclass classification tasks of interest. In addition, we also checked the performance of state-off of-the-art verifiably robust models on these two datasets from a leaderboard (18). For MNIST, the best certifiably robust model has a 1 loss of 0.27 at a budget of 1.52 and 0.44 at a budget of 2.0, while for CIFAR- 10, the best certifiably robust model has 0 loss of 0.6 at budget of 1.0 and 0.8 at a budget of 2.0. These are much higher than the optimal lower bound that is achievable for these datasets which is O in all these cases.
Takeaway: Performance of state-of-the-an robust models, both empirical and verifiable, exhibit large gap from the range of values predicted by our bounds on optimal 0 - 1 loss, even when is small. Future research focusing on developing algorithms to decrease this gap while maintaining generalization capabilities may lead to improvements in model robustness.
Discussion and Related Work
When the data distribution satisfies certain properties, Dohmatob 11) and Mahlouji- far et al. (20) use the 'blowup' property to determine bounds on the robust loss, given some level of loss on benign data. We note that these papers use a different loss function that depends on the original classification output on benign data, thus their bounds are not comparable. Bhagoji et al. (5 (), and Pydi et al. (22) provide lower bounds on robust loss when the set of classifiers under consideration is all measurable functions. These works only provide bounds in the binary classification setting. provides bounds on the robustness of specific classifiers. Yang al. (30) independently introduced the concept of 'conflict graph' to obtain robust non- parametric classifiers via an adversarial pruning defense. The closest related work to ours is Trillos et al. (29). which uses optimal transport theory to find lower bounds multi-class classification that are applicable for both continuous and discrete distributions. While their theoretical bounds exact and more general than ours, accounting for distributional adversaries, their numerically computed bounds via the Sinkhorn algorithm are approximate and converge to the true value only as the entropy regularization decreases. In contrast, we provide methods to directly compute the optimal loss for discrete distributions, along with efficient methods for determining its range to overcome the computational bottlenecks encountered.
Related Work:
Work on verifying robustness (8 13 18)
Discussion and Limitations: Our work in this paper firmly establishes for the multi-class case what was known only in the binary setting before: there exists large gap in the performance of current robust classifiers and the optimal classifier. It also provides methods to bound the loss efficiently in practice, giving practitioners quick means to determine the gap. The question then arises: why does this gap arise and how can we improve training to decrease this gap? This paper, however, does not tackle the problem of actually closing this gap. Possible methods include increasing the architecture size (26), using additional data (I5) and using soft-labels (6). A surprising finding from our experiments was that the addition of hyperedges to the multi-way conflict graph did not change the lower bounds much, indicating we are in a regime where multi-way intersections minimally impact optimal probabilities. One major limitation of our work is the computational expense at nature of
larger budgets, sample sizes and class sizes. We suspect this is due to the the solvers we use and future work should look into developing custom algorithms to speed up the determination of lower bounds.
Acknowledgments and Disclosure of Funding
ANB, WD and BYZ were supported in part by NSF grants CNS-2241303. CNS-1949650, and the DARPA GARD program. SD was supported in part by the National Science Foundation Graduate Research Fellowship under Grant No. DGF-2039656. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect
10

---

the views of the National Science Foundation. SD and PM were supported in part by the National Science Foundation under grant CNS-2131938, the ARL's Army Artificial Intelligence Innovation Institute (A212), Schmidt DataX award, and Princeton E-ffiliates Award.
References
[T] N. Alon and J. H. Spencer. The probabilistic method. John Wiley & Sons, 2016.
[2] M. S. Andersen, J. Dahl, and L. Vandenberghe. Cvxopt: Python software for convex optimiza- tion, 2013.
[3] M. ApS. MOSEK Optimizer API Python 10.0.22, 2019. URL https:://occs.mme mosek. com/
10. htppthhonapiiinee..........e html
[4] A. N. Bhagoji, W. He, B. Li, and D. Song. Exploring the space of black-box attacks on deep neural networks. arXiv preprint arXiv:1712.09491, 2017.
[5] A. N. Bhagoji, D. Cullina, and P. Mittal. Lower bounds on adversarial robustness from optimal transport. In Advances in Neural Information Processing Systems, pages 7496-7500 2019.
[6] A. N. Bhagoji, D. Cullina, V. Sehwag, and Mittal. Lower bounds on cross-entropy loss in the presence of test-time adversaries. In Proceedings of the 38th International Conference on Machine Learning, 2021.
[7] R. Bunel, I. Turkaslan, P. H. Torr, P. Kohli, and M. P. Kumar. A unified view of piecewise linear neural network verification. arXiv preprint
2017.
[8] N. Carlini and A. Wagner. Towards evaluating the robustness of neural networks. CoRR, haw/1608.044444 2016. URI.http://arxiv org/ 1108. .4644
[9] Croce and M. Hein. Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free free attacks. In International Conference on Machine Learning, pages 2206-2216. PMLR, 2020.
[10] D. Cullina, A. N. Bhagoji, and Mittal. Pac-learning in the presence adversaries. In Advances in Neural Information Processing Systems, pages 230-241, 2018.
[11] E. Dohmatob. Generalized no free lunch theorem for adversarial robustness. In Proceedings of the 36th International Conference on Machine Learning, pages 1646-16555 1446-1654,22 2019.
[12] I. J. Goodfellow, J. Shlens, and C. Szegedy. Explaining and harnessing adversarial examples. In International Conference on Learning Representations, 2015.
[13] S. Gowal, K. Dvijotham, R. Stanforth, R. Bunel, C. Qin, J. Uesato, T. Mann, and P. Kohli. On the effectiveness of interval bound propagation for training verifiably robust models. arXiv preprint arXiv: 1810 2018
[14] Gowal, C. Qin, Uesato, Mann, and P. Kohli. Uncovering the limits of adversarial training against norm-bounded adversarial examples. arXiv preprint arXiv: 2010:2010000 0..5909,,, 2020.
[15] S. Gowal, S. Rebuffi, O. Wiles, F. Stimberg, D. A. Calian, and T. A. Mann. Improving robustness using generated data. M. Ranzato, A. Beygelzimer, Y. N. Dauphin, P. Liang, and J. W. Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6- 14, 2021, virtual, pages 4218 4233, 2021. URL /ttp:tttt////sooeddiiiii
nwwrinsr.p... cotuips..c/pppee... ccppaprr////cac 2222///eaa//11100007222200000000 Awst-ratttttt... html
[16] A. Krizhevsky and G. Hinton. Learning multiple layers of features from tiny images. 2009.
[17] Y. LeCun and C. Cortes. The MNIST database of handwritten digits. 1998.
[18] I. Li, T. Xie, and B. Li. Sok: Certified robustness for deep neural networks. 2023 IEEE Symposium Security and Privacy (SP), pages 1289-1310. IEEE, 2023,

---

[19] A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Vladu. Towards deep learning models resistant to adversarial attacks. In ICLR, 2018.
[20] S. Mahloujifar, D. I. Diochnos, and M. Mahmoody, The curse of concentration in robust learning: Evasion and poisoning attacks from concentration of measure. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages
2019.
[21] O. Montasser, Hanneke, and N. Srebro. Ve classes are adversarially robustly learnable, but only improperly. arXiv preprint arXiv: 2019.
[22] M. Pydi and V. Jog. Adversarial risk via optimal transport and optimal couplings. In Proceedings of the 37th International Conference on Machine Learning, pages 7814-7823, 2020.
[23] M. S. Pydi and V. Jog. The Many Faces of Adversarial Risk, Jan. 2022. URL http:://a// org/ arg/abs/ tabs/2201..oe 2201.08956) WrXiv:2201.09990 [cs, math, stat].
[24] E. R. Scheinerman and D. H. Ullman. Fractional Graph Theory: Rational Approach to the Theory of Graphs. Wiley, Sept. 1997. ISBN 978-0-471-1786444, Google-Books Books-Io:
KujuAAAAMAAJ.
[25] L. Schmidt, S. Santurkar, D. Tsipras, K. Talwar, and A. Madry. Adversarially robust generaliza- tion requires more data. arXiv preprint arXiv: /285, 2018.
[26] V. Schwag, S. Mahloujifar, T. Handina, S. Dai, C. Xiang, M. Chiang, and P. Mittal. Robust learning meets generative models: Can proxy distributions improve adversarial robustness? In The Tenth International Conference on Learning Representations. ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net, 2022. URL https://openrevien..n www.::/wwwwtfooommommmmm WVXONNVBBRVI
[27] C. Szegedy, W. Zaremba, I. Sutskever, J. Bruna, D. Erhan, I. Goodfellow, and R. Fergus. Intriguing properties of neural networks. arXiv preprint arXiv:1312.6199, 2013.
[28] V. Tjeng, K. Y. Xiao, and R. Tedrake. Evaluating robustness of neural networks with mixed integer programming. In ICLR, 2019.
[29] N. G. Trillos, M. Jacobs, and J. Kim. The multimarginal optimal transport formulation of adversarial multiclass classification. Journal of Machine Learning Research, 24(45):1-56, 2023.
[30] Y.-Y. Yang, C. Rashtchian, Wang, and Chaudhuri. Robustness for non con-parametric classifi- cation: A generic attack and defense. In International Conference Artificial Intelligence and Statistics, pages 941- PMLR, 2020.
[31] H. Zhang, Y. Yu, J. Jiao, E. P. Xing, L. E. Ghaoui, and M. I. Jordan. Theoretically principled trade-off between robustness and accuracy. arXiv preprint arXiv:1901.085550 2019.
12

---

This Supplementary Material accompanies paper: Characterizing the Optimal 0 1 Loss for Multi- class Classification with Test-time Attacker NeurIPS 2023.
We first present proofs for theorems from the main body in A We then explain fractional packing
and covering in [B] We present our algorithm for hyperedge finding in $ $ Contaain further details
about the experimental setup with all additional experimental results in
A Proofs
Proof of Theorem 1. This follows immediately from Theorem 2 with K.
Proof of Theorem 2. Recall that the definition of the correct-classfficttion probabilities is
Qm, (H) inf #EN(x) ce ( SEE
min h(;;; C)2
and the set of achievable correct-classification probabilities
PVNNH
U II 00, (x)c)) REW
First, we will show P..,...H.off C E 2 0, BSng q S 1}. The constraint h E Hsoft, S (h) I 1 holds because classification probabilities h(2, C)2, must lie in the range [0, 1].
We will now demonstrate that the constraint BSnn S must also hold. Let e ((x1, (ze, ve)) be size-L hyperedge in g(Sm), By construction of g(Sm), there exists some I Ti=nN(a Let S E ((K) be some superset of {yn..... .ye.. which exists because / S m. From the definition of 9m,N (h), we have that 4m.N 4m.,(()((z..))) (h) S ((ū for each 1 S f. Thus,
Σ am, (1b) S S), S Σ
h(ā, S) 1.
jEy
This gives (BSmq)e g)c I
Now we will show Pm,,,N.He 2 fa ER 02 B mm 9 1 1}.
For any vector q the polytope, have a classifier h: X ((K)) - R that achieves least those
correct classification probabilities. This mean that h has the following properties. First, h(ā, L)g 2 0 and EvE(K] h(ū, L)y = Second, for all (z, y) E V. all ē E (z), and all ((k)) such that E L. we have li,,, L) 2 ((2.9))
i & and g( D)y max(0, max Sup (((.)))))) Ty E Vy, E E N N(r,)) })) H). Let L' C L be the set of indices where g L)y > 0. Then any list of vertices e = (xg y E I/, Ty E Vyy E ((x,)) forms a hyperedge of size TT'| S m.
To get h, first define the function g X (1K) R( g(ō, D), = for
Thus
Σ g(; Σ g(ū, L)y sup Σ (ay.a) I sup vE[K]
BEL'
yEL'
To produce h, allocate the remaining probability (1 E, g(, D)y) to an arbitrary class.
Proof of Theorem 3. The first part of this proof applies for any side-information size m. The adversarial strategy for selecting C' is a specified by conditional p.m.f. (Cly). Thus (y)C( = Pa (C(W)))))) Ey (C1y(Cly/) (3'))
The optimal loss of the classifier against a particular adversarial strategy is just a mixture of the optimal losses for each class list: Ec Poly(CCl)) LP) E N,,
(Cly)(Cly) = Pcly (C'ly) for all y, y E C, then PMC( (y (/w)/Evec Evec Py and the adversary has not provided the classifier with extra information beyond the fact that y E C. Thus Paly ( C*).
13

---

Now we can spcialize to the m 2 case. Any stochastic matrix s with zeros on the diagonal specifies an adversarial strategy for selecting C' with PCIp ((i,j]]i St.j. Furthermore, if is also symmetric, PCly (i:) ((i.j()))))) and Poic the side-information game uses the (2) optimal classifiers for the two-class games and incurs loss Ei, Pr[Y = j where aijj = LP E (i, N).. Because the diagonal entries are all zero, there is always a maximizing choice of s with a zero diagonal. Thus is not necessary to include that constraint when specifying the optimization.
= Pylc(((ii,)).. Then the optimal classifier for
Proof of Theorem 4. If w 0, then the lower bound is zero and holds trivially. Otherwise, 1=w w forms a probability distribution over the vertices. Let X E y be sequence of i..d. random vertices with this distribution. From this sequence, we define random independent set as follows. Include in the set if it appears in the sequence X before any of its neighbors in G. If and u' are adjacent, at most of them can be included, so this procedure does in fact construct an independent set. wi I"w and the probability that X; or adjacent to v is [(A+)w)) 1' 10
The probability that X; = The first time that the latter event occurs, is either included in the set or ruled out. If > O, the probability that e is included in the set ([A+))w) and otherwise is zero. Thus the quantity
P(S in Theorem is the expected size of the random independent set and G must contain some independent set least that large.
B Fractional packing and covering
In this section, we record some standard definition in fractional graph and hypergraph theory (24).
Let 9 (V.E) be hypergraph and let B E REXV be its edge-vertex incidence matrix. That is, Be = if v E and Be,- = 0 otherwise. Let E RV be a vector of nonnegative vertex weights. Let 0 be the vector of all zeros and let be the vector of all ones (of whichever dimensions are required).
fractional vertex packing in G is vector q E VRV in the polytope
2
Bq $1. 1.
The minimum weight fractional vertex packing linear program is
minp' 1a s.t.
0
Bq S 1.
fractional hyperedge covering in & for weights p is vector 2 E RV in the polytope
q BT22p.
The minimum weight fractional hyperedge covering linear program is
min 1T s.t. 220, BTzZP
These linear programs form dual pair. The independent polytope for G is the convex hull of the independent set indicator vectors.
Let g' be a graph on the vertex set V. A clique in G' is a subset of vertices which every pair are adjacent. Let C' be the set of cliques of G' and let C' e gxV be the clique vertex incidence matrix. (In fact this construction can be interpreted as another hypergraph on V.) A fractional clique cover in g' for vertex weights p is vector RC in the polytope
0
C.p2.
Somewhat confusingly, the dual concept is called fractional independent set in g'. This is vector q E R in the polytope
Cq S 1.
14

---

C Hyperedge Finding
One challenge in computing lower bounds for - 1 loss in the multi-class setting is that we need to find hyperedges in the conflict hypergraph. In this section, we will consider Ez adversary: N(z) = {a' E X ||ا - æl12 S <} and describe an algorithm for finding hyperedges within the conflict graph.
We first note that for an n-way hyperedge to exist between inputs (xi)121 {mr) must all lie on the interior of
1-dimensional hypersphere of radius
Given input #1, Iy where 2; E Ed, we first show that distance between any two points in the affine subspace spanned by the inputs can be represented by a distance matrix whose entries are the squared distance between inputs. This allows us to compute the circumradius using the distance information only, not requiring a coordinate system in high dimension. Then we find the circumradius using the properties that the center of the circumsphere in the affine subspace spanned by the inputs and has equal distance to all inputs.
We construct matrix X R whose 7th column is input zi. Let D E R be the matrix of squared distances between the inputs, i.e., Da, = | - -xyl 122
We first notice that can be represented by X and vector 1" whose 7th entry is the squared Then given that Dij is
norm of x;. Let A E R" be such vector such that A, = |0;||2 the squared distance between 2i and æy, we have
Dij |2,||
+
|0, 112 ((11,
which implies that
D= A1" + 1A -2x
Let Ot, 3 E IR" be vectors of affine weights: 1 a: = 3² Then Xa and X are two points the
affine subspace spanned by the columns of X. The distance between Xa and XB (aa-3)) 83 D(a-8) shown as below:
- (ax (3) D(a 3) - (A1 +1A -2X x)) 3)
2
2 -00+0- 2(a -B) XT x
2
||Xaa= - -x/9112
Now we compute the circumradius using the squared distance matrix D. The circumcenter is in the affine subspace spanned by the inputs so we let Xa to be the circumcenter where 1 = 1. Let e(t) E R be the jt standard basis vector. The distance between the circumcenter and x; is
||Xa X 12 From previous computation, know that |Xa Xe -aa-e(")" D(a-e(") Since the circumcenter has equal distance to all inputs, we have
(ar - ( D(a e(a) =... (a (x)) ((())
Note that the quadratic term in a is identical in each of these expressions, In addition, e(i) (e = 0 for all i. So equation 7 simplifies to the linear system
( Da Da=c== = Da cl
cD
for some constant c. Since aTa we have
1 = T D-1
= D
15

---

assuming that D is invertible. The square of the circumradius, r², which is the squared distance between the circumcenter and 21,
|| x2
- (ax - --(0)) D(a e(2))
2
a Dax
=1 Da
C²1'D-1 '1
-
2
2
21"
Therefore, assuming matrix D is invertible, the circumradius is D21TDD11
The inverse of can be computed as det adj D Since a = cD-11, we have a = edet D [adj D 1. As p2
D constant is non-negative. Therefore, a X adj
When all entries of are non-negative, the cireumcenter is a convex combination of the all inputs and the circumsphere is the minimum sphere in RR-1 that contains all inputs. Otherwise, the cireumsphere of {a: (o 0} is the minimum sphere contains all inputs.
After finding the radius of the minimum sphere that contains all imputs, we compare the radius with the budget If the radius is no larger than then there is hyperedge of degree among the inputs.
D Experimental Setup
In this section, describe our experimental setup. Our code for computing bounds is also available at hhttps:/// : // htt///gtttt..t///////////tt wtt.coomiiiniee iwwpiriiiiieeeeeeee ceceppirr-gouup/// wwwpoo//mmmicllsssooooeooeeee
Datasets:
We compute lower bounds for MNIST (17), CIFAR-10, and CIFAR- 100 (16). Since we do know the true distribution of these datasets, we compute lower bounds based on the empirical distribution of the training set for each dataset.
Attacker: We will consider
adversary: N(x) (x' x ||= - 2112 S $c). This has been used
in most prior work 5 29).
LP solver: For solving the LP in Equation (4), we primarily use the Mosek LP solver 3 When the Mosek solver did not converge, we default to using CVXOpt's LP solver (2).
Computing infrastructure. In order to compute lower bounds, we perform computations across 10 2.4 GHz Intel Broadwell CPUs. For adversarial training, we train on a single A100 GPU.
40-step optimization to find adversarial examples during training and use step size 3n and train all models for 20 epochs. For CIFAR-I0 and CIFAR-IOK we use 10 step optimization to find adversarial examples and step size & and train models for 100 epochs. For MNIST TRADES training, we use 8 = and for CIFAR-10 10 and CIFAR- -00, we use f = 6. Additionally, for CIFAR-10 10 and CIFAR- 100, optimize the model using SGD with learning rate and learning rate scheduling from (4). For MNIST, we use learning rate 0.01.
Training Details For MNIST, s
Architectures used: For CIFAR-10 and CIFAR-100, we report results from training a WRN-28-10 architecture. For MNIST, we train small CNN architecture consisting of 2 convolutional layers. each followed by batch normalization, ReLU, and 2 by max pooling. The first convolutional layer uses 5 by 5 convolutional kernel and has 20 output channels. The second convolutional layer also uses 5 by kernel and has output channels. After the set of convolutional layers with batch normalization, ReLU, and pooling, the network has fully connected layer with 500 output channels followed by a fully connected classifier (10 output channels). In SE.8 architecture on closing the gap to the optimal loss.
we consider the impact of
16

---

E Additional Experimental Results
In this Section, we provide additional experimental results to complement those from the main body of the paper. We organize it as follows:
E.1 We analyze a toy problem on 2D Gaussian data to get a better understanding of the
impact of hyperedges on the optimal loss computation.
We investigate why higher degree hyperedges dp not have a large impact on lower bounds at lower values of
E.2
E.33 We show the runtime explosion higher values of that makes challenging for us
to report optimal loss values.
E.4
Classwise L.2 distance statistics and heatmaps for pairwise losses used to compute
class-only lower bounds in main paper.
E.. We provide results with standard PGD-based adversarial training, and show it is outperformed by Trades.
E.6
We provide results on the CIFAR-100 dataset.
We show lower bounds for a different of 3 classes than the one considered in the main body. Main takeaways remain the same.
E..7
$ We ablate across larger neural networks to check if increasing capacity reduces the optimal.
gap
E. We attempt dropping examples from the training set that the optimal clasifier cannot classify correctly order to improve convergence.
11.10 We compute lower bounds on the test set for MNIST 3-class classification
E.1 Results for Gaussian data
Figure 4: sample 3-class Gaussian problem (each color pertains to a class) and a corresponding classifier for this problem shown in black. The classifier classifies a sample incorrectly when it lies over the edge of the margin (shown by the red lines) nearest the corresponding Gaussian center.
We begin with a 3-way classification problem on 2D Gaussian data. To generate our Gaussian dataset, we sample 1000 points per class from 3 spherical Gaussians with means at distance away from from the origin (a sample is shown in Figure 4). We compute multiclass lower bounds via the LP in Theorem on robust accuracy at various &g budget e and display these values in Figure as L (3)).. Additionally, compare to deterministic 3 way classifier. This classifier is the best performing out of the strategies: 1) constantly predict a single class (thus achieving 2 loss) or 2) is the classifier in black in Figure which classifies incorrectly when sample lies over the edge of the nearest margin of the classifier.
We observe that at smaller values of the loss achieved by the 3-way classifier matches optimal loss (L* (3)): however, after 2.5 for o² 0.05 and 2.3 for o² 0.5, we find the classifier no longer achieves optimal loss. This suggests that there is a more optimal classification strategy these larger values of e. Figures [[nd we visualize
distribution correct classification probabilities obtained through solving the I.P with and without considering hyperedges. These figures are generated by taking fresh sample of 1000 points from each class and coloring the point based on the correct classification probability qo assigned to its nearest neighbor that was used in the conflict
17

---

0.8
L'(2)
0.8
(2(
(3)
L"(3)
loss
0.6
Classifler loss
0-1 loss
Classifier loss
0.4
0.4
0.0
2.0
2.1
2.2
2.3
2.4
2.5
2.6
2.7
2.8
0.0
1.5
1.6
1.7
1.8
1.9
2.0
2.5
(a) 0²
0.05
(b) 0² 0.5
Figure Lower bounds on error for the Gaussian 3-class problem (o² 0.05 and 0² 0.5) computed using only constraints from edges (2)) and up to degree 3 hyperedges (L* (3) in
comparison the performance of the deterministic 3-way classifier depicted in Figure 4
hypergraph when computing the lower bound. We observe from Figure for all classes, the data mostly assigned classification probabilities around 0.5. In Figure we can see that when we consider hyperedges, we some of these 0.5 assignments are reassigned values close &/2 and 5. Interestingly, we notice that when we do not consider hyperedges, our solver finds an asymmetric solution to the problem (strategies for class O, and differ) while when considering hyperedges this solution becomes symmetric.
45
(a) Class 0
(b) Class
(c) Class
Figure 6: Distribution of optimal classification probabilities across samples from each class of the Gaussian obtained as a solution when computing L (2).
02
(a) Class 0
(b) Class
(c) Class 2
Figure 7: Distribution of optimal classification probabilities across samples from each class of the Gaussian obtained solution when computing L" (3).
E.2 Impact of hyperedges
In Figure we show the count of edges, degree hyperedges, and degree hyperedges found in the conflict hypergraphs of the MNIST, CIFAR- 10, and CIFAR- 100 train sets. We note that did
18

---

not observe any increase in loss when considering degree 4 hyperedges at the with data point for number of degree 4 hyperedges in Figure We find that the relative number of edges and hyperedges is not reflective of whether we expect to see increase in loss after considering hyperedges. For example CIFAR-10, at e 4.0, we there are about 100 times more hyperedges than edges, but we see no noticeable increase in the 0 1 loss lower bound when incorporating these hyperedge constraints.
Edges
Degree 3 hyperedges
Degree hyperedges
MNIST
CIFAR-10
CIFAR: 100
104
10
107
104
20
207
207
101
20a
2.5
3.0
3.5
2.0
3.0
5.0
(a) MNIST
(b) CIFAR-10
(c) CIFAR-100
Figure 8: Number of edges, degree 3 hyperedges, and degree 4 hyperedges found in the conflict hypergraphs of MNIST, CIFAR-10, and CIFAR-100 train sets. The red vertical line indicates the at which we noticed an increase in the 0 loss lower bound when considering degree hyperedges.
To understand why including more information about hyperedges does not influence the computed lower bound much, we examine the distribution of g. obtained from solutions to the LP with (L* (3)) and without degree 3 hyperedges (L* (2)). Fig. 9 contains a histogram of the distributions of qu for MNIST. For small e, there is change in the distribution of qu, the distribution of q, is almost identical between I." (2) and (3). At larger values of c, in I." (2), significant fraction of vertices are assigned Go near 0.5. While these shift with the addition of hyperedges, very few of them were in triangles of g that were replaced by hyperedge in g This leads to the loss value changing minimally.
Similar to Figure 9 we plot the distribution of vertex weights obtained through solving the LP for L (2) and L (3) for CIFAR-10 in Figure TO Similar to trends for MNIST, we find that the gap between L (2) and L (3) only occurs when the frequency of 0.5 weights is higher.
(2)
L3(3)
Distribution of for g=2.5
Distribution q, for g=3.0
Distribution g, for 3.3555
0.8
fraquency
0.6
frequancyy
0.6
frequency
0.6
0.2
0.2
0.2
0.0
0.75
1.00
0.0
0.50
0.75
4
9
(a) 6 2.5
(b) c = 3.0
(c) 3.5
Figure 9: Distribution of optimal classification probabilities q obtained by solving the LP with up to
degree 2 hyperedges (m = 2) and to degree 3 hyperedges (m 3) on the MNIST training set.
E.3
Computational complexity of computing lower bounds
Our experiments of L=(() and (4) at higher are limited due to computation constraints. Figure I1 we see that the time taken compute the (3)(3) grows rapidly with e. We also report timings for all bounds for CIFAR-10 10 a in Table In future work, we are seeking algorithmic optimization to achieve more results at high
19

---

(2)
L. (3)
9, c=3.5
9, c=4.0
Distribution q,
0.8
frequency
0.0
fraquancy
0.6
frequency
0.4
0.4
0.2
0.2
0.0
0.00
0.25
0.50
0.75
1.00
0.0
0.00
0.25
0.50
0.75
1.00
0.0
0.00
0.25
0.50
0.75
1.00
%v
4v
(a)
3.5
(b)
4.0
(c) c = 4.5
Figure 10: Distribution of optimal classification probabilities y obtained by solving the LP with up to degree hyperedges (L* (2) and up to degree 3 hyperedges (L)) the CIFAR-10 training set.
(2)
(')
MNIST
CIFAR-10
10F
10a
10
37 102
tme (6)
10*
Uime
301
5.5
(a) MNIST
(b) CIFAR-IU
Figure 11: Time taken to compute (2) and (3) for MNIST and CIFAR-10.
E.4 Classwise statistics and pairwise losses
In order have better understanding of the difficulty of the classification task under the presence of an l2 bounded adversary, we report the average & to the nearest neighbor of another class for each class in the MNIST and CIFAR-I0 datasets in Table 3
Another way of understanding the relative difficulty of classifying between classes is by computing the optimal loss for all 1v1 binary classification tasks. We note that these values used in Section 4.2 to compute lower bound on the optimal loss in the 10-class case from maximum weight coupling optimal losses for lvl binary classification problems. In Figure 12, show the heat maps for optimal losses for each pair of lv1 classification problems for 3 on MNIST and = on CIFAR-10. We find that for both datasets only few pairs of classes have high losses. Specifically, for MNIST, we find that the class pairs 4-9 and 7-9 have significantly higher loss than all other pairs of classes. For CIFAR-IO, we find that 2-4 has the highest loss compared to other pairs, and 2-6 and 6-4 are also quite high.
E.5 Additional adversarial training results
In Figure [3] we also add the loss achieved by PGD adversarial training. We find that this approach generally performs worse on MNIST compared to TRADES and is also unable to fit to CIFAR-10 data at the values tested.
E.6 Truncated hypergraph lower bounds for CIFAR-100
We provide results for truncated hypergraph lower bounds for the CIFAR-100 train set. We observe that similar to MNIST and CIFAR-10, including more hyperedge constraints does not influence the computed lower bound.
20

---

Loss bound
Runtime (s)
L2(2)
188.24
(²(3)
10413.91
(4)
>86400
(2)
327.92
Low
192.27
Table Runtimes for computing different bounds for CIFAR-10 dataset at 6 = 4. We note that the To (2) reports the time for computing all pairwise losses sequentially and can be sped up by running these computations in parallel. We also note that (4) computation did not terminate within day.
0
2
3
4
5
8
9
MNIST
7.07
4.33
6.94
6.29
5.72
6.29
6.42
5.52
6.29
5.15
CIFAR-10
8.96
10.84
8.48
9.93
8.22
10.04
8.72
10.05
9.23
10.91
Table 3: Average & distance to nearest neighbor in another class for each class in MNIST and CIFAR-10 datasets.
E.7 Computed bounds for a different set of 3-classes
plot 3-class lower bounds via truncated hypergraphs (2) and (²)3)) for different set of classes as shown the main body. These classes generally have less similarity than the classes shown in the main body of the paper causing the loss bound to increase more slowly as epsilon increases. However, we find that patterns observed for the classes present in the main body of the paper also present here: the gap between L (2) and L L*(3) is only visible at large values of 0-1 loss (ie. loss of 0.4).
In Figure 15
E.8 Impact of architecture size
Previously, we saw that adversarial training with larger values of generally fails to converge (leading to losses matching random guessing across classes). We now investigate whether increasing model capacity can resolve this convergence issue. In Figure 16 plot the training losses of 3 WRN architectures commonly used adversarial ML research across attack strength for the 3-class CIFAR- 10 (classes 0, 2. 8) problem. All models trained with TRADES adversarial training. Interestingly, we find that the benefit of larger architecture size only appears for the smallest value of epsilon plotted (e 1) at which the optimal classifier can theoretically obtain 0 loss. At larger values of epsilon, the improvement in using larger architecture generally disappears.
E.9 Impact of dropping "hard" examples
From our experiments involving adversarial training, we found that training with large values of e generally fails to converge. A potential way of trying to improve convergence using the results from our LP is to drop examples with optimal classification probability less than and train with the remaining examples. Since even the optimal classifier cannot classify these examples correctly, these examples can be considered "hard" to learn. We find that in practice this does not lead to lower training loss, specifically, training without "hard" examples leads to a loss of 0.64 for CIFAR-10 10 with = 3 while training with "hard" examples leads to loss 0.57. We note that this loss is computed over the entire training dataset (including "hard" examples) for both settings.
E.10 Lower bounds on test set
In the main text, computer lower bounds on the train set this would measure how well existing training algorithms are able to fit to the training data. In Table 4 we compute lower bounds on the test set (which contains 1000 samples per class) for MNIST 3-class classification between classes 1, 4, and 7. We find that the computed loss is similar to what computed on a subset of the train set which contains the same number of samples per class.
21

---

pairwise
painwise when c-4
0.30
0.200
0.25
0.150
0.20
0.15
0.100
0.10
7-
0.050
0.05
7
5
0.00
0.000
(a) MNIST (c
3)
CIFAR-I0 4)
Figure 12: Heat maps for optimal loss for each pair of Ivl classification problems.
0.8
loss
0.6
loss
0.6
N
0.44
(2)2)
0.44
L2)
L')
(3(3)
0.2
TRADES-AT
0.2
TRADES-AT
PGD-AT
PGD-AT
0.0
2.0
2.5
3.0
3.5
5.0
0.0
3.0
4.0
4.5
5.5
6.0
6.5
7.0
(a) MNIST (1, 7, 9)
(b) CIFAR-I0 (0, 2)
Figure 13: Lower bounds error for MNIST and CIFAR-10 3-class problems (1000 samples per class) computed using only constraints from edges (L" (2)) and up to degree hyperedges (L" (3)) in comparison to TRADES adversarial training (TRADES-AT) and PGD adversarial training (PGD-AT) loss.
0.8
+ (2)
0.6
L'(3)
0-1 loss
(4)
0.4
0.2
0.0
2.0
2.5
3.0
3.5
4.0
4.5
5.0
5.5
6.0
6.5
E
Figure 14: Lower bounds for optimal 0-1 loss the for CIFAR-100 train set
MNIST Class 2, 5, 8
CIFAR-10 Class 1, 4, 9
0.6
(2)
0.6
(2)
(3(3)
L"(3)
0.4
loss
0.4
0-1
0-1
0.0
2.0
2.5
3.0
3.5
4.0
4.5
5.0
3.0
3.5
4.0
4.5
5.0
5.5
6.0
6.5
7.0
(a) MNIST (2, 5, 8)
(b) CIFAR- 10 (1, 4,
Figure 15: Lower bounds on error for MNIST and CIFAR-10 3-class problems (1000 samples per class) computed using only constraints from edges (I." (2)) and up degree 3 hyperedges (L)(3)
22

---

(3) WRN-28:10
WAN-34-10
WAN-70-16
0-1
Figure 16: Impact of architecture size training loss for 3-class CIFAR (0, 2, 8) different strengths c for models trained with TRADES adversarial training.
train
train set
test set
(1000 samples per class)
2
0.0045
0.0020
0.0025
2.5
0.0260
0,0193
0.0149
3
0.1098
0.0877
0.0773
3.5
0.2587
0.2283
0.2181
4
0.4083
0.3987
Table 4: Optimal losses (3) for MNIST class problem (classes 4, 7) computed across the train set, the first 1000 samples of each class in the train set, and computed across the test set.
23


Reviews:
[{"review_id": "cQlePvdj4O", "reviewer": "Reviewer_baps", "summary": "This paper aims to analyze the optimal 0/1 loss under the most strongest test time attack. The study commences by formulating the problem of obtaining the optimal classifier (based on 0/1 loss) as a linear program on a graph. Subsequently, the authors address the high computational complexity of calculating the optimal 0/1 loss by proposing a reduction technique through graph truncation. This reduction enables the computation of a lower bound of the 0/1 loss in a feasible timeframe. Ultimately, the authors present empirical evidence comparing their bound with the empirical defense method on real-world data. Notably, they discover that the widely-used baseline (adversarial training) still offers significant potential for improvement.", "questions": "Are there any of my review comments that misunderstood the paper? If so, please point them out. I am happy to adjust accordingly.\n", "limitations": "The authors do properly addressed the limitation of this work, which includes the lack of scalability of their algorithm and the lack of implications on how to close the gap between the current robust classifiers and the optimal classifier.\n", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is written clearly and easy to follow.\n- This paper extents the analysis on the optimal classifier under test time attack to multi-class classification setting. It seems to be a decent extension/contribution to the theoretical side of the field of adversarial robustness.\n- Usually for this kind of problem, the computation complexity is one of the main challenge. However, they are able to find a way to speed it up. The idea of reducing it to a graph and then truncate the complex edges to reduce the computation needed for getting the bounds is interesting. In addition, they also show that empirically, such relaxation does not lose much information.", "weaknesses": "- Although it is mentioned in the related work that this is different from verifying robustness. I think it would be a valuable information to include bounds for verified classifiers in the empirical section. It would be interesting to see how close the existing verified classifiers are to the optimal bound. \n- A related work titled \"Robustness for non-parametric classification: A generic attack and defense.\" published in International Conference on Artificial Intelligence and Statistics, 2020 can be added. This work also utilize the idea of creating graph with the vertices being each example and edges being conflicting examples pairs. They tried to approach the optimal 0/1 by removing minimum number of edges. Although they did not compute specific bounds on the optimal 0/1 loss, I think it is still worth being discussed.\n- This is a work with solid technical contribution. However, as mentioned in the limitation, the lack of implication on how to close the gap between the current robust classifiers and the optimal classifier limits the impact of this work to a moderate-to-high impact paper.\n- Although a method for speeding up the algorithm through truncating the graph is proposed, the applicability of the proposed algorithm in practice seems to be still limited in practice due to heavy computational cost (in the experiment, only three class classification problems are run).\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their insightful feedback and positive appraisal of our paper. We are glad they found it clear and easy to follow. We address their questions and concerns below:\n\n**Comparison to bounds for verified classifiers:** Thank you for the interesting prompt. We checked the available leaderboard (https://sokcertifiedrobustness.github.io/leaderboard/) on verifiably robust models for the settings we are concerned with ($\\ell_2$ robustness for the MNIST and CIFAR-10 datasets), and found:\n- For MNIST, the best certifiably robust model has a 0-1 loss of 0.27 at a budget of 1.52 and 0.44 at a budget of 2.0.\n- For CIFAR-10, the best certifiably robust model has a 0-1 loss of 0.6 at a budget of 1.0 and 0.8 at a budget of 2.0.\n\nThese are much higher than the optimal lower bound that is achievable for these datasets which is 0 in all these cases. We will add these numbers to the updated text in the paper for the value it provides in terms of providing a comparison to verifiably robust classifiers.\n\n**Related work on ‘Robustness for non-parametric classification’:** Many thanks for the pointer to this very interesting paper. Having gone through the paper, we find it to be quite relevant to our method for finding lower bounds. In particular, the construction of the graph in Section 3.1 matches that of our conflict graph. In addition, we have used a technique similar to the ‘adversarial pruning defense’ proposed in the paper to attempt to close the gap to optimal in Section D.9. of the Supplementary Material for neural networks, although we found little to no impact in the multi-class setting. Our technique was inspired by a similar one used in Bhagoji et al. (2021), which did find improvements in the two-class setting. We will update the related work to reflect the connection to this paper.\n\n**Potential measures to close the gap between optimal and current robust classifiers:** The main focus of our work is to provide a measure of progress for defenses by comparing them to the optimal loss. Regardless, we agree that it is interesting to consider measures to close the gap between optimal and current robust classifiers. In Section D.9. of the Appendix, we propose dropping hard data points to close this gap (inspired by Bhagoji et al. (2021)). However, we found limited to no improvement, pointing towards a need for a deeper exploration of the way in which the optimal loss construction can be used to close the gap. A few potential steps on the training side are increasing the architecture size and using additional unlabeled data. We could also potentially use the optimal classifier to overrule decisions in parts of the input space where trained neural networks are wrong, and the optimal classifier is fully specified. However, the input space coverage of the optimal classifier is low as it is only specified on points in the training data. Methods to improve this coverage would be an interesting direction for future work.\n\n**Results in the 10-class setting:** We would like to clarify that the paper does contain experiments beyond the 3-class setting. Section 4.2 of the paper has results and discussion for the 10-class case (See Figure 3). Due to computational limitations, we use a truncated version of the hypergraph containing up to degree-4 hyperedges. The Caro-Wei upper bound is also reasonably tight until $\\epsilon=3.0$, indicating that the use of higher-order hyperedges will not provide any additional information about the optimal loss. We provide an updated version of Figure 3 in the attached pdf that may be clearer. \n"}, {"review_id": "siIr9gAmrN", "reviewer": "Reviewer_QPxv", "summary": "This work proposes to theoretically evaluate the robustness of a multi-class classifier by setting the lower and upper bounds of the optimal loss, i,e, the lowest loss achievable for a given hypothesis family. The lower bound is established by extending the conflict graph-based framework previously applied to the binary classification setting. The upper bound is built by generalizing the Caro-Wei bound. Beyond theoretical analysis, this work also focuses on computable methods to estimate the bounds, i.e. using the lower bounds of binary classification problems to compute that for the multi-class problem. \n\n\n", "questions": "How tight are the upper and lower bound ?  Especially for the upper bound, this is established based the Caro-Wei bound, which is different from the conflict hypergraph framework. It is not clear how accurate the upper bound could be. ", "limitations": "None", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "It is an important contribution to set up an upper and lower bound for the lowest achievable classification loss under the testing-time perturbation. These two bounds help to narrow down the possible range of the classification loss facing input noise, which measures accurately the robustness of a classifier.  Furthermore, this work provides the link between the optimal loss bound of binary classification tasks and that for multi-class tasks. This contribution enables efficient computation of the bound estimates when the number of classes increases.", "weaknesses": "I have to admit that I am not familiar with this theory. It takes me quite some time to read the contexts before I can figure out how this framework can be integrated into the investigated problem. I think for any readers / reviewers without the background information, offering even a brief introduction could be very helpful to evaluate the contribution. \n\n\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive appraisal of our paper and comments to improve it further. We address their comments below:\n\n**Further details to evaluate the contribution:**\nOur contribution lies in both theoretical and experimental aspects of characterizing the optimal robust 0-1 loss for multi-class classification. This optimal loss is important to characterize so that progress in defenses can be measured. There is value in knowing how well the best possible classifier could perform in a given adversarial setting so we know how far our current defenses are.\n\nIn terms of a roadmap of our approach, we first provide an expression for the optimal loss and use Lemma 1 to connect the problem of finding the optimal loss with a linear program defined with respect to a graph of conflicts between data points from different classes (Section 2). Having established this connection, we then develop computationally more efficient methods to solve the conflict graph problem in practice (Section 3). We will elaborate upon our approach further in the beginnings of Sections 2 and 3.\n\nWe extend the approaches taken in previous work [1,2,3] that characterize the optimal loss in the case of binary classification, to the multi-class setting. Our use of the conflict graph is inspired by [1,2] which first introduced this concept, and our major contribution lies in extending it to the notion of conflict hypergraphs for multi-class classification.\n\n**Tightness of the bounds:**\nWe would like to clarify that the Caro-Wei upper bound uses the conflict graph to determine the size of the maximum independent set. However, the reviewer is correct to observe that this upper bound does differ from the form of the other bounds, which truncate the hypergraph to obtain a lower bound on the optimal loss. The tightness of the truncation based lower bounds as well as Caro-Wei upper bound depend directly on the structure of the conflict graph. In practice, we find that the bounds are tight when the perturbation budget epsilon is small. The gap between the bounds grows larger as we increase epsilon. An exact theoretical characterization of the gap is beyond the scope of this paper and we can add it to the limitations if the reviewer thinks that will add clarity.\n\n[1] A. N. Bhagoji, D. Cullina, and P. Mittal. Lower bounds on adversarial robustness from optimal transport. In Advances in Neural Information Processing Systems, pages 7496–7508, 2019.\n[2] A. N. Bhagoji, D. Cullina, V. Sehwag, and P. Mittal. Lower bounds on cross-entropy loss in the presence of test-time adversaries. In International Conference on Machine Learning, pp. 863-873. PMLR, 2021.\n[2] M. S. Pydi and V. Jog. Adversarial risk via optimal transport and optimal couplings. In Proceedings of the 37th International Conference on Machine Learning, pages 7814–7823, 2020.\n"}, {"review_id": "7Ld3osZghB", "reviewer": "Reviewer_yCc4", "summary": "Deep learning techniques achieve state-of-the art performance on various classification tasks, but alarmingly, they are highly susceptible to adversarial perturbations. It is currently unknown whether there even exist classifiers that achieve low adversarial training risk on standard datasets. This paper aims to close this gap. The authors restate the adversarial learning problem over all classifiers as a linear program which can then be solved using standard LP techniques. This LP is stated in terms of the hyperedges of a hypergraph. As the resulting LP is computationally intractable, the authors then propose several ways to truncate this LP. The paper concludes with an experimental section in which they use the paper's techniques to upper bound the minimal possible adversarial loss for MNIST and CIFAR-10.", "questions": "- Can you explain the issues with Lemma 1 pointed in in the first bullet under weaknesses? Resolving this issue would convince me to change the review score\n- Problems in optimal transport frequently need to solve linear programs in $\\mathbf q$  with the constraint $\\mathbf q\\geq 0$. For computational expediency, the sinkhorn algorithm uses entropic regularization to deal with this constraint. Could you possibly make use of this technique?\n- It seems that in the matrix inequality $Bq\\leq 1$ in Lemma 1, many rows may be linearly dependent. Have you tried getting rid of such rows?", "limitations": "One central limitation of this work is that it studies the minimal possible adversarial risk over all possible (soft) classifiers rather than a particular function class. \nThis limitation is discussed in the paper.", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 1, "contribution": 3, "strengths": "- It is currently unknown if finding robust classifiers to real-world datasets is possible. This paper presents a strong argument that such classifiers exist\n- Using linear programming to attack this problem is very creative!", "weaknesses": "- I have some concerns about the correctness of this paper. Here are some specific issues\n1. $q$ in line 20 of the supplementary material is not defined. This makes it quite hard to evaluate the correctness of the proof of Lemmas 1 and 2\n2. I suspect Lemma 1 is false. Lower bounds on the adversarial risk computed in this paper rely on this lemma, so if Lemma 1 is false, these bounds would be invalidated. \n\nConsider the following example: Consider 3 vertices with the incidence hypergraph of the left picture in Figure 1. Specifically, $\\mathcal N(u)= \\{u,v\\},\\mathcal N(v)=\\{v,w\\}, \\mathcal N(w)=\\{w,v\\}$.  Then the incidence matrix $B$ is\n|               |$u$|$v$|$w$|\n|------------|-----|----|----|\n|$e_{wu}$| 1   | 0   |1 |\n|$e_{uv}$|1    | 1    |0|\n|$e_{vw}$| 0    | 1   |1 |\n|$e_{u}$  |1     | 0  |0 |\n|$e_{v}$  |0     |0     |1 |\n|$e_{w}$ |0     |1     |0|\n\n\n\n\nConsider the vector $b= [0.5, 0.3, 0.2]$ (with vertices in order $u$, $v$, $w$). This vector clearly satisfies $b\\geq 0$ and $Bb \\leq \\mathbf 1$.\nWe will now show that this vector is not in $\\mathcal P_{\\mathcal V, N,\\mathcal H}$, as defined in line 96 of the paper.  For contradiction, assume that there is an $h$ for which $q_N(h)$ satisfies $0\\leq b_i\\leq q_N(h)_i$ for $i\\in \\{u,v,w\\}$. By definition, $q_N(h)_v=\\inf$ { $h(x): x\\in N(v)$}. \nThus $h(u)\\geq .5$ and $h(v)\\geq .5$. As $h$ is a probability vector, it follows that $h=(.5, .5, 0)$ and $q_N(h)=(.5,0,0)$. This is a contradiction as $h(v)\\leq b(v)=.3$. \n\n\n3. In definition 2, h is defined to be $\\cY$-valued but the expression $1-h(\\tilde x,c)_y$ assumes that this function is $\\mathbb R$ valued. As this definition is central to section 3, the correctness of this section is hard to evaluate\n- The paper does not introduce central mathematical concepts or introduces them poorly. For instance, \n1. line 82: \"architecture\" is discussed before neural nets are introduced\n2. what is 'downwards-closed' in line 110?\n3. The phrase \"correct probability vectors\" in Lemma 1 is misleading because the q's typically don't sum to 1\n4. What does 'fractional coverings' mean in line 119?\n5. lines 241-246: an argument is presented involving the fractional vertex packing polytope and the independent set polytope but these are only introduced very briefly", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their detailed engagement with our work and aim to address their concerns below, particularly those regarding the correctness of the main Lemmas in the paper.\n\nWe are confident that Lemma 1 is correct. We show below that your suggested counterexample vector is achieved by an explicit classifier. We also walk through the constructions used in the proof for this example to provide some intuition for the general argument.\n\n1. At line 20, $q$ is the vector that was introduced at line 15. It is an arbitrary point in $\\mathcal{P}\\_{m,V,N,\\mathcal{H}_{soft}}$, the correct-classification-probability vector region. We will better explain the high level structure of the proof.\n\n2. In your comment, you treated $h(u)$ and $h(v)$ as scalars, but they are in fact vectors in $\\mathbb{R}^3$ and probability mass functions over $\\mathcal{Y}$.\n  We have $q\\_N(h)\\_{(x,y)} = \\inf \\{ h(\\tilde{x})\\_y : \\tilde{x} \\in N(x) \\}$ rather than $q\\_N(h)\\_{(x,y)} = \\inf \\{ h(x) : \\tilde{x} \\in N(x) \\}$.\n  This confusion may be related to the typo discussed in point 3.\n\nFor the left example in Figure 1, $\\mathcal{P}\\_{V,N,\\mathcal{H}\\_{soft}}$ contains the vector $b = (0.5,0.3,0.2)^T$: it is $q\\_N(h)$ for the constant classifier $h(x) = b$.\nApplying the definitions, we have $q\\_N(h)\\_{(x,y)} = \\inf \\{ h(\\tilde{x})\\_y : \\tilde{x} \\in N(x) \\} = \\inf \\{b\\_y\\} = b\\_y$.\n\nWe can work out the whole structure of $\\mathcal{P}\\_{V,N,\\mathcal{H}\\_{soft}}$ by following the arguments in the proof of Lemma 2.\nLemma 1 states that contains the vectors $(q\\_u,q\\_v,q\\_w)$ that satisfy the inequalities $q\\_u \\geq 0$, $q\\_v \\geq 0$, $q\\_w \\geq 0$, $q\\_u + q\\_v \\leq 1$, $q\\_u + q\\_w \\leq 1$, and $q\\_v + q\\_w \\leq 1$.\nThe latter three inequalities come from the three edges in the conflict graph.\nWe will demonstrate the derivation of one of these as an example.\nBecause the edge $\\{u,v\\}$ is present, there is some $\\tilde{x} \\in N(u) \\cap N(v)$.\nLet $u$ be from class $0$ and $v$ be from class $1$.\nThus we get inequalities $q\\_N(h)\\_u \\leq h(\\tilde{x})\\_0$, $q\\_N(h)\\_v \\leq h(\\tilde{x})\\_1$, and $h(\\tilde{x})\\_0 + h(\\tilde{x})\\_1 \\leq 1$, which imply $q\\_N(h)\\_u + q\\_N(h)\\_w \\leq 1$.\n \nThe polytope described above has extreme points $(0,0,0)^T$, $(1,0,0)^T$, $(0,1,0)^T$, $(0,0,1)^T$, and $(1/2,1/2,1/2)^T$.\nThe middle three points are the correct-classification-probability vectors of the three constant hard classifiers.\nThe latter point is the correct-classification-probability vector of the classifier that assigns probability $\\frac{1}{2}$ to each of whichever two classes could have produced $\\tilde{x}$.\nThis is described at lines 150-152 of the paper.\nThis is not a constant classifier, which allows it to have better performance.\nWe can achieve intermediate correct-classification-probability vectors (or better) by averaging the outputs of soft classifiers achieving the extreme points.\n\nWe will attempt to make space to add the explicit descriptions of $\\mathcal{P}\\_{V,N,\\mathcal{H}}$ to Section 2.3.\n\n2. We have a typo at line 174. It should read $h: \\mathcal{X} \\times \\binom{\\mathcal{Y}}{m} \\to [0,1]^{\\mathcal{Y}}$, paralleling the definition at line 71. Thus $1 - h(\\tilde{x}, c)\\_y$ is a real number. We are sorry for the confusion that this caused.\n\nMore:\n\n1. We mean a function class in which each function is specified by a finite number of parameters. This encompasses neural networks but is more general. We will expand this discussion to improve the clarity.\n2. The hyperedge set being downward closed means that if $e \\in \\mathcal{E}$ and $e' \\subseteq e$, then $e' \\in \\mathcal{E}$. This follows from $\\cap_{(x,y) \\in e} N(x) \\subseteq \\cap{(x,y) \\in e'} N(x)$, i.e. the same witness of the hyperedge e also witnesses e'.\n3. The phrase should be read as correct-classification-probability vectors, because an entry of the vector is a correct classification probability. These are conditional probabilities (the entry $q_{N}(h)_v$ is the probability that the randomized classifier with distribution $h$ is correct given that the natural example is $v$), so as you point out, they do not sum to one in general. We can use this hyphenation.\n4. A fractional covering is a standard concept from graph and hypergraph theory: it is a nonnegative weighting $z$ of the hyperedges such that each vertex receives coverage at least its weight. I.e. the sum of the weights of the hyperedges containing $v$ is at least the weight of $v$: $B^Tz \\geq p$. We will add a textbook reference.\n5. The discussion is brief due to space constraints. We will add a citation to make it clear that these are standard facts in combinatorial optimization and not new claims.\n\nQuestions:\n\n* This point about entropic regularization connects to several other papers as well as directions for further research.\nIf the inequality $q \\geq 0$ is replaced with a cross-entropy regularization term $\\sum_i p_i \\log \\frac{1}{q_q}$, which is infinite at the boundaries $q_i = 0$, the resulting problem is related to the optimal adversarial cross entropy loss.\nIn Bhagoji et al. 2021, this is investigated for the two class setting.\nThey compute the optimal cross-entropy loss by solving a sequence of 0-1 loss optimization problems.\nThe dual problem of optimizing over adversarial strategies is more connected to optimal transport.\nTrillos et al. have multiple characterizations of the optimal loss in the multiclass setting terms of various optimal transport problems and use established entropy regularized solving methods to compute optimal losses.\nThere are more possible ways to apply entropy regularization and we think that this is a fruitful direction for further investigation.\n\n* We do eliminate redundant constraints when possible, but it is not as simple as checking for linear dependence.\nBecause $Bq \\leq 1$ is an inequality, a row of $B$ can only be eliminated when it is a nonnegative linear combination of other rows and rows of $-I$ (which comes from the other constraint $-Iq \\leq 0$)."}, {"review_id": "0tSfbCHUar", "reviewer": "Reviewer_Q9vC", "summary": "The paper generalizes lower bounds on the adversarially robust error on a finite dataset from binary to multi-class classification.", "questions": "1. While Equation (1) is true, I think it is not trivial, but a theorem that depends on some assumptions (which appear to be fulfilled by the considered hypothesis classes). It was proven in (Pydi,Jog 2022: \"The Many Faces of Adversarial Risk\")[https://arxiv.org/abs/2201.08956], but there might be earlier, more well known versions of the theorem. I think the intuition why (1) is true should be given.\n2. l. 89 I think it should better read \"the vector of _robustly_ correct classification\"\n3. l. 97 Should \"feasible\" read \"achievable\" here to stay consistent?\n4. l. 97 Do the nonnegative linear combinations need to have factors that sum to less than 1?\n5. Is L without * correct in Eq. (2)? If so, it wasn't defined.\n6. l. 122 missing word\n7. l. 124 extra (\n8. Is the construction of the full hypergraph indeed computationally expensive for an l2 threat model? Intutitively, the geometry might make incidence matrix very sparse and its computation quite straightforward. Or is it rather an issue with the LP solver?\n9. Would it make sense to regard the reverse truncation where if we find a triple of pairs with overlap (as in Fig. 1 left), we assume that there is also a point that generates the degree 3 hyperedge (and so on for higher degrees)? this might maybe yield an upper bound on $L^*(K)$.\n10. l. 296 whether and in which sense the hypothesis class is much smaller is not obvious, and it is not clear if insufficient fitting within the class might be responsible for a large part of the gap.\n11. In Figure 3, an empirical model evaluation as in Figure 2 should be included. ($L_{CW}$ is a bit confusing at first look, since many papers use that for Carlini-Wagner l2 attacks.)\n12. Why not use the full AutoAttack?\n13. The statistics on number of hyperedges should be included for all datasets, and a few values of epsilon (including 2 and 2.5), since they quantify the importance of regarding multi-class overlaps.\n14. Also statistics like the average distance of an image to the closest one from another class would be nice to understand the geometry of the neighborhood overlaps.\n15. It would be great if the authors could find a type of dataset and threat model where multi-class neighborhood overlap plays a bigger role than with MNIST and CIFAR. Maybe even a toy example would be illustrative.\n16. Since the paper talks about optimal errors for finite distributions, it would make sense to show evaluations both on training and test sets.\n17. A more concrete comparison to Trillos et al.[21], if applicable with evaluation numbers, would be helpful.\n18. A discussion of the limitation to distributions with finite support and whether one can expect this assumption to be softened in future works building on this one would be interesting.", "limitations": "The limitations are discussed in detail.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. The paper is well presented and easy to read, which is no mean feat for the amount of theory that is introduced and developed.\n2. The formalization and assumptions are clearly stated, well arranged, and do not contain unnecessary complications.\n3. The developed theory is correct as far as I can tell.\n4. The experimental evaluations make sense for the discussed topic, regard standard baselines and are easy to understand. They are shown even while they don't support the necessity of the multi-class theory, which is nice to see.\n5. The fact that calculating the bounds based on binary l2-ball intersections makes no difference in practice doesn't mean that the theory is not helpful for estimations that are in principle more correct.\n6. Limitations are discussed honestly.\n7. The code looks nice, but I haven't tested it.", "weaknesses": "1. While they are no clear weaknesses, there are some points unclear to me which I list below in the Questions section and I would much appreciate to see answered and in some cases discussed in the paper.\n2. A substantial part of the formalization, theory and experimental design are not completely newly developed, but carried over from the previous paper \"Lower Bounds on Cross-Entropy Loss in the Presence of Test-time Adversaries\" which deals with the same problem in the more special case of binary classification. This is why I'm rating this submission currently as a standard \"accept\".", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful feedback.  We are encouraged that you find our presentation clear and experiments interesting.  We address your questions below:\n1) This is a good observation.  The technical issue with equation (1) is that for a particular $h$, the function $(x,y) \\mapsto \\sup_{\\tilde{x} \\in N(x)} \\ell(h, (\\tilde{x},y))$ may not be a measurable so the expectation may not be defined.  In this case, our hypothesis class does not help us, but our assumption that the data distribution has finite support ensures that the adversarial risk is well defined.\nOne reason that we work only with finite-support probability distributions is to side-step these technical issues while still handling what we believe to be an interesting example of the problem.  Effectively we are placing the power-set sigma algebra on our space $\\mathcal{X}$: every set and function becomes measurable at the cost of reducing the number of measures available.  This lets us avoid technical assumptions about the space $\\mathcal{X}$ and the neighborhoods $N(x)$.\nPydi and Jog provide some conditions to ensure that adversarial risk is well-defined, one of which is taking $\\mathcal{X} = \\mathbb{R}^d$ and working with Lebesgue measurable functions.  While we stated the theory portions of the paper in a more abstract setting, all of our experiments fit into that case.\nWe should move our assumption that the data distribution is discrete from Section 2.2 up to 2.1 to justify equation (1).  We will also add a citation of Pydi Jog 2022 with a comment about the technical complexities that can arise in a more general setting.\n\n2, 3, 5, 6, 7) We will update the paper to fix these typos.\n\n4) When we optimize over the correct classification polytope, the weights are the example probabilities so they do sum to one. However, even if the weights did not sum to one, extending the region to include the origin would not affect the result of the optimization. \n\n8, 13) Sparsity helps since we do not need to search all $\\binom{n}{3}$ vertices for 3-way hyperedges, but even with sparsity, it is still expensive to find all hyperedges due to many triangles within the graph.  Solving the LP is also expensive at large $\\epsilon$ due to the large number of constraints (we are generally bottlenecked by the LP solver inefficiency before being unable to compute hyperedges).  In Appendix Figure 5, we plot the number of edges, degree 3 hyperedges, and degree 4 hyperedges across $\\epsilon$ for MNIST and CIFAR-10.  We find that the number of edges/hyperedges grows exponentially with the number of hyperedges increasing at a faster rate than edges.\n\n9) This is a good suggestion and would lead to another upper bound on the optimal loss ($L^*(K)$).  The polytope that results from this process is the fractional independent set polytope of the conflict graph, which has a constraint for each clique.  Optimizing over this polytope gives the fractional independence number of the conflict graph.  In general, this polytope cannot always be computed quickly: there could be $\\Omega(n^K)$ maximal cliques.\nHowever, we could probably compute the fractional independence number in many of the cases we experiment with, and are willing to add it to the updated version if the reviewer thinks it would be interesting.\n\n10) Thank you for pointing this out, the gap may be due to optimization or due to the hypothesis class.  We will update the wording in this section to reflect this.\n\n11) Thank you for the suggestion, we have updated Figure 3 to also include a line for PGD-AT performance as in Figure 2.  Please see our updated plot in the rebuttal pdf (Figure 1).  We have also shaded the region between the $L_{CW}$ and $L^*(2)$ lines to indicate the space where the true value of the optimal loss lies and make it more clear that $L_{CW}$ is an upper bound on optimal loss.\n\n12) The second attack of the AA suite (APGD-T) uses targeted DLR loss which assumes at least 4 classes and cannot be used for 3 class experiments.  Additionally, we find that there is small change in robust accuracy when including all attacks so we choose to use APGD-CE in our experiments to reduce computation time.\n\n14) Thank you for the suggestion.  We provide these statistics for each class in MNIST and CIFAR-10 in Table 1 of the rebuttal pdf.  We will add this into the Appendix.\n\n15) Currently, it is unclear for what data distribution and threat models the multi-class overlap would play a bigger role.  In the Appendix, we present results for Gaussian data, but we observe similar trends as with MNIST and CIFAR-10 in this case.\n\n16) Thank you for the suggestion, we provide some comparisons between evaluations on the training set and evaluations on the test set for MNIST classes 1, 4, and 7 in Table 3 of the rebuttal pdf.  We observe that the optimal loss computed on the test set is close to the optimal loss computed on a sample of the training set of the same size as the test set.  We will add this table to the Appendix of our paper.\n\n17) The code used by Trillos et al. is unavailable and details about experimental setup are missing so it is difficult to compare.  Looking at the plot in Figure 6 of their paper, it seems they compute a loss lower bound of ~0.05 for MNIST classes 1, 4, 6, and 9 at $\\ell_2$ budget of 800/255.  Computing $L^*(2)$ across the entire MNIST training set in this setting, we obtain $L^*(2)=0.21$.  We believe that Trillos et al. likely provide results on a subset of the dataset causing this discrepancy.\n\n18) Thank you for this suggestion, we will add a discussion of this into the paper. We note that the optimal transport formulation proposed by Trillos et al. allows for general distributions, and focuses on transforming the problem to one where known methods exist to enable efficient bound computation. While our results are restricted to finite support, we are focused more on computing bounds on natural datasets efficiently by transforming the conflict graph directly.\n"}]

Author rebuttal:
We thank the reviewers for their thoughtful and constructive engagement with the paper. As reviewers ourselves, we greatly appreciate the reviewers’ efforts at providing thorough and insightful commentary on the paper. We have addressed all the reviewer’s concerns in the respective rebuttals, including providing Reviewer **yCc4** with a detailed explanation for why we strongly believe that Lemmas 1 and 2 are correct along with a refutation of the constructed counter-example.

We are glad that multiple reviewers found our theoretical contributions important (**baps**, **Qpxv**), approach creative (**yCc4**), and experiments interesting with easy to understand baselines (**Q9vC**).  We are also happy that multiple reviewers found the presentation to be clear and easy to follow (**baps**, **Q9vC**), appreciated our proposed techniques for making the problem more computationally efficient (**baps**, **Qpxv**), and appreciated our code and honest discussion of limitations (**Q9vC**).

In the attached pdf, we provide
1. An updated version of Figure 3 in the paper with losses from adversarial training (**Q9vC**) and shading to indicate the space between the upper bound ($L_{CW}$) and tightest lower bound where the optimal loss $L^*(10)$ would lie (**baps**, **Q9vC**)
2. A table of statistics for the average distance of examples to their nearest neighbor in another class for each class in MNIST and CIFAR-10 (**Q9vC**)
3. A table of optimal losses computed on the MNIST train set and MNIST test set (**Q9vC**)
We plan on incorporating both tables into the Appendix of our paper.

In light of suggestions for improvement suggested by the reviewers and in addition to the clarifications already provided in the rebuttals, we also commit to making the following changes to the camera-ready version of the paper:
1. Improvements to the clarity of the text:
    - Add an overview of our approach in Sections 2 and 3 (**QPxv**)
    - Add citations for graph theory concepts such as fractional coverings, fractional vertex packing polytope, and the independent set polytope (**yCc4**)
    - Fix typos pointed out by reviewers (**yCc4**, **Q9vC**)
2. Add discussion of the following papers:
    - Yang et al. 2020: “Robustness for non-parametric classification” (**baps**)
    - Pydi, Jog 2022: "The Many Faces of Adversarial Risk" (**Q9vC**)
3. A comparison to bounds for verified classifiers (**baps**)
4. Discussion of limitation to distributions with finite support (**Q9vC**)


Meta-review: ## Summary:

This theoretical paper studies the multi-class classification robustness. The authors prove upper and lower bounds of the lowest possible loss for a hypothesis class. The main results generalize lower bounds on the adversarially robust error on a finite dataset from binary to multi-class classification, which is an important problem in robustness. On the technical side, the authors use a link between robust error and certain graph theoretic concepts (e.g., the conflict hypergraph), which allows them to analysis the multi-class setting. Then, the authors can study the optimal loss using linear programming and a generalization of the Caro-Wei bound. 

The reviewers found the contributions to be impactful, novel, and well-motivated. Along the way, the authors also study a computational approach to compute the optimal 0/1 loss. The reviewers also appreciated this result, as well as the empirical results that were possible because of it. In particular, it leads to new insights around adversarial training, which is one of the standard robust training algorithms in practice. The authors do experiments on 3- and 10-class problems to verify the theory in practice.

The authors and reviewers had a fruitful discussion. The authors did a great job quickly addressing many comments and incorporating them into the revision. For example, there were many comments raised around the exposition of the theoretical results, including increasing the self-contained nature of the paper by including definitions and adding more references.

Overall, after the author-reviewer discussions, all the reviewers speak highly of the paper and the impact of the results.

## Further improvements:

It would be good to continue improving the final version of the paper by including (either in the main paper or appendix) all of the necessary background. For example, there seem to be no theorems presented by the authors (only Lemmas and Corollaries). For a theoretical paper, it is usually good to present a main theorem or two, which are the key results for the readers to focus on.

The reviewers had a hard time full verifying the correctness of the paper, but they believe the results to be true and follow from the techniques in the paper. In particular, some concerns around the correctness of some lemmas were clarified during the author-reviewer discussion. On the other hand, the proofs in the appendix do seem somewhat terse, with many claims about graphs and probabilities that are stated with minimal justification. Given that there is no page limit for the appendix, it would be good to expand on the proofs of the lemma in Appendix A+B.
Decision: Accept (spotlight)