# Noisy Feature Mixup

Soon Hoe Lim
Nordita, KTH Royal Institute of Technology
and Stockholm University
<EMAIL_ADDRESS>
& N. Benjamin Erichson*
University of Pittsburgh
<EMAIL_ADDRESS>
&Francisco Utrera
University of Pittsburgh and ICSI
<EMAIL_ADDRESS>&Winnie Xu
University of Toronto
<EMAIL_ADDRESS>&Michael W. Mahoney
ICSI and UC Berkeley
<EMAIL_ADDRESS>equal contributions

###### Abstract

We introduce Noisy Feature Mixup (NFM), an inexpensive yet effective method
for data augmentation that combines the best of interpolation based training
and noise injection schemes. Rather than training with convex combinations of
pairs of examples and their labels, we use noise-perturbed convex combinations
of pairs of data points in both input and feature space. This method includes
mixup and manifold mixup as special cases, but it has additional advantages,
including better smoothing of decision boundaries and enabling improved model
robustness. We provide theory to understand this as well as the implicit
regularization effects of NFM. Our theory is supported by empirical results,
demonstrating the advantage of NFM, as compared to mixup and manifold mixup.
We show that residual networks and vision transformers trained with NFM have
favorable trade-offs between predictive accuracy on clean data and robustness
with respect to various types of data perturbation across a range of computer
vision benchmark datasets.

##  1 Introduction

Mitigating over-fitting and improving generalization on test data are central
goals in machine learning. One approach to accomplish this is regularization,
which can be either data-agnostic or data-dependent (e.g., explicitly
requiring the use of domain knowledge). Noise injection is a typical example
of data-agnostic regularization [3], where noise can be injected into the
input data [1], or the activation functions [27], or the hidden layers of
neural networks [5, 43].

$\boldsymbol{x}_{1}$$\boldsymbol{x}_{2}$$\lambda\boldsymbol{x}_{1}+(1-\lambda)\boldsymbol{x}_{2}$

$\boldsymbol{x}_{1}^{\prime}$$\boldsymbol{x}_{2}^{\prime}$$\lambda\boldsymbol{x}_{1}^{\prime}+(1-\lambda)\boldsymbol{x}_{2}^{\prime}$

Figure 1: An illustration of how two data points, ${\bf x}_{1}$ and ${\bf
x}_{2}$, are transformed in mixup (top) and NFM with $\mathcal{S}:=\\{0\\}$
(bottom).

Data augmentation constitutes a different class of regularization methods [2,
7, 12], which can also be either data-agnostic or data-dependent. Data
augmentation involves training a model with not just the original data, but
also with additional data that is properly transformed, and it has led to
state-of-the-art results in image recognition [9, 37]. The recently-proposed
data-agnostic method, mixup [79], trains a model on linear interpolations of a
random pair of examples and their corresponding labels, thereby encouraging
the model to behave linearly in-between training examples. Both noise
injection and mixup have been shown to impose smoothness and increase model
robustness to data perturbations [80, 6, 43], which is critical for many
safety and sensitive applications [24, 44].

In this paper, we propose and study a simple, inexpensive yet effective data
augmentation method, which we call Noisy Feature Mixup (NFM). This method
combines mixup and noise injection, thereby inheriting the benefits of both
methods, and can be seen as a generalization of input mixup [79] and manifold
mixup [68]. When compared to noise injection and mixup, NFM imposes
regularization on the largest natural region surrounding the dataset (see Fig.
1), which may help improve robustness and generalization when predicting on
out of distribution data. Conveniently, NFM can be implemented on top of
manifold mixup, introducing minimal computation overhead.

#### Contributions.

Our main contributions in this paper are summarized as follows.

  * •

We study NFM via the lens of implicit regularization, showing that NFM
amplifies the regularizing effects of manifold mixup and noise injection,
implicitly reducing the feature-output Jacobians and Hessians according to the
mixing level and noise levels (see Theorem 1).

  * •

We provide mathematical analysis to show that NFM can further improve model
robustness when compared to manifold mixup and noise injection. In particular,
we show that, under appropriate assumptions, NFM training approximately
minimizes an upper bound on the sum of an adversarial loss and feature-
dependent regularizers (see Theorem 2).

  * •

We provide empirical results in support of our theoretical findings, showing
that NFM improves robustness with respect to various forms of data
perturbation across a wide range of state-of-the-art architectures on computer
vision benchmark tasks. Research codes are shared via
https://github.com/erichson/noisy_mixup.

In Supplementary Materials (SM), we provide proofs for our theorems along with
additional theoretical and empirical results to gain more insights into NFM.
In particular, we show that NFM can implicitly increase classification margin
(see Proposition 1 in SM C) and the noise injection procedure in NFM can
robustify manifold mixup in a probabilistic sense (see Theorem 5 in SM D). We
also provide and discuss generalization bounds for NFM (see Theorem 6 and 7 in
SM E).

Notation. $I$ denotes identity matrix, $[K]:=\\{1,\dots,K\\}$, the superscript
T denotes transposition, $\circ$ denotes composition, $\odot$ denotes Hadamard
product, $\mathbb{1}$ denotes the vector with all components equal one. For a
vector $v$, $v^{k}$ denotes its $k$th component and $\|v\|_{p}$ denotes its
$l_{p}$ norm for $p>0$. $conv(\mathcal{X})$ denote the convex hull of
$\mathcal{X}$. $M_{\lambda}(a,b):=\lambda a+(1-\lambda)b$, for random
variables $a,b,\lambda$. $\delta_{z}$ denotes the Dirac delta function,
defined as $\delta_{z}(x)=1$ if $x=z$ and $\delta_{z}(x)=0$ otherwise.
$\mathbb{1}_{A}$ denotes indicator function of the set $A$. For
$\alpha,\beta>0$,
$\tilde{\mathcal{D}}_{\lambda}:=\frac{\alpha}{\alpha+\beta}Beta(\alpha+1,\beta)+\frac{\beta}{\alpha+\beta}Beta(\beta+1,\alpha)$
denotes a uniform mixture of two Beta distributions. For two vectors $a,b$,
$\cos(a,b):=\langle a,b\rangle/\|a\|_{2}\|b\|_{2}$ denotes their cosine
similarity. $\mathcal{N}(a,b)$ is a Gaussian distribution with mean $a$ and
covariance $b$.

##  2 Related Work

Regularization. Regularization refers to any technique that reduces
overfitting in machine learning; see [46, 45] and references therein, in
particular for a discussion of _implicit_ regularization, a topic that has
received attention recently in the context of stochastic gradient optimization
applied to neural network models. Traditional regularization techniques such
as ridge regression, weight decay and dropout do not make use of the training
data to reduce the model capacity. A powerful class of techniques is data
augmentation, which constructs additional examples from the training set,
e.g., by applying geometric transformations to the original data [60]. A
recently proposed technique is mixup [79], where the examples are created by
taking convex combinations of pairs of inputs and their labels. [68] extends
mixup to hidden representations in deep neural networks. Subsequent works by
[26, 75, 18, 34, 76, 31] introduce different variants and extensions of mixup.
Regularization is also intimately connected to robustness [32, 61, 49, 17,
48]. Adding to the list is NFM, a powerful regularization method that we
propose to improve model robustness.

Robustness. Model robustness is an increasingly important issue in modern
machine learning. Robustness with respect to adversarial examples [39] can be
achieved by adversarial training [25, 44, 66]. Several works present
theoretical justifications to observed robustness and how data augmentation
can improve it [30, 74, 10, 51, 52, 80, 81, 6, 35, 11, 71, 23, 8]. Relatedly,
[20, 21, 43] investigate how noise injection can be used to improve
robustness. Parallel to this line of work, we provide theory to understand how
NFM can improve robustness. Also related to this line of work is the study of
the trade-offs between robustness and accuracy [47, 78, 65, 58, 63, 54, 73].
There are also attempts to study generalization in terms of robustness [72,
16, 33].

##  3 Noisy Feature Mixup

Noisy Feature Mixup is a generalization of input mixup [79] and manifold mixup
[68]. The main novelty of NFM against manifold mixup lies in the injection of
noise when taking convex combinations of pairs of input and hidden layer
features. Fig. 1 illustrates, at a high level, how this simple modification
alters the region in which the resulting augmented data resides. Fig. 2 shows
that NFM can be most effective at smoothing the decision boundary of the
trained classifiers; compared to noise injection and mixup alone, it imposes
the strongest smoothness on this dataset.

[5pt]Baseline (85.5%). [5pt]Dropout (87.0%). [5pt]Weight decay (88.0%).
[5pt]Noise injections (87.0%).

[5pt]Mixup (84.5%). [5pt]Manifold mixup (88.5%). [5pt]Noisy mixup (89.0%).
[5pt]NFM (90.0%).

Figure 2: The decision boundaries and test accuracy (in parenthesis) for
different training schemes on a toy dataset in binary classification (see
Subsection F.2 for details).

Formally, we consider multi-class classification with $K$ labels. Denote the
input space by $\mathcal{X}\subset\mathbb{R}^{d}$ and the output space by
$\mathcal{Y}=\mathbb{R}^{K}$. The classifier, $g$, is constructed from a
learnable map $f:\mathcal{X}\to\mathbb{R}^{K}$, mapping an input $x$ to its
label, $g(x)=\arg\max_{k}f^{k}(x)\in[K]$. We are given a training set,
$\mathcal{Z}_{n}:=\\{(x_{i},y_{i})\\}_{i=1}^{n}$, consisting of $n$ pairs of
input and one-hot label, with each training pair
$z_{i}:=(x_{i},y_{i})\in\mathcal{X}\times\mathcal{Y}$ drawn i.i.d. from a
ground-truth distribution $\mathcal{D}$. We consider training a deep neural
network $f:=f_{k}\circ g_{k}$, where $g_{k}:\mathcal{X}\to g_{k}(\mathcal{X})$
maps an input to a hidden representation at layer $k$, and
$f_{k}:g_{k}(\mathcal{X})\to g_{L}(\mathcal{X}):=\mathcal{Y}$ maps the hidden
representation to a one-hot label at layer $L$. Here,
$g_{k}(\mathcal{X})\subset\mathbb{R}^{d_{k}}$ for $k\in[L]$, $d_{L}:=K$,
$g_{0}(x)=x$ and $f_{0}(x)=f(x)$.

Training $f$ using NFM consists of the following steps:

  1. 1.

Select a random layer $k$ from a set, $\mathcal{S}\subset\\{0\\}\cup[L]$, of
eligible layers in the neural network.

  2. 2.

Process two random data minibatches $(x,y)$ and $(x^{\prime},y^{\prime})$ as
usual, until reaching layer $k$. This gives us two immediate minibatches
$(g_{k}(x),y)$ and $(g_{k}(x^{\prime}),y^{\prime})$.

  3. 3.

Perform mixup on these intermediate minibatches, producing the mixed
minibatch:

$(\tilde{g}_{k},\tilde{y}):=(M_{\lambda}(g_{k}(x),g_{k}(x^{\prime})),M_{\lambda}(y,y^{\prime})),$
(1)

where the mixing level $\lambda\sim Beta(\alpha,\beta)$, with the hyper-
parameters $\alpha,\beta>0$.

  4. 4.

Produce noisy mixed minibatch by injecting additive and multiplicative noise:

$\displaystyle(\tilde{\tilde{g}}_{k},\tilde{y})$
$\displaystyle:=((\mathbb{1}+\sigma_{mult}\xi_{k}^{mult})\odot
M_{\lambda}(g_{k}(x),g_{k}(x^{\prime}))+\sigma_{add}\xi_{k}^{add},M_{\lambda}(y,y^{\prime})),$
(2)

where the $\xi_{k}^{add}$ and $\xi_{k}^{mult}$ are $\mathbb{R}^{d_{k}}$-valued
independent random variables modeling the additive and multiplicative noise
respectively, and $\sigma_{add},\sigma_{mult}\geq 0$ are pre-specified noise
levels.

  5. 5.

Continue the forward pass from layer $k$ until the output using the noisy
mixed minibatch $(\tilde{\tilde{g}}_{k},\tilde{y})$.

  6. 6.

Compute the loss and gradients that update all the parameters of the network.

At the level of implementation, following [68], we backpropagate gradients
through the entire computational graph, including those layers before the
mixup layer $k$.

In the case where $\sigma_{add}=\sigma_{mult}=0$, NFM reduces to manifold
mixup [68]. If in addition $\mathcal{S}=\\{0\\}$, it reduces to the original
mixup method [79]. The main difference between NFM and manifold mixup lies in
the noise injection of the fourth step above. Note that NFM is equivalent to
injecting noise into $g_{k}(x),g_{k}(x^{\prime})$ first, then performing mixup
on the resulting pair, i.e., the order that the third and fourth steps occur
does not change the resulting noisy mixed minibatch. For simplicity, we have
used the same mixing level, noise distribution and noise levels for all layers
in $\mathcal{S}$ in our formulation.

Within the above setting, we consider the expected NFM loss:

$L^{NFM}(f)=\mathbb{E}_{(x,y),(x^{\prime},y^{\prime})\sim\mathcal{D}}\mathbb{E}_{k\sim\mathcal{S}}\mathbb{E}_{\lambda\sim
Beta(\alpha,\beta)}\mathbb{E}_{\boldsymbol{\xi}_{k}\sim\mathcal{Q}}l(f_{k}(M_{\lambda,\boldsymbol{\xi}_{k}}(g_{k}(x),g_{k}(x^{\prime}))),M_{\lambda}(y,y^{\prime})),$

where $l:\mathbb{R}^{K}\times\mathbb{R}^{K}\to[0,\infty)$ is a loss function
(note that here we have suppressed the dependence of both $l$ and $f$ on the
learnable parameter $\theta$ in the notation),
$\boldsymbol{\xi}_{k}:=(\xi_{k}^{add},\xi_{k}^{mult})$ are drawn from some
probability distribution $\mathcal{Q}$ with finite first two moments, and

$\displaystyle M_{\lambda,\boldsymbol{\xi}_{k}}(g_{k}(x),g_{k}(x^{\prime}))$
$\displaystyle:=(\mathbb{1}+\sigma_{mult}\xi_{k}^{mult})\odot
M_{\lambda}(g_{k}(x),g_{k}(x^{\prime}))+\sigma_{add}\xi_{k}^{add}.$

NFM seeks to minimize a stochastic approximation of $L^{NFM}(f)$ by sampling a
finite number of $k,\lambda,\boldsymbol{\xi}_{k}$ values and using minibatch
gradient descent to minimize this loss approximation.

##  4 Theory

In this section, we provide mathematical analysis to understand NFM. We begin
with formulating NFM in the framework of vicinal risk minimization and
interpreting NFM as a stochastic learning strategy in Subsection 4.1. Next, we
study NFM via the lens of implicit regularization in Subsection 4.2. Our key
contribution is Theorem 1, which shows that minimizing the NFM loss function
is approximately equivalent to minimizing a sum of the original loss and
feature-dependent regularizers, amplifying the regularizing effects of
manifold mixup and noise injection according to the mixing and noise levels.
In Subsection 4.3, we focus on demonstrating how NFM can enhance model
robustness via the lens of distributionally robust optimization. The key
result of Theorem 2 shows that NFM loss is approximately the upper bound on a
regularized version of an adversarial loss, and thus training with NFM not
only improves robustness but can also mitigate robust over-fitting, a dominant
phenomenon where the robust test accuracy starts to decrease during training
[57].

###  4.1 NFM: Beyond Empirical Risk Minimization

The standard approach in statistical learning theory [4] is to select a
hypothesis function $f:\mathcal{X}\to\mathcal{Y}$ from a pre-defined
hypothesis class $\mathcal{F}$ to minimize the expected risk with respect to
$\mathcal{D}$ and to solve the risk minimization problem:
$\inf_{f\in\mathcal{F}}\mathcal{R}(f):=\mathbb{E}_{(x,y)\sim\mathcal{D}}[l(f(x),y)]$,
for a suitable choice of loss function $l$. In practice, we do not have access
to the ground-truth distribution. Instead, we find an approximate solution by
solving the empirical risk minimization (ERM) problem, in which case
$\mathcal{D}$ is approximated by the empirical distribution
$\mathbb{P}_{n}=\frac{1}{n}\sum_{i=1}^{n}\delta_{z_{i}}$. In other words, in
ERM we solve the problem:
$\inf_{f\in\mathcal{F}}\mathcal{R}_{n}(f):=\frac{1}{n}\sum_{i=1}^{n}l(f(x_{i}),y_{i})$.

However, when the training set is small or the model capacity is large (as is
the case for deep neural networks), ERM may suffer from overfitting. Vicinal
risk minimization (VRM) is a data augmentation principle introduced in [67]
that goes beyond ERM, aiming to better estimate expected risk and reduce
overfitting. In VRM, a model is trained not simply on the training set, but on
samples drawn from a vicinal distribution, that smears the training data to
their vicinity. With appropriate choices for this distribution, the VRM
approach has resulted in several effective regularization schemes [7].

Input mixup [79] can be viewed as an example of VRM, and it turns out that NFM
can be constructed within a VRM framework at the feature level (see Section A
in SM). On a high level, NFM can be interpreted as a random procedure that
introduces feature-dependent noise into the layers of the deep neural network.
Since the noise injections are applied only during training and not inference,
NFM is an instance of a stochastic learning strategy. Note that the injection
strategy of NFM differs from those of [1, 5, 43]. Here, the structure of the
injected noise differs from iteration to iteration (based on the layer chosen)
and depends on the training data in a different way. We expect NFM to amplify
the benefits of training using either noise injection or mixup alone, as will
be shown next.

###  4.2 Implicit Regularization of NFM

We consider loss functions of the form $l(f(x),y):=h(f(x))-yf(x)$, which
includes standard choices such as the logistic loss and the cross-entropy
loss, and recall that $f:=f_{k}\circ g_{k}$. Denote
$L_{n}^{std}:=\frac{1}{n}\sum_{i=1}^{n}l(f(x_{i}),y_{i})$ and let
$\mathcal{D}_{x}$ be the empirical distribution of training samples
$\\{x_{i}\\}_{i\in[n]}$. We shall show that NFM exhibits a natural form of
implicit regularization, i.e., regularization imposed implicitly by the
stochastic learning strategy or approximation algorithm, without explicitly
modifying the loss.

