Asymmetric Certified Robustness via Feature-Convex Neural Networks
Recent works have introduced input-convex neural networks (ICNNs) as learning
models with advantageous training, inference, and generalization properties
linked to their convex structure. In this paper, we propose a novel
feature-convex neural network architecture as the composition of an ICNN with a
Lipschitz feature map in order to achieve adversarial robustness. We consider
the asymmetric binary classification 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 MNIST, Fashion-MNIST, and CIFAR-10 datasets show that feature-convex
classifiers attain state-of-the-art certified $\ell_1$-radii as well as
substantial $\ell_2$- and $\ell_{\infty}$-radii while being far more
computationally efficient than any competitive baseline.
Samuel Pfrommer, Brendon G. Anderson, Julien Piet, Somayeh Sojoudi
# Asymmetric Certified Robustness via Feature-Convex Neural Networks

###### Abstract

Recent works have introduced input-convex neural networks (ICNNs) as learning models with advantageous training, inference, and generalization properties linked to their convex structure. In this paper, we propose a novel _feature-convex neural network_ architecture as the composition of an ICNN with a Lipschitz feature map in order to achieve adversarial robustness. We consider the asymmetric binary classification 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 MNIST, Fashion-MNIST, and CIFAR-10 datasets show that feature-convex classifiers attain state-of-the-art certified \(\ell_{1}\)-radii as well as substantial \(\ell_{2}\)- and \(\ell_{\infty}\)-radii while being far more computationally efficient than any competitive baseline. 1

Footnote 1: Code for reproducing our results is available on GitHub.

## 1 Introduction

Although neural networks achieve state-of-the-art performance across a range of machine learning tasks, researchers have shown that they can be highly sensitive to adversarial inputs that are maliciously designed to fool the model (Biggio et al., 2013; Szegedy et al., 2014; Nguyen et al., 2015). For example, the works Eykholt et al. (2018) and Liu et al. (2019) show that small physical and digital alterations of vehicle traffic signs can cause image classifiers to fail. In safety-critical applications of neural networks, such as autonomous driving (Bojarski et al., 2016; Wu et al., 2017) and medical diagnostics (Amato et al., 2013; Yadav & Jadhav, 2019), this sensitivity to adversarial inputs is clearly unacceptable.

A line of heuristic defenses against adversarial inputs has been proposed, only to be defeated by stronger attack methods (Carlini & Wagner, 2017; Kurakin et al., 2017; Athalye et al., 2018; Uesato et al., 2018; Madry et al., 2018). This has led researchers to develop certifiably robust methods that provide a provable guarantee of safe performance. The strength of such certificates can be highly dependent on network architecture; general off-the-shelf models tend to have large Lipschitz constants, leading to loose Lipschitz-based robustness guarantees (Hein & Andriushchenko, 2017; Fazlyab et al., 2019; Yang et al., 2020). Consequently, lines of work that impose certificate-amenable structures onto networks have been popularized, e.g., specialized model layers (Trockman & Kolter, 2021; Zhang et al., 2021), randomized smoothing-based networks (Li et al., 2019; Cohen et al., 2019; Zhai et al., 2020; Yang et al., 2020; Anderson & Sojoudi, 2022), and \(\mathrm{ReLU}\) networks that are certified using convex optimization and mixed-integer programming (Wong & Kolter, 2018; Weng et al., 2018; Raghunathan et al., 2018; Anderson et al., 2020; Ma & Sojoudi, 2021). 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 method families incur serious computational challenges: randomized smoothing typically requires the classification of thousands 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 are unnecessarily restrictive for most 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 a binary setting with only one _sensitive class_ that must be made robust to adversarial perturbations. Consider the representative problem of spam classification; a malicious adversary crafting a spam email will always attempt to fool the classifier toward the "not-spam" class--never conversely (Kuchipudi et al., 2020). Similar logic applies for a range of applications, including malware detection (Grosse et al., 2017), mali
cious network traffic filtering (Sadeghzadeh et al., 2021), fake news and social media bot detection (Cresci et al., 2021), hate speech removal (Grolman et al., 2022), insurance claims filtering (Finlayson et al., 2019), and financial fraud detection (Cartella et al., 2021).

These applications motivate us to introduce a narrower, asymmetric robustness problem and develop a novel classifier architecture to address this challenge.

### Problem Statement and Contributions

This work considers the problem of _asymmetric robustness certification_. Specifically, we assume a classification setting wherein one class is "sensitive" and seek to certify that, if some input is classified into this sensitive class, then adversarial perturbations of sufficiently small magnitude cannot change the prediction.

To tackle the asymmetric robustness certification problem and attain state-of-the-art certified radii, we propose _feature-convex neural networks_, and achieve the following contributions in doing so:

