Label Noise SGD Provably Prefers Flat Global Minimizers

Introduction

One of the central questions in modern machine learning theory is the generalization capability of overparametrized models trained by stochastic gradient descent (SGD). Recent work identifies the implicit regularization effect due to the optimization algorithm as one key factor in explaining the generalization of overparameterized models . This implicit regularization is controlled by many properties of the optimization algorithm including search direction , learning rate , batch size , momentum and dropout .

The parameter-dependent noise distribution in SGD is a crucial source of regularization . Blanc et al. initiated the study of the regularization effect of label noise SGD with square lossLabel noise SGD computes the stochastic gradient by first drawing a sample $(x_{i},y_{i})$, perturbing $y^{\prime}_{i}=y_{i}+\epsilon$ with $\epsilon\sim\{-\sigma,\sigma\}$, and computing the gradient with respect to $(x_{i},y^{\prime}_{i})$. by characterizing the local stability of global minimizers of the training loss. By identifying a data-dependent regularizer $R(\theta)$, Blanc et al. proved that label noise SGD locally diverges from the global minimizer $\theta^{\ast}$ if and only if $\theta^{\ast}$ is not a first-order stationary point of

The analysis is only able to demonstrate that with sufficiently small step size $\eta$, label noise SGD initialized at $\theta^{\ast}$ locally diverges by a distance of $\eta^{0.4}$ and correspondingly decreases the regularizer by $\eta^{0.4}$. This is among the first results that establish that the noise distribution alters the local stability of stochastic gradient descent. However, the parameter movement of $\eta^{0.4}$ is required to be inversely polynomially small in dimension and condition number and is thus too small to affect the predictions of the model.

HaoChen et al. , motivated by the local nature of Blanc et al. , analyzed label noise SGD in the quadratically-parametrized linear regression model . Under a well-specified sparse linear regression model and with isotropic features, HaoChen et al. proved that label noise SGD recovers the sparse ground-truth despite overparametrization, which demonstrated a global implicit bias towards sparsity in the quadratically-parametrized linear regression model.

This work seeks to identify the global implicit regularization effect of label noise SGD. Our primary result, which supports Blanc et al. , proves that label noise SGD converges to a stationary point of $L(\theta)+\lambda R(\theta)$, where the regularizer $R(\theta)$ penalizes sharp regions of the loss landscape.

The focus of this paper is on label noise SGD due to its strong regularization effects in both real and synthetic experiments . Furthermore, label noise is used in large-batch training as an additional regularizer when the regularization from standard regularizers (e.g. mini-batch, batch-norm, and dropout) is not sufficient. Label noise SGD is also known to be less sensitive to initialization, as shown in HaoChen et al. . In stark contrast, mini-batch SGD remains stuck when initialized at any poor global minimizer. Our analysis demonstrates a global regularization effect of label noise SGD by proving it converges to a stationary point of a regularized loss $L(\theta)+\lambda R(\theta)$, even when initialized at a zero error global minimum.

The learning rate and minibatch size in SGD are also known to be important sources of regularization . Our main theorem highlights the importance of learning rate and batch size as the hyperparameters that control the balance between the loss and the regularizer – larger learning rate and smaller batch size leads to stronger regularization.

Section 2 reviews the notation and assumptions used throughout the paper. Section 2.4 formally states the main result and Section 3 sketches the proof. Section 4 presents experimental results which support our theory. Finally, Section 6 discusses the implications of this work.

Problem Setup and Main Result

Section 2.1 describes our notation and the SGD with label noise algorithm. Section 2.2 introduces the explicit formula for the regularizer $R(\theta)$. Sections 2.3 and 2.4 formally state our main result.

Note that $\sigma$ controls the strength of the label noise and will control the strength of the implicit regularization in Theorem 1. Throughout the paper we will use $\|\cdot\|=\|\cdot\|_{2}$. We make the following standard assumption on $f$:

In addition, we make the following local Kurdyka-Łojasiewicz assumption (KL assumption) which ensures that there are no regions where the loss is very flat. The KL assumption is very general and holds for some $\delta>0$ for any analytic function defined on a compact domain (see Lemma 17).

Let $\theta^{*}$ be any global minimizer of $L$. Then there exist $\epsilon_{KL}>0,\mu>0$ and $0<\delta\leq 1/2$ such that if $L(\theta)-L(\theta^{*})\leq\epsilon_{KL}$, then $L(\theta)-L(\theta^{*})\leq\mu\|\nabla L(\theta)\|^{1+\delta}$.

We assume $L(\theta^{*})=0$ for any global minimizer $\theta^{*}$. Note that if $L$ satisfies 3 for some $\delta$ then it also satisfies 3 for any $\delta^{\prime}<\delta$. 3 with $\delta=1$ is equivalent to the much stronger Polyak-Łojasiewicz condition which is equivalent to local strong convexity.

2 The Implicit Regularizer R​(θ)𝑅𝜃R(\theta)

Here $\log$ refers to the matrix logarithm. To better understand the regularizer $R(\theta)$, let $\lambda_{1},\ldots,\lambda_{d}$ be the eigenvalues of $\nabla^{2}L(\theta)$ and let $R(\lambda_{i})=-\frac{1}{2\eta}\log(1-\frac{\eta\lambda_{i}}{2})$. Then,

In the limit as $\eta\to 0$, $R(\theta)\to\frac{1}{4}\operatorname{tr}\nabla^{2}L(\theta)$, which matches the regularizer in Blanc et al. for infinitesimal learning rate near a global minimizer. However, in additional to the linear scaling rule, which is implicit in our definition of $\lambda$, our analysis uncovers an additional regularization effect of large learning rates that penalizes larger eigenvalues more than smaller ones (see Figure 1 and Section 6.1).

3 (ϵ,γ)italic-ϵ𝛾(\epsilon,\gamma)-Stationary Points

We begin with the standard definition of an approximate stationary point:

$\theta$ is an $\epsilon$-stationary point of $f$ if $\|\nabla f(\theta)\|\leq\epsilon.$

$\theta$ is an $(\epsilon,\gamma)$-stationary point of $f$ if there exists some $\theta^{*}$ such that $\|\nabla f(\theta^{*})\|\leq\epsilon$ and $\|\theta-\theta^{*}\|\leq\gamma$.

Intuitively, Algorithm 1 converges to an $(\epsilon,\gamma)$-stationary point when it converges to a neighborhood of some $\epsilon$-stationary point $\theta^{*}$.

