# Bekenstein-Hawking Entropy Products for NUT class of Black Holes in AdS
Space

Parthapratim<EMAIL_ADDRESS>
Department of Physics
Hiralal Mazumdar Memorial College For Women
Dakshineswar, Kolkata-700035, India

###### Abstract

We derive the entropy product rule for Taub-NUT (Newman-Unti-Tamburino)-de
Sitter black hole (BH) and Taub-NUT–Anti-de Sitter BH. We show that the
entropy products in terms of both the physical horizons are _mass-
independent_. Both _perturbative_ approximation and _direct_ method have been
considered. By introducing the cosmological horizon we show that for Taub-NUT-
de Sitter BH, there exists a mass-independent entropy functional relation in
terms of three horizons namely event horizon (EH), Cauchy horizon (CH) and
cosmological horizon (CHH) which depends on cosmological parameter ($\Lambda$)
and the NUT parameter ($N$). For Taub-NUT-anti-de Sitter BHs, we determine the
mass-independent entropy functional relations in terms of two physical
horizons (namely EH and CH) which depends on only NUT parameter. Some-times
some complicated functions of EH entropy and CH entropy are also strictly
mass-independent. This is plausible only due to the new formalism developed in
[2] [Phys. Rev. D 100, 101501(R) (2019)] for NUT class of BHs. The formalism
states that a generic four dimensional Taub-NUT spacetime should be described
completely in terms of three or four different types of thermodynamic hairs.
They could be defined as the Komar mass ($M=m$), the angular momentum
($J_{n}=mn$), the gravitomagnetic charge ($N=n$), the dual (magnetic) mass
$(\tilde{M}=n)$. Finally, we could say that this universality is mainly due to
the presence of _new conserved charges $J_{N}=MN$_ which is closely analogue
to the Kerr like angular momentum $J=aM$.

##  1 Introduction

Area (or entropy) products [1, 4, 5, 6, 7, 8, 9, 10, 11] are very fascinating
topic of research in BH physics. These products are constructed in terms of
the entropy of event (outer) horizons (${\cal H}^{+}$) and Cauchy (inner)
horizons (${\cal H}^{-}$). Again these horizons are called as physical
horizons 222The fact that CH is a blue-shift region while EH is a red-shift
region by its own virtue. It should be noted that the CH is highly unstable
due to the exterior perturbation [38]. The products are fascinating in a sense
that they are independent of the Arnowitt-Deser-Misner (ADM) mass of the BH
spacetime and depends only on various quantised charges, _quantised_ angular
momentum and moduli etc.. For example, it should be noted that for most
general axisymmetric Kerr-Newman class of BH having EH and CH, the entropy
product of ${\cal H}^{\pm}$ should be

$\displaystyle S_{+}S_{-}$ $\displaystyle=$ $\displaystyle
4\pi^{2}\left[J^{2}+\frac{Q^{4}}{4}\right]~{}.$ (1)

The fundamental physics is that due to stationarity there is an absence of
matter between the two horizons [1]. Now a vital question is that what is the
origin of Bekenstein-Hawking [19, 18] entropy $S_{\pm}=\frac{A_{\pm}}{4}$ at
the microscopic level? This is a real problem in quantum theory of gravity.
Here $A_{\pm}$ is the area of the black hole EH and CH. There has been a
momentous success in four and five dimensions for super-symmetric Bogomol’ni-
Prasad-Sommerfield (BPS) class of black holes [20].

Where it was exhibited that the microscopic degrees of freedom could be
explained in terms of 2D conformal-field-theory (CFT). If there exists BH
entropy ($S_{+}$) for EH then it is also equally authenticate that there
exists BH entropy ($S_{-}$) for CH. Hence there might be a relevance of inner
horizon (CH) in BH mechanics to understanding the microscopic nature of inner
BH entropy in compared with the outer BH entropy. For extremal Kerr spacetime,
the microscopic entropy should be found in [21]. However, the detailed
information of the microscopic entropy of non-extremal BH still to be obscure
to us. Some fruitful progress have been indicated in [22]. For BPS category of
BHs, the entropy product of ${\cal H}^{\pm}$ is derived to be [5]

$\displaystyle S_{+}S_{-}$ $\displaystyle=$
$\displaystyle(2\pi)^{2}\left[\sqrt{N_{L}}+\sqrt{N_{R}}\right]\left[\sqrt{N_{L}}-\sqrt{N_{R}}\right]$
(2) $\displaystyle=$ $\displaystyle
4\pi^{2}N,\,\,N\in{\mathbb{N}},N_{L}\in{\mathbb{N}},N_{R}\in{\mathbb{N}}~{}.$
(3)

The integers $N_{L}$ and $N_{R}$ can be interpreted as the excitation numbers
of the left and right moving modes of a weakly-coupled 2D CFT. The parameters
$N_{L}$ and $N_{R}$ are depends explicitly on all the BH parameters. This
indicates that the product should be quantized [23, 24, 25, 26] and it is an
integer quantity.

Sometimes the conjectured _mass-independence_ also breaks down. For instance,
by introducing the cosmological constant, it has been shown that the entropy
products for Schwarzschild-de-Sitter (Kottler) BH in terms of EH and CH are
_not_ mass-independent [1]. By adding the third horizon namely virtual horizon
(VH) (even though unphysical), the results do not change. For Schwarzschild-
anti-de-Sitter BHs, there exists three horizons: one physical horizon (called
as EH) and other two horizons are VH (unphysical). Hence the results indicates
the entropy products in terms of these horizons are _not_ mass-independent.

Introducing the charge parameter in Schwarzschild-de-Sitter spacetime i.e. for
Reissner-Nordström-de Sitter BH, the situation is little bit improved. Here,
the Killing horizons equations are fourth order polynomial. There exists three
physical horizons (EH, CH and CHH) and one VH. So, the entropy products in
terms of three physical horizons are mass-independent [1]. Though they are
some complicated function of physical horizons but they are no less than mass-
independent. Similarly, for Reissner-Nordström-anti-de Sitter BH, there exists
two physical horizons and two VHs. So, the entropy products are determined
perturbatively and it was shown that the products are not mass-independent. In
a nutshell, the entropy products are _not generic_.

However, in this work interestingly we prove the entropy products for NUT
class of BHs in AdS space have _generic_ feature. Specifically, we have
considered _Taub-NUT-de Sitter BHs_ and _Taub-NUT–anti-de Sitter_ BHs. First,
we have calculated perturbatively the entropy products in terms of EH and CH.
We prove that the products are _mass-independent_. Next we compute the entropy
products in terms of three physical horizons by direct method and show that
the functional form of three physical horizons is independent of the mass
parameter but it depends on only the NUT parameter and cosmological constant.
Next we calculate the mass-independent relation in terms of two physical
horizons.

In some cases, there exists mass-dependent relation in terms of two physical
horizons but introducing the formalism developed in [2] [See also [3]] we can
reformulate it mass-independent form. The formalism argued that a generic four
dimensional Taub-NUT spacetime can be described completely in terms of three
or four different types of thermodynamic hairs. They should be defined as the
Komar mass ($M=m$), the angular momentum ($J_{n}=mn$), the gravitomagnetic
charge ($N=n$), the dual (magnetic) mass $(\tilde{M}=n)$. The generic feature
comes solely due to the presence of new conserved charges $J_{N}=MN$ which is
closely analogue to the Kerr like angular momentum $J=aM$.

In our previous work, we have already examined the area (or entropy) products
for NUT class of BHs [9]. We have considered there the Lorentzian Taub-NUT BH,
Euclidean Taub-NUT BH, Reissner-Nordström–Taub-NUT, Kerr-Taub-NUT BH and Kerr-
Newman-Taub-NUT BH. In each cases, we proved that the entropy product of both
physical horizons is universal in nature after the incorporation of angular
momentum like parameter $J_{N}=MN$ with the generic parameters $M$ and $N$ as
a global conserved charges. However we have _not_ considerd the AdS spacetime.
Here we have explicitly considered the _AdS spacetime particularly Taub-NUT-de
Sitter BHs and Taub-NUT-anti-de Sitter BHs_. This is an another strong reason
to investigate this work.

It should be mentioned that in recent years various aspects of thermodynamics
of Lorentzian Taub-NUT BH in ($3+1$) dimensional Einstein-Maxwell gravity have
studied by many authors in different perspectives. We should mention some of
good references [16, 17][See also[27, 28, 29, 30, 31, 32, 33, 34, 35]] for our
readers.

The paper is organized as follows. In the next section, we will consider the
Taub-NUT-de Sitter BHs and examined the mass-independence feature both
perturbatively and direct method. Analogously in Sec. (3), we will examine the
mass-independent feature both perturbatively and direct method for Taub-
NUT–anti-de Sitter BHs. Finally, in Sec. (4), we have given the conclusions of
the work.

##  2  Taub-NUT-de Sitter BHs

The Taub-NUT–de-Sitter spacetime in Schwarzschild like coordinates has the
form [12, 13, 14, 15, 36][Page-236, Griffiths & Podolský]

$\displaystyle ds^{2}$ $\displaystyle=$
$\displaystyle-\Upsilon(r)\,\left(dt+2n\cos\theta
d\phi\right)^{2}+\frac{dr^{2}}{\Upsilon(r)}+\left(r^{2}+n^{2}\right)\left(d\theta^{2}+\sin^{2}\theta
d\phi^{2}\right)~{},$ (4)

where the function $\Upsilon(r)$ is given by

$\displaystyle\Upsilon(r)$ $\displaystyle=$
$\displaystyle\frac{1}{r^{2}+n^{2}}\left[r^{2}-n^{2}-2mr-\frac{\Lambda}{3}\left(r^{4}+6n^{2}r^{2}-3n^{4}\right)\right]$
(5)

We know the global conserved charges for Taub-NUT spacetime [2] is

$\displaystyle m$ $\displaystyle=$ $\displaystyle M~{}\mbox{(Komar mass)}$
$\displaystyle n$ $\displaystyle=$ $\displaystyle N~{}\mbox{(Gravitomagnetic
charge)}$ $\displaystyle m\,n$ $\displaystyle=$ $\displaystyle
J_{n}=J_{N}=M\,N~{}\mbox{(Angular momentum)}~{}.$ (6)

If we incorporate the condition [Eq. (6)], then we may rewrite the metric as

$\displaystyle ds^{2}$ $\displaystyle=$
$\displaystyle-\Upsilon(r)\,\left(dt+2N\cos\theta
d\phi\right)^{2}+\frac{dr^{2}}{\Upsilon(r)}+\left(r^{2}+N^{2}\right)\left(d\theta^{2}+\sin^{2}\theta
d\phi^{2}\right)~{},$ (7)

and the function $\Upsilon(r)$ is defined by

$\displaystyle\Upsilon(r)$ $\displaystyle=$
$\displaystyle\frac{1}{r^{2}+N^{2}}\left[r^{2}-N^{2}-2Mr-\frac{\Lambda}{3}\left(r^{4}+6N^{2}r^{2}-3N^{4}\right)\right]$
(8)

It may be noted that the metric reduces to Schwarzschild-de Sitter (Kottler)
spacetime when $N=0$. The Hawking temperature of the BH is

$T_{\pm}=\frac{{\kappa}_{\pm}}{2\pi}=\frac{\Upsilon^{\prime}(r_{\pm})}{4\pi\left(r_{\pm}^{2}+N^{2}\right)}$

where $\kappa_{\pm}$ is the surface gravity of the BH. The first law of
thermodynamics with cosmological constant is derived in Ref. [2] and without
cosmological constant is derived in [10].

Now the Killing horizons are determined by solving the following equation

$\displaystyle\Upsilon(r)$ $\displaystyle=$ $\displaystyle 0$ (9)

This can be rewritten as

$\displaystyle
r^{2}-N^{2}-2Mr-\frac{\Lambda}{3}\left(r^{4}+6N^{2}r^{2}-3N^{4}\right)$
$\displaystyle=$ $\displaystyle 0~{}$ (10)

For $\Lambda>0$, it is advantageous to put

$b^{2}=\frac{1}{\Lambda},$

where $b$ denotes the spatial radius of curvature. Thus

$\displaystyle r^{4}-3(b^{2}-2N^{2})r^{2}+6Mb^{2}r+3b^{2}N^{2}-3N^{4}$
$\displaystyle=$ $\displaystyle 0~{}$ (11)

In the limit $\Lambda\rightarrow 0$ (or $b\rightarrow\infty$) we find standard
Taub-NUT spacetime. Also $N\rightarrow 0$ and $\Lambda\neq 0$ gives
Schwarzschild–de Sitter (Kottler) spacetime. The quartic equation [Eq. (11)]
can be rewritten as

$\displaystyle
r^{4}-3(b^{2}-2N^{2})\left[r^{2}-2M\left(\frac{b^{2}}{b^{2}-2N^{2}}\right)r+\left(\frac{N^{4}-b^{2}N^{2}}{b^{2}-2N^{2}}\right)\right]$
$\displaystyle=$ $\displaystyle 0~{}$ (12)

It can be reformulated as

$\displaystyle r^{4}-3(b^{2}-2N^{2})(r-r_{+})(r-r_{-})$ $\displaystyle=$
$\displaystyle 0~{}$ (13)

where

$r_{+}+r_{-}=\frac{2M}{\left(1-2\frac{N^{2}}{b^{2}}\right)}$

and

$r_{+}\,r_{-}=\frac{N^{2}\left(\frac{N^{2}}{b^{2}}-1\right)}{\left(1-2\frac{N^{2}}{b^{2}}\right)}$

where $r_{\pm}$ denote two roots of the term of the square bracket in Eq.
(12), and they reduces to the horizon radii of the Taub-NUT solution when
$b\rightarrow\infty$.

###  2.1 Perturbative Analysis

The quartic equation in Eq. (13) has an exact solution but it is more
convenient to find the roots perturbatively. To do that we can re-write the
above equation as

$\displaystyle r$ $\displaystyle=$ $\displaystyle
r_{\pm}+\frac{r^{4}}{3\left(b^{2}-2N^{2}\right)\left(r-r_{\mp}\right)}.~{}$
(14)

Now we can solve it perturbatively.

####  2.1.1 Event and Cauchy Horizons

To a first approximation, for outer or event horizon (${\cal H}^{+}$) we get

$\displaystyle r_{h}\approx
r_{+}+\frac{r_{+}^{4}}{3\left(b^{2}-2N^{2}\right)\left(r_{+}-r_{-}\right)}=r_{+}\left[1+\frac{r_{+}^{3}}{3\left(b^{2}-2N^{2}\right)\left(r_{+}-r_{-}\right)}\right].~{}$
(15)

Similarly, for inner or Cauchy horizon (${\cal H}^{-}$) we get

$\displaystyle r_{i}\approx
r_{-}+\frac{r_{-}^{4}}{3\left(b^{2}-2N^{2}\right)\left(r_{-}-r_{+}\right)}=r_{-}\left[1-\frac{r_{-}^{3}}{3\left(b^{2}-2N^{2}\right)\left(r_{+}-r_{-}\right)}\right].~{}$
(16)

Accordingly,

$\displaystyle r_{h}\,r_{i}\approx
r_{+}\,r_{-}\left[1+\frac{r_{+}^{3}-r_{-}^{3}}{3\left(b^{2}-2N^{2}\right)\left(r_{+}-r_{-}\right)}\right].~{}$
(17)

and therefore

$\displaystyle r_{h}\,r_{i}\approx
r_{+}\,r_{-}\left[1+\frac{r_{+}^{2}+r_{-}^{2}+r_{+}r_{-}}{3\left(b^{2}-2N^{2}\right)}\right].~{}$
(18)

Now

