On the Inherent Regularization Effects of Noise Injection During Training

I Introduction

A popular approach to improving the generalization performance is to randomly perturb the network during the training process . Such random perturbations are widely used as an implicit regularization to the learning problem. One way that random perturbation has been used as a regularization is by injecting it to the input data before starting the learning process . In this paper, we provide a theoretical analysis of such learning procedure on a random feature model under Gaussian input and perturbation vectors. Our analysis particularly shows that Gaussian noise injection introduces a weighted ridge regularization, asymptotically.

where $\lambda>0$ denotes the regularization parameter. Note that the problem in (3) is a standard feature formulation when $\Delta=0$. Then, we refer to (3) as the noisy formulation, when $\Delta>0$ and the standard formulation, otherwise.

I-B Performance Measure

Here, the expectation is taken over the distribution of the unobserved test vector $\boldsymbol{a}_{\text{new}}$ and the (random) functions $\varphi(\cdot)$ and $\widehat{\varphi}(\cdot)$. We take $\upsilon=0$ for regression problems (e.g. $\varphi(\cdot)$ is the identity function) and $\upsilon=1$ for binary classification problems (e.g. $\varphi(\cdot)$ is the sign function). In this paper, we assume that the test data is generated according to the same training model introduced in (1). Furthermore, we measure the performance of the formulation in (3) on the training data via the training error defined as follows

Note that the training error is the optimal cost value of our learning formulation in (3) without regularization.

I-C Contributions

The contribution of this paper can be summarized as follows:

Our first contribution is a correlated Gaussian equivalence conjecture (cGEC). Our conjecture considers Gaussian input and perturbation vectors. It states that the learning formulation in (3) is asymptotically equivalent to a simpler optimization problem that can be formulated by replacing the non–linear vectors

with linear vectors with the following form

where $x_{1}=z+\Delta v_{1}$, $x_{2}=z+\Delta v_{2}$, and $z$, $v_{1}$ and $v_{2}$ are independent standard Gaussian random variables. Specifically, the cGEC states that the performance of the formulation:

is asymptotically equivalent to the performance of the noisy formulation. This conjecture is valid in the asymptotic limit (i.e. $n$, $p$ and $k$ grow to infinity at finite ratios). More details about this equivalence is provided in Section II. We refer to ((C.1)) as the Gaussian formulation. The cGEC is verified by presenting multiple simulations in different scenarios.

The second contribution is a precise characterization of the training and generalization errors of the noise injection procedure formulated in (3) for Gaussian input and perturbation vectors. Our analysis is based on the cGEC and valid in the high–dimensional setting (i.e. $n$, $p$ and $k$ grow to infinity at finite ratios). Our predictions show that the asymptotic limit of the training and generalization errors can be precisely predicted after solving a scalar deterministic formulation. The theoretical predictions are obtained using an extended version of the convex Gaussian min-max theorem (CGMT) which we refer to as the multivariate CGMT. The new version of the CGMT accounts for the correlation introduced by injecting Gaussian noise during the learning process. Our asymptotic results hold for a general family of feature matrices, activation functions and generative models satisfying (1).

Finally, we provide a precise asymptotic characterization of the training and generalization errors corresponding to (7). We refer to this formulation as the limiting formulation.

I-D Related Work

There has been significant interest in precisely characterizing the performance of the random feature model in recent literature . The ridge regression formulation, (i.e. $\varphi(\cdot)$ is the identity function and $\Delta=0$ in (3)) is precisely analyzed in where the feature matrix is Gaussian. In a subsequent work, uses the CGMT to accurately analyze the maximum-margin linear classifier in the overparametrized regime. The work in precisely characterizes the performance of the standard formulation, i.e. $\Delta=0$, for general families of feature matrices and convex loss functions. The results presented in are derived using the non–rigorous replica method . The predictions in are rigiourously verified in using the CGMT. All the previous work consider an unperturbed formulation of the random feature model. In this paper, we study the effects of adding random noise during training. Our analysis is based on an extended version of the CGMT referred to as the multivariate CGMT. The CGMT is first used in and further developed in . It extends a Gaussian theorem first introduced in . It relies on (strong) convexity properties to prove an equivalence between two Gaussian processes. It has been successfully applied in the analysis of convex regression and convex classification formulations.

There has been significant interest in studying the effects of random noise injection during training (see e.g. ). In particular, prior literature shows that Gaussian noise injection during training improves the robustness of the network. Moreover, several recent papers show that such perturbation technique introduces some sort of regularization to the loss function. In particular, the work in shows that minimizing the worst–case loss introduces a gradient norm regularization.

Another popular perturbation approach used in regularizing learning models is the dropout method . It consists of perturbing the learning problem by randomly dropping units from the network during the training procedure. In this paper, we precisely analyze the Gaussian noise injection method and we leave the analysis of the dropout technique for future work. Our empirical studies suggest that the dropout method has a better convergence rate as compared to the noisy formulation. Moreover, they suggest that both methods have comparable generalization performance.

I-E Organization

The rest of this paper is organized as follows. Section II provides more details about the cGEC. Section III lay out the technical assumptions under which our results are derived. Section IV provides an asymptotic characterization of the noisy formulation. Our theoretical predictions hold for a general family of feature matrices, activation functions and generative models as in (1). We provide additional simulation examples for special cases of our results in Section V. The detailed proof of our theoretical predictions is provided in Section VI. Section VII concludes the paper. The appendix in Section VIII provides additional technical details.

II Gaussian Equivalence Conjecture with an Intuitive Explanation

In the standard setting, i.e. $\Delta=0$, the cGEC is equivalent to the uniform Gaussian equivalence theorem (uGET), observed and used in many earlier papers . Recently, the work in provided a rigorous proof of the uGET. Specifically, the work in proves a special case of cGEC when $\Delta=0$, the feature matrix is Gaussian and the activation functions have bounded first three derivatives. However, similar to previous literature , we conjecture that the cGEC is valid under more general settings. We believe that the analysis in can be extended to prove the cGEC and we leave the full technical details for future work.

III Technical Assumptions

In this paper, we precisely characterize the noisy formulation under the following technical assumptions.