Let $\epsilon>0$ be a small parameter. In the sequel, we rescale
$1-\lambda\mapsto\epsilon(1-\lambda)$,
$\sigma_{add}\mapsto\epsilon\sigma_{add}$,
$\sigma_{mult}\mapsto\epsilon\sigma_{mult}$, and denote $\nabla_{k}f$ and
$\nabla_{k}^{2}f$ as the first and second directional derivative of $f_{k}$
with respect to $g_{k}$ respectively, for $k\in\mathcal{S}$. By working in the
small parameter regime, we can relate the NFM empirical loss $L_{n}^{NFM}$ to
the original loss $L_{n}^{std}$ and identify the regularizing effects of NFM.

######  Theorem 1.

Let $\epsilon>0$ be a small parameter, and assume that $h$ and $f$ are twice
differentiable. Then,
$L^{NFM}_{n}=\mathbb{E}_{k\sim\mathcal{S}}L^{NFM(k)}_{n}$, where

$L^{NFM(k)}_{n}=L_{n}^{std}+\epsilon
R_{1}^{(k)}+\epsilon^{2}\tilde{R}_{2}^{(k)}+\epsilon^{2}\tilde{R}_{3}^{(k)}+\epsilon^{2}\varphi(\epsilon),$
(3)

with
$\tilde{R}_{2}^{(k)}=R_{2}^{(k)}+\sigma_{add}^{2}R_{2}^{add(k)}+\sigma_{mult}^{2}R_{2}^{mult(k)}$
and
$\tilde{R}_{3}^{(k)}=R_{3}^{(k)}+\sigma_{add}^{2}R_{3}^{add(k)}+\sigma_{mult}^{2}R_{3}^{mult(k)}$,
where

$\displaystyle R_{2}^{add(k)}$
$\displaystyle=\frac{1}{2n}\sum_{i=1}^{n}h^{\prime\prime}(f(x_{i}))\nabla_{k}f(g_{k}(x_{i}))^{T}\mathbb{E}_{\boldsymbol{\xi}_{k}}[\xi_{k}^{add}(\xi_{k}^{add})^{T}]\nabla_{k}f(g_{k}(x_{i})),$
(4) $\displaystyle R_{2}^{mult(k)}$
$\displaystyle=\frac{1}{2n}\sum_{i=1}^{n}h^{\prime\prime}(f(x_{i}))\nabla_{k}f(g_{k}(x_{i}))^{T}(\mathbb{E}_{\boldsymbol{\xi}_{k}}[\xi_{k}^{add}(\xi_{k}^{add})^{T}]\odot
g_{k}(x_{i})g_{k}(x_{i})^{T})\nabla_{k}f(g_{k}(x_{i})),$ (5) $\displaystyle
R_{3}^{add(k)}$
$\displaystyle=\frac{1}{2n}\sum_{i=1}^{n}(h^{\prime}(f(x_{i}))-y_{i})\mathbb{E}_{\boldsymbol{\xi}_{k}}[(\xi_{k}^{add})^{T}\nabla_{k}^{2}f(g_{k}(x_{i}))\xi_{k}^{add}],$
(6) $\displaystyle R_{3}^{mult(k)}$
$\displaystyle=\frac{1}{2n}\sum_{i=1}^{n}(h^{\prime}(f(x_{i}))-y_{i})\mathbb{E}_{\boldsymbol{\xi}_{k}}[(\xi_{k}^{mult}\odot
g_{k}(x_{i}))^{T}\nabla_{k}^{2}f(g_{k}(x_{i}))(\xi_{k}^{mult}\odot
g_{k}(x_{i}))].$ (7)

Here, $R_{1}^{{k}}$, $R_{2}^{{k}}$ and $R_{3}^{{k}}$ are the regularizers
associated with the loss of manifold mixup (see Theorem 3 in SM for their
explicit expression), and $\varphi$ is some function such that
$\lim_{\epsilon\to 0}\varphi(\epsilon)=0$.

Theorem 1 implies that, when compared to manifold mixup, NFM introduces
additional smoothness, regularizing the directional derivatives,
$\nabla_{k}f(g_{k}(x_{i}))$ and $\nabla_{k}^{2}f(g_{k}(x_{i}))$, with respect
to $g_{k}(x_{i})$, according to the noise levels $\sigma_{add}$ and
$\sigma_{mult}$, and amplifying the regularizing effects of manifold mixup and
noise injection. In particular, making $\nabla^{2}f(x_{i})$ small can lead to
smooth decision boundaries (at the input level), while reducing the confidence
of model predictions. On the other hand, making the
$\nabla_{k}f(g_{k}(x_{i}))$ small can lead to improvement in model robustness,
which we discuss next.

###  4.3 Robustness of NFM

We show that NFM improves model robustness. We do this by considering the
following three lenses: (1) implicit regularization and classification margin;
(2) distributionally robust optimization; and (3) a probabilistic notion of
robustness. We focus on (2) in the main paper. See Section C-D in SM and the
last paragraph in this subsection for details on (1) and (3).

We now demonstrate how NFM helps adversarial robustness. By extending the
analysis of [79, 41], we can relate the NFM loss function to the one used for
adversarial training, which can be viewed as an instance of distributionally
robust optimization (DRO) [40, 38, 55] (see also Proposition 3.1 in [62]). DRO
provides a framework for local worst-case risk minimization, minimizing
supremum of the risk in an ambiguity set, such as in the vicinity of the
empirical data distribution.

Following [41], we consider the binary cross-entropy loss, setting
$h(z)=\log(1+e^{z})$, with the labels $y$ taking value in $\\{0,1\\}$ and the
classifier model $f:\mathbb{R}^{d}\to\mathbb{R}$. In the following, we assume
that the model parameter
$\theta\in\Theta:=\\{\theta:y_{i}f(x_{i})+(y_{i}-1)f(x_{i})\geq 0\text{ for
all }i\in[n]\\}$. Note that this set contains the set of all parameters with
correct classifications of training samples (before applying NFM), since
$\\{\theta:1_{\\{f(x_{i})\geq 0\\}}=y_{i}\text{ for all
}i\in[n]\\}\subset\Theta$. Therefore, the condition of $\theta\in\Theta$ is
satisfied when the model classifies all labels correctly for the training data
before applying NFM. Since, in practice, the training error often becomes zero
in finite time, we study the effect of NFM on model robustness in the regime
of $\theta\in\Theta$.

Working in the data-dependent parameter space $\Theta$, we have the following
result.

######  Theorem 2.

Let $\theta\in\Theta:=\\{\theta:y_{i}f(x_{i})+(y_{i}-1)f(x_{i})\geq 0\text{
for all }i\in[n]\\}$ such that $\nabla_{k}f(g_{k}(x_{i}))$ and
$\nabla_{k}^{2}f(g_{k}(x_{i}))$ exist for all $i\in[n]$, $k\in\mathcal{S}$.
Assume that $f_{k}(g_{k}(x_{i}))=\nabla_{k}f(g_{k}(x_{i}))^{T}g_{k}(x_{i})$,
$\nabla_{k}^{2}f(g_{k}(x_{i}))=0$ for all $i\in[n]$, $k\in\mathcal{S}$. In
addition, suppose that $\|\nabla f(x_{i})\|_{2}>0$ for all $i\in[n]$,
$\mathbb{E}_{r\sim\mathcal{D}_{x}}[g_{k}(r)]=0$ and $\|g_{k}(x_{i})\|_{2}\geq
c_{x}^{(k)}\sqrt{d_{k}}$ for all $i\in[n]$, $k\in\mathcal{S}$. Then,

$\displaystyle
L_{n}^{NFM}\geq\frac{1}{n}\sum_{i=1}^{n}\max_{\|\delta_{i}\|_{2}\leq\epsilon_{i}^{mix}}l(f(x_{i}+\delta_{i}),y_{i})+L_{n}^{reg}+\epsilon^{2}\phi(\epsilon),$
(8)

where

$\displaystyle\epsilon_{i}^{mix}$
$\displaystyle:=\epsilon\mathbb{E}_{\lambda\sim\tilde{\mathcal{D}}_{\lambda}}[1-\lambda]\cdot\mathbb{E}_{k\sim\mathcal{S}}\left[r_{i}^{(k)}c_{x}^{(k)}\frac{\|\nabla_{k}f(g_{k}(x_{i}))\|_{2}}{\|\nabla
f(x_{i})\|_{2}}\sqrt{d_{k}}\right]$ (9)

and

$L_{n}^{reg}:=\frac{1}{2n}\sum_{i=1}^{n}|h^{\prime\prime}(f(x_{i}))|(\epsilon_{i}^{reg})^{2},$
(10)

with $r_{i}^{(k)}:=|\cos(\nabla_{k}f(g_{k}(x_{i})),g_{k}(x_{i}))|$ and

$\displaystyle(\epsilon_{i}^{reg})^{2}$
$\displaystyle:=\epsilon^{2}\|\nabla_{k}f(g_{k}(x_{i}))\|_{2}^{2}\bigg{(}\mathbb{E}_{\lambda}[(1-\lambda)]^{2}\mathbb{E}_{x_{r}}[\|g_{k}(x_{r})\|_{2}^{2}\cos(\nabla_{k}f(g_{k}(x_{i})),g_{k}(x_{r}))^{2}]$
$\displaystyle\hskip
19.91684pt+\sigma_{add}^{2}\mathbb{E}_{\boldsymbol{\xi}_{k}}[\|\xi_{k}^{add}\|_{2}^{2}\cos(\nabla_{k}f(g_{k}(x_{i})),\xi_{k}^{add})^{2}]$
$\displaystyle\hskip
19.91684pt+\sigma_{mult}^{2}\mathbb{E}_{\boldsymbol{\xi}_{k}}[\|\xi_{k}^{mult}\odot
g_{k}(x_{i})\|_{2}^{2}\cos(\nabla_{k}f(g_{k}(x_{i})),\xi_{k}^{mult}\odot
g_{k}(x_{i}))^{2}]\bigg{)},$ (11)

and $\phi$ is some function such that $\lim_{\epsilon\to 0}\phi(\epsilon)=0$.

The second assumption stated in Theorem 2 is similar to the one made in [41,
80], and is satisfied by linear models and deep neural networks with ReLU
activation function and max-pooling. Theorem 2 shows that the NFM loss is
approximately an upper bound of the adversarial loss with $l_{2}$ attack of
size $\epsilon^{mix}=\min_{i\in[n]}\epsilon^{mix}_{i}$, plus a feature-
dependent regularization term $L_{n}^{reg}$. Therefore, we see that minimizing
the NFM loss not only results in a small adversarial loss, while retaining the
robustness benefits of manifold mixup, but it also imposes additional
smoothness (due to noise injection) on the adversarial loss. The latter can
help mitigate robust overfitting and improve test performance [57, 56]. This
offers a plausible explanation for the remarkable performance of NFM (see next
section).

NFM can also implicitly increase the classification margin (see Section C of
SM). Moreover, since the main novelty of NFM lies in the introduction of noise
injection, it would be insightful to isolate the robustness boosting benefits
of injecting noise on top of manifold mixup. We demonstrate these advantages
via the lens of probabilistic robustness in Section D of SM.

##  5 Empirical Results

In this section, we study the test performance of models trained with NFM, and
examine to what extent NFM can improve robustness to input perturbations. We
demonstrate the tradeoff between predictive accuracy on clean and perturbed
test sets. We consider input perturbations that are common in the literature:
(a) white noise; (b) salt and pepper; and (c) adversarial perturbations (see
Subsection F.1 for details).

We evaluate the average performance of NFM with different model architectures
on CIFAR-10 [36], CIFAR-100 [36], and ImageNet [13]. We use a pre-activated
residual network (ResNet) with depth 18 [29] and a compact vision transformer
(ViT-lite) with 7 attention layers and 4 heads [28] on small scale tasks. For
more challenging and higher dimensional tasks, we consider the performance of
wide ResNet-18 [77] and ResNet-50 architectures, respectively.

Baselines. We evaluate against related data augmentation schemes that have
shown performance improvements in recent years: mixup [79]; manifold mixup
[68]; and noisy mixup [74]. Further, we compare to both vanilla models trained
without data augmentation (baseline) and those trained on white noise
perturbed inputs.

Experimental details. All hyperparameters are consistent with those of the
baseline model across the ablation experiments. In the models trained on the
different data augmentation schemes, we vary only $\alpha$, i.e., the
parameter defining $Beta(\alpha,\alpha)$, from which the $\lambda$ parameter
controlling the convex combination between data point pairs is sampled.
Appropriately, we compare all methods varying $\alpha$ according to previous
works [68, 74]. Across all models trained with NFM, we control the level of
noise injections by fixing the additive noise level to $\sigma_{add}=0.4$ and
multiplicative noise to $\sigma_{mult}=0.2$. To demonstrate the significant
improvements on robustness upon the introduction of these small input
perturbations, we compare against an ablation model (‘*’) that was injected
with higher noise levels (i.e., $\sigma_{add}=1.0$, $\sigma_{mult}=0.5$). See
SM (Section F.4) for further details and comparisons against NFM models
trained on various other levels of noise injections.

Research code is provided here: https://github.com/erichson/noisy_mixup.

\begin{overpic}[width=433.62pt]{figures/cifar10_white.pdf}
\put(-6.0,16.0){\rotatebox{90.0}{ Test Accuracy}} \put(31.0,-3.0){ {White
Noise ($\sigma$)}} \end{overpic}

\begin{overpic}[width=433.62pt]{figures/cifar10_sp.pdf} \put(31.0,-3.0){ {Salt
and Pepper Noise ($\gamma$)}} \end{overpic}

Figure 3: Pre-actived ResNet-18 evaluated on CIFAR-10 with different training
schemes. Shaded regions indicate one standard deviation about the mean.
Averaged across 5 random seeds. Table 1: Robustness of ResNet-18 w.r.t. white
noise ($\sigma$) and salt and pepper ($\gamma$) perturbations evaluated on
CIFAR-10. The results are averaged over 5 models trained with different seed
values.

Scheme | Clean (%) |  $\sigma$ (%) |  $\gamma$ (%)
---|---|---|---
|  | $0.1$ | $0.2$ | $0.3$ | $0.02$ | $0.04$ | $0.1$
Baseline | 94.6 | 90.4 | 76.7 | 56.3 | 86.3 | 76.1 | 55.2
Baseline + Noise | 94.4 | 94.0 | 87.5 | 71.2 | 89.3 | 82.5 | 64.9
Mixup ($\alpha=1.0$) [79] | 95.6 | 93.2 | 85.4 | 71.8 | 87.1 | 76.1 | 55.2
Noisy Mixup ($\alpha=1.0$) [74] | 78.9 | 78.6 | 66.6 | 46.7 | 66.6 | 53.4 | 25.9
Manifold Mixup ($\alpha=0.2$) [68] | 95.5 | 93.0 | 82.5 | 65.5 | 87.5 | 77.1 | 53.9
Manifold Mixup ($\alpha=1.0$) [68] | 95.7 | 92.7 | 82.7 | 67.6 | 88.9 | 80.2 | 57.6
Manifold Mixup ($\alpha=2.0$) [68] | 95.6 | 92.6 | 81.8 | 64.5 | 89.2 | 80.7 | 58.2
Noisy Feature Mixup ($\alpha=0.2$) | 95.4 | 94.7 | 90.2 | 78.7 | 92.2 | 88.2 | 74.4
Noisy Feature Mixup ($\alpha=1.0$) | 95.4 | 95.0 | 91.6 | 83.0 | 91.9 | 87.4 | 73.3
Noisy Feature Mixup ($\alpha=2.0$) | 95.3 | 94.9 | 91.3 | 82.4 | 91.3 | 85.9 | 69.7

###  5.1 CIFAR10

Pre-activated ResNet-18. Table 1 summarizes the performance improvements and
indicates a consistent robustness across different $\alpha$ values. The model
trained with NFM outperforms the baseline model on the clean test set, while
being more robust to input perturbations (Fig. 3; left). This advantage is
also displayed in the models trained with mixup and manifold mixup, though in
a less pronounced way. Notably, the NFM model is also robust to salt and
pepper perturbations and could be significantly more so by further increasing
the noise levels (Fig. 3; right).

Vision Transformer (ViT-7/4). Fig. 4 (left) compares vision transformers
trained with different data augmentation strategies. Again, NFM improves the
robustness of the models while achieving state-of-the-art accuracy when
evaluated on clean data. However, mixup and manifold mixup do not boost the
robustness. Further, Fig. 4 (right) shows that that the vision transformer is
less sensitive to salt and pepper perturbations as compared to the ResNet
model. These results are consistent with the high robustness properties of
transformers recently reported in [59, 50]. Table 4 provides additional
results for different $\alpha$ values.

\begin{overpic}[width=433.62pt]{figures/cifar10_vit_white.pdf}
\put(-6.0,16.0){\rotatebox{90.0}{ Test Accuracy}} \put(31.0,-3.0){ {White
Noise ($\sigma$)}} \end{overpic}

\begin{overpic}[width=433.62pt]{figures/cifar10_vit_sp.pdf} \put(31.0,-3.0){
{Salt and Pepper Noise ($\gamma$)}} \end{overpic}

Figure 4: Vision transformers evaluated on CIFAR-10 with different training
schemes.

\begin{overpic}[width=433.62pt]{figures/cifar100_white.pdf}
\put(-6.0,16.0){\rotatebox{90.0}{ Test Accuracy}} \put(31.0,-3.0){ {White
Noise ($\sigma$)}} \end{overpic}

\begin{overpic}[width=433.62pt]{figures/cifar100_sp.pdf} \put(31.0,-3.0){
{Salt and Pepper Noise ($\gamma$)}} \end{overpic}

Figure 5: Wide ResNets evaluated on CIFAR-100. Averaged across 5 random seeds.

###  5.2 CIFAR-100

Wide ResNet-18. Previous work indicates that data augmentation has a positive
effect on performance for this dataset [79]. Fig. 5 (left) confirms that mixup
and manifold mixup improve the generalization performance on clean data and
highlights the advantage of data augmentation. The NFM training scheme is also
capable of further improving the generalization performance. In addition, we
see that the model trained with NFM is less sensitive to both white noise and
salt and pepper perturbations. These results are surprising, as robustness is
often thought to be at odds with accuracy [65]. However, we demonstrate NFM
has the ability to improve both accuracy and robustness. Table 2 indicates
that for the same $\alpha$, NFM can achieve an average test accuracy of
$80.9\%$ compared to only $80.3\%$ in the mixup setting.

###  5.3 ImageNet

ResNet-50. Table 3 similarly shows that NFM improves both the generalization
and robustness capacities with respect to data perturbations. Although less
pronounced in comparison to previous datasets, NFM shows a favorable trade-off
without requiring additional computational resources. Note that due to
computational costs, we do not average across multiple seeds and only compare
NFM to the baseline and manifold mixup models.

