# Small generators of abelian number fields

Martin Widmer  Department of Mathematics
Royal Holloway, University of London
TW20 0EX Egham
UK<EMAIL_ADDRESS>
###### Abstract.

We show that for each abelian number field $K$ of sufficiently large degree
$d$ there exists an element $\alpha\in K$ with $K=\mathbb{Q}(\alpha)$ and
absolute Weil height $H(\alpha)\ll_{d}|\Delta_{K}|^{1/2d}$ , where
$\Delta_{K}$ denotes the discriminant of $K$. This answers a question of
Ruppert from 1998 in the case of abelian extensions of sufficiently large
degree. We also show that the exponent $1/2d$ is best-possible when $d$ is
even.

###### Key words and phrases:

Weil height, small generators, Ruppert’s conjecture, abelian number fields,
Linnik’s Theorem

###### 2010 Mathematics Subject Classification:

Primary 11R04; 11G50 Secondary 11R29; 11R06

##  1\. Introduction

In this article we answer Ruppert’s question on small generators of number
fields for abelian fields of sufficiently large degree. We also show that
Ruppert’s proposed bound is sharp when the degree is even.

Let $K$ be a number field, and for $\alpha\in K$ let

$\displaystyle H(\alpha)=\prod_{v\in
M_{K}}\max\\{1,|\alpha|_{v}\\}^{\frac{d_{v}}{[K:\mathbb{Q}]}}$

be the absolute multiplicative Weil height of $\alpha$. Here $M_{K}$ denotes
the set of places of $K$ and for each place $v$ we choose the unique
representative $|\cdot|_{v}$ that either extends the usual Archimedean
absolute value on $\mathbb{Q}$ or a usual $p$-adic absolute value on
$\mathbb{Q}$, and $d_{v}=[K_{v}:\mathbb{Q}_{v}]$ denotes the local degree at
$v$. By the product formula $H(\alpha)$ is independent of the number field $K$
containing $\alpha$, and thus $H(\cdot)$ is a well-defined function on the
algebraic numbers $\overline{\mathbb{Q}}$. For an extension $K/F$ of number
fields we write

$\displaystyle\delta(K/F)=\min\\{H(\alpha);K=F(\alpha)\\}.$

Northcott’s Theorem implies that the above minimum exists, and thus
$\delta(K/F)$ is well-defined. We write $\Delta_{K}$ for the discriminant of
$K$. In 1998 Ruppert [12, Question 2] proposed the following question.

######  Question 1.

[Ruppert, 1998] Let $d>1$ be an integer. Is it true that

(1.1) $\displaystyle\delta(K/\mathbb{Q})\ll_{d}|\Delta_{K}|^{\frac{1}{2d}}$

for every number field $K$ of degree $d$?

Ruppert showed that for $d=2$ the answer is yes. In [14] an affirmative answer
to Ruppert’s question was given for all number fields $K$ that have a real
embedding, confirming (1.1) for all odd $d$. In the same article it was also
shown that (1.1) holds, provided the Riemann-hypothesis for the Dedekind-zeta
function of the Galois closure $K^{(G)}$ of $K/\mathbb{Q}$ holds true.

Pierce, Turnage-Butterbaugh and Wood [10, Theorem 8.2] have shown that (1.1)
holds for $100\%$ (when enumerated by modulus of their discriminant) of all
number fields in various families of degree $d$-extensions with prescribed
Galois group and certain conditions on the ramification types111Some of their
results are conditional on the strong Artin conjecture (but not the Riemann-
hypothesis for the corresponding Dedekind-zeta function)..

Very recently Akhtari, Vaaler, and the author [1, Theorem 1.3] showed that
(1.1) can only fail for CM-fields with trivial torsion $\mathop{\rm
Tor}\nolimits(K^{\times})=\\{\pm 1\\}$. Further, apart from these exceptional
fields, there exists an _integral_ 222 Ruppert observed that
$H(\alpha)\geq\frac{1}{2}|\Delta_{K}|^{1/2}$ for integral generators of
imaginary quadratic fields $K$, and thus (1.1) cannot hold when restricting to
integral generators (see also [1] for a quartic example). generator $\alpha$
satisfying the height bound (1.1). We remark that the Galois group
$\mathop{{\rm Gal}}\nolimits(K^{(G)}/\mathbb{Q})$ of the Galois closure
$K^{(G)}$ of a CM-field satisfies an exact sequence

(1.2) $\displaystyle 0\to(\mathbb{Z}/2\mathbb{Z})^{\nu}\to\mathop{{\rm
Gal}}\nolimits(K^{(G)}/\mathbb{Q})\to\mathop{{\rm
Gal}}\nolimits(k^{(G)}/\mathbb{Q})\to 1,$

where $k$ denotes the maximal totally real subfield of $K$, $\nu$ is an
integer satisfying $1\leq\nu\leq d/2$, $(\mathbb{Z}/2\mathbb{Z})^{\nu}$ is
identified with the normal subgroup $\mathop{{\rm
Gal}}\nolimits(K^{(G)}/k^{(G)})$ of $\mathop{{\rm
Gal}}\nolimits(K^{(G)}/\mathbb{Q})$, and the penultimate homomorphism sends
$\sigma$ to the restriction $\sigma_{|_{k^{(G)}}}$ (cf. [3, Proposition]).

This implies that, apart from the families of cyclic number fields [10,
Theorem 3.3, (1)], the “almost all” result [10, Theorem 8.2] is
superseded333The families of even degree considered in [10, Theorem 8.2] are
(certain) $d$-extensions $K$ with $\mathop{{\rm
Gal}}\nolimits(K^{(G)}/\mathbb{Q})$ isomorphic to either $A_{d}$, $S_{d}$, a
cyclic group, or a simple group. Of those only the cases $S_{4}$, $A_{4}$, and
cyclic groups can satisfy (1.2). For Galois $S_{4}$\- or $A_{4}$-extensions
$K^{(G)}/\mathbb{Q}$ the quartic subfield $K$ has no quadratic subfield,
ruling out that $K$ is a CM-field. by the recent pointwise result [1, Theorem
1.3].

Regarding cyclic, and more generally abelian, number fields, we have the
following pointwise result.

######  Theorem 1.

Let $L$ be the effectively computable constant from (3.18), and suppose $d\geq
4L$. Then, apart from finitely many exceptional fields, we have

$\delta(K/\mathbb{Q})\leq(25|\Delta_{K}|)^{\frac{1}{2d}}$

for each abelian number field $K$ of degree $d$.

The proof is a combination of well-known facts, classical tools, and [14,
Theorem 1.4], which yields (1.1) provided there exists a product of distinct
degree one primes of size between $|\Delta_{K}|^{1/2}$ and
$\gamma|\Delta_{K}|^{1/2}$ (for some $\gamma=\gamma_{d}>1$).

For abelian number fields a sufficient condition for the splitting of a prime
$p$ can be given in terms of a congruence condition modulo the conductor
$\mathfrak{f}$ of $K$. The latter is related to the discriminant by Hasse’s
conductor-discriminant formula, and one can show that
$\mathfrak{f}\leq|\Delta_{K}|^{2/d}$. Linnik’s Theorem provides a prime $p$ in
the required residue class modulo $\mathfrak{f}$ and satisfying
$p\leq\mathfrak{f}^{L}$, where $L$ is an absolute constant (usually called
Linnik’s constant). This upper bound is sufficient as long as $d\geq 4L$. We
also need $p>|\Delta_{K}|^{1/2}$ but a minor adjustment to the proof of
Linnik’s Theorem allows one to take care of this additional constraint.

For abelian fields of small degree better bounds for the least splitting prime
$p$ were obtained by Pollack [11] (see also [19] for an extension to certain
non-abelian number fields). The proof is based on the observation that a lower
bound on the number of ideals of bounded norm furnishes an upper bound on the
smallest splitting prime. Unfortunately, it is unclear how to use this method
to establish a splitting prime $p$ in the required interval
$|\Delta_{K}|^{1/2}<p\ll_{d}|\Delta_{K}|^{1/2}$.

The constant $L$ in Theorem 1 is expressed in terms of the constants
$c,c_{1},c_{2},c_{3}$ that arise from the three fundamental principles
Linnik’s Theorem is based upon (cf. Section 2). These four constants are all
explicitly computable and are subject to further improvement. However, getting
good values requires rather tedious computations, which come at the expense of
clarity and simplicity of the proof. But even the strongest methods (as
developed in [7] and [18]) would at very best lead to the bound $L=5$, leaving
the cases $2<d<20$ still open. Therefore, we have not attempted to present
explicit values for $c,c_{1},c_{2}$, and $c_{3}$.

It is also worthwhile mentioning that the bound (1.1) is stable under taking
composite fields with coprime discriminants. To see this let $\alpha_{i}\in
K_{i}$ with

$\delta(K_{i}/\mathbb{Q})=H(\alpha_{i})\ll_{d_{i}}|\Delta_{K_{i}}|^{\frac{1}{2d_{i}}}\quad(1\leq
i\leq 2).$

There exists a generator $\alpha=m_{1}\alpha_{1}+m_{2}\alpha_{2}$ of
$K=K_{1}K_{2}$ with rational integers $0\leq m_{i}<d$ (see, e.g., [17, Lemma
3.3]). If $(\Delta_{K_{1}},\Delta_{K_{2}})=1$ then it follows (cf. [9, Theorem
4.9]) that $d=[K:\mathbb{Q}]=d_{1}d_{2}$ and444In fact, $d=d_{1}d_{2}$ implies
that already $\alpha=\alpha_{1}+\alpha_{2}$ is a generator of $K$, as was
shown by Isaac (cf. [16, Theorem 1.3]).

$|\Delta_{K}|=|\Delta_{K_{1}}^{d_{2}}\Delta_{K_{2}}^{d_{1}}|,$

and thus

$\delta(K/\mathbb{Q})\leq
H(\alpha)\ll_{d}|\Delta_{K_{1}}|^{\frac{1}{2d_{1}}}|\Delta_{K_{2}}|^{\frac{1}{2d_{2}}}=|\Delta_{K}|^{\frac{1}{2d}}.$

Can the exponent $1/2d$ in (1.1) be improved? A well-known result of Silverman
[13, Theorem 1.1] implies that

(1.3)
$\displaystyle\delta(K/\mathbb{Q})\gg_{d}|\Delta_{K}|^{\frac{1}{2d(d-1)}}.$

Ruppert’s [12, Theorem 1.1] shows that for $d=2$ the reversed inequality holds
true as well. This suggests the following strengthening of Question 1.1, also
proposed by Ruppert [12, Question 1].

######  Question 2.

[Ruppert, 1998] Let $d>1$ be an integer. Is it true that

(1.4)
$\displaystyle\delta(K/\mathbb{Q})\ll_{d}|\Delta_{K}|^{\frac{1}{2d(d-1)}}$

for every number field $K$ of degree $d$?

However, Vaaler and the author [15, Theorem 1.2] have shown that there exist
infinitely many number fields $K$ of degree $d$ with

(1.5) $\displaystyle\delta(K/\mathbb{Q})\geq|\Delta_{K}|^{\gamma}$

whenever

