Year: 2021

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.

heading: 1 INTRODUCTION
text: 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 or data). Noise injection is a typical example of data-agnostic regularization (Bishop, 1995), where noise can be injected into the input data (An, 1996), or the activation functions (Gulcehre et al., 2016), or the hidden layers of deep neural networks (Camuto et al., 2020; Lim et al., 2021). Data augmentation constitutes a different class of regularization methods (Baird, 1992; Chapelle et al., 2001; DeCoste & Schölkopf, 2002), 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 (Cireşan et al., 2010; Krizhevsky et al., 2012). The recently-proposed data-agnostic method, mixup (Zhang et al., 2017), 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 (Zhang et al., 2020; Carratino et al., 2020; Lim et al., 2021), which is critical for many safety and sensitive applications (Goodfellow et al., 2018; Madry et al., 2017).
In this paper, we propose and study a simple 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 it can be seen as a generalization of input mixup (Zhang et al., 2017) and manifold mixup (Verma et al., 2019). 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-theart architectures on computer vision benchmark tasks.
In the 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, . . . ,K}, the superscript T denotes transposition, ◦ denotes composition, denotes Hadamard product, 1 denotes the vector with all components equal one. For a vector v, vk denotes its kth component and ‖v‖p denotes its lp norm for p > 0. conv(X ) denote the convex hull of X . Mλ(a, b) := λa+ (1−λ)b, for random variables a, b, λ. δz denotes the Dirac delta function, defined as δz(x) = 1 if x = z and δz(x) = 0 otherwise. 1A denotes indicator function of the set A. For α, β > 0, D̃λ := αα+βBeta(α + 1, β) + β α+βBeta(β + 1, α) denotes a uniform mixture of two Beta distributions. For two vectors a, b, cos(a, b) := 〈a, b〉/‖a‖2‖b‖2 denotes their cosine similarity. N (a, b) is a Gaussian distribution with mean a and covariance b.

heading: 2 RELATED WORK
text: Regularization. Regularization refers to any technique that reduces overfitting in machine learning; see (Mahoney & Orecchia, 2011; Mahoney, 2012) 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 (Shorten & Khoshgoftaar, 2019). A recently proposed technique is mixup (Zhang et al., 2017), where the examples are created by taking convex combinations of pairs of inputs and their labels. Verma et al. (2019) extends mixup to hidden representations in deep neural networks. Subsequent works by Greenewald et al. (2021); Yin et al. (2021); Engstrom et al. (2019); Kim et al. (2020a); Yun et al. (2019); Hendrycks et al. (2019) introduce different variants and extensions of mixup. Regularization is also intimately connected to robustness (Hoffman et al., 2019; Sokolić et al., 2017; Novak et al., 2018; Elsayed et al., 2018; Moosavi-Dezfooli et al., 2019). 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 (Kurakin et al., 2016) can be achieved by adversarial training (Goodfellow et al., 2014; Madry et al., 2017; Utrera et al., 2020). Several works present theoretical justifications to observed robustness and how data augmentation can improve it (Hein & Andriushchenko, 2017; Yang et al., 2020b; Couellan, 2021; Pinot et al., 2019a; 2021; Zhang et al., 2020; 2021; Carratino et al., 2020; Kimura, 2020; Dao et al., 2019; Wu et al., 2020; Gong et al., 2020; Chen et al., 2020). Relatedly, Fawzi et al. (2016); Franceschi et al. (2018); Lim et al. (2021) 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 is the study of the trade-offs between robustness and accuracy (Min et al., 2020; Zhang et al., 2019; Tsipras et al., 2018; Schmidt et al., 2018; Su et al., 2018; Raghunathan et al., 2020; Yang et al., 2020a).

heading: 3 NOISY FEATURE MIXUP
text: Noisy Feature Mixup is a generalization of input mixup (Zhang et al., 2017) and manifold mixup (Verma et al., 2019). 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 modification alters the region in which the resulting augmented data resides. Fig. 2 shows that NFM is 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.
Formally, we consider multi-class classification with K labels. Denote the input space by X ⊂ Rd and the output space by Y = RK . The classifier, g, is constructed from a learnable map f : X → RK , mapping an input x to its label, g(x) = arg maxk fk(x) ∈ [K]. We are given a training set, Zn := {(xi, yi)}ni=1, consisting of n pairs of input and one-hot label, with each training pair zi := (xi, yi) ∈ X × Y drawn i.i.d. from a ground-truth distribution D. We consider training a deep neural network f := fk ◦ gk, where gk : X → gk(X ) maps an input to a hidden representation at layer k, and fk : gk(X )→ gL(X ) := Y maps the hidden representation to a one-hot label at layer L. Here, gk(X ) ⊂ Rdk for k ∈ [L], dL := K, g0(x) = x and f0(x) = f(x). Training f using NFM consists of the following steps:
1. Select a random layer k from a set, S ⊂ {0} ∪ [L], of eligible layers in the neural network. 2. Process two random data minibatches (x, y) and (x′, y′) as usual, until reaching layer k. This
gives us two immediate minibatches (gk(x), y) and (gk(x′), y′).
3. Perform mixup on these intermediate minibatches, producing the mixed minibatch:
(g̃k, ỹ) := (Mλ(gk(x), gk(x ′)),Mλ(y, y ′)), (1)
where the mixing level λ ∼ Beta(α, β), with the hyper-parameters α, β > 0. 4. Produce noisy mixed minibatch by injecting additive and multiplicative noise:
(˜̃gk, ỹ) := ((1 + σmultξ mult k ) Mλ(gk(x), gk(x′)) + σaddξaddk ,Mλ(y, y′)), (2)
where the ξaddk and ξ mult k are R dk -valued independent random variables modeling the additive and multiplicative noise respectively, and σadd, σmult ≥ 0 are pre-specified noise levels.
5. Continue the forward pass from layer k until the output using the noisy mixed minibatch (˜̃gk, ỹ).
6. Compute the loss and gradients that update all the parameters of the network.
At the level of implementation, following (Verma et al., 2019), we backpropagate gradients through the entire computational graph, including those layers before the mixup layer k.
In the case where σadd = σmult = 0, NFM reduces to manifold mixup (Verma et al., 2019). If in addition S = {0}, it reduces to the original mixup method (Zhang et al., 2017). 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 gk(x), gk(x′) 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 S in our formulation. Within the above setting, we consider the expected NFM loss:
LNFM (f) = E(x,y),(x′,y′)∼DEk∼SEλ∼Beta(α,β)Eξk∼Ql(fk(Mλ,ξk(gk(x), gk(x ′))),Mλ(y, y ′)),
where l : RK × RK → [0,∞) is a loss function (note that here we have suppressed the dependence of both l and f on the learnable parameter θ in the notation), ξk := (ξaddk , ξ mult k ) are drawn from some probability distribution Q with finite first two moments, and Mλ,ξk(gk(x), gk(x ′)) := (1 + σmultξ mult k ) Mλ(gk(x), gk(x′)) + σaddξaddk .
NFM seeks to minimize a stochastic approximation of LNFM (f) by sampling a finite number of k, λ, ξk values and using minibatch gradient descent to minimize this loss approximation.

heading: 4 THEORY
text: 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 (Rice et al., 2020).

heading: 4.1 NFM: BEYOND EMPIRICAL RISK MINIMIZATION
text: The standard approach in statistical learning theory (Bousquet et al., 2003) is to select a hypothesis function f : X → Y from a pre-defined hypothesis class F to minimize the expected risk with respect to D and to solve the risk minimization problem: inff∈F R(f) := E(x,y)∼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 D is approximated by the empirical distribution Pn = 1n ∑n i=1 δzi . In other words, in
ERM we solve the problem: inff∈F Rn(f) := 1n ∑n i=1 l(f(xi), yi).
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 (Vapnik, 2013) 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 (Chapelle et al., 2001).
Input mixup (Zhang et al., 2017) 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 An (1996); Camuto et al. (2020); Lim et al. (2021). 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.

