x-y\right\rVert\leq\frac{\sqrt{2}\alpha}{\sigma\sqrt{\pi}}\int_{-\frac{\left\lVert
x-y\right\rVert}{2}}^{\frac{\left\lVert
x-y\right\rVert}{2}}\exp(-\frac{u^{2}}{2\sigma^{2}})d\leq\frac{\sqrt{2}\alpha}{\sigma\sqrt{\pi}}\left\lVert
x-y\right\rVert$

Obviously, taking $x,y$ such that $\left\lVert x-y\right\rVert\leq
2\sqrt{2}\sigma$,

$\frac{\sqrt{2}\alpha}{e\sigma\sqrt{\pi}}\left\lVert
x-y\right\rVert\leq\left\lVert\nabla l_{\mu}(x;\xi)-\nabla
l_{\mu}(y;\xi)\right\rVert\leq\frac{\sqrt{2}\alpha}{\sigma\sqrt{\pi}}\left\lVert
x-y\right\rVert$

we could conclude the Lipschitz bound for $\nabla l_{\mu}$ cannot be improved
by more than a constant factor.

Then we are going to show smooth objective $l_{\mu}$ is $\beta$ smooth and the
bound is tight.

$\displaystyle\left\lVert\nabla l_{\mu}(x;\xi)-\nabla
l_{\mu}(y;\xi)\right\rVert=$
$\displaystyle\left\lVert\nabla\mathbb{E}_{Z\sim\mu}[l_{o}(x+Z)]-\nabla\mathbb{E}_{Z\sim\mu}[l_{o}(x+Z)]\right\rVert$
$\displaystyle=$ $\displaystyle\left\lVert\mathbb{E}_{Z\sim\mu}[\nabla
l_{o}(x+Z)-\nabla l_{o}(y+Z)]\right\rVert$ $\displaystyle=$
$\displaystyle\left\lVert\int[\nabla l_{o}(x+Z)-\nabla
l_{o}(y+Z)]\mu(z)dz\right\rVert$ $\displaystyle\leq$
$\displaystyle\int\left\lVert\nabla l_{o}(x+Z)-\nabla
l_{o}(y+Z)\right\rVert\mu(z)dz$ $\displaystyle\leq$
$\displaystyle\int\beta\left\lVert(x+z)-(y+z)\right\rVert\mu(z)dz$
$\displaystyle=$ $\displaystyle\beta\left\lVert x-y\right\rVert\int\mu(z)dz$
$\displaystyle=$ $\displaystyle\beta\left\lVert x-y\right\rVert$

Therefore, $l_{\mu}$ is $\beta$-smooth. Then we are going to show the bound is
tight and cannot be improved. Define $\alpha$ Lipschitz continuous and
$\beta$-smooth function $l_{o}:\mathbb{R}^{d}\to\mathbb{R}$ as

$\displaystyle l_{o}(\theta;\xi)=\frac{1}{2}\beta\left\lVert
w\right\rVert^{2}\quad\quad\theta\in B(0,\frac{\alpha}{\beta}).$

Hence, we have

$\displaystyle\left\lVert\nabla l_{\mu}(x;\xi)-\nabla
l_{\mu}(y;\xi)\right\rVert=$ $\displaystyle\left\lVert\int(\beta x-\beta
y)\mu(z)dz\right\rVert$ $\displaystyle=$
$\displaystyle\left\lVert\beta(x-y)\int\mu(z)dz\right\rVert$ $\displaystyle=$
$\displaystyle\beta\left\lVert x-y\right\rVert.$

Therefore. $l_{\mu}$ is exactly $\beta$-smooth.

  * iii)

By Jensen’s inequality, for left hand side:

$\displaystyle
l_{\mu}(\theta;\xi)=\mathbb{E}_{Z\sim\mu}[l_{o}(\theta+Z;\xi)]\geq
l_{o}(\theta+\mathbb{E}_{Z\sim\mu}[Z];\xi)=l_{o}(\theta;\xi).$

For the tightness proof, defining $l_{o}(\theta;\xi)=\frac{1}{2}v^{T}\theta$
for $v\in\mathbb{R}^{d}$ leads to $l_{\mu}=l_{o}$.

For right hand side:

$\displaystyle l_{\mu}(\theta;\xi)=$
$\displaystyle\mathbb{E}_{Z\sim\mu}[l_{o}(\theta+Z;\xi)]$ $\displaystyle\leq$
$\displaystyle l_{o}(\theta;\xi)+\alpha\mathbb{E}_{Z\sim\mu}[\left\lVert
Z\right\rVert]\quad\quad(\alpha\text{-Lipchitz continuous})$
$\displaystyle\leq$ $\displaystyle
l_{o}(\theta;\xi)+\alpha\sqrt{\mathbb{E}[\left\lVert
Z\right\rVert^{2}]}\quad\quad(\frac{\left\lVert
Z\right\rVert^{2}}{\sigma^{2}}\sim\mathcal{X}^{2}(d))$ $\displaystyle=$
$\displaystyle l_{o}(\theta;\xi)+\alpha\sigma\sqrt{d}.$