Table 2: Robustness of Wide-ResNet-18 w.r.t. white noise ($\sigma$) and salt
and pepper ($\gamma$) perturbations evaluated on CIFAR-100. The results are
averaged over 5 models trained with different seed values.

Scheme | Clean (%) |  $\sigma$ (%) |  $\gamma$ (%)
---|---|---|---
|  | $0.1$ | $0.2$ | $0.3$ | $0.02$ | $0.04$ | $0.1$
Baseline | 76.9 | 64.6 | 42.0 | 23.5 | 58.1 | 39.8 | 15.1
Baseline + Noise | 76.1 | 75.2 | 60.5 | 37.6 | 64.9 | 51.3 | 23.0
Mixup ($\alpha=1.0$) [79] | 80.3 | 72.5 | 54.0 | 33.4 | 62.5 | 43.8 | 16.2
Noisy Mixup ($\alpha=1.0$) [74] | 78.9 | 78.6 | 66.6 | 46.7 | 66.6 | 53.4 | 25.9
Manifold Mixup ($\alpha=0.2$) [68] | 79.7 | 70.6 | 46.6 | 25.3 | 62.1 | 43.0 | 15.2
Manifold Mixup ($\alpha=1.0$) [68] | 79.7 | 70.5 | 45.0 | 23.8 | 62.1 | 42.8 | 14.8
Manifold Mixup ($\alpha=2.0$) [68] | 79.2 | 69.3 | 43.8 | 23.0 | 62.8 | 44.2 | 16.0
Noisy Feature Mixup ($\alpha=0.2$) | 80.6 | 79.2 | 70.2 | 51.7 | 71.5 | 60.4 | 30.3
Noisy Feature Mixup ($\alpha=1.0$) | 80.9 | 80.1 | 72.1 | 55.3 | 72.8 | 62.1 | 34.4
Noisy Feature Mixup ($\alpha=2.0$) | 80.7 | 80.0 | 71.5 | 53.9 | 72.7 | 62.7 | 36.6

Table 3: Robustness of ResNet-50 w.r.t. white noise ($\sigma$) and salt and
pepper ($\gamma$) perturbations evaluated on ImageNet. Here, the NFM training
scheme improves both the predictive accuracy on clean data and robustness with
respect to data perturbations.

Scheme | Clean (%) |  $\sigma$ (%) |  $\gamma$ (%)
---|---|---|---
|  | $0.1$ | $0.25$ | $0.5$ | $0.06$ | $0.1$ | $0.15$
Baseline | 76.0 | 73.5 | 67.0 | 50.1 | 53.2 | 50.4 | 45.0
Manifold Mixup ($\alpha=0.2$) [68] | 76.7 | 74.9 | 70.3 | 57.5 | 58.1 | 54.6 | 49.5
Noisy Feature Mixup ($\alpha=0.2$) | 77.0 | 76.5 | 72.0 | 60.1 | 58.3 | 56.0 | 52.3
Noisy Feature Mixup ($\alpha=1.0$) | 76.8 | 76.2 | 71.7 | 60.0 | 60.9 | 58.8 | 54.4

###  5.4 Robustness to Adversarial Examples

So far we have only considered white noise and salt and pepper perturbations.
We further consider adversarial perturbations. Here, we use projected gradient
decent [44] with $7$ iterations and various $\epsilon$ levels to construct the
adversarial perturbations. Fig. 6 highlights the improved resilience of
ResNets trained with NFM to adversarial input perturbations. Fig. 6 shows
results for CIFAR-10 (left) and CIFAR-100 (right). Models trained with both
mixup and manifold mixup do not show a substantially increased resilience to
adversarial perturbations.

In Section F.5, we compare NFM to models that are adversarially trained
models. There we see that adversarially trained models are indeed more robust
to adversarial attacks, while at the same time being less accurate on clean
data. However, models trained with NFM show an advantage compared to
adversarially trained models when faced with salt and pepper perturbations.

\begin{overpic}[width=433.62pt]{figures/cifar10_pgd.pdf}
\put(-6.0,16.0){\rotatebox{90.0}{ Test Accuracy}} \put(31.0,-3.0){
{Adverserial Noise ($\epsilon$)}} \end{overpic}

\begin{overpic}[width=433.62pt]{figures/cifar100_pgd.pdf} \put(31.0,-3.0){
{Adverserial Noise ($\epsilon$)}} \end{overpic}

Figure 6: Pre-actived ResNet-18 evaluated on CIFAR-10 (left) and Wide
ResNet-18 evaluated on CIFAR-100 (right) with respect to adversarially
perturbed inputs. Shaded regions indicate one standard deviation about the
mean. Averaged across 5 random seeds.

##  6 Conclusion

We introduce Noisy Feature Mixup, an effective data augmentation method that
combines mixup and noise injection. We identify the implicit regularization
effects of NFM, showing that the effects are amplifications of those of
manifold mixup and noise injection. Moreover, we demonstrate the benefits of
NFM in terms of superior model robustness, both theoretically and
experimentally. Our work inspires a range of interesting future directions,
including theoretical investigations of the trade-offs between accuracy and
robustness for NFM and applications of NFM beyond computer vision tasks.
Further, it will be interesting to study whether NFM may also lead to better
model calibration by extending the analysis of [64, 81].

## Acknowledgements

S. H. Lim would like to acknowledge the WINQ Fellowship and the Knut and Alice
Wallenberg Foundation for providing support of this work. N. B. Erichson and
M. W. Mahoney would like to acknowledge IARPA (contract W911NF20C0035), NSF,
and ONR for providing partial support of this work. Our conclusions do not
necessarily reflect the position or the policy of our sponsors, and no
official endorsement should be inferred. We are also grateful for the generous
support from Amazon AWS.

## References

  * [1] Guozhong An.  The effects of adding noise during backpropagation training on a generalization performance.  Neural Computation, 8(3):643–674, 1996.
  * [2] Henry S Baird.  Document image defect models.  In Structured Document Image Analysis, pages 546–556. Springer, 1992.
  * [3] Chris M Bishop.  Training with noise is equivalent to Tikhonov regularization.  Neural Computation, 7(1):108–116, 1995.
  * [4] Olivier Bousquet, Stéphane Boucheron, and Gábor Lugosi.  Introduction to statistical learning theory.  In Summer school on machine learning, pages 169–207. Springer, 2003\.
  * [5] Alexander Camuto, Matthew Willetts, Umut Şimşekli, Stephen Roberts, and Chris Holmes.  Explicit regularisation in Gaussian noise injections.  arXiv preprint arXiv:2007.07368, 2020.
  * [6] Luigi Carratino, Moustapha Cissé, Rodolphe Jenatton, and Jean-Philippe Vert.  On mixup regularization.  arXiv preprint arXiv:2006.06049, 2020.
  * [7] Olivier Chapelle, Jason Weston, Léon Bottou, and Vladimir Vapnik.  Vicinal risk minimization.  Advances in Neural Information Processing Systems, pages 416–422, 2001.
  * [8] Shuxiao Chen, Edgar Dobriban, and Jane H Lee.  A group-theoretic framework for data augmentation.  Journal of Machine Learning Research, 21(245):1–71, 2020.
  * [9] Dan Claudiu Cireşan, Ueli Meier, Luca Maria Gambardella, and Jürgen Schmidhuber.  Deep, big, simple neural nets for handwritten digit recognition.  Neural Computation, 22(12):3207–3220, 2010.
  * [10] Nicolas Couellan.  Probabilistic robustness estimates for feed-forward neural networks.  Neural Networks, 142:138–147, 2021.
  * [11] Tri Dao, Albert Gu, Alexander Ratner, Virginia Smith, Chris De Sa, and Christopher Ré.  A kernel theory of modern data augmentation.  In International Conference on Machine Learning, pages 1528–1537. PMLR, 2019.
  * [12] Dennis DeCoste and Bernhard Schölkopf.  Training invariant support vector machines.  Machine Learning, 46(1):161–190, 2002.
  * [13] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei.  Imagenet: A large-scale hierarchical image database.  In 2009 IEEE Conference on Computer Vision and Pattern Recognition, pages 248–255. Ieee, 2009.
  * [14] Luc Devroye, Abbas Mehrabian, and Tommy Reddad.  The total variation distance between high-dimensional Gaussians.  arXiv preprint arXiv:1810.08693, 2018.
  * [15] Cynthia Dwork, Aaron Roth, et al.  The algorithmic foundations of differential privacy.  Found. Trends Theor. Comput. Sci., 9(3-4):211–407, 2014.
  * [16] Gintare Karolina Dziugaite, Alexandre Drouin, Brady Neal, Nitarshan Rajkumar, Ethan Caballero, Linbo Wang, Ioannis Mitliagkas, and Daniel M Roy.  In search of robust measures of generalization.  arXiv preprint arXiv:2010.11924, 2020.
  * [17] Gamaleldin F Elsayed, Dilip Krishnan, Hossein Mobahi, Kevin Regan, and Samy Bengio.  Large margin deep networks for classification.  arXiv preprint arXiv:1803.05598, 2018.
  * [18] Logan Engstrom, Justin Gilmer, Gabriel Goh, Dan Hendrycks, Andrew Ilyas, Aleksander Madry, Reiichiro Nakano, Preetum Nakkiran, Shibani Santurkar, Brandon Tran, Dimitris Tsipras, and Eric Wallace.  A discussion of ’adversarial examples are not bugs, they are features’.  Distill, 2019.
  * [19] Logan Engstrom, Andrew Ilyas, Shibani Santurkar, Dimitris Tsipras, Brandon Tran, and Aleksander Madry.  Adversarial robustness as a prior for learned representations.  ArXiv preprint arXiv:1906.00945, 2020.
  * [20] Alhussein Fawzi, Seyed-Mohsen Moosavi-Dezfooli, and Pascal Frossard.  Robustness of classifiers: from adversarial to random noise.  arXiv preprint arXiv:1608.08967, 2016.
  * [21] Jean-Yves Franceschi, Alhussein Fawzi, and Omar Fawzi.  Robustness of classifiers to uniform $l_{p}$ and Gaussian noise.  In International Conference on Artificial Intelligence and Statistics, pages 1280–1288. PMLR, 2018.
  * [22] Alison L Gibbs and Francis Edward Su.  On choosing and bounding probability metrics.  International Statistical Review, 70(3):419–435, 2002.
  * [23] Chengyue Gong, Tongzheng Ren, Mao Ye, and Qiang Liu.  Maxup: A simple way to improve generalization of neural network training.  arXiv preprint arXiv:2002.09024, 2020.
  * [24] Ian Goodfellow, Patrick McDaniel, and Nicolas Papernot.  Making machine learning robust against adversarial inputs.  Communications of the ACM, 61(7):56–66, 2018.
  * [25] Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy.  Explaining and harnessing adversarial examples.  arXiv preprint arXiv:1412.6572, 2014.
  * [26] Kristjan Greenewald, Anming Gu, Mikhail Yurochkin, Justin Solomon, and Edward Chien.  k-mixup regularization for deep learning via optimal transport.  arXiv preprint arXiv:2106.02933, 2021.
  * [27] Caglar Gulcehre, Marcin Moczulski, Misha Denil, and Yoshua Bengio.  Noisy activation functions.  In International Conference on Machine Learning, pages 3059–3068. PMLR, 2016.
  * [28] Ali Hassani, Steven Walton, Nikhil Shah, Abulikemu Abuduweili, Jiachen Li, and Humphrey Shi.  Escaping the big data paradigm with compact transformers.  arXiv preprint arXiv:2104.05704, 2021.
  * [29] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Identity mappings in deep residual networks.  In European Conference on Computer Vision, pages 630–645. Springer, 2016.
  * [30] Matthias Hein and Maksym Andriushchenko.  Formal guarantees on the robustness of a classifier against adversarial manipulation.  arXiv preprint arXiv:1705.08475, 2017.
  * [31] Dan Hendrycks, Norman Mu, Ekin D Cubuk, Barret Zoph, Justin Gilmer, and Balaji Lakshminarayanan.  Augmix: A simple data processing method to improve robustness and uncertainty.  arXiv preprint arXiv:1912.02781, 2019.
  * [32] Judy Hoffman, Daniel A Roberts, and Sho Yaida.  Robust learning with Jacobian regularization.  arXiv preprint arXiv:1908.02729, 2019.
  * [33] Yiding Jiang, Dilip Krishnan, Hossein Mobahi, and Samy Bengio.  Predicting the generalization gap in deep networks with margin distributions.  arXiv preprint arXiv:1810.00113, 2018.
  * [34] Jang-Hyun Kim, Wonho Choo, and Hyun Oh Song.  Puzzle mix: Exploiting saliency and local statistics for optimal mixup.  In International Conference on Machine Learning, pages 5275–5285. PMLR, 2020.
  * [35] Masanari Kimura.  Mixup training as the complexity reduction.  arXiv preprint arXiv:2006.06231, 2020.
  * [36] Alex Krizhevsky.  Learning multiple layers of features from tiny images.  Technical Report, 2009.
  * [37] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton.  Imagenet classification with deep convolutional neural networks.  Advances in Neural Information Processing Systems, 25:1097–1105, 2012.
  * [38] Daniel Kuhn, Peyman Mohajerin Esfahani, Viet Anh Nguyen, and Soroosh Shafieezadeh-Abadeh.  Wasserstein distributionally robust optimization: Theory and applications in machine learning.  In Operations Research & Management Science in the Age of Analytics, pages 130–166. INFORMS, 2019.
  * [39] Alexey Kurakin, Ian Goodfellow, Samy Bengio, et al.  Adversarial examples in the physical world, 2016.
  * [40] Yongchan Kwon, Wonyoung Kim, Joong-Ho Won, and Myunghee Cho Paik.  Principled learning method for Wasserstein distributionally robust optimization with local perturbations.  In International Conference on Machine Learning, pages 5567–5576. PMLR, 2020.
  * [41] Alex Lamb, Vikas Verma, Juho Kannala, and Yoshua Bengio.  Interpolated adversarial training: Achieving robust neural networks without sacrificing too much accuracy.  In Proceedings of the 12th ACM Workshop on Artificial Intelligence and Security, pages 95–103, 2019.
  * [42] Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana.  Certified robustness to adversarial examples with differential privacy.  In 2019 IEEE Symposium on Security and Privacy (SP), pages 656–672. IEEE, 2019.
  * [43] Soon Hoe Lim, N Benjamin Erichson, Liam Hodgkinson, and Michael W Mahoney.  Noisy recurrent neural networks.  arXiv preprint arXiv:2102.04877, 2021.
  * [44] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu.  Towards deep learning models resistant to adversarial attacks.  arXiv preprint arXiv:1706.06083, 2017.
  * [45] M. W. Mahoney.  Approximate computation and implicit regularization for very large-scale data analysis.  In Proceedings of the 31st ACM Symposium on Principles of Database Systems, pages 143–154, 2012.
  * [46] M. W. Mahoney and L. Orecchia.  Implementing regularization implicitly via approximate eigenvector computation.  In Proceedings of the 28th International Conference on Machine Learning, pages 121–128, 2011.
  * [47] Yifei Min, Lin Chen, and Amin Karbasi.  The curious case of adversarially robust models: More data can help, double descend, or hurt generalization.  arXiv preprint arXiv:2002.11080, 2020.
  * [48] Seyed-Mohsen Moosavi-Dezfooli, Alhussein Fawzi, Jonathan Uesato, and Pascal Frossard.  Robustness via curvature regularization, and vice versa.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 9078–9086, 2019.
  * [49] Roman Novak, Yasaman Bahri, Daniel A Abolafia, Jeffrey Pennington, and Jascha Sohl-Dickstein.  Sensitivity and generalization in neural networks: an empirical study.  arXiv preprint arXiv:1802.08760, 2018.
  * [50] Sayak Paul and Pin-Yu Chen.  Vision transformers are robust learners.  arXiv preprint arXiv:2105.07581, 2021.
  * [51] Rafael Pinot, Laurent Meunier, Alexandre Araujo, Hisashi Kashima, Florian Yger, Cédric Gouy-Pailler, and Jamal Atif.  Theoretical evidence for adversarial robustness through randomization.  arXiv preprint arXiv:1902.01148, 2019.
  * [52] Rafael Pinot, Laurent Meunier, Florian Yger, Cédric Gouy-Pailler, Yann Chevaleyre, and Jamal Atif.  On the robustness of randomized classifiers to adversarial examples.  arXiv preprint arXiv:2102.10875, 2021.
  * [53] Rafael Pinot, Florian Yger, Cédric Gouy-Pailler, and Jamal Atif.  A unified view on differential privacy and robustness to adversarial examples.  arXiv preprint arXiv:1906.07982, 2019.
  * [54] Aditi Raghunathan, Sang Michael Xie, Fanny Yang, John Duchi, and Percy Liang.  Understanding and mitigating the tradeoff between robustness and accuracy.  arXiv preprint arXiv:2002.10716, 2020.
  * [55] Hamed Rahimian and Sanjay Mehrotra.  Distributionally robust optimization: A review.  arXiv preprint arXiv:1908.05659, 2019.
  * [56] Sylvestre-Alvise Rebuffi, Sven Gowal, Dan A Calian, Florian Stimberg, Olivia Wiles, and Timothy Mann.  Fixing data augmentation to improve adversarial robustness.  arXiv preprint arXiv:2103.01946, 2021.
  * [57] Leslie Rice, Eric Wong, and Zico Kolter.  Overfitting in adversarially robust deep learning.  In International Conference on Machine Learning, pages 8093–8104. PMLR, 2020.
  * [58] Ludwig Schmidt, Shibani Santurkar, Dimitris Tsipras, Kunal Talwar, and Aleksander Madry.  Adversarially robust generalization requires more data.  arXiv preprint arXiv:1804.11285, 2018.
  * [59] Rulin Shao, Zhouxing Shi, Jinfeng Yi, Pin-Yu Chen, and Cho-Jui Hsieh.  On the adversarial robustness of visual transformers.  arXiv preprint arXiv:2103.15670, 2021.
  * [60] Connor Shorten and Taghi M Khoshgoftaar.  A survey on image data augmentation for deep learning.  Journal of Big Data, 6(1):1–48, 2019.
  * [61] Jure Sokolić, Raja Giryes, Guillermo Sapiro, and Miguel RD Rodrigues.  Robust large margin deep neural networks.  IEEE Transactions on Signal Processing, 65(16):4265–4280, 2017\.
  * [62] Matthew Staib and Stefanie Jegelka.  Distributionally robust deep learning as a generalization of adversarial training.  In NIPS workshop on Machine Learning and Computer Security, volume 3, page 4, 2017.
  * [63] Dong Su, Huan Zhang, Hongge Chen, Jinfeng Yi, Pin-Yu Chen, and Yupeng Gao.  Is robustness the cost of accuracy?–a comprehensive study on the robustness of 18 deep image classification models.  In Proceedings of the European Conference on Computer Vision (ECCV), pages 631–648, 2018.
  * [64] Sunil Thulasidasan, Gopinath Chennupati, Jeff Bilmes, Tanmoy Bhattacharya, and Sarah Michalak.  On mixup training: Improved calibration and predictive uncertainty for deep neural networks.  arXiv preprint arXiv:1905.11001, 2019.
  * [65] Dimitris Tsipras, Shibani Santurkar, Logan Engstrom, Alexander Turner, and Aleksander Madry.  Robustness may be at odds with accuracy.  arXiv preprint arXiv:1805.12152, 2018.
  * [66] Francisco Utrera, Evan Kravitz, N Benjamin Erichson, Rajiv Khanna, and Michael W Mahoney.  Adversarially-trained deep nets transfer better.  arXiv preprint arXiv:2007.05869, 2020.
  * [67] Vladimir Vapnik.  The Nature of Statistical Learning Theory.  Springer Science & Business Media, 2013.
  * [68] Vikas Verma, Alex Lamb, Christopher Beckham, Amir Najafi, Ioannis Mitliagkas, David Lopez-Paz, and Yoshua Bengio.  Manifold mixup: Better representations by interpolating hidden states.  In International Conference on Machine Learning, pages 6438–6447. PMLR, 2019.
  * [69] Colin Wei and Tengyu Ma.  Data-dependent sample complexity of deep neural networks via Lipschitz augmentation.  arXiv preprint arXiv:1905.03684, 2019.
  * [70] Colin Wei and Tengyu Ma.  Improved sample complexities for deep networks and robust classification via an all-layer margin.  arXiv preprint arXiv:1910.04284, 2019.
  * [71] Sen Wu, Hongyang Zhang, Gregory Valiant, and Christopher Ré.  On the generalization effects of linear transformations in data augmentation.  In International Conference on Machine Learning, pages 10410–10420. PMLR, 2020.
  * [72] Huan Xu, Constantine Caramanis, and Shie Mannor.  Robustness and regularization of support vector machines.  Journal of Machine Learning Research, 10(7), 2009.
  * [73] Yao-Yuan Yang, Cyrus Rashtchian, Hongyang Zhang, Ruslan Salakhutdinov, and Kamalika Chaudhuri.  A closer look at accuracy vs. robustness.  arXiv preprint arXiv:2003.02460, 2020.
  * [74] Yaoqing Yang, Rajiv Khanna, Yaodong Yu, Amir Gholami, Kurt Keutzer, Joseph E Gonzalez, Kannan Ramchandran, and Michael W Mahoney.  Boundary thickness and robustness in learning models.  In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 6223–6234, 2020.
  * [75] Wenpeng Yin, Huan Wang, Jin Qu, and Caiming Xiong.  BatchMixup: Improving training by interpolating hidden states of the entire mini-batch.  In Findings of the Association for Computational Linguistics: ACL-IJCNLP 2021, pages 4908–4912, 2021.
  * [76] Sangdoo Yun, Dongyoon Han, Seong Joon Oh, Sanghyuk Chun, Junsuk Choe, and Youngjoon Yoo.  Cutmix: Regularization strategy to train strong classifiers with localizable features.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 6023–6032, 2019.
  * [77] Sergey Zagoruyko and Nikos Komodakis.  Wide residual networks.  arXiv preprint arXiv:1605.07146, 2016.
  * [78] Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent El Ghaoui, and Michael Jordan.  Theoretically principled trade-off between robustness and accuracy.  In International Conference on Machine Learning, pages 7472–7482. PMLR, 2019.
  * [79] Hongyi Zhang, Moustapha Cisse, Yann N Dauphin, and David Lopez-Paz.  Mixup: Beyond empirical risk minimization.  arXiv preprint arXiv:1710.09412, 2017.
  * [80] Linjun Zhang, Zhun Deng, Kenji Kawaguchi, Amirata Ghorbani, and James Zou.  How does mixup help with robustness and generalization?  arXiv preprint arXiv:2010.04819, 2020.
  * [81] Linjun Zhang, Zhun Deng, Kenji Kawaguchi, and James Zou.  When and how mixup improves calibration.  arXiv preprint arXiv:2102.06289, 2021.