heading: 4.2 IMPLICIT REGULARIZATION OF NFM
text: 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 := fk ◦ gk. Denote Lstdn := 1 n ∑n i=1 l(f(xi), yi) and let Dx be the empirical distribution of training samples {xi}i∈[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 > 0 be a small parameter. In the sequel, we rescale 1 − λ 7→ (1 − λ), σadd 7→ σadd, σmult 7→ σmult, and denote ∇kf and ∇2kf as the first and second directional derivative of fk with respect to gk respectively, for k ∈ S. By working in the small parameter regime, we can relate the NFM empirical loss LNFMn to the original loss L std n and identify the regularizing effects of NFM.
Theorem 1. Let > 0 be a small parameter, and assume that h and f are twice differentiable. Then, LNFMn = Ek∼SL NFM(k) n , where
LNFM(k)n = L std n + R (k) 1 + 2R̃ (k) 2 + 2R̃ (k) 3 + 2ϕ( ), (3)
with R̃(k)2 = R (k) 2 +σ 2 addR add(k) 2 +σ 2 multR mult(k) 2 and R̃ (k) 3 = R (k) 3 +σ 2 addR add(k) 3 +σ 2 multR mult(k) 3 , where
R add(k) 2 =
1
2n n∑ i=1 h′′(f(xi))∇kf(gk(xi))TEξk [ξaddk (ξaddk )T ]∇kf(gk(xi)), (4)
R mult(k) 2 =
1
2n n∑ i=1 h′′(f(xi))∇kf(gk(xi))T (Eξk [ξmultk (ξmultk )T ] gk(xi)gk(xi)T )∇kf(gk(xi)),
(5)
R add(k) 3 =
1
2n n∑ i=1 (h′(f(xi))− yi)Eξk [(ξaddk )T∇2kf(gk(xi))ξaddk ], (6)
R mult(k) 3 =
1
2n n∑ i=1 (h′(f(xi))− yi)Eξk [(ξmultk gk(xi))T∇2kf(gk(xi))(ξmultk gk(xi))]. (7)
Here, Rk1 , R k 2 and R k 3 are the regularizers associated with the loss of manifold mixup (see Theorem 3 in SM for their explicit expression), and ϕ is some function such that lim →0 ϕ( ) = 0.
Theorem 1 implies that, when compared to manifold mixup, NFM introduces additional smoothness, regularizing the directional derivatives, ∇kf(gk(xi)) and ∇2kf(gk(xi)), with respect to gk(xi), according to the noise levels σadd and σmult, and amplifying the regularizing effects of manifold mixup and noise injection. In particular, making ∇2f(xi) small can lead to smooth decision boundaries (at the input level), while reducing the confidence of model predictions. On the other hand, making the∇kf(gk(xi)) small can lead to improvement in model robustness, which we discuss next.

heading: 4.3 ROBUSTNESS OF NFM
text: 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 Zhang et al. (2017); Lamb et al. (2019), 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) (Kwon et al., 2020; Kuhn et al., 2019; Rahimian & Mehrotra, 2019) (see also Proposition 3.1 in (Staib & Jegelka, 2017)). 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 (Lamb et al., 2019), we consider the binary cross-entropy loss, setting h(z) = log(1 + ez), with the labels y taking value in {0, 1} and the classifier model f : Rd → R. In the following, we
assume that the model parameter θ ∈ Θ := {θ : yif(xi) + (yi − 1)f(xi) ≥ 0 for all i ∈ [n]}. Note that this set contains the set of all parameters with correct classifications of training samples (before applying NFM), since {θ : 1{f(xi)≥0} = yi for all i ∈ [n]} ⊂ Θ. Therefore, the condition of θ ∈ Θ 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 θ ∈ Θ. Working in the data-dependent parameter space Θ, we have the following result. Theorem 2. Let θ ∈ Θ := {θ : yif(xi) + (yi− 1)f(xi) ≥ 0 for all i ∈ [n]} such that∇kf(gk(xi)) and ∇2kf(gk(xi)) exist for all i ∈ [n], k ∈ S. Assume that fk(gk(xi)) = ∇kf(gk(xi))T gk(xi), ∇2kf(gk(xi)) = 0 for all i ∈ [n], k ∈ S. In addition, suppose that ‖∇f(xi)‖2 > 0 for all i ∈ [n], Er∼Dx [gk(r)] = 0 and ‖gk(xi)‖2 ≥ c (k) x √ dk for all i ∈ [n], k ∈ S. Then,
LNFMn ≥ 1
n n∑ i=1 max ‖δi‖2≤ mixi l(f(xi + δi), yi) + L reg n + 2φ( ), (8)
where
mixi := Eλ∼D̃λ [1− λ] · Ek∼S [ r (k) i c (k) x ‖∇kf(gk(xi))‖2 ‖∇f(xi)‖2 √ dk ] (9)
and Lregn := 1 2n ∑n i=1 |h′′(f(xi))|( reg i ) 2, with r(k)i := | cos(∇kf(gk(xi)), gk(xi))| and
( regi ) 2 := 2‖∇kf(gk(xi))‖22 ( Eλ[(1− λ)]2Exr [‖gk(xr)‖22 cos(∇kf(gk(xi)), gk(xr))2]
+ σ2addEξk [‖ξaddk ‖22 cos(∇kf(gk(xi)), ξaddk )2] + σ2multEξk [‖ξmultk gk(xi)‖22 cos(∇kf(gk(xi)), ξmultk gk(xi))2] ) , (10)
and φ is some function such that lim →0 φ( ) = 0.
The second assumption stated in Theorem 2 is similar to the one made in Lamb et al. (2019); Zhang et al. (2020), 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 l2 attack of size mix = mini∈[n] mixi , plus a feature-dependent regularization term Lregn (see SM for further discussions). 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 (Rice et al., 2020; Rebuffi et al., 2021).
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.

heading: 5 EMPIRICAL RESULTS
text: 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 Section F).
We evaluate the average performance of NFM with different model architectures on CIFAR10 (Krizhevsky, 2009), CIFAR-100 (Krizhevsky, 2009), ImageNet (Deng et al., 2009), and CIFAR10c (Hendrycks & Dietterich, 2019). We use a pre-activated residual network (ResNet) with depth 18 (He et al., 2016) on small scale tasks. For more challenging tasks, we consider the performance of wide ResNet-18 (Zagoruyko & Komodakis, 2016) and ResNet-50 architectures, respectively.
Baselines. We evaluate against related data augmentation schemes that have shown performance improvements in recent years: mixup (Zhang et al., 2017); manifold mixup (Verma et al., 2019);
cutmix (Yun et al., 2019); puzzle mixup (Kim et al., 2020b); and noisy mixup (Yang et al., 2020b). Further, we compare to vanilla models trained without data augmentation (baseline), models trained with label smoothing, 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 keep α fixed, i.e., the parameter defining Beta(α, α), from which the λ parameter controlling the convex combination between data point pairs is sampled. Across all models trained with NFM, we control the level of noise injections by fixing the additive noise level to σadd = 0.4 and multiplicative noise to σmult = 0.2. To demonstrate the significant improvements on robustness upon the introduction of these small input perturbations, we show a second model (‘*’) that was injected with higher noise levels (i.e., σadd = 1.0, σmult = 0.5). See SM (Section F.5) for further details and comparisons against NFM models trained on various other levels of noise injections.

heading: 5.1 CIFAR10
text: Pre-activated ResNet-18. Table 1 summarizes the performance improvements and indicates a consistent robustness across different α 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).