For the tightness proof, taking
$l_{o}(\theta;\xi)=\alpha\left\lVert\theta\right\rVert$.Since
$l_{\mu}(\theta;\xi)\geq c\alpha\sigma\sqrt{d}$ for some constant $c$.
Therefore, the bound cannot be improved by more than a constant factor.

∎

###  15.2 Brief justification for Theorem 3

Note that former works also use the ratio of upper-bounds to approximate the
ratio of generalization error. For example, in (Chaudhari et al., 2017), they
use the ratio of upper-bounds to compare the generalization error of Entropy-
SGD and Vanilla-SGD (see their Equation 9). Also, in (Sokolic et al., 2017)
they use the ratio of upper-bounds (see their Equation 15) to compare the
generalization error of the model with and without invariant method. Finally,
comparing the properties, including convergence rate or generalization error,
of learning algorithms using $\mathcal{O}$ notation is common in the field.

###  15.3 Proof for Theorem 3

We first consider the generalization error in the context of the original loss
$L$, and then we analyze smoothed loss function $L\circledast K$. The true
loss is defined as

$\displaystyle L^{true}(\theta):=\mathbb{E}_{\xi\sim D}l(\theta;\xi).$ (15.6)

where $l$ is an arbitrary loss function (i.e., $l_{o}$ for SGD case and
$l_{\mu}$ for LPF-SGD case). Since the distribution $\mathcal{D}$ is unknown,
we replace the true loss by the empirical loss given as

$\displaystyle
L^{\mathcal{S}}(\theta):=\frac{1}{m}\sum_{i=1}^{m}l(\theta;\xi).$ (15.7)

In order to bound the generalization error $\epsilon_{g}$, we consider the
following stability bound.

######  Definition 2 ($\epsilon_{s}$-uniform stability (Hardt et al., 2016)).

Let $\mathcal{S}$ and $\mathcal{S}^{\prime}$ denote two data sets from input
data distribution $\mathcal{D}$ such that $\mathcal{S}$ and
$\mathcal{S}^{\prime}$ differ in at most one example. Algorithm $A$ is
$\epsilon_{s}$-uniformly stable if and only if for all data sets $\mathcal{S}$
and $\mathcal{S}^{\prime}$ we have

$\displaystyle\sup_{\xi}\mathbb{E}[l(A(\mathcal{S});\xi)-l(A(\mathcal{S}^{\prime});\xi)]\leq\epsilon_{s}.$
(15.8)

The following theorem, proposed in (Hardt et al., 2016), implies that the
generalization error could be bounded using the uniform stability bound.

######  Theorem 2.

If $A$ is an $\epsilon_{s}$-uniformly stable algorithm, then the
generalization error (the gap between the true risk and the empirical risk) of
$A$ is upper-bounded by the stability factor $\epsilon_{s}$:

$\displaystyle\epsilon_{g}:=\mathbb{E}_{\mathcal{S},A}[L^{true}(A(\mathcal{S}))-L^{\mathcal{S}}(A(\mathcal{S}))]\leq\epsilon_{s}$
(15.9)

Denote the original true loss and empirical loss as:

$\displaystyle L^{true}_{o}(\theta):=\mathbb{E}_{\xi\sim
D}l_{o}(\theta;\xi)\quad\text{and}\quad
L^{\mathcal{S}}_{o}(\theta):=\frac{1}{m}\sum_{i=1}^{m}l_{o}(\theta;\xi).$

Denote the stability gap and generalization error of original loss function as
$\epsilon_{s}^{o}$ and $\epsilon_{g}^{o}$, respectively. Theorem 4 bounds
links the stability with Lipschitz factor $\alpha$, smoothing factor $\beta$,
and number of iterations $T$ of SGD. Its proof can be found in (Hardt et al.,
2016).

######  Theorem 4 (Uniform stability of SGD (Hardt et al., 2016)).

Assume that $l_{o}(\theta;\xi)\in[0,1]$ is a $\alpha$-Lipschitz and
$\beta$-smooth loss function for every example $\xi$. Suppose that we rum SGD
for $T$ steps with monotonically non-increasing step size $\eta_{t}\leq c/t$.
Then SGD is uniformly stable with the stability factor $\epsilon_{s}^{o}$
satisfying:

$\displaystyle\epsilon_{s}^{o}\leq\frac{1+1/\beta
c}{n-1}(2c\alpha^{2})^{\frac{1}{\beta c+1}}T^{\frac{\beta c}{\beta c+1}}.$
(15.10)