Supplementary Material (SM) for “Noisy Feature Mixup”

Organizational Details. This SM is organized as follows.

  * •

In Section A, we study the regularizing effects of NFM within the vicinal risk
minimization framework, relating the effects to those of mixup and noise
injection.

  * •

In Section B, we restate the results presented in the main paper and provide
their proof.

  * •

In Section C, we study robutsness of NFM through the lens of implicit
regularization, showing that NFM can implicitly increase the classification
margin.

  * •

In Section D, we study robustness of NFM via the lens of probabilistic
robustness, showing that noise injection can improve robustness on top of
manifold mixup while keeping track of maximal loss in accuracy incurred under
attack by tuning the noise levels.

  * •

In Section E, we provide results on generalization bounds for NFM and their
proofs, identifying the mechanisms by which NFM can lead to improved
generalization bound.

  * •

In Section F, we provide additional experimental results and their details.

We recall the notation that we use in the main paper as well as this SM.

Notation. $I$ denotes identity matrix, $[K]:=\\{1,\dots,K\\}$, the superscript
T denotes transposition, $\circ$ denotes composition, $\odot$ denotes Hadamard
product, $\mathbb{1}$ denotes the vector with all components equal one. For a
vector $v$, $v^{k}$ denotes its $k$th component and $\|v\|_{p}$ denotes its
$l_{p}$ norm for $p>0$. $conv(\mathcal{X})$ denote the convex hull of
$\mathcal{X}$. $M_{\lambda}(a,b):=\lambda a+(1-\lambda)b$, for random
variables $a,b,\lambda$. $\delta_{z}$ denotes the Dirac delta function,
defined as $\delta_{z}(x)=1$ if $x=z$ and $\delta_{z}(x)=0$ otherwise.
$\mathbb{1}_{A}$ denotes indicator function of the set $A$. For
$\alpha,\beta>0$,
$\tilde{\mathcal{D}}_{\lambda}:=\frac{\alpha}{\alpha+\beta}Beta(\alpha+1,\beta)+\frac{\beta}{\alpha+\beta}Beta(\beta+1,\alpha)$,
a uniform mixture of two Beta distributions. For two vectors $a,b$,
$\cos(a,b):=\langle a,b\rangle/\|a\|_{2}\|b\|_{2}$ denotes their cosine
similarity. $\mathcal{N}(a,b)$ denotes the Gaussian distribution with mean $a$
and covariance $b$.

##  Appendix A NFM Through the Lens of Vicinal Risk Minimization

In this section, we shall show that NFM can be constructed within a vicinal
risk minimization (VRM) framework at the level of both input and hidden layer
representations.

To begin with, we define a class of vicinal distributions and then relate NFM
to such distributions.

######  Definition 1 (Randomly perturbed feature distribution).

Let $\mathcal{Z}_{n}=\\{z_{1},\dots,z_{n}\\}$ be a feature set. We say that
$\mathbb{P}_{n}^{\prime}$ is an $e_{i}$-randomly perturbed feature
distribution if there exists a set $\\{z_{1}^{\prime},\dots,z_{n}^{\prime}\\}$
such that
$\mathbb{P}_{n}^{\prime}=\frac{1}{n}\sum_{i=1}^{n}\delta_{z_{i}^{\prime}}$,
with $z_{i}^{\prime}=z_{i}+e_{i}$, for some random variable $e_{i}$ (possibly
dependent on $\mathcal{Z}_{n}$) drawn from a probability distribution.

Note that the support of an $e_{i}$-randomly perturbed feature distribution
may be larger than that of $\mathcal{Z}$.

If $\mathcal{Z}_{n}$ is an input dataset and the $e_{i}$ are bounded variables
such that $\|e_{i}\|\leq\beta$ for some $\beta\geq 0$, then
$\mathbb{P}_{n}^{\prime}$ is a $\beta$-locally perturbed data distribution
according to Definition 2 in [40]. Examples of $\beta$-locally perturbed data
distribution include that associated with denoising autoencoder, input mixup,
and adversarial training (see Example 1-3 in [40]). Definition 1 can be viewed
as an extension of the definition in [40], relaxing the boundedness condition
on the $e_{i}$ to cover a wide families of perturbed feature distribution. One
simple example is the Gaussian distribution, i.e., when
$e_{i}\sim\mathcal{N}(0,\sigma_{i}^{2})$, which models Gaussian noise
injection into the features. Another example is the distribution associated
with NFM, which we now discuss.

To keep the randomly perturbed distribution close to the original
distribution, the amplitude of the perturbation should be small. In the
sequel, we let $\epsilon>0$ be a small parameter and rescale
$1-\lambda\mapsto\epsilon(1-\lambda)$,
$\sigma_{add}\mapsto\epsilon\sigma_{add}$ and
$\sigma_{mult}\mapsto\epsilon\sigma_{mult}$.

Let $\mathcal{F}_{k}$ be the family of mappings from $g_{k}(\mathcal{X})$ to
$\mathcal{Y}$ and consider the VRM:

$\inf_{f_{k}\in\mathcal{F}_{k}}\mathcal{R}_{n}(f_{k}):=\mathbb{E}_{(g^{\prime}_{k}(x),y^{\prime})\sim\mathbb{P}^{(k)}_{n}}[l(f_{k}(g^{\prime}_{k}(x))),y^{\prime})],$
(12)

where
$\mathbb{P}^{(k)}_{n}=\frac{1}{n}\sum_{i=1}^{n}\delta_{(g_{k}^{\prime}(x_{i}),y_{i}^{\prime})}$,
with $g_{k}^{\prime}(x_{i})=g_{k}(x_{i})+\epsilon e_{i}^{NFM(k)}$ and
$y_{i}^{\prime}=y_{i}+\epsilon e_{i}^{y}$, for some random variables
$e_{i}^{NFM(k)}$ and $e_{i}^{y}$.

In NFM, we approximate the ground-truth distribution $\mathcal{D}$ using the
family of distributions $\\{\mathbb{P}^{(k)}_{n}\\}_{k\in\mathcal{S}}$, with a
particular choice of $(e_{i}^{NFM(k)},e_{i}^{y})$. In the sequel, we denote
NFM at the level of $k$th layer as $NFM(k)$ (i.e., the particular case when
$\mathcal{S}:=\\{k\\}$).

The following lemma identifies the $(e_{i}^{NFM(k)},e_{i}^{y})$ associated
with $NFM(k)$ and relates the effects of $NFM(k)$ to those of mixup and noise
injection, for any perturbation level $\epsilon>0.$

######  Lemma 1.

Let $\epsilon>0$ and denote $z_{i}(k):=g_{k}(x_{i})$. Learning the neural
network map $f$ using $NFM(k)$ is a VRM with the $(\epsilon
e_{i}^{NFM(k)},\epsilon e_{i}^{y})$-randomly perturbed feature distribution,
$\mathbb{P}_{n}^{(k)}=\frac{1}{n}\sum_{i=1}^{n}\delta_{(z_{i}^{\prime}(k),y_{i}^{\prime})}$,
with $z_{i}^{\prime}(k):=z_{i}(k)+\epsilon e_{i}^{NFM(k)}$,
$y_{i}^{\prime}:=y_{i}+\epsilon e_{i}^{y}$, as the vicinal distribution. Here,
$e_{i}^{y}=(1-\lambda)(\tilde{y}_{i}-y_{i})$,

$e^{NFM(k)}_{i}=(\mathbb{1}+\epsilon\sigma_{mult}\xi_{mult})\odot
e_{i}^{mixup(k)}+e_{i}^{noise(k)},$ (13)

where $e_{i}^{mixup(k)}=(1-\lambda)(\tilde{z}_{i}(k)-z_{i}(k))$ and
$e_{i}^{noise(k)}=\sigma_{mult}\xi_{mult}\odot
z_{i}(k)+\sigma_{add}\xi_{add}$, with $z_{i}(k),\tilde{z}_{i}(k)\in
g_{k}(\mathcal{X})$, $\lambda\sim Beta(\alpha,\beta)$, and
$y_{i},\tilde{y}_{i}\in\mathcal{Y}$. Here, $(\tilde{z}_{i}(k),\tilde{y}_{i})$
are drawn randomly from the training set.

Therefore, the random perturbation associated to NFM is data-dependent, and it
consists of a randomly weighted sum of that from injecting noise into the
feature and that from mixing pairs of feature samples. As a simple example,
one can take $\xi_{add},\xi_{mult}$ to be independent standard Gaussian random
variables, in which case we have
$e_{i}^{noise(k)}\sim\mathcal{N}(0,\sigma_{add}^{2}I+\sigma_{mult}^{2}diag(z_{i}(k))^{2})$,
and
$e_{i}\sim\mathcal{N}(0,\sigma_{add}^{2}+\sigma_{mult}^{2}M_{\lambda}(z_{i}(k),\tilde{z}_{i}(k))^{2})$
in Lemma 1.

We now prove Lemma 1.

###### Proof of Lemma 1.

Let $k$ be given and set $\epsilon=1$ without loss of generality. For every
$i\in[n]$, $NFM(k)$ injects noise on top of a mixed sample $z_{i}^{\prime}(k)$
and outputs:

$\displaystyle z_{i}^{\prime\prime}(k)$
$\displaystyle=(\mathbb{1}+\sigma_{mult}\xi_{mult})\odot
z_{i}^{\prime}(k)+\sigma_{add}\xi_{add}$ (14)
$\displaystyle=(\mathbb{1}+\sigma_{mult}\xi_{mult})\odot(\lambda
z_{i}(k)+(1-\lambda)\tilde{z}_{i}(k))+\sigma_{add}\xi_{add}$ (15)
$\displaystyle=z_{i}(k)+e_{i}^{NFM(k)},$ (16)

where
$e_{i}^{NFM(k)}=(1-\lambda)(\tilde{z}_{i}(k)-z_{i}(k))+\sigma_{mult}\xi_{mult}\odot(\lambda
z_{i}(k)+(1-\lambda)\tilde{z}_{i}(k))+\sigma_{add}\xi_{add}$.

Now, note that applying mixup to the pair $(z_{i}(k),\tilde{z}_{i}(k))$
results in $z_{i}^{\prime}(k)=z_{i}(k)+e_{i}^{mixup(k)}$, with
$e_{i}^{mixup(k)}=(1-\lambda)(\tilde{z}_{i}(k)-z_{i}(k))$, where
$z_{i}(k),\tilde{z}_{i}(k)\in g_{k}(\mathcal{X})$ and $\lambda\sim
Beta(\alpha,\beta)$, whereas applying noise injection to $z_{i}(k)$ results in
$(\mathbb{1}+\sigma_{mult}\xi_{mult})\odot
z_{i}(k)+\sigma_{add}\xi_{add}=z_{i}(k)+e_{i}^{noise(k)}$, with
$e_{i}^{noise(k)}=\sigma_{mult}\xi_{mult}\odot
z_{i}(k)+\sigma_{add}\xi_{add}$. Rewriting $e^{NFM(k)}_{i}$ in terms of
$e_{i}^{mixup(k)}$ and $e_{i}^{noise(k)}$ gives

$e^{NFM(k)}_{i}=(\mathbb{1}+\sigma_{mult}\xi_{mult})\odot
e_{i}^{mixup(k)}+e_{i}^{noise(k)}.$ (17)

Similarly, we can derive the expression for $e_{i}^{y}$ using the same
argument. The results in the lemma follow upon applying the rescaling
$1-\lambda\mapsto\epsilon(1-\lambda)$,
$\sigma_{add}\mapsto\epsilon\sigma_{add}$ and
$\sigma_{mult}\mapsto\epsilon\sigma_{mult}$, for $\epsilon>0$. ∎

##  Appendix B Statements and Proof of the Results in the Main Paper

###  B.1 Complete Statement of Theorem 1 in the Main Paper and the Proof

We first state the complete statement of Theorem 1 in the main paper.

######  Theorem 3 (Theorem 1 in the main paper).

Let $\epsilon>0$ be a small parameter, and assume that $h$ and $f$ are twice
differentiable. Then,
$L^{NFM}_{n}=\mathbb{E}_{k\sim\mathcal{S}}L^{NFM(k)}_{n}$, where

$L^{NFM(k)}_{n}=L_{n}^{std}+\epsilon
R_{1}^{(k)}+\epsilon^{2}\tilde{R}_{2}^{(k)}+\epsilon^{2}\tilde{R}_{3}^{(k)}+\epsilon^{2}\varphi(\epsilon),$
(18)

with

$\displaystyle\tilde{R}_{2}^{(k)}$
$\displaystyle=R_{2}^{(k)}+\sigma_{add}^{2}R_{2}^{add(k)}+\sigma_{mult}^{2}R_{2}^{mult(k)},$
(19) $\displaystyle\tilde{R}_{3}^{(k)}$
$\displaystyle=R_{3}^{(k)}+\sigma_{add}^{2}R_{3}^{add(k)}+\sigma_{mult}^{2}R_{3}^{mult(k)},$
(20)

where