4 Main Result

Having defined an $(\epsilon,\gamma)$-stationary point we can now state our main result:

Proof Sketch

where $c$ is a sufficiently large constant. Assume $f$ satisfies 1 and $\eta$ satisfies 2. Let $\theta$ follow Algorithm 1 starting at $\theta^{*}$ and assume that $L(\theta^{*})\leq\mathscr{L}$ for some $0<\delta\leq 1/2$. Then there exists a random process $\{\xi_{k}\}$ such that for any $\tau\leq\mathscr{T}$ satisfying $\max_{k\leq\tau}\|\Phi_{k}(\theta^{*})-\theta^{*}\|\leq 8\mathscr{M}$, with probability at least $1-10d\tau e^{-\iota}$ we have simultaneously for all $k\leq\tau$,

Toward simplifying the update in Algorithm 1, we define $L^{(k)}$ to be the true loss without label noise on batch $\mathcal{B}^{(k)}$. The label-noise update $\hat{L}^{(k)}(\theta_{k})$ is an unbiased perturbation of the mini-batch update: $\nabla\hat{L}^{(k)}(\theta_{k})=\nabla L^{(k)}(\theta_{k})-\frac{1}{B}\sum_{i\in\mathcal{B}^{(k)}}\epsilon_{i}^{(k)}\nabla f_{i}(\theta_{k})$. We decompose the update rule into three parts:

Let $m_{k}=-\eta[\nabla L^{(k)}(\theta_{k})-\nabla L(\theta_{k})]$ denote the minibatch noise. Throughout the proof we will show that the minibatch noise is dominated by the label noise. We will also decompose the label noise into two terms. The first, $\epsilon_{k}^{*}$ will represent the label noise if the gradient were evaluated at $\theta^{*}$ whose distribution does not vary with $k$. The other term, $z_{k}$ represents the change in the noise due to evaluating the gradient at $\theta_{k}$ rather than $\theta^{*}$. More precisely, we have

We define $G(\theta)=\frac{1}{n}\sum_{i}\nabla f_{i}(\theta)\nabla f_{i}(\theta)^{T}$ to be the covariance of the model gradients. Note that $\epsilon_{k}^{*}$ has covariance $\eta\lambda G(\theta^{*})$. To simplify notation in the Taylor expansions, we will use the following shorthand to refer to various quantities evaluated at $\theta^{*}$:

First we need the following standard decompositions of the Hessian:

The matrix $G$ in Proposition 1 is known as the Gauss-Newton term of the Hessian. We can now Taylor expand Algorithm 1 and Equation 2 to first order around $\theta^{*}$:

We define $v_{k}=\theta_{k}-\Phi_{k}(\theta^{*})$ to be the deviation from the regularized trajectory. Then subtracting these two equations gives

where we used Proposition 1 to replace $\nabla^{2}L$ with $G$. Temporarily ignoring the higher order terms, we define the random process $\xi$ by

The process $\xi$ is referred to as an Ornstein Uhlenbeck process and it encodes the movement of $\theta$ to first order around $\theta^{*}$. We defer the proofs of the following properties of $\xi$ to Appendix B:

We can now analyze the effect of $\xi_{k}$ on the second order Taylor expansion. Let $r_{k}=\theta_{k}-\Phi_{k}(\theta^{*})-\xi_{k}$ be the deviation of $\theta$ from the regularized trajectory after removing the Ornstein Uhlenbeck process $\xi$. Lemma 1 is equivalent to $\Pr[\|r_{\tau}\|\geq\mathscr{D}]\leq 10\tau de^{-\iota}$.

We will prove by induction that $\|r_{k}\|\leq\mathscr{D}$ for all $k\leq t$ with probability at least $1-10tde^{-\iota}$ for all $t\leq\tau$. The base case follows from $r_{0}=0$ so assume the result for some $t\geq 0$. The remainder of this section will be conditioned on the event $\|r_{k}\|\leq\mathscr{D}$ for all $k\leq t$. $O(\cdot)$ notation will only be used to hide absolute constants that do not change with $t$ and will additionally not hide dependence on the absolute constant $c$. The following proposition fills in the missing second order terms in the Taylor expansion around $\theta^{*}$ of $r_{k}$:

With probability at least $1-2de^{-\iota}$,

The intuition for the implicit regularizer $R(\theta)$ is that by Propositions 2 and 1,

Therefore, when averaged over long timescales,

The second equality follows from the more general equality that for any matrix function $A$ and any scalar function $h$ that acts independently on each eigenvalue, $\nabla(\operatorname{tr}h(A(\theta)))=(\nabla A(\theta))(h^{\prime}(A(\theta)))$ which follows from the chain rule. The above equality is the special case when $A(\theta)=\nabla^{2}L(\theta)$ and $h(x)=-\frac{1}{\eta}\log\left(1-\frac{\eta}{2}x\right)$, which satisfies $h^{\prime}(x)=\frac{1}{2-\eta x}$.

Like Blanc et al. , Lemma 1 shows that $\theta$ locally follows the trajectory of gradient descent on an implicit regularizer $R(\theta)$. However, there are a few crucial differences:

Unlike in Blanc et al. , we do not require the learning rate $\eta$ to be small. Instead, we only require that $\lambda$ scales with $\epsilon$ which can be accomplished either by decreasing the learning rate $\eta$ or increasing the batch size $B$. This allows for stronger implicit regularization in the setting when $\eta$ is large (see Section 6.1). In particular, our regularizer $R(\theta)$ changes with $\eta$ and is only equal to the regularizer in Blanc et al. in the limit $\eta\to 0$.

2 Global Convergence

To be able to repeat the local analysis in Lemma 1 with multiple reference points, we need a more general coupling lemma that allows the random process $\xi$ defined in each coupling to continue where the random process in the previous coupling ended. To accomplish this, we define $\xi$ outside the scope of the local coupling lemma:

Given a sequence of reference points $\{\theta_{m}^{*}\}$ and a sequence of coupling times $\{\tau_{m}\}$, we define the random process $\xi$ by $\xi_{0}=0$, and for $k\in[T_{m},T_{m+1})$,

Then we can prove the following more general coupling lemma:

Let $\mathscr{X},\mathscr{L},\mathscr{D},\mathscr{M},\mathscr{T}$ be defined as in Lemma 1. Assume $f$ satisfies 1 and $\eta$ satisfies 2. Let $\Delta_{m}=\theta_{T_{m}}-\xi_{T_{m}}-\theta_{m}^{*}$ and assume that $\|\Delta_{m}\|\leq\mathscr{D}$ and $L(\theta_{m}^{*})\leq\mathscr{L}$ for some $0<\delta\leq 1/2$. Then for any $\tau_{m}\leq\mathscr{T}$ satisfying $\max_{k\in[T_{m},T_{m+1})}\|\Phi_{k-T_{m}}(\theta_{m}^{*}+\Delta_{m})-\theta_{m}^{*}\|\leq 8\mathscr{M}$, with probability at least $1-10d\tau_{m}e^{-\iota}$ we have simultaneously for all $k\in(T_{m},T_{m+1}]$,

Unlike in Lemma 1, we couple to the regularized trajectory starting at $\theta_{m}^{*}+\Delta_{m}$ rather than at $\theta_{m}^{*}$ to avoid accumulating errors (see Figure 2). The proof is otherwise identical to that of Lemma 1.

Let $\mathscr{F}=\frac{\mathscr{D}^{2}}{\eta\nu\mathscr{T}}$. Let $\Delta_{m}=\theta_{T_{m}}-\xi_{T_{m}}-\theta_{m}^{*}$ and assume $\|\Delta_{m}\|\leq\mathscr{D}$ and $L(\theta_{m}^{*})\leq\mathscr{L}$. Then if $\theta_{T_{m}}$ is not an $(\epsilon,\gamma)$-stationary point, there exists some $\tau_{m}<\mathscr{T}$ such that if we define

then with probability $1-10d\tau_{m}e^{-\iota}$,

We defer the proofs of Lemma 2 and Lemma 3 to Appendix B. Theorem 1 now follows directly from repeated applications of Lemma 3:

Experiments

In order to test the ability of SGD with label noise to escape poor global minimizers and converge to better minimizers, we initialize Algorithm 1 at global minimizers of the training loss which achieve $100\%$ training accuracy yet generalize poorly to the test set. Minibatch SGD would remain fixed at these initializations because both the gradient and the noise in minibatch SGD vanish at any global minimizer of the training loss. We show that SGD with label noise escapes these poor initializations and converges to flatter minimizers that generalize well, which supports Theorem 1. We run experiments with two initializations:

Full Batch Initialization: We run full batch gradient descent with random initialization until convergence to a global minimizer. We call this minimizer the full batch initialization. The final test accuracy of the full batch initialization was 76%.

Adversarial Initialization: Following Liu et al. , we generate an adversarial initialization with final test accuracy $48\%$ that achieves zero training loss by first teaching the network to memorize random labels and then training it on the true labels. See Appendix D for full details.

Experiments were run with ResNet18 on CIFAR10 without data augmentation or weight decay. The experiments were conducted with randomized label flipping with probability $0.2$ (see Appendix E for the extension of Theorem 1 to classification with label flipping), cross entropy loss, and batch size 256. Because of the difficulty in computing the regularizer $R(\theta)$, we approximate it by its lower bound $\operatorname{tr}\nabla^{2}L(\theta)$. Figure 3 shows the test accuracy and $\operatorname{tr}\nabla^{2}L$ throughout training.

SGD with label noise escapes both zero training loss initializations and converges to flatter minimizers that generalize much better, reaching the SGD baseline from the fullbatch initialization and getting within $1\%$ of the baseline from the adversarial initialization. The test accuracy in both cases is strongly correlated with $\operatorname{tr}\nabla^{2}L$. The strength of the regularization is also strongly correlated with $\eta$, which supports Theorem 1. See Figure 4 for experimental results for SGD with momentum.

Extensions

We make the following mild assumption on the smoothed loss $\bar{l}$ which is explicitly verified for the logistic loss, exponential loss, and square loss in Section E.2:

In addition, we assume that $\bar{l}^{\prime},\bar{l}^{\prime\prime}$ are $\rho_{l}$, $\kappa_{l}$ Lipschitz respectively restricted to the set $\{x:\bar{l}(x)\leq\epsilon_{Q}\}$.

Then we define the per-sample loss and the sample loss as:

Now note that the noise per sample from label smoothing at a zero loss global minimizer $\theta^{*}$ can be written as

which will determine the strength of the regularization in Theorem 2. Finally, in order to study the local behavior around $c$ we define $\alpha=\bar{l}^{\prime\prime}(c)>0$ by 4. Corresponding values for $c,\sigma^{2},\alpha$ for logistic loss, exponential loss, and square loss are given in Table 1.

Our main result is a version of Theorem 1:

2 SGD with Momentum

We consider heavy ball momentum with momentum $\beta$, i.e. we replace the update in Algorithm 1 with

As in Lemma 1, the error is $8$ times smaller than the maximum movement of the regularized trajectory. Note that momentum increases the regularization parameter $\lambda$ by $\frac{1}{1-\beta}$. For the commonly used momentum parameter $\beta=0.9$, this represents a $10\times$ increase in regularization, which is likely the cause of the improved performance in Figure 4 ($\beta=0.9$) over Figure 3 ($\beta=0$).

3 Arbitrary Noise Covariances

Let $\theta$ be initialized at a minimizer $\theta^{*}$ of $L$. Assume $\nabla^{2}L$ is Lipschitz, let $H=\nabla^{2}L(\theta^{*})$ and assume that $\Sigma(\theta^{*})\preceq CH$ for some absolute constant $C$. Let $\mathscr{X}=\sqrt{\frac{Cd\lambda\iota}{\nu}}$, $\mathscr{D}=c\lambda^{3/4}\iota$, and $\mathscr{T}=\frac{1}{c^{2}\eta\mathscr{X}\iota}$ for a sufficiently large constant $c$. Then there exists a mean zero random process $\xi$ such that for any $\tau\leq\mathscr{T}$ satisfying $\max_{k<\tau}\|\Phi_{k}(\theta^{*})-\theta^{*}\|\leq 8\mathscr{D}$ and with probability $1-10d\tau e^{-\iota}$, we have simultaneously for all $k\leq\tau$:

As in Lemma 1, the error is $8$ times smaller than the maximum movement of the regularized trajectory. Although Proposition 5 couples to gradient descent on $R_{S}$, $S$ is defined in terms of the Hessian and the noise covariance at $\theta^{*}$ and therefore depends on the choice of reference point. Because $R_{S}$ is changing, we cannot repeat Proposition 5 as in Section 3.2 to prove convergence to a stationary point because there is no fixed potential. Although it is sometimes possible to relate $R_{S}$ to a fixed potential $R$, we show in Section F.2 that this is not generally possible by providing an example where minibatch SGD perpetually cycles. Exploring the properties of these continuously changing potentials and their connections to generalization is an interesting avenue for future work.

