# Application of Fermion Quantum Number $F$ and Unit Electroweak Charge
$F_{0}$ in the Electroweak Theory

Xin-Hua Ma
Key Laboratory of Particle Astrophyics, Institute of High Energy Physics,
Chinese Academy of Sciences, 100049 Beijing, China
TIANFU Cosmic Ray Research Center, Chengdu, Sichuan, China
<EMAIL_ADDRESS>

###### Abstract

After hypercharge $Y$, isospin $I$, isospin projection $I_{3}$, and four
flavour quantum numbers ($S$, $C$, $B^{*}$ and $T$), weak isospin $I_{w3}$ and
weak hypercharge $Y_{w}$ in the electroweak theory are substituted by fermion
quantum number $F$ and unit electroweak charge $F_{0}$, both of which are
conserved in electromagnetic interaction, weak interaction and strong
interaction. Electrical charge $Q$ and neutral current weak charge $Q_{Z}$ in
electroweak interaction can be expressed by mixture of $F$ and $F_{0}$ via the
Weinberg angle $\theta_{W}$. Electroweak interaction is separated into two
parts: one is neutral current electroweak interaction which has no change of
particle types with only exchange of neutral bosons, and the other is charged
current weak interaction which has change of particle types, i.e., decays.

##  1 Introduction

At the most elementary particle level, fermions include quarks and leptons.
During development of the elementary particle physics, it was found that
fermions have several additive quantum numbers traditionally: electric charge
$Q$ (with unit of electron charge $e$), baryon quantum number $B$, lepton
quantum number $L$, hypercharge $Y$, isospin $I$ with isospin projection
$I_{3}$ and flavour quantum numbers including $S$, $C$, $B^{*}$ and $T$. $Y$
is sum of $B$ and flavour quantum numbers. Only $Q$, $B$ and $L$ are conserved
in electromagnetic interaction, strong interaction and weak interaction.
Especially, weak interaction changes the lepton only into itself or into the
other member of the same generation in the lepton family, so leptons have
three individually conserved lepton quantum numbers $L_{e}$, $L_{\mu}$ and
$L_{\tau}$. $Y$, $I_{3}$, $S$, $C$, $B^{*}$ and $T$ are conserved in
electromagnetic interaction and strong interaction, but not conserved in weak
interaction. $I$ is conserved in strong interaction, but not conserved in
either electromagnetic interaction or weak interaction. In the electroweak
theory, also known as the Glashow-Weinberg-Salam (GWS) theory, weak isospin
$I_{w}$ with weak isospin projection $I_{w3}$ and weak hypercharge $Y_{w}$
were inducted for electroweak interaction analogical to $I$ and $Y$ by using
Gell-Mann-Nishijima formula, but values of $I_{w3}$ and $Y_{w}$ completely
different with $I$ and $Y$ respectively except for the left-handed u and d
quark. Antifermions have additive quantum numbers with the same absolute
values as fermions but the opposite sign of fermion, except that antiquarks
have same $I$ as quarks. Knowledge above can be found in textbooks about
elementary particle physics, e.g., [1][2][3][4][5] .

Recently, fermion quantum number $F$ was brought forward to replace $I$,
$I_{3}$ and flavour quantum numbers to solve their problems of not
conservation [6]. In fact, $I$ and $I_{3}$ can be defined as a combination of
flavour quantum numbers of $u$ and $d$ quark. Same as $Q$ and $F_{0}$ which is
combination of $B$ and $L$, $F$ is conserved in electromagnetic interaction,
strong interaction and weak interaction. The formula of relation between $Q$,
$F$ and $F_{0}$ for all fermions is more general than the Gell-Mann-Nishijima
formula. Furthermore, it was found that all the miscellaneous selection rules
in all types of weak interaction can be interpreted by conservation of $F$,
and even why some selections have not been observed in experiments can be
explained by not conservation of $F$ in the cases [7]. In this paper, I apply
$F$ and $F_{0}$ in the electroweak theory instead of $I_{w3}$ and $Y_{w}$, and
deduce Lagrangian of the electroweak interaction in new type.

##  2 Traditional Additive Quantum Numbers of Fermions

Values of traditional additive quantum numbers of fermions are listed in Table
1. Relation between $Q$, $I_{3}$ and $Y$ was given by Gell-Mann-Nishijima
formula [8][9][10] (in extended form):

$Q=I_{3}+Y/2$ (1)

fermion | $Q$ | $B$ | $I$ | $I_{3}$ | $S$ | $C$ | $B^{*}$ | $T$ | $Y$ | $L_{e}$ | $L_{\mu}$ | $L_{\tau}$ | $L$
---|---|---|---|---|---|---|---|---|---|---|---|---|---
$d$ | -1/3 | 1/3 | 1/2 | -1/2 | 0 | 0 | 0 | 0 | 1/3 | 0 | 0 | 0 | 0
$u$ | 2/3 | 1/3 | 1/2 | 1/2 | 0 | 0 | 0 | 0 | 1/3 | 0 | 0 | 0 | 0
$s$ | -1/3 | 1/3 | 0 | 0 | -1 | 0 | 0 | 0 | -2/3 | 0 | 0 | 0 | 0
$c$ | 2/3 | 1/3 | 0 | 0 | 0 | 1 | 0 | 0 | 4/3 | 0 | 0 | 0 | 0
$b$ | -1/3 | 1/3 | 0 | 0 | 0 | 0 | -1 | 0 | -2/3 | 0 | 0 | 0 | 0
$t$ | 2/3 | 1/3 | 0 | 0 | 0 | 0 | 0 | 1 | 4/3 | 0 | 0 | 0 | 0
$e$ | -1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1
$\nu_{e}$ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1
$\mu$ | -1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1
$\nu_{\mu}$ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1
$\tau$ | -1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1
$\nu_{\tau}$ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1
Table 1: Traditional additive quantum numbers of fermions. Antifermions have
additive quantum numbers with the same absolute values as fermions but the
opposite sign of fermion, except that antiquarks have same $I$ as quarks.

In the GWS theory, The weak force in its original form, that is, before mixing
and spontaneous symmetry breakdown, has chiral $SU(2)$ symmetry. The true weak
force and the electromagnetic force are based on a mixture of $SU(2)$ and
$U(1)$. All the left-handed fermions constitute doublets. All the right-handed
fermions belong to $SU(2)$ singlets. In this section, the form of the
variables and the equations refers to [5], except that lower corner mark ”w”
for ”weak” is added explicitly. All the leptons can be classified by their
weak isospin component as