Our theoretical predictions are valid in the high-dimensional setting where $n$, $p$ and $k$ grow to infinity at finite ratios.

Moreover, we consider the following assumption to ensure that the generalization error defined in (5) concentrates in the high–dimensional limit.

The data generating function $\varphi(\cdot)$ introduced in (1) is independent of the input vectors, the noise vectors and the feature matrix. Moreover, the following conditions are satisfied.

For any compact interval $[c,C]$, there exists a function $g(\cdot)$ such that

In addition to the assumptions in Section II, we consider the following regularity conditions for the activation function.

In addition to the assumptions discussed in Section II, we consider a family of feature matrices that satisfy the following assumption to guarantee that the Gaussian formulation converges to a deterministic problem.

We assume that $\boldsymbol{U}$ is a Haar-distributed random unitary matrix.

Based on Assumption 2, we also have the following property $\delta_{p}=k(p)/p\to\delta>0$ as $p$ grows to infinity. Our theoretical predictions use the weak convergence in Assumption 5 to fully characterize the noisy formulation.

IV Precise Analysis of the Noisy Formulation

In this section, we asymptotically analyze the noise injection procedure introduced in (3). Specifically, we provide a precise asymptotic characterization of the training and generalization errors corresponding to (3).

Before stating our technical results, we start with few definitions. Define the following two deterministic functions

Furthermore, define the following four-dimensional deterministic optimization problem

Now, we summarize our main theoretical results in the following theorem.

Suppose that the assumptions in Section III are all satisfied and the cGEC introduced in Section II is valid. Then, the training error converges in probability as follows

where $C^{\star}(\Delta,\lambda)$ is the optimal cost of the deterministic problem in (IV-A). Here, the function $h(\cdot)$ is defined as follows

Moreover, the generalization error defined in (5) converges in probability to a deterministic function as follows

where $g_{1}$ and $g_{2}$ have a bivariate Gaussian distribution with mean vector $[0,\mu_{0s}\vartheta^{\star}]$ and covariance matrix $\boldsymbol{C}$, defined as follows

where the constants $V_{1}$, $V_{2}$, $V_{3}$ and $V_{4}$ are defined as follows

Here, $q^{\star}=q^{\star}_{t^{\star},\tau^{\star}}$ is given in (11), $\boldsymbol{t}^{\star}=[t_{1}^{\star},t_{2}^{\star}]^{\top}$ and $\boldsymbol{\tau}^{\star}=[\tau_{1}^{\star},\tau_{2}^{\star}]^{\top}$. Moreover, $\{t_{1}^{\star},t_{2}^{\star},\tau_{1}^{\star},\tau_{2}^{\star}\}$ denotes the optimal solution of the problem defined in (IV-A). Also, we treat $q^{\star}$, $\boldsymbol{t}^{\star}$ and $\boldsymbol{\tau}^{\star}$ as constants independent of $\lambda$ when we compute the derivative of the function $h(\cdot)$.

IV-B Noise Regularization Effects

Suppose that the assumptions in Theorem 1 are all satisfied. Moreover, define the following formulation

Here, the regularization matrix $\boldsymbol{R}$ is defined as follows

and the new activation function $\widehat{\sigma}(\cdot)$ satisfies the properties

where $x_{1}=z+\Delta v_{1}$, $x_{2}=z+\Delta v_{2}$ and $z$, $v_{1}$ and $v_{2}$ are independent standard Gaussian random variables. Also, define $\widehat{\mathcal{E}}_{\text{train}}$ and $\widehat{\mathcal{E}}_{\text{test}}$ as the training and generalization errors corresponding to the problem in (14). Then, for any $\zeta>0$, we have the following convergence results

where ${\mathcal{E}}_{\text{test}}$ and ${\mathcal{E}}_{\text{train}}$ are the training and generalization errors corresponding to the noisy formulation.

Here, the constant $\vartheta^{\star}$ satisfies $\vartheta^{\star}=0$ if $\mu_{0}=0$ and $\vartheta^{\star}=\gamma_{3}/\mu_{0}$ otherwise, and $T_{1}$ is defined in Section IV-A. Moreover, the functions $\widehat{q}_{t,\tau}^{\star}$ and $\widehat{T}_{2,\lambda}(\cdot,\cdot)$ are defined as follows

Here, the functions $\widehat{T}_{3,\lambda}(\cdot,\cdot)$ and $\widehat{g}_{\kappa,\lambda}(\cdot,\cdot)$ are defined as follows

Suppose that the assumptions in Theorem 1 are all satisfied. Then, the training error corresponding to the limiting formulation in (14) converges in probability as follows

where $\widehat{C}^{\star}(\Delta,\lambda)$ is the optimal cost of the deterministic problem in (18). Here, the function $\widehat{h}(\cdot)$ is defined as follows

Moreover, the generalization error corresponding to the limiting formulation in (14) converges in probability to a deterministic function as follows

where $g_{1}$ and $g_{2}$ have a bivariate Gaussian distribution with mean vector $[0,\mu_{0s}\vartheta^{\star}]$ and covariance matrix $\boldsymbol{C}$, defined as follows

where the constants $V_{1}$, $V_{2}$, $V_{3}$ and $V_{4}$ are defined as follows

Here, $\widehat{q}^{\star}=\widehat{q}^{\star}_{t^{\star},\tau^{\star}}$ is given in (19). Moreover, $\{t_{1}^{\star},\tau_{1}^{\star}\}$ denotes the optimal solution of the problem defined in (18). Also, we treat $\widehat{q}^{\star}$, $t_{1}^{\star}$ and $\tau_{1}^{\star}$ as constants independent of $\lambda$ when we compute the derivative of the function $\widehat{h}(\cdot)$.

V Simulation Results

In this part, we provide additional simulation examples to verify our asymptotic results stated in Theorem 1, Theorem 2 and Lemma 1. Our predictions stated in Section IV are valid for a general family of feature matrices, activation functions and generative models satisfying (1). We specialize our general results to popular learning models.