Discussion

Various factors can control the strength of the implicit regularization in Theorem 1. Most important is the implicit regularization parameter $\lambda=\frac{\eta\sigma^{2}}{|B|}$. This supports the hypothesis that large learning rates and small batch sizes are necessary for implicit regularization , and agrees with the standard linear scaling rule which proposes that for constant regularization strength, the learning rate $\eta$ needs to be inversely proportional to the batch size $|B|$.

However, our analysis also uncovers an additional regularization effect of large learning rates. Unlike the regularizer in Blanc et al. , the implicit regularizer $R(\theta)$ defined in Equation 1 is dependent on $\eta$. It is not possible to directly analyze the behavior of $R(\theta)$ as $\eta\to 2/\lambda_{1}$ where $\lambda_{1}$ is the largest eigenvalue of $\nabla^{2}L$, as in this regime $R(\theta)\to\infty$ (see Figure 1). If we let $\eta=\frac{2-\nu}{\lambda_{1}}$, then we can better understand the behavior of $R(\theta)$ by normalizing it by $\log 2/\nu$. This givesHere we assume $\lambda_{1}>\lambda_{2}$. If instead $\lambda_{1}=\ldots=\lambda_{k}>\lambda_{k+1}$, this limit will be $k\|\nabla^{2}L(\theta)\|_{2}$.

so after normalization, $R(\theta)$ becomes a better and better approximation of the spectral norm $\|\nabla^{2}L(\theta)\|$ as $\eta\to 2/\lambda_{1}$. $R(\theta)$ can therefore be seen as interpolating between $\operatorname{tr}\nabla^{2}L(\theta)$, when $\eta\approx 0$, and $\|\nabla^{2}L(\theta)\|_{2}$ when $\eta\approx 2/\lambda_{1}$. This also suggests that SGD with large learning rates may be more resilient to the edge of stability phenomenon observed in Cohen et al. as the implicit regularization works harder to control eigenvalues approaching $2/\eta$.

The sharpness-aware algorithm (SAM) of is also closely related to $R(\theta)$. SAM proposes to minimize $\max_{\|\delta\|_{2}\leq\epsilon}L(\theta+\delta)$. At a global minimizer of the training loss,

The SAM algorithm is therefore explicitly regularizing the spectral norm of $\nabla^{2}L(\theta)$, which is closely connected to the large learning rate regularization effect of $R(\theta)$ when $\eta\approx 2/\lambda_{1}$.

2 Generalization Bounds

The implicit regularizer $R(\theta)$ is intimately connected to data-dependent generalization bounds, which measure the Lipschitzness of the network via the network Jacobian. Specifically, Wei and Ma propose the all-layer margin, which bounds the $\textup{generalization error}\lesssim\frac{\sum_{l=1}^{L}\mathcal{C}_{l}}{\sqrt{n}}\sqrt{\frac{1}{n}\sum_{i=1}^{n}\frac{1}{m_{F}(x_{i},y_{i})^{2}}}$, where $\mathcal{C}_{l}$ depends only on the norm of the parameters and $m_{F}$ is the all-layer margin. The norm of the parameters is generally controlled by weight decay regularization, so we focus our discussion on the all-layer margin. Ignoring higher-order secondary terms, Wei and Ma [30, Heuristic derivation of Lemma 3.1] showed for a feed-forward network $f(\theta;x)=\theta_{L}\sigma(\theta_{L-1}\ldots\sigma(\theta_{1}x))$, the all-layer margin satisfiesThe output margin is defined as $\min_{i}f_{i}(\theta)y_{i}$. The following uses Equation (3.3) and the first-order approximation provided Wei and Ma and the chain rule $\frac{\partial f}{\partial\theta_{l}}=\frac{\partial f}{\partial h_{l}}\frac{\partial h_{l}}{\partial\theta_{l-1}}=\frac{\partial f}{\partial h_{l}}h_{l-1}^{\top}$.:

as $R(\theta)$ is an upper bound on the squared norm of the Jacobian at any global minimizer $\theta$. We emphasize this bound is informal as we discarded the higher-order terms in controlling the all-layer margin, but it accurately reflects that the regularizer $R(\theta)$ lower bounds the all-layer margin $m_{F}$ up to higher-order terms. Therefore SGD with label noise implicitly regularizes the all-layer margin.

Acknowledgements

AD acknowledges support from a NSF Graduate Research Fellowship. TM acknowledges support of Google Faculty Award and NSF IIS 2045685. JDL acknowledges support of the ARO under MURI Award W911NF-11-1-0303, the Sloan Research Fellowship, NSF CCF 2002272, and an ONR Young Investigator Award.

The experiments in this paper were performed on computational resources managed and supported by Princeton Research Computing, a consortium of groups including the Princeton Institute for Computational Science and Engineering (PICSciE) and the Office of Information Technology’s High Performance Computing Center and Visualization Laboratory at Princeton University.

We would also like to thank Honglin Yuan and Jeff Z. HaoChen for useful discussions throughout various stages of the project.

References

Appendix A Limitations

In Section 2 we make three main assumptions: 1 (smoothness), 2 (learning rate separation), and 3 (KL).

1 imposes the necessary smoothness conditions on $f$ to enable second order Taylor expansions of $\nabla L$. These smoothness conditions may not hold, e.g. if ReLU activations are used. This can be easily resolved by using a smooth activation like softplus or SiLU .

Appendix B Missing Proofs

In addition if we define $e_{i}(\theta)=f_{i}(\theta)-y_{i}$,

We define the quadratic variation $[\cdot]$ and quadratic covariation $[\cdot,\cdot]$ of a martingale $X$ to be

therefore by Corollary 1, with probability at least $1-2de^{-\iota}$, $\|\xi_{k}\|\leq\mathscr{X}$. ∎

We prove the following version of Proposition 2 for the setting of Lemma 2:

Let $\xi_{k}$ be defined as in Definition 3. Then for any $t\geq 0$, with probability $1-2de^{-\iota}$, $\|\xi_{t}\|\leq\mathscr{X}$.

For $k\in(T_{m},T_{m+1}]$ define $G_{k}=G(\theta_{m}^{*})$. Then we can write for any $k\geq 0$,