1. We provide easily-computable class \(1\) certified robust radii for feature-convex classifiers with respect to arbitrary \(\ell_{p}\)-norms.
2. We characterize the decision region geometry of feature-convex classifiers, extend the universal approximation theorem for input-convex \(\mathrm{ReLU}\) neural networks to the classification setting, and show that, in high dimensions, feature-convex classifiers can perfectly fit even unstructured, uniformly distributed datasets.
3. We evaluate against several baselines on MNIST 3-8 (LeCun, 1998), Malimg malware classification (Nataraj et al., 2011), Fashion-MNIST shirts (Xiao et al., 2017), and CIFAR-10 cats-dogs (Krizhevsky et al., 2009), and show that our classifiers yield state-of-the-art certified robust radii.

### Related Works

Certified adversarial robustness.Three of the most popular approaches for generating robustness certificates are Lipschitz-based bounds, randomized smoothing, and convex optimization. Successfully bounding the Lipschitz constant of a neural network can give rise to an efficient certified radius of robustness, e.g., via the methods proposed in Hein & Andriushchenko (2017). However, in practice such Lipschitz constants are too large to yield meaningful certificates, or it is computationally burdensome to compute or bound the Lipschitz constants in the first place (Virmaux & Scaman, 2018; Fazlyab et al., 2019; Yang et al., 2020). To overcome these computational limitations, certain methods impose special structures on their model layers to provide immediate Lipschitz guarantees. Specifically, Trockman & Kolter (2021) uses the Cayley transform to derive convolutional layers with immediate \(\ell_{2}\)-Lipschitz constants, and Zhang et al. (2021) introduces a \(\ell_{\infty}\)-distance neuron that provides similar Lipschitz guarantees with respect to the \(\ell_{\infty}\)-norm. We compare with both these approaches in our experiments.

Randomized smoothing, popularized by Lecuyer et al. (2019); Li et al. (2019); Cohen et al. (2019), uses the expected prediction of a model when subjected to Gaussian input noise. These works derive \(\ell_{2}\)-norm balls around inputs on which the smoothed classifier remains constant, but suffer from nondeterminism and high computational burden. Follow-up works generalize randomized smoothing to certify input regions defined by different metrics, e.g., Wasserstein, \(\ell_{1}\)-, and \(\ell_{\infty}\)-norms (Levine & Feizi, 2020; Teng et al., 2020; Yang et al., 2020). Other works focus on enlarging the certified regions by optimizing the smoothing distribution (Zhai et al., 2020; Eiras et al., 2021; Anderson et al., 2022), incorporating adversarial training into the base classifier (Salman et al., 2019; Zhang et al., 2020), and employing dimensionality reduction at the input (Pfrommer et al., 2022).

Convex optimization-based certificates seek to derive a convex 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-approximations have been proposed, e.g., based on linear programming and bounding (Wong & Kolter, 2018; Weng et al., 2018), semidefinite programming (Raghunathan et al., 2018), and branch-and-bound approaches (Anderson et al., 2020; Ma & Sojoudi, 2021; Wang et al., 2021). The \(\alpha,\beta\)-CROWN method (Wang et al., 2021) uses an efficient bound propagation to linearly bound the neural network output in conjunction with a per-neuron branching heuristic to achieve state-of-the-art certified radii, winning both the 2021 and the 2022 VNN certification competitions (Bak et al., 2021; Muller et al., 2022). In contrast to these optimization-based methods, our approach in this paper is to directly exploit the convex structure of input-convex neural networks to derive closed-form robustness certificates for our proposed architecture, altogether avoiding the common efficiency-tightness tradeoffs of prior methods, which we find to compete with and even outperform the state-of-the-art \(\alpha,\beta\)-CROWN in several settings.

Input-convex neural networks.Input-convex neural networks, popularized by Amos et al. (2017), are a class of parameterized models whose input-output mapping is convex (in at least a subset of the input variables). In Amos et al. (2017), the authors develop tractable methods to learn
an input-convex neural network \(f\colon\mathbb{R}^{d}\times\mathbb{R}^{n}\to\mathbb{R}\) and show that utilizing it for the convex optimization-based inference \(x\mapsto\arg\min_{y\in\mathbb{R}^{n}}f(x,y)\) yields state-of-the-art results in a variety of domains. Subsequent works propose novel applications of input-convex neural networks in areas such as optimal control and reinforcement learning (Chen et al., 2019; Zeng et al., 2022), optimal transport (Makkuva et al., 2020), and optimal power flow (Chen et al., 2020; Zhang et al., 2021). Other works have generalized input-convex networks to input-invex networks (Nesterov et al., 2022) and global optimization networks (Zhao et al., 2022) so as to maintain the benign optimization properties of input-convexity. The authors of Siahkamari et al. (2022) present algorithms for efficiently learning convex functions, while Chen et al. (2019); Kim and Kim (2022) derive universal approximation theorems for input-convex neural networks in the convex regression setting. The work Sivaprasad et al. (2021) shows that input-convex neural networks do not suffer from overfitting, and generalize better than multilayer perceptrons on common benchmark datasets. In this work, we incorporate input-convex neural networks as a part of our overall feature-convex architecture, and we leverage convexity properties to derive our novel robustness guarantees.