$\begin{array}[]{l}\left\\{\begin{array}[]{l}I_{w3}=1/2\\\
I_{w3}=-1/2\end{array}\right.\\\
I_{w3}=0\end{array}\quad\begin{array}[]{l}\Psi_{L}=\left(\begin{array}[]{l}\nu_{e}\\\
e\end{array}\right)_{L},\left(\begin{array}[]{l}\nu_{\mu}\\\
\mu\end{array}\right)_{L},\left(\begin{array}[]{l}\nu_{\tau}\\\
\tau\end{array}\right)_{L}\\\ e_{R},\mu_{R},\tau_{R}\end{array}$ (2)

The right-handed neutrinos do not exist. For the quarks

$\begin{array}[]{l}\left\\{\begin{array}[]{l}I_{w3}=1/2\\\
I_{w3}=-1/2\end{array}\right.\\\
I_{w3}=0\end{array}\quad\begin{array}[]{l}\Psi_{L}=\left(\begin{array}[]{l}u\\\
d^{\prime}\end{array}\right)_{L},\left(\begin{array}[]{l}c\\\
s^{\prime}\end{array}\right)_{L},\left(\begin{array}[]{l}t\\\
b^{\prime}\end{array}\right)_{L}\\\
u_{R},d_{R},c_{R},s_{R},t_{R},b_{R}\end{array}$ (3)

where ($d^{\prime}$,$s^{\prime}$,$b^{\prime}$) are Cabibbo-Kobayashi-Maskawa
(CKM) rotated fields. Relation between $Q$, $I_{w3}$ and $Y_{w}$ is given by
Gell-Mann-Nishijima-like formula:

$Q=I_{w3}+Y_{w}/2$ (4)

Values of $I_{w3}$ and $Y_{w}$ of fermions are explicitly listed in Table 2
and 3. Comparing Table 2, 3 and 1, we can see that $I_{w3}$ and $Y_{w}$ are
completely different from $I_{3}$ and $Y$ except for $d^{\prime}_{L}$ and
$u_{L}$.

fermion | $Q$ | $I_{w3}$ | $Y_{w}$
---|---|---|---
$d^{\prime}_{L}$ | -1/3 | -1/2 | 1/3
$u_{L}$ | 2/3 | 1/2 | 1/3
$s^{\prime}_{L}$ | -1/3 | -1/2 | 1/3
$c_{L}$ | 2/3 | 1/2 | 1/3
$b^{\prime}_{L}$ | -1/3 | -1/2 | 1/3
$t_{L}$ | 2/3 | 1/2 | 1/3
$e_{L}$ | -1 | -1/2 | -1
$\nu_{eL}$ | 0 | 1/2 | -1
$\mu_{L}$ | -1 | -1/2 | -1
$\nu_{\mu L}$ | 0 | 1/2 | -1
$\tau_{L}$ | -1 | -1/2 | -1
$\nu_{\tau L}$ | 0 | 1/2 | -1
Table 2: $I_{w3}$ and $Y_{w}$ of the left-handed fermions in the GWS theory. Antifermions have additive quantum numbers with the same absolute values as fermions but the opposite sign of fermion. fermion | $Q$ | $I_{w3}$ | $Y_{w}$
---|---|---|---
$d_{R}$ | -1/3 | 0 | -2/3
$u_{R}$ | 2/3 | 0 | 4/3
$s_{R}$ | -1/3 | 0 | -2/3
$c_{R}$ | 2/3 | 0 | 4/3
$b_{R}$ | -1/3 | 0 | -2/3
$t_{R}$ | 2/3 | 0 | 4/3
$e_{R}$ | -1 | 0 | -2
$\nu_{eR}$ | 0 | 0 | 0
$\mu_{R}$ | -1 | 0 | -2
$\nu_{\mu R}$ | 0 | 0 | 0
$\tau_{R}$ | -1 | 0 | -2
$\nu_{\tau R}$ | 0 | 0 | 0
Table 3: $I_{w3}$ and $Y_{w}$ of the right-handed fermions in the GWS theory.
Antifermions have additive quantum numbers with the same absolute values as
fermions but the opposite sign of fermion.

In the original Lagrangian of the electroweak interaction, the part of the
interaction of the gauge boson with the fermion

$-\mathscr{L}_{Wff}=\bar{\Psi}i\gamma^{\mu}D_{\mu}\Psi$ (5)

is contained in the covariant derivative

$D_{\mu}=\partial_{\mu}+ig_{W}\mathbf{W}_{\mu}\cdot\mathbf{t}+i\frac{g_{B}}{2}Y_{w}B_{\mu}$
(6)

where $\gamma^{\mu}$ ($\mu$=0,1,2,3) are Dirac $\gamma$ matrices,
$\mathbf{W}_{\mu}$ is the $SU(2)$ gauge field, $B_{\mu}$ is the gauge boson of
$U(1)$, $g_{W}$ and $g_{B}$ are coupling strength of $\mathbf{W}_{\mu}$ and
$B_{\mu}$ respectively, $\mathbf{t}=\mathbf{\tau}/2$ is weak isospin operator,
and $\mathbf{\tau}$ is the Pauli $2\times 2$ matrix. By using the Weinberg
angle $\theta_{W}$, $g_{W}$ and $g_{B}$ has relation in

$tan\theta_{W}=\frac{g_{B}}{g_{W}}.$ (7)

After mixing $SU(2)$ and $U(1)$, it can be deduced

$-\mathscr{L}_{Wff}=\mathscr{L}_{W}+\mathscr{L}_{Z}+\mathscr{L}_{em}$ (8)

which is composed of the charged current weak interaction part

$\mathscr{L}_{W}=\frac{g_{W}}{\sqrt{2}}\bar{\Psi}_{L}\gamma^{\mu}(W^{+}_{\mu}\tau_{+}+W^{-}_{\mu}\tau_{-})\Psi_{L},$
(9)

the neutral current weak interaction part

$\mathscr{L}_{Z}=g_{Z}\bar{\Psi}\gamma^{\mu}(I_{w3}-Qs^{2}_{W})\Psi Z_{\mu}$
(10)

and the electromagnetic interaction part

$\mathscr{L}_{em}=e\bar{\Psi}\gamma^{\mu}Q\Psi A_{\mu}$ (11)

where $W_{\mu}^{+}$ and $W_{\mu}^{-}$ are charged boson field operators,
$Z_{\mu}$ is neutral boson field operator, $A_{\mu}$ is electromagnetic field
operator, $\tau_{\pm}=(\tau_{1}\pm i\tau_{2})/2$, $s_{W}=sin\theta_{W}$,
$c_{W}=cos\theta_{W}$, and $e$ and $g_{Z}$ are coupling constant of $A_{\mu}$
and $Z_{\mu}$ respectively defined in terms of $g_{W}$ and $\theta_{W}$ as

$\begin{array}[]{l}e=g_{W}s_{W}\\\ g_{Z}=g_{W}/c_{W}.\end{array}$ (12)

Coupling types which appear in the Feynman amplitude rule are given by the
matrix element $i\mathscr{L}_{Wff}$, so, omitting the field operators and
attaching a suffix to differentiate the fermion flavour, interaction vertices
are expressed as

$\gamma-ff:-ie\gamma^{\mu}Q_{f}$ (13)
$W^{\pm}-ff:-i\frac{g_{W}}{2\sqrt{2}}\gamma^{\mu}(1-\gamma^{5})$ (14)
$Z-ff:-i\frac{g_{W}}{2}\gamma^{\mu}(v_{f}-a_{f}\gamma^{5})$ (15)

where $\gamma^{5}$ is chirality operator, $f$ = $e,\mu,\tau$ or $d,u,s,c,b,t$,
and

$\begin{array}[]{l}v_{f}=I_{w3f}-2Q_{f}s_{W}^{2}\\\ a_{f}=I_{w3f}\end{array}$
(16)

##  3 Fermion Quantum number $F$ and Unit Electroweak Charge $F_{0}$

Instead of $I$, $I_{3}$, $S$, $C$, $B^{*}$ and $T$, $F$ for all fermions have
simple values [6]:

$F=\left\\{\begin{array}[]{r@{\quad:\quad}l}-1&\mbox{fermion is 'd' type}\\\
+1&\mbox{fermion is 'u' type}\end{array}\right.$ (17)

The relation between electric charge $Q$, $F_{0}$ and $F$ is simple and
direct:

$Q=\frac{F}{2}+\frac{F_{0}}{2},$ (18)

where F0 is:

$F_{0}=\left\\{\begin{array}[]{r@{\quad:\quad}l}B=+1/3&\mbox{fermion is
quark}\\\ -L=-1&\mbox{fermion is lepton}\end{array}\right.$ (19)

The Formula (Equation 18) of relation between $Q$, $F$ and $F_{0}$ is for all
fermions, more general than the Gell-Mann-Nishijima formula (Equation 1).
Values of $Q$, $F$ and $F_{0}$ are listed in Table 4.

fermion | $Q$ | $F$ | $F_{0}$
---|---|---|---
$d$ | -1/3 | -1 | 1/3
$u$ | 2/3 | 1 | 1/3
$s$ | -1/3 | -1 | 1/3
$c$ | 2/3 | 1 | 1/3
$b$ | -1/3 | -1 | 1/3
$t$ | 2/3 | 1 | 1/3
$e$ | -1 | -1 | -1
$\nu_{e}$ | 0 | 1 | -1
$\mu$ | -1 | -1 | -1
$\nu_{\mu}$ | 0 | 1 | -1
$\tau$ | -1 | -1 | -1
$\nu_{\tau}$ | 0 | 1 | -1
Table 4: Values of $Q$, $F$ and $F_{0}$. Antifermions have additive quantum
numbers with the same absolute values as fermions but the opposite sign of
fermion.

By comparing Table 4 with Table 2, it is demonstrated that for the left-handed
fermions,

$I_{w3}=\frac{F}{2}$ (20)

and

$Y_{w}=F_{0},$ (21)

that is, weak isospin projection $I_{w3}$ and weak hypercharge $Y_{w}$ in the
electroweak theory are equivalent to half of $F$ and $F_{0}$ respectively. By
extending $F$ and $F_{0}$ to the right-handed fermions with Equation 18 and
$F=0$, we obtain values of $F$ and $F_{0}$ of all fermions listed in Table 5.

fermion | $Q$ | $F$ | $F_{0}$
---|---|---|---
$d^{\prime}_{L}$ | -1/3 | -1 | 1/3
$u_{L}$ | 2/3 | 1 | 1/3
$s^{\prime}_{L}$ | -1/3 | -1 | 1/3
$c_{L}$ | 2/3 | 1 | 1/3
$b^{\prime}_{L}$ | -1/3 | -1 | 1/3
$t_{L}$ | 2/3 | 1 | 1/3
$e_{L}$ | -1 | -1 | -1
$\nu_{eL}$ | 0 | 1 | -1
$\mu_{L}$ | -1 | -1 | -1
$\nu_{\mu L}$ | 0 | 1 | -1
$\tau_{L}$ | -1 | -1 | -1
$\nu_{\tau L}$ | 0 | 1 | -1
$d_{R}$ | -1/3 | 0 | -2/3
$u_{R}$ | 2/3 | 0 | 4/3
$s_{R}$ | -1/3 | 0 | -2/3
$c_{R}$ | 2/3 | 0 | 4/3
$b_{R}$ | -1/3 | 0 | -2/3
$t_{R}$ | 2/3 | 0 | 4/3
$e_{R}$ | -1 | 0 | -2
$\nu_{eR}$ | 0 | 0 | 0
$\mu_{R}$ | -1 | 0 | -2
$\nu_{\mu R}$ | 0 | 0 | 0
$\tau_{R}$ | -1 | 0 | -2
$\nu_{\tau R}$ | 0 | 0 | 0
Table 5: $Q$, $F$ and $F_{0}$ extended to the left-handed and right-handed
fermions in the electroweak theory. Antifermions have additive quantum numbers
with the same absolute values as fermions but the opposite sign of fermion.

In term of F, the leptons can be classified as

$\begin{array}[]{l}\left\\{\begin{array}[]{l}F=1\\\ F=-1\end{array}\right.\\\
F=0\end{array}\quad\begin{array}[]{l}\Psi_{L}=\left(\begin{array}[]{l}\nu_{e}\\\
e\end{array}\right)_{L},\left(\begin{array}[]{l}\nu_{\mu}\\\
\mu\end{array}\right)_{L},\left(\begin{array}[]{l}\nu_{\tau}\\\
\tau\end{array}\right)_{L}\\\ e_{R},\mu_{R},\tau_{R}\end{array}$ (22)

and the quarks

$\begin{array}[]{l}\left\\{\begin{array}[]{l}F=1\\\ F=-1\end{array}\right.\\\
F=0\end{array}\quad\begin{array}[]{l}\Psi_{L}=\left(\begin{array}[]{l}u\\\
d^{\prime}\end{array}\right)_{L},\left(\begin{array}[]{l}c\\\
s^{\prime}\end{array}\right)_{L},\left(\begin{array}[]{l}t\\\
b^{\prime}\end{array}\right)_{L}\\\
u_{R},d_{R},c_{R},s_{R},t_{R},b_{R}\end{array}$ (23)

The covariant derivative can be rewritten as

$D_{\mu}=\partial_{\mu}+i\frac{g_{W}}{2}\mathbf{W}_{\mu}\cdot\mathbf{\tau}+i\frac{g_{B}}{2}F_{0}B_{\mu}$
(24)

where Pauli $2\times 2$ matrix $\mathbf{\tau}$ directly becomes $F$ operator
and $F_{0}$ substitutes $Y_{w}$. After mixing $SU(2)$ and $U(1)$, it can be
deduced that the charged current part $\mathscr{L}_{W}$ and the
electromagnetic part $\mathscr{L}_{em}$ are same as Equation 9 and 11
respectively, but the neutral current part becomes

$\mathscr{L}_{Z}=g_{Z}\bar{\Psi}\gamma^{\mu}Q_{Z}\Psi Z_{\mu}$ (25)

where $Q_{Z}$ is neutral current weak charge

$Q_{Z}=\frac{c_{W}^{2}}{2}F-\frac{s_{W}^{2}}{2}F_{0}$ (26)

Interaction vertices of the charged current part and the electromagnetic part
are same as Equation 13 and 14 respectively, but one of the neutral current
part becomes

$\begin{array}[]{l}v_{f}=(\frac{1}{2}-s_{W}^{2})F_{f}-s_{W}^{2}F_{0f}\\\
a_{f}=\frac{1}{2}F_{f}\end{array}$ (27)

Combining Equation 18 and 26 we can obtain

$\begin{array}[]{l}\left(\begin{array}[]{l}Q\\\
Q_{Z}\end{array}\right)=\frac{1}{2}\left(\begin{array}[]{c}1\\\
c_{W}^{2}\end{array}\right.\left.\begin{array}[]{c}1\\\
-s_{W}^{2}\end{array}\right)\left(\begin{array}[]{l}F\\\
F_{0}\end{array}\right).\end{array}$ (28)

In consequence, charge ($Q$, $Q_{Z}$) of electromagnetic interaction and
neutral current weak interaction, which can be combined as neutral current
electroweak interaction, can be deduced from mixture of $F$ and $F_{0}$ via
$\theta_{W}$, and $F_{0}$ works as unit electroweak charge. Conservation of
charge ($Q$, $Q_{Z}$) is originated from conservation of $F$ and $F_{0}$.

Furthermore, we can take following vectors and tensor which combine constants
and parameters of neutral current electroweak interaction:

Electroweak charge vector

$\begin{array}[]{l}\mathbf{Q_{eZ}}=\left(\begin{array}[]{l}~{}~{}eQ\\\
g_{Z}Q_{Z}\end{array}\right),\end{array}$ (29)

electroweak fermion quantum number vector

$\begin{array}[]{l}\mathbf{F_{eZ}}=\left(\begin{array}[]{l}F\\\
F_{0}\end{array}\right),\end{array}$ (30)

and transformation tensor

$\begin{array}[]{l}\mathbf{C}=\left(\begin{array}[]{c}1\\\
a_{w}\end{array}\right.\left.\begin{array}[]{c}1\\\
-t_{w}\end{array}\right)\end{array}$ (31)

where $t_{W}=tan\theta_{W}$ and $a_{W}=atan\theta_{W}$, and the relation
between $\mathbf{Q_{eZ}}$ and $\mathbf{F_{eZ}}$ is gained:

$\begin{array}[]{l}\mathbf{Q_{eZ}}=\frac{1}{2}e\mathbf{C}\mathbf{F_{eZ}}.\end{array}$
(32)

Finally, by combining electromagnetic field and neutral current weak field
into neutral current electroweak field,

$\begin{array}[]{l}\mathbf{X_{\mu}}=\left(\begin{array}[]{l}A_{\mu}\\\
Z_{\mu}\end{array}\right),\end{array}$ (33)

Lagrangian of the electroweak interaction can be rewritten, including two
parts:

$-\mathscr{L}_{Wff}=\mathscr{L}_{W}+\mathscr{L}_{eZ}$ (34)

where part of neutral current electroweak interaction is

$\mathscr{L}_{eZ}=\mathscr{L}_{em}+\mathscr{L}_{Z}=\bar{\Psi}\gamma^{\mu}Q_{eZ}^{\nu}\Psi
X_{\mu\nu}$ (35)

where $\nu$=1,2.

##  4 Conclusion and Discussion

Both fermion quantum number $F$ and unit electroweak charge $F_{0}$ are
conserved in electromagnetic interaction, weak interaction and strong
interaction. Not only hypercharge $Y$, isospin $I$, isospin projection $I_{3}$
and four flavour quantum numbers ($S$, $C$, $B^{*}$ and $T$), but also weak
isospin $I_{w3}$ and weak hypercharge $Y_{w}$ in the electroweak theory are
substituted by $F$ and $F_{0}$ in simpler method of additive quantum numbers.
Indistinguishability of fermions results in $F$ conservation, and
indistinguishability of relative phases of wave functions of fermions results
in $F_{0}$ conservation. It can be analogical to the fact that
indistinguishability of protons and neutrons results in $I_{3}$ conservation
in nuclei, and indistinguishability of relative phases of wave functions of
charged particles results in $Q$ conservation in electromagnetic interaction.

More profoundly, by combining electromagnetic interaction and neutral current
weak interaction into neutral current electroweak interaction, electroweak
charge $\mathbf{Q_{eZ}}$ can be deduced from electroweak fermion quantum
number $\mathbf{F_{eZ}}$ via $\theta_{W}$. Then electroweak interaction is
separated into two parts: one is neutral current electroweak interaction which
has no change of particle types with only exchange of neutral bosons, and the
other is charged current weak interaction which has change of particle types,
i.e., decays.

In fact, generality among electromagnetic interaction, neutral current weak
interaction and strong interaction is that flavours of fermions are not
changed (including fermion pair production), and the interactions happen
between fermions via exchanging neutral bosons (photon, $Z^{0}$ and gluon
respectively). On the the other hand, in charged current weak interaction,
including all types of decays and their equivalent reactions, flavours of
fermions are changed, which means charged current weak interaction happens
inside fermions via emitting or absorbing charged bosons ($W^{\pm}$). It is
interesting that the selection rules of charged current weak interaction are
determined by conservation of $F$ [7], meanwhile electroweak fermion quantum
number $\mathbf{F_{eZ}}$ (including $F$ and $F_{0}$) determines electroweak
charge $\mathbf{Q_{eZ}}$ (including $Q$, $Q_{Z}$) of neutral current
electroweak interaction. Maybe we should recombine different interactions in
the unified theory into the flavour-unchanged part and the flavour-changed
part where $\mathbf{F_{eZ}}$ should perform a function.

## Acknowledgement

This research was funded by National Natural Science Foundation of China
(NSFC, No. 12320101005 and U2031103).

## References

  * [1] N. S. Zhang, _Particle Physics (I)_ , Science Press (1986).
  * [2] N. S. Zhang, _Particle Physics (II)_ , Science Press (1987).
  * [3] Q. H. Kim and X. Y. Pham, _Elementary Particles and Their Interactions_. (Springer, 1998).
  * [4] Y. Nagashima, _Elementary Particle Physics, Volume 1: Quantum Field Theory and Particles_. (Wiley, 2010).
  * [5] Y. Nagashima, _Elementary Particle Physics, Volume 2: Foundations of the Standard Model_. (Wiley, 2013).
  * [6] Xin-Hua Ma, _Consideration of Additive Quantum Numbers of Fermions and Their Conservations_ , _Universe_ , 7 (2021) 317.
  * [7] Xinhua Ma, _Selection Rules in Weak Interaction and Conservation of Fermion Quantum Number_ , _Journal of Modern Physics_ , 13 (2022) 700.
  * [8] Tadao Nakano and Kazuhiko Nishijima, _Charge Independence for V-particles_ , _Progress of Theoretical Physics_ , 10(5) (1953) 581.
  * [9] Kazuhiko Nishijima, _Charge Independence Theory of V Particles_ , _Progress of Theoretical Physics_ , 13(3) (1955) 285.
  * [10] Murray Gell-Mann, _The Interpretation of the New Particles as Displaced Charged Multiplets_ , _Il Nuovo Cimento_ , 4 (1956) 848.


On the Convergence of Stochastic Gradient Descent in Low-precision Number
Formats

Matteo Cacciola1 Antonio Frangioni2 Masoud Asgharian3 Alireza Ghaffari4 Vahid
Partovi Nia4

1Polytechnique Montreal 2University of Pisa 3McGill University 4Huawei Noah’s
Ark Lab

###### Abstract

Deep learning models are dominating almost all artificial intelligence tasks
such as vision, text, and speech processing. Stochastic Gradient Descent (SGD)
is the main tool for training such models, where the computations are usually
performed in single-precision floating-point number format. The convergence of
single-precision SGD is normally aligned with the theoretical results of real
numbers since they exhibit negligible error. However, the numerical error
increases when the computations are performed in low-precision number formats.
This provides compelling reasons to study the SGD convergence adapted for low-
precision computations. We present both deterministic and stochastic analysis
of the SGD algorithm, obtaining bounds that show the effect of number format.
Such bounds can provide guidelines as to how SGD convergence is affected when
constraints render the possibility of performing high-precision computations
remote.

##  1 Introduction

The success of deep learning models in different machine learning tasks have
made these models de facto for almost all vision, text, and speech processing
tasks. Figure 1 depicts the size of deep learning models, indicating an
exponential increase in the size of the models, and hence an urge for
efficient computations. A common technique used in training deep learning
models is SGD but the theoretical behaviour of SGD in rarely studied in low-
precision number formats. Although there is a surge of articles on real
numbers (for example see Polyak (1967), Schmidt et al. (2011), Ram et al.
(2009)), the performance of SGD in low-precision number formats started
recently. Depending on the precision, the loss landscape can change
considerably. Figure 2, for instance, depicts this situation for ResNet-18
loss landscape in both single-precision and low-precision number formats.
Motivated by Figure 2, we present a formal study of SGD for quasi-convex
functions when computations are performed in low-precision number formats.

Figure 1: Exploding trend of deep learning models for image classification
(black) and language models (blue) in time.

We note that numerical errors, both in forward and back propagation, can
possibly affect the convergence behaviour of the algorithm. It is conceivable
that the numerical errors should increase as the precision decreases. To
understand the effect of number format on the convergence of SGD, a careful
analysis of the SGD algorithm for a predetermined precision is needed. We
present both deterministic and stochastic analysis of the normalized SGD
algorithm, obtaining bounds that show, explicitly, the effect of precision,
i.e. number format. Such bounds can provide guidelines as to how SGD
convergence is affected when constraints render performing high-precision
computations impractical, and to what extent the precision can be reduced
without compromising SGD convergence.

Our experiments are performed for logistic regression on MNIST dataset. They
confirm that the trajectory of the loss in low-precision SGD setup has at
least a limit point whose loss value is in the proximity of the minimum when
the numerical errors are relatively small, see Theorem 4.1 and Theorem 4.3.

This paper is organized as follows. Section 2 presents a literature review on
the low-precision training of deep learning models and also provides some
common background for theoretical analysis of SGD. Section 3 discusses some
preliminary notations and definitions for analysis of quasi-convex loss
function and also the floating point number formats. Section 4 contains the
main theoretical results. Section 5 provides some experimental results that
support our theoretical results. We conclude in Section 6.

Figure 2: ResNet-18 loss landscape in single-precision (left) and low-
precision number format (right).

##  2 Related works

Recently, deep learning models provide state-of-the-art performance in various
machine learning tasks such as computer vision, speech, and natural language
processing (NLP). The size of ImageNet classification models after the
introduction of AlexNet size is exploded to $200\times$, and the size of
language models are getting $10\times$ bigger every year. The recent trend of
deep learning models shows that larger models such as transformers (Vaswani et
al., 2017) and their variants such as GPT2 (Radford et al., 2019), MegatronLM
(Shoeybi et al., 2019), and Brown et al. (2020) are easier to generalize on
different downstream tasks. Moreover, examples of large language models are
included in Figure 1 (blue line) and they show an increasing trend in number
of parameters over time. A similar trend also appear in vision models,
specially after the advent of vision transformers (Zhai et al., 2022; Goyal et
al., 2022) that beat convolutional neural networks (Mahajan et al., 2018) on
various tasks, see Figure 1 (black line). Although such large models have
advantage in terms of accuracy, they suffer from high computational cost in
their training and inference phases. Moreover, the high computational
complexity of these models causes high energy consumption and memory usage
which makes their training and deployment difficult and even sometimes
infeasible. Thus, reducing the computational complexity of large deep learning
models is crucial.

On the other hand, there has been some efforts in manually redesigning smaller
models with similar accuracy as large models which often require more
complicated training. In image classification small models such as MobileNet
(Howard et al., 2017) have a similar accuracy as ResNet He et al. (2016), and
in language models, DistilBERT (Sanh et al., 2019) shows close performance to
BERT. Meanwhile there have been some efforts in designing models automatically
such as Liu et al. (2018); Zoph et al. (2018). Other methods include those
preserving the baseline model’s architecture while modifying computations e.g.
compressing large models using sparse estimation Luo et al. (2017);
Ramakrishnan et al. (2020); Furuya et al. (2022), or simplifying computations
by running on low-precision number formats Jacob et al. (2018); Wu et al.
(2020). Some researchers are even pushing frontiers by storing weights and
reducing activation to binary (Hubara et al., 2016) or ternary numbers (Li et
al., 2021).

Training large models are compute intensive using single-precision floating
point. This is why hardware manufacturers such as NVIDIA, Google, Transcent,
and Huawei started supporting hardware for low-precision number formats such
as Bfloat, float16, and int8. Recently researchers try to map single-precision
computations on lower bits, see Zhang et al. (2020); Zhao et al. (2021);
Ghaffari et al. (2022).

Majority of the literature on SGD assumes convex loss function. We weaken this
assumption by considering quasi-convex class of loss functions that include
convex functions as special case. One of the first works on quasi-convex
optimization is Kiwiel and Murty (1996), where is proven that the gradient
descent algorithm converges to a stationary point. Later, in Kiwiel (2001),
the differentiability hypothesis is removed and the convergence result is
shown using quasi-subgradients. In the case of perturbed SGD, in Hu et al.
(2015) the authors are able to deal with bounded biased perturbation on the
quasi-subgradient computation. In a subsequent work Hu et al. (2016) analyzed
the stochastic setting. Recently, Zhang et al. (2022) studied the low-
precision SGD for strongly convex loss functions where the authors used
Langevin dynamics. In comparison, our work differs in two aspects (i) we
assume quasi-convexity, (ii) our setup adds noise to the SGD and this allows
for less stringent assumptions on the noise and its distribution.

##  3 Preliminaries

We start with some preliminary notations about quasi-convexity and floating
point number formats in the sequel.

###  3.1 Quasi-convexity

######  Definition 3.1.

A function $f:{\rm I\\!R}^{d}\rightarrow{\rm I\\!R}$ is said to be quasi-
convex if $\forall a\in{\rm I\\!R}$, $f^{-1}[(-\infty,a)]=\\{\mathbf{w}\in{\rm
I\\!R}^{d}|\,f(\mathbf{w})\in(-\infty,a)\\}={\cal S}_{f,a}$ is convex.

######  Definition 3.2.

Given a quasi-convex function $f:{\rm I\\!R}^{d}\rightarrow{\rm I\\!R}$, the
quasi-subgradient of $f$ at $\mathbf{w}\in{\rm I\\!R}^{d}$ is defined as
$\bar{\partial}^{*}f(\mathbf{w})=\\{g\in{\rm I\\!R}^{d}\mid\langle
g,\mathbf{w}^{\prime}-\mathbf{w}\rangle\leq
0,\;\forall\mathbf{w}^{\prime}\in{\cal S}_{f,f(\mathbf{w})}\\}$

In what follows, the optimal value and optimal set of a function $f$ on a set
$\mathbf{\Omega}$ are respectively denoted by $f^{*}$ and
$\mathbf{\Omega}^{*}$, i.e.
$f^{*}=\inf_{\mathbf{w}\in\mathbf{\Omega}}f(\mathbf{w})$ and
$\mathbf{\Omega}^{*}=\operatornamewithlimits{argmin}_{\mathbf{w}\in\mathbf{\Omega}}f(\mathbf{w}).$

######  Definition 3.3.

Let $p>0$ and $L>0$. $f:{\rm I\\!R}^{d}\rightarrow{\rm I\\!R}$ is said to
satisfy the H$\ddot{\text{o}}$lder condition of order $p$ with constant $L$ if

$f(\mathbf{w})-f^{*}\leq
L[\operatorname*{dist}(\mathbf{w},\mathbf{\Omega}^{*})]^{p}$

where
$\operatorname*{dist}(\mathbf{w},\mathbf{w}^{\prime})=\min_{\mathbf{w}^{\prime}}\|\mathbf{w}-\mathbf{w}^{\prime}\|$
where $\|\cdot\|$ denotes the Euclidean norm.

###  3.2 Floating points

A base $\beta\in\mathbb{N}$, with precision $t\in\mathbb{N}$, and exponent
range $[e_{\min},e_{\max}]\subset\mathbb{Z}$ define a floating point system
$\mathbb{F}$, where an element $y\in\mathbb{F}$ can be represented as

$\displaystyle y=\pm m\times\beta^{e-t},$ (1)

where $m\in\mathbb{Z}$, $0\leq m<\beta^{t}$, and $e\in[e_{\min},e_{\max}]$.

For an $x\in[\beta^{e_{\min}-t},\beta^{e_{\max}}(1-\beta^{-t})]$, let the
float projection function be
$\operatorname{fl}(x):=\mathsf{P}_{\mathbb{F}}(x)$, then for
$x,y\in\mathbb{F}$, the rounding error for basic operations
$\operatorname{op}\in\\{+,-,\times,/\\}$, is

$\displaystyle\operatorname{fl}(x\operatorname{op}y)=(x\operatorname{op}y)(1+\delta_{0}),$
(2)

where the error is bounded by $\delta_{0}\leq\beta^{1-t}$ .

When trying to compute a subgradient $g\in\partial f(w)$ for a
$w\in\mathbb{F}$ the error is bounded to

$\displaystyle\operatorname{fl}(g)=g(1+\delta_{1}),$

where $|\delta_{1}|\leq c\delta_{0}$ and $c>0$ depends on the number of
operations needed for computing such subgradient. A step of subgradient
descent in floating point in ${\rm I\\!R}^{d}$ is:

$\displaystyle\mathbf{w}_{k+1}$
$\displaystyle=\left\\{\mathbf{w}_{k}-\eta[\mathbf{g}_{k}(1+\boldsymbol{\delta}_{1k})]\right\\}(1+\boldsymbol{\delta}_{2k}),$

where we suppose $\eta\in\mathbb{F},$
$\left\lVert\boldsymbol{\delta}_{1k}\right\rVert\leq c\delta_{0}\sqrt{d}$ and
$\left\lVert\boldsymbol{\delta}_{2k}\right\rVert\leq\delta_{0}\sqrt{d}$ where
$d$ is the dimension of $\boldsymbol{\delta}$. We can reformulate it in terms
of absolute error

$\displaystyle\mathbf{w}_{k+1}$
$\displaystyle=\mathbf{w}_{k}-\eta(\mathbf{g}_{k}+\mathbf{r}_{k})+\mathbf{s}_{k},$

and if the norm of the subgradient $\mathbf{g}_{k}$ and $\mathbf{w}_{k+1}$ is
bounded, then so are $\left\lVert\mathbf{r}_{k}\right\rVert\leq R$ and
$\left\lVert\mathbf{s}_{k}\right\rVert\leq S$. Note that the infinity norm of
the errors are bounded

$\|\delta_{1k}\|_{\infty}\leq
c\delta_{0},\qquad\|\delta_{2k}\|_{\infty}\leq\delta_{0},$

so

${R}^{2}\leq c\delta_{0}\left\lVert\mathbf{g}_{k}\right\rVert,\quad
S^{2}\leq\delta_{0}\left\lVert\mathbf{w}_{k}\right\rVert.$

##  4 Main results

Although our study is mainly motivated by training deep learning models and
floating point errors, they can be applied elsewhere.

###  4.1 Deterministic analysis

Let $\mathsf{P}_{\Omega}(\cdot)$ be the projection operator over
$\mathbf{\Omega}$. We start with adapting and improving the results of Hu et
al. (2015) in the presence of error in the summation

######  Theorem 4.1.

Let $f:{\rm I\\!R}^{d}\rightarrow{\rm I\\!R}$ be a quasi-convex function
satisfying the H$\ddot{\text{o}}$lder condition of order $p$ and constant $L$.
Let
$\mathbf{w}_{k+1}=\mathsf{P}_{\Omega}(\mathbf{w}_{k}-\eta\hat{g}_{k}+\mathbf{s}_{k})$
where $\mathbf{\Omega}\subset{\rm I\\!R}^{d}$ is compact, $c$ is the diameter
of $\Omega$, and
$\hat{\mathbf{g}}_{k}=\frac{\mathbf{g}_{k}}{\|\mathbf{g}_{k}\|}+\mathbf{r}_{k}$,
with $\mathbf{g}_{k}\in\bar{\partial}^{*}f(\mathbf{w}_{k})$,
$\|\mathbf{r}_{k}\|<R<1,\;\|\mathbf{s}_{k}\|\leq S$. Then

$\liminf_{k\rightarrow\infty}f(\mathbf{w}_{k})\leq f^{*}+L\Gamma^{p}(c),$

where

$\Gamma(c)=\frac{\eta}{2}\left[1+\left(R+\frac{S}{\eta}\right)^{2}\right]\bigvee\left[\frac{\eta}{2}\left\\{1-\left(R+\frac{S}{\eta}\right)^{2}\right\\}+c\left(R+\frac{S}{\eta}\right)\right].$

See the Appendix for the proof.
Remark: Unlike Hu et al. (2015), decreasing $\eta$ does not decrease the error
bound always, so we can derive its optimal value by minimizing the bound with
respect to $\eta$.

Define

$\eta_{1}=\frac{S}{\sqrt{1+R^{2}}},\quad\eta_{2}=\sqrt{\frac{S(c-2S)}{1-R^{2}}},\quad\eta_{3}=\frac{c-S}{R}$

######  Corollary 4.1.1.

The optimal choice for the step size $\eta$ that minimizes the error bound in
Theorem 4.1 is reached in at least one of this 3 points
$\\{\eta_{1},\eta_{2},\eta_{3}\\}$.

The next result presents a finite iteration version of the previous result.
The effect of the number of iterations $K$, and the starting point
$\mathbf{w}_{0}$ are clearly reflected in the bound for
$\min_{k<K}f(\mathbf{w}_{k})$.

######  Theorem 4.2.

Let $f:{\rm I\\!R}^{d}\rightarrow{\rm I\\!R}$ be a quasi-convex function
satisfying the H$\ddot{\text{o}}$lder condition of order $p$ and constant $L$.
Let $\mathbf{w}^{\prime}_{k+1}=\mathbf{w}_{k}-\eta\hat{\mathbf{g}}_{k}$ and
$\mathbf{w}_{k+1}=\mathbf{w}^{\prime}_{k+1}+\mathbf{s}_{k}$ where
$\hat{\mathbf{g}}_{k}=\frac{\mathbf{g}_{k}}{\left\lVert\mathbf{g}_{k}\right\rVert}+\mathbf{r}_{k}$,
where $\mathbf{g}_{k}\in\bar{\partial}^{*}f(\mathbf{w}_{k})$,
$\|\mathbf{r}_{k}\|<R,\;\|\mathbf{s}_{k}\|\leq S.$ Then,

$\min_{k<K}f(\mathbf{w}_{k})\leq f^{*}+L\left[\Gamma(c_{0})+\frac{c_{0}}{2\eta
K}\right]^{p},$

with $c_{0}=\|\mathbf{w}_{0}-\mathbf{w}^{*}\|.$

See the Appendix for the proof.

###  4.2 Stochastic analysis

Here, we present the stochastic counterpart of Theorem 4.1. The theorem
requires only mild conditions on the first two moments of the errors. We start
by defining the notion of stochastic quasi-subgradient.

######  Definition 4.1.

Let $\mathbf{w}$ and $\mathbf{w}^{\prime}$ be $d$-dimensional random vectors
defined on the probability space $(\mathcal{W},{\cal F},\mathcal{P})$ and
$f:{\rm I\\!R}^{d}\rightarrow{\rm I\\!R}$ be a measurable quasi-convex
function. Then $\mathbf{g}(\mathbf{w})$ is called a unit noisy quasi-
subgradient of $f$ at $\mathbf{w}$ if
$\|\mathbf{g}(\mathbf{w})\|\stackrel{{\scriptstyle a.s.}}{{=}}1$ and
$\mathcal{P}\left\\{{\cal
S}_{f,f(\mathbf{w})}\cap\mathcal{A}_{\mathbf{w}}\neq\emptyset\right\\}=0,$
where
$\mathcal{A}_{\mathbf{w}}=\\{\mathbf{w}^{\prime}:\langle\mathbf{g}(\mathbf{w}),\mathbf{w}^{\prime}-\mathbf{w}\rangle>0\\}\cdot$

Thus, inspired by results of Hu et al. (2016), we prove the following theorem
that take into account both randomness in the gradient and the computation
numerical error.

######  Theorem 4.3.

Let $f:{\rm I\\!R}^{d}\rightarrow{\rm I\\!R}$ be a continuous quasi-convex
function satisfying the H$\ddot{\text{o}}$lder condition of order $p$ and
constant $L$ . Let
$\mathbf{w}_{k+1}=\mathsf{P}_{\Omega}[\mathbf{w}_{k}-\eta(\hat{\mathbf{g}}_{k}+\mathbf{r}_{k})+\mathbf{s}_{k}]$
where $\mathbf{\Omega}$ is a convex closed set, $\hat{\mathbf{g}}_{k}$ is a
unit noisy quasi-subgradient of $f$ at $\mathbf{w}_{k}$, $\mathbf{r}_{k}$’s
are i.i.d. random vectors with ${\rm
I\\!E}\left\\{\mathbf{r}_{k}\right\\}=\mathbf{0}$ and ${\rm
I\\!E}\left\\{\|\mathbf{r}_{k}\|^{2}\right\\}=d\sigma^{2}_{r}$, and similarly
$\mathbf{s}_{k}$’s are i.i.d random vectors with ${\rm
I\\!E}\left\\{\mathbf{s}_{k}\right\\}=\mathbf{0}$ and ${\rm
I\\!E}\left\\{\|\mathbf{s}_{k}\|^{2}\right\\}=d\sigma^{2}_{s}$. Further assume
that $\hat{\mathbf{g}}_{k}$, $\mathbf{s}_{k}$, and $\mathbf{r}_{k}$ are
uncorrelated. Then,

$\liminf_{k\rightarrow\infty}f(\mathbf{w}_{k})\leq
f^{*}+L\left[\frac{\eta}{2}(1+d\sigma^{2}_{r})+\frac{d\sigma^{2}_{s}}{2\eta}\right]^{p}\quad
a.s.$

See the Appendix for the proof.

Figure 3: A two dimensional $\left\lVert\mathbf{w}\right\rVert^{0.2}$ quasi-
convex function (top panel), and the SGD trace plot confirming the stochastic
and deterministic bounds hold (bottom panel).

Similar to Corollary 4.1.1 one can derive the optimal step size.

######  Corollary 4.3.1.

The optimal step size $\eta$ that minimizes the error bound in Theorem 4.3 is
$\eta^{*}=\sqrt{\frac{d\sigma^{2}_{s}}{d\sigma^{2}_{r}+1}}.$

Remark: It immediately follows the optimal step size is
$\frac{\sigma_{s}}{\sigma_{r}}$ for large $d$.

##  5 Experiments

We performed two types of experiments, a simple quasi-convex function and a
logistic regression on MNIST dataset.

###  5.1 Simple quasi-convex function

To asses the bounds obtained in our theorems we start with a simple quasi-
convex function that exactly satisfy the Holder’s condition. We chose
$f(\mathbf{w})=3\|\mathbf{w}\|^{0.2}$ where $\mathbf{w}\in{\rm I\\!R}^{40}$.
In this example, the parameters of Holder’s condition are $p=0.2$ and $L=3$.
We added noise to the gradients and to the weight update denoted by
$\|\mathbf{r}_{k}\|$ and $\|\mathbf{s}_{k}\|$ respectively. This noise has a
uniform distribution $\mathbf{r}_{ki}\sim U(-B_{r},B_{r}),$ and $s_{ki}\sim
U(-B_{s},B_{s})$. Figure 3 shows the stochastic and deterministic bound for
this experiment. Note that, the theoretical bounds holds in both stochastic
and deterministic cases.

###  5.2 Logistic regression

Here, we present experimental results of logistic regression on the first two
principal components of MNIST dataset. For this experiment, we need to
estimate the parameters of the Holder’s condition for the loss function in
order to compute the bounds. To do so, the Holder’s parameters $p$ and $L$ are
manually fitted to the loss function that is evaluated at different distances
from the optimal point, see Figure 4. The optimal point $\mathbf{w}^{*}$ in
our experiments is obtained using single-precision floating point gradient
descent (GD) method and is used as a reference to compute the parameters of
the bounds $f^{*}$ and $c$.

Figure 4:  The Holder’s parameters $p$ and $L$ are manually fitted to the loss
function that is evaluated at different distances from the optimal point. The
left panel is a linear fit with $p=1$ and $L=0.95$. The right panel
demonstrate the fit with $p=1.6$ and $L=0.85$. We used $p=1.6$ and $L=0.85$
for our experiments.

Computation of the gradients involves inner products that are computed by
multipliers and accumulators. The accumulator have numerical error relative to
its mantissa size. We tested our logistic regression setup using Bfloat number
format and reduced accumulator size. Also note that according to Theorem 4.3,
the values of $d\sigma^{2}_{s}$ and $d\sigma^{2}_{r}$ are required to compute
the bounds. Thus, in our experiments, we used empirical values of those
parameters to compute the bounds. Also note that we did not plot the
deterministic bounds for these experiments as they are too pessimistic.

Figure 5: Logistic regression trained using single-precision SGD and a fixed
learning rate.

In order to evaluate the Holder’s condition parameters, $p$ and $L$, estimated
as shown in Figure 4, we use a single-precision SGD to confirm if the bounds
hold. Figure 5 demonstrates that the loss trajectory (blue line) has a limit
point in the proximity of the optimal point of the convex loss function.
Figure 6 demonstrates the loss trajectory when both weight update and gradient
computations are performed using Bfloat number format. Note that Bfloat has 8
bit exponent and 7 bit mantissa and is used recently to train deep learning
models. The computations are performed using 15-bit accumulator mantissa.
Figure 7 shows the loss trajectory when the weight update is in single
precision and only gradient computations are performed using Bfloat number
format. In this experiment, the stochastic bound is numerically equal to the
single-precision SGD, indicating that the precision of weight update is more
important compared to the precision of the gradients.

Figure 6: Logistic regression trained using Bfloat SGD with accumulator size
of 15 ($\mathbf{s}_{k}\neq 0$ and $\mathbf{r}_{k}\neq 0$). Figure 7: Logistic
regression trained using Bfloat gradients with accumulator size of 15, and
single-precision weight update ($\mathbf{s}_{k}=0$ and $\mathbf{r}_{k}\neq
0$). Figure 8: Logistic regression trained using Bfloat gradients with
accumulator size of 10, and single-precision weight update ($\mathbf{s}_{k}=0$
and $\mathbf{r}_{k}\neq 0$).

Reducing the accumulator mantissa size has a direct effect on the convergence
of SGD. Figure 8 shows that stochastic bound is increased in the case of
10-bit accumulator size. In this experiment, the loss trajectory oscillates
more in the neighbourhood of the optimum point. This indicates the accumulator
size plays an important role in reducing the numerical errors of the low-
precision SGD computations, and consequently improves the convergence of SGD.

##  6 Conclusion

We have studied the convergence of low-precision floating-point SGD for quasi-
convex loss functions and extended some existing deterministic and stochastic
bounds for convex loss functions. In our theoretical setup, we considered
numerical errors for weight update and gradient computations. We have also
derived the optimal step size as a corollary of our theoretical results.
Furthermore, in our experiments, the effect of numerical errors on weight
update and gradient computations are demonstrated. Our experiments show that
the accumulator mantissa size plays a key role in reducing the numerical error
and improving the convergence of SGD. Although our experiments with logistic
regression are promising, extension of the experiments for more complex models
is an appealing direction as the future work.

## References

  * Brown et al. (2020) Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al.  Language models are few-shot learners.  _Advances in neural information processing systems_ , 33:1877–1901, 2020.
  * Furuya et al. (2022) Takashi Furuya, Kazuma Suetake, Koichi Taniguchi, Hiroyuki Kusumoto, Ryuji Saiin, and Tomohiro Daimon.  Spectral pruning for recurrent neural networks.  In _International Conference on Artificial Intelligence and Statistics_ , pages 3458–3482. PMLR, 2022.
  * Ghaffari et al. (2022) Alireza Ghaffari, Marzieh S Tahaei, Mohammadreza Tayaranian, Masoud Asgharian, and Vahid Partovi Nia.  Is integer arithmetic enough for deep learning training?  _arXiv preprint arXiv:2207.08822_ , 2022.
  * Goyal et al. (2022) Priya Goyal, Quentin Duval, Isaac Seessel, Mathilde Caron, Mannat Singh, Ishan Misra, Levent Sagun, Armand Joulin, and Piotr Bojanowski.  Vision models are more robust and fair when pretrained on uncurated images without supervision.  _arXiv preprint arXiv:2202.08360_ , 2022.
  * He et al. (2016) Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 770–778, 2016.
  * Howard et al. (2017) Andrew G Howard, Menglong Zhu, Bo Chen, Dmitry Kalenichenko, Weijun Wang, Tobias Weyand, Marco Andreetto, and Hartwig Adam.  Mobilenets: Efficient convolutional neural networks for mobile vision applications.  _arXiv preprint arXiv:1704.04861_ , 2017.
  * Hu et al. (2015) Yaohua Hu, Xiaoqi Yang, and Chee-Khian Sim.  Inexact subgradient methods for quasi-convex optimization problems.  _European Journal of Operational Research_ , 240(2):315–327, 2015.
  * Hu et al. (2016) Yaohua Hu, Carisa Yu, and Chong Li.  Stochastic subgradient method for quasi-convex optimization problems.  _Journal of nonlinear and convex analysis_ , 17:711–724, 01 2016.
  * Hubara et al. (2016) Itay Hubara, Matthieu Courbariaux, Daniel Soudry, Ran El-Yaniv, and Yoshua Bengio.  Binarized neural networks.  _Advances in neural information processing systems_ , 29, 2016.
  * Jacob et al. (2018) Benoit Jacob, Skirmantas Kligys, Bo Chen, Menglong Zhu, Matthew Tang, Andrew Howard, Hartwig Adam, and Dmitry Kalenichenko.  Quantization and training of neural networks for efficient integer-arithmetic-only inference.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 2704–2713, 2018.
  * Kiwiel and Murty (1996) Krzysztof Kiwiel and Katta Murty.  Convergence of the steepest descent method for minimizing quasiconvex functions.  _Journal of Optimization Theory and Applications_ , 89, 04 1996.  doi: 10.1007/BF02192649.
  * Kiwiel (2001) Krzysztof C. Kiwiel.  Convergence and efficiency of subgradient methods for quasiconvex minimization.  _Mathematical Programming_ , 90:1–25, 2001.
  * Li et al. (2021) Xinlin Li, Bang Liu, Yaoliang Yu, Wulong Liu, Chunjing Xu, and Vahid Partovi Nia.  S3: Sign-sparse-shift reparametrization for effective training of low-bit shift networks.  _Advances in Neural Information Processing Systems_ , 34:14555–14566, 2021.
  * Liu et al. (2018) Hanxiao Liu, Karen Simonyan, and Yiming Yang.  Darts: Differentiable architecture search.  _arXiv preprint arXiv:1806.09055_ , 2018.
  * Luo et al. (2017) Jian-Hao Luo, Jianxin Wu, and Weiyao Lin.  Thinet: A filter level pruning method for deep neural network compression.  In _Proceedings of the IEEE international conference on computer vision_ , pages 5058–5066, 2017.
  * Mahajan et al. (2018) Dhruv Mahajan, Ross Girshick, Vignesh Ramanathan, Kaiming He, Manohar Paluri, Yixuan Li, Ashwin Bharambe, and Laurens Van Der Maaten.  Exploring the limits of weakly supervised pretraining.  In _Proceedings of the European conference on computer vision (ECCV)_ , pages 181–196, 2018.
  * Polyak (1967) Boris Polyak.  A general method for solving extremum problems.  _Soviet Mathematics. Doklady_ , 8, 01 1967.
  * Radford et al. (2019) Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al.  Language models are unsupervised multitask learners.  _OpenAI blog_ , 1(8):9, 2019.
  * Ram et al. (2009) S. Sundhar Ram, A. Nedić, and V. V. Veeravalli.  Incremental stochastic subgradient algorithms for convex optimization.  _SIAM Journal on Optimization_ , 20(2):691–717, 2009.  doi: 10.1137/080726380.  URL https://doi.org/10.1137/080726380.
  * Ramakrishnan et al. (2020) Ramchalam Kinattinkara Ramakrishnan, Eyyub Sari, and Vahid Partovi Nia.  Differentiable mask for pruning convolutional and recurrent networks.  In _2020 17th Conference on Computer and Robot Vision (CRV)_ , pages 222–229. IEEE, 2020.
  * Sanh et al. (2019) Victor Sanh, Lysandre Debut, Julien Chaumond, and Thomas Wolf.  Distilbert, a distilled version of bert: smaller, faster, cheaper and lighter.  _arXiv preprint arXiv:1910.01108_ , 2019.
  * Schmidt et al. (2011) Mark Schmidt, Nicolas Roux, and Francis Bach.  Convergence rates of inexact proximal-gradient methods for convex optimization.  _Advances in neural information processing systems_ , 24, 2011.
  * Shoeybi et al. (2019) Mohammad Shoeybi, Mostofa Patwary, Raul Puri, Patrick LeGresley, Jared Casper, and Bryan Catanzaro.  Megatron-lm: Training multi-billion parameter language models using model parallelism.  _arXiv preprint arXiv:1909.08053_ , 2019.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  _Advances in neural information processing systems_ , 30, 2017.
  * Wu et al. (2020) Hao Wu, Patrick Judd, Xiaojie Zhang, Mikhail Isaev, and Paulius Micikevicius.  Integer quantization for deep learning inference: Principles and empirical evaluation.  _arXiv preprint arXiv:2004.09602_ , 2020.
  * Zhai et al. (2022) Xiaohua Zhai, Alexander Kolesnikov, Neil Houlsby, and Lucas Beyer.  Scaling vision transformers.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 12104–12113, 2022.
  * Zhang et al. (2022) Ruqi Zhang, Andrew Gordon Wilson, and Christopher De Sa.  Low-precision stochastic gradient langevin dynamics.  In _International Conference on Machine Learning_ , pages 26624–26644. PMLR, 2022.
  * Zhang et al. (2020) Xishan Zhang, Shaoli Liu, Rui Zhang, Chang Liu, Di Huang, Shiyi Zhou, Jiaming Guo, Qi Guo, Zidong Du, Tian Zhi, et al.  Fixed-point back-propagation training.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 2330–2338, 2020.
  * Zhao et al. (2021) Kang Zhao, Sida Huang, Pan Pan, Yinghan Li, Yingya Zhang, Zhenyu Gu, and Yinghui Xu.  Distribution adaptive int8 quantization for training cnns.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 35, pages 3483–3491, 2021.
  * Zoph et al. (2018) Barret Zoph, Vijay Vasudevan, Jonathon Shlens, and Quoc V Le.  Learning transferable architectures for scalable image recognition.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 8697–8710, 2018.

Supplementary Materials

##  7 Proofs

Let $\mathbf{w}\in{\rm I\\!R}^{d}$ and $r\in{\rm I\\!R}^{+}$. Define
$\mathbb{B}(\mathbf{w},r)=\left\\{\mathbf{w}^{\prime}\in{\rm
I\\!R}^{d}|\;\|\mathbf{w}^{\prime}-\mathbf{w}\|\leq r\right\\}$. Given that
$f$ is quasi-convex and satisfies a Holder condition, and $\mathbf{\Omega}$ is
a compact set, it follows that $\mathbf{\Omega}^{*}\neq\emptyset$ and
$f^{*}>-\infty$. We start with two technical lemmas needed for the proof of
Theorem 4.1.

######  Lemma 7.1.

Let $\mathbf{g}\in{\rm I\\!R}^{d}$ be a $d$-dimensional vector and
$R,C,B,\eta\in{\rm I\\!R}^{+}$ be real constants such that $\|\mathbf{g}\|=1$,
$R<1$ and $C>B$. Define
$F(\mathbf{w},\mathbf{r})=\eta\|\mathbf{g}+\mathbf{r}\|^{2}-2\langle\mathbf{w},\mathbf{g}+\mathbf{r}\rangle$
where $\mathbf{r},\mathbf{w}\,\in{\rm I\\!R}^{d}$. Consider the following
optimization problem,

$\displaystyle F^{*}=\max_{\mathbf{w},\mathbf{r}\in{\rm I\\!R}^{d}}\,$
$\displaystyle F(\mathbf{w},\mathbf{r}),\;$ (3) subject to:
$\displaystyle\langle\mathbf{g},\mathbf{w}\rangle\geq B,$
$\displaystyle\|\mathbf{r}\|^{2}\leq R^{2},$
$\displaystyle\|\mathbf{w}\|^{2}\leq C^{2}.$ (4)

Then

$F^{*}\leq\max\left\\{\eta\left(1+R^{2}\right)+2R\sqrt{\eta^{2}+C^{2}-2\eta
B}-2B,\eta\left(R^{2}-1\right)\right\\}.$

######  Corollary 7.0.1.

The upper bound in Lemma 7.1 is attained if $d\geq 2$.

######  Lemma 7.2.

(Lemma 6 of Kiwiel (2001)) Suppose $f(\cdot)$ satisfies an
H$\ddot{\text{o}}$lder condition on ${\rm I\\!R}^{d}$ with parameter $p$ and
constant $L$. If $\mathbb{B}(\mathbf{w}^{*},M)\subset{\cal
S}_{f,f(\mathbf{w})},$ then
$\langle\mathbf{w}-\mathbf{w}^{*},\mathbf{g}/\|\mathbf{g}\|\rangle\geq
M,\quad\forall\mathbf{g}\in\bar{\partial}^{*}f(\mathbf{w})$.

Theorem 4.1 is proved by contradiction using a standard argument for this type
of results. For the sake of simplicity, we prove the theorem assuming that
$S=0$. The proof for the general case, i.e. $S\neq 0$, is similar upon
noticing that
$\mathbf{w}_{k+1}=\mathsf{P}_{\Omega}\left[\mathbf{w}_{k}-\eta\left(\frac{\mathbf{g}_{k}}{\|\mathbf{g}_{k}\|}+\mathbf{r}_{k}+\frac{\mathbf{s}_{k}}{\eta}\right)\right]$
and replacing $R$ with $R+\frac{S}{\eta}$. Given that $\eta$ is assumed to be
fixed, this change does not cause any difficulty.

###  7.1 Proof of Theorem 4.1

###### Proof.

Given that $c$ is the diameter of $\mathbf{\Omega}$, the desired result
clearly holds if $\Gamma(c)\geq c$. Thus, assume $\Gamma(c)<c$. Suppose that
$\exists\
\delta>0,\;\bar{k}>0\;s.t.\,f(\mathbf{w}_{k})>f^{*}+L(\Gamma(c)+\delta)^{p}\quad\forall\,k>\bar{k}$
and $\mathbf{w}^{*}\in\mathbf{\Omega}^{*}$. Given that $f(\cdot)$ satisfies
the H$\ddot{\text{o}}$lder condition, we have for all $k>\bar{k}$

$f(\mathbf{w})-f^{*}\leq
L\operatorname*{dist}(\mathbf{w},\mathbf{\Omega}^{*})^{p}\leq
L(\Gamma(c)+\delta)^{p}<f(\mathbf{w}_{k})-f^{*},\qquad\forall\,\mathbf{w}\in\mathbb{B}(\mathbf{w}^{*},\Gamma(c)+\delta,)\quad,$

which implies that $\mathbb{B}(\mathbf{w}^{*},\Gamma(c)+\delta)\subset{\cal
S}_{f,f(\mathbf{w}_{k})},\;\forall\,k>\bar{k}$. Using Lemma 7.2

$\langle\frac{\mathbf{g}_{k}}{\|\mathbf{g}_{k}\|},\mathbf{w}_{k}-\mathbf{w}^{*}\rangle\geq\Gamma(c)+\delta,\quad\forall\,k>\bar{k},$

hence one can use Lemma 7.1 with
$\;B=\Gamma(c)+\delta,\,C=c,\,\mathbf{g}=\frac{\mathbf{g}_{k}}{\|\mathbf{g}_{k}\|},\,\mathbf{w}=\mathbf{w}^{*}-\mathbf{w}_{k},\,\mathbf{r}=\mathbf{r}_{k},\,R=R\,$
and $\eta=\eta$. This yields

$\langle\mathbf{w}_{k}-\mathbf{w}^{*},\mathbf{g}_{k}\rangle+\langle\mathbf{w}_{k}-\mathbf{w}^{*},\mathbf{r}_{k}\rangle-\frac{\eta}{2}\|\frac{\mathbf{g}_{k}}{\|\mathbf{g}_{k}\|}+\mathbf{r}_{k}\|^{2}\geq\min\left\\{\Gamma(c)+\delta-\frac{\eta}{2}\left(1+R^{2}\right)-R\sqrt{\eta^{2}+c^{2}-2\eta\left[\Gamma(c)+\delta\right]},\frac{\eta}{2}\left(1-R^{2}\right)\right\\}.$
(5)

It is shown that for $\delta$ is small enough

$\Gamma(c)+\delta-\frac{\eta}{2}\left(1+R^{2}\right)-R\sqrt{\eta^{2}+c^{2}-2\eta\left[\Gamma(c)+\delta\right]}<\frac{\eta}{2}\left(1-R^{2}\right).$

Given that $\Gamma(c)$ is the maximum of two terms, we show the inequality
holds for both terms, and hence for their maximum. If
$\Gamma(c)=\frac{\eta}{2}(1+R^{2})$, then

$\Gamma(c)+\delta-\frac{\eta}{2}\left(1+R^{2}\right)-R\sqrt{\eta^{2}+c^{2}-2\eta\left[\Gamma(c)+\delta\right]}=\delta-R\sqrt{\eta^{2}+c^{2}-2\eta\left[\Gamma(c)+\delta\right]}\leq
0\leq\frac{\eta}{2}\left(1-R^{2}\right),$ (6)

where the first inequality follows from the fact that we can choose $\delta$
arbitrarily small and second one from $R<1$. Otherwise,
$\Gamma(c)=\frac{\eta(1-R^{2})}{2}+Rc$, thus

$\displaystyle\left[\Gamma(c)+\delta-\frac{\eta}{2}\left(1+R^{2}\right)\right]^{2}$
$\displaystyle=\frac{\eta^{2}}{4}\left(1+R^{2}\right)^{2}+\left[\Gamma(c)+\delta\right]^{2}-\eta\left[\Gamma(c)+\delta\right]\left(1+R^{2}\right)$
$\displaystyle=\frac{\eta^{2}}{4}\left(1+R^{2}\right)^{2}+\left[\frac{\eta\left(1-R^{2}\right)}{2}+Rc+\delta\right]^{2}-\eta\left[\frac{\eta\left(1-R^{2}\right)}{2}+R\delta+\delta\right]\left(1+R^{2}\right)$
$\displaystyle=\frac{\eta^{2}}{4}\left(1+R^{2}\right)^{2}+\frac{\eta^{2}\left(1-R^{2}\right)^{2}}{4}+R^{2}c^{2}+\eta
Rc\left(1-R^{2}\right)-\frac{\eta^{2}\left(1-R^{4}\right)}{2}$
$\displaystyle\hskip 7.22743pt-\eta Rc\left(1+R^{2}\right)+\delta^{2}+2\delta
Rc+\delta\eta\left(1-R^{2}\right)-\delta\eta\left(1+R^{2}\right)$
$\displaystyle=\frac{\eta^{2}}{2}\left(1+R^{4}\right)+R^{2}c^{2}-2\eta
cR^{3}-\frac{\eta^{2}\left(1-R^{4}\right)}{2}+\delta^{2}+2\delta
Rc-2\delta\eta R^{2}$ $\displaystyle=R^{4}\eta^{2}+R^{2}c^{2}-2\eta
cR^{3}+\delta^{2}+2\delta Rc-2\delta\eta R^{2}$
$\displaystyle=R^{2}\left(c^{2}+\eta^{2}R^{2}-2\eta
Rc-2\eta\delta\right)+\delta^{2}+2\delta Rc$
$\displaystyle=R^{2}\left[\eta^{2}+c^{2}-\eta^{2}\left(1-R^{2}\right)-2\eta
Rc-2\eta\delta\right]+\delta^{2}+2\delta Rc$
$\displaystyle=R^{2}\left\\{\eta^{2}+c^{2}-2\eta\left[\Gamma(c)+\delta\right]\right\\}+\delta^{2}+2\delta
Rc.$

Taking the square root of the first and last term

$\displaystyle\Gamma(c)+\delta-\frac{\eta}{2}\left(1+R^{2}\right)=\sqrt{R^{2}\left\\{\eta^{2}+c^{2}-2\eta\left[\Gamma(c)+\delta\right]\right\\}+\delta^{2}+2\delta
Rc}.$ (7)

Then, the first term in the $\min$ operator of (5) is

$\displaystyle\Gamma(c)+\delta-\frac{\eta}{2}\left(1+R^{2}\right)-R\sqrt{\eta^{2}+c^{2}-2\eta\left[\Gamma(c)+\delta\right]}$
$\displaystyle=\sqrt{R^{2}\left\\{\eta^{2}+c^{2}-2\eta\left[\Gamma(c)+\delta\right]\right\\}+\delta^{2}+2\delta
Rc}$ (8) $\displaystyle\hskip
7.22743pt-R\sqrt{\eta^{2}+c^{2}-2\eta\left[\Gamma(c)+\delta\right]}\xmapsto{\delta\rightarrow
0}0.$

Hence, if $\delta$ is small enough

$\Gamma(c)+\delta-\frac{\eta}{2}\left(1+R^{2}\right)-R\sqrt{\eta^{2}+c^{2}-2\eta\left[\Gamma(c)+\delta\right]}\leq\frac{\eta}{2}\left(1-R^{2}\right).$
(9)

If $\delta$ is small enough, Eq. (5), (6) and (9) yield

$\langle\mathbf{w}_{k}-\mathbf{w}^{*},\mathbf{g}_{k}\rangle+\langle\mathbf{w}_{k}-\mathbf{w}^{*},\mathbf{r}_{k}\rangle-\frac{\eta}{2}\|\frac{\mathbf{g}_{k}}{\|\mathbf{g}_{k}\|}+\mathbf{r}_{k}\|^{2}\geq\Gamma(c)+\delta-\frac{\eta}{2}\left(1+R^{2}\right)-R\sqrt{\eta^{2}+c^{2}-2\eta\left[\Gamma(c)+\delta\right]}.$
(10)

It follows from the argument leading to Eq. (7) that if
$\Gamma(c)\geq\frac{\eta(1-R^{2})}{2}+Rc$,

$\Gamma(c)+\delta-\frac{\eta}{2}(1+R^{2})\geq\sqrt{R^{2}\left\\{\eta^{2}+c^{2}-2\eta\left[\Gamma(c)+\delta\right]\right\\}+\delta^{2}+2\delta
Rc}.$ (11)

Having noted that $\Gamma(c)>\frac{\eta}{2}$, we obtain
$\eta^{2}+c^{2}-2\eta(\Gamma(c)+\delta)<c^{2}$. This yields

$\displaystyle
R^{2}\left\\{\eta^{2}+c^{2}-2\eta\left[\Gamma(c)+\delta\right]\right\\}+\delta^{2}+2\delta
Rc$
$\displaystyle=\left\\{R\sqrt{\eta^{2}+c^{2}-2\eta\left[\Gamma(c)+\delta\right]}+\delta\right\\}^{2}$
$\displaystyle\hskip 7.22743pt-2\delta
R\sqrt{\eta^{2}+c^{2}-2\eta\left[\Gamma(c)+\delta\right]}+2R\delta c$ (12)
$\displaystyle\geq\left\\{R\sqrt{\eta^{2}+c^{2}-2\eta\left[\Gamma(c)+\delta\right]}+\delta\right\\}^{2}.$

It follows from Eq. (10), (11) and (12) that

$\langle\mathbf{w}_{k}-\mathbf{w}^{*},\mathbf{g}_{k}\rangle+\langle\mathbf{w}_{k}-\mathbf{w}^{*},\mathbf{r}_{k}\rangle-\frac{\eta}{2}\|\frac{\mathbf{g}_{k}}{\|\mathbf{g}_{k}\|}+\mathbf{r}_{k}\|^{2}\geq\delta,$

leading to

$\|\mathbf{w}_{k+1}-\mathbf{w}^{*}\|\leq\|\mathbf{w}_{k}-\mathbf{w}^{*}\|^{2}-2\eta\left({\langle\mathbf{w}_{k}-\mathbf{w}^{*},\mathbf{g}_{k}\rangle+\langle\mathbf{w}_{k}-\mathbf{w}^{*},\mathbf{r}_{k}\rangle-\frac{\eta}{2}\|\frac{\mathbf{g}_{k}}{\|\mathbf{g}_{k}\|}+\mathbf{r}_{k}\|^{2}}\right)\leq\|\mathbf{w}_{k}-\mathbf{w}^{*}\|^{2}-2\eta\delta,$

where we used the definition of $\mathbf{w}_{k+1}$ and the property of the
projection map $\mathsf{P}_{\Omega}(\cdot)$ in the first inequality.

Thus

$\|\mathbf{w}_{k+1}-\mathbf{w}^{*}\|^{2}\leq\|\mathbf{w}_{k}-\mathbf{w}^{*}\|-2\eta\delta\leq\ldots\leq\|\mathbf{w}_{0}-\mathbf{w}^{*}\|-2\eta(k-\bar{k}+1)\delta,\quad\forall\,k>\bar{k}.$
(13)

The desired result then follows upon noticing that the upper bound tends to
$-\infty$ as $k$ tends to $+\infty$ which leads to a contradiction.

∎

####  7.1.1 Intuition behind Lemma 7.1

By scrutinizing the proof of our Theorem 4.1 and Theorem 3.1 of (Hu et al.,
2015), we notice that the key to the proof is

$\displaystyle\|\mathbf{w}_{k+1}-\mathbf{w}^{*}\|^{2}$
$\displaystyle\leq\|\mathbf{w}_{k}-t\hat{\mathbf{g}}_{k}-\mathbf{w}^{*}\|^{2}=\|\mathbf{w}_{k}-\mathbf{w}^{*}\|^{2}-2\eta\langle\mathbf{w}_{k}-\mathbf{w}^{*},\frac{\mathbf{g}_{k}}{\|\mathbf{g}_{k}\|}\rangle-2\eta\langle\mathbf{w}_{k}-\mathbf{w}^{*},\mathbf{r}_{k}\rangle+\eta^{2}\|\frac{\mathbf{g}_{k}}{\|\mathbf{g}_{k}\|}+\mathbf{r}_{k}\|^{2}$
$\displaystyle=\|\mathbf{w}_{k}-\mathbf{w}^{*}\|^{2}-2\eta\left({B+\langle\mathbf{w}_{k}-\mathbf{w}^{*},\mathbf{r}_{k}\rangle-\frac{\eta}{2}\|\frac{\mathbf{g}_{k}}{\|\mathbf{g}_{k}\|}+\mathbf{r}_{k}\|^{2}}\right),$

where $B$ should be such that
$\exists\delta^{\prime}>0\;|\;\left({B+\langle\mathbf{w}_{k}-\mathbf{w}^{*},\mathbf{r}_{k}\rangle-\frac{\eta}{2}\|\frac{\mathbf{g}_{k}}{\|\mathbf{g}_{k}\|}+\mathbf{r}_{k}\|^{2}}\right)>\delta^{\prime}$.
The final bound will significantly depend on $B$. More precisely, greater $B$
values lead to greater, hence worse, bounds.

$\mathbf{g}$$\mathbf{w}^{*}-\mathbf{w}$$\mathbf{r}$•$\mathbf{w}$$\mathbf{w}^{*}$
Figure 9: Given $\mathbf{w}$ and $\mathbf{w}^{*}$, $\mathbf{g}$ needs to have
positive scalar product with $\mathbf{w}^{*}-\mathbf{w}$ (gray zone). So it s
not possible for $\mathbf{r}$ to be opposite to $\mathbf{w}^{*}-\mathbf{w}$
and colinear with $\mathbf{g}$ at the same time.
$\eta\mathbf{g}$$\mathbf{w}^{*}-(\mathbf{w}+\eta\mathbf{g})$$\mathbf{r}$$\mathbf{w}^{*}-\mathbf{w}$$\mathbf{r}$•$\mathbf{w}$$\mathbf{w}^{*}$
Figure 10: Given $\mathbf{w}$, $\mathbf{w}^{*}$ and $\mathbf{g}$ the worst
case seems to be $-\mathbf{r}=\mathbf{w}^{*}-(\mathbf{w}+\eta\mathbf{g})$,
scaled to have norm $R$.

In Hu et al. (2015) the authors use

$|\mathbf{w}_{k}-\mathbf{w}^{*}\|^{2}-2\eta\left(B+\langle\mathbf{w}_{k}-\mathbf{w}^{*},\mathbf{r}_{k}\rangle-\frac{\eta}{2}\|\frac{\mathbf{g}_{k}}{\|\mathbf{g}_{k}\|}+\mathbf{r}_{k}\|^{2}\right)\leq\|\mathbf{w}_{k}-\mathbf{w}^{*}\|^{2}-2\eta\left(B-Rc-\frac{\eta}{2}(1+R)^{2}\right),$
(14)

and then choose $B=Rc+\frac{\eta}{2}(1+R)^{2}+\delta$. To obtain Eq. (14), Hu
et al. (2015) uses

$\displaystyle\langle\mathbf{w}_{k}-\mathbf{w}^{*},\mathbf{r}_{k}\rangle\geq-\|\mathbf{w}_{k}-\mathbf{w}^{*}\|\|\mathbf{r}_{k}\|,$
(15)
$\displaystyle\|\frac{\mathbf{g}_{k}}{\|\mathbf{g}_{k}\|}+\mathbf{r}_{k}\|\leq\|\frac{\mathbf{g}_{k}}{\|\mathbf{g}_{k}\|}\|+\|\mathbf{r}_{k}\|.$
(16)

The equality holds in (15) and (16) if
$\mathbf{r}_{k}=-\alpha(\mathbf{w}_{k}-\mathbf{w}^{*})$ and
$\mathbf{r}_{k}=\beta\mathbf{g}_{k}$ with $\alpha,\;\beta>0$, respectively.
This then implies that
$\langle\mathbf{g}_{k},\mathbf{w}_{k}-\mathbf{w}^{*}\rangle=\langle\mathbf{r}_{k}/\beta,-\mathbf{r}_{k}/\alpha\rangle=-\frac{1}{\alpha\beta}\|\mathbf{r}_{k}\|^{2}<0$,
which contradicts the definition of quasi sub-differential for
$\mathbf{g}_{k}\in\bar{\partial}^{*}f(\mathbf{w}_{k})$. This means that
equality cannot hold in Eq. (15) and (16) simultaneously. That is why, we used
Lemma 7.1 instead of Eq. (14) to prove Theorem 4.1. Figure 9 provides the
insight for our argument.

Figure 10 shows that the worst case scenario happens if $\mathbf{r}_{k}$ is
collinear with
$\mathbf{w}_{k}+\eta\frac{\mathbf{g}_{k}}{\|\mathbf{g}_{k}\|}-\mathbf{w}^{*}$.
The proof is given in Section 7.1.2.

####  7.1.2 Proof of Lemma 7.1

Loosely speaking, the idea is to use KKT’s conditions and to prove that the
optimal solutions are on the boundary of the feasible set.

###### Proof.

The gradient of the objective function is

$\nabla
F(\cdot)=(-2(\mathbf{g}+\mathbf{r}),2\eta(\mathbf{g}+\mathbf{r})-2\mathbf{w}).$

The objective function is convex so the optimum is reached in at least a point
on the boundary of the feasible region. We recall that the weak Slater’s
conditions for Problem 3 are satisfied if
$\exists\,\mathbf{r},\mathbf{w}\in{\rm I\\!R}^{d}$ such that

$\displaystyle\langle\mathbf{g},\mathbf{w}\rangle\geq B,$
$\displaystyle\|\mathbf{r}\|^{2}<R^{2},$
$\displaystyle\|\mathbf{w}\|^{2}<C^{2}.$

These conditions are fulfilled by $\mathbf{r}=0$ and $\mathbf{w}=B\mathbf{g}$,
hence we can use the KKT’s equations to obtain necessary conditions on the
optimal solutions of Problem (3). From the KKT’s condition on the gradient
component with respect to $\mathbf{r}$

$\displaystyle\frac{\partial
F}{\partial\mathbf{r}}=\lambda\frac{\partial(\|\mathbf{r}\|^{2}-R^{2})}{\partial\mathbf{r}}$
$\displaystyle\Leftrightarrow 2\eta(\mathbf{g}+\mathbf{r})-2\mathbf{w}=\lambda
2\mathbf{r}$

with $\lambda\in{\rm I\\!R}^{+}$.

If $\eta=\lambda$, then $\mathbf{w}=\eta\mathbf{g}$, and thus the objective
function is simplified to $\eta+\eta\|\mathbf{r}\|^{2}-2\eta$. In this case,
any $\mathbf{r}$ such that $\|\mathbf{r}\|=R$ achieves the optimal value,
being $\eta(R^{2}-1)$. Otherwise,

$\mathbf{r}=\frac{\mathbf{w}-\eta\mathbf{g}}{\eta-\lambda}.$ (17)

The objective function can be written as

$F(\mathbf{r},\mathbf{w})=\eta+2\langle\eta\mathbf{g}-\mathbf{w},\mathbf{r}\rangle+\eta\|\mathbf{r}\|^{2}-2\langle\mathbf{w},\mathbf{g}\rangle.$

Let $(\mathbf{r}^{*},\mathbf{w}^{*})$ be an optimal solution of Problem (3).
We prove the following facts by contradiction:

  * a)

$\langle\mathbf{r}^{*},\eta\mathbf{g}-\mathbf{w}^{*}\rangle\geq 0.$

Assume $\langle\mathbf{r}^{*},\eta\mathbf{g}-\mathbf{w}^{*}\rangle<0$.
Consider $\tilde{\mathbf{r}}=-\mathbf{r}^{*}$, the solution
$(\tilde{\mathbf{r}},\mathbf{w}^{*})$ is feasible since
$\|\tilde{\mathbf{r}}\|=\|\mathbf{r}^{*}\|\leq R$. Moreover,
$\langle\eta\mathbf{g}-\mathbf{w}^{*},\tilde{\mathbf{r}}\rangle>0>\langle\eta\mathbf{g}-\mathbf{w}^{*},\mathbf{r}^{*}\rangle$,
this yields

$F(\mathbf{r}^{*},\mathbf{w}^{*})-F(\tilde{\mathbf{r}},\mathbf{w}^{*})=\langle\eta\mathbf{g}-\mathbf{w}^{*},\mathbf{r}^{*}\rangle-\langle\eta\mathbf{g}-\mathbf{w}^{*},\tilde{\mathbf{r}}\rangle<0.$

The last inequality violates the optimality of $\mathbf{r}^{*}$, therefore the
claim is proved.

  * b)

$\|\mathbf{r}^{*}\|=R.$

Assume $\|\mathbf{r}^{*}\|<R$. Consider
$\tilde{\mathbf{r}}=R\frac{\mathbf{r}^{*}}{\|\mathbf{r}^{*}\|}$, using point
(a) we have

$\langle\eta\mathbf{g}-\mathbf{w}^{*},\tilde{\mathbf{r}}\rangle-\langle\eta\mathbf{g}-\mathbf{w}^{*},r^{*}\rangle=\left(\frac{R}{\|\mathbf{r}^{*}\|}-1\right)\langle\eta\mathbf{g}-\mathbf{w}^{*},\mathbf{r}^{*}\rangle\geq
0.$

Moreover, $R=\|\tilde{\mathbf{r}}\|>\|\mathbf{r}^{*}\|$, hence

$F(\mathbf{r}^{*},\mathbf{w}^{*})-F(\tilde{\mathbf{r}},\mathbf{w}^{*})=2\left[\left(\frac{R}{\|\mathbf{r}^{*}\|}-1\right)\langle\eta\mathbf{g}-\mathbf{w}^{*},\mathbf{r}^{*}\rangle\right]+\eta(\|\mathbf{r}^{*}\|-R)<0.$

The last inequality violates the optimality of $\mathbf{r}^{*}$ and hence the
result follows.

  * c)

$\langle\mathbf{w}^{*},\mathbf{g}\rangle=B.$

Assume $\langle\mathbf{w}^{*},\mathbf{g}\rangle>B$. Then
$\tilde{\mathbf{w}}=\mathbf{w}^{*}-(\langle\mathbf{w}^{*},\mathbf{g}\rangle-B)\mathbf{g}$,
$(\mathbf{r}^{*},\tilde{\mathbf{w}})$ is a feasible point since

$\displaystyle\|\tilde{\mathbf{w}}\|^{2}=\|\mathbf{w}^{*}\|^{2}+(\langle\mathbf{w}^{*},\mathbf{g}\rangle-B)^{2}-2\left[\langle\mathbf{w}^{*},\mathbf{g}\rangle-B\right]\langle\mathbf{w}^{*},\mathbf{g}\rangle<\|\mathbf{w}^{*}\|^{2}$

and $\langle\tilde{\mathbf{w}},\mathbf{g}\rangle=B$.

$\displaystyle
F(\mathbf{w}^{*},\mathbf{r}^{*})-F(\tilde{\mathbf{w}},\mathbf{r}^{*})=$
$\displaystyle
2\langle\tilde{\mathbf{w}}-\mathbf{w}^{*},\mathbf{g}+\mathbf{r}^{*}\rangle=-2\langle\left[\langle\mathbf{w}^{*},\mathbf{g}\rangle-B\right]\mathbf{g},\mathbf{g}+\mathbf{r}^{*}\rangle$
$\displaystyle=$
$\displaystyle-2(\langle\mathbf{w}^{*},\mathbf{g}\rangle-B)-2\langle[\langle\mathbf{w}^{*},\mathbf{g}\rangle-B]\mathbf{g},\mathbf{r}^{*}\rangle$
$\displaystyle\leq$
$\displaystyle-2[\langle\mathbf{w}^{*},\mathbf{g}\rangle-B](1-\|\mathbf{g}\|\|\mathbf{r}^{*}\|)<0.$

The last inequality violates the optimality of $\mathbf{w}^{*}$, this
completes the proof of this part.

It follows from Eq. (17), (a) and (b) that

$\mathbf{r}^{*}=\alpha(\eta\mathbf{g}-\mathbf{w}^{*})\;\text{ with
}\;\alpha=\frac{R}{\|\eta\mathbf{g}-\mathbf{w}^{*}\|}.$ (18)

The desired result follows from (18), (4) ,

$\displaystyle F(\mathbf{w}^{*},\mathbf{r}^{*})$
$\displaystyle=\eta(1+R^{2})+2R\sqrt{\eta^{2}+\|\mathbf{w}\|^{2}-2\eta B}-2B$
$\displaystyle\leq\eta(1+R^{2})+2R\sqrt{\eta^{2}+c^{2}-2\eta B}-2B.$

∎

We now present the proof of Corollary 7.0.1

###### Proof.

Assume $d\geq 2$ and $\|\mathbf{w}^{*}\|<C$. Consider $\mathbf{y}$ s.t.
$\langle\mathbf{g},\mathbf{y}\rangle=0$ and
$\langle\mathbf{w}^{*},\mathbf{y}\rangle\geq 0$. Since $d\geq 2$ we can
assume, without loss of generality, that $\|\mathbf{y}\|=1$ . Furthermore,
define $\tilde{\mathbf{w}}=\mathbf{w}^{*}+a\mathbf{y}$ with $a\in{\rm I\\!R}$,
then $\exists\;a>0\;s.t.\;\|\tilde{\mathbf{w}}\|=C$. The point
$(\mathbf{r}^{*},\tilde{\mathbf{w}})$ is a feasible point since
$\langle\tilde{\mathbf{w}},\mathbf{g}\rangle=\langle\mathbf{w}^{*},\mathbf{g}\rangle=B$.

We consider two cases:

\- $\mathbf{g}$ is not collinear with $\mathbf{w}^{*}$.

In this case $\exists\,\mathbf{y}$ such that
$\langle\mathbf{w}^{*},\mathbf{y}\rangle>0$. Eq. (18) yields

$\displaystyle
F(\mathbf{w}^{*},\mathbf{r}^{*})-F(\tilde{\mathbf{w}},\mathbf{r}^{*})$
$\displaystyle=2\langle\tilde{\mathbf{w}}-\mathbf{w}^{*},\mathbf{g}+\mathbf{r}^{*}\rangle$
$\displaystyle=2\langle a\mathbf{y},\mathbf{g}+\mathbf{r}^{*}\rangle$
$\displaystyle=2\langle a\mathbf{y},\mathbf{r}^{*}\rangle$
$\displaystyle=2\langle
a\mathbf{y},\alpha[\eta\mathbf{g}-\mathbf{w}^{*}]\rangle$
$\displaystyle=-2a\alpha\langle\mathbf{y},\mathbf{w}^{*}\rangle$
$\displaystyle<0.$

The last equation violates the optimality of $\mathbf{w}^{*}$, thus

$\|\mathbf{w}^{*}\|=C.$ (19)

\- $\mathbf{g}$ is collinear with $\mathbf{w}^{*}$.

In this case (c) implies $\mathbf{w}^{*}=B\mathbf{g}$ . Consider
$\tilde{\mathbf{r}}=\beta[(\eta-B)\mathbf{g}-a\mathbf{y}]$, then

$\displaystyle
F(\mathbf{w}^{*},\mathbf{r}^{*})-F(\tilde{\mathbf{w}},\tilde{\mathbf{r}})=$
$\displaystyle
2\left[\langle\eta\mathbf{g}-\mathbf{w}^{*},\mathbf{r}^{*}\rangle-\langle\eta\mathbf{g}-\tilde{\mathbf{w}},\tilde{\mathbf{r}}\rangle-\langle\mathbf{g},\mathbf{w}^{*}-\tilde{\mathbf{w}}\rangle\right]$
$\displaystyle=$ $\displaystyle
2\left\\{\langle(\eta-B)\mathbf{g},\operatorname*{sgn}(\eta-B)R\mathbf{g}\rangle-\langle(\eta-B)\mathbf{g}-a\mathbf{y},\beta\left[(\eta-B)\mathbf{g}-a\mathbf{y}\right]\rangle\right\\}$
$\displaystyle=$ $\displaystyle
2\left\\{\langle\operatorname*{sgn}(\eta-B)(\eta-B)\mathbf{g},R\mathbf{g}\rangle-\beta\langle(\eta-B)\mathbf{g}-a\mathbf{y},(\eta-B)\mathbf{g}-a\mathbf{y}\rangle\right\\}$
$\displaystyle=$ $\displaystyle
2\left\\{|\eta-B|R-\beta\left[(\eta-B)^{2}+a^{2}\right]\right\\}$
$\displaystyle=$ $\displaystyle
2\left\\{|\eta-B|R-R\sqrt{(\eta-B)^{2}+a^{2}}\right\\}$ $\displaystyle=$
$\displaystyle
R\sqrt{(\eta-B)^{2}+a^{2}}\left(\frac{|\eta-B|}{\sqrt{(\eta-B)^{2}+a^{2}}}-1\right)$
$\displaystyle<$ $\displaystyle 0,$

where the second equality follows from $\mathbf{w}^{*}=B\mathbf{g}$, Eq. (18)
and $\langle\mathbf{g},\mathbf{y}\rangle=0$, and the fourth and fifth
equalities are implied by $\langle\mathbf{g},\mathbf{y}\rangle=0$. The last
equation violates the optimality of $(\mathbf{w}^{*},\mathbf{r}^{*})$, thus
(19) must be fulfilled. The desired result then follows,

$F(\mathbf{w}^{*},\mathbf{r}^{*})=\eta(1+R^{2})+2R\sqrt{\eta^{2}+c^{2}-2\eta
B}-2B.$

∎

###  7.2 Corollary 4.1.1

###### Proof.

Minimizing the bound in Theorem 4.1 is equivalent to minimizing

$\max\left\\{\frac{\eta}{2}\left[1+\left(R+\frac{S}{\eta}\right)^{2}\right],\frac{\eta}{2}\left[1-\left(R+\frac{S}{\eta}\right)^{2}\right]+c\left[R+\frac{S}{\eta}\right]\right\\}.$

Define the function $G(\eta)$ as

$\displaystyle G(\eta):=$
$\displaystyle\max\left\\{\frac{\eta}{2}(1+R^{2}+\frac{S^{2}}{\eta^{2}}+\frac{2SR}{\eta}),\frac{\eta(1-R^{2}-\frac{S^{2}}{\eta^{2}}-\frac{2RS}{\eta})}{2}+Rc+\frac{Sc}{\eta}\right\\}$
$\displaystyle=$
$\displaystyle\max\left\\{\frac{\eta}{2}(1+R^{2})+\frac{S^{2}}{2\eta}+SR,\frac{\eta}{2}(1-R^{2})-\frac{S^{2}}{2\eta}-RS+Rc+\frac{Sc}{\eta}\right\\}.$

Note that

$\displaystyle
G(\eta)=\begin{cases}\frac{\eta}{2}(1+R^{2})+\frac{S^{2}}{2\eta}+SR&\text{if
}t\geq\frac{c-S}{R}=\eta_{3},\\\
\frac{\eta}{2}(1-R^{2})-\frac{S^{2}}{2\eta}-RS+Rc+\frac{Sc}{\eta}&\text{otherwise}.\end{cases}$

The minimum of the first part is achieved at
$\eta_{1}=\frac{S}{\sqrt{1+R^{2}}}$ while the minimum of the second part is
achieved at $\eta_{2}=\sqrt{\frac{S(c-2S)}{1-R^{2}}}$. Since $G(\eta)$ is the
maximum of two convex functions, it attains its global minimum in the set
$\left\\{\eta_{1}.\eta_{2},\eta_{3}\right\\}$.

∎

####  7.2.1 Proof of Theorem 4.2

The theorem follows immediately from Eq. (13) if
$\mathbf{w}_{k+1}=\mathsf{P}_{\Omega}(\mathbf{w}_{k}-\eta\hat{\mathbf{g}}_{k}+\mathbf{s}_{k}).$
However, the key to prove Theorem 4.2 is
$\|\mathbf{w}_{k+1}-\mathbf{w}^{*}\|\leq\|\mathbf{w}_{k}-\mathbf{w}^{*}\|,\;\forall\,0<k<\tilde{k}$
where
$\tilde{k}=\inf\left\\{k|\,f(\mathbf{w}_{k})>f^{*}+L\left[\Gamma(C_{0})\right]^{p}\right\\}$.
It therefore suffices to establish this last inequality to complete the proof
of Theorem 4.2.

###### Proof.

Fix $K>0$. Suppose $\delta>0$ and
$f(\mathbf{w}_{k})>f^{*}+L(\Gamma(C_{0})+\delta)^{p},\quad\forall\;k\leq K.$
It is shown by induction that

$\|\mathbf{w}_{k}-\mathbf{w}^{*}\|\leq C_{0}-2\eta\delta k,\quad\forall\,k\leq
K.$

The case $k=0$ is trivial.

Suppose $\|\mathbf{w}_{j}-\mathbf{w}^{*}\|\leq C_{0}-2\eta\delta j\leq
C_{0},\;\forall j\leq k$, then the argument of the proof Theorem 4.1 can be
repeated with $c=C_{0}$. This is possible because the projection operator in
the definition of $\mathbf{w}_{k+1}$ of Theorem 4.1 was needed only to bound
the norm of $\|\mathbf{w}_{k}-\mathbf{w}^{*}\|$ when Lemma 7.1 is used. Using
a similar argument leading to Eq. (13) and the induction hypothesis, we have

$\|\mathbf{w}_{k+1}-\mathbf{w}^{*}\|^{2}\leq\|\mathbf{w}_{k}-\mathbf{w}^{*}\|-2\eta\delta\leq
C_{0}-2\eta\delta(k+1),$

If $\delta\geq\frac{C_{0}}{2\eta K}$, the above inequality leads to a
contradiction since $f(\mathbf{w}_{K})>f^{*}$. Thus $\exists\,k\leq
K\;s.t.\;f(\mathbf{w}_{k})\leq f^{*}+L(\Gamma(C_{0})+\delta)^{p}$. This
completes the proof. ∎

####  7.2.2 Proof of Corollary 4.3.1

###### Proof.

Define $G(\eta)=\eta(d\sigma^{2}_{r}+1)+\frac{d\sigma^{2}_{s}}{\eta}$. The
function $G(\cdot)$ is convex and continuosly differentiable in ${\rm
I\\!R}^{+}\setminus\\{0\\}$. Hence the minimum of $G(\cdot)$ is achieved at
the roots of its derivative. Obviously only positive roots are of interest.
The derivative of $G(\cdot)$ is

$\frac{\partial
G(\cdot)}{\partial\eta}=d\sigma^{2}_{r}+1-\frac{d\sigma^{2}_{s}}{\eta^{2}},$

with positive root
$\eta^{*}=\sqrt{\frac{d\sigma^{2}_{s}}{d\sigma^{2}_{r}+1}}$.

∎

###  7.3 Proof of Theorem 4.3

###### Proof.

Let ${\cal
F}_{n}=\sigma\\{\mathbf{w}_{0},\mathbf{w}_{1},\dots,\mathbf{w}_{n}\\}$ be the
$\sigma$-algebra generated by
$\\{\mathbf{w}_{0},\mathbf{w}_{1},\dots,\mathbf{w}_{n}\\}$. Suppose
$\mathbf{w}_{n}\notin\mathbf{\Omega}^{*}$, it follows from the definition of
$\mathbf{w}_{n+1}$

$\displaystyle\|\mathbf{w}_{n+1}-\mathbf{w}^{*}\|^{2}$
$\displaystyle\leq\|\mathbf{w}_{n}-\eta\hat{\mathbf{g}}(\mathbf{w}_{n})-\eta\mathbf{r}_{n}-\mathbf{s}_{n}-\mathbf{w}^{*}\|^{2}$
$\displaystyle\leq\|\mathbf{w}_{n}-\mathbf{w}^{*}\|^{2}-2\eta\langle\hat{\mathbf{g}}(\mathbf{w}_{n}),\mathbf{w}_{n}-\mathbf{w}^{*}\rangle-2\eta\langle\mathbf{w}_{n}-\mathbf{w}^{*},\mathbf{r}_{n}\rangle$
$\displaystyle\hskip
7.22743pt-2\langle\mathbf{w}_{n}-\mathbf{w}^{*},\mathbf{s}_{n}\rangle+\eta^{2}\|\hat{\mathbf{g}}(\mathbf{w}_{n})+\mathbf{r}_{n}+\frac{\mathbf{s}_{n}}{\eta}\|^{2}.$

Taking conditional expectation given ${\cal F}_{n}$

$\displaystyle{\rm I\\!E}\left\\{\|\mathbf{w}_{n+1}-\mathbf{w}^{*}\|^{2}|{\cal
F}_{n}\right\\}$
$\displaystyle\leq\|\mathbf{w}_{n}-\mathbf{w}^{*}\|^{2}-2\eta{\rm
I\\!E}\left\\{\langle\hat{\mathbf{g}}(\mathbf{w}_{n}),\mathbf{w}_{n}-\mathbf{w}^{*}\rangle|{\cal
F}_{n}\right\\}-2\eta{\rm
I\\!E}\left\\{\langle\mathbf{w}_{n}-\mathbf{w}^{*},\mathbf{r}_{n}\rangle|{\cal
F}_{n}\right\\}$ $\displaystyle\hskip 7.22743pt-2{\rm
I\\!E}\left\\{\langle\mathbf{w}_{n}-\mathbf{w}^{*},\mathbf{s}_{n}\rangle|{\cal
F}_{n}\right\\}+\eta^{2}{\rm
I\\!E}\left\\{\|\hat{\mathbf{g}}(\mathbf{w}_{n})+\mathbf{r}_{n}+\frac{\mathbf{s}_{n}}{\eta}\|^{2}|{\cal
F}_{n}\right\\}$
$\displaystyle\leq\|\mathbf{w}_{n}-\mathbf{w}^{*}\|^{2}-2\eta\left(\frac{f(\mathbf{w})-f^{*}}{L}\right)^{\frac{1}{p}}-2\eta\langle\mathbf{w}_{n}-\mathbf{w}^{*},{\rm
I\\!E}\left\\{\mathbf{r}_{n}\right\\}\rangle$ $\displaystyle\hskip
7.22743pt-2\langle\mathbf{w}_{n}-x^{*},{\rm
I\\!E}\left\\{\mathbf{s}_{n}\right\\}\rangle+\eta^{2}\left(1+{\rm
I\\!E}\left\\{\|\mathbf{r}_{n}\|^{2}\right\\}+2{\rm
I\\!E}\left\\{\langle\hat{\mathbf{g}}(\mathbf{w}_{n}),\mathbf{r}_{n}\rangle|{\cal
F}_{n}\right\\}\right)$ $\displaystyle\hskip 7.22743pt+{\rm
I\\!E}\left\\{\|\mathbf{s}_{n}\|^{2}\right\\}+2\eta{\rm
I\\!E}\left\\{\langle\hat{\mathbf{g}}(\mathbf{w}_{n}),\mathbf{s}_{n}\rangle|{\cal
F}_{n}\right\\}+2\eta{\rm
I\\!E}\left\\{\langle\mathbf{s}_{n},\mathbf{r}_{n}\rangle\right\\}$
$\displaystyle\leq\|\mathbf{w}_{n}-\mathbf{w}^{*}\|^{2}-2\eta\left(\frac{f(\mathbf{w})-f^{*}}{L}\right)^{\frac{1}{p}}+\eta^{2}\left(1+d\sigma^{2}_{r}\right)+d\sigma^{2}_{s},$
(20)

where Lemma 7.3 is used to derive the second inequality. The third inequality
follows from the ortogonality of
$\mathbf{g}(\mathbf{w}_{n}),\,\mathbf{r}_{n},\,\mathbf{s}_{n}$ and the fact
that ${\rm I\\!E}\left\\{\mathbf{r}_{n}\right\\}={\rm
I\\!E}\left\\{\mathbf{s}_{n}\right\\}=0$. Consider now $\delta>0$ and

$\mathbf{\Omega}_{\delta}=\mathbf{\Omega}\cap{\cal S}_{f,a},$

with
$a=f^{*}+L\left[\frac{\eta}{2}\left(1+d\sigma^{2}_{r}\right)+\frac{d\sigma^{2}_{s}}{2\eta}+\delta\right]^{p}$.
Since $f$ is continuos, $\exists\mathbf{y}\in{\rm
I\\!R}^{d}|\;\mathbf{y}_{\delta}\in\mathbf{\Omega}$ and
$f(\mathbf{y}_{\delta})=f^{*}+L(\delta)^{p}$. Define the process

$\tilde{\mathbf{w}}_{k+1}=\begin{cases}\mathsf{P}_{\Omega}\left[\eta\mathbf{w}_{k}-\eta\hat{\mathbf{g}}\left(\tilde{\mathbf{w}}_{k}\right)\right],&\text{if
}\tilde{\mathbf{w}}_{k}\notin\mathbf{\Omega}_{\delta},\\\
\mathbf{y}_{\delta}&\text{otherwise.}\end{cases}$

We show that
$\tilde{\mathbf{w}}_{k}\notin\mathbf{\Omega}_{\delta},\,\forall\,k>K,\,K\in\mathbb{N}$
leads to a contradiction. Without loss of generality we consider $K=0$. Assume
$\tilde{\mathbf{w}}_{k}\notin\mathbf{\Omega}_{\delta}$ for any $k$ and let
$\hat{{\cal
F}}_{k}=\\{\tilde{\mathbf{w}}_{0},\tilde{\mathbf{w}}_{1},\dots,\tilde{\mathbf{w}}_{k}\\}$.
Since $f(\tilde{\mathbf{w}}_{k})\geq
f^{*}+L\left[\frac{\eta}{2}\left(1+d\sigma^{2}_{r}\right)+\frac{d\sigma^{2}_{s}}{2\eta}+\delta\right]^{p}$,
using Eq. (20) it follows that
$\forall\,\mathbf{w}^{*}\in\mathbf{\Omega}^{*}$,

$\displaystyle{\rm
I\\!E}\left\\{\|\tilde{\mathbf{w}}_{k+1}-\mathbf{w}^{*}\|^{2}|\,\hat{{\cal
F}}_{k}\right\\}$
$\displaystyle\leq\|\tilde{\mathbf{w}}_{k}-\mathbf{w}^{*}\|^{2}-2\eta\left[\left(\frac{f(\tilde{\mathbf{w}}_{k})-f^{*}}{L}\right)^{\frac{1}{p}}-\frac{t}{2}(1+d\sigma^{2}_{r})-\frac{d\sigma^{2}_{s}}{2\eta}\right]$
$\displaystyle\leq\|\tilde{\mathbf{w}}_{k}-\mathbf{w}^{*}\|^{2}-2\eta\delta.$

Theorem 7.4 then implies $\sum_{k=0}^{+\infty}2\eta\delta<+\infty$. This is a
contradiction and hence the proof is complete. ∎

######  Lemma 7.3.

(Lemma 2.4 of Hu et al. (2016)). Let be $\mathbf{w}\notin\mathbf{\Omega}^{*}$
and $\hat{\mathbf{g}}(\mathbf{w})$ a unit noisy quasi sub-gradient of $f$ at
$\mathbf{w}$. Then, $\forall\,\mathbf{w}^{*}\in\mathbf{\Omega}^{*}$ it holds
that, given any ${\cal F}=\sigma\\{\mathbf{w}_{1},...,\mathbf{w}_{k}\\}$ where
$\mathbf{w}_{i}$ are random variables $\forall i=1,..,k$, then

${\rm
I\\!E}\left\\{\langle\hat{g}(\mathbf{w}),\mathbf{w}^{*}-\mathbf{w}\rangle|{\cal
F}\right\\}\geq\left(\frac{f(\mathbf{w})-f^{*}}{L}\right)^{\frac{1}{p}}.$

######  Lemma 7.4.

(Lemma 2.5 of Hu et al. (2016)). Let $\\{Y_{k}\\}$, $\\{Z_{k}\\}$ and
$\\{W_{k}\\}$ be three sequences of nonnegative random, and let $\\{{\cal
F}_{k}\\}$ be a filtration. Suppose that the following conditions are
satisfied for each $k$:

  * a)

$Y_{k}$, $Z_{k}$ and $W_{k}$ are functions of the random variables in ${\cal
F}_{k}$;

  * b)

${\rm I\\!E}\left\\{Y_{k+1}|{\cal F}_{k}\right\\}\leq Y_{k}-Z_{k}+W_{k}$;

  * c)