Now, we have already bound the stability gap $\epsilon_{s}^{o}$ on original
loss. Then we will move onto the stability gap $\epsilon_{s}^{\mu}$ of loss
for Gaussian LPF kernel smoothed loss function. Let $\mu$ be distribution
$\mathcal{N}(0,\sigma^{2}I)$. By the definition of Gaussian LPF (Definition
1), the true loss and the empirical loss with respect to the Gaussian LPF
smoothed function are

$\displaystyle L_{\mu}^{true}(\theta):=(L^{true}_{o}\circledast
K)(\theta)=\int_{-\infty}^{\infty}L^{true}_{o}(\theta-\tau)\mu(\tau)d\tau=\mathbb{E}_{Z\sim\mu}[L^{true}_{o}(\theta+Z)],$
(15.11) $\displaystyle
L_{\mu}^{\mathcal{S}}(\theta)\quad:=(L^{\mathcal{S}}_{o}\circledast
K)(\theta)=\int_{-\infty}^{\infty}L^{\mathcal{S}}_{o}(\theta-\tau)\mu(\tau)d\tau=\mathbb{E}_{Z\sim\mu}[L^{\mathcal{S}}_{o}(\theta+Z)],$
(15.12)

where K is the Gaussian LPF kernel satisfies distribution $\mu$ and Z is a
random variable satisfies distribution $\mu$. Since
$L^{true}_{o}(\theta):=\mathbb{E}_{\xi\sim D}l_{o}(\theta;\xi)$ and
$L^{\mathcal{S}}_{o}(\theta):=\frac{1}{m}\sum_{i=1}^{m}l_{o}(\theta;\xi)$,
$L_{\mu}^{true}$ and $L_{\mu}$ could be rewritten as

$\displaystyle
L_{\mu}^{true}(\theta)\\!=\\!\\!\\!\int_{-\infty}^{\infty}\\!\\!\\!\\!\mathbb{E}_{\xi\sim
D}[l_{o}(\theta-\tau;\xi)]\mu(\tau)d\tau\\!=\\!\mathbb{E}_{\xi\sim
D}\left[\\!\int_{-\infty}^{\infty}\\!\\!\\!l_{o}(\theta-\tau;\xi)\mu(\tau)d\tau\right]\\!=\\!\mathbb{E}_{\xi\sim
D}\left[l_{\mu}(\theta;\xi)\right]$ (15.13) $\displaystyle
L_{\mu}^{\mathcal{S}}(\theta)\\!=\\!\int_{-\infty}^{\infty}\\!\\!\frac{1}{m}\sum_{i=1}^{m}l_{o}(\theta;\xi)\mu(\tau)d\tau\\!=\\!\frac{1}{m}\sum_{i=1}^{m}\left[\\!\int_{-\infty}^{\infty}\\!\\!l_{o}(\theta-\tau;\xi_{i})\mu(\tau)d\tau\right]=\frac{1}{m}\sum_{i=1}^{m}l_{\mu}(\theta;\xi_{i}).$
(15.14)

Compare formulas (15.13-15.14) with (15.6-15.7). We could conclude that the
true and empirical Gaussian LPF smoothed loss function ($L^{true}_{\mu}$ and
$L^{\mathcal{S}}_{\mu}$) is exactly the formula of original true and empirical
loss ($L^{true}_{o}$ and $L^{\mathcal{S}}_{o}$) by replacing
$l_{o}(\theta;\xi)$ with smoothed $l_{\mu}(\theta;\xi)$. Since LPF-SGD is
exactly performing SGD iteration on Gaussian LPF smoothed loss function
instead of original loss, the generalization error and stability gap of LPF-
SGD also satisfies Theorem 2 and Theorem 4 after replacing $l_{o}$ with
$l_{\mu}$.

In section 5.1 we analyze the change of Lipschitz continuous and smooth
properties of the objective function after Gaussian LPF smoothing. Therefore,
by Theorem 1, $l_{\mu}$ is $\alpha$-Lipschitz continuous and
$\min\\{\frac{\alpha}{\sigma},\beta\\}$-smooth. Define
$\hat{\beta}=\min\\{\frac{\alpha}{\sigma},\beta\\}$, then we could bound the
stability gap for LPF-SGD as

$\displaystyle\epsilon_{s}^{\mu}\leq\frac{1+1/\hat{\beta}c}{n-1}(2c\alpha^{2})^{\frac{1}{\beta
c+1}}T^{\frac{\beta c}{\beta c+1}}.$

Combine Theorem 1 with Theorem 4 we could have the following proposition.

######  Theorem 3 (Generalization error (GE) bound of LPF-SGD).