$\displaystyle R_{1}^{(k)}$
$\displaystyle=\frac{\mathbb{E}_{\lambda\sim\tilde{\mathcal{D}}_{\lambda}}[1-\lambda]}{n}\sum_{i=1}^{n}(h^{\prime}(f(x_{i})-y_{i})\nabla_{k}f(g_{k}(x_{i}))^{T}\mathbb{E}_{x_{r}\sim\mathcal{D}_{x}}[g_{k}(x_{r})-g_{k}(x_{i})],$
(21) $\displaystyle R_{2}^{(k)}$
$\displaystyle=\frac{\mathbb{E}_{\lambda\sim\tilde{\mathcal{D}}_{\lambda}}[(1-\lambda)^{2}]}{2n}\sum_{i=1}^{n}h^{\prime\prime}(f(x_{i}))\nabla_{k}f(g_{k}(x_{i}))^{T}$
$\displaystyle\hskip
14.22636pt\times\mathbb{E}_{x_{r}\sim\mathcal{D}_{x}}[(g_{k}(x_{r})-g_{k}(x_{i}))(g_{k}(x_{r})-g_{k}(x_{i}))^{T}]\nabla_{k}f(g_{k}(x_{i})),$
(22) $\displaystyle R_{3}^{(k)}$
$\displaystyle=\frac{\mathbb{E}_{\lambda\sim\tilde{\mathcal{D}}_{\lambda}}[(1-\lambda)^{2}]}{2n}\sum_{i=1}^{n}(h^{\prime}(f(x_{i}))-y_{i})$
$\displaystyle\hskip
14.22636pt\times\mathbb{E}_{x_{r}\sim\mathcal{D}_{x}}[(g_{k}(x_{r})-g_{k}(x_{i}))^{T}\nabla_{k}^{2}f(g_{k}(x_{i}))(g_{k}(x_{r})-g_{k}(x_{i}))],$
(23) $\displaystyle R_{2}^{add(k)}$
$\displaystyle=\frac{1}{2n}\sum_{i=1}^{n}h^{\prime\prime}(f(x_{i}))\nabla_{k}f(g_{k}(x_{i}))^{T}\mathbb{E}_{\boldsymbol{\xi}_{k}}[\xi_{k}^{add}(\xi_{k}^{add})^{T}]\nabla_{k}f(g_{k}(x_{i})),$
(24) $\displaystyle R_{2}^{mult(k)}$
$\displaystyle=\frac{1}{2n}\sum_{i=1}^{n}h^{\prime\prime}(f(x_{i}))\nabla_{k}f(g_{k}(x_{i}))^{T}(\mathbb{E}_{\boldsymbol{\xi}_{k}}[\xi_{k}^{add}(\xi_{k}^{add})^{T}]\odot
g_{k}(x_{i})g_{k}(x_{i})^{T})\nabla_{k}f(g_{k}(x_{i})),$ (25) $\displaystyle
R_{3}^{add(k)}$
$\displaystyle=\frac{1}{2n}\sum_{i=1}^{n}(h^{\prime}(f(x_{i}))-y_{i})\mathbb{E}_{\boldsymbol{\xi}_{k}}[(\xi_{k}^{add})^{T}\nabla_{k}^{2}f(g_{k}(x_{i}))\xi_{k}^{add}],$
(26) $\displaystyle R_{3}^{mult(k)}$
$\displaystyle=\frac{1}{2n}\sum_{i=1}^{n}(h^{\prime}(f(x_{i}))-y_{i})\mathbb{E}_{\boldsymbol{\xi}_{k}}[(\xi_{k}^{mult}\odot
g_{k}(x_{i}))^{T}\nabla_{k}^{2}f(g_{k}(x_{i}))(\xi_{k}^{mult}\odot
g_{k}(x_{i}))],$ (27)

and $\varphi$ is some function such that $\lim_{\epsilon\to
0}\varphi(\epsilon)=0$.

###### Proof of Theorem 3.

To begin with, we note that, following the argument of the proof of Lemma 3.1
in [80], the loss function minimized by NFM can be written as
$L^{NFM}_{n}=\mathbb{E}_{k\sim\mathcal{S}}L^{NFM(k)}_{n}$, where

$L^{NFM(k)}_{n}=\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}_{\lambda\sim\tilde{\mathcal{D}}_{\lambda}}\mathbb{E}_{x_{r}\sim\mathcal{D}_{x}}\mathbb{E}_{\boldsymbol{\xi}_{k}\sim\mathcal{Q}}[h(f_{k}(g_{k}(x_{i})+\epsilon
e_{i}^{NFM(k)}))-y_{i}f_{k}(g_{k}(x_{i})+\epsilon e_{i}^{NFM(k)})],$ (28)

with

$e^{NFM(k)}_{i}=(\mathbb{1}+\epsilon\sigma_{mult}\xi_{k}^{mult})\odot
e_{i}^{mixup(k)}+e_{i}^{noise(k)}.$ (29)

Here $e_{i}^{mixup(k)}=(1-\lambda)(g_{k}(x_{r})-g_{k}(x_{i}))$ and
$e_{i}^{noise(k)}=\sigma_{mult}\xi_{k}^{mult}\odot
g_{k}(x_{i})+\sigma_{add}\xi_{k}^{add}$, with $g_{k}(x_{i}),g_{k}(x_{r})\in
g_{k}(\mathcal{X})$ and $\lambda\sim Beta(\alpha,\beta)$.

Denote $\psi_{i}(\epsilon):=h(f_{k}(g_{k}(x_{i})+\epsilon
e_{i}^{NFM(k)}))-y_{i}f_{k}(g_{k}(x_{i})+\epsilon e_{i}^{NFM(k)})$. Since $h$
and $f_{k}$ are twice differentiable by assumption, $\psi_{i}$ is twice
differentiable in $\epsilon$, and

$\psi_{i}(\epsilon)=\psi_{i}(0)+\epsilon\psi_{i}^{\prime}(0)+\frac{\epsilon^{2}}{2}\psi^{\prime\prime}_{i}(0)+\epsilon^{2}\varphi_{i}(\epsilon),$
(30)

where $\varphi_{i}$ is some function such that $\lim_{\epsilon\to
0}\varphi_{i}(\epsilon)=0$.

Denoting $\tilde{g}_{k}(x_{i}):=g_{k}(x_{i})+\epsilon e_{i}^{NFM(k)}$, we
compute, using linearity and chain rule:

$\displaystyle\psi_{i}^{\prime}(\epsilon)$
$\displaystyle=(h^{\prime}(f_{k}(\tilde{g}_{k}(x_{i})))-y_{i})\nabla_{k}f_{k}(\tilde{g}_{k}(x_{i}))^{T}e_{i}^{NFM(k)}$
(31)
$\displaystyle=(h^{\prime}(f_{k}(\tilde{g}_{k}(x_{i})))-y_{i})\nabla_{k}f_{k}(\tilde{g}_{k}(x_{i}))^{T}[(1-\lambda)(\tilde{g}_{k}(x_{r})-\tilde{g}_{k}(x_{i}))+\sigma_{add}\xi_{k}^{add}$
$\displaystyle\ \ \ \
+\sigma_{mult}\xi_{k}^{mult}\odot\tilde{g}_{k}(x_{i})+\epsilon(1-\lambda)\sigma_{mult}\xi_{k}^{mult}\odot(\tilde{g}_{k}(x_{r})-\tilde{g}_{k}(x_{i}))],$
(32) $\displaystyle\psi_{i}^{\prime\prime}(\epsilon)$
$\displaystyle=h^{\prime\prime}(f_{k}(\tilde{g}_{k}(x_{i})))\nabla_{k}f_{k}(\tilde{g}_{k}(x_{i}))^{T}e_{i}^{NFM(k)}(e_{i}^{NFM(k)})^{T}\nabla_{k}f_{k}(\tilde{g}_{k}(x_{i}))$
$\displaystyle\ \ \ \
+(h^{\prime}(f_{k}(\tilde{g}_{k}(x_{i})))-y_{i})(e_{i}^{NFM(k)})^{T}\nabla_{k}^{2}f_{k}(\tilde{g}_{k}(x_{i}))e_{i}^{NFM(k)}$
(33)
$\displaystyle=h^{\prime\prime}(f_{k}(\tilde{g}_{k}(x_{i})))\nabla_{k}f_{k}(\tilde{g}_{k}(x_{i}))^{T}[(1-\lambda)(\tilde{g}_{k}(x_{r})-\tilde{g}_{k}(x_{i}))+\sigma_{add}\xi_{k}^{add}$
$\displaystyle\ \ \ \
+\sigma_{mult}\xi_{k}^{mult}\odot\tilde{g}_{k}(x_{i})+\epsilon(1-\lambda)\sigma_{mult}\xi_{k}^{mult}\odot(\tilde{g}_{k}(x_{r})-\tilde{g}_{k}(x_{i}))]$
$\displaystyle\ \ \ \
\times[(1-\lambda)(\tilde{g}_{k}(x_{r})-\tilde{g}_{k}(x_{i}))+\sigma_{add}\xi_{k}^{add}+\sigma_{mult}\xi_{k}^{mult}\odot\tilde{g}_{k}(x_{i})$
$\displaystyle\ \ \ \
+\epsilon(1-\lambda)\sigma_{mult}\xi_{k}^{mult}\odot(\tilde{g}_{k}(x_{r})-\tilde{g}_{k}(x_{i}))]^{T}\nabla_{k}f_{k}(\tilde{g}_{k}(x_{i}))$
$\displaystyle\ \ \ \
+(h^{\prime}(f_{k}(\tilde{g}_{k}(x_{i})))-y_{i})[(1-\lambda)(\tilde{g}_{k}(x_{r})-\tilde{g}_{k}(x_{i}))+\sigma_{add}\xi_{k}^{add}+\sigma_{mult}\xi_{k}^{mult}\odot\tilde{g}_{k}(x_{i})$
$\displaystyle\ \ \ \
+\epsilon(1-\lambda)\sigma_{mult}\xi_{k}^{mult}\odot(\tilde{g}_{k}(x_{r})-\tilde{g}_{k}(x_{i}))]^{T}\nabla_{k}^{2}f_{k}(\tilde{g}_{k}(x_{i}))[(1-\lambda)(\tilde{g}_{k}(x_{r})-\tilde{g}_{k}(x_{i}))$
$\displaystyle\ \ \ \
+\sigma_{add}\xi_{k}^{add}+\sigma_{mult}\xi_{k}^{mult}\odot\tilde{g}_{k}(x_{i})+\epsilon(1-\lambda)\sigma_{mult}\xi_{k}^{mult}\odot(\tilde{g}_{k}(x_{r})-\tilde{g}_{k}(x_{i}))].$
(34)

The equation in the theorem follows upon setting $\epsilon=0$ in the
expression for $\psi_{i}^{\prime}(\epsilon)$ and
$\psi_{i}^{\prime\prime}(\epsilon)$ above, and then substituting the resulting
expressions into (28), with
$\varphi(\epsilon):=\frac{1}{n}\sum_{i=1}^{n}\varphi_{i}(\epsilon)$. ∎

###  B.2 Theorem 2 in the Main Paper and the Proof

We first restate Theorem 2 in the main paper and then provide the proof.
Recall that we consider the binary cross-entropy loss, setting
$h(z)=\log(1+e^{z})$, with the labels $y$ taking value in $\\{0,1\\}$ and the
classifier model $f:\mathbb{R}^{d}\to\mathbb{R}$.

######  Theorem 4 (Theorem 2 in the main paper).

Let $\theta\in\Theta:=\\{\theta:y_{i}f(x_{i})+(y_{i}-1)f(x_{i})\geq 0\text{
for all }i\in[n]\\}$ be a point such that $\nabla_{k}f(g_{k}(x_{i}))$ and
$\nabla_{k}^{2}f(g_{k}(x_{i}))$ exist for all $i\in[n]$, $k\in\mathcal{S}$.
Assume that $f_{k}(g_{k}(x_{i}))=\nabla_{k}f(g_{k}(x_{i}))^{T}g_{k}(x_{i})$,
$\nabla_{k}^{2}f(g_{k}(x_{i}))=0$ for all $i\in[n]$, $k\in\mathcal{S}$. In
addition, suppose that $\|\nabla f(x_{i})\|_{2}>0$ for all $i\in[n]$,
$\mathbb{E}_{r\sim\mathcal{D}_{x}}[g_{k}(r)]=0$ and $\|g_{k}(x_{i})\|_{2}\geq
c_{x}^{(k)}\sqrt{d_{k}}$ for all $i\in[n]$, $k\in\mathcal{S}$. Then,

$\displaystyle
L_{n}^{NFM}\geq\frac{1}{n}\sum_{i=1}^{n}\max_{\|\delta_{i}\|_{2}\leq\epsilon_{i}^{mix}}l(f(x_{i}+\delta_{i}),y_{i})+L_{n}^{reg}+\epsilon^{2}\phi(\epsilon),$
(35)

where

$\displaystyle\epsilon_{i}^{mix}$
$\displaystyle=\epsilon\mathbb{E}_{\lambda\sim\tilde{\mathcal{D}}_{\lambda}}[1-\lambda]\cdot\mathbb{E}_{k\sim\mathcal{S}}\left[r_{i}^{(k)}c_{x}^{(k)}\frac{\|\nabla_{k}f(g_{k}(x_{i}))\|_{2}}{\|\nabla
f(x_{i})\|_{2}}\sqrt{d_{k}}\right],$ (36) $\displaystyle r_{i}^{(k)}$
$\displaystyle=|\cos(\nabla_{k}f(g_{k}(x_{i})),g_{k}(x_{i}))|,$ (37)
$\displaystyle L_{n}^{reg}$
$\displaystyle=\frac{1}{2n}\sum_{i=1}^{n}|h^{\prime\prime}(f(x_{i}))|(\epsilon_{i}^{reg})^{2},$
(38)

with

$\displaystyle(\epsilon_{i}^{reg})^{2}$
$\displaystyle=\epsilon^{2}\|\nabla_{k}f(g_{k}(x_{i}))\|_{2}^{2}\bigg{(}\mathbb{E}_{\lambda}[(1-\lambda)]^{2}\mathbb{E}_{x_{r}}[\|g_{k}(x_{r})\|_{2}^{2}\cos(\nabla_{k}f(g_{k}(x_{i})),g_{k}(x_{r}))^{2}]$
$\displaystyle\hskip
19.91684pt+\sigma_{add}^{2}\mathbb{E}_{\boldsymbol{\xi}}[\|\xi_{add}\|_{2}^{2}\cos(\nabla_{k}f(g_{k}(x_{i})),\xi_{add})^{2}]$
$\displaystyle\hskip
19.91684pt+\sigma_{mult}^{2}\mathbb{E}_{\boldsymbol{\xi}}[\|\xi_{mult}\odot
g_{k}(x_{i})\|_{2}^{2}\cos(\nabla_{k}f(g_{k}(x_{i})),\xi_{mult}\odot
g_{k}(x_{i}))^{2}]\bigg{)},$ (39)

and $\phi$ is some function such that $\lim_{\epsilon\to 0}\phi(\epsilon)=0$.

###### Proof of Theorem 4.

For $h(z)=\log(1+e^{z})$, we have
$h^{\prime}(z)=\frac{e^{z}}{1+e^{z}}=:S(z)\geq 0$ and
$h^{\prime\prime}(z)=\frac{e^{z}}{(1+e^{z})^{2}}=S(z)(1-S(z))\geq 0$.
Substituting these expressions into the equation of Theorem 3 and using the
assumptions that
$f_{k}(g_{k}(x_{i}))=\nabla_{k}f(g_{k}(x_{i}))^{T}g_{k}(x_{i})$ and
$\mathbb{E}_{r\sim\mathcal{D}_{x}}[g_{k}(r)]=0$, we have, for
$k\in\mathcal{S}$,

$R_{1}^{(k)}=\frac{\mathbb{E}_{\lambda\sim\tilde{\mathcal{D}}_{\lambda}}[1-\lambda]}{n}\sum_{i=1}^{n}(y_{i}-S(f(x_{i})))f_{k}(g_{k}(x_{i})),$
(40)

and we compute:

$\displaystyle R_{2}^{(k)}$
$\displaystyle=\frac{\mathbb{E}_{\lambda\sim\tilde{\mathcal{D}}_{\lambda}}[(1-\lambda)^{2}]}{2n}\sum_{i=1}^{n}S(f(x_{i}))(1-S(f(x_{i})))\nabla_{k}f(g_{k}(x_{i}))^{T}$
$\displaystyle\hskip
14.22636pt\times\mathbb{E}_{x_{r}\sim\mathcal{D}_{x}}[(g_{k}(x_{r})-g_{k}(x_{i}))(g_{k}(x_{r})-g_{k}(x_{i}))^{T}]\nabla_{k}f(g_{k}(x_{i}))$
(41)
$\displaystyle\geq\frac{\mathbb{E}_{\lambda\sim\tilde{\mathcal{D}}_{\lambda}}[(1-\lambda)]^{2}}{2n}\sum_{i=1}^{n}|S(f(x_{i}))(1-S(f(x_{i})))|\nabla_{k}f(g_{k}(x_{i}))^{T}$
$\displaystyle\hskip
14.22636pt\times\mathbb{E}_{x_{r}\sim\mathcal{D}_{x}}[(g_{k}(x_{r})-g_{k}(x_{i}))(g_{k}(x_{r})-g_{k}(x_{i}))^{T}]\nabla_{k}f(g_{k}(x_{i}))$
(42)
$\displaystyle=\frac{\mathbb{E}_{\lambda\sim\tilde{\mathcal{D}}_{\lambda}}[(1-\lambda)]^{2}}{2n}\sum_{i=1}^{n}|S(f(x_{i}))(1-S(f(x_{i})))|\nabla_{k}f(g_{k}(x_{i}))^{T}$
$\displaystyle\hskip
14.22636pt\times(\mathbb{E}_{x_{r}\sim\mathcal{D}_{x}}[(g_{k}(x_{r})g_{k}(x_{r})^{T}]+g_{k}(x_{i})g_{k}(x_{i})^{T}])\nabla_{k}f(g_{k}(x_{i}))$
(43)
$\displaystyle=\frac{\mathbb{E}_{\lambda\sim\tilde{\mathcal{D}}_{\lambda}}[(1-\lambda)]^{2}}{2n}\sum_{i=1}^{n}|S(f(x_{i}))(1-S(f(x_{i})))|(\nabla_{k}f(g_{k}(x_{i}))^{T}g_{k}(x_{i}))^{2}$
$\displaystyle\ \ \ \ \
+\frac{\mathbb{E}_{\lambda\sim\tilde{\mathcal{D}}_{\lambda}}[(1-\lambda)]^{2}}{2n}\sum_{i=1}^{n}|S(f(x_{i}))(1-S(f(x_{i})))|\mathbb{E}_{x_{r}\in\mathcal{D}_{x}}[(\nabla_{k}f(g_{k}(x_{i}))^{T}g_{k}(x_{r}))^{2}]$
(44)
$\displaystyle=\frac{\mathbb{E}_{\lambda\sim\tilde{\mathcal{D}}_{\lambda}}[(1-\lambda)]^{2}}{2n}\sum_{i=1}^{n}|S(f(x_{i}))(1-S(f(x_{i})))|\|\nabla_{k}f(g_{k}(x_{i}))\|_{2}^{2}\|g_{k}(x_{i})\|_{2}^{2}$
$\displaystyle\hskip
14.22636pt\times(\cos(\nabla_{k}f(g_{k}(x_{i})),g_{k}(x_{i})))^{2}+\frac{1}{2n}\sum_{i=1}^{n}|S(f(x_{i}))(1-S(f(x_{i})))|\|\nabla_{k}f(g_{k}(x_{i}))\|_{2}^{2}$
$\displaystyle\ \ \ \ \ \
\times\mathbb{E}_{\lambda}[(1-\lambda)]^{2}\mathbb{E}_{x_{r}}[\|g_{k}(x_{r})\|_{2}^{2}\cos(\nabla_{k}f(g_{k}(x_{i})),g_{k}(x_{r}))^{2}]$
(45)
$\displaystyle\geq\frac{1}{2n}\sum_{i=1}^{n}|S(f(x_{i}))(1-S(f(x_{i})))|\|\nabla_{k}f(g_{k}(x_{i}))\|_{2}^{2}\mathbb{E}_{\lambda\sim\tilde{\mathcal{D}}_{\lambda}}[(1-\lambda)]^{2}d_{k}(r_{i}^{(k)}c_{x}^{(k)})^{2}$
$\displaystyle\ \ \ \
+\frac{1}{2n}\sum_{i=1}^{n}|S(f(x_{i}))(1-S(f(x_{i})))|\|\nabla_{k}f(g_{k}(x_{i}))\|_{2}^{2}\cdot\mathbb{E}_{\lambda}[(1-\lambda)]^{2}\mathbb{E}_{x_{r}}[\|g_{k}(x_{r})\|_{2}^{2}$
$\displaystyle\ \ \ \ \
\times\cos(\nabla_{k}f(g_{k}(x_{i})),g_{k}(x_{r}))^{2}]$ (46)
$\displaystyle=\frac{1}{2n}\sum_{i=1}^{n}|S(f(x_{i}))(1-S(f(x_{i})))|\|\nabla
f(x_{i})\|_{2}^{2}$ $\displaystyle\ \ \ \
\times\left(\mathbb{E}_{\lambda\sim\tilde{\mathcal{D}}_{\lambda}}[(1-\lambda)]^{2}\frac{\|\nabla_{k}f(g_{k}(x_{i}))\|_{2}^{2}}{\|\nabla
f(x_{i})\|_{2}^{2}}d_{k}(r_{i}^{(k)}c_{x}^{(k)})^{2}\right)$ $\displaystyle\ \
\ \
+\frac{1}{2n}\sum_{i=1}^{n}|S(f(x_{i}))(1-S(f(x_{i})))|\|\nabla_{k}f(g_{k}(x_{i}))\|_{2}^{2}\cdot\mathbb{E}_{\lambda}[(1-\lambda)]^{2}\mathbb{E}_{x_{r}}[\|g_{k}(x_{r})\|_{2}^{2}$
$\displaystyle\ \ \ \ \
\times\cos(\nabla_{k}f(g_{k}(x_{i})),g_{k}(x_{r}))^{2}].$ (47)