Let $\mathcal{F}_{t}=\sigma\{\mathcal{B}^{(k)},\epsilon^{(k)}:k<t\}$. To each $k$ we will associate a martingale $\{X^{(k)}_{j}\}_{j\leq k}$ adapted to $\mathcal{F}$ as follows. First let $X^{(k)}_{0}=0$. Then for all $k\geq 0$ and all $j\geq 0$,

First we need to show $X^{(k)}$ is in fact a martingale. We will show this by induction on $k$. The base case of $k=0$ is trivial. Next, it is easy to see that $X_{j}^{(k)}\in\mathcal{F}_{j}$. Therefore,

where the second line followed from the induction hypothesis and the third line followed from the definition of $X_{j}^{(k)}$. Therefore $X^{(k)}$ is a martingale for all $k$.

Next, I claim that $\xi_{k}=X_{k}^{(k)}$. We can prove this by induction on $k$. The base case is trivial as $\xi_{0}=X^{(0)}_{0}=0$. Then,

Finally, I claim that $[X^{(k)},X^{(k)}]_{k}\preceq\frac{n\lambda}{\nu}I$. We will prove this by induction on $k$. The base case is trivial as $X^{(0)}_{0}=0$. Then,

Therefore by Corollary 1, $\|\xi_{k}\|\leq\mathscr{X}$ with probability at least $1-2de^{-\iota}$. ∎

We will prove Proposition 3 and Proposition 4 in the more general setting of Lemma 2. For notational simplicity we will apply the Markov property and assume that $m=0$. We define $\Delta=\Delta_{0}$ and $\theta^{*}=\theta_{0}^{*}$ and note that due to this time change that $\xi_{0}$ is not necessarily . We define $v_{k}=\theta_{k}-\Phi_{k}(\theta^{*}+\Delta)$ and $r_{k}=\theta_{k}-\xi_{k}-\Phi_{k}(\theta^{*}+\Delta)$.

First, by Proposition 6, $\|\xi_{t}\|\leq\mathscr{X}$ with probability at least $1-2de^{-\iota}$. Then note that for $k\leq t$,

so Taylor expanding the update in Algorithm 1 and Equation 2 to second order around $\theta^{*}$ and subtracting gives

Note that for each $i\in\mathcal{B}^{(k)}$,

Therefore by Lemma 5, with probability $1-2de^{-\iota}$,

Next, by a second order Taylor expansion around $\theta^{*}$ we have

Now we will turn to concentrating $\xi_{k}\xi_{k}^{T}$. We will use the shorthand $g_{i}=\nabla f_{i}(\theta^{*})$. Let

We can expand out $\nabla^{3}L$ using the fact that $L$ is square loss to get

so it suffices to bound the contribution of the first two terms individually. Starting with the second term, we have $\operatorname{tr}\left[(S_{k}-S^{*})H_{i}\right]=O(\mathscr{X}^{2})$, so by Lemma 12,

so this difference contributes at most $O(\eta^{2}\lambda t\sqrt{\mathscr{L}})=O(\eta t\mathscr{X}\sqrt{\mathscr{L}})$ so it suffices to bound

and thatThis identity directly follows from multiplying both sides by $2-\eta G$ and the fact that all of these matrices commute .

Let $D_{k}=S_{k}-\bar{S}$. Then subtracting these two equations gives

Let $W_{k}=(I-\eta G)\xi_{k}(\epsilon_{k}^{*})^{T}+\epsilon_{k}^{*}\xi_{k}^{T}(I-\eta G)$ and let $Z_{k}=((\epsilon_{k}^{*})(\epsilon_{k}^{*})^{T}-\eta\lambda G)$ so that

so we are left with the martingale part in the second term. The final term to bound is therefore

We can switch the order of summations to get

Now if we extract the inner sum, note that

is a martingale difference sequence. Recall that

The inner sums are bounded by $O(\mathscr{X}\eta^{-1})$ by Lemma 14. Therefore by Lemma 5, with probability at least $1-2de^{-\iota}$, the contribution of the $W$ term in Equation 72 is at most $O(\sqrt{\eta\lambda k\iota}\mathscr{X})=O(\sqrt{\eta k}\mathscr{X}^{2})$. The final remaining term to bound is the $Z$ term in (72). We can write the inner sum as

which by Lemma 14 is bounded by $O(\lambda)$. Therefore by Lemma 5, with probability at least $1-2de^{-\iota}$, the full contribution of $Z$ to Equation 72 is $O(\eta\lambda\sqrt{t\iota})=O(\sqrt{\eta t}\mathscr{X}^{2})$. Putting all of these bounds together we get with probability at least $1-10de^{-\iota}$,

The following lemma is necessary for some of the proofs below:

Assume that $L(\theta)\leq\mathscr{L}$. Then for any $k\geq 0$, $L(\Phi_{k}(\theta))\leq\mathscr{L}$.

By induction it suffices to prove this for $k=1$. Let $\theta^{\prime}=\Phi_{1}(\theta)$. First consider the case when

Then by 3, $L(\theta^{\prime})\leq\mathscr{L}$ so we are done. Otherwise, note that

and for $c$ sufficiently large, the second term is larger than the third so $L(\theta^{\prime})\leq L(\theta)\leq\mathscr{L}$. ∎

In the context of Lemma 3, if $\theta_{T_{m}}$ is not an $(\epsilon,\gamma)$-stationary point, there exists $\tau_{m}\leq\mathscr{T}$ such that:

Let $G=G(\theta_{m}^{*})$ and let $\tau_{m}$ be chosen as in Proposition 7. Then, $\theta_{m+1}^{*}-\Phi_{\tau_{m}}(\theta_{m}^{*})=(I-\eta G)^{\tau_{m}}\Delta_{m}+r$ where $\|r\|=O(\eta\tau_{m}\mathscr{M}^{2})$ and $\|r\|_{G}^{2}=O(\eta\tau_{m}\mathscr{M}^{4})$.

Combining Propositions 8 and 10, we have that

The following corollary also follows from the choice of $\tau_{m}$, Proposition 9, and Lemma 2:

$\|\Phi_{\tau_{m}}(\theta_{m}^{*}+\Delta_{m})-\theta_{m}^{*}\|\leq 8\mathscr{M}$ and with probability at least $1-8d\tau_{m}e^{-\iota}$, $\|\Delta_{m+1}\|\leq\mathscr{D}$.