(1.8) $\displaystyle\gamma<\left\\{\begin{array}[]{lll}&1/((b+1)d):&\text{ if
}b\leq 3,\\\ &{1}/{(2(b+1)d)}+{1}/{(b^{2}(b+1)d)}:&\text{
otherwise.}\end{array}\right.$

Here $b=b(d)>1$ denotes the smallest divisor of $d$. This provides a negative
answer to Question 2 when $d$ is composite.

A negative answer was also given [15, Theorem 1.3] for prime $d>3$,
conditional on a weak form of a folklore conjecture about the distribution of
number fields. Very recently Dubickas [4, Theorem 1] showed unconditionally
that for odd $d$ one can take

(1.9) $\displaystyle\gamma=\frac{d+1}{2d^{2}(d-1)},$

hence showing that Ruppert’s Question 2 has a negative answer also for prime
$d>2$. While the bound (1.8) is better for composite $d$ than (1.9) Dubickas
provides an explicit family of fields whereas there is no such description for
the fields in [15, Theorem 1.2 and Corollary 4.1].

Our next result shows that for even $d$ the exponent $1/2d$ in (1.1) cannot be
replaced by any smaller value. Furthermore, it improves the exponents $\gamma$
in (1.8) and (1.9) when $d$ is composite and $b\neq 3$, and it provides an
explicit description of the fields $K$. On the other hand the method in [15]
(cf. [15, Corollary 4.2]) also provides density statements which we do not
recover here.

######  Theorem 2.

Let $m$ and $n>1$ be positive integers, and set $d=mn$. Then there are
infinitely many number fields $K$ of degree $d$ such that

$\displaystyle{\frac{1}{\sqrt{2d}}}|\Delta_{K}|^{\frac{1}{2d(n-1)}}\leq\delta(K/\mathbb{Q})\leq(2d)^{2}|\Delta_{K}|^{\frac{1}{2d(n-1)}}.$

More precisely, the above bounds hold for each
$K=\mathbb{Q}(2^{1/m},(p/q)^{1/n})$ where $p$ and $q$ are primes satisfying
$m<p<q<2p$.

Theorem 2 is a simple consequence of an observation of Ruppert (and
independently of Masser), and a standard height inequality of Silverman.

In [15] it was proposed to determine the cluster points555 What the authors in
[15] meant by “cluster point of the set
$\left\\{\frac{\log\delta(K/\mathbb{Q})}{\log|\Delta_{K}|};[K:\mathbb{Q}]=d\right\\}$”
is a real number $\eta$ such that for each $\varepsilon>0$ there are
infinitely many number fields $K$ of degree $d$ with
$\left|\frac{\log\delta(K/\mathbb{Q})}{\log|\Delta_{K}|}-\eta\right|<\varepsilon$.
of the set

$\displaystyle\left\\{\frac{\log\delta(K/\mathbb{Q})}{\log|\Delta_{K}|};[K:\mathbb{Q}]=d\right\\}.$

Ruppert [12] has shown that $1/(2d(d-1))$ is the smallest cluster point, and
for $d=3$ Dubickas has recently shown that $1/9$ is a cluster point. Theorem 2
shows that $1/2d(n-1)$ is a cluster point for every divisor $n>1$ of $d$.

## Acknowledgement

It is my pleasure to thank Glyn Harman for pointing out that a lower bound as
in Lemma 2 can be derived by an easy adaptation of the usual proof of Linnik’s
theorem; and Marc Technau for noting that Proposition 1 follows easily from
[8, Proposition 18.5]. I am also grateful to Shabnam Akhtari and Jeffrey
Vaaler for many fruitful and interesting discussions on Ruppert’s questions
and beyond.

##  2\. Primes of a given residue class in short intervals

For $x\geq 1$ and coprime positive integers $a$ and $q$ let

$\displaystyle\pi(x;q,a)$ $\displaystyle=\sum_{p\leq x\atop p\equiv a\
(\mathrm{mod}\ q)}1,$ $\displaystyle\psi(x;q,a)$ $\displaystyle=\sum_{n\leq
x\atop n\equiv a\ (\mathrm{mod}\ q)}\Lambda(n),$

where in the first sum $p$ denotes a prime, and in the second sum
$\Lambda(\cdot)$ denotes the von Mangoldt function. Noting that

$\psi(x;q,a)=\sum_{p\leq x\atop p\equiv a\ (\mathrm{mod}\
q)}\left\lfloor\frac{\log x}{\log p}\right\rfloor\log p,$

and splitting the sum in $p\leq\sqrt{x}$ and $p>\sqrt{x}$ gives the
inequalities

$\displaystyle\frac{1}{2}\log
x\left(\pi(x;q,a)-\pi(\sqrt{x};q,a)\right)\leq\psi(x;q,a)\leq\log
x\left(\pi(x;q,a)+\pi(\sqrt{x};q,a)\right).$

This in turn yields for $y>x\geq 2$

(2.10) $\displaystyle\pi(y;q,a)-\pi(x;q,a)\geq\frac{\psi(y;q,a)}{\log
y}-\frac{2\psi(x;q,a)}{\log x}+O\left(\frac{\sqrt{y}}{\log y}\right),$

where the implicit constant in the $O$-term is absolute.

As explained in Section 3, to prove Theorem 1 it suffices to prove a positive
lower bound for

$\pi(y;q,a)-\pi(x;q,a),$

when $y=\gamma x$ for some absolute $\gamma>1$ and $x$ is of size $q^{d/4}$.

Such a lower bound can be deduced by an easy adaptation of the usual proof of
Linnik’s theorem, provided $d$ is sufficiently big. We follow Iwaniec-Kowalski
[8] which itself borrows significantly from Graham’s work [6, 5]. However, to
keep track of the constants which determine the threshold $4L$ for the degree
in Theorem 1 we need to give some background.

Following [8] we write $L_{q}(s)$ for the product of all Dirichlet
$L$-functions associated to Dirichlet characters $\chi$ modulo $q$

$\displaystyle L_{q}(s)=\prod_{\chi\ (\mathrm{mod}\ q)}L(s,\chi).$

For $\frac{1}{2}\leq\alpha\leq 1$, and $T\geq 1$ we write

$\displaystyle N_{q}(\alpha,T)$

for the number of zeros of $L_{q}(s)$, counted with multiplicity, with real
part $\alpha<\sigma\leq 1$, and modulus of the imaginary part $|t|\leq T$.

The proof of Linnik’s Theorem rests on the following three principles which we
quote from [8]666In [8] the authors state these principles for more general
ranges $|t|\leq T$ but only apply them with $T=q$. The authors [8, Section
18.1, p. 429] remark that for $q$ sufficiently large and $T\leq\log q$ one can
choose $c_{1}=1/10,c_{2}=3,c_{3}=1/2$ (they provide no value for $c$).
However, following [8] we choose $T=q$, and thus these values may not be
eligible in our setting..

######  Principle 1 (The zero-free region).

There is an effectively computable positive constant $c_{1}$ such that
$L_{q}(s)$ has at most one zero in the region

$\displaystyle\sigma\geq 1-c_{1}/2\log q,\quad|t|\leq q.$

The exceptional zero, if it exists, is real and simple, and it is for a real,
non-principal character.

######  Principle 2 (The log-free zero-density estimate).

There are effectively computable positive constants $c,c_{2}$ such that for
any $\frac{1}{2}\leq\alpha\leq 1$

$\displaystyle N_{q}(\alpha,q)\leq cq^{2c_{2}(1-\alpha)}.$

######  Principle 3 (The exceptional zero repulsion).

There is an effectively computable positive constant $c_{3}$ such that if the
exceptional zero $\beta_{1}$ exists, say $L(\beta_{1},\chi_{1})=0$ with

$\displaystyle 1-c_{1}/2\log q\leq\beta_{1}<1,$

then the function $L_{q}(s)$ has no other zeros in the region

$\displaystyle\sigma\geq 1-c_{3}\frac{|\log(1-\beta_{1})|}{2\log
q},\quad|t|\leq q.$

For the effectively computable constants from Principle 1, 2, and 3 we assume
(as we can) throughout this section that

$\displaystyle c,c_{2}>1>c_{1},c_{3}>0.$

We say that the real number $\beta_{1}$ is an exceptional zero of $L_{q}(s)$
if there exists a real character $\chi_{1}$ modulo $q$ for which
$L(\beta_{1},\chi_{1})=0$, and $\beta_{1}=1-\delta_{1}$ with

$\displaystyle\delta_{1}\leq\frac{c_{1}}{2\log q}.$

Let

$\displaystyle\eta=\frac{c_{1}}{2\log q}$

if the exceptional zero $\beta_{1}$ does not exist, and let

$\displaystyle\eta=c_{3}\frac{|\log(2\delta_{1}\log q)|}{2\log q}$

if $\beta_{1}$ does exist.

We will use [8, Proposition 18.5] which we state as a lemma.

######  Lemma 1.

[8, Proposition 18.5] Let $c,c_{1},c_{2},c_{3}$ be the absolute constants from
Principles 1, 2, 3. Then for $x\geq q^{4c_{2}}$ we have

$\displaystyle\psi(x;q,a)=\frac{x}{\phi(q)}\left\\{1-\chi_{1}(a)\frac{x^{\beta_{1}-1}}{\beta_{1}}+\theta
cx^{-\eta/2}+O\left(\frac{\log q}{q}\right)\right\\}$

where the term involving $\beta_{1}$ does not exist if $\beta_{1}$ does not
exist, $\eta$ is as above and $|\theta|\leq 4$, and the implied constant is
absolute.

Next we consider the quantity777We have additionally included the term
$4/c_{3}$ as $\nu\geq 4/c_{3}$ is used in [8] without mentioning. $\nu$ from
[8, (18.90)], but we allow an additional real parameter $U$, and we set

(2.11)
$\displaystyle\nu=\max\left\\{4c_{2},\frac{4}{c_{1}},\frac{4}{c_{3}},\frac{4\log(2Uc)}{c_{3}|\log
c_{1}|}\right\\}.$

######  Proposition 1.

Suppose the exceptional zero $\beta_{1}$ of $L_{q}(s)$ exists, let $U\geq 1$,
and let $\gamma\geq 5$. Further, suppose that $x\geq q^{\nu}$. Then

$\displaystyle\psi(\gamma
x;q,a)-3\psi(x;q,a)\geq\frac{x}{\phi(q)}\left\\{\left[\frac{4(\gamma-3)}{3c_{1}}-\frac{4(\gamma+3)}{Uc_{1}}-\frac{(\gamma-3)}{\log
q}\right]\delta_{1}\log q+O\left(\frac{\gamma\log q}{q}\right)\right\\},$

where the implied constant is absolute.

###### Proof.

Let $c,c_{1},c_{2},c_{3}$ and $\eta$ be as in Lemma 1. Applying Lemma 1 we get

$\displaystyle\psi(\gamma x;q,a)-3\psi(x;q,a)=$ $\displaystyle\frac{\gamma
x}{\phi(q)}\left\\{1-\chi_{1}(a)\frac{(\gamma
x)^{\beta_{1}-1}}{\beta_{1}}+\theta_{1}c(\gamma x)^{-\eta/2}+O\left(\frac{\log
q}{q}\right)\right\\}$
$\displaystyle-\frac{3x}{\phi(q)}\left\\{1-\chi_{1}(a)\frac{x^{\beta_{1}-1}}{\beta_{1}}+\theta_{2}cx^{-\eta/2}+O\left(\frac{\log
q}{q}\right)\right\\}$ $\displaystyle=$
$\displaystyle\frac{x}{\phi(q)}\left\\{(\gamma-3)-(\gamma^{\beta_{1}}-3)\chi_{1}(a)\frac{x^{\beta_{1}-1}}{\beta_{1}}+(\theta_{1}\gamma^{1-\eta/2}-3\theta_{2})cx^{-\eta/2}+O\left(\frac{\gamma\log
q}{q}\right)\right\\}.$

Since $\gamma\geq 5$ we have $\left|\gamma^{\beta_{1}}-3\right|\leq\gamma-3$,
and since $|\theta_{i}|\leq 4$ we get
$|\theta_{1}\gamma^{1-\eta/2}-3\theta_{2}|\leq 4(\gamma+3)$. Hence,

(2.12) $\displaystyle\psi(\gamma
x;q,a)-3\psi(x;q,a)\geq\frac{x}{\phi(q)}\left\\{(\gamma-3)\left(1-|\chi_{1}(a)|\frac{x^{\beta_{1}-1}}{\beta_{1}}\right)-4(\gamma+3)cx^{-\eta/2}+O\left(\frac{\gamma\log
q}{q}\right)\right\\}.$

Now following [8, p. 441] we get

$\displaystyle
1-|\chi_{1}(a)|\frac{x^{\beta_{1}-1}}{\beta_{1}}=1-\frac{x^{-\delta_{1}}}{\beta_{1}}\geq\beta_{1}-q^{-\nu\delta_{1}}=1-q^{-\nu\delta_{1}}-\delta_{1}\geq\frac{\nu\delta_{1}\log
q}{1+\nu\delta_{1}\log q}-\delta_{1}\geq\frac{\nu\delta_{1}\log q}{1+\frac{\nu
c_{1}}{2}}-\delta_{1}$ (2.13) $\displaystyle\geq\frac{4\delta_{1}}{3c_{1}}\log
q-\delta_{1}.$

Furthermore, following [8, p. 441] and using that $\nu c_{3}/4\geq 1$, we get

(2.14) $\displaystyle x^{-\eta/2}\leq q^{-\nu\eta/2}=(2\delta_{1}\log q)^{\nu
c_{3}/4}\leq(2\delta_{1}\log q)c_{1}^{\nu
c_{3}/4-1}\leq\frac{\delta_{1}}{Ucc_{1}}\log q.$

Finally, plugging (2) and (2.14) into (2.12) yields

$\displaystyle\psi(\gamma
x;q,a)-3\psi(x;q,a)\geq\frac{x}{\phi(q)}\left\\{\left[\frac{4(\gamma-3)}{3c_{1}}-\frac{4(\gamma+3)}{Uc_{1}}-\frac{(\gamma-3)}{\log
q}\right]\delta_{1}\log q+O\left(\frac{\gamma\log q}{q}\right)\right\\}.$

∎

######  Lemma 2.

Let $5\leq\gamma\leq\sqrt{x}$, let
$U>3\left(\frac{\gamma+3}{\gamma-3}\right)$, and let

(2.15) $\displaystyle
L_{U}=\max\left\\{4c_{2},\frac{4}{c_{3}},\frac{4\log(2Uc)}{c_{1}},\frac{4\log(2Uc)}{c_{3}|\log
c_{1}|}\right\\}.$

There exists $q_{0}$ such that for $q\geq q_{0}$ and $x\geq q^{L_{U}}$

$\displaystyle\pi(\gamma
x;q,a)-\pi(x;q,a)\gg_{\gamma,U,c_{1},q_{0}}\frac{x}{\phi(q)\sqrt{q}\log\gamma
x}.$

###### Proof.

From (2.10), and using that $q\leq x^{1/L_{U}}\leq x^{1/4}$, we see that it
suffices to show that

(2.16) $\displaystyle\frac{\psi(\gamma x;q,a)}{\log\gamma
x}-\frac{2\psi(x;q,a)}{\log
x}\gg_{\gamma,U,c_{1},q_{0}}\frac{x}{\phi(q)\sqrt{q}\log\gamma x}.$

Since $\gamma\leq\sqrt{x}$ we have

(2.17) $\displaystyle\frac{\psi(\gamma x;q,a)}{\log\gamma
x}-\frac{2\psi(x;q,a)}{\log x}\geq\frac{1}{\log\gamma x}\left(\psi(\gamma
x;q,a)-3\psi(x;q,a)\right).$

First suppose the exceptional zero $\beta_{1}$ of $L_{q}(s)$ exists. Then
(2.16) follows immediately from (2.17) and Proposition 1 upon noticing that
$\delta_{1}\log q\gg q^{-1/2}$ by Siegel’s Theorem.

Next suppose the exceptional zero $\beta_{1}$ does not exists so that
$\eta=c_{1}/(2\log q)$. Applying Lemma 1, and using that $x\geq
q^{\frac{4\log(2Uc)}{c_{1}}}$, yields

$\displaystyle\psi(\gamma x;q,a)-3\psi(x;q,a)=$
$\displaystyle\frac{x}{\phi(q)}\left\\{(\gamma-3)+(\theta_{1}\gamma^{1-\eta/2}-3\theta_{2})cx^{-\eta/2}+O\left(\frac{\gamma\log
q}{q}\right)\right\\}$ $\displaystyle\geq$
$\displaystyle\frac{x}{\phi(q)}\left\\{(\gamma-3)-4(\gamma+3)cx^{-\eta/2}+O\left(\frac{\gamma\log
q}{q}\right)\right\\}$ $\displaystyle\geq$
$\displaystyle\frac{x}{\phi(q)}\left\\{(\gamma-3)-\frac{2(\gamma+3)}{U}+O\left(\frac{\gamma\log
q}{q}\right)\right\\}\gg_{\gamma,U,q_{0}}\frac{x}{\phi(q)\sqrt{q}}.$

This in conjunction with (2.17) proves (2.16). ∎

##  3\. Proof of Theorem 1

We will apply Theorem 4.1 from [14]. Here we state only a special case,
sufficient for our purposes.

######  Theorem 3.

[14, Theorem 4.1] Let $K$ be a number field of degree $d$, and let
$p>|\Delta_{K}|^{1/2}$ be a prime that splits completely in $K$. Then there
exists $\alpha\in K$ with $K=\mathbb{Q}(\alpha)$ and $H(\alpha)\leq p^{1/d}$.

If $K$ is an abelian number field of conductor $\mathfrak{f}$ then any prime
$p\equiv 1\pmod{\mathfrak{f}}$ splits completely in $K$ (cf. [9, Theorem
8.1]). Thus, to prove Theorem 1 it suffices to show that, apart from finitely
many exceptional fields, there exists a prime $p\equiv 1\pmod{\mathfrak{f}}$
with $|\Delta_{K}|^{1/2}<p\leq 5|\Delta_{K}|^{1/2}$. Let
$c,c_{2}>1>c_{1},c_{3}>0$ be the absolute constants from Principles 1, 2, 3.
We apply Lemma 2 with $\gamma=5$, $U=13$, $a=1$, and $q=\mathfrak{f}$ to
conclude that if $\mathfrak{f}$ is sufficiently large then there exists a
prime $p$ that splits completely in $K$ and satisfies $x<p\leq 5x$, provided
$x\geq\mathfrak{f}^{L}$ where

(3.18) $\displaystyle
L=L_{13}=\max\left\\{4c_{2},\frac{4}{c_{3}},\frac{4\log(26c)}{c_{1}},\frac{4\log(26c)}{c_{3}|\log
c_{1}|}\right\\}.$

We note that $\mathfrak{f}\leq|\Delta_{K}|^{2/d}$ (see [2, Lemma 9.2.1]).
Since $d\geq 4L$ the hypothesis $x\geq\mathfrak{f}^{L}$ holds for
$x=|\Delta_{K}|^{1/2}$, and thus we conclude that there exists a splitting
prime $p$ with $|\Delta_{K}|^{1/2}<p\leq 5|\Delta_{K}|^{1/2}$ whenever
$\mathfrak{f}$ is sufficiently large. Thus Theorem 3 yields a sufficiently
small generator for these fields. Finally, as there are only finitely many
abelian fields of degree $d$ with conductor below a given bound the proof of
Theorem 1 is complete.

##  4\. Proof of Theorem 2

Theorem 2 is an immediate consequence of the following proposition.

######  Proposition 2.

Let $m$ and $n>1$ be positive integers, let $F$ be a number field of degree
$m=[F:\mathbb{Q}]$, and set $d=mn$.
(1) Let $K$ be a field extension of $F$ of degree $n=[K:F]$. Then we have

$\displaystyle\delta(K/\mathbb{Q})\geq\left(n^{m}|\Delta_{F}|\right)^{-\frac{1}{2m(n-1)}}|\Delta_{K}|^{\frac{1}{2d(n-1)}}.$

(2) Let $K=F((p/q)^{1/n})$ where $p$ and $q$ are primes, $p$ is unramified in
$F$ and $p<q<2p$. Then $[K:F]=n$ and

$\displaystyle\delta(K/\mathbb{Q})\leq
2^{1+\frac{1}{2n}}d^{2}\delta(F/\mathbb{Q})|\Delta_{K}|^{\frac{1}{2d(n-1)}}.$

###### Proof.

By a result of Silverman [13, Theorem 2] we have

$H(\alpha)\geq
n^{-\frac{1}{2(n-1)}}N_{F/\mathbb{Q}}(D(K/F))^{\frac{1}{2d(n-1)}}$

whenever $K=F(\alpha)$. Here $D_{K/F}$ denotes the relative discriminant of
$K/F$ and $N_{F/\mathbb{Q}}(\cdot)$ is the norm from $F$ to $\mathbb{Q}$.
Since $N_{F/\mathbb{Q}}(D(K/F))=|\Delta_{F}|^{-n}|\Delta_{K}|$ the first part
follows immediately.

For the second part we start with an observation of Ruppert [12]: let
$\alpha=(p/q)^{1/n}$ and set $M=\mathbb{Q}(\alpha)$. Then $H(\alpha)=q^{1/n}$
and $(pq)^{n-1}|\Delta_{M}$. Hence $H(\alpha)\leq
2^{1/2n}|\Delta_{M}|^{1/2n(n-1)}$. Next let $\beta\in F$ be such that
$F=\mathbb{Q}(\beta)$. Hence, $K=F(\alpha)=M(\beta)=\mathbb{Q}(\alpha,\beta)$.
There are integers $0\leq a,b<d$ such that with $\gamma=a\alpha+b\beta$ we
have $K=\mathbb{Q}(\gamma)$ (see, e.g., [17, Lemma 3.3]). As $p$ is unramified
in $F$ and totally ramified in $M$ we conclude that $[MF:F]=[M:\mathbb{Q}]$,
hence $[K:F]=n$. By standard properties of the height we get $H(\gamma)\leq
2d^{2}H(\alpha)H(\beta)$. Choosing the $\beta$ with minimal height we conclude

(4.19) $\displaystyle\delta(K/\mathbb{Q})\leq
2^{1+\frac{1}{2n}}d^{2}\delta(F/\mathbb{Q})|\Delta_{M}|^{\frac{1}{2n(n-1)}}.$

Finally, noticing that $[K:M]=m$ and thus $\Delta_{M}^{m}|\Delta_{K}$ the
second claim follows from (4.19). ∎

Theorem 2 follows now easily from Proposition 2. Let $F=\mathbb{Q}(2^{1/m})$
so that $[F:\mathbb{Q}]=m$, $\delta(F/\mathbb{Q})\leq 2^{1/m}$, and
$|\Delta_{F}|\leq(2m)^{m}$. Moreover, no prime $p>m$ ramifies in $F$. The
lower bound follows from part $(1)$. The upper bound follows from part $(2)$
upon noticing that $2^{1+\frac{1}{2n}}d^{2}\delta(F/\mathbb{Q})<(2d)^{2}$,
where for $m=1$ we have used that $\delta(F/\mathbb{Q})=1$. This completes the
proof of Theorem 2.

## References

  * [1] S. Akhtari, J. D. Vaaler, and M. Widmer, _Small generators of number fields, II_ , submitted (2023).
  * [2] H. Cohen, _Advanced Topics in Computational Number Theory_ , Graduate Texts in Mathematics, vol. 193, Springer-Verlag, 2000.
  * [3] B. Dodson, _The structure of Galois groups of CM-fields_ , Trans. Amer. Math. Soc. 283 (1984), no. 1.
  * [4] A. Dubickas, _Minimal Mahler measures for generators of some fields_ , Rev. Math. Iberoam. 39, no. 1 (2023), 269–282.
  * [5] S. Graham, _An asymptotic estimate related to Selberg’s sieve_ , J. Number Theory 10 (1978), 83–94.
  * [6] by same author, _On Linnik’s constant_ , Acta Arith. XXXIX (4) (1981), 163–179.
  * [7] R. Heath-Brown, _Zero-free regions for dirichlet l-functions, and the least prime in an arithmetic progression_ , Proc. London Math. Soc. 64 (1991), no. 3.
  * [8] H. Iwaniec and E. Kowalski, _Analytic number theory_ , vol. 53, American Mathematical Soc., 2004.
  * [9] W. Narkiewicz, _Elementary and Analytic Theory of Algebraic Numbers_ , Springer, 1990.
  * [10] L. B. Pierce, C. Turnage-Butterbaugh, and M. Matchett Wood, _An effective Chebotarev density theorem for families of number fields, with an application to l-torsion in class groups_ , Invent. Math. 219, no.2 (2020), 701–778.
  * [11] P. Pollack, _The smallest prime that splits completely in an abelian number field_ , Proc. Amer. Math. Soc. 142 (2014), 1925–1934.
  * [12] W. Ruppert, _Small generators of number fields_ , Manuscripta math. 96 (1998), 17–22.
  * [13] J. Silverman, _Lower bounds for height functions_ , Duke Math. J. 51 (1984), 395–403.
  * [14] J. D. Vaaler and M. Widmer, _On small generators of number fields_ , Diophantine Methods, Lattices, and Arithmetic Theory of Quadratic Forms, Contemporary Mathematics, vol. 587, Amer. Math. Soc., Providence, RI, 2013 (2013).
  * [15] by same author, _Number fields without small generators_ , Math. Proc. Cam. Philos. Soc. 159, no.3 (2015), 379–385.
  * [16] S. H. Weintraub, _Observations on primitive, normal, and subnormal elements of field extensions_ , Monatsh. Math. 162 (2011), :239–244.
  * [17] M. Widmer, _Counting primitive points of bounded height_ , Trans. Amer. Math. Soc. 362 (2010), 4793–4829.
  * [18] T. Xylouris, _Über die Nullstellen der Dirichletschen L-Funktionen und die kleinste Primzahl in einer arithmetischen Progression, Dissertation for the degree of Doctor of Mathematics and Natural Sciences at the University of Bonn_ , Bonner Math. Schriften, 404 (2011).
  * [19] M. Milinovich Z. Ge and P. Pollack, _A note on the least prime that splits completely in a nonabelian Galois number field_ , Math. Z. 292 (2019), 183–192.


remarkRemark hypothesisHypothesis claimClaim AEGD: Adaptive Gradient Descent
with EnergyH. Liu and X. Tian

# AEGD: Adaptive Gradient Descent with Energy††thanks: Submitted to the
editors 5/31/2021. We would like to acknowledge support for this project from
the National Science Foundation (NSF grant DMS-1812666).

Hailiang Liu Department of Mathematics, Iowa State University, Ames, IA 50011,
USA (, https://faculty.sites.iastate.edu/hliu/<EMAIL_ADDRESS>Xuping Tian
Department of Mathematics, Iowa State University, Ames, IA 50011, USA ().
<EMAIL_ADDRESS>
###### Abstract

We propose AEGD, a new algorithm for first-order gradient-based optimization
of non-convex objective functions, based on a dynamically updated ‘energy’
variable. The method is shown to be unconditionally energy stable,
irrespective of the step size. We prove energy-dependent convergence rates of
AEGD for both non-convex and convex objectives, which for a suitably small
step size recovers desired convergence rates for the batch gradient descent.
We also provide an energy-dependent bound on the stationary convergence of
AEGD in the stochastic non-convex setting. The method is straightforward to
implement and requires little tuning of hyper-parameters. Experimental results
demonstrate that AEGD works well for a large variety of optimization problems:
it is robust with respect to initial data, capable of making rapid initial
progress. The stochastic AEGD shows comparable and often better generalization
performance than SGD with momentum for deep neural networks. The code is
available at https://github.com/txping/AEGD.

###### keywords:

Stochastic optimization, gradient descent, energy stability

90C15, 65K10, 68Q25

##  1 Introduction

From a mathematical perspective, training neural networks is a high-
dimensional non-convex optimization problem, and the dynamics of the training
process is incredibly complicated. Despite this, stochastic gradient descent
(SGD) [45] and its variants have proven to be extremely effective for training
neural networks in practice (see, for example, [9, 15]). Such stochastic
training often reduces to solving the following unconstrained minimization
problem

(1) $\min_{\theta\in\mathbb{R}^{n}}f(\theta)$

where $f:\mathbb{R}^{n}\to\mathbb{R}$ is a finite-sum function, defined as
$f(\theta):=\frac{1}{m}\sum_{i=1}^{m}f_{i}(\theta)$, where
$f_{i}(\theta):=L(F(x_{i};\theta);y_{i})$ is the loss of a given machine
learning (ML) model $F(\cdot;\theta)$ on the training data
$\\{x_{i},y_{i}\\}$, parametrized by $\theta$. For many practical
applications, $f(\theta)$ is highly non-convex, and $F(\cdot;\theta)$ is
chosen among deep neural networks (DNNs), known for their superior performance
across various tasks. These deep models are heavily over-parametrized and
require large amounts of training data. Thus, both $m$ and the dimension $n$
of $\theta$ can scale up to millions or even billions. These complications
pose serious computational challenges.

Gradient descent (GD) or its variants are the method of choice for solving
(1). There are two variations of gradient decent, which differ in how much
data we use to compute the gradient of the objective function. They are fully
gradient decent, aka batch GD, and SGD. For large dataset, SGD is usually much
faster by performing a parameter update for each training example. The GD
method dates back to Cauchy (1847), and it updates $\theta$ according to:

(2) $\theta_{k+1}=\theta_{k}-\eta\nabla f(\theta_{k}),$

where $\eta>0$ is the step size (called the learning rate in ML). GD has
advantages of easy implementation and being fast for well-conditioned and
strongly convex objectives, independent of the dimension of the underlying
problem [37]. However, GD typically limits the step size to ensure numerical
stability. The step limitation issue can be largely resolved by implicit
updates [54],

(3) $\theta_{k+1}=\theta_{k}-\eta\nabla f(\theta_{k+1}).$

This can be rewritten in the form of the celebrated proximal point algorithm
(PPA) [46]:

(4) $\theta_{k+1}={\rm
argmin}_{\theta}\left\\{f(\theta)+\frac{1}{2\eta}\|\theta-\theta_{k}\|^{2}\right\\}.$

Such method has the advantage of being monotonically decreasing, which is
guaranteed for any step size $\eta>0$. However, for non-quadratic function
$f$, one would have to solve it by iteration, for example by the backward
Euler method [59]. A natural question is:

Can we adapt the GD (2) and improve stability with arbitrary step size as in
(3) but still easy to implement?

We answer this question by proposing AEGD, a new method for efficient
optimization that only requires first-order gradients. At its core, an
auxiliary energy variable is used to adjust the step size at each update. The
name AEGD is derived from the adaptive GD method with energy. This method is
motivated by the energy dissipation structure hidden in the GD method with
momentum (GDM) [41]. We would like to emphasize that our AEGD features both a
global and an element-wise formulation, while by empirical evidence, the
latter appears to perform better in most cases.

###  1.1 Main Contributions

To our best knowledge, AEGD is the first algorithm that uses the energy update
to stabilize GD in the optimization of non-convex objective functions.
Meanwhile we show that AEGD still feathers the expected convergence rates for
first-order gradient-based methods including GD. Some major benefits of AEGD
are summarized below:

  * •

It is shown to be unconditionally energy stable, irrespective of the step
size.

  * •

It allows a larger base step size than GD.

  * •

It converges fast even for objective functions that have a large condition
number.

  * •

It is robust with respect to initial data.

  * •

It has visible advantages over the GD algorithm with momentum.

Most of the above advantages are kept for the stochastic AEGD, which will be
discussed in Section 4. In particular, our numerical results also show that
the stochastic AEGD has the potential for training neural networks with better
generalization, at least on some benchmark machine learning tasks.

###  1.2 Further Related Work

A numerical method bearing a direct relation to AEGD is the invariant energy
quadratization (IEQ) approach introduced by [58] and [63] for gradient flows
in the form of partial differential equations (PDEs). The IEQ approach uses
modified quadratic energy to construct linear, unconditionally energy stable
schemes for solving time-dependent PDEs [27, 28, 51]. The AEGD algorithm here
is new in that we use an auxiliary energy variable to obtain unconditionally
energy stable optimization algorithms.

In the field of stochastic optimization, there is an extensive volume of
research for designing algorithms to speed up convergence. Among others, two
common approaches to accelerate SGD are momentum [41] and adaptive step size
[14, 53, 60]. The latter makes use of the historical gradient to adapt the
step size, with renowned works like RMSProp [53], Adagrad [14], and Adadelta
[60] (see also the overview article [48]). The integration of momentum and
adaptive step size led to Adam [22], which is one of the optimization
algorithms that are widely used by the deep learning community. Many further
advances have improved Adam [11, 13, 25, 29, 33, 34, 44].

The name momentum stems from an analogy to momentum in physics. A simple batch
GD with constant momentum such as the heavy-ball (HB) method [41] is known to
enjoy the convergence rate of $O(1/k)$ for convex smooth optimization.
Remarkably, with an adaptive momentum the Nesterov accelerated gradient (NAG)
[35, 52] has the convergence rate up to the optimal $O(1/k^{2})$. Recent
advances showed that NAG has other advantages such as speeding up escaping
saddle points [19], accelerating SGD or GD in non-convex problems [43, 64].
One can also improve generalization with SGD in training DNNs with scheduled
restart techniques [38, 47, 55]. Both first and second order optimization
methods can be designed via inertial systems [4, 52, 10].

Another major bottleneck for fast convergence of SGD lies in its variance [7,
49, 50]. Different ideas have been proposed to develop variance reduction
algorithm. Some representative works are SAGA [12], SCSG [26], SVRG [20],
Laplacian smoothing [39, 56], and iterative averaging methods [42, 62].

For a gradient based method the geometric property of $f$ often affects the
convergence rates. For the non-convex $f$ we consider an old condition
originally introduced by Polyak [40], who showed that it is a sufficient
condition for gradient descent to achieve a linear convergence rate; see [21]
for a recent convergence study under this condition. Such condition is often
called the Polyak-Łojasiewicz (PL) inequality in the literature since it is a
special case of the inequality introduced by Łojasiewicz in 1963 [31]. The
works on convergence using the Łojasiewicz inequality include [32, 1]. A
generalization of the PL property for non-smooth optimization is the KL
inequality [24, 5]. The KL inequality has been successfully used to study the
convergence of the proximal algorithms [3], and the proximal alternating and
projection methods [2].

###  1.3 Organization

In Section 2, we motivate and present the AEGD method for non-convex
optimization in both global and element-wise version. Theoretical results,
including stability, convergence, and convergence rates, are given in Section
3, with technical proofs deferred to Appendix A. In Section 4 we present the
stochastic AEGD and some theoretical results. Section 5 provides some
experimental results to show the advantages of AEGD. We end this paper with
concluding remarks in Section 6.

###  1.4 Notation

Throughout this paper, we denote $\\{1,\cdots,m\\}$ by $[m]$ for integer $m$.
For vectors and matrices we use $\|\cdot\|$ to denote the $l_{2}$-norm. For a
function $f:\mathbb{R}^{n}\to\mathbb{R}$, we use $\nabla f$ and $\nabla^{2}f$
to denote its gradient and Hessian, and $\theta^{*}$ to denote a local
minimizer of $f$. We also use the notation
$\partial_{i}:=\partial_{\theta_{i}}$. In the algorithm description we use
$z=x/y$ to denote element-wise division if $x$ and $y$ are both vectors of
size $n$; $x\odot y$ is element-wise product, and $x^{2}=x\odot x$.

##  2 AEGD and Algorithm

It is known one can accelerate gradients for certain objective functions by
momentum, say by the HB scheme [41] of form

$\theta_{k+1}=\theta_{k}-\eta\nabla
f(\theta_{k})+\mu(\theta_{k}-\theta^{k-1}),$

where $0<\mu<1$ is a constant. This upon passing limit $\eta\to 0$ and $\mu\to
1$ with $\alpha=\frac{\eta}{(1-\mu)^{2}}$ kept fixed leads to

(5) $\displaystyle\alpha\ddot{\theta}+\dot{\theta}=-\nabla f,\quad\alpha>0.$

The faster convergence and reduced oscillation may be expected from the
perspective that the system is driven by the energy dissipation law
$\dot{E}=-|\dot{\theta}|^{2}\leq 0$ with the energy
$E(t)=f(\theta(t))+\frac{\alpha}{2}|\dot{\theta}(t)|^{2}$. Motivated by this
energy dissipation structure, we define $g(\theta)=\sqrt{f(\theta)+c}$ with
$c$ chosen so that $f(\theta)+c>0$. Set $r=g(\theta)$, then $r^{2}$ plays the
role of energy and

$\nabla f=2r\nabla g,\quad r=g(\theta).$

This transformation leads to an augmented system

(6a) $\displaystyle\dot{\theta}=-2r\nabla g(\theta),$ (6b)
$\displaystyle\dot{r}=\nabla g\cdot\dot{\theta}.$

It allows the dissipation of the quadratic energy
$\frac{d}{dt}(r^{2})=-|\dot{\theta}|^{2}$ in place of the dissipation of
nonlinear loss function: $\frac{d}{dt}f(\theta)=-|\dot{\theta}|^{2}$. Note
also that the above transformation with $c$ taken as constant is linked back
to the first order gradient flow $\dot{\theta}=-\nabla f$, instead of the
inertial equation (5). Based on (6) we introduce the following update rule:

(7a) $\displaystyle\theta_{k+1}=\theta_{k}-2\eta r_{k+1}\nabla
g(\theta_{k}),\quad k=0,1,2,\cdots,$ (7b) $\displaystyle r_{k+1}-r_{k}=\nabla
g(\theta_{k})\cdot(\theta_{k+1}-\theta_{k}).$

This is actually a linear algorithm since

(8a) $\displaystyle r_{k+1}=\frac{r_{k}}{1+2\eta|\nabla
g(\theta_{k})|^{2}},\quad r_{0}=\sqrt{f(\theta_{0})+c},$ (8b)
$\displaystyle\theta_{k+1}=\theta_{k}-2\eta r_{k+1}\nabla g(\theta_{k}),\quad
k=0,1,2,\cdots,$

which are easy to implement. In order to allow the use of different learning
rate in each coordinate, we also propose an element-wise AEGD, set forth as
follows:

(9a) $\displaystyle
r_{k+1,i}=\frac{r_{k,i}}{1+2\eta(\partial_{i}g(\theta_{k}))^{2}},\quad
i\in[n],\quad r_{0,i}=\sqrt{f(\theta_{0})+c},$ (9b)
$\displaystyle\theta_{k+1,i}=\theta_{k,i}-2\eta
r_{k+1,i}\partial_{i}g(\theta_{k}).\quad k=0,1,2,\cdots$

This also implies

(10) $\displaystyle
r_{k+1,i}-r_{k,i}=\partial_{i}g(\theta_{k})(\theta_{k+1,i}-\theta_{k,i}),\quad
i\in[n].$

######  Remark 2.1.

The essential idea behind (6) is the so called invariant energy quadratizaton
(IEQ) strategy, originally introduced for developing linear and
unconditionally energy stable schemes for gradient flows in the form of
partial differential equations [58, 63]. One may wonder whether
$r=(f+c)^{\alpha}$ is admissible for building similar algorithms for all
$\alpha\in(0,1)$. To see this, we write the corresponding augmented system as

$\dot{\theta}=-\alpha^{-1}r^{1/\alpha-1}\nabla g(\theta),\quad\dot{r}=\nabla
g\cdot\dot{\theta}.$

A similar implicit- explicit discretization can yield a linear update for $r$
if and only if $\frac{1}{\alpha}-1=1\Leftrightarrow\alpha=\frac{1}{2}.$ This
explains why energy quadratization has been used in the PDE community to name
such strategy.

##  3 Theoretical Results

In this section, we will show AEGD is unconditionally energy stable,
irrespective of the step size $\eta$, and obtain different convergence rates
for non-convex, convex, and strongly convex functions. We say $f$ is
$\alpha$-strongly convex if for all $u$ and $v$ we have $f(u)\geq
f(v)+\langle\nabla f(v),u-v\rangle+\alpha\|u-v\|^{2}/2$; $f$ is $L$-smooth if
$\|\nabla^{2}f(u)\|\leq L$ for any $u\in\mathbb{R}^{n}$. For convex
($\alpha=0$) and $L$-smooth functions, it is known that the convergence rate
$O(1/k)$ for GD of form (2) is guaranteed if $\eta\leq\frac{1}{L}$ [36]. This
may suggest very small step-sizes in practice, which is a condition that may
be violated in more complicated scenarios. In contrast, AEGD is energy stable
for any $\eta>0$ (see Theorem 3.1), and converges for a large range of $\eta$
(see Theorem 3.4).

###  3.1 Unconditional energy stability

######  Theorem 3.1.

(Energy stability and convergence) Consider
$\min\\{f(\theta),\;\theta\in\mathbb{R}^{n}\\},$ where $f(\theta)$ is
differentiable and bounded from below so that $f(\theta)+c>0$ for some $c>0$.
Then
(i) AEGD (8) is unconditionally energy stable in the sense that for any step
size $\eta>0$,

(11)
$r_{k+1}^{2}=r^{2}_{k}-(r_{k+1}-r_{k})^{2}-\eta^{-1}\|\theta_{k+1}-\theta_{k}\|^{2},$

$r_{k}$ is strictly decreasing and convergent with $r_{k}\to r^{*}$ as
$k\to\infty$, and also

(12)
$\lim_{k\to\infty}\|\theta_{k+1}-\theta_{k}\|=0,\quad\sum_{j=0}^{\infty}\|\theta_{j+1}-\theta_{j}\|^{2}\leq\eta(r^{2}_{0}-(r^{*})^{2}).$

(ii) AEGD (9) is unconditionally energy stable in the sense that for any step
size $\eta>0$,

(13)
$r^{2}_{k+1,i}=r^{2}_{k,i}-(r_{k+1,i}-r_{k,i})^{2}-\eta^{-1}(\theta_{k+1,i}-\theta_{k,i})^{2},\quad
i\in[n],$

$r_{k,i}$ is strictly decreasing and convergent with $r_{k,i}\to r_{i}^{*}$ as
$k\to\infty$, and also

(14)
$\lim_{k\to\infty}\|\theta_{k+1}-\theta_{k}\|=0,\quad\sum_{j=0}^{\infty}\|\theta_{j+1}-\theta_{j}\|^{2}\leq\eta\sum_{i=1}^{n}(r^{2}_{0,i}-(r^{*}_{i})^{2}).$

######  Proof 3.2.

(i) We use the two equations in (7) to derive

$2r_{k+1}(r_{k+1}-r_{k})=2r_{k+1}\nabla
g(\theta_{k})\cdot(\theta_{k+1}-\theta_{k})=-4\eta r_{k+1}\|\nabla
g(\theta_{k})\|^{2}=-\frac{1}{\eta}\|\theta_{k+1}-\theta_{k}\|^{2}.$

Upon rewriting with $2b(b-a)=b^{2}-a^{2}+(b-a)^{2}$ we obtain equality (11).
From this we see that $r^{2}_{k}$ is monotonically decreasing (also bounded
below), therefore convergent; so does $r_{k}$ since $r_{k}\geq 0$. Summation
of (11) over $k$ from $0,1,\cdots$ yields (12). The proof of (ii) is entirely
similar.

######  Remark 3.3.

It is worth pointing out that this theorem does not require the function $f$
satisfy L-smoothness or convexity assumption. The result asserts that the
unconditional energy stability featured by AEGD also implies convergence of
$\\{r_{k}\\}_{k\geq 0}$ for any $\eta>0$, and the sequence
$\\{\|\theta_{k+1}-\theta_{k}\|\\}_{k\geq 0}$ converges to zero at a rate of
at least $1/\sqrt{k}$. But this is not sufficient—at least in general—to prove
convergence of the sequence $\\{\theta_{k}\\}_{k\geq 0}$, when no further
information is available about this sequence.

###  3.2 Convergence and convergence rates

To understand the convergence behavior of AEGD (8), we reformulate it as

(15) $\theta_{k+1}=\theta_{k}-\eta_{k}\nabla
f(\theta_{k}),\quad\eta_{k}:=\eta\frac{r_{k+1}}{g(\theta_{k})}.$

Note that using $L$-smoothness of $f$ and (15) we have

$\displaystyle f(\theta_{k+1})$ $\displaystyle\leq
f(\theta_{k})-\left(\frac{1}{\eta_{k}}-\frac{L}{2}\right)\|\theta_{k+1}-\theta_{k}\|^{2}<f(\theta_{k}),$

when $\eta_{k}$ gets smaller so that $\eta_{k}<2/L$. Since $r_{k}$ is
decreasing, after finite number of iterations $\eta_{j}$ can be ensured (by
choosing $\eta$ to be suitably small if necessary) to fall below $2/L$ under
which $f(\theta_{j})$ turns into a strictly decreasing sequence, hence
convergent. To ensure the convergence of $\\{\theta_{k}\\}$, one needs further
info on the geometrical property of the objective function, such as convexity,
or the Kurdyka-Lojasiewicz (KL) property. The KL property at a point describes
how the objective function can be made sharp through a concave mapping near
that point. This property characterizes a rich function class, and often
considered as a structural assumption in general nonconvex optimization (see
[3] for a detailed account on this property and its applications). In the
present work we restrict to a special case of KL, called Polyak-Lojasiewics
(PL) property: $f$ is PL if there exists $\mu>0$ such that

(16) $\displaystyle\frac{1}{2}\|\nabla
f(\theta)\|^{2}\geq\mu(f(\theta)-f^{*}),$

where we assume that $\\{\theta,\min f(\theta)=f^{*}\\}$ is not empty. One
such example $f(x)=x^{2}+3sin^{2}(x)$ is non-convex, yet satisfying the PL
inequality with $f^{*}=0$ and $\mu=1/32$.

In Theorem 3.4 below, we present convergence rates of AEGD in three different
cases: nonconvex with the PL property, convex and strongly convex. For general
$\eta$, convergence rates can depend on the behavior of $r_{k}$, which is part
of the solution to the AEGD algorithm. Therefore, we present a hybrid result
of convergence rates combining both $k$ and $r_{k}$ (a posterior estimates).

######  Theorem 3.4.

(Convergence rates) Suppose $f$ is differentiable and bounded from below. Let
$\theta_{k}$ be the $k$-th iterate generated by AEGD (15), then

$\frac{1}{k}\sum_{j=0}^{k-1}\|\nabla
g(\theta_{j})\|^{2}\leq\frac{\sqrt{f(\theta_{0})+c}}{2\eta kr_{k}}.$

We have convergence rates in three distinct cases:
(i) $f$ is PL and $L$-smooth with a minimizer $\theta^{*}$. If
$\max_{k_{0}\leq j<k}\eta_{j}\leq 1/L$ for some $k_{0}\geq 0$, then
$\\{\theta_{k}\\}$ is convergent. Moreover,

(17)
$\displaystyle\sum_{k=k_{0}}^{\infty}\|\theta_{k+1}-\theta_{k}\|\leq\frac{4}{\sqrt{2\mu}}\sqrt{f(\theta_{k_{0}})-f(\theta^{*})},$
$\displaystyle f(\theta_{k})-f(\theta^{*})\leq
e^{-c_{0}(k-k_{0})r_{k}}(f(\theta_{k_{0}})-f(\theta^{*})),\quad
c_{0}:=\frac{\mu\eta}{\sqrt{f(\theta_{k_{0}})+c}}.$

(ii) $f$ is convex and $L$-smooth with a global minimizer $\theta^{*}$. If
$\max_{k_{0}\leq j<k}\eta_{j}\leq 1/L$ for some $k_{0}\geq 0$, then

$f(\theta_{k})-f(\theta^{*})\leq\frac{c_{1}\|\theta_{k_{0}}-\theta^{*}\|^{2}}{2(k-k_{0})r_{k}},\;c_{1}:=\frac{\sqrt{f(\theta_{k_{0}})+c}}{\eta}.$

(iii) $f$ is $\alpha$-strongly convex and $L$-smooth with the global minimizer
$\theta^{*}$. Assume that $\max_{k_{0}\leq j<k}\eta_{j}\leq\frac{2}{\alpha+L}$
for some $k_{0}\geq 0$, then

$\|\theta_{k}-\theta^{*}\|\leq
e^{-c_{2}(k-k_{0})r_{k}}\|\theta_{k_{0}}-\theta^{*}\|,\quad
c_{2}:=\frac{\alpha\eta}{\sqrt{f(\theta_{k_{0}})+c}}.$

See Appendix A.1 for the proof.

######  Remark 3.5.

The gradient estimate in Theorem 3.4 when using $g(\theta)=\sqrt{f(\theta)+c}$
gives

$\frac{1}{k}\sum_{j=0}^{k-1}\|\nabla
f(\theta_{j})\|^{2}\leq\frac{2(f(\theta_{0})+c)^{\frac{1}{2}}(F_{k}+c)}{\eta
kr_{k}},\quad F_{k}=max_{j<k}f(\theta_{j}).$

For this estimate, neither $L$-smoothness nor step size restriction is needed.
This is in sharp contrast to the classical result for GD (see pages 29-31 in
[36]).

######  Remark 3.6.

Regarding the convergence rates, a series of remarks are in order.

  1. 1.

The convergence rate in (i) may be extended to the case when $f$ features the
more general KL property; see [3, 2] for relevant techniques in establishing
convergence rates for proximal and other gradient methods.

  2. 2.

If $r^{*}>0$, which is the case to be shown in Lemma 3.8 for $\eta<\tau$,
$r_{k}$ on the right of the three estimates in Theorem 3.4 can all be replaced
by $r^{*}(<r_{k})$, hence (i) guarantees the linear convergence rate when $f$
is PL; and (ii) recovers the usual sublinear rate $O(\frac{1}{k})$; while with
strict convexity, (iii) gives the usual linear convergence rate.

  3. 3.

It is clear that all results are valid as long as $r_{k}\to 0$ slower than
$1/k$. Our numerical tests indicate that for each objective function $f$ there
exists a sharp threshold $\tilde{\eta}$ in the sense that convergence is
ensured if $\eta\leq\tilde{\eta}$. However, identifying $\tilde{\eta}$ appears
to be a challenging task in theory.

######  Remark 3.7.

Regarding the base step size $\eta$, we make further remarks.

  1. 1.

Empirical evidence (see Figure 2 (c)) shows that there exists a threshold
index $J$ so that $\eta_{j}$ turns to decrease for $j>J$. Hence the
assumptions in (i)-(iii) are reasonable and readily met.

  2. 2.

Our results suggest that decaying $\eta$ at a later stage (say $k\geq k_{0}$
for some $k_{0}$) to ensure the sufficient conditions in Theorem 3.4 can help
to achieve all-time good performance of the AEGD algorithm. This comment
applies to the element-wise AEGD as well (see Theorem 3.11).

###  3.3 Behavior of the energy

Since $r_{k}$ is strictly decreasing and $g(\theta_{k})$ is positive and
bounded from below and above, their relative ratio $\eta_{k}$ essentially
depends on the behavior of $r_{k}$. On the other hand, as $\eta\to 0$, the
numerical solution $(\theta_{k},r_{k})$ may be shown to converge to the
solution of the ODE system

(18) $\displaystyle\dot{\theta}=-2r\nabla g,\quad\dot{r}=\nabla
g\cdot\dot{\theta}$

at $t_{k}=k\eta$, subject to initial data
$\theta(0)=\theta_{0},r(0)=g(\theta_{0})$. For this system the level set
$r(t)-g(\theta(t))=0$ is invariant for all time. Hence for a fixed but
suitably small $\eta$, starting from $(\theta_{0},g(\theta_{0}))$, the limit
of $(\theta_{k},r_{k})$ as $k\to\infty$ must be approaching to
$(\theta^{*},g(\theta^{*}))$, that is

$r^{*}=g(\theta^{*})>0.$

A natural question is whether a threshold for the base step size $\eta$ can be
identified so that we will still have $r^{*}>0$ for any $\eta<\tau$. Indeed,
we are able to obtain a sufficient condition to ensure this.

######  Lemma 3.8.

Suppose $f$ is $L$-smooth, bounded from below by $f(\theta^{*})$ and we have
$\max\|\nabla f(\theta)\|\leq G_{\infty}$, then $g$ is $L_{g}$-smooth with

$g\geq g(\theta^{*})=\sqrt{f(\theta^{*})+c},\quad
L_{g}=\frac{1}{2g(\theta^{*})}\left(L+\frac{G_{\infty}^{2}}{2g^{2}(\theta^{*})}\right).$

Consider AEGD (8), then

$r_{k}>r^{*}>g(\theta^{*})(1-\eta/\tau),\quad\tau:=\frac{2g(\theta^{*})}{L_{g}(g(\theta_{0}))^{2}}.$

This implies that $r^{*}>0$ if $\eta\leq\tau$.

######  Proof 3.9.

For any $x,y\in\\{\theta_{k}\\}_{j=0}^{T}$ we have

$\displaystyle\|\nabla g(x)-\nabla g(y)\|$
$\displaystyle=\frac{1}{2}\bigg{\|}\frac{\nabla
f(x)(g(y)-g(x))}{g(x)g(y)}+\frac{\nabla f(x)-\nabla f(y)}{g(y)}\bigg{\|}$
$\displaystyle\leq\frac{G_{\infty}}{2(g(\theta^{*}))^{2}}|g(y)-g(x)|+\frac{1}{2g(\theta^{*})}\|\nabla
f(x)-\nabla f(y)\|\leq L_{g}\|x-y\|.$

Such $L_{g}$-smoothness of $g$ implies that

$\displaystyle g(\theta_{j+1})$ $\displaystyle\leq g(\theta_{j})+\nabla
g(\theta_{j})\cdot(\theta_{j+1}-\theta_{j})+\frac{L_{g}}{2}\|\theta_{j+1}-\theta_{j}\|^{2}$
$\displaystyle=g(\theta_{j})+r_{j+1}-r_{j}+\frac{L_{g}}{2}\|\theta_{j+1}-\theta_{j}\|^{2}.$

Take a summation over $j$ from $0$ to $k-1$ so that

$\displaystyle g(\theta_{k})-g(\theta_{0})$ $\displaystyle\leq
r_{k}-r_{0}+\frac{L_{g}}{2}\sum_{j=0}^{k-1}\|\theta_{j+1}-\theta_{j}\|^{2}$
$\displaystyle=r_{k}-r_{0}+\frac{L_{g}\eta}{2}\sum_{j=0}^{k-1}\left(r^{2}_{j}-r^{2}_{j+1}-(r_{j+1}-r_{j})^{2}\right)$
$\displaystyle=r_{k}-r_{0}+\frac{L_{g}\eta}{2}\left(r^{2}_{0}-r^{2}_{k}-\sum_{j=0}^{k-1}(r_{j+1}-r_{j})^{2}\right),$

where (11) was used. Using $r_{0}=g(\theta_{0})$ and $g(\theta_{k})\geq
g(\theta^{*})$, we have for any $k$,

$\frac{L_{g}\eta}{2}\sum_{j=0}^{k-1}(r_{j+1}-r_{j})^{2}+\frac{L_{g}\eta}{2}r^{2}_{k}-r_{k}+g(\theta^{*})-\frac{L_{g}\eta}{2}(g(\theta_{0}))^{2}\leq
0.$

Passing to the limit as $k\to\infty$, we also have

$\frac{L_{g}\eta}{2}\sum_{j=0}^{\infty}(r_{j+1}-r_{j})^{2}+\frac{L_{g}\eta}{2}(r^{*})^{2}-r^{*}+g(\theta^{*})(1-\eta/\tau)\leq
0.$

Hence $r^{*}>g(\theta^{*})(1-\eta/\tau).$

######  Remark 3.10.

1\. Note that $\eta<\tau$ is only a sufficient condition, not necessary for
$r^{*}>0$ to surely happen.
2\. One may take a suitably large $\eta$ to gain initial rapid progress, and
adjust $\eta$ at a later stage at $k=k_{0}$. A similar argument shows that
$r^{*}>0$ is ensured by $\eta<\tau_{1}$ for $k\geq k_{0}$,

(19)
$\eta<\tau_{1}:=\frac{2(g(\theta^{*})+r_{k_{0}}-g(\theta_{k_{0}}))}{L_{g}r^{2}_{k_{0}}}.$

As we expected, for small $\eta$, AEGD features same convergence rates as GD
does, since the rates are essentially depending on the local geometry of $f$
near $\theta^{*}$.

###  3.4 Convergence results for the element-wise AEGD

Similar results also hold for the element-wise AEGD (9), although analysis is
more involved. With the notation

$\eta_{ij}:=\eta r_{j+1,i}/g(\theta_{j}),\;i\in[n],\quad j=0,1,2,\cdots,$

we now present the main result for (9) in the following.

######  Theorem 3.11.

(Convergence rates) Suppose $f$ is differentiable and bounded from below. Let
$\theta_{k}$ be the $k$-th iterate generated by the AEGD (9), then

$\min_{j<k}(\partial_{i}g(\theta_{j}))^{2}\leq\frac{1}{k}\sum_{j=0}^{k-1}(\partial_{i}g(\theta_{j}))^{2}\leq\cfrac{\sqrt{f(\theta_{0})+c}}{2\eta
kr_{k,i}},\quad i\in[n].$

We have convergence rates in three distinct cases:
(i) $f$ is PL and $L$-smooth with a minimizer $\theta^{*}$. If
$\max_{k_{0}\leq j\leq k}\eta_{ij}\leq\frac{1}{L}$ for $i\in[n]$ and some
$k_{0}\geq 0$, then

$\displaystyle f(\theta_{k})-f(\theta^{*})\leq
e^{-c_{0}(k-k_{0})\min_{i}r_{k,i}}(f(\theta_{k_{0}})-f(\theta^{*})),\quad
c_{0}:=\frac{\mu\eta}{\sqrt{f(\theta_{k_{0}})+c}}.$

(ii) $f$ is convex and $L$-smooth with a global minimizer $\theta^{*}$. If
$\max_{k_{0}\leq j<k}\eta_{ij}\leq\frac{1}{L}$ for $i\in[n]$ and some
$k_{0}\geq 0$, then

$f(\theta_{k})-f(\theta^{*})\leq\frac{c_{1}\max_{k_{0}\leq
j<k}\|\theta_{j}-\theta^{*}\|^{2}}{(k-k_{0})\min_{i}r_{k,i}},\;c_{1}:=\frac{\sqrt{f(\theta_{k_{0}})+c}}{\eta}.$

(iii) $f$ is $\alpha-$strongly convex and $L$-smooth with the global minimizer
$\theta^{*}$. Assume that $\max_{k_{0}\leq
j<k}\eta_{ij}\leq\frac{2}{\alpha+L}$ for $i\in[n]$ and some $k_{0}\geq 0$,
then

$\|\theta_{k}-\theta^{*}\|\leq
e^{-c_{2}(k-k_{0})\min_{i}r_{k,i}}\|\theta_{k_{0}}-\theta^{*}\|,\quad
c_{2}:=\frac{\alpha\eta}{\sqrt{f(\theta_{k_{0}})+c})}.$

See Appendix A.3 for the proof.

######  Remark 3.12.

The above gradient estimate when using $g(\theta)=\sqrt{f(\theta)+c}$ leads to

$\min_{j<k}(\partial_{i}f(\theta_{j}))^{2}\leq\frac{1}{k}\sum_{j=0}^{k-1}(\partial_{i}f(\theta_{j}))^{2}\leq\cfrac{2(f(\theta_{0})+c)^{\frac{1}{2}}(F_{k}+c)}{\eta
kr_{k,i}},\quad F_{k}=max_{j<k}f(\theta_{j}).$

As argued above, our convergence rates in Theorem 3.11 depend also on the
behavior of $r_{k,i}$, about which we have the following result.

######  Lemma 3.13.

Under the same assumptions as in Lemma 3.8, for AEGD (9) we have for
$i\in[n]$,

$r_{k,i}>r_{i}^{*}>g(\theta^{*})(1-\eta/\tilde{\tau}),\quad\tilde{\tau}:=\frac{2g(\theta^{*})}{nL_{g}(g(\theta_{0}))^{2}}.$

This implies that $r_{i}^{*}>0$ if $\eta<\tilde{\tau}$.

We include a proof in Appendix A.2.

##  4 Stochastic AEGD

This section presents a stochastic AEGD algorithm for the unconstrained
finite-sum optimization problem:

(20)
$\min_{\theta}\left\\{f(\theta)=\frac{1}{m}\sum_{i=1}^{m}f_{i}(\theta)\right\\}.$

We use $\theta^{*}$ to denote a minimizer of $f(\theta)$, and assume that
$f_{i}$ is differentiable and lower bounded so that $f_{i}(\theta)>-c$, for
$i\in[m]$, for some $c>0$. This problem is prevalent in machine learning tasks
where $\theta$ corresponds to the model parameters, $f_{i}(\theta)$ represents
the loss on the training point $i$ and the aim is to minimize the average loss
$f(\theta)$ across points. When $m$ is large, SGD or its variants are
preferred for solving (20) mainly because of their cheap per iteration cost.
To present a stochastic algorithm, we use $v_{k}$ to denote a random search
direction at $k$-th step. Here we give only the element-wise version of our
stochastic AEGD algorithm.

Algorithm 1 Stochastic AEGD. Good default setting for parameters are $c=1$ and
$\eta=0.1$.

1:$\\{f_{i}({\theta})\\}_{i=1}^{m}$, $\eta$: the step size, $\theta_{0}$:
initial guess of $\theta$, and $T$: the total number of iterations.

2:$c$: a parameter such that for any $i\in[m]$, $f_{i}({\theta})+c>0$ for all
$\theta\in\mathbb{R}^{n}$, initial energy:
$r_{0}=\sqrt{f_{i_{0}}(\theta_{0})+c}{\bf 1}$

3:for $k=0$ to $k-1$ do

4: $v_{k}:=\nabla
f_{i_{k}}(\theta_{k})/\big{(}2\sqrt{f_{i_{k}}(\theta_{k})+c}\big{)}$ ($i_{k}$
is a random sample from $[m]$ at step $k$)

5: $r_{k+1}=r_{k}/(1+2\eta v_{k}\odot v_{k})$ (update energy)

6: $\theta_{k+1}=\theta_{k}-2\eta r_{k+1}\odot v_{k}$

7:end for

8:return $\theta_{k}$

######  Remark 4.1.

If at each iteration step, a mini-batch of training data were selected,
Algorithm 1 still applies if $f_{i_{k}}(\theta_{k})$ is replaced by
$\frac{1}{b}\sum_{i\in B_{k}}f_{i}(\theta_{k}),$ where $B_{k}$ denotes a
randomly selected subset of $[m]$ of size $b$ at step $k$ with $b\ll m$.

To allow for any form of minibatching we use the arbitrary sampling notation

$f_{\xi}(\theta)=\frac{1}{m}\sum_{j=1}^{m}\xi_{j}f_{j}(\theta),$

where $\xi=(\xi^{1},\cdots,\xi^{m})\in\mathbb{R}^{m}_{+}$ is a random sampling
vector (drawn from some distribution) such that $\mathbb{E}[\xi^{j}]=1$ for
$j\in[m].$ The element-wise update rule for the stochastic AEGD with arbitrary
sampling can be reformulated as

(21a) $\displaystyle v_{k}=\nabla
f_{\xi_{k}}(\theta_{k})/(2\sqrt{f_{\xi_{k}}(\theta_{k})+c}),$ (21b)
$\displaystyle r_{k+1,i}-r_{k,i}=v_{k,i}(\theta_{k+1,i}-\theta_{k,i}),\quad
r_{0,i}=\sqrt{f_{\xi_{0}}(\theta_{0})+c}$ (21c)
$\displaystyle\theta_{k+1,i}=\theta_{k,i}-2\eta r_{k+1,i}v_{k,i}\quad
k=0,1,2,\cdots.$

It follows immediately from the definition of sampling vector $\xi$ that

$\mathbb{E}[f_{\xi}(\theta)]=f(\theta),\quad\mathbb{E}[\nabla
f_{\xi}(\theta)]=\nabla f(\theta),$

which means that we still have access to unbiased estimates of $f$ and its
gradient. Of particular interest is the minibatch sampling:
$\xi\in\mathbb{R}^{m}_{+}$ is a b-minibatch sampling if for every subset
$B\in[m]$ with $|B|=b$ we have that

$\mathbb{P}\left[\xi=\frac{m}{b}\sum_{i\in
B}e_{i}\right]=\frac{b!(m-b)!}{m!}.$

One can show by a double counting argument that if $\xi$ is a $b-$minibatch
sampling, it is indeed a valid sampling with $\mathbb{E}[\xi^{j}]=1$ (see
[16]) and $\frac{1}{m}\sum_{j=1}^{m}\xi^{j}=1$.

No matter how $v_{k}$ is defined, we have the following result.

######  Theorem 4.2.

(Unconditional energy stability) The stochastic AEGD of form (21) is
unconditionally energy stable in the sense that for any step size $\eta>0$,

(22)
$\mathbb{E}[r^{2}_{k+1,i}]=\mathbb{E}[r^{2}_{k,i}]-\mathbb{E}[(r_{k+1,i}-r_{k,i})^{2}]-\eta^{-1}\mathbb{E}[(\theta_{k+1,i}-\theta_{k,i})^{2}],\quad
i\in[n],$

that is $\mathbb{E}[r_{k,i}]$ is strictly decreasing and convergent with
$\mathbb{E}[r_{k,i}]\to r_{i}^{*}$ as $k\to\infty$, and also

(23)
$\lim_{k\to\infty}\mathbb{E}[(\theta_{k+1,i}-\theta_{k,i})^{2}]=0,\quad\sum_{j=0}^{\infty}\mathbb{E}[(\theta_{j+1,i}-\theta_{j,i})^{2}]\leq\eta(f(\theta_{0})+c),\quad\forall
i\in[n].$

The proof is entirely similar to that for Theorem 3.1, details are omitted.

Due to the nonlinearity of $v_{k}$ in terms of the random variables, we only
have $2\mathbb{E}\left[v_{k}\sqrt{f_{\xi_{k}}(\theta_{k})+c}\right]=\nabla
f(\theta_{k}),$ the estimate of convergence rates can be quite subtle.
Nevertheless, with mild assumptions on $f_{l}$ we are able to establish the
following.

######  Theorem 4.3.

Suppose $\|\nabla f_{l}\|_{\infty}\leq G_{\infty}$, and $f_{l}+c\geq a>0$ for
all $l\in[m]$. Then stochastic AEGD of form (21) admits the following
direction-wise estimate, for $i\in[n]$,

$\frac{1}{k}\sum_{j=0}^{k}\mathbb{E}[(v_{j,i})^{2}]\leq\frac{C_{i}}{k\mathbb{E}[r_{k,i}]},\quad
C_{i}:=\frac{\mathbb{E}[r_{0,i}](2a+\eta G^{2}_{\infty})}{4a\eta}.$

The proof is given in Appendix A.4.

##  5 Experimental Results

We evaluate the deterministic AEGD (9) and stochastic AEGD (Algorithm 1) on
several benchmarks for optimization, including convex and non-convex
performance testing problems, k-means clustering, which has a non-smooth
objective function, and convolutional neural networks on the standard CIFAR-10
and CIFAR-100 data sets. Overall, we show that AEGD is a versatile algorithm
that can efficiently solve a variety of optimization problems.

In all experiments, we fine tune the base step size for each algorithm to
obtain its best performance. The base step size is given in respective plots,
denoted as “lr”, the momentum in GDM and stochastic GDM (SGDM) is set to
$0.9$. For AEGD we found that the parameters that impacts performance the most
were the base step size and step decay schedule in the deep learning
experiments. We, therefore, leave the energy parameter $c$ with the default
value $1$.

Our experiments show the following primary findings: (i) AEGD allows larger
effective step size, hence converges much faster than GD; (ii) Empirically the
performance of AEGD appears better than or at least comparable with (S)GDM: in
full batch setting, AEGD typically displays rapid initial progress while GDM
tends to overshoot and detour to the target; in stochastic setting, AEGD
produces solutions that generalize better than SGDM when coupled with a
learning rate decay schedule.

###  5.1 Performance Testing Problems

We begin with comparing AEGD with GD and GDM on two benchmark convex and non-
convex performance testing problems for optimization algorithms. Consider
searching the minima $x^{*}$ of the following quadratic function (a strongly
convex function with $\alpha=2/100$ and $L=2$)

(24)
$f(x_{1},x_{2},...,x_{100})=\sum_{i=1}^{50}x^{2}_{2i-1}+\sum_{i=1}^{50}\frac{x^{2}_{2i}}{10^{2}},$

and the 2D Rosenbrock function (non-convex and $L$-smooth)

(25) $f(x_{1},x_{2})=(1-x_{1})^{2}+100(x_{2}-x_{1}^{2})^{2}.$

The initial points for (24) and (25) are set to $(1,1,...,1)$ and $(-3,-4)$,
respectively. Numerical comparison results are in Figure 1 (a) for the
quadratic function and Figure 2 (a) for the Rosenbrock function. We see that
AEGD converges much faster than both GD and GDM on the quadratic problem. For
the Rosenbrock problem, the convergence of GD is very slow compared with GDM
and AEGD. Though the number of iterations that AEGD needs to reach the minima
is slightly more than GDM, AEGD makes a faster initial progress. This can be
observed more clearly in Figure 3, which shows that GD and GDM tend to
overshoot and detour to the minima while AEGD goes along a more direct path to
the minima.

(a)

(b)

(c)

Figure 1: The quadratic problem: (a) Optimality gap of different algorithms;
(b) Behavior of $r_{k,1}$ for different $\eta$; (c) Behavior of $\eta_{1k}$
for different $\eta$.

(a)

(b)

(c)

Figure 2: The Rosenbrock problem: (a) Optimality gap of different algorithms;
(b) Behavior of $r_{k,1}$ for different $\eta$; (c) Behavior of $\eta_{1k}$
for different $\eta$.

We also investigated how the basestep size $\eta$ affects the behavior of
$r_{k}$ of AEGD on the two problems. (For both functions,
$r_{k,1}=\min_{i}r_{k,i}$, hence we only show the behavior of $r_{k,1}$.) The
results are presented in Figure 1 (b) for the quadratic problem and Figure 2
(b) for the Rosenbrock problem. From these results, there appears to exist a
threshold $\tilde{\eta}$ such that when $\eta<\tilde{\eta}$, $r^{*}>0$; when
$\eta>\tilde{\eta}$, $r^{*}=0$; when $\eta=\tilde{\eta}$, $r_{k}$ converges to
$0$ at the speed rate of $O(1/k)$; and when $\eta\leq\tilde{\eta}$, AEGD
converges to the minima. We conjecture that such critical threshold phenomenon
for the basestep size $\eta$ should hold true for more general objective
functions.

Specifically, for the quadratic problem: $\tilde{\eta}\sim 26.51$; for the
Rosenbrock problem, $\tilde{\eta}\sim 8.4e-4$. Based on our tests, the largest
step size GD allows to ensure convergence is $1$ for the quadratic problem and
$\sim 3.94e-4$ for the Rosenbrock problem. In both cases, $\tilde{\eta}$ is
much larger than the admissible step sizes for GD.

Figure 3: Trajectories of different optimization algorithms on the Rosenbrock
function.

###  5.2 K-means Clustering

We consider $k$-means clustering problem for a set of data points
$\\{\bm{p}_{i}\\}^{m}_{i=1}$ in $\mathbb{R}^{d}$ with $K$ centroids
$\\{\bm{x}_{j}\\}^{K}_{j=1}$. Denote
$\bm{x}=[\bm{x}_{1},\cdots,\bm{x}_{K}]\in\mathbb{R}^{Kd}$, we seek to minimize
the quantization error:

(26)
$\min_{\bm{x}\in\mathbb{R}^{Kd}}\left\\{f(\bm{x}):=\frac{1}{2m}\sum_{i=1}^{m}\min_{1\leq
j\leq K}\|\bm{x}_{j}-\bm{p}_{i}\|^{2}\right\\}.$

If a data point $\bm{p}_{i}$ has more than one distinct nearest centroids, we
assign $\bm{p}_{i}$ to one of them randomly. We define the gradient of $f$
(presented in Appendix B.1) as [8] did when applying the gradient-based
method. In this example, the Iris data set, which contains $150$ four-
dimensional data samples from $3$ categories, is used to compare the
robustness to initialization of three methods: GD, AEGD, and expectation
maximization (EM) [30].

(a)

(b)

(c)

(d)

Figure 4: The histogram of the quantization error of $k$-means on Iris trained
by EM (a), GD (b) and AEGD (c) over $100$ independent experiments. (d)
Frequency of GD and AEGD achieve the improved minimum valued at $\sim 0.26$ in
$100$ runs with different base step sizes.

Figure 4 (a) (b) (c) present the frequency of error given by the three methods
in $100$ runs. In each run, the initial centroids are selected from the data
set randomly. We see that though there are chances for all the three methods
to get stuck at a local minimum whose value is $\sim 0.48$, AEGD managed to
locate an improved minimum valued at $\sim 0.26$ with the highest probability.

We also present the frequency of GD and AEGD achieving the improved minimum in
$100$ runs with different base step sizes in Figure 4 (d). We see that
compared with GD, AEGD allows a larger set of base step size to achieve the
improved minimum with much higher probability, with $\eta\sim 6.5$ being the
optimal choice.

###  5.3 Convolutional Neural Networks

First, we should point out that the generalization capability of AEGD in
training deep neural networks remains to be further understood. However, we
would like to present some preliminary results to show the potential of the
AEGD in this aspect.

(a) Training loss, ResNet-56, CIFAR-10

(b) Test accuracy, ResNet-56, CIFAR-10

(c) Training loss, SqueezeNet, CIFAR-100

(d) Test accuracy, SqueezeNet, CIFAR-100

Figure 5: Training loss and test accuracy for ResNet-56 on CIFAR-10 and
SqueezeNet on CIFAR-100

Using ResNet-56 [17] and SqueezeNet [18], we consider the task of image
classification on the standard CIFAR-10 and CIFAR-100 datasets. In our
experiments, we employ the fixed budget of 200 epochs and reduce the learning
rates by 10 after 150 epochs, with a minibatch size of $128$ and weight decay
of $1\times 10^{-4}$. We recall that weight decay has been a standard trick in
training neural networks [6, 23]. For SGD, it can be interpreted as a form of
$L^{2}$ regularization, but for adaptive algorithms such as Adam, careful
implementation techniques are often needed [33, 57, 61]. Inspired by [33], we
introduce an AEGD-specific weight decay algorithm, called AEGDW. The algorithm
for AEGDW and the initial set of step sizes are presented in Appendix B.2.

Our experimental results, as given in Figure 5, show that Adam and AdamW
perform better than other algorithms early. But by epoch $150$ when the
learning rates are decayed, AEGD and AEGDW significantly outperform other
methods in generalization. In the above two experiments, AEGD(W) even
surpasses SGDM by $1\%$ in test accuracy.

##  6 Conclusions

Inspired by the IEQ approach for gradient flows in the form of time-dependent
partial differential equations, we proposed AEGD in both global and element-
wise form, as a new algorithm for first-order gradient-based optimization of
non-convex objective functions. This simple update with an auxiliary energy
variable is easy to implement, proven to be unconditionally energy stable
irrespective of the step size, and features energy-dependent convergence rates
with mild conditions on the step size. It is suitable for general objective
functions, as long as they are bounded from below. Numerical examples ranging
from performance test problems, K-means clustering, to CNNs, all demonstrate
the advantages of the proposed AEGD: it enjoys rapid initial progress and
faster convergence than GD, is robust with respect to initial data, and
generalizes better for deep learning problems. Overall, the results presented
in this paper suggest that further research of AEGD could prove useful.

##  Appendix A Technical Proofs

In this section, we prove Theorem 3.4 and Theorem 3.11 from Section 3.

###  A.1 Proof of Theorem 3.4

We rewrite AEGD (8) as

(27) $\theta_{k+1}=\theta_{k}-\eta_{k}\nabla
f(\theta_{k}),\quad\eta_{k}:=\eta\frac{r_{k+1}}{g(\theta_{k})}.$

This is in the form of the usual GD with a variable step size $\eta_{k}$.
(i) Using scheme (7) we have

$r_{j+1}-r_{j}=\nabla g(\theta_{j})\cdot(\theta_{j+1}-\theta_{j})=-2\eta
r_{j+1}\|\nabla g(\theta_{j})\|^{2}.$

Take a summation over $j$ from $0$ to $k-1$ gives

$r_{0}-r_{k}=2\eta\sum_{j=0}^{k-1}r_{j+1}\|\nabla g(\theta_{j})\|^{2}\geq
2\eta r_{k}\sum_{j=0}^{k-1}\|\nabla g(\theta_{j})\|^{2}$

Use $r_{0}=g(\theta_{0})$ and $r_{k}$ is strictly decreasing to get

$k\min_{j<k}\|\nabla g(\theta_{j})\|^{2}\leq\sum_{j=0}^{k-1}\|\nabla
g(\theta_{j})\|^{2}\leq\frac{g(\theta_{0})}{2\eta r_{k}}.$

Next we prove (i), (ii) and (iii), taking $k_{0}=0$, for simplicity in
presentation.
(i) By L-smoothness of $f$ and scheme (27), we have

(28) $\displaystyle f(\theta_{k+1})-f(\theta_{k})$ $\displaystyle\leq\nabla
f(\theta_{k})\cdot(\theta_{k+1}-\theta_{k})+\frac{L}{2}\|\theta_{k+1}-\theta_{k}\|^{2}$
$\displaystyle\leq-\frac{\eta_{k}}{2}(2-L\eta_{k})\|\nabla
f(\theta_{k})\|^{2}\leq-\frac{\eta_{k}}{2}\|\nabla f(\theta_{k})\|^{2}$

as long as $\eta_{k}\leq 1/L$. Here and in what follows, we denote
$w_{k}=f(\theta_{k})-f^{*}$, then the PL property reads

$\frac{1}{2}\|\nabla f(\theta_{k})\|^{2}\geq\mu(f(\theta_{k})-f^{*})=\mu
w_{k}.$

With this property, (28) can be written as

$w_{k+1}-w_{k}\leq-\mu\eta_{k}w_{k}.$

This implies $w_{k+1}\leq(1-\mu\eta_{k})w_{k}$. By induction,

$\displaystyle w_{k}$
$\displaystyle\leq\prod_{j=0}^{k-1}(1-\mu\eta_{j})w_{0}=\exp\left(\sum_{j=0}^{k-1}{\rm
log}(1-\mu\eta_{j})\right)w_{0}\leq\exp\left(-\mu\sum_{j=0}^{k-1}\eta_{j}\right)w_{0}.$

Noticing that
$\eta_{j}=\eta\frac{r_{j+1}}{g(\theta_{j})}\geq\eta\frac{r_{k}}{g(\theta_{0})},$
we further get

$w_{k}\leq\exp(-c_{0}kr_{k})w_{0},\quad c_{0}=\frac{\mu\eta}{g(\theta_{0})}.$

To obtain the convergence of $\theta_{k}$, we use scheme (27) to rewrite (28)
as

$f(\theta_{k})-f(\theta_{k+1})\geq\frac{1}{2\eta_{k}}\|\theta_{k+1}-\theta_{k}\|^{2}\quad\Rightarrow\quad
w_{k}-w_{k+1}\geq\frac{1}{2\eta_{k}}\|\theta_{k+1}-\theta_{k}\|^{2}.$

The PL property when combined with (27) gives

$\|\theta_{k+1}-\theta_{k}\|^{2}\geq
2\mu\eta^{2}_{k}w_{k}\quad\Rightarrow\quad\frac{1}{\sqrt{w_{k}}}\geq\frac{\sqrt{2\mu}\eta_{k}}{\|\theta_{k+1}-\theta_{k}\|}.$

Using the above two inequalities and noting that $w_{k}\geq w_{k+1}$, we have

$\displaystyle\sqrt{w_{k}}-\sqrt{w_{k+1}}$
$\displaystyle\geq\frac{1}{2\sqrt{w_{k}}}(w_{k}-w_{k+1})\geq\frac{\sqrt{2\mu}}{4}\|\theta_{k+1}-\theta_{k}\|.$

Taking a summation over $k$ from $0$ to $\infty$ gives

$\sum_{k=0}^{\infty}\|\theta_{k+1}-\theta_{k}\|\leq\frac{4}{\sqrt{2\mu}}\sqrt{w_{0}}.$

This yields (17), which ensures the convergence of $\\{\theta_{k}\\}$.
(ii) By the $L$-smoothness assumption, scheme (27) and $\eta_{k}\leq 1/L$, as
in (i) we obtain

$f(\theta_{k+1})\leq
f(\theta_{k})-\frac{1}{2\eta_{k}}\|\theta_{k+1}-\theta_{k}\|^{2}.$

Denoting $d_{k}:=\|\theta_{k}-\theta^{*}\|$, we proceed to obtain the
convergence rate. By convexity of $f$,

$f(\theta_{k})\leq f(\theta^{*})+\nabla
f(\theta_{k})\cdot(\theta_{k}-\theta^{*}).$

These when combined lead to

$\displaystyle w_{k+1}$ $\displaystyle\leq\frac{1}{2\eta_{k}}(2\eta_{k}\nabla
f(\theta_{k})\cdot(\theta_{k}-\theta^{*})-\|\theta_{k+1}-\theta_{k}\|^{2})$
$\displaystyle=\frac{1}{2\eta_{k}}(-2(\theta_{k+1}-\theta_{k})\cdot(\theta_{k}-\theta^{*})-\|\theta_{k+1}-\theta_{k}\|^{2})$
$\displaystyle=\frac{1}{2\eta_{k}}(d_{k}^{2}-d_{k+1}^{2}).$

Upon summation over iteration steps, we have

$d_{0}^{2}-d_{k}^{2}=2\sum_{j=0}^{k-1}\eta_{i}w_{i+1}\geq
w_{k}\sum_{j=0}^{k-1}\eta_{i}\geq 2kw_{k}\frac{\eta r_{k}}{g(\theta_{0})}.$

Hence for $\max_{j<k}\eta_{j}\leq 1/L$, we have

$f(\theta_{k})-f(\theta^{*})=w_{k}\leq\frac{\|\theta_{0}-\theta^{*}\|^{2}g(\theta_{0})}{2k\eta
r_{k}}.$

(iii) To obtain the convergence rate of $\theta_{k}$, we proceed with

$\displaystyle\theta_{k+1}-\theta^{*}$
$\displaystyle=\theta_{k}-\theta^{*}-\eta_{k}\nabla f(\theta_{k})$
$\displaystyle=\theta_{k}-\theta^{*}-\eta_{k}(\nabla f(\theta_{k})-\nabla
f(\theta^{*}))$
$\displaystyle=\theta_{k}-\theta^{*}-\eta_{k}\left(\int_{0}^{1}\nabla^{2}f(\theta^{*}+s(\theta_{k}-\theta^{*}))ds=:A_{k}\right)(\theta_{k}-\theta^{*}).$

Therefore,

$\displaystyle d_{k+1}$
$\displaystyle=\|(I-\eta_{k}A_{k})(\theta_{k}-\theta^{*})\|$
$\displaystyle\leq\|I-\eta_{k}A_{k}\|d_{k}\leq\Pi_{i=0}^{k}\|I-\eta_{i}A_{i}\|d_{0}$
$\displaystyle\leq\max_{\alpha\leq\lambda\leq
L}\Pi_{i=0}^{k}|1-\eta_{i}\lambda|d_{0}.$

For $\max_{j<k}\eta_{j}\leq\frac{2}{\alpha+L}$, we have

$\displaystyle d_{k}$
$\displaystyle\leq\Pi_{i=0}^{k-1}(1-\eta_{i}\alpha)d_{0}\leq
e^{-c_{2}kr_{k}}d_{0},\quad c_{2}=\frac{\alpha\eta}{g(\theta_{0})}.$

This completes the proof.

###  A.2 Proof of Lemma 3.13

The $L_{g}$-smoothness of $g$ implies that

$\displaystyle g(\theta_{j+1})$ $\displaystyle\leq g(\theta_{j})+\nabla
g(\theta_{j})\cdot(\theta_{j+1}-\theta_{j})+\frac{L_{g}}{2}\|\theta_{j+1}-\theta_{j}\|^{2}$
$\displaystyle=g(\theta_{j})+\sum_{i=1}^{n}\partial_{i}g(\theta_{j})(\theta_{j+1,i}-\theta_{j,i})+\frac{L_{g}}{2}\sum_{i=1}^{n}(\theta_{j+1,i}-\theta_{j,i})^{2}$
$\displaystyle\leq g(\theta_{j})+\sum_{i=1}^{n}(r_{j+1,i}-r_{j,i})+\frac{\eta
L_{g}}{2}\sum_{i=1}^{n}(r^{2}_{j,i}-r^{2}_{j+1,i}).$

Take summation over $j$ from $0$ to $k-1$ and use $r_{0,i}=g(\theta_{0})$, so
that

$\displaystyle g(\theta_{k})-g(\theta_{0})$
$\displaystyle\leq\sum_{i=1}^{n}r_{k,i}-ng(\theta_{0})+\frac{\eta
L_{g}}{2}\left(n(g(\theta_{0}))^{2}-\sum_{i=1}^{n}r^{2}_{k,i}\right).$

Using $g(\theta_{k})\geq g(\theta^{*})$, we have for any $k$,

$-\sum_{i=1}^{n}r_{k,i}+g(\theta^{*})+(n-1)g(\theta_{0})-\frac{n\eta
L_{g}}{2}(g(\theta_{0}))^{2}\leq 0.$

Passing to the limit as $k\to\infty$, we also have

$-\sum_{i=1}^{n}r_{i}^{*}+g(\theta^{*})+(n-1)g(\theta_{0})-\frac{n\eta
L_{g}}{2}(g(\theta_{0}))^{2}\leq 0.$

From this we get

$-\left(\min_{i}r_{i}^{*}+(n-1)g(\theta_{0})\right)+g(\theta^{*})+(n-1)g(\theta_{0})-\frac{n\eta
L_{g}}{2}(g(\theta_{0}))^{2}\leq 0,$

which can be reduced to

$-\min_{i}r_{i}^{*}+g(\theta^{*})(1-\eta/\tilde{\tau})\leq
0,\quad\tilde{\tau}:=\frac{2g(\theta^{*})}{nL_{g}(g(\theta_{0}))^{2}}.$

Hence

$\min_{i}r_{i}^{*}>g(\theta^{*})(1-\eta/\tilde{\tau}).$

###  A.3 Proof of Theorem 3.11

We rewrite AEGD (9) for $i\in[n]$ as

(29)
$\theta_{k+1,i}=\theta_{k,i}-\eta_{ik}\partial_{i}f(\theta_{k}),\quad\eta_{ik}:=\eta\frac{r_{k+1,i}}{g(\theta_{k})}.$

(i) Using scheme (10), for $i\in[n]$ we have

$r_{j+1,i}-r_{j,i}=\partial_{i}g(\theta_{j})(\theta_{j+1,i}-\theta_{j,i})=-2\eta
r_{j+1,i}(\partial_{i}g(\theta_{j}))^{2}.$

Take summation over $j$ from $0$ to $k-1$ gives

$\displaystyle
r_{0,i}-r_{k,i}=2\eta\sum_{j=0}^{k-1}r_{j+1,i}(\partial_{i}g(\theta_{j}))^{2}\geq
2\eta r_{k,i}\sum_{j=0}^{k-1}(\partial_{i}g(\theta_{j}))^{2}$

Using $r_{0,i}=g(\theta_{0})$ and $r_{j,i}$ is strictly decreasing, we get

$k\min_{j<k}(\partial_{i}g(\theta_{j}))^{2}\leq\sum_{j=0}^{k-1}(\partial_{i}g(\theta_{j}))^{2}\leq\frac{g(\theta_{0})}{2\eta
r_{k,i}}.$

Next we turn to prove (i), (ii) and (iii). For simplicity in presentation, we
take $k_{0}=0$.
(i) By L-smoothness of $f$ and scheme (27), we have

$\displaystyle f(\theta_{k+1})-f(\theta_{k})$ $\displaystyle\leq\nabla
f(\theta_{k})\cdot(\theta_{k+1}-\theta_{k})+\frac{L}{2}\|\theta_{k+1}-\theta_{k}\|^{2}$
$\displaystyle\leq-\sum_{i=1}^{n}\frac{\eta_{ik}}{2}(\partial_{i}f(\theta_{k}))^{2}\leq-\frac{\min_{i}\eta_{ik}}{2}\|\nabla
f(\theta_{k})\|^{2}$

as long as $\eta_{ik}\leq 1/L$. As in the proof for Theorem 3.4 (i), we have

$\displaystyle
w_{k}\leq\exp\left(-\mu\sum_{j=0}^{k-1}\min_{i}\eta_{ij}\right)w_{0}.$

Noticing that
$\min_{i}\eta_{ij}=\min_{i}\eta\frac{r_{j+1,i}}{g(\theta_{j})}\geq\eta\frac{\min_{i}r_{k,i}}{g(\theta_{0})},$
we further get

$w_{k}\leq\exp(-c_{0}k\min_{i}r_{k,i})w_{0},\quad
c_{0}=\frac{\mu\eta}{g(\theta_{0})}.$

(ii) Using the L-smoothness assumption, scheme (9) and $\eta_{ik}\leq 1/L$, as
in (i) we obtain

$f(\theta_{k+1})\leq
f(\theta_{k})-\sum_{i=1}^{n}\frac{1}{2\eta_{ik}}(\theta_{k+1,i}-\theta_{k,i})^{2}.$

Denote $d_{ik}:=\theta_{k,i}-\theta_{i}^{*}$, then by convexity of $f$,

$f(\theta_{k})\leq f(\theta^{*})+\nabla
f(\theta_{k})\cdot(\theta_{k}-\theta^{*}).$

These when combined lead to

$\displaystyle w_{k+1}$
$\displaystyle\leq\sum_{i=1}^{n}\frac{1}{2\eta_{ik}}(2\eta_{ik}\partial_{i}f(\theta_{k})(\theta_{k,i}-\theta_{i}^{*})-(\theta_{k+1,i}-\theta_{k,i})^{2})$
$\displaystyle=\sum_{i=1}^{n}\frac{1}{2\eta_{ik}}(-2(\theta_{k+1,i}-\theta_{k,i})(\theta_{k,i}-\theta_{i}^{*})-(\theta_{k+1,i}-\theta_{k,i})^{2})$
$\displaystyle=\sum_{i=1}^{n}\frac{1}{2\eta_{ik}}(d_{ik}^{2}-d_{i,k+1}^{2}).$

That is

$\frac{2\eta}{g(\theta_{k})}w_{k+1}\leq\sum_{i=1}^{n}\frac{1}{r_{k+1,i}}(d_{ik}^{2}-d_{i,k+1}^{2}).$

This upon summation over iteration steps gives

$\displaystyle\sum_{j=0}^{k-1}\frac{2\eta}{g(\theta_{j})}w_{j+1}$
$\displaystyle\leq\sum_{j=0}^{k-1}\sum_{i=1}^{n}\frac{1}{r_{j+1,i}}(d_{ij}^{2}-d_{i,j+1}^{2})$
$\displaystyle\leq\sum_{i=1}^{n}\left[\frac{d^{2}_{i0}}{r_{1,i}}-\frac{d^{2}_{ik}}{r_{k,i}}+\sum_{j=0}^{k-1}\left(\frac{1}{r_{j+1,i}}-\frac{1}{r_{j,i}}\right)d^{2}_{ij}\right]=:RHS.$

Since $f(\theta_{j})$ is decreasing in $j$, so is $g(\theta_{j})$. Hence

$\sum_{j=0}^{k-1}\frac{2\eta}{g(\theta_{j})}w_{j+1}\geq
2k\eta\frac{w_{k}}{g(\theta_{0})}.$

On the other hand, using $r_{j,i}>r_{j+1,i}$, we have

$\displaystyle RHS$
$\displaystyle\leq\sum_{i=1}^{n}\left[\frac{d^{2}_{i0}}{r_{1,i}}-\frac{d^{2}_{ik}}{r_{k,i}}+\max_{j<k}d^{2}_{ij}\sum_{j=0}^{k-1}\left(\frac{1}{r_{j+1,i}}-\frac{1}{r_{j,i}}\right)\right]$
$\displaystyle\leq\sum_{i=1}^{n}\left[\frac{d^{2}_{i0}}{r_{1,i}}-\frac{d^{2}_{ik}}{r_{k,i}}+\max_{j<k}d^{2}_{ij}\left(\frac{1}{r_{k,i}}-\frac{1}{r_{0,i}}\right)\right]$
$\displaystyle\leq 2\sum_{i=1}^{n}\frac{\max_{j<k}d^{2}_{ij}}{r_{k,i}}.$

Hence

$w_{k}\leq\frac{g(\theta_{0})}{k\eta}\sum_{i=1}^{n}\frac{\max_{j<k}|\theta_{j,i}-\theta_{i}^{*}|^{2}}{r_{k,i}}\leq\frac{g(\theta_{0})}{k\eta}\frac{\max_{j<k}\|\theta_{j}-\theta^{*}\|^{2}}{\min_{i}r_{k,i}}.$

(iii) To obtain the rate of $\theta_{k}$ converging to $\theta^{*}$, we
proceed with

$\displaystyle\theta_{k+1,i}-\theta_{i}^{*}$
$\displaystyle=\theta_{k,i}-\theta_{i}^{*}-\eta_{ik}(\partial_{i}f(\theta_{k})-\partial_{i}f(\theta^{*}))$
$\displaystyle=\theta_{k,i}-\theta_{i}^{*}-\eta_{ik}\sum_{l=1}^{n}\left(\int_{0}^{1}\partial_{i}\partial_{l}f(\theta^{*}+s(\theta_{k}-\theta^{*}))ds=:a_{il}^{k}\right)(\theta_{l}^{k}-\theta_{l}^{*})$

That is

$\theta_{k+1}-\theta^{*}=(I-{\rm
diag}(\eta_{k})A_{k})(\theta_{k+1}-\theta^{*}),$

where ${\rm diag}(\eta_{k})={\rm diag}(\eta_{1k},\cdots,\eta_{nk})$ and
$A_{k}=(a_{il}^{k})$. By matrix norm properties, we obtain

$\displaystyle\|\theta_{k}-\theta^{*}\|=\Pi_{j=0}^{k-1}\left(\max_{i}\max_{\lambda\in[\alpha,L]}|1-\eta_{ik}\lambda|\right)\|\theta_{0}-\theta^{*}\|.$

Under the assumption $\eta_{ik}\leq\frac{2}{\alpha+L}$, we have

$\displaystyle\|\theta_{k}-\theta^{*}\|$
$\displaystyle\leq\Pi_{j=0}^{k-1}\max_{i}(1-\eta_{ij}\alpha)\|\theta_{0}-\theta^{*}\|\leq\exp\left(\sum_{j=0}^{k-1}{\rm
log}(1-\min_{i}\eta_{ij}\alpha)\right)\|\theta_{0}-\theta^{*}\|$
$\displaystyle\leq\exp\left(-\alpha\sum_{j=0}^{k-1}\min_{i}\eta_{ij}\right)\|\theta_{0}-\theta^{*}\|\leq
e^{-k\alpha\eta\min_{i}r_{k,i}/g(\theta_{0})}\|\theta_{0}-\theta^{*}\|.$

In the last inequality we used the estimate
$\eta_{ij}=\eta\frac{r_{j+1,i}}{g(\theta_{j})}\geq\eta\frac{r_{k,i}}{g(\theta_{0})}$
for $j<k.$

###  A.4 Proof of Theorem 4.3

From
$v_{j,i}=\partial_{i}f_{\xi}(\theta_{j})/(2\sqrt{f_{\xi}(\theta_{j})+c}),$ it
follows $(v_{j,i})^{2}\leq\frac{G_{\infty}^{2}}{4a}.$ Using (21a, b), we
obtain

(30) $r_{j,i}-r_{j+1,i}=-v_{j,i}(\theta_{j+1,i}-\theta_{j,i})=2\eta
r_{j+1,i}(v_{j,i})^{2}=2\eta
r_{j,i}\frac{(v_{j,i})^{2}}{1+2\eta(v_{j,i})^{2}},$

where we used $r_{j+1,i}=\frac{r_{j,i}}{1+2\eta(v_{j,i})^{2}}.$ Taking
expectation conditioned on $(\theta_{j},r_{j})$ in (30), we have

(31) $r_{j,i}-\mathbb{E}[r_{j+1,i}]=2\eta
r_{j,i}\mathbb{E}\bigg{[}\frac{(v_{j,i})^{2}}{1+2\eta(v_{j,i})^{2}}\bigg{]}\geq\frac{2\eta
r_{j,i}}{1+2\eta G_{\infty}^{2}/(4a)}\mathbb{E}[(v_{j,i})^{2}].$

Rearranging and taking expectations to get

$\mathbb{E}[r_{j,i}]-\mathbb{E}[r_{j+1,i}]\geq\frac{4a\eta}{2a+\eta
G_{\infty}^{2}}\mathbb{E}[r_{j,i}]\mathbb{E}[(v_{j,i})^{2}].$

Summing over $j$ from $0$ to $k-1$ and using telescopic cancellation gives

$\mathbb{E}[r_{0,i}]-\mathbb{E}[r_{k,i}]\geq\frac{4a\eta}{2a+\eta
G_{\infty}^{2}}\sum_{j=0}^{k-1}\mathbb{E}[r_{j,i}]\mathbb{E}[(v_{j,i})^{2}]\geq\frac{4a\eta}{2a+\eta
G_{\infty}^{2}}\mathbb{E}[r_{k,i}]\sum_{j=0}^{k-1}\mathbb{E}[(v_{j,i})^{2}].$

That is

$k\min_{j<k}\mathbb{E}[(v_{j,i})^{2}]\leq\sum_{j=0}^{k-1}\mathbb{E}[(v_{j,i})^{2}]\leq\frac{C_{i}}{\mathbb{E}[r_{k,i}]},\quad
C_{i}:=\frac{\mathbb{E}[r_{0,i}](2a+\eta G_{\infty}^{2})}{4a\eta}.$

This completes the proof.

##  Appendix B Additional Experimental Results and Implementation Details

Here we provide additional experimental results and implementation details
beyond those in Section 5.

###  B.1 K-means Clustering

By abuse of notation, we can define the ‘gradient’ of $f$ at any point
$\bm{x}$ as

(32) $\nabla
f(\bm{x})=\frac{1}{m}\left[\sum_{i\in\mathcal{C}_{1}}(\bm{x}_{1}-\bm{p}_{i}),...,\sum_{i\in\mathcal{C}_{K}}(\bm{x}_{K}-\bm{p}_{i})\right]^{\top},$

where $\mathcal{C}_{j}$ denotes the index set of the points that are assigned
to the centroid $\bm{x}_{j}$. With the definition of loss function in (26) and
its gradient so defined, we can apply gradient-based methods including AEGD to
solve the $k-$means clustering problem.

###  B.2 Convolutional Neural Networks

The initial set of step sizes used for each algorithm are
SGDM: {0.05, 0.1, 0.2, 0.3},
Adam: {1e-4, 3e-4, 5e-4, 1e-3, 2e-3},
AdamW: {5e-4, 1e-3, 3e-3, 5e-3},
AEGD: {0.1, 0.2, 0.3, 0.4},
AEGDW: {0.6, 0.7, 0.8, 0.9}.

The results presented in Figure 5 show that Adam(W) does not generalize as
well as SGDM and AEGD(W). Therefore, we only compare the generalization
capability of AEGD(W) with SGDM for the remainder of the experiments.

MLP on MNIST. We train a simple multi-layer perceptron (MLP), a special class
of feedforward neural networks, with one hidden layer of $200$ neurons for the
multi-class classification problem on MNIST data set. We run $50$ epochs with
a batch size of $128$ and a weight decay of $10^{-4}$ for this experiment.
Figure 6 (b) shows that AEGDW performs slightly better than SGDM in this case.
This is as expected for simple networks.

CifarNet on CIFAR-10. We also train a simple 3-block convolutional neural
network and name it CifarNet on CIFAR-10. We use the same training set as
before – that is, reduce the learning rates by $10$ after $150$ epochs – with
a minibatch size of $128$ and weight decay of $10^{-4}$. Results for this
experiment are reported in Figure 6 (d). The overall performance of each
algorithm for CifarNet on CIFAR-10 is similar to the experiments in Figure 5.

AEGDW as an improved AEGD can help to reduce the variance and generalize
better early, but such generalization performance does not seem to sustain
after decaying the learning rate as pre-scheduled (see examples in Figure 6
(a) and (c)). Overall, AEGDW or AEGD can give better generalization
performance than SGDM as evidenced by our experiments.

Algorithm 2 AEGD with decoupled weight decay (AEGDW). Good default setting for
parameters are $c=1$ and $\eta=0.7/0.9$ for deep learning problems

1:$\\{f_{j}({\theta})\\}_{j=1}^{m}$, $\eta$: the step size, $\theta_{0}$:
initial guess of $\theta$, and $T$: the total number of iterations.

2:$c$: a parameter such that $f({\theta})+c>0$ for all
$\theta\in\mathbb{R}^{n}$, initial energy, $r_{0}=\sqrt{f(\theta_{0})+c}{\bf
1}$, weight decay factor $\lambda\in\mathbb{R}$

3:for $k=0$ to $k-1$ do

4: $v_{k}:=\nabla
f_{i_{k}}(\theta_{k})/\big{(}2\sqrt{f_{i_{k}}(\theta_{k})+c}\big{)}$ ($i_{k}$
is a random sample from $[m]$ at step $k$)

5: $r_{k+1}=r_{k}/(1+2\eta v_{k}\odot v_{k})$ (update energy)

6: $\theta_{k+1}=\theta_{k}-\eta(2r_{k+1}\odot v_{k}+\lambda\theta_{k})$
(update parameters with weight decay)

7:end for

8:return $\theta_{k}$

(a) AEGD v.s. AEGDW

(b) Test Accuracy for MLP on MNIST

(c) AEGD v.s. AEGDW

(d) Test Accuracy for CifarNet on CIFAR-10

Figure 6: Test accuracy for MLP on MNIST and CifarNet on CIFAR-10

## References

  * [1] P. Absil, R. Mahony, and B. Andrews, Convergence of the iterates of descent methods for analytic cost functions, SIAM J. Optim., 16 (2005), pp. 531–547.
  * [2] H. Attouch, J. Bolte, P. Redont, and A. Soubeyran, Proximal alternating minimization and projection methods for nonconvex problems: An approach based on the Kurdyka-Łojasiewicz inequality, Math. Oper. Res., 35 (2010), pp. 438–457.
  * [3] H. Attouch, J. Bolte, and B. Svaiter, Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward–backward splitting, and regularized Gauss–Seidel methods, Mathematical Programming, 137 (2013), pp. 91–129.
  * [4] H. Attouch, Z. Chbani, J. Fadili, and H. Riahi, First-order optimization algorithms via inertial systems with Hessian driven damping, ArXiv, abs/1907.10536 (2020).
  * [5] J. Bolte, A. Daniilidis, O. Ley, and L. Mazet, Characterizations of łojasiewicz inequalities: Subgradient flows, talweg, convexity, Transactions of The American Mathematical Society - TRANS AMER MATH SOC, 362 (2009), pp. 3319–3363.
  * [6] S. Bos and E. Chug, Using weight decay to optimize the generalization ability of a perceptron, in Proceedings of International Conference on Neural Networks, vol. 1, 1996, pp. 241–246.
  * [7] L. Bottou, Stochastic gradient descent tricks, Neural Networks: Tricks of the Trade, 7700 (2012), pp. 421–436.
  * [8] L. Bottou and Y. Bengio, Convergence properties of the K-means algorithms, in Advances in Neural Information Processing Systems 7, 1995, pp. 585–592.
  * [9] L. Bottou, F. E. Curtis, and J. Nocedal, Optimization methods for large-scale machine learning, SIAM Review, 60(2) (2018), pp. 223–311.
  * [10] C. Castera, J. Bolte, C. Févotte, and E. Pauwels, An inertial Newton algorithm for deep learning, ArXiv, abs/1905.12278 (2021).
  * [11] J. Chen, C. Wolfe, Z. Li, and A. Kyrillidis, Decaying momentum helps neural network training, ArXiv, abs/1910.04952 (2019).
  * [12] A. Defazio, F. Bach, and S. Lacoste-Julien, SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives, in Advances in Neural Information Processing Systems 27, 2014, pp. 1646–1654.
  * [13] T. Dozat, Incorporating Nesterov momentum into Adam, in International Conference on Learning Representation (ICLR), 2016.
  * [14] J. Duchi, E. Hazan, and Y. Singer, Adaptive subgradient methods for online learning and stochastic optimization, Journal of Machine Learning Research, 12(61) (2011), pp. 2121–2159.
  * [15] I. Goodfellow, Y. Bengio, and A. Courville, Deep Learning, MIT Press, 2016.
  * [16] R. M. Gower, N. Loizou, X. Qian, A. Sailanbayev, E. Shulgin, and P. Richtarik., SGD: General analysis and improved rates, ArXiv, abs/1901.09401 (2019).
  * [17] K. He, X. Zhang, S. Ren, and J. Sun, Deep residual learning for image recognition, in IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2016, pp. 770–778.
  * [18] F. Iandola, S. Han, M. Moskewicz, K. Ashraf, W. Dally, and K. Keutzer, SqueezeNet: AlexNet-level accuracy with 50x fewer parameters and $<$ 1MB model size, ArXiv, abs/1602.07360 (2017).
  * [19] C. Jin, P. Netrapalli, and M. I. Jordan, Accelerated gradient descent escapes saddle points faster than gradient descent, in Proceedings of Machine Learning Research, vol. 75, 2018, pp. 1042–1085.
  * [20] R. Johnson and T. Zhang, Accelerating stochastic gradient descent using predictive variance reduction, in Advances in Neural Information Processing Systems 26, 2013, pp. 315–323.
  * [21] H. Karimi, J. Nutini, and M. Schmidt, Linear convergence of gradient and proximal-gradient methods under the Polyak-Łojasiewicz condition, ArXiv, abs/1608.04636 (2020).
  * [22] D. Kingma and J. Ba, Adam: A method for stochastic optimization, in International Conference on Learning Representations (ICLR), 2014.
  * [23] A. Krogh and J. A. Hertz, A simple weight decay can improve generalization, in Advances in Neural Information Processing Systems 4, 1992, pp. 950–957.
  * [24] K. Kurdyka, On gradients of functions definable in o-minimal structures, Annales de l’Institut Fourier, 48 (1998), pp. 769–783.
  * [25] v. d. M. Laurens and G. Hinton, Visualizing data using t-SNE, Journal of machine learning research, 9 (2008), pp. 2579–2605.
  * [26] L. Lei, C. Ju, J. Chen, and M. I. Jordan, Non-convex finite-sum optimization via SCSG methods, in Advances in Neural Information Processing Systems 30, 2017, pp. 2348–2358.
  * [27] H. Liu and P. Yin, Unconditionally energy stable DG schemes for the Swift-Hohenberg equation, Journal of Scientific Computing, 81 (2019), pp. 789–819.
  * [28] H. Liu and P. Yin, Unconditionally energy stable DG schemes for the Cahn-Hilliard equation, ArXiv, abs/1912.10197 (2020).
  * [29] L. Liu, H. Jiang, P. He, W. Chen, X. Liu, J. Gao, and J. Han, On the variance of the adaptive learning rate and beyond, in International Conference on Learning Representations (ICLR), 2020.
  * [30] S. P. Lloyd, Least squares quantization in PCM, IEEE Transactions on Information Theory, 28 (1982), pp. 129–137.
  * [31] S. Łojasiewicz, A topological property of real analytic subsets (in french), Coll. du CNRS, Les equations aux ´ deriv ´ ees partielles, (1963), p. 87–89.
  * [32] S. Łojasiewicz, Sur les trajectoires du gradient d’une fonction analytique (in french), Seminari di Geometria, (1984), p. 115–117.
  * [33] I. Loshchilov and F. Hutter, Decoupled weight decay regularization, in International Conference on Learning Representations (ICLR), 2019.
  * [34] L. Luo, Y. Xiong, Y. Liu, and X. Sun, Adaptive gradient methods with dynamic bound of learning rate, in International Conference on Learning Representations (ICLR), 2019.
  * [35] Y. E. Nesterov, A method for solving the convex programming problem with convergence rate $o(1/k^{2})$, Dokl. Akad. Nauk SSSR, 269 (1983), pp. 543–547.
  * [36] Y. E. Nesterov, Introductory Lectures on Convex Optimization: A Basic Course, Springer, 2014.
  * [37] J. Nocedal and S. J. Wright, Numerical Optimization, Springer, 2006\.
  * [38] B. O’Donoghue and E. Candes, Adaptive restart for accelerated gradient schemes, Foundations of Computational Mathematics, 15 (2015), pp. 715–732.
  * [39] S. Osher, B. Wang, P. Yin, X. Luo, M. Pham, and A. Lin, Laplacian smoothing gradient descent, ArXiv, abs/1806.06317 (2019).
  * [40] B. T. Poljak, Gradient methods for minimizing functionals, Ž. Vyčisl. Mat i Mat. Fiz., 3 (1963), pp. 643–653.
  * [41] B. Polyak, Some methods of speeding up the convergence of iteration methods, USSR Computational Mathematics and Mathematical Physics, 4 (1964), pp. 1–17.
  * [42] B. Polyak and A. Juditsky, Acceleration of stochastic approximation by averaging, SIAM Journal on Control and Optimization, 30 (1992), pp. 838–855.
  * [43] N. Qian, On the momentum term in gradient descent learning algorithms, Neural Networks, 12 (1999), pp. 145–151.
  * [44] S. J. Reddi, S. Kale, and S. Kumar, On the convergence of Adam and beyond, in International Conference on Learning Representations (ICLR), 2018\.
  * [45] H. Robbins and S. Monro, A stochastic approximation method, The Annals of Mathematical Statistics, 22 (1951), pp. 400–407.
  * [46] R. T. Rockafellar, Monotone operators and the proximal point algorithm, SIAM Journal on Control and Optimization, 14 (1976), pp. 877–898.
  * [47] V. Roulet and A. d’Aspremont, Sharpness, restart and acceleration, in Advances in Neural Information Processing Systems 30, 2017, pp. 1119–1129.
  * [48] S. Ruder, An overview of gradient descent optimization algorithms, ArXiv, abs/1609.04747 (2016).
  * [49] O. Shamir and T. Zhang, Stochastic gradient descent for non-smooth optimization: convergence results and optimal averaging schemes, International Conference on Machine Learning (ICML), (2013).
  * [50] A. Shapiro and Y. Wardi, Convergence analysis of gradient descent stochastic algorithms, Journal of Optimization Theory and Applications, 91 (1996), pp. 439–454.
  * [51] J. Shen, J. Xu, and J. Yang, A new class of efficient and robust energy stable schemes for gradient flows, SIAM Review, 61 (2019), pp. 474–506.
  * [52] W. Su, S. Boyd, and E. Candes, A differential equation for modeling Nesterov’s accelerated gradient method: theory and insights, in Advances in Neural Information Processing Systems 27, 2014, pp. 2510–2518.
  * [53] T. Tieleman and G. Hinton, Lecture 6.5-RMSProp: Divide the gradient by a running average of its recent magnitude, COURSERA: Neural networks for machine learning, 4 (2012), pp. 26–31.
  * [54] P. Toulis and E. Airoldi, Asymptotic and finite-sample properties of estimators based on stochastic gradients, The Annals of Statistics, 45 (2017), pp. 1694–1727.
  * [55] B. Wang, T. Nguyen, A. Bertozzi, R. Baraniuk, and S. Osher, Scheduled restart momentum for accelerating SGD, ArXiv, abs/2002.10583 (2020).
  * [56] B. Wang, D. Zhou, Q. Gu, and S. Osher, Laplacian smoothing stochastic gradient Markov Chain Monte Carlo, ArXiv, abs/1911.00782 (2019).
  * [57] A. C. Wilson, R. Roelofs, M. Stern, N. Srebro, and B. Recht, The marginal value of adaptive gradient methods in machine learning, in Advances in Neural Information Processing Systems 30, 2017, pp. 4148–4158.
  * [58] X. Yang, Linear, first and second-order, unconditionally energy stable numerical schemes for the phase field model of homopolymer blends, Journal of Computational Physics, 327 (2016), pp. 294–316.
  * [59] P. Yin, M. Pham, A. Oberman, and S. Osher, Stochastic backward Euler: an implicit gradient descent algorithm for K-means clustering, Journal of Scientific Computing, 77 (2018), pp. 1133–1146.
  * [60] M. Zeiler, Adadelta: an adaptive learning rate method, ArXiv, abs/1212.5701 (2012).
  * [61] G. Zhang, C. Wang, B. Xu, and R. Grosse, Three mechanisms of weight decay regularization, in International Conference on Learning Representations (ICLR), 2019.
  * [62] S. Zhang, A. E. Choromanska, and Y. LeCun, Deep learning with Elastic Averaging SGD, in Advances in Neural Information Processing Systems 28, 2015, pp. 685–693.
  * [63] J. Zhao, Q. Wang, and X. Yang, Numerical approximations for a phase field dendritic crystal growth model based on the invariant energy quadratization approach, International Journal for Numerical Methods in Engineering, 110 (2017), pp. 279–300.
  * [64] Z. Zhu, Katyusha: The first direct acceleration of stochastic gradient methods, The Journal of Machine Learning Research, 18(1) (2018), pp. 1–51.