Lower Bounds on Cross-Entropy Loss in the Presence of Test-time Adversaries

Arjun Nitin Bhagoji * 1 Daniel Cullina * 2 Vikash Sehwag 3 Prateek Mittal 3

Abstract
Understanding the fundamental limits of robust
supervised learning has emerged as a problem of
immense interest, from both practical and theoretical standpoints. In particular, it is critical todetermine classifier-agnostic bounds on the training loss to establish when learning is possible. In
this paper, we determine optimal lower bounds onthe cross-entropy loss in the presence of test-timeadversaries, along with the corresponding optimal classification outputs. Our formulation of thebound as a solution to an optimization problem
is general enough to encompass any loss function depending on soft classifier outputs. We also
propose and provide a proof of correctness for a
bespoke algorithm to compute this lower boundefficiently, allowing us to determine lower bounds
for multiple practical datasets of interest. We use
our lower bounds as a diagnostic tool to determine the effectiveness of current robust training
methods and find a gap from optimality at larger
budgets. Finally, we investigate the possibilityof using of optimal classification outputs as softlabels to empirically improve robust training.

1. Introduction
The robustness of machine learning systems, particularlyclassifiers in the supervised setting, to adversarial perturbations (Szegedy et al., 2013; Goodfellow et al., 2015; Carlini & Wagner, 2017; Bhagoji et al., 2018; Madry et al.,2018) has become an important line of research owing to
the critical role they play in society. While there is a tremendous amount of work on attacks and defenses (Papernot
et al., 2016), a focus of recent research (Bhagoji et al., 2019;
Dohmatob, 2019; Schmidt et al., 2018; Cullina et al., 2018;
Mahloujifar et al., 2019; Diochnos et al., 2018) has been*
Equal contribution 1 Department of Computer Science, University of Chicago 2 Department of Electrical and Computer Engineering, Pennsylvania State University 3 Department of ElectricalEngineering, Princeton University. Correspondence to: Arjun
Nitin Bhagoji <abhagoji@uchicago.edu>.

Proceedings of the 38 th International Conference on Machine
Learning, PMLR 139, 2021. Copyright 2021 by the author(s).

on establishing fundamental bounds on learning in the presence of test-time adversaries in various settings. One line ofresearch (Bhagoji et al., 2019; Dohmatob, 2019; Pydi & Jog,
2020) into the limits of learning in the presence of test-timeattackers has established classifier-agnostic lower bounds
on adversarial robustness, i.e. the minimum 0 − 1 loss
that would be incurred by any classifier, when adversarial
perturbations are added to the underlying data distribution.
However, practical approaches to training classifiers such asneural networks usually use surrogate loss functions such as
the cross-entropy loss that depend on the output confidence,and it is critical to establish bounds on these.
Thus, in this paper, we extend work on the informationtheoretic limits of learning in the presence of test-time adversaries to any loss function that uses the output probabilities of a classifier, such as the cross-entropy loss. The key
question this paper answers is:
What is the minimum possible cross-entropy loss that will
be incurred by any classifier given a data distribution andadversary specification?
Answering this question enables us to quantitatively diagnose the effectiveness of practical defenses against adversarial examples (Madry et al., 2018; Zhang et al., 2019),
and can inform the design of better learning algorithms. In
particular, we can determine if current robust optimization
techniques are able to recover these bounds as well as findregimes in which robust classification is not possible. A
further goal is to investigate the findings from Bhagoji et al.
(2019) which indicated a large gap between the theoreticallydetermined lower bound for the 0 − 1 loss and what wasachievable in practice from robust training. We seek to determine if the gap arises solely from the use of a surrogate
loss during training or if there is a more fundamental barrier
to robustness.
To determine classifier-agnostic lower bounds on the crossentropy loss, we focus on the interaction between data points
when they are perturbed. We represent points from eachclass as the vertices of a graph, with edges existing between two vertices if the neighborhoods in which they canbe perturbed overlap. We refer to this structure as a conflict graph (first implicitly defined by Bhagoji et al. (2019)).
Data points connected by edges are then challenging to classify, even for the optimal classifier. The problem is thenLower Bounds on Cross-entropy Loss in the Presence of Test-time Adversaries

translated to one of finding the output probabilities of the
optimal classifier over this graph. Minimizing the crossentropy loss over this graph determines these probabilities
and provides a lower bound, which can be efficiently computed as the resulting optimization problem is convex. Thisquantity, known as the graph entropy (Körner, 1973), has
independently appeared in information theory as the solution to a coding problem. We also determine an exact form
for the lower bound on cross-entropy for a mixture of two
Gaussians, along with the optimal classifer and adversarial
strategy.
An efficient determination of these lower bounds is possible
since the optimization problem is convex, but we find thatexisting solvers are prohibitively slow for the programs
resulting from real-world distributions of interest. In light of
this, we derive a custom algorithm that exploits the bipartite
structure of the conflict graph and can determine bounds
far faster than a generic convex solver for instantiationsof interest. Our algorithm can find a solution in 10s of
seconds for benchmark datasets such as MNIST (LeCun& Cortes, 1998), Fashion MNIST (Xiao et al., 2017) and
CIFAR-10 (Krizhevsky & Hinton, 2009). We provide a
proof of correctness and convergence for our algorithm.
We use our algorithm to find lower bounds on the crossentropy loss for these benchmark datasets, as well as forsynthetic Gaussian data. Comparing these bounds to thetraining loss obtained by state-of-the-art robust optimization
techniques on commonly used deep neural networks, wefind a gap in terms of convergence to the optimal loss. Interestingly, the gap is much larger for the 0 − 1 loss than for the
cross-entropy loss, indicating that the use of a surrogate loss
does impact achievability but is not the sole reason for it. We
examine the impact of model architectures and activation
functions on this gap, finding that the former aids convergence while the latter has a negligible impact. Finally, forcertain adversarial budgets, we find that the use of soft labels
obtained from our framework during training can aid withboth convergence and generalization. The code to reproduce
all results in this paper is available at https://github.
com/arjunbhagoji/log-loss-lower-bounds.
1.1. Summary of Contributions
General framework for lower bounds for all convex
losses using output probabilities in the presence of testtime adversaries: Our problem formulation allows us todetermine lower bounds on any loss function for a given
dataset and adversary. In particular, we can compute lower
bounds on the commonly used cross-entropy loss as well as
the the optimal classification probabilities for all points.