The proof of Lemma 3 follows directly from Equation 89, Proposition 11, and Corollary 2. The proofs of the above propositions can be found below:

Then we can upper bound each element in this sum by

for sufficiently large $c$. Therefore there must exist $\tau_{m}$ such that

Therefore there must exist some $k$ such that

by the choice of $\lambda$ in Theorem 1. In addition,

again by the choice of $\lambda$. Therefore $\theta_{T_{m}}$ is an $(\epsilon,\gamma)$-stationary point. ∎

Let $v_{k}=\Phi_{k}(\theta_{m}^{*}+\Delta_{m})-\Phi_{k}(\theta_{m}^{*})$, so that $v_{0}=\Delta_{m}$ and let $r_{k}=v_{k}-(I-\eta G)^{\tau_{m}}$ so that $r_{0}=0$. Let $C$ be a sufficiently large absolute constant. We will prove by induction that $r_{k}\leq C\eta\tau_{m}\mathscr{M}^{2}$. Note that

because of the values chosen for $\mathscr{M}$, $\mathscr{T}$. Therefore Taylor expanding around $\theta_{m}^{*}$ gives:

where $\|s_{k}\|=O(\eta\mathscr{M}^{2})$ by the definition of $\mathscr{M}$. Therefore

so if $g_{i}=\nabla f_{i}(\theta_{m}^{*})$,

We will need the following lemma before the next proof:

Let $v=\theta_{m+1}-\Phi_{\tau_{m}}(\theta_{m}^{*})=(I-\eta G)^{\tau_{m}}\Delta_{m}+r$ where by Proposition 9, $\|r\|=O(\eta\tau_{m}\mathscr{M}^{2})$, $G=G(\theta_{m}^{*})$, and $r^{T}Gr=O(\eta\tau_{m}\mathscr{M}^{4})$. Then,

for sufficiently large $c$. Therefore by Lemma 7 and Proposition 7,

for sufficiently large $c$. Finally, the remainder term is bounded by

for sufficiently large $c$ for the same reason as above. Putting it all together,

Assume otherwise for the sake of contradiction. Because $\nabla R$ is Lipschitz, $R(\theta_{m+1}^{*})-R(\theta_{m}^{*})=O(\mathscr{M})$. Therefore by Equation 89,

Then by the same arguments as in Proposition 10, we can Taylor expand around $\Phi_{\tau_{m}}(\theta_{m}^{*})$ to get

because $\delta\leq 1/2$. Therefore $L(\theta_{m+1}^{*})=O(\lambda^{1+\delta})\leq\mathscr{L}$ for sufficiently large $c$. ∎

Appendix C Reaching a global minimizer with NTK

It is well known that overparameterized neural networks in the kernel regime trained by gradient descent reach global minimizers of the training loss . In this section we describe how to extend the proof in to show that SGD with label noise (Algorithm 1) converges to a neighborhood of a global minimizer $\theta^{*}$ as required by Theorem 1. We will use the following lemma from :

Let $\xi_{0}=0$ and $\theta_{0}^{*}=\theta_{0}$. We will define $\xi_{k},\theta_{k}^{*}$ iteratively as follows:

Let $v_{k}=\theta_{k}-\theta_{k}^{*}$ and let $r_{k}=v_{k}-\xi_{k}$. We will prove by induction that for all $t\leq T=\frac{4\log\left[L(\theta_{0})\lambda_{0}/\lambda^{2}\right]}{\eta\lambda_{0}}$ we have $\|r_{k}\|\leq\mathscr{D}$. The base case follows from $r_{0}=0$. For $k\geq 0$ we have

which completes the induction. Therefore it suffices to show that the loss of $\theta_{T}^{*}$ is small. We have

where the last line follows from Young’s inequality. Therefore,

Let $J$ be the Jacobian of $f$ and $e$ be the vector of residuals. Then $\nabla L=Je$. Now so long as $\|\theta_{k}^{*}-\theta_{0}\|\leq R$,

for small $\lambda$ by the choice of $T$. It only remains to check that $\|\theta_{k}^{*}-\theta_{0}\|\leq R$. Note that

Note that a direct application of Theorem 1 requires starting $\xi$ at . However, this does not affect the proof in any way and the $\xi$ from this proof can simply be continued as in Lemma 2.

Appendix D Additional Experimental Details

The model used in our experiments is ResNet18 with GroupNorm instead of BatchNorm to maintain independence of sample gradients when computed in a batch. We used a fixed group size of 32.

For the full batch initialization, we trained ResNet18 on the CIFAR10 training set (50k images, 5k per class) , with cross entropy loss. CIFAR10 images are provided under an MIT license. We trained using SGD with momentum with $\eta=1$ and $\beta=0.9$ for $2000$ epochs. We used learning rate warmup starting at which linearly increased until $\eta=1$ at epoch $600$ and then it decayed using a cosine learning rate schedule to between epochs $600$ and $2000$. We also used a label smoothing value of $0.2$ (non-randomized) so that the expected objective function is the same for when we switch to SGD with label flipping (see Appendix E). The final test accuracy was $76\%$.

For the adversarial initialization, we first created an augmented adversarial dataset as follows. We duplicate every image in CIFAR10 $10\times$, for a total of 500k images. In each image, we randomly zero out $10\%$ of the pixels in the image and we assign each of the 500k images a random label. We trained ResNet18 to interpolate this dataset without label smoothing with the following hyperparameters: $\eta=0.01$, $300$ epochs, batch size $256$. Starting from this initialization we ran SGD on the true dataset with $\eta=0.01$ and a label smoothing value of $0.2$ with batch size $256$ for $1000$ epochs. The final test accuracy was $48\%$.

For the remaining experiments starting at these two initializations we ran both with and without momentum (see Figure 4 for the results with momentum) for $1000$ epochs per run. We used a fixed batch size of $256$ and varied the maximum learning rate $\eta$. We used learning rate warmup by linearly increasing the learning rate from to the max learning rate over $300$ epochs, and we kept the learning rate constant from epochs $300$ to $1000$. The regularizer was estimated by computing the strength of the noise in each step and then averaging over an epoch. More specifically, we compute the average of $\|\nabla\hat{L}^{(k)}(\theta_{k})-\nabla L^{(k)}(\theta_{k})\|^{2}$ over an epoch and then renormalize by the batch size.