In the above, we have used the facts that
$\mathbb{E}[Z^{2}]=\mathbb{E}[Z]^{2}+Var(Z)\geq\mathbb{E}[Z]^{2}$ and
$S,S(1-S)\geq 0$ to obtain (42), the assumption that
$\mathbb{E}_{r\sim\mathcal{D}_{x}}[g_{k}(r)]=0$ to arrive at (B.2), the
assumption that $\|g_{k}(x_{i})\|_{2}\geq c_{x}^{(k)}\sqrt{d_{k}}$ for all
$i\in[n]$, $k\in\mathcal{S}$ to arrive at (46), and the assumption that
$\|\nabla f(x_{i})\|_{2}>0$ for all $i\in[n]$ to justify the last equation
above.

Next, we bound $R_{1}^{(k)}$, using the assumption that $\theta\in\Theta$.
Note that from our assumption on $\theta$, we have
$y_{i}f(x_{i})+(y_{i}-1)f(x_{i})\geq 0$, which implies that $f(x_{i})\geq 0$
if $y_{i}=1$ and $f(x_{i})\leq 0$ if $y_{i}=0$. Thus, if $y_{i}=1$, then
$(y_{i}-S(f(x_{i})))f_{k}(g_{k}(x_{i}))=(1-S(f(x_{i})))f_{k}(g_{k}(x_{i}))\geq
0$, since $f(x_{i})\geq 0$ and $(1-S(f(x_{i})))\geq 0$ due to the fact that
$S(f(x_{i}))\in(0,1)$. A similar argument leads to
$(y_{i}-S(f(x_{i})))f_{k}(g_{k}(x_{i}))\geq 0$ if $y_{i}=0$. So, we have
$(y_{i}-S(f(x_{i})))f_{k}(g_{k}(x_{i}))\geq 0$ for all $i\in[n]$.

Therefore, noting that
$\mathbb{E}_{\lambda\sim\tilde{\mathcal{D}}_{\lambda}}[1-\lambda]\geq 0$, we
compute:

$\displaystyle R_{1}^{(k)}$
$\displaystyle=\frac{\mathbb{E}_{\lambda\sim\tilde{\mathcal{D}}_{\lambda}}[1-\lambda]}{n}\sum_{i=1}^{n}|y_{i}-S(f(x_{i}))||f_{k}(g_{k}(x_{i}))|$
(48)
$\displaystyle=\frac{\mathbb{E}_{\lambda\sim\tilde{\mathcal{D}}_{\lambda}}[1-\lambda]}{n}\sum_{i=1}^{n}|S(f(x_{i}))-y_{i}|\|\nabla_{k}f(g_{k}(x_{i}))\|_{2}\|g_{k}(x_{i})\|_{2}|\cos(\nabla_{k}f(g_{k}(x_{i})),g_{k}(x_{i}))|$
(49)
$\displaystyle\geq\frac{1}{n}\sum_{i=1}^{n}|S(f(x_{i}))-y_{i}|\|\nabla_{k}f(g_{k}(x_{i}))\|_{2}(\mathbb{E}_{\lambda\sim\tilde{\mathcal{D}}_{\lambda}}[1-\lambda]r_{i}^{(k)}c_{x}^{(k)}\sqrt{d_{k}})$
(50) $\displaystyle=\frac{1}{n}\sum_{i=1}^{n}|S(f(x_{i}))-y_{i}|\|\nabla
f(x_{i})\|_{2}\left(\mathbb{E}_{\lambda\sim\tilde{\mathcal{D}}_{\lambda}}[1-\lambda]\frac{\|\nabla_{k}f(g_{k}(x_{i}))\|_{2}}{\|\nabla
f(x_{i})\|_{2}}r_{i}^{(k)}c_{x}^{(k)}\sqrt{d_{k}}\right).$ (51)

Note that $R_{3}^{(k)}=0$ as a consequence of our assumption that
$\nabla_{k}^{2}f(g_{k}(x_{i}))=0$ for all $i\in[n]$, $k\in\mathcal{S}$, and
similar argument leads to:

$\displaystyle R_{2}^{add(k)}$
$\displaystyle=\frac{1}{2n}\sum_{i=1}^{n}|S(f(x_{i}))(1-S(f(x_{i})))|\nabla_{k}f(g_{k}(x_{i}))^{T}\mathbb{E}_{\boldsymbol{\xi}_{k}}[\xi_{k}^{add}(\xi_{k}^{add})^{T}]\nabla_{k}f(g_{k}(x_{i}))$
(52)
$\displaystyle=\frac{1}{2n}\sum_{i=1}^{n}|S(f(x_{i}))(1-S(f(x_{i})))|\|\nabla_{k}f(g_{k}(x_{i}))\|_{2}^{2}$
$\displaystyle\ \ \ \ \
\times\mathbb{E}_{\boldsymbol{\xi}_{k}}[\|\xi_{k}^{add}\|_{2}^{2}\cos(\nabla_{k}f(g_{k}(x_{i})),\xi_{k}^{add})^{2}]$
(53) $\displaystyle R_{2}^{mult(k)}$
$\displaystyle=\frac{1}{2n}\sum_{i=1}^{n}|S(f(x_{i}))(1-S(f(x_{i})))|\nabla_{k}f(g_{k}(x_{i}))^{T}(\mathbb{E}_{\boldsymbol{\xi}_{k}}[\xi_{k}^{add}(\xi_{k}^{add})^{T}]\odot
g_{k}(x_{i})g_{k}(x_{i})^{T})$ $\displaystyle\ \ \ \
\times\nabla_{k}f(g_{k}(x_{i}))$
$\displaystyle=\frac{1}{2n}\sum_{i=1}^{n}|S(f(x_{i}))(1-S(f(x_{i})))|\|\nabla_{k}f(g_{k}(x_{i}))\|_{2}^{2}$
$\displaystyle\ \ \ \ \
\times\mathbb{E}_{\boldsymbol{\xi}_{k}}[\|\xi_{k}^{mult}\odot
g_{k}(x_{i})\|_{2}^{2}\cos(\nabla_{k}f(g_{k}(x_{i})),\xi_{mult}\odot
g_{k}(x_{i}))^{2}].$ (54)

Using Theorem 3 and the above results, we obtain:

$\displaystyle L^{NFM}_{n}-\frac{1}{n}\sum_{i=1}^{n}l(f(x_{i}),y_{i})$
$\displaystyle\geq\mathbb{E}_{k}[\epsilon
R_{1}^{(k)}+\epsilon^{2}R_{2}^{(k)}+\epsilon^{2}R_{2}^{add(k)}+\epsilon^{2}R_{2}^{mult(k)}+\epsilon^{2}\varphi(\epsilon)]$
(55) $\displaystyle\geq\frac{1}{n}\sum_{i=1}^{n}|S(f(x_{i}))-y_{i}|\|\nabla
f(x_{i})\|_{2}\epsilon_{i}^{mix}$ (56) $\displaystyle\ \ \ \
+\frac{1}{2n}\sum_{i=1}^{n}|S(f(x_{i}))(1-S(f(x_{i})))|\|\nabla
f(x_{i})\|_{2}^{2}(\epsilon_{i}^{mix})^{2}$ $\displaystyle\ \ \ \
+\frac{1}{2n}\sum_{i=1}^{n}|S(f(x_{i}))(1-S(f(x_{i})))|\|\nabla_{k}f(g_{k}(x_{i}))\|_{2}^{2}\cdot\mathbb{E}_{\lambda}[(1-\lambda)]^{2}\mathbb{E}_{x_{r}}[\|g_{k}(x_{r})\|_{2}^{2}$
$\displaystyle\ \ \ \ \ \
\times\cos(\nabla_{k}f(g_{k}(x_{i})),g_{k}(x_{r}))^{2}]$ (57) $\displaystyle\
\ \ \
+\frac{1}{2n}\sum_{i=1}^{n}|S(f(x_{i}))(1-S(f(x_{i})))|(\epsilon_{i}^{noise})^{2}+\epsilon^{2}\varphi(\epsilon),$
(58)

where
$\epsilon_{i}^{mix}:=\epsilon\mathbb{E}_{\lambda\sim\tilde{\mathcal{D}}_{\lambda}}[1-\lambda]\mathbb{E}_{k}\left[\frac{\|\nabla_{k}f(g_{k}(x_{i}))\|_{2}}{\|\nabla
f(x_{i})\|_{2}}r_{i}^{(k)}c_{x}^{(k)}\sqrt{d_{k}}\right]$ and

$\displaystyle(\epsilon_{i}^{noise})^{2}$
$\displaystyle=\epsilon^{2}\|\nabla_{k}f(g_{k}(x_{i}))\|_{2}^{2}\bigg{(}\sigma_{add}^{2}\mathbb{E}_{\boldsymbol{\xi}_{k}}[\|\xi_{k}^{add}\|_{2}^{2}\cos(\nabla_{k}f(g_{k}(x_{i})),\xi_{k}^{add})^{2}]$
$\displaystyle\hskip
19.91684pt+\sigma_{mult}^{2}\mathbb{E}_{\boldsymbol{\xi}_{k}}[\|\xi_{k}^{mult}\odot
g_{k}(x_{i})\|_{2}^{2}\cos(\nabla_{k}f(g_{k}(x_{i})),\xi_{k}^{mult}\odot
g_{k}(x_{i}))^{2}]\bigg{)}.$ (59)

On the other hand, for any small parameters $\epsilon_{i}>0$ and any inputs
$z_{1},\dots,z_{n}$, we can, using a second-order Taylor expansion and then
applying our assumptions, compute:

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\max_{\|\delta_{i}\|_{2}\leq\epsilon_{i}}l(f(z_{i}+\delta_{i}),y_{i})-\frac{1}{n}\sum_{i=1}^{n}l(f(z_{i}),y_{i})$
$\displaystyle\leq\frac{1}{n}\sum_{i=1}^{n}|S(f(z_{i}))-y_{i}|\|\nabla
f(z_{i})\|_{2}\epsilon_{i}+\frac{1}{2n}\sum_{i=1}^{n}|S(f(z_{i}))(1-S(f(z_{i})))|\|\nabla
f(z_{i})\|_{2}^{2}\epsilon_{i}^{2}$ $\displaystyle\ \ \ \
+\frac{1}{n}\sum_{i=1}^{n}\max_{\|\delta_{i}\|_{2}\leq\epsilon_{i}}\|\delta_{i}\|_{2}^{2}\varphi_{i}^{\prime}(\delta_{i})$
(60) $\displaystyle\leq\frac{1}{n}\sum_{i=1}^{n}|S(f(z_{i}))-y_{i}|\|\nabla
f(z_{i})\|_{2}\epsilon_{i}+\frac{1}{2n}\sum_{i=1}^{n}|S(f(z_{i}))(1-S(f(z_{i})))|\|\nabla
f(z_{i})\|_{2}^{2}\epsilon_{i}^{2}$ $\displaystyle\ \ \ \
+\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}^{2}\varphi_{i}^{\prime\prime}(\epsilon_{i}),$
(61)

where the $\varphi_{i}^{\prime}$ are functions such that $\lim_{z\to
0}\varphi_{i}^{\prime}(z)=0$,
$\varphi_{i}^{\prime\prime}(\epsilon_{i}):=\max_{\|\delta_{i}\|_{2}\leq\epsilon_{i}}\varphi_{i}^{\prime}(\delta_{i})$
and $\lim_{z\to 0}\varphi_{i}^{\prime\prime}(z)=0$.

Combining (58) and (61), we see that

$\displaystyle L_{n}^{NFM}$
$\displaystyle\geq\frac{1}{n}\sum_{i=1}^{n}\max_{\|\delta_{i}^{mix}\|_{2}\leq\epsilon_{i}^{mix}}l(f(x_{i}+\delta_{i}^{mix}),y_{i})+L_{n}^{reg}+\epsilon^{2}\varphi(\epsilon)-\frac{1}{n}\sum_{i=1}^{n}(\epsilon_{i}^{mix})^{2}\varphi_{i}^{\prime\prime}(\epsilon_{i}^{mix})$
(62)
$\displaystyle=:\frac{1}{n}\sum_{i=1}^{n}\max_{\|\delta_{i}^{mix}\|_{2}\leq\epsilon_{i}^{mix}}l(f(x_{i}+\delta_{i}^{mix}),y_{i})+L_{n}^{reg}+\epsilon^{2}\phi(\epsilon),$
(63)

where $L_{n}^{reg}$ is defined in the theorem. Noting that $\lim_{\epsilon\to
0}\phi(\epsilon)=0$, the proof is done. ∎

##  Appendix C NFM Through the Lens of Implicit Regularization and
Classification Margin

First, we define classification margin at the input level. We shall show that
minimizing the NFM loss can lead to an increase in the classification margin,
and therefore improve model robustness in this sense.

######  Definition 2 (Classification Margin).

The classification margin of a training input-label sample
$s_{i}:=(x_{i},c_{i})$ measured by the Euclidean metric $d$ is defined as the
radius of the largest $d$-metric ball in $\mathcal{X}$ centered at $x_{i}$
that is contained in the decision region associated with the class label
$c_{i}$, i.e., it is: $\gamma^{d}(s_{i})=\sup\\{a:d(x_{i},x)\leq a\Rightarrow
g(x)=c_{i}\ \ \forall x\\}.$

Intuitively, a larger classification margin allows a classifier to associate a
larger region centered on a point $x_{i}$ in the input space to the same
class. This makes the classifier less sensitive to input perturbations, and a
perturbation of $x_{i}$ is still likely to fall within this region, keeping
the classifier prediction. In this sense, the classifier becomes more robust.
In the typical case, the networks are trained by a loss (cross-entropy) that
promotes separation of different classes in the network output. This, in turn,
maximizes a certain notion of score of each training sample [61].

######  Definition 3 (Score).

For an input-label training sample $s_{i}=(x_{i},c_{i})$, we define its score
as $o(s_{i})=\min_{j\neq c_{i}}\sqrt{2}(e_{c_{i}}-e_{j})^{T}f(x_{i})\geq 0,$
where $e_{i}\in\mathbb{R}^{K}$ is the Kronecker delta vector (one-hot vector)
with $e_{i}^{i}=1$ and $e_{i}^{j}=0$ for $i\neq j$.

A positive score implies that at the network output, classes are separated by
a margin that corresponds to the score. A large score may not imply a large
classification margin, but score can be related to classification margin via
the following bound.

######  Proposition 1.

Assume that the score $o(s_{i})>0$ and let $k\in\mathcal{S}$. Then, the
classification margin for the training sample $s_{i}$ can be lower bounded as:

$\gamma^{d}(s_{i})\geq\frac{C(s_{i})}{\sup_{x\in
conv(\mathcal{X})}\|\nabla_{k}f(g_{k}(x))\|_{2}},$ (64)

where $C(s_{i})=o(s_{i})/\sup_{x\in conv(\mathcal{X})}\|\nabla
g_{k}(x)\|_{2}$.

Since NFM implicitly reduces the feature-output Jacobians $\nabla_{k}f$
(including the input-output Jacobian) according to the mixup level and noise
levels (see Proposition 3), this, together with Theorem 1, suggests that
applying NFM implicitly increases the classification margin, thereby making
the model more robust to input perturbations. We note that a similar, albeit
more involved, bound can also be obtained for the all-layer margin, a more
refined version of classification margin introduced in [70], and the
conclusion that applying NFM implicitly increases the margin also holds.

We now prove the proposition.

###### Proof of Proposition 1.

Note that, for any $k\in\mathcal{S},$ $\nabla f(x)=\nabla_{k}f(g_{k}(x))\nabla
g_{k}(x)$ by the chain rule, and so

$\displaystyle\|\nabla f(x)\|_{2}$
$\displaystyle\leq\|\nabla_{k}f(g_{k}(x))\|_{2}\|\nabla g_{k}(x)\|_{2}$ (65)
$\displaystyle\leq\left(\sup_{x\in
conv(\mathcal{X})}\|\nabla_{k}f(g_{k}(x))\|_{2}\right)\left(\sup_{x\in
conv(\mathcal{X})}\|\nabla g_{k}(x)\|_{2}\right).$ (66)

The statement in the proposition follows from a straightforward application of
Theorem 4 in [61] together with the above bound. ∎

##  Appendix D NFM Through the Lens of Probabilistic Robustness