$\displaystyle
r_{+}^{2}+r_{-}^{2}+r_{+}r_{-}=\frac{4M^{2}}{\left(1-2\frac{N^{2}}{b^{2}}\right)^{2}}-\frac{N^{2}\left(\frac{N^{2}}{b^{2}}-1\right)}{\left(1-2\frac{N^{2}}{b^{2}}\right)}.~{}$
(19)

This indicates that

$\displaystyle
r_{h}\,r_{i}\approx\frac{N^{2}\left(\frac{N^{2}}{b^{2}}-1\right)}{\left(1-2\frac{N^{2}}{b^{2}}\right)}\left[1+\frac{\left\\{\frac{4M^{2}}{\left(1-2\frac{N^{2}}{b^{2}}\right)^{2}}-\frac{N^{2}\left(\frac{N^{2}}{b^{2}}-1\right)}{\left(1-2\frac{N^{2}}{b^{2}}\right)}\right\\}}{3b^{2}\left(1-2\frac{N^{2}}{b^{2}}\right)}\right].~{}$
(20)

This can also be written as

$\displaystyle r_{h}\,r_{i}\approx\frac{N^{2}\left(\Lambda
N^{2}-1\right)}{\left(1-2\Lambda
N^{2}\right)}\left[1+\frac{\Lambda}{3}\frac{\left\\{\frac{4M^{2}}{\left(1-2\Lambda
N^{2}\right)^{2}}-\frac{N^{2}\left(\Lambda N^{2}-1\right)}{\left(1-2\Lambda
N^{2}\right)}\right\\}}{\left(1-2\Lambda
N^{2}\right)}+\mathcal{O}(\Lambda^{2})\right].~{}$ (21)

Now we need to know the entropy of the BH. It is determined by the following
equation

$\displaystyle S_{h}$ $\displaystyle=$
$\displaystyle\frac{A_{h}}{4}=\frac{1}{4}\int^{2\pi}_{0}\int^{\pi}_{0}\sqrt{g_{\theta\theta}\,g_{\phi\phi}}{\mid}_{r=r_{h}}d\theta\,d\phi=\pi(r_{h}^{2}+N^{2})$
(22)

and consequently for ${\cal H}^{-}$, the entropy becomes

$\displaystyle S_{i}$ $\displaystyle=$ $\displaystyle\pi(r_{i}^{2}+N^{2})$
(23)

Hence

$\displaystyle S_{h}\,S_{i}=\pi^{2}\Biggl{[}\frac{N^{4}\left(\Lambda
N^{2}-1\right)^{2}}{\left(1-2\Lambda
N^{2}\right)^{2}}\left\\{1+\frac{2}{3}\Lambda\frac{\left(\frac{4M^{2}}{(1-2\Lambda
N^{2})^{2}}-\frac{N^{2}(\Lambda N^{2}-1)}{(1-2\Lambda
N^{2})}\right)}{(1-2\Lambda N^{2})}\right\\}\ $
$\displaystyle+N^{2}\Biggl{[}\frac{4M^{2}}{(1-2\Lambda
N^{2})^{2}}\left\\{1+\frac{2}{3}\Lambda\frac{\left(\frac{4M^{2}}{(1-2\Lambda
N^{2})^{2}}-\frac{N^{2}(\Lambda N^{2}-1)}{(1-2\Lambda
N^{2})}\right)}{(1-2\Lambda N^{2})}\right\\}$
$\displaystyle-\frac{2N^{2}\left(\Lambda N^{2}-1\right)}{\left(1-2\Lambda
N^{2}\right)}\Biggl{\\{}1+\frac{\Lambda}{3}\frac{\left(\frac{4M^{2}}{\left(1-2\Lambda
N^{2}\right)^{2}}-\frac{N^{2}\left(\Lambda N^{2}-1\right)}{\left(1-2\Lambda
N^{2}\right)}\right)}{\left(1-2\Lambda N^{2}\right)}\Biggr{\\}}\Biggr{]}$
$\displaystyle+N^{4}+\mathcal{O}(\Lambda^{2})\Biggr{]}~{}$ (24)

This indicates that the entropy product is explicitly mass dependent. Taking
cognizance of Eq. (6), we find

$\displaystyle S_{h}\,S_{i}=\pi^{2}\Biggl{[}\frac{N^{2}\left(\Lambda
N^{2}-1\right)^{2}}{\left(1-2\Lambda
N^{2}\right)^{2}}\left\\{N^{2}+\frac{2}{3}\Lambda\frac{\left(\frac{4J_{N}^{2}}{(1-2\Lambda
N^{2})^{2}}-\frac{N^{4}(\Lambda N^{2}-1)}{(1-2\Lambda
N^{2})}\right)}{(1-2\Lambda N^{2})}\right\\}\ $
$\displaystyle+\frac{4J_{N}^{2}}{(1-2\Lambda
N^{2})^{2}}\left\\{1+\frac{2}{3}\Lambda\frac{\left(\frac{4J_{N}^{2}}{N^{2}(1-2\Lambda
N^{2})^{2}}-\frac{N^{2}(\Lambda N^{2}-1)}{(1-2\Lambda
N^{2})}\right)}{(1-2\Lambda N^{2})}\right\\}$
$\displaystyle-\frac{2N^{2}\left(\Lambda N^{2}-1\right)}{\left(1-2\Lambda
N^{2}\right)}\Biggl{\\{}N^{2}+\frac{\Lambda}{3}\frac{\left(\frac{4J_{N}^{2}}{\left(1-2\Lambda
N^{2}\right)^{2}}-\frac{N^{2}\left(\Lambda N^{2}-1\right)}{\left(1-2\Lambda
N^{2}\right)}\right)}{\left(1-2\Lambda N^{2}\right)}\Biggr{\\}}$
$\displaystyle+N^{4}+\mathcal{O}(\Lambda^{2})\Biggr{]}~{}$ (25)

which is definitely _mass-independent_.

For our record we also write

$\displaystyle
r_{h}+r_{i}\approx\frac{2M}{\left(1-2\frac{N^{2}}{b^{2}}\right)}\left[1+\frac{\left\\{\frac{4M^{2}}{\left(1-2\frac{N^{2}}{b^{2}}\right)^{2}}-\frac{N^{2}\left(\frac{N^{2}}{b^{2}}-1\right)}{\left(1-2\frac{N^{2}}{b^{2}}\right)}\right\\}}{3b^{2}\left(1-2\frac{N^{2}}{b^{2}}\right)}\right].~{}$
(26)

which is again mass dependent. But taking cognizance of Eq. (6), we see that

$\displaystyle
r_{h}+r_{i}\approx\frac{2J_{N}}{N\left(1-2\frac{N^{2}}{b^{2}}\right)}\left[1+\frac{\left\\{\frac{4J_{N}^{2}}{N^{2}\left(1-2\frac{N^{2}}{b^{2}}\right)^{2}}-\frac{N^{2}\left(\frac{N^{2}}{b^{2}}-1\right)}{\left(1-2\frac{N^{2}}{b^{2}}\right)}\right\\}}{3b^{2}\left(1-2\frac{N^{2}}{b^{2}}\right)}\right].~{}$
(27)

this quantity is surely _mass-independent_.

####  2.1.2 Cosmological Horizon

Now we will see where is the cosmological horizon in this perturbative
procedure? To do that from the exact Killing horizon equation (13) we have

$\displaystyle r^{2}$ $\displaystyle=$ $\displaystyle
3(b^{2}-2N^{2})\frac{(r-r_{+})(r-r_{-})}{r^{2}}~{}$ (28)

As a zero order approximation, we get

$\displaystyle r_{\Lambda}\approx\sqrt{3}b-\sqrt{3}\frac{N^{2}}{b}~{}$ (29)

As a first order approximation, we get

$\displaystyle r_{\Lambda}$ $\displaystyle\approx$
$\displaystyle\sqrt{3}b\left(1-\frac{N^{2}}{b^{2}}\right)\left[\frac{\left\\{\sqrt{3}b\left(1-\frac{N^{2}}{b^{2}}\right)-r_{+}\right\\}\left\\{\sqrt{3}b\left(1-\frac{N^{2}}{b^{2}}\right)-r_{-}\right\\}}{\sqrt{3}b\left(1-\frac{N^{2}}{b^{2}}\right)}\right]^{\frac{1}{2}}$
(30) $\displaystyle\approx$
$\displaystyle\sqrt{3}b\left(1-\frac{N^{2}}{b^{2}}\right)\left[1-\frac{r_{+}+r_{-}}{2\sqrt{3}b\left(1-\frac{N^{2}}{b^{2}}\right)}\right]$
(31) $\displaystyle\approx$
$\displaystyle\sqrt{3}b\left(1-\frac{N^{2}}{b^{2}}\right)-M\left(1+2\frac{N^{2}}{b^{2}}\right)~{}$
(32)

Thus the cosmological horizon is situated at

$\displaystyle
r_{\Lambda}\approx\sqrt{3}b-M-\frac{N^{2}}{b^{2}}(\sqrt{3}b+2M)~{}$ (33)

It implies that the cosmological horizon depends on both NUT charge and the
mass parameter including the cosmological constant.

####  2.1.3 Virtual Horizon

Now we will determine the location of virtual horizon (unphysical) from the
exact quartic equation. To do that we find from the exact quartic equation

$\displaystyle r_{V}$ $\displaystyle=$
$\displaystyle-\left(r_{h}+r_{i}+r_{\Lambda}\right)~{}$ (34)

Thus to a first approximation

$\displaystyle r_{V}\approx\sqrt{3}b-M-\frac{N^{2}}{b^{2}}(2M-\sqrt{3}b)~{}$
(35)

###  2.2 Exact Results

Which relations are exactly independent of $M$? This is our main aim in this
section. To do that from exact quartic equation we have

$\displaystyle r_{h}\,r_{i}\,r_{\Lambda}\,r_{V}$ $\displaystyle=$
$\displaystyle-3N^{2}(N^{2}-b^{2})~{}$ (36)

This can be rewritten in terms of physical horizons

$\displaystyle r_{h}\,r_{i}\,r_{\Lambda}(r_{h}+r_{i}+r_{\Lambda})$
$\displaystyle=$ $\displaystyle 3N^{2}(N^{2}-b^{2})~{}$ (37)

indicating that it is strictly independent of $M$. Now we want to write this
equation in terms entropy to get a relation like $S_{+}S_{-}$. Thus the
reduced entropy could be defined for different horizons as

$\tilde{S}_{h}=\frac{S_{h}}{\pi},\,\,\tilde{S}_{i}=\frac{S_{i}}{\pi},\,\,\tilde{S}_{\Lambda}=\frac{S_{\Lambda}}{\pi}$

In terms of reduced entropy one obtains the mass-independent relation

$\left[\sqrt{\tilde{S}_{h}-N^{2}}+\sqrt{\tilde{S}_{i}-N^{2}}+\sqrt{\tilde{S}_{\Lambda}-N^{2}}\right]\times$
$\displaystyle\sqrt{\tilde{S}_{h}-N^{2}}\,\sqrt{\tilde{S}_{i}-N^{2}}\,\sqrt{\tilde{S}_{\Lambda}-N^{2}}=3N^{2}(N^{2}-b^{2})~{}$
(38)

But it not looks like that of $S_{+}S_{-}$. So we take the another condition
from quartic equation

$\sum_{i>j}r_{i}r_{j}=-3(b^{2}-2N^{2}).~{}$ (39)

This implies that

$\left(r_{h}+r_{i}+r_{\Lambda}\right)\,r_{V}+r_{h}\,\left(r_{i}+r_{\Lambda}\right)+r_{i}\,r_{\Lambda}=-3(b^{2}-2N^{2}),~{}$
(40)

Moreover,

$\left(r_{h}+r_{i}+r_{\Lambda}\right)^{2}-r_{h}\,\left(r_{i}+r_{\Lambda}\right)-r_{i}\,r_{\Lambda}=3(b^{2}-2N^{2}),~{}$
(41)

Furthermore,

$\displaystyle
r_{h}^{2}+r_{i}^{2}+r_{\Lambda}^{2}+r_{h}\,r_{i}+r_{i}\,r_{\Lambda}+r_{\Lambda}\,r_{h}=3(b^{2}-2N^{2}).~{}$
(42)

This is also explicitly mass-independent. Now in terms of entropy it can be
written as

$\left(\tilde{S}_{h}+\tilde{S}_{i}+\tilde{S}_{\Lambda}-3N^{2}\right)+\sqrt{\tilde{S}_{h}-N^{2}}\,\sqrt{\tilde{S}_{i}-N^{2}}+$
$\displaystyle\sqrt{\tilde{S}_{i}-N^{2}}\,\sqrt{\tilde{S}_{\Lambda}-N^{2}}+\sqrt{\tilde{S}_{h}-N^{2}}\,\sqrt{\tilde{S}_{\Lambda}-N^{2}}$
$\displaystyle=$ $\displaystyle 3(b^{2}-2N^{2}).~{}$ (43)

Eliminating further one obtains

$\displaystyle\frac{r_{h}\,r_{i}\,r_{\Lambda}\,(r_{h}+r_{i}+r_{\Lambda})}{r_{h}^{2}+r_{i}^{2}+r_{\Lambda}^{2}+r_{h}r_{i}+r_{i}\,r_{\Lambda}+r_{\Lambda}\,r_{h}}=\frac{N^{2}(N^{2}-b^{2})}{(b^{2}-2N^{2})}~{}$
(44)

Unquestionably, this is mass-independent. But it is somehow a complicated
function of three physical horizon radii. It strictly depends upon the NUT
charge and cosmological constat.

If one can prefer it to write in terms of entropy then the equation would be

$\displaystyle f(\tilde{S}_{h},\,\tilde{S}_{i},\,\tilde{S}_{\Lambda})$
$\displaystyle=$
$\displaystyle\frac{N^{2}\left(\frac{N^{2}}{b^{2}}-1\right)}{\left(1-2\frac{N^{2}}{b^{2}}\right)}~{}$
(45)

where

$f(\tilde{S}_{h},\,\tilde{S}_{i},\,\tilde{S}_{\Lambda})=$
$\displaystyle\frac{\left[\sqrt{\tilde{S}_{h}-N^{2}}+\sqrt{\tilde{S}_{i}-N^{2}}+\sqrt{\tilde{S}_{\Lambda}-N^{2}}\right]\sqrt{\tilde{S}_{h}-N^{2}}\,\sqrt{\tilde{S}_{i}-N^{2}}\,\sqrt{\tilde{S}_{\Lambda}-N^{2}}}{\left(\tilde{S}_{h}+\tilde{S}_{i}+\tilde{S}_{\Lambda}-3N^{2}\right)+\sqrt{\tilde{S}_{h}-N^{2}}\,\sqrt{\tilde{S}_{i}-N^{2}}+\sqrt{\tilde{S}_{i}-N^{2}}\,\sqrt{\tilde{S}_{\Lambda}-N^{2}}+\sqrt{\tilde{S}_{h}-N^{2}}\,\sqrt{\tilde{S}_{\Lambda}-N^{2}}}$
(46)

This is the functional form of three physical horizon entropy in terms of NUT
parameter and cosmological constant. Of-course this is certainly a complicated
functional form. But it is never near as straight-forward relation like as
simple entropy products of Taub-NUT BH. If we could prefer it to be written in
terms of cosmological constant then the functional form becomes

$\displaystyle f(\tilde{S}_{h},\,\tilde{S}_{i},\,\tilde{S}_{\Lambda})$
$\displaystyle=$ $\displaystyle\frac{N^{2}\left(\Lambda
N^{2}-1\right)}{\left(1-2\Lambda N^{2}\right)}~{}$ (47)

###  2.3 Mass-Independent Relation in terms of two Physical Horizon Areas

