Asymmetric Certified Robustness via Feature-Convex Neural Networks
Authors: Samuel Pfrommer
Brendon G. Anderson
Julien Piet
Somayeh Sojoudi
Venue: NeurIPS 2023 poster (2023)
Keywords: asymmetric certified robustness
input-convex neural networks
TL;DR: This work composes input-convex neural networks with a Lipschitz feature map to produce a classifier with closed-form asymmetric certified radii for any norm.

Abstract: Real-world adversarial attacks on machine learning models often feature an asymmetric structure wherein adversaries only attempt to induce false negatives (e.g., classify a spam email as not spam). We formalize the asymmetric robustness certification problem and correspondingly present the feature-convex neural network architecture, which composes an input-convex neural network (ICNN) with a Lipschitz continuous feature map in order to achieve asymmetric adversarial robustness. We consider the aforementioned binary setting with one "sensitive" class, and for this class we prove deterministic, closed-form, and easily-computable certified robust radii for arbitrary $\ell_p$-norms. We theoretically justify the use of these models by characterizing their decision region geometry, extending the universal approximation theorem for ICNN regression to the classification setting, and proving a lower bound on the probability that such models perfectly fit even unstructured uniformly distributed data in sufficiently high dimensions. Experiments on Malimg malware classification and subsets of the MNIST, Fashion-MNIST, and CIFAR-10 datasets show that feature-convex classifiers attain substantial certified $\ell_1$, $\ell_2$, and $\ell_{\infty}$-radii while being far more computationally efficient than competitive baselines.

Asymmetric Certified Robustness via Feature-Convex Neural Networks
Samuel Pfrommer"
Brendon G. Anderson"
Julien Piet Somayeh Sojoudi
University of California. Berkeley
[sam, pfrommer, bggndeeee,,aannssooo bgwnderson, piet, sojoudi)]berkeeey.. edu
Abstract
Real-world adversarial attacks on machine learning models often feature an asym- metric structure wherein adversaries only attempt to induce false negatives (e-g., classify a spam email as not spam). We formalize the asymmetric robustness certification problem and correspondingly present the feature-conver neural net- work architecture, which composes an input-convex neural network (ICNN) with Lipschitz continuous feature map in order to achieve asymmetric adversarial robustness. We consider the aforementioned binary setting with one "sensitive" class, and for this class we prove deterministic, closed-form, and certified robust radii for arbitrary lp -o-nosss We theoretically justify the use of these models by extending the universal approximation theorem for ICNN regression the classification setting, and proving lower bound on the probability that such models perfectly even unstructured uniformly distributed data in sufficiently high dimensions. Experiments on Malimg malware classification and subsets of the MNIST, Fashion-MNIST. and CIFAR- 10 datasets show that feature-convex classifiers attain substantial certified 4, l, and radii while being far more computationally efficient than competitive baselines.
1 Introduction
Although neural networks achieve state-of-the-arr performance across range of machine learning tasks, researchers have shown that they can be highly sensitive to adversarial inputs that are mali- ciously designed to fool the model [1T 61 (2). For example, the works Eykholt et al. [22] and Liu et al. [42 show that small physical and digital alterations of vehicle traffic signs can cause image classifiers fail. In safety-critical applications of neural networks, such autonomous driving and medical diagnostics 71). this sensitivity to adversarial inputs is clearly unacceptable.
12 69
A line of heuristic defenses against adversarial inputs has been proposed, only to be defeated by stronger attack methods [14] 36
7 64 46). This has led researchers to develop certifiably robust methods that provide provable guarantee of safe performance. The strength of such certificates be highly dependent on network architecture; general off-the-shelf models tend to have large Lipschitz constants, leading to loose Lipschitz-basee robustness guarantees 29
Consequently. lines of work that impose prrificate-amenall structures onto networks have been popularized, e.g., specialized model layers [63] 777, randomized semoothinn-bbseld networks 4 18
76
72
3 and
RcLU networks that are certified using convex optimization and mixed -ittger programming [68 67
The first category only directly certifies against one specific choice of norm, producing poorly scaled radii for other norms in high dimensions. The latter two approaches incur serious computational challenges: randomized smoothing typically requires the classification of thousands
54 4 [45
"qqual contribution.
Code for reproducing our results is available on GitHuu
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

of randomly perturbed samples per input, while optimization- based solutions scale poorly to large networks.
Despite the moderate success of these certifiable classifiers, conventional assumptions in the literature unnecessarily restrictive for many practical adversarial settings. Specifically, most works consider a multiclass setting where certificates are desired for inputs of any class. By contrast, many real-world adversarial attacks involve binary setting with only one sensitive class that must be robust to adversarial perturbations. Consider the representative problem of spam classification; a malicious adversary crafting a spam email will only attempt to fool the classifier toward the "not-spam" class never conversely [20]. Similar logic applies for a range of applications such as malware detection (28). malicious network traffic filtering [56]. fake news and social media bot detection [1)) hate speech removal (27), insurance claims filtering (24), and financial fraud detection [[5].
The important asymmetric nature of these classification problems has long been recognized in various subfields, and some domain-specific attempts at robustification have been proposed with this in mind. This commonly involves robustifying against adversaries appending features to the classifier input. In spam classification, such an attack is known as the "good word" attack [44]. In malware detection, numerous approaches have been proposed to provably counter such additive-only adversaries using special classifier structures such as non-negative networks [25] and monotonic classifiers 32). We note these works strictly focus on additive adversaries and cannot handle general adversarial perturbations of the input that are capable of perturbing existing features. We propose adding this important asymmetric structure to the study of norm ball-certifiably robust classifiers. This narrowing of the problem to the asymmetric setting provides prospects for novel certifiable architectures, and we present feature-convex neural networks as one such possibility.
1.1 Problem Statement and Contributions
This section formalizes the asymmetric robustness certification problem for general norn-bounded adversaries. Specifically, we assume binary classification setting wherein one class is "sensitive" meaning we seek to certify that, if some input is classified into this sensitive class, then adversarial perturbations of sufficiently small magnitude cannot change the prediction.
Formally, consider a binary classifier fy: Rd + {1,2). where class is the sensitive class for which we desire certificates. We take f- to be a standard thresholded version of a soft classifier g: Rd - R, expressible as f- (z) = T- (g())), where T,: R- + {1,2} is the thresholding function defined by
1 if f 0,
(v)
(1)
2 ffy+r50 0.
with 7 E R being a user-specified parameter that shifts the classification threshold. A classifier fr considered certifiably robust at a class input x E IR" with a radius r(x) E R. if f= + 6) fr (x) = 1 for all d E IRd with || < r(x) for some norm || ||. Thus, 7 induces a tradeoff between the clean accuracy on class 2 and certification performance on class 1. As T + cc, fr approaches a constant classifier which achieves infinite class certified radii but has zero class 2 accuracy.
For a particular choice of T, the performance of fr can be analyzed similarly to a typical certified classifier. Namely, it exhibits class 2 clean accuracy (r) E [0, 1] as well as class 1 certified accuracy surface I with values T(r, 7) E [o, 1] that capture the fraction of the class samples that can be certifiably classified by fr at radius inferable from I' as the certified accuracy at r = 0.
R... The class 1 clean accuracy (T) = [(0, r) is
The full asymmetric certification performance of the family of classifiers f- can be captured by plotting the surface I'(r, r). as will be shown in Figure La] Instead of plotting against 7 directly, we plot against the more informative difference in clean accuracies a (r) - (T). This surface can be viewed as an asymmetric robustness analogue to the classic receiver operating characteristic curve.
Note that while computing the asymmetric robustmess surface is possible for our feature- convex archi- tecture (to be defined shortly), it is computationally prohibitive for conventional certification methods. We therefore standardize our comparisons throughout this work to the certified accuracy cross section T(r, r") for a a such that clean accuracies are balanced the sense that a2(7") = an (r*), noting that on monotonically increases in and (22 mononically decreases in We discuss finding such 7" in Appendix E.4 This choice allows for a direct comparison of the resulting certified accuracy curves without considering the non-sensitive class clean accuracy.

---

With the above formalization in place, the goal at hand is two-fold: 1) develop classification architecture tailored for the asymmetric setting with high robustness, as characterized by the surface r, and 2) provide efficient methods for computing the certified robust radii r(x:) used to generate l'
Contributions. We tackle the above two goals by proposing croposingfecture-ccovee neural networks and achieve the following contributions:
1. We exploit the feature- structure of the proposed classifier provide asymmetrically tailored closed-form class certified robust radii for arbitrary lp-norms, solving the second goal above and yielding efficient computation of T.
2. We characterize the decision region geometry of convex classifiers, extend the universal approximation theorem for input-convex ReLU neural networks to the classification setting, and show that convex classifiers are sufficiently expressive for high-dimennional data.
3. We evaluate against several baselines on MNIST 3-8 [37, Maling malware classification [50], Fashion-MNIST shirts 770), and CIFAR-10 10 cats-dogs [35, and show that our classifiers yield certified robust radii competitive with the state-of-the-ane empirically addressing the first goal listed above.
All proofs and appendices can be found in the Supplemental Material.
1.2 Related Works
Certified adversarial robustness. Three of the most popular approaches for generating robustness certificates are Lipschitz-ber baasee bounds, randomized smoothing, and optimization baazza methods. Successfully bounding the Lipschitz constant of neural network can give rise efficient certified radius robustness, e.g., via the methods proposed in Hein and Andriushchenko practice such Lipschitz constants burdensome to compute or bound the Lipschitz constants in the first place [65] 23
[29]. However, in too large to yield meaningful certificates, it is computationally
73). To overcome
these computational limitations, certain methods impose special structures on their model layers to provide immediate Lipschitz guarantees. Specifically, Trockman and Kolter 663 uses the Cayley transform derive convolutional layers with immediate fz-Lipschitz constants, and Zhang al. [77 introduces a -distannc neuron that provides similar Lipschitz guarantees with respect to the 2x -norm. We compare with both these approaches in our experiments.
Randomized smoothing, popularized by Lecuyer et al. [38] Li et al. [1)), Cohen et al. 18 uses the expected prediction of model when subjected to Gaussian input noise. These works derive fnrm balls around inputs on which the smoothed classifier remains constant, but suffer from nondeterminism and high computational burden. Follow-up works generalize randomized smoothing certify input regions defined by different metrics, e.g., Wasserstein, f1-, and E (39
62
72 Other
works focus enlarging the certified regions by optimizing the smoothing distribution 776
[5]
incorporating adversarial training into the base classifier [57] 78]. and employing dimensionality
reduction the input (53)
Optimization- based certificates typically seek to derive a tractable over-approximation of the set of possible outputs when the input is subject to adversarial perturbations, and show that this over- approximation is safe. Various over-approximation have been proposed, e.g., based on linear programming and bounding 68 67). semidefinite programming [54]. and maach-and-bouut 45 66). The ax, B.-RROW method [66] uses an efficient bound propagation to linearly bound the neural network output in conjunction with a per-neuron branching heuristic achieve state-of- the-art certified radii, winning both the 2021 and the 2022 VNN certification competitions [8] 48) In contrast to optimization-basel methods, our approach directly exploits the convex structure of input-convex neural networks to derive closed-form robustness certificates, altogether avoiding any Efficiency-tightnes tradcoffs.
[4]
Input-convex neural networks. Input-convex neural networks, popularized by Amos et al. (2). are a class of parameterized models whose input-output mapping is convex. The authors develop tractable methods to learn input-convex neural networks, and show that such models yield state-of- the-art results variety of domains where convexity may be exploited, e.g., optimization-bal inference. Subsequent works propose novel applications of input-convex neural networks in areas
3

---