### Notations

The sets of natural numbers and real numbers are denoted by \(\mathbb{N}\) and \(\mathbb{R}\), respectively. The \(d\times d\) identity matrix is written as \(I_{d}\in\mathbb{R}^{d\times d}\), and the identity map on \(\mathbb{R}^{d}\) is denoted by \(\operatorname{Id}\colon x\mapsto x\). For \(A\in\mathbb{R}^{n\times d}\), we define \(|A|\in\mathbb{R}^{n\times d}\) by \(|A|_{ij}=|A_{ij}|\) for all \(i,j\), and we write \(A\geq 0\) if and only if \(A_{ij}\geq 0\) for all \(i,j\). The \(\ell_{p}\)-norm on \(\mathbb{R}^{d}\) is given by \(\|\cdot\|_{p}\colon x\mapsto(|x_{1}|^{p}+\cdots+|x_{d}|^{p})^{1/p}\) for \(p\in[1,\infty)\) and by \(\|\cdot\|_{p}\colon x\mapsto\max\{|x_{1}|,\ldots,|x_{d}|\}\) for \(p=\infty\). The dual norm of \(\|\cdot\|_{p}\) is denoted by \(\|\cdot\|_{p,*}\). The convex hull of a set \(X\subseteq\mathbb{R}^{d}\) is denoted by \(\operatorname{conv}(X)\). The subdifferential of a convex function \(g\colon\mathbb{R}^{d}\to\mathbb{R}\) at \(x\in\mathbb{R}^{d}\) is denoted by \(\partial g(x)\). If \(\epsilon\colon\Omega\to\mathbb{R}^{d}\) is a random variable on a probability space \((\Omega,\mathcal{B},\mathbb{P})\) and \(P\) is a predicate defined on \(\mathbb{R}^{d}\), then we write \(\mathbb{P}(P(\epsilon))\) to mean \(\mathbb{P}(\{\omega\in\Omega:P(\epsilon(\omega))\})\). Lebesgue measure on \(\mathbb{R}^{d}\) is denoted by \(m\). We define \(\operatorname{ReLU}\colon\mathbb{R}\to\mathbb{R}\) as \(\operatorname{ReLU}(x)=\max\{0,x\}\), and if \(x\in\mathbb{R}^{d}\), \(\operatorname{ReLU}(x)\) denotes \((\operatorname{ReLU}(x_{1}),\ldots,\operatorname{ReLU}(x_{d}))\). For a function \(\varphi\colon\mathbb{R}^{d}\to\mathbb{R}^{q}\) and \(p\in[1,\infty]\), we define \(\operatorname{Lip}_{p}(\varphi)=\inf\{K\geq 0\ :\ \|\varphi(x)-\varphi(x^{\prime})\|_{p} \leq K\|x-x^{\prime}\|_{p}\text{ for all }x,x^{\prime}\in\mathbb{R}^{d}\}\), and if \(\operatorname{Lip}_{p}(\varphi)<\infty\) we say that \(\varphi\) is Lipschitz continuous with constant \(\operatorname{Lip}_{p}(\varphi)\) (with respect to the \(\ell_{p}\)-norm).

## 2 Feature-Convex Classifiers

Let \(d,q\in\mathbb{N}\) and \(p\in[1,\infty]\) be fixed, and consider the task of classifying inputs from a subset of \(\mathbb{R}^{d}\) into a fixed set of classes \(\mathcal{Y}\subseteq\mathbb{N}\). In what follows, we restrict to the binary setting where \(\mathcal{Y}=\{1,2\}\) and class \(1\) is the sensitive class for which we desire robustness certificates (Section 1). In Appendix A, we briefly discuss avenues to generalize our framework to multiclass settings using one-versus-all and sequential classification methodologies and provide a proof-of-concept example for the Malimg dataset.

We now formally define the classifiers considered in this work.

**Definition 2.1**.: Let \(f\colon\mathbb{R}^{d}\to\{1,2\}\) be defined by

\[f(x)=\begin{cases}1&\text{if }g(\varphi(x))>0,\\ 2&\text{if }g(\varphi(x))\leq 0,\end{cases}\]