$\sum_{k=0}^{\infty}W_{k}<+\infty$.

Then $\sum_{k=0}^{\infty}Z_{k}<+\infty$, and the sequence $\\{Y_{k}\\}$
converges to a nonnegative random variable $Y$, almost surely.

##  8 Details of the experiments setting

We used the Normalized Gradient Descent (NGD) algorithm to perform the
experiments with the deterministic function
$f(\mathbf{w})=\|\mathbf{w}\|^{0.2}$ presented in Section 5. The maximum
number of epochs is set to 1500. Different values for $C_{0}$, $B_{r}$,
$B_{s}$ and learning rates were used. The errors, which are manually added,
have uniform distribution in each coordinate. Thus, the variances required in
Theorem 4.3 are $\sigma^{2}_{r}=\frac{B_{r}^{2}}{3}$ and
$\sigma^{2}_{s}=\frac{B_{s}^{2}}{3}$. For the computation of the bound in
Theorem 4.1, $c=C_{0}$ was used.

###  8.1 Testing the optimal learning rate

We performed experiments with fixed values for $B_{s}$, $B_{r}$, but different
choices of $\eta$ to acquire the optimal choice $\eta^{*}$ given by Corollary
4.3.1 . The experiment is repeated 10 times, for each tested value of $\eta$,.
Finally, the maximum loss function value observed across all the experiments
with the same $\eta$ is plotted at each epoch.