interest, our algorithm provides a speedup of multiple ordersof magnitude over a generic convex solver from CVXOPT(Andersen et al., 2013).
Analyzing the effectiveness of current robust training
methods: Our framework enables us to determine regimes
where robust classification is possible. In these regimes, wefind that current robust training techniques are able to getclose to, but not match, the lower bounds on cross-entropy
loss. This gap is smaller than that for the 0 − 1 loss observedin previous work, showing the impact of using surrogate
losses. We also investigate the use of the optimal classification probabilities computed by our framework as soft-labels
during training, and find that these aid in both convergenceand generalization for certain adversarial budgets.

2. Lower Bounds on Cross-Entropy Loss
In this section, we derive lower bounds on the cross-entropy
loss in the presence of a test-time attacker by demonstratingthat it is the solution to a convex optimization problem. We
show how this problem can be derived using a graphicalinterpretation of the classification problem. Our method
applies to all discrete two-class distributions as well as all
adversaries perturbing points within a non-empty neighborhood. We also extend our framework to the special case ofa mixture of two Gaussians.
2.1. Problem formulation
We consider the following supervised classification problem.
Data points x are drawn from a space X , with labels y ∈Y = {−1, 1}. The joint probability distribution over thisdata is P 1 . The classification function (or classifier) f :X → Y maps data points to the space of labels. We also
define a ‘soft’ classifier h : X → [0, 1]Y that maps data
points to a metric of their confidence of being in a class.
The index of the maximum element of h recovers f . Thisapproach is followed in classification algorithms such as
logistic regression and neural networks (Shalev-Shwartz &Ben-David, 2014).
Test-time adversary: We consider a test-time adversarythat can modify any data point to generate an adversarial
example (Goodfellow et al., 2015; Szegedy et al., 2013;
Carlini & Wagner, 2017) within a neighborhood, i.e. x̃ =N (x), where x̃ is the adversarial example and N (·) is a
non-empty neighborhood function. This general definition
includes the `p family of constraints most widely used inprevious work.
Loss functions and robust training: To obtain a classifier
1

Efficient determination of optimal log-loss: We propose
a bespoke algorithm to compute these lower bounds andprovide a proof of its correctness. For practical settings of

We note that some formalizations of the test-time adversary
problem assume that the labels are determined by a ground-truthclassifier.

Lower Bounds on Cross-entropy Loss in the Presence of Test-time Adversaries

robust to test-time adversaries, f musthbe trained to minii
mize the robust 0 − 1 loss, defined as E `˜0−1 (f, (x, y)) =hi
E supx̃∈N (x) 1 (f (x̃) 6= y) . However, since the 0 − 1loss is non-differentiable, surrogate losses that are differentiable and upper bound it are used in practice. One of
the most common is the cross-entropy or log loss, definedas `CE (h, v) = − log h(x)y for a 2-class problem, wherev = (x, y) and h(x) ∈ [0, 1]Y is the probability distribution
over Y that the soft classifier h assigns to x. The robust
classification problem using a surrogate loss ` is then"inf EPh#CE

sup ` (h, (x̃, y))x̃∈N (x)h= inf EP `˜CE (h, (x, y))
h

i

(1)

a classifier. The feasible set of such probabilities isq≥0
M q ≤ 1.

(2)

 
E
∈ R(EtV)×V and E ∈ RE×V is the edgeI
incidence matrix of the conflict graph.
where M =Proof. Suppose that (u, v) ∈ E. Then, there is some x̃ ∈N (u) ∩ N (v). We have qu ≤ h(x̃)1 , qv ≤ h(x̃)−1 , andh(x̃)1 + h(x̃)−1 = 1. Combining these gives the constraintin (2) indexed by (u, v).
Now, we will show that each vector q in the polytope isachievable by some h. Let h(x̃)1 = supu:x̃∈N (u) qu andh(x̃)−1 = 1 − h(x̃)1 . Then,inf x̃∈N (u) h(x̃)1 =inf x̃∈N (u) qu = quProblem Statement: Our aim is to determine the value ofinf h EP [`˜CE (h, (x, y))] over all measurable functions h, fora given discrete, two class distribution P and neighborhood
function N (·).

The output when the true example is v is
inf x̃∈N (v) h(x̃)−1 = inf x̃∈N (v) (1 − supu:x̃∈N (u) qu ) =inf u:∃x̃∈N (u)∩N (v) (1 − qu ) ≥ qv .

2.2. Lower bound as the solution to a convex program
We first define a conflict graph in order to cast the problemof finding the lower bound as an optimization problem overthe vertices of this graph. Then, we show that the feasible setof output probabilities is determined by the edge incidence
matrix of the conflict graph. Finally, we determine the lower
bound on the cross-entropy loss by minimizing over thisfeasible set.
Conflict graph: We define a conflict graph G = (V, E) that
accounts for intersections between the neighborhoods ofpoints from different classes. Each neighborhood represents
the set of points reachable by the adversary from point x. LetV ⊆ X ×Y be the support of the distribution P . This meansthat each labeled data point (x, y) with strictly positive
probability in P is represented as a vertex v. Since weconsider a binary classification problem, the conflict graphis bipartite. Each part of the graph is Vc = V ∩ (X × {c}),where c ∈ {−1, 1}. The edge ((x, 1), (x0 , −1)) is present
if and only if N ((x, 1)) ∩ N ((x0 , −1)) is nonempty. There
are no edges between vertices in the same part of the graph.
Definition 1. For a soft classifier h, the correctclassification probability qv that it can achieve on an example v = (x, y) in the presence of an adversary is
qv =

inf
x̃∈N (x)h(x̃)y .

Lemma 1 (Feasible output probabilities). Let q ∈ RV be
the vector of correct-classification probabilities obtained byinf x̃∈N (u) supu0 :x̃∈N (u0 ) qu0≥

The robust cross-entropy loss is of particular interest in therobust training of neural networks (Madry et al., 2018).

In the non-adversarial case, all constraints in (2) are of
the forms qv ≤ 1 and q(x,1) + q(x,−1) ≤ 1. Non-trivial
adversaries lead to constraints between the probabilities
achieved for distinct examples.
Having determined the feasible set of output probabilities,
we can now determine the minimum possible cross-entropy
loss by minimizing it over this feasible set.
Theorem 1 (Lower bound on cross-entropy loss). The discrete joint probability distribution P over data from twoclasses, and the neighborhood function N (·) define a bipartite conflict graph G with incidence matrix E. Let p ∈ RV
with pv = P ({v}). Let q ∗ be the minimizer of the following
program:Xmin−pv log qv
qv:pv >0s.t. q ≥ 0(3)

M q ≤ 1.
Then, there is a classifier h∗ that achieves thecorrect-classification probabilities q ∗ and for all h,
EP [`˜CE (h∗ , v)] ≤ EP [`˜CE (h, v)].
Proof. From Lemma 1, we know that the constraints inEq.(2) represent the feasible set of all possible q. Further,
there exists some h that achieves each q. The objective function must have a minimum in the feasible set. Additionally,
the objective is convex and the constraints are linear, leading
to a convex program.

Lower Bounds on Cross-entropy Loss in the Presence of Test-time Adversaries

We note that a modification of the program above can beused to derive the minimum
P 0 − 1 loss for discrete distributions by setting minq v p| q as the objective function.
This partially recovers results from Bhagoji et al. (2019),
although that work considers a more general class of distributions including continuous distributions.

Our first lemma proves that the optimal classifier is linear
and the corresponding optimal adversarial strategy z ∗ 2 isjust a translation of each component of the mixture. To show
this, we just establish that these are identical to the solutions
obtained in the 0 − 1 loss case, allowing us to use Lemma 1
from (Bhagoji et al., 2019).

Lemma 2 (Properties of an optimal q). Suppose we have q
and z such that

Lemma 3. The optimal classifier h∗y minimizing the cross1∗
entropy loss is given by 1+exp (y(w=∗ )| x) where w
2Σ−1 (µ − z ∗ ), and z ∗ is the optimal adversarial strategy
given by Lemma 1 of (Bhagoji et al., 2019).

q≥0

(4)

Mq ≤ 1

(5)

z≥0

(6)

diag(q)M > z ≥ p(7)

1> z ≤ 1> p.

(8)

The cross-entropy lower bound can then be directly computed.
Theorem 2. The cross-entropy lower bound for a mixtureof two Gaussians is
inf EP [`˜CE (h, v)]