In particular, we consider two families of feature matrices. We consider feature matrices that can be expressed as $\boldsymbol{F}=d\boldsymbol{V}$, where: (a) The scalar $d$ satisfies $d=1/\sqrt{p}$ and the matrix $\boldsymbol{V}$ has independent standard Gaussian components. We refer to this matrix as the Gaussian feature matrix. (b) The scalar $d$ satisfies $d=\sqrt{3/p}$ and the matrix $\boldsymbol{V}$ has independent uniformly distributed components in $[-1~{}1]$. We refer to this matrix as the uniform feature matrix.

Also, we consider two popular regression and classification models. For the regression model, we assume that $\varphi(\cdot)$ is the ReLu function and $\widehat{\varphi}(\cdot)$ is the identity function. For the classification model, we assume that $\varphi(\cdot)$ is the sign function with possible sign flip with probability $\theta$ and $\widehat{\varphi}(\cdot)$ is the sign function.

V-B Limiting Performance

Our fourth simulation considers the non–linear regression model. Figure 4 compares the numerical predictions and our predictions stated in Theorem 2 and Lemma 1.

V-C Impact of the Noise Variance

In this simulation example, we study the effects of the noise variance $\Delta$ on the generalization error corresponding to the noisy formulation and the limiting formulation. Here, we consider the binary classification model. Figure 5 compares the numerical predictions and our theoretical predictions stated in Theorem 1, Theorem 2 and Lemma 1.

V-D Alternative Formulations

Now, we consider the binary classification model, where $\theta=0$. We compare the performance of the noisy formulation given in (3) and the dropout technique. In this paper, we consider the following version of the dropout method

In Figure 6, we compare the performance of the noisy formulation and the dropout formulation for four different activation functions.

V-D2 Convergence Behavior

In the last simulation example, we study the convergence behavior of the noisy and dropout formulations for different activation functions. Figure 7 first shows that our theoretical predictions stated in Theorem 1, Theorem 2 and Lemma 1 match with the actual performance of the noisy formulation and its limiting formulation. This gives another empirical verification of our predictions.

VI Technical Details: Analysis of the Noisy Formulation

In this part, we provide a rigorous proof of the predictions stated in Theorem 1, Theorem 2 and Lemma 1. To this end, we suppose that the assumptions considered in Sections II and III are all satisfied. We derive our theoretical results using an extended version of the CGMT framework which we refer to as the multivariate CGMT.

To derive the asymptotic results stated in Theorem 1, Theorem 2 and Lemma 1, we use an extended version of the CGMT framework introduced in . The CGMT is used to accurately analyze a generally hard primary formulation by introducing an asymptotically equivalent auxiliary optimization problem. In this paper, we consider primary optimization problems of the following form

There exists a constant $\phi$ such that the optimal cost $\phi_{k}$ converges in probability to $\phi$ as $k$ goes to $+\infty$.

There exists a constant $\phi^{c}$ such that the optimal cost $\phi^{c}_{k}$ converges in probability to $\phi^{c}$ as $k$ goes to $+\infty$, for any fixed $\epsilon>0$.

There exists a positive constant $\zeta>0$ such that $\phi^{c}\geq\phi+\zeta$, for any fixed $\epsilon>0$.

Then, the following convergence in probability holds

for any fixed $\epsilon>0$, where $\Phi_{k}$ and $\widehat{\boldsymbol{w}}_{k}$ are the optimal cost and the optimal solution of the multivariate PO formulation in (22).

The above theorem allows us to analyze the generally easy multivariate AO formulation given in (23) to infer asymptotic properties of the generally hard multivariate PO formulation in (22). The proof of Theorem 3 follows by showing that the formulation in (23) and the following formulation

Combining this result with the assumptions of Theorem 3 completes the proof. We omit the detailed proof since it is similar to the analysis in and . We refer to Theorem 3 as the multivariate convex Gaussian min-max theorem (multivariate CGMT).

Next, we use the multivariate CGMT to rigorously prove the technical results provided in Theorem 1, Theorem 2 and Lemma 1. Our approach is to reformulate the Gaussian formulation in ((C.1)) in the form of the multivariate PO problem given in (22). Then, use the multivariate CGMT framework to show that the formulation in (3) is asymptotically equivalent to an easier formulation that can be written in the form of the multivariate AO problem given in (23). The next step is to show that the multivariate AO formulation converges in probability to a deterministic problem that can be expressed in the form of the formulation given in (IV-A).

VI-B Asymptotic Analysis of the Noisy Formulation

In this part, we provide the technical steps to obtain the theoretical results stated in Theorem 1. Specifically, we use the multivariate CGMT framework to precisely analyze the noisy formulation introduced in (3). Next, we suppose that the assumptions introduced in Section III are all satisfied.

Based on the cGEC introduced in Section II, it suffices to precisely analyze the Gaussian formulation in the large system limit. Then, it suffices to analyze the following formulation

Note that the formulation in (VI-B1) is strongly convex with a strong convexity parameter equals to $\lambda$. This means that it has a unique optimal solution. Note that the multivariate CGMT framework assumes that the feasibility sets of the multivariate PO formulation in (22) are compact. The following lemma shows that this assumption is satisfied by our formulation.

Assume that $\widehat{\boldsymbol{w}}_{p}$ is the unique optimal solution of the formulation given in (VI-B1). Then, there exist two positive constants $C_{w}>0$ and $C_{\vartheta}>0$ such that

where the second asymptotic result is valid only when $\mu_{0}\neq 0$.

Given that the loss function in (VI-B1) is proper and strongly convex, one can use the results in [16, Lemma 1] to prove Lemma 2. This asymptotic result follows using Assumptions 3, 4, and 5 and [34, Theorem 2.1]. Combining this result with the theoretical result stated in [16, Proposition 1], the Gaussian formulation is asymptotically equivalent to the following formulation

Assume that $\widehat{\boldsymbol{u}}_{p}$ is the unique optimal solution of the formulation given in (28). Then, there exists a positive constants $C_{u}>0$ such that

This result can also be proved using similar steps as in [16, Lemma 2]. Specifically, we can use the result in [35, Proposition 11.3] to show the compactness of the optimal dual vector $\widehat{\boldsymbol{u}}_{p}$. The results in Lemma 2 and Lemma 3 show that the Gaussian formulation is asymptotically equivalent to the following formulation