So far, we have derived mass-independent entropy-functional relation in terms
three physical horizons. Now in this section for completeness we will derive
mass-independent entropy-functional relation in terms two physical horizons.
There are three possible situations. First by eliminating virtual horizon and
cosmological horizon. Second, by eliminating virtual horizon and Cauchy
horizon. And finally, by eliminating virtual horizon and event horizon.

First we will eliminate the virtual horizon and cosmological horizon. Then
using Viète’s theorem we would obtain following equations from exact quartic

$\displaystyle\left(r_{h}+r_{i}\right)^{2}-r_{h}\,r_{i}+\frac{3N^{2}(N^{2}-b^{2})}{r_{h}\,r_{i}}$
$\displaystyle=$ $\displaystyle 3(b^{2}-2N^{2})~{}$ (48)

and

$\displaystyle\left(r_{h}+r_{i}\right)\left[r_{h}\,r_{i}+\frac{3N^{2}(N^{2}-b^{2})}{r_{h}\,r_{i}}\right]$
$\displaystyle=$ $\displaystyle 6M\,b^{2}~{}$ (49)

Further solving, we can rewrite these equations

$\displaystyle r_{h}\,r_{i}$ $\displaystyle=$
$\displaystyle\frac{3N^{2}(N^{2}-b^{2})+r_{h}^{2}\,r_{i}^{2}}{3(b^{2}-2N^{2})-(r_{h}^{2}+r_{i}^{2})}~{}$
(50)

and

$\displaystyle r_{h}+r_{i}$ $\displaystyle=$
$\displaystyle\frac{6M\,b^{2}}{3(b^{2}-2N^{2})-\left(r_{h}^{2}+r_{i}^{2}\right)}~{}$
(51)

Now we will use these simple formulae to avoid the square root in entropy

$\displaystyle r_{h}^{2}+r_{i}^{2}$ $\displaystyle=$
$\displaystyle\left(r_{h}+r_{i}\right)^{2}-2r_{h}\,r_{i}~{}$ (52)

and

$\displaystyle r_{h}^{2}\,r_{i}^{2}=\left(r_{h}\,r_{i}\right)^{2}~{}$ (53)

In terms of entropy we found that

$\tilde{S}_{h}\,\tilde{S}_{i}\left(\tilde{S}_{h}^{2}+\tilde{S}_{i}^{2}+\tilde{S}_{h}\,\tilde{S}_{i}\right)=N^{2}\left(\tilde{S}_{h}+\tilde{S}_{i}\right)\left[\tilde{S}_{h}^{2}+\tilde{S}_{i}^{2}-8\tilde{S}_{h}\,\tilde{S}_{i}\right]+8N^{4}\left(\tilde{S}_{h}^{2}+\tilde{S}_{i}^{2}+\tilde{S}_{h}\,\tilde{S}_{i}\right)$
$\displaystyle+6b^{2}\left[\tilde{S}_{h}\,\tilde{S}_{i}\left(\tilde{S}_{h}+\tilde{S}_{i}\right)-N^{2}\left(\tilde{S}_{h}^{2}+\tilde{S}_{i}^{2}-\tilde{S}_{h}\,\tilde{S}_{i}\right)-2N^{4}\left(\tilde{S}_{h}+\tilde{S}_{i}\right)\right]$
$\displaystyle-9b^{4}\left[\tilde{S}_{h}\,\tilde{S}_{i}-N^{2}\left(\tilde{S}_{h}+\tilde{S}_{i}\right)\right]~{}$
(54)

This is strictly mass-independent. But it is some complicated function of two
physical horizons. It can also be written as

$\tilde{S}_{h}\,\tilde{S}_{i}\left(\tilde{S}_{h}^{2}+\tilde{S}_{i}^{2}+\tilde{S}_{h}\,\tilde{S}_{i}\right)=N^{2}\left(\tilde{S}_{h}+\tilde{S}_{i}\right)\left[\tilde{S}_{h}^{2}+\tilde{S}_{i}^{2}-8\tilde{S}_{h}\,\tilde{S}_{i}\right]+8N^{4}\left(\tilde{S}_{h}^{2}+\tilde{S}_{i}^{2}+\tilde{S}_{h}\,\tilde{S}_{i}\right)$
$\displaystyle+\frac{6}{\Lambda}\left[\tilde{S}_{h}\,\tilde{S}_{i}\left(\tilde{S}_{h}+\tilde{S}_{i}\right)-N^{2}\left(\tilde{S}_{h}^{2}+\tilde{S}_{i}^{2}-\tilde{S}_{h}\,\tilde{S}_{i}\right)-2N^{4}\left(\tilde{S}_{h}+\tilde{S}_{i}\right)\right]$
$\displaystyle-\frac{9}{\Lambda^{2}}\left[\tilde{S}_{h}\,\tilde{S}_{i}-N^{2}\left(\tilde{S}_{h}+\tilde{S}_{i}\right)\right]~{}$
(55)

When the cosmological constant is switched-off ($\Lambda\rightarrow 0$) one
obtains the standard result of Taub-NUT BH. When the NUT parameter is
switched-off ($N\rightarrow 0$) one obtains the mass-independent relation of
Kottler spacetime.

For completeness we also note that the _mass-dependent_ relation in terms of
two physical horizons entropy

$\left(\tilde{S}_{h}+\tilde{S}_{i}\right)\left[\left(\tilde{S}_{h}^{2}+\tilde{S}_{i}^{2}-4\tilde{S}_{h}\,\tilde{S}_{i}\right)+12N^{2}\left(\tilde{S}_{h}+\tilde{S}_{i}\right)+9b^{4}-24N^{4}\right]$
$\displaystyle-6b^{2}\left(\tilde{S}_{h}^{2}+\tilde{S}_{i}^{2}+\tilde{S}_{h}\,\tilde{S}_{i}\right)$
$\displaystyle=$ $\displaystyle 36b^{4}(M^{2}+N^{2})-72b^{2}N^{4}+32N^{6}~{}$
(56)

Whenever we take the new criterion defined in Eq. (6), one obtains _mass-
independent_ entropy functional relation in terms of two physical horizons

$N^{2}\left(\tilde{S}_{h}+\tilde{S}_{i}\right)\left[\left(\tilde{S}_{h}^{2}+\tilde{S}_{i}^{2}-4\tilde{S}_{h}\,\tilde{S}_{i}\right)+12N^{2}\left(\tilde{S}_{h}+\tilde{S}_{i}\right)+9b^{4}-24N^{4}\right]$
$\displaystyle-6b^{2}N^{2}\left(\tilde{S}_{h}^{2}+\tilde{S}_{i}^{2}+\tilde{S}_{h}\,\tilde{S}_{i}\right)$
$\displaystyle=$ $\displaystyle
36b^{4}J_{N}^{2}+4N^{4}\left(9b^{4}-18b^{2}N^{2}+8N^{4}\right)~{}$ (57)

Remarkably, this is _mass-independent_. It is possible only due to the
introduction of conserved charges $J_{N}$ which is quite analogues to the Kerr
like angular momentum $J=aM$. This is the _first_ time we obtain such type of
relation.

It may be rewritten as

$\displaystyle f(\tilde{S}_{h},\,\tilde{S}_{i})$ $\displaystyle=$
$\displaystyle\frac{36}{\Lambda^{2}}J_{N}^{2}+4N^{4}\left(\frac{9}{\Lambda^{2}}-\frac{18}{\Lambda}N^{2}+8N^{4}\right)~{}$
(58)

where

$f(\tilde{S}_{h},\,\tilde{S}_{i})=N^{2}\left(\tilde{S}_{h}+\tilde{S}_{i}\right)\left[\left(\tilde{S}_{h}^{2}+\tilde{S}_{i}^{2}-4\tilde{S}_{h}\,\tilde{S}_{i}\right)+12N^{2}\left(\tilde{S}_{h}+\tilde{S}_{i}\right)+\frac{9}{\Lambda^{2}}-24N^{4}\right]$
$\displaystyle-\frac{6}{\Lambda}N^{2}\left(\tilde{S}_{h}^{2}+\tilde{S}_{i}^{2}+\tilde{S}_{h}\,\tilde{S}_{i}\right).~{}$
(59)

Case II: When we would eliminate the virtual horizon and the Cauchy horizon
then we would obtain

$\left(\tilde{S}_{h}+\tilde{S}_{\Lambda}-2N^{2}\right)\left[\left(3b^{2}-2N^{2}\right)-\left(\tilde{S}_{h}+\tilde{S}_{\Lambda}-2N^{2}\right)\right]^{2}+$
$2\left[3N^{2}(N^{2}-b^{2})+(\tilde{S}_{h}-N^{2})(\tilde{S}_{\Lambda}-N^{2})\right]\times\left[3\left(b^{2}-2N^{2}\right)-\left(\tilde{S}_{h}+\tilde{S}_{\Lambda}-2N^{2}\right)\right]$
$\displaystyle=$ $\displaystyle 36M^{2}b^{4}.~{}$ (60)

More explicitly, it can be written as

$\left(\tilde{S}_{h}+\tilde{S}_{\Lambda}\right)\left[\left(\tilde{S}_{h}^{2}+\tilde{S}_{\Lambda}^{2}-4\tilde{S}_{h}\,\tilde{S}_{\Lambda}\right)+12N^{2}\left(\tilde{S}_{h}+\tilde{S}_{\Lambda}\right)+9b^{4}-24N^{4}\right]$
$\displaystyle-6b^{2}\left(\tilde{S}_{h}^{2}+\tilde{S}_{\Lambda}^{2}+\tilde{S}_{h}\,\tilde{S}_{\Lambda}\right)$
$\displaystyle=$ $\displaystyle
36b^{4}\,(M^{2}+N^{2})-72b^{2}\,N^{4}+32N^{6}.~{}$ (61)

Again this is certainly mass-dependent relation of some complicated function
of two physical horizons entropy. Remarkably, it turns out to be _mass-
independent_ when we have taken the input of Eq. (6). So, it could be written
as

$N^{2}\left(\tilde{S}_{h}+\tilde{S}_{\Lambda}\right)\left[\left(\tilde{S}_{h}^{2}+\tilde{S}_{\Lambda}^{2}-4\tilde{S}_{h}\,\tilde{S}_{\Lambda}\right)+12N^{2}\left(\tilde{S}_{h}+\tilde{S}_{\Lambda}\right)+9b^{4}-24N^{4}\right]$
$\displaystyle-6b^{2}\,N^{2}\left(\tilde{S}_{h}^{2}+\tilde{S}_{\Lambda}^{2}+\tilde{S}_{h}\,\tilde{S}_{\Lambda}\right)$
$\displaystyle=$ $\displaystyle
36\,b^{4}\,J_{N}^{2}+4N^{4}\left(9b^{4}-18b^{2}N^{2}+8N^{4}\right)~{}$ (62)

Another _mass-independent_ relation in terms of two physical horizons entropy
namely event horizon entropy and cosmological horizon entropy is

$\left(\tilde{S}_{h}-N^{2}\right)\left(\tilde{S}_{\Lambda}-N^{2}\right)\left[\left(3b^{2}-2N^{2}\right)-\left(\tilde{S}_{h}+\tilde{S}_{\Lambda}-2N^{2}\right)\right]^{2}$
$\displaystyle=$
$\displaystyle\left[3N^{2}(N^{2}-b^{2})+(\tilde{S}_{h}-N^{2})(\tilde{S}_{\Lambda}-N^{2})\right]^{2}.~{}$
(63)

More explicitly,

$\tilde{S}_{h}\,\tilde{S}_{\Lambda}\left(\tilde{S}_{h}^{2}+\tilde{S}_{\Lambda}^{2}+\tilde{S}_{h}\,\tilde{S}_{\Lambda}\right)=N^{2}\left(\tilde{S}_{h}+\tilde{S}_{\Lambda}\right)\left[\tilde{S}_{h}^{2}+\tilde{S}_{\Lambda}^{2}-8\tilde{S}_{h}\,\tilde{S}_{\Lambda}\right]+8N^{4}\left(\tilde{S}_{h}^{2}+\tilde{S}_{\Lambda}^{2}+\tilde{S}_{h}\,\tilde{S}_{\Lambda}\right)$
$\displaystyle+6b^{2}\left[\tilde{S}_{h}\,\tilde{S}_{\Lambda}\left(\tilde{S}_{h}+\tilde{S}_{\Lambda}\right)-N^{2}\left(\tilde{S}_{h}^{2}+\tilde{S}_{\Lambda}^{2}-\tilde{S}_{h}\,\tilde{S}_{\Lambda}\right)-2N^{4}\left(\tilde{S}_{h}+\tilde{S}_{\Lambda}\right)\right]$
$\displaystyle-9b^{4}\left[\tilde{S}_{h}\,\tilde{S}_{\Lambda}-N^{2}\left(\tilde{S}_{h}+\tilde{S}_{\Lambda}\right)\right].~{}$
(64)

Analoguosly, by eliminating virtual horizon and event horizon one could obtain
mass-independent relations in terms of cosmological horizon and Cauchy
horizon. Now we will turn to the AdS case.

##  3  Taub-NUT–anti-de Sitter BHs

Let us put in Eq. (10)

$\Lambda=-\frac{1}{|b|^{2}},$

then the relevent quartic equation will be

$\displaystyle
r^{4}+3\left(2N^{2}+|b|^{2}\right)r^{2}-6\,M\,r\,|b|^{2}-3\,N^{2}\,|b|^{2}-3\,N^{4}$
$\displaystyle=$ $\displaystyle 0~{}$ (65)

This quartic equation has four roots. Among four roots, two roots are complex
and two roots are real. Complex roots correspond to two virtual horizons,
$r_{V}^{\pm}$. These horizons are unphysical. While real roots correspond to
two physical horizons: an event (or outer) horizon $r_{h}$ and a Cauchy
horizon or inner horizon $r_{i}$.

###  3.1 Perturbative Results

Proceeding analogously to a first approximation for ${\cal H}^{+}$, we have

$\displaystyle r_{h}\approx
r_{+}-\frac{r_{+}^{4}}{3\left(|b|^{2}+2N^{2}\right)\left(r_{+}-r_{-}\right)}=r_{+}\left[1-\frac{r_{+}^{3}}{3\left(|b|^{2}+2N^{2}\right)\left(r_{+}-r_{-}\right)}\right].~{}$
(66)

Similarly, for ${\cal H}^{-}$ we find

$\displaystyle r_{i}\approx
r_{-}+\frac{r_{-}^{4}}{3\left(|b|^{2}+2N^{2}\right)\left(r_{+}-r_{-}\right)}=r_{-}\left[1+\frac{r_{-}^{3}}{3\left(|b|^{2}+2N^{2}\right)\left(r_{+}-r_{-}\right)}\right].~{}$
(67)

Resultantly,

$\displaystyle r_{h}\,r_{i}\approx
r_{+}\,r_{-}\left[1-\frac{r_{+}^{3}-r_{-}^{3}}{3\left(|b|^{2}+2N^{2}\right)\left(r_{+}-r_{-}\right)}\right].~{}$
(68)

and thus

$\displaystyle r_{h}\,r_{i}\approx
r_{+}\,r_{-}\left[1-\frac{r_{+}^{2}+r_{-}^{2}+r_{+}r_{-}}{3\left(|b|^{2}+2N^{2}\right)}\right].~{}$
(69)

Since

$\displaystyle
r_{+}^{2}+r_{-}^{2}+r_{+}r_{-}=\frac{4M^{2}}{\left(1+2\frac{N^{2}}{|b|^{2}}\right)^{2}}+\frac{N^{2}\left(\frac{N^{2}}{|b|^{2}}+1\right)}{\left(1+2\frac{N^{2}}{|b|^{2}}\right)}.~{}$
(70)

So,

