Lower Bounds on the Robustness of Fixed Feature Extractors to Test-time Adversaries
Authors: Arjun Nitin Bhagoji
Daniel Cullina
Ben Zhao
Venue: ICLR 2022 Submitted (2022)
Keywords: robustness
lower bounds

Abstract: Understanding the robustness of machine learning models to adversarial examples generated by test-time adversaries is a problem of great interest. Recent theoretical work has derived lower bounds on how robust \emph{any model} can be, when a data distribution and attacker constraints are specified. However, these bounds only apply to arbitrary classification functions and do not account for specific architectures and models used in practice, such as neural networks. In this paper, we develop a methodology to analyze the robustness of fixed feature extractors, which in turn provide bounds on the robustness of any classifier trained on top of it. In other words, this indicates how robust the representation obtained from that extractor is with respect to a given adversary. Our bounds hold for arbitrary feature extractors. The tightness of these bounds relies on the effectiveness of the method used to find collisions between pairs of perturbed examples at deeper layers. For linear feature extractors, we provide closed-form expressions for collision finding while for arbitrary feature extractors, we propose a bespoke algorithm based on the iterative solution of a convex program that provably finds collisions. We utilize our bounds to identify the layers of robustly trained models that contribute the most to a lack of robustness, as well as compare the same layer across different training methods to provide a quantitative comparison of their relative robustness. Our experiments establish that each of the following lead to a measurable drop in robustness: i) layers that linearly reduce dimension, ii) sparsity induced by ReLU activations and, iii) mismatches in the attacker constraints at train and test time. These findings point towards future design considerations for robust models that arise from our methodology.

Under review as a conference paper at ICLR 2022
LOWER BOUNDS ON THE ROBUSTNESS OF FIXED FEA- TURE EXTRACTORS TO TEST-TIME ADVERSARIES
Anonymous authors Paper under double-blind review
ABSTRACT
Understanding the robustness of machine learning models to adversarial examples generated by test-time adversaries is a problem of great interest. Recent theoret- ical work has derived lower bounds on how robust any model can be, when a data distribution and attacker constraints are specified. However, these bounds only apply to arbitrary classification functions and do not account for specific ar- chitectures and models used in practice, such as neural networks. In this paper, we develop methodology to analyze the robustness of fixed feature extractors, which in turn provides bounds on the robustness of any classifier trained on top of it. The tightness of these bounds relies on the effectiveness of the method used to find collisions between pairs of perturbed examples at deeper layers. For linear feature extractors, we provide closed-form expressions for collision finding while for arbitrary feature extractors, we propose a bespoke algorithm based on the iter- ative solution of convex program that provably finds collisions. We utilize bounds to identify the layers of robustly trained models that contribute the most a lack of robustness, as well as compare the same layer across different training methods to provide quantitative comparison of their relative robustness.
INTRODUCTION
The robustness of machine learning models to test-time (evasion) attacks, particularly via adversarial examples, has been studied extensively from empirical perspective (Croce et al., 2020 Papernot
ct al., 2016 Li et al. 2020
Biggio & Roli, 2017). A plethora of attacks (Szegedy et al., 2013]
Carlini & Wagner 2017
Bhagoji et al. 2018: Croce & Hein 2020) and defenses (Madry et al.
2018 Zhang et al. 2019) has been proposed. The resulting arms race between proposed attacks and
defenses, has led recent theoretical work (Dohmatob) 2019 Cullina et al.) 2018) Mahloujifar al.,
2019 Bhagoji et al. 2019 2021 Montasser et al. 2011)) to focus on understanding the fundamental bounds of learning in the presence adversarially perturbed inputs, in terms of both the existence of robust classifiers and the sample complexity required to learn them.
A line of research this front has investigated lower bounds on the robustness attainable by any classifier when classifying data from distributions modified by adversarial perturbations (Pydi & Jog] 2020; Bhagoji et al. 2019) 202I). In particular, fformation-theoretee lower bounds on the minimum possible robust 0 and cross-entropy losses have been derived for arbitrary discrete distributions and very general attack models. However, the bounds from these papers are only applicable when considering the set of possible classifiers to be all measurable functions, which does not translate to practice. The classifier architecture and even some portion of the parameters fixed (such in transfer learning) in practical approaches to training machine learning models.
In this paper, we leverage this line of work to find lower bounds on the robustness of commonly used, fixed feature extractors. This provides principled method to compare the robustness of feature extractors obtained by different training methods to arbitrary test-time adversaries. The key question we answer is:
What is the minimum robust loss incurred by any classifier trained on top of a fixe feature extractor?
Two challenges for training robust machine learning models motivate this question. First, since transfer learning is now common practice, it is incumbent upon the model trainer to choose a robust pre-trained feature extractor. Our work offers principled and quantitative method to choose among

---

Under review as a conference paper at ICLR 2022
feature extractors obtained from different layers and training methods. Second, are able to shed light on the impact of common architectural choices, such as activation functions and dimensionality reduction on robustness. This arises from our study of how the lower bound evolves from layer to layer within deep neural networks.
Importance of lower bounds robustness: To determine classifier-agnsstic lower bounds robustness, earlier work focused on the interaction between points from different classes in the input space when perturbed through the construction of a conflict graph. Minimizing an appropriately defined loss function over this graph determines an information-theoretie lower bound on the loss. Intuitively, the denser the graph is, the higher the lower bound. These classifier -agnosicc bounds are able to determine the plausibility of robust classification for given adversary and dataset, and highlight practically relevant perturbation budget.
1.1 CONTRIBUTIONS
Lower bounds on robustness for fixed feature extractors: We significantly extend prior work by deriving lower bounds that depend the architecture and weights of fixed feature extractors. We construct a distance function over the input space that depends on the feature extractor in use. Our results have implications for both analyzing the robustness of already trained classifiers as well as determining feature extractors to use for applications such as transfer learning.
For linear feature extractors such as the first layer of a neural network, we determine exact, closed form expressions to find collisions. Collision finding for non-linear feature extractors custom algorithm. We approach the cellision-finding problem with a descent algorithm that solves a sequence of convex optimization problems over polytopes. This algorithm has the structural ad- vantage of maintaining feasibility (for some adversarial budget constraint) at each step. Despite the fact that it does not find a global minimum, the solutions found are useful for obtaining not just approximations but actual lower bounds optimal adversarial classification loss.
Bespoke algorithms for collision finding:
non-convex optimization problem, for which we propose
Empirical findings: We utilize our method to find numerical lower bounds on the robustness of fixed feature extractors trained on two different datasets with both fully- connecedd and convolutional architectures. Our results indicate that the use of cimensionality-reducii linear layers as well as the effective compression induced by ReL.U activations lead to significantly less robust networks. Further, we confirm the oft-cited observation that mismatches between the adversary's 's budget at train and test time impacts robustness negatively. Taken together, these findings point towards future design considerations for robust models.
2 DERIVING LOWER BOUNDS FOR FIXED FEATURE EXTRACTORS
In this section, we develop method for evaluating the robustness a feature extractor for classifica- tion in the presence of test-time adversary. We characterize the optimal adversarial loss achievable by any classifier that uses the fixed feature extractor as its initial layer. This characterization is based on conflict graph derived from discrete data distribution and the constraints of the adversary.
We consider a supervised classification problem with a test-time adversary. We have example space X' and label space y = 11, Labeled examples are sampled from a joint probability distribution P over X' x y.
Examples and labels:
Test-time adversary: The test-time adversary modifies natural example subject to some con- straints to generate an adversarial example that will be classified GoodifildGGooofelllo et al. (2015): Szegedy al. (203)); Carlini & Wagner (2017). Formally, the adversary samples labeled example (ær, y) from P and selects ă E N(x), where : X + 2 is the neighborhood function encoding the constraints on the adversary and X is the space of adversarial examples 1 For all x, N(x) must be nonempty. This definition encompasses the l, family of constraints widely used previous work.
'In most (but not all) settings that have previously been studied, X = X. We believe that making the distinction helps to clarify some of our definitions: their applicability in this general context affects what properties they be expected to have.
2