for some \(\varphi\colon\mathbb{R}^{d}\to\mathbb{R}^{q}\) and some \(g\colon\mathbb{R}^{q}\to\mathbb{R}\). Then \(f\) is said to be a _feature-convex classifier_ if the _feature map_\(\varphi\) is Lipschitz continuous with constant \(\operatorname{Lip}_{p}(\varphi)<\infty\) and \(g\) is a convex function.

We denote the class of all feature-convex classifiers by \(\mathcal{F}\). Furthermore, for \(q=d\), the subclass of all feature-convex classifiers with \(\varphi=\operatorname{Id}\) is denoted by \(\mathcal{F}_{\operatorname{Id}}\).

As we will see 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 \(g\) are restricted to be convex, the feature map \(\varphi\) is included to increase the representation power and practical performance of our architecture (see Appendix B for a motivating example). In practice, we find that it suffices to choose \(\varphi\) to be a simple map with a small closed-form Lipschitz constant. For example, in our experiments that follow with \(q=2d\), we choose \(\varphi(x)=(x-\mu,|x-\mu|)\) with a constant channel-wise dataset mean \(\mu\), yielding \(\operatorname{Lip}_{1}(\varphi)\leq 2\), \(\operatorname{Lip}_{2}(\varphi)\leq\sqrt{2}\), and \(\operatorname{Lip}_{\infty}(\varphi)\leq 1\). Although this particular choice of \(\varphi\) is convex, the function \(g\) need not be monotone, and therefore the composition \(g\circ\varphi\) is nonconvex in general. The prediction and certification of feature-convex classifiers are illustrated in Figure 1.

In practice, we implement feature-convex classifiers using parameterizations of \(g\), which we now make explicit. Following Amos et al. (2017), we instantiate \(g\) as a neural network with nonnegative weight matrices and nondecreasing convex nonlinearities. Specifically, we consider \(\operatorname{ReLU}\) nonlinearities, which is not restrictive, as our universal approximation result in Theorem 3.6 proves.

**Definition 2.2**.: A _feature-convex \(\operatorname{ReLU}\) neural network_ is a function \(\hat{f}\colon\mathbb{R}^{d}\to\{1,2\}\) defined by

\[\hat{f}(x)=\begin{cases}1&\text{if }\hat{g}(\varphi(x))>0,\\ 2&\text{if }\hat{g}(\varphi(x))\leq 0,\end{cases}\]
with \(\varphi\colon\mathbb{R}^{d}\to\mathbb{R}^{q}\) Lipschitz continuous with constant \(\operatorname{Lip}_{p}(\varphi)<\infty\) and \(\hat{g}\colon\mathbb{R}^{q}\to\mathbb{R}\) defined by

\[x^{(1)} =\operatorname{ReLU}\left(A^{(1)}x^{(0)}+b^{(1)}\right),\] \[x^{(l)} =\operatorname{ReLU}\left(A^{(l)}x^{(l-1)}+b^{(l)}+C^{(l)}x^{(0) }\right),\] \[\hat{g}(x^{(0)}) =A^{(L)}x^{(L-1)}+b^{(L)}+C^{(L)}x^{(0)},\]

for all \(l\in\{2,3,\ldots,L-1\}\) for some \(L\in\mathbb{N}\), \(L>1\), and for some consistently sized matrices \(A^{(l)},C^{(l)}\) and vectors \(b^{(l)}\) satisfying \(A^{(l)}\geq 0\) for all \(l\in\{2,3,\ldots,L\}\).

Going forward, we denote the class of all feature-convex \(\operatorname{ReLU}\) neural networks by \(\hat{\mathcal{F}}\). Furthermore, if \(q=d\), the subclass of all feature-convex \(\operatorname{ReLU}\) neural networks with \(\varphi=\operatorname{Id}\) is denoted by \(\hat{\mathcal{F}}_{\operatorname{Id}}\), which corresponds to the input-convex \(\operatorname{ReLU}\) neural networks proposed in Amos et al. (2017).

For every \(\hat{f}\in\hat{\mathcal{F}}\), it holds that \(\hat{g}\) is a convex function due to the rules for composition and nonnegatively weighted sums of convex functions (Boyd & Vandenberghe, 2004, Section 3.2), and therefore \(\hat{\mathcal{F}}\subseteq\mathcal{F}\) and \(\hat{\mathcal{F}}_{\operatorname{Id}}\subseteq\mathcal{F}_{\operatorname{Id}}\). The "passth through" weights \(C^{(l)}\) were originally included by Amos et al. (2017) to improve the practical performance of the architecture. In some of 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^{(l)}\) and \(C^{(l)}\) can be taken to be convolutions, which are nonnegatively weighted linear operations and thus preserve convexity (Amos et al., 2017).

## 3 Certification and Analysis of Feature-Convex Classifiers