$\displaystyle
r_{h}\,r_{i}\approx-\frac{N^{2}\left(\frac{N^{2}}{|b|^{2}}+1\right)}{\left(1+2\frac{N^{2}}{|b|^{2}}\right)}\left[1-\frac{\left\\{\frac{4M^{2}}{\left(1+2\frac{N^{2}}{|b|^{2}}\right)^{2}}+\frac{N^{2}\left(\frac{N^{2}}{|b|^{2}}+1\right)}{\left(1+2\frac{N^{2}}{|b|^{2}}\right)}\right\\}}{3|b|^{2}\left(1+2\frac{N^{2}}{|b|^{2}}\right)}\right].~{}$
(71)

If we have considered the case $\Lambda<0$ then we are in a situation where
the cosmological horizon does not exist but have asymptotically AdS spacetime.
Only two physical horizons ${\cal H}^{\pm}$ are exist. Therefore

$\displaystyle
r_{h}\,r_{i}\approx-\frac{N^{2}\left(|\Lambda|N^{2}+1\right)}{\left(1+2|\Lambda|N^{2}\right)}\left[1-\frac{|\Lambda|}{3}\frac{\left\\{\frac{4M^{2}}{\left(1+2|\Lambda|N^{2}\right)^{2}}+\frac{N^{2}\left(|\Lambda|N^{2}+1\right)}{\left(1+2|\Lambda|N^{2}\right)}\right\\}}{\left(1+2|\Lambda|N^{2}\right)}+\mathcal{O}(\Lambda^{2})\right].~{}$
(72)

This suggests that for _either_ sign of the cosmological constant one has

$\displaystyle r_{h}\,r_{i}\approx-\frac{N^{2}\left(\Lambda
N^{2}+1\right)}{\left(1+2\Lambda
N^{2}\right)}\left[1+\frac{\Lambda}{3}\frac{\left\\{\frac{4M^{2}}{\left(1+2\Lambda
N^{2}\right)^{2}}+\frac{N^{2}\left(\Lambda N^{2}+1\right)}{\left(1+2\Lambda
N^{2}\right)}\right\\}}{\left(1+2\Lambda
N^{2}\right)}+\mathcal{O}(\Lambda^{2})\right].~{}$ (73)

Note that it is evidently mass-dependent. But taking the cognizance of Eq.
(6), one obtains

$\displaystyle r_{h}\,r_{i}\approx-\frac{\left(\Lambda
N^{2}+1\right)}{\left(1+2\Lambda
N^{2}\right)}\left[N^{2}+\frac{\Lambda}{3}\frac{\left\\{\frac{4J_{N}^{2}}{\left(1+2\Lambda
N^{2}\right)^{2}}+\frac{N^{4}\left(\Lambda N^{2}+1\right)}{\left(1+2\Lambda
N^{2}\right)}\right\\}}{\left(1+2\Lambda
N^{2}\right)}+\mathcal{O}(\Lambda^{2})\right].~{}$ (74)

Now it is definitely _mass-independent_.

###  3.2 Exact Results

The exact results could be obtain by taking the combinations of various roots.
Using Viète’s theorem we have

$\displaystyle r_{h}+r_{i}+r_{V}^{+}+r_{V}^{-}$ $\displaystyle=$
$\displaystyle 0,$ (75) $\displaystyle
r_{h}\,r_{i}+\left(r_{h}+r_{i}\right)\left(r_{V}^{+}+r_{V}^{-}\right)+r_{V}^{+}\,r_{V}^{-}$
$\displaystyle=$ $\displaystyle 3\left(|b|^{2}+2N^{2}\right),$ (76)
$\displaystyle
r_{h}\,r_{i}\left(r_{V}^{+}+r_{V}^{-}\right)+r_{V}^{+}\,r_{V}^{-}\left(r_{h}+r_{i}\right)$
$\displaystyle=$ $\displaystyle 6M\,|b|^{2},$ (77) $\displaystyle
r_{h}\,r_{i}\,r_{V}^{+}\,r_{V}^{-}$ $\displaystyle=$
$\displaystyle-3\,N^{2}\left(|b|^{2}+N^{2}\right).~{}$ (78)

Since we have earlier mentioned that there exists two physical horizons thus
we are eliminating the virtual horizons due to the unphysical nature. So, we
obtain

$\displaystyle r_{h}\,r_{i}$ $\displaystyle=$
$\displaystyle-\frac{3N^{2}(N^{2}+|b|^{2})+r_{h}^{2}\,r_{i}^{2}}{3(|b|^{2}+2N^{2})+\left(r_{h}^{2}+r_{i}^{2}\right)}~{}$
(79)

and

$\displaystyle r_{h}+r_{i}$ $\displaystyle=$
$\displaystyle\frac{6M\,|b|^{2}}{3(|b|^{2}+2N^{2})+\left(r_{h}^{2}+r_{i}^{2}\right)}~{}$
(80)

As previously, to avoid the square root in entropy formula we have to use the
formulae of Eq. (52) and Eq. (53). So, in terms of area (or entropy) of two
physical horizons we found that mass-independent relation

$\left(\tilde{S}_{h}-N^{2}\right)\left(\tilde{S}_{i}-N^{2}\right)\left[3|b|^{2}+4N^{2}+\tilde{S}_{h}+\tilde{S}_{i}\right]^{2}$
$\displaystyle=$
$\displaystyle\left[3N^{2}(N^{2}+|b|^{2})+(\tilde{S}_{h}-N^{2})(\tilde{S}_{i}-N^{2})\right]^{2}.~{}$
(81)

Also we find another important equation

$\left(\tilde{S}_{h}+\tilde{S}_{i}-2N^{2}\right)\left[3|b|^{2}+4N^{2}+\tilde{S}_{h}+\tilde{S}_{i}\right]^{2}$
$-2\left[3N^{2}(N^{2}+|b|^{2})+(\tilde{S}_{h}-N^{2})(\tilde{S}_{i}-N^{2})\right]\left[3|b|^{2}+4N^{2}+\tilde{S}_{h}+\tilde{S}_{i}\right]$
$\displaystyle=$ $\displaystyle 36\,M^{2}|b|^{4}.~{}$ (82)

which is strictly mass-dependent. Taking cognizance of Eq. (6), we can make it
_mass-independent_.

$N^{2}\left(\tilde{S}_{h}+\tilde{S}_{i}-2N^{2}\right)\left[3|b|^{2}+4N^{2}+\tilde{S}_{h}+\tilde{S}_{i}\right]^{2}$
$-2N^{2}\left[3N^{2}(N^{2}+|b|^{2})+(\tilde{S}_{h}-N^{2})(\tilde{S}_{i}-N^{2})\right]\left[3|b|^{2}+4N^{2}+\tilde{S}_{h}+\tilde{S}_{i}\right]$
$\displaystyle=$ $\displaystyle 36\,J_{N}^{2}|b|^{4}.~{}$ (83)

This is in fact strictly _mass-independent_. This is possible only due to the
factor $J_{N}$, a new conserved charges in NUT class of geometry. All above
computations demonstrate that the entropy products for NUT class of BHs in AdS
space are _generic_ as well as _universal_.

##  4  Conclusions

It has been argued that a generic four dimensional Taub-NUT BH should be
completely described in terms of three or four different types of
thermodynamic hairs. They should be defined as the Komar mass ($M=m$), the
angular momentum ($J_{n}=mn$), the gravitomagnetic charge ($N=n$), the dual
(magnetic) mass $(\tilde{M}=n)$. Under these circumtances, we examined the
generic feature of area (or entropy) products of NUT class of BHs in AdS
space.

Particularly, we considered Taub-NUT-de Sitter BHs and Taub-NUT–anti-de Sitter
BHs. First, we calculated perturbatively the entropy products in terms of
event horizon and Cauchy horizon. We showed that the products have mass-
independent feature. Next we computed the entropy products in terms of three
physical horizons by direct method and proved that the functional form in
terms of three physical horizons is independent of the mass parameter but it
depends on only the NUT parameter and cosmological constant. Then we computed
the mass-independent relation in terms of two physical horizons.

The analysis that we perfomed in this work indicates the mass-independent
features of NUT class of BHs in AdS space are interestingly shown to be
_generic as well as universal_ which was earlier stated in the literature as
“mass-dependent” characteristics for Schwarzschild–de Sitter BH and
Schwarzschild-anti-de Sitter BH in $3+1$ dimensions. The mass-independent
feature or universality comes solely due to the presence of new global
conserved charges $J_{N}=MN$ which is closely analogue to the Kerr like
angular momentum $J=aM$.

Finally, the Visser’s conjectured “the mass-independence often fails once a
cosmological constant is added” is _violated_ in the present work. The generic
feature of area (or entropy) products that we have examined for NUT class of
BHs in AdS space has deep significance for further possible explanation of the
microscopic nature of BHs in ($3+1$) dimensions.

Recently, we defined a entropy product function (EPF) [37] for NUT class of
BHs and we found that there is an remarkable relation exist between the
central charges and the EPF as

$c=6\left(\frac{\partial{\cal F}}{\partial{\cal N}_{i}}\right)$

where ${\cal F}=\frac{{\cal S}_{h}{\cal S}_{i}}{4\pi^{2}}$ is EPF and ${\cal
N}_{i}$ is one of the integer valued charges i.e. the NUT charges ($N$) or any
new conserved charges ($J_{N}$). It would be an interesting topic of research
if we could answer that “Does it work for NUT class of BHs in AdS spacetime
like Eq. (25)?. Because the entropy product is mass independent for this case.
Thus from Eq. (25), we can easily compute the central charges for NUT picture,
$J_{N}$ picture and cosmological picture i.e. $\Lambda$ picture.

_Data Availability Statement:_
All datasets generated and analysed during this study are available in the
manuscript.

_Conflict of Interest Statement:_
The author here by declare that there is no conflict of interest

## References

  * [1] M. Visser, Area products for stationary black hole horizons, https://doi.org/10.1103/PhysRevD.88.044014 Phys. Rev. D 88, 044014 (2013)
  * [2] S. Wu and D. Wu, Thermodynamical hairs of the four-dimensional Taub-Newman-Unti-Tamburino spacetimes, https://doi.org/10.1103/PhysRevD.100.101501 Phys. Rev. D 100, 101501(R) (2019).
  * [3] S. Wu and D. Wu, Consistent mass formulas for the four-dimensional dyonic NUT-charged spacetimes, https://doi.org/10.1103/PhysRevD.105.124013 Phys. Rev. D 105, 124013 (2022).
  * [4] M. Ansorg and J. Hennig, The Inner Cauchy horizon of axisymmetric and stationary black holes with surrounding matter in Einstein-Maxwell theory, https://doi.org/10.1103/PhysRevLett.102.221102 Phys. Rev. Lett. 102, 221102 (2009).
  * [5] M. Cvetic, G. W. Gibbons and C. N. Pope, Universal Area Product Formulae for Rotating and Charged Black Holes in Four and Higher Dimensions, https://doi.org/10.1103/PhysRevLett.102.221102 Phys. Rev. Lett. 106, 121301 (2011).
  * [6] M. Cvetič, H. Lu, C. N. Pope., Entropy-product rules for charged rotating black holes, https://doi.org/10.1103/PhysRevD.88.044046 Phys. Rev. D 88, 044046 (2013).
  * [7] P. Pradhan, Thermodynamic product formula for Hořava-Lifshitz black hole, https://doi.org/10.1016/j.physletb.2015.05.054 Phys. Lett. B 747, 64 (2015).
  * [8] Xin-He Meng, Wei Xu and Jia Wang, A note on entropy relations of black hole horizons https://doi.org/10.1142/S0217751X14500882 International Journal of Mod. Phys. A 29, 1450088 (2014)
  * [9] P. Pradhan, Area (or entropy) products for Newman-Unti-Tamburino class of black holes, https://doi.org/10.1016/j.physletb.2020.135521 Phys. Lett. B 807, 135521 (2020).
  * [10] P, Pradhan, Energy formula for Newman-Unti-Tamburino class of black holes, https://doi.org/10.1007/s10714-021-02836-w Gen. Relativ. Gravit. 53, 69 (2021).
  * [11] P. Pradhan, Thermodynamic product formula for a Taub-NUT black hole, https://doi.org/10.1134/S1063776116010088 JETP 122, 113 (2016).
  * [12] A. H. Taub, Empty Space-Times Admitting a Three Parameter Group of Motions, https://doi.org/10.2307/1969567 Ann. of Maths. 53, 3 (1951).
  * [13] J. G. Miller, M. D. Kruskal and B. B. Godfrey, Taub-NUT (Newman-Unti-Tamburino) Metric and Incompatible Extensions, https://doi.org/10.1103/PhysRevD.4.2945 Phys. Rev. D 4, 2945 (1971).
  * [14] C. W. Misner, The Flatter regions of Newman, Unti and Tamburino’s generalized Schwarzschild space, https://doi.org/10.1063/1.1704019 J. Math. Phys. 4, 924 (1963).
  * [15] J. G. Miller, Global analysis of the Kerr-Taub-NUT metric, https://doi.org/10.1063/1.1666343 J. Math. Phys. (N.Y.) 14, 486 (1973).
  * [16] C. Chakraborty, S Bhattacharyya, Does the gravitomagnetic monopole exist? A clue from a black hole x-ray binary, https://doi.org/10.1103/PhysRevD.98.043021 Phys. Rev. D 98, 043021 (2018).
  * [17] C. Chakraborty, S Bhattacharyya, Circular orbits in Kerr-Taub-NUT spacetime and their implications for accreting black holes and naked singularities, https://doi.org/10.1088/1475-7516/2019/05/034 JCAP. 05, 034 (2019).
  * [18] J. M. Bardeen et al., The Four laws of black hole mechanics, https://doi.org/10.1007/BF01645742 Commun. Math. Phys. 31, 161 (1973).
  * [19] J. D. Bekenstein, Black holes and entropy, https://doi.org/10.1103/PhysRevD.7.2333 Phys. Rev. D 7, 2333 (1973).
  * [20] A. Strominger and C. Vafa, Microscopic origin of the Bekenstein-Hawking entropy, https://doi.org/10.1016/0370-2693(96)00345-0 Phys. Lett. B. 379, 99 (1996).
  * [21] M. Guica et al., The Kerr/CFT correspondence, https://doi.org/10.1103/PhysRevD.80.124008 Phys. Rev. D 80, 124008 (2009).
  * [22] A. Castro et al., Hidden conformal symmetry of the Kerr black hole, https://doi.org/10.1103/PhysRevD.82.024008 Phys. Rev. D 82, 024008 (2010).
  * [23] F. Larsen, A String model of black hole microstates, https://doi.org/10.1103/PhysRevD.56.1005 Phys. Rev. D 56, 1005 (1997).
  * [24] M. Cvetič and D. Youm, Entropy of nonextreme charged rotating black holes in string theory, https://doi.org/10.1103/PhysRevD.54.2612 Phys. Rev. D 54, 2612 (1996).
  * [25] M. Cvetič and F. Larsen, Greybody factors for rotating black holes in four dimensions, https://doi.org/10.1103/PhysRevD.57.6297 Nucl. Phys. B 506, 107 (1997).
  * [26] M. Cvetič and F. Larsen, General rotating black holes in string theory: Greybody factors and event horizons, https://doi.org/10.1103/PhysRevD.56.4994 Phys. Rev.  D 56, 4994 (1997).
  * [27] W. B. Bonor, A new interpretation of the NUT metric in general relativity, https://doi.org/10.1017/S0305004100044807 Math. Proc. of the Cambridge Physical Society, 66, 145 (1969).
  * [28] V. S. Manko and E. Ruiz, Physical interpretation of the NUT family of solutions, https://doi.org/10.1088/0264-9381/22/17/014 Classical Quantum Gravity 22, 3555 (2005).
  * [29] J. S. Dowker, The nut solution as a gravitational dyon, https://doi.org/10.1007/BF02451402 Gen. Relativ. Gravit. 5, 603 (1974).
  * [30] A. Ashtekar and A. Sen, NUT 4‐momenta are forever, https://doi.org/10.1063/1.525274 J. Math. Phys. (N.Y.) 23, 2168 (1982).
  * [31] C. J. Hunter, Action of instantons with a nut charge, https://doi.org/10.1103/PhysRevD.59.024009 Phys. Rev. D 59, 024009 (1998).
  * [32] S. W. Hawking and C. J. Hunter, Gravitational entropy and global structure, https://doi.org/10.1103/PhysRevD.59.044025 Phys. Rev. D 59, 044025 (1999).
  * [33] S. W. Hawking, C. J. Hunter, D. N. Page, NUT charge, anti-de Sitter space, and entropy, https://doi.org/10.1103/PhysRevD.59.044033 Phys. Rev. D 59, 044033 (1999).
  * [34] A. Chamblin et al., Large N phases, gravitational instantons and the nuts and bolts of AdS holography, https://doi.org/10.1103/PhysRevD.59.064010 Phys. Rev. D 59, 064010 (1999).
  * [35] R. Emparan et al. Surface terms as counterterms in the AdS/CFT correspondence, https://doi.org/10.1103/PhysRevD.60.104001 Phys. Rev. D 60, 104001 (1999).
  * [36] J. B. Griffiths, J. Podolský, Exact Space-Times in Einstein’s General Relativity, 2nd edition. https://doi.org/10.1017/CBO9780511635397 Cambridge UNiversity Press, (online ISBN-9780511635397) 2009.
  * [37] P. Pradhan,  Entropy product function and central charges in NUT geometry https://doi.org/ 10.1142/S0217751X23500902 Inter. Journal of Mod. Phys. A, 2350090 (2023)
  * [38] S. Chandrashekar, The Mathematical Theory of Black Holes, Clarendon Press, Oxford, 1983.


