Adversarial Training of Two-Layer Polynomial and ReLU Activation Networks via Convex Optimization

## Abstract

Abstract Training neural networks which are robust to adversarial attacks remains an important problem in deep learning, especially as heavily overparameterized models are adopted in safety-critical settings. Drawing from recent work which reformulates the training problems for two-layer ReLU and polynomial activation networks as convex programs, we devise a convex semidefinite program (SDP) for adversarial training of two-layer polynomial activation networks and prove that the convex SDP achieves the same globally optimal solution as its nonconvex counterpart. The convex SDP is observed to improve robust test accuracy against ℓ ∞ subscript ℓ \ell_{\infty} roman_ℓ start_POSTSUBSCRIPT ∞ end_POSTSUBSCRIPT attacks relative to the original convex training formulation on multiple datasets. Additionally, we present scalable implementations of adversarial training for two-layer polynomial and ReLU networks which are compatible with standard machine learning libraries and GPU acceleration. Leveraging these implementations, we retrain the final two fully connected layers of a Pre-Activation ResNet-18 model on the CIFAR-10 dataset with both polynomial and ReLU activations. The two ‘robustified’ models achieve significantly higher robust test accuracies against ℓ ∞ subscript ℓ \ell_{\infty} roman_ℓ start_POSTSUBSCRIPT ∞ end_POSTSUBSCRIPT attacks than a Pre-Activation ResNet-18 model trained with sharpness-aware minimization, demonstrating the practical utility of convex adversarial training on large-scale problems.

## 1 Introduction

While neural networks have demonstrated great success in many application areas, they are prone to learning unstable outputs. In particular, adversarial attacks can easily deceive neural networks (Goodfellow et al., ). The problem of adversarial robustness has motivated a number of approaches (Foret et al., ; Xu et al., ) which can incur significant computational overhead and often require training a model from scratch for optimal results.

A related problem is the lack of interpretability and optimality guarantees in neural network training. Towards understanding these issues, recent works have developed convex reformulations of certain neural network architectures (Pilanci & Ergen, ; Bartan & Pilanci, ; ). These convex programs offer insight into how neural networks learn (Mishkin & Pilanci, ; Lacotte & Pilanci, ), while also providing guarantees for both the global optimality of weights and computational complexity of training.

We emphasize that convexity of the loss landscape is useful beyond guaranteeing local optima are global. Indeed, a major pain-point of machine learning is that parameters extrinsic to the model (e.g. the learning rate, momentum or batch size) significantly impact performance. Convex reformulations are optimizer-agnostic, so off-the-shelf solvers (Diamond & Boyd, ; Agrawal et al., ) will reliably converge to the global optimum without hyperparameter tuning. Given that convexly trained neural networks enjoy greater interpretability and reproducibility, there is motivation to study them in the context of adversarial robustness. For example, Bai et al. () derives a convex adversarial training problem for two-layer ReLU networks by modifying the original convex training problem introduced by Pilanci & Ergen (). However, to the best of our knowledge, there is no convex reformulation of adversarial training for polynomial activation networks.

### 1.1 Contributions