We begin by deriving asymmetric robustness certificates for our feature-convex classifier in Section 3.1. In Section 3.2, we introduce convexly separable sets and theoretically analyze the clean performance of our classifiers through this lens. Namely, we show that there exists a feature-convex classifier with \(\varphi=\operatorname{Id}\) that perfectly classifies the CIFAR-10 cats-dogs training dataset. We show that this strong learning capacity generalizes by proving that feature-convex classifiers can perfectly fit high-dimensional uniformly distributed data with high probability. Proofs are deferred to the appendices.

### Certified Robustness Guarantees

In this section, we address the asymmetric certified robustness problem by providing class \(1\) robustness certificates for feature-convex classifiers \(f\in\mathcal{F}\). Such robustness corresponds to proving the absence of false negatives in the case that class \(1\) represents positives and class \(2\) represents negatives. For example, if in a malware detection setting class \(1\) represents malware and class \(2\) represents non-malware, the following certificate gives a lower bound on the magnitude of the malware file alteration needed in order to misclassify the file as non-malware.

**Theorem 3.1**.: _Let \(f\in\mathcal{F}\) be as in Definition 2.1 and let \(x\in f^{-1}(\{1\})=\{x^{\prime}\in\mathbb{R}^{d}:f(x^{\prime})=1\}\). If \(\nabla g(\varphi(x))\in\mathbb{R}^{q}\) is a nonzero subgradient of the convex function \(g\) at \(\varphi(x)\), then \(f(x+\delta)=1\) for all \(\delta\in\mathbb{R}^{d}\) such that_

\[\|\delta\|_{p}<r(x)\coloneqq\frac{g(\varphi(x))}{\operatorname{Lip}_{p}( \varphi)\|\nabla g(\varphi(x))\|_{p,*}}.\]

_Remark 3.2_.: For \(f\in\mathcal{F}\) and \(x\in f^{-1}(\{1\})\), a subgradient \(\nabla g(\varphi(x))\in\mathbb{R}^{q}\) of \(g\) always exists at \(\varphi(x)\), since the subdifferential \(\partial g(\varphi(x))\) is a nonempty closed bounded convex set, as \(g\) is a finite convex function on all of \(\mathbb{R}^{q}\)--see Theorem 23.4 in Rockafellar (1970) and the discussion thereafter. Furthermore, if \(f\) is not a constant classifier, such a subgradient \(\nabla g(\varphi(x))\) must necessarily be nonzero, since, if it were zero, then \(g(y)\geq g(\varphi(x))+\nabla g(\varphi(x))^{\top}(y-\varphi(x))=g(\varphi(x))>0\) for all \(y\in\mathbb{R}^{q}\), implying that \(f\) identically predicts class \(1\), which is a contradiction. Thus, the certified radius given in Theorem 3.1 is always well-defined in practical settings.

Figure 1: Illustration of feature-convex classifiers and their robustness certification. Since \(g\) is convex, it can be globally underapproximated by its tangent plane at \(\varphi(x)\), yielding certified sets for all norm balls in the higher-dimensional feature space. Lipschitzness of \(\varphi\) then yields appropriately scaled certificates in the original input space.
Theorem 3.1 is derived from the fact that a 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(\varphi(x))\) and inversely with the input sensitivity \(\|\nabla g(\varphi(x))\|_{p,*}\). In practice, \(\operatorname{Lip}_{p}(\varphi)\) can be made quite small as mentioned in Section 2, and furthermore the subgradient \(\nabla g(\varphi(x))\) is easily evaluated as the Jacobian of \(g\) at \(\varphi(x)\) using standard automatic differentiation packages. This provides fast, deterministic class \(1\) certificates for any \(\ell_{p}\)-norm without modification of the feature-convex network's training procedure or architecture.

### Representation Power Characterization

We now restrict our analysis to the class \(\mathcal{F}_{\mathrm{ld}}\) of feature-convex classifiers with an identity feature map. This can be equivalently considered as the class of classifiers for which the input-to-logit map is convex. We therefore refer to models in \(\mathcal{F}_{\mathrm{ld}}\) as _input-convex classifiers_. While the feature map \(\varphi\) 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 \(\mathcal{F}_{\mathrm{Id}}\).

**Definition 3.3**.: Let \(X_{1},X_{2}\subseteq\mathbb{R}^{d}\). The ordered pair \((X_{1},X_{2})\) is said to be _convexly separable_ if there exists a nonempty closed convex set \(X\subseteq\mathbb{R}^{d}\) such that \(X_{2}\subseteq X\) and \(X_{1}\subseteq\mathbb{R}^{d}\setminus X\).