such as optimal control and reinforcement learning 16 75 optimal transport 47 and optimal power flow [7 79). Other works have generalized input-convex networks to input-invex networks [58 51 and global optimization networks [80] so as to maintain the benign optimization properties
of input-convexity. The authors of Siahkamari et al. [59] present algorithms for efficiently learning convex functions, while Chen et al. [6]. Kim and Kim
R derive universal approximation theorems for input-convex neural networks in the convex regression setting. The work Sivaprasad et al. [60] shows that input-convex neural networks do not suffer from overfitting, and generalize better than multilayer perceptrons on common benchmark datasets. this work, we incorporate input-convex neural networks as a part of our feature-conver architecture and leverage convexity properties to derive novel robustness guarantees.
1.3 Notations
The sets of natural numbers, real numbers, and nonnegative real numbers are denoted by N, R, and R,+ respectively. The d x d identity matrix is written as Ia E Raxd and the identity map on Rd is denoted by Id: x + x. For A E Raxd, we define |A| E Raxd by |Alis = -Asyl for all j, and we write A 2 0 if and only if Auj 2 0 for all i,j. The l--norm on R2 is given by -|- Ipp: x + (1211/ +...+............ |x2/)) for p [1, oo) and by || 1Ip + max[[ 1,..... |raB for p == oc. The dual norm of || ||p is denoted by llp.-- The convex hull of set X Rdd is denoted by cX) The subdifferential of convex function g: Rd - R at x E Rd is denoted by 0g(x)) ef: Ω + Rd is random variable on probability space (2, B,P)) IP) and P is predicate defined on Rd, then we write P(P(e)) to mean P[[w E Q P(e(w)))) Lebesgue measure on R is denoted by m. We define ReLU: R- + R as ReLU(() (e)U(x)) denotes (ReLU(z))) ..... ReLUU(a)) We recall the threshold function Ty: R + {1,2} defined by ( and we define T To. For function yp: Ie + R" and p E [1, 00),
max x}, and if x E gd
define (T) inf K 2 0 [1<)(=) p(x'))>> S K|| x' z'Ilp for all x;, x' E RR), and if Lip, < oo we say that yp is Lipschitz continuous with constant (Vp) (with respect to the f fp-norm).
2 Feature-Convex Classifiers
oo] be fixed, and consider the task of classifying inputs from a subset of Rd into a fixed set of classes y S N. In what follows, we restrict to the binary setting where Y = (1 and class 1 is the sensitive class for which we desire robustness certificates (Section [ In Appendix A we briefly discuss avenues to generalize our framework to multiclass settings using one-versus-all and sequential classification methodologies and provide proof-of-concep example for the Maling dataset.
Let d, q E and p E [o]
We now formally define the classifiers considered in this work. Note that the classification threshold 7 discussed in Section I.I is omitted for simplicity.
Definition 2.1. Let f: Rd > {1. 2} be defined by = T(g()((((((()) for some ;: IR + R and some g: R2 - R. Then f is said be a feature-conver classifier the feature map o Lipschitz continuous with constant Lip,, < oo and g is a convex function.
We denote the class of all feature-conver classifiers by F. Furthermore, for q = d, the subclass of all feature-conver classifiers with = Id is denoted by Fia-
As we will in Section 3.1 defining our classifiers using the composition of a convex classifier with a Lipschitz feature map enables the fast computation of certified regions in the input space. This naturally arises from the global underestimation of convex functions by first-order Taylor approximations. Since sublevel sets of such are restricted to be convex, the feature map yp is included to increase the representation power of our architecture (see Appendix for a motivating example). In practice, we find that it suffices to choose &p to be a simple map with a small closed- form Lipschitz constant. For example, in our experiments that follow with q = 2d, we choose ((()) (x μ. x (i)) with a constant channel- dataset mean μ4, yielding Lip, (P) < 2, Lip, (g) < 22, and Lip (1) < 1. Although this particular choice of yp is convex, the function need not be monotone, and therefore the composition g o &p nonconvex in general. The prediction and certification of feature-conver classifiers are illustrated in Figure lb

---

Prediction
Input
(Lipschitz) Feature space
(Convex)
Logit
space
1.0
Cortaled acouracy
0.6
((p(2))
0.2
2oo
0.4
Clean acessaacy Offfernnce
0.2
Input
Lipschitzaass
Feature
Convexity
Margin
certificate
certificate
Gptadios
20
Certification
(a)
(b)
Figure (ab
The asymmetric certified accuracy surface [(r; r) for MNIST 3-8, as described in
Section 1.1 The "clean accuracy difference" axis plots on (1(r) (2(T), and the black line highlights
the certified robustness curve for when clean accuracy is equal across the two classes. (b) Illustration of feature-convex classifiers and their certification. Since g is convex, it is globally underapproximated feature
by its tangent plane at (rx), yielding certified sets for norm balls the higher-dimension space. Lipschitzness of ip then yields appropriately scaled certificates in the original input space.
In practice, we implement feature-convex classifiers using parameterizations of g, which we now make explicit. Following Amos et al. (2). we instantiate g as a neural network with nonnegative weight matrices and nondecreasing convex nonlinearities. Specifically, we consider ReLU nonlinearities, which is not restrictive, our universal approximation result in Theorem 3.6 proves.
Definition 2.2. A feature-comee ReLU neural network is a function f: Rd + {1,2] defined by f(z) T()()()))) with yp: Rdd + IR Lipschitz continuous with constant Lip)(p) oo and g: Rd R defined by
(0x ( (L-1) ((L) (0)
(0 ReLU (A 100 (O
for all 1 (1,2,... L 1} for some E N. > 1, and for some consistently sized matrices A C()) and vectors ((1) satisfying A 2 0 for all I (2,3....,L),
Going forward, we denote the class of all feature-convex ReLU neural networks by F. Furthermore, if q = d, the subclass of all feature-come convex ReLU neural networks with Id is denoted by Fia- which corresponds the input-convex ReLU neural networks proposed in Amos et 22]
For every e F. it holds that ğ is convex due the rules for composition and nonnegatively weighted sums of convex functions [K] Section 3.2], and therefore f F and Aia Fia. The "passthrough" weights ( were originally included by Amos et al. 2 improve the practical performance of the architecture. some our more challenging experiments that follow, we remove these passthrough operations and instead add residual identity mappings between hidden layers, which also preserves
convexity. We note that the transformations defined by A and ( can be taken to be convolutions, which are nonnegatively weighted linear operations and thus preserve convexity 22]
3 Certification and Analysis of Feature-Convex Classifiers
present our main theoretical results this section. First, we derive asymmetric robustness certificates (Theorem 3.1 for our feature-convex classifiers in Section Then, in Section 3.2 we introduce the notion convexly separable sets in order to theoretically characterize the representation power of our classifiers. Our primary representation results give universal function approximation

---

theorem for our classifiers with o Id and ReLU activation functions (Theorem 3.6 and show that such classifiers can perfectly fit convexly separable datasets (Theorem (.7]. including the CIFAR- 10 cats-dogs training data (.8) We also show that this strong learning capacity generalizes by proving that feature-convex classifiers can perfectly fit high-dimensional uniformly distributed data with high probability (Theorem 3.10
3.1 Certified Robustness Guarantees
In this section, we address the asymmetric certified robustness problem by providing class robustness certificates for feature-conee of false negatives in the case that class represents positives and class 2 represents negatives. For example, if in malware detection setting class 1 represents malware and class 2 represents non- malware, the following certificate gives lower bound on the magnitude the malware file alteration needed in order to misclassify the file as non-malware.
classifiers f E F. Such robustness corresponds to proving the absence
Theorem 3.1 Let f E F be as in Definition 2.1 and let a E ( = (a' Rd f(x') = 1}. If (g(((())) R2 is nonzero sub subgradient of the convex function g at (p(x), then f(x ((x+6) 1 for all 6 E Rd such that
g(p(()))
|11|, < <rz))=
Remark 3.2. For f E and x E (-1()), a subgradient Vg(p(=)) E R of g always exists at (p()), since the subdifferential (x)) is nonempty closed bounded convex set, g is finite convex function on all of Ree Theorem 23.4 Rockafellar (55) and the discussion thereafter. Furthermore, if f is not constant classifier, such subgradient Vg(((z)) must necessarily be nonzero, since, if it were zero, then g(y) 2 ((<((z) V)(s<(x))T (v - (p(x)) = g({(xx) > 0 for all y E 12, implying that f identically predicts class 1, which is contradiction. Thus, the certified radius given in Theorem 3.1 is always well-defined in practical settings.
see
Theorem is derived from the fact that convex function is globally underapproximated by any tangent plane. The nonconstant terms in Theorem 3.1 afford an intuitive interpretation: the radius scales proportionally to the confidence g(p(x)) and inversely with the input sensitivity [VV((((z)))l,,,- In practice, Lip,,s)) can be made quite small as mentioned Section 2 and furthermore the subgradient Vg((p(z)) is easily evaluated as the Jacobian of g at yx(x) using standard automatic differentiation packages. This provides fast, deterministic class certificates for any f--norm without modification of the feature-convex network's training procedure or architecture. We emphasize that robustness certificates of Theorem 3.1 are independent of the architecture of S.
3.2 Representation Power Characterization
We now restrict our analysis to the class Fia of fcature-convex classifiers with an identity feature map. This can be equivalently considered as the class of classifiers for which the input-to-logit map convex. We therefore refer to models in Fia as input-comve classifiers. While the feature map is useful in boosting the practical performance of our classifiers, the theoretical results in this section suggest that there is significant potential in using input-convex classifiers as a standalone solution.
Classifying convexly separable sets. We begin by introducing the notion of convexly separable sets, which are intimately related to decision regions representable by the class Fia-
Definition 3.3. Let X1, S Rd The ordered pair (X1, X2) said to be convexly separable there exists nonempty closed convex set X C Rd such that X3 X and X₃ C Rd X.
Notice that it may be the case that pair (X1,X2) is convexly separable yet the pair (X2, X2) is not. Although low-dimensional intuition may raise concerns regarding the convex separability of binary-labeled data, we will soon see in Fact 3.8 and Theorem 33 1h convex separability typically holds in high dimensions. We now show that convexly separable datasets possess the property that they may always be perfectly fit by input-convex classifiers.
Proposition 3.4. For any nonempty closed convex sei X C Rd,, there exists I E Fia such that X f- ( fx E Idd f(x)= 2}. In particular, this shows that if X2) is convexly

---

separable pair of subsets of IR, then there exists f E Fia such that f(x) 1 for all x E X1 and fz) 2or all x E X2.
We also show that the converse of Proposition 3.4 holds: the geometry of the decision regions of classifiers in Fia consists of a convex set and its complement.
Proposition 3.5 Let f E Fia. The decision region under f associated to class 2, namely X = ((2)) = 2 R f(x) = 2}, is a closed convex set.
Note that this is not necessarily true for more general feature-convex architectures with yp * Id. We continue our theoretical analysis of input-convex classifiers by extending the universal approx- imation theorem for regressing upon real-valued convex functions (given in Chen et al. [16] to the classification setting. In particular, Theorem below shows that any input-convex classifier E Fia be approximated arbitrarily well on any compact set by ReLU neural networks with nonnegative weights. Here, "arbitrarily well" means that the set of inputs where the neural network prediction differs from that of f be made have arbitrarily small Lebesgue measure.
Theorem 3.6, For any f E Fia, any compact convex subset X of R², and any > 0, there exists E Fia such that m(fz E X f(z) + f(x))) <c
extension of the proof of Theorem 3.6 combined with Proposition 3.4 yieldss that input-convex ReLU neural networks can perfectly fit convexly separable sampled datasets.
Theorem 3.7
If (X1, is a convexly separable pair of finite subsets of RR, then there exists ʃ Fia such that f(xx) = 1 for all x E X1 and f(x) = for all x E X2.
Theorems 3.6 and 3.7 being specialized to models with ReLU activation functions, theoretically justify the particular parameterization Definition 2.2 for learning feature-convex classifiers to fit convexly separable data.
Empirical convex separability. Interestingly, we find empirically that high-dimensional image training data convexly separable. We illustrate this in Appendix[D] by attempting reconstruct CIFAR-10 cat image from convex combination of the dogs and vice versa, the error is significantly positive for every sample the training dataset, and image reconstruction visually poor. This fact, combined with Theorem 3.7 immediately yields the following result.
Fact 3.8. There exists f e Fia such that f achieves perfect training accuracy for the unaugmented CIFAR-1O cats-versus-dogs dataset.
The gap between this theoretical guarantee and practical performance is large; without the feature map, our CIFAR-10 cats-dogs classifier achieves just 73.4% training accuracy (Table{4. While high training accuracy does not necessarily imply strong test set performance, Fact demonstrates that the typical deep learning paradigm of overfitting to the training dataset is theoretically attainable [49] We thus posit that there is substantial room for improvement in the design and optimization of input-convex classifiers. We leave the challenge of overfitting to the CIFAR- cats-dogs training data with an input-convex classifier as an open research problem for the field.
Open Problem 3.9. Learn an input-convex ReLU neural network that achieves 100% training accuracy on the unaugmented CIFAR-1O cats-versus-dog dataset.
Convex separability in high dimensions. We conclude by investigating why the convex separability property that allows for Fact maymmy hold for natural image datasets. We argue that dimensionality facilitates this phenomenon by showing that data is easily separated by some f E Fia when is sufficiently large. In particular, although it may seem restrictive to rely on models in Fia with convex class 2 decision regions, we show in Theorem 3.10 below that even uninformative data distributions that are seemingly difficult to classify may be fit by such models with high probability as the dimensionality of the data increases.
Theorem 3.10
Consider M,N E N. Let X1 = (o(1), (M) c IRd and X₂ = (8) (6)
(v()) (N) S Bd be samples with all elements 2 Vi drawn independently and identi-
7

---

cally from the uniform probability distribution on [-1, 1).
Then, it holds that
(1
MINI (M+NY
d
for all d E N, if 2 MN
PP (a) is convexly separable)
2
(2)
In particular, Fia contains an inpul-convex ReLU neural network that classifies all x(0) into class 1 and all σ into class? 2 almost surely for sufficiently large dimensions d.
Although the uniformly distributed data in Theorem 3.10 is unrealistic in practice, the result demon- strates that the class Fia of input-convex ReLU neural networks has sufficient complexity to fit even the most unstructured data in high dimensions. Despite this ability, researchers have found that currett input-convex neural networks tend to not overfit in practice, yielding small generalization gaps relative conventional neural networks [60]. Achieving the modern deep learning paradigm of overfitting to the training dataset with input-convex networks is an exciting open challenge [49]
4 Experiments
This section compares our feature-convex classifiers against a variety of state-of-the-an baselines in the asymmetric setting. Before discussing the results, we briefly describe the datasets, baselines, and architectures used. For more in-depth description and hyperparameter details, see Appendix
Datasets. We use four datasets. First, we consider distinguishing between 28 x 28 greyscale MNIST digits and (37], which are generally more visually similar and challenging to distinguish than other digit pairs. Next, we consider identifying malware from the "Allaple.A" class in the Maling dataset of 512 x 512 bytewise encodings of malware [50]. Next, we consider distinguishing between shirts and T-shirts in the FaShion-MNIST dataset of 28 x 28 greyscale images (70], which tend be the hardest classes to distinguish (3 Finally, we consider the 32 x 32 RGB CIFAR- 10 cat and dog images since they relatively difficult to distinguish 226 43 30) The latter two datasets can be considered as our more challenging settings. All pixel values are normalized into the interval [o, 1].
Baseline Methods. We consider several of-eeof-the-eee randomized and deterministic baselines. For all datasets, we evaluate the randomized smoothing certificates of Yang et al. (72) for the Gaussian, Laplacian, and uniform distributions trained with noise augmentation (denoted RS Gaussian, RS Laplacian, and RS Uniform, respectively), as well as the deterministic bound propagation framework o, a, B.CWN (66,, which is scatter plotted since certification only reported as binary answer at given radius. We also evaluate, when applicable, deterministic certified methods for each norm ball. These include the splitting-noise & f--certificates from Levine and Feizi 40 (denoted Splitting), the orthogonality- and the -ds-iistanee-bas -crtiiffis from Zhang et al. [77] (denoted -Net). The last two deterministic methods are not evaluated on the large-scale Maling dataset due to their prohibitive runtime. Furthermore, the -Net was unable to significantly outperform a random classifier on the CIFAR-10 cats-dogs dataset, and is therefore only included in the MNIST 3-8 and Fashion- MNIST shirts experiments. Notice that the three randomized smoothing basclines have fundamentally different predictions and certificates than the deterministic methods (including ours), namely, the predictions are random and the certificates hold only with high probability.
fn-certificates from Trockman and Kolter (63) (denoted Cayley),
Feature- Architecture, Our simple experiments (MNIST 3-8 and Maling) require feature map to achieve high accuracy (4p = Id). The Fashion-MNIST shirts dataset also benefited minimally from the feature map inclusion. For the CIFAR-10 cats-dogs task, we let our feature map be the concatenation xpx) = (xr
x p4(). as motivated by Appendix B where is the channel- dataset mcan (e.g., size for an RGB image) broadcasted to the appropriate dimensions. Our MNIST 3-8 and Malimg architecture then consists of a simple two-hidden-laye input-convex multilayer perceptron with (M1, = (200, 50) hidden features, ReLU nonlinearities, and passthrough weights For the Mishion-MNIST shirts (CIFAR-10 cats-dogs, resp.) dataset, we use convex ConvNet architecture consisting of 3 (5, resp.) convolutional, BatchNorm, and ReLU layers. All models are trained using SGD on the standard binary cross entropy loss with Jacobian regularization, and clean accuracies are balanced as described in Section T.T and Appendix E.4 ensure fair comparison of different robustness certificates.
8

---

Results and Discussion. Experimental results for & -o-no certification are reported in Figure 2 where our feature-conved classifier radii, denoted by Convex*, are similar or better than all other baselines across all datasets. Also reported is each method's clean test accuracy without any attacks, denoted by "clean." Due to space constraints, we defer the corresponding plots for l2- and & -oom balls to Appendix[]) where our certified radii are not dominant but still comparable methods tailored specifically for particular norm. We accomplish this while maintaining completely deterministic, closed-fome certificates with orders-of-magnitude faster computation time than competitive baselines.
1.0
Convex
[99.0% clean]
RS Gaussian
[99.8% clean]
0.8
RS Laplacian
[99.8% clean]
Certified accuracy
RS Uniform
[99.6% clean]
0.6
Splitingg
198.4% clean]
x 8-CROWN
[99.2% clean]
Cayley
[100 clean]
Convex*
197.9% clean
0.4
-Nel
[100 clean]
Gaussian
[98.0% clean]
RS Laplacian [98.09 clean]
RS Uniform
[98.4% clean]
X
0.2
Splitiing
[98.6% clean]
x 3-CROWN (97.7% clean]
0.0
10
15
10
10
10
10
(a) MNIST 3-8.
(b) Malimg.
1.0
Convex
[83. clean]
Convex
[68.0% clean]
RS Gaussian
[80.5% clean]
RS Gaussian
[65.0% clean]
0.8
RS Laplacian
[82. clean]
RS Laplacian
[66.6% clean]
Certified accuracy
RS Unitorm
[80.7% clean]
RS Uniform
[67.2% clean]
0.6
Splitting
[85.8% clcan]
Splitting
[73.0% clean]
X a, 8-CROWN
[83.9% clean]
X a, 8-CROWN
[61.6% clean]
Cayley
[87.5% clean]
Cayley
[76.1 16. clean]
0.4
&s -Net
[79.4% clean]
0.2
x
0.0
10
20
30
0
10
20
30
-radiuss
E -radiuss
(c) Fashion-MNIST shirts.
(d) CIFAR-10 cats-dogs.
Figure 2: Class 1 certified radii curves for the fo-nrmm Note the log-scale on the Malimg plot.
For the MNIST 3-8 and Maling datasets (Figures 2a and 2b). all methods achieve high clean test accuracy. Our & raddi scale exceptionally well with the dimensionality of the input, with two orders of magnitude improvement over smoothing basclines for the Malimg dataset. The Malimg certificates in particular have interesting concrete interpretation. As cach pixel corresponds one byte in the original malware file, an ε ficcertificate of radius provides a robustness certificate for up to bytes in the file. Namely, even if malware designer were to arbitrarily change malware bytes, they would be unable to fool our classifier into returning a false negative. We note that this is primarily illustrative and is unlikely to have immediate practical impact small semantic changes (e.g., reordering unrelated instructions) can induce large L, n,-norm shifts.
While our method produces competitive robustness certificates for l2- and lxc -noms (Appendix F). offers the largest improvement for -eettiifiiaaess in the high-dimensional image spaces considered. This is likely due to the characteristies of the subgradient dual norm factor in the denominator of

---

Table Average runtimes (seconds) per input for computing the &,. E2, and -obusst radii. our method. per-property verification time. certified radius computed via binary search.
MNIST 3-8
Maling
Fashion-MNIST shirts
CIFAR-10 10 cats-dogs
Convex
0.00159
0.00295
0.00180
0.00180
RS Gaussian
2.16
111.9
2.41
5.78
RS Laplacian
2.23
114.8
2.51
5.81
RS Uniform
2.18
112.4
2.44
5.80
Splitting
0.597
994.5
0.185
0.774
a, B-CROWW
6,088
6,138
6,425
9.133
Cayley
0.000505
0.0451
0.0441
-Net
0.138
0.115
The dual of the fj-norm is the -nomm, which selects the largest magnitude element in the gradient of the output logit with respect to the input pixels. As the input image scales, it is natural for the classifier to become less dependent on any one specific pixel, shrinking the denominator in Theorem 3.1 Conversely, when certifying for the & one must evaluate the & fn-rr of the gradient, which scales proportionally to the input size. Nevertheless, we find in Appendix [F] that our f2- and lo -radi are generally comparable those of the baselines while maintaining speed and determinism.
Theorem 3.1
Our feature-convex neural network certificates are almost immediate, requiring just one forward pass and one backward pass through the network. This certification procedure requires few milliseconds per sample on our hardware and scales well with network size. This is substantially faster than the runtime for randomized smoothing, which scales from several seconds per CIFAR-IO image to minutes for an ImageNet image [88. The only method that rivaled our nnorm certificates was o, B- CROWN; however, such bound propagation frameworks suffer from exponential computational complexity in network size, and even for small CIFAR- 10 ConvNets typically take on the order of minutes to certify nontrivial radii. For computational tractability, we therefore used a smaller network in our experiments (Appendix Eb. Certification time for all methods is reported in Table
Unlike the randomized smoothing baselines, our method is completely deterministic in both prediction and certification. Randomized prediction poses particular problem for randomized smoothing certificates: even for perturbation of "certified" magnitude, repeated evaluations the perturbed point will eventually yield misclassification for any nontrivial classifier. While the splitting-base -baeed certificates of Levine and Feizi 40) are deterministic, they only certify quantized (not continuous) & --eeturbations, which scale poorly to fg- and -erttiiiisss (Appendix [F). Furthermore, the certification runtime grows linearly in the smoothing noise o, evaluating the certified radii at used for the Malimg experiment takes several minutes per sample.
Ablation tests examining the impact of Jacobian regularization, the feature map yp, and data augmen- tation are included Appendix G We illustrate the certification performance of our method across all combinations of MNIST classes in Appendix
5 Conclusion
This work introduces the problem of asymmetric certified robustness, which we show naturally applies to number of practical adversarial settings. We define feature-convex classifiers in this context and theoretically characterize their representation power from geometrie, approximation theoretic, and statistical lenses. Closed-form sensitive-class certified robust radii for the feature-convex architecture are provided for arbitrary l.- -p-norms. We find that our fr-rouutteess certificates in particular match or outperform those of the current state-of-the-arr methods, with our f2- and f- -radi also competitive to methods tailored for a particular norm. Unlike smoothing and bound propagation baselines, we accomplish this with a completely deterministic and near- near-immediat computation scheme. We also show theoretically that significant performance improvements should be realizable for natural image datasets such as CIFAR-10 cats- vets-versus-dos. Possible directions for future research include bridging the gap between the theoretical power of feature-convex models and their practical implementation, as well exploring more sophisticated choices of the feature map p.
10

---

References
[1] Filippo Amato, Alberto López, Eladia María Peñia-Mendez, Petr Vañhara, Ales Hampl, and Josef Havel. Artificial neural networks in medical diagnosis. Journal of Applied Biomedicine, 11(2):47-58, 2013.
[2] Brandon Amos, Lei Xu, and Zico Kolter. Input convex neural networks. In International Conference on Machine Learning, pages 146-155. PMLR, 2017.
[3] Brendon G. Anderson and Somayeh Sojoudi. Certified robustness via locally biased randomized smoothing. In Learning for Dynamics and Control. PMLR, 2022.
[4] Brendon G. Anderson, Ziye Ma, Jingqi Li, and Somayeh Sojoudi. Tightened convex relaxations for neural network robustness certification. In Proceedings of the 59th IEEE Conference Decision and Control, 2020.
[5] Brendon G. Anderson, Samuel Pfrommer, and Somayeh Sojoudi. Towards optimal randomized smoothing: A semi-infinite linear programming approach. In ICML Workshop on Formal Verification of Machine Learming, 2022.
[6] MOSEK ApS. The MOSEK optimization toolbox for MATLAB manual. Version 9.0., 2019. URL httt:::///ceeeee mos.k....coooo.koooooo/o/oeo..k. com/ wtttt/oooooooeeeeeeeeeeoeeeeeeee windexxxxiidexxxoo html
[7] Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples. In International Conference on Machine Learning, pages 274-283. PMLR, 2018.
[8] Stanley Bak, Changliu Liu, and Taylor Johnson. The second international verification of neural networks competition (VNN-COMP 2021): Summary and results. arXiv preprint arXiv:2109.0042 2021.
[9] Randall Balestriero, Jerome Pesenti, and Yann LeCun. Learning in high dimension always amounts extrapolation. arXiv preprini arXiv:21 2021.
[10] Dimitri Bertsekas. Nonlinear Programming. Athena Scientific, 3rd edition, 2016.
[11] Battista Biggio, Igino Corona, Davide Maiorca, Blaine Nelson, Nedim Šindié, Pavel Laskov, Giorgio Giacinto, and Fabio Roli. Evasion attacks against machine learning at test time. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 387-402. Springer, 2013.
[12] Mariusz Bojarski, Davide Del Testa, Daniel Dworakowski, Bernhard Firner, Beat Flepp, Prasoon Goyal, Lawrence D. Jackel, Mathew Monfort, Urs Muller, Jiakai Zhang, et al. End to end learning for self-driving cars. arXiv preprint 160iv: 063 2016.
[13] Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
[14] Nicholas Carlini and David Wagner. Adversarial examples are not easily detected: Bypassing ten detection methods. In Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security, pages 3-14, 2017.
[15] Francesco Cartella, Orlando Anunciacao, Yuki Funabiki, Daisuke Yamaguchi, Toru Akishita, and Olivier Elshocht. Adversarial attacks for tabular data: Application to fraud detection and imbalanced data. arXiv preprini arXiv:2101.08030, 2021.
[16] Yize Chen, Yuanyuan Shi, and Baosen Zhang. Optimal control via neural networks: convex approach. In International Conference on Learning Representations, 2019.
[17] Yize Chen, Yuanyuan Shi, and Baosen Zhang. Data-driven optimal voltage regulation using input convex neural networks. Electric Power Systems Research, 189:106741, 2020.
[18] Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing, In International Conference Machine Learning, pages 1310-1320. PMLR, 2019.
11

---

[19] Stefano Cresci, Marinella Petrocchi, Angelo Spognardi. and Stefano Tognazzi. Adversarial machine learning for protecting against online manipulation. IEEE Internet Computing, 26(2):
47-52, 2021.
[20] Nilesh Dalvi, Pedro Domingos. Sumit Sanghai, and Deepak Verma. Adversarial classification. In Pruceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 99-108, 2004.
[21] Francisco Eiras, Motasem Alfarra, M Pawan Kumar, Philip HS Torr, Puncet K. Dokania, Bernard Ghanem, and Adel Bibi. ANCER: Anisotropic certification via sample-wise volume maximization. arXiv preprint arXlv:2107.04570, 2021.
[22] Kevin Eykholt, Ivan Evtimov, Earlence Fernandes, Bo Li, Amir Rahmati, Chaowei Xiao, Atul Prakash, Tadayoshi Kohno, and Dawn Song. Robust physical-worde attacks on deep learning visual classification. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pages 1625-1634, 2018.
[23] Mahyar Fazlyab, Alexander Robey, Hamed Hassani, Manfred Morari, and George Pappas. Efficient and accurate estimation of Lipschitz constants for deep neural networks. Advances in Neural Information Processing Systems, 32, 2019.
[24] Samuel G Finlayson, John D Bowers, Joichi Ito, Jonathan L Zittrain, Andrew L Beam, and Isaac S Kohane. Adversarial attacks on medical machine learning. Science, 363(6433):1287- 1289, 2019.
[25] William Fleshman, Edward Raff, Jared Sylvester. Steven Forsyth, and Mark McLean. Non- negative networks against adversarial attacks. arXiv preprint arXiv: 1806. 06 00800, 2018.
[26] Felipe Giuste and Juan C Vizearra. CIFAR-I0 image classification using feature ensembles. arXiv preprini arXiv:2002.03840 2020.
[27] Edita Grolman, Hodaya Binyamini, Asaf Shabtai, Yuval Elovici, Ikuya Morikawa, and Toshiya Shimizu. Hate Versaria: Adversarial attack against hate speech detection algorithms on Twitter. In Proceedings of the 30th ACM Conference on User Modeling, Adaptation and Personalization, pages 143-152, 2022.
[28] Kathrin Grosse, Nicolas Papemot, Praveen Manoharan, Michael Backes, and Patrick McDanicl. Adversarial examples for malware detection. In European Symposium on Research in Computer Security, pages 62-79. Springer, 2017.
[29] Matthias Hein and Maksym Andriushchenko. Formal guarantees on the robustness of a classifier against adversarial manipulation. Advances in Neural Information Processing Systems, 30, 2017.
[30] Tien Ho-Phuoc. CIFARIO to compare visual recognition performance between deep neural networks and humans. arXiv preprint arXiv: 2018
[31] Judy Hoffman, Daniel Roberts, and Sho Yaida. Robust learning with Jacobian regularization. arXiv preprint arXiv: 00999999...9.....9 2019.
[32] fñigo incer Romeo, Michael Theodorides, Sadia Afroz, and David Wagner. Adversarially robust malware detection using monotonic classification. In Proceedings of the Fourth ACM International Workshop on Security and Privacy Analytics, pages 54-63, 2018
[33] Mohammed Kayed, Ahmed Anter, and Hadeer Mohamed. Classification of garments from fashion MNIST dataset using CNN LeNet-S architecture. In 2020 International Conference on Innovative Trends in Communication and Computer Engineering (ITCE), pages 238-243. IEEE, 2020.
[34] Jinrae Kim and Youdan Kim. Parameterized convex universal approximators for decision- making problems. IEEE Transactions on Neural Networks and Learning Systems, 2022.
[35] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
12

---

[36] Alexey Kurakin, Ian Goodfellow, and Samy Bengio. Adversarial machine learning at scale. In International Conference on Learning Representations, 2017.
[37] Yann LeCun. The MNIST database of handwritten digits. 1998.
[38] Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness to adversarial examples with differential privacy. In IEEE Symposium on Security and Privacy, pages 656-672. IEEE, 2019.
[39] Alexander Levine and Soheil Feizi, Wasserstein smoothing: Certified robustness against Wasserstein adversarial attacks. In International Conference Artificial Intelligence and Statistics, pages 3938-3947. PMLR, 2020.
[40] Alexander J Levine and Soheil Feizi. Improved, deterministic smoothing for & certified robustness. In International Conference on Machine Learning, pagess 6254-6264. PMLR, 2021.
[41] Bai Li, Changyou Chen, Wenlin Wang, and Lawrence Carin. Certified adversarial robustness with additive noise. In Advances in Neural Information Processing Systems, volume 32, 2019.
[42] Aishan Liu, Xianglong Liu, Jiaxin Fan, Yuqing Ma, Anlan Zhang, Huiyuan Xie, and Dacheng Tao. Perceptual serceptual-eensitvee GAN for generating adversarial patches. In Proceedings of the AAAI Conference Artificial Intelligence, volume 33, pages 1028-1033 2019.
[43] Qun Liu and Supratik Mukhopadhyay, Unsupervised learning using pretrained enn and associa- tive memory bank. In 2018 International Joint Conference on Neural Networks (IJCN),, pages 01-08. IEEE, 2018.
[44] Daniel Lowd and Christopher Meek. Good word attacks on statistical spam filters. In CEAS, volume 2005, 2005.
[45] Ziye Ma and Somayeh Sojoudi. A sequential framework towards exact SDP verification of neural networks. In 202/ IEEE 8th International Conference on Data Science and Advanced Analytics (DSAA), pages 1-8. IEEE, 2021.
[46] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant adversarial attacks. In International Conference Learning Representations, 2018.
[47] Ashok Makkuva, Amirhossein Taghvaei, Sewoong Oh, and Jason Lee. Optimal transport mapping via input convex neural networks. In International Conference on Machine Learning, pages 6672-6681. PMLR, 2020.
[48] Mark Niklas Müller, Christopher Brix, Stanley Bak, Changliu Liu, and Taylor T Johnson. The third international verification of neural networks competition (VNN-COMP 2022): Summary and results. arXiv preprint 221 2022.
[49] Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and Ilya Sutskever. Deep double descent: Where bigger models and more data hurt. Journal of Statistical Mechanics: Theory and Experiment, 2021(12):124003 2021.
[50] Lakshmanan Nataraj, Sreejith Karthikeyan, Gregoire Jacob, and Bangalore S Manjunath. Mal- ware images: Visualization and automatic classification. Proceedings of the 8th International Symposium on Visualization for Cyber Security, pages 1-7, 2011.
[51] Vitali Nesterov, Fabricio Arend Torres, Monika Nagy-Huber Maxim Samarin, and Volker Roth. Learning invariances with generalised input-convex neural networks. arXiv preprint arXiv:2204.07000 07009, 2022.
[52] Anh Nguyen, Jason Yosinski, and Jeff Clune. Deep neural networks are easily fooled: High confidence predictions for unrecognizable images. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 427-436, 2015.
13

---

[53] Samuel Pfrommer, Brendon G. Anderson, and Somayeh Sojoudi. Projected randomized smooth- ing for certified udversarial robustness. Preprint, 2022. URL https://breedon anderssn http://ww.....a.eooooaaaaeea//an
[54] Aditi Raghunathan, Jacob Steinhardt, and Percy S Liang. Semidefinite relaxations for certifying robustness to adversarial examples. In Advances in Neural Information Processing Systems, pages 10877-10887, 2018.
[55] R Tyrrell Rockafellar. Conver Analysis. Princeton University Press, 1970.
[56] Amir Mahdi Sadeghzadeh, Saeed Shiravi, and Rasool Jalili. Adversarial network traffic: Towards evaluating the robustness of deep-learning-base -aanid network traffic classification. IEEE Transactions on Network and Service Management, 1822)6192-1196, 2021.
[57] Hadi Salman, Jerry Li, Ilya Razenshteyn, Pengchuan Zhang. Huan Zhang, Sebastien Bubeck, and Greg Yang. Provably robust deep learning via adversarially trained smoothed classifiers. In Advances in Neural Information Processing Systems, volume 32, 2019.
[58] Suman Sapkota and Binod Bhattarai. Input invex neural network. arXiv preprint arXiv:2106.08748, 2021.
[59] Ali Siahkamari, Durmus Alp Emre Acar, Christopher Liao, Kelly L Geyer, Venkatesh Saligrama, and Brian Kulis. Faster algorithms for learning convex functions. In International Conference on Machine Learning, pages 20176-20194, PMLR, 2022.
[60] Sarath Sivaprasad, Ankur Singh, Naresh Manwani, and Vineet Gandhi. The curious case of convex neural networks. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 738-754, Springer, 2021.
[61] Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Good- fellow, and Rob Fergus. Intriguing properties of neural networks. In International Conference on Learning Representations, 2014.
[62] Jayy Teng, Guang-He Lee, and Yang Yuan. l adversarial robustness certificates: A ran- domized smoothing approach. Preprint, 2020. U.Lpatp:://oppneereew...ee wttp://wwwwi.eee//oonni/iii.. H11QIgrFDS
[63] Asher Trockman and J Zico Kolter. Orthogonalizing convolutional layers with the Cayley transform. arXiv preprint arXiv:2104.07/6 2021.
[64] Jonathan Uesato, Brendan O' D'Dnogguee Pushmeet Kohli, and Aaron Oord. Adversarial risk and the dangers of evaluating against weak attacks. In International Conference on Machine Learning, pages 5025-5034. PMLR, 2018.
[65] Aladin Virmaux and Kevin Scaman. Lipschitz regularity of deep neural networks: Analysis and efficient estimation. Advances in Neural Information Processing Systems, 31, 2018
[66] Shiqi Wang. Huan Zhang, Kaidi Xu, Xue Lin, Suman Jana, Cho-Jui Hsich, and J Zico Kolter. Beta-CROWN: Efficient bound propagation with per-neuron split constraints for neural network robustness verification. Advances in Neural Information Processing Systems, 14:29909-29921 2021.
[67] Lily Weng, Huan Zhang, Hongge Chen, Zhao Song, Cho-Jui Hsieh, Luca Daniel, Duane Boning, and Inderjit Dhillon. Towards fast computation of certified robustness for ReLU networks, In International Conference on Machine Learning, pages 5276-5285. PMLR, 2018
[68] Eric Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In International Conference on Machine Learning, pages 5286-5295. PMLR, 2018
[69] Bichen Wu, Forrest landola, Peter H. Jin, and Kurt Keutzer. SqueezeDet: Unified, small, low power fully convolutional neural networks for real-time object detection for autonomous driving. In Proceedings of the IEEE Conference on Computer Vision and Puttern Recognition Workshops, pages 129-137, 2017.
14

---

[70] Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-MNISTI A novel image dataset for benchmarking machine learning algorithms. arXiv preprint wrXiv:1708.077440 2017.
[71] Samir S Yadav and Shivajirao M Jadhav. Deep convolutional neural network based medical image classification for disease diagnosis. Journal of Big Data, 6(1):1-18, 2019.
[72] Greg Yang, Tony Duan, J Edward Hu, Hadi Salman, Ilya Razenshteyn, and Jerry Li. Randomized smoothing of all shapes and sizes. In International Conference on Machine Learning, pages 10693-10705. PMLR, 2020.
[73] Yao-Yuan Yang. Cyrus Rashtchian, Hongyang Zhang, Russ R Salakhutdinov, and Kamalika Chaudhuri. A closer look at accuracy vs. robustness. Advances in Neural Information Processing Systems, 33:8588-8601 2020.
[74] Roozbeh Yousefradeh. Deep learning generalization and the convex hull of training sets. In Neurips Deep Learning through Information Workshop, 2020.
[75] Fancheng Zeng, Guanqiu Qi, Zhiqin Zhu, Jian Sun, Gang Hu, and Matthew Haner. Convex neural networks based reinforcement learning for load frequency control under denial service attacks. Algorithms, 15(2):34, 2022.
[76] Runtian Zhai, Chen Dan, Di He. Huan Zhang, Boqing Gong, Pradeep Ravikumar, Cho-Jui Hsieh, and Liwei Wang. MACER: Attack-free and scalable robust training via maximizing certified radius. In International Conference on Learning Representations, 2020.
[77] Bohang Zhang, Du Jiang, Di He, and Liwei Wang. Boosting the certified robustness of I-infinity distance nets. arXiv preprint arXiv:21 2021.
[78] Dinghuai Zhang, Mao Ye, Chengyue Gong, Zhanxing Zhu, and Qiang Liu. Black-box certifica- tion with randomized smoothing: A functional optimization based framework. Advances in Neural Information Processing Systems, volume 33, pages 2316-2326, 2020.
[79] Ling Zhang, Yize Chen, and Baosen Zhang. A convex neural network solver for DCOPF with generalization guarantees. IEEE Transactions on Control of Network Systems, 2021.
[80] Sen Zhao, Erez Louidor, and Maya Gupta. Global optimization networks. In International Conference Machine Learning, pages 26927-26957. PMLR, 2022.
15

---

Supplementary Material
A Classification Framework Generalization
While outside the scope of our work, we note that there are two natural ways to extend our approach to a multiclass setting with one sensitive class. Let y 21, C], with class being the sensitive class for which we aim to generate certificates.
One approach involves two-step architecture, where feature-conver classifier first distinguishes between the sensitive class 1 and all other classes 12..,... c} and an arbitrary second classifier distinguishes between the classes 3........44 The first classifier could then be used to generate class 1 certificates, as described in Section 3.1
Alternatively, could define g to map directly output logits, with the first logit convex in the input and the other logits concave in the input. Concavity can be easily achieved by negating the output of convex network. Let the ith output logit then be denoted as Oi and consider an input x where the classifier predicts class (i.e., 91 (s((x)) 2 (i((((z)) for all i E (2, (2.3..... c)); since the difference of convex and a concave function is convex, we can generate certificate for the nonnegativity of each convex decision function o 9; o o around x. Minimizing these certificates over all E (2, c} yields robustness certificate for the sensitive class.
Note that g mapping to 2 or more logits, all convex in the input, would not yield any tractable certificates. This is because the classifier decision function would now be the difference of two convex functions and have neither convex nor concave structure. We therefore choose to instantiate our binary classification networks with a single convex output logit for clarity.
A.1 Maling Multiclass Extension
As proof-of-concepl. we provide concrete realization of the first scheme above on the Maling dataset. Namely, consider the setting where we want to distinguish between "clean" binaries and 24 classes of malware. A malware designer seeks to maliciously perturb the bytes in their binary to fool a classifier into falsely predicting that the malware is "clean." " We therefore consider a cascading architecture where first feature-conver classifier answers the "clean malware" question, and then a subsequent classifier (not necessarily feature-convex) predicts the particular class of malware in the case that the feature-convex classifier assigns "malware" prediction. Note that, in the initial step, we can either certify the "clean" binaries or the collection of all 24 malware classes, simply by negating the feature-convex classifier output logit. We logically choose certify the malware classes as done in our experiments of Section 4 these certificates provide guarantees against a piece of malware going undetected.
We use the same feature-convex architecture and training details as described in Appendix E For the cascaded malware classifier, we use ResNet-18 architecture trained with Adam for 150 epochs with a learning rate 10-3, The confusion plot for the multiclass classifier is provided in Figure 3 with overall accuracy of 96.5%. With the exception of few challenging classes to distinguish, the classifier achieves reasonable performance despite the unbalanced class sizes.
Figure visualizes the distribution of certified radii for the four most common malware classes in the dataset, excluding the "Yuner.A" class which featured duplicated images. Note that certification performance varies between classes, with high correlation across different norms for particular malware class. Classes which tend to have larger certificates can be interpreted as clustering further away from the clean binaries, requiring larger perturbations to fool the classifier.
B Feature Map Motivation
This section examines the importance of the feature map (p with low-dimensional example. Consider the binary classification setting where one class X₂ C Rd is clustered around the origin and the other class X, C I surrounds it in a ring. Here, the pair (X1, X2) convexly separable (see
Definition 3.3 as an f2-norm ball decision region covering X₂ is convex (Figure Sap. Note that the
reverse pair (X2, 2, X,) not convexly separable, as there does not exist a convex set containing X,
but excluding X2. A standard input-convex classifier with p ld would therefore be unable to

---

1.0
Clean
0.6
10-
Thue label
12
0.4
18
0.2
20
22
21
Clean
14
16
18
20
22
24
Predicted label
The row-normalized confusion plot for the Malimg multiclass classifier. The overall accuracy of the composite classifier is 96.5%. The various malware classes (1-24) are circumscribed with black rectangle. These are certified against the class of "clean" binaries. See Section 4 for more details on the mock clean binaries.
Figure 3:
discriminate between the classes in this direction (Proposition 3.5 i.e., we would be able to learn classifier that generates certificates for points X1, but not X².
The above problem is addressed by choosing the feature map to be the simple concatenation (xx) (a,, (ær]) mapping from IR. to IR9 2d with associated Lipschitz constants (ip) s Lip)(1) < 22, and (P)
In this augmented feature space, Xı and X2 convexly separable in both directions, as they are each contained in a convex set (specifically, half-space) whose complement contains the other class. We sensitive class for which certificates are required (Figure(5h) This parallels the motivation of the support vector machine "kernel trick," " where inputs are augmented wherein the data is linearly separable (instead of convexly separable as in our case).
able to learn classifier that takes X₂ the
nigher-dimensional space
C Proofs and Supplemental Theoretical Results
Theorem 3.1 Let f FF be as in Definition 2.1 and let f-1) = (x' Rd. f(z') 1}. If Vg(((()) E R9 is a nonzero subgradient of the convex function at ((xx), then f(a + 8) = 1 for all E Rdd such that
g(p(z))
||ō1|, < r(x)
Proof.
Suppose that (z(p(x)) E R a nonzero subgradient of g at p(x), so that g(y) 2 g(p(x))
Vg(v<())) (y - v(x)) for all y RR. Let 8 Rd be such that [|б'|, < r(x). Then it holds that g(6(x 8)) 2 s(p(x)) + T (1p( + 5) p(x))
,(p(x)) (V)(((()))))))) 11xx -
)(((()) (V (+))()))01),
0.

---

X10
1.2
I
90
T
I
0.24
1.1
80
0:22
Eyourtlleste
0:20
0.18
60
0.16
0.6
30
0.11
0.5
Allaph
Fakereu
Instatt...
VB VB.AT
Allaple
Fakeran
Instant...
Allaple
Fakeront
Instant...
VB.AT
VB.
Figure 4; Certified radii distributions for four malware classes in the Malimg dataset.
20
10
10
20
(b)
Figure 5: Experiments demonstrating the role of the feature map yp (x, (x]) in R², with the output logit shaded. Certified radii from our method are shown as black rings. (a) Certifying the outer class (dark red points). This is possible using input-convex classifier the inner class (dark blue points). ( Certifying the inner class (dark red points). This would not be possible with o Id there is convex set containing the outer class (dark blue points) but excluding the inner. The feature map & enables this by permitting convex separability in the higher dimensional space. Note that although the shaded output logit not convex in the input, still generate certificates.
convex sublevel set contains
so indeed f(x 5) 1.
We now introduce preliminary lemma for the results in Section 3.2
Lemma C.I. For any nonempty closed convex set X C Rdd there exists convexfunction g: Rdd TR such that X g - 0)) {x ıd g(x)) < 0}.

---

Proof. Let X C Rd be nonempty closed convex set. We take the distance function g dx defined by dx (z) infyex lyy 2/12. Since is closed and y + lly æll2 is coercive for all x E Rd, holds that y + |yy x||2 attains its infimum over X [ Proposition A.8]. Let a00), (x()) (xx2) R and let 8 E [0, 1]. Then there exist y(), yy2) X such that g(x(1) lly 21
and g(x(2)) lly - =2(2)/2 Since is convex, it holds that 0y(1) + (1 (1-0)y(3) (2) X, and therefore
g(0x(1)) ) + (1 -))x(1))
inf l1y (0z(1) + (1 0)xx())
vEX
- 110y + (1 0ly (0x(1) + +11 0) 1l22
S 011y(1) -x 11 + (1 - -8)1l x1()
0g(z!11) (1 11-00y1 0)g
Hence, = dx is convex. Since X = fa E R jn l1 - x||2 = 0} fx E dx(x)) =
0} = (x E Rd :x(xx) S 0) = (a E Rd g(x) s 0} by nonnegativity of dx, the lemma holds.
Proposition 3.4 For any nonempty closed convex set X S Rd, there exists f E Fia such that
X x= ( for E R ff(z) 2}. In particular, this shows that if (X1. a convexly RRd
separable pair of subsets Tf, then there exists Fia such that f(x) 1 for all X1 and f(z) = for all x E X2.
Proof. Let X C Rd be nonemply closed convex set. By Lemma
C.1 there exists a convex function
g: Fd + R such that X {x IR g(x) S 0}. Define f: Rd {1, by f(x) 1 i g())
and f(x) 2 if g(x) I 0. Clearly, it holds that f E Fia. Furthermore, for all æ E X it holds that
g(x) S 0, implying that f(xx) = 2 for all x E X. Conversely, if x E Rd is such that f(x) = 2, then
g(x) & 0, implying that x E X. Hence, X {x E Rd f(z) = 2].
If (X,, X2) is convexly separable pair of subsets of Rd, then there exists nonempty closed convex
set X nd such that X₂ C X and X₁ Id X, and therefore there exists Fia such that
X2 C X = (-2 and X1 C Rd x= f ((1)), implying that indeed f(x) = 1 for all E X and f(x) 2 for all X2-
L
Proposition 3.5
Let Fia. The decision region under associated class namely
f- ((2)) x E Rd: f(x) = 2}, is closed convex set.
Proof. For all x E Rd. it holds that f(x) = if and only if g(z) < 0. Since f E Fid. 9 is convex, and hence, X = fa E Rd g(x) I 0} is a (nonstrict) sublevel set of convex function and is therefore closed convex set.
In order to apply the universal approximation results in Chen et al. 166, we now introduce their pa- rameterization of input-convex ReLU neural networks. Note that it imposes the additional constraint that the first weight matrix A1) is elementwise nonnegative.
Definition C.2. Define Fia to the class of functions j: Rd + [1,2} given by f(x) = T(ū()))
with g: Rd + R given by
(1) = ReLU (4(4) (10++b())
(1) = ReLU (1-11 + 100 + c(ll)), E (2,3,...,L-1 1}.
((x) = (L) ((L) ((D)r
for some L E N, L > 1, and some consistently sized matrices A C(I) ALL), c(C), all of which have nonnegative elements, and some consistently sized vectors ((1) b(t.)
The following preliminary lemma relates the class Fia from Definition 2.2 to the class Fia above.
Lemma C.3. It holds that Fia C Fia-

---

Proof. Let f E Fia. Then certainly A 2 0 for all I E f2.3..... L}, so indeed f f Fia. Hence, Fia S Fia.
Theorem in Chen et al. [T6] shows that a Lipschitz convex function can be approximated within an arbitrary tolerance. We now provide technical lemma adapting Theorem in Chen al. [T6 to show that convex functions can be underapproximated within an arbitrary tolerance on a compact convex subset.
Lemma C.4. For any convex function g: IR + I. any compact convex subset X of R2, and any > O, there exists f E Fia such that g(x) < g(z) for all x E X and supsex (g(x) ((x)) < e.
Proof. Let g: Rd + R be a convex function, let X be a compact convex subset of Rd, and let e <> 0. Since g - c/2 a real- convex function on Fd (and hence is proper), its restriction to the closed and bounded set X is Lipschitz continuous [55] Theorem 10.4], and therefore Lemma
C.3 together with Theorem 1 in Chen et al. [16] gives that there exists f E Fia S Fia such that
SuP [[((x)) c/2) ((x) < c/2. Thus, for all X,
(o(x) 2) ((x)
( 0(x)
(g(x) ;) -((x) sup yEX
(M(v) ;) ](w)
(o(x) 5 ((x) + (9(x)) ;)) 5(x)
20.
Furthermore,
sup (0(x) - ((z)) sup 19(2) [(+)1
xEX
xEX
(9(x) ;) - -](x) 2
sup
=ex
(9(x) E)
5) ((x) 2
e
S sup xeX G
which proves the lemma.
We leverage Lemma C.4 to construct uniformly converging sequence of underapproximating functions.
Lemma C.5. For all E Fia and all compact convex subsets X Rd, there exists sequence (fn Faa n N) S Fia such that 9æ((x) (n+1(x) < g(x) for all E and all and 9n. converges uniformly to on X as + oc.
Proof. Let E Fia and let X be a compact convex subset of Rdd. Let {en > 0: n NJ be sequence such that ent1 < for all E N and 6n + 0 as + Do. Such a sequence clearly exists, e.g., by taking En 1/n for all N. Now, for all n E N, the function g - 6n41 is convex,
and therefore by Lemma C.4 there exists fn E Fia such that (x) < g(x) cn+1 for all x X
and suPrex ((((z) (n+1) - (x)) < en Entl. Fixing such sn, Ôn for all n E N, we see that
supzex ((g(z) - En42) (n+1(x)) 6n+1 En+2, which implies that
(n+1(x) g(x) - ent > (N(
for all x E X, which proves the first inequality. The second inequality comes from the fact that (nt1(1)) < g(x) (nt2 g(x) for all X. Finally, since g(x) (a(x) > 6xt1 >> for all
x E X and all E N. we see that
sup (g(()) (x)) sup (g(x) - (x)) < cn - 0 n zeX
x
which proves that lim supxex (g(x) - gn (=)) = 0, so indeed 9. converges uniformly to g on X +
5

---

With all the necessary lemmas in place, we now present our main theoretical results.
Theorem 3.6 For any f Fia, any compact convex subset X of R2, and any > 0, there exists E Fia such that m(fx E X f(z) ) + f(x)}) <.
Proof. Let f E Fia and let X be a compact convex subset of R By Lemma C.5 there exists a sequence (In E Fia n E N] S Fia such that In (2) < (0+11(2) (xx) < g(x) for all æ E X and all N and In. converges uniformly g X as 0o. Fix this sequence.
For all n E N, define
= (
i.e., the set of points in X for which the classification under Sn does not agree with that under f. Since (x) < g(x) for all x E X and all n E N, we see that
En {a E (x) > and g s 0) fa E X (x(x)) S 0 and g(x) > 0}
f E X 9n (x) S 0 and g(x) 0}.
Since y is real-valued convex function Rd, it is continuous [55 Corollary 10.1.1], and therefore g ((0, oc)) = {ir E Rd g(x) > 0} is measurable. Similarly, 9r, ((-oc, 0]) = {x E R In (x) S 0} also measurable for all as it is compact. Therefore. En is measurable for all n E N. Now, since (x) < 9n+1 for all X and all n E N. it holds that F,+ C E,, for all n E N. It is clear that to prove the result, suffices to show that lim (En))= = 0. Therefore, if we show that m (ΠneN E,,) = O, then the fact that m m(E) (E)) ) < mmX < αo together with Lebesgue measure's continuity from above yields that lim,-+00 m F.) 0, thereby proving the result.
since 9n is continuous. Furthermore, X is measurable
It remains to be shown that m (ΠnnN Fm) = 0. To this end, suppose for the sake of contradiction that OnEN En # 0. Then there exists æ E NNENN En, meaning that g(x) > 0 and (x) < 0 for all n E N. Thus, for this x E X, we find that lim sup, (x) S < g(x), which contradicts the fact that on uniformly converges to g on X. Therefore, it must be that ONEN F. 0, and thus m (ПEEN En) 0, which concludes the proof.
Theorem 3.7 If (2) is a convexly separable pair of finite subsets of RRd then there exists Fia such that f(x) for all x E X, and f(x) = 2 for all x E X2.
Proof. Throughout this proof, we denote the complement of set Y C CR = YY.
C Rd are such that (X1,X) is convexly separable. Then, by definition of convex separability, there exists a nonempty closed convex set X' S Rd such that X₂ S X' and X, S Rd X'. Let X = X' n conv(X2). Since X2 S X' and both sets X' and conv are convex, the set X is nonempty and convex. By finiteness of X2, the set conv(X2) is compact, and therefore by closedness of X', the set X is compact and hence closed.
Suppose that X; = ( (M) S Ted and X₂ (,,
yN ".,,...,"")))
By Proposition 3.4 there exists f E Fia such that ((2)) = X. Since conv(X, UX2.) is compact and convex, Lemma C.5 gives that there exists a sequence (fr Fia : E N} S Fia such that In (x) < Io+1 (x) < g(x) for all x E conv(X, X2) and all n E N and 9n converges uniformly to g on cXnv(X, X2) as n > oo. Fix this sequence.
Let x. E X2. Then, since X₂ C X' and X₂ S conv(X2), it holds that x E X' n conv conv(X2) = X = ((2)),,,, implying that f(x) 2 and hence g(z) S Since 9n (x) < g(x) for all N. this shows that fx( = for n E N. On the other hand, let (l..... ... MM and consider
x = x00) E X,, Since X, C Rdd X' Ted n (X')e
Rd n X Rd )f-((( holds that f=) 1 and thus g(x) > O. Suppose for the sake of contradiction
(X' conv(X2))
that fx(x) = for all n E Then 9, (x) < 0 for all n E N. Therefore, for this x E X1, we find that lim -u (x) 0 < g(x), which contradicts the fact that 9n uniformly converges
on conv (X1 U22.. Therefore, it must be that there exists n; N such that fr, (x) 1, and thus
Ing (x) > O. Since (x(xx) < In+ (x) for all n E N. this implies that 9o (x) > 0 for all n 2 n.
Hence, fx( fn(2()) = 1 for all 2 n4.

---

Let n² be the maximum of all such n, i.e, n² = max(n; E fi....,MH Then the above analysis shows that fa- (a: for all E X2 and that fn-(x) 1 for all æ e X1. Since fu- E Fid the claim has been proven.
Theorem 3.10
Consider M,N N. Let X1 (x(1) x()) S R2 and X2
{y()) ..... yf y( ? Rdd be samples with all elements Ikk (6) ( drown independently and identi-
cally from the uniform probability distribution [-1, 11. Then, holds that
1- (1
MINI
for all E N, if M N
IP X2) is convexly separable)
(M+N))
In particular, Fia contains input-convex ReLU neural network that classifies all 20) into class 1 and all y0) into class almost surely for sufficiently large dimensions d.
Proof. Throughout the proof, we denote the cardinality of set S by |S]. For the reader's 's convenience,
also recall that, for E N, the symmetric group S,, consists of all permutations (i.e., bijections) on the set in Sn, denote the restriction of to the domain 1 C (1,2, .,,,..... . .n by alr: I - {1,2, ...... n), which we recall is defined by lf2 (i) = (i) for all i E 7, and is not necessarily a permutation on in general.
n). and that |Sm| = n!. If a: {1, 1,2,....77 , - (1.2..... .. is a permutation
Consider first the case where d 2 M + N. Let E M+N be the vector defined by b, for
all (1..... M} and b; -1 for all i (M + 1, ...... .M N). Then, since 2ik Vi are independent uniformly distributed random variables on [-1, 1J, holds that the matrix
(1) ())
x(1)
x(1))
ER (M+
8(1)
(
has rank M N almost surely, and therefore the linear system of equations
x11)T
x(Mr)
T(1)T
a= b
(
has solution E Rd with probability 1, and we note that from this solution we find that X₃ is subset of the nonempty closed convex {i Rd complement. Hence, (X1, X2) is convexly separable with probability in this case.
< 0} and that X₁ subset of its
Now let consider the general case: d N and in general may be the case that d < M N. For notational convenience, let P be the probability of interest:
P= ((X1, is convexly separable).
(i) for all pairs (i,j) e Suppose that there exists coordinate & E {1, 21, ........... d} such that a Vi ,...,, V/ (N)) =
{1, (1.2...., M] x 21,2..... N) and that = min(y) ......yk (N)) < max [yx (1)
Then, let X = {i E Idd . E [a, 6j}. That is, X is the extrusion of the convex hull of the projections (v ..... (1)) along all remaining coordinates. The set X is nonempty closed convex set, and
7

---

is clear by our supposition that X2 S X and X1 C R X. Therefore, the supposition implies that (X,.X2) X2) is convexly separable, and thus
Pz P (there exists & E 21, d3 such that Tik
(6)
yk
() for all pairs (i,j)
and that min (14 (1)
..... (N) max(yk) (2)
...... Uk (N)
11 - (for all & E [1, , d), it holds that 4 2 1/ for some pair (i,j)
or that min V (2)
..... Uk (N)] = max(y (1)
())
II P (
(i) for some pair (i.j) or min (1) . (N)] = max . 1).
Vk
where the final equality follows from the independence of the coordinates of the samples. Since min (1)
yk 1 maxful
(1) yk ( almost surely, we find that
d II
P2 1
P(ak 2 Ui for some pair (i.j))
(2)
k=1
+ P(min (vb ..... yk ) max ..... u/ 11))))
d
II
P
(
2 yk
(5)
for some pair (i.j))
d
(
< 4ik
(
for all pairs (i,
k=1
d
(
1
1 P
max
Ik
min
iE(1.2...... M)
JE(1.2.....V)
Jml
d
1 P
(a
(1)
(M) (1)
yk
Uk
(N)
U E,
aES
where we define S to be the set of permutations on f1..... M +N whose restriction to (1....,44 M} also a permutation;
$ = fo E SM+N (I E Sm
and where, for permutation ordered according to
E SMHN, Fa is the event where an (M N)-vector has indices
E, = f= R.M+M 22(11) < 2o(M+N)}
We note that the final equality in 3 relies on the fact that (P = (1) P( = y1 (3))
= for
all i' o and all j' + j. which is specific our uniform distribution at hand.
Now, since Eg, Ear are disjoint for distinct permutations a, o' SM+NN. the bound gives that
P21
II
Σ OES
P(
!
IE (M)
De (N) E Fio)
(4)
1=1
Since r ..... Ik Ui ..... 1/
(1)
(M (1)
(N)
are independent and identically distributed samples, they define
an exchangeable sequence random variables, implying that PP((2(1) ....,
,x (M)
y ,..,,... Vk (N) E
(1)
E.) ((=
(M)
(1)
(N) for all permutations a E SM+N- Since, under y (1)
1 yk
the uniform distribution at hand, (4 ..... I Us ..... (())) E, for some e SMLn almost
(1)
(af)

---

surely, it holds that
1 P
(x
24
(M) (N)
9k
Uk
(N))
E U E.
INSMIN
E
P((a
(1)
2
(M)
(1)
( Ea)
OESM+N
|SM+N P(ak ....
(M)
< Vkc
(1)
< ... < Uk
(N))
This implies that
P(( (1)
(M) (1)
Vk (N)) Ex) S
(M + N)!
for all permutations SM+N- Hence, bound becomes
d
(1
|S|
= (1
d (M + NN!
S
P21- II
(M + NJ!
Finally, we immediately see that that map r: SM x SN + SM+N defined by
if E [l..... ..... M). I(a, 00) - M) M if {M ..... M N),
(a(i)
is injective and has image S, implying that |S| = SSM x Sxl = |SM MIN!. Thus,
MIN! d
P2 1 (M + NN!
which proves 2
The unit probability of Fia containing classifier that classifies all xt0) into class and all yا) into class 2 for large follows immediately from Theorem 3.7
D CIFAR-10 Cats-versus-Dogs Convex Separability
order to establish that the cat and dog images in CIFAR-10 are convexly separable, we experimen- tally attempt reconstruct an image from one class using convex combination of all images in the other class (without augmentation such as random crops, flips, etc.). Namely, if is drawn from one class and (1) ,"),..., ....,,(N) represent the entirety of the other class, we form the following optimization problem:
N
minimize
Σ
NERN
j=l
subject
a
N Σ 1. j=1
The reverse experiment for the other class follows similarly. We solve the optimization using Σ}= agy()) in Figure 6 Reconstruction accuracy is generally very poor, with no reconstruction achieving better than an -errro of 52. A typical reconstructed image is shown in Figure
MOSEK [6], and report the various norms of x
Yousefzadeh 74 and Balestriero et al. 9 showed a related empirical result for CIFAR-10, namely, that no test set image can be reconstructed as convex combination of training set images. However, we remark that their findings do not necessarily imply that training set image cannot be reconstructed via other training set images; our new finding that the CIFAR- 10 versussssss training set convexly separable is required in order to assert Fact 3.8

---

700
0.8
14
600
12.
500
E2-reconsiruction error
Fac neccoottrcciooo ernr
0.6
10
--revonstruction
400
0.5
8
6
0.3
4
0.2
2
Dogs cal
Cats + dog
Dogs cal
Cats - dog
Dogs cal
Cats + dog
Figure 6: Reconstructing CIFAR-10 cat and dog images convex combinations. The label "Dogs + cat" indicates that a cat image was attempted to be reconstructed as a convex combination of all 5000 dog images.
Figure 7: Reconstructing CIFAR-10 cat image (left) from convex combination of dog images (right). The reconstruction error norms are 294.57, 6.65, and 0.38 for the b1,, lz.. and foo -noms, respectively. These are typical, indicated by Figure
E Experimental Setup
We include detailed exposition of our experimental setup in this section, beginning with general details on our choice epochs and batch size. We then discuss baseline methods, architecture choices for our method, class balancing, and data processing.
Epochs and batch size. Exempting the randomized smoothing baselines, for the MNIST 3-8 and Fashion-MNIST shirts experiments, we use 60 epochs for all methods. This is increased to 150 epochs for the Malimg dataset and CIFAR-10 cats-dogs experiments. The batch size is 64 for all datasets besides the 512 x 512 Maling dataset, where it is lowered to 32.
10

---

To ensure fair comparison, the randomized smoothing baseline epochs are scaled larger than the aforementioned methods according to the noise value specified in the sweeps in Section The final epochs and smoothing noise values used are reported in T Note that as classifiers are typically more robust to the noise from splitting smoothing, larger values of a are used for only this smoothing method in the MNIST 3-8 and Malimg datasets. For Malimg, we find experimentally that even noise values of up to a = 100 are tractable for the splitting method, outside the sweep range considered in Section | As verification at that already takes several minutes per sample and runtime scales linearly with o, we do not explore larger values of o.
Table 2: Randomized smoothing final noise and epoch hyperparameters.
Dataset
Laplacian, Uniform, Gaussian Parameters
Splitting Parameters
MNIST 3-8 Malimg
(a,n) = (0.75, 60)
(a,n) = (0.75 4, 60 4)
(a.n)
1510-44 4)
(g.n) (100, 150 4)
Fashion-MNIST shirts
(a. = (0.75, 60)
(a. n (0.75, 60)
CIFAR-10 cats-dogs
(a, = (0.75 -2 600 2)
(a, n) = (0.75 2, 600 2)
Hardware. All experiments were conducted on a single Ubuntu 20.04 instance with an Nvidia RTX A6000 GPU. Complete reproduction of the experiments takes approximately 0.08 GPU-years.
E.1
Datasets
We introduce the various datasets considered in this work. MNIST 3-8 and Malimg are relatively simple classification problems where near near- perfect classification accuracy is attainable; the Maling dataset falls in this category despite containing relatively large images. Our more challenging settings consist a Mushion-MNIST shirts dataset as well as CIFAR-10 cats-versus-dog dataset.
For consistency with 77. we augment the MNIST and Fashion-MNIST training data with 1 1-pixel padding and random cropping- The CIFAR-10 dataset augmented with 3-pixel edge padding. horizontal flips, and random cropping. The Malimg dataset is augmented with 20- 20-pixel padding and random 512 X 512 cropping.
For CIFAR-10, 10, MNIST, and MaShion-MNIST, we use the preselected test sets. For Maling we hold out a random 20% test dataset, although this may not be entirely used during testing. The training set is further subdivided by an 80%-20% validation split. For all experiments, we normalize pixel values into the interval [o, 1]. and we use the first 1000 test samples to evaluate our methods.
MNIST 3-8. For our MNIST binary classification problem, we choose the problem of distinguishing between and 8 337. These were selected as 3 and are generally more visually similar and challenging to distinguish than other digit pairs. Images are 28 x 28 pixels and greyscale.
Maling. Our malware classification experiments use greyscale, bytewise encodings of raw malware binaries Nataraj et al. [50). Each image pixel corresponds to one byte of data, in the range of 0-255, and successive bytes are added horizontally from left to right on the image until wrapping at some predetermined width. We use the extracted malware images from the seminal dataset Nataraj et al. [50]. normalizing pixel values into [0, 1], as well as padding and cropping images to be 512 x 512. Note that licensing concerns generally prevent the distribution of "clean" executable binaries. As this work is focused on providing a general approach to robust classification, in the spirit of reproducibility we instead report classification results between different kinds of malware. Namely, we distinguish between malware from the most numerous "Allaple.A" class (2949 samples) and an identically-sin random subset of all other 24 malware classes. To simulate a scenario where we must provide robustness against evasive malware, we provide certificates for the latter collection of classes.
Mashion-MNIST shirts. The hardest classes to distinguish in the Mashi dataset are T-shirts vs shirts, which we take as our two classes 33
70. Images are 28 x 28 pixels and greyscale.
CIFAR-10 cats-dogs. We take as our two CIFAR-10 classes the cat and dog classes since they are relatively difficult to distinguish 26 classify since large background features (e.g., blue water) are strongly correlated with the target label.
43
30 Other classes (e-g., ships) are typically easier to
Samples are 32 x 32 RGB images.

---

E.2 Baseline Methods
We provide additional details on each of the baseline methods below.
Randomized smoothing. Since the certification runtime of randomized smoothing is large, especially for the 512 x 512 pixel Malimg images, we evaluate the randomized smoothing classifiers over 10a samples and project the certified radius to 10 samples by scaling the number fed into the Clopper- Pearson confidence interval, as described in [8]. This allows for a representative and improved certified accuracy curve while dramatically reducing the method's runtime. We take initial guess for the certification class with By = 100 samples and set the incorrect prediction tolerance parameter 0.001. For CIFAR-10 we use depth-40 Wide ResNet base classifier, mirroring the choices from Cohen et al. [88 Yang et al. [72]: for all other datasets we use a ResNet-18 18. All networks are trained using SGD with initial learning rate of 0.1, Nesterov momentum of 0.9, weight decay of 10-1, and cosine annealing scheduling as described in Yang et al. [72). Final smoothing noise values are selected as in Table 2 and are determined from the noise level comparison sweeps Appendix
Splitting noise. As this method is a deterministic derivative of randomized smoothing, it avoids the many aforementioned hyperparameter choices. We use the same architectures described above for the other randomized smoothing experiments.
Cayley convolutions. To maintain consistency, we use a two-hidden-layer multilayer perceptron with (m1, m2) = (200, 50) hidden features, Cayleyl Linear layers, and GroupSort activations for the MNIST experiment. For the more challenging Fashion-MNIST and CIFAR-10 experiments, we use the ResNet-9 architecture implementation from [63]. Following the authors' suggestions, we train these networks using Adam with a learning rate of 0.001.
lx dis-tanne nets. As the architecture of the lee distancee net 777 is substantially different from traditional architectures, we use the authors' 5-layer MNIIS/FFsthon-MNIST architecture and 6-layer CIFAR-10 architecture with 5120 neurons per hidden layer. Unfortunately, the classification accuracy on the CIFAR-10 10 cats-dogs experiment remained near 50% throughout training. This was not the case when tested easier classes, such as planes-versus-casy where large features (e.g.. blue sky) can be used to discriminate. We therefore only include this model in the MNIST and FaShion-MNIST experiments, and use the training procedure directly from the aforementioned paper's codebase.
a, B.-CROON. As a, 3-CROWN certification time scales exponentially with the network size, we keep the certified networks small in order to improve the certification performance of the baseline. For all datasets, we train and certify a one-hidden- activations. All networks are adversarially trained for eer-rrrruraaiooon radius starting at 0.001 and linearly scaling to the desired over the first 20 epochs, as described in Kayed et al. 33 which trained the models used in Wang et al. (66]. The desired final c set to 0.3 for MNIST, 0.1 for Tashion-MNIST and Maling, and 2/255 for CIFAR-10. The adversarial training uses standard PGD attack with 50 steps and step size 2e/50. Other optimizer training details are identical to Wang et al. (66). The mracchandd-oung timeout is set to 30 seconds to maintain comparability to other methods, and robustness is evaluated over a lataset-dependen range of discrete radií for each adversarial norm.
network with 200 hidden units and ReL.U
E.3 Feature-Convex Architecture and Training
In this section, we provide more details of the feature-convex architectures used in our experiments of Section[ For the more challenging datasets (FNSSIon-MNIIST shirts and CIFAR-10 10 cats-dogs), we use various instantiations of a convex ConvNet (described below) where successive layers have constant number of channels and image size. This allows for the addition of identity residual connections to each convolution and lets us remove the passthrough connections altogether. Convexity is enforced by projecting relevant weights onto the nonnegative orthant after each epoch and similarly constraining BatchNorm 7 parameters to be positive. We initialize positive weight matrices to be drawn uniformly from the interval [0, e). where 0.003 for linear weights and 0.005 for convolutional weights. Jacobian regularization is also used to improve our certified radii 31.
The convex ConvNet architecture consists of a sequence of convolutional layers, BatchNorms, and ReLU nonlinearities. The first convolutional layer is unconstrained, as the composition of a convex function with an affine function is still convex ( All subsequent convolutions and the final linear readout layer are uniformly initialized from some small positive weight interval (O, 0.003) for linear weights, [0, 0.005) for convolutional weights) and projected to have nonnegative weights after
12

---

each gradient step. We found this heuristic initialization choice helps to stabilize network training. as standard Kaiming initialization assumptions are violated when weights are constrained to be nonnegative instead of normally distributed with mean zero. More principled weight initialization strategies for this architecture would form an exciting area of future research. Before any further processing, inputs into the network are fed into an initial BatchNorm- this enables flexibility with different feature augmentation maps.
Since the first convolutional layer is permitted negative weights, we generally attain better perfor- mance by enlarging the first convolution kernel size (see Table For subsequent convolutions, we set the stride to 1, the input and output channel counts to the output channel count from the first convolution, and the padding to half the kernel size, rounded down. This ensures that the output of each of these deeper convolutions has equivalent dimension to its input, allowing for an identity residual connection across each convolution. (z(z) convolutional operation on hidden feature this corresponds to evaluating (z) + instead of just (z))). The final part of the classifier applies MaxPool and BatchNorm layers before a linear readout layer with output dimension See Figure 8 for diagram depicting exemplar convex ConvNet instantiation.
scalar logit batchnorm fc nonneg
4 x 4 x 32
maxpool size 4
16 16 x-32 conv1 stride
16 16 32 conv2 nonneg
16 16 32 conv3 nonneg
16 16 32 conv4 nonneg
convolutional
ReLU batchnorm
32 32 feature map input
maxpool
fully connected
Figure 8: An example convex ConvNet of depth with a C1 stride 2, pool size 4, and 32 32 RGB images. There are 6 input channels from the output of the feature map yp: -> (xr nt, ml)-
For training, we use a standard binary cross entropy loss, optionally augmented with Jacobian regularizer on the Frobenius norm of the network Jacobian scaled by X > 0 (3T). As our certified radii Theorem 3.1 vary inversely the norm of the Jacobian, this regularization helps boost our certificates at a minimal loss clean accuracy. We choose À = 0.0075 for CIFAR-IO 10, 0.075 for Malimg and À 0.01 for MNIST and Fashion-MNIST. Further ablation tests studying the impact of regularization are reported in Appendix G All feature convex networks are trained using SGD with a leamning rate of 0.001, momentum 0.9, and exponential learning rate decay with 7 0.99.
Table 3: Convex ConvNet architecture parameters. C₁ denotes the first convolution, with C2... denoting all subsequent convolutions. The "Features" column denotes the number of output features of C1. which is held fixed across C2.... The "Pool" column refers to the size of the final MaxPool window before the linear readout layer. The MNIST and Malimg architectures simple multilayer
perceptrons and are therefore not listed here.
Dataset
Features
Depth
C1 size
C₁ stride
C₁ dilation
Ce... size
Pool
Fashion-MNNIN 4
3
CIFAR-10 16
5
11
1
1
13

---

E.4 Class Accuracy Balancing
As discussed in Section 1.1 balanced class and class 2 test accuracy essential for a fair comparison of different methods. For methods where the output logits can be directly balanced, this is easily accomplished by computing the ROC curve and choosing the threshold that minimizes [TPR- (1 - FPR)|. This includes both our feature-convex classifiers with one output logit and the Cayley orthogonalization and Co-Neet architectures with two output logits.
Randomized smoothing classifiers are more challenging as the relationship between the base classifier threshold and the smoothed classifier prediction is indirect. We address this using binary search balancing procedure. Namely, on each iteration, the classifier's prediction routine is executed over the test dataset and the "error" between the class 1 accuracy and the class 2 accuracy is computed. The sign of the error then provides the binary signal for whether the threshold should be shifted higher or lower the standard binary search implementation. This procedure is continued until the error drops below 1%.
F l- and CCe-tifie Radii
This section reports the counterpart to Figure for the f2- and -noms,. Across experiments, we attain substantial 62- and rradi without relying computationally expensive sampling schemes or nondeterminism. Methods that certify to another norm llp are converted to Ey-radii a factor of 1 p > q or dl/p-1/9 otherwise.
Certified f2-radii are reported in Figure 9 Our f2-radi are moderate, generally slightly smaller than those produced by Gaussian randomized smoothing.
lo -radi are reported in Figure 10 For the MNIST 3-8 experiment, the distance nets produce exceptional certified radii. Likewise, the -disttance net certificates are dominant for the Rashion-MNIST dataset, despite achieving slightly inferior clean accuracy. We note however that the applicability of -distancce nets for sophisticated vision tasks is uncertain as the method is unable to achieve setter-than-randon performance for CIFAR-10 10 cats-dogs (Section E.2) Our method is comparable auddmizzed-smoothing and a, 3-CROWN in all fo experiments.
Certified
14

---

1.0
Convex
199.0% clean]
RS Gaussian
[99.8% clean]
0.8
RS Laplacian
[99.8% clean]
Certified accuracy
RS Uniform
[99.6% clean]
0.6
Splitting
[98.4% clean]
X a. 8-CROWN
[99.2% clean]
Cayley
[100 clean]
Convex
[97.9% clean]
0.4
-Net
[100 clean]
Gaussian
[98.0% clean]
R$ Laplacian
[98.0% clean]
Uniform
[98.4% clean]
0.2
Splitting
198.6%8 clean]
X
x a. B--CRONN [97.7% clean]
0.0
10
10-3
10
10
(a) MNIST 3-8.
Malimg.
1.0
Convex*
183.1% clean]
Convex
[68.0% clean]
RS Gaussian
[80.5% clean]
RS Gaussian
[65.0% clean|
0.8
Laplacian
[82. clean]
R$ Laplacian
[66.6% clean]
Certified accuracy
RS Unitorm
[80.7% clean]
RS Uniform
[67.2% clean]
0.6
Splitting
[85.8% clcan]
Splitting
[73.0% clcan]
X a, 3-CROWN
[83.9% clean]
a, 3-CROWN
[61.6% clean]
Cayley
[87.5% clean]
Cayley
[76.1% clean]
0.4
eootNet
[79.4% clean]
x
0.2
x
0.0
2
0
2
4
6
Ig-radius
22-radius
(c) Fashion-MMaa shirts.
(d) CIFAR- cats cats-dogs.
Figure 9: Class certified radii curves for the norm.
15

---

1.0
Convex
[99.0% clean]
RS Gaussian
[99.8% clean]
0.8
RS Laplacian
[99.8% clean]
Certified accuracy
RS Uniform
[99.6% clean]
0.6
Splitting
[98.4% clean]
a, 8-CROWN
[99.2% clean]
Cayley
[100 % clean]
Convex
[97.9% clean]
0.4
-Net
[100 clean]
RS Gaussian
[98.0% clean]
Laplacian
[98.0% 0% clean]
R$ Uniform
[98.4% clean]
0.2
Spliting
[98. 098.6% clean]
x a, 8-CROWN 197.7% clean]
0.0
0.0
0.2
0.4
10
10
10
(a) MNIST 3-8.
(b) Maling.
1.0
Convex*
[83.1% clean]
Convex*
[68.0% clean]
Gaussian
[80.5% clean]
Gaussian
[65.0% clean]
0.8
RS Laplacian
[82.1% clean]
RS Laplacian
[66.6% clean]
Certified accuracy
Uniform
[80.7% clean]
RS Uniform
[67.2% clean]
0.6
Splitting
[85.8% clean]
Splitting
[73.0% clean]
X B-CROWN
[83.9% clcan]
X a, 8-CROWN
[61.6% clean]
Cayley
[87.5% clean]
Cayley
[76.1% clean]
0.4
eoo-Net
[79.4% clean]
0.2
x
0.0
0.0
0.1
0.2
018000
0.025
0.050
0.075
0.100
foc radius
-rdiius
(c) Fashion-MNIST shirts.
(d) CIFAR-10 cats-dogs.
Figure 10: Class certified radii curves for the & norm.
G
Ablation Tests
We conduct series of ablation tests the CIFAR-10 cats-dogs dataset, examining the impact of regularization, feature maps, and data augmentation.
G.1
Regularization
Figure 11 examines the impact of Jacobian regularization over a range of regularization scaling factors with corresponding to no regularization. As is typical, we see tradeoff between clean accuracy and certified radii. Further increases in À yield minimal additional benefit.
G.2 Feature Map
In this section, we investigate the importance of the feature map sp. Figure compares our standard feature-convex classifier with ((x)) = (x 14, x 14)) against an equivalent architecture with & = Id. Note that the initial layer get normalized before being passed into the convolutional architecture. We perform this experiment across both the standard cats-dogs experiment (cats are certified) in the main text and the reverse dogs-cats experiment (dogs certified).
convex ConvNet a BatchNorm, so even with y = Id, features still
16

---

1.0
À 0.0
[72.6% clean]
0.0025
[70.6% clean]
0.8
0.005
[68.2% clean]
0.0075
[68.0% clean]
Certified accuracy
[65.8% clean]
0.6
0.4
0.2
0.0
10
20
30
50
L fraddiss
Figure 11: Impact of the Jacobian regularization parameter À CIFAR-10 cats-dogs classification.
As expected, the clean accuracies for both datasets are lower for 0 1d, while the certified radii generally larger due to the Lipschitz scaling factor in Theorem 3.1 Interestingly, while the standard ie produces comparable performance both experiments, the identity feature map classifier is more effective in the dogs cats experiment, achieving around 7% greater clean accuracy. This reflects the observation that convex separability is an asymmetric condition and suggests that feature maps can mitigate this concern.
Cats-dogs (certifying cats)
Dogs-cats (certifying dogs)
1.0
ld Standard
(60.2% clean]
V Standard
[66.4% clean]
72.6% clcan]
[72.4% clean]
0.8
Certified accuracy
0.6
0.4
0.2
0.0
10
20
5
10
15
radius
E -radius
(a)
(b)
Figure 12: (a) Certification performance with cats as class and dogs as class 2. b Certification performance with dogs class and cats class 2.
G.3 Unaugmented Accuracies
Table 4
summarizes the experimental counterpart to Section 3.2 Namely, Fact 3.8 proves that there exists an input-convex classifier (y = Id) that achieves perfect training accuracy on the CIFAR-10 cats-dogs dataset with dataset augmentations (random crops, flips, etc.). Our practical experiments
17

---

are far from achieving this theoretical guarantee, with just 73.4% accuracy for cats cats-dogs and 77.2% for dogs-cats. Improving the practical performance input-convex classifiers match their theoretical capacity is an exciting area of future research.
Table 4: CIFAR-10 10 accuracies with no feature augmentation (pp = [d) and no input augmentation.
Class 1-class data
Training accuracy
Test accuracy (balanced)
Cats-dogs
73.4%
57.3%
Dogs-cats
77.2%
63.9%
H MNIST Classes Sweep
For our comparison experiments, we select specific challenging MNIST class pair (3 versus 8). For completeness, this section includes certification results for our method over all combinations of class pairs in MNIST, As this involves training models over 90 combinations, epochs from 60 to 10, maintaining all other architectural details described in Appendix
lower the number of
20
0.10
0.15
Non-scasiive class
2-
Non-sinsi closs
2
Non-stusi cluss
4
4.
4
Sensitive clars
Sensitive class
Sensitive class
(a) E1-certificates.
(b) Ez-certificates.
(c) Ex certiifiiass.
Figure 13: Plotting the median certified radii for the MNIST feature-convex architecture over a range of class combinations. The horizontal axis the class being certified. The MNIST 3-8 experiment considered throughout therefore corresponds to the cell (3, 8) in each plot.
Our certified radii naturally scale with the complexity of the classification problem. As expected, 3 and 8 are among the most challenging digits to distinguish, along with 2-8, 5-8, 4-9, and 7-9, Particularly easy combinations to classify typically include 0 or 1.
The certification performance is remarkably symmetric across the diagonal despite the asymmetry in our convex architectures. In other words, when classifying between digits and if convex classifier exists which generates strong certificates for i, then we can generally train an asymmetric classifier that generates strong certificates for j. A few exceptions the most notable are the 1-9 versus 9-1 pairs and the 4-8 versus 8-4 pairs. A deeper understanding of how class characteristics affect asymmetric certification is exciting avenue of future research.
this can be seen in Figure 13
I Randomized Smoothing Noise Level Sweeps
In this section, we reproduce the performance randomized smoothing classifiers under different noise distributions for range of noise parameters a. Namely, we sweep over multiples of base values of reported in the subcaptions of Figures 14 [5] and The base values of were set to a 0.75 for the MNIST 3-8, Mushion-MNISS and CIFAR-TU cats-dogs experiments. For the higher-resolution Maling experiment, we increase the base noise to a 3.5, matching the highest noise level examined in Levine and Feizi 44). The epochs used for training were similarly scaled by n, starting from the base values provided Section El with the exception the CIFAR-10 10 base epochs being increased to 600 epochs.
18

---

1.0
RS Gaussian (n o))
RS Gaussian (n σ)
0.8
RS Laplacian (n-o)
RS Laplacian (n-o)
Certified accuracy
RS Uniform (n)
RS Uniform (n.o)
0.6
Splitting (n r))
Splitting (n o)
0.4
0.2
0.0
0
4
0
50
100
150
(a) MNIST 3-8, 0.75.
(b) Malimg, 3.5.
1.0
RS Gaussian (n a))
RS Gaussian (n r7)
0.8
RS Laplacian (n o)
RS Laplacian (v o)
Certified accuracy
RS Uniform (n (n)
RS Uniform (n σ)
0.6
Splitting (n o)
Splitting (n- .)
0.4
0.2
0.0
5
10
f-radius
-rddius
(c) Fashaonn MNNIST shirts, = 0.75.
(d) CIFAR-10 cats-dogs, a = 0.75.
Figure 14: Randomized smoothing certified radii sweeps for the L norm. Line shade indicates value of the integer noise multiplier n, with ranging from 1 (darkest line) to 4 (lightest line).
19

---

1.0
RS Gaussian o))
RS Gaussian (n σ))
0.8
RS Laplacian (n-
RS Laplacian (n- o)
Certified accuracy
RS Uniform (n)
RS Uniform (n (n.o)
0.6
Splitting (n o)
Splitting (n (n)
0.4
0.2
0.0
3
40
(a) MNIST 3-8, 0.75.
(b) Malimg, 3.5.
1.0
RS Gaussian (n ())
RS Gaussian (n σ)
0.8
RS Laplacian (n o)
RS Laplacian (n.o)
Cerüified accuracy
RS Uniform (n.o) σ)
RS Uniform (n o)
0.6
Splitting (n-og o))
Splitting (n o)
0.4
0.2
0.0
2
4
0.0
2.5
5.0
7.5
10.0
22-radius
22-radius
(c) Dishion-MNIST shirts, 0.75.
(d) CIFAR-10 cats-dogs, 0.75.
Figure 15: Randomized smoothing certified radii sweeps for the f2-norm. Line shade indicates value of the integer noise multiplier n, with n ranging from (darkest line) to 4 (lightest line). For nigher-dimensione. inputs (Malimg and CIFAR- 10) methods which certify to different norm and convert are uncompetitive.
20

---

1.0
RS Gaussian (n o)
RS Gaussian (n σ)
0.8
RS Laplacian (n-o)
RS Laplacian (n-or
Certified accuracy
RS Uniform (n)
RS Uniform (n.o)
0.6
Splitting (n o))
Splitting (n o)
0.4
0.2
0.0
0.00
0.05
0.10
0.000
0.025
0.050
0.075
0.100
(a) MNIST 3-8, 0.75.
(b) Malimg, 3.5.
1.0
RS Gaussian (n .))
RS Gaussian (n- r7)
0.8
RS Laplacian (n o)
RS Laplacian (v a)
Certified accuracy
RS Uniform on)
RS Uniform (n σ)
0.6
Splitting (n o)
Splitting (n- .))
0.4
0.2
0.0
0.00
0.05
0.10
0.15
0.00
0.05
0.10
0.15
0.20
radius
faddius
(c) Fashion-MNNn shirts, 0.75.
(d) CIFAR-10 cats-dogs, o = 0.75.
Figure 16: Randomized smoothing certified radii sweeps for the for norm. Line shade indicates value of the integer noise multiplier n, with ranging from (darkest line) to 4 (lightest line).
21


Reviews:
[{"review_id": "5Elft3LSgc", "reviewer": "Reviewer_qP9X", "summary": "The paper is about certified robustness of neural networks.  In particular the authors explore the concept that there is typically a one-sided attack that needs to be certified since adversaries have certain goals that only work in certain directions (e.g., classify a spam email as ham).  The authors call this framework \"asymmetric robustness certification problem\" and approach a solution to this problem using a feature-convex neural network architecture.  The analysis is upon ReLU activation functions where the authors formalize and prove several results that are related to the geometry/convexity of the input data and how this can translate into the existence (not the identification) of a neural network that has perfect accuracy on the dataset.  Of course, it is a neural network at the end of the day and can be applied anywhere and observe its performance.  In this direction, eventually the authors evaluate their method on four different datasets against several baselines.\n\n**After Rebuttal:**\nI have read the reviews of others as well as the response by the authors. I am happy with the answers provided by the authors as well as their willingness to improve the presentation of the paper. I will upgrade my presentation score from 1 to 2 and also increase my overall score from borderline accept to weak accept.", "questions": "Q1. Are ReLU functions instrumental in the results that you prove? Can these results be extended to other activation functions?\n\nQ2. Apart from the experimental proof that cats and dogs from CIFAR-10 is convexly separable, were you aware of any classification datasets that are convexly separable and could motivate the work that you did?  Of course, this is not to diminish the work that you did; I am just asking.\n\nQ3. At the top of page 4 we see that a neural network is defined as a mapping\n$f \\colon R^d \\times R^n \\rightarrow R$.\nCan you explain why your input is decomposed to $(x, y)$, with $x\\in R^d$ and $y\\in R^n$, and why we have R in the output?", "limitations": "N/A", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "+ A new approach for certified robustness in a framework that deserves attention.\n+ The proposed method is backed up with theoretical guarantees.\n+ Experimental results on different datasets show that the method behaves well.", "weaknesses": "I think the main issue of the paper is the presentation of the results.  Granted the authors have put a lot of effort in this paper as it can be seen from the full paper.  Nevertheless: \n+ The authors use in many situations very long sentences and this makes it hard to follow their work, their descriptions, and ultimately give the appropriate merit to their work.  \n+ In addition to that, Section 3 and especially Section 3.2, is hard to follow as we have a sequence of definitions, propositions, and theorems that the authors prove as part theoretically justifying their method. \n+ Not only that, but it is hard to understand what is important and what is not for the story that the authors want to discuss.\n+ In Section 4 where we find the experiments, we have Figure 2 where the authors' method is compared against baseline methods. However, neither in the caption of the figure and the subfigures, nor in the actual text of the paper do we get to see what the other baselines are.  There are some keywords in the legends of the different subfigures, but no explanation.  Most likely RS X means randomized smoothing using noise X (but this is left as an exercise to the reader).  No more information about the rest of the cases is given either, neither are papers cited for these methods that are used as baselines (at least not in that section).  Also, there are some some percentage points next to each method which should present (from the context) that these values correspond to accuracy without any perturbations (and hence the \"clean\" word appearing next to these numbers) but really, these things need to be spelled out on the paper. One cannot really throw some figures on a paper, with keywords resembling names of certain methods but refuse to explain what these methods really are.  After looking into the appendix, indeed the authors there explain the names of the different methods and cite the relevant work, but this is happening 14 pages after the figure was presented to the reader.  I am sorry, but this is not how papers are read.\n\nI am really torn with this paper and I would like to see the views of the other reviewers. Nevertheless, I appreciate theoretical results and I am leaning more towards acceptance.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive suggestions. We have addressed all of your comments and questions below, and revised the manuscript accordingly.\n\n1. \"The authors use... long sentences\":\n\nWe have identified and revised some of our lengthier sentences: \"Specifically, we assume...\" (line 59); \"We characterize...\" (line 94); \"In contrast...\" (line 130); \"While high...\" (line 286). Please let us know if there were other areas of the text that you found convoluted.\n\n2/3. \"Section 3 and especially Section 3.2, is hard to follow\"... \"it is hard to understand what is important\":\n\nWe appreciate your feedback on the framing of our theoretical results. As reviewer 44oN raised similar concerns, please see our response and alterations in point 2 for Reviewer 44oN. If you have other suggestions on how we might adjust presentation and/or language to clarify our main contributions to the reader, we would appreciate hearing them.\n\n4. \"In Section 4... we [do not] get to see what the other baselines are\":\n\nWe have adjusted the experiments section according to each of your points brought up. In particular, we have moved the most pertinent details of the experiments from Appendix E to Section 4, and we have explicitly defined the keywords in the legends, including the baselines (with citations) as well as the clean accuracy numbers. We believe that, in following your suggestions, these edits make the presentation of our experimental results much clearer to the reader. Please find the revised text in the general response.\n\n\nQ1. \"Are ReLU functions instrumental in the results that you prove?\":\n\nOnly Theorems 3.6, 3.7, and the second part of Theorem 3.9 rely on ReLU activation functions, since we prove our uniform approximation theorem (Theorem 3.6) in terms of ReLU activations. In particular, our primary robustness certificate (Theorem 3.1) holds for general feature-convex models, which may be constructed using any convex nondecreasing activation functions. Notice also that the primary result of Theorem 3.9 (the fact that high-dimensional uniform datasets are convexly separable with high probability) is unrelated to architecture choice.\n\nQ2. \"...were you aware of any classification datasets that are convexly separable?\":\n\nYes. As mentioned in Appendix D, \"Yousefzadeh [74] and Balestriero et al. [9] showed a related empirical result for CIFAR-10, namely, that no test set image can be reconstructed as a convex combination of training set images.\" It is important to note that their result does not show the convex separability of two classes of training images, and therefore does not allow one to conclude that a feature-convex classifier can achieve perfect training accuracy. Therefore, our experiment on the cats-dogs training dataset is required in order for us to come to the conclusion of Corollary 3.8.\n\nQ3. \"Can you explain why your input is decomposed...\":\n\nThe work being cited there (Amos et al. [2]) proposed input-convex neural networks as a means to build a model $f(x,y)$ that is convex in the variable $y$, but possibly nonconvex in $x$. They use such a variable decomposition for the specific purposes of optimization-based inference with a real-valued output, i.e., mapping an input $x$ to an ouput defined by the convex optimization problem $\\arg\\min_{y} f(x,y) \\in \\mathbb{R}$. Since, in their application of optimization-based inference, one of the inputs to $f$ is being \"optimized out,\" they need to include an auxiliary/decomposed input so that there is still an input $x$ to be fed to $\\arg\\min_y f(x,y)$. On the other hand, our work, as well as many other works that use input-convexity (e.g., [16,17,48,75,79] in our manuscript), are not interested in optimization-based inference, but rather seek to exploit input-convexity for other reasons, so there is no part of the model input being \"optimized out.\" In our case, we exploit input convexity for purposes of model robustness. Therefore, our work (and the others listed) have no need for an auxiliary input or an input decomposition. That is, we simply use models $g(x)$ that are input-convex in the entire variable $x$."}, {"review_id": "AloJfxTQXG", "reviewer": "Reviewer_yvd4", "summary": "This paper considers a specific problem in binary classification task, where one class is recognized as a ‘sensitive’ class, which needs to be certified for robustness. The authors propose a special network called feature-convex neural network, which combines a Lipschitz network and a convex ReLU network. Expressive power of input-convex networks for convexly separable sets are provided. Experiments show that proposed networks achieve better performance on $l_1$ robustness compared to other certified robustness methods.", "questions": "1. When selecting the parameter $\\tau$ to shift the classification threshold, why use the balanced accuracy $\\alpha_2(\\tau)=\\alpha_1(\\tau)$, but not the commonly-used criterion in binary classification, F1-score or AUROC? Does there exist previous work using balanced accuracy for (asymmetric) binary classification?\n\n2. Can your method be extended to multi-class classification tasks?\n\n3. A very simple Lipschitz feature extractor $g$ is used in the proposed classifier. Can a more complex Lipschitz feature extractor be used to keep both certified robustness and accuracy high?\n\n4. In the proposed application on spam classification, why attackers only attempt to fool the classifier toward the “not-spam” class? The converse attack is more detrimental if the classifier recognizes a not-spam, important email as a spam one.", "limitations": "See weakness", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well-written and the problem and proposed method are clear.\n2. The proposed problem and method are new.\n3. The theoretical results are solid.", "weaknesses": "1. The proposed feature-convex network may limited classification power to be practically useful. The lower training accuracy on larger dataset like CIFAR-10 may imply that this architecture will be harder to apply in more complex real-world datasets.\n\n2. The verification of convex separability of CIFAR-10 cats vs dogs is confusing. The authors use convex optimization showing that certain cat image is hard to be recovered from the convex combination of dog images. Is this the sufficient evidence for convex separability? As authors mentioned, input-convex classifier is hard to fit the CIFAR-10 cats vs dogs data, which only achieves $70\\%+$ training accuracy. To make convex separability convincing, one may at least design an input-convex network architecture to achieve higher training accuracy (even without generalization ability).\n\n3. The experimental results are a little weak. The proposed feature-convex classifier only shows decent performance on $l_1$ robustness, but is suboptimal in $l_2$ and $l_{\\infty}$ robustness. As randomized smoothing is a more general certified method which is not designed for asymmetric binary classification, the suboptimality of feature-convex classifier shows the limited power of the proposed network.\n\n4. A two-layers neural network is used to evaluate the certified power of $\\alpha,\\beta$-CROWN. This seems to be a weaker baseline, as the conv-small net in $\\alpha,\\beta$-CROWN uses a four-layer convolutional network [1].\n\n5. The applications mentioned in the paper are mostly for imbalanced dataset (one class has more data than another), but the experiments are mostly for balanced dataset.\n\n[1] S Wang, H Zhang, K Xu, X Lin, S Jana, C J Hsieh, and J Z Kolter. Beta-CROWN: Efficient bound propagation with per-neuron split constraints for neural network robustness verification. In NeurIPS 2021.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We greatly appreciate your positive feedback on our paper's presentation, proposed problem/approach, and theory.\n\n1. \"The proposed feature-convex network may limit classification power...\":\n\nIn practice, we find our clean accuracies to be on par with the state-of-the-art robust classification baseline methods at a comparable level of certification performance (c.f., Figure 2). Corollary 3.8 further shows that our model is theoretically capable of attaining perfect training accuracy on CIFAR cats-dogs. Under standard training, our learned model on CIFAR achieves 73.4% accuracy, emphasizing that there is significant room for improvement. We are thus limited by standard architecture designs and training algorithms when applying them to input-convex models--not the capabilities of ICNNs themselves. We therefore hope that this result motivates future research on new algorithms that are specially tailored to FCNNs/ICNNS.\n\nWe have revised the manuscript to more clearly pose this open problem to the readers by adding the following \"Open Problem\" statement at line 292:\n\n\"**Open Problem 3.9.** Train an input-convex ReLU neural network that achieves 100% training accuracy on the unaugmented CIFAR-10 cats-versus-dogs dataset.\"\n\n2. \"The verification of convex separability of CIFAR-10 cats vs dogs is confusing\":\n\nWe use convex optimization to verify that, if you choose any cat image, it cannot be represented as a convex combination of the dog images. Hence, the set of cat images (call it, $X_1$) lies completely outside the convex hull of the dog images (call dog images $X_2$ and the convex hull of dog images $X$). This is precisely what it means for cats-dogs to be convexly separable: namely, that $X_2\\subseteq X$ and $X_1\\subseteq \\mathbb{R}^d \\setminus X$. This analysis of the dataset is therefore sufficient to conclude convex separability. That our learned ICNN (using standard training) achieves 73.4% training accuracy does not alter the fact that cats-dogs is convexly separable, as the above experiment already verifies the separability. As discussed above, this points to the need for novel ICNN designs and training algorithms to unlock their full potential.\n\n3. \"The experimental results are a little weak\":\n\nWe emphasize that our approach features several substantial benefits over randomized smoothing. Unlike our deterministic certificates, RS is inherently probabilistic (since it is based on an empirical expectation): there is always a strictly positive probability of a RS classifier producing a prediction that violates its own certificates. Furthermore, randomized smoothing approaches are highly computationally intensive, taking on the order of seconds while our certificates are closed-form and can be computed in milliseconds (~$1000\\times$ speedup). As our certificates are generally comparable (for $\\ell_2$/$\\ell_\\infty$-norms) or decidedly superior ($\\ell_1$-norm), we consider these advantages to be significant enough to highlight the promise of our method.\n\n4. \"A two-layers neural network is used to evaluate ... $\\alpha,\\beta$-CROWN\":\n\nWe used a smaller network for $\\alpha,\\beta$-CROWN to increase the verification performance of the baseline, as larger networks tended to be more computationally intensive to certify at a particular radius and runtime.\n\n5. \"The applications mentioned in the paper are mostly for imbalanced dataset\":\n\nWe focus our evaluation primarily on balanced datasets to avoid added analysis complexity, as the work is already quite lengthy. We note that our framework and method apply equally to the balanced and unbalanced scenarios.\n\nQ1. \"...why use the balanced accuracy...\":\n\nWe balance the class accuracies in order to provide a fair comparison of certified accuracy curves across different methods. Otherwise, consider Method A and Method B, where Method A has a superior certified accuracy curve and Method B has a higher clean accuracy for the non-sensitive class; it would be difficult to compare the two methods' certified accuracy curves as it is unclear how much of Method A's advantage came from compromising on non-sensitive class accuracy. Thus, we feel our approach is best for providing directly interpretable certified accuracy curves in the asymmetric setting. Note that in practice a user can adjust the threshold however they see fit--we chose this approach to fascilitate fair and standardized comparisons between methods.\n\nQ2. \"Can your method be extended to multi-class...\":\n\nYes. On line 168 in the main paper, we refer to the supplemental material where we propose two ways to extend our method to multi-class settings. Our multi-class generalizations allow for efficient and closed-form asymmetric robustness certificates either for one sensitive class, or one \"group\" of sensitive classes.\n\nQ3. \"Can a more complex Lipschitz feature extractor be used...\":\n\nAny feature map can be used so long as it provides a bounded Lipschitz constant. However, more complicated feature maps may come at the expense of a larger Lipschitz constant, resulting in smaller robustness certificates. Therefore, the feature map should be kept as simple as possible to assist with (ideally closed-form) computation of a small Lipschitz constant, but sophisticated enough to make the data convexly separable. Designing and/or learning low-Lipschitz yet high-performing feature maps is left as future work.\n\nQ4. \"...why attackers only attempt to fool the classifier toward the not-spam class?\":\n\nBy definition, a message generated by an attacker is spam, and therefore the only way they can possibly fool the classifier is if they craft a message that is classified as non-spam. Our natural goal is therefore to certify that an adversary cannot \"lightly edit\" a spam email to make it look to us like non-spam. On the other hand, your proposed situation is not adversarial in nature. An adversary would not craft genuinely important non-spam emails while trying to fool the classifier into thinking that they are spam.\n"}, {"review_id": "2QhA8AjpZl", "reviewer": "Reviewer_44oN", "summary": "This paper tackles the asymmetric nature of classification and adversarial attacks intrinsic in most real-world scenarios that have a live and motivated attacker: that attacks are unidirectional, and proposes a general-purpose technique for specifying a certifiably robust defense in such scenarios. This is done by using an Input Convex Neural Network (ICNN) to guarantee the convexity of the function $g(x)$, and then double-backprop is applied to get the gradient of the ICNN with respect to its input to compute the certificate radius. \n\n-------\n\nI think my concerns are mostly addressed. I'm waffling between 6/7, so at least updating my minimum confidence. ", "questions": "1. How much faster is your approach at certifying a radius against each other classifier? This should be in the experiments section to justify the value of the method. \n2. Is there a predictive difference in your approach verses other methods (I suspect yes, e.g., randomized smoothing)? See Q1, it should be in Experiments. \n3. I read the appendix and it says the \"pixels\" in malimage are [0, 255] encoded. Wouldn't that mean 10^4/255 = 39 pixels can be altered? It looks like others are right around the one-pixel attack radius in this case. \n4. Why not use the neural network approach/data from _SOREL-20M: A large scale benchmark dataset for malicious PE detection_? The MalImage dataset is highly flawed, taking an approach (\"malware images\") that has been long known to be errant (_Malware Detection by Eating a Whole EXE_) and has significant issues in failing to account for biases that occur in the malware space (_TESSERACT: Eliminating Experimental Bias in Malware Classification across Space and Time_). ", "limitations": "Limitations are maybe sufficiently addressed, see questions. ", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 1, "contribution": 4, "strengths": "1. Valuable theoretical contribution to how adversarial machine learning works in real-life, over unmotivated fears about a computer-vision boogie man. \n2. Comparisons against many alternative certifiable defenses, with significant improvement in some cases. \n3. Should be faster, but such results are obscured. ", "weaknesses": "1. The experimental section is woefully presented and obscures the nature of the benefit, abdicating the setup/explanation to the appendix is not acceptable in my opinion. \n2. The mathematical presentation (additionally not helped by the NeurIPS template) is hard to follow, e.g. the setup for the reader in section 1.3 is crammed into a tightly packed paragraph to hit the page limit, and the readability suffers. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments and questions. We have addressed them below, and revised the manuscript accordingly.\n\n1. \"The experimental section...\":\n\nAs mentioned in our response to Reviewer qP9X, we have revised the Experiments section to satisfy your suggestions. In particular, we have moved the most pertinent details of the experimental setup from Appendix E to Section 4, and we have explicitly defined the keywords in the legends, including the baselines (with citations) as well as the clean accuracy numbers. We believe these edits make the presentation of our experimental results self-contained and much clearer to the reader. Please find the revised section in the general response. \n\n2. \"The mathematical presentation... is hard to follow, e.g.... section 1.3\":\n\nWe made the following revisions to the mathematical presentation according to your comments and the suggestions from Reviewer qP9X:\n\na) We have moved Propositions 3.4 and 3.5 (that characterize the decision region geometry) to Appendix C, for two reasons:\n\ni) To more clearly highlight the important theorems and avoid a long sequence of mathematically dense results.\n\nii) To make room for our experimental details added to Section 4. In place of these propositions, we have modified lines 250--254 with the more easily understood description:\n\n\"Although low-dimensional intuition may cause concerns regarding the convex separability of sets of binary-labeled data, we will soon see in Corollary 3.8 and Theorem 3.9 that, even the CIFAR-10 cats and dogs classes are convexly separable, as well as relatively unstructured binary datasets in high dimensions (with high probability). This convex separability of datasets is an highly advantageous property, as input-convex classifiers may always perfectly fit such data, and conversely, input-convex classifiers have interpretable decision regions consisting of a convex set and its complement (the latter of which is not necessarily true for our more general feature-convex architectures with $\\varphi\\ne\\text{Id}$). We formally state and prove these geometric characterizations in Propositions 3.4 and 3.5 of Appendix C.\"\n\nb) We have updated the first paragraph of Section 3 to clarify the importance of the presented results:\n\n\"We present our main theoretical results in this section. First, we derive asymmetric robustness certificates (Theorem 3.1) for our feature-convex classifiers in Section 3.1. Then, in Section 3.2, we introduce the notion of convexly separable sets in order to theoretically characterize the representation power of our classifiers. Our primary representation results give a universal function approximation theorem for our classifiers with $\\varphi=\\text{Id}$ and ReLU activation functions (Theorem 3.6) and show that such classifiers can perfectly fit convexly separable datasets (Theorem 3.7), including the CIFAR-10 cats-dogs training data (Corollary 3.8). We also show that this strong learning capacity generalizes by proving that feature-convex classifiers can perfectly fit high-dimensional uniformly distributed data with high probability (Theorem 3.9).\"\n\nSince the notations introduced in Section 1.3 are used throughout the paper, we find it best to define them up front and in their own short section for reference. We are open to any suggestions you may have for enhancing the readibility of Section 1.3.\n\nQ1. \"How much faster is your approach...\":\n\nTo make the runtime discussion in Section 4 more explicit, we ran a quick benchmark on the CIFAR cats-dogs dataset:\n\n| Method | Certification time (s) |\n| ------ | ------------------ |\n| FCNN | 0.0021 | \n| RS Laplace | 5.95 |\n| RS Gauss | 5.89 |\n| RS Uniform | 5.91 |\n| Splitting | 0.08 |\n| Cayley | 0.052 |\n\nAll RS methods use 100,000 samples. $\\alpha,\\beta$-CROWN is more difficult to compare directly as runtime is computed per property; but generally it is far more computationally expensive and takes on the order of tens of seconds. We also note that the splitting method scales linearly with noise and image size and thus takes on the order of several minutes per sample on Malimg.\n\nQ2. \"Is there a predictive difference...\":\n\nYes, the predictions and certificates are fundamentally different in nature between the three randomized smoothing baselines and deterministic methods (including our deterministic method). We have added the following sentence to the Experiments section to remind the reader of this fact and more clearly categorize the different methods in consideration:\n\n\"Notice that the three randomized smoothing baselines have fundamentally different predictions and certificates than the deterministic methods (including ours), namely, the predictions are random and the certificates hold only with high probability.\"\n\nQ3. \"Wouldn't that mean 10^4/255 = 39 pixels can be altered?\": \n\nWe normalize the pixel values to $[0, 1]$. We have added the clarifying sentence \"All pixel values are normalized into the interval $[0,1]$.\" to Section 4 of the manuscript.\n\nQ4. \"Why not use ... SOREL-20M...\":\n\nThe baseline network proposed in SOREL-20M operates on features extracted from the binary. An architecture that certifies robustness to changes in features is difficult to analyze, as the implications for robustness in bit-space (which the adversary can directly manipulate) are unclear. While more sophisticated approaches for classifying directly on bit-space exist (see [25] in our manuscript), we consider these outside the aim of our work. Our primary aim is to introduce a more general framework of certified asymmetric robustness (not just for malware). We used Malimg to give an intuitive practical application that naturally fits within this asymmetric framework; we are making no claims regarding whether the Malimg approach is good or bad for the specific problem of malware classification."}, {"review_id": "bPWMDYBzUJ", "reviewer": "Reviewer_g6eM", "summary": "This paper is based on the following elegant observation: Consider the case of binary classification in which we learn a function $f: \\mathbb R^e\\to \\mathbb R$ and classify a point based on thresh-holding $f$ at 0. Assume $f(x)=g(\\phi(x))$ where $f:\\mathbb R^m \\to \\mathbb R$ is convex and $\\phi$ is Lipschitz. Then using the Lipschitz consonant of $\\phi$ and the fact that $g(y)\\geq g(\\phi(x))+\\nabla g(\\phi(x))\\cdot (h-\\phi(x))$ for any subgradient of $g$, one can easily compute a robustness certification for $f$. The authors then argue that this paradigm is fairly applicable to adversarial binary classification based on the following observations: 1) If $m$ is larger than the number of data points and $\\phi$ is the identity, then there is a convex function achieving perfect accuracy. 2) There are many adversarial classification tasks involving asymmetric binary classification such as malware detection and spam detection", "questions": "See the questions in the first two bullets of \"Weaknesses\". A convincing response to the first bullet could significantly change my opinion on the rating of this paper.", "limitations": "See the first two bullets under \"Weaknesses\"", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "- computation of a robust certificate for this method is much faster than competing methods and achieves comparable performance\n- formalizes the fact that in many real world applications, adversarial classification is an asymmetric problem\n- exposition is excellent and bibliography is very thorough ", "weaknesses": "- Binary classification problems are often handled by SVMs, for which a robust certification is easy to compute. These models are simpler and easier to train than neural nets. Furthermore, one expects some robustness to arise from these models as they minimize the maximum margin. This paper does not compare accuracy or robustness with SVMs. For instance, due to Corrollary 3.8, I would expect SVMs to perform well on the CIFAR 10 example. Can you find an example where your method does better than an SVM in terms of either accuracy or robustness?\n- Consider $\\hat g$ as defined in definition 2.2 If $b_2,\\ldots b_\\ell\\geq 0$, the last $\\ell-1$ layers reduce to a linear function. This observation suggests that depth for convex neural nets has fairly different effects than depth for standard neural nets. This observation further suggests that to achieve an expression $\\hat g$, $\\ell$ would need to be quite large. Can you elaborate on your choice of $\\ell$? \n- There are many instances for which the dimension of the dataset $d$ is less than the number of data points. One would expect that using a non-identity $\\phi$ in these cases would be advantageous. The paper does not discuss how to choose $\\phi$ in this case\n- Comment: I would call \"Corollary 3.8\" a \"Fact\" rather than a \"Corollary\". Optimization in finite precision arithmetic always has errors, which is weaker than a formal proof. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your kind complement on the exposition of our paper. We appreciate your constructive suggestions, which we address below.\n\n1. \"Can you find an example where your method does better than an SVM in terms of either accuracy or robustness?\":\n\nCertainly, we have shared the relevant script with the AC through an anonymized link (as per the rebuttal guidelines). For the CIFAR-10 task that you mentioned, a linear SVM only achieves a 54.8% clean accuracy, compared to 68% for our method (with regularization). We also experimented with adding the same Lipschitz-continuous feature map that we used for our architecture (the concatenation $x\\mapsto (x,|x|)$, after shifting the images to be in the $[-0.5, 0.5]$ range). This only marginally improved the clean accuracy of the SVM to 55.6%. Certification performance is also roughly an order of magnitude worse than our method across all norms---e.g., the maximum $\\ell_1$-norm certified radius was just 2.93, compared to over 30 for our method. This reflects the fact that convex classifiers are significantly more flexibile than linear classifiers, while retaining fast certification computation by using linear underapproximators. Note that Corollary 3.8 applies to the class of input-convex ReLU neural networks; it does not imply that an SVM can achieve perfect training accuracy, since SVMs constitute only a small subset of all possible convex classifiers. For an SVM to achieve perfect training accuracy, the dataset would need to be linearly separable, which is a much stronger condition than the convex separability in both directions (cats-dogs and dogs-cats) that we show (e.g., consider class 1 points at $(-1,0),(1,0)\\in\\mathbb{R}^d$ and class 2 points at $(0,-1),(0,1)\\in\\mathbb{R}^2$, which are convexly separable in both directions but not linearly separable).\n\nHere are the clean accuracies and maximum certified radii for the SVM on the CIFAR-10 cats-dogs task, outputted from the script:\n\n**With no feature map:**\n\nClean accuracy: 0.548\n\nl1: 2.930618825346973\n\nl2: 0.2083568160433327\n\nlinf: 0.004723921349099762\n\n**With the $(x, |x|)$ feature map:**\n\nClean accuracy: 0.556\n\nl1: 1.4921445716893802\n\nl2: 0.11696300733917692\n\nlinf: 0.002664742804160659\n\n2. \"Consider $\\hat{g}$ as defined in definition 2.2...\":\n\nThe biases $b^{(l)}$ are not constrained to be nonnegative, and even if they are nonnegative, the $l$th layer may still be nonlinear in the \"passthrough\" $x^{(0)}$, since $C^{(l)}x^{(0)}$ is fed into the activation with $C^{(l)}$ having possibly negative elements. This nonlinearity then propagates into all subsequent layers.\n\nWe selected our layer count $L$ empirically based on certification performance, finding that relatively shallow networks tend to suffice (i.e., $5$ layers for CIFAR-10 cats-dogs). We presume that this is tied to the documented tendency for ICNNs to avoid overfitting (see [60] in our manuscript), although a more thorough investigation of this phenomenom is better suited for future work.\n\n3. \"The paper does not discuss how to choose $\\phi$ in this case\":\n\nThe relationship between dataset dimensionality and the number of datapoints is quite complex, and our feeling is that the characteristics of the dataset distribution are practically more important than its dimension. For example, many noncomplex datasets in lower dimensions might be well classified with a simple classifier, and don't need any feature map (i.e., the MNIST 3-8 dataset). On the other hand, the higher dimensional CIFAR cats-dogs dataset benefited significantly from a feature map (see appendix G.2). While our Theorem 3.9 does begin to look at the interplay of dimension and separability, a more empirical investigation of this phenomenon and appropriate feature maps is better suited for future work.\n\n4. \"Optimization in finite precision arithmetic always has errors, which is weaker than a formal proof\":\n\nYour point on finite precision is a good one. Thus, we have re-labeled the result as a \"Fact,\" per your suggestion.\n\nQ1. \"A convincing response to the first bullet could significantly change my opinion on the rating...\":\n\nThank you for your openness. We have addressed each of your raised points, and in particular demonstrated the superiority of our method over SVMs, as per your first bullet point. We hope that you find our updates sufficient to significantly change your rating, and appreciate your help in enhancing the paper."}]

Author rebuttal:
We sincerely thank the Reviewers for their insightful comments and valuable suggestions. We are happy to see that 3/4 reviews are generally positive on our work, with primarily presentation-focused concerns that we address below. Reviewer g6eM has indicated their willingness to update their score with a convincing SVM comparison, which we have also provided.

Please see our individual responses to each Reviewer, where we address each point raised and highlight the corresponding revisions we have made to the manuscript. Here, we briefly describe the main revisions:

1. Mathematical presentation: we have edited and added descriptions in Section 3 to ensure the theoretical results are easily understood by the reader, and to more clearly illustrate the importance of such results and how they play into the overall story of the paper. In doing so, we moved Propositions 3.4 and 3.5 to Appendix C, and added in their place a more easily readable description of what they say.

2. Experiments: we have moved the most pertinent details of the experiments from Appendix E to Section 4, explicitly describing the datasets, baselines (with citations), and our model's architecture, in addition to defining the keywords in the legends and the clean accuracy numbers reported in Figure 2. We believe that, in following the Reviewers' suggestions, these edits make the presentation and contextualization of our experimental results much clearer to the reader and aid in justifying our work.

_Experimental section addition._

"This section compares our feature-convex classifiers against a variety of state-of-the-art baselines in the asymmetric setting. Before discussing the results, we briefly describe the datasets, baselines, and architectures used. For a more in-depth description and hyperparameter details, see Appendix E.

**Datasets.** We evaluate our approach using four datasets. First, we consider distinguishing between $28\times 28$ greyscale MNIST digits $3$ and $8$ [37], which are generally more visually similar and challenging to distinguish than other digit pairs. Next, we consider identifying malware from the "Allaple.A" class in the Malimg dataset of $512\times 512$ bytewise encodings of malware [51]. We then consider distinguishing between shirts and T-shirts in the Fashion-MNIST dataset of $28\times 28$ greyscale images [70], which tend to be the hardest classes to distinguish [33]. Finally, we consider the $32\times 32$ RGB CIFAR-10 cat and dog images since they are again relatively difficult to distinguish [26,44,30]. The latter two datasets can be considered as our more challenging settings. All pixel values are normalized into the interval $[0,1]$.

**Baseline Methods.** We consider several state-of-the-art randomized and deterministic baselines. For all datasets, we evaluate the randomized smoothing certificates of [72] for the Gaussian, Laplacian, and uniform distributions trained with noise augmentation (denoted RS Gaussian, RS Laplacian, and RS Uniform, respectively), as well as the deterministic bound propagation framework $\alpha,\beta$-CROWN [66], which is scatter plotted since certification is only reported as a binary answer at a given radius. We also evaluate, when applicable, deterministic certified methods for each norm ball. These include the splitting-noise $\ell_1$-certificates from [40] (denoted Splitting), the orthogonality-based $\ell_2$-certificates from [63] (denoted Cayley), and the $\ell_{\infty}$-distance-based $\ell_{\infty}$-certificates from [77] (denoted $\ell_\infty$-Net). The last two deterministic methods are not evaluated on the large-scale Malimg dataset due to their prohibitive runtime. Furthermore, the $\ell_{\infty}$-Net was unable to significantly outperform a random classifier on the CIFAR-10 cats-dogs dataset, and is therefore only included in the MNIST 3-8 and Fashion-MNIST shirts experiments. Notice that the three randomized smoothing baselines have fundamentally different predictions and certificates than the deterministic methods (including ours), namely, the predictions are random and the certificates hold only with high probability.

**Feature-Convex Architecture.** Our simple experiments (MNIST 3-8 and Malimg) require no feature map to achieve high accuracy ($\varphi=\text{Id}$). The Fashion-MNIST shirts dataset also benefited minimally from the feature map inclusion. For the CIFAR-10 cats-dogs task, we let our feature map be the concatenation $\varphi(x)=(x-\mu,|x-\mu|)$, as motivated by Appendix B, where $\mu$ is the channel-wise dataset mean (e.g., size $3$ for an RGB image) broadcasted to the appropriate dimensions. Our MNIST 3-8 and Malimg architecture then consists of a simple two-hidden-layer input-convex multilayer perceptron with $(n_1,n_2)=(200,50)$ hidden features, ReLU nonlinearities, and passthrough weights. For the Fashion-MNIST shirts (CIFAR-10 cats-dogs, resp.) dataset, we use a convex ConvNet architecture consisting of $3$ ($5$, resp.) convolutional, BatchNorm, and ReLU layers. All models are trained using SGD on the standard binary cross entropy loss with Jacobian regularization, and clean accuracies are balanced as described in Section 1.1 and Appendix E.4 to ensure a fair comparison of different robustness certificates.

**Results and Discussion.** Experimental results for $\ell_1$-norm certification are reported in Figure 2, where our feature-convex classifier radii, denoted by Convex*, are similar or better than all other baselines across all datasets. Also reported is each method's clean test accuracy without any attacks, denoted by "clean."..."

Meta-review: Dear Authors,

Thank you for your valuable contribution to Neurips and the ML community. Your submitted paper has undergone a rigorous review process, and I have carefully read feedback provided by the reviewers and considered the author rebuttal in detail.

This paper is focused on constructing certifiably robust neural networks. The authors employ input convex neural networks and Lipschitz continuity to design robust models. They propose applying double-backprop to get the gradient of the network with respect to its input to compute the robustness radius. The reviewers all agree that the introduced method is novel and interesting, the numerical results are good and writing of the paper is high-quality.

Given this positive assessment, I am willing to recommend the acceptance of your paper for publication.

I would like to remind you to carefully review the reviewer feedback and the resulting discussion. While most reviews were positive, the reviewers have offered valuable suggestions that can further strengthen the quality of the paper. Please take another careful look a the 'weaknesses' section of each reviewer comment. Please also review the discussions with Reviewer yvd4, whose review was the most critical. I encourage you to use the feedback to make any necessary improvements and refinements before submitting the final version of your paper.

Once again, thank you for submitting your work to Neurips.

Best,
Area Chair
Decision: Accept (poster)