The results with $B_{r}=B_{s}=0.1$ are shown in Figure 11 and Figure 12. The
loss trajectory (blue line) observed with the value suggested by Corollary
4.3.1, $\eta=0.0348$, is the trajectory that has the lowest level . Our
theorems correctly predict that decreasing the value of $\eta$ is sometimes
not beneficial in terms of convergence, see Figure 12.

Figure 11: Results with $\eta=0.1$ (left panel) and $\eta=0.5$ (right panel)

Figure 12: Results with $\eta=0.01$ (left panel) and $\eta=0.0348$ (right
panel), decreasing the value of $\eta$ leads to worse bound and worse
convergence

###  8.2 Experimental results on original MNIST

In this section the results obtained on the original MNIST dataset are
reported. In contrast to the experiments in the main body of the manuscript,
PCA is not used to reduce the size of the inputs.

Figure 14 demonstrates that the loss trajectory (blue line) has a limit point
in the proximity of the optimal point of the convex loss function. Figure 14
shows the loss trajectory when the weight update is in single precision and
only gradient computations are performed using Bfloat number format. In this
experiment, the stochastic bound is numerically equal to the single-precision
SGD, confirming what already observed in Figure 7.

Figure 13: Logistic regression trained using single-precision SGD and a fixed
learning rate.

Figure 14: Logistic regression trained using Bfloat gradients with accumulator
size of 50, and single-precision weight update ($\mathbf{s}_{k}=0$ and
$\mathbf{r}_{k}\neq 0$).

##  9 More motivations for the quasi-convex hypothesis

To further motivate the quasi convex hypothesis we show the ResNet-56 loss-
landscape projection in two and three dimensions without skip connections over
the CIFAR10 dataset, see Figure 15. In this figure, the convex regions and the
quasi-convex regions are highlighted. The quasi-convex regions are larger than
the convex regions. This means that our theory is applicable in a larger
domain of the loss function.

Figure 15: The quasi-convex regions (in green) are larger than the convex
regions (in yellow).