Notice that it may be the case that a pair \((X_{1},X_{2})\) is convexly separable yet the pair \((X_{2},X_{1})\) is not. Although low-dimensional intuition may cause concerns regarding the convex separability of sets of binary-labeled data, we will soon see in Theorem 3.9 that, even for relatively unstructured data distributions, binary datasets are actually convexly separable in high dimensions with high probability. 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 set \(X\subseteq\mathbb{R}^{d}\), there exists \(f\in\mathcal{F}_{\mathrm{ld}}\) such that \(X=f^{-1}(\{2\})=\{x\in\mathbb{R}^{d}:f(x)=2\}\). In particular, this shows that if \((X_{1},X_{2})\) is a convexly separable pair of subsets of \(\mathbb{R}^{d}\), then there exists \(f\in\mathcal{F}_{\mathrm{ld}}\) such that \(f(x)=1\) for all \(x\in X_{1}\) and \(f(x)=2\) for all \(x\in X_{2}\)._

We also show that the converse of Proposition 3.4 holds: the geometry of the decision regions of classifiers in \(\mathcal{F}_{\mathrm{ld}}\) consists of a convex set and its complement.

**Proposition 3.5**.: _Let \(f\in\mathcal{F}_{\mathrm{ld}}\). The decision region under \(f\) associated to class \(2\), namely \(X\coloneqq f^{-1}(\{2\})=\{x\in\mathbb{R}^{d}:f(x)=2\}\), is a closed convex set._