Next, we focus on precisely analyzing the formulation in (30). Now, note that the label vector $\boldsymbol{y}$ depend on the Gaussian matrix $\boldsymbol{A}$. Then, we decompose $\boldsymbol{A}$ as follows

The above results show that it suffices to precisely analyze the formulation given in (33). Moreover, note that (33) can be equivalently formulated as follows

We can notice that the optimization problem formulated in (35) is in the form of the multivariate PO problem given in (22). Therefore, applying the multivariate CGMT, the corresponding multivariate AO problem can be expressed as follows

VI-B2 Simplifying the Multivariate Auxiliary Formulation

Now, we are ready to further simplify the multivariate AO formulation. The first step is to fix $t_{1}$ and $t_{2}$ and solve the formulation in (37) over the direction of the independent vectors $\boldsymbol{u}_{1}$ and $\boldsymbol{u}_{-1}$. Specifically, based on the result in Lemma 3, the formulation given in (37) can be simplified as follows

Note that the difference between the cost functions of the formulations in (38) and (39) are terms that converge in probability to zero. Before showing the asymptotic equivalence between the formulations in (38) and (39), we provide important convexity properties of the optimization problem in (39) as given in the following lemma.

Define $\widehat{f}_{p,2}$ as the cost function of the problem in (39). Then, $\widehat{f}_{p,2}$ is strongly convex in the vector $\boldsymbol{w}$ where $\lambda$ is a strong convexity parameter. Moreover, it is strongly concave in the variables $t_{1}$ and $t_{2}$ in the feasibility sets where $-1$ is a strong concavity parameter.

The strong convexity can be proved by observing that the cost function of (39) is a positive sum of convex and strongly convex functions in terms of $\boldsymbol{w}$ for fixed feasible $t_{1}$ and $t_{2}$. Moreover, note that the term ${\sqrt{t_{1}^{2}+t_{2}^{2}}}\boldsymbol{g}_{2}^{\top}\boldsymbol{\Gamma}^{\frac{1}{2}}\boldsymbol{w}$ can be replaced with $t_{1}\boldsymbol{g}_{21}^{\top}\boldsymbol{\Gamma}^{\frac{1}{2}}\boldsymbol{w}+t_{2}\boldsymbol{g}_{22}^{\top}\boldsymbol{\Gamma}^{\frac{1}{2}}\boldsymbol{w}$ without changing the statistics of our formulation, where $\boldsymbol{g}_{21}$ and $\boldsymbol{g}_{22}$ are two independent Gaussian vectors. Then, one can see that the cost function of (39) is strongly concave in the variables $t_{1}$ and $t_{2}$ where $-1$ is a strong concavity parameter. ∎

Lemma 4 provides important convexity properties of the optimization problem formulated in (39). These properties are essential to prove the equivalence between (38) and (39) as stated in the following lemma.

Define $\widehat{\mathcal{S}}^{\star}_{p,1}$ and $\widehat{\mathcal{S}}^{\star}_{p,2}$ as the sets of optimal solutions of the minimization problems in (38) and (39), respectively. Moreover, let $\widehat{O}^{\star}_{p,1}$ and $\widehat{O}^{\star}_{p,2}$ be the optimal objective values of the optimization problems in (38) and (39), respectively. Then, the following convergence in probability holds

The detailed proof of Lemma 5 is deferred to Appendix VIII-A. Lemma 5 particularly shows that the optimization problems in (38) and (39) are asymptotically equivalent. Then, it suffices to precisely analyze the formulation in (39). To solve over the primal vector $\boldsymbol{w}$, we introduce two independent scalar optimization variables $\tau_{1}$ and $\tau_{2}$ where they both solve optimization problems of the following form

Here, note that the optimal solution of the problem in (41) can be expressed as $\tau^{\star}=\sqrt{x}$. Next, we use the identity in (41) to transform the non-smooth square roots in the cost function of the formulation given in (39) to smooth terms. This is an essential step to solve over the primal vector $\boldsymbol{w}$. Specifically, based on the result in Lemma 2, our multivariate AO formulation given in (39) can be expressed as follows

There exist positive constants independent of $p$, $c_{\tau_{1}}>0$, $C_{\tau_{1}}>0$, $c_{\tau_{2}}>0$ and $C_{\tau_{2}}>0$, such that the following convergence in probability holds

where $\widehat{\tau}_{1}$ and $\widehat{\tau}_{2}$ are the optimal solutions of the formulation in (LABEL:ana_fm7).

The detailed proof of Lemma 6 is provided in Appendix VIII-B. Based on Lemmas 4 and 6, the optimization problem given in (LABEL:ana_fm7) is asymptotically equivalent to the following problem

where $C_{q}>0$ and $C_{r}>0$ are two positive constants selected to satisfy the asymptotic result in Lemma 2. Here, we also drop terms that converge in probability to zero. One way to justify this step is using similar analysis as in Lemma 5. Note that the convexity results in Lemma 4 are still satisfied by the formulation in (LABEL:ana_fm8). Specifically, the cost function in (LABEL:ana_fm8) is jointly strongly convex in the minimization variables and jointly strongly concave in the maximization variables.

where $\bar{\boldsymbol{B}}^{\perp}_{\boldsymbol{v}}=({\boldsymbol{B}}^{\perp}_{\boldsymbol{v}})^{\top}$. After computing the derivative of the function $g(\cdot)$ and setting it to zero, the optimal solution of the unconstrained version of minimizing the function $g(\cdot)$ can be expressed as follows

Similar to the analysis in Lemmas 2, 3 and 6, one can show that the norm of the optimal vector $\widetilde{\boldsymbol{r}}^{\star}$ is bounded. This means that $\widetilde{\boldsymbol{r}}^{\star}$ is an optimal solution of the formulation in (LABEL:ana_fm8). Then, the optimal loss function can be expressed as follows

Based on the SVD decomposition of the matrix $\boldsymbol{M}$, it can be checked that the last term in the multivariate AO formulation given in (LABEL:ana_fm8) is zero. Then, the formulation given in (LABEL:ana_fm8) can be expressed as follows