# Why Does Multi-Epoch Training Help?

Yi Xu, Qi Qian, Hao Li, Rong Jin
Machine Intelligence Technology, Alibaba Group
{yixu, qi.qian, lihao.lh<EMAIL_ADDRESS>
(First Version: )

###### Abstract

Stochastic gradient descent (SGD) has become the most attractive optimization
method in training large-scale deep neural networks due to its simplicity, low
computational cost in each updating step, and good performance. Standard
excess risk bounds show that SGD only needs to take one pass over the training
data and more passes could not help to improve the performance. Empirically,
it has been observed that SGD taking more than one pass over the training data
(multi-pass SGD) has much better excess risk bound performance than the SGD
only taking one pass over the training data (one-pass SGD). However, it is not
very clear that how to explain this phenomenon in theory. In this paper, we
provide some theoretical evidences for explaining why multiple passes over the
training data can help improve performance under certain circumstance.
Specifically, we consider smooth risk minimization problems whose objective
function is non-convex least squared loss. Under Polyak-Łojasiewicz (PL)
condition, we establish faster convergence rate of excess risk bound for
multi-pass SGD than that for one-pass SGD.

##  1 Introduction

We consider the following stochastic optimization problem in this work:

$\displaystyle\min_{\mathbf{w}\in\mathbb{R}^{d}}F_{\mathcal{S}}(\mathbf{w}):=\frac{1}{n}\sum_{i=1}^{n}\ell(\mathbf{w};\mathbf{z}_{i}),$
(1)

where $\mathbf{w}$ is the model parameters,
$\mathcal{S}=\\{\mathbf{z}_{1},\dots,\mathbf{z}_{n}\\}$ is a set of training
examples sampled from a distribution $\mathcal{P}$ with support on
$\mathcal{Z}$, and
$\ell(\mathbf{w};\mathbf{z}):\mathbb{R}^{d}\times\mathcal{Z}\longrightarrow\mathbb{R}_{+}$
is a non-negative smooth loss function. Problem (1) arises in most machine
learning based optimization problems such as standard empirical risk
minimization (ERM) and deep learning.

Although tremendous stochastic algorithms have been proposed to solving
problem (1), stochastic gradient descent (SGD) (Robbins and Monro, 1951) is
probably the simplest and has emerged as one of the most popular techniques.
Specifically, at each training iteration $t$, SGD randomly samples an example
$\mathbf{z}_{i_{t}}$ and then it updates solutions iteratively by

$\displaystyle\mathbf{w}_{t+1}=\mathbf{w}_{t}-\eta_{t}\mathbf{g}_{t},$ (2)

where
$\mathbf{g}_{t}:=\nabla_{\mathbf{w}}\ell(\mathbf{w}_{t};\mathbf{z}_{i_{t}})$
is the stochastic gradient of objective function at $\mathbf{w}_{t}$, $i_{t}$
is uniformly sampled from $[n]$, $\eta_{t}>0$ is a learning rate. Theoretical
convergences of SGD and its variants from an optimization viewpoint have been
extensively studied under different conditions of the objection function
(Nemirovski et al., 2009; Ghadimi and Lan, 2013; Karimi et al., 2016; Xu et
al., 2017). In real applications such as training deep neural networks, we are
more interested in whether the learned model can generalize well and result in
the least excess risk (Vapnik, 2013; Bottou and Bousquet, 2007)? This
introduces us another direction of research, which is the generalization of
SGD. That is to say, we want to test the performance of the output of SGD by
solving problem (1) on the following expected risk minimization (a.k.a.
population risk minimization)

$\displaystyle\min_{\mathbf{w}\in\mathbb{R}^{d}}F(\mathbf{w}):=\mathrm{E}_{\mathbf{z}\sim\mathcal{P}}[\ell(\mathbf{w};\mathbf{z})].$
(3)

In this work, we consider the excess risk as the performance measurement

$\displaystyle F(\widehat{\mathbf{w}})-F(\mathbf{w}_{*}),$ (4)

where
$\mathbf{w}_{*}\in\operatorname*{arg\,min}_{\mathbf{w}\in\mathbb{R}^{d}}F(\mathbf{w})$
is the optimal solution, $\widehat{\mathbf{w}}$ is the output of SGD for
solving problem (1). The upper bound of excess risk (4) is known as excess
risk bound, which has been extensively studied in the literature. In the
seminal paper by Hardt et al. (2016), the authors establish standard excess
risk bound $O(1/\sqrt{n})$ under the convex optimization setting, then Zhou et
al. (2018) extend the result of excess risk bound $O(1/\sqrt{n})$ to non-
convex optimization setting. With different assumptions such as strongly
convex, Polyak-Łojasiewicz (PL) (Polyak, 1963) and the quadratic growth (QG)
conditions, many works (e.g., (Charles and Papailiopoulos, 2018; Kuzborskij
and Lampert, 2018; Yuan et al., 2019; Lei and Ying, 2020, 2021)) achieve fast
rate of excess risk bound $O(1/n)$. One interesting observation from the
theoretical side is that SGD only needs to take $O(n)$ stochastic gradient
evaluations to get this fast rate $O(1/n)$, meaning that one-pass SGD can
achieve the fast rate under some assumptions on the objective function.
However, in practice like training neural networks (He et al., 2019),
continuing running SGD after first epoch can still reduce the testing error,
which makes multi-pass SGD more powerful than one-pass SGD. Several works have
been studied the generalization of multi-pass SGD and fast rates are
established under different conditions (Rosasco and Villa, 2015; Lin et al.,
2016; Lin and Rosasco, 2017; Pillaud-Vivien et al., ; Feldman and Vondrak,
2019; Lei et al., 2021). In general, existing fast rates are established in
the convex optimization setting and they are not better than the rate of
$O(1/n)$. It not fully explains the phenomenon observed in practice for deep
learning that continuing training SGD for more epochs can still improve the
performances on testing data. In this work, we aim to theoretically understand
the observation and try to answer the following question:

Why multiple epochs can help improve the generalization performances?

To answer this question, we will establish a faster excess risk bound for non-
convex SGD. When the objective function is smooth and satisfies PL condition,
we will show that SGD can achieve the excess risk bound
$\widetilde{O}(1/n^{2})$ by continuing conducting SGD after the first epoch.
This reveals that multi-pass on training data when using SGD for training deep
learning would help to improve the performance on testing data. It is worth
mentioning that beyond using SGD, many existing works provide faster rates of
excess risk bound under different convex settings (Zhang et al., 2017; Liu et
al., 2018; Ye et al., 2019). Their excess risk bounds are constructed for the
optimal solution of (1) and they did not consider an efficient optimization
algorithm such as SGD for solving their formulation. By contrast, we focus on
the excess risk bound for non-convex SGD in this work.

##  2 Preliminaries and Notations

Let the pair of input $\mathbf{x}\in\mathcal{X}$ and label $y\in\mathcal{Y}$
follows a distribution $\mathcal{P}$:
$\mathbf{z}=(\mathbf{x},y)\sim\mathcal{P}$. Let denote by
$f(\mathbf{w};\mathbf{x}):\mathbb{R}^{d}\times\mathcal{X}\to\mathcal{Y}$ the
prediction function parameterized by $\mathbf{w}\in\mathbb{R}^{d}$, and we
want it is as close as possible to label $y$. Based on the given data set
$\mathcal{S}=\\{\mathbf{z}_{1},\dots,\mathbf{z}_{n}\\}$ that is sampled from
the distribution $\mathcal{P}$, we are interested in solving the empirical
risk minimization problem (1). Following by (Allen-Zhu et al., 2019), we
consider non-convex squared loss in this work, whose function is given by

$\displaystyle\ell(\mathbf{w};\mathbf{z}):=\frac{1}{2}(f(\mathbf{w};\mathbf{x})-y)^{2}.$
(5)

Since the non-convexity of $f(\mathbf{w};\mathbf{x})$, the loss function
$\ell(\mathbf{w};\mathbf{z})$ is non-convex.

Let denote by $\nabla F(\mathbf{w})$ the gradient of a function
$F(\mathbf{w})$. We use $\|\cdot\|$ to denote the Euclidean norm and use
$\langle\cdot,\cdot\rangle$ to denote the inner product. Let
$\mathrm{E}_{\mathbf{z}}[\cdot]$ be the expectation taking over random
variable $\mathbf{z}$.

Next, we present some assumptions that will be used in the convergence
analysis in this work. Specifically, we make the following assumptions for the
loss function.

######  Assumption 1.

Assume the following conditions hold:

  * (i)

The stochastic gradient of $F(\mathbf{w})$ is unbiased, i.e.,
$\mathrm{E}_{\mathbf{z}}[\nabla\ell(\mathbf{w};\mathbf{z})]=\nabla
F(\mathbf{w})$, and the variance of stochastic gradient is bounded.
Specifically, theres exists two constants $B>0$ and $G>0$, such that

$|y|+|f(\mathbf{w};\mathbf{x})|\leq B,\quad\|\nabla
f(\mathbf{w};\mathbf{x})\|\leq G.$

  * (ii)

$F(\mathbf{w})$ is smooth with an $L$-Lipchitz continuous gradient, i.e., it
is differentiable and there exists a constant $L>0$ such that

$\|\nabla F(\mathbf{w})-\nabla F(\mathbf{u})\|\leq
L\|\mathbf{w}-\mathbf{u}\|,\forall\mathbf{w},\mathbf{u}\in\mathbb{R}^{d}.$

Assumption 1 (i) and (ii) are commonly used assumptions in the literature
(Ghadimi and Lan, 2013; Rosasco and Villa, 2015; Lin et al., 2016; Lin and
Rosasco, 2017; Pillaud-Vivien et al., ; Yuan et al., 2019). Assumption 1 (i)
assures that the stochastic gradient is bounded, i.e.,
$\|\nabla\ell(\mathbf{w};\mathbf{z})\|\leq GB$. Thus, by Jensen’s inequality
we have
$\mathrm{E}_{\mathbf{z}}\left[\left\|\nabla\ell(\mathbf{w};\mathbf{z})-\nabla
F(\mathbf{w})\right\|^{2}\right]\leq\sigma^{2}$, where
$\sigma^{2}:=4G^{2}B^{2}$. Assumption 1 (ii) says the objective function is
$L$-smooth, and it has an equivalent expression (Nesterov, 2004) which is

$F(\mathbf{w})-F(\mathbf{u})\leq\langle\nabla
F(\mathbf{u}),\mathbf{w}-\mathbf{u}\rangle+\frac{L}{2}\|\mathbf{w}-\mathbf{u}\|^{2},\forall\mathbf{w},\mathbf{u}\in\mathbb{R}^{d}.$

We then introduce two functional properties as follows.

######  Definition 1 (Strongly convex).

We say $F(\mathbf{w})$ is strongly convex, if there exists a constant
$\gamma>0$ such that $F(\mathbf{w})-F(\mathbf{u})\geq\langle\nabla
F(\mathbf{u}),\mathbf{w}-\mathbf{u}\rangle+\frac{\gamma}{2}\|\mathbf{w}-\mathbf{u}\|^{2},\forall\mathbf{w},\mathbf{u}\in\mathbb{R}^{d}.$

######  Definition 2 (Polyak-Łojasiewicz (PL) condition).

There exists a constant $\mu>0$ such that
$2\mu(F(\mathbf{w})-F_{*})\leq\|\nabla
F(\mathbf{w})\|^{2},\forall\mathbf{w}\in\mathbb{R}^{d}$, where
$F_{*}=\min_{\mathbf{w}\in\mathbb{R}^{d}}F(\mathbf{w})$ is the optimal value.

The PL condition has been theoretically and empirically observed in training
deep neural networks (Allen-Zhu et al., 2019; Yuan et al., 2019). This
condition is widely used to establish convergence in the literature of non-
convex optimization, please see (Yuan et al., 2019; Karimi et al., 2016; Li
and Li, 2018; Charles and Papailiopoulos, 2018) and references therein.

##  3 Main Results

We will present the main theoretical results in this section. The analyses
contain two parts. First, we focus on the optimization of the first epoch.
Note that in the first epoch, it satisfies the condition of statistical
independence and therefore we can apply the standard analysis of stochastic
gradient descent. Second, we consider the updates after the first epoch. In
our analysis, we set $F(\mathbf{w}_{*})=0$ without loss of generality, a
common property observed in training deep neural networks (Zhang et al., 2016;
Allen-Zhu et al., 2019; Du et al., 2018, 2019; Arora et al., 2019; Chizat et
al., 2019; Hastie et al., 2019; Yun et al., 2019; Zou et al., 2020).

First, we will show that under the PL-condition in Definition 2, if we use a
uniformly sampling without replacement, one-pass SGD has the excess risk bound
of $\widetilde{O}(1/n)$. We present the results in the following theorem.

######  Theorem 1 (First Epoch).

Suppose the objective function $F$ satisfies Assumption 1 and the PL-condition
in Definition 2, if the learning rate is set to be $\eta=\frac{1}{\mu
n}\log\left(\frac{n\mu^{2}F(\mathbf{w}_{0})}{\sigma^{2}L}\right)$ in SGD, then
we have

$\displaystyle\mathrm{E}[F(\mathbf{w}_{n})]\leq
O\left(\frac{\sigma^{2}L\log(n)}{\mu^{2}n}\right).$ (6)

Next, let’s examine the late stage of the optimization beyond the first epoch,
in which we do not have the statistical independence between the model to be
updated and the training data. As a result, our objective function “becomes”
$F_{\mathcal{S}}(\mathbf{w})$. For any iteration $t$ after first epoch (we
denote by $\mathbf{w}_{1}$ the solution obtained from the first epoch), define

$\displaystyle\Omega(\widehat{r}_{t},s)=\left\\{\mathbf{w}:\frac{1}{n}\sum_{i=1}^{n}\left(f(\mathbf{w};\mathbf{x}_{i})-y_{i}\right)^{2}\leq\widehat{r}_{t}^{2},\quad\frac{1}{n}\sum_{i=1}^{n}\left|f(\mathbf{w};\mathbf{x}_{i})-y_{i}\right|\leq\sqrt{s_{t}}\right\\}$
(7)

where

$\displaystyle\widehat{r}_{t}^{2}:=\frac{1}{n}\sum_{i=1}^{n}\left(f(\mathbf{w}_{t};\mathbf{x}_{i})-y_{i}\right)^{2},\quad\sqrt{s_{t}}:=\sqrt{\frac{s}{n}}\widehat{r}_{t}.$
(8)

We assume that $s\ll n$, implying that vector
$(f(\mathbf{w}_{t};\mathbf{x}_{1})-y_{1},\ldots,f(\mathbf{w}_{t};\mathbf{x}_{n})-y_{n})$
is a sparse vector. This sparse assumption can be relaxed when the objective
function has an additional property – strongly convex. In such setting,
strongly convex can be considered as a special case of PL condition (see the
Proof of Theorem 4 in Appendix). For completeness, we include the analysis and
convergence results for strongly convex case in Appendix.

We give the following results of bounding the variances of the stochastic
gradients, which is the key to the analyses.

######  Theorem 2.

Under the assumption $n\geq 64B^{2}\log(2/\delta)$, we have, with a
probability $1-3\delta$,

$\displaystyle\max\limits_{\mathbf{w}\in\Omega(\widehat{r},s)}\|\nabla
F(\mathbf{w})-\nabla F_{\mathcal{S}}(\mathbf{w})\|\leq
C\left(\frac{GB\log(1/\delta)}{n}+G\widehat{r}\left[\sqrt{\frac{\log(1/\delta)}{n}}+\sqrt{\frac{s}{n}\log\frac{2m}{s}}\left(1+\log
n\right)\right]\right),$ (9)

where $C$ is a universal constant.

Now, we are ready to give the main convergence result for the epochs after the
first one.

######  Theorem 3 (After First Epoch).

Suppose the objective function $F$ satisfies Assumption 1 and the PL-condition
in Definition 2, if
$n\geq\frac{6C^{2}G^{2}}{\mu}\left[\log(1/\delta)+s\log\left(\frac{2n}{s}\right)\left(1+\log
n\right)^{2}\right]$, by setting $t=\frac{2}{\eta\mu}\log\left(\frac{\mu
F(\mathbf{w}_{1})}{\eta G^{2}B^{2}L}\right)$ and
$\eta=\min\left(\frac{1}{n^{2}},\frac{1}{L}\right)$, then with probability at
least $1-\delta$ we have

$\displaystyle F(\mathbf{w}_{t+n})\leq$
$\displaystyle\frac{3C^{2}G^{2}B^{2}\log^{2}\left(\frac{2}{\eta\mu\delta}\log\left(\frac{\mu
F(\mathbf{w}_{1})}{\eta G^{2}B^{2}L}\right)\right)}{n^{2}\mu}+\frac{2\eta
G^{2}B^{2}L}{\mu}\leq\widetilde{O}\left(\frac{1}{n^{2}}\right).$ (10)

Remark. Based on Theorem 3, we know the excess risk bound is
$\widetilde{O}(1/n^{2})$ if SGD takes $n$ passes over the training data whose
sample size is $n$. In particular, the excess risk bound is in the order of
$\widetilde{O}\left(1/n^{2}+\eta\right)$ when $t=\widetilde{O}(1/\eta)$, that
is, if SGD continutes running $\widetilde{O}(1/\eta)\leq n^{2}$ iterations,
the excess risk bound is $\widetilde{O}\left(\eta\right)$. However, after
$O(n^{2})$ iterations ($O(n)$ epochs), the excess risk bound can not be
further improved even SGD runs more epochs.

##  4 Proofs

In this section, we provide the proofs of theorems in Section 3.

###  4.1 Proof of Theorem 1

We first focus on the optimization of the first epoch. Note that in the first
epoch, it satisfies the condition of statistical independence and therefore we
can apply the standard analysis of stochastic gradient descent. Then, for each
iteration $t$, we have

$\displaystyle\mathrm{E}[F(\mathbf{w}_{t+1})-F(\mathbf{w}_{t})]$
$\displaystyle\overset{(a)}{\leq}$ $\displaystyle\mathrm{E}[\langle\nabla
F(\mathbf{w}_{t}),\mathbf{w}_{t+1}-\mathbf{w}_{t}\rangle]+\frac{L}{2}\mathrm{E}[\|\mathbf{w}_{t+1}-\mathbf{u}_{t}\|^{2}]$
$\displaystyle\overset{(b)}{\leq}$ $\displaystyle-\eta\left(1-\frac{\eta
L}{2}\right)\mathrm{E}[\|\nabla
F(\mathbf{w}_{t})\|^{2}]+\frac{\eta^{2}\sigma^{2}L}{2}$
$\displaystyle\overset{(c)}{\leq}$
$\displaystyle-\eta\mu\mathrm{E}[F(\mathbf{w}_{t})-F_{*}]+\frac{\eta^{2}\sigma^{2}L}{2},$
(11)

where (a) uses the smoothness of $F(\mathbf{w})$ in Assumption 1 (ii); (b)
uses $\mathbf{w}_{t+1}=\mathbf{w}_{t}-\eta\mathbf{g}_{t}$, and
$\mathrm{E}[\mathbf{g}_{t}]=\nabla F(\mathbf{w}_{t})$ by the unbiased property
of $\nabla\ell(\mathbf{w};\mathbf{z})$ in Assumption 1 (i), and
$\mathrm{E}[\|F(\mathbf{w}_{t})-\mathbf{g}_{t}\|^{2}]\leq\sigma^{2}$ in
Assumption 1 (ii); (c) uses $\eta L\leq 1$ and the PL-condition in Definition
2. Therefore, we have

$\displaystyle\mathrm{E}[F(\mathbf{w}_{n})-F_{*}]\leq\exp(-\eta\mu
n)F(\mathbf{w}_{0})+\frac{\eta\sigma^{2}L}{2\mu}\leq
O\left(\frac{\sigma^{2}L\log(n)}{\mu^{2}n}\right),$ (12)

where the last inequality is due to the setting of $\eta=\frac{1}{\mu
n}\log\left(\frac{n\mu^{2}F(\mathbf{w}_{0})}{\sigma^{2}L}\right)$. We complete
the proof by using the fact that $F_{*}=0$.

###  4.2 Proof of Theorem 2

In this proof, we consider the case of iteration $t+1$ conditional on
iteration $t$, then for simplicity, we omit the subscript $t$. Since we have

$\max_{\mathbf{w}\in\Omega(\widehat{r},s)}\|\nabla F(\mathbf{w})-\nabla
F_{\mathcal{S}}(\mathbf{w})\|=\max_{\mathbf{w}\in\Omega(\widehat{r},s)}\left\|\frac{1}{n}\sum_{i=1}^{n}(f(\mathbf{w};\mathbf{x}_{i})-y_{i})\nabla
f(\mathbf{w};\mathbf{x}_{i})-\nabla F(\mathbf{w})\right\|,$

using the Bousquet inequality (Koltchinskii, 2011), with appropriate
definition of the function space, we have, with a probability $1-\delta$

$\displaystyle\max\limits_{\mathbf{w}\in\Omega(\widehat{r},s)}\left\|\frac{1}{nG}\sum_{i=1}^{n}(f(\mathbf{w};\mathbf{x}_{i})-y_{i})\nabla
f(\mathbf{w};\mathbf{x}_{i})-\nabla F(\mathbf{w})\right\|$ $\displaystyle\leq$
$\displaystyle
2\mathrm{E}\left[\max\limits_{\mathbf{w}\in\Omega(\widehat{r},s)}\left\|\frac{1}{nG}\sum_{i=1}^{n}(f(\mathbf{w};\mathbf{x}_{i})-y_{i})\nabla_{k}f(\mathbf{w};\mathbf{x}_{i})-\nabla_{k}F(\mathbf{w})\right\|\right]+\frac{4B\log(1/\delta)}{3n}+\sqrt{\frac{2\sigma_{P}^{2}}{n}\log\frac{1}{\delta}}$

where
$\sigma_{P}^{2}\leq\frac{1}{G^{2}}\max\limits_{\mathbf{w}\in\Omega(\widehat{r},s)}\mathrm{E}\left[(f(\mathbf{w};\mathbf{x}_{i})-y_{i})^{2}\|\nabla
f(\mathbf{w};\mathbf{x}_{i})\|^{2}\right]\leq\max\limits_{\mathbf{w}\in\Omega(\widehat{r},s)}\mathrm{E}\left[(f(\mathbf{w};\mathbf{x}_{i})-y)^{2}\right]\leq
r^{2}$ with the Assumption 1 that $\|\nabla f(\mathbf{w};\mathbf{x})\|\leq G$.
Using the Berstein inequality, we have, with a probability $1-\delta$,

$\widehat{r}^{2}\geq
r^{2}-\frac{2B^{2}}{3n}\log\frac{2}{\delta}-2B\sqrt{\frac{\widehat{r}^{2}}{n}\log\frac{2}{\delta}}$

Using the assumption that $m\geq 64B^{2}\log(2/\delta)$, we have, with a
probability $1-\delta$

$r^{2}\leq 2\widehat{r}^{2}+\frac{4B^{2}}{3n}\log\frac{2}{\delta},$

and therefore

$\sigma_{P}^{2}\leq 2\widehat{r}^{2}+\frac{4B^{2}}{3n}\log\frac{2}{\delta}.$

As a result, with a probability $1-2\delta$, we have

$\displaystyle\max\limits_{\mathbf{w}\in\Omega(\widehat{r},s)}\left\|\frac{1}{nG}\sum_{i=1}^{n}(f(\mathbf{w};\mathbf{x}_{i})-y_{i})\nabla
f(\mathbf{w};\mathbf{x}_{i})-\nabla F(\mathbf{w})\right\|$ $\displaystyle\leq$
$\displaystyle
2\mathrm{E}\left[\max\limits_{\mathbf{w}\in\Omega(\widehat{r},s)}\left\|\frac{1}{nG}\sum_{i=1}^{n}(f(\mathbf{w};\mathbf{x}_{i})-y_{i})\nabla_{k}f(\mathbf{w};\mathbf{x}_{i})-\nabla_{k}F(\mathbf{w})\right\|\right]+\frac{3B}{n}\log\frac{1}{\delta}+2\widehat{r}\sqrt{\frac{2\log(1/\delta)}{n}}$
$\displaystyle\leq$ $\displaystyle
4\mathrm{E}_{x,\sigma}\left[\max\limits_{\mathbf{w}\in\Omega(\widehat{r},s)}\left\|\frac{1}{nG}\sum_{i=1}^{n}\sigma_{i}(f(\mathbf{w};\mathbf{x}_{i})-y_{i})\nabla
f(\mathbf{w};\mathbf{x}_{i})\right\|\right]+\frac{4B\log(1/\delta)}{n}+2\widehat{r}\sqrt{\frac{2\log(1/\delta)}{n}}.$

We then bound $\mathrm{E}_{x,\sigma}[\cdot]$. Using Klei-Rio bound
(Koltchinskii, 2011), with a probability $1-2\delta$, we have

$\displaystyle\mathrm{E}_{x,\sigma}\left[\max\limits_{\mathbf{w}\in\Omega(\widehat{r},s)}\left\|\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}(f(\mathbf{w};\mathbf{x}_{i})-y_{i})\nabla
f(\mathbf{w};\mathbf{x}_{i})\right\|\right]$ $\displaystyle\leq$
$\displaystyle
2\mathrm{E}_{\sigma}\left[\max\limits_{\mathbf{w}\in\Omega(\widehat{r},s)}\left\|\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}(f(\mathbf{w};\mathbf{x}_{i})-y_{i})\nabla
f(\mathbf{w};\mathbf{x}_{i})\right\|\right]+2\widehat{r}\sqrt{\frac{\log(1/\delta)}{n}}+\frac{9B}{n}\log\frac{1}{\delta}$