Note that this is not necessarily true for our more general feature-convex architectures with \(\varphi\neq\mathrm{Id}\). We continue our theoretical analysis of input-convex classifiers by extending the universal approximation theorem for regressing upon real-valued convex functions (given in Chen et al. (2019)) to the classification setting. In particular, Theorem 3.6 below shows that any input-convex classifier \(f\in\mathcal{F}_{\mathrm{ld}}\) can be approximated arbitrarily well on any compact set by \(\mathrm{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\) can be made to have arbitrarily small Lebesgue measure.

**Theorem 3.6**.: _For any \(f\in\mathcal{F}_{\mathrm{ld}}\), any compact convex subset \(X\) of \(\mathbb{R}^{d}\), and any \(\epsilon>0\), there exists \(\hat{f}\in\hat{\mathcal{F}}_{\mathrm{ld}}\) such that \(m(\{x\in X:\hat{f}(x)\neq f(x)\})<\epsilon\)._

An extension of the proof of Theorem 3.6 combined with Proposition 3.4 yields that input-convex \(\mathrm{ReLU}\) neural networks can perfectly fit convexly separable sampled datasets.

**Theorem 3.7**.: _If \((X_{1},X_{2})\) is a convexly separable pair of finite subsets of \(\mathbb{R}^{d}\), then there exists \(\hat{f}\in\hat{\mathcal{F}}_{\mathrm{ld}}\) such that \(\hat{f}(x)=1\) for all \(x\in X_{1}\) and \(\hat{f}(x)=2\) for all \(x\in X_{2}\)._

Theorems 3.6 and 3.7 theoretically justify the particular parameterization in 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 is convexly separable. We illustrate this in Appendix D by attempting to reconstruct a CIFAR-10 cat image from a convex combination of the dogs and vice versa; the error is significantly positive for _every_ sample in the training dataset, and image reconstruction is visually poor. This fact, combined with Theorem 3.7, immediately yields the following result.

**Corollary 3.8**.: _There exists \(\hat{f}\in\hat{\mathcal{F}}_{\mathrm{ld}}\) such that \(\hat{f}\) achieves perfect training accuracy for the unaugmented CIFAR-10 cats-versus-dogs dataset._

The gap between this theoretical guarantee and our practical performance is large; without the feature map, our CIFAR-10 cats-dogs classifier achieves just \(73.4\%\) training accuracy (Table 3). While high training accuracy may not necessarily imply strong test set performance, Corollary 3.8 demonstrates that the typical deep learning paradigm of overfitting to the training dataset is attainable and that there is at least substantial room for improvement in the design and optimization of input-convex classifiers (Nakkiran et al., 2021). We leave the challenge of overfitting to the CIFAR-10 cats-dogs training data with an input-convex classifier as an open research problem for the field.
**Convex separability in high dimensions.** We conclude by investigating _why_ the convex separability property that allows for Corollary 3.8 may hold for natural image datasets. We argue that dimensionality facilitates this phenomenon by showing that data is easily separated by some \(f\in\hat{\mathcal{F}}_{\mathrm{Id}}\) when \(d\) is sufficiently large. In particular, although it may seem restrictive to rely on models in \(\hat{\mathcal{F}}_{\mathrm{Id}}\) with convex class \(2\) decision regions, we show in Theorem 3.9 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.9**.: _Consider \(M,N\in\mathbb{N}\). Let \(X_{1}=\{x^{(1)},\ldots,x^{(M)}\}\subseteq\mathbb{R}^{d}\) and \(X_{2}=\{y^{(1)},\ldots,y^{(N)}\}\subseteq\mathbb{R}^{d}\) be samples with all elements \(x_{k}^{(i)},y_{l}^{(j)}\) drawn independently and identically from the uniform probability distribution on \([-1,1]\). Then, it holds that_

\[\mathbb{P}\left((X_{1},X_{2})\text{ is convexly separable}\right) \tag{1}\] \[\quad\geq\begin{cases}1-\left(1-\frac{M!N!}{(M+N)!}\right)^{d}& \text{for all }d\in\mathbb{N},\\ 1&\text{if }d\geq M+N.\end{cases}\]

_In particular, \(\hat{\mathcal{F}}_{\mathrm{Id}}\) contains an input-convex \(\mathrm{ReLU}\) neural network that classifies all \(x^{(i)}\) into class \(1\) and all \(y^{(j)}\) into class \(2\) almost surely for sufficiently large dimensions \(d\)._

Although the uniformly distributed data in Theorem 3.9 is unrealistic in practice, the result demonstrates that the class \(\hat{\mathcal{F}}_{\mathrm{Id}}\) of input-convex \(\mathrm{ReLU}\) neural networks has sufficient complexity to fit even the most unstructured data in high dimensions. Despite this ability, researchers have found that current input-convex neural networks tend to not over-fit in practice, yielding small generalization gaps relative to conventional neural networks (Sivaprasad et al., 2021). Achieving the modern deep learning paradigm of overfitting to the training dataset with input-convex networks is an exciting open challenge (Nakkiran et al., 2021).

## 4 Experiments

We first describe our baseline methods, feature-convex architecture, and class accuracy balancing procedure. Our results are then reported across a variety of datasets, with further experimental setup details deferred to Appendix E.

**Baseline methods.** We consider several state-of-the-art randomized and deterministic baselines. For all datasets, we evaluate the randomized smoothing certificates of Yang et al. (2020) 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 (Wang et al., 2021), 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 Levine and Feizi (2021) (denoted Splitting), the orthogonality-based \(\ell_{2}\)-certificates from Trockman and Kolter (2021) (denoted Cayley), and the \(\ell_{\infty}\)-distance-based \(\ell_{\infty}\)-certificates from Zhang et al. (2021) (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.

**Feature-convex architecture.** Our simple experiments (MNIST 3-8 and Malimg) require no feature map to achieve high accuracy (\(\varphi=\mathrm{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|)\), 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, \(\mathrm{ReLU}\) nonlinearities, and passthrough weights. For the more challenging datasets, we use various instantiations of a convex ConvNet where successive layers have a 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 \(\gamma\) parameters to be positive. We initialize positive weight matrices to be drawn uniformly from the interval \([0,\epsilon]\), where \(\epsilon=0.003\) for linear weights and \(\epsilon=0.005\) for convolutional weights. Jacobian regularization is also used to improve our certified radii (Hoffman et al., 2019).

**Class accuracy balancing.** Since we consider _asymmetric_ certified robustness, care must be taken to ensure a fair comparison of class \(1\) certificates. Indeed, a constant classifier that always outputs class \(1\) would achieve perfect class \(1\) accuracy and infinite class \(1\) certified radii--yet it would not be a particularly interesting classifier as its accuracy on class \(2\) inputs would be poor. We therefore post-process the decision threshold of each classifier such that the clean class \(1\) and class \(2\) accuracies are equivalent, allowing for a direct comparison of the certification performance for class \(1\).

### Datasets

We now introduce the various datasets considered in this work. MNIST 3-8 and Malimg are relatively simple classification problems where near-perfect classification accuracy is attainable; the Malimg dataset falls in this category despite
containing relatively large images. Our more challenging settings consist of a Fashion-MNIST shirts dataset as well as CIFAR-10 cats-versus-dogs dataset. Data augmentation details are deferred to Appendix E.4.

**MNIST 3-8.** For our MNIST binary classification problem, we choose the problem of distinguishing between \(3\) and \(8\)(LeCun, 1998). These were selected as \(3\) and \(8\) are generally more visually similar and challenging to distinguish than other digit pairs. Images are \(28\times 28\) pixels and greyscale.

**Malimg.** Our malware classification experiments use greyscale, bytewise encodings of raw malware binaries Nataraj et al. (2011). 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. (2011), padding and cropping images to be \(512\times 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-sized 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.

**Fashion-MNIST shirts.** The hardest classes to distinguish in the Fashion-MNIST dataset are T-shirts vs shirts, which we take as our two classes (Kayed et al., 2020; Xiao et al., 2017). Images are \(28\times 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 (Giuste & Vizcarra, 2020; Liu & Mukhopadhyay, 2018; Ho-Phuoc, 2018). Other classes (e.g., ships) are typically easier to classify since large background features (e.g., blue water) are strongly correlated with the target label. Samples are \(32\times 32\) RGB images.

### Discussion

Experimental results for \(\ell_{1}\)-norm balls are reported in Figure 2, where our feature-convex classifier radii are similar or better than all other baselines across all datasets. Due to space constraints, we defer the corresponding plots for \(\ell_{2}\)- and \(\ell_{\infty}\)-norm balls to Appendix F, where our certified radii are not dominant but still comparable to methods tailored specifically for a particular norm. We accomplish this while maintaining completely deterministic, closed-form certificates with orders-of-magnitude faster computation time than competitive baselines.

For the MNIST 3-8 and Malimg datasets (Figures 1(a) and 1(b)), all methods achieve high clean test accuracy. Our \(\ell_{1}\)-radii scale exceptionally well with the dimensionality of the input, with two orders of magnitude improvement over smoothing baselines for the Malimg dataset. The Malimg certificates in particular have an interesting concrete interpretation. As each pixel corresponds to one byte in the original malware file, an \(\ell_{1}\)-certificate of radius \(r\) provides a robustness certificate for up to \(r\) bytes in the file. Namely, even if a malware designer were to arbitrarily change \(r\) malware bytes, they would be unable to fool our classifier into returning a false negative. This may not have an immediate practical impact as small semantic changes (e.g., reordering unrelated instructions) could induce large \(\ell_{p}\)-norm shifts. However, as randomized smoothing was extended from pixel-space to semantic transformations (Li et al., 2021), we expect that similar extensions can produce practical certifiably robust malware classifiers.

While our method produces competitive robustness certificates for \(\ell_{2}\)- and \(\ell_{\infty}\)-norms (Appendix F), it offers the largest improvement for \(\ell_{1}\)-certificates in the high-dimensional image spaces considered. This is likely due to the characteristics of the subgradient dual norm factor in the denominator of Theorem 3.1. The dual of the \(\ell_{1}\)-norm is the \(\ell_{\infty}\)-norm, 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 \(\ell_{\infty}\)-norm, one must evaluate the \(\ell_{1}\)-norm of the gradient, which scales proportionally to the input size. Nevertheless, we find in Appendix F that our \(\ell_{2}\)- and \(\ell_{\infty}\)-radii are generally comparable those of the baselines while maintaining speed and determinism.

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 fewer than \(10\) 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-10 image to minutes for an ImageNet image (Cohen et al., 2019). The only method that rivaled our \(\ell_{1}\)-norm certificates was \(\alpha,\beta\)-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.

Unlike the randomized smoothing baselines, our method is completely deterministic in both prediction and certification. Randomized prediction poses a particular problem for randomized smoothing certificates: even for a perturbation of a "certified" magnitude, repeated evaluations at the perturbed
point will eventually yield misclassification for any nontrivial classifier. While the splitting-based certificates of Levine and Feizi (2021) are deterministic, they only certify quantized (not continuous) \(\ell_{1}\)-perturbations, which scale poorly to \(\ell_{2}\)- and \(\ell_{\infty}\)-certificates (Appendix F). Furthermore, the certification runtime grows linearly in the smoothing noise \(\sigma\); evaluating the certified radii at \(\sigma\) used for the Malimg experiment takes several minutes per sample.

Ablation tests examining the impact of Jacobian regularization, the feature map \(\varphi\), and data augmentation are included in Appendix G. We illustrate the certification performance of our method across all combinations of MNIST classes in Appendix H.

## 5 Conclusion

This work introduces the problem of asymmetric certified robustness, which we show naturally applies to a number of practical adversarial settings. We define feature-convex classifiers in this context and theoretically characterize their representation power from geometric, approximation theoretic, and statistical lenses. Closed-form sensitive-class certified robust radii for the feature-convex architecture are provided for arbitrary \(\ell_{p}\)-norms. We find that our \(\ell_{1}\)-robustness certificates in particular match or outperform those of the current state-of-the-art methods, with our \(\ell_{2}\)- and \(\ell_{\infty}\)-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-immediate computation scheme. We also show theoretically that significant performance improvements should be realizable for natural image datasets such as CIFAR-10 cats-versus-dogs. Possible directions for future research include bridging the gap between the theoretical power of feature-convex models and their practical implementation, as well as exploring more sophisticated choices of the feature map \(\varphi\).

Figure 2: Class \(1\) certified radii curves for the \(\ell_{1}\)-norm. Note the \(\log\)-scale on the Malimg plot.