Since the main novelty of NFM lies in the introduction of noise injection, it
would be insightful to isolate the robustness boosting benefits of injecting
noise on top of manifold mixup. We shall demonstrate the isolated benefit in
this section.

The key idea is based on the observation that manifold mixup produces
minibatch outputs that lie in the convex hull of the feature space at each
iteration. Therefore, for $k\in\mathcal{S}$, $NFM(k)$ can be viewed as
injecting noise to the layer $k$ features sampled from some distribution over
$conv(g_{k}(\mathcal{X}))$, and so the $NFM(k)$ neural network $F_{k}$ can be
viewed as a probabilistic mapping from $conv(g_{k}(\mathcal{X}))$ to
$\mathcal{P}(\mathcal{Y})$, the space of probability distributions on
$\mathcal{Y}$.

To isolate the benefit of noise injection, we adapt the approach of [51, 52]
to our setting to show that the Gaussian noise injection procedure in NFM
robustifies manifold mixup in a probabilistic sense. At its core, this
probabilistic notion of robustness amounts to making the model locally
Lipschitz with respect to some distance on the input and output space,
ensuring that a small perturbation in the input will not lead to large changes
(as measured by some probability metric) in the output. Interestingly, it is
related to a notion of differential privacy [42, 15], as formalized in [53].

We now formalize this probabilistic notion of robustness.

Let $p>0$. We say that a standard model $f:\mathcal{X}\to\mathcal{Y}$ is
$\alpha_{p}$-robust if for any $(x,y)\sim\mathcal{D}$ such that $f(x)=y$, one
has, for any data perturbation $\tau\in\mathcal{X}$,

$\|\tau\|_{p}\leq\alpha_{p}\implies f(x)=f(x+\tau).$ (67)

Analogous definition can be formulated when output of the model is
distribution-valued.

######  Definition 4 (Probabilistic robustness).

A probabilistic model $F:\mathcal{X}\to\mathcal{P}(\mathcal{Y)}$ is called
$(\alpha_{p},\epsilon)$-robust with respect to $D$ if, for any
$x,\tau\in\mathcal{X}$, one has

$\|\tau\|_{p}\leq\alpha_{p}\implies D(F(x),F(x+\tau))\leq\epsilon,$ (68)

where $D$ is a metric or divergence between two probability distributions.

We refer to the probabilistic model (built on top of a manifold mixup
classifier) that injects Gaussian noise to the layer $k$ features as
probabilistic FM model, and we denote it by
$F^{noisy(k)}:conv(g_{k}(\mathcal{X}))\to\mathcal{P}(\mathcal{Y})$. We denote
$G$ as the classifier constructed from $F^{noisy(k)}$, i.e.,
$G:x\mapsto\arg\max_{j\in[K]}[F^{noisy(k)}]^{j}(x)$.

In the sequel, we take $D$ to be the total variation distance $D_{TV}$,
defined as:

$D_{TV}(P,Q):=\sup_{S\subset\mathcal{X}}|P(S)-Q(S)|,$ (69)

for any two distributions $P$ and $Q$ over $\mathcal{X}$. Recall that if $P$
and $Q$ have densities $\rho_{p}$ and $\rho_{q}$ respectively, then the total
variation distance is half of the $L^{1}$ distance, i.e.,
$D_{TV}(P,Q)=\frac{1}{2}\int_{\mathcal{X}}|\rho_{p}(x)-\rho_{q}(x)|dx$. The
choice of the distance depends on the problem on hand and will give rise to
different notions of robustness. One could also consider other statistical
distances such as the Wasserstein distance and Renyi divergence, which can be
related to total variation (see [52, 22] for details).

Before presenting our main result in this section, we need the following
notation. Let $\Sigma(x):=\sigma_{add}^{2}I+\sigma_{mult}^{2}xx^{T}$. For
$x,\tau\in\mathcal{X}$, let $\Pi_{x}$ be a $d_{k}$ by $d_{k}-1$ matrix whose
columns form a basis for the subspace orthogonal to $g_{k}(x+\tau)-g_{k}(x)$,
and $\\{\rho_{i}(g_{k}(x),\tau)\\}_{i\in[d_{k}-1]}$ be the eigenvalues of
$(\Pi_{x}^{T}\Sigma(g_{k}(x))\Pi_{x})^{-1}\Pi_{x}^{T}\Sigma(g_{k}(x+\tau))\Pi_{x}-I$.
Also, let $[F]^{topk}(x)$ denote the $k$th highest value of the entries in the
vector $F(x)$.

Viewing an $NFM(k)$ classifier as a probabilistic FM classifier, we have the
following result.

######  Theorem 5 (Gaussian noise injection robustifies FM classifiers).

Let $k\in\mathcal{S}$, $d_{k}>1$, and assume that
$g_{k}(x)g_{k}(x)^{T}\geq\beta_{k}^{2}I>0$ for all $x\in conv(\mathcal{X})$
for some constant $\beta_{k}$. Then, $F^{noisy(k)}$ is
$\left(\alpha_{p},\epsilon_{k}(p,d,\alpha_{p},\sigma_{add},\sigma_{mult})\right)$-robust
with respect to $D_{TV}$ against $l_{p}$ adversaries, with

$\epsilon_{k}(p,d,\alpha_{p},\sigma_{add},\sigma_{mult})=\frac{9}{2}\min\\{1,\max\\{A,B\\}\\},$
(70)

where

$\displaystyle A$
$\displaystyle=A_{p}(\alpha_{p})\frac{\sigma_{mult}^{2}}{\sigma_{add}^{2}+\sigma_{mult}^{2}\beta_{k}^{2}}\bigg{(}\left\|\int_{0}^{1}\nabla
g_{k}(x+t\tau)dt\right\|_{2}^{2}+2\|g_{k}(x)\|_{2}\left\|\int_{0}^{1}\nabla
g_{k}(x+t\tau)dt\right\|_{2}\bigg{)},$ (71) $\displaystyle B$
$\displaystyle=B_{k}(\tau)\frac{\alpha_{p}(\mathbb{1}_{p\in(0,2]}+d^{1/2-1/p}\mathbb{1}_{p\in(2,\infty)}+\sqrt{d}\mathbb{1}_{p=\infty})}{\sqrt{\sigma_{add}^{2}+\sigma_{mult}^{2}\beta_{k}^{2}}},$
(72)

with

$A_{p}(\alpha_{p})=\begin{cases}\alpha_{p}\mathbb{1}_{\alpha_{p}<1}+\alpha_{p}^{2}\mathbb{1}_{\alpha_{p}\geq
1},&\text{if}\ p\in(0,2],\\\
d^{1/2-1/p}(\alpha_{p}\mathbb{1}_{\alpha_{p}<1}+\alpha_{p}^{2}\mathbb{1}_{\alpha_{p}\geq
1}),&\text{if}\ p\in(2,\infty),\\\
\sqrt{d}(\alpha_{p}\mathbb{1}_{\alpha_{p}<1}+\alpha_{p}^{2}\mathbb{1}_{\alpha_{p}\geq
1}),&\text{if}\ p=\infty,\end{cases}$ (73)

and

$B_{k}(\tau)=\sup_{x\in conv(\mathcal{X})}\bigg{(}\left\|\int_{0}^{1}\nabla
g_{k}(x+t\tau)dt\right\|_{2}\cdot\sqrt{\sum_{i=1}^{d_{k}-1}\rho_{i}^{2}(g_{k}(x),\tau)}\bigg{)}.$
(74)

Moreover, if $x\in\mathcal{X}$ is such that
$[F^{noisy(k)}]^{top1}(x)\geq[F^{noisy(k)}]^{top2}(x)+2\epsilon(p,d,\alpha_{p},\sigma_{add},\sigma_{mult})$,
then for any $\tau\in\mathcal{X}$, we have

$\|\tau\|_{p}\leq\alpha\implies G(x)=G(x+\tau),$ (75)

for any $p>0$.

Theorem 5 implies that we can inject Gaussian noise into the feature mixup
representation to improve robustness of FM classifiers in the sense of
Definition 4, while keeping track of maximal loss in accuracy incurred under
attack, by tuning the noise levels $\sigma_{add}$ and $\sigma_{mult}$. To
illustrate this, suppose that $\sigma_{mult}=0$ and consider the case of
$p=2$, in which case $A=0$, $B\sim\alpha_{2}/\sigma_{add}$ and so injecting
additive Gaussian noise can help controlling the change in the model output,
keeping the classifier’s prediction, when the data perturbation is of size
$\alpha_{2}$.

We now prove Theorem 5. Before this, we need the following lemma.

######  Lemma 2.

Let $x_{1}:=z\in\mathbb{R}^{d_{k}}$ and $x_{2}:=z+\tau\in\mathbb{R}^{d_{k}}$,
with $\tau>0$ and $d_{k}>1$, and
$\Sigma(x):=\sigma_{add}^{2}I+\sigma_{mult}^{2}xx^{T}\geq(\sigma_{add}^{2}+\sigma_{mult}^{2}\beta^{2})I>0$,
for some constant $\beta$, for all $x$. Let $\Pi$ be a $d_{k}$ by $d_{k}-1$
matrix whose columns form a basis for the subspace orthogonal to $\tau$, and
let $\rho_{1}(z,\tau),\dots,\rho_{d_{k}-1}(z,\tau)$ denote the eigenvalues of
$(\Pi^{T}\Sigma(x_{1})\Pi)^{-1}\Pi^{T}\Sigma(x_{2})\Pi-I$.

Define the function $C(x_{1},x_{2},\Sigma):=\max\\{A,B\\}$, where

$\displaystyle A$
$\displaystyle=\frac{\sigma_{mult}^{2}}{\sigma_{add}^{2}+\sigma_{mult}^{2}\beta^{2}}(\|\tau\|_{2}^{2}+2\tau^{T}z),$
(76) $\displaystyle B$
$\displaystyle=\frac{\|\tau\|_{2}}{\sqrt{\sigma_{add}^{2}+\sigma_{mult}^{2}\beta^{2}}}\sqrt{\sum_{i=1}^{d_{k}-1}\rho_{i}^{2}(z,\tau)}.$
(77)

Then, the total variation distance between $\mathcal{N}(x_{1},\Sigma(x_{1}))$
and $\mathcal{N}(x_{2},\Sigma(x_{2}))$ admits the following bounds:

$\frac{1}{200}\leq\frac{D_{TV}(\mathcal{N}(x_{1},\Sigma(x_{1})),\mathcal{N}(x_{2},\Sigma(x_{2})))}{\min\\{1,C(x_{1},x_{2},\Sigma)\\}}\leq\frac{9}{2}.$
(78)

###### Proof of Lemma 2.

The result follows from a straightforward application of Theorem 1.2 in [14],
which provides bounds on the total variation distance between Gaussians with
different means and covariances. ∎

With this lemma in hand, we now prove Theorem 5.

###### Proof of Theorem 5.

We denote the noise injection procedure by the map
$\mathcal{I}:x\to\mathcal{N}(x,\Sigma(x))$, where
$\Sigma(x)=\sigma_{add}^{2}I+\sigma_{mult}^{2}xx^{T}$.

Let $x\in\mathcal{X}$ be a test datapoint and $\tau\in\mathcal{X}$ be a data
perturbation such that $\|\tau\|_{p}\leq\alpha_{p}$ for $p>0$.

Note that

$\displaystyle
D_{TV}(F_{k}(\mathcal{I}(g_{k}(x))),F_{k}(\mathcal{I}(g_{k}(x+\tau))))$
$\displaystyle\leq D_{TV}(\mathcal{I}(g_{k}(x)),\mathcal{I}(g_{k}(x+\tau)))$
(79) $\displaystyle\leq
D_{TV}(\mathcal{I}(g_{k}(x)),\mathcal{I}(g_{k}(x)+g_{k}(x+\tau)-g_{k}(x)))$
(80)
$\displaystyle=D_{TV}\left(\mathcal{I}(g_{k}(x)),\mathcal{I}\left(g_{k}(x)+\tau_{k}\right)\right)$
(81)
$\displaystyle\leq\frac{9}{2}\min\\{1,\Phi(g_{k}(x),\tau_{k},\sigma_{add},\sigma_{mult},\beta_{k})\\},$
(82)

where $\tau_{k}:=g_{k}(x+\tau)-g_{k}(x)=\left(\int_{0}^{1}\nabla
g_{k}(x+t\tau)dt\right)\tau$ by the generalized fundamental theorem of
calculus, and

$\displaystyle\Phi(g_{k}(x),\tau_{k},\sigma_{add},\sigma_{mult},\beta_{k})$
$\displaystyle:=\max\left\\{\frac{\sigma_{mult}^{2}}{\sigma_{add}^{2}+\sigma_{mult}^{2}\beta_{k}^{2}}(\|\tau_{k}\|_{2}^{2}+2\langle\tau_{k},g_{k}(x)\rangle),\frac{\|\tau_{k}\|_{2}}{\sqrt{\sigma_{add}^{2}+\sigma_{mult}^{2}\beta_{k}^{2}}}\sqrt{\sum_{i=1}^{d_{k}-1}\rho_{i}^{2}(g_{k}(x),\tau)}\right\\},$
(83)

where the $\rho_{i}(g_{k}(x),\tau)$ are the eigenvalues given in the theorem.

In the first line above, we have used the data preprocessing inequality
(Theorem 6 in [52]), and the last line follows from applying Lemma 2 together
with the assumption that $g_{k}(x)g_{k}(x)^{T}\geq\beta_{k}^{2}>0$ for all
$x$.

Using the bounds

$\displaystyle\|\tau_{k}\|_{2}$ $\displaystyle\leq\left\|\int_{0}^{1}\nabla
g_{k}(x+t\tau)dt\right\|_{2}\|\tau\|_{2}$ (84)

and

$|\langle\tau_{k},g_{k}(x)\rangle|\leq\|g_{k}(x)\|_{2}\left\|\int_{0}^{1}\nabla
g_{k}(x+t\tau)dt\right\|_{2}\|\tau\|_{2},$ (85)

we have

$\displaystyle\Phi(g_{k}(x),\tau_{k},\sigma_{add},\sigma_{mult},\beta_{k})$
$\displaystyle\leq\max\left\\{A,B\right\\},$ (86)

where

$A=\frac{\sigma_{mult}^{2}}{\sigma_{add}^{2}+\sigma_{mult}^{2}\beta_{k}^{2}}\bigg{(}\left\|\int_{0}^{1}\nabla
g_{k}(x+t\tau)dt\right\|_{2}^{2}\|\tau\|_{2}^{2}+2\|g_{k}(x)\|_{2}\left\|\int_{0}^{1}\nabla
g_{k}(x+t\tau)dt\right\|_{2}\|\tau\|_{2}\bigg{)}$ (87)

and

$\displaystyle B$ $\displaystyle=\frac{\left\|\int_{0}^{1}\nabla
g_{k}(x+t\tau)dt\right\|_{2}\|\tau\|_{2}}{\sqrt{\sigma_{add}^{2}+\sigma_{mult}^{2}\beta_{k}^{2}}}\sqrt{\sum_{i=1}^{d_{k}-1}\rho_{i}^{2}(g_{k}(x),\tau)}$
(88) $\displaystyle\leq\sup_{x\in
conv(\mathcal{X})}\bigg{(}\left\|\int_{0}^{1}\nabla
g_{k}(x+t\tau)dt\right\|_{2}\cdot\sqrt{\sum_{i=1}^{d_{k}-1}\rho_{i}^{2}(g_{k}(x),\tau)}\bigg{)}\frac{\|\tau\|_{2}}{\sqrt{\sigma_{add}^{2}+\sigma_{mult}^{2}\beta_{k}^{2}}}$
(89)
$\displaystyle=:B_{k}(\tau)\frac{\|\tau\|_{2}}{\sqrt{\sigma_{add}^{2}+\sigma_{mult}^{2}\beta_{k}^{2}}}.$
(90)

The first statement of the theorem then follows from the facts that
$\|\tau\|_{2}\leq\|\tau\|_{p}\leq\alpha_{p}$ for $p\in(0,2]$,
$\|\tau\|_{2}\leq d^{1/2-1/q}\|\tau\|_{q}\leq d^{1/2-1/q}\alpha_{q}$ for
$q>2$, and
$\|\tau\|_{2}\leq\sqrt{d}\|\tau\|_{\infty}\leq\sqrt{d}\alpha_{\infty}$ for any
$\tau\in\mathbb{R}^{d}$. In particular, these imply that $A\leq CA_{p}$, where

$A_{p}=\begin{cases}\alpha_{p}\mathbb{1}_{\alpha_{p}<1}+\alpha_{p}^{2}\mathbb{1}_{\alpha_{p}\geq
1},&\text{if}\ p\in(0,2],\\\
d^{1/2-1/p}(\alpha_{p}\mathbb{1}_{\alpha_{p}<1}+\alpha_{p}^{2}\mathbb{1}_{\alpha_{p}\geq
1}),&\text{if}\ p\in(2,\infty),\\\
\sqrt{d}(\alpha_{p}\mathbb{1}_{\alpha_{p}<1}+\alpha_{p}^{2}\mathbb{1}_{\alpha_{p}\geq
1}),&\text{if}\ p=\infty,\end{cases}$ (91)

and

$C:=\frac{\sigma_{mult}^{2}}{\sigma_{add}^{2}+\sigma_{mult}^{2}\beta_{k}^{2}}\bigg{(}\left\|\int_{0}^{1}\nabla
g_{k}(x+t\tau)dt\right\|_{2}^{2}+2\|g_{k}(x)\|_{2}\left\|\int_{0}^{1}\nabla
g_{k}(x+t\tau)dt\right\|_{2}\bigg{)}.$ (92)

The last statement in the theorem essentially follows from Proposition 3 in
[52]. ∎

##  Appendix E On Generalization Bounds for NFM

Let $\mathcal{F}$ be the family of mappings $x\mapsto f(x)$ and
$Z_{n}:=((x_{i},y_{i}))_{i\in[n]}$. Given a loss function $l$, the Rademacher
complexity of the set $l\circ\mathcal{F}:=\\{(x,y)\mapsto
l(f(x),y):f\in\mathcal{F}\\}$ is defined as:

$R_{n}(l\circ\mathcal{F}):=\mathbb{E}_{Z_{n},\sigma}\left[\sup_{f\in\mathcal{F}}\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}l(f(x_{i}),y_{i})\right],$
(93)

where $\sigma:=(\sigma_{1},\dots,\sigma_{n})$, with the $\sigma_{i}$
independent uniform random variables taking values in $\\{-1,1\\}$.