where $\boldsymbol{t}=[t_{1},t_{2}]^{\top}$ and $\boldsymbol{\tau}=[\tau_{1},\tau_{2}]^{\top}$. Here, $\boldsymbol{1}_{n}$ denotes the vector of all one with size $n$ and the functions $V_{p,2}(\cdot,\cdot)$, $V_{p,3}(\cdot,\cdot)$ and $V_{p,4}(\cdot,\cdot)$ depend on the optimization variables and are given by

Note that we simplified the multivariate AO formulation given in (36) to a scalar optimization problem as given in (51). Then, it remains to study the asymptotic properties of the scalar formulation in (51). We refer to this problem as the scalar formulation.

VI-B3 Asymptotic Analysis of the Scalar Formulation

In this part, we study the asymptotic properties of the scalar formulation in (51) corresponding to the multivariate AO problem. Based on Assumption 5 and the result in [37, Proposition 3], the random variable ${T}_{p,1}$ converges pointwisely in probability to the scalar $T_{1}$ defined as follows

where $\boldsymbol{t}=[t_{1},t_{2}]^{\top}$ and $\boldsymbol{\tau}=[\tau_{1},\tau_{2}]^{\top}$. Then, using the theoretical results in and based on Assumption 5, the random function $V_{p,2}(\cdot,\cdot)$ converges pointwisely in probability as follows

where the random function $\widehat{V}_{p,4}(\cdot,\cdot)$ is defined as follows

Here, $\text{Tr}[.]$ represents the trace. Additionally, the matrix $\widehat{\boldsymbol{\Sigma}}$ is given as $\widehat{\boldsymbol{\Sigma}}=\widetilde{\mu}_{1}^{2}\boldsymbol{F}^{\top}\boldsymbol{F}+\mu_{2}^{2}\boldsymbol{I}_{k}$ and the matrix $\widehat{\boldsymbol{G}}$ has the following expression $\widehat{\boldsymbol{G}}={t_{1}\mathinner{\!\left\lVert\boldsymbol{h}_{1}\right\rVert}^{2}}/{(\tau_{1}n)}\widehat{\boldsymbol{\Sigma}}+{\zeta_{p,t,\tau}}/{n}\boldsymbol{\Gamma}$. Using again [37, Proposition 3] and Assumption 5, we can also see that the random function $V_{p,4}(\cdot,\cdot)$ converges in probability to the function $V_{4}(\cdot,\cdot)$ defined as follows

Now, it remains to study the asymptotic properties of the random function $V_{p,3}(\cdot,\cdot)$. Based on the block matrix inversion lemma, it can be checked that the random function $V_{p,3}(\cdot,\cdot)$ satisfies the following

Here, the random function $T_{p,2}(\cdot,\cdot)$ is defined as follows

Using the matrix inversion lemma, it can be checked that the random function $T_{p,2}(\cdot,\cdot)$ converges in probability to the function $T_{2,\lambda}(\cdot,\cdot)$ defined as follows

where the function $g_{\kappa,\lambda}(\cdot,\cdot)$ is defined in Section IV. Additionally, using the weak law of large numbers (WLLN), we have the following convergence property

is the converging limit of the cost function the scalar formulation in (51), where the function $T_{3,\lambda}(\cdot,\cdot)$ is given by $V_{4}(\boldsymbol{t},\boldsymbol{\tau})/\eta$. Before continuing our analysis, we summarize convexity properties of the cost function of (61) in the following lemma.

Define $\widehat{f}$ as the cost function of the problem in (61) defined in the feasibility set. Then, $\widehat{f}$ is jointly strongly convex in the variables $(q,\vartheta,\tau_{1},\tau_{2})$ for fixed feasible $(t_{1},t_{2})$. Moreover, it is jointly strongly concave in the variables $(t_{1},t_{2})$ for fixed feasible $(q,\vartheta,\tau_{1},\tau_{2})$.

This result can be proved by observing that the strong convexity parameters in Lemma 4 are independent of $p$ and that the operations performed after Lemma 4 preserve the convexity properties. Another property of the scalar formulation is that its set of optimal solutions concentrates around the set of optimal solutions of the formulation in (61) as summarized in the following lemma.

Define $\tau_{p,1}^{\star}$, $\tau_{p,2}^{\star}$, $t_{p,1}^{\star}$, $t_{p,2}^{\star}$ and $q_{p}^{\star}$ as the optimal solutions of the scalar formulation given in (51). Additionally, define $\tau_{1}^{\star}$, $\tau_{2}^{\star}$, $t_{1}^{\star}$, $t_{2}^{\star}$ and $q^{\star}$ as the optimal solutions of the deterministic optimization problem given in (61). Therefore, the following convergence in probability holds

Moreover, define $\vartheta_{p}^{\star}$ and $\vartheta^{\star}$ as the optimal solutions of the minimization problems of (51) and (61) over $\vartheta$ in the feasibility set defined in (27). Then, we also have the following convergence in probability

The convergence result in (LABEL:sop_conv) follows using [38, Theorem 2.1]. We can see that all the assumptions in [38, Theorem 2.1] are satisfied by the formulations in (51) and (61). Moreover, the result in (63) follows using [16, Proposition 2]. The detailed proof is omitted since it follows similar ideas as in Proposition $4$ and Proposition $5$ in . Based on , we can further simplify the formulation in (61) by solving the minimization problem over the variables $q$ and $\vartheta$. Note that the optimal $\vartheta^{\star}$ satisfies $\vartheta^{\star}=0$ if $\mu_{0}=0$ and $\vartheta^{\star}=\gamma_{3}/\mu_{0}$ otherwise. Furthermore, the optimal $q$ denoted by $q_{t,\tau}^{\star}$ can be expressed as follows

Observe that the optimal solutions, $\vartheta^{\star}$ and $q_{t,\tau}^{\star}$, satisfy the boundedness constraints. Moreover, note that our results are valid for any bounds that satisfy the results in Lemmas 2, 3 and 6. Now that we obtained the asymptotic scalar optimization problem, it remains to study the asymptotic behavior of the training and generalization errors.

VI-B4 Asymptotic Analysis of the Training and Generalization Errors

First, the generalization error is given by