Then, q is optimal in (3).

h= p1 EN (µ−z∗ ,Σ) [log(1 + exp ((w∗ )| x))]
Proof. From (7) we have 1> p ≤ q > M > z and from the(5) we have z > M q ≤ z > 1. Then (8) implies 1> z =1> p = q > M > z. Furthermore pv = (diag(q)M > z)v =qv (M > z)v .
There is always some feasible q that makes the objectivefunction finite, so qv∗ = 0 implies pv = 0. For qv∗ > 0, theupper bound on log qv from the linear approximation at qv∗
q −q ∗
is vq∗ v + log qv∗ . Thusv

Xqv − qv∗
∗
+
log
q
v
qv∗
v:pv >0
X pv
X=
q v − 1> p +pv log qv∗ .
∗qv:p >0 v
v:p >0

pv log qv ≤v:pv >0

X



pv

v

P

(9)

+ p−1 EN (µ+z∗ ,Σ) [log(1 + exp (−(w∗ )| x))]We defer the proofs to Section A of the Supplementary.

3. Efficiently Computing Lower Bounds
In this section, we show that the convex program defined
above can be efficiently solved by lower bounding its objective with a linear function and solving a recursive series oflinear programs. We develop a specialized algorithm insteadof using an off-the-shelf convex program solver in order toexploit the structure in the problem for faster computation.
3.1. Algorithm overviewv∗
v −pv log qv for all q, we>P

To provev −pv log qv ≥Pneed v pq∗v qv ≤ 1> p. To show this, we note that z M q ≤v
z > 1 and 1> z ≤ 1> p. Then, we only need that (z > M )v ≥pv>
q ∗ , which follows from diag(q)M z = p.
v

The vector z in Lemma 2 can be interpreted as the optimal
strategy followed by the adversary.
2.3. Gaussian Case
We now consider the case when the data is generated froma mixture of two Gaussians with identical covariances andmeans that differ in their sign. Formally, we have P =p1 N (µ, Σ) + p−1 N (−µ, Σ), where p1 , p−1 ∈ [0, 1] andp1 + p−1 = 1. X is then Rd . We set the neighborhood
function N (x) = x + ∆, where  is the adversarial budgetand ∆ ∈ Rd is a closed, convex, absorbing and originsymmetric set.

Our algorithm (OptProb) executes the following strategy. It
starts by guessing that there is a single correct-classification
probability that should be assigned to all vertices from class
1 and a single probability for vertices from class −1. If thiswere the case, those probabilities should reflect the relative
frequencies of the classes. The algorithm solves a linear
program and either finds a dual certificate proving that theinitial guess is correct or a partition of the vertices basedon whether the optimal correct-classification probabilities
are larger or smaller than the guess. In the latter case, thealgorithm is applied recursively to the two subproblems andtheir solutions are assembled into a solution to the original
problem. A precise description appears as Algorithm 1.
The computation of OptProb uses the function LinOpt
at each stage of the recursion.
The function
LinOpt(A, B, E, P ) solves a dual pair of linear programswith variables y ∈ RA∪B and z ∈ R(A×B)∪A∪B :2
We note that there is a slight abuse of notation here since z in
the previous section is a probability and is a perturbation here.

Lower Bounds on Cross-entropy Loss in the Presence of Test-time Adversaries