Assume that $l_{o}(\theta;\xi)\in[0,1]$ is a $\alpha$-Lipschitz and
$\beta$-smooth loss function for every example $\xi$. Suppose that we run SGD
and LPF-SGD for $T$ steps with non-increasing learning rate $\eta_{t}\leq
c/t$. Denote the generalization error bound (GE bound) of SGD and LPF-SGD as
$\hat{\epsilon}_{g}^{o}$ and $\hat{\epsilon}_{g}^{\mu}$, respectively. Then
the ratio of GE bound is

$\rho=\frac{\hat{\epsilon}_{g}^{\mu}}{\hat{\epsilon}_{g}^{o}}=\frac{1-p}{1-\hat{p}}\left(\frac{2c\alpha}{T}\right)^{\hat{p}-p}=O(\frac{1}{T^{\hat{p}-p}}),$
(15.15)

where $p=\frac{1}{\beta c+1}$,
$\hat{p}=\frac{1}{\min\\{\frac{\alpha}{\sigma},\beta\\}c+1}$.

Finally, the following two properties hold:

  * i)

If $\sigma>\frac{\alpha}{\beta}$ and $T\gg
2c\alpha^{2}\left(\frac{1-p}{1-\hat{p}}\right)^{\frac{1}{\hat{p}-p}}$,
$\rho\ll 1$.

  * ii)

If $\sigma>\frac{\alpha}{\beta}$ and $T>2c\alpha^{2}\exp(\frac{2}{1-p})$,
increasing $\sigma$ leads to a smaller $\rho$.

###### Proof.

For easy notation, denote $\hat{\beta}=\min\\{\frac{\alpha}{\sigma},\beta\\}$,
$\epsilon_{S}^{o}$ and $\epsilon_{s}^{\mu}$ are stability gaps of SGD and LPF-
SGD, respectively. From Theorem 4 and based on the facts that $l_{o}$ is
$\alpha$-Lipschitz continuous and $\beta$-smooth and that smoothed objective
$l_{\mu}$ is $\alpha$-Lipschitz continuous and
$\min\\{\frac{\alpha}{\sigma},\beta\\}$-smooth, the upper bounds for the
stability gaps are

$\displaystyle\epsilon_{s}^{o}$ $\displaystyle\leq\frac{1+1/\beta
c}{n-1}(2c\alpha^{2})^{\frac{1}{\beta c+1}}T^{\frac{\beta c}{\beta c+1}},$
$\displaystyle\epsilon_{s}^{\mu}$
$\displaystyle\leq\frac{1+1/\hat{\beta}c}{n-1}(2c\alpha^{2})^{\frac{1}{\hat{\beta}c+1}}T^{\frac{\hat{\beta}c}{\hat{\beta}c+1}}.$

Denote $p=\frac{1}{\beta c+1}$, $\hat{p}=\frac{1}{\hat{\beta}c+1}$, the bound
could be rewritten as

$\displaystyle\epsilon_{s}^{o}$
$\displaystyle\leq\frac{1}{(n-1)(1-p)}(2c\alpha^{2})^{p}T^{1-p},$
$\displaystyle\epsilon_{s}^{\mu}$
$\displaystyle\leq\frac{1}{(n-1)(1-\hat{p})}(2c\alpha^{2})^{\hat{p}}T^{1-\hat{p}}.$

By Theorem 2, the generalization errors $\epsilon_{g}^{o}$ and
$\epsilon_{g}^{\mu}$ are bounded by stability gaps $\epsilon_{s}^{o}$ and
$\epsilon_{s}^{\mu}$:

$\displaystyle\epsilon_{g}^{o}$
$\displaystyle\leq\epsilon_{s}^{o}\leq\frac{1}{(n-1)(1-p)}(2c\alpha^{2})^{p}T^{1-p},$
$\displaystyle\epsilon_{g}^{\mu}$
$\displaystyle\leq\epsilon_{s}^{\mu}\leq\frac{1}{(n-1)(1-\hat{p})}(2c\alpha^{2})^{\hat{p}}T^{1-\hat{p}}.$

Therefore, the GE bound for SGD and LPF-SGD could be written as

$\displaystyle\hat{\epsilon}_{g}^{o}=\frac{1}{(n-1)(1-p)}(2c\alpha^{2})^{p}T^{1-p}\text{
and
}\hat{\epsilon}_{g}^{\mu}=\frac{1}{(n-1)(1-\hat{p})}(2c\alpha^{2})^{\hat{p}}T^{1-\hat{p}},$

respectively. Then the ratio of GE bound is

$\displaystyle\rho=\frac{\hat{\epsilon}_{g}^{\mu}}{\hat{\epsilon}_{g}^{o}}=\frac{1-p}{1-\hat{p}}\left(\frac{2c\alpha}{T}\right)^{\hat{p}-p}=O(\frac{1}{T^{\hat{p}-p}}).$

  * i)