We can bound the expectation term using Dudley entropy bound (Lemma A.5 of
(Bartlett et al., 2017)),i.e.

$\displaystyle\mathrm{E}_{\sigma}\left[\max\limits_{\mathbf{w}\in\Omega(\widehat{r},s)}\left\|\frac{1}{nGB}\sum_{i=1}^{n}\sigma_{i}(f(\mathbf{w};\mathbf{x}_{i})-y_{i})\nabla
f(\mathbf{w};\mathbf{x}_{i})\right\|\right]$ $\displaystyle\leq$
$\displaystyle\mathrm{E}_{\sigma}\left[\max\limits_{\mathbf{w}\in\Omega(\widehat{r},s),h\in
S_{d}}\left\|\frac{1}{nGB}\sum_{i=1}^{n}\sigma_{i}(f(\mathbf{w};\mathbf{x}_{i})-y_{i})\langle\nabla
f(\mathbf{w};\mathbf{x}_{i}),h\rangle\right\|\right]$ $\displaystyle\leq$
$\displaystyle\inf\limits_{\alpha}\left(\frac{4\alpha}{\sqrt{n}}+\frac{12}{n}\int_{\alpha}^{\sqrt{n}}\sqrt{\log\mathcal{N}(\mathcal{G}(\widehat{r},s);\epsilon)}d\epsilon\right)$
(13)

where $\mathcal{N}(\mathcal{G}(\widehat{r},s);\epsilon)$ is the covering
number of proper $\epsilon$-net over $\mathcal{G}(\widehat{r},s)$ and $S_{d}$
is a simplex set. Here $\mathcal{G}(\widehat{r},s)$ is defined as

$\mathcal{G}(\widehat{r},s)=\left\\{v\in\mathbb{R}^{n}:\|v\|\leq\frac{\sqrt{n}\widehat{r}}{B},\|v\|_{1}\leq\frac{\sqrt{ns}\widehat{r}}{B}\right\\}$

Using the covering number result for sparse vectors (Lemma 3.4 of (Plan and
Vershynin, 2013)), we have

$\log\mathcal{N}\left(\mathcal{G}(\widehat{r},s);\frac{\sqrt{n}\widehat{r}}{B}\epsilon\right)\leq\frac{Cs}{\epsilon^{2}}\log\frac{2n}{s}$

and therefore

$\log\mathcal{N}\left(\mathcal{G}(\widehat{r},s);\epsilon\right)\leq\frac{Cn\widehat{r}^{2}s}{B^{2}\epsilon^{2}}\log\frac{2n}{s}$

Plugging into the Dudley entropy bound, we have

$\mathrm{E}_{\sigma}\left[\max\limits_{\mathbf{w}\in\Omega(\widehat{r},s)}\left\|\frac{1}{nB}\sum_{i=1}^{n}\sigma_{i}(f(\mathbf{w};\mathbf{x}_{i})-y_{i})\right\|\right]\leq\inf\limits_{\alpha}\left(\frac{4\alpha}{\sqrt{n}}+\frac{12\widehat{r}}{B}\sqrt{\frac{Cs}{n}\log\frac{2n}{s}}\log\frac{\sqrt{n}}{\alpha}\right)$

By choosing $\alpha$ as

$\alpha=\frac{3\widehat{r}}{B}\sqrt{Cs\log\frac{2n}{s}},$

we have