Algorithm 1 OptProb
Input: Bipartite graph (A, B, E), vertex weights P
Output: Classifier probabilities q, adversarial strategy z
1: (A+ , A− , B + , B − , z lin ) = LinOpt(A, B, E, P )2: if P (A+ )P (B + ) > P (A− )P (B − ) then3:
E 0 = E ∩ (A+ × B − )4:
E 00 = E ∩ (A− × B + )5:(q 0 , z 0 ) = OptProb(A+ , B − , E 0 , P )6:(q 00 , z 00 ) =(OptProb(A− , B + , E 00 , P )qv0 v ∈ A+ ∪ B −7:
q = v 7→
q 00 v ∈ A− ∪ B +
v
0
+
−
+
−

ze e ∈ (A × B ) ∪ A ∪ B
8:z = e 7→ ze00 e ∈ (A− × B + ) ∪ A− ∪ B +0otherwise
9: else(P (A)/P (A ∪ B) v ∈ A
10:
q = v 7→
P (B)/P (A ∪ B) v ∈ B
lin
11:
z=z
12: return (q, z)

max r> ymin 1> zslackness arguments for linear programs.
Lemma 4. The function LinOpt(A, B, E, P ) produces(A+ , A− , B + , B − , z) with the following properties.
1. P (A+ )P (B + ) ≥ P (A− )P (B − )2. If P (A+ )P (B + ) = P (A− )P (B − ), then(a) 1> z = P (A ∪ B),(A)(b) P P(A∪B)(M > z)v = P ({v}) for all v ∈ A,
(B)
(M > z)v = P ({v}) for all v ∈ B.
(c) P P(A∪B)

Lemma 5 establishes that OptProb terminates and describes
the structure of the optimal (q, z) in detail. Both vertex sets
are split in partitions with paired parts and each pair ofparts behaves similarly to a complete bipartite graph. Edges
between pairs of parts are restricted by an order relation.
Lemma 5. If P (A ∪ B) > 0, the computation of
OptProb(A, B, E, P ) terminates and produces a pair (q, z).
For some [k] = {0, 1, . . . , k − 1}, there are functions
a : A → [k] and b : B → [k] with the following properties.

z≥0

y≥0
>

My ≤ 1M z≥r
A∪B
where r ∈ R
is defined as follows. If both P (A) > 0
and P (B) > 0, then(P ({v})P (A ∪ B)/P (A) v ∈ A
rv =P ({v})P (A ∪ B)/P (B) v ∈ B
and otherwise rv = P ({v}).
The primal polytope is the vertex packing polytope of the
bipartite graph (A, B, E). This is integral, so there is some
optimal y ∈ {0, 1}A∪B . The sets A+ , A− , B + , B − encode
the support of y in a way that is convenient for expressing
OptProb: A+ = {v ∈ A : yv = 1}, A− = A \ A+ ,B + = {v ∈ B : yv = 1}, and B − = B \ B + . The supportof y is an independent set: (A+ × B + ) ∩ E = ∅.
3.2. Proof sketch for algorithm optimality
Theorem 3 (Convergence to optimal for algorithm). The
proposed Algorithm 1 returns the correct optimal classifierprobability: the minimizer of (3).
The proof of Theorem 3 mirrors the recursive structure of
OptProb and uses induction on the number of vertices. It
relies on two technical lemmas (proofs deferred to Section
B of the Supplementary). Lemma 4 establishes propertiesof the solutions to linear programs that are solved at each iteration. The proof uses standard duality and complementary

1. If (u, v) ∈ E, a(u) ≤ b(v).
2. We have z ≥ 0, 1> z = P (A ∪ B), and P ({v}) =qv (M > z)v .
3. Let Ai = a−1 (i) and Bi = b−1 (i).
For all i, P (Ai ∪ Bi ) > 0. For all u ∈ A and v ∈ B,
P (Ab(v) )P (A)
qu = P (Aa(u)a(u)∪Ba(u) ) and qv = P (Ab(v) ∪Bb(v) ) .
4. For u, u0 ∈ A, if a(u) ≤ a(u0 ) then qu ≤ qu0 .
Proof of Theorem 3. From Lemma 5, we have that the computation of OptProb terminates and some information about(q, z) = OptProb(V1 , V−1 , E, P ). Properties 1,3, and 4 together imply (4) and (5) (i.e. that q is feasible in (3)): forany (u, v) ∈ E, there is some u0 such that a(u0 ) = b(v) andqu ≤ qu0 = 1 − qv . Property 2 provides (6), (7), and (8).
Lemma 2 establishes the optimality of q.
3.3. Complexity analysis
In the worst case, at each step of the algorithm, only asingle vertex will be removed from one part of the bipartite
graph, and the algorithm will only terminate when only
singleton parts of the graph remain. In this case, if there are|V| vertices in the graph, there will be |V| recursive steps,
with each run taking O(|V||E| log(|V|2 /|E|)) (Goldberg &Tarjan, 1988).

Lower Bounds on Cross-entropy Loss in the Presence of Test-time Adversaries

0.7
200
800
3200
5000

0.5
0.4
0.3
0.2

0.4
0.3
0.2
0.1

0

0
2.5

3

3.5

4



4.5

5

5.5

200
800
3200
5000

0.5

0.1

2

0.7

0.6

Cross-entropy loss

0.6

Cross-entropy loss

Cross-entropy loss

0.76(a) MNIST

0.6

200
800
3200
5000

0.5
0.4
0.3
0.2
0.1
0

2

2.5

3

3.5

4



4.5

(b) Fashion MNIST

5

5.5

6

3

3.5

4

4.5

5



5.5

6

6.5

7

(c) CIFAR-10

Figure 1. Variation in minimum log-loss for an `2 adversary with adversarial budget  and the number of samples from each class. The
maximum possible log-loss is ln 2, which is around 0.693. The total number of samples is 5000.

4. Experiments: Using Bounds as a
Diagnostic Tool

nonetheless choose to use them to provide a point of comparison with existing work.

In the previous section, we derived lower bounds on the
cross-entropy loss that are applicable for all discrete distributions as well as for Gaussian data. In this section, we
compute and use these bounds as a diagnostic tool to better
understand limits of robust learning for practical datasets
and algorithms. We determine lower bounds on the crossentropy loss for practical datasets of interest. We analyze
the runtime of Algorithm 1 and show its speedup over thegeneric non-linear convex solver from CVXOPT (Andersen
et al., 2013). Finally, we uncover a gap between the loss
obtained by several robust training methods and the lower
bound, and investigate the use of ‘soft-label’ training with
optimal classifier outputs to close this gap. All results are
obtained on an Intel Xeon cluster with 8 P100 GPUs.

Algorithm implementation: We first create the conflictgraph by checking for `2 ball intersections between all pairsof points from the two classes. The number of vertices
V in the conflict graph G is n1 + n−1 . We will generally
consider the case when the total number of datapoints ineach class is equal, giving |V| = 2n. The total number ofedges E is then p̂(n, )n2 , where p̂(n, ) is an estimate of
the probability that the neighborhoods around points fromthe two classes have a non-empty intersection. We find thatfor the `2 norm, p̂(n, ) increases monotonically with  andunlike the log-loss, is largely independent of the number ofsamples (Section C.2. of the Appendix).

4.1. Lower bounds on robustness for real-world
datasets
From Theorem 3 and Algorithm 1, we have an efficientmethod to compute the optimal log-loss for any empirical
distribution. Here, we consider 3 benchmark computer
vision datasets: MNIST (LeCun & Cortes, 1998), Fashion
MNIST (Xiao et al., 2017) and CIFAR-10 (Krizhevsky &Hinton, 2009). Each of these datasets is originally a 10class classification problem, and from each, without lossof generality, we choose the ‘3 vs. 7’ classification task asa representative binary classification problem (results forother choices are in Section C.1. of the Supplementary). In
each case, there are a total of n = 5000 training samples
per class which can be used to compute the lower bound.
To derive a numerical bound, we need to specify the neighborhood function (adversarial constraints). While ourbounds are valid for any non-empty neighborhood function, we pick the commonly used `2 -norm ball constraint,
parametrized by its radius . This has been used numerous times for both attacks (Carlini & Wagner, 2017) anddefenses (Madry et al., 2018), and has well-establishedbenchmarks (adv). Although `p -norm constraints have been
critiqued (Gilmer et al., 2018a; Evtimov et al., 2020), weUsing this conflict graph, represented by a sparse matrix,
we use Algorithm 1 to compute the lower bound. We use
the maximum flow algorithm from Scipy (Virtanen, 2020)
as LinOpt at the top level and for each recursively obtained
split. This implementation uses the Edmonds-Karp (Edmonds & Karp, 1972) algorithm. We note that any linear
program solver can be used and casting the problem as
maximum flow is not canonical.
Numerical lower bounds: In Figure 1, we plot the variation in the minimum cross-entropy loss over the full set of5000 training samples for all 3 datasets as the adversary’s `2budget is varied. The lower bound is only non-trivial after abudget of around 3.0 for the MNIST dataset and 4.0 for the
CIFAR-10 dataset. At smaller budgets, the optimal classifier
can achieve 0 loss even in the presence of an adversary. We
note that this classifier may not generalize well to test data,
since these bounds do not represent the population lower
bound over the unknown underlying distribution.
Impact of subsampling: We also analyze the impact of
subsampling from the complete set of samples to understand the dependence of the lower bound on the number ofsamples. We find that as the number of samples increases,
the lower bound increases as well, indicating the presence ofmore intersections among samples, and thus more flexibility
for the adversary.
Empirical runtime comparison: We compare the runtime

Lower Bounds on Cross-entropy Loss in the Presence of Test-time Adversaries

10000

0.7
CustomGeneric

6000
4000
2000
0
500

1000

1500

2000

2500

3000

Sample Size

3500

4000

4500

5000

(a) Scaling with sample size at  = 6.0

Cross-entropy loss

Runtime (s)

8000

0.6
0.5

Population loss
1000 samples
5000 samples

0.4
0.3
0.2
0.1
0
0

10000

0.5

1

1.5

2



2.5

3

3.5

4

4.5

Runtime (s)8000
CustomGeneric

6000

Figure 3. Comparing the population-level and sample-level lower
bounds on cross-entropy loss for synthetic 2-class Gaussian dataof dimension 100.

4000
2000
0
4

4.5

5

5.5



6

6.5

7

(b) Scaling with  for 5000 samples per
class
Figure 2. Algorithm runtime comparisons for CIFAR-10

of Algorithm 1 using the max-flow solver from Scipy tothat of the general purpose solver for convex programs with
non-linear objective functions from CVXOPT (Andersen
et al., 2013), which uses primal-dual interior point methods(Boyd et al., 2004).
The two parameters that determine the runtime of the algorithms to compute the minimum log-loss are the number ofvertices |V| and the adversary’s budget  which controls thegraph density. In Figure 2a, we show the variation in CPU
time in seconds as the number of vertices in each class isvaried. The mean and standard deviation over 10 runs isreported and the maximum time either algorithm is allowed
to run is 10, 000 seconds after which it is terminated. It
is clear that our custom algorithm runs significantly fasterthan the general purpose convex solver, with speed-ups ofup to 3000×. The advantages are even starker as  is variedin Figure 2b, with the general purpose solver taking in excess of 10, 000 seconds for any budget greater than 5.6. We
can draw the same conclusions for the other two datasetsfrom the runtime analysis presented in Section C.3. of the
Supplementary.
4.2. Synthetic Gaussian data
From Section 2.3, we have a complete characterization of
the robust learning problem for Gaussian distributions withrespect to the cross-entropy loss. We use this to study
the gap between population-level and sample-level crossentropy lower bounds, finding that this gap increases withthe dimension of the data. Thus, when the underlying distribution is unknown, sample-level lower bounds must be
used carefully, especially with a small number of samples.
We use a diagonal covariance matrix Σ with Σii sampled√ ii , where C
uniformly between 0 and 1, and set µi = CΣdis a constant determining the distance between the means.

The two classes have identical covariances and means of
opposite sign. In Figure 3, we compare the lower boundon cross-entropy loss directly obtained from Theorem 2(‘Population loss’) and that over the empirical distributions
resulting from sampling it (‘k samples’) for d = 100. In thelatter case, the lower bounds are computed using Algorithm
1. The reason for the lack of intersections at lower budgets
for the empirical distribution is that in high dimensions, evenwhen the underlying distributions overlap, further perturbation is needed for intersections between the neighborhoodsof sampled points. Results for other choices of d are in
Section C.4. of the Supplementary.
4.3. Evaluating the performance of robust training
We now compare the cross-entropy loss obtained by robust training techniques such as adversarial training (Madryet al., 2018) and TRADES (Zhang et al., 2019) to our lower
bounds. We present results on the MNIST (LeCun & Cortes,
1998) and Fashion-MNIST (Xiao et al., 2017) datasets in themain body, and on CIFAR-10 in Section ?? of the Appendix.
Our key takeaways are i) standard adversarial training canachieve close to the minimum cross-entropy loss with a sufficiently large architecture, but a gap still remains for the
0 − 1 loss and, ii) soft label training with optimal probabilities obtained from our framework can help close this gap aswell as aid in generalization in some cases.
Robust training setup. We train a ResNet-18 network
using adversarial training and TRADES, these being themost effective robust training methods for an `2 adversary(Croce et al., 2020). The robust cross-entropy loss for thesemodels is computed using the state-of-the-art AutoAttack(Croce & Hein, 2020). Adversarial training, referred toas ‘hard labels’ in Figure 4, utilizes one-hot labels, while
TRADES uses the network’s own prediction as soft-labels.
How close is the robust training loss of current techniques to optimal? In Figure 4, for both datasets, adversarial training achieves close to the minimum possible crossentropy loss on the training data. However, TRADES isLower Bounds on Cross-entropy Loss in the Presence of Test-time Adversaries
Table 1. Comparison of train and test set robust accuracy withdifferent robust training techniques for the FMNIST dataset.

Cross-entropy loss

0.7
0.6

FMNIST ( = 4.6)

0.5
0.4
0.3

Hard labels
Clipped soft labels
OptimalMinimum loss
Adv. training
TRADES (β = 1.0)
TRADES (β = 6.0)

0.2
0.1

FMNIST ( = 5.0)

Train

Test

Train

Test

0.349
0.326
0.305

0.348
0.331
–

0.451
0.419
0.401

0.451
0.420
–

0
2

2.5

3

3.5

4



4.5

5

(a) MNIST

Cross-entropy loss

0.7
0.6
0.5
0.4
0.3

Minimum loss
Adv. training
TRADES (β = 1.0)
TRADES (β = 6.0)

0.2
0.1
0
2

2.5

3

3.5

4



4.5

5

5.5

6

(b) Fashion MNIST
Figure 4. Comparison on training data between the cross-entropy
loss (computed using AutoAttack) obtained by different training
methods versus the optimal loss.

outperformed by standard adversarial training with hardlabels. This runs counter to earlier observations at lower
adversarial budgets that TRADES was more robust. In thecase of the 0 − 1 loss for all datasets and the cross-entropy
loss for CIFAR-10, the gap is far larger even for moderatebudgets (Section D of the Supplementary). Nevertheless,since a gap exists even for the cross-entropy loss, we canrule out the possibility that the gap previously observed forthe 0 − 1 loss in Bhagoji et al. (2019) is only due to theuse of a surrogate loss. Our experiments indicate that atlarger adversarial budgets, especially for the MNIST and
CIFAR-10 datasets, robust training does not converge tothe optimal loss. We leave for future work to determine if
closing this gap will lead to improved generalization.
We also conduct ablation studies with larger networks andsmoother activation functions, techniques known to help
with robust training. Resnet-101 for FMNIST reduces crossentropy loss to 0.42, in comparison to 0.45 with ResNet-18,
which is close to the optimal loss for Fashion MNIST at = 5.0. Additionally, with over 15 different activation
functions, we did not observe any significant drop in crossentropy loss compared to the standard ReLU. Further details
and results are in Section D.2. of the Supplementary.
Using soft labels. Training using soft labels is known to
improve the performance of deep neural networks (Zheng
et al., 2016). Since at higher values of , the optimal classi-fier may assign a higher probability to the opposite class as
the true label, the obtained soft labels are noisy. To avoid
introducing this label noise, while also extracting meaningful gradients, we impose a lower bound on the probabilityof the correct class (details in Section ?? of the Appendix).
We find that training with these clipped soft-labels can reduce the cross-entropy loss by a significant margin (Table
1). Additionally, this method can also improve the 0 − 1 loss
for the MNIST datasets for a range of budgets (Section D.1.
of the Supplementary). Overall, these results indicate thatappropriately calibrated soft label training can help withrobustness.

5. Related Work
We only discuss the closest related work here on theoreticalanalysis of test-time adversaries and robust training. Extensive surveys (Papernot et al., 2016; Liu et al., 2018; Biggio& Roli, 2017; Li et al., 2020) provide a broader overview.
Information-theoretic limits on robust learning. All previous work on information-theoretic limits on robust learning has focused on the 0 − 1 loss. (Dohmatob, 2019) and(Mahloujifar et al., 2019) use the ‘blowup’ property of specific data distributions to determine bounds on the robust
loss, given some level of loss on benign data. (Bhagoji
et al., 2019) and (Pydi & Jog, 2020) use optimal transport toprovide lower bounds on the robust loss for a general classof distributions, without a dependence on the loss on benign
data. While (Pydi & Jog, 2020) does consider convex losses,
we are the first to provide an explicit method and framework,
as well as numerical results, for the cross-entropy loss.
Generalization for adversarially robust learning. A
number of papers analyze the sample complexity of robust
learning for specific distributions of interest such as Gaussians (Schmidt et al., 2018; Javanmard et al., 2020; Danet al., 2020), uniform (Diochnos et al., 2018) and spherical(Gilmer et al., 2018b). The sample complexity of PAClearning (worst case over distributions) for robust classifiers
has also been derived (Cullina et al., 2018; Yin et al., 2019;
Montasser et al., 2019). However, this line of work does notanalyze the minimum possible loss, only the gap between
the minimum and learned.
Computational limits of robust learning. Computationally bounded adversaries (Garg et al., 2020) were consid-

Lower Bounds on Cross-entropy Loss in the Presence of Test-time Adversaries

ered to devise instances where there is a separation between
their power and that of unbounded adversaries. Other work
(Bubeck et al., 2018; Awasthi et al., 2019; Montasser et al.,2020) has focused on instances where computationally efficient robust learning is possible.
Robust training of neural networks. Adversarial training (Madry et al., 2018) with follow-up improvements in
TRADES (Zhang et al., 2019), remains the most successful
robust training technique. Its performance is further improved with larger networks (Gowal et al., 2020), smooth
activations (Xie et al., 2020), early stopping (Rice et al.,2020), and careful tuning of weight decay (Pang et al., 2021).
Some other works investigate the effect of weight perturbation (Wu et al., 2020), weight averaging (Gowal et al.,2020), sub-networks on robustness (Sehwag et al., 2020)
and additional data (Carmon et al., 2019). Wang et al. (2020)
further demonstrate minor improvements in robustness withsample-weighted adversarial training. Goibert & Dohmatob (2019) show that the use of smoothed labels obtained
from the classifier can improve upon benign training, but
performs worse than standard adversarial training. For adetailed comparison of state-of-the-art robust training techniques, we refer the reader to RobustBench (Croce et al.,2020).

6. Discussion
In this paper, we have provided a framework to compute
optimal lower bounds on the cross-entropy loss for generaldiscrete distributions as well as Gaussian mixtures. We
showed how to leverage this framework to analyze current
robust training methods.
While the results in this paper are restricted to the two-classcase, here we sketch how they can be extended to the multiclass setting. There are several relationships between our
approach to the two class problem and the analogous quantities for the k-class problem with k ≥ 3. When k ≥ 3, thetargeted and untargeted adversarial classification problems
become distinct. The untargeted version is the direct generalization of our formulation for the two class version. In
the targeted version, in addition to a labeled example, theadversary received another random class label that serves
as the target and the classifier incurs a loss based on theprobability for the target class assigned to the adversarial
example. Clearly, the untargeted version is more favorable
for the adversary and the optimal loss for the untargetedversion is at least as large as the optimal loss for the targetedversion. Using the optimal losses for all of the one-vs-one
and one-vs-rest two-class classification tasks, simple lower
bounds on the optimal loss for both versions of the k-classproblem can be derived.
Our characterization of the exact optimal loss extends tothe untargeted version of the k-class problem in a reasonbly straightforward manner. The bipartite conflict graph isreplaced with a k-partite hypergraph: hyperedges containup to one vertex from each class. A polytope derived fromthis hypergraph contains the achievable correct classification probabilities. Minimizing the cross-entropy over thispolytope is still a convex problem, but our special purpose
algorithm no longer applies. The situation in the targetedcase is more complicated and we are currently extending
our framework to handle this case.
On the empirical front, we aim to further investigate theconvergence of robust training for complex datasets suchas CIFAR-10, as well as to use our framework to guide thegeneration of more robust feature representations. The link
between achieving a training loss close to optimal and thegeneralization gap for robust training is one of great interest
for future work in this domain.

Acknowledgements
This work was supported in part by the National Science
Foundation under grants CNS-1553437, CNS-1704105 andCNS-1949650, the DARPA GARD program, the Army Research Laboratory’s Army Artificial Intelligence Innovation
Institute (A2I2), the Office of Naval Research Young Investigator Award, the Army Research Office Young Investigator Prize, a faculty research award from Facebook, theSchmidt DataX award, and Princeton E-ffiliates Award. Any
opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do notnecessarily reflect the views of any funding agencies.

References
Advbench: Adversarial robustness benchmark. https://advbench.github.io/. Accessed: 2020-09-27.
Andersen, M. S., Dahl, J., and Vandenberghe, L. Cvxopt:
Python software for convex optimization, 2013.
Awasthi, P., Dutta, A., and Vijayaraghavan, A. On robustness to adversarial examples and polynomial optimization. In Proceedings of Neural Information Processing
Systems, 2019.
Bhagoji, A. N., He, W., Li, B., and Song, D. Practical blackbox attacks on deep neural networks using efficient querymechanisms. In European Conference on Computer Vision, pp. 158–174. Springer, 2018.
Bhagoji, A. N., Cullina, D., and Mittal, P. Lower bounds
on adversarial robustness from optimal transport. In Advances in Neural Information Processing Systems, pp.
7496–7508, 2019.

Lower Bounds on Cross-entropy Loss in the Presence of Test-time Adversaries

Biggio, B. and Roli, F. Wild patterns: Ten years after
the rise of adversarial machine learning. arXiv preprint
arXiv:1712.03141, 2017.

hardness. In Proceedings of the 31st International Conference on Algorithmic Learning Theory, pp. 364–385,
2020.

Boyd, S., Boyd, S. P., and Vandenberghe, L. Convex optimization. Cambridge university press, 2004.

Gilmer, J., Adams, R. P., Goodfellow, I., Andersen, D., andDahl, G. E. Motivating the rules of the game for adversarial example research. arXiv preprint arXiv:1807.06732,
2018a.

Bubeck, S., Price, E., and Razenshteyn, I. Adversarial
examples from computational constraints. arXiv preprint
arXiv:1805.10204, 2018.
Carlini, N. and Wagner, D. Towards evaluating the robustness of neural networks. In Security and Privacy (SP),2017 IEEE Symposium on, pp. 39–57. IEEE, 2017.
Carmon, Y., Raghunathan, A., Schmidt, L., Liang, P., andDuchi, J. C. Unlabeled data improves adversarial robustness. In Neural Information Processing Systems, 2019.
Croce, F. and Hein, M. Reliable evaluation of adversarialrobustness with an ensemble of diverse parameter-free attacks. In International Conference on Machine Learning,pp. 2206–2216. PMLR, 2020.
Croce, F., Andriushchenko, M., Sehwag, V., Flammarion,
N., Chiang, M., Mittal, P., and Hein, M. Robustbench:a standardized adversarial robustness benchmark. arXiv
preprint arXiv:2010.09670, 2020.
Cullina, D., Bhagoji, A. N., and Mittal, P. Pac-learningin the presence of adversaries. In Advances in Neural
Information Processing Systems, pp. 230–241, 2018.
Dan, C., Wei, Y., and Ravikumar, P. Sharp statistical guaratees for adversarially robust Gaussian classification. In
Proceedings of the 37th International Conference on Machine Learning, pp. 2345–2355, 2020.
Diochnos, D., Mahloujifar, S., and Mahmoody, M. Adversarial risk and robustness: General definitions andimplications for the uniform distribution. In Advancesin Neural Information Processing Systems, pp. 10359–
10368, 2018.
Dohmatob, E. Generalized no free lunch theorem for adversarial robustness. In Proceedings of the 36th International
Conference on Machine Learning, pp. 1646–1654, 2019.
Edmonds, J. and Karp, R. M. Theoretical improvements inalgorithmic efficiency for network flow problems. Journal of the ACM (JACM), 19(2):248–264, 1972.
Evtimov, I., Cui, W., Kamar, E., Kiciman, E., Kohno, T.,
and Li, J. Security and machine learning in the real world.
arXiv preprint arXiv:2007.07205, 2020.
Garg, S., Jha, S., Mahloujifar, S., and Mohammad, M. Adversarially robust learning could leverage computational

Gilmer, J., Metz, L., Faghri, F., Schoenholz, S. S., Raghu,
M., Wattenberg, M., and Goodfellow, I. Adversarial
spheres. In ICLR, 2018b.
Goibert, M. and Dohmatob, E. Adversarial robustness via
label-smoothing. arXiv preprint arXiv:1906.11567, 2019.
Goldberg, A. V. and Tarjan, R. E. A new approach to the
maximum-flow problem. Journal of the ACM (JACM),
35(4):921–940, 1988.
Goodfellow, I. J., Shlens, J., and Szegedy, C. Explaining
and harnessing adversarial examples. In International
Conference on Learning Representations, 2015.
Gowal, S., Qin, C., Uesato, J., Mann, T., and Kohli, P.
Uncovering the limits of adversarial training against
norm-bounded adversarial examples. arXiv preprint
arXiv:2010.03593, 2020.
Javanmard, A., Soltanolkotabi, M., and Hassani, H. Precise tradeoffs in adversarial training for linear regression.
In Proceedings of Thirty Third Conference on Learning
Theory, pp. 2034–2078, 2020.
Körner, J. Coding of an information source having ambiguous alphabet and the entropy of graphs. In 6th Prague
conference on information theory, 1973.
Krizhevsky, A. and Hinton, G. Learning multiple layers offeatures from tiny images. 2009.
LeCun, Y. and Cortes, C. The MNIST database of handwritten digits. 1998.
Li, L., Qi, X., Xie, T., and Li, B. Sok: Certified robustness for deep neural networks. arXiv preprint
arXiv:2009.04131, 2020.
Liu, Q., Li, P., Zhao, W., Cai, W., Yu, S., and Leung, V. C.
A survey on security threats and defensive techniques ofmachine learning: A data driven view. IEEE access, 6:12103–12117, 2018.
Madry, A., Makelov, A., Schmidt, L., Tsipras, D., andVladu, A. Towards deep learning models resistant toadversarial attacks. In ICLR, 2018.

Lower Bounds on Cross-entropy Loss in the Presence of Test-time Adversaries

Mahloujifar, S., Diochnos, D. I., and Mahmoody, M. The
curse of concentration in robust learning: Evasion andpoisoning attacks from concentration of measure. In
Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 4536–4543, 2019.
Montasser, O., Hanneke, S., and Srebro, N. Vc classes
are adversarially robustly learnable, but only improperly.
arXiv preprint arXiv:1902.04217, 2019.
Montasser, O., Goel, S., Diakonikolas, I., and Srebro, N.
Efficiently learning adversarially robust halfspaces withnoise. In Proceedings of the 37th International Conference on Machine Learning, pp. 7010–7021, 2020.
Pang, T., Yang, X., Dong, Y., Su, H., and Zhu, J. Bag oftricks for adversarial training. In International Conference on Learning Representations, 2021. URL https://openreview.net/forum?id=Xb8xvrtB8Ce.
Papernot, N., McDaniel, P., Sinha, A., and Wellman, M.
Towards the science of security and privacy in machinelearning. arXiv preprint arXiv:1611.03814, 2016.
Pydi, M. S. and Jog, V. Adversarial risk via optimal transport and optimal couplings. In Proceedings of the 37th
International Conference on Machine Learning, pp. 7814–
7823, 2020.
Rice, L., Wong, E., and Kolter, Z. Overfitting in adversarially robust deep learning. In International Conference on
Machine Learning, pp. 8093–8104. PMLR, 2020.
Schmidt, L., Santurkar, S., Tsipras, D., Talwar, K., andMadry, A. Adversarially robust generalization requires
more data. arXiv preprint arXiv:1804.11285, 2018.
Sehwag, V., Wang, S., Mittal, P., and Jana, S. Hydra: Pruning adversarially robust neural networks. Advances in
Neural Information Processing Systems (NeurIPS), 7,
2020.
Shalev-Shwartz, S. and Ben-David, S. Understanding machine learning: From theory to algorithms. Cambridge
university press, 2014.
Szegedy, C., Zaremba, W., Sutskever, I., Bruna, J., Erhan,D., Goodfellow, I., and Fergus, R. Intriguing properties ofneural networks. arXiv preprint arXiv:1312.6199, 2013.
Virtanen, P. e. a. SciPy 1.0: Fundamental Algorithms for
Scientific Computing in Python. Nature Methods, 17:
261–272, 2020. doi: 10.1038/s41592-019-0686-2.
Wang, Y., Zou, D., Yi, J., Bailey, J., Ma, X., and Gu,
Q. Improving adversarial robustness requires revisiting misclassified examples. In International Conference on Learning Representations, 2020. URL https://openreview.net/forum?id=rklOg6EFwS.

Wu, D., Xia, S.-T., and Wang, Y. Adversarial weight perturbation helps robust generalization. Advances in Neural
Information Processing Systems, 33, 2020.
Xiao, H., Rasul, K., and Vollgraf, R. Fashion-mnist: a
novel image dataset for benchmarking machine learningalgorithms, 2017.
Xie, C., Tan, M., Gong, B., Yuille, A., and Le, Q. V. Smooth
adversarial training. arXiv preprint arXiv:2006.14536,
2020.
Yin, D., Ramchandran, K., and Bartlett, P. Rademacher
complexity for adversarially robust generalization. In
ICML, 2019.
Zhang, H., Yu, Y., Jiao, J., Xing, E. P., Ghaoui, L. E., and Jordan, M. I. Theoretically principled trade-off between robustness and accuracy. arXiv preprint arXiv:1901.08573,
2019.
Zheng, S., Song, Y., Leung, T., and Goodfellow, I. Improving the robustness of deep neural networks via stability training. In Proceedings of the ieee conference on
computer vision and pattern recognition, pp. 4480–4488,
2016.