where $\boldsymbol{a}_{\text{new}}$ is an unseen data sample and $\widehat{\boldsymbol{w}}$ is the optimal solution of the noisy formulation. Based on the uniform Gaussian equivalence theorem (uGET), observed and proved in many earlier papers , the asymptotic properties of the generalization error are equivalent to the asymptotic properties of $\overline{\mathcal{E}}_{\text{test}}$ defined as follows

Given the optimal solutions $\widehat{\boldsymbol{w}}$ and $\widehat{\vartheta}_{p}$, the random variables $g_{1}$ and $g_{2}$ have a bivariate Gaussian distribution with mean vector $[0,\mu_{0s}\widehat{\vartheta}_{p}]^{\top}$ and covariance matrix given by

Define the random variables $\widehat{q}_{p}^{\star}$, $\widehat{\beta}_{p}^{\star}$ and $\widehat{r}_{p}^{\star}$ as follows

where $\bar{\boldsymbol{v}}=\boldsymbol{v}/\mathinner{\!\left\lVert\boldsymbol{v}\right\rVert}$ and the vector $\boldsymbol{v}$ is defined as $\boldsymbol{v}=\boldsymbol{F}^{\top}{\boldsymbol{\xi}}$. Then, the covariance matrix $\boldsymbol{C}_{p}$ can be expressed as follows

Hence, to study the asymptotic properties of the generalization error, it suffices to study the asymptotic properties of $\widehat{\vartheta}^{\star}_{p}$, $\widehat{q}^{\star}_{p}$, $\widehat{\beta}^{\star}_{p}$ and $\widehat{r}^{\star}_{p}$. The following lemma summarizes the asymptotic properties of our primal formulation given in (27).

The random variables $\widehat{\vartheta}^{\star}_{p}$, $\widehat{q}^{\star}_{p}$, $\widehat{\beta}^{\star}_{p}$ and $\widehat{r}^{\star}_{p}$ converge in probability as follows

where $q^{\star}$ and $\vartheta^{\star}$ are optimal solutions of the deterministic scalar formulation in (61). Moreover, the function $h(\cdot)$ and $\beta^{\star}$ are defined in Theorem 1.

Note that the analysis in Section VI-B2 shows that the scalar formulation given in (51) is a simplified version of the multivariate AO formulation given in (36). Define the random variable $\widetilde{\vartheta}_{p}^{\star}$ as the optimal solution of the minimization of the problem (36) over $\vartheta$ in the feasibility set defined in (27). Moreover, define the random variables $\widetilde{q}_{p}^{\star}$, $\widetilde{\beta}_{p}^{\star}$ and $\widetilde{r}_{p}^{\star}$ as follows

where $\widetilde{\boldsymbol{w}}$ is the optimal solution of the multivariate AO formulation given in (36). Based on the decomposition in (45), note that $\widetilde{\beta}^{\star}_{p}$ satisfies the following expression

where $\widetilde{\boldsymbol{r}}^{\star}$ is defined in (49) and is the optimal solution of minimizing the function $g(\cdot)$ introduced in (47). Substituting the expression of $\widetilde{\boldsymbol{r}}^{\star}$ given in (49), performing the same analysis as in Section VI-B3 and using the convergence result in (LABEL:sop_conv), it can be shown that the random quantity $\widetilde{\beta}^{\star}_{p}$ converges in probability to $\beta^{\star}$ defined in (1). Additionally, observe that $\widetilde{r}_{p}^{\star}$ can be expressed as follows

Define the function $h_{p}\mathrel{\mathop{\mathchar 58\relax}}\lambda\to-(\widetilde{q}^{\star}_{p})^{2}V_{p,3}(\boldsymbol{t}^{\star}_{p},\boldsymbol{\tau}^{\star}_{p})-V_{p,4}(\boldsymbol{t}^{\star}_{p},\boldsymbol{\tau}^{\star}_{p})$, where the random functions $V_{p,3}(\cdot,\cdot)$ and $V_{p,4}(\cdot,\cdot)$ are defined in (52) and where $\boldsymbol{t}^{\star}_{p}=[t_{p,1}^{\star},t_{p,2}^{\star}]^{\top}$ and $\boldsymbol{\tau}^{\star}_{p}=[\tau_{p,1}^{\star},\tau_{p,2}^{\star}]^{\top}$. Here, $\{t_{p,1}^{\star},t_{p,2}^{\star},\tau_{p,1}^{\star},\tau_{p,2}^{\star}\}$ are defined in Lemma 8. Given the expression of $\widetilde{\boldsymbol{r}}^{\star}$ in (49), we can see that $\widetilde{r}_{p}^{\star}$ can be expressed as follows

where the optimal solutions are treated as constants independent of $\lambda$. Performing the same analysis as in Section VI-B3 and using the convergence result in (LABEL:sop_conv), it can be shown that the random quantity $\widetilde{r}_{p}^{\star}$ converges in probability as follows

where $q^{\star}$ is the optimal solution of (61) and the function $h(\cdot)$ is defined in Theorem 1. Given that the scalar formulation given in (51) is a simplified version of the multivariate AO formulation and based on Lemma 8, we obtain the following asymptotic properties

where $q^{\star}$ and $\vartheta^{\star}$ are the optimal solutions of the deterministic scalar formulation in (61). Following a similar analysis as in , we can show that the assumptions in Theorem 3 are all satisfied. The main idea is to define the set $\mathcal{S}_{p,\epsilon}$ introduced in Theorem 3 as

Then, use the strong convexity properties of the formulation in (LABEL:ana_fm8) to prove that the assumptions in Theorem 3 are satisfied. This means that $\widehat{\vartheta}^{\star}_{p}$, $\widehat{q}^{\star}_{p}$, $\widehat{\beta}^{\star}_{p}$ and $\widehat{r}^{\star}_{p}$ defined in (65) concentrates around the same values as $\widetilde{\vartheta}^{\star}_{p}$, $\widetilde{q}^{\star}_{p}$, $\widetilde{\beta}^{\star}_{p}$ and $\widetilde{r}^{\star}_{p}$ defined in (68). ∎