When $\sigma>\frac{\alpha}{\beta}$ and
$T>2c\alpha^{2}\left(\frac{1-p}{1-\hat{p}}\right)^{\frac{1}{\hat{p}-p}}$,
$\rho=\frac{1-p}{1-\hat{p}}(\frac{2c\alpha^{2}}{T})^{\hat{p}-p}<1$. Therefore,
if $\sigma>\frac{\alpha}{\beta}$ and $T\gg
2c\alpha^{2}\left(\frac{1-p}{1-\hat{p}}\right)^{\frac{1}{\hat{p}-p}}$,
$\rho\ll 1$ and property i) holds.

  * ii)

Denote $x:=\hat{p}-p$, the reciprocal of approximated ratio could be re-
written as

$\displaystyle\frac{1}{\rho}\approx(1-\frac{\hat{p}-p}{1-p})(\frac{T}{2c\alpha^{2}})^{\hat{p}-p}=(1-\frac{x}{1-p})(\frac{T}{2c\alpha^{2}})^{x}$

Define function $h(x)=(1-ax)b^{x}$, where $a=\frac{1}{1-p}$ and
$b=\frac{T}{2c\alpha^{2}}$. Compute the derivative of function $h$:

$\displaystyle h^{\prime}(x)=(-ax\ln b-a+\ln b)b^{x}$
$h^{\prime}(x_{0})=0\Longleftrightarrow x_{0}=\frac{lnb-a}{a\ln b}$

When $x\leq\frac{lnb-a}{a\ln b}$, $h^{\prime}(x)\geq 0$. Otherwise
$h^{\prime}(x)<0$. Since $0<p<\hat{p}<1$, obviously the domain of function $h$
is in the interval $[0,1]$. If $\frac{lnb-a}{a\ln b}>1$, the function $h$ is
increasing in its domain. Which means that if the difference between $\hat{p}$
and $p$ increase, the reciprocal of approximated ratio of stability gap
$\frac{1}{\rho}$ increase, which is equivalent to the approximate ratio $\rho$
of stability gap decrease. Because

$\frac{\ln b-a}{a\ln b}>1\Longleftrightarrow\ln
b>\frac{a}{1-a}\Longleftrightarrow T>2c\alpha^{2}e^{-p}.$

In all, we could conclude if $T>2c\alpha^{2}e^{-p}$, $\hat{p}-p$ increase
leads to the approximate ratio of stability gap $\rho$ decrease.

What’s more, we are going to analysis the relation between Gaussian filter
factor $\sigma$ and the difference $\hat{p}-p$. Since

$p=\frac{1}{\beta c+1},\quad\hat{p}=\frac{1}{\hat{\beta}c+1},$

where $\hat{\beta}=\min\\{\frac{\alpha}{\sigma},\beta\\}$. $\hat{p}-p$
increase is equivalent to $\hat{\beta}$ decrease. When the Gaussian factor
$\sigma$ is large enough ($\frac{\alpha}{\sigma}<\beta$), the smoother factor
$\hat{\beta}$ for function $l_{\mu}$ is exactly $\frac{\alpha}{\sigma}$.
Moreover, increasing the factor $\sigma$ leads to the decrease of
$\hat{\beta}$.

Due to the analysis above, if $T>2c\alpha^{2}e^{-p}$ and
$\frac{\alpha}{\sigma}<\beta$, increasing $\sigma$ will cause the approximate
ratio $\rho$ to decrease and the generalization error will be smaller. We
finish the proof for condition ii).

∎

###  15.4  Non-scalar covariance version

In this section, we analysis the case when the covariance
$\Sigma=\gamma*diag(||\theta_{1}||,||\theta_{2}||\cdots||\theta_{k}||)$ for
Gaussian kernel K is no longer a scalar diagonal matrix. For easy notation, we
denoted $\Sigma=diag(\sigma_{1}^{2},\cdots,\sigma_{d}^{2})$ where
$\sigma_{i}^{2}=\gamma*||\theta_{i}||$.

######  Theorem 5.

Let $\mu$ be the $\mathcal{N}(0,\Sigma)$ distribution, where
$\Sigma=diag(\sigma_{1}^{2},\cdots,\sigma_{d}^{2})\in\mathbb{R}^{d\times d}$
is diagonal. Denote
$\sigma_{-}^{2}=\min\\{\sigma_{1}^{2},\cdots,\sigma_{d}^{2}\\}$. Assume the
differentiable loss function
$l_{o}(\theta;\xi):\mathbb{R}^{d}\rightarrow\mathbb{R}$ is $\alpha$-Lipschitz
continuous and $\beta$-smooth with respect to $l_{2}$-norm. The smoothed loss
function $l_{\mu}(\theta;\xi)$ is defined as (5.1). Then the following
properties hold:

  * i)

$l_{\mu}$ is $\alpha$-Lipschitz continuous.

  * ii)