Following [41], we can derive the following generalization bound for the NFM
loss function, i.e., the upper bound on the difference between the expected
error on unseen data and the NFM loss. This bound shows that NFM can reduce
overfitting and give rise to improved generalization.

######  Theorem 6 (Generalization bound for the NFM loss).

Assume that the loss function $l$ satisfies $|l(x,y)-l(x^{\prime},y)|\leq M$
for all $x,x^{\prime}$ and $y$. Then, for every $\delta>0$, with probability
at least $1-\delta$ over a draw of $n$ i.i.d. samples
$\\{(x_{i},y_{i})\\}_{i=1}^{n}$, we have the following generalization bound:
for all maps $f\in\mathcal{F}$,

$\mathbb{E}_{x,y}[l(f(x),y)]-L_{n}^{NFM}\leq
2R_{n}(l\circ\mathcal{F})+2M\sqrt{\frac{\ln(1/\delta)}{2n}}-Q_{\epsilon}(f),$
(94)

where

$Q_{\epsilon}(f)=\mathbb{E}[\epsilon
R^{(k)}_{1}+\epsilon^{2}\tilde{R}^{(k)}_{2}+\epsilon^{2}\tilde{R}^{(k)}_{3}]+\epsilon^{2}\varphi(\epsilon),$
(95)

for some function $\varphi$ such that $\lim_{x\to\infty}\varphi(x)=0$.

To compare the generalization behavior of NFM with that without using NFM, we
also need the following generalization bound for the standard loss function.

######  Theorem 7 (Generalization bound for the standard loss).

Assume that the loss function $l$ satisfies $|l(x,y)-l(x^{\prime},y)|\leq M$
for all $x,x^{\prime}$ and $y$. Then, for every $\delta>0$, with probability
at least $1-\delta$ over a draw of $n$ i.i.d. samples
$\\{(x_{i},y_{i})\\}_{i=1}^{n}$, we have the following generalization bound:
for all maps $f\in\mathcal{F}$,

$\mathbb{E}_{x,y}[l(f(x),y)]-L_{n}^{std}\leq
2R_{n}(l\circ\mathcal{F})+2M\sqrt{\frac{\ln(1/\delta)}{2n}}.$ (96)

By comparing the above two theorems and following the argument of [41], we see
that the generalization benefit of NFM comes from two mechanisms. The first
mechanism is based on the term $Q_{\epsilon}(f)$. Assuming that the Rademacher
complexity term is the same for both methods, then NFM has a better
generalization bound than that of standard method if $Q_{\epsilon}(f)>0$. The
second mechanism is based on the Rademacher complexity term
$R_{n}(l\circ\mathcal{F})$. For certain families of neural networks, this term
can be bounded by the norms of the hidden layers of the network and the norms
of the Jacobians of each layer with respect to all previous layers [69, 70].
Therefore, this term differs for the case of training using NFM and the case
of standard training. Since NFM implicitly reduces the feature-output
Jacobians (see Theorem 3), we can argue that NFM leads to a smaller Rademacher
complexity term and hence a better generalization bound.

We now prove Theorem 6. The proof of Theorem 7 follows the same argument as
that of Theorem 6.

###### Proof of Theorem 6.

Let $Z_{n}:=\\{(x_{i},y_{i})\\}_{i\in[n]}$ and
$Z^{\prime}_{n}:=\\{(x^{\prime}_{i},y^{\prime}_{i})\\}_{i\in[n]}$ be two test
datasets, where $Z_{n}^{\prime}$ differs from $Z_{n}$ by exactly one point of
an arbitrary index $i_{0}$.

Denote
$GE(Z_{n}):=\sup_{f\in\mathcal{F}}\mathbb{E}_{x,y}[l(f(x),y)]-L_{n}^{NFM}$,
where $L_{n}^{NFM}$ is computed using the dataset $Z_{n}$, and likewise for
$GE(Z_{n}^{\prime})$. Then,

$GE(Z_{n}^{\prime})-GE(Z_{n})\leq\frac{M(2n-1)}{n^{2}}\leq\frac{2M}{n},$ (97)

where we have used the fact that $L_{n}^{NFM}$ has $n^{2}$ terms and there are
$2n-1$ different terms for $Z_{n}$ and $Z_{n}^{\prime}.$ Similarly, we have
$GE(Z_{n})-GE(Z_{n}^{\prime})\leq\frac{2M}{n}$.

Therefore, by McDiarmid’s inequality, for any $\delta>0$, with probability at
least $1-\delta$,

$GE(Z_{n})\leq\mathbb{E}_{Z_{n}}[GE(Z_{n})]+2M\sqrt{\frac{\ln(1/\delta)}{2n}}.$
(98)

Applying Theorem 3, we have

$\displaystyle GE(Z_{n})$
$\displaystyle\leq\mathbb{E}_{Z_{n}}\left[\sup_{f\in\mathcal{F}}\mathbb{E}_{Z_{n}^{\prime}}\left[\frac{1}{n}\sum_{i=1}^{n}l(f(x_{i}^{\prime}),y_{i}^{\prime})\right]-L_{n}^{NFM}\right]+2M\sqrt{\frac{\ln(1/\delta)}{2n}}$
(99)
$\displaystyle=\mathbb{E}_{Z_{n}}\left[\sup_{f\in\mathcal{F}}\mathbb{E}_{Z_{n}^{\prime}}\left[\frac{1}{n}\sum_{i=1}^{n}l(f(x_{i}^{\prime}),y_{i}^{\prime})\right]-\frac{1}{n}\sum_{i=1}^{n}l(f(x_{i}),y_{i})\right]-Q_{\epsilon}(f)$
$\displaystyle\ \ \ \ +2M\sqrt{\frac{\ln(1/\delta)}{2n}}$ (100)
$\displaystyle\leq\mathbb{E}_{Z_{n},Z_{n}^{\prime}}\left[\sup_{f\in\mathcal{F}}\frac{1}{n}\sum_{i=1}^{n}(l(f(x_{i}^{\prime}),y_{i}^{\prime})-l(f(x_{i}),y_{i}))\right]-Q_{\epsilon}(f)+2M\sqrt{\frac{\ln(1/\delta)}{2n}}$
(101)
$\displaystyle\leq\mathbb{E}_{Z_{n},Z_{n}^{\prime},\sigma}\left[\sup_{f\in\mathcal{F}}\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}(l(f(x_{i}^{\prime}),y_{i}^{\prime})-l(f(x_{i}),y_{i}))\right]-Q_{\epsilon}(f)+2M\sqrt{\frac{\ln(1/\delta)}{2n}}$
(102) $\displaystyle\leq
2\mathbb{E}_{Z_{n},\sigma}\left[\sup_{f\in\mathcal{F}}\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}l(f(x_{i}),y_{i})\right]-Q_{\epsilon}(f)+2M\sqrt{\frac{\ln(1/\delta)}{2n}}$
(103)
$\displaystyle=2R_{n}(l\circ\mathcal{F})-Q_{\epsilon}(f)+2M\sqrt{\frac{\ln(1/\delta)}{2n}},$
(104)

where (99) uses the definition of $GE(Z_{n})$, (100) uses
$\pm\frac{1}{n}\sum_{i=1}^{n}l(f(x_{i}),y_{i})$ inside the expectation and the
linearity of expectation, (101) follows from the Jensen’s inequality and the
convexity of the supremum, (102) follows from the fact that
$\sigma_{i}(l(f(x_{i}^{\prime}),y_{i}^{\prime})-l(f(x_{i}),y_{i}))$ and
$l(f(x_{i}^{\prime}),y_{i}^{\prime})-l(f(x_{i}),y_{i})$ have the same
distribution for each $\sigma_{i}\in\\{-1,1\\}$ (since $Z_{n},Z_{n}^{\prime}$
are drawn i.i.d. with the same distribution), and (103) follows from the
subadditivity of supremum.

The bound in the theorem then follows from the above bound. ∎

##  Appendix F Additional Experiments and Details

###  F.1 Input Perturbations

We consider the following three types of data perturbations during inference
time:

  * •

_White noise perturbations_ are constructed as $\tilde{x}=x+\Delta x$, where
the additive noise is sampled from a Gaussian distribution $\Delta
x\sim\mathcal{N}(0,\sigma)$. This perturbation strategy emulates measurement
errors that can result from data acquisition with poor sensors (where $\sigma$
corresponds to the severity of these errors).

  * •

_Salt and pepper perturbations_ emulate defective pixels that result from
converting analog signals to digital signals. The noise model takes the form
$\mathbb{P}(\tilde{X}=X)=1-\gamma$, and
$\mathbb{P}(\tilde{X}=\max)=\mathbb{P}(\tilde{X}=\min)=\gamma/2,$ where
$\tilde{X}(i,j)$ denotes the corrupted image and $\min$, $\max$ denote the
minimum and maximum pixel values, respectively. $\gamma$ parameterizes the
proportion of defective pixels.

  * •

_Adversarial perturbations_ are “worst-case” non-random perturbations that
maximize the loss $\ell(g^{\delta}(X+\Delta X),y)$ subject to the constraint
$\|\Delta X\|\leq r$ on the norm of the perturbation. We consider the
projected gradient decent for constructing these perturbations [44].

###  F.2 Illustration of the Effects of NFM on Toy Datasets

We consider a binary classification task for the noise corrupted 2D dataset
whose data points form two concentric circles. Points on the same circle
corresponds to the same label class. We generate 500 samples, setting the
scale factor between inner and outer circle to be 0.05 and adding Gaussian
noise with zero mean and standard deviation of 0.3 to the samples. Fig. 7
shows the training and test data points. We train a fully connected
feedforward neural network that has four layers with the ReLU activation
functions on these data, using 300 points for training and 200 for testing.
All models are trained with Adam and learning rate $0.1$, and the seed is
fixed across all experiments. Note that the learning rate can be considered as
a temperature parameter which introduces some amount of regularization itself.
Hence, we choose a learning rate that is large for this problem to better
illustrate the regularization effects imposed by the different schemes that we
consider.

Fig. 2 illustrates how different regularization strategies affect the decision
boundaries of the neural network classifier. The decision boundaries and the
test accuracy indicate that white noise injections and dropout (we explore
dropout rates in the range $[0.0,0.9]$ and we finds that $0.2$ yields the best
performance) introduce a favorable amount of regularization. Most notably is
the effect of weight decay (we use $9e{-3}$), i.e., the decision boundary is
nicely smoothed and the test accuracy is improved. In contrast, the simple
mixup data augmentation scheme shows no benefits here, whereas manifold mixup
is improving the predictive accuracy considerably. Combining mixup (manifold
mixup) with noise injections yields the best performance in terms of both
smoothness of the decision boundary and predictive accuracy. Indeed, NFM is
outperforming all other methods here.

The performance could be further improved by combining NFM with weight decay
or dropout. This shows that there are interaction effects between different
regularization schemes. In practice, when one trains deep neural networks,
different regularization strategies are considered as knobs that are fine-
tuned. From this perspective, NFM provides additional knobs to further improve
a model.

\begin{overpic}[width=433.62pt]{figures/toy_train.pdf} \end{overpic} (a) Data
points for training.

\begin{overpic}[width=433.62pt]{figures/toy_test.pdf} \end{overpic} (b) Data
points for testing.

Figure 7: The toy dataset in $\mathbb{R}^{2}$ that we use for binary
classification.

###  F.3 Additional Results for Vision Transformers

Table 4 shows results for vision transformers trained with different data
augmentation schemes and different values of $\alpha$. It can be seen that NFM
with $\alpha=0.1$ helps to improve the predictive accuracy on clean data while
also improving the robustness of the models. For example, the model trained
with NFM shows about a $25\%$ improvement compared to the baseline model when
faced with salt and paper perturbations ($\gamma=0.2$). Further, our results
indicate that larger values of $\alpha$ have a negative effect on the
generalization performance of vision transformer.

Table 4: Robustness of Wide-ResNet-18 w.r.t. white noise ($\sigma$) and salt
and pepper ($\gamma$) perturbations evaluated on CIFAR-100. The results are
averaged over 5 models trained with different seed values.

Scheme | Clean (%) |  $\sigma$ (%) |  $\gamma$ (%)
---|---|---|---
|  | $0.1$ | $0.2$ | $0.3$ | $0.08$ | $0.12$ | $0.2$
Baseline | 91.3 | 89.4 | 77.0 | 56.7 | 83.2 | 74.6 | 48.6
Mixup ($\alpha=0.1$) [79] | 91.2 | 89.5 | 77.6 | 57.7 | 82.9 | 74.6 | 48.6
Mixup ($\alpha=0.2$) [79] | 91.2 | 89.2 | 77.8 | 58.9 | 82.6 | 74.5 | 47.9
Noisy Mixup ($\alpha=0.1$) [74] | 90.9 | 90.4 | 87.5 | 80.2 | 84.0 | 79.4 | 63.8
Noisy Mixup ($\alpha=0.2$) [74] | 90.9 | 90.4 | 87.4 | 79.8 | 83.8 | 79.3 | 63.4
Manifold Mixup ($\alpha=0.1$) [68] | 91.2 | 89.2 | 77.2 | 56.9 | 83.0 | 74.3 | 47.1
Manifold Mixup ($\alpha=1.0$) [68] | 90.2 | 88.4 | 76.0 | 55.1 | 81.3 | 71.4 | 42.7
Manifold Mixup ($\alpha=2.0$) [68] | 89.0 | 87.0 | 74.3 | 53.7 | 79.8 | 70.3 | 41.9
Noisy Feature Mixup ($\alpha=0.1$) | 91.4 | 90.2 | 88.2 | 84.8 | 84.4 | 81.2 | 74.4
Noisy Feature Mixup ($\alpha=1.0$) | 89.8 | 89.1 | 86.6 | 82.7 | 82.5 | 79.0 | 71.4
Noisy Feature Mixup ($\alpha=2.0$) | 88.4 | 87.6 | 84.6 | 80.1 | 80.4 | 76.5 | 68.6

###  F.4 Additional Results for ResNets with Higher Levels of Noise Injections

In the experiments in Section 5, we considered models trained with NFM that
use noise injection levels $\sigma_{add}=0.4$ and $\sigma_{mult}=0.2$, whereas
the ablation model uses $\sigma_{add}=1.0$ and $\sigma_{mult}=0.5$. Here, we
want to better illustrate the trade-off between accuracy and robustness. We
saw that there exists a potential sweet-spot where we are able to improve both
the predictive accuracy and the robustness of the model. However, if the
primary aim is to push the robustness of the model, then we need to sacrifice
some amount of accuracy.

Fig. 8 is illustrating this trade-off for pre-actived ResNet-18s trained on
CIFAR-10. We can see that increased levels of noise injections considerably
improve the robustness, while the accuracy on clean data points drops. In
practice, the amount of noise injection that the user chooses depend on the
situation. If robustness is critical, than higher noise levels can be used. If
adversarial examples are the main concern, than other training strategies such
as adversarial training might be favorable. However, the advantage of NFM over
adversarial training is that (a) we have a more favorable trade-off between
robustness and accuracy in the small noise regime, and (b) NFM is
computationally inexpensive, when compared to most adversarial training
schemes. This is further illustrated in the next section.

\begin{overpic}[width=433.62pt]{figures/cifar10_white_high.pdf}
\put(-6.0,16.0){\rotatebox{90.0}{ Test Accuracy}} \put(31.0,-3.0){ {White
Noise ($\sigma$)}} \end{overpic}

\begin{overpic}[width=433.62pt]{figures/cifar10_sp_high.pdf} \put(31.0,-3.0){
{Salt and Pepper Noise ($\gamma$)}} \end{overpic}

Figure 8: Pre-actived ResNet-18 evaluated on CIFAR-10 trained with NFM and
varying levels of additive ($\sigma_{add}$) and multiplicative
($\sigma_{mult}$) noise injections. Shaded regions indicate one standard
deviation about the mean. Averaged across 5 random seeds.

###  F.5 Comparison with Adversarial Trained Models

Here, we compare NFM to adversarial training in the small noise regime, i.e.,
the situation where models do not show a significant drop on the clean test
set. Specifically, we consider the projected gradient decent (PGD) method [44]
using $7$ attack iterations and varying $l_{2}$ perturbation levels $\epsilon$
to train adversarial robust models. First, we compare how resilient the
different models are with respect to adversarial input perturbations during
inference time (Fig. 9; left). Again the adversarial examples are constructed
using the PGD method with $7$ attack iterations. Not very surprisingly, the
adversarial trained model with $\epsilon=0.01$ features the best resilience
while sacrificing about $0.5\%$ accuracy as compared to the baseline model
(here not shown). In contrast, the models trained with NFM are less robust,
while being about $1-1.5\%$ more accurate on clean data.

Next, we compare in (Fig. 9; right) the robustness with respect to salt and
pepper perturbations, i.e., perturbations that both models have not seen
before. Interestingly, here we see an advantage of the NFM scheme with high
noise injection levels as compared to the adversarial trained models.

\begin{overpic}[width=433.62pt]{figures/cifar10_adv_comp.pdf}
\put(-6.0,16.0){\rotatebox{90.0}{ Test Accuracy}} \put(31.0,-3.0){
{Adverserial Noise ($\epsilon$)}} \end{overpic}

\begin{overpic}[width=433.62pt]{figures/cifar10_adv_comp_sp.pdf}
\put(31.0,-3.0){ {Adverserial Noise ($\epsilon$)}} \end{overpic}

Figure 9: Pre-actived ResNet-18 evaluated on CIFAR-10 (left) and Wide
ResNet-18 evaluated on CIFAR-100 (right) with respect to adversarial perturbed
inputs. Shaded regions indicate one standard deviation about the mean.
Averaged across 5 random seeds.

###  F.6 Feature Visualization Comparison

In this subsection, we concern ourselves with comparing the features learned
by three ResNet-50 models trained on Restricted Imagenet [65]: without mixup,
manifold mixup [68], and NFM. We can compare features by maximizing randomly
chosen pre-logit activations of each model with respect to the input, as
described by [19]. We do so for all models with Projected Gradient Ascent over
200 iterations, a step size of 16, and an $\ell_{2}$ norm constraint of 2,000.
Both the models trained with manifold mixup and NFM use an $\alpha=0.2$, and
the NFM model uses in addition $\sigma_{add}=2.4$ and $\sigma_{mult}=1.2$. The
result, as shown in Fig. 10, is that the features learned by the model trained
with NFM are slightly stronger (i.e., different from random noise) than the
clean model.

\begin{overpic}[width=238.49231pt]{figures/feature_viz.pdf} \end{overpic}
Figure 10: The features learned by the NFM classifier are slightly stronger
(i.e., different from random noise) than the clean model. See Subsection F.6
for more details.