We contribute (1) a convex reformulation for adversarial training of polynomial activation networks based on the main result of Bartan & Pilanci (), (2) a proof that our reformulation achieves the same optimal value as the nonconvex adversarial training formulation, (3) an exact solver of the convex SDP for small-scale problems using the open-source Python library CVXPY (Diamond & Boyd, ), and (4) PyTorch implementations of adversarial training for both polynomial and ReLU activation networks. While we only present convex adversarial training programs for two-layer networks, we demonstrate that robust classification accuracy of deep image classification models (e.g. a Pre-Activation ResNet model from He et al. ()), can be greatly improved by retraining the final two layers with the developed convex adversarial training programs, even outperforming the same architecture trained with sharpness-aware minimization. Code is available [here](https://github.com/dklbs493/cvx-adversarial-training).

### 1.2 Paper Organization & Notation

Section 2 discusses standard convex training programs for two-layer neural networks. Section 3 introduces our main theoretical result (Theorem 3.1) and treats convex adversarial training for two-layer ReLU networks. Section 4 contains numerical results and a discussion thereof. We conclude the paper and discuss future work in Sectin 5. Appendix A proves the main theoretical result. Appendix B states and proves miscellaneous lemmas used in Appendix A. Appendix C derives a convex SDP to exactly compute the distance to the decision boundary of a polynomial activation network.

Notation: We use $[n]$ to denote the set $\{1,2,...,n\}$ (e.g. we write $\forall i\in[n]$). The set of $n\times n$ real symmetric matrices is $\mathcal{S}^{n}$. The set of positive semidefinite symmetric matrices is $\mathcal{S}^{n}_{+}$. Given a square matrix $A$, $A\succ 0$ and $A\succeq 0$ indicate positive definiteness and positive semidefiniteness of $A$, respectively. $\operatorname{Tr}(A)$ is the trace of the matrix $A$. For square matrices $A$ and $B$, we denote the matrix inner product $\left<A,B\right>=\operatorname{Tr}(AB)$. The nonnegative orthant of $\mathbb{R}^{n}$ is denoted $\mathbb{R}^{n}_{+}$. The convex (Fenchel) conjugate of a function $\ell:\mathbb{R}^{n}\rightarrow\mathbb{R}$ is denoted $\ell^{*}$, where $\ell^{*}(y)=\sup_{x\in\text{dom}\ell}\{y^{T}x-\ell(x)\}$.

## 2 Standard Convex Training for Two-Layer Neural Networks

We discuss standard convex training for polynomial and ReLU activation networks in 2.1 and 2.2, respectively.

### 2.1 Polynomial Activation Networks

Suppose we have a two-layer neural network $f:\mathbb{R}^{d}\rightarrow\mathbb{R}$ with first-layer weights $\{u_{j}\}_{j=1}^{m}$, $u_{j}\in\mathbb{R}^{d}$, second-layer weights $\{\alpha_{j}\}_{j=1}^{m}$, $\alpha_{j}\in\mathbb{R}$, and polynomial activation functions $\sigma(x)=ax^{2}+bx+c$. Here, $a,b,c$ are fixed coefficients which are chosen so that $\sigma(x)$ best approximates the ReLU activation function ReLU$(x)=\max\{x,0\}$ in the least-squares sense ($a=0.09,b=0.5,c=0.47$). We define this neural network as follows:

$$ $\displaystyle f(x)=\sum^{m}_{j=1}\sigma(x^{T}u_{j})\alpha_{j}$ (1) $$

Let $\{x_{i},y_{i}\}_{i=1}^{n}$, $x_{i}\in\mathbb{R}^{d}$, $y_{i}\in\mathbb{R}$ be the problem data. Then, for a convex loss function $\ell:\mathbb{R}^{n}\rightarrow\mathbb{R}$, the training problem for a polynomial activation network with regularization strength $\beta$ and optimization variables $\{u_{j},\alpha_{j}\}_{j=1}^{m}$ and $\{\hat{y}_{j}\}_{j=1}^{n}$ is

$$ $\displaystyle\underset{\{u_{j},\alpha_{j}\}_{j=1}^{m}}{\operatorname{minimize}}$ $\displaystyle\ell\left(\hat{y},y\right)+\beta\sum^{m}_{j=1}|\alpha_{j}|$ (2) subject to $\displaystyle\hat{y}_{i}=\sum^{m}_{j=1}\sigma(x_{i}^{T}u_{j})\alpha_{j}\quad \forall i\in[n]$ $\displaystyle||u_{j}||_{2}=1\quad\forall j\in[m]$ $$

This is not a convex optimization problem, because the equality constraints are not affine functions of the variables, and so the feasible set is not convex.
Here, the constraints $||u_{j}||_{2}=1$ and choice of $\ell_{1}$ norm regularization are crucial to the derivation of the convex training problem for polynomial activation networks developed by Bartan & Pilanci (). Because this is not a convex optimization problem, standard stochastic gradient descent methods may be trapped by local minima, and the optimal values reached tend to depend on hyperparameters such as learning rate and optimizer (e.g. stochastic gradient descent vs. Adam Kingma & Ba ()). The following convex reformulation introduced by Bartan & Pilanci () ameliorates these problems. Note that the optimization variables are the symmetric matrices $Z,Z^{\prime}\in\mathcal{S}^{d+1}$.

$$ $\displaystyle\underset{Z,Z^{\prime}\in\mathcal{S}^{d+1}}{\operatorname{ minimize}}$ $\displaystyle\ell(\hat{y},y)+\beta(Z_{4}+Z_{4}^{\prime})$ (3) subject to $\displaystyle\hat{y}_{i}=ax_{i}^{T}\tilde{Z}_{1}x_{i}+b\tilde{Z}_{2}^{T}x_{i}+ c\tilde{Z}_{4}\quad\forall i\in[n]$ $\displaystyle Z=\begin{bmatrix}Z_{1}&Z_{2}\\ Z_{2}^{T}&Z_{4}\end{bmatrix}\succeq 0$ $\displaystyle Z^{\prime}=\begin{bmatrix}Z_{1}^{\prime}&Z_{2}^{\prime}\\ Z_{2}^{\prime T}&Z_{4}^{\prime}\end{bmatrix}\succeq 0$ $\displaystyle\tilde{Z}=Z-Z^{\prime}$ $\displaystyle\text{tr}(Z_{1})=Z_{4}$ $\displaystyle\text{tr}(Z_{1}^{\prime})=Z_{4}^{\prime}$ $$

###### Theorem 2.1 ( Bartan & Pilanci ( 2021 ) )

The solution of the convex program (3) provides a globally optimal solution for the non-convex
problem (2) when the number of neurons $m$ satisfies $m\geq m^{\star}$, where $m^{\star}=\operatorname{rank}{Z^{\star}}+\operatorname{rank}{Z^{\prime\star}}$ and $Z^{\star},Z^{\prime\star}$ are the solutions of  (3).

We remark that the globally optimal neural network weights $\{u_{j}^{\star},\alpha_{j}^{\star}\}^{m}_{j=1}$ for (2) can be obtained from $Z^{\star},Z^{\prime\star}$ using the neural decomposition procedure, which is outlined in Section 4 of Bartan & Pilanci (). The number of neurons recovered from $Z^{\star}$ and $Z^{\prime\star}$ is equal to the sum of their ranks, implying that the number of neurons required to minimize the loss in (2) is at most $2(d+1)$. This bound is usually not tight—low rank optimal solutions can be encouraged by tuning $\beta$ (Bartan & Pilanci, ).

###### Theorem 2.1 ( Bartan & Pilanci ( 2021 ) )

### 2.2 ReLU Activation Networks

Now suppose we have a two-layer neural network $f:\mathbb{R}^{d}\rightarrow\mathbb{R}$ with $m$ neurons, first-layer weights $\{u_{j}\}_{j=1}^{m}$, $u_{j}\in\mathbb{R}^{d}$, second-layer weights $\{\alpha_{j}\}_{j=1}^{m}$, $\alpha_{j}\in\mathbb{R}$, and ReLU activation functions ReLU$(x)=(x)_{+}=\max\{0,x\}.$ For a single example $x_{i}\in\mathbb{R}^{d}$, the neural network output is

$$ $\displaystyle f(x)=\sum_{j=1}^{m}(u_{j}^{T}x)_{+}\alpha_{j}.$ (4) $$

For convenience of notation moving forward, we will write the neural network output in a vectorized form. Given a data matrix $X\in\mathbb{R}^{n\times d}$ where each row $x_{i}\in\mathbb{R}^{d}$ represents a single example, we write the predictions of $f$ on $X$ as follows:

$$ $\displaystyle f(X)=\sum_{j=1}^{m}(Xu_{j})_{+}\alpha_{j}$ (5) $$

Let $y\in\mathbb{R}^{n}$ be the training labels corresponding to the examples $X$, and consider the usual $\ell_{2}$-regularized training problem with optimization variables $\{u_{j},\alpha_{j}\}_{j=1}^{m}$:

$$ $\displaystyle\underset{\{u_{j},a_{j}\}_{j=1}^{m}}{\operatorname{minimize}}\;\; \ell\left(\sum^{m}_{j=1}(Xu_{j})_{+}\alpha_{j},y\right)+\frac{\beta}{2}\sum^{m }_{j=1}(||u_{j}||^{2}_{2}+\alpha^{2}_{j})$ (6) $$

As in the previous subsection 2.1, our training problem  (6) is nonconvex as written. However, globally optimal solutions $\{u^{\star}_{j},\alpha^{\star}_{j}\}_{j=1}^{m}$ to  (6) can be recovered from the optimal solutions to the following convex program with optimization variables $\{v_{i},w_{i}\}_{i=1}^{P}$:

$$ $\displaystyle\underset{\{v_{i},w_{i}\}_{i=1}^{P}}{\operatorname{minimize}}$ $\displaystyle\ell\left(\sum^{P}_{i=1}D_{i}X(v_{i}-w_{i}),y\right)+\frac{\beta} {2}\sum^{m}_{j=1}(||v_{i}||_{2}+||w_{i}||_{2})$ (7) $\displaystyle\operatorname{subject\;\,to}$ $\displaystyle(2D_{i}-I_{n})Xv_{i}\geq 0,\quad i\in[P]$ $\displaystyle(2D_{i}-I_{n})Xw_{i}\geq 0,\quad i\in[P]$ $$

In  (7), the $D_{i}$’s are diagonal matrices which enumerate all possible ReLU activation patterns on $X$. Mathematically, we have $D=\{D_{1},...,D_{P}\}=\{\text{diag}(\textbf{1}[Xu\geq 0]):u\in\mathbb{R}^{d}\}$.
We refer the reader to Pilanci & Ergen () for a more detailed discussion of these activation pattern matrices and an asymptotic analysis of $P$ with respect to number of examples $n$, network width $m$, input dimension $d$, and rank of the data matrix $\operatorname{rank}{X}$. The short story is that, while $P$ grows exponentially with $\operatorname{rank}{X}$, convexly trained ReLU networks perform well even if a small subset of $D$ is sampled. We now state the theorem relating problems  (6) and  (7):

###### Theorem 2.2 ( Pilanci & Ergen ( 2020 ) )

The convex program  (7) and the non-convex program  (6) have identical optimal values when $m\geq m^{\star}$, where $m^{\star}$ is the number of nonzero variables in $\{v^{\star}_{i},w^{\star}_{i}\}^{P}_{i=1}$. Moreover, if the width requirement $m\geq m^{\star}$ is met, an optimal solution to  (6) can be constructed from an optimal solution to  (7) as follows:

$$ $\displaystyle(u^{\star}_{j_{i}},\alpha^{\star}_{j_{i}})=\begin{cases}\left( \frac{v^{\star}_{i}}{\sqrt{||v_{i}^{\star}||_{2}}},\sqrt{||v_{i}^{\star}||_{2} }\right)&\text{if}\quad v_{i}^{\star}\neq 0\\ \left(\frac{w^{\star}_{i}}{\sqrt{||w_{i}^{\star}||_{2}}},\sqrt{||w_{i}^{\star} ||_{2}}\right)&\text{if}\quad w_{i}^{\star}\neq 0\end{cases}$ (8) $$

###### Theorem 2.2 ( Pilanci & Ergen ( 2020 ) )

## 3 Convex Adversarial Training for Two-Layer Neural Networks

In subsection 3.1, we present our main theoretical result: a convex SDP for adversarial training of polynomial activation networks. In subsection 3.2, we state the analogous convex program for ReLU activation networks developed by Bai et al. ().

### 3.1 Polynomial Activation Networks

We now develop an analogous result to Theorem 2.1 for adversarial training of polynomial activation networks. To simplify notation, we limit our focus to binary classification for the remainder of the section. Hence we consider the case where all data points have $y_{i}\in\{-1,1\}$ and let $\operatorname{sign}(f(x_{i}))\in\{-1,1\}$ be the prediction of the neural network for $x_{i}$. Consider the quantities $w_{i}$, defined as follows for all $i\in[n]$.

$$ $\displaystyle w_{i}$ $\displaystyle=\min_{||\Delta||_{2}\leq r}y_{i}f(x_{i}+\Delta)$ (9) $\displaystyle=\min_{||\Delta||_{2}\leq r}y_{i}\sum_{j=1}^{m}\sigma((x_{i}+ \Delta)^{T}u_{j})\alpha_{j}$ $$

Here, $w_{i}$ can be thought of as the worst-case score of the neural network in a closed $\ell_{2}$-ball of radius $r$ around $x_{i}$, denoted $\mathcal{B}_{r}(x_{i})$. Note: we will refer to $r$ as the ‘robust radius parameter’ throughout the paper. If $w_{i}$ is positive, the sign of the neural network output matches that of $y_{i}$ everywhere in $\mathcal{B}_{r}(x_{i})$. A negative $w_{i}$ implies that the sign of the neural network output differs from $y_{i}$ somewhere in $\mathcal{B}_{r}(x_{i})$. Assuming $r$ is suitably chosen so that it makes sense for all points in $\mathcal{B}_{r}(x_{i})$ to reside in the same class, a positive $w_{i}$ indicates that the neural network is correct everywhere in $B_{r}(x_{i})$. In other words, $w_{i}>0$ implies the predictor $f$ is correct and robust to $\ell_{2}$-norm attacks of magnitude at most $r$ at $x_{i}$.

A training problem which penalizes nonpositivity of the $w_{i}$’s is precisely an adversarial training problem for the predictor $f$. We write one such problem for polynomial activation networks below, with robust radius parameter $r$, regularization strength $\beta\in\mathbb{R}$, and optimization variables $w\in\mathbb{R}^{n}$, $\{u_{j},\alpha_{j}\}_{j=1}^{m}$. Here, $\ell(\cdot)$ is a convex, nonincreasing loss function. The variables $\{u_{j},\alpha_{j}\}_{j=1}^{m}$ are the neural network weights, while $w$ is a vector of the worst-case outputs for each training example.

$$ $\displaystyle\underset{\{u_{j},\alpha_{j}\}_{j=1}^{m},w}{\operatorname{ minimize}}$ $\displaystyle\quad\ell(w)+\beta\sum_{j=1}^{m}|\alpha_{j}|$ (10) $\displaystyle\operatorname{subject\;\,to}$ $\displaystyle\quad w_{i}=\min_{||\Delta||_{2}\leq r}y_{i}\sum_{j=1}^{m}\sigma( (x_{i}+\Delta)^{T}u_{j})\alpha_{j}\quad\forall i\in[n]$ $\displaystyle||u_{j}||_{2}=1\quad\forall j\in[m]$ $$

We remark that the constraints $||u_{j}||_{2}=1$ and $\ell_{1}$ norm regularization on the $\alpha_{j}$’s are necessary in proving Theorem 3.1. In practice, these design choices do not prevent our formulation from outperforming state-of-the-art adversarial training methods. We use the hinge loss $\ell(w)=\frac{1}{n}\sum_{i=1}^{n}(1-w_{i})_{+}$ as the training objective for the remainder of the paper. Our reasons are twofold. First, an optimization which minimizes hinge loss pushes $w_{i}$’s to be positive, so the predictor will learn to robustly classify the training examples. Second, hinge loss is convex, so it is a valid training objective for the soon-to-be-introduced convex reformulation of adversarial training.

The current form of  (10) is intractable. It contains two nonlinear equality constraints, spoiling the convexity of the problem. As written, our only hope of approximating the solution to  (10) would be through a computationally expensive descent method like projected gradient (Madry et al., ). Sadly, this approach offers no optimality guarantees and requires computing multiple descent steps for each training batch to approximate $w_{i}$. We propose a convex reformulation of  (10), which is solvable to global optimality in fully polynomial time. The optimization variables are $Z,Z^{\prime}\in\mathcal{S}^{d+1}_{+}$, $\lambda\in\mathbb{R}^{n}_{+},w\in\mathbb{R}^{n}$. As in  (10), the variable $w$ is a vector of the worst-case scores for each $x_{i}$, while the matrices $Z$ and $Z^{\prime}$ are the new weights. The parameters $r$ and $\beta$ are again the robust radius parameter and regularization strength.

$$ $\displaystyle\underset{Z,Z^{\prime},w,\lambda}{\operatorname{minimize}}$ $\displaystyle\quad\ell(w)+\beta(Z_{4}+Z_{4}^{\prime})$ (11) $\displaystyle\operatorname{subject\;\,to}$ $\displaystyle\quad Z=\begin{bmatrix}Z_{1}&Z_{2}\[2.84526pt] Z_{2}^{T}&Z_{4}\end{bmatrix}\succeq 0$ $\displaystyle\quad Z^{\prime}=\begin{bmatrix}Z_{1}^{\prime}&Z_{2}^{\prime}\[2 .84526pt] Z_{2}^{\prime T}&Z_{4}^{\prime}\end{bmatrix}\succeq 0$ $\displaystyle\quad\operatorname{Tr}(Z_{1})=Z_{4}$ $\displaystyle\quad\operatorname{Tr}(Z_{1}^{\prime})=Z_{4}^{\prime}$ $\displaystyle\quad\tilde{Z}=Z-Z^{\prime}$ $\displaystyle\quad y_{i}\begin{bmatrix}y_{i}\lambda_{i}I+a\tilde{Z}_{1}&ax_{i} ^{T}\tilde{Z}_{1}+\frac{1}{2}b\tilde{Z}_{2}\[5.69054pt] a\tilde{Z}_{1}x_{i}+\frac{1}{2}b\tilde{Z}_{2}&ax_{i}^{T}\tilde{Z}_{1}x_{i}+bx_ {i}^{T}\tilde{Z}_{2}+c\tilde{Z}_{4}-y_{i}\lambda_{i}r^{2}-y_{i}w_{i}\end{ bmatrix}\succeq 0$ $\displaystyle\quad\lambda_{i}\geq 0\quad\forall i\in[n]$ $$

###### Theorem 3.1 (Our Result)

Provided that the number of neurons $m$ in problem (10) satisfies $m\geq m^{\star}=\operatorname{rank}{Z^{\star}}+\operatorname{rank}{Z^{\prime
\star}}$, the optimal values of  (11) and (10) are the same. Moreover, the optimal solutions $w^{\prime\star},\{u^{\star}_{j},\alpha^{\star}_{j}\}^{m^{\star}}_{j=1}$ of  (10) can be recovered from the optimal solutions $w^{\star},Z^{\star},Z^{\prime\star}$ of  (11).

As stated above, as long as the neural network in problem (10) is sufficiently wide, we can recover its globally optimal solution from  (11), which is an efficiently solvable convex program. The proof of Theorem 3.1 is deferred to Appendix A. As in problem (3) the regularization parameter controls $m^{\star}=\operatorname{rank}{Z^{\star}}+\operatorname{rank}{Z^{\prime\star}}$, so it’s possible to encourage low rank solutions by tuning $\beta$.

###### Theorem 3.1 (Our Result)

### 3.2 ReLU Activation Networks

Let $f$ be a ReLU activation network as described in 2.2. With the same binary classification setup as in the previous subsection, the worst-case output of $f$ in an $\ell_{p}$ ball of radius $r$ around a training example $x_{k}$ is

$$ $\displaystyle\min_{\Delta:||\Delta||_{p}\leq r}y_{k}f(x_{k}+\Delta)$ $\displaystyle=\min_{\Delta:||\Delta||_{p}\leq r}y_{k}\sum^{m}_{j=1}(x_{k}^{T}u _{j})_{+}\alpha_{j}$ (12) $\displaystyle=\min_{\Delta:||\Delta||_{p}\leq r}y_{k}\sum^{P}_{i=1}D_{i,\{k,k \}}(x_{k}+\Delta)^{T}(v_{i}-w_{i})$ $$

In the second equality, we use the lifted convex form of the ReLU network, where $D_{i,\{k,k\}}$ denotes the $k$-th diagonal entry of $D_{i}$ (Note: to do this, we must assume that the width-requirement $m\geq m^{\star}$ from 2.2 is met). Crucially, this reformulates the worst-case output of the neural network as the minimum of an affine function of $\Delta$ over an $\ell_{p}$ ball. It is well known that for an $\ell_{p}$ norm $||\cdot||_{p}$, with $1\leq p\leq\infty$, we have

$$ $\displaystyle\min_{x:||x||_{p}\leq r}c^{T}x+b=-r||c||_{q}+b$ (13) $$

where $\frac{1}{p}+\frac{1}{q}=1$. Then, using  (13) for fixed $\{v_{i},w_{i}\}_{i=1}^{P}$, we have an analytical expression for the worst-case output of a two-layer ReLU network in the $\ell_{p}$ ball of radius $r$ around $x_{k}$:

$$ $\displaystyle\min_{x:||\Delta||_{p}\leq r}y_{k}\sum^{P}_{i=1}D_{i,\{k,k\}}(x_{ k}+\Delta)^{T}(v_{i}-w_{i})$ $\displaystyle=y_{k}x_{k}^{T}\sum^{P}_{i=1}D_{i,\{k,k\}}(v_{i}-w_{i})-r\bigg{\| }\sum^{P}_{i=1}D_{i,\{k,k\}}(v_{i}-w_{i})\bigg{\|}_{q}$ $$

Following equation (13) and corollary 3.1 from Bai et al. (), we have

$$ $\displaystyle\min_{x:||\Delta||_{p}\leq r}(2D_{i,\{k,k\}}-1)(x_{k}+\Delta)^{T} v_{i}\geq 0$ $\displaystyle\iff$ $\displaystyle(2D_{i,\{k,k\}}-1)x_{k}^{T}v_{i}\geq r||v_{i}||_{q}$ (14) $$

The equivalence clearly also holds for $w_{i}$. As in Theorem 4 from Bai et al. (), the convex adversarial training problem for binary classification under hinge loss is written below. The optimization variables are again $\{v_{i},w_{i}\}^{P}_{j=1}$. The equality constraint involving $\theta_{k}$ is added only for readability.

$$ $\displaystyle\underset{\{v_{i},w_{i}\}_{i=1}^{P}}{\operatorname{minimize}}$ $\displaystyle\frac{1}{n}\sum^{n}_{k=1}\left(1-y_{k}x_{k}^{T}\theta_{k}+r\| \theta_{k}\|_{q}\right)_{+}+\frac{\beta}{2}\sum^{m}_{j=1}(||v_{i}||_{2}+||w_{i }||_{2})$ (15) $\displaystyle\operatorname{subject\;\,to}$ $\displaystyle(2D_{i}-I_{n})Xv_{i}\geq r||v_{i}||_{q},\quad i\in[P]$ $\displaystyle(2D_{i}-I_{n})Xw_{i}\geq r||w_{i}||_{q},\quad i\in[P]$ $\displaystyle\theta_{k}=\sum^{P}_{i=1}D_{i,\{k,k\}}(v_{i}-w_{i}),\quad k\in[n]$ $$

The left sides of the inequality constraints in  (7) and  (15) are vector-valued, where each entry must be at least the corresponding scalar value on the right. With further tolerance for unwieldy notation,  (7) and  (15) can be generalized to the multi-class regime under multimargin loss. We omit the derivation for brevity.

As noted earlier, $P$ grows exponentialy with the rank of the data matrix $X$ (Pilanci & Ergen, ; Ojha, ), so in practice it is necessary to randomly sample a subset of $D$. Even in high-dimensional settings such as image classification, it is readily observed that sampling a few thousand sign patterns and solving  (7) leads to comparable or even better test accuracy than the nonconvex training problem  (6). Our numerical experiments in Section 4 corroborate this.

#### 3.2.1 Practical Implementation of Convex Adversarial ReLU Networks

Observing that $v_{i}=0=w_{i}$, $i\in[P]$ is in the feasible set, we can approximately solve  (15)
with typical machine learning libraries (e.g. PyTorch) by replacing the constraints with added penalty
terms in the objective. For a tunable coefficient $\rho\in\mathbb{R}$ and $\hat{P}$ sampled sign pattern matrices $\{D\}_{i=1}^{\hat{P}}$, we can use descent methods such as Adam or stochastic gradient descent on the objective below. Equality constraints on $\theta_{k}$ are for notational purposes only.

$$ $\displaystyle\underset{\{v_{i},w_{i}\}_{i=1}^{P}}{\operatorname{minimize}}$ $\displaystyle\frac{1}{n}\sum^{n}_{k=1}\left(1-y_{k}x_{k}^{T}\theta_{k}+r\| \theta_{k}\|_{q}\right)_{+}+\frac{\beta}{2}\sum^{m}_{j=1}(||v_{i}||_{2}+||w_{i }||_{2})$ (16) $\displaystyle\qquad\qquad+\rho\sum^{n}_{k=1}\sum^{\hat{P}}_{i=1}\left(r(||v_{i }||_{q}+||w_{i}||_{q})-(2\hat{D}_{i,\{k,k\}}-1)x_{k}^{T}(v_{i}+w_{i})\right)_{+}$ $\displaystyle\operatorname{subject\;\,to}$ $\displaystyle\theta_{k}=\sum^{\hat{P}}_{i=1}\hat{D}_{i,\{k,k\}}(v_{i}-w_{i}), \quad k\in[n]$ $$

By initializing the weights from zero, constraint violations remain negligible throughout training, and, in practice, we achieve excellent robustness to adversarial attacks. In contrast to Bai et al. (), this approach enables convex adversarial training on large-scale problems (see Table 2) and outperforms other adversarial training methods with less computational overhead.

## 4 Numerical Results

### 4.1 Exact Solutions on Small-Scale Problems

We train polynomial activation networks via the standard convex program in  (3) and the adversarial convex program  (11) to perform binary classification on the Wisconsin Breast Cancer dataset (Wolberg, ) and Ionosphere dataset (Sigillito et al., ). The datasets are shuffled and split with 80%, 10%, and 10% training, validation, and test examples, respectively. A parameter search was conducted to determine values of $\beta$ and $r$ for the adversarial training program and $\beta$ for the standard program. For the Wisconsin Breast Cancer dataset, we choose $\beta=0.01$ for both models and $r=1.5$ in  (11). For the ionosphere dataset, we choose $\beta=0.1$ for both models and $r=1.45$ in  (11). Table 1 compares clean and robust test accuracies for each model, where we use the fast gradient sign method (FGSM) (Goodfellow et al., ) to compute $\ell_{\infty}$ adversarial attacks of varying magnitude. We obtain exact solutions to the convex training problems using the splitting conic solver (O’Donoghue et al., ) with a tolerance of 1e-5.

In Table 1, our robust model trained with the convex program (11) achieves higher robust test accuracy for all attack sizes. In particular, on the Wisconsin Breast Cancer dataset, robust accuracy degrades far more slowly for our robust polynomial activation network than the standard polynomial activation network. Indeed, for attack size $=0.9$, the accuracy of our model is $76\%$, while the standard model is far worse than random at $15\%$. On the ionosphere dataset, our robust model outperforms the standard model for all attack sizes. While clean accuracy of our model is slightly worse, we remark that minor degradation of clean accuracy is commonly observed in other adversarial training techniques (Foret et al., ; Madry et al., ).

**Table 1: Clean and $\ell_{\infty}$-robust accuracies of polynomial activation networks.**
| Wisconsin Breast Cancer Dataset |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- |
|  | $\ell_{\infty}$-norm of attack |  |  |  |  |  |
| Method | Clean | $.50$ | $.60$ | $.70$ | $.80$ | $.90$ |
| Adversarial | .993 | .864 | .829 | .821 | .786 | .764 |
| Standard | .993 | .864 | .679 | .443 | .2786 | .150 |
| Ionosphere Dataset |  |  |  |  |  |  |
|  | $\ell_{\infty}$-norm of attack |  |  |  |  |  |
| Method | Clean | $.05$ | $.10$ | $.15$ | $.20$ | $.25$ |
| Adversarial | .803 | .761 | .761 | .732 | .718 | .648 |
| Standard | .831 | .761 | .718 | .620 | .578 | .521 |

In Figure 1, we hold $\beta=0.01$ constant and visualize how clean test accuracy, robust test accuracy, and average distance to the decision boundary of correctly classified examples vary with the robust radius parameter $r$. The distance to the decision boundary $d_{\mathcal{D}}(x_{i})$ is exactly computable for polynomial activation networks, as described in Appendix C.

With clean accuracy held constant, the distance to the decision boundary of correctly classified examples is perhaps the clearest indicator of a model’s robustness to adversarial attacks. From $r=0$ to $r\approx 1.5$ in 1, we observe an increase in robust accuracy and average distance to the decision boundary of correctly classified examples (denoted $d_{\mathcal{D}}(x)$), while clean accuracy remains steady at over 99%. It is evident that, up to a point, robustness increases with $r$. However, an over-smoothing effect eventually sets in. When $r$ becomes large enough that $r$-balls around training examples of different classes intersect, it is impossible for the model to robustly classify both examples. Too many of these inter-class $r$-ball collisions will force the model to minimize the loss by only predicting the majority class. This behavior is evident for $r$ values above 2.3 in the right plot of Figure 1. Note that we do not plot $d_{\mathcal{D}}(x)$ for values of $r$ greater than 2.3. This is because the optimization problem  (41) is unbounded when the predictor only outputs one class, i.e. there is no decision boundary to compute a distance to.

Figure: Figure 1: We solve the optimizaton problem (11) on the Wisconsin Breast Cancer dataset for a range of $r$ values while holding $\beta=0.01$ constant. On the left, we plot average distance to the decision boundary of test examples against $r$. On the right, we plot robust accuracy against FGSM attacks of $\ell_{\infty}$ magnitude 0.8 for the adversarial and standard models. We additionally plot clean accuracy for the adversarial model.
Refer to caption: extracted/5932387/figures/dec_dist_oversmoothing_final.png

### 4.2 Robust Image Classification

We replace the final two fully connected layers of a pre-trained Pre-Activation ResNet-18 model (He et al., ) with a two-layer polynomial activation network. A uniform random sample of $1\%$ of the training images in the CIFAR-10 dataset () is collected and used to train the convex polynomial and ReLU activation networks. As a baseline adversarial training method, we train a Pre-Activation ResNet-18 model with sharpness-aware minimization (SAM) on the full training set. Table 2 presents clean and robust accuracies for the standard Pre-Activation ResNet-18, the same architecture trained with sharpness-aware minimization, and our adversarial polynomial and ReLU activation models trained on a $1\%$ subset of the data. We choose $\beta=0.01,r=0.5$ for the robust polynomial network. For the robust ReLU network, $\beta=0.01$, $r=40$, $p=1$, $q=\infty$, and the number of sampled sign patterns is $P=500$. We additionally train the adversarial ReLU activation model (with the same $\beta,r,p,q,P$) on the full CIFAR-10 training set. We train the robust two-layer ReLU and polynomial activation networks with the Adam optimizer (Kingma & Ba, ).

**Table 2: Clean and $\ell_{\infty}$-robust test accuracies of Pre-Activation ResNet18 models with various training methods.**
| 1% Subset of CIFAR-10 Dataset |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- |
|  | $\ell_{\infty}$-norm of attack |  |  |  |  |  |
| Method | Clean | $1/255$ | $2/255$ | $4/255$ | $6/255$ | $8/255$ |
| Adversarial Polynomial | .934 | .704 | .558 | .417 | .351 | .308 |
| Adversarial ReLU | .935 | .585 | .389 | .244 | .193 | .168 |
| Full CIFAR-10 Dataset |  |  |  |  |  |  |
| Adversarial ReLU | .920 | .813 | 0.676 | 0.522 | 0.449 | 0.4005 |
| Sharpness-Aware | .928 | .732 | .520 | .276 | .172 | .169 |
| Standard | .940 | .588 | .386 | .246 | .196 | 0.170 |

Figure: Figure 2: Visualization of the results in Table 2. Dashed lines indicate that the final convex layers were trained on a random $1\%$ subset of training data.
Refer to caption: extracted/5932387/figures/cifar_acc_results_final.png

With just $1\%$ of the training set, our robust polynomial activation network significantly outperforms sharpness-aware minimization (which was trained on the full dataset) for all attack sizes except $1/255$, where it still provides a large performance boost relative to standard training. On the full dataset, the adversarial ReLU network is by far the best model. Though it suffers from a mild degradation of clean accuracy, it performs much better than sharpness-aware minimization for all attack sizes. However, on the subsampled CIFAR-10 dataset, the adversarial ReLU network doesn’t provide a boost in robust accuracy over standard training.

These results corroborate the observations in Bartan & Pilanci (); Rodrigues & Givigi (); Bartan & Pilanci () that polynomial activation networks excel when data is scarce. While the optimization problem in  (11) is costly to solve, it is both computationally feasible and highly performant in data-constrained applications. For applications where data is more abundant, the ReLU formulation of  (15) is cheaper and likely to provide better results. This is due to the difference in expressive power between polynomial and ReLU activation networks. Specifically, the high bias of polynomial activation networks prevents overfitting when little data is available. On the other hand, ReLU activation networks exhibit low bias and high variance, making it difficult to train a model in the data-constrained setting without overfitting the random trends inherent to small sample sizes.

## 5 Conclusion

Our results demonstrate that the convex adversarial training program for two-layer polynomial activation networks is performant on small-scale classification datasets. Further, when the input dimension is large (on the order of $10^{2}$ or $10^{3}$), the robust polynomial activation network still improves robust test accuracy over sharpness-aware minimization when trained on a small random sample of the data. Convex adversarial training of two-layer ReLU networks is feasible with large amounts of data, yielding significant improvements in robustness to adversarial attacks over sharpness-aware minimization. However, we find that when training data is constrained, ReLU networks are less effective.

Adversarial training methods such as projected gradient descent (Madry et al., ) involve computing multiple descent steps for each training batch, which drastically increases the computational overhead of training (Schwinn et al., ). The convex programs  (11) and  (15) analytically penalize the worst-case value such descent methods approximate. While convex adversarial programs are currently limited by neural network depth, they can still offer significant performance increases with less computational overhead than iterative descent methods.

Future research directions could include layer-wise convex adversarial training for deep neural networks, derivations of convex adversarial programs for deeper architectures, or extensions of these techniques for regression tasks.

## 6 Acknowledgement

Mert Pilanci was supported in part by National Science Foundation (NSF) under Grant DMS-2134248; in part by the NSF CAREER Award under Grant CCF-2236829; in part by the U.S. Army Research Office Early Career Award under Grant W911NF-21-1-0242; in part by the Office of Naval Research under Grant N00014-24-1-2164.

## Appendix A Proof of The Main Theorem

In Subsection A.1, we make a duality argument to prove that the convex program (11) gives a lower bound for  (10). Subsection A.2 leverages the neural decomposition procedure (Bartan & Pilanci, ) to prove the upper bound. Before that, we state two versions of the S-procedure, which is a useful theorem of alternatives concerning pairs of quadratic
constraints. It allows us to convert implications involving two quadratics
to more tractable semidefinite constraints (Boyd & Vandenberghe, ; Uhlig, ; Pólik & Terlaky, ).

###### Theorem A.1 (S-procedure with inequality)

Let $g:\mathbb{R}^{d}\rightarrow\mathbb{R}$, $f:\mathbb{R}^{d}\rightarrow\mathbb{R}$ be quadratic functions such that $g(x)=x^{T}A_{1}x+2b_{1}^{T}x+c_{1}$ and $f(x)=x^{T}A_{2}x+2b_{2}^{T}x+c_{2}$. We make no assumptions about the convexity of $g$ or $f$. Provided $g(x)\leq 0$ is strictly feasible, the implication $g(x)\leq 0\implies f(x)\leq 0$ holds if and only if there exists some $\lambda\geq 0$ such that

$$ $\displaystyle\lambda\begin{bmatrix}A_{1}&b_{1}\\ b_{1}^{T}&c_{1}\end{bmatrix}-\begin{bmatrix}A_{2}&b_{2}\\ b_{2}^{T}&c_{2}\end{bmatrix}\succeq 0.$ $$

Proof: We refer the reader to pp. 657-658 of Boyd & Vandenberghe ().

###### Theorem A.2 (S-procedure with equality)

Let $g:\mathbb{R}^{d}\rightarrow\mathbb{R}$, $f:\mathbb{R}^{d}\rightarrow\mathbb{R}$ be quadratic functions such that $g(x)=x^{T}A_{1}x+2b_{1}^{T}x+c_{1}$ and $f(x)=x^{T}A_{2}x+2b_{2}^{T}x+c_{2}$. Suppose that $g$ is strictly convex (i.e. $A_{1}\succ 0$) and takes on both positive and negative values. The implication $g(x)=0\implies f(x)\leq 0$ holds if and only if there exists some $\lambda\in\mathbb{R}$ such that

$$ $\displaystyle\lambda\begin{bmatrix}A_{1}&b_{1}\\ b_{1}^{T}&c_{1}\end{bmatrix}-\begin{bmatrix}A_{2}&b_{2}\\ b_{2}^{T}&c_{2}\end{bmatrix}\succeq 0.$ (17) $$

Proof: See Appendix B.1.

###### Theorem A.1 (S-procedure with inequality)

###### Theorem A.2 (S-procedure with equality)

### A.1 Lower bound: convex duality and S-procedure

Expanding the right sides of the worst-case constraints in  (10), we obtain

$$ $w_{i}=\min_{||\Delta||_{2}\leq r}\Delta^{T}Q_{i}\Delta+\Delta^{T}g_{i}+h_{i} \quad\forall i\in[n]\\$ (18) $$

where $Q_{i},g_{i},h_{i}$ are defined as follows for all $i\in[n]$:

$$ $\displaystyle Q_{i}$ $\displaystyle=y_{i}\sum_{j=1}^{m}au_{j}u_{j}^{T}\alpha_{j},\quad g_{i}=y_{i} \sum_{j=1}^{m}(bu_{j}+2au_{j}u_{j}^{T}x_{i})\alpha_{j}$ (19) $\displaystyle h_{i}$ $\displaystyle=y_{i}\sum_{j=1}^{m}(ax_{i}^{T}u_{j}u_{j}^{T}x_{i}+bx_{i}^{T}u_{j }+c)\alpha_{i}$ $$

Lemma B.2, allows us to relax the equality constraints on the $w_{i}$’s without changing the optimal value of  (10). Observe the following equivalence:

$$ $\displaystyle w_{i}\leq\min_{||\Delta||_{2}\leq r}y_{i}\sum_{j=1}^{m}\sigma((x _{i}+\Delta)^{T}u_{j})\alpha_{j}$ (20) $\displaystyle\iff$ $\displaystyle[\Delta^{T}\Delta-r^{2}\leq 0\implies w_{i}\leq y_{i}(\Delta^{T}Q _{i}\Delta+\Delta^{T}g_{i}+h_{i})]$ $$

The inequality $\Delta^{T}\Delta-r^{2}\leq 0$ is strictly feasible, so we may apply the S-procedure with inequality (Theorem A.1). We additionally split up the minimization in  (10) to obtain
(21), a new optimization problem with the same optimal value as  (10). Note that the optimization variables $\{Q_{i},g_{i},h_{i}\}^{n}_{i=1}$ are defined only to make  (21) more readable.

$$ $\displaystyle\underset{\{u_{j}\}_{j=1}^{m},||u_{j}||_{2}=1}{\operatorname{ minimize}}\quad\underset{\{\alpha_{j}\}_{j=1}^{m}}{\operatorname{minimize}}$ $\displaystyle\quad\ell(w)+\beta\sum_{j=1}^{m}|\alpha_{j}|$ (21) $\displaystyle\operatorname{subject\;\,to}$ $\displaystyle\quad\begin{bmatrix}\lambda_{i}I+Q_{i}&\frac{1}{2}g_{i}\\ \frac{1}{2}g_{i}^{T}&h_{i}-\lambda_{i}r^{2}+w_{i}\end{bmatrix}\succeq 0$ $\displaystyle\quad\lambda_{i}\geq 0\quad\forall i\in[n]$ $\displaystyle\quad Q_{i}=y_{i}\sum_{j=1}^{m}au_{j}u_{j}^{T}\alpha_{j},\quad g_ {i}=y_{i}\sum_{j=1}^{m}(bu_{i}+2au_{j}u_{j}^{T}x_{i})\alpha_{j}$ $\displaystyle\quad h_{i}=y_{i}\sum_{j=1}^{m}(ax_{i}^{T}u_{j}u_{j}^{T}x_{i}+bx_ {i}^{T}u_{j}+c)\alpha_{i}$ $$

Define the Lagrange multipliers $\{M_{i}\}_{i=1}^{n}$, $\{\gamma_{i}\}_{i=1}^{n}$, where $M_{i}\in\mathcal{S}^{d+1}_{+}$ and $\gamma\in\mathbb{R}^{n}_{+}$. We will shortly need to reference the block constituents of $M_{i}$, defined as follows: $M_{i,1}\in\mathcal{S}^{d},M_{i,2}\in\mathbb{R}^{d},M_{i,4}\in\mathbb{R}$, where $M_{i}=\begin{bmatrix}M_{i,1}&M_{i,2}\\
M_{i,2}^{T}&M_{i,4}\end{bmatrix}$. Then the Lagrangian of the inner minimization problem in  (21), excluding the notational equality constraints, is

$$ $\displaystyle L(w,\alpha,\gamma,M)=\ell(w)+\beta\sum^{m}_{j=1}|\alpha_{j}|+ \sum_{i=1}^{n}\left[\left<M_{i},\begin{bmatrix}\lambda_{i}I+Q_{i}&\frac{1}{2}g _{i}\\ \frac{1}{2}g_{i}^{T}&h_{i}-\lambda_{i}r^{2}+w_{i}\end{bmatrix}\right>+\gamma_{ i}\lambda_{i}\right]$ (22) $$

For ease of notation, define $M_{4}\in\mathbb{R}^{n}$, where the $i$-th entry of $M_{4}$ is $M_{i,4}$. Then, maximizing the Lagrangian over $w$ and $\alpha$, we obtain  (23), which is the dual to the inner problem of  (21). The optimization variables $\{Z_{j}\}_{j=1}^{m}$ are defined only to make  (23)
more readable.

$$ $\displaystyle\underset{\{M_{i},\}_{i=1}^{n},\{Z_{j}\}_{j=1}^{m}}{\operatorname {maximize}}$ $\displaystyle\quad-\ell^{*}(-M_{4})$ (23) $\displaystyle\operatorname{subject\;\,to}$ $\displaystyle\quad M_{i}\succeq 0\quad$ $\displaystyle\quad r^{2}M_{i,4}-\operatorname{Tr}(M_{i,1})\geq 0\quad\forall i \in[n]$ $\displaystyle\quad|Z_{j}|\leq\beta$ $\displaystyle\quad Z_{j}=au_{j}^{T}\left(\sum^{n}_{i=1}y_{i}M_{i,1}\right)u_{j }+\sum^{n}_{i=1}y_{i}M_{i,2}^{T}(bu_{i}+2au_{j}u_{j}^{T}x_{i})$ $\displaystyle\qquad\qquad+\sum^{n}_{i=1}y_{i}M_{i,4}(ax_{i}u_{j}u_{j}^{T}x_{i} +bx_{i}^{T}u_{j}+c)$ $$

Observe that the optimal value of  (23) is a function of the $u_{j}$’s. Let $d^{\star}$ be the minimum of this function over the $u_{j}$’s, subject to $||u_{j}||_{2}=1$ for all $j\in[m]$. Following Lemma B.1, we swap the order of the minimization and maximization operations, obtaining a lower bound on $d^{*}$, which is in turn a lower bound on the optimal value of  (10):

$$ $\displaystyle d^{*}\geq\underset{\{u_{j},Z_{j}\}_{j=1}^{m},\{M_{i}\}_{i=1}^{n} }{\operatorname{maximize}}$ $\displaystyle\quad-\ell^{*}(-M_{4})$ (24) $\displaystyle\operatorname{subject\;\,to}$ $\displaystyle\quad||u_{j}||_{2}=1\quad\forall j\in[m]$ $\displaystyle\quad M_{i}\succeq 0\quad$ $\displaystyle\quad r^{2}M_{i,4}-\operatorname{Tr}(M_{i,1})\geq 0\quad\forall i \in[n]$ $\displaystyle\quad|Z_{j}|\leq\beta$ $\displaystyle\quad Z_{j}=au_{j}^{T}\left(\sum^{n}_{i=1}y_{i}M_{i,1}\right)u_{j }+\sum^{n}_{i=1}y_{i}M_{i,2}^{T}(bu_{i}+2au_{j}u_{j}^{T}x_{i})$ $\displaystyle\qquad\qquad+\sum^{n}_{i=1}y_{i}M_{i,4}(ax_{i}u_{j}u_{j}^{T}x_{i} +bx_{i}u_{j}+c)$ $$

Note first that $Z_{j}$ is quadratic in $u_{j}$ and second that $|Z_{j}|\leq\beta$ if and only if $Z_{j}\leq\beta$ and $Z_{j}\geq-\beta$. Our constraints enforce the implications $||u_{j}||_{2}=1\implies Z_{j}\leq\beta$ and $||u_{j}||_{2}=1\implies Z_{j}\geq-\beta$, so we apply the S-procedure with equality (Theorem A.2) twice. In doing so, we obtain two semidefinite constraints and two new optimization variables $\rho_{1},\rho_{2}\in\mathbb{R}$. We the define optimization variables $Q^{\prime}\in\mathcal{S}^{d},g^{\prime}\in\mathbb{R}^{d},h^{\prime}\in\mathbb{R}$ for readability.

$$ $\displaystyle\underset{\{M_{i}\}_{i=1}^{n},Q^{\prime},g^{\prime},h^{\prime}, \rho_{1},\rho_{2}}{\operatorname{maximize}}$ $\displaystyle\quad-\ell^{*}(-M_{4})$ (25) $\displaystyle\operatorname{subject\;\,to}$ $\displaystyle\quad M_{i}\succeq 0,\quad r^{2}M_{i,4}-\operatorname{Tr}(M_{i,1} )\geq 0\quad\forall i\in[n]$ $\displaystyle\quad\begin{bmatrix}\rho_{1}I-Q^{\prime}&-\frac{1}{2}g^{\prime}\\ -\frac{1}{2}g^{\prime T}&\beta-h^{\prime}-\rho_{1}\end{bmatrix}\succeq 0$ $\displaystyle\quad\begin{bmatrix}\rho_{2}I+Q^{\prime}&\frac{1}{2}g^{\prime}\\ \frac{1}{2}g^{\prime T}&\beta+h^{\prime}-\rho_{2}\end{bmatrix}\succeq 0$ $\displaystyle\quad Q^{\prime}=\sum^{n}_{i=1}ay_{i}\left(M_{i,1}+2M_{i,2}x_{i}^ {T}+M_{i,4}x_{i}x_{i}^{T}\right)$ $\displaystyle\quad g^{\prime}=\sum^{n}_{i=1}by_{i}(M_{i,2}+M_{i,4}x_{i}),\quad h ^{\prime}=\sum^{n}_{i=1}cy_{i}M_{i,4}$ $$

We introduce the Lagrange multipliers $Z,Z^{\prime}\in\mathcal{S}_{+}^{d+1}$, $\{R_{i}\}_{i=1}^{n}$, $R_{i}\in\mathcal{S}_{+}^{d+1}$, $\lambda\in\mathbb{R}^{n}_{+}$. Then, excluding notational equality constraints on $Q^{\prime},g^{\prime},h^{\prime}$, the Lagrangian of  (25) is

$$ $\displaystyle L(M,\rho_{1},\rho_{2},Z,Z^{\prime},R_{i},\lambda)=$ $\displaystyle-\ell^{*}(-M_{4})+\sum^{n}_{i=1}\left[\lambda_{i}(r^{2}M_{i,4}- \operatorname{Tr}(M_{i,1}))+\left<R_{i},M_{i}\right>\right]$ (26) $\displaystyle+\left<Z,\begin{bmatrix}\rho_{1}I-Q^{\prime}&-\frac{1}{2}g^{ \prime}\\ -\frac{1}{2}g^{\prime T}&\beta-h^{\prime}-\rho_{1}\end{bmatrix}\right>+\left<Z ^{\prime},\begin{bmatrix}\rho_{2}I+Q^{\prime}&\frac{1}{2}g^{\prime}\\ \frac{1}{2}g^{\prime T}&\beta+h^{\prime}-\rho_{2}\end{bmatrix}\right>$ $$

Let $\tilde{Z}=Z-Z^{\prime}$. With some algebraic manipulations (e.g. expanding $Q^{\prime},g^{\prime},h^{\prime}$), we obtain the final form of the Lagrangian by adding $0=\sum^{n}_{i=1}(M_{i,4}w_{i}-M_{i,4}w_{i})$ to  (26), where $w\in\mathbb{R}^{n}$:

$$ $\displaystyle L(M,\rho_{1},\rho_{2},Z,Z^{\prime},R_{i},\lambda)$ (27) $\displaystyle=-\ell^{*}(-M_{4})-\sum^{n}_{i=1}M_{i,4}w_{i}+\rho_{1}( \operatorname{Tr}(Z_{1})-Z_{4})+\beta(Z_{4}+Z_{4}^{\prime})+\rho_{2}( \operatorname{Tr}(Z_{1}^{\prime})-Z_{4}^{\prime})$ $\displaystyle+\sum^{n}_{i=1}\left<M_{i},R_{i}+y_{i}\begin{bmatrix}-y_{i} \lambda_{i}I-a\tilde{Z}_{1}&-ax_{i}^{T}\tilde{Z}_{1}-\frac{1}{2}b\tilde{Z}_{2} \\ -a\tilde{Z}_{1}x_{i}-\frac{1}{2}b\tilde{Z}_{2}^{T}&-ax_{i}^{T}\tilde{Z}_{1}x_{ i}-bx_{i}^{T}\tilde{Z}_{2}-c\tilde{Z}_{4}+y_{i}\lambda_{i}r^{2}+w_{i}y_{i}\end {bmatrix}\right>$ $$

Lastly, to arrive at the dual problem, we must maximize  (27) over $\{M_{i}\}_{i=1}^{n},\rho_{1},\rho_{2}$. Note that  (27) is only bounded when the following conditions are met:

$$ $\displaystyle\operatorname{Tr}(Z_{1})=Z_{4},\qquad\operatorname{Tr}(Z_{1}^{ \prime})=Z_{4}^{\prime},\qquad R_{i}\succeq 0$ (28) $\displaystyle R_{i}=y_{i}\begin{bmatrix}y_{i}\lambda_{i}I+a\tilde{Z}_{1}&ax_{i }^{T}\tilde{Z}_{1}+\frac{1}{2}b\tilde{Z}_{2}\\ a\tilde{Z}_{1}x_{i}+\frac{1}{2}b\tilde{Z}_{2}&ax_{i}^{T}\tilde{Z}_{1}x_{i}+bx_ {i}^{T}\tilde{Z}_{2}+c\tilde{Z}_{4}-y_{i}\lambda_{i}r^{2}-w_{i}y_{i}\end{ bmatrix}\quad\forall i\in[n]$ $$

We say that the lagrange multipliers $\{R_{i}\}^{n}_{i=1},Z,Z^{\prime}$ are dual feasible if they satisfy all constraints in  (28). Then we have

$$ $\displaystyle\max_{\{M_{i}\}_{i=1}^{n},\rho_{1},\rho_{2}}$ $\displaystyle L(M,\rho_{1},\rho_{2},Z,Z^{\prime},R_{i},\lambda_{i})$ $\displaystyle=\begin{cases}\ell(w)+\beta(Z_{4}+Z_{4}^{\prime})&\text{if $\{R_{ i}\}^{n}_{i=1},Z,Z^{\prime}$ are dual feasible}\\ \infty&\text{otherwise}\end{cases}$ (29) $$

In writing out the dual problem, we recover the proposed convex adversarial training problem  (11). This proves the optimal value of  (11) is a lower bound on that of the nonconvex formulation  (10).

### A.2 Upper bound: neural decomposition

Let $Z^{\star},Z^{\prime\star},\lambda^{\star},w^{\star}$ be optimal solutions to  (11). Using the neural decomposition procedure devised in Section 4 of Bartan & Pilanci (), we obtain $\{u_{j},d_{j}\}^{k}_{j=1}$ and $\{u^{\prime}_{j},d^{\prime}_{j}\}^{k^{\prime}}_{j=1}$ where $u_{j},u^{\prime}_{j}\in\mathbb{R}^{d}$, $d_{j},d^{\prime}_{j}\in\mathbb{R}$, $||u_{j}||_{2}=||u^{\prime}_{j}||_{2}=1$, $\operatorname{rank}{Z^{\star}}=k,\operatorname{rank}{Z^{\prime\star}}=k^{\prime}$ and

$$ $\displaystyle Z_{1}^{\star}=\sum^{k}_{j=1}u_{j}u_{j}^{T}d_{j}^{2},\quad Z_{2}^ {\star}=\sum^{k}_{j=1}u_{j}d_{j}^{2},\quad Z_{4}^{\star}=\sum^{k}_{j=1}d_{j}^{2}$ (30) $\displaystyle Z_{1}^{\prime\star}=\sum^{k^{\prime}}_{j=1}u^{\prime}_{j}{u^{ \prime}_{j}}^{T}{d^{\prime}_{j}}^{2},\quad Z_{2}^{\prime\star}=\sum^{k^{\prime }}_{j=1}u^{\prime}_{j}{d^{\prime}_{j}}^{2},\quad Z_{4}^{\prime\star}=\sum^{k^{ \prime}}_{j=1}{d^{\prime}_{j}}^{2}$ $$

Since $Z^{\star},Z^{\prime\star},\lambda^{\star},w^{\star}$ are feasible in problem (11), the S-procedure (Theorem A.1) guarantees that, for $i\in[n]$,

$$ $\displaystyle w_{i}^{\star}\leq\min_{||\Delta||_{2}\leq r}a(x_{i}+\Delta)^{T}( Z^{\star}_{1}-Z^{\prime\star}_{1})(x_{i}+\Delta)+b(Z_{2}^{\star}-Z^{\prime \star}_{2})^{T}(x_{i}+\Delta)+c(Z^{\star}_{4}-Z^{\prime\star}_{4})$ (31) $$

Let $m^{\star}=k+k^{\prime}$ and rename the neural network weights as follows: $u_{k+j}=u^{\prime}_{j}$, $\alpha_{j}=d^{2}_{j}$, $\alpha_{k+j}=-d^{\prime 2}_{j}$. Plugging in the decompositions for $Z^{\star}$ and $Z^{\prime\star}$, a bit of algebra shows that $w^{\star}$ and $\{u_{j},\alpha_{j}\}^{m^{\star}}_{j=1}$ are feasible in the relaxed nonconvex training problem  (36) for a neural network with $m^{\star}$ neurons:

$$ $\displaystyle w_{i}^{\star}\leq\min_{||\Delta||_{2}\leq r}\sum^{k}_{j=1}\sigma (u_{j}^{T}(x_{i}+\Delta))d_{j}^{2}-\sum^{k^{\prime}}_{j=1}\sigma({u^{\prime}}_ {j}^{T}(x_{i}+\Delta))d_{j}^{\prime 2}=\min_{||\Delta||_{2}\leq r}\sum^{m^{ \star}}_{j=1}\sigma(u_{j}^{T}(x_{i}+\Delta))\alpha_{j}$ (32) $$

Importantly, the objectives of problem (11) and problem (36) are identical after plugging in the decomposition:

$$ $\displaystyle\ell(w^{\star})+\beta(Z^{\star}_{4}+Z^{\prime\star}_{4})=\ell(w^{ \star})+\beta\left(\sum^{k}_{j=1}d_{j}^{2}+\sum^{k^{\prime}}_{j=1}{d^{\prime}_ {j}}^{2}\right)=\ell(w^{\star})+\beta\sum^{m^{\star}}_{j=1}|\alpha_{j}|$ (33) $$

Let $p_{\text{convex}}^{\star}$, $p_{\text{relaxed}}^{\star}$, and $p_{\text{original}}^{\star}$ be the optimal values of the convex formulation  (11), relaxed nonconvex formulation  (36), and original nonconvex formulation  (10), respectively. Since $w^{\star},\{u_{j},\alpha_{j}\}^{m^{\star}}_{j=1}$ are feasible in  (36) and the objectives of  (36) and  (11) have the same form, we conclude $p_{\text{convex}}^{\star}\geq p_{\text{relaxed}}^{\star}=p_{\text{original}}^{\star}$ (the equality is due to Lemma B.2). From Section A.1, $p_{\text{convex}}^{\star}$ is also a lower bound and therefore $p_{\text{convex}}^{\star}=p_{\text{relaxed}}^{\star}=p_{\text{original}}$. Hence $w^{\star},\{u_{j},\alpha_{j}\}^{m^{\star}}_{j=1}$ provide an optimal solution to the relaxed nonconvex problem  (36). Finally, from Corollary B.1, there exists some $w^{\prime\star}$ such that $w^{\prime\star},\{u_{j},\alpha_{j}\}^{m^{\star}}_{j=1}$ are also optimal in the original nonconvex program  (10).

## Appendix B Proofs of Useful Lemmas

### B.1 Proof of the S-procedure With Equality

Applying proposition 3.1 from Pólik & Terlaky (), we have that $g(x)=0\implies f(x)\leq 0$ if and only if there exists some $\lambda\in\mathbb{R}$ such that $\lambda g(x)-f(x)\geq 0$ for all $x\in\mathbb{R}^{d}$. Rewriting the inequality, we have

$$ $\displaystyle 0\leq\lambda g(x)-f(x)=\begin{bmatrix}x\\ 1\end{bmatrix}^{T}\left(\lambda\begin{bmatrix}A_{1}&b_{1}\\ b_{1}^{T}&c_{1}\end{bmatrix}-\begin{bmatrix}A_{2}&b_{2}\\ b_{2}&c_{2}\end{bmatrix}\right)\begin{bmatrix}x\\ 1\end{bmatrix}$ (34) $$

Note that  (34) implies  (17) because, for any vector $v\in\mathbb{R}^{d+1}$,

$$ $\displaystyle v^{T}\left(\lambda\begin{bmatrix}A_{1}&b_{1}\\ b_{1}^{T}&c_{1}\end{bmatrix}-\begin{bmatrix}A_{2}&b_{2}\\ b_{2}&c_{2}\end{bmatrix}\right)v$ (35) $\displaystyle=\frac{1}{v^{2}_{d+1}}\begin{bmatrix}v_{1:d}/v_{d+1}\\ 1\end{bmatrix}^{T}\left(\lambda\begin{bmatrix}A_{1}&b_{1}\\ b_{1}^{T}&c_{1}\end{bmatrix}-\begin{bmatrix}A_{2}&b_{2}\\ b_{2}&c_{2}\end{bmatrix}\right)\begin{bmatrix}v_{1:d}/v_{d+1}\\ 1\end{bmatrix}\geq 0.$ $$

Here, $v_{1:d}$ denotes the $d$-vector containing the first $d$ entries of $v$, and $v_{d+1}$ is the $d+1$-th entry of $v$. If  (17) holds, it immediately follows that $\lambda g(x)-f(x)\geq 0$ for all $x\in\mathbb{R}^{d}$.

### B.2 Other Lemmas

###### Lemma B.1 (Max-min inequality)

For any $f:X\times Y\rightarrow R$,

$$ $\displaystyle\underset{x\in X}{\sup}\underset{y\in Y}{\inf}f(x,y)\leq\underset {y\in Y}{\inf}\underset{x\in X}{\sup}f(x,y)$ $$

Proof: Let $g(y)=\sup_{x\in X}f(x,y)$. Note that $f(x,y)\leq g(y)$ for all $y\in Y,x\in X$. Hence $\inf_{y\in Y}f(x,y)\leq\inf_{y\in Y}g(y)$ for all $x\in X$. Taking the supremum over $x$ on the left of the inequality completes the proof.

###### Lemma B.2

The relaxed problem  (36) has the same optimal value as the original problem  (10) when $\ell:\mathbb{R}^{n}\rightarrow\mathbb{R}$ is nonincreasing in its inputs:

$$ $\displaystyle\underset{\{u_{j},\alpha_{j}\}_{j=1}^{m},w}{\operatorname{ minimize}}$ $\displaystyle\quad\ell(w)+\beta\sum_{j=1}^{m}|\alpha_{j}|$ (36) $\displaystyle\operatorname{subject\;\,to}$ $\displaystyle\quad w_{i}\leq\min_{||\Delta||_{2}\leq r}y_{i}\sum_{j=1}^{m} \sigma((x_{i}+\Delta)^{T}u_{j})\alpha_{j}\quad\forall i\in[n]$ $\displaystyle||u_{j}||_{2}=1\quad\forall j\in[m]$ $$

Proof: The optimal value of  (36) is clearly a lower bound on that of  (10). We now prove that it is an upper bound. Let $w^{\star},\{u_{j}^{\star},\alpha_{j}^{\star}\}_{j=1}^{m}$ be the optimal solutions for  (36). Define $w^{\prime\star}$ as follows:

$$ $\displaystyle w^{\prime\star}_{i}=\min_{||\Delta||_{2}\leq r}y_{i}\sum_{j=1}^{ m}\sigma((x_{i}+\Delta)^{T}u^{\star}_{j})\alpha^{\star}_{j}$ $$

Then $\ell(w^{\prime\star})=\ell(w^{\star})$ since $\ell(\cdot)$ is nonincreasing and $w^{\star}_{i}\leq w^{\prime\star}_{i}$ for all $i\in[n]$. Hence $w^{\prime\star},\{u_{j}^{\star},\alpha_{j}^{\star}\}_{j=1}^{m}$ are also an optimal solution for  (36). Observe that $w^{\prime\star},\{u_{j}^{\star},\alpha_{j}^{\star}\}_{j=1}^{m}$ are feasible in  (10), so $\ell(w^{\prime\star})+\beta\sum^{m}_{j=1}|\alpha_{j}^{\star}|$ is an upper bound on the optimal value of  (10). Note that since $\ell(w^{\prime\star})+\beta\sum^{m}_{j=1}|\alpha_{j}^{\star}|$ is also a lower bound, it gives the optimal value for the original adversarial training problem  (10).

###### Corollary B.1

Suppose $w^{\star},\{u_{j}^{\star},\alpha_{j}^{\star}\}_{j=1}^{m}$ are optimal in the relaxed problem  (36). Then there exists $w^{\prime\star}$ such that $w^{\prime\star},\{u_{j}^{\star},\alpha_{j}^{\star}\}_{j=1}^{m}$ are optimal in the original adversarial training problem  (10).

Proof:
This result follows by taking $w^{\prime\star}$ as defined in the proof of Lemma B.2 above.

###### Lemma B.1 (Max-min inequality)

###### Lemma B.2

###### Corollary B.1

## Appendix C Distance to the Decision Boundary of a Polynomial Activation Network

In the binary classification setting, the decision boundary of a two-layer polynomial activation network $f$ is the set $\mathcal{D}=\{x:f(x)=0\}$. We define the $\ell_{2}$-distance from an example $x$ to $\mathcal{D}$:

$$ $\displaystyle d_{\mathcal{D}}(x)=\min_{\gamma\in\mathcal{D}}||x-\gamma||_{2}$ (37) $$

For typical neural network architectures, nonconvexity of $\mathcal{D}$ and $f$ prevent efficient computation of $d_{\mathcal{D}}(x)$. In this section, we show  (37) can be formulated as a convex SDP for two-layer polynomial activation networks and hence $d_{\mathcal{D}}(x)$ is computable in fully polynomial time.

For an example $x$ with label $y$, suppose that $f$ correctly classifies $x$ (i.e. $\operatorname{sign}{f(x)}=y)$. Since $\gamma\in\mathcal{D}\implies f(\gamma)=0$,  (37) becomes

$$ $\displaystyle d_{\mathcal{D}}(x)$ $\displaystyle=\min_{\gamma:f(\gamma)=0}||x-\gamma||_{2}=\min_{\gamma:yf(\gamma )\leq 0}||x-\gamma||_{2}$ (38) $$

We claim that relaxing the constraint $f(\gamma)=0$ to $yf(\gamma)\leq 0$ does not change the optimal value of  (37): any $\gamma$ for which $yf(\gamma)<0$ is strictly on the opposite side of the decision boundary relative to $x$, but, by continuity of $f$, there lies $\gamma^{\prime}$ in $\mathcal{D}$ which is between $x$ and $\gamma$. Hence $||x-\gamma^{\prime}||_{2}\leq||x-\gamma||_{2}$.

Recognizing that $\gamma^{*}=\operatorname*{arg\,min}_{\gamma:yf(\gamma)\leq 0}||x-\gamma||_{2}=
\operatorname*{arg\,min}_{\gamma:yf(\gamma)\leq 0}||x-\gamma||^{2}_{2}$, we again use the S-procedure with inequality (Theorem A.1). Consider the implication

$$ $\displaystyle yf(\gamma)\leq 0\implies(x-\gamma)^{T}(x-\gamma)\geq s$ (39) $$

Then the optimization problem (with variables $s$ and $\gamma$)

$$ maximize $\displaystyle s$ subject to $\displaystyle[yf(\gamma)\leq 0\implies(x-\gamma)^{T}(x-\gamma)\geq s]$ (40) $$

has the same optimal value as $\min_{\gamma:yf(\gamma)\leq 0}||x-\gamma||^{2}_{2}$. If our classifier takes on both positive and negative values (a very reasonable assumption), the first inequality in  (39) is strictly feasible. So  (C) is equivalent to

$$ maximize $\displaystyle s$ (41) subject to $\displaystyle\lambda\geq 0$ $\displaystyle\lambda y\begin{bmatrix}a\tilde{Z}_{1}&\frac{1}{2}b\tilde{Z}_{2} \\ \ \frac{1}{2}b\tilde{Z}_{2}^{T}&c\tilde{Z}_{4}\end{bmatrix}-\begin{bmatrix}-I& x\\ x^{T}&-||x||_{2}^{2}+s\end{bmatrix}\succeq 0$ $$

The weights $\tilde{Z}_{1},\tilde{Z}_{2},\tilde{Z}_{4}$ of the classifier $f$ are fixed, so the only optimization variables in  (41) are $s$ and $\lambda$.

## Peer Reviews

confidence: 4
contribution: 2
initial_rating: 3
presentation: 2
questions: N/A
soundness: 2
strengths: The convex semidefinite program analysis for adversarial training in two-layer polynomial activation networks is novel to me.
summary: This paper introduces a convex semidefinite program (SDP) for adversarial training in two-layer polynomial activation networks, proving that it achieves the same globally optimal solution as its nonconvex counterpart and improves robust test accuracy against l infty attacks. Scalable implementations compatible with standard libraries and GPU acceleration show that retraining the final layers of a Pre-Activation ResNet-18 model on CIFAR-10 with this method significantly boosts robust test accuracy, underscoring the practical benefits of convex adversarial training for large models.
weaknesses: This paper has two major flaws and, in its current form, should not be accepted to ICLR.

1.The adversarial attack method used in this paper, FGSM, is outdated and too weak; the authors should at least employ AutoAttack to more rigorously test the model's robustness.

2.The baseline model is trained with sharpness-aware minimization, which primarily targets generalization rather than robustness. To demonstrate the effectiveness of their approach, the authors should compare against a stronger baseline focused on robust training.

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 1
questions: I have plenty of questions about the paper, which leads me to believe that the paper is not ready for publication.

The main contribution of the paper is Theorem 3.1, which proves that the optimal solutions to the adversarial training objective (Equation 10) can be recovered from the optimal solutions to its convex reformulation (Equation 11) with polynomial activation networks and $\ell_2$ perturbations. The motivation for proving such a result seems to originate from a previous work (Bai et al. 2022), claiming that convexly trained neural networks enjoy greater interpretability and reproducibility. Although this claim intuitively makes sense, it is not well-explained in the context of learning an adversarially robust neural network. Generally speaking, there is a lack of detailed discussions and results regarding the implications of Theorem 3.1. To my knowledge, it is unclear whether this is potentially an important contribution to advancing the research field of adversarial machine learning. Besides, it’s recommended for the authors to discuss their assumptions, e.g., whether Theorem 3.1 can be applied to general $\ell_p$ perturbations and ReLU-activated neural nets. 

Regarding the experiments, Section 4 considers FGSM attacks for $\ell_\infty$ perturbations. There is an obvious gap compared with the setting considered for Theorem 3.1. It has been shown in the literature that FGSM tends to underestimate the adversarial power with respect to $\ell_\infty$ perturbations - FGSM attack simply cannot approximate the worst-case in many cases. It is suggested that the adversarial robustness should be evaluated using stronger attacks, such as PGD attack [1] and Auto Attack [2]. $\ell_2$ perturbations should also be tested, which is more aligned with the theoretical settings. In addition, I think the authors should provide comparison results of their adversarial convex program with adversarial training [1], showcasing whether both lead to a similar set of model weights and comparable robustness performance. From my point of view, the set of presented experiments is fairly limited, which does not support the main argument of the paper well.

[1] Towards Deep Learning Models Resistant to Adversarial Attacks, https://arxiv.org/pdf/1706.06083

[2] Reliable Evaluation of Adversarial Robustness with an Ensemble of Diverse Parameter-free Attacks, https://arxiv.org/pdf/2003.01690


__Other Comments and Questions:__

1. The authors should do a better literature review on adversarially robust learning. There are only a few citations and fairly limited discussions of existing works, making it difficult for readers to see the paper's position within the relevant literature clearly.

2. A line of existing work develops certified methods to train an adversarially robust network, e.g., [3, 4]. They also reformulate the problem into a convex optimization problem. Can the authors provide some discussions?

3. The presentation of the paper should be largely improved. Sections 2 and 3 contain too many mathematical notations and equations, which take up lots of space. These equations should be simplified and replaced by other important discussions or results. In the title, there is even a typo regarding the word “Polyomial.” The authors should really proofread their manuscript more carefully before submitting the paper.  

[3] Certified defenses against adversarial examples, https://arxiv.org/pdf/1801.09344

[4] Provable defenses against adversarial examples via the convex outer adversarial polytope, https://arxiv.org/pdf/1711.00851
soundness: 1
strengths: + The theoretical results are new to the field, which might lead to some implications for training a robust model.
summary: The paper proposes a convex reformulation for the optimization objective of adversarial training and provides a theoretical result showing that the optimal solutions for both problems are equivalent.
weaknesses: - The implications of the work are unclear. In particular, a couple of important related works are not cited or discussed

- The numerical results are insufficient. 

- The presentation of the paper should be largely improved.

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 3
questions: - Could the authors consider additional convex activation functions and derive their corresponding reformulations? This would be a valuable contribution.
- The trade-off between clean accuracy and adversarial robustness has always been a critical issue in adversarial training. The authors are advised to report the accuracy of their adversarial trained models on clean samples.
- The experiment results on CIFAR-10 demonstrate that the adversarial trained network achieves approximately 40% accuracy against FGSM attacks ($l_\infty=8/255$). However, many state-of-the-art defense methods achieve better results. It would be beneficial for the authors to explain whether this relates to any conflicts with the optimality of their proofs.
soundness: 3
strengths: - Establishing a provable defense against adversarial is crucial, and the authors reformulate the adversarial training for polynomial activation neural networks to a convex SDP.
- In the manuscript, the authors provide detailed theoretical proofs for the equality between the global optimal solution of convex SDP and the solution of the non-convex formulation.
- Convex SDP is more friendly for obtaining the global optimal solution, and the experiments on multiple datasets also support the effectiveness.
summary: In this paper, the authors mainly focus on adversarial training for polynomial activation neural networks against $l_\infty$ adversarial attacks. Building on recent works that reformulate adversarial training for ReLU networks, the authors reformulate the problem for two-layer polynomial networks as a convex semidefinite program (SDP). The authors provide theoretical proof demonstrating that the global optimal solution of the convex SDP is equivalent to that of the original non-convex formulation. Additionally, the authors propose an implementation of the convex adversarial network within standard machine learning libraries, which demonstrates superior performance compared to both sharpness-aware and standard training methods.
weaknesses: - Although the authors present an implementation of convex SDP for both ReLU and polynomial activation networks, the theoretical results regarding the reformulation are limited to polynomial activations, which diminishes the overall contribution. Furthermore, most of the state-of-the-art networks today predominantly utilize ReLU activations rather than polynomial ones.
- In the experimental section, the authors provide accuracy results under various adversarial radius; however, they do not include accuracy metrics for the adversarial trained models on clean samples.
- It appears that adversarial training for polynomial activations may not generalize to larger datasets and is limited to operating on subsets of CIFAR-10.

---

confidence: 2
contribution: 2
initial_rating: 5
presentation: 2
questions: 1. To clarify, it seems to me that the program (12) is equivalent to the first two constriants in program (15) since (14) is an iff condition, is that correct? Moreover, is there an optimality guarantee or error analysis for the program (16)? Additionally, I’m curious about how many samples from [P] would be sufficient to obtain an adequately approximate solution. Further discussion or empirical results on this would be valuable.

2. Is there a specific reason why bias terms are omitted? What are the main challenges in considering bias terms? Furthermore, did the authors encounter any difficulties in generalizing the results to deeper networks (even without bias terms)? I assume the program would become significantly more complicated, but technically it feels feasible...?

3. How were $\beta$ and $r$ chosen in the experiments? Perhaps I missed it, but did authors report the  values of the tuning parameters $\rho$ for (16)? Also, why were different $r$ values selected for polynomial and ReLU activations? Any justifications would be helpful. The authors mention, "polynomial activation networks excel when data is scarce... For applications where data is more abundant, the ReLU formulation is cheaper and likely to provide better results," but there is no direct comparison between adversarial ReLU and adversarial polynomial in abundant-data settings. Could the authors elaborate on this point?

4. Is there a specific reason why the results for adversarial polynomial are reported only on 1% of CIFAR-10? Is this due to computational costs? It would be helpful if the authors could report training times across all results, particularly the run time comparisons of adversarial polynomial, adversarial ReLU, and other adversarial benchmarks.
soundness: 3
strengths: This is a well-written technical paper that clearly defines and derives its results. It is among the first works (perhaps the first, to my knowledge) to study convex reformulation of adversarial training. The proposed method provides a feasible and performant alternative for adversarial training.
summary: This paper proposes convex reformulations for adversarial training of two-layer NN without bias terms, using polynomial and ReLU activations. The authors provide well-presented theoretical formulations and optimality analysis. They also present a practical implementation using PyTorch instead of SDP solvers. Finally, experiments on various tasks and result analysis are presented.
weaknesses: 1. My primary concern is about efficiency. For adversarial polynomial, while the program (11) can be solved in polynomial time and is optimal for sufficiently wide networks, the authors suggest in line 481 that solving it remains costly. For adversarial ReLU, the authors approximate program (15) by using GD-like methods on (16) with samples from [P]. Thus, despite a solid theoretical foundation, I’m concerned about the practicality of applying this method to large-scale problems. In fact, the experiments are conducted on relatively small datasets, which may feel outdated in the context of current research standards.

2. Another concern is the scope of the contribution. This paper focuses on wide enough two-layer NNs, without bias terms, and with ReLU or polynomial activations, which is not typically used in practice for adversarial training. While the theoretical formulation (Programs 11 and 15) and optimality analysis (Theorem 3.1) are insightful, the problem setting feels somewhat simplified compared to practical scenarios.

Detailed questions are attached in the section below.