$\mathrm{E}_{\sigma}\left[\max\limits_{\mathbf{w}\in\Omega(\widehat{r},s)}\left\|\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}(f(\mathbf{w};\mathbf{x}_{i})-y_{i})\right\|\right]\leq
12\widehat{r}\sqrt{\frac{Cs}{n}\log\frac{2n}{s}}\left(1+\frac{1}{2}\log\left(\frac{n}{9\sqrt{Cs\log(2n/s)}}\right)\right)$

Combining the above results together, with a probability $1-3\delta$, we prove
the inequality (9).

###  4.3 Proof of Theorem 3

In this proof, we consider the updates after first epoch, i.e., $t\geq n$.

$\displaystyle F(\mathbf{w}_{t+1})-F(\mathbf{w}_{t})$
$\displaystyle\overset{(a)}{\leq}$ $\displaystyle\langle\nabla
F(\mathbf{w}_{t}),\mathbf{w}_{t+1}-\mathbf{w}_{t}\rangle+\frac{L}{2}\|\mathbf{w}_{t+1}-\mathbf{w}_{t}\|^{2}$
$\displaystyle\overset{(b)}{=}$ $\displaystyle-\eta\langle\nabla
F(\mathbf{w}_{t}),\nabla\ell(\mathbf{w}_{t};\mathbf{z}_{i_{t}})\rangle+\frac{\eta^{2}L}{2}\|\nabla\ell(\mathbf{w}_{t};\mathbf{z}_{i_{t}})\|^{2}$
$\displaystyle\overset{(c)}{\leq}$ $\displaystyle-\eta\langle\nabla
F(\mathbf{w}_{t}),\nabla\ell(\mathbf{w}_{t};\mathbf{z}_{i_{t}})\rangle+\frac{\eta^{2}LG^{2}B^{2}}{2},$
(14)

where (a) uses the smoothness of $F(\mathbf{w})$ in Assumption 1 (ii); (b)
uses $\mathbf{w}_{t+1}=\mathbf{w}_{t}-\eta\mathbf{g}_{t}$; (c) uses Assumption
1 (i) that $\|\mathbf{g}_{t}\|\leq GB$. By summing the above inequalities
across $i_{t}=1,\dots,n$ and dividing by $n$, we get

$\displaystyle F(\mathbf{w}_{t+1})-F(\mathbf{w}_{t})$ $\displaystyle\leq$
$\displaystyle-\eta\langle\nabla F(\mathbf{w}_{t}),\nabla
F_{\mathcal{S}}(\mathbf{w}_{t}))\rangle+\frac{\eta^{2}LG^{2}B^{2}}{2},$
$\displaystyle\leq$ $\displaystyle\frac{\eta}{2}\left\|\nabla
F(\mathbf{w}_{t})-\nabla
F_{\mathcal{S}}(\mathbf{w}_{t})\right\|^{2}-\frac{\eta}{2}\left\|\nabla
F(\mathbf{w}_{t})\right\|^{2}+\frac{\eta^{2}LG^{2}B^{2}}{2}$
$\displaystyle\leq$ $\displaystyle\frac{\eta M_{t}}{2}-\eta\mu
F(\mathbf{w}_{t})+\frac{\eta^{2}LG^{2}B^{2}}{2},$ (15)

where the last inequality uses PL-condition and Theorem 2 with

$\displaystyle M_{t}:=$ $\displaystyle
C^{2}\left(\frac{GB\log(1/\delta)}{n}+G\widehat{r}_{t}\left[\sqrt{\frac{\log(1/\delta)}{n}}+\sqrt{\frac{s}{n}\log\left(\frac{2n}{s}\right)}\left(1+\log
n\right)\right]\right)^{2}.$

By assuming that $n$ is large such that
$n\geq\frac{6C^{2}G^{2}}{\mu}\left[\log(1/\delta)+s\log\left(\frac{2n}{s}\right)\left(1+\log
n\right)^{2}\right]$, then

$\displaystyle M_{t}\leq$
$\displaystyle\frac{3C^{2}G^{2}B^{2}\log^{2}(1/\delta)}{n^{2}}+3C^{2}G^{2}\widehat{r}_{t}^{2}\left[\frac{\log(1/\delta)}{n}+\frac{s}{n}\log\left(\frac{2n}{s}\right)\left(1+\log
n\right)^{2}\right]$ $\displaystyle\leq$
$\displaystyle\frac{3C^{2}G^{2}B^{2}\log^{2}(1/\delta)}{n^{2}}+\frac{\mu}{2}\widehat{r}_{t}^{2}.$

Therefore, with probability at least $1-3\delta$ we have

$\displaystyle F(\mathbf{w}_{t+1})-F(\mathbf{w}_{t})\leq$
$\displaystyle\frac{3\eta
C^{2}G^{2}B^{2}\log^{2}(1/\delta)}{2n^{2}}+\frac{\eta\mu}{2}\frac{1}{2}\widehat{r}_{t}^{2}-\eta\mu
F(\mathbf{w}_{t})+\frac{\eta^{2}G^{2}B^{2}L}{2}$ $\displaystyle\leq$
$\displaystyle\frac{3\eta
C^{2}G^{2}B^{2}\log^{2}(1/\delta)}{2n^{2}}-\frac{\eta\mu}{2}F(\mathbf{w}_{t})+\frac{\eta^{2}G^{2}B^{2}L}{2},$

which implies that with probability at least $1-3t\delta$,

$\displaystyle F(\mathbf{w}_{t+1})\leq$
$\displaystyle\left(1-\frac{\eta\mu}{2}\right)^{t}F(\mathbf{w}_{1})+\frac{3C^{2}G^{2}B^{2}\log^{2}(1/\delta)}{n^{2}\mu}+\frac{\eta
G^{2}B^{2}L}{\mu}$ $\displaystyle\leq$ $\displaystyle\exp\left(-\frac{\eta\mu
t}{2}\right)F(\mathbf{w}_{1})+\frac{3C^{2}G^{2}B^{2}\log^{2}(1/\delta)}{n^{2}\mu}+\frac{\eta
G^{2}B^{2}L}{\mu}.$

By setting $t=\frac{2}{\eta\mu}\log\left(\frac{\mu F(\mathbf{w}_{1})}{\eta
G^{2}B^{2}L}\right)$ and $\eta=\min\left(\frac{1}{n^{2}},\frac{1}{L}\right)$,
then with probability at least $1-\delta$ we have

$\displaystyle F(\mathbf{w}_{t+1})\leq$
$\displaystyle\frac{3C^{2}G^{2}B^{2}\log^{2}\left(\frac{2}{\eta\mu\delta}\log\left(\frac{\mu
F(\mathbf{w}_{1})}{\eta G^{2}B^{2}L}\right)\right)}{n^{2}\mu}+\frac{2\eta
G^{2}B^{2}L}{\mu}\leq\widetilde{O}\left(\frac{1}{n^{2}}\right).$

##  5 Conclusions

In this work, we analyze the convergence of multi-pass SGD for solving non-
convex smooth risk minimization problem. Under the Polyak-Łojasiewicz
condition, we establish faster rate of excess risk bound for multi-pass SGD
than one-pass SGD. This result reveals that multiple epochs in training deep
neural networks can help improve the generalization performance. However,
multi-pass SGD can not always improve the performance after it takes $n$
passed over the training data, where $n$ is the sample size of training data.

## References

  * Allen-Zhu et al. [2019] Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song.  A convergence theory for deep learning via over-parameterization.  In _International Conference on Machine Learning_ , pages 242–252, 2019.
  * Arora et al. [2019] Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, and Ruosong Wang.  Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks.  _arXiv preprint arXiv:1901.08584_ , 2019.
  * Bartlett et al. [2017] Peter Bartlett, Dylan J Foster, and Matus Telgarsky.  Spectrally-normalized margin bounds for neural networks.  _arXiv preprint arXiv:1706.08498_ , 2017.
  * Bottou and Bousquet [2007] Léon Bottou and Olivier Bousquet.  The tradeoffs of large scale learning.  In _Advances in Neural Information Processing Systems_ , pages 161–168, 2007.
  * Charles and Papailiopoulos [2018] Zachary Charles and Dimitris Papailiopoulos.  Stability and generalization of learning algorithms that converge to global optima.  In _International Conference on Machine Learning_ , pages 745–754, 2018.
  * Chizat et al. [2019] Lenaic Chizat, Edouard Oyallon, and Francis Bach.  On lazy training in differentiable programming.  In _Advances in Neural Information Processing Systems_ , pages 2937–2947, 2019.
  * Du et al. [2019] Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai.  Gradient descent finds global minima of deep neural networks.  In _International Conference on Machine Learning_ , pages 1675–1685, 2019.
  * Du et al. [2018] Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh.  Gradient descent provably optimizes over-parameterized neural networks.  _arXiv preprint arXiv:1810.02054_ , 2018.
  * Feldman and Vondrak [2019] Vitaly Feldman and Jan Vondrak.  High probability generalization bounds for uniformly stable algorithms with nearly optimal rate.  In _Conference on Learning Theory_ , pages 1270–1279. PMLR, 2019\.
  * Ghadimi and Lan [2013] Saeed Ghadimi and Guanghui Lan.  Stochastic first-and zeroth-order methods for nonconvex stochastic programming.  _SIAM Journal on Optimization_ , 23(4):2341–2368, 2013.
  * Hardt et al. [2016] Moritz Hardt, Ben Recht, and Yoram Singer.  Train faster, generalize better: Stability of stochastic gradient descent.  In _International Conference on Machine Learning_ , pages 1225–1234, 2016.
  * Hastie et al. [2019] Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J Tibshirani.  Surprises in high-dimensional ridgeless least squares interpolation.  _arXiv preprint arXiv:1903.08560_ , 2019.
  * He et al. [2019] Tong He, Zhi Zhang, Hang Zhang, Zhongyue Zhang, Junyuan Xie, and Mu Li.  Bag of tricks for image classification with convolutional neural networks.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pages 558–567, 2019.
  * Karimi et al. [2016] Hamed Karimi, Julie Nutini, and Mark Schmidt.  Linear convergence of gradient and proximal-gradient methods under the polyak-łojasiewicz condition.  In _Joint European Conference on Machine Learning and Knowledge Discovery in Databases_ , pages 795–811. Springer, 2016.
  * Koltchinskii [2011] Vladimir Koltchinskii.  _Oracle Inequalities in Empirical Risk Minimization and Sparse Recovery Problems: Ecole d’Eté de Probabilités de Saint-Flour XXXVIII-2008_ , volume 2033.  Springer Science & Business Media, 2011.
  * Kuzborskij and Lampert [2018] Ilja Kuzborskij and Christoph Lampert.  Data-dependent stability of stochastic gradient descent.  In _International Conference on Machine Learning_ , pages 2815–2824. PMLR, 2018.
  * Lei and Ying [2020] Yunwen Lei and Yiming Ying.  Fine-grained analysis of stability and generalization for stochastic gradient descent.  In _International Conference on Machine Learning_ , pages 5809–5819. PMLR, 2020.
  * Lei and Ying [2021] Yunwen Lei and Yiming Ying.  Sharper generalization bounds for learning with gradient-dominated objective functions.  In _International Conference on Learning Representations_ , 2021.
  * Lei et al. [2021] Yunwen Lei, Ting Hu, and Ke Tang.  Generalization performance of multi-pass stochastic gradient descent with convex loss functions.  _Journal of Machine Learning Research_ , 22(25):1–41, 2021.
  * Li and Li [2018] Zhize Li and Jian Li.  A simple proximal stochastic gradient method for nonsmooth nonconvex optimization.  In _Advances in Neural Information Processing Systems_ , pages 5564–5574, 2018.
  * Lin and Rosasco [2017] Junhong Lin and Lorenzo Rosasco.  Optimal rates for multi-pass stochastic gradient methods.  _The Journal of Machine Learning Research_ , 18(1):3375–3421, 2017.
  * Lin et al. [2016] Junhong Lin, Raffaello Camoriano, and Lorenzo Rosasco.  Generalization properties and implicit regularization for multiple passes sgm.  In _International Conference on Machine Learning_ , pages 2340–2348. PMLR, 2016.
  * Liu et al. [2018] Mingrui Liu, Xiaoxuan Zhang, Lijun Zhang, Rong Jin, and Tianbao Yang.  Fast rates of erm and stochastic approximation: adaptive to error bound conditions.  In _Proceedings of the 32nd International Conference on Neural Information Processing Systems_ , pages 4683–4694, 2018.
  * Nemirovski et al. [2009] Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro.  Robust stochastic approximation approach to stochastic programming.  _SIAM Journal on optimization_ , 19(4):1574–1609, 2009.
  * Nesterov [2004] Yurii Nesterov.  _Introductory lectures on convex optimization : a basic course_.  Applied optimization. Kluwer Academic Publ., 2004.  ISBN 1-4020-7553-7.
  * [26] Loucas Pillaud-Vivien, Alessandro Rudi, and Francis Bach.  Statistical optimality of stochastic gradient descent on hard learning problems through multiple passes.  _Advances in Neural Information Processing Systems_.
  * Plan and Vershynin [2013] Yaniv Plan and Roman Vershynin.  One-bit compressed sensing by linear programming.  _Communications on Pure and Applied Mathematics_ , 66(8):1275–1297, 2013.
  * Polyak [1963] Boris Teodorovich Polyak.  Gradient methods for minimizing functionals.  _Zhurnal Vychislitel’noi Matematiki i Matematicheskoi Fiziki_ , 3(4):643–653, 1963.
  * Robbins and Monro [1951] Herbert Robbins and Sutton Monro.  A stochastic approximation method.  _The annals of mathematical statistics_ , pages 400–407, 1951.
  * Rosasco and Villa [2015] Lorenzo Rosasco and Silvia Villa.  Learning with incremental iterative regularization.  In _Advances in Neural Information Processing Systems_ , pages 1630–1638, 2015.
  * Vapnik [2013] Vladimir Vapnik.  _The nature of statistical learning theory_.  Springer science & business media, 2013.
  * Xu et al. [2017] Yi Xu, Qihang Lin, and Tianbao Yang.  Stochastic convex optimization: Faster local growth implies faster global convergence.  In _International Conference on Machine Learning_ , pages 3821–3830. PMLR, 2017.
  * Ye et al. [2019] Han-Jia Ye, De-Chuan Zhan, and Yuan Jiang.  Fast generalization rates for distance metric learning.  _Machine Learning_ , 108(2):267–295, 2019.
  * Yuan et al. [2019] Zhuoning Yuan, Yan Yan, Rong Jin, and Tianbao Yang.  Stagewise training accelerates convergence of testing error over sgd.  In _Advances in Neural Information Processing Systems_ , pages 2604–2614, 2019.
  * Yun et al. [2019] Chulhee Yun, Suvrit Sra, and Ali Jadbabaie.  Small relu networks are powerful memorizers: a tight analysis of memorization capacity.  In _Advances in Neural Information Processing Systems_ , pages 15558–15569, 2019.
  * Zhang et al. [2016] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals.  Understanding deep learning requires rethinking generalization.  _arXiv preprint arXiv:1611.03530_ , 2016.
  * Zhang et al. [2017] Lijun Zhang, Tianbao Yang, and Rong Jin.  Empirical risk minimization for stochastic convex optimization: $\text{O}(1/n)$\- and $\text{O}(1/n^{2})$-type of risk bounds.  In _Conference on Learning Theory_ , pages 1954–1979. PMLR, 2017\.
  * Zhou et al. [2018] Yi Zhou, Yingbin Liang, and Huishuai Zhang.  Generalization error bounds with probabilistic guarantee for sgd in nonconvex optimization.  _arXiv preprint arXiv:1802.06903_ , 2018.
  * Zou et al. [2020] Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu.  Gradient descent optimizes over-parameterized deep relu networks.  _Machine Learning_ , 109(3):467–492, 2020.

##  Appendix A Results for Strongly Convex