heading: 5.2 CIFAR-100
text: Wide ResNet-18. Previous work indicates that data augmentation has a positive effect on performance for this dataset (Zhang et al., 2017). Fig. 4 (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 (Tsipras et al., 2018). However, we demonstrate NFM has the ability to improve both accuracy and robustness. Table 2 indicates that for the same α, NFM can achieve an average test accuracy of 80.9% compared to only 80.3% in the mixup setting.

heading: 5.3 IMAGENET
text: 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.

heading: 5.4 CIFAR-10C
text: In Figure 6 we use the CIFAR-10C dataset (Hendrycks & Dietterich, 2019) to demonstrate that models trained with NFM are more robust to a range of perturbations on natural images. Figure 6 (left) shows
the average test accuracy across six selected perturbations and demonstrates the advantage of NFM being particularly pronounced with the progression of severity levels. The right figure shows the performance on the same set of six perturbations for the median severity level 3. NFM excels on Gaussian, impulse, speckle and shot noise, and is competitive with the rest on the snow perturbation.

heading: 5.5 ROBUSTNESS TO ADVERSARIAL EXAMPLES
text: So far we have only considered white noise and salt and pepper perturbations. We further consider adversarial perturbations. Here, we use projected gradient decent (Madry et al., 2017) with 7 iterations and various levels to construct the adversarial perturbations. Fig. 5 highlights the improved resilience of ResNets trained with NFM to adversarial input perturbations and shows this consistently on both 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.6, we compare NFM to models that are adversarially trained. 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.

heading: 6 CONCLUSION
text: 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 Thulasidasan et al. (2019); Zhang et al. (2021).

heading: CODE OF ETHICS
text: We acknowledge that we have read and commit to adhering to the ICLR Code of Ethics.

heading: REPRODUCIBILITY
text: The code that can be used to reproduce the empirical results, as well as description of the data processing steps, presented in this paper is available as a zip file in Supplementary Material at OpenReview.net. For the theoretical results, all assumptions, proofs and the related discussions are provided in SM.

heading: A NFM THROUGH THE LENS OF VICINAL RISK MINIMIZATION
text: 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 Zn = {z1, . . . , zn} be a feature set. We say that P′n is an ei-randomly perturbed feature distribution if there exists a set {z′1, . . . , z′n} such that P′n = 1 n ∑n i=1 δz′i , with z ′ i = zi + ei, for some random variable ei (possibly dependent on Zn) drawn from a probability distribution.
Note that the support of an ei-randomly perturbed feature distribution may be larger than that of Z . If Zn is an input dataset and the ei are bounded variables such that ‖ei‖ ≤ β for some β ≥ 0, then P′n is a β-locally perturbed data distribution according to Definition 2 in (Kwon et al., 2020). Examples of β-locally perturbed data distribution include that associated with denoising autoencoder, input mixup, and adversarial training (see Example 1-3 in (Kwon et al., 2020)). Definition 1 can be viewed as an extension of the definition in (Kwon et al., 2020), relaxing the boundedness condition on the ei to cover a wide families of perturbed feature distribution. One simple example is the Gaussian distribution, i.e., when ei ∼ N (0, σ2i ), 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 > 0 be a small parameter and rescale 1− λ 7→ (1− λ), σadd 7→ σadd and σmult 7→ σmult. Let Fk be the family of mappings from gk(X ) to Y and consider the VRM:
inf fk∈Fk Rn(fk) := E(g′k(x),y′)∼P(k)n [l(fk(g ′ k(x))), y ′)], (11)
where P(k)n = 1n ∑n i=1 δ(g′k(xi),y′i), with g ′ k(xi) = gk(xi) + e NFM(k) i and y ′ i = yi + e y i , for some random variables eNFM(k)i and e y i .
In NFM, we approximate the ground-truth distribution D using the family of distributions {P(k)n }k∈S , with a particular choice of (eNFM(k)i , e y i ). In the sequel, we denote NFM at the level of kth layer as NFM(k) (i.e., the particular case when S := {k}).
The following lemma identifies the (eNFM(k)i , e y i ) associated with NFM(k) and relates the effects of NFM(k) to those of mixup and noise injection, for any perturbation level > 0.
Lemma 1. Let > 0 and denote zi(k) := gk(xi). Learning the neural network map f using NFM(k) is a VRM with the ( eNFM(k)i , e y i )-randomly perturbed feature distribution, P (k) n = 1 n ∑n i=1 δ(z′i(k),y′i), with z ′ i(k) := zi(k)+ e NFM(k) i , y ′ i := yi+ e y i , as the vicinal distribution. Here, eyi = (1− λ)(ỹi − yi),
e NFM(k) i = (1 + σmultξmult) e mixup(k) i + e noise(k) i , (12)
where emixup(k)i = (1− λ)(z̃i(k)− zi(k)), and e noise(k) i = σmultξmult zi(k) + σaddξadd, with zi(k), z̃i(k) ∈ gk(X ), λ ∼ Beta(α, β) and yi, ỹi ∈ Y . Here, (z̃i(k), 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 ξadd, ξmult to be independent standard Gaussian random variables, in which case we have enoise(k)i ∼ N (0, σ2addI + σ2multdiag(zi(k))2), and ei ∼ N (0, σ2add + σ2multMλ(zi(k), z̃i(k))2) in Lemma 1. We now prove Lemma 1.
Proof of Lemma 1. Let k be given and set = 1 without loss of generality. For every i ∈ [n], NFM(k) injects noise on top of a mixed sample z′i(k) and outputs:
z′′i (k) = (1 + σmultξmult) z′i(k) + σaddξadd (13) = (1 + σmultξmult) (λzi(k) + (1− λ)z̃i(k)) + σaddξadd (14)
= zi(k) + e NFM(k) i , (15)
where eNFM(k)i = (1− λ)(z̃i(k)− zi(k)) + σmultξmult (λzi(k) + (1− λ)z̃i(k)) + σaddξadd.
Now, note that applying mixup to the pair (zi(k), z̃i(k)) results in z′i(k) = zi(k) + e mixup(k) i , with e mixup(k) i = (1 − λ)(z̃i(k) − zi(k)), where zi(k), z̃i(k) ∈ gk(X ) and λ ∼ Beta(α, β), whereas applying noise injection to zi(k) results in (1 +σmultξmult) zi(k) +σaddξadd = zi(k) +enoise(k)i , with enoise(k)i = σmultξmult zi(k) + σaddξadd. Rewriting e NFM(k) i in terms of e mixup(k) i and e noise(k) i gives
e NFM(k) i = (1 + σmultξmult) e mixup(k) i + e noise(k) i . (16)
Similarly, we can derive the expression for eyi using the same argument. The results in the lemma follow upon applying the rescaling 1 − λ 7→ (1 − λ), σadd 7→ σadd and σmult 7→ σmult, for > 0.

heading: B STATEMENTS AND PROOF OF THE RESULTS IN THE MAIN PAPER

heading: B.1 COMPLETE STATEMENT OF THEOREM 1 IN THE MAIN PAPER AND THE PROOF
text: We first state the complete statement of Theorem 1 in the main paper.
Theorem 3 (Theorem 1 in the main paper). Let > 0 be a small parameter, and assume that h and f are twice differentiable. Then, LNFMn = Ek∼SL NFM(k) n , where
LNFM(k)n = L std n + R (k) 1 + 2R̃ (k) 2 + 2R̃ (k) 3 + 2ϕ( ), (17)
with
R̃ (k) 2 = R (k) 2 + σ 2 addR add(k) 2 + σ 2 multR mult(k) 2 , (18)
R̃ (k) 3 = R (k) 3 + σ 2 addR add(k) 3 + σ 2 multR mult(k) 3 , (19)
where
R (k) 1 = Eλ∼D̃λ [1− λ] n n∑ i=1 (h′(f(xi)− yi)∇kf(gk(xi))TExr∼Dx [gk(xr)− gk(xi)], (20)
R (k) 2 =
Eλ∼D̃λ [(1− λ) 2]
2n
n∑ i=1 h′′(f(xi))∇kf(gk(xi))T
× Exr∼Dx [(gk(xr)− gk(xi))(gk(xr)− gk(xi))T ]∇kf(gk(xi)), (21)
R (k) 3 =
Eλ∼D̃λ [(1− λ) 2]
2n
n∑ i=1 (h′(f(xi))− yi)
× Exr∼Dx [(gk(xr)− gk(xi))T∇2kf(gk(xi))(gk(xr)− gk(xi))], (22)
R add(k) 2 =
1
2n n∑ i=1 h′′(f(xi))∇kf(gk(xi))TEξk [ξaddk (ξaddk )T ]∇kf(gk(xi)), (23)
R mult(k) 2 =
1
2n n∑ i=1 h′′(f(xi))∇kf(gk(xi))T (Eξk [ξmultk (ξmultk )T ] gk(xi)gk(xi)T )∇kf(gk(xi)),
(24)
R add(k) 3 =
1
2n n∑ i=1 (h′(f(xi))− yi)Eξk [(ξaddk )T∇2kf(gk(xi))ξaddk ], (25)
R mult(k) 3 =
1
2n n∑ i=1 (h′(f(xi))− yi)Eξk [(ξmultk gk(xi))T∇2kf(gk(xi))(ξmultk gk(xi))], (26)
and ϕ( ) = Eλ∼D̃λExr∼DxEξk∼Q[ϕ( )], with ϕ some function such that lim →0 ϕ( ) = 0.
Following the setup of Zhang et al. (2020), we provide empirical results to show that the second order Taylor approximation for the NFM loss function is generally accurate (see Figure 7).
Recall from the main paper that the NFM loss function to be minimized is LNFMn = Ek∼SL NFM(k) n , where
LNFM(k)n = 1
n2 n∑ i=1 n∑ j=1 Eλ∼Beta(α,β)Eξk∼Ql(fk(Mλ,ξk(gk(xi), gk(xj))),Mλ(yi, yj)), (27)
where l : RK × RK → [0,∞) is a loss function of the form l(f(x), y) = h(f(x)) − yf(x), ξk := (ξ add k , ξ mult k ) are drawn from some probability distribution Q with finite first two moments (with zero mean), and Mλ,ξk(gk(x), gk(x ′)) := (1 + σmultξ mult k ) Mλ(gk(x), gk(x′)) + σaddξaddk . (28)
Before proving Theorem 3, we note that, following the argument of the proof of Lemma 3.1 in Zhang et al. (2020), the loss function minimized by NFM can be written as follows. For completeness, we provide all details of the proof.
Lemma 2. The NFM loss (27) can be equivalently written as LNFMn = Ek∼SL NFM(k) n , where
LNFM(k)n = 1
n n∑ i=1 Eλ∼D̃λExr∼DxEξk∼Q[h(fk(gk(xi)+ e NFM(k) i ))−yifk(gk(xi)+ e NFM(k) i )],
(29) with
e NFM(k) i = (1 + σmultξ mult k ) e mixup(k) i + e noise(k) i . (30)
Here emixup(k)i = (1−λ)(gk(xr)− gk(xi)) and e noise(k) i = σmultξ mult k gk(xi) +σaddξaddk , with gk(xi), gk(xr) ∈ gk(X ) and λ ∼ Beta(α, β).
Proof of Lemma 2. From (27), we have:
LNFM(k)n = 1
n2 n∑ i=1 n∑ j=1 Eλ∼Beta(α,β)Eξk∼Ql(fk(Mλ,ξk(gk(xi), gk(xj))),Mλ(yi, yj)). (31)
We can rewrite: Eλ∼Beta(α,β)l(fk(Mλ,ξk(gk(xi), gk(xj))),Mλ(yi, yj))
= Eλ∼Beta(α,β)[h(fk(Mλ,ξk(gk(xi), gk(xj))))−Mλ(yi, yj)fk(Mλ,ξk(gk(xi), gk(xj)))] (32) = Eλ∼Beta(α,β)[λ(h(fk(Mλ,ξk(gk(xi), gk(xj))))− yifk(Mλ,ξk(gk(xi), gk(xj))))
+ (1− λ)(h(fk(Mλ,ξk(gk(xi), gk(xj))))− yjfk(Mλ,ξk(gk(xi), gk(xj))))] (33) = Eλ∼Beta(α,β)EB∼Bern(λ)[B(h(fk(Mλ,ξk(gk(xi), gk(xj))))− yifk(Mλ,ξk(gk(xi), gk(xj))))
+ (1−B)(h(fk(Mλ,ξk(gk(xi), gk(xj))))− yjfk(Mλ,ξk(gk(xi), gk(xj))))], (34) where Bern(λ) denotes the Bernoulli distribution with parameter λ (i.e., P[B = 1] = λ and P[B = 0] = 1− λ). Note that λ ∼ Beta(α, β) and B|λ ∼ Bern(λ). By conjugacy, we can switch their order:
B ∼ Bern ( α
α+ β
) , λ|B ∼ Beta(α+B, β + 1−B), (35)
and arrive at: Eλ∼Beta(α,β)l(fk(Mλ,ξk(gk(xi), gk(xj))),Mλ(yi, yj))
= EB∼Bern( αα+β ) Eλ∼Beta(α+B,β+1−B)[B(h(fk(Mλ,ξk(gk(xi), gk(xj))))
− yifk(Mλ,ξk(gk(xi), gk(xj)))) + (1−B)(h(fk(Mλ,ξk(gk(xi), gk(xj))))− yjfk(Mλ,ξk(gk(xi), gk(xj))))] (36)
= α
α+ β Eλ∼Beta(α+1,β)[h(fk(Mλ,ξk(gk(xi), gk(xj))))− yifk(Mλ,ξk(gk(xi), gk(xj)))]
+ β
α+ β Eλ∼Beta(α,β+1)[h(fk(Mλ,ξk(gk(xi), gk(xj))))− yjfk(Mλ,ξk(gk(xi), gk(xj)))].
(37)
Using the facts that Beta(β + 1, α) and 1 − Beta(α, β + 1) are of the same distribution and M1−λ(xi, xj) = Mλ(xj , xi), we have:∑
i,j
Eλ∼Beta(α,β+1)[h(fk(Mλ,ξk(gk(xi), gk(xj))))− yjfk(Mλ,ξk(gk(xi), gk(xj)))]
= ∑ i,j Eλ∼Beta(β+1,α)[h(fk(Mλ,ξk(gk(xi), gk(xj))))− yifk(Mλ,ξk(gk(xi), gk(xj)))]. (38)
Therefore, denoting D̃λ := αα+βBeta(α+ 1, β) + β α+βBeta(β + 1, α) and Dx := 1 n ∑n j=1 δxj the empirical distribution induced by the training samples {xj}j∈[n], we have:
LNFM(k)n = 1
n n∑ i=1 Eλ∼D̃λExr∼DxEξk∼Q[h(fk(Mλ,ξk(gk(xi), gk(xr))))
− yifk(Mλ,ξk(gk(xi), gk(xr)))]. (39)
The statement of the lemma follows upon substituting the fact thatMλ,ξk(gk(xi), gk(xr)) = gk(xi)+ e NFM(k) i into the above equation.
With this lemma in hand, we now prove Theorem 3.
Proof of Theorem 3. Denote ψi( ) := h(fk(gk(xi) + e NFM(k) i )) − yifk(gk(xi) + e NFM(k) i ), where eNFM(k)i is given in (30). Since h and fk are twice differentiable by assumption, ψi is twice differentiable in , and
ψi( ) = ψi(0) + ψ ′ i(0) +
2
2 ψ′′i (0) + 2ϕi( ), (40)
where ϕi is some function such that lim →0 ϕi( ) = 0. Therefore, by Lemma 2, LNFMn = Ek∼SL NFM(k) n , where
LNFM(k)n = 1
n n∑ i=1 Eλ∼D̃λExr∼DxEξk∼Q[ψi( )] (41)
= 1
n n∑ i=1 Eλ∼D̃λExr∼DxEξk∼Q [ ψi(0) + ψ ′ i(0) + 2 2 ψ′′i (0) + 2ϕi( ) ] (42)
= 1
n n∑ i=1 Eλ∼D̃λExr∼DxEξk∼Q [ ψi(0) + ψ ′ i(0) + 2 2 ψ′′i (0) ] + 2ϕ( ) (43)
=: Lstdn + R (k) 1 + 2(R̃ (k) 2 + R̃ (k) 3 ) + 2ϕ( ), (44)
where ϕ( ) = 1n ∑n i=1 Eλ∼D̃λExr∼DxEξk∼Q[ϕi( )].
It remains to compute ψ′i(0) and ψ ′′ i (0) in order to arrive at the expression for the R (k) 1 , R̃ (k) 2 and R̃ (k) 3 presented in Theorem 3.
Denoting g̃k(xi) := gk(xi) + e NFM(k) i , we compute, applying chain rule:
ψ′i( ) = h ′(fk(g̃k(xi)))∇kfk(g̃k(xi))T
∂g̃k(xi)
∂ − yi∇kfk(g̃k(xi))T
∂g̃k(xi)
∂ (45)
= (h′(fk(g̃k(xi)))− yi)∇kfk(g̃k(xi))T ∂g̃k(xi)
∂ (46)
= (h′(fk(g̃k(xi)))− yi)∇kfk(g̃k(xi))T eNFM(k)i (47) = (h′(fk(g̃k(xi)))− yi)∇kfk(g̃k(xi))T [(1− λ)(gk(xr)− gk(xi)) + σaddξaddk
+ σmultξ mult k gk(xi) + (1− λ)σmultξmultk (gk(xr)− gk(xi))], (48)
where we have used ∂g̃k(xi)∂ = e NFM(k) i in the second last line and substituted the expression for e NFM(k) i from (30) in the last line above.
Therefore,
ψ′i(0) = (h ′(fk(gk(xi)))− yi)∇kfk(gk(xi))T [(1− λ)(gk(xr)− gk(xi)) + σaddξaddk
+ σmultξ mult k gk(xi)], (49)
and
Eξk∼Qψ ′ i(0) = (h ′(fk(gk(xi)))− yi)∇kfk(gk(xi))T [(1− λ)(gk(xr)− gk(xi))], (50)
where we have used the assumptions that Eξk∼Qξ add k = 0 and Eξk∼Qξ mult k = 0. The expression for the R(k)1 in the theorem then follows from substituting (50) into (43).
Next, using chain rule, we have:
ψ′′i ( ) = ∂
∂
( (h′(fk(g̃k(xi)))− yi)∇kfk(g̃k(xi))T ∂g̃k(xi)
∂
) (51)
=
( ∂
∂ (h′(fk(g̃k(xi)))− yi)
) ∇kfk(g̃k(xi))T ∂g̃k(xi)
∂
+ (h′(fk(g̃k(xi)))− yi) ∂
∂
( ∇kfk(g̃k(xi))T ∂g̃k(xi)
∂
) . (52)
Note that, applying chain rule,
∂
∂
( ∇kfk(g̃k(xi))T ∂g̃k(xi)
∂
) = ∂
∂
( ∇kfk(g̃k(xi))T eNFM(k)i ) (53)
= ∂
∂
( (e NFM(k) i ) T∇kfk(g̃k(xi)) )
(54)
= (e NFM(k) i ) T∇2kfk(g̃k(xi)) ∂g̃k(xi)
∂ (55)
= (e NFM(k) i ) T∇2kfk(g̃k(xi))e NFM(k) i . (56)
Also, using chain rule again,( ∂
∂ (h′(fk(g̃k(xi)))− yi)
) = h′′(fk(g̃k(xi)))∇kfk(g̃k(xi))T ∂g̃k(xi)
∂ (57)
= h′′(fk(g̃k(xi)))∇kfk(g̃k(xi))T eNFM(k)i . (58)
Therefore, we have:
ψ′′i ( ) = h ′′(fk(g̃k(xi)))∇kfk(g̃k(xi))T eNFM(k)i (e NFM(k) i ) T∇kfk(g̃k(xi))
+ (h′(fk(g̃k(xi)))− yi)(eNFM(k)i ) T∇2kfk(g̃k(xi))e NFM(k) i (59)
= h′′(fk(g̃k(xi)))∇kfk(g̃k(xi))T [(1− λ)(gk(xr)− gk(xi)) + σaddξaddk + σmultξ mult k gk(xi) + (1− λ)σmultξmultk (gk(xr)− gk(xi))]
× [(1− λ)(gk(xr)− gk(xi)) + σaddξaddk + σmultξmultk gk(xi) + (1− λ)σmultξmultk (gk(xr)− gk(xi))]T∇kfk(g̃k(xi)) + (h′(fk(g̃k(xi)))− yi)[(1− λ)(gk(xr)− gk(xi)) + σaddξaddk + σmultξmultk gk(xi) + (1− λ)σmultξmultk (gk(xr)− gk(xi))]T∇2kfk(g̃k(xi))[(1− λ)(gk(xr)− gk(xi)) + σaddξ add k + σmultξ mult k gk(xi) + (1− λ)σmultξmultk (gk(xr)− gk(xi))] (60) =: h′′(fk(g̃k(xi)))∇kfk(g̃k(xi))TP1( )∇kfk(g̃k(xi)) + (h′(fk(g̃k(xi)))− yi)P2( ), (61)
where we have substituted the expression for the eNFM(k)i into the first line to arrive at the last line above.
Note that,
Eξk∼QP1( )
= Eξk∼Q[(1− λ)(gk(xr)− gk(xi)) + σaddξaddk + σmultξmultk gk(xi) + (1− λ)σmultξmultk (gk(xr)− gk(xi))]× [(1− λ)(gk(xr)− gk(xi)) + σaddξaddk + σmultξ mult k gk(xi) + (1− λ)σmultξmultk (gk(xr)− gk(xi))]T (62)
= (1− λ)2(gk(xr)− gk(xi))(gk(xr)− gk(xi))T + σ2addEξk∼Q[ξaddk (ξaddk )T ] + σ2multEξk∼Q[(ξ mult k gk(xi))(ξmultk gk(xi))T ] + o( ) (63)
= (1− λ)2(gk(xr)− gk(xi))(gk(xr)− gk(xi))T + σ2addEξk∼Q[ξaddk (ξaddk )T ] + σ2multEξk∼Q[(ξ mult k (ξ mult k ) T ) gk(xi))gk(xi)T ] + o( ), (64)
as → 0, where we have used the assumption that Eξk∼Qξaddk = 0 and Eξk∼Qξmultk = 0 in the second last line above.
Similarly,
Eξk∼QP2( )
= Eξk∼Q[(1− λ)(gk(xr)− gk(xi)) + σaddξaddk + σmultξmultk gk(xi) + (1− λ)σmultξmultk (gk(xr)− gk(xi))]T∇2kfk(g̃k(xi))[(1− λ)(gk(xr)− gk(xi)) + σaddξ add k + σmultξ mult k gk(xi) + (1− λ)σmultξmultk (gk(xr)− gk(xi))] (65)
= (1− λ)2(gk(xr)− gk(xi))T∇2kfk(g̃k(xi))(gk(xr)− gk(xi)) + σ2addEξk∼Q[(ξ add k )
T∇2kfk(g̃k(xi))ξaddk ] + σ2multEξk∼Q[(ξ mult k gk(xi))T∇2kfk(g̃k(xi))(ξmultk gk(xi))] + o( ), (66)
as → 0. Now, recall from Eq. (43) that we have
LNFM(k)n = 1
n n∑ i=1 Eλ∼D̃λExr∼DxEξk∼Q [ ψi(0) + ψ ′ i(0) + 2 2 ψ′′i (0) ] + 2ϕ( ) (67)
=: Lstdn + R (k) 1 + 2(R̃ (k) 2 + R̃ (k) 3 ) + 2ϕ( ), (68)
where ψi(0) = h(fk(gk(xi)))− yifk(gk(xi)). Also, we have:
Eξk∼Q[ψ ′′ i ( )]
= h′′(fk(g̃k(xi)))∇kfk(g̃k(xi))TEξk∼Q[P1( )]∇kfk(g̃k(xi)) + (h′(fk(g̃k(xi)))− yi)Eξk∼Q[P2( )] (69) = h′′(fk(g̃k(xi)))∇kfk(g̃k(xi))T [(1− λ)2(gk(xr)− gk(xi))(gk(xr)− gk(xi))T
+ σ2addEξk∼Q[ξ add k (ξ add k ) T ] + σ2multEξk∼Q[(ξ mult k (ξ mult k ) T ) gk(xi))gk(xi)T ] + o( )] ×∇kfk(g̃k(xi)) + (h′(fk(g̃k(xi)))− yi)[(1− λ)2(gk(xr)− gk(xi))T∇2kfk(g̃k(xi))(gk(xr)− gk(xi)) + σ2addEξk∼Q[(ξ add k )
T∇2kfk(g̃k(xi))ξaddk ] + σ2multEξk∼Q[(ξ mult k gk(xi))T∇2kfk(g̃k(xi))(ξmultk gk(xi))] + o( )]. (70)
Therefore, setting = 0,
Eξk∼Q[ψ ′′ i (0)]
= h′′(fk(gk(xi)))∇kfk(gk(xi))T [(1− λ)2(gk(xr)− gk(xi))(gk(xr)− gk(xi))T
+ σ2addEξk∼Q[ξ add k (ξ add k ) T ] + σ2multEξk∼Q[(ξ mult k (ξ mult k ) T ) gk(xi))gk(xi)T ]] ×∇kfk(gk(xi)) + (h′(fk(gk(xi)))− yi)[(1− λ)2(gk(xr)− gk(xi))T∇2kfk(gk(xi))(gk(xr)− gk(xi)) + σ2addEξk∼Q[(ξ add k )
T∇2kfk(gk(xi))ξaddk ] + σ2multEξk∼Q[(ξ mult k gk(xi))T∇2kfk(gk(xi))(ξmultk gk(xi))]]. (71)
The expression for the R̃(k)2 and R̃ (k) 3 in the theorem follows upon substituting (71) into (67).