---

Under review as a conference paper at ICLR 2022
Measuring ad adversarial loss: We consider 'soft' classification functions (or classifiers) that map examples to probability distributions over the classes. These are h : X' - A>, where A {p E R p 0. DyE Py 1}. We measure classification performance with loss function 8: 8: x y - R, so the expected performance of a classifier is ElsupseN {(h(z), y),, where (r, ~ P. In the two class setting, h1(²) = - h( so any loss function that treats the classes symmetrically can be expressed as {(p y) E' (Pyy) Additionally, é' should be decreasing. Together, these allow the optimization over adversarial examples to be moved inside the loss function, giving B [[((infaEN() (in(zen(=) k(:)y.9) Thus, the adversarial optimization can be analyzed by itself.
Definition For a soft classifier h, the correct-classifeen classfccassifiiaatio probability qu that it achieves on an example = (x. u) in the presence of an adversary is qu in(2eN(x) h(()). The space of achievable correct classification probabilities is
PV,N.
U {IERY: :((a,)) EV, 05 (ey)) S inf KEH
1())) $EN(w)
Bhagoji et al. (2021) characterized Pv.N.H in the case that H. is the class measurable functions X + A For a data distribution P that is discrete with finite support V S X x V, this allows the optimization over Pv,N.H
minimum adversarial loss achievable to be expressed
inf NEW
inf (a.))~ sup ((h(B).)) PEPv.N.M eEV SEN(x)
P((()))
We extend their approach to analyze feature extractors as follows. Given a feature space Z and fixed, measurable feature extractor f + Z. define H, = {h E H h = f): an element of Hl is some measureable y + A composed with f. Our aim to characterize Py,N. so that we can optimize loss functions over it to evaluate the suitability of ʃ.
In Bhagoji et (202T), the notion of a conflict graph was used to record neigh- borhood intersections for pairs of points from different classes. When such intersection exists, is impossible for any classifier to correctly classify both those points in the adversarial setting. We extend this notion to apply to the family of classifiers using fixed feature extractor f. In our setting, conflict exists between a pair of points when each of them has neighbor that is mapped the same point in the feature space.
Conflict graph:
We call the conflict graph Gy.nHH, where V C X x D When we apply Gv.N. in order to understand classification of labeled examples with distribution P. take V to be the support of P. The graph is bipartite: the vertex set is partitioned into parts V. = Vn (X x {c)). The edge set is
Ev.N.f = {((u, 1), (v. -1) E V1 x V-1 : 3ě E (()), E N(v) such that f(ū) = f())}.
Lemma 1 (Feasible output probabilities). The set of correct classification probability vectors for support points V, adversarial constraint N, and hypothesis class H, is
Pv.N., (q E V q 0,
where B E XV is the edge incidence matrix of the conflict graph Gv.N.--
The proof is given in Appendix A And follows the structure of the proof in Bhagoji et al. (2021)
Approximating Gy.N. and P If instead of knowing the true conflict graph Gy.N. have some subgraph, then we can find a polytope that is a superset of the true Py, N If we mini- mize some expected loss over this proxy polytope, we obtain lower bound the optimal loss over Hy. Because subgraphs of the conflict graph lead to valid lower bounds on optimal classification performance, can use this method evaluate the quality of feature extractor f even if exact computation of the conflict graph is computationally intractable.
2.1 DISTANCE INTERPRETATION
The construction conflict graph and characterization of the feasible correct classification prob- abilities from the previous section apply any feature extractor and neighborhood constraint. In
3

---

Under review as a conference paper at ICLR 2022
(a) Some fibers of
(b) { with the fiher (1)
Figure 1: Induced distances for f I R², (10 xi (max(1ro 0), max 0)), pair of
ReLUs). Let a, b > 0. Then the fiber (f b)H) is the point {(a b)}. The fiber f- ({ 0)}) the ray {(a, y) I 0}. The fiber (( 0)}) is the quadrant {(x, y) r 0. S 0}. For
(1, and = (9, -5) 5), we have (u, v) 5. (4,0), (4, -)), and E (4,
the most commonly studied settings, the neighborhood constraint arises from distance function: No (z) = (a X d(x, 2) S 3). This parameter is the adversarial budget constraint.
For any two examples and v, natural quantity to consider is the smallest adversarial budget that would cause the edge (u. v) be appear the conflict graph:
(u, v) = im 0: (. N. # 2 inf max(d(u, (enx(d(,,))dd d(v,
sex
We will call this the distance on X' induced by d. When X X and (') = || per--" =' I|p. the minimal adversarial budget is simply 2||uu ullp- Because the relationship to the distance used in the adversarial budget constraint so simple, this quantity is not usually discussed independently. This definition generalizes easily to the setting of classification with particular feature extractor, the resulting quantity much more interesting.
Definition 2.
The distance induced X by d and f is the minimum adversarial budget required to create a conflict between u and v after a feature extractor f:
Et u) = inf(= 20. 0: ((NN(()))(((N(()) # 20
inf max(dlu, (o)(dd,,),d(r; 8)). (2)
This reduces to e* (u, v) when f is the identity function, or more generally any injective function. Observe that any choice of u and @ provide an upper bound on (", v), which is useful for finding subgraph of Gv,N.f and lower bounds optimal classification performance in Hy.
Figure illustrates the computation of E for simple f that is related to the ReLU function.
Induced distance not a distance on the feature space: The fact E defined on X' is essential: not possible interpret it as a distance on Z. For full explanation of this point, see Appendix B
3 DISTANCE COMPUTATIONS FOR PRACTICAL FEATURE EXTRACTORS
Throughout the remainder of the paper, we will work in more concrete setting. We assume that our example space is a real vector space and that adversarial examples are from the same space: nonempty, closed, convex, origin-symmetric set. These conditions
X x= X _d Let B C X' imply the zero vector in contained in B. We take the neighborhood of any point to be scaled, (z) x + =B. Neighborhood constraints derived from & norms fit into this class: encode them by defining B {6 E R ||0| < 1}, which results in (=(x) = {ē E R" || - & s}. We will focus on L based neighborhoods, but our algorithms could be adapted any choice of B over which efficient optimization is possible.
shifted version of this ball:

---

Under review as a conference paper at ICLR 2022
3.1 LINEAR FEATURE EXTRACTORS
Suppose that our feature extractor is an affine linear function of the input example: f(x) Lx + k for some matrix L E R
X and vector l: E R Then the distance e (u, v) becomes
inf 2 0: {1: +(u+ : 8 EB) n (k + L(u + 8¹) : E EB) # 23.
Because ((E,5) E R E eB} is closed convex cone, E (u, 2) can be expressed as the following convex optimization problem:
infe subject to ā E EB, 8' EB,
- 80) ((v u)) u)
Because B is closed and the linear subspace is always nonempty, the infimum is achieved. Also, it is sufficient to consider (ò, 8') satisfying ö' = -6: for any feasible 6, 0"), the point (s, (5 /2)/2, (6' 0)/2) is also feasible, has the same value, and satisfies the additional constraint. The feasibility of the symmetrized point uses the orgiin-symmetry of B. The simplified program is
min subject ò E eB, Lô = L( L u)/2.
Thus the optimal adversarial strategy for creating conflict between u and is intuitive: produce examples with the same features as the midpoint (u + e2/2.
B is the unit lg ball, there are further simplifications. Consider the singular value decomposition == UEVT where we do not include zero singular values in E. Then the linear map given by UE is injective and can be canceled from the linear constraint on 5. The resulting program is
1 VT (u u)),
min subject to ||ō1|2 c, VT5
2
the optimal choice of 5 1 VV u). and ( v) 1 | (v u)ll.. Observe that this ?
is the norm of vector in IR f.e. the feature space, contrasting with our discussion in Section B However, this is essentially the only case Eu, v) simplifies into feature space distance.
3.2 FULLY CONNECTED NEURAL NETWORKS WITH RELU ACTIVATIONS
For this feature extractor architecture, we have = f(0) ..... f(I) where the layer i function is f()) R": + Roan (z) (4:10 + 2)) Here =+ represents the component- wise positive part of the vector Then (u, v) the value of the following optimization problem:
mine subject to 8 E eB, eB, o
+ 8) = ( ....o (0) + +').
As in the linear case, the minimum exists because the feasible. In contrast with the linear case, the equality constraint is nonconvex.
closed and the equality constraint is
The local linear approximation to f (z) around point z' is diag(s (1.=²) (f.=")))))))))) (K())) (L))) where (t.=")
a zero-one vector that depends on the sign pattern of 1:(0 + L(0 2/: s f(2²) ((R(0) + 2/)2) >
0). In other words, (i.=z) is the ReLU activation pattern layer when z' is the input to that layer.
Using these linear approximations, the feasible set of (6, E R satisfying the constraint f(u 6) f( + 8') can be decomposed a linear subspace and there are some linear inequalities specifying the region where that activation pattern actually occurs. For one-layer network, the linear piece for pattern is
union of polytopes: each activation pattern defines
f(x) = diag(s)(k: + L2) for diag(2s 1) + T.2) 2 0.
Thus one of the polytopes composing the feasible set is 55, t satisfying
diag(s)(k + L(u + 6)) = diag(s (A: + L(u 8')),
diaiag()) - () L(u + 8)) 2
(2 diag(s') - 1) L(v 8')) 2 0.
In the one-layer case, the whole feasible region is covered by polytopes where s s = Observe that the dimension of the subspace satisfying the linear equality varies with s. When contains multiple layers, each polytope in the feasible set is defined by a linear equality constraint involving feature vectors together with linear inequality for the sign of each ReL.U input.
5

---

Under review as a conference paper at ICLR 2022
We optimize over this feasible set with descent algorithm: Algorithm 2 details the version for single-layer networks. The method generalizes to multiple layers and is used to obtain our results in Section 4.2) A full description of the general version is in Appendix [ We initialize our search in a polytope that we know to be nonempty because it contains the feature space collision induced by the midpoint of the two examples. Within each polytope, we can minimize the objective exactly by solving linear cone program. We examine the dual variables associated with the linear inequality constraints determine whether an adjacent polytope exists in which we can continue the search.
In the one layer case, the cone program that we solve, which depends on (L, k, u, U, 8), is
ming subject to
(c, 8") E R + 8 E eB, 8' E EB,
diag(s) + 8) = diag( 8) [[ + 5¹), diagg(s) () L(u + 6)) 2 0, (ddia(s)) - [) + + 2 0.
We need not just the values of the primal solu- tion, but the values of dual variables associated with the linear inquualities in the solution to the dual problem. These are called & and 2' in Al- gorithm 2 When both 2j > 0 and z/ 0, the input to ReLU j is zero when both f( and f + 8') are computed, and the objective func- tion could be decreased further by allowing the input to switch signs. In this case, we move to another polytope based on the new ReLU states and search there.
Algorithm Descent with midpoint initialization
Input: u E R L E R=2xa, A R Output: E RR, 6, 8 E &Rn
s k+ [u + +.) 2 -u--vl wll
2: for 0 S < n2 do
3:
8j x 1 0),
4: end for
5: repeat
6: gold 4
7: (e, 8' =,,²) + Con U,,)
8:
sold t
When we fail to find such pairs of dual vari- ables, either the minimum is in the interior of the current polytope (and thus is supported only by cone constraints), or the minimum is on the boundary of the current polytope but there is no adjacent polytope in which we could continue the search. Thus we end the search.
9: for S j < n2 do
10:
if 2j > 0and 2/$ > 0 then
11:
8, - 1 8j
end if 13: end for
until gold or gold
Algorithm termination, convergence, and complexity: The descent algorithm will terminate in a finite number of iterations and will find a local minimum of the distance function. Since the feasible space is non-convex, any local descent procedure is not guaranteed to find the global minimum. The number of variables in the cone program is proportional the number of ReLUs in the feature extractor plus the dimension of the example space. The time-complexity of a single iteration of the search is polynomial in the input dimension and number of ReLUs. The feasible region is the union of a finite but exponentially large number of convex polytopes. Due to the requirement that each iteration make progress, it is impossible to ever revisit polytope. Thus, termination is guaranteed, but no polynomial bound on the number of iterations is available. We suspect that as in the case of the simplex algorithm for linear programming, input data resulting in an extremely large number of iterations may exist, but would have delicate structure that is unlikely to arise in practice.
3.3 FURTHER COMMON LAYERS
Convolution: is straightforward to represent convolutional layer a linear layer by constructing the appropriate Topelitz matrix, and thus our method applies directly.
Batch norm layers are simply affine functions of their inputs at test-time, and the transformations they induce can be easily included in a linear layer. Our method thus applics.
Batch-normmllizttion:
Max-pool layers, like ReLUs, piecewise linear functions of their inputs, con- straints coming from the equality of max-pool outputs also lead to feasible regions that are the union of polytopes. This is simple extension left for future work due to lack of space.
Max pooling:
Other activation functions and architectures: Injective activation functions such as Leaky ReLU, EL. and sigmoid will not lead additional collisions. Further, since they are not piecewise,

---

Under review as a conference paper at ICLR 2022
different descent algorithm would be needed. We note that framework cannot find collisions in networks with both forward and backward flows, such as those with attention.
4 EVALUATION
In this section, we demonstrate how the methodology outlined in the previous sections for determin- ing the robustness of a fixed feature extractor can be used in practice. Our detailed results provide insights on how the overall robustness of a neural network evolves through its different layers and is impacted by the training procedure used.
4.1 FROM CILLISION-FINDINE TO LOWER BOUNDS
We find lower bounds on robust loss over the training set by minimizing a loss function over Gy.N.-
Vertices V from training data: The vertex set V is representation of the training data. We use 2-class problems derived from MNIST (LeCun & Cortes
1998) Fashion MNIST (Xiao et al.
2017) as in previous work (Pydi & Jog 2020 Bhagoji et al., 2019: 2021}.
Neighborhood function N: We use the common Eg nn-mo ball constraint (Madry al. 2018 in which the adversary's 's strength is parametrized by the radius e of the ball 2
Fixed feature extractors f: We use the composition of the layers of convolutional and fully- connected DNNs as our fixed feature extractors (details in Appendix E). The first layer of any of these networks (before non-linear activation is applied) behaves as a linear feature extractor. Sub- sequent layers behave as non-linear feature extractors. These networks are trained using one of stan- dard cross-entropy loss minimization or robust training with either PGD-based adversarial training (Madry et al. 2018) or the TRADES loss (Zhang et al. 2019).
Edge set from collision finding: Algorithm provides a greedy, iterative method to find col- lisions between feature representations of pairs of points from different classes. Each successful collision an edge in the bipartite conflict graph. Each iteration of this algorithm can be cast as a convex program in the form of linear cone (as detailed in Appendix [D). We solve this linear cone program using CVXOPT (Andersen et al.) 2013). Since we are working with an f2-norm constrained adversary, we can speed up computation by projecting the inputs onto the space spanned by the right singular vectors of the first linear layer. For linear convolutional layers, we cast the convolution operation as a matrix multiplication also experimented with a modification of the Auto-PGD (Croce & Hein 2020) algorithm to find collisions at deeper layers with fixed budgets as done in Engstrom et al. (2019). However, this was less effective and more expensive at finding collisions, so all further results use Algorithm 2
enable the use of the closed form derived in Section 3.1 We
Computing the lower bound from the conflict graph:
The conflict graph determines the set of possible output probabilities for each vertex (training data point) for the optimal classifier. Mini- mizing the 0- and cross-entropy losses over this graph thus results losses since any classifier must incur larger loss than the optimal classifier, by definition. We use the method from Bhagoji et al. (22TI) over the conflict graphs we derive from deeper layer representations. Results in the main body are for the cross-entropy loss (others in Appendix F..
lower bound over these
4.2 RESULTS
Interpreting lower bound values: The lower bound on the input space representations is computed by considering all possible classifiers and thus the best possible, while bounds for other represen- tations are computed by restricting the space of possible classifiers. Intuitively, the latter will always be larger than or equal to the former. The key metric to understanding the robustness of feature extractors is to check how much larger the corresponding lower bounds are. The magnitude of this difference measures the contribution of that layer to the overall network's 's lack of robustness.
Robustness of linear layer representations: Using the procedure outlined in Section 3.1 we find collisions after the first linear layer and construct a conflict graph for several models (Fig. 2 for
We are aware of the critiques of this constraint (Gilmer et al. 2018 and only use it to compare with previous work.
7

---

Under review as a conference paper at ICLR 2022
06
Trger
Besten tnantsg
ARC In8
AdG TRADES, TRADES, 2-0
TRADISS - 20 TRADESS
25
25
(a) MNIST
(b) Fashion MNIST
Figure 2: Robustness of the representation obtained from the first linear layer of a 3-layer FCNN using different training procedures
06
Pist Inea -0- Bell)
Fira linar -0- BeL.U
Secord Rell!
Sccoed Bel.))
2.5
2.5
(a) MNIST
(b) Fashion MNIST
Figure 3: Robustness of representations obtained from different layers of a 3-layer FCNN trained
using benign training both the MNIST and Fashion MNIST datasets. As expected, the linear layers of models with benign training are the least robust, with robustness increasing with the budget Guain used during training. Somewhat surprisingly, the marginal benefits of using larger budget reduce as étrain increases.
How does robustness evolve across layers? Having looked at the how robust linear layer represen- tations are, it is pertinent to consider other representations derived from other layers deeper in the network. Of particular interest are post-Rel.U representations for models with benign (Fig. 3 and robust training (Fig. 4. We find that the first ReLU activation layer contributes significantly to an increase in the lower bound for both benign and robustly trained networks. We observe that post- ReLU representations tend to be sparse, leading to easier search problem and larger number of collisions. The second linear layer, on the other hand, does not lead to much additional increase in the loss. This is a property of the particular architecture we use, and smaller linear layer is likely to lead to larger increases in loss. Finally, the second set of ReLU activations does have a measurable impact on robustness, particularly for the benign network. The impact of layer width on robustness is discussed in Appendix F.1
How does the parametrization of robust training impact layer-wise robustness? As expected, layers extracted from robustly trained network are more robust than their benign counterparts for corresponding values of c. We find a significant difference between PGD-based adversarial training and TRADES in terms of the robustness of their first linear layers (Fig. D but this largely disappears by the second ReLUU activation layer (Fig. 5). Interestingly, we observe a phenomenon where layers of network robustly trained using higher values of firain can be less robust than those using lower value, when the value at which evaluation is performed is less than the higher Erain-
Impact of linear convolutional layers robustness: As discussed in Section 3.3 the first con- volutional layer can thought as simply a matrix multiplication, although the size of the resulting matrix can be large. We find that since the effective dimension of the resulting features is much larger than the input dimension for the datasets we consider, the linear convolutional layer does not lead to increase in the lower bound (Fig. 11 in Appendix).
RELATED WORK AND DISCUSSION
5.1
RELATED WORK
Lower bounds on robustness: For cases when the data distribution is specified, Dohmatob| (2019) and Mahloujiaa et al. 2019) use the 'blowup' property determine bounds the robust loss, given
8

---

Under review as a conference paper at ICLR 2022
0.6
Ioear Rel.I
liner Fixe Rel
Scouri Re
Soceal Ret II
25
25
(a) MNIST
(b) Fashion MNIST
Figure 4: Robustness of representations obtained from different layers of a 3-layer FCNN trained
using PGD adversarial training with e 2.0
Typat space
Tapu-ppac Alk was
Beves
Alc mann
Adc mntt
TRADES - 20 TEADIS
TEADES. 1.0
TRADES, 3.0
(a) MNIST
(b) Fashion MNIST
Figure 5: Robustness of the representation obtained from the second ReLU layer of 3-layer FCNN using different training procedures. some level of loss on benign data. Bhagoji et al. (2019) Pydi & Jog (020) and Bhagoji et al. (2021) provide lower bounds robust loss when the set of classifiers under consideration is all measurable functions. These bounds are distribution-age aggnossiic and do not depend on the loss on benign data.
Work on certified robustness has considered techniques for training neural networks such that the resulting models are provably robust to perturbations upper bounded by given budget (Kolter Wong 2018 RRghhnnthhan al. 2018 Cohen al.! 2019 Li al. 2020). Typically. these models can only be certified to be robust to small budgets. In contrast, our work provides lower bounds on the robustness of partial models which are applicable across large range of budgets. Approaches to verifying the robustness of neural networks (Bunel et al.) [2017] Tieng et al., [2199] Gowal et al.) 2018) are closely related to our work, but differ in that they consider fixed end-to-end networks while we focus on a layer-by-laye analysis, allowing us to argue about the robustness of classifiers trained on top of given feature extractors.
Certification and Verification:
5.2 DISCUSSION
Implications for training robust models: Our results indicate that layers in the network that reduce the effective dimension of their incoming inputs have the largest negative impact on robustness (see further results in Appendix F.I). Two prominent examples of this are ReLU layers that reduce effective dimension by only considering non-negative outputs and fully connected layers with fewer outputs than inputs. On the other hand, linear convolutional layers do not have a negative impact on robustness. This indicates that not reducing the effective dimension of any deeper feature to be lower than that of the input data is likely benefit robustness. Further, our results confirm that the use of larger values of érainn does not necessarily translate to higher robustness at lower budgets. This points towards the need for algorithms that can effectively train a network to robust to more than single adversary at time. Finally, we find qualitative difference in the layers learned using PGD-training and TRADES, implying interesting learning dynamics with different robust losses.
Extending to state-of-the-an models and datasets: All of our experiments in this paper are on simple models and datasets which demonstrate the feasibility and use of our method. However, state-of-the art feature extractors for datasets such as Imagenet are far deeper than those considered in this paper. Thus, our algorithm would need to be made considerably faster to handle these cases. While framework, Nevertheless, the feature extractors we consider are robust for the tasks we evaluate them on, making our results and conclusions representative.
handle skip connections, networks with attention are beyond its scope.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Martin S Andersen, Joachim Dahl, and Lieven Vandenberghe. Cvxopt: Python software for convex optimization, 2013.
Arjun Nitin Bhagoji, Warren He, Bo Li, and Dawn Song. Practical black-box attacks on deep neural networks using efficient query mechanisms. In European Conference Computer Vision, pp- 158-174. Springer, 2018.
Arjun Nitin Bhagoji, Daniel Cullina, and Prateek Mittal. Lower bounds on adversarial robustness from optimal transport. Advances in Neural Information Processing Systems, pp. 7496-7508, 2019.
Arjun Nitin Bhagoji, Daniel Cullina, Vikash Sehwag, and Prateek Mittal. Lower bounds cross- entropy loss in the presence of test-time adversaries. Proceedings of the 38th International Conference Machine Learning, 2021.
Battista Biggio and Fabio Roli. Wild patterns: Ten years after the rise of adversarial machine learning. arXiv preprint 1712.037 2017.
Rudy Bunel, lIker Turkaslan, Philip HS Torr, Pushmeet Kohli, and M Pawan Kumar. unified view of piecewise linear neural network verification. arXiv preprint
2017.
Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In Security and Privacy (SP), 2017 IEEE Symposium on, pp. 39-57, IEEE, 2017.
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. In International Conference on Machine Learning, pp. 1310-1320. PMLR, 2019.
Francesco Croce and Matthias Hein. Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free free attacks. In International Conference on Machine Learning, pp. 2206- 2216. PMLR, 2020.
Francesco Croce, Maksym Andriushchenko, Vikash Sehwag, Nicolas Flammarion, Mung Chiang, Prateek Mittal, and Matthias Hein. Robustbench: a standardized adversarial robustness bench- mark. arXiv preprint arXiv:2010.06670 2020.
Daniel Cullina, Arjun Nitin Bhagoji, and Prateek Mittal. Pac-Icarning in the presence of adversaries. In Advances in Neural Information Processing Systems, pp. 230-241, 2018.
Elvis Dohmatob. Generalized no free lunch theorem for adversarial robustness. In Proceedings of the 36th International Conference on Machine Learning, pp. 1646-1654, 2019.
Logan Engstrom, Andrew Ilyas, Shibani Santurkar, Dimitris Tsipras, Brandon Tran, and Alek- sander Madry. Adversarial robustness prior for learned representations. arXiv preprint 1906.009900094 2019.
Justin Gilmer, Ryan P Adams, Ian Goodfellow, David Andersen, and George E Dahl. Motivating the rules of the game for adversarial example research. arXiv preprint 1807: 06732, 2018.
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In International Conference on Learning Representations, 2015.
Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Ue- sato, Timothy Mann, and Pushmeet Kohli. On the effectiveness of interval bound propagation for training verifiably robust models. arXiv preprint arXiv: 1810. 12715, 2018.
J Zico Kolter and Eric Wong. Provable defenses against adversarial examples via the convex outer adversarial polytope. In /CML, 2018.
Yann LeCun and Corrina Cortes. The MNIST database of handwritten digits. 1998.
Linyi Li, Xiangyu Qi, Tao Xie, and Bo Li. Sok: Certified robustness for deep neural networks. arXiv preprint arX 101141009.04131,, 2020.
10

---

Under review as a conference paper at ICLR 2022
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In ICLR, 2018.
Saeed Mahloujifar, Dimitrios Diochnos, and Mohammad 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, pp. 4536-4543, 2019.
Omar Montasser, Steve Hanneke, and Nathan Srebro. Vc classes are adversarially robustly learnable, but only improperly. arXiv preprint 1902.049 2019.
Nicolas Papernot, Patrick McDaniel, Arunesh Sinha, and Michael Wellman. Towards the science of security and privacy in machine learning. arXiv preprint /rXiv:/6/ /. 1.03814, 2016.
Muni Sreenivas Pydi and Varun Jog. Adversarial risk via optimal transport and optimal couplings. In Proceedings of the 37th International Conference on Machine Learning, pp. 7814-7823, 2020.
Aditi Raghunathan, Jacob Steinhardt, and Percy Liang. Certified defenses against adversarial exam- ples. In ICLR, 2018
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruma, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint arXiv:1312.669990 2013.
Vincent Tjeng, Kai Y. Xiao, and Russ Tedrake. Evaluating robustness of neural networks with mixed integer programming. In ICLR, 2019.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Aushion-mnisee a novel image dataset for benchmark- ing machine learning algorithms, 2017.
Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent Ghaoui, and Michael I Jordan. Theoretically principled trade-off between robustness and accuracy. arXiv preprint 19110:1901.08573. 2019.
11

---

Under review as a conference paper at ICLR 2022
A PROOFS
Proof of Lemma / Suppose that == ((u, (u, -1) E &. Then, there are some 2 E 2, E (u)).
and ū E (v)) such that f()) = f(ö) = 2. We have qu S h((( = h(3) Ou S h(f(())-1 h(z) and h(3) + h(ū) = Combining these gives the constraint (Bq)e S 1, which appears in
Now, we will show that each vector q the polytope is achievable by some The construction is simple: at each point in the feature space, assign the largest possible probability class 1: let h(2)1 = sup fu (w)) qu and h(2) = h(2)1 This achieves the desired performance for examples from class 1:
sup qw 2 inf qu qu- inf h(f(ū)) (EN(u) wn ((N)(( (EN(u)
inf
uEN
For an example is v in class -1 we have
inf ((((8)-1= = inf 6EN(2)
sup (N)())) (1 qw0
Jwi
sEN(e)
inf GEN(u) w: (c)(())((N()))
inf
w:((w.1),0,,1))ee) -ww)
inf
qv-
The final inequality uses the fact that satisfies Bq S 1.
B INDUCED DISTANCE IS NOT A DISTANCE ON Z
The fact E? is defined on X' is essential. It is not possible to interpret the induced distance as distance in the feature space 2. This is because f((N())), the set of features of points near x, cannot be derived from f(No(z)), the set of features of the uncorrupted version of x. This is because distinct choices of x may lead to the same features f(N((1)), but f may vary more in the neighborhood one choice of x that the other.
example is helpful to illustrate this point. Let x let 2 IR, let (x) be the closed la ball of radius around z, and let f(z0, arctan(z1/zy for * 0 (the value that we pick for f(0, x1) is irrelevant). In other words, ff finds the angle between the horizontal axis and the line containing The range of values that the adversary
cause f(ă) to take depends | If || < e. f()) can be any angle from 0 to n, and |a||z 2 e, (f()) f(x)] S arcsin(e/|I<rlla
This example also illustrates that Ey is not necessarily metric, Given u, E RR2, we have ey,u, om)) 0, E ( ar) 0, and é (oru, av) can be made arbitrarily small by selecting a to be small. Despite this, s(u, v) will be on the order of min([[u/], ||,]]]..
in cases where is metric.
An alternative approach to studying the induced distance is to define adversarial classification problem on Z by taking (z) [[N[[ (f Note that this construction only makes sense when X X and thus the domain of f is X. This is more conservative: for any feature point z considers the worst-case with feature 2: the in whose neighborhood, varies the most.
C DESCENT ALGORITHM FOR MULTIPLE LAYER NETWORKS
We start by repeating the notion used in Section 3.2 f = -())... o...o o f()) where the layer function
f(8) I. + - (z) (k-(+) + I 2)+ + Then (u v) is the value of the following
optimization problem:
mins subject to ê E sB, 8' E =B, (10.... (u +0) 8) = ( (v
Using the local linear approximation, the equality constraint becomes
(iag(s()))k) + (9 diag(s + ( (u +))))
diag(s (1)) I (0) diag(s + [() 6')))).
12

---

Under review as a conference paper at ICLR 2022
and for each 1 < S the inequalities
(2 (2aags( T)(k + diag(s + ( (u +)))) 2 0 (v 8')))) 2
(2 diag(s" () + ( di...dssss
must hold in order for the linear approximation to be valid. Any collision must be in a polytope with g(*) s'((), which is why we only needed one set variables in the single layer case. However, ReLU activation variables for earlier layers cannot be merged.
The main modification to algorithm is to the process of changing the s variables after each iteration. The variables for all but the final layer allowed change independently, while the variables in the final layer are changed together following the same rule as in the single layer algorithm.
Algorithm 2 Descent with midpoint initialization
Input: u, E R L E Ro2xx1, k R=2 Output: 8 E IR
E Rd I: +-4- k [L + +v),++ 2 - xll
2: for J n2 do
3:
8; 4 1(2g 0),
4: end for
5: repeat
6:
gold 6
7:
(5,6, 6, 8' 1,2,,² x') - ConeL ... L(9, k(1) ...1(9) u, u, 8 ... .00 5 ((-)))
gold f 8
8:
9:
for S i <
1 do
10:
for 0 < j
< 11++1 do
(1)
> 0 then
(6)
(i)
13:
end
if
14:
if
> 0 then
15:
+ - 8j
16:
end if
end for
18:
end for
19:
for
j ne+1 do
20:
if ) > and = then
21:
+ 1 sj
22:
end
23:
end for
24:
until godd 8 or old =
D CONVERTING COLLISION FINDING TO A LINEAR CONE PROGRAM
In this section, demonstrate how the collision finding problem after one linear and one ReLU layer can be cast as a linear cone program.
We have network with first layer Lv + l where L R and R
Given a pair of points (v', v") E 2 we would like to search over the space of (8',8") e 2 such that (L(v' + +0)) k)+ (L(v" + 8") - k) This space is always nonempty because
take v + 8' = + = (v' + /
Let S C [na] be the subset of active ReLUs. Let F E x| be the inclusion indicator matrix for the subset: Fi, if and only if S and [S n [5]l i (there are exactly elements of strictly smaller than j. so j is the + 1st element of S). Let D be the diagonal matrix with D = for j E and D33 -1 for S.
13

---

Under review as a conference paper at ICLR 2022
For S (the active ReLUs), need the constraint (L(v' + 8)) k); (L(e' + 8') + k)5. In
matrix form, this is FL(o' + 8') = FL(e" + +8),
For j E S. need (L(v' + 8') + k) 0, (L(e" + 8") + 2 0. and for & S. need
(L(e' + 8') + k)j 2 0, (L("" + 8") + =)j S
In matrix form, these are D(L(v' + 8') + k) 2 0,
D(L(e" + +8")
Our objective is max([10'112 12. [18")12). We will replace with a linear objective by adding two additional variables (t', t") satisfying t' 2 |8%) and t"
12
The evx-opt system is
minimize d'r subject to Gx + 8 = h
Ar b
8 82 0
The cones involved are nonnegative orthant of dimension 2n, and two second order cones, each
of dimension no + Thus (D(L(e' + 8') + k), D(L(v" + 8") + k). t'. 8', "',',,,,""" 8"). We
then let x (f, 8', 8"). The matrix relating and is G ho))
and
= h Gr. The block structure is
DL
0
D(La' + k)
DL
D(Le" +k)
0
0
G
-1
0
0
-1
0
0
-I
We Ar = b encode FT.(6' 8") -FI(V' - -²)), so A (1 b RISI, and
(0 FL -FL) b= b=-FL(y -1").
Finally,
D.1 FACTORIZED I.
ni < no, then we can take advantage of the fact that the rank at most n1. Let = UEVT.
Replace L(v + 8) with US(V" + e), no with size of E.
New and A:
0
DUE
O
0
DUE
-1
0
G
= FUY -FUE)
-1
0
0 -T
Also, the length of e is reduced. The constant vectors h and are unchanged.
E FURTHER EXPERIMENTAL DETAILS
We consider the following two architectures for our experiments:
3-layer fully connected neural network (FCNN): 300 FC-ReLU-200 FC-ReLU-2 FC
2. layer convolutional neural network (CNN): 20x5x5 conv-BN-ReLL- 2x MaxPool- 50x5x5 Lonv-BNNRReLL 2x2 MaxPool- 500 FC 2 FC
We also construct a 'Small' and 'Smaller' version the FCNN with layers that are 2x and 4x narrower respectively.
14

---

Under review as a conference paper at ICLR 2022
06
Eaxtspas
Seaal
Reg.
Small,
Rck- 73
Sendls -0
Ras Fi.
Scaal:: FL.
-
Seutler
Seal. FL
Seales
Sanh
Sendkn. 58
25
25
(a) MNIST
(b) Fashion MNIST
Figure 6: Robustness of the representations obtained from fully connected networks with layers of
decreasing size.
lagal gaac
ARI 1.0 D5
07
Adc.
03
Ads maas.
Ars
TRADES 1.0
05
TRANES
TRADES
DJ
03
ILE
011
25
53
25
MNIST
(b) Fashion MNIST
Figure 7: 0 - 1 Loss: Robustness of the representation obtained from the first linear layer of 3-layer FCNN using different training procedures
F ADDITIONAL RESULTS
F. IMPACT OF REDUCTION OF NETWORK SIZE
In Figure 0 we compare the robustness of representations obtained from fully connected networks with decreasing layer sizes. The 'Regular' network is the one used throughout, while the 'Small' and 'Smaller' networks have corresponding layers that are 2x and 4x narrower respectively. We can clearly see that as the width the feature extractor decreases, so does its robustness.
F.2 0 LOSS RESULTS
In Figures g and 10 provide lower bounds the 0 loss in the same settings those considered in the main body of the paper. We note that the results and conclusions remain the same qualitatively.
F.3 LINEAR CONVOLUTIONAL LAYERS
see that the representations extracted from the first linear layer of convolu- tional network not have any negative impact on the robustness the overall model.
In Figure I]
15

---

Under review as a conference paper at ICLR 2022
tbear Secoed Sccial Rel.1
Fine Jecr Lince Seaee K:U
06
0.6
114
7.5
(a) MNIST
(b) Fashion MNIST
Figure 8: 0 Loss:
Robustness of representations obtained from different layers of 3-layer FCNN trained using benign training
Fid Uhwar Secoed
Diee Bear
065
Sazai Bel.l
0.6
Stoed Linoe
Saats KAU
144
0.
02
02
255
2.5
(a) MNIST
(b) Fashion MNIST
Figure 0 1 Loss: Robustness of representations obtained from different layers of 3-layer FCNN trained using PGD adversarial training with = 2.0
Besaen tradig
Bcoan masgg
86
2.0
06
Adc tai. 3.0
TRADS 20
TRADES
TRADES
2.0
04
022
02
2.5
(a) MNIST
(b) Fashion MNIST
Figure 10: Loss: Robustness of the representation obtained from the second ReLU layer of 3-layer FCNN using different training procedures.
0.6
Adh: main,
1.0
Aft wit
1.0
Jul: traes
3.5
35
(a) MNIST
(b) Fashion MNIST
Figure 11: Robustness of the representation obtained from the first linear layer of 4-layer CNN using different training procedures.
16


Reviews:
[{"review_id": "kJvRYmSY5nD", "reviewer": "Reviewer_nQgV", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength:\n- The authors develop a reasonable algorithm for constructing the conflict graph for a specific fixed feature extractor.\n\nWeakness:\n- Motivation of calculating the lower bound on the adversarial loss for the fixed feature extractor is somewhat unclear.\n- The paper lacks the analysis for justifying the proposed algorithm.\n\n\nMy current decision is acceptance. However, the motivation of the fixed feature extractor is unclear for me. I'd like the authors to clarify the motivation for calculating the lower bound on the adversarial loss with the fixed feature extractor.\n\nThe motivations in the related works, including Pydi & Jog 2020 and Bhagoji et al. 2019;  2021, are understandable. The lower bounds on the Bayes optimal adversarial loss are useful for evaluating the performance of the robust learning algorithms and for confirming the fundamental limit of the robustness. The lower bound investigated in this paper is no longer the fundamental limit. Because there is no necessity to employ the pre-trained feature extractor, I cannot imagine the situation where the use of the given feature extractor is enforced. So, I'm wondering if such a lower bound is useful for evaluating something. In the experiments, the authors evaluated the lower bounds with fixed first 1 or 2 layers as usage of the proposed method; however, it is unclear how to use the evaluated adversarial loss. \n\nThe theoretical result, i.e., Lemma 1, is the straightforward extension of Bhagoji et al. 2021's result. The theoretical contribution of this paper seems to be incremental.\n\nThe main contribution of this paper is the algorithm development shown in Section 3. The authors provide the reasonable construction of the algorithm for certifying the existence of the specific edge in the conflict graph. However, it is non-trivial that the present algorithm converges to the desired solution. It is necessary to clarify this point. \n\n\nMinor comments:\n- In the second paragraph on page 3, the right bracket is missing in the adversarial loss.", "summary_of_the_paper": "This paper investigates the lower bound on the adversarial loss with the given specific feature extractor.  The authors develop an algorithm to compute such a lower bound for the feature extractor employing the forward feed network with ReLU activation. The experiments demonstrate the usage of the proposed algorithm.", "summary_of_the_review": "My current decision is acceptance. However, the motivation of the fixed feature extractor is unclear for me. I'd like the authors to clarify the motivation for calculating the lower bound on the adversarial loss with the fixed feature extractor.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "SZ64M0zwlAv", "reviewer": "Reviewer_btdg", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper begins by analyzing linear feature extractors, which is a simpler case that can be analyzed theoretically in full, but is not directly applicable to the non-linear case. For the non-linear case, the paper uses gradient descent to try to find collisions, which is reasonable; the authors may want to include a citation to [1], which has also previously tried to find collisions in representations via a different gradient descent algorithm on inputs.\n\nThe main algorithm (Algorithm 1 in the paper) appears reasonable, but I have some questions about it. In particular, in line 10, it appears to cause branching for every ReLU. How does this algorithm scale with the number of ReLUs? Will it scale exponentially? If so, it is worth mentioning, as this is often a limitation of related methods that involving branching for every ReLU. For example, exact certification of neural network robustness is shown to be NP-hard in [2].\n\nThe experimental results in this work are primarily focused on very basic datasets (MNIST and Fashion-MNIST), so it is unclear how results will generalize to larger datasets (CIFAR, ImageNet). The networks used are also usually simple 3 layer networks; I think the paper could be made more convincing with either (1) experiments on more complex datasets/models and/or (2) discussion/experiments showing how this approach scales as model size/dataset complexity increases. For example, how does the proposed algorithm scale for deeper networks? Could it feasibly be scaled up to find collisions for ResNets or deeper ConvNets?\n\nFinally, the authors draw conclusions regarding how various layers contribute to (lack-of) robustness. I think this section is very interesting, but I think deeper investigation is necessary to draw such conclusions. In particular, the authors focus on how their robustness loss lower bound changes depending on the structure of each layer, but this robustness lower bound is merely a proxy for true robustness. Thus, concluding that certain properties of each layer affect true robustness is too strong, and should be qualified further. In particular, the implications for how to train robust models section is interesting, and it may be worthwhile to try to find supportive experimental evidence to see whether insights derived from analyzing the robustness lower bound help.\n\nSmall Comments and Questions:\n- You repeat “are fixed” before and after the parentheses in the 4th-to-last line of page 1\n- In Figure 3a/b, the blue line is missing\n- You mention that “convolutional networks are more robust than fully connected ones” is “commonly held wisdom” - is this actually true? Usually, adversarial attacks are capable of completely breaking both types of networks.\n\n[1] https://arxiv.org/abs/1906.00945 Adversarial Robustness as a Prior for Learned Representations (Logan Engstrom, Andrew Ilyas, Shibani Santurkar, Dimitris Tsipras, Brandon Tran, Aleksander Madry)\n\n[2] https://arxiv.org/abs/1702.01135 Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks\nGuy Katz, Clark Barrett, David Dill, Kyle Julian, Mykel Kochenderfer\n\n\n=========================================================================\n\nI thank the authors for the rebuttal. After reading the rebuttal and other reviewer comments, I have decided to maintain my score of \"weak reject\". As Reviewer r9vz noted, a lot of the most interesting work is left as \"future work\" at the moment; it is still unclear to me whether this approach will scale effectively to more complex datasets (CIFAR/ImageNet vs. MNIST/Fashion-MNIST) or more standard and modern architectures (CNNs, resnets vs. 3-layer fully-connected networks).", "summary_of_the_paper": "This paper analyzes the robustness of fixed feature extractors (e.g. all but the last layer of a pre-trained network). They do so by attempting to find pairs of inputs that have collisions (at some later layer of the network). By analyzing these collisions in both simpler cases and in more general cases, the authors argue that they can also pinpoint what properties of certain layers contribute to lack-of-robustness, including dimensionality reducing layers, different adversaries at train/test, and ReLUs.\n", "summary_of_the_review": "I recommend a weak reject due to the fact that the datasets and models used in this paper are too simplistic; understanding how this method scales as those factors change will improve the work.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Q-SSlpbxWoL", "reviewer": "Reviewer_r9vz", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Please find my full review of the paper *\"Lower Bounds on the Robustness of Fixed Feature Extractors to Test-Time Adversaries\"* below. Unfortunately I can not recommend the current version of the presented manuscript for acceptance at the ICLR conference. The main contributors to this decision is the unclarity in the contributions of the work, the empirical evidence supporting the claims made being too sparse, and the large amount of crucial work left for future work. \n\nBefore further elaborating on my reservations about the paper I would like to clearly state that I found the paper to be particularly hard to follow. Personally I believe that this is primarily due to the introduction not properly introducing the setting and aims of the paper, but I should also acknowledge that I was not entirely familiar with the work [Bhagoji, 2021] (on which this paper heavily builds) before getting assigned this paper for review. \nFor this reason, I would be very interested in hearing from the other reviewers to what extend they found the paper hard to follow as well. \n\n### Contributions of work\n\nIf I understood correctly, the main contribution of the paper is to provide a lower bound on the adversarial robustness of specific models. This is in contrast with earlier work on adversarial robustness certification that focusses on arbitrary classification functions. While this does sound interesting, I struggle in finding how this differs from performing a simple adversarial robustness evaluation on a model using a standard adversarial attack. This should also provide a lower-bound on the true loss of the model under attack. I would be grateful if the authors could clarify this for me. \n\nThe method by which the authors achieve this lower-bound heavily builds upon earlier work [Bhagoji, 2021]. Again, if I understood correctly, the main contribution of the work presented here is extending this method to small (mostly linear) neural networks using a greedy search algorithm. Given that there is not true evaluation presented of how efficient this search algorithm is, I find it difficult to evaluation the significance of this contribution. \n\n### Empirical Evidence\n\nThe authors use their proposed method for determining a number general statements about layers that hypothetically lead to a measurable drop in robustness. Based on the rigour of the presented empirical evaluation, I do not believe that these general claims can be made. In general, the method proposed by the authors is only applied to a very limited set of network architectures. The models evaluated in the paper are in general very shallow and in my opinion not representative of architectures used in practice. For example, the architecture used is only applicable for binary classification. \n\nThe fact that this limitation of the architecture is not clearly communicated in the main body of the paper is something that I find to be especially troubling. \n\n### Future work\n\nLastly, I believe that the current version of the manuscript, unfortunately, leaves most of the interesting for future work. For example, the extension to CNNs, BatchNormalization and Residual Blocks is left for future work. With these often applied layers pushed to future work, I find it hard to judge the applicability of the presented method.\n\n\n# Updates after rebuttal\nI've increased my score. Please see the comment chain for further clarification. ", "summary_of_the_paper": "The authors present a method for deriving a lower bound on the loss of a specific model architecture under adversarial attack. The method heavily relies on previous work [Bhagoji, 2021]. The main contribution of the paper is therefore extending the concepts presented in [Bhagoji, 2021] for evaluating the input of a model to the output of later layers. \nUsing their proposed method the authors perform an evaluation of the robustness of a simple feature extractor.", "summary_of_the_review": "The contributions of the paper are unfortunately unclear. In addition to this, based on the empirical evaluation, the made claims are to general. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "BjxC6sFe6dR", "reviewer": "Reviewer_8XE9", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\n- This paper expands on previous theory while making it directly applicable to neural networks that are commonly used.\n- They provide an algorithm that calculates lower bounds on robustness for real networks.\n- Experimental results on multiple datasets and robust training algorithms are provided, comparing how close the different methods are to their theoretical lower bounds.\n- Based on their experimental results, they discuss implications for model training. Specifically they note that ReLU seems to reduce the robustness of features in later layers of the network.\n\nWeaknesses:\n\n- There is no discussion of other network architectures for which this method does not work. The method seems to work on the fact that ReLU layers reduce the dimensionality of the space that must be searched for collisions, so it would be interesting to hear about other activation functions for which that is not the case. The subsection \"Other neural network architectures\" only seems to cover networks where this method works. It also seems to require that the entire network (including activation functions) be expressible as a series of matrix multiplications, so I'm not sure of the applicability of this to architectures with, for example, attention.\n\n- Some notation and definitions are unclear or hard to follow. For example, in section 3: \"We take the neighborhood of any point to be a scaled shifted version of this ball: N_\\epsilon(x): n + \\epsilon \\mathcal{B}\", but x is missing from the right hand side.  \n\nIn subsection 3.2 \"... satisfying the constraint f(u + \\delta) = f(v + \\delta)\" seems like it should be \"f(u + \\delta) = f(v + \\delta')\". \\epsilon seems to be a bit overloaded as well, where it is a function of two points in section in 2.1 and later a real number. \n\nIn equation 1 in lemma 1, since q is a vector, are the inequalities acting coordinate-wise on the vector? In that case, is q a vector in \\[0, 1\\]^\\mathcal{V}? I have a similar question regarding the equation in definition 1, as q is also a vector in an inequality with a real number and another vector.\n", "summary_of_the_paper": "This paper adapts previous work on the lower bounds  of robustness from any possible measurable function to commonly used neural architectures for image classification. In order to do this, they create an algorithm based on linear programming to find collisions in feature representations at different layers in neural networks. Once the collisions are found, the minimum achievable loss by a classifier using these features is computed. Experiments are done on fully connected neural networks trained on MNIST and Fashion MNIST with standard and robust training methods. The authors find that adversarial training produces features closer to their predicted lower bound than networks trained with TRADES loss or with standard training.", "summary_of_the_review": "This paper provides an important application of previous work while also introducing a practical algorithm to find collisions in feature space and calculate a lower bound of adversarial robustness. While neural network architectures for which this algorithm is not applicable seem to be ignored and some notational issues made it take longer to read, I think the paper should be accepted.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "-8xsnHSH2sV", "reviewer": "Reviewer_hh5w", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall I like the idea of the paper: it gives more insights to how different model architecture can affect the robustness lower bound, and thus gives some guidance to how we design a robust system. \n\nOn the other hand, I have difficulty understanding the theoretical part and the algorithmic aspect of the paper. The paper is written in a rather theoretical manner. I hope the authors can comment on my following questions so that I can understand the details better. \n\n1) Does the robustness lower bound depend on the underlying data distribution? Intuitively, the collision graph shows that whether two instances in the space can have the same representation after perturbation. However, it's possible that 1) u, v have collision but 2) u, v will never appear in natural samples. I don't see an explicit link to the input distribution, and therefore hope the authors to clarify what this robust entropy is measuring.\n\n2) Are the robust entropy evaluated on the training dataset? What's the relation of this empirical value to the theoretical value over the distribution? I know that the full graph will only have more collision, but the probability of each node appearing can change too. Therefore, the relation is not immediately clear to me.\n\n3) In Section 3.1, the algorithm solves an optimization problem using descent. My questions is, how does the outcome of this algorithm translate to the figures in Sec 4? Or rather, how is Figure 2 produced out of the outcome of Algorithm 1? (Sec 4 gives a pointer to Bhagoji et.al, but it would be good to summarize the key steps in this procedure.)\n\n", "summary_of_the_paper": "This paper investigates the lower bound of robustness, i.e. the best robustness we can expect, with the added constraints of model architecture. It derives an algorithm of estimating the lower bound, and empirically shows how various types of layers -- such as linear, ReLU and convolutional layer -- can impact the lowerbound.", "summary_of_the_review": "Overall I find the idea interesting and the results reasonable. Once my questions are addressed, I can offer better advice on the paper organization. I'm giving a score of 5 now, but I'm willing to raise the score after my questions are answered.\n\n===================================================\n\nAfter viewing the author response, my technical questions are resolved. I'm raising the score to 6 for the completeness in the idea. The paper can be enhanced by considering considering more data sets. MNIST and FashionMNIST is slightly too simple. The in-sample v.s. distributional robustness can be an interesting future direction to explore too. Currently it's addressed by using a practical attack algorithm as a probe. More explanation to this end can enhance the paper too.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Thank you for your submission to ICLR.  The reviewers were split on this paper, with more favoring acceptance but with relatively low confidence.  After reading through the paper and reviews, I tend to agree slightly more with the more critical comments.  The paper is very much on the borderline, but ultimately 1) the rather incremental nature of the work compared to [Bhagoji, 2021], and 2) the rather small-scale evaluations in the current version, which the field has largely moved on from as they often give overly-optimistic impressions of certified robustness.  Ultimately a lot of the extensions (which at this point are fairly standard in most methods for deep network verification), seem like they should really be taken into account in the current paper.  For these reasons I lean slightly towards not accepting the paper in its current state.
Decision: Reject