In this section, we will show the results under the strongly convex assumption
in Definition 1. First, i f we use a uniformly sampling without replacement,
SGD can have the generalization bound of $\widetilde{O}(1/n)$ by passing
training data only once. We present the results in the following theorem.

######  Theorem 4 (First Epoch).

Suppose the objective function $F$ satisfies Assumption 1 and the strongly
convex assumption in Definition 1, if the learning rate is set to be
$\eta=\frac{4L}{\gamma^{2}n}\log\left(\frac{n\gamma^{4}F(\mathbf{w}_{0})}{4\sigma^{2}L^{2}}\right)$
in SGD, then we have

$\displaystyle\mathrm{E}[F(\mathbf{w}_{n})]\leq
O\left(\frac{\sigma^{2}L^{3}\log(n)}{\gamma^{4}n}\right).$ (16)

Next, let’s examine the late stage of the optimization beyond the first epoch,
in which we do not have the statistical independence between the model to be
updated and the training data. As a result, our objective function “becomes”
$F_{\mathcal{S}}(\mathbf{w})$. For any iteration $t$ after first epoch (we
denote by $\mathbf{w}_{1}$ the solution obtained from the first epoch), define

$\displaystyle\Omega(r_{t})=\left\\{\mathbf{w}:\|\mathbf{w}-\mathbf{w}_{*}\|\leq
r_{t}\right\\}$ (17)

where

$\displaystyle r_{t}:=\left\|\mathbf{w}_{t}-\mathbf{w}_{*}\right\|.$ (18)

We assume that our model is powerful in fitting the data and therefore $\nu$
will be a small value. Specifically, we assume
$\nu:=\max_{(\mathbf{x},y)}\|\nabla
f(\mathbf{w}_{*};\mathbf{x})(f(\mathbf{w}_{*};\mathbf{x})-y)\|\leq Gr$.

We give the following results of bounding the variances of the stochastic
gradients, which is the key to the analyses.

######  Theorem 5.

Under the assumption $\nu:=\max_{(\mathbf{x},y)}\|\nabla
f(\mathbf{w}_{*};\mathbf{x})(f(\mathbf{w}_{*};\mathbf{x})-y)\|\leq Gr$ and
$\nu<1$, we have, with a probability $1-3\delta$,

$\displaystyle\max\limits_{\mathbf{w}\in\Omega(r)}\|\nabla
F(\mathbf{w})-\nabla F_{\mathcal{S}}(\mathbf{w})\|\leq
C\left(\frac{Gr}{n}+Gr\sqrt{\frac{\log(1/\delta)+d\log(n)}{n}}\right),$ (19)

where $C$ is a universal constant.

Now, we are ready to give the convergence result for the epochs after the
first one.

######  Theorem 6 (After First Epoch).

Suppose the objective function $F$ satisfies Assumption 1 and the
$\gamma$-strongly convex in Definition 1, if
$n\geq\frac{4C^{2}G^{2}(\log(t/\delta)+d\log(n))}{\gamma^{2}}$, by setting
$t=\frac{2}{\eta\gamma}\log\left(\frac{\gamma
n^{2}F(\mathbf{w}_{1})}{2C^{2}G^{2}B^{2}}\right)$ and
$\eta=\min\left(\frac{1}{n^{2}},\frac{1}{L}\right)$, then with probability at
least $1-\delta$ we have

$\displaystyle F(\mathbf{w}_{t+1})\leq\frac{4C^{2}G^{2}B^{2}}{\gamma
n^{2}}+\frac{\eta G^{2}B^{2}L}{\gamma}\leq O\left(\frac{1}{n^{2}}\right).$
(20)

###  A.1 Proof of Theorem 4

We first focus on the optimization of the first epoch. Note that in the first
epoch, it satisfies the condition of statistical independence and therefore we
can apply the standard analysis of stochastic gradient descent. Then, for each
iteration $t$, we have

$\displaystyle\mathrm{E}[F(\mathbf{w}_{t+1})-F(\mathbf{w}_{t})]$
$\displaystyle\overset{(a)}{\leq}$ $\displaystyle\mathrm{E}[\langle\nabla
F(\mathbf{w}_{t}),\mathbf{w}_{t+1}-\mathbf{w}_{t}\rangle]+\frac{L}{2}\mathrm{E}[\|\mathbf{w}_{t+1}-\mathbf{w}_{t}\|^{2}]$
$\displaystyle\overset{(b)}{\leq}$ $\displaystyle-\eta\left(1-\frac{\eta
L}{2}\right)\mathrm{E}[\|\nabla
F(\mathbf{w}_{t})\|^{2}]+\frac{\eta^{2}\sigma^{2}L}{2}$
$\displaystyle\overset{(c)}{\leq}$
$\displaystyle-\eta\widehat{\gamma}\mathrm{E}[F(\mathbf{w}_{t})-F_{*}]+\frac{\eta^{2}\sigma^{2}L}{2},$
(21)

where (a) uses the smoothness of $F(\mathbf{w})$ in Assumption 1 (ii); (b)
uses $\mathbf{w}_{t+1}=\mathbf{w}_{t}-\eta\mathbf{g}_{t}$, and
$\mathrm{E}[\mathbf{g}_{t}]=\nabla F(\mathbf{w}_{t})$ by the unbiased property
of $\nabla\ell(\mathbf{w};\mathbf{z})$ in Assumption 1 (i), and
$\mathrm{E}[\|F(\mathbf{w}_{t})-\mathbf{g}_{t}\|^{2}]\leq\sigma^{2}$ in
Assumption 1 (ii); (c) uses $\eta L\leq 1$ and the $\gamma$-strongly convex in
Definition 1, and (23) with $\widehat{\gamma}:=\frac{\gamma^{2}}{4L}$. In
fact, by the smoothness of $F$, we get
$F(\mathbf{w})-F(\mathbf{v})\leq\langle\nabla
F(\mathbf{v}),\mathbf{w}-\mathbf{v}\rangle+\frac{L}{2}\|\mathbf{w}-\mathbf{v}\|^{2}$.
Let $\mathbf{v}=\mathbf{w}_{*}$, then

$\displaystyle
F(\mathbf{w})-F_{*}\leq\frac{L}{2}\|\mathbf{w}-\mathbf{w}_{*}\|^{2}.$ (22)

On the other hand, by the strong convexity of $F$, we get
$F(\mathbf{v})-F(\mathbf{w})\geq\langle\nabla
F(\mathbf{w}),\mathbf{v}-\mathbf{w}\rangle+\frac{\gamma}{2}\|\mathbf{w}-\mathbf{v}\|^{2}$.
Let $\mathbf{v}=\mathbf{w}_{*}$, then

$\displaystyle\|\nabla F(\mathbf{w})\|\|\mathbf{w}-\mathbf{w}_{*}\|\geq$
$\displaystyle\langle\nabla F(\mathbf{w}),\mathbf{w}-\mathbf{w}_{*}\rangle$
$\displaystyle\geq$ $\displaystyle
F(\mathbf{w})-F_{*}+\frac{\gamma}{2}\|\mathbf{w}-\mathbf{w}_{*}\|^{2}$
$\displaystyle\geq$
$\displaystyle\frac{\gamma}{2}\|\mathbf{w}-\mathbf{w}_{*}\|^{2},$

which implies

$\displaystyle\|\nabla
F(\mathbf{w})\|^{2}\geq\frac{\gamma^{2}}{4}\|\mathbf{w}-\mathbf{w}_{*}\|^{2}\overset{(\ref{thm:1:eq:2})}{\geq}\frac{\gamma^{2}}{4}\frac{2(F(\mathbf{w})-F_{*})}{L}=\frac{\gamma^{2}}{2L}(F(\mathbf{w})-F_{*}).$
(23)

Therefore, by (A.1) we have

$\displaystyle\mathrm{E}[F(\mathbf{w}_{n})-F_{*}]\leq\exp(-\eta\widehat{\gamma}n)(F(\mathbf{w}_{0})-F_{*})+\frac{\eta\sigma^{2}L}{2\widehat{\gamma}}\leq
O\left(\frac{\sigma^{2}L\log(n)}{\widehat{\gamma}^{2}n}\right),$ (24)

where the last inequality is due to the setting of
$\eta=\frac{1}{\widehat{\gamma}n}\log\left(\frac{n\widehat{\gamma}^{2}F(\mathbf{w}_{0})}{\sigma^{2}L}\right)$.
We complete the proof by using $F_{*}=0$ in (24).

###  A.2 Proof of Theorem 5

In this proof, we consider the case of iteration $t+1$ conditional on
iteration $t$, then for simplicity, we omit the subscript $t$. To bound
$\|\nabla F(\mathbf{w})-\nabla F_{\mathcal{S}}(\mathbf{w})\|$, we first have

$\displaystyle\|\nabla F(\mathbf{w})-\nabla
F_{\mathcal{S}}(\mathbf{w})\|\leq\|\nabla F(\mathbf{w})-\nabla
F(\mathbf{w}_{*})+\nabla F_{\mathcal{S}}(\mathbf{w}_{*})-\nabla
F_{\mathcal{S}}(\mathbf{w})\|+\|\nabla F(\mathbf{w}_{*})-\nabla
F_{\mathcal{S}}(\mathbf{w}_{*})\|.$ (25)

Using the standard concentration inequality, with a probability $1-\delta$, we
have

$\displaystyle\|\nabla F(\mathbf{w}_{*})-\nabla
F_{\mathcal{S}}(\mathbf{w}_{*})\|\leq
C\left(\frac{\nu}{n}+\nu\sqrt{\frac{\log(1/\delta)}{n}}\right),$ (26)

where $\nu=\max_{(\mathbf{x},y)}\|\nabla
f(\mathbf{w}_{*};\mathbf{x})(f(\mathbf{w}_{*};\mathbf{x})-y)\|$.

To bound $\|\nabla F(\mathbf{w})-\nabla F(\mathbf{w}_{*})+\nabla
F_{\mathcal{S}}(\mathbf{w}_{*})-\nabla F_{\mathcal{S}}(\mathbf{w})\|$, for any
$\mathbf{w}\in\Omega(r)$, we denote by $\mathcal{N}(\Omega(r),\epsilon)$ the
covering number of the proper $\epsilon$-net of $\Omega(r)$. It is easy to
verify that with a probability at least $1-\delta$,

$\displaystyle\|\nabla F(\mathbf{w})-\nabla F(\mathbf{w}_{*})+\nabla
F_{\mathcal{S}}(\mathbf{w}_{*})-\nabla F_{\mathcal{S}}(\mathbf{w})\|\leq
C\left(\frac{Gr}{n}+Gr\sqrt{\frac{\log(1/\delta)+d\log(r/\epsilon)}{n}}+G\epsilon\right),$
(27)

where we used the fact that
$\mathcal{N}(\Omega(r),\epsilon)=O((r/\epsilon)^{d})$. Combining above three
inequalities, we have, with a probability at least $1-2\delta$

$\displaystyle\|\nabla F(\mathbf{w})-\nabla F_{\mathcal{S}}(\mathbf{w})\|\leq
C\left(\frac{\nu}{n}+\nu\sqrt{\frac{\log(1/\delta)}{n}}+\frac{Gr}{n}+\frac{Gr}{\sqrt{n}}\left(\sqrt{\log(1/\delta)+d\log(n)/2}+1\right)\right),$
(28)

where we choose $\epsilon=r/\sqrt{n}$. Since $\nu\leq Gr$, we have, with a
probability at least $1-3\delta$

$\displaystyle\|\nabla F(\mathbf{w})-\nabla F_{\mathcal{S}}(\mathbf{w})\|\leq
O\left(Gr\sqrt{\frac{\log(1/\delta)+d\log(n)}{n}}\right).$ (29)

###  A.3 Proof of Theorem 6

In this proof, we consider the updates after first epoch, i.e., $t\geq n$.
Following the similar analysis of Theorem 3, we have

$\displaystyle F(\mathbf{w}_{t+1})-F(\mathbf{w}_{t})\leq$
$\displaystyle\frac{\eta}{2}\left\|\nabla F(\mathbf{w}_{t})-\nabla
F_{\mathcal{S}}(\mathbf{w}_{t})\right\|^{2}-\frac{\eta}{2}\left\|\nabla
F(\mathbf{w}_{t})\right\|^{2}+\frac{\eta^{2}G^{2}B^{2}L}{2}$
$\displaystyle\leq$ $\displaystyle\frac{\eta M_{t}}{2}-\eta\gamma
F(\mathbf{w}_{t})+\frac{\eta^{2}G^{2}B^{2}L}{2},$ (30)

where the last inequality uses $\gamma$-strongly convexity and Theorem 5 with

$\displaystyle M_{t}:=$ $\displaystyle
C^{2}\left(\frac{Gr_{t}}{n}+Gr_{t}\sqrt{\frac{\log(1/\delta)+d\log(n)}{n}}\right)^{2}.$
(31)

Therefore, with probability at least $1-3\delta$ we have

$\displaystyle F(\mathbf{w}_{t+1})-F(\mathbf{w}_{t})\leq$ $\displaystyle\eta
C^{2}\left(\frac{G^{2}B^{2}}{n^{2}}+G^{2}r_{t}^{2}\frac{\log(1/\delta)+d\log(n)}{n}\right)-\eta\gamma
F(\mathbf{w}_{t})+\frac{\eta^{2}G^{2}B^{2}L}{2}.$

By the strong convexity and $F_{*}=0$ we know

$\displaystyle r_{t}^{2}\leq\frac{2(F(\mathbf{w}_{t}))}{\gamma}.$

Thus

$\displaystyle F(\mathbf{w}_{t+1})-F(\mathbf{w}_{t})\leq$
$\displaystyle\frac{\eta C^{2}G^{2}B^{2}}{n^{2}}+F(\mathbf{w}_{t})\frac{2\eta
C^{2}G^{2}(\log(1/\delta)+d\log(n))}{\gamma n}-\eta\gamma
F(\mathbf{w}_{t})+\frac{\eta^{2}G^{2}B^{2}L}{2}$ $\displaystyle\leq$
$\displaystyle\frac{\eta
C^{2}G^{2}B^{2}}{n^{2}}-\frac{\eta\gamma}{2}F(\mathbf{w}_{t})+\frac{\eta^{2}G^{2}B^{2}L}{2}.$

where the last inequality is due to
$n\geq\frac{4C^{2}G^{2}(\log(1/\delta)+d\log(n))}{\gamma^{2}}$. Then, with
probability at least $1-3t\delta$,

$\displaystyle F(\mathbf{w}_{t+1})\leq$
$\displaystyle\left(1-\frac{\eta\gamma}{2}\right)^{t}F(\mathbf{w}_{1})+\frac{2C^{2}G^{2}B^{2}}{\gamma
n^{2}}+\frac{\eta G^{2}B^{2}L}{\gamma}$ $\displaystyle\leq$
$\displaystyle\exp\left(-\frac{\eta\gamma
t}{2}\right)F(\mathbf{w}_{1})+\frac{2C^{2}G^{2}B^{2}}{\gamma n^{2}}+\frac{\eta
G^{2}B^{2}L}{\gamma}.$

By setting $t=\frac{2}{\eta\gamma}\log\left(\frac{\gamma
n^{2}F(\mathbf{w}_{1})}{2C^{2}G^{2}B^{2}}\right)$ and
$\eta=\min\left(\frac{1}{n^{2}},\frac{1}{L}\right)$, then with probability at
least $1-\delta$ we have

$\displaystyle F(\mathbf{w}_{t+1})\leq$
$\displaystyle\frac{4C^{2}G^{2}B^{2}}{\gamma n^{2}}+\frac{\eta
G^{2}B^{2}L}{\gamma}\leq O\left(\frac{1}{n^{2}}\right).$