$l_{\mu}$ is continuously differentiable; moreover, its gradient is
$\min\\{\frac{\alpha}{\sigma_{-}},\beta\\}$-Lipschitz continuous, i.e.
$l_{\mu}$ is $\min\\{\frac{\alpha}{\sigma_{-}},\beta\\}$-smooth.

  * iii)

If l is convex,
$l_{\mu}(\theta;\xi)=l(\theta;\xi)+\alpha\sqrt{tr(\Sigma)}=l(\theta;\xi)+\alpha\sqrt{\sum_{i=1}^{d}\sigma_{i}^{2}}$.

In addition, for bound i) and iii), there exists a function $l$ such that the
bound cannot be improved by more than a constant factor.

###### Proof.

We are going to prove the properties one by one.

  * i)

The proof for properties i) is exactly the same as Theorem 1.

  * ii)

As is shown in the proof for Theorem 1, firstly, we need to first address that
$l_{\mu}$ is $\frac{\alpha}{\sigma}$-smooth. then show that $l_{\mu}$ is
$\beta$-smooth. Since, the proof for second part remains the same as what in
Theorem 1. We will focus on demonstrating $l_{\mu}$ is
$\frac{\alpha}{\sigma}$-smooth.

By Lemma 1, for $\forall x,y\in\mathbb{R}^{n}$,

$\displaystyle\left\lVert\nabla l_{\mu}(x;\xi)-\nabla
l_{\mu}(y;\xi)\right\rVert\leq\alpha\underbrace{\int|\mu(z-x)-\mu(z-y)|dz}_{I_{2}}.$
(15.16)

Denoted the integral as $I_{2}$. We follow the technique in (Lakshmanan and
Pucci De Farias, 2008) and (Duchi et al., 2012). Since $\mu(z-x)\geq\mu(z-y)$
is equivalent to $\left\lVert z-x\right\rVert\geq\left\lVert z-y\right\rVert$,

$\displaystyle I_{2}=$ $\displaystyle\int|\mu(z-x)-\mu(z-y)|dz$
$\displaystyle=$ $\displaystyle\int_{z:\left\lVert
z-x\right\rVert\geq\left\lVert
z-y\right\rVert}[\mu(z-x)-\mu(z-y)]dz+\int_{z:\left\lVert
z-x\right\rVert\leq\left\lVert z-y\right\rVert}[\mu(z-y)-\mu(z-x)]dz$
$\displaystyle=$ $\displaystyle 2\int_{z:\left\lVert
z-x\right\rVert\leq\left\lVert z-y\right\rVert}[\mu(z-x)-\mu(z-y)]dz$
$\displaystyle=$ $\displaystyle 2\int_{z:\left\lVert
z-x\right\rVert\leq\left\lVert z-y\right\rVert}\mu(z-x)dz-2\int_{z:\left\lVert
z-x\right\rVert\leq\left\lVert z-y\right\rVert}\mu(z-y)dz.$

Denote $u=z-x$ for $\mu(z-x)$ term and $u=z-y$ for $\mu(z-y)$ term, we have

$\displaystyle I_{2}=$ $\displaystyle 2\int_{z:\left\lVert
u\right\rVert\leq\left\lVert u-(x-y)\right\rVert}\mu(u)dz-2\int_{z:\left\lVert
u\right\rVert\geq\left\lVert u-(x-y)\right\rVert}\mu(u)dz$ $\displaystyle=$
$\displaystyle 2\mathbb{P}_{Z\sim\mu}(\left\lVert Z\right\rVert\leq\left\lVert
Z-(x-y)\right\rVert)-2\mathbb{P}_{Z\sim\mu}(\left\lVert
Z\right\rVert\geq\left\lVert Z-(x-y)\right\rVert).$

Obviously,

$\displaystyle\mathbb{P}_{Z\sim\mu}(\left\lVert Z\right\rVert\leq\left\lVert
Z-(x-y)\right\rVert)$ $\displaystyle=$
$\displaystyle\mathbb{P}_{Z\sim\mu}(\left\lVert
Z\right\rVert^{2}\leq\left\lVert Z-(x-y)\right\rVert^{2})$ $\displaystyle=$
$\displaystyle\mathbb{P}_{Z\sim\mu}(2\langle z,x-y\rangle\leq\left\lVert
x-y\right\rVert^{2})$ $\displaystyle=$
$\displaystyle\mathbb{P}_{Z\sim\mu}(2\langle z,\frac{x-y}{\left\lVert
x-y\right\rVert}\rangle\leq\left\lVert x-y\right\rVert),$

Denote $p=\frac{x-y}{\left\lVert x-y\right\rVert}\in\mathbb{R}^{d\times d}$,
$\frac{x-y}{\left\lVert x-y\right\rVert}$ has norm 1 implies
$\sum_{i=1}^{d}p_{i}^{2}=1$. Since $Z\sim\mathcal{N}(0,\Sigma)$ and
$\Sigma=diag(\sigma_{1}^{2},\cdots,\sigma_{d}^{2})$, each element in vector
$Z$ satisfies $z_{i}\sim\mathcal{N}(0,\sigma_{i}^{2})$. Hence, we have