Now, to show the convergence of the generalization error in Theorem 1, it suffices to show that $\overline{\mathcal{E}}_{\text{test}}$ is a continuous function in $\widehat{\vartheta}^{\star}_{p}$, $\widehat{q}^{\star}_{p}$, $\widehat{\beta}^{\star}_{p}$ and $\widehat{r}^{\star}_{p}$. Based on Assumption 3, the functions $\varphi(\cdot)$ and $\widehat{\varphi}(\cdot)$ are square integrable over Gaussian distributions. Moreover, the optimal solutions $\widehat{\vartheta}^{\star}_{p}$, $\widehat{q}^{\star}_{p}$, $\widehat{\beta}^{\star}_{p}$ and $\widehat{r}^{\star}_{p}$ are bounded. Based on Assumption 3 and the continuity under integral sign property , the continuity of $\overline{\mathcal{E}}_{\text{test}}$ follows. These properties lead to the convergence result given in (20) in Theorem 1. Based on the analysis in Lemma 9 and Theorem 3, the optimal cost value of the noisy formulation converges in probability to the optimal cost value of the deterministic formulation in (61). Combining this result with the asymptotic property stated in (72) shows the convergence of the training error stated in Theorem 1.

VI-C Large Number of Noise Injections

where $\boldsymbol{t}=[t_{1},t_{2}]^{\top}$ and $\boldsymbol{\tau}=[\tau_{1},\tau_{2}]^{\top}$. Here, the functions $T_{2,\lambda}(\cdot,\cdot)$ and $q_{t,\tau}^{\star}$ are the same as the ones provided in Section IV. Furthermore, the functions $T_{3,\lambda}(\cdot,\cdot)$ and $g_{\kappa,\lambda}(\cdot,\cdot)$ are given as follows

Now, we focus on analyzing the formulation in (76) when the number of noise injections grows to infinity. The following lemma summarizes our main technical results.

The convergence result in Lemma 10 follows using [38, Theorem 2.1]. Specifically, we use the strong convexity property in Lemma 7. Also, we use the pointwise convergence of the cost functions based on Assumptions 4 and 5 and the dominated convergence theorem. This shows that all the assumptions in [38, Theorem 2.1] are satisfied by the formulation in (76) and its asymptotic formulation mentioned in Lemma 10. Next, we refer to the asymptotic limit obtained in Lemma 10 as the asymptotic deterministic formulation.

Performing a similar analysis as in Sections VI-B1, VI-B2 and VI-B3, it can be checked that the asymptotic deterministic formulation obtained in Lemma 10 is the asymptotic limit of the following formulation

Here, the regularization matrix $\boldsymbol{R}$ is defined as follows

and the new activation function $\widehat{\sigma}(\cdot)$ satisfies the following properties

We can see that the optimal solution of the max-min problem in (VI-C), denoted by $t^{\star}$ and $\tau^{\star}$, satisfies $t^{\star}=\tau^{\star}$. This trick can be used in the CGMT framework to show that the asymptotic limit of the formulation in (77) can also be expressed as follows

where the constant $\vartheta^{\star}$ satisfies $\vartheta^{\star}=0$ if $\mu_{0}=0$ and $\vartheta^{\star}=\gamma_{3}/\mu_{0}$ otherwise. Moreover, $q_{t,\tau,\infty}^{\star}$ is defined as follows

Here, the functions $T_{2,\lambda,\infty}(\cdot,\cdot)$, $T_{3,\lambda,\infty}(\cdot,\cdot)$ and $g_{\kappa,\lambda,\infty}(\cdot,\cdot)$ can be expressed as follows

The property in (VI-C) can also be used to show that the optimal solution $t_{2}^{\star}$ and $\tau_{2}^{\star}$ of the asymptotic deterministic formulation obtained in Lemma 10 satisfy $t_{2}^{\star}=\tau_{2}^{\star}$. This then leads to the formulation in (LABEL:scprob1_asy_pf).

Now, define the asymptotic training and generalization errors stated in Theorem 1 as $\mathcal{E}_{\text{train},\infty}$ and $\mathcal{E}_{\text{test},\infty}$, respectively. Then, the asymptotic training error converges as follows

where $C^{\star}(\Delta,\lambda)$ is the optimal cost of the deterministic problem in (LABEL:scprob1_asy_pf). Here, the function $h_{\infty}(\cdot)$ is defined as follows

Moreover, the asymptotic generalization error converges as follows

where $g_{1}$ and $g_{2}$ have a bivariate Gaussian distribution with mean vector $[0,\mu_{0s}\vartheta^{\star}]$ and covariance matrix $\boldsymbol{C}$, defined as follows

where the constants $V_{1}$, $V_{2}$, $V_{3}$ and $V_{4}$ are defined as follows

Here, $q^{\star}=q^{\star}_{t^{\star},\tau^{\star},\infty}$ satisfies the expression in (82). Moreover, $t_{1}^{\star}$ and $\tau_{1}^{\star}$ denote the optimal solution of the problem defined in (LABEL:scprob1_asy_pf). Also, we treat $q^{\star}$, $t_{1}^{\star}$ and $\tau_{1}^{\star}$ as constants independent of $\lambda$ when we compute the derivative of the function $h_{\infty}(\cdot)$. The results in (84) and (85) can be proved using a similar analysis as in Section VI-B4. Performing a similar analysis as in Sections VI-B1, VI-B2, VI-B3 and VI-B4, it can be checked that the training and generalization errors corresponding to the formulation in (77) converge in probability to the limiting functions obtained in (84) and (85), respectively.

Note that the analysis in this Section is valid for any bounds that satisfy the theoretical results in Lemmas 2, 3 and 6. Moreover, observe that the cost functions of both deterministic problems in (61) and (LABEL:scprob1_asy_pf) diverge when $t_{1}$, $t_{2}$, $\tau_{1}$ or $\tau_{2}$ grows to infinity or when $\tau_{1}$ or $\tau_{2}$ goes to . This means that the solution of the unconstrained version of the formulations in (61) and (LABEL:scprob1_asy_pf) should satisfy the feasibility constraints in (61) and (LABEL:scprob1_asy_pf). This means that the optimization problems in (61) and (LABEL:scprob1_asy_pf) can be equivalently formulated as in (IV-A) and (18). This completes the proof of Theorem 1, Theorem 2 and Lemma 1.

VII Conclusion