heading: B.2 THEOREM 2 IN THE MAIN PAPER AND THE PROOF
text: 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 + ez), with the labels y taking value in {0, 1} and the classifier model f : Rd → R. Theorem 4 (Theorem 2 in the main paper). Let θ ∈ Θ := {θ : yif(xi)+(yi−1)f(xi) ≥ 0 for all i ∈ [n]} be a point such that ∇kf(gk(xi)) and ∇2kf(gk(xi)) exist for all i ∈ [n], k ∈ S. Assume that fk(gk(xi)) = ∇kf(gk(xi))T gk(xi), ∇2kf(gk(xi)) = 0 for all i ∈ [n], k ∈ S. In addition, suppose that ‖∇f(xi)‖2 > 0 for all i ∈ [n], Er∼Dx [gk(r)] = 0 and ‖gk(xi)‖2 ≥ c (k) x √ dk for all i ∈ [n], k ∈ S. Then,
LNFMn ≥ 1
n n∑ i=1 max ‖δi‖2≤ mixi l(f(xi + δi), yi) + L reg n + 2φ( ), (72)
where
mixi = Eλ∼D̃λ [1− λ] · Ek∼S [ r (k) i c (k) x ‖∇kf(gk(xi))‖2 ‖∇f(xi)‖2 √ dk ] , (73)
r (k) i = | cos(∇kf(gk(xi)), gk(xi))|, (74)
Lregn = 1
2n n∑ i=1 |h′′(f(xi))|( regi ) 2, (75)
with
( regi ) 2 = 2‖∇kf(gk(xi))‖22 ( Eλ[(1− λ)]2Exr [‖gk(xr)‖22 cos(∇kf(gk(xi)), gk(xr))2]
+ σ2addEξ[‖ξadd‖22 cos(∇kf(gk(xi)), ξadd)2] + σ2multEξ[‖ξmult gk(xi)‖22 cos(∇kf(gk(xi)), ξmult gk(xi))2] ) , (76)
and φ is some function such that lim →0 φ( ) = 0.
Theorem 4 says that LNFMn is approximately an upper bound of sum of an adversarial loss with l2attack of size mix = mini mixi and a feature-dependent regularizer with the strength of mini( reg i )
2. Therefore, minimizing the NFM loss would result in a small regularized adversarial loss. We note that both mixi and reg i depend on the cosine similarities between the directional derivatives and the features at which the derivatives are evaluated at, whereas the regi additionally depend on the cosine similarities between the directional derivatives and the injected noise.
Before proving Theorem 4, we remark that the assumption that fk(gk(xi)) = ∇kf(gk(xi))T gk(xi), ∇2kf(gk(xi)) = 0 for all i ∈ [n], k ∈ S is satisfied by fully connected neural networks with ReLU activation function or max-pooling. For a proof of this, we refer to Section B.2 in Zhang et al. (2020). The assumption that Er∼Dx [gk(r)] = 0 could be relaxed at the cost of obtaining a more complicated formula (see Remark 1 for the formula) for the regi in the bound, which could be derived in a straightforward manner.
Proof of Theorem 4. For h(z) = log(1 + ez), we have h′(z) = e z 1+ez =: S(z) ≥ 0 and h ′′(z) =
ez
(1+ez)2 = S(z)(1− S(z)) ≥ 0. Substituting these expressions into the equation of Theorem 3 and using the assumptions that fk(gk(xi)) = ∇kf(gk(xi))T gk(xi) and Er∼Dx [gk(r)] = 0, we have, for k ∈ S,
R (k) 1 = Eλ∼D̃λ [1− λ] n n∑ i=1 (yi − S(f(xi)))fk(gk(xi)), (77)
and we compute:
R (k) 2 =
Eλ∼D̃λ [(1− λ) 2]
2n
n∑ i=1 S(f(xi))(1− S(f(xi)))∇kf(gk(xi))T
× Exr∼Dx [(gk(xr)− gk(xi))(gk(xr)− gk(xi))T ]∇kf(gk(xi)) (78)
≥ Eλ∼D̃λ [(1− λ)] 2
2n
n∑ i=1 |S(f(xi))(1− S(f(xi)))|∇kf(gk(xi))T
× Exr∼Dx [(gk(xr)− gk(xi))(gk(xr)− gk(xi))T ]∇kf(gk(xi)) (79)
= Eλ∼D̃λ [(1− λ)] 2
2n
n∑ i=1 |S(f(xi))(1− S(f(xi)))|∇kf(gk(xi))T
× (Exr∼Dx [(gk(xr)gk(xr)T ] + gk(xi)gk(xi)T ])∇kf(gk(xi)) (80)
= Eλ∼D̃λ [(1− λ)] 2
2n
n∑ i=1 |S(f(xi))(1− S(f(xi)))|(∇kf(gk(xi))T gk(xi))2
+ Eλ∼D̃λ [(1− λ)] 2
2n
n∑ i=1 |S(f(xi))(1− S(f(xi)))|Exr∈Dx [(∇kf(gk(xi))T gk(xr))2]
(81)
= Eλ∼D̃λ [(1− λ)] 2
2n
n∑ i=1 |S(f(xi))(1− S(f(xi)))|‖∇kf(gk(xi))‖22‖gk(xi)‖22
× (cos(∇kf(gk(xi)), gk(xi)))2 + 1
2n n∑ i=1 |S(f(xi))(1− S(f(xi)))|‖∇kf(gk(xi))‖22
× Eλ[(1− λ)]2Exr [‖gk(xr)‖22 cos(∇kf(gk(xi)), gk(xr))2] (82)
≥ 1 2n n∑ i=1 |S(f(xi))(1− S(f(xi)))|‖∇kf(gk(xi))‖22Eλ∼D̃λ [(1− λ)] 2dk(r (k) i c (k) x ) 2
+ 1
2n n∑ i=1 |S(f(xi))(1− S(f(xi)))|‖∇kf(gk(xi))‖22 · Eλ[(1− λ)]2Exr [‖gk(xr)‖22
× cos(∇kf(gk(xi)), gk(xr))2] (83)
= 1
2n n∑ i=1 |S(f(xi))(1− S(f(xi)))|‖∇f(xi)‖22
× (
Eλ∼D̃λ [(1− λ)] 2 ‖∇kf(gk(xi))‖22 ‖∇f(xi)‖22 dk(r (k) i c (k) x ) 2 ) + 1
2n n∑ i=1 |S(f(xi))(1− S(f(xi)))|‖∇kf(gk(xi))‖22 · Eλ[(1− λ)]2Exr [‖gk(xr)‖22
× cos(∇kf(gk(xi)), gk(xr))2]. (84)
In the above, we have used the facts that E[Z2] = E[Z]2 + V ar(Z) ≥ E[Z]2 and S, S(1−S) ≥ 0 to obtain (79), the assumption that Er∼Dx [gk(r)] = 0 to arrive at (80), the assumption that ‖gk(xi)‖2 ≥ c (k) x √ dk for all i ∈ [n], k ∈ S to arrive at (83), and the assumption that ‖∇f(xi)‖2 > 0 for all i ∈ [n] to justify the last equation above.
Next, we bound R(k)1 , using the assumption that θ ∈ Θ. Note that from our assumption on θ, we have yif(xi) + (yi − 1)f(xi) ≥ 0, which implies that f(xi) ≥ 0 if yi = 1 and f(xi) ≤ 0 if yi = 0. Thus, if yi = 1, then (yi − S(f(xi)))fk(gk(xi)) = (1 − S(f(xi)))fk(gk(xi)) ≥ 0, since f(xi) ≥ 0 and (1− S(f(xi))) ≥ 0 due to the fact that S(f(xi)) ∈ (0, 1). A similar argument leads to (yi − S(f(xi)))fk(gk(xi)) ≥ 0 if yi = 0. So, we have (yi − S(f(xi)))fk(gk(xi)) ≥ 0 for all i ∈ [n]. Therefore, noting that Eλ∼D̃λ [1− λ] ≥ 0, we compute:
R (k) 1 = Eλ∼D̃λ [1− λ] n n∑ i=1 |yi − S(f(xi))||fk(gk(xi))| (85)
= Eλ∼D̃λ [1− λ]
n
n∑ i=1 |S(f(xi))− yi|‖∇kf(gk(xi))‖2‖gk(xi)‖2| cos(∇kf(gk(xi)), gk(xi))|
(86)
≥ 1 n n∑ i=1 |S(f(xi))− yi|‖∇kf(gk(xi))‖2(Eλ∼D̃λ [1− λ]r (k) i c (k) x √ dk) (87)
= 1
n n∑ i=1 |S(f(xi))− yi|‖∇f(xi)‖2 ( Eλ∼D̃λ [1− λ] ‖∇kf(gk(xi))‖2 ‖∇f(xi)‖2 r (k) i c (k) x √ dk ) . (88)
Note that R(k)3 = 0 as a consequence of our assumption that∇2kf(gk(xi)) = 0 for all i ∈ [n], k ∈ S , and similar argument leads to:
R add(k) 2 =
1
2n n∑ i=1 |S(f(xi))(1− S(f(xi)))|∇kf(gk(xi))TEξk [ξaddk (ξaddk )T ]∇kf(gk(xi)) (89)
= 1
2n n∑ i=1 |S(f(xi))(1− S(f(xi)))|‖∇kf(gk(xi))‖22
× Eξk [‖ξaddk ‖22 cos(∇kf(gk(xi)), ξaddk )2] (90)
R mult(k) 2 =
1
2n n∑ i=1 |S(f(xi))(1− S(f(xi)))|∇kf(gk(xi))T (Eξk [ξaddk (ξaddk )T ] gk(xi)gk(xi)T )
×∇kf(gk(xi))
= 1
2n n∑ i=1 |S(f(xi))(1− S(f(xi)))|‖∇kf(gk(xi))‖22
× Eξk [‖ξmultk gk(xi)‖22 cos(∇kf(gk(xi)), ξmult gk(xi))2]. (91)
Using Theorem 3 and the above results, we obtain:
LNFMn − 1
n n∑ i=1 l(f(xi), yi)
≥ Ek[ R(k)1 + 2R (k) 2 + 2R add(k) 2 + 2R mult(k) 2 + 2ϕ( )] (92)
≥ 1 n n∑ i=1 |S(f(xi))− yi|‖∇f(xi)‖2 mixi (93)
+ 1
2n n∑ i=1 |S(f(xi))(1− S(f(xi)))|‖∇f(xi)‖22( mixi )2
+ 1
2n n∑ i=1 |S(f(xi))(1− S(f(xi)))|‖∇kf(gk(xi))‖22 · Eλ[(1− λ)]2Exr [‖gk(xr)‖22
× cos(∇kf(gk(xi)), gk(xr))2] (94)
+ 1
2n n∑ i=1 |S(f(xi))(1− S(f(xi)))|( noisei )2 + 2ϕ( ), (95)
where mixi := Eλ∼D̃λ [1− λ]Ek [ ‖∇kf(gk(xi))‖2 ‖∇f(xi)‖2 r (k) i c (k) x √ dk ] and
( noisei ) 2 = 2‖∇kf(gk(xi))‖22 ( σ2addEξk [‖ξaddk ‖22 cos(∇kf(gk(xi)), ξaddk )2]
+ σ2multEξk [‖ξmultk gk(xi)‖22 cos(∇kf(gk(xi)), ξmultk gk(xi))2] ) . (96)
On the other hand, for any small parameters i > 0 and any inputs z1, . . . , zn, we can, using a second-order Taylor expansion and then applying our assumptions, compute:
1
n n∑ i=1 max ‖δi‖2≤ i l(f(zi + δi), yi)− 1 n n∑ i=1 l(f(zi), yi)
≤ 1 n n∑ i=1 |S(f(zi))− yi|‖∇f(zi)‖2 i + 1 2n n∑ i=1 |S(f(zi))(1− S(f(zi)))|‖∇f(zi)‖22 2i
+ 1
n n∑ i=1 max ‖δi‖2≤ i ‖δi‖22ϕ′i(δi) (97)
≤ 1 n n∑ i=1 |S(f(zi))− yi|‖∇f(zi)‖2 i + 1 2n n∑ i=1 |S(f(zi))(1− S(f(zi)))|‖∇f(zi)‖22 2i
+ 1
n n∑ i=1 2iϕ ′′ i ( i), (98)
where the ϕ′i are functions such that limz→0 ϕ ′ i(z) = 0, ϕ ′′ i ( i) := max‖δi‖2≤ i ϕ ′ i(δi) and limz→0 ϕ ′′ i (z) = 0.
Combining (95) and (98), we see that
LNFMn ≥ 1
n n∑ i=1 max ‖δmixi ‖2≤ mixi l(f(xi + δ mix i ), yi) + L reg n + 2ϕ( )− 1 n n∑ i=1 ( mixi ) 2ϕ′′i ( mix i )
(99)
=: 1
n n∑ i=1 max ‖δmixi ‖2≤ mixi l(f(xi + δ mix i ), yi) + L reg n + 2φ( ), (100)
where Lregn is defined in the theorem. Noting that lim →0 φ( ) = 0, the proof is done.
Remark 1. Had we assumed that Er∼Dx [gk(r)] 6= 0, then the statements of Theorem 4 remain unchanged, but with ( regi ) 2 replaced by
( regi ) 2 = 2‖∇kf(gk(xi))‖22 ( Eλ[(1− λ)]2Exr [‖gk(xr)‖22 cos(∇kf(gk(xi)), gk(xr))2]
+ σ2addEξ[‖ξadd‖22 cos(∇kf(gk(xi)), ξadd)2] + σ2multEξ[‖ξmult gk(xi)‖22 cos(∇kf(gk(xi)), ξmult gk(xi))2] )
− 2Eλ[(1− λ)]2∇kf(gk(xi))T [Ergk(r)gk(xi)T + gk(xi)Ergk(r)T ]∇kf(gk(xi)). (101)