$\langle z,\frac{x-y}{\left\lVert
x-y\right\rVert}\rangle=\sum_{i=1}^{d}p_{i}z_{i}\sim\mathcal{N}(0,\sum_{i=1}^{d}p_{i}^{2}\sigma_{i}^{2}).$

Denote $\sigma^{2}=\sum_{i=1}^{d}p_{i}^{2}\sigma_{i}^{2}$,
$\sigma_{+}^{2}=\max\\{\sigma_{1}^{2},\cdots,\sigma_{d}^{2}\\}$ and
$\sigma_{-}^{2}=\min\\{\sigma_{1}^{2},\cdots,\sigma_{d}^{2}\\}$. Because
$\sum_{i=1}^{d}p_{i}^{2}=1$, it is easy to know

$\displaystyle\langle z,\frac{x-y}{\left\lVert
x-y\right\rVert}\rangle\sim\mathcal{N}(0,\sigma^{2}),\quad\text{where
}\sigma_{-}^{2}\leq\sigma^{2}\leq\sigma_{+}^{2}.$ (15.17)

Hence, we have

$\displaystyle\mathbb{P}_{Z\sim\mu}(\left\lVert Z\right\rVert\leq\left\lVert
Z-(x-y)\right\rVert)$ $\displaystyle=$
$\displaystyle\mathbb{P}_{Z\sim\mu}(\langle z,\frac{x-y}{\left\lVert
x-y\right\rVert}\rangle\leq\frac{\left\lVert x-y\right\rVert}{2})$
$\displaystyle=$ $\displaystyle\int_{-\infty}^{\frac{\left\lVert
x-y\right\rVert}{2}}\frac{1}{\sqrt{2\pi\sigma^{2}}}\exp(-\frac{u^{2}}{2\sigma^{2}})du.$

Similarly,

$\displaystyle\mathbb{P}_{Z\sim\mu}(\left\lVert Z\right\rVert\geq\left\lVert
Z-(x-y)\right\rVert)$ $\displaystyle=$
$\displaystyle\mathbb{P}_{Z\sim\mu}(\langle z,\frac{x-y}{\left\lVert
x-y\right\rVert}\rangle\geq\frac{\left\lVert x-y\right\rVert}{2})$
$\displaystyle=$ $\displaystyle\int_{\frac{\left\lVert
x-y\right\rVert}{2}}^{+\infty}\frac{1}{\sqrt{2\pi\sigma^{2}}}\exp(-\frac{u^{2}}{2\sigma^{2}})du.$

Therefore,

$\displaystyle I_{2}$ $\displaystyle=2\int_{-\infty}^{\frac{\left\lVert
x-y\right\rVert}{2}}\frac{1}{\sqrt{2\pi\sigma^{2}}}\exp(-\frac{u^{2}}{2\sigma^{2}})du-2\int_{\frac{\left\lVert
x-y\right\rVert}{2}}^{+\infty}\frac{1}{\sqrt{2\pi\sigma^{2}}}\exp(-\frac{u^{2}}{2\sigma^{2}})du$
$\displaystyle=2\int_{-\frac{\left\lVert
x-y\right\rVert}{2}}^{\frac{\left\lVert
x-y\right\rVert}{2}}\frac{1}{\sqrt{2\pi\sigma^{2}}}\exp(-\frac{u^{2}}{2\sigma^{2}})du$
$\displaystyle\leq\frac{\sqrt{2}\left\lVert
x-y\right\rVert}{\sigma\sqrt{\pi}}\leq\frac{\sqrt{2}\left\lVert
x-y\right\rVert}{\sigma_{-}\sqrt{\pi}}$ (15.18)

In conclusion, combine formula (15.16) and (15.18) we have

$\displaystyle\left\lVert\nabla l_{\mu}(x;\xi)-\nabla
l_{\mu}(y;\xi)\right\rVert\leq\alpha\frac{\sqrt{2}\left\lVert
x-y\right\rVert}{\sigma_{-}\sqrt{\pi}}\leq\frac{\alpha}{\sigma_{-}}\left\lVert
x-y\right\rVert.$

We finish proving that $l_{\mu}$ is $\frac{\alpha}{\sigma_{-}}$-smooth. Since
covariance matrix $\Sigma$ for distribution $\mu$ is no longer a scalar matix
and $\mu$ is not rotationally symmetric, the bound can no longer be achieved.

  * iii)

By Jensen’s inequality, for left hand side:

$\displaystyle
l_{\mu}(\theta;\xi)=\mathbb{E}_{Z\sim\mu}[l_{o}(\theta+Z;\xi)]\geq
l_{o}(\theta+\mathbb{E}_{Z\sim\mu}[Z];\xi)=l_{o}(\theta;\xi).$

For the tightness proof, defining $l_{o}(\theta;\xi)=\frac{1}{2}v^{T}\theta$
for $v\in\mathbb{R}^{d}$ leads to $l_{\mu}=l_{o}$.

For right hand side:

$\displaystyle l_{\mu}(\theta;\xi)=$
$\displaystyle\mathbb{E}_{Z\sim\mu}[l_{o}(\theta+Z;\xi)]$ $\displaystyle\leq$
$\displaystyle l_{o}(\theta;\xi)+\alpha\mathbb{E}_{Z\sim\mu}[\left\lVert
Z\right\rVert]\quad\quad(\alpha\text{-Lipchitz continuous})$
$\displaystyle\leq$ $\displaystyle
l_{o}(\theta;\xi)+\alpha\sqrt{\mathbb{E}[\left\lVert Z\right\rVert^{2}]}.$

Letting $C^{T}C=\Sigma$ and $V\sim\mathcal{N}(0,I)$, because
$Z\sim\mathcal{N}(0,\Sigma)$, we have

$\displaystyle\mathbb{E}[\left\lVert Z\right\rVert^{2}]=\mathbb{E}[\left\lVert
CV\right\rVert^{2}]=\mathbb{E}[V^{T}C^{T}CV]=tr(C^{T}C\mathbb{E}[V^{T}V])=tr(\Sigma).$

Therefore,

$\displaystyle
l_{\mu}(\theta;\xi)=l_{o}(\theta;\xi)+\alpha\sqrt{tr(\Sigma)}=l_{o}(\theta;\xi)+\alpha\sqrt{\sum_{i=1}^{d}\sigma_{i}^{2}}.$

For the tightness proof, taking
$l_{o}(\theta;\xi)=\alpha\left\lVert\theta\right\rVert$. Since
$l_{\mu}(\theta;\xi)\geq c\alpha\sqrt{tr(\Sigma)}$ for some constant $c$.
Therefore, the bound cannot be improved by more than a constant factor.

∎

######  Proposition 1.

Let $\mu$ be the $\mathcal{N}(0,\Sigma)$ distribution, where
$\Sigma=diag(\sigma_{1}^{2},\cdots,\sigma_{d}^{2})\in\mathbb{R}^{d\times d}$
is diagonal. Denote
$\sigma_{-}^{2}=\left\lVert\Sigma\right\rVert_{\infty}=\min\\{\sigma_{1}^{2},\cdots,\sigma_{d}^{2}\\}$.
Assume loss function
$l_{o}(\theta;\xi)\\!:\\!\mathbb{R}^{d}\\!\rightarrow\\!\mathbb{R}$ is
$\alpha$-Lipschitz and $\beta$-smooth. The smoothed loss function $l_{\mu}$ is
defined as (5.1). Suppose we execute SGD and LPF-SGD for T steps with non-
increasing learning rate $\eta_{t}\leq c/t$. Denote the generalization error
bound (GE bound) of SGD and LPF-SGD as $\hat{\epsilon}_{g}^{o}$ and
$\hat{\epsilon}_{g}^{\mu}$, respectively. Then the ratio of GE bound is

$\rho=\frac{\hat{\epsilon}_{g}^{\mu}}{\hat{\epsilon}_{g}^{o}}=\frac{1-p}{1-\hat{p}}\left(\frac{2c\alpha}{T}\right)^{\hat{p}-p}=O(\frac{1}{T^{\hat{p}-p}}),$
(15.19)

where $p=\frac{1}{\beta c+1}$,
$\hat{p}=\frac{1}{\min\\{\frac{\alpha}{\sigma},\beta\\}c+1}$.

Finally, the following two properties hold:

  * i)

If $\sigma_{-}>\frac{\alpha}{\beta}$ and $T\gg
2c\alpha^{2}\left(\frac{1-p}{1-\hat{p}}\right)^{\frac{1}{\hat{p}-p}}$,
$\rho\ll 1$.

  * ii)

If $\sigma_{-}>\frac{\alpha}{\beta}$ and $T>2c\alpha^{2}e^{-p}$, increasing
$\sigma_{-}$ leads to a smaller $\rho$.

###### Proof.

By Theorem 5, the smoothed loss function $l_{\mu}$ is $\alpha$-Lipschitz
continuous and $\min\\{\frac{\alpha}{\sigma_{-}},\beta\\}$-smooth. This gives
as equivalency to Theorem 1 after substituting $\sigma_{-}$ for $\sigma$.
Therefore, proof of Theorem 1 is exactly the same as that of Proposition 3
after performing this substitution and therefore will be omitted.

∎