In this paper, we precisely analyzed a random perturbation method used to regularize machine learning problems. Specifically, we provided an accurate characterization of the training and generalization errors corresponding to the noisy feature formulation. Our predictions are based on a correlated Gaussian equivalence conjecture and an extended version of the CGMT, referred to as the multivariate CGMT. Moreover, our analysis shows that Gaussian noise injection in the input data has the same effects of a weighted ridge regularization when the number of noise samples grows to infinity. Additionally, it provides the explicit dependence of the introduced regularization on the feature matrix, the activation function and the noise variance. Simulation results validate our predictions and show that inserting noise during training moves the interpolation threshold and can mitigate the double descent phenomenon in the generalization error.

VIII Appendix: Additional Technical Details

In this part, we provide additional technical details to prove the results stated in Theorem 1, Theorem 2 and Lemma 1. Specifically, we provide a rigorous proof of the theoretical results stated in Lemma 5 and Lemma 6.

The optimization problems given in (38) and (39) share the same feasibility set $\mathcal{D}$ which we define as follows

Define $\widehat{f}_{p,1}$ as the cost function of the optimization problem given in (38) and define $\widehat{f}_{p,2}$ as the cost function of the optimization problem given in (39). Note that the following inequality $\mathinner{\!\left\lvert\sqrt{x}-\sqrt{y}\right\rvert}\leq\sqrt{\mathinner{\!\left\lvert x-y\right\rvert}}$ is true for any $x\geq 0$ and $y\geq 0$. Therefore, we have the following inequality

where we perform the change of variable $t_{1}=t_{1}/\sqrt{n}$ and $t_{2}=t_{2}/\sqrt{n}$. Here, $Z_{p,1}$ is defined as follows

Given that the set $\mathcal{D}$ is bounded and based on Assumptions 4 and 5, $Z_{p,1}$ and $Z_{p,2}$ can be bounded by a constant independent of the optimization variables. Combining this with the weak law of large numbers, one can see that the right hand side of (88) converges in probability to zero. Then, we obtain the following convergence in probability

Moreover, the following two properties are true for bounded functions

Given that the functions $\widehat{f}_{p,1}$ and $\widehat{f}_{p,2}$ are bounded in the set $\mathcal{D}$ and the result in (91), we get the following convergence in probability

where $\widehat{O}^{\star}_{p,1}$ and $\widehat{O}^{\star}_{p,2}$ are the optimal objective values of the optimization problems given in (38) and (39), respectively. Now, define $\widehat{\mathcal{S}}^{\star}_{p,1}$ and $\widehat{\mathcal{S}}^{\star}_{p,2}$ as the set of optimal solutions of the minimization problems in (38) and (39), respectively. Next, the objective is to show that

Moreover, define the functions $\widetilde{f}_{p,1}$ and $\widetilde{f}_{p,2}$ as follows

Note that the set $\widehat{\mathcal{S}}^{\star}_{p,1}$ is the set of minimizing $\boldsymbol{w}$ of the first function in (95). Based on Lemma 4, the function $\widetilde{f}_{p,2}$ is strongly convex in the feasibility set where $\lambda$ is a strong convexity parameter. This means that it has a unique minimizer denoted by $\boldsymbol{w}_{p,2}^{\star}$. Now, assume that $\boldsymbol{w}_{p,1}^{\star}$ is a minimizer of the function $\widetilde{f}_{p,1}$. Moreover, assume that there exists $\gamma>0$ independent of $p$ such that the following convergence holds true

Given the strong convexity of the function $\widetilde{f}_{p,2}$, we have the following inequality

where this is valid for any $\beta\in$ and feasible $\boldsymbol{w}_{1}$ and $\boldsymbol{w}_{2}$. Take $\boldsymbol{w}_{1}=\boldsymbol{w}_{p,1}^{\star}$, $\boldsymbol{w}_{2}=\boldsymbol{w}_{p,2}^{\star}$ and $\beta=1/2$. Based on the fact that $\boldsymbol{w}_{p,2}^{\star}$ is a minimizer of the function $\widetilde{f}_{p,2}$, there exists $\gamma>0$ independent of $p$ such that

Next, we use the convergence in probability established in (91) and (93) to show that the result in (98) produces a contradiction. To this end, note that the following inequality is always valid

which means that the following inequality is always true

Observe that the inequality derived in (100) implies that the following inequality holds true

Now, based on (91), (92) and (93), the right hand side of (100), converges in probability to zero. This means that the following convergence in probability holds

This means that the following convergence in probability is true

VIII-B Proof of Lemma 6: Additional Compactness

We start our prove by analyzing the feasibility sets of the primal formulation in (28). Note that the optimal solution of the formulation given in (28) can be expressed in closed form as follows

with probability going to $1$ as $p$ grows to $+\infty$. Therefore, there exists a positive constant $C_{2}>0$ such that

where $\sigma_{\text{min}}(\cdot)$ denotes the minimum eigenvalue. Now, observe that

where $\boldsymbol{B}=\bar{\boldsymbol{G}}\boldsymbol{\Sigma}^{\frac{1}{2}}+\boldsymbol{T}\boldsymbol{\Gamma}^{\frac{1}{2}}$. Given that the random quantities $\boldsymbol{s}$, $\boldsymbol{G}$ and $\boldsymbol{T}$ have independent standard Gaussian components, we have the following

Moreover, using the weak law of large numbers and Assumptions 3 and 5, we obtain the following asymptotic results

Combining this with Assumptions 3, 4 and 5, we obtain the following inequality

valid with probability going to $1$ as $p$ grows to infinity. This shows that there exists a positive constant $c_{w}>0$ such that

with probability going to $1$ as $p$ grows to infinity. Then, we can apply the multivariate CGMT framework with the additional constraint in (113). Based on this result and Assumption 4, there exists positive constants $c_{\tau_{1}}>0$, $C_{\tau_{1}}>0$, $c_{\tau_{2}}>0$ and $C_{\tau_{2}}>0$, such that the following convergence in probability holds

where $\widehat{\tau}_{1}$and $\widehat{\tau}_{2}$ are the optimal solutions of the formulation in (LABEL:ana_fm7). This completes the proof of Lemma 6.

References