heading: C NFM THROUGH THE LENS OF IMPLICIT REGULARIZATION AND CLASSIFICATION MARGIN
text: 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 si := (xi, ci) measured by the Euclidean metric d is defined as the radius of the largest d-metric ball in X centered at xi that is contained in the decision region associated with the class label ci, i.e., it is: γd(si) = sup{a : d(xi, x) ≤ a⇒ g(x) = ci ∀x}.
Intuitively, a larger classification margin allows a classifier to associate a larger region centered on a point xi in the input space to the same class. This makes the classifier less sensitive to input perturbations, and a perturbation of xi 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 (Sokolić et al., 2017). Definition 3 (Score). For an input-label training sample si = (xi, ci), we define its score as o(si) = minj 6=ci √ 2(eci − ej)T f(xi) ≥ 0, where ei ∈ RK is the Kronecker delta vector (one-hot vector) with eii = 1 and e j i = 0 for i 6= 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(si) > 0 and let k ∈ S. Then, the classification margin for the training sample si can be lower bounded as:
γd(si) ≥ C(si)
supx∈conv(X ) ‖∇kf(gk(x))‖2 , (102)
where C(si) = o(si)/ supx∈conv(X ) ‖∇gk(x)‖2.
Since NFM implicitly reduces the feature-output Jacobians∇kf (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 (Wei & Ma, 2019b), 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 ∈ S, ∇f(x) = ∇kf(gk(x))∇gk(x) by the chain rule, and so
‖∇f(x)‖2 ≤ ‖∇kf(gk(x))‖2‖∇gk(x)‖2 (103)
≤ ( sup
x∈conv(X ) ‖∇kf(gk(x))‖2
)( sup
x∈conv(X ) ‖∇gk(x)‖2
) . (104)
The statement in the proposition follows from a straightforward application of Theorem 4 in (Sokolić et al., 2017) together with the above bound.

heading: D NFM THROUGH THE LENS OF PROBABILISTIC ROBUSTNESS
text: 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 ∈ S , NFM(k) can be viewed as injecting noise to the layer k features sampled from some distribution over conv(gk(X )), and so the NFM(k) neural network Fk can be viewed as a probabilistic mapping from conv(gk(X )) to P(Y), the space of probability distributions on Y . To isolate the benefit of noise injection, we adapt the approach of (Pinot et al., 2019a; 2021) 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 (Lecuyer et al., 2019; Dwork et al., 2014), as formalized in (Pinot et al., 2019b).
We now formalize this probabilistic notion of robustness.
Let p > 0. We say that a standard model f : X → Y is αp-robust if for any (x, y) ∼ D such that f(x) = y, one has, for any data perturbation τ ∈ X ,
‖τ‖p ≤ αp =⇒ f(x) = f(x+ τ). (105)
Analogous definition can be formulated when output of the model is distribution-valued.
Definition 4 (Probabilistic robustness). A probabilistic model F : X → P(Y) is called (αp, )-robust with respect to D if, for any x, τ ∈ X , one has
‖τ‖p ≤ αp =⇒ D(F (x), F (x+ τ)) ≤ , (106)
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 Fnoisy(k) : conv(gk(X )) → P(Y). We denote G as the classifier constructed from Fnoisy(k), i.e., G : x 7→ arg maxj∈[K][F noisy(k)]j(x).
In the sequel, we take D to be the total variation distance DTV , defined as:
DTV (P,Q) := sup S⊂X |P (S)−Q(S)|, (107)
for any two distributions P andQ overX . Recall that if P andQ have densities ρp and ρq respectively, then the total variation distance is half of the L1 distance, i.e.,DTV (P,Q) = 12 ∫ X |ρp(x)−ρ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 (Pinot et al., 2021; Gibbs & Su, 2002) for details).
Before presenting our main result in this section, we need the following notation. Let Σ(x) := σ2addI + σ 2 multxx
T . For x, τ ∈ X , let Πx be a dk by dk − 1 matrix whose columns form a basis for the subspace orthogonal to gk(x+ τ)− gk(x), and {ρi(gk(x), τ)}i∈[dk−1] be the eigenvalues of (ΠTxΣ(gk(x))Πx)
−1ΠTxΣ(gk(x + τ))Πx − I . Also, let [F ]topk(x) denote the kth 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 ∈ S, dk > 1, and assume that gk(x)gk(x)T ≥ β2kI > 0 for all x ∈ conv(X ) for some constant βk. Then, Fnoisy(k) is (αp, k(p, d, αp, σadd, σmult))-robust with respect to DTV against lp adversaries, with
k(p, d, αp, σadd, σmult) = 9
2 min{1,max{A,B}}, (108)
where
A = Ap(αp) σ2mult
σ2add + σ 2 multβ 2 k (∥∥∥∥∫ 1 0 ∇gk(x+ tτ)dt ∥∥∥∥2 2 + 2‖gk(x)‖2 ∥∥∥∥∫ 1 0 ∇gk(x+ tτ)dt ∥∥∥∥ 2 ) ,
(109)
B = Bk(τ) αp(1p∈(0,2] + d1/2−1/p1p∈(2,∞) + √ d1p=∞)√
σ2add + σ 2 multβ 2 k
, (110)
with
Ap(αp) =  αp1αp<1 + α 2 p1αp≥1, if p ∈ (0, 2], d1/2−1/p(αp1αp<1 + α 2 p1αp≥1), if p ∈ (2,∞),√
d(αp1αp<1 + α 2 p1αp≥1), if p =∞,
(111)
and
Bk(τ) = sup x∈conv(X ) (∥∥∥∥∫ 1 0 ∇gk(x+ tτ)dt ∥∥∥∥ 2 · √√√√dk−1∑ i=1 ρ2i (gk(x), τ) ) . (112)
Moreover, if x ∈ X is such that [Fnoisy(k)]top1(x) ≥ [Fnoisy(k)]top2(x) + 2 (p, d, αp, σadd, σmult), then for any τ ∈ X , we have
‖τ‖p ≤ α =⇒ G(x) = G(x+ τ), (113) 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 σadd and σmult. To illustrate this, suppose that σmult = 0 and consider the case of p = 2, in which case A = 0, B ∼ α2/σ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 α2.
We now prove Theorem 5. Before this, we need the following lemma. Lemma 3. Let x1 := z ∈ Rdk and x2 := z + τ ∈ Rdk , with τ > 0 and dk > 1, and Σ(x) := σ2addI+σ 2 multxx
T ≥ (σ2add+σ2multβ2)I > 0, for some constant β, for all x. Let Π be a dk by dk−1 matrix whose columns form a basis for the subspace orthogonal to τ , and let ρ1(z, τ), . . . , ρdk−1(z, τ) denote the eigenvalues of (ΠTΣ(x1)Π)−1ΠTΣ(x2)Π− I . Define the function C(x1, x2,Σ) := max{A,B}, where
A = σ2mult
σ2add + σ 2 multβ
2 (‖τ‖22 + 2τT z), (114)
B = ‖τ‖2√
σ2add + σ 2 multβ 2 √√√√dk−1∑ i=1 ρ2i (z, τ). (115)
Then, the total variation distance between N (x1,Σ(x1)) and N (x2,Σ(x2)) admits the following bounds:
1 200 ≤ DTV (N (x1,Σ(x1)),N (x2,Σ(x2))) min{1, C(x1, x2,Σ)} ≤ 9 2 . (116)
Proof of Lemma 3. The result follows from a straightforward application of Theorem 1.2 in (Devroye et al., 2018), 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 I : x → N (x,Σ(x)), where Σ(x) = σ2addI + σ 2 multxx T .
Let x ∈ X be a test datapoint and τ ∈ X be a data perturbation such that ‖τ‖p ≤ αp for p > 0. Note that
DTV (Fk(I(gk(x))), Fk(I(gk(x+ τ)))) ≤ DTV (I(gk(x)), I(gk(x+ τ))) (117) ≤ DTV (I(gk(x)), I(gk(x) + gk(x+ τ)− gk(x)))
(118) = DTV (I(gk(x)), I (gk(x) + τk)) (119)
≤ 9 2 min{1,Φ(gk(x), τk, σadd, σmult, βk)}, (120)
where τk := gk(x+ τ)− gk(x) = (∫ 1 0 ∇gk(x+ tτ)dt ) τ by the generalized fundamental theorem of calculus, and
Φ(gk(x), τk, σadd, σmult, βk)
:= max  σ2multσ2add + σ2multβ2k (‖τk‖22 + 2〈τk, gk(x)〉), ‖τk‖2√σ2add + σ2multβ2k √√√√dk−1∑ i=1 ρ2i (gk(x), τ)  , (121)
where the ρi(gk(x), τ) are the eigenvalues given in the theorem.
In the first line above, we have used the data preprocessing inequality (Theorem 6 in (Pinot et al., 2021)), and the last line follows from applying Lemma 3 together with the assumption that gk(x)gk(x)T ≥ β2k > 0 for all x. Using the bounds
‖τk‖2 ≤ ∥∥∥∥∫ 1
0 ∇gk(x+ tτ)dt ∥∥∥∥ 2 ‖τ‖2 (122)
and
|〈τk, gk(x)〉| ≤ ‖gk(x)‖2 ∥∥∥∥∫ 1
0 ∇gk(x+ tτ)dt ∥∥∥∥ 2 ‖τ‖2, (123)
we have
Φ(gk(x), τk, σadd, σmult, βk) ≤ max {A,B} , (124)
where
A = σ2mult
σ2add + σ 2 multβ 2 k (∥∥∥∥∫ 1 0 ∇gk(x+ tτ)dt ∥∥∥∥2 2 ‖τ‖22 + 2‖gk(x)‖2 ∥∥∥∥∫ 1 0 ∇gk(x+ tτ)dt ∥∥∥∥ 2 ‖τ‖2 )
(125) and
B = ∥∥∥∫ 10 ∇gk(x+ tτ)dt∥∥∥2 ‖τ‖2√ σ2add + σ 2 multβ 2 k √√√√dk−1∑ i=1 ρ2i (gk(x), τ) (126)
≤ sup x∈conv(X ) (∥∥∥∥∫ 1 0 ∇gk(x+ tτ)dt ∥∥∥∥ 2 · √√√√dk−1∑ i=1 ρ2i (gk(x), τ) ) ‖τ‖2√ σ2add + σ 2 multβ 2 k
(127)
=: Bk(τ) ‖τ‖2√
σ2add + σ 2 multβ 2 k
. (128)
The first statement of the theorem then follows from the facts that ‖τ‖2 ≤ ‖τ‖p ≤ αp for p ∈ (0, 2], ‖τ‖2 ≤ d1/2−1/q‖τ‖q ≤ d1/2−1/qαq for q > 2, and ‖τ‖2 ≤ √ d‖τ‖∞ ≤ √ dα∞ for any τ ∈ Rd. In particular, these imply that A ≤ CAp, where
Ap =  αp1αp<1 + α 2 p1αp≥1, if p ∈ (0, 2], d1/2−1/p(αp1αp<1 + α 2 p1αp≥1), if p ∈ (2,∞),√
d(αp1αp<1 + α 2 p1αp≥1), if p =∞,
(129)
and
C := σ2mult
σ2add + σ 2 multβ 2 k (∥∥∥∥∫ 1 0 ∇gk(x+ tτ)dt ∥∥∥∥2 2 + 2‖gk(x)‖2 ∥∥∥∥∫ 1 0 ∇gk(x+ tτ)dt ∥∥∥∥ 2 ) . (130)
The last statement in the theorem essentially follows from Proposition 3 in (Pinot et al., 2021).