The experiments were run on NVIDIA P100 GPUs through Princeton Research Computing. Code was written in Python using PyTorch and PyTorch Lightning , and experiments were logged using Wandb . Code can be found at https://github.com/adamian98/LabelNoiseFlatMinimizers.

Appendix E Extension to Classification

The proof of Theorem 2 is virtually identical to that of Theorem 1. First we make a few simplifications without loss of generality:

Next note that without loss of generality we can replace each $f_{i}$ with $y_{i}f_{i}$ and set all of the true labels $y_{i}$ to $1$. Therefore from now on we will simply speak of $f_{i}$.

Let $\{\tau_{m}\}$ be a sequence of coupling times and $\{\theta_{m}^{*}\}$ a sequence of reference points. Let $T_{m}=\sum_{j<m}\tau_{m}$. Then for $k\in[T_{m},T_{m+1})$, if $L^{(k)}$ denotes true value of the loss on batch $\mathcal{B}^{(k)}$, we can decompose the loss as

We decompose $\epsilon_{k}=\epsilon_{k}^{*}+z_{k}$ where

and $z_{k}=\epsilon_{k}-\epsilon_{k}^{*}$. Note that $\epsilon_{k}^{*}$ has covariance $\eta\lambda G(\theta_{m}^{*})$. We define $\xi_{0}=0$ and for $k\in[T_{m},T_{m+1})$,

Then we have the following version of Proposition 6:

Let $\mathscr{X}=\sqrt{\max\left(\frac{p}{1-p},\frac{1-p}{p}\right)\cdot\frac{2\lambda d\iota}{\nu}}$. Then for any $t\geq 0$, with probability $1-2de^{-\iota}$, $\|\xi_{t}\|\leq\mathscr{X}$.

Let $P=\max\left(\frac{p}{1-p},\frac{1-p}{p}\right)$. Define the martingale sequence $X^{(k)}_{j}$ as in Proposition 6. I claim that $[X^{(k)},X^{(k)}]_{k}\preceq\frac{n\lambda P}{\nu}I$. We will prove this by induction on $k$. The base case is trivial as $X^{(0)}_{0}=0$. Then,

Define $\iota,\mathscr{D},\mathscr{M},\mathscr{T},\mathscr{L}$ as in Lemma 1. Then we have the following local coupling lemma:

Assume $f$ satisfies 1, $\eta$ satisfies 2, and $l$ satisfies 4. Let $\Delta_{m}=\theta_{T_{m}}-\xi_{T_{m}}-\theta_{m}^{*}$ and assume that $\|\Delta_{m}\|\leq\mathscr{D}$ and $L(\theta_{m}^{*})\leq\mathscr{L}$ for some $0<\delta\leq 1/2$. Then for any $\tau_{m}\leq\mathscr{T}$ satisfying $\max_{k\in[T_{m},T_{m+1})}\|\Phi_{k-T_{m}}(\theta_{m}^{*}+\Delta_{m})-\theta_{m}^{*}\|\leq 8\mathscr{M}$, with probability at least $1-10d\tau_{m}e^{-\iota}$ we have simultaneously for all $k\in(T_{m},T_{m+1}]$,

The proof of Lemma 9 follows directly from the following decompositions:

Let $\nabla^{2}L=\nabla^{2}L(\theta_{m}^{*})$, $\nabla^{3}L=\nabla^{3}L(\theta_{m}^{*})$, $G=G(\theta_{m}^{*})$, $f_{i}=f_{i}(\theta_{m}^{*})$, $g_{i}=\nabla f_{i}(\theta_{m}^{*})$, $H_{i}=\nabla^{2}f_{i}(\theta_{m}^{*})$. Then,

These are the exact same decompositions used Proposition 3 and Proposition 4, so Lemma 9 immediately follows. In addition, as we never used the exact value of the constant in $\mathscr{X}$ in the proof of Theorem 1, the analysis there applies directly as well showing that we converge to an $(\epsilon,\gamma)$-stationary point and proving Theorem 2.

E.2 Verifying 4

We verify 4 for the logistic loss, the exponential loss, and the square loss and derive the corresponding values of $c,\sigma^{2}$ found in Table 1.

For logistic loss, we let $l(x)=\log(1+e^{-x})$, and $\bar{l}(x)=pl(-x)+(1-p)l(x)$. Then

which is negative when $x<\log\frac{1-p}{p}$ and positive when $x>\log\frac{1-p}{p}$ so it is minimized at $c=\log\frac{1-p}{p}$. To show the quadratic approximation holds at $c$, it suffices to show that $\bar{l}^{\prime\prime\prime}(x)$ is bounded. We have $\bar{l}^{\prime\prime}(x)=\frac{e^{x}}{(1+e^{x})^{2}}$ and

so we are done. Finally, to calculate the strength of the noise at $c$ we have

E.2.2 Exponential Loss

We have $l(x)=e^{-x}$ and $\bar{l}(x)=pl(-x)+(1-p)l(x)$. Then,

which is negative when $x<\frac{1}{2}\log\frac{1-p}{p}$ and positive when $x>\frac{1}{2}\log\frac{1-p}{p}$ so it is minimized at $c=\frac{1}{2}\log\frac{1-p}{p}$. Then we can compute

because $\cosh x\geq 1+\frac{x^{2}}{2}$. Finally to compute the strength of the noise we have

E.2.3 Square Loss

We have $l(x)=\frac{1}{2}(1-x)^{2}$ and $\bar{l}(x)=pl(-x)+(1-p)l(x)$. Then,

which is a quadratic minimized at $c=1-2p$. The quadratic approximation trivially holds and the strength of the noise is:

Appendix F Arbitrary Noise

We follow the proof of Lemma 2. First, let $\epsilon_{k}=\sqrt{\eta\lambda}\Sigma^{1/2}(\theta_{k})x_{k}$ with $x_{k}\sim N(0,I)$ and define $\epsilon_{k}^{*}=\sqrt{\eta\lambda}\Sigma^{1/2}(\theta^{*})x_{k}$ and $z_{k}=\epsilon_{k}-\epsilon_{k}^{*}$. Let $H=\nabla^{2}L(\theta^{*})$, $\Sigma=\Sigma(\theta^{*})$, and $\nabla R_{S}=\nabla R_{S}(\theta^{*})$. Let $\alpha$ be the smallest nonzero eigenvalue of $H$. Unlike in Lemma 1, we will omit the dependence on $\alpha$.

First we need to show $S$ exists. Consider the update