heading: E ON GENERALIZATION BOUNDS FOR NFM
text: Let F be the family of mappings x 7→ f(x) and Zn := ((xi, yi))i∈[n]. Given a loss function l, the Rademacher complexity of the set l ◦ F := {(x, y) 7→ l(f(x), y) : f ∈ F} is defined as:
Rn(l ◦ F) := EZn,σ [ sup f∈F 1 n n∑ i=1 σil(f(xi), yi) ] , (131)
where σ := (σ1, . . . , σn), with the σi independent uniform random variables taking values in {−1, 1}. Following (Lamb et al., 2019), 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′, y)| ≤ M for all x, x′ and y. Then, for every δ > 0, with probability at least 1 − δ over a draw of n i.i.d. samples {(xi, yi)}ni=1, we have the following generalization bound: for all maps f ∈ F ,
Ex,y[l(f(x), y)]− LNFMn ≤ 2Rn(l ◦ F) + 2M √ ln(1/δ)
2n −Q (f), (132)
where Q (f) = E[ R
(k) 1 + 2R̃ (k) 2 + 2R̃ (k) 3 ] + 2ϕ( ), (133) for some function ϕ such that limx→∞ ϕ(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′, y)| ≤ M for all x, x′ and y. Then, for every δ > 0, with probability at least 1 − δ over a draw of n i.i.d. samples {(xi, yi)}ni=1, we have the following generalization bound: for all maps f ∈ F ,
Ex,y[l(f(x), y)]− Lstdn ≤ 2Rn(l ◦ F) + 2M √ ln(1/δ)
2n . (134)
By comparing the above two theorems and following the argument of (Lamb et al., 2019), we see that the generalization benefit of NFM comes from two mechanisms. The first mechanism is based on the term Q (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 (f) > 0. The second mechanism is based on the Rademacher complexity term Rn(l ◦ 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 (Wei & Ma, 2019a;b). 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 Zn := {(xi, yi)}i∈[n] and Z ′n := {(x′i, y′i)}i∈[n] be two test datasets, where Z ′n differs from Zn by exactly one point of an arbitrary index i0.
Denote GE(Zn) := supf∈F Ex,y[l(f(x), y)]−LNFMn , where LNFMn is computed using the dataset Zn, and likewise for GE(Z ′n). Then,
GE(Z ′n)−GE(Zn) ≤ M(2n− 1) n2 ≤ 2M n , (135)
where we have used the fact that LNFMn has n 2 terms and there are 2n− 1 different terms for Zn and Z ′n. Similarly, we have GE(Zn)−GE(Z ′n) ≤ 2Mn . Therefore, by McDiarmid’s inequality, for any δ > 0, with probability at least 1− δ,
GE(Zn) ≤ EZn [GE(Zn)] + 2M √ ln(1/δ)
2n . (136)
Applying Theorem 3, we have
GE(Zn) ≤ EZn [ sup f∈F EZ′n [ 1 n n∑ i=1 l(f(x′i), y ′ i) ] − LNFMn ] + 2M √ ln(1/δ) 2n (137)
= EZn [ sup f∈F EZ′n [ 1 n n∑ i=1 l(f(x′i), y ′ i) ] − 1 n n∑ i=1 l(f(xi), yi) ] −Q (f)
+ 2M
√ ln(1/δ)
2n (138)
≤ EZn,Z′n [ sup f∈F 1 n n∑ i=1 (l(f(x′i), y ′ i)− l(f(xi), yi)) ] −Q (f) + 2M √ ln(1/δ) 2n (139)
≤ EZn,Z′n,σ [ sup f∈F 1 n n∑ i=1 σi(l(f(x ′ i), y ′ i)− l(f(xi), yi)) ] −Q (f) + 2M √ ln(1/δ) 2n
(140)
≤ 2EZn,σ [ sup f∈F 1 n n∑ i=1 σil(f(xi), yi) ] −Q (f) + 2M √ ln(1/δ) 2n (141)
= 2Rn(l ◦ F)−Q (f) + 2M √ ln(1/δ)
2n , (142)
where (137) uses the definition of GE(Zn), (138) uses ± 1n ∑n i=1 l(f(xi), yi) inside the expectation and the linearity of expectation, (139) follows from the Jensen’s inequality and the convexity of the supremum, (140) follows from the fact that σi(l(f(x′i), y ′ i) − l(f(xi), yi)) and l(f(x′i), y′i) − l(f(xi), yi) have the same distribution for each σi ∈ {−1, 1} (since Zn, Z ′n are drawn i.i.d. with the same distribution), and (141) follows from the subadditivity of supremum.
The bound in the theorem then follows from the above bound.

heading: F ADDITIONAL EXPERIMENTS AND DETAILS
text: F.1 INPUT PERTURBATIONS
We consider the following three types of data perturbations during inference time:
• White noise perturbations are constructed as x̃ = x + ∆x, where the additive noise is sampled from a Gaussian distribution ∆x ∼ N (0, σ). This perturbation strategy emulates measurement errors that can result from data acquisition with poor sensors (where σ 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 P(X̃ = X) = 1− γ, and P(X̃ = max) = P(X̃ = min) = γ/2, where X̃(i, j) denotes the corrupted image and min, max denote the minimum and maximum pixel values, respectively. γ parameterizes the proportion of defective pixels.
• Adversarial perturbations are “worst-case” non-random perturbations that maximize the loss `(gδ(X + ∆X), y) subject to the constraint ‖∆X‖ ≤ r on the norm of the perturbation. We consider the projected gradient decent for constructing these perturbations (Madry et al., 2017).
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. 8 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.

heading: F.3 ADDITIONAL RESULTS FOR VISION TRANSFORMERS
text: Here we consider compact vision transformer (ViT-lite) with 7 attention layers and 4 heads (Hassani et al., 2021). Fig. 9 (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. 9 (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 Shao et al. (2021); Paul & Chen (2021). Table 4 provides additional results for different α values.
Table 4 shows results for vision transformers trained with different data augmentation schemes and different values of α. It can be seen that NFM with α = 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 (γ = 0.2). Further, our results indicate that larger values of α have a negative effect on the generalization performance of vision transformer.

heading: F.4 ABLATION STUDY
text: In Table 5 we provide a detailed ablation study where we vary several knobs. First, we can see that just injecting noise helps to improve robustness, but it is only marginally improving the testing performance. On the other hand, just mixing inputs and hidden features improves the testing performance of the model, but it does not significantly improve the robustness of a model. In contrast, the NFM scheme combines best of both worlds and shows that both accuracy and robustness can be increased. Varying the noise levels indicates that there is a trade-off between test accuracy on
clean data and robustness to perturbations. We also vary the mixup parameter α to show that the good performance is consistent across a range of different values.

heading: F.5 ADDITIONAL RESULTS FOR RESNETS WITH HIGHER LEVELS OF NOISE INJECTIONS
text: In the experiments in Section 5, we considered models trained with NFM that use noise injection levels σadd = 0.4 and σmult = 0.2, whereas the ablation model uses σadd = 1.0 and σ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. 10 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.

heading: F.6 COMPARISON WITH ADVERSARIAL TRAINED MODELS
text: 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 (Madry et al., 2017) using 7 attack iterations and varying l2 per-
turbation levels to train adversarial robust models. First, we compare how resilient the different models are with respect to adversarial input perturbations during inference time (Fig. 11; left). Again the adversarial examples are constructed using the PGD method with 7 attack iterations. Not very surprisingly, the adversarial trained model with = 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. 11; 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.

heading: F.7 FEATURE VISUALIZATION COMPARISON
text: In this subsection, we concern ourselves with comparing the features learned by three ResNet50 models trained on Restricted Imagenet (Tsipras et al., 2018): without mixup, manifold mixup (Verma et al., 2019), and NFM. We can compare features by maximizing randomly chosen pre-logit activations of each model with respect to the input, as described by Engstrom et al. (2020). We do so for all models with Projected Gradient Ascent over 200 iterations, a step size of 16, and an `2 norm constraint of 2,000. Both the models trained with manifold mixup and NFM use an α = 0.2, and the NFM model uses in addition σadd = 2.4 and σmult = 1.2. The result, as shown in Fig. 12, is that the features learned by the model trained with NFM are slightly stronger (i.e., different from random noise) than the clean model.

heading: F.8 TRAIN AND TEST ERROR FOR CIFAR-100
text: Figure 13 shows models trained with different training schemes on CIFAR-100. Compared to the baseline model, the models trained with manifold mixup and NFM have a similar convergence behavior. However, they are able to achieve a smaller test error. This shows that both manifold mixup and NFM have a favorable implicit regularization effect, where the effect is more pronounced for the NFM scheme.

Review summaries:
This paper proposes noise added version of the manifold mixup. The authors verify the theoretical properties of the method in terms of regularization and robustness. The paper verifies the effectiveness of the proposed method on image classification tasks with noisy test environments. 

The paper proposes a new and inexpensive mixup method named Noisy Feature Mixup (NFM) to mitigate over-fitting and improve generalization. NFM combines mixup and noise injection, which inherits the benefits of these methods. Due to its conciseness, it is convenient to apply NFM in model training. More importantly, the authors prove NFM's regularization effect on model optimization and robustness improvement with mathematical derivation. They build the implicit connection between the NFM empirical loss and the original loss. Then they identify the regularizing effects of the proposed NFM. To demonstrate that NFM helps robustness, the authors relate the NFM loss to the one used for adversarial training, which can be regarded as an example belonging to distributionally robust optimization. With integrated experiments, NFM shows its superiority on various models and datasets. The further discussion shows the interesting tradeoff between predictive accuracy on clean and perturbed test sets. The Supplementary Material provides detailed proof and additional experimental results to show NFM's firmed ground.

This paper studies data augmentation methods for improving the robustness of supervised learning. The main contribution is presenting Noisy Feature Mixup, extending input mixup and manifold mixup to all layers of a neural net. The experimental results show that the proposed approach improves the robustness of supervised learning under several noise attacks on the input data set. The theoretical results derive the Taylor's expansion of the Noisy Feature Mixup optimization objective.

This paper proposes a new method for data augmentation, named Noisy Feature Mixup (NFM). This method combines the advantages of both the interpolation based training and noise injection schemes. In particular, this method is simple and easy to implement. Empirically, this paper shows that NFM achieves a favorable trade-off between the test accuracy on the clean set and the model robustness. Theoretically, it is shown that NFM enables smoother decision boundary, and amplifies the regularization effects of manifold mixup and noise injection. Additional theoretical analysis also shows that NFM training is approximately minimizing an upper bound related to the adversarial loss, thereby leading to more robust model.