Restricted to the span of $H$, this is a contraction so it must converge to a fixed point. In fact, we can write this fixed point in a basis of $H$ explicitly. Let $\{\lambda_{i}\}$ be the eigenvalues of $H$. The following computation will be performed in an eigenbasis of $H$. Then the above update is equivalent to:

Therefore if $\lambda_{i},\lambda_{j}\neq 0$ we can set

so by Corollary 1, $\|\xi_{k}\|\leq\mathscr{X}$ with probability $1-2de^{-\iota}$. Define $v_{k}=\theta_{k}-\Phi_{k}(\theta_{0})$ and $r_{k}=\theta_{k}-\xi_{k}-\Phi_{k}(\theta_{0})$. We will prove by induction that $\|r_{t}\|\leq\mathscr{D}$ with probability at least $1-8dte^{-\iota}$. First, with probability $1-2de^{-\iota}$, $\|\xi_{t}\|\leq\mathscr{X}$. In addition, for $k\leq t$,

Therefore from the second order Taylor expansion:

Because $z_{k}$ is Gaussian with covariance bounded by $O(\eta\lambda\mathscr{X}^{2})$ by the assumption that $\Sigma^{1/2}$ is Lipschitz, we have by the standard Gaussian tail bound that its contribution after summing is bounded by $\sqrt{\eta\lambda\mathscr{X}k\iota}$ with probability at least $1-2de^{-\iota}$ so summing over $k$ gives

Now denote $S_{k}=\xi_{k}\xi_{k}^{T}$. Then we need to bound

Let $D_{k}=S_{k}-S$. Then plugging this into the recurrence for $S_{k}$ gives

where $\Pi_{H}$ is the projection onto $H$. We switch the order of summation for the next two terms to get

Note that conditioned on $\epsilon_{l}^{*}$, $l<j$, the $W_{j}$ part of the inner sum is Gaussian with variance bounded by $O(\eta\lambda\mathscr{X}^{2})$ so by Lemma 16, with probability at least $1-2de^{-\iota}$, the contribution of $W$ is bounded by $O(\sqrt{\eta\lambda t\iota}\mathscr{X})$.

With probability $1-2dte^{-r^{2}/2}$ we can assume that $x_{j}x_{j}^{T}=\bar{x}_{j}\bar{x}_{j}^{T}$ for all $j\leq t$ so the first term is zero. For the second term the inner sum is bounded by $O(r^{2}\eta^{-1})$ and has variance bounded by $O(\eta^{-2})$ by the same arguments as above. Therefore by Bernstein’s inequality, the whole term is bounded by $O(\eta\lambda\sqrt{t\iota}+r^{2}\eta\lambda\iota)$ with probability $1-2de^{-\iota}$. Finally, to bound the third term note that

Therefore the whole term is bounded by $O(\eta\lambda te^{-r^{2}/4})$. Finally, pick $r=\sqrt{4\iota\log\mathscr{T}}$. Then the final bound is

for sufficiently large $c$. This completes the induction.

F.2 SGD Cycling

Let $\theta=(x,y,z_{1},z_{2},z_{3},z_{4})$. We will define a set of functions $f_{i}$ as follows:

The intuition for the definition of $f$ above is as follows. When $x=1$ and $y=0$, due to the constraints from $f_{9}$ to $f_{1}2$, only $z_{1}$ can grow to become nonzero. Then locally, $f_{1}=z_{1}-1$ and $f_{2}=z_{1}+1$ so this will cause oscillations in the $z_{1}$ direction, so $S$ will concentrate in the $z_{1}$ direction which will bias minibatch SGD towards decreasing the corresponding entry in $\nabla^{2}L(\theta)$ which is proportional to $(1-x)^{2}+2(1-y)^{2}$, which means it will increase $y$. Similarly when $x=0,y=1$ there is a bias towards decreasing $x$, when $x=-1,y=0$ there is a bias towards decreasing $y$, and when $x=0,y=-1$ there is a bias towards increasing $x$. Each of these is handled by a different Ornstein Uhlenbeck process $z_{i}$. $f_{13}$ ensures that $\theta$ remains on $x^{2}+y^{2}=1$ throughout this process. This cycling is a result of minimizing a rapidly changing potential and shows that the implicit bias of minibatch SGD cannot be recovered by coupling to a fixed potential.

Appendix G Weak Contraction Bounds and Additional Lemmas

where we used that the function $xe^{-x}<\frac{1}{e}$ is bounded. ∎

where we used the fact that the function $xe^{-x}\leq\frac{1}{e}$ is bounded. ∎

The following concentration inequality is from Jin et al. :

we have that for any $\iota>0$ there exists an absolute constant $c$ such that with probability at least $1-2de^{-\iota}$,

Assume that $L$ is analytic and $\theta$ is restricted to some compact set $\mathcal{D}$. Then there exist $\delta>0,\mu>0,\epsilon_{KL}>0$ such that 3 is satisfied.

It is known that there exist $\mu_{\theta},\delta_{\theta}$ satisfying the KL-inequality in the neighborhood of any critical point $\theta$ of $L$, i.e. for every critical point $\theta$, there exists a neighborhood $U_{\theta}$ of $\theta$ such that for any $\theta^{\prime}\in U_{\theta}$,

Let $S=\{\theta\in\mathcal{D}:L(\theta)=L(\theta^{*})\}$ for any global minimizer $\theta^{*}$. For every global min $\theta\in S$, let $U_{\theta}$ be a neighborhood of $\theta$ such that the KL inequality holds with constants $\mu_{\theta},\delta_{\theta}$. Because $\mathcal{D}$ is compact and $S$ is closed, $S$ is compact and there must exist some $\theta_{1},\ldots,\theta_{n}$ such that $S\subset\bigcup_{i\in[k]}U_{\theta_{i}}$. Let $\delta=\min_{i}\delta_{\theta_{i}}$. Then for all $i$, there must exist some $\mu_{i}$ such that $\mu_{i},\delta$ satisfies the KL inequality and let $\mu=\max_{i}\mu_{i}$. Finally, let $U=\bigcup_{i}U_{\theta_{i}}$ which is an open set containing $S$. Then $\mathcal{D}\setminus U$ is a compact set and therefore $L$ must achieve a minimum $\epsilon_{KL}$ on this set. Note that $\epsilon_{KL}>0$ as $S\subset U$. Then if $L(\theta)\leq\epsilon_{KL}$, $\theta\in U$ so $\mu,\delta$ satisfy the KL inequality at $\theta$. ∎