# A Generalized Version of Chung’s Lemma and its Applications

Li Jiang<EMAIL_ADDRESS>
Xiao Li<EMAIL_ADDRESS>
Andre Milzarek<EMAIL_ADDRESS>
Junwen Qiu<EMAIL_ADDRESS>
School of Data Science
The Chinese University of Hong Kong, Shenzhen (CUHK-Shenzhen)
Guangdong 518172, P.R. China

###### Abstract

Chung’s lemma is a classical tool for establishing asymptotic convergence
rates of (stochastic) optimization methods under strong convexity-type
assumptions and appropriate polynomial diminishing step sizes. In this work,
we develop a generalized version of Chung’s lemma, which provides a simple
non-asymptotic convergence framework for a more general family of step size
rules. We demonstrate broad applicability of the proposed generalized Chung’s
lemma by deriving tight non-asymptotic convergence rates for a large variety
of stochastic methods. In particular, we obtain partially new non-asymptotic
complexity results for stochastic optimization methods, such as Stochastic
Gradient Descent (${\sf SGD}$) and Random Reshuffling (${\sf RR}$), under a
general $(\theta,\mu)$-Polyak-Łojasiewicz (PL) condition and for various step
sizes strategies, including polynomial, constant, exponential, and cosine step
sizes rules. Notably, as a by-product of our analysis, we observe that
exponential step sizes can adapt to the objective function’s geometry,
achieving the optimal convergence rate without requiring exact knowledge of
the underlying landscape. Our results demonstrate that the developed variant
of Chung’s lemma offers a versatile, systematic, and streamlined approach to
establish non-asymptotic convergence rates under general step size rules.

Keywords: Chung’s lemma, non-asymptotic convergence rates, stochastic methods,
exponential and cosine step sizes, $(\theta,\mu)$-Polyak-Łojasiewicz condition

##  1 Introduction

Chung’s lemma (Chung (1954)) is widely utilized to derive asymptotic
convergence rates of stochastic optimization methods; see, e.g., Bottou et al.
(2018); Gürbüzbalaban et al. (2019); Nguyen et al. (2021); Gürbüzbalaban et
al. (2021); Li et al. (2023). In the pioneering paper (Chung (1954)), Chung
analyzed the stochastic gradient method (${\sf SGD}$, Robbins and Monro
(1951)) using the polynomial step size rule $\alpha_{k}\sim 1/k^{p}$. Let
$\\{\bm{x}^{k}\\}_{k}$ and $\bm{x}^{*}$ denote the sequence of iterates
generated by ${\sf SGD}$ and the corresponding optimal solution, respectively.
The recursion for $a_{k}:=\mathbb{E}[\|\bm{x}^{k}-\bm{x}^{*}\|^{2}]$ analyzed
in Chung (1954) is then given by

$a_{k+1}\leqslant\left(1-\frac{c}{k^{p}}\right)a_{k}+\frac{d}{k^{p+q}},\quad\text{where}\quad
p\in(0,1],\quad c,d,q>0.$ (1)

A crucial task in the convergence analysis is to study how fast
$\\{a_{k}\\}_{k}$ converges to 0. Chung provided a useful tool as follows (see
Lemma 23 for a full version).

Chung’s Lemma (Informal) Let $\\{a_{k}\\}_{k}\subseteq\mathbb{R}_{++}$ be
given as in (1). If $0<p<1$ or $p=1$, $c>q$, then $a_{k}=\mathcal{O}(k^{-q})$.

The classical version of Chung’s lemma only applies to polynomial step sizes.
In order to go beyond such a specific step size rule and to encompass a
broader class of strategies (e.g., exponential and cosine step size rules), we
consider the following general recursion:

$a_{k+1}\leqslant\left(1-\frac{1}{s(b_{k})}\right)a_{k}+\frac{1}{t(b_{k})},$
(2)

where $\\{b_{k}\\}_{k}\subseteq\mathbb{R}_{++}$ is given and
$s,t:\mathbb{R}_{++}\to\mathbb{R}_{++}$ are continuously differentiable
functions. Clearly, $s(b_{k})$ and $t(b_{k})$ generalize the terms $k^{p}/c$
and $k^{p+q}/d$ in (1). Existing strategies for solving recursions of the form
(2) mainly rely on explicit expansions:

$a_{K+1}\leqslant
a_{0}\prod_{k=0}^{K}\left(1-\frac{1}{s(b_{k})}\right)+\sum_{k=0}^{K}\left[{\prod}_{i=k+1}^{K}\left(1-\frac{1}{s(b_{i})}\right)\right]\frac{1}{t(b_{k})},$
(3)

where $\prod_{i=K+1}^{K}(1-\frac{1}{s(b_{i})}):=1$. While this methodology can
seemingly deal with any choice of $s$ and $t$, it requires to derive tight
bounds of the different appearing product and sum terms, which can be highly
nontrivial and case-dependent; see, e.g., Li et al. (2021). Based on these
observations, our work is motivated by the following core question:

Can we provide a _simple, non-asymptotic_ upper bound for the sequence
$\\{a_{k}\\}_{k}$ defined in (2) (as in the classic Chung’s lemma) for more
_general step size rules_ , i.e., for general $s(b_{k}),t(b_{k})$?

###  1.1 Contributions

In this work, we address the latter core question affirmatively by imposing an
additional (mild) structure on $s$ and $t$. We now list our main
contributions:
Generalized Chung’s Lemma. We derive a novel generalized variant of Chung’s
Lemma to characterize the growth behavior of $\\{a_{k}\\}_{k}$. An informal
version is shown below:

Generalized Chung’s Lemma (Informal Theorem 1) Suppose that
$\\{a_{k}\\}_{k}\subseteq\mathbb{R}_{++}$ follows the recursion (2) with
$r:=s/t$ being convex on some interval $I$ and $\\{b_{k}\\}_{k}\subseteq I$.
Then, under certain conditions, we have for all $k\geq 0$
$a_{k+1}\leavevmode\nobreak\ \leqslant\leavevmode\nobreak\
\underbracket{C_{1}\cdot
r(b_{k+1})\vphantom{\left[1-\frac{1}{s(b_{i})}\right]}}_{\text{$\mathcal{T}$-induced
rate}}\leavevmode\nobreak\ +\leavevmode\nobreak\
\underbracket{C_{2}a_{0}\cdot{\prod}_{i=0}^{k}\left[1-\frac{1}{s(b_{i})}\right]}_{\text{$\mathcal{S}$-induced
rate}},\quad\text{for some }\;C_{1},C_{2}>0.$ (4)

As indicated in the informal theorem, our generalized variant of Chung’s lemma
naturally decomposes the rate bound into two components, a $\mathcal{T}$\- and
an $\mathcal{S}$-induced rate. The $\mathcal{T}$-induced (often “slower”) rate
is linked with the “error term” ${1}/{t(b_{k})}$ which, in turn, is typically
associated with stochastic gradient errors or other types of errors. The
$\mathcal{S}$-induced (often “faster”) part represents the convergence rate
derived from recursion (2) without the error term ${1}/{t(b_{k})}$ and is
solely connected to the mapping $s$. In Corollary 6, we present evidence
demonstrating that the $\mathcal{S}$-induced term usually converges at a
faster rate compared to the $\mathcal{T}$-induced part. Thus, the convergence
rate of $\\{a_{k}\\}_{k}$ in (2) is
$\mathcal{O}(s(b_{k})/t(b_{k}))=\mathcal{O}(r(b_{k}))$, which generalizes
Chung’s classical result $\mathcal{O}(k^{p}/k^{p+q})=\mathcal{O}(k^{-q})$ for
recursion (1). Overall, our generalized Chung’s lemma provides a simple tool
to obtain _non-asymptotic convergence rates_ based on the recursion (2). As a
direct application, we utilize Theorem 1 to derive a non-asymptotic extension
of the classical asymptotic Chung’s Lemma (cf. Theorem 24).
$(\theta,\mu)$-PL Condition, Exponential and Cosine Step Sizes. Building on
the generalized Chung’s lemma, we provide non-asymptotic analyses for ${\sf
SGD}$ and the random reshuffling method (${\sf RR}$, Algorithm 2) with
exponential and cosine step size rules under a general $(\theta,\mu)$-PL
condition; see Theorems 13, 14, 15 and 16. Note that the existing analyses for
these step size rules primarily focus on ${\sf SGD}$ with
$\theta=\frac{1}{2}$. We recover existing complexity bounds and improve the
convergence rates for cosine step sizes. Moreover, we establish new results
for general PL-exponents $\theta\in(\frac{1}{2},1]$. A detailed comparison of
our findings to the existing ones is displayed in Section 1.1. From a
technical standpoint, there are two main challenges. The first challenge is
that under the general $(\theta,\mu)$-PL condition, we need to analyze a more
intricate recursion,

$y_{k+1}\leqslant(1+\ell_{1}\alpha_{k}^{\tau})y_{k}-\ell_{2}\alpha_{k}y_{k}^{2\theta}+\ell_{3}\alpha_{k}^{\tau},$
(5)

which renders the non-asymptotic Chung’s Lemma inapplicable when
$\theta\in(\frac{1}{2},1]$. We tackle this issue by constructing auxiliary
sequences, for which our generalized Chung’s lemma offers important
instructional guidance, to simplify (5) to a recursion of the form (2). We
refer to Section 3.2 for more details. The analysis of exponential and cosine
step size rules presents additional challenges, i.e., the required assumptions
for applying the generalized Chung’s lemma only hold for part of the iterates,
but not all of them. We introduce a novel splitting technique by combining the
generalized Chung’s lemma with an extension lemma (see Lemma 5) to resolve
this problem. See Section 3.3 for more details.
Polynomial and Constant Step Size Rules. For completeness, we also provide
non-asymptotic analyses for ${\sf SGD}$ and ${\sf RR}$ with polynomial and
constant step size rules under the $(\theta,\mu)$-PL condition based on our
generalized Chung’s lemma; see Theorems 20, 21, 17 and 18. Our findings not
only corroborate the established results in the literature but also introduce
several new ones, particularly for scenarios where $\theta\in(\frac{1}{2},1]$.
A comparison between our results and the existing body of work is provided in
Section 1.1.

In summary, our generalized Chung’s lemma serves as a versatile tool,
providing a systematic way to establish convergence rates and complexity
bounds for various optimization methods with different step sizes rules.

cell-space-limits=1pt —p1.2cmp1.5cm—p2.3cmp2.7cm—p2.45cmp2.85cm—[ code-before
= lavender!403-110-1 lavender!403-310-3 lavender!403-510-5 ] [c]1-2Algorithms
[c]1-2${\sf SGD}$ [c]1-2${\sf RR}$
1-1$\theta$ 1-1step size 1-1existing 1-1ours 1-1existing 1-1ours
4-1$\frac{1}{2}$ 1-1Exp 1-1$\mathcal{O}(\frac{\log(K)}{K})$
${}^{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\text{(a)}}}$
1-1$\mathcal{O}(\frac{\log(K)}{K})$ 1-1$-$
1-1$\mathcal{O}(\frac{\log^{2}(K)}{NK^{2}})$
1-1Cos
${}^{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\text{(b)}}}$
1-1$\mathcal{O}(\frac{1}{K^{2/3}})$
${}^{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\text{(c)}}}$
1-1$\mathcal{O}(\frac{\log^{1/(2\beta+1)}(K)}{K})$ 1-1$-$
1-1$\mathcal{O}(\frac{\log^{2/(2\beta+1)}(NK)}{NK^{2}})$
1-1Const 1-1$\mathcal{O}(\frac{\log(K)}{K})$
${}^{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\text{(d)}}}$
1-1$\mathcal{O}(\frac{\log(K)}{K})$
1-1$\mathcal{O}(\frac{\log^{2}(NK)}{NK^{2}})$
${}^{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\text{(e)}}}$
1-1$\mathcal{O}(\frac{\log^{2}(NK)}{NK^{2}})$
1-1Poly 1-1$\mathcal{O}({K^{-1}})$
${}^{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\text{(f)}}}$
1-1$\mathcal{O}({K^{-1}})$ 1-1$\mathcal{O}(\frac{\log(K)}{NK^{2}})$
${}^{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\text{(g)}}}$
1-1$\mathcal{O}(\frac{\log^{2}(N)}{NK^{2}})$
4-1$(\frac{1}{2},1]$
${}^{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\text{(h)}}}$
1-1Exp 1-1$-$ 1-1$\mathcal{O}([{\frac{\log(K/\beta)}{K}}]^{\omega_{1}})$ 4-1✗
1-1$\mathcal{O}([{\frac{\log(K/\beta)}{\sqrt{N}K}}]^{\omega_{2}})$
1-1Cos 1-1$-$ 1-1$\mathcal{O}([{\frac{\log^{v_{1}}(K)}{K}}]^{\omega_{1}})$
1-1$\mathcal{O}([{\frac{\log^{v_{2}}(NK)}{\sqrt{N}K}}]^{\omega_{2}})$
1-1Const 1-1$-$ 1-1$\mathcal{O}([{\frac{\log(K)}{K}}]^{\omega_{1}})$
1-1$\mathcal{O}([{\frac{\log(NK)}{\sqrt{N}K}}]^{\omega_{2}})$
1-1Poly 1-1$\mathcal{O}({K}^{-\omega_{1}})$
${}^{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\text{(i)}}}$
1-1$\mathcal{O}({K}^{-\omega_{1}})$
1-1$\mathcal{O}([{\frac{\log(N)}{\sqrt{N}K}}]^{\omega_{2}})$

Table 1: Comparison of our results with existing literature. (a) See (Wang et
al., 2021, Theorem 4.1). The result in Wang et al. (2021) is achieved under
stricter assumptions compared to ours, necessitating $f$ to be strongly convex
and ${\sf L}$-smooth, along with a bounded stochastic gradient condition.
(b) We use cosine step sizes of the form
$\alpha_{k}=\alpha[\frac{1+\cos(\frac{k\pi}{K})}{2}]^{\beta}$, $\beta>0$;
Existing literature only covers the case when $\beta=1$.
(c) See (Li et al., 2021, Theorem 2). We improve this rate by suggesting a
particular method for selecting $\alpha$ in cosine step sizes, i.e., setting
$\alpha\sim\frac{\log(K)}{K}$.
(d) See Shamir and Zhang (2013); Needell et al. (2014); Bottou et al. (2018);
Gower et al. (2019).
(e) See (Nguyen et al., 2021, Theorem 1).
(f) See (Gower et al., 2021, Theorem 4.8).
(g) See (Nguyen et al., 2021, Theorem 7). Here, a direct comparison of our
result is not possible due to some minor mistakes in the proof of (Nguyen et
al., 2021, Theorem 7), which cannot be easily remedied. In Nguyen et al.’s
proof of Theorem 7, the step size $\eta_{t}=\frac{2}{t+\beta}$ is selected,
where $\beta=1+\frac{1}{N}$. The choice of $\beta$ is critical as $\beta-1$ is
required to yield the factor $1/N$ in the convergence rate. However, we
identified a missing parameter, $\rho$, in the selection of $\eta_{t}$.
According to (Nguyen et al., 2021, Lemma 1), $\eta_{t}$ should satisfy
$\frac{q}{\rho(t+\beta)}$, where $q=2$ and $\rho=\frac{1}{4\tau}$, i.e.,
$\rho=\frac{\mu}{2}$ in our notation. Hence, it holds that
$\eta_{t}={4}({\mu(t+1+\frac{1}{N})})^{-1}$. Meanwhile, the proof of (Nguyen
et al., 2021, Theorem 7) requires $\eta_{t}$ to satisfy $\eta_{t}\leq({{\sf
L}\sqrt{2(\Theta/N+1)}})^{-1}$ for all $t\geqslant 1$. However, this leads to
a contradiction requiring the condition number to satisfy $\frac{{\sf
L}}{\mu}\leq\frac{1}{4\sqrt{2}}{(2+\frac{1}{N})}<1$. It is important to note
that the rescaling argument in Nguyen et al. (2021) is not applicable in this
context because the condition number is invariant under rescaling. One
straightforward solution is to increase $\beta$; however, this adjustment
would eliminate the factor $\frac{1}{N}$ in the convergence rate in their
proof.
(h) Here, we use the notation $\omega_{1}=\frac{1}{4\theta-1}$,
$\omega_{2}=\frac{1}{3\theta-1}$, $\varrho_{1}=\frac{2\theta}{4\theta-1}$,
$\varrho_{2}=\frac{\theta}{3\theta-1}$,
$v_{1}=\frac{\varrho_{1}}{2\beta+\varrho_{1}}$ and
$v_{2}=\frac{\varrho_{2}}{2\beta+\varrho_{2}}$.
(i) See (Fontaine et al., 2021, Theorem 12); (Fatkhullin et al., 2022,
Corollary 1).

###  1.2 Related Works

Recursions of the form (2) are abundant in stochastic optimization; see, e.g.,
Mishchenko et al. ; Nguyen et al. (2021); Bottou et al. (2018); Shamir (2016);
Gürbüzbalaban et al. (2019, 2021); Ahn et al. (2020); Huang et al. (2021). As
mentioned, the functions $s,t$ in (2) are often related to the step size
dynamics. Our overview focuses on Chung’s lemma and its extensions, different
step size rules, and convergence analyses based on PL-type conditions.
$\blacktriangleright$ Chung’s Lemma and Extensions. Chung’s lemma (Chung
(1954)) is a fundamental tool extensively used in the literature to analyze
the convergence rate of stochastic approximation and optimization algorithms,
(Chung (1954); Derman (1956); Sacks (1958); Fabian (1968); Nemirovski et al.
(2009); Moulines and Bach (2011); Gürbüzbalaban et al. (2019); Karimi et al.
(2016); Bottou et al. (2018); Gürbüzbalaban et al. (2021); Ahn et al. (2020);
Nguyen et al. (2021); Fatkhullin et al. (2022)). Non-asymptotic extensions of
Chung’s lemma are established in (Moulines and Bach (2011); Ahn et al. (2020);
Nguyen et al. (2021)), which are tailored to polynomial step size rules. In
addition, some studies have considered the recursion (2) with specific non-
polynomial forms of $s(b_{k})$ and $t(b_{k})$, see (Li et al. (2021); Wang et
al. (2021)). To the best of our knowledge, the literature appears to lack non-
asymptotic variants of Chung’s lemma that accommodate fully general terms
$s(b_{k})$ and $t(b_{k})$.
$\blacktriangleright$ Exponential and Cosine Step Sizes. Exponential step
sizes (Li et al. (2021)), also known as geometrically decaying step sizes
(Goffin (1977); Ge et al. (2019)), were utilized by Goffin (1977) for
subgradient methods. This step size strategy is also widely used in machine
learning, and is currently one of the learning rate decay schedules in
Tensorflow (Abadi et al. (2015)) and PyTorch (Paszke et al. (2019)). The
theoretical analysis of exponential step size is limited. In Ge et al. (2019),
the authors provide derivations for least-squares regression problems.
Theoretical and broader guarantees for a more general class of functions are
shown in Li et al. (2021); Wang et al. (2021). Cosine step sizes, initially
proposed by Loshchilov and Hutter (2016), are used as a popular warm restart
scheme in performing stochastic algorithms. Recently, cosine step sizes have
been widely employed in the optimization and training of large language
models. For instance, the Llama-2 model family (Touvron et al. (2023)) is pre-
trained using an AdamW optimizer with a cosine step size rule. Its fine-tuning
procedure uses the same step size scheme. Therefore, understanding the
convergence properties of representative stochastic optimization methods with
this step size rule is crucial. Yet, the convergence behavior of stochastic
methods under cosine step sizes has not been well understood. The first
complexity bounds for ${\sf SGD}$ with cosine step sizes are presented in (Li
et al., 2021, Theorem 2). In the general nonconvex setting, extensions to an
${\sf RR}$-type method (with momentum) are considered in (Tran et al., 2021,
Corollary 4).
$\blacktriangleright$ Stochastic Optimization under PL-type Conditions. The
Polyak-Łojasiewicz (PL) condition (Polyak (1963); Łojasiewicz (1959, 1963))
provides a measure of the “strong convexity-like” behavior of a function
without requiring it to be convex. The recent convergence frameworks discussed
in Fontaine et al. (2021); Fatkhullin et al. (2022) rely on certain
generalizations of the PL condition. In this paper, we consider a
$(\theta,\mu)$-PL condition (Definition 9), which encompasses the well-known
Polyak-Łojasiewicz condition when $\theta=\frac{1}{2}$. The additional PL
exponent, $\theta\in[\frac{1}{2},1]$, enables the PL condition to hold for a
wider range of functions, particularly those relevant to contemporary machine
learning applications (see (Fatkhullin et al., 2022, Appendix A) for pertinent
examples). Specifically, in the field of reinforcement learning, the objective
function may satisfy the $(1,\mu)$-PL condition for a certain $\mu>0$, (Wang
and Zou (2022); Agarwal et al. (2021); Mei et al. (2020)). These evidences
indicate that analyzing the cases beyond the standard setting
$\theta=\frac{1}{2}$ holds significance in real applications.

##  2 Generalized Chung’s Lemma

Throughout this work, we concentrate on the non-asymptotic behavior of
sequence $\\{a_{k}\\}_{k}$ satisfying

$a_{k+1}\leqslant\left(1-\frac{1}{s(b_{k})}\right)a_{k}+\frac{1}{t(b_{k})},\quad\forall\leavevmode\nobreak\
k\in[K]:=\\{0,1,\dots,K\\}.$ (6)

The following generalized Chung’s lemma provides a non-asymptotic upper bound
for $\\{a_{k}\\}_{k}$.

######  Theorem 1 (Generalized Chung’s Lemma)

Let
$\\{a_{k}\\}_{k}\subseteq\mathbb{R}_{++},\,\\{b_{k}\\}_{k}\subseteq\mathbb{R}$
and the continuous differentiable functions
$s,t:\mathbb{R}\rightarrow\mathbb{R}_{++}$ be given. Assume that
$\\{a_{k}\\}_{k}$ follows (6) and there is an interval $I$ such that $b_{k}\in
I$ for all $k\in[K]$, $s(x)\geqslant 1$ for all $x\in I$, and $r:=s/t$ is
convex on $I$. Define $u:=s^{\prime}-t^{\prime}r$; if either of the following
statements holds:

  1. (a)

There exists a sequence $\\{\lambda_{k}\\}_{k}\subseteq\mathbb{R}_{+}$ such
that for all $k\in[K-1]$,

$\lambda_{k+1}(s(b_{k})+(b_{k+1}-b_{k})u(b_{k}))\geqslant\lambda_{k}(s(b_{k})-1)+1,$
(7)

  2. (b)

There exists a non-decreasing sequence
$\\{\lambda_{k}\\}_{k}\subseteq\mathbb{R}_{++}$ such that for all $k\in[K-1]$,

$(b_{k+1}-b_{k})u(b_{k})\geq-1+\frac{1}{\lambda_{k+1}},$ (8)

then we have

$a_{k+1}\leqslant\lambda_{k+1}r(b_{k+1})+\left(a_{0}-\lambda_{0}r(b_{0})\right)\prod_{i=0}^{k}\left(1-\frac{1}{s(b_{i})}\right),\quad\forall\leavevmode\nobreak\
k\in[K-1].$ (9)

Proof  Let us set $\beta_{k}:=b_{k+1}-b_{k}$. By the convexity of the mapping
$r$, we have

$r(b_{k+1})\geqslant
r(b_{k})+r^{\prime}(b_{k})\beta_{k}=r(b_{k})+\beta_{k}\frac{s^{\prime}(b_{k})t(b_{k})-s(b_{k})t^{\prime}(b_{k})}{t(b_{k})^{2}}=\frac{\beta_{k}u(b_{k})+s(b_{k})}{t(b_{k})}.$
(10)

If statement (a) holds, substituting the latter estimate into (7), this yields

$\displaystyle\lambda_{k+1}r(b_{k+1})$
$\displaystyle\geqslant\frac{1}{t(b_{k})}\cdot\lambda_{k+1}\left(\beta_{k}u(b_{k})+s(b_{k})\right)\geqslant\lambda_{k}\left(\frac{s(b_{k})}{t(b_{k})}-\frac{1}{t(b_{k})}\right)+\frac{1}{t(b_{k})}$
$\displaystyle=\lambda_{k}\left(r(b_{k})-\frac{r(b_{k})}{s(b_{k})}\right)+\frac{1}{t(b_{k})}=\lambda_{k}r(b_{k})\left(1-\frac{1}{s(b_{k})}\right)+\frac{1}{t(b_{k})}.$

Hence, invoking the recursion (6), we obtain
$a_{k+1}-\lambda_{k+1}r(b_{k+1})\leqslant(1-\frac{1}{s(b_{k})})(a_{k}-\lambda_{k}r(b_{k}))$.
This verifies (9).

When statement (b) is valid, we notice that the condition (8) readily implies
(7), then (9) follows.

We now provide a simple example to briefly illustrate the application of
Theorem 1.

###### Example 1

Let us consider the recursion $a_{k+1}\leqslant(1-\alpha)a_{k}+\beta$, where
$\alpha\in(0,1)$, $\beta>0$. Setting $I=\mathbb{R}$,
$s\equiv\frac{1}{\alpha}$, $t\equiv\frac{1}{\beta}$, $b_{k}=k$, $\lambda=1$,
the rate mapping $r\equiv\frac{\beta}{\alpha}$ is convex and we have
$(b_{k+1}-b_{k})u(b_{k})=0=-1+\frac{1}{\lambda}$ for all $k$. Consequently,
Theorem 1 is applicable, then
$a_{k}\leqslant\frac{\beta}{\alpha}+(1-\alpha)^{k}(a_{0}-\frac{\beta}{\alpha})$
holds for all $k$.

###### Remark 2

The most significant and useful setting for Theorem 1 arises when the sequence
$\\{\lambda_{k}\\}_{k}$ in condition (b) can be chosen to be constant. A
majority of our subsequent analysis will be built based on this particular
scenario.

###### Remark 3

The convexity requirement on $r:=s/t$ in Theorem 1 is not strict since there
is flexibility in choosing $\\{b_{k}\\}_{k}$. Consider the example
$r(b_{k})=1+\cos(\frac{k\pi}{K})$, $k\in[K]$. A direct choice $b_{k}:=k$,
$r(x):=1+\cos(\frac{x\pi}{K})$, and $I=[0,K]$ does not meet the convexity
condition. However, we can ensure the convexity of $r$ by instead selecting
$b_{k}:=1+\cos(\frac{x\pi}{K})$, $r(x):=x$, and $I=\mathbb{R}$. This strategy
proves valuable in the analysis of cosine step sizes, see Section 3.3.

Non-asymptotic Extension of Chung’s Lemma. As a quick application, we use
Theorem 1 to obtain a non-asymptotic extension of the classical Chung’s lemma.

######  Lemma 4 (Non-asymptotic Chung’s Lemma)

Let $\\{a_{k}\\}_{k}\subseteq\mathbb{R}_{++}$ be given satisfying

$a_{k+1}\leqslant\left(1-\frac{c}{(k+\gamma)^{p}}\right)a_{k}+\frac{d}{(k+\gamma)^{p+q}},\quad
p\in(0,1],\leavevmode\nobreak\ q>0,\leavevmode\nobreak\
c,d>0,\leavevmode\nobreak\ \gamma\geqslant c^{\frac{1}{p}}.$

Then, the following statements hold:

  1. (a)

If $p\in(0,1)$, $\gamma\geqslant c^{\frac{1}{p}}$ and
$\gamma>(\frac{q}{c})^{\frac{1}{1-p}}$, then

$\displaystyle a_{k+1}\leqslant\frac{\lambda
d}{c}(k+1+\gamma)^{-q}+\left(a_{0}-\frac{\lambda
d}{c\gamma^{q}}\right)^{+}\exp\left(\frac{c\gamma^{1-p}}{1-p}\right)\exp\left[-\frac{c(k+1+\gamma)^{1-p}}{1-p}\right],$

holds for all $k\in[K]$, where $\lambda=\frac{c\gamma^{1-p}}{c\gamma^{1-p}-q}$
and $(x)^{+}:=\max\\{x,0\\}$.

  2. (b)

If $p=1$, $c>q$, and $\gamma\geqslant c$, then

$a_{k+1}\leqslant\frac{d}{c-q}(k+1+\gamma)^{-q}+\gamma^{c}\left(a_{0}-\frac{d}{(c-q)\gamma^{q}}\right)^{+}(k+1+\gamma)^{-c}.$

Here, we only discuss the cases $0<p<1$ and $p=1$, $c>q$, as these are most
relevant to the convergence analysis of stochastic optimization methods. A
full derivation is provided in Appendix B.

Proof  We now apply our main theorem (especially Theorem 1 (b)) to prove the
non-asymptotic version of the classical Chung’s lemma. To make use of Theorem
1 (b), we first specify the following sequences and functions:

$b_{k}:=k+\gamma,\quad s(x):={x^{p}}/{c},\quad\text{and}\quad
t(x):={x^{p+q}}/{d}.$

We only need to check if the conditions in Theorem 1 (b) are fulfilled. Let us
note that the mapping $r(x):=s(x)/t(x)=\frac{d}{c}x^{-q}$ is convex on
$\mathbb{R}_{++}$. In addition, it holds that

$u(x):=s^{\prime}(x)-r(x)t^{\prime}(x)=\frac{p}{c}x^{p-1}-\frac{d}{c}x^{-q}\cdot\frac{p+q}{d}x^{p+q-1}=-\frac{q}{c}x^{p-1}$

and $s(x)\geqslant 1$ for all $x\geqslant c^{{1}/{p}}$. By assumption, we have
$\gamma\geqslant c^{{1}/{p}}$ implying $b_{k}\in
I:=[c^{{1}/{p}},\infty)\subseteq\mathbb{R}_{++}$ for all $k\in[K]$. Now, it
only remains to verify the condition (8). Since $b_{k+1}-b_{k}=1$, we need to
find a non-decreasing sequence $\\{\lambda_{k}\\}_{k}\subseteq\mathbb{R}_{+}$
such that

$-\frac{q}{c}(k+\gamma)^{p-1}\geqslant-1+\frac{1}{\lambda_{k+1}},\quad\forall\;k\in[K].$
(11)

Based on the parameter $p\in(0,1]$, we now discuss different cases.
Case I: $p\in(0,1)$. Let us set
$\lambda_{k}\equiv\lambda=\frac{c\gamma^{1-p}}{c\gamma^{1-p}-q}$. Per
assumption, we further have $\gamma>(\frac{q}{c})^{\frac{1}{1-p}}$ and thus,
we can infer $\lambda>0$ and

$-\frac{q}{c}(k+\gamma)^{p-1}\geqslant-\frac{q}{c}\gamma^{p-1}=-1+\frac{c\gamma^{1-p}-q}{c\gamma^{1-p}}=-1+\frac{1}{\lambda}\quad\forall\leavevmode\nobreak\
k\in[K].$ (12)

Hence, the condition (11) is satisfied for this choice of $\lambda_{k}$ and
$\lambda$. Utilizing Theorem 1 (b), the inequality $1-x\leqslant\exp(-x)$, and
the integral test (Proposition 22), we obtain

$\displaystyle a_{k+1}$ $\displaystyle\leqslant\lambda
r(b_{k+1})+(a_{0}-\lambda
r(\gamma))\cdot{\prod}_{i=0}^{k}\left[1-\frac{1}{s(b_{i})}\right]$
$\displaystyle=\frac{\lambda d}{c}(k+1+\gamma)^{-q}+\left(a_{0}-\frac{\lambda
d}{c\gamma^{q}}\right){\prod}_{i=0}^{k}\left[1-\frac{c}{(i+\gamma)^{p}}\right]$
$\displaystyle\leqslant\frac{\lambda
d}{c}(k+1+\gamma)^{-q}+\left(a_{0}-\frac{\lambda
d}{c\gamma^{q}}\right)^{+}\exp\left(-{\sum}_{i=0}^{k}\frac{c}{(i+\gamma)^{p}}\right)$
$\displaystyle\leqslant\frac{\lambda
d}{c}(k+1+\gamma)^{-q}+\left(a_{0}-\frac{\lambda
d}{c\gamma^{q}}\right)^{+}\exp\left(\frac{c\gamma^{1-p}}{1-p}\right)\exp\left(-\frac{c(k+1+\gamma)^{1-p}}{1-p}\right),$

where the last line is due to
$\sum_{i=0}^{k}\,(i+\gamma)^{-p}\geq\int_{0}^{k+1}(x+\gamma)^{-p}\textup{{d}}x=\frac{1}{1-p}[(k+1+\gamma)^{1-p}-\gamma^{1-p}]$.
Case II: $p=1$, $c>q$, and $\gamma\geqslant c$. Setting
$\lambda_{k}\equiv\lambda=\frac{c}{c-q}$, the condition (11) is obviously
satisfied (cf. (12)). Repeating the core steps in Case I, we obtain

$\displaystyle a_{k+1}\leqslant\leavevmode\nobreak$
$\displaystyle\frac{\lambda d}{c}(k+1+\gamma)^{-q}+\left(a_{0}-\frac{\lambda
d}{c\gamma^{q}}\right){\prod}_{i=0}^{k}\left[1-\frac{c}{i+\gamma}\right]$
$\displaystyle\leqslant\leavevmode\nobreak$
$\displaystyle\frac{d}{c-q}(k+1+\gamma)^{-q}+\gamma^{c}\left(a_{0}-\frac{d}{(c-q)\gamma^{q}}\right)^{+}(k+1+\gamma)^{-c}.$

Notice that the difference in the analysis only stems from the integral test
(Proposition 22):
${\sum}_{i=0}^{k}\,\frac{1}{i+\gamma}\geqslant{\int}_{0}^{k+1}\frac{1}{x+\gamma}\;\textup{{d}}x=\log(k+1+\gamma)-\log(\gamma)$.

Unfortunately, many of the following applications are not as simple as Example
1 or Lemma 4. In general, condition (7) in Theorem 1 (a) is less restrictive
compared to (8). However, determining $\lambda_{k}$ in (7) can be challenging
as it requires the non-trivial construction of a new recursive sequence
$\\{\lambda_{k}\\}_{k}$. It is worth noting that, in most cases, Theorem 1 (b)
is easier to apply. Nevertheless, there may be situations where it is not
possible to construct the sequence $\\{\lambda_{k}\\}_{k}$ in (8) for all
$k\in[K]$, although it is feasible for a subset of $[K]$. This issue becomes
evident when analyzing exponential and cosine step sizes (as discussed in
Section 3.3). To address this potential limitation, we introduce the following
important lemma, which significantly enhances the applicability of Theorem 1
(b).

######  Lemma 5 (Extension Lemma)

Let $\\{a_{k}\\}_{k}\subseteq\mathbb{R}_{++}$,
$\\{b_{k}\\}_{k}\subseteq\mathbb{R}_{+}$ and the $C^{1}$-functions
$s,t:\mathbb{R}\rightarrow\mathbb{R}_{++}$ be given. Suppose that
$\\{a_{k}\\}_{k}$ follows the recursion (6). Assume that $s(b_{k})\geqslant
1$, and $\\{r(b_{k})\\}_{k}$ is non-increasing w.r.t. $k$ for all $k\in[K]$.
If there exist $k_{0},\overline{K}\in[K-1]$, $k_{0}\leqslant\overline{K}$,
$C\in\mathbb{R}$, and $\bar{\lambda}\geqslant 1$ such that

$a_{\overline{K}+1}\leqslant\bar{\lambda}r(b_{\overline{K}+1})+C\prod_{i=k_{0}}^{\overline{K}}\left(1-\frac{1}{s(b_{i})}\right),$
(13)

then, we have
$a_{K}\leqslant\bar{\lambda}r(b_{\overline{K}+1})+C\prod_{i=k_{0}}^{K-1}\left(1-\frac{1}{s(b_{i})}\right)$.

Proof  There is nothing to show in the case $\overline{K}=K-1$. We can verify
the result for $\overline{K}<K-1$ via induction. For any
$k=\overline{K}+1,\dots,K-1$, if
$a_{k}\leqslant\bar{\lambda}r(b_{\overline{K}+1})+C\prod_{i=k_{0}}^{k-1}({1-\frac{1}{s(b_{i})}})$,
and by applying (6), we obtain

$\displaystyle a_{k+1}\leqslant\leavevmode\nobreak\ $
$\displaystyle\left[\frac{1}{t(b_{k})}+\left(1-\frac{1}{s(b_{k})}\right)\bar{\lambda}r(b_{\overline{K}+1})\right]+C\prod_{i=k_{0}}^{k}\left(1-\frac{1}{s(b_{i})}\right)$
$\displaystyle=\leavevmode\nobreak\ $
$\displaystyle\left[\frac{1}{s(b_{k})}r(b_{k})+\left(1-\frac{1}{s(b_{k})}\right)\bar{\lambda}r(b_{\overline{K}+1})\right]+C\prod_{i=k_{0}}^{k}\left(1-\frac{1}{s(b_{i})}\right)$
$\displaystyle\leqslant\leavevmode\nobreak\ $
$\displaystyle\bar{\lambda}r(b_{\overline{K}+1})+C\prod_{i=k_{0}}^{k}\left(1-\frac{1}{s(b_{i})}\right),$

where we used $\bar{\lambda}\geqslant 1$ and $r(b_{k})\leqslant
r(b_{\overline{K}+1})$ for any $k\geqslant\overline{K}+1$ in the last step.
Hence, by induction, it follows
$a_{K}\leqslant\bar{\lambda}r(b_{\overline{K}+1})+C\prod_{i=k_{0}}^{K-1}({1-\frac{1}{s(b_{i})}})$.

The combination of Theorem 1 and Lemma 5 is crucial in the subsequent
applications. The key idea is to partition the index set $[K]$ into two
subsets. Initially, we determine the largest value of $\overline{K}$ that
satisfies condition (8) for all $k\in[\overline{K}]$. By applying Theorem 1
(b), we can establish an upper bound for $a_{\overline{K}+1}$ resembling (13).
Lemma 5 then enables us to extend this estimate from $a_{\overline{K}+1}$ to
the final iterate $a_{K}$. This technique will be important when analyzing
exponential and cosine step size rules (cf. Section 3.3).
Forgetting Initial Conditions. The following corollary offers insight into the
relationship between the $\mathcal{S}$\- and $\mathcal{T}$-induced components
in (4).

###### Corollary 6

Suppose that the assumptions in Theorem 1 (b) hold with
$\lambda_{k}\equiv\lambda\geqslant 1$. Then, we have

$a_{k+1}\leqslant\lambda
r(b_{k+1})+\max\left\\{\frac{a_{0}}{r(b_{0})}-\lambda,0\right\\}\prod_{i=0}^{k}\left(1-\frac{1/\lambda}{s(b_{i})-1+1/\lambda}\right)r(b_{k+1}),\quad\forall\;k\in[K].$

Proof  From Theorem 1 (b), we have for all $k\in[K]$,

$\displaystyle a_{k+1}\leqslant\leavevmode\nobreak\ $ $\displaystyle\lambda
r(b_{k+1})+\max\left\\{\frac{a_{0}}{r(b_{0})}-\lambda,0\right\\}\prod_{i=0}^{k}\left(1-\frac{1}{s(b_{i})}\right)r(b_{0})$
$\displaystyle=\leavevmode\nobreak\ $ $\displaystyle\lambda
r(b_{k+1})+\max\left\\{\frac{a_{0}}{r(b_{0})}-\lambda,0\right\\}\prod_{i=0}^{k}\left[\left(1-\frac{1}{s(b_{i})}\right)\frac{r(b_{i})}{r(b_{i+1})}\right]r(b_{k+1}).$

Combining equation (10) and the condition (8), we obtain

$r(b_{i+1})\geqslant\frac{(b_{i+1}-b_{i})u(b_{i})+s(b_{i})}{t(b_{i})}\geqslant\frac{s(b_{i})-1+{1}/{\lambda}}{t(b_{i})}>0.$

Thus, we can establish the upper bound

$\left(1-\frac{1}{s(b_{i})}\right)\frac{r(b_{i})}{r(b_{i+1})}\leqslant\left(1-\frac{1}{s(b_{i})}\right)\frac{s(b_{i})}{s(b_{i})-1+{1}/{\lambda}}=1-\frac{1/\lambda}{s(b_{i})-1+{1}/{\lambda}}.$

Substituting this bound into the first estimate finishes the proof.

Corollary 6 shows that if the assumptions in Theorem 1 (b) are satisfied, then
the $\mathcal{S}$-induced rate will generally be faster than the
$\mathcal{T}$-induced rate, which can be quantified by the term
$\prod_{i=0}^{k}(1-\frac{1/\lambda}{s(b_{i})-1+1/\lambda})$. This phenomenon
is known as the “forgetting initial conditions” in the literature; but it is
usually discussed for specific step size rules. For instance, in (Moulines and
Bach (2011)), this phenomenon is studied for polynomial step sizes. Corollary
6 reveals that this property holds in a more general context.

##  3 Convergence Rates of Stochastic Methods under ($\theta$,$\mu$)-PL
Condition

In this section, we establish non-asymptotic rates for stochastic methods
under various step size strategies through the application of the generalized
Chung’s lemma—Theorem 1. We consider the optimization problem

$\min_{x\in\mathbb{R}^{n}}\;f(x),$ (14)

where $f:\mathbb{R}^{n}\to\mathbb{R}$ is a continuously differentiable
mapping.

###  3.1 Basic Assumptions and Descent Properties

Below, in Algorithms 1 and 2, we present the main algorithmic steps of ${\sf
SGD}$ and the random reshuffling (${\sf RR}$) method to solve the problem
(14). We note that, in ${\sf RR}$, the objective function $f$ is assumed to
have the following finite-sum structure
$f(x):=\frac{1}{N}\sum_{i=1}^{N}f_{i}(x)$.

Algorithm 1 Stochastic Gradient Descent (${\sf SGD}$)

1:Choose an initial point $x^{0}\in\mathbb{R}^{n}$ and step sizes
$\\{\alpha_{k}\\}_{k}\subset\mathbb{R}_{++}$;

2:while stopping criterion is not met do

3: Generate a new stochastic gradient $g^{k}\approx\nabla f(x^{k})$;

4: Perform the update $x^{k+1}=x^{k}-\alpha_{k}g^{k}$;

5:end while

Algorithm 2 Random Reshuffling (${\sf RR}$)

1:Choose an initial point $x^{0}\in\mathbb{R}^{n}$ and step sizes
$\\{\alpha_{k}\\}_{k}\subset\mathbb{R}_{++}$;

2:while stopping criterion not met do

3: Generate a uniformly random permutation $\pi^{k}$ of $\\{1,\ldots,N\\}$ and
set $\tilde{x}_{0}^{k}=x^{k}$;

4: for $i=1,2,\ldots,N$ do

5: Update the inner iterate via
$\tilde{x}_{i}^{k}=\tilde{x}_{i-1}^{k}-\frac{\alpha_{k}}{N}\,\nabla{f}_{\pi^{k}_{i}}(\tilde{x}_{i-1}^{k});$

6: end for

7: Perform the update $x^{k+1}=\tilde{x}_{N}^{k}$;

8:end while

Our analysis will be based on a filtered probability space
$(\Omega,\mathcal{F},\\{\mathcal{F}_{k}\\}_{k},\mathbb{P})$ to which the
stochastic processes $\\{\bm{x}^{k}\\}_{k}$ generated by these two algorithms
are adapted. We make the following standard assumptions for ${\sf SGD}$ and
${\sf RR}$, respectively.

######  Assumption 7 (Conditions for ${\sf SGD}$)

We consider the assumptions:

  1. (A.1)

The objective $f$ is ${\sf L}$-smooth, i.e., $\nabla
f:\mathbb{R}^{n}\to\mathbb{R}^{n}$ is ${\sf L}$-Lipschitz continuous.

  2. (A.2)

The stochastic gradient $\bm{g}^{k}:\Omega\to\mathbb{R}^{n}$ is an unbiased
estimator of $\nabla f(\bm{x}^{k})$, and there exist ${\sf A},\sigma\geqslant
0$, $\bar{f}\in\mathbb{R}$ such that $\mathbb{E}[\|\bm{g}^{k}-\nabla
f(\bm{x}^{k})\|^{2}\mid\mathcal{F}_{k-1}]\leqslant{\sf
A}(f(\bm{x}^{k})-\bar{f})+\sigma^{2}$ a.s. .

######  Assumption 8 (Conditions for ${\sf RR}$)

We work with the conditions:

  1. (B.1)

The individual component functions $f_{1},f_{2},\dots,f_{N}$ are all ${\sf
L}$-smooth.

  2. (B.2)

There exist constants ${\sf A},\sigma>0$, $\bar{f}\in\mathbb{R}$ such that for
all $x\in\mathbb{R}^{n}$, it holds that

$\frac{1}{N}\,{\sum}_{i=1}^{N}\|\nabla f_{i}(x)-\nabla f(x)\|^{2}\leqslant{\sf
A}(f(x)-\bar{f})+\sigma^{2}.$

  3. (B.3)

The permutations $\\{\pi^{k}\\}_{k}$ are sampled independently (for each $k$)
and uniformly without replacement from $\\{1,\dots,N\\}$.

The Lipschitz smootheness in (A.1) and (B.1) is ubiquitous in the analysis of
optimization methods, see, e.g., Bolte et al. (2014); Gürbüzbalaban et al.
(2019); HaoChen and Sra (2019). The assumptions (A.2) and (B.2) have been
extensively employed in the analysis of stochastic gradient-based methods
(Nguyen et al. (2021); Mishchenko et al. ; Shamir (2016); Sohl-Dickstein et
al. (2014)). In the case ${\sf A}=0$, (A.2) and (B.2) reduce to bounded
variance conditions. Furthermore, (B.2) is applicable in a wide range of
scenarios. For instance, (B.2) is satisfied when each individual component
function $f_{i}$ is Lipschitz smooth and bounded from below, see (Mishchenko
et al., , Proposition 2).

For both ${\sf SGD}$ and ${\sf RR}$, we will work with the following core
property that allows characterizing the geometric landscape of $f$.

######  Definition 9 (($\theta$,$\mu$)-PL Condition)

Given $\theta\in[\frac{1}{2},1]$ and $\mu>0$, the function $f$ is said to
satisfy the ($\theta$,$\mu$)-PL condition if $f$ is bounded from below by
$f^{*}:=\inf_{x\in\mathbb{R}^{n}}f(x)>-\infty$ and

$\|\nabla
f(x)\|\geqslant\sqrt{2\mu}(f(x)-f^{*})^{\theta},\quad\forall\,x\in\mathbb{R}^{n}.$

Definition 9 covers the well-known, classical Polyak-Łojasiewicz condition
(Polyak (1963)) as a special case when $\theta=\frac{1}{2}$.

######  Assumption 10 (PL Condition for $f$)

We consider the following assumption:

  1. (P)

For some $\theta\in[\frac{1}{2},1]$, $\mu>0$, the objective function $f$
satisfies ($\theta,\mu$)-PL condition.

In the following sections, we will employ Theorem 1 to establish the
convergence rates for various sampling schemes, under the $(\theta,\mu)$-PL
condition where $\theta\in[\frac{1}{2},1]$, with different step size schemes
in stochastic gradient-based methods. Under assumption (P) and without loss
generality, we set $\bar{f}=f^{*}$ in (A.2) and (B.2). We start with
(approximate) descent-type properties for ${\sf SGD}$ and ${\sf RR}$.

######  Lemma 11 (Descent-type Properties)

Suppose assumption (P) holds.

  1. (a)

Let $\\{\bm{x}^{k}\\}_{k}$ be generated by Algorithm 1 with step sizes
$\alpha_{k}\in(0,\frac{1}{{\sf L}}]$ and let the assumptions (A.1)–(A.2) be
satisfied. Then, it holds that

$\mathbb{E}[f(\bm{x}^{k+1})-f^{*}]\leqslant\Big{(}1+\frac{{\sf A}{\sf
L}\alpha_{k}^{2}}{2}\Big{)}\mathbb{E}[f(\bm{x}^{k})-f^{*}]-\mu\alpha_{k}(\mathbb{E}[f(\bm{x}^{k})-f^{*}])^{2\theta}+\frac{{\sf
L}\sigma^{2}\alpha_{k}^{2}}{2}.$ (15)

  2. (b)

Let the sequence $\\{\bm{x}^{k}\\}_{k}$ be generated by Algorithm 2 with step
sizes $\alpha_{k}\in(0,\frac{1}{2{\sf L}}]$ and let (B.1)–(B.3) hold. Then, we
have

$\mathbb{E}[f(\bm{x}^{k+1})-f^{*}]\leqslant\Big{(}1+\frac{{\sf A}{\sf
L}^{2}\alpha_{k}^{3}}{2N}\Big{)}\mathbb{E}[f(\bm{x}^{k})-f^{*}]-\frac{\mu\alpha_{k}}{2}(\mathbb{E}[f(\bm{x}^{k})-f^{*}])^{2\theta}+\frac{{\sf
L}^{2}\sigma^{2}\alpha_{k}^{3}}{2N}.$ (16)

Proof  For Algorithm 1, with assumptions (A.1)–(A.2), and
$\alpha_{k}\in(0,\frac{1}{{\sf L}}]$, we have

$\mathbb{E}[f(\bm{x}^{k+1})-f^{*}]\leqslant\Big{(}1+\frac{{\sf A}{\sf
L}\alpha_{k}^{2}}{2}\Big{)}\mathbb{E}[f(\bm{x}^{k})-f^{*}]-\frac{\alpha_{k}}{2}\mathbb{E}[\|\nabla
f(\bm{x}^{k})\|^{2}]+\frac{{\sf L}\sigma^{2}\alpha_{k}^{2}}{2}.$

For Algorithm 2, we refer to the result in (Mishchenko et al., , Appendix 9.5,
Proof of Theorem 4, eq. (47)). With (B.1)–(B.3), for
$\alpha_{k}\in(0,\frac{1}{2{\sf L}}]$, we have

$\mathbb{E}[f(\bm{x}^{k+1})-f^{*}]\leqslant\Big{(}1+\frac{{\sf A}{\sf
L}^{2}\alpha_{k}^{3}}{2N}\Big{)}\mathbb{E}[f(\bm{x}^{k})-f^{*}]-\frac{\alpha_{k}}{4}\mathbb{E}[\|\nabla
f(\bm{x}^{k})\|^{2}]+\frac{{\sf L}^{2}\sigma^{2}\alpha_{k}^{3}}{2N}.$

Combining $\|\nabla f(x)\|^{2}\geqslant 2\mu(f(x)-f^{*})^{2\theta}$ in (P) and
Hölder’s inequality, we obtain

$\mathbb{E}[\|\nabla f(x)\|^{2}]\geqslant
2\mu\mathbb{E}[(f(x)-f^{*})^{2\theta}]\geqslant
2\mu\mathbb{E}[(f(x)-f^{*})]^{2\theta},$

which finalizes the proof.

###  3.2 Main Recursion and Analysis Roadmap

From Lemma 11, it is evident that under the $(\theta,\mu)$-PL framework, the
problem reduces to analyzing the recursion with the given form:

$y_{k+1}\leqslant(1+\ell_{1}\alpha_{k}^{\tau})y_{k}-\ell_{2}\alpha_{k}y_{k}^{2\theta}+\ell_{3}\alpha_{k}^{\tau},\quad
k\in[K-1],$ (17)

where $y_{k}=\mathbb{E}[f(\bm{x}^{k})-f^{*}]$. For ${\sf SGD}$, we have
$\ell_{1}=\frac{{\sf A}{\sf L}}{2}$, $\ell_{2}=\mu$, $\ell_{3}=\frac{{\sf
L}\sigma^{2}}{2}$, $\tau=2$, and for ${\sf RR}$, it holds that
$\ell_{1}=\frac{{\sf A}{\sf L}^{2}}{2N}$, $\ell_{2}=\frac{\mu}{2}$,
$\ell_{3}=\frac{{\sf L}^{2}\sigma^{2}}{2N}$, $\tau=3$. Recursion (17)
generally lies beyond the scope of the generalized Chung’s lemma in the case
$\theta\neq\frac{1}{2}$. To address this discrepancy, we propose a solution
that involves constructing an auxiliary sequence $\\{u_{k}\\}_{k}$, for which
our generalized Chung’s lemma offers valuable instructional guidance. Here, we
provide a general roadmap for the analysis.

Step 1: Linearization and Relaxation. In the case $\theta\neq\frac{1}{2}$, the
term “$\ell_{2}\alpha_{k}y_{k}^{2\theta}$” depends on $y_{k}$ in a nonlinear
fashion and hence, Chung’s lemma is not immediately applicable to the
recursion (17). This can be resolved by substituting “$y_{k}^{2\theta}$” with
a suitable expression that only depends linearly on $y_{k}$. Since the mapping
$y\mapsto h_{\theta}(y):=y^{2\theta}$ is convex (on $\mathbb{R}_{+}$), this
can be essentially accomplished by utilizing the estimate

$y^{2\theta}\geqslant x^{2\theta}+2\theta
x^{2\theta-1}(y-x)\quad\forall\leavevmode\nobreak\ x,y\geqslant 0.$

Upon setting $y=y_{k}$ and $x=u_{k}$, this allows relaxing (17) to

$\displaystyle y_{k+1}$
$\displaystyle\leqslant(1+\ell_{1}\alpha_{k}^{\tau})y_{k}-\ell_{2}\alpha_{k}[h_{\theta}(u_{k})+2\theta
u_{k}^{2\theta-1}y_{k}-2\theta h_{\theta}(u_{k})]+\ell_{3}\alpha_{k}^{\tau}$
(18)
$\displaystyle=[1+\ell_{1}\alpha_{k}^{\tau}-2\theta\ell_{2}\alpha_{k}u_{k}^{2\theta-1}]y_{k}+[(2\theta-1)\ell_{2}\alpha_{k}u_{k}^{2\theta}+\ell_{3}\alpha_{k}^{\tau}],$

where $\\{u_{k}\\}_{k\geqslant 0}$ is a (free) non-negative auxiliary
sequence.

Step 2: Optimal Choice of $\\{u_{k}\\}_{k}$. The sequence $\\{u_{k}\\}_{k}$
should be chosen such that

  * 1.

The term “$\theta\ell_{2}\alpha_{k}u_{k}^{2\theta-1}$” is not smaller than
“$\ell_{1}\alpha_{k}^{\tau}$” (for all $k$), then (18) can be further relaxed
to

$y_{k+1}\leqslant[1-\theta\ell_{2}\alpha_{k}u_{k}^{2\theta-1}]y_{k}+[(2\theta-1)\ell_{2}\alpha_{k}u_{k}^{2\theta}+\ell_{3}\alpha_{k}^{\tau}].$
(19)

  * 2.

For recursion (19), the expected rate
$r_{k}\sim\frac{(2\theta-1)\ell_{2}\alpha_{k}u_{k}^{2\theta}+\ell_{3}\alpha_{k}^{\tau}}{\alpha_{k}u_{k}^{2\theta-1}}=(2\theta-1)\ell_{2}u_{k}+\ell_{3}\frac{\alpha_{k}^{\tau-1}}{u_{k}^{2\theta-1}}$
is optimal (as fast as possible), cf. Theorem 1.

Optimizing $r_{k}$ (as a function of $u_{k}$), we can obtain the following
candidate for $\\{u_{k}\\}_{k}$:

$u_{k}=\left({\ell_{3}}/{\ell_{2}}\right)^{\frac{1}{2\theta}}\alpha_{k}^{\frac{\tau-1}{2\theta}}.$
(20)

To satisfy the first requirement, we need
$\theta\ell_{2}\alpha_{k}u_{k}^{2\theta-1}\geqslant l_{1}\alpha_{k}^{\tau}$,
i.e.,
$\alpha_{k}\leqslant(\frac{\theta\ell_{2}^{\frac{1}{2\theta}}\ell_{3}^{\frac{2\theta-1}{2\theta}}}{\ell_{1}})^{\frac{2\theta}{\tau-1}}$.
Substituting (19) into (18), this yields

$y_{k+1}\leqslant[1-\theta\ell_{2}^{\frac{1}{2\theta}}\ell_{3}^{\frac{2\theta-1}{2\theta}}\alpha_{k}^{\frac{(2\theta-1)\tau+1}{2\theta}}]y_{k}+2\theta\ell_{3}\alpha_{k}^{\tau}.$

To simplify the notations, let us define
$\zeta:=\theta\ell_{2}^{\frac{1}{2\theta}}\ell_{3}^{\frac{2\theta-1}{2\theta}}$,
$\varrho:=\frac{2\theta}{(2\theta-1)\tau+1}$, and
$\omega:=\frac{\tau-1}{(2\theta-1)\tau+1}$. Then, we conclude that for all

$\alpha_{k}\leqslant\Big{(}\frac{\zeta}{\ell_{1}}\Big{)}^{\frac{\varrho}{\omega}},$
(21)

we have

$y_{k+1}\leqslant[1-\zeta\alpha_{k}^{{1}/{\varrho}}]y_{k}+2\theta\ell_{3}\alpha_{k}^{\tau}.$
(22)

The simplified and relaxed recursion (22) is the basis of our final step and
of the application of the generalized Chung’s lemma.

Step 3: Application of Chung’s Lemma to (22). To facilitate the analysis, we
need to assume $\zeta\alpha_{k}^{{1}/{\varrho}}\leqslant 1$, i.e.,

$\alpha_{k}\leqslant\zeta^{-\varrho}.$ (23)

Moreover, suppose that the step sizes $\alpha_{k}$ can be represented as a
function $\eta:\mathbb{R}\to\mathbb{R}_{+}$ evaluated at $b_{k}$, i.e.,
$\alpha_{k}=\eta(b_{k})$. Then, in Theorem 1, we can set

$s(x)=\frac{1}{\zeta}\eta(x)^{-\frac{1}{\varrho}},\leavevmode\nobreak\
\leavevmode\nobreak\
t(x)=\frac{1}{2\theta\ell_{3}}\eta(x)^{-\tau},\leavevmode\nobreak\
\leavevmode\nobreak\
r(x)=2\left(\frac{\ell_{3}}{\ell_{2}}\right)^{\frac{1}{2\theta}}\eta(x)^{\frac{\omega}{\varrho}},\leavevmode\nobreak\
\leavevmode\nobreak\
u(x)=\frac{\omega}{\varrho\zeta}\eta(x)^{-(1+\frac{1}{\varrho})}\eta^{\prime}(x),$
(24)

which satisfy $u(x)=s^{\prime}(x)-r(x)t^{\prime}(x)$. The rest of derivation
involves determining the appropriate function $\eta$ and sequence
$\\{b_{k}\\}_{k}$ to use for different types of step sizes and verifying the
conditions stated in Theorem 1 for such $\eta$ and $\\{b_{k}\\}_{k}$.

Linearization& Relaxation$-$linearize/relax nonlinear terms$-$introduce
auxiliary seq. $\\{u_{k}\\}_{k}$Step 1Optimal Choiceof
$\\{u_{k}\\}_{k}$$-$select $\\{u_{k}\\}_{k}$ and constants tooptimize the
convergence rateStep 2Application ofChung’s Lemma$-$use step size
functions$-$verify assump. in Theorem 1Step 3

Notation. Throughout this paper, we use $K$ to represent the total iterations
in ${\sf SGD}$ (or epochs in ${\sf RR}$). For all $k\in[K]$, we denote

$y_{k}:=\mathbb{E}[f(\bm{x}^{k})-f^{*}].$

We will use the following two sets of notations in the analysis of ${\sf SGD}$
(Algorithm 1) and ${\sf RR}$ (Algorithm 2), respectively. For ${\sf SGD}$, we
use

$\varrho_{1}=\frac{2\theta}{4\theta-1},\,\omega_{1}=\frac{1}{4\theta-1},\,\zeta_{1}={\theta}\mu^{\frac{1}{2\theta}}\Big{(}\frac{{\sf
L}\sigma^{2}}{2}\Big{)}^{1-\frac{1}{2\theta}},\,C_{1}=\frac{{\sf
A}^{4\theta-1}{\sf
L}}{2\theta^{4\theta}\sigma^{8\theta-4}\mu^{2}},\,C_{2}=\frac{2^{1-\frac{1}{2\theta}}{\sf
L}}{\theta\mu^{\frac{1}{2\theta}}(\sigma^{2})^{1-\frac{1}{2\theta}}}.$

For ${\sf RR}$, we use

$\varrho_{2}=\frac{\theta}{3\theta-1},\,\omega_{2}=\frac{1}{3\theta-1},\,\zeta_{2}=\frac{\theta}{2}\mu^{\frac{1}{2\theta}}\Big{(}\frac{{\sf
L}^{2}\sigma^{2}}{N}\Big{)}^{1-\frac{1}{2\theta}},\,C_{3}=\frac{2{\sf
A}^{3\theta-1}{\sf
L}}{\theta^{3\theta}\sigma^{6\theta-3}\mu^{\frac{3}{2}}},\,C_{4}=\frac{2^{4-\frac{1}{\theta}}{\sf
L}}{\theta\mu^{\frac{1}{2\theta}}(\sigma^{2})^{1-\frac{1}{2\theta}}}.$

###  3.3 The Analysis of Exponential and Cosine Step Sizes

Exponential and Cosine Step Size. We will use the following formats for
exponential step sizes:

$\alpha_{k}=\alpha\gamma^{k},\quad\text{where
$\gamma=\Big{(}\frac{\beta}{K}\Big{)}^{\frac{p}{K}}$, $\beta,p>0$,
{$K\geqslant 2^{\frac{\varrho}{p}}\beta$}},$

and for cosine step sizes:

$\alpha_{k}=\alpha\left[\frac{1+\cos(\frac{k\pi}{K})}{2}\right]^{\beta},\quad\text{where
$\beta>0$.}$

Selection of $b_{k}$ and $\eta$. For exponential step sizes, the naïve choice
$b_{k}=k$, $\eta(x)=\alpha\gamma^{x}$ already ensures the convexity of $r$.
However, for cosine step sizes, the choice $b_{k}=k$,
$\eta(x)=\alpha(\frac{1+\cos(\frac{x\pi}{K})}{2})^{\beta}$ does not work. As
we will see later in the proof of Lemma 12, the alternative choice
$b_{k}=[\frac{1+\cos(\frac{k\pi}{K})}{2}]^{\frac{\beta\omega}{\varrho}}$ and
$\eta(x)=\alpha x^{\frac{\varrho}{\omega}}$ can resolve this problem. Here, we
set $\varrho=\varrho_{1}=\frac{2\theta}{4\theta-1}$,
$\omega=\omega_{1}=\frac{1}{4\theta-1}$ in ${\sf SGD}$, and
$\varrho=\varrho_{2}=\frac{\theta}{3\theta-1}$,
$\omega=\omega_{2}=\frac{1}{3\theta-1}$ in ${\sf RR}$.

An Important Splitting Technique. A direct application of Theorem 1 to
exponential and cosine step sizes may lead to failure. To illustrate this, let
us consider ${\sf SGD}$ with exponential step sizes. For simplicity, we set
$\theta=\frac{1}{2}$, $\beta=1$, and $p=1$. Following the previous roadmap, we
only need to analyze recursion (22). Using the same notations as in (24) with
$b_{k}=k$ and $\eta(x)=\alpha K^{-\frac{x}{K}}$, we obtain

$s(x)=\frac{2}{\ell_{2}\alpha}K^{\frac{x}{K}},\quad
t(x)=\frac{1}{\ell_{3}\alpha^{2}}K^{\frac{2x}{K}},\quad
r(x)=\frac{2\ell_{3}\alpha}{\ell_{2}}K^{-\frac{x}{K}},\quad
u(x)=-\frac{1}{\zeta\alpha}K^{\frac{x}{K}}\frac{\log(K)}{K}.$

To verify (8), we need to find a non-decreasing positive sequence
$\\{\lambda_{k}\\}_{1\leqslant k\leqslant K}$ such that for all $k\in[K-1]$,
it holds that

$(b_{k+1}-b_{k})u(b_{k})=-\frac{1}{\zeta\alpha}K^{\frac{k}{K}}\frac{\log(K)}{K}\geqslant-1+\frac{1}{\lambda_{k+1}}.$
(25)

By simply setting $k=K-1$, we can observe that this is infeasible. When
$k=K-1$, equation (25) implies

$(b_{K}-b_{K-1})u(b_{K-1})\geqslant-1+\frac{1}{\lambda_{K}}>-1.$ (26)

However, by (25), we have

$(b_{K}-b_{K-1})u(b_{K-1})=-\frac{\log(K)}{\zeta\alpha}K^{-\frac{1}{K}}\leqslant-C\log(K),\quad\text{for
some $C>0$.}$ (27)

Consequently, (27) contradicts (26) whenever $K\geqslant\exp(-{1}/{C})$.
Therefore, for large $K$, condition (25) cannot be satisfied for the entire
sequence. Based on the diminishing property of the function $u$, this problem
arises when $k$ approaches the upper limit $K-1$.

Nonetheless, it is possible to fulfill (25) when $k$ is not close to $K-1$.
This observation inspires the subdivision of the index set $[K]$ into two
distinct sets. During the first iterations, (25) can be satisfied, and
subsequently, a non-asymptotic estimation for the endpoint can be derived by
applying Theorem 1. Subsequently, using Lemma 5, this estimation can be
extended to the final iterate $y_{k}$. We proceed by demonstrating the
execution of this idea in a simple example. Let us set $\lambda_{k}\equiv 2$.
Then, condition (25) is satisfied if and only if

$k\leqslant\log\Big{(}\frac{\zeta\alpha K}{2\log(K)}\Big{)}\frac{K}{\log(K)},$

which implies that (25) holds for all $0\leqslant k\leqslant\overline{K}$,
where $\overline{K}:=\lfloor\log\left(\frac{\zeta\alpha
K}{2\log(K)}\right)\frac{K}{\log(K)}\rfloor$. Applying Theorem 1 (b) to the
sequence $\\{y_{k}\\}_{0\leqslant k\leqslant\overline{K}+1}$, we obtain:

$y_{\overline{K}+1}\leqslant
2r(b_{\overline{K}+1})+(y_{0}-2r(b_{0}))\prod_{i=1}^{\overline{K}}\left(1-\frac{1}{s(b_{k})}\right).$

By utilizing Lemma 5, we can extend this estimate to $y_{K}$:

$y_{K}\leqslant
2r(b_{\overline{K}+1})+(y_{0}-2r(b_{0}))\prod_{i=1}^{K-1}\left(1-\frac{1}{s(b_{k})}\right),$

where

$r(b_{\overline{K}+1})=\frac{2\ell_{3}\alpha}{\ell_{2}}K^{-\frac{\overline{K}+1}{K}}\leqslant\frac{2\ell_{3}\alpha}{\ell_{2}}\exp\Big{(}-\log(K)\cdot\frac{\log(\frac{\zeta\alpha
K}{2\log(K)})}{\log(K)}\Big{)}=\frac{4\ell_{3}}{\ell_{2}\zeta}\frac{\log(K)}{K}.$

According to Corollary 6, the leading rate is
$\mathcal{O}(r(b_{\overline{K}+1}))$, i.e., $\mathcal{O}(\frac{\log(K)}{K})$.

Results on Exponential and Cosine Step Sizes. Following the general roadmap
and with the help of the above splitting technique, we are able to show the
convergence rate of both ${\sf SGD}$ and ${\sf RR}$ under general
$(\theta,\mu)$-PL condition with exponential and cosine step sizes. We first
introduce an important technical lemma.

###### Lemma 12

Consider a non-negative sequence $\\{y_{k}\\}_{0\leqslant k\leqslant K}$
satisfying

$y_{k+1}\leqslant(1+\ell_{1}\alpha_{k}^{\tau})y_{k}-\ell_{2}\alpha_{k}y_{k}^{2\theta}+\ell_{3}\alpha_{k}^{\tau}$
(28)

for all $k\in[K-1]$, where $\ell_{1},\ell_{2},\ell_{3}>0$, $K\in\mathbb{N}$
are given. Let us define

$\varrho:=\frac{2\theta}{(2\theta-1)\tau+1},\quad\omega:=\frac{\tau-1}{(2\theta-1)\tau+1},\quad\zeta:=\theta\ell_{2}^{\frac{1}{2\theta}}\ell_{3}^{\frac{2\theta-1}{2\theta}}.$

Then, the following statements hold.

  1. (a)

Let $\alpha_{k}=\alpha\gamma^{k}$ and $\gamma=(\frac{\beta}{K})^{\frac{p}{K}}$
be given and assume
$0<\alpha\leqslant\min\\{(\frac{\zeta}{\ell_{1}})^{\frac{\varrho}{\omega}},\zeta^{-\varrho}\\}$,
$p>0$, $K\geqslant 2^{\frac{\varrho}{p}}\beta>0$ and
$\frac{\log({K}/{\beta})}{K}\leqslant\frac{\varrho\zeta\alpha^{{1}/{\varrho}}}{2p\omega}$.
Then, it holds that

$y_{K}\leqslant
4\Big{(}{\frac{2p\omega}{\varrho}}\Big{)}^{\omega}\zeta^{-\omega}\Big{(}\frac{\ell_{3}}{\ell_{2}}\Big{)}^{\frac{1}{2\theta}}\left[\frac{\log({K}/{\beta})}{K}\right]^{\omega}+y_{0}\exp\left(-\frac{\varrho\zeta\alpha^{{1}/{\varrho}}}{2p}\frac{K}{\log({K}/{\beta})}\right).$

  2. (b)

Let $\alpha_{k}=\alpha[\frac{1+\cos(\frac{k\pi}{K})}{2}]^{\beta}$ be given
with
$0<\alpha\leqslant\min\\{(\frac{\zeta}{\ell_{1}})^{\frac{\varrho}{\omega}},\zeta^{-\varrho}\\}$,
then:

     * •

if $\beta\geqslant\frac{\varrho}{\omega}$, and
$K\geqslant\frac{\pi^{2}\beta\omega}{\alpha^{1/\varrho}\varrho\zeta}$, we have

$y_{K}\leqslant
4\Big{(}\frac{\pi}{2}\Big{)}^{\frac{{2\beta\omega}}{\varrho}}\Big{(}\frac{\ell_{3}}{\ell_{2}}\Big{)}^{\frac{1}{2\theta}}\alpha^{\frac{\omega}{\varrho}}\left[\frac{\pi^{2}\beta\omega}{\alpha^{1/\varrho}\varrho\zeta}\frac{1}{K}\right]^{\frac{2\beta\omega}{2\beta+\varrho}}+y_{0}\exp\left(-\frac{\zeta\alpha^{{1}/{\varrho}}}{2^{\max\\{1,{\beta}/{\varrho}\\}}}K\right).$

     * •

if $0<\beta<\frac{\varrho}{\omega}$, and
$K\geqslant\frac{4\pi^{2}\beta\omega}{\alpha^{1/\varrho}\varrho\zeta}$, we
have

$y_{K}\leqslant
4\Big{(}{\frac{\pi}{2}}\Big{)}^{\frac{2\beta\omega}{\varrho}}\Big{(}\frac{\ell_{3}}{\ell_{2}}\Big{)}^{\frac{1}{2\theta}}\alpha^{\frac{\omega}{\varrho}}\cdot\max\left\\{K^{-\frac{2\beta\omega}{\varrho}},\Big{(}\frac{4\pi^{2}\beta\omega}{\alpha^{1/\varrho}\varrho\zeta}\frac{1}{K}\Big{)}^{\frac{2\beta\omega}{2\beta+\varrho}}\right\\}+y_{0}\exp\left(-\frac{\zeta\alpha^{{1}/{\varrho}}K}{2^{\max\\{1,{\beta}/{\varrho}\\}}}\right).$

Proof  We prove the different parts of Lemma 12 in a step-by-step fashion and
following the previous derivations. Recall that the roadmap outlined in
Section 3.2 is applicable provided that
$\alpha_{k}\leq\min\\{(\frac{\zeta}{\ell_{1}})^{\frac{\varrho}{\omega}},\zeta^{-\varrho}\\}$,
see (21) and (23).

Proof of Part (a). We consider exponential step sizes of the form
$\alpha_{k}=\alpha\gamma^{k}$ where $\gamma=(\frac{\beta}{K})^{\frac{p}{K}}$,
$\alpha\leqslant\min\\{(\frac{\zeta}{\ell_{1}})^{\frac{\varrho}{\omega}},\zeta^{-\varrho}\\}$
and we have $p>0$, $K\geqslant 2^{\frac{\varrho}{p}}\beta>0$ and
$\frac{\log({K}/{\beta})}{K}\leqslant\frac{\varrho\zeta\alpha^{{1}/{\varrho}}}{2p\omega}$.
Let us set $b_{k}=k$ and $\eta(x)=\alpha\gamma^{x}$. The explicit formula of
$s,t,r,u$ can be obtained by substituting $\eta(x)=\alpha\gamma^{x}$ into
(24), i.e.,

$s(x)=\frac{1}{\zeta\alpha^{1/\varrho}}\gamma^{-\frac{x}{\varrho}},\leavevmode\nobreak\
\leavevmode\nobreak\ t(x)=\frac{1}{2\theta\ell_{3}\alpha^{\tau}}\gamma^{-\tau
x},\leavevmode\nobreak\ \leavevmode\nobreak\
r(x)=2\Big{(}\frac{\ell_{3}}{\ell_{2}}\Big{)}^{\frac{1}{2\theta}}\alpha^{\frac{\omega}{\varrho}}\gamma^{\frac{\omega
x}{\varrho}},\leavevmode\nobreak\ \leavevmode\nobreak\
u(x)=\frac{\omega\log(\gamma)}{\varrho\zeta\alpha^{1/\varrho}}\gamma^{-\frac{x}{\varrho}}.$

Since $0<\gamma<1$, we have $r$ is convex over the real line and $r(b_{k})$ is
decreasing w.r.t. $k$, which meets the requirements for $r$ in Theorem 1 and
Lemma 5. Meanwhile, $u$ is also decreasing on $\mathbb{R}$. Then for all

$k\leqslant\varrho\log\left(-\frac{2\omega\log(\gamma)}{\varrho\zeta\alpha^{{1}/{\varrho}}}\right)\Big{/}\log(\gamma)=\frac{\varrho}{p}\log\left(\frac{\varrho\zeta\alpha^{{1}/{\varrho}}K}{2p\omega\log({K}/{\beta})}\right)\frac{K}{\log({K}/{\beta})},$

we have

$(b_{k+1}-b_{k})u(b_{k})\geqslant-\frac{1}{2}.$

We can now apply Theorem 1 (b) and Lemma 5 to (22) in tandem by setting

$k_{0}=0,\quad\overline{K}=\min\left\\{K-1,\left\lfloor{\frac{\varrho}{p}\log\left(\frac{\varrho\zeta\alpha^{{1}/{\varrho}}K}{2p\omega\log({K}/{\beta})}\right)\frac{K}{\log({K}/{\beta})}}\right\rfloor\right\\}\quad\text{and}\quad\lambda_{k}\equiv
2.$

This yields

$y_{K}\leqslant
2r(\overline{K}+1)+y_{0}\prod_{k=0}^{K-1}(1-\frac{1}{s(b_{k})})\leqslant
4\left(\frac{\ell_{3}}{\ell_{2}}\right)^{\frac{1}{2\theta}}\alpha^{\frac{\omega}{\varrho}}\left(\frac{\beta}{K}\right)^{\frac{\overline{K}+1}{K}\frac{p\omega}{\varrho}}+y_{0}\prod_{k=0}^{K-1}(1-\zeta\alpha^{\frac{1}{\varrho}}\gamma^{\frac{k}{\varrho}}).$

In addition, we can establish the following relation

$\Big{(}\frac{\beta}{K}\Big{)}^{\frac{\overline{K}+1}{K}}=\exp\left(-\frac{\overline{K}+1}{K}\log({K}/{\beta})\right)\leqslant\exp\left(-\frac{\varrho}{p}\log\Big{(}\frac{\varrho\zeta\alpha^{{1}/{\varrho}}K}{2p\omega\log({K}/{\beta})}\Big{)}\right)=\left[\frac{2p\omega\log({K}/{\beta})}{\varrho\zeta\alpha^{{1}/{\varrho}}K}\right]^{\frac{\varrho}{p}}.$

Noticing
$\gamma^{\frac{K}{\varrho}}=(\frac{\beta}{K})^{\frac{p}{\varrho}}\leqslant\frac{1}{2}$
and using the geometric series $\sum_{k=0}^{K-1}x^{k}=\frac{1-x^{K}}{1-x}$,
$x\neq 1$, we have

$\displaystyle\prod_{k=0}^{K-1}(1-\zeta\alpha^{\frac{1}{\varrho}}\gamma^{\frac{k}{\varrho}})$
$\displaystyle\leqslant\exp\left(-\zeta\alpha^{\frac{1}{\varrho}}\sum_{k=0}^{K-1}\gamma^{\frac{k}{\varrho}}\right)$
$\displaystyle=\exp\left(-\zeta\alpha^{\frac{1}{\varrho}}\frac{1-\gamma^{{K}/{\varrho}}}{1-\gamma^{{1}/{\varrho}}}\right)\leqslant\exp\left(-\frac{\zeta\alpha^{{1}/{\varrho}}}{2}\frac{1}{1-\gamma^{{1}/{\varrho}}}\right).$

Applying the inequality $\exp(x)\geqslant 1+x$, we further obtain

$(1-\gamma^{\frac{1}{\varrho}})^{-1}=(1-\exp({\varrho^{-1}}\log(\gamma)))^{-1}\geqslant(-{\varrho^{-1}}\log(\gamma))^{-1}=\frac{\varrho}{p}\frac{K}{\log({K}/{\beta})}.$

Hence, we can conclude

$\displaystyle y_{K}\leqslant\leavevmode\nobreak$ $\displaystyle
4\left(\frac{\ell_{3}}{\ell_{2}}\right)^{\frac{1}{2\theta}}\alpha^{\frac{\omega}{\varrho}}\left[\frac{2p\omega\log({K}/{\beta})}{\varrho\zeta\alpha^{{1}/{\varrho}}K}\right]^{\omega}+y_{0}\prod_{k=0}^{K-1}(1-\zeta\alpha^{\frac{1}{\varrho}}\gamma^{\frac{k}{\varrho}})$
$\displaystyle\leqslant\leavevmode\nobreak$ $\displaystyle
4({\frac{2p\omega}{\varrho}})^{\omega}\zeta^{-\omega}\left(\frac{\ell_{3}}{\ell_{2}}\right)^{\frac{1}{2\theta}}\left[\frac{\log({K}/{\beta})}{K}\right]^{\omega}+y_{0}\exp\left(-\frac{\varrho\zeta\alpha^{{1}/{\varrho}}}{2p}\frac{K}{\log({K}/{\beta})}\right).$

Proof of Part (b). Now we consider cosine step sizes
$\alpha_{k}=\alpha[\frac{1+\cos(\frac{k\pi}{K})}{2}]^{\beta}$ where
$\alpha\leqslant\min\\{(\frac{\zeta}{\ell_{1}})^{\frac{\varrho}{\omega}},\zeta^{-\varrho}\\}$,
$\beta>0$. Let us define
$b_{k}:=[\frac{1+\cos(\frac{k\pi}{K})}{2}]^{\frac{\beta\omega}{\varrho}}$ and
$\eta(x):=\alpha x^{\frac{\varrho}{\omega}}$, then

$s(x)=\frac{1}{\zeta\alpha^{1/\varrho}}x^{-\frac{1}{\omega}},\leavevmode\nobreak\
\leavevmode\nobreak\
t(x)=\frac{1}{2\theta\ell_{3}\alpha^{\tau}}x^{-\frac{\varrho\tau}{\omega}},\leavevmode\nobreak\
\leavevmode\nobreak\
r(x)=2\left(\frac{\ell_{3}}{\ell_{2}}\right)^{\frac{1}{2\theta}}\alpha^{\frac{\omega}{\varrho}}x,\leavevmode\nobreak\
\leavevmode\nobreak\
u(x)=\frac{1}{\alpha^{{1}/{\varrho}}\zeta}x^{-(1+\frac{1}{\omega})}.$

Firstly, $r$ is linear, thus convex, over the real line, satisfying the
requirement for $r$ in Theorem 1. Moreover, as $r$ is increasing and $b_{k}$
is decreasing, $r(b_{k})$ decreases with respect to $k$, making Lemma 5
applicable. To prepare, we present an explicit formula for $u(b_{k})$:

$u(b_{k})=\frac{1}{\alpha^{{1}/{\varrho}}\zeta}\left[\frac{1+\cos(\frac{k\pi}{K})}{2}\right]^{-(\frac{\beta\omega}{\varrho}+\frac{\beta}{\varrho})}.$

Case I: $\beta\geqslant\frac{\varrho}{\omega}$. Since the function $x\mapsto
x^{\frac{\beta\omega}{\varrho}}$ is convex on $[0,+\infty)$, we have

$b_{k+1}-b_{k}\geqslant\frac{\beta\omega}{\varrho}\left[\frac{1+\cos(\frac{k\pi}{K})}{2}\right]^{\frac{\beta\omega}{\varrho}-1}\left[\frac{\cos(\frac{(k+1)\pi}{K})-\cos(\frac{k\pi}{K})}{2}\right].$

Thus, it follows

$(b_{k+1}-b_{k})u(b_{k})\geqslant\frac{\beta\omega}{\alpha^{{1}/{\varrho}}\varrho\zeta}\left[\frac{1+\cos(\frac{k\pi}{K})}{2}\right]^{-(\frac{\beta}{\varrho}+1)}\left[\frac{\cos(\frac{(k+1)\pi}{K})-\cos(\frac{k\pi}{K})}{2}\right].$

For $k\in[K]$, by double angle formula $1-\cos(2a)=2\sin^{2}(a)$, it holds
that
$1+\cos(\frac{k\pi}{K})=1-\cos(\frac{(K-k)\pi}{K})=2\sin^{2}(\frac{(K-k)\pi}{2K})$.
The function $x\mapsto\frac{\sin(x)}{x}$ is monotonically decreasing on
$[0,\frac{\pi}{2}]$ and hence, we have $\sin(x)\geqslant\frac{2}{\pi}x$ for
all $x\in[0,\frac{\pi}{2}]$. Hence, we can infer
$1+\cos(\frac{k\pi}{K})\geqslant 2(1-\frac{k}{K})^{2}$ and

$\left[\frac{1+\cos(\frac{k\pi}{K})}{2}\right]^{-(1+\frac{\beta}{\varrho})}\leqslant\left(1-\frac{k}{K}\right)^{-2(1+\frac{\beta}{\varrho})}.$

In addition, utilizing the sum-to-product identity
$\cos(a)-\cos(b)=-2\sin(\frac{1}{2}(a+b))\sin(\frac{1}{2}(a-b))$,
$\sin(x)=\sin(\pi-x)$, and $\sin(x)\leq x$, it holds that

$\cos\left(\frac{(k+1)\pi}{K}\right)-\cos\left(\frac{k\pi}{K}\right)=-2\sin\left(\frac{(2k+1)\pi}{2K}\right)\sin\left(\frac{\pi}{2K}\right)\geqslant-\frac{\pi^{2}}{K}\left(1-\frac{k}{K}\right).$
(29)

Then, we obtain

$(b_{k+1}-b_{k})u(b_{k})\geqslant-\frac{\pi^{2}\beta\omega}{2\alpha^{{1}/{\varrho}}\varrho\zeta}\frac{1}{K}\left(1-\frac{k}{K}\right)^{-(1+2\frac{\beta}{\varrho})}.$

Thus, for all $0\leqslant k\leqslant
K(1-[\frac{\pi^{2}\beta\omega}{\alpha^{1/\varrho}\varrho\zeta}\frac{1}{K}]^{\frac{1}{1+2\beta/\varrho}})$,
we have $(b_{k+1}-b_{k})u(b_{k})\geqslant-\frac{1}{2}$. Moreover, the rate
function $r$ is convex on the whole real line and $r(b_{k})$ is non-increasing
w.r.t. $k$ for all $k\in[K]$. Invoking Theorem 1 (b) and Lemma 5 in tandem for
(22) with

$k_{0}=0,\quad\overline{K}=\left\lfloor
K-K\Big{(}\frac{\pi^{2}\beta\omega}{\alpha^{1/\varrho}\varrho\zeta}\frac{1}{K}\Big{)}^{\frac{1}{2\beta/\varrho+1}}\right\rfloor\quad\text{and}\quad\lambda_{k}\equiv
2,$

it follows

$y_{K}\leqslant
4\left(\frac{\ell_{3}}{\ell_{2}}\right)^{\frac{1}{2\theta}}\alpha^{\frac{\omega}{\varrho}}\left[\frac{1+\cos(\frac{(\overline{K}+1)\pi}{K})}{2}\right]^{\frac{\beta\omega}{\varrho}}+y_{0}\prod_{k=0}^{K-1}\left(1-{\zeta}\alpha^{\frac{1}{\varrho}}\Big{[}\frac{1+\cos(\frac{k\pi}{K})}{2}\Big{]}^{\frac{\beta}{\varrho}}\right).$

Here, the condition $\overline{K}\geqslant 0$ is guaranteed by
$K\geqslant\frac{\pi^{2}\beta\omega}{\alpha^{1/\varrho}\varrho\zeta}$. Using
$\overline{K}+1\geqslant
K(1-[\frac{\pi^{2}\beta\omega}{\alpha^{1/\varrho}\varrho\zeta}\frac{1}{K}]^{\frac{1}{2\beta/\varrho+1}})$
and $1+\cos(\frac{k\pi}{K})\leqslant\frac{\pi^{2}}{2}(1-\frac{k}{K})^{2}$, we
further have

$1+\cos\left(\frac{(\overline{K}+1)\pi}{K}\right)\leqslant\frac{\pi^{2}}{2}\left(1-\frac{\overline{K}+1}{K}\right)^{2}\leqslant\frac{\pi^{2}}{2}\left[\frac{\pi^{2}\beta\omega}{\alpha^{1/\varrho}\varrho\zeta}\frac{1}{K}\right]^{\frac{2}{2\beta/\varrho+1}}.$

To handle the product term, we notice

$\prod_{k=0}^{K-1}\left(1-{\zeta}\alpha^{\frac{1}{\varrho}}\Big{[}\frac{1+\cos(\frac{k\pi}{K})}{2}\Big{]}^{\frac{\beta}{\varrho}}\right)\leqslant\exp\left(-{\zeta}\alpha^{\frac{1}{\varrho}}\sum_{k=0}^{K-1}\Big{[}\frac{1+\cos(\frac{k\pi}{K})}{2}\Big{]}^{\frac{\beta}{\varrho}}\right).$

Using Lagrange’s trigonometric identity
$\sum_{k=0}^{n}\cos(ka)=\frac{1}{2}+\frac{\sin(\frac{(2n+1)a}{2})}{2\sin(\frac{a}{2})}$,
we have
$\sum_{k=0}^{K-1}[1+\cos(\frac{k\pi}{K})]=K+\frac{1}{2}+\frac{\sin((K-\frac{1}{2})\frac{\pi}{K})}{2\sin(\frac{\pi}{2K})}=K+1$.
Next, we further consider the following cases:

  * •

If $\beta>\varrho$, applying Jensen’s inequality, it follows

$\sum_{k=0}^{K-1}\Big{[}\frac{1+\cos(\frac{k\pi}{K})}{2}\Big{]}^{\frac{\beta}{\varrho}}\geqslant
K\Big{[}\frac{1}{K}\sum_{k=0}^{K-1}\frac{1+\cos(\frac{k\pi}{K})}{2}\Big{]}^{\frac{\beta}{\varrho}}\geqslant\frac{K}{2^{\beta/\varrho}}.$

  * •

If $\beta\leqslant\varrho$, we then have
$\sum_{k=0}^{K-1}[\frac{1+\cos(\frac{k\pi}{K})}{2}]^{\frac{\beta}{\varrho}}\geqslant\sum_{k=0}^{K-1}[\frac{1+\cos(\frac{k\pi}{K})}{2}]\geqslant\frac{K}{2}$.

This shows
$\sum_{k=0}^{K-1}[\frac{1+\cos(\frac{k\pi}{K})}{2}]^{\frac{\beta}{\varrho}}\geqslant\frac{K}{2^{\max\\{1,{\beta}/{\varrho}\\}}}$
and we can conclude

$y_{K}\leqslant
4\left(\frac{\pi}{2}\right)^{\frac{{2\beta\omega}}{\varrho}}\left(\frac{\ell_{3}}{\ell_{2}}\right)^{\frac{1}{2\theta}}\alpha^{\frac{\omega}{\varrho}}\left[\frac{\pi^{2}\beta\omega}{\alpha^{1/\varrho}\varrho\zeta}\frac{1}{K}\right]^{\frac{2\beta\omega}{2\beta+\varrho}}+y_{0}\exp\left(-\frac{\zeta\alpha^{{1}/{\varrho}}}{2^{\max\\{1,{\beta}/{\varrho}\\}}}K\right).$

Case II: $0<\beta<\frac{\varrho}{\omega}$. In this case, the function
$x\mapsto x^{\frac{\beta\omega}{\varrho}}$ is concave on $[0,+\infty)$, and we
obtain

$b_{k+1}-b_{k}\geqslant\frac{\beta\omega}{\varrho}\left[\frac{1+\cos(\frac{(k+1)\pi}{K})}{2}\right]^{\frac{\beta\omega}{\varrho}-1}\left[\frac{\cos(\frac{(k+1)\pi}{K})-\cos(\frac{k\pi}{K})}{2}\right].$

Thus, it follows

$\displaystyle(b_{k+1}-b_{k})u(b_{k})$
$\displaystyle\geqslant\leavevmode\nobreak$
$\displaystyle\frac{\beta\omega}{\alpha^{{1}/{\varrho}}\varrho\zeta}\left[\frac{1+\cos(\frac{k\pi}{K})}{2}\right]^{-(\frac{\beta\omega}{\varrho}+\frac{\beta}{\varrho})}\left[\frac{1+\cos(\frac{(k+1)\pi}{K})}{2}\right]^{\frac{\beta\omega}{\varrho}-1}\left[\frac{\cos(\frac{(k+1)\pi}{K})-\cos(\frac{k\pi}{K})}{2}\right]$
$\displaystyle=\leavevmode\nobreak$
$\displaystyle\frac{\beta\omega}{\alpha^{{1}/{\varrho}}\varrho\zeta}\left[\frac{1+\cos(\frac{(k+1)\pi}{K})}{1+\cos(\frac{k\pi}{K})}\right]^{\frac{\beta\omega}{\varrho}}\left[\frac{1+\cos(\frac{k\pi}{K})}{2}\right]^{-\frac{\beta}{\varrho}}\left[\frac{1+\cos(\frac{(k+1)\pi}{K})}{2}\right]^{-1}\left[\frac{\cos(\frac{(k+1)\pi}{K})-\cos(\frac{k\pi}{K})}{2}\right]$
$\displaystyle\geqslant\leavevmode\nobreak$
$\displaystyle\frac{\beta\omega}{\alpha^{{1}/{\varrho}}\varrho\zeta}\left[\frac{1+\cos(\frac{k\pi}{K})}{2}\right]^{-\frac{\beta}{\varrho}}\left[\frac{1+\cos(\frac{(k+1)\pi}{K})}{2}\right]^{-1}\left[\frac{\cos(\frac{(k+1)\pi}{K})-\cos(\frac{k\pi}{K})}{2}\right].$

Utilizing $1+\cos(\frac{k\pi}{K})\geqslant 2(1-\frac{k}{K})^{2}$ as shown in
Case I, we have for all $k\in[K-1]$,

$\Big{[}{\frac{1+\cos(\frac{k\pi}{K})}{2}}\Big{]}^{-\frac{\beta}{\varrho}}\leqslant\Big{(}1-\frac{k}{K}\Big{)}^{-\frac{2\beta}{\varrho}},$

and for all $k\in[K-2]$,

$\Big{[}{\frac{1+\cos(\frac{(k+1)\pi}{K})}{2}}\Big{]}^{-1}\leqslant\Big{(}1-\frac{k+1}{K}\Big{)}^{-2}\leqslant
4\Big{(}1-\frac{k}{K}\Big{)}^{-2}.$

For the last inequality, we use
$1-\frac{k+1}{K}\geqslant\frac{1}{2}(1-\frac{k}{K})$. Combining the previous
estimates and (29), we can infer:

$(b_{k+1}-b_{k})u(b_{k})\geqslant-\frac{2\pi^{2}\beta\omega}{\alpha^{{1}/{\varrho}}\varrho\zeta}\frac{1}{K}\Big{(}1-\frac{k}{K}\Big{)}^{-(1+2\frac{\beta}{\varrho})}.$

Then, for all $0\leqslant
k\leqslant\min\\{K-2,K(1-[\frac{4\pi^{2}\beta\omega}{\alpha^{1/\varrho}\varrho\zeta}\frac{1}{K}]^{\frac{1}{1+2\beta/\varrho}})\\}$,
we have $(b_{k+1}-b_{k})u(b_{k})\geqslant-\frac{1}{2}$. Invoking Theorem 1 (b)
and Lemma 5 in tandem for (22) with

$k_{0}=0,\quad\overline{K}=\min\\{K-2,\left\lfloor
K(1-[\frac{4\pi^{2}\beta\omega}{\alpha^{1/\varrho}\varrho\zeta}\frac{1}{K}]^{\frac{1}{2\beta/\varrho+1}})\right\rfloor\\},\quad\text{and
}\lambda_{k}\equiv 2,$

it follows

$y_{K}\leqslant
4\Big{(}\frac{\ell_{3}}{\ell_{2}}\Big{)}^{\frac{1}{2\theta}}\alpha^{\frac{\omega}{\varrho}}\Big{[}\frac{1+\cos(\frac{(\overline{K}+1)\pi}{K})}{2}\Big{]}^{\frac{\beta\omega}{\varrho}}+y_{0}\prod_{k=0}^{K-1}\Big{(}1-{\zeta}\alpha^{\frac{1}{\varrho}}\Big{[}\frac{1+\cos(\frac{k\pi}{K})}{2}\Big{]}^{\frac{\beta}{\varrho}}\Big{)}.$

Here, the condition $\overline{K}\geqslant 0$ is guaranteed by
$K\geqslant\frac{4\pi^{2}\beta\omega}{\alpha^{1/\varrho}\varrho\zeta}$. Using
$\overline{K}+1\geqslant\min\\{K-1,K(1-[\frac{4\pi^{2}\beta\omega}{\alpha^{1/\varrho}\varrho\zeta}\frac{1}{K}]^{\frac{1}{2\beta/\varrho+1}})\\}$
and $1+\cos(\frac{k\pi}{K})\leqslant\frac{\pi^{2}}{2}(1-\frac{k}{K})^{2}$, we
have

$1+\cos\left(\frac{(\overline{K}+1)\pi}{K}\right)\leqslant\frac{\pi^{2}}{2}\left(1-\frac{\overline{K}+1}{K}\right)^{2}\leqslant\frac{\pi^{2}}{2}\max\left\\{\frac{1}{K^{2}},\left[\frac{4\pi^{2}\beta\omega}{\alpha^{1/\varrho}\varrho\zeta}\frac{1}{K}\right]^{\frac{2}{2\beta/\varrho+1}}\right\\}.$

Using the same strategy in Case I to handle the product term, we can conclude

$y_{K}\leqslant
4\left(\frac{\pi}{2}\right)^{\frac{2\beta\omega}{\varrho}}\left(\frac{\ell_{3}}{\ell_{2}}\right)^{\frac{1}{2\theta}}\alpha^{\frac{\omega}{\varrho}}\max\\{K^{-\frac{2\beta\omega}{\varrho}},\left[\frac{4\pi^{2}\beta\omega}{\alpha^{1/\varrho}\varrho\zeta}\frac{1}{K}\right]^{\frac{2\beta\omega}{2\beta+\varrho}}\\}+y_{0}\exp\left(-\frac{\zeta\alpha^{{1}/{\varrho}}}{2^{\max\\{1,{\beta}/{\varrho}\\}}}K\right).$

This finishes the proof of Lemma 12.
The following results on exponential and cosine step sizes can be obtained
directly from Lemma 12.

######  Theorem 13 (Convergence Rate of ${\sf SGD}$ with Exponential Step
Sizes)

Let (A.1)–(A.2) and (P) hold, and let the sequence
$\\{\bm{x}^{k}\\}_{0\leqslant k\leqslant K}$, $K\geqslant 1$, be generated by
${\sf SGD}$ with $\alpha_{k}=\alpha\gamma^{k}$ and
$\gamma=(\frac{\beta}{K})^{\frac{p}{K}}$. If
$0<\alpha\leqslant\min\\{(\frac{2\zeta_{1}}{{\sf A}{\sf
L}})^{2\theta},\zeta_{1}^{-\varrho_{1}},{{\sf L}}^{-1}\\}$ and $K$ is
sufficiently large such that $K\geqslant 2^{\frac{\varrho_{1}}{p}}\beta>0$ and
$\frac{\log({K}/{\beta})}{K}\leqslant\frac{\varrho_{1}\zeta_{1}\alpha^{{1}/{\varrho_{1}}}}{2p\omega_{1}}$,
then we have

$y_{K}\leqslant
4\left(\frac{p}{2\theta^{2}}\right)^{\omega_{1}}\left(\frac{{\sf
L}\sigma^{2}}{\mu^{2}}\right)^{\omega_{1}}\left[\frac{\log({K}/{\beta})}{K}\right]^{\omega_{1}}+y_{0}\exp\left(-\frac{\varrho_{1}\zeta_{1}\alpha^{{1}/{\varrho_{1}}}}{2p}\frac{K}{\log({K}/{\beta})}\right).$
(30)

The full proof can be found in Section C.1. In the case
$\alpha=\min\\{(\frac{2\zeta_{1}}{{\sf A}{\sf
L}})^{2\theta},\zeta_{1}^{-\varrho_{1}},{{\sf L}}^{-1}\\}$, the term
$\zeta_{1}\alpha^{1/\varrho_{1}}$ in (30) further simplifies to
$\zeta_{1}\alpha^{1/\varrho_{1}}=\min\\{C_{1}^{-1},C_{2}^{-1},1\\}$. When
$\theta=\frac{1}{2}$, (Li et al., 2021, Theorem 1) shows a similar rate to
(30), with the difference being that they have a worse $\log^{2}(K)$
dependence in the dominant term. The work (Wang et al., 2021, Theorem 4.1)
derives the same type of results under strong convexity and a more stringent
bounded variance assumption. It is worth noting that our result also covers
the range $\theta\in(\frac{1}{2},1]$, which is not present in these previous
works.

######  Theorem 14 (Convergence Rate of ${\sf RR}$ with Exponential Step
Sizes)

Let (B.1)–(B.3) and (P) hold, and let $\\{\bm{x}^{k}\\}_{0\leqslant k\leqslant
K}$, $K\geqslant 1$, be generated by ${\sf RR}$ with
$\alpha_{k}=\alpha\gamma^{k}$ and $\gamma=(\frac{\beta}{K})^{\frac{p}{K}}$. If
$\alpha\leqslant\min\\{(\frac{2N\zeta_{2}}{{\sf A}{\sf
L}^{2}})^{\theta},\zeta_{2}^{-\varrho_{2}},\frac{1}{2{\sf L}}\\}$ and $K$ is
large enough such that $K\geqslant 2^{\frac{\varrho_{2}}{p}}\beta>0$ and
$\frac{\log({K}/{\beta})}{K}\leqslant\frac{\varrho_{2}\zeta_{2}\alpha^{{1}/{\varrho_{2}}}}{2p\omega_{2}}$,
then it holds that

$y_{K}\leqslant
4\left(\frac{4p}{\theta^{2}}\right)^{\omega_{2}}\left(\frac{{\sf
L}\sigma}{\mu^{{3}/{2}}}\right)^{\omega_{2}}\left[\frac{\log({K}/{\beta})}{\sqrt{N}K}\right]^{\omega_{2}}+y_{0}\exp\left(-\frac{\varrho_{2}\zeta_{2}\alpha^{{1}/{\varrho_{2}}}}{2p}\frac{K}{\log({K}/{\beta})}\right).$
(31)

Moreover, if $\alpha=\min\\{(\frac{2N\zeta_{2}}{{\sf A}{\sf
L}^{2}})^{\theta},\zeta_{2}^{-\varrho_{2}},\frac{1}{2{\sf L}}\\}$,
$\frac{K}{\log(K/\beta)}\geqslant\frac{4p}{\theta}\max\\{\frac{C_{3}}{\sqrt{N}},C_{4}N^{1-\frac{1}{2\theta}},1\\}\log(NK)$,
and $K\geqslant 2^{\frac{\varrho_{2}}{p}}\beta>0$, then

$y_{K}\leqslant
4\left(\frac{4p}{\theta^{2}}\right)^{\omega_{2}}\left(\frac{{\sf
L}\sigma}{\mu^{{3}/{2}}}\right)^{\omega_{2}}\left[\frac{\log({K}/{\beta})}{\sqrt{N}K}\right]^{\omega_{2}}+y_{0}(NK)^{-\omega_{2}}.$
(32)

The proof of Theorem 14 is provided in Section C.1. Theorem 14 extends the
theoretical results for ${\sf RR}$ by including exponential step sizes case
under the general $(\theta,\mu)$-PL condition.

######  Theorem 15 (Convergence Rate for ${\sf SGD}$ with cosine step sizes)

Suppose (A.1)–(A.2) and (P) hold. Let the sequence
$\\{\bm{x}^{k}\\}_{0\leqslant k\leqslant K}$ where $K\geqslant 2$ be generated
by Algorithm 1 with
$\alpha_{k}=\alpha[\frac{1+\cos(\frac{k\pi}{K})}{2}]^{\beta}$. Let
$\alpha\leqslant\min\\{(\frac{2\zeta_{1}}{{\sf A}{\sf
L}})^{2\theta},\zeta_{1}^{-\varrho_{1}},{\sf L}^{-1}\\}$, then

  * •

if $\beta\geqslant 2\theta$ and
$K\geqslant\frac{\pi^{2}\beta}{2\theta\alpha^{1/\varrho_{1}}\zeta_{1}}$, we
have

$y_{K}\leqslant
4\Big{(}\frac{\pi}{2}\Big{)}^{\frac{{2\beta\omega_{1}}}{\varrho_{1}}}\Big{(}\frac{{\sf
L}\sigma}{2\mu}\Big{)}^{\frac{1}{2\theta}}\alpha^{\frac{\omega_{1}}{\varrho_{1}}}\Big{[}\frac{\pi^{2}\beta}{2\theta\alpha^{1/\varrho_{1}}\zeta_{1}}\frac{1}{K}\Big{]}^{\frac{2\beta\omega_{1}}{2\beta+\varrho_{1}}}+y_{0}\exp\Big{(}-\frac{\zeta_{1}\alpha^{{1}/{\varrho_{1}}}}{2^{\max\\{1,{\beta}/{\varrho_{1}}\\}}}K\Big{)}.$
(33)

  * •

if $\beta<2\theta$ and
$K\geqslant\frac{2\pi^{2}\beta}{\theta\alpha^{1/\varrho_{1}}\zeta_{1}}$, we
have

$y_{K}\leqslant
4\Big{(}\frac{\pi}{2}\Big{)}^{\frac{{2\beta\omega_{1}}}{\varrho_{1}}}\Big{(}\frac{{\sf
L}\sigma}{2\mu}\Big{)}^{\frac{1}{2\theta}}\alpha^{\frac{\omega_{1}}{\varrho_{1}}}\max\Big{\\{}K^{-\frac{2\beta\omega_{1}}{\varrho_{1}}},\Big{[}\frac{\pi^{2}\beta}{2\theta\alpha^{1/\varrho_{1}}\zeta_{1}}\frac{1}{K}\Big{]}^{\frac{2\beta\omega_{1}}{2\beta+\varrho_{1}}}\Big{\\}}+y_{0}\exp\Big{(}-\frac{\zeta_{1}\alpha^{{1}/{\varrho_{1}}}}{2^{\max\\{1,{\beta}/{\varrho_{1}}\\}}}K\Big{)}.$
(34)

Moreover, if
$\alpha=2^{\max\\{\beta,\varrho_{1}\\}}(\frac{2\omega_{1}\log(K)}{\zeta_{1}K})^{\varrho_{1}}$,
${K}\geqslant\Theta(\max\\{{C_{1}},C_{2},1\\}){\log(K)})$, then

$y_{K}=\mathcal{O}\Big{(}\Big{[}\frac{(\log(K))^{\frac{\varrho_{1}}{2\beta+\varrho_{1}}}}{K}\Big{]}^{\omega_{1}}\Big{)}.$
(35)

The proof is deferred to Section C.2. To the best of our knowledge, the only
existing theoretical analysis on the convergence of cosine step sizes under
PL-type condition is provided in Li et al. (2021). In (Li et al., 2021,
Theorem 2), the authors obtained the complexity bound
$\mathcal{O}(K^{-\frac{2}{3}})$ for ${\sf SGD}$ with $\beta=1$ under the
$(\frac{1}{2},\mu)$-PL condition. Our Theorem 15 can recover their result by
setting $\beta=1$ and $\theta=\frac{1}{2}$ in (33). Furthermore, we can
improve this rate to $\mathcal{O}(\log^{1/3}(K)/K)$ by carefully selecting the
step size parameter $\alpha$; see (35). It is worth mentioning that we also
derive the result for $\theta\in(\frac{1}{2},1]$, which are new.

######  Theorem 16 (Convergence Rate for ${\sf RR}$ with Cosine Step Sizes)

Suppose (B.1)–(B.3) and (P) hold. Let the sequence
$\\{\bm{x}^{k}\\}_{0\leqslant k\leqslant K}$, $K\geqslant 2$, be generated by
${\sf SGD}$ with
$\alpha_{k}=\alpha[\frac{1+\cos(\frac{k\pi}{K})}{2}]^{\beta}$. Let
$\alpha\leqslant\min\\{(\frac{2N\zeta_{2}}{{\sf A}{\sf
L}^{2}})^{\theta},\zeta_{2}^{-\varrho_{2}},(2{\sf L})^{-1}\\}$, then

  * •

if $\beta\geqslant\theta$ and
$K\geqslant\frac{\pi^{2}\beta}{\theta\alpha^{1/\varrho_{2}\zeta_{2}}}$, we
have

$y_{K}\leqslant
4\Big{(}\frac{\pi}{2}\Big{)}^{\frac{{2\beta\omega_{2}}}{\varrho_{2}}}\Big{(}\frac{{\sf
L}^{2}\sigma^{2}}{\mu
N}\Big{)}^{\frac{1}{2\theta}}\alpha^{\frac{\omega_{2}}{\varrho_{2}}}\Big{[}\frac{\pi^{2}\beta}{\theta\alpha^{1/\varrho_{2}}\zeta_{2}}\frac{1}{K}\Big{]}^{\frac{2\beta\omega_{2}}{2\beta+\varrho_{2}}}+y_{0}\exp\Big{(}-\frac{\zeta_{2}\alpha^{{1}/{\varrho_{2}}}}{2^{\max\\{1,{\beta}/{\varrho_{2}}\\}}}K\Big{)}.$
(36)

  * •

if $\beta<\theta$ and
$K\geqslant\frac{4\pi^{2}\beta}{\theta\alpha^{1/\varrho_{2}}\zeta_{2}}$, we
have

$y_{K}\leqslant
4\Big{(}\frac{\pi}{2}\Big{)}^{\frac{{2\beta\omega_{2}}}{\varrho_{2}}}\Big{(}\frac{{\sf
L}^{2}\sigma^{2}}{\mu
N}\Big{)}^{\frac{1}{2\theta}}\alpha^{\frac{\omega_{2}}{\varrho_{2}}}\max\Big{\\{}K^{-\frac{2\beta\omega_{2}}{\varrho_{2}}},\Big{[}\frac{\pi^{2}\beta}{\theta\alpha^{1/\varrho_{2}}\zeta_{2}}\frac{1}{K}\Big{]}^{\frac{2\beta\omega_{2}}{2\beta+\varrho_{2}}}\Big{\\}}+y_{0}\exp\Big{(}-\frac{\zeta_{2}\alpha^{{1}/{\varrho_{2}}}}{2^{\max\\{1,{\beta}/{\varrho_{2}}\\}}}K\Big{)}.$
(37)

Moreover, if
$\alpha=2^{\max\\{\varrho_{2},\beta\\}}(\frac{2\omega_{2}\log(NK)}{\zeta_{2}K})^{\varrho_{2}}$
and
${K}\geqslant\Theta(\max\\{\frac{C_{3}}{\sqrt{N}},C_{4}N^{1-\frac{1}{2\theta}},1\\})\log(NK))$,
then

$y_{K}=\mathcal{O}\Big{(}\Big{[}\frac{(\log(NK))^{\frac{1}{2\beta/\varrho_{2}+1}}}{\sqrt{N}K}\Big{]}^{\omega_{2}}\Big{)}.$
(38)

The proof is deferred to Section C.2. The results in Theorem 16 are new for
${\sf RR}$.

###  3.4 The Analysis of Constant and Polynomial Step Sizes

For comprehensiveness, we conduct the aforementioned analysis for polynomial
and constant step size rules. The findings are presented in Theorems 20, 21,
17 and 18, accompanied by an in-depth comparison to prior research.

####  3.4.1 Constant Step Sizes

Based on the roadmap in Section 3.2, we can obtain the following convergence
results for ${\sf SGD}$ and ${\sf RR}$ utilizing constant step sizes.

######  Theorem 17 (Convergence Rate for ${\sf SGD}$ with Constant Step Size)

Let (A.1)–(A.2) and (P) hold. Let the sequence $\\{\bm{x}^{k}\\}_{0\leqslant
k\leqslant K}$, $K\geqslant 2$, be generated by ${\sf SGD}$ with
$\alpha_{k}=[\frac{\alpha\log(K)}{K}]^{\varrho_{1}}$. If $\alpha>0$ and $K$
satisfies $K\geqslant 1$,
$\frac{\alpha\log(K)}{K}\leqslant\min\\{(\frac{2\zeta_{1}}{{\sf A}{\sf
L}})^{\frac{1}{\omega_{1}}},\zeta_{1}^{-1},{{\sf
L}}^{-\frac{1}{\varrho_{1}}}\\}$, then

$y_{K}\leqslant 2\left(\frac{{\sf
L}\sigma^{2}}{2\mu}\right)^{\frac{1}{2\theta}}\left[\frac{\alpha\log(K)}{K}\right]^{\omega_{1}}+y_{0}K^{-\zeta_{1}\alpha}.$
(39)

Moreover, if $\alpha=\frac{2\omega_{1}}{\zeta_{1}}$ and
$K\geqslant({2\omega_{1}}\max\\{{C_{1}},C_{2},1\\})\log(K)$, then

$y_{K}\leqslant
2\left(\frac{\omega_{1}}{\theta}\right)^{\omega_{1}}\left(\frac{{\sf
L}\sigma^{2}}{\mu^{2}}\right)^{\omega_{1}}\left[\frac{\log(K)}{K}\right]^{\omega_{1}}+y_{0}K^{-2\omega_{1}}.$
(40)

The proof is provided in Section D.2. ${\sf SGD}$ under constant step sizes
has been extensively studied, but mostly limited to the case where
$\theta=\frac{1}{2}$ (or under stronger assumptions); see, e.g., Gower et al.
(2019); Bottou et al. (2018); Needell et al. (2014); Shamir and Zhang (2013).
We can recover the existing results and provide new complexity bounds when
$\theta\in(\frac{1}{2},1]$, which have not been studied in the literature to
our knowledge.

######  Theorem 18 (Convergence Rate for ${\sf RR}$ with Constant Step Size)

Let (B.1)–(B.3) and (P) hold. Let the sequence $\\{\bm{x}^{k}\\}_{0\leqslant
k\leqslant K}$, $K\geqslant 2$, be generated by ${\sf RR}$ with
$\alpha_{k}=[\frac{\alpha\log(K)}{K}]^{\varrho_{2}}$. If $\alpha>0$ and $K$
satisfies $\frac{\alpha\log(K)}{K}\leqslant\min\\{(\frac{2N\zeta_{2}}{{\sf
A}{\sf L}^{2}})^{\frac{1}{\omega_{2}}},\zeta_{2}^{-1},(2{\sf
L})^{-\frac{1}{\varrho_{2}}}\\}$, then

$y_{K}\leqslant 2\left(\frac{{\sf L}^{2}\sigma^{2}}{\mu
N}\right)^{\frac{1}{2\theta}}\left[\frac{\alpha\log(K)}{K}\right]^{\omega_{2}}+y_{0}K^{-\zeta_{2}\alpha}.$
(41)

If we set $\alpha=\frac{2\omega_{2}}{\zeta_{2}}[1+\frac{\log(N)}{\log(K)}]$
and $K$ satisfies
${K}\geqslant({2\omega_{2}}\max\\{\frac{C_{3}}{\sqrt{N}},C_{4}N^{1-\frac{1}{2\theta}},1\\})\log(NK)$,
then we have

$y_{K}\leqslant
2\left(\frac{4\omega_{2}}{\theta}\right)^{\omega_{2}}\left(\frac{{\sf
L}\sigma}{\mu^{{3}/{2}}}\right)^{\omega_{2}}\left[\frac{\log(NK)}{\sqrt{N}K}\right]^{\omega_{2}}+y_{0}(NK)^{-2\omega_{2}}.$
(42)

The proof is deferred to Section D.2. To our knowledge, Theorem 18 is the
first non-asymptotic result under the general $(\theta,\mu)$-PL condition for
random shuffling (Algorithm 2) with constant step size. The existing
literature on ${\sf RR}$ with constant step size mainly assumes the
$(\frac{1}{2},\mu)$-PL condition (or even strong convexity); see, e.g.,
HaoChen and Sra (2019); Ahn et al. (2020); Mishchenko et al. ; Nguyen et al.
(2021). For instance, the work (Nguyen et al., 2021, Theorem 1) obtains the
complexity bound $\mathcal{O}(\frac{{\sf
L}^{2}\sigma^{2}}{\mu^{3}}\frac{\log^{2}(NK)}{NK^{2}}+y_{0}\frac{1}{NK^{2}})$
under strong convexity, which matches our result for $\theta=\frac{1}{2}$.

####  3.4.2 Results on Polynomial Step Sizes.

We now study the convergence of ${\sf SGD}$ and ${\sf RR}$ under the general
$(\theta,\mu)$-PL condition when utilizing polynomial step sizes. We first
proceed with a technical lemma to provide the convergence analysis for
sequences $\\{y_{k}\\}_{k}$ that follow the key algorithmic recursion (17).

###### Lemma 19

Let $\\{y_{k}\\}_{k\geqslant 0}$ be a given sequence satisfying the following
recursion:

$y_{k+1}\leqslant(1+\ell_{1}\alpha_{k}^{\tau})y_{k}-\ell_{2}\alpha_{k}y_{k}^{2\theta}+\ell_{3}\alpha_{k}^{\tau},$
(43)

where $\ell_{1},\ell_{2},\ell_{3},p>0$, $\tau>1$, $\theta\in[\frac{1}{2},1]$
and $\alpha_{k}=\frac{\alpha}{(k+\gamma)^{p}}$, $\alpha,\gamma>0$. Let us set

$\varrho:=\frac{2\theta}{(2\theta-1)\tau+1},\;\;\zeta=\theta\ell_{2}^{\frac{1}{2\theta}}\ell_{3}^{\frac{2\theta-1}{2\theta}},\;\;\mathcal{u}_{1}=\frac{p(\tau-1)}{2\theta},\;\;\mathcal{u}_{2}=\frac{\tau-1}{(2\theta-1)\tau+1},\;\;\mathcal{u}_{3}=\frac{1-p}{2\theta-1}.$

The following statements hold:

  1. (a)

If $p\in(0,\varrho)$ and
$\gamma\geqslant\max\\{(\frac{\ell_{1}}{\zeta})^{\frac{1}{\mathcal{u}_{1}}}\alpha^{\frac{1}{p}},\zeta^{\frac{\varrho}{p}}\alpha^{\frac{1}{p}},(\frac{2\mathcal{u}_{1}}{\zeta\alpha^{{1}/{\varrho}}})^{\frac{1}{1-{p}/{\varrho}}}\\}$,
then we have

$y_{k+1}\leqslant
4\left(\frac{\ell_{3}}{\ell_{2}}\right)^{\frac{1}{2\theta}}\alpha^{\frac{\tau-1}{2\theta}}(k+1+\gamma)^{-\mathcal{u}_{1}}+y_{0}\exp\left(-\frac{\alpha^{{1}/{\varrho}}\zeta(k+1)}{(k+1+\gamma)^{p/\varrho}}\right).$

  2. (b)

If $p=\varrho$ and
$\alpha\geqslant(\frac{2\mathcal{u}_{2}}{\zeta})^{\varrho}$,
$\gamma\geqslant\max\\{(\frac{\ell_{1}}{\zeta})^{\frac{1}{\mathcal{u}_{2}}}\alpha^{\frac{1}{\varrho}},\zeta\alpha^{\frac{1}{\varrho}}\\}$,
then it holds that

$y_{k+1}\leqslant
4\left(\frac{\ell_{3}}{\ell_{2}}\right)^{\frac{1}{2\theta}}\alpha^{\frac{\tau-1}{2\theta}}(k+1+\gamma)^{-\mathcal{u}_{2}}+y_{0}\left(\gamma^{-1}(k+1+\gamma)\right)^{-\zeta\alpha^{{1}/{\varrho}}}.$

  3. (c)

If $\theta\in(\frac{1}{2},1]$, $p\in(\varrho,1)$,
$\alpha\geqslant\frac{2\mathcal{u}_{3}}{\theta\ell_{2}}$, and
$\gamma\geqslant\max\\{(\frac{\alpha^{\tau-1}\ell_{1}}{\theta\ell_{2}})^{\frac{1}{\tau
p-1}},(\frac{\alpha^{\tau-1}\ell_{3}}{\ell_{2}})^{\frac{1}{\tau
p-\mathcal{u}_{3}-1}},\alpha\theta\ell_{2}\\}$, then:

$y_{k+1}\leqslant
4(k+1+\gamma)^{-\mathcal{u}_{3}}+y_{0}\left(\gamma^{-1}(k+1+\gamma)\right)^{-\theta\ell_{2}\alpha}.$

  4. (d)

Suppose $\theta\in(\frac{1}{2},1]$, $p=1$. Then, for every
$\alpha\geqslant\frac{2}{\theta(2\theta-1)\ell_{2}}$, there is $\gamma_{0}>0$,
which only depends on $\alpha,\ell_{1},\ell_{2},\ell_{3},\tau$, such that for
all $\gamma\geqslant\gamma_{0}$, we have

$y_{k+1}\leqslant
4\log(k+1+\gamma)^{-\frac{1}{2\theta-1}}+y_{0}\left(\frac{\log(k+1+\gamma)}{\log(\gamma)}\right)^{-\alpha\theta\ell_{2}}.$

The proof mainly follows the roadmap in Section 3.2, but requires certain
refinements. We provide a detailed discussion in Section E.1.

######  Theorem 20 (Convergence Rate for ${\sf SGD}$ with Polynomial Step
Sizes)

Suppose (A.1)–(A.2) and (P) hold. Let the sequence
$\\{\bm{x}^{k}\\}_{0\leqslant k\leqslant K}$ be generated by ${\sf SGD}$ with
$\alpha_{k}=\frac{\alpha}{(k+\gamma)^{\varrho_{1}}}$. Then for any
$\alpha\geqslant(\frac{2\omega_{1}}{\zeta_{1}})^{\varrho_{1}}$,
$\gamma\geqslant\max\\{(\frac{{\sf A}{\sf
L}}{2\zeta_{1}})^{\frac{1}{\omega_{1}}}\alpha^{\frac{1}{\varrho_{1}}},\zeta_{1}\alpha^{\frac{1}{\varrho_{1}}},({\sf
L}\alpha)^{\frac{1}{\varrho_{1}}}\\}$, we have

$y_{K}\leqslant 4\left(\frac{{\sf
L}\sigma^{2}}{2\mu}\right)^{\frac{1}{2\theta}}\alpha^{\frac{1}{2\theta}}(K+\gamma)^{-\omega_{1}}+y_{0}\left[\gamma^{-1}(K+\gamma)\right]^{-\zeta_{1}\alpha^{\frac{1}{\varrho_{1}}}}.$
(44)

If we set $\alpha=(\frac{2\omega_{1}}{\zeta_{1}})^{\varrho_{1}}$ and
$\gamma=2\omega_{1}\max\\{C_{1},C_{2},1\\}$, then

$y_{K}\leqslant
4\left(\frac{\omega_{1}}{\theta}\right)^{\omega_{1}}\left(\frac{{\sf
L}\sigma^{2}}{\mu^{2}}\right)^{\omega_{1}}(K+\gamma)^{-\omega_{1}}+y_{0}\left[\frac{2\omega_{1}\max\\{C_{1},C_{2},1\\}}{K+\gamma}\right]^{2\omega_{1}}.$
(45)

The proof is presented in Appendix E. For simplicity, Theorem 20 exclusively
addresses the convergence concerning the optimal polynomial step sizes.
However, it is apparent that the convergence for any polynomial step sizes
$\frac{\alpha}{(k+\gamma)^{p}}$ with $p\in(0,1]$ can be directly inferred from
Lemma 19. In (Fontaine et al., 2021, Theorem 12), the authors studied
polynomial step sizes $\frac{\alpha}{(k+\gamma)^{p}}$ with $p\in(0,1)$ under a
PL-type condition and a bounded variance condition. By setting $\ell_{1}=0$,
$\ell_{2}=\mu$, and $\ell_{3}=\frac{{\sf L}\sigma^{2}}{2}$ in Lemma 19, we can
reproduce their findings. Furthermore, Lemma 19 allows us to cover the case
$p=1$ and $\theta\neq\frac{1}{2}$; this scenario, not addressed in (Fontaine
et al., 2021, Theorem 12), leads to a rate of
$\mathcal{O}((\log(K+\gamma))^{-\frac{1}{2\theta-1}})$ for ${\sf SGD}$. In
(Fatkhullin et al., 2022, Corollary 1), the convergence rate of ${\sf SGD}$ is
studied under the same $(\theta,\mu)$-PL conditions, along with a more general
assumption on the variance of the stochastic gradients, but only for the
optimal polynomial step sizes. Theorem 20 can recover the most typical cases,
i.e., for $h(t)=t,b_{k}=1$ in (Fatkhullin et al., 2022, Assumption 4), or
equivalently, setting $\beta=1$ and $\tau=0$ in (Fatkhullin et al., 2022,
Corollary 1).

We can also derive some other interesting non-asymptotic results for specific
$\theta$ in Theorem 20. If $\theta=\frac{1}{2}$, we can obtain the rate
$\mathcal{O}(\frac{{\sf L}\sigma^{2}}{\mu^{2}K}+y_{0}[\frac{{\sf A}{\sf
L}}{\mu^{2}K}]^{2})$. This result matches exactly that of (Gower et al., 2021,
Theorem 4.8). For the case when $\theta=1$ and $p\in[\frac{1}{2},1]$, the
convergence rate resulting in Lemma 19 matches the results for the convex
functions class contained in (Moulines and Bach, 2011, Theorem 4).

######  Theorem 21 (Convergence Rate for ${\sf RR}$ with Polynomial Step
Sizes)

Suppose (B.1)–(B.3) and (P) hold. Let the sequence
$\\{\bm{x}^{k}\\}_{0\leqslant k\leqslant K}$ be generated by ${\sf RR}$ with
$\alpha_{k}=\frac{\alpha}{(k+\gamma)^{\varrho_{2}}}$. Then for any
$\gamma\geqslant\max\\{(\frac{{\sf A}{\sf
L}^{2}}{2N\zeta_{2}})^{\frac{1}{\omega_{2}}}\alpha^{\frac{1}{\varrho_{2}}},\zeta_{2}\alpha^{\frac{1}{\varrho_{2}}},(2{\sf
L}\alpha)^{\frac{1}{\varrho_{2}}}\\}$, and
$\alpha\geqslant(\frac{2\omega_{2}}{\zeta_{2}})^{\varrho_{2}}$, we obtain

$y_{K}\leqslant 4\left(\frac{{\sf L}^{2}\sigma^{2}}{\mu
N}\right)^{\frac{1}{2\theta}}\alpha^{\frac{1}{\theta}}(K+\gamma)^{-\omega_{2}}+y_{0}\left[\gamma^{-1}(K+\gamma)\right]^{-\zeta_{2}\alpha^{\frac{1}{\varrho_{2}}}}.$
(46)

Moreover, if
$\alpha=[\frac{2\omega_{2}(1+\log(N))}{\zeta_{2}}]^{\varrho_{2}}$,
$\gamma=2\omega_{2}(1+\log(N))\max\\{\frac{C_{3}}{\sqrt{N}},C_{4}N^{1-\frac{1}{2\theta}},1\\}$
and $K\geqslant 2\gamma$, then

$y_{K}\leqslant
4\Big{(}\frac{4\omega_{2}}{\theta}\Big{)}^{\omega_{2}}\Big{(}\frac{{\sf
L}\sigma}{\mu^{{3}/{2}}}\Big{)}^{\omega_{2}}\Big{[}\frac{1+\log(N)}{\sqrt{N}(K+\gamma)}\Big{]}^{\omega_{2}}+y_{0}\Big{[}{\frac{2\omega_{2}(1+\log(N))\max\\{\frac{C_{3}}{\sqrt{N}},C_{4}N^{1-\frac{1}{2\theta}},1\\}}{N(K+\gamma)}}\Big{]}^{2\omega_{2}}.$
(47)

To the best of our knowledge, Theorem 21 is the first non-asymptotic result
for ${\sf RR}$ under the general $(\theta,\mu)$-PL condition with polynomial
step sizes.

Figure 1: 2D Heatmap of convergence rate with respect to $p,\theta$; left:
${\sf SGD}$, right: ${\sf RR}$

The Dependence of Convergence Rate on $p$ and $\theta$. From Lemma 19, it is
evident that the convergence rate of polynomial step sizes depends
significantly on the values of $p$ and $\theta$. When $\theta=\frac{1}{2}$,
the upper bounds for ${\sf SGD}$ and ${\sf RR}$ are
$\mathcal{O}(K^{-\frac{p}{2\theta}})$ and
$\mathcal{O}(K^{-\frac{p}{\theta}})$, respectively. For
$\theta\in({1}/{2},1]$, when $p=1$, both ${\sf SGD}$ and ${\sf RR}$ share a
common upper bound of $\mathcal{O}((\log(K+\gamma))^{-\frac{1}{2\theta-1}})$.
In the case where $\theta\in(1/2,1]$ and $p\in(0,1)$, ${\sf SGD}$ converges
with an upper bound of $\mathcal{O}(K^{-\mathcal{w}_{1}(p,\theta)})$, while
${\sf RR}$ exhibits a convergence rate of the form
$\mathcal{O}(K^{-\mathcal{w}_{2}(p,\theta)})$, where
$\mathcal{w}_{1}(p,\theta)$ and $\mathcal{w}_{2}(p,\theta)$ are defined as
follows:

$\mathcal{w}_{1}(p,\theta)=\begin{cases}\frac{p}{2\theta},\leavevmode\nobreak\
\leavevmode\nobreak\ &\text{if $p\in(0,\varrho_{1}]$,}\\\
\frac{1-p}{2\theta-1},\leavevmode\nobreak\ \leavevmode\nobreak\ &\text{if
$p\in(\varrho_{1},1)$,}\end{cases}\quad\mathcal{w}_{2}(p,\theta)=\begin{cases}\frac{p}{\theta},\leavevmode\nobreak\
\leavevmode\nobreak\ &\text{if $p\in(0,\varrho_{2}]$,}\\\
\frac{1-p}{2\theta-1},\leavevmode\nobreak\ \leavevmode\nobreak\ &\text{if
$p\in(\varrho_{2},1)$.}\end{cases}$

A visualization of the rate mappings $\mathcal{w}_{1}$ and $\mathcal{w}_{2}$
is provided in Figure 1. Notably, the full characterization of the rate over
all instances of $p\in(0,1]$ and $\theta\in[\frac{1}{2},1]$ for ${\sf RR}$
seems new.

###  3.5 Exponential Step Sizes Adapt to the Geometry of Objective Functions

The convergence rates of ${\sf SGD}$ or ${\sf RR}$ employing constant,
polynomial, and cosine step size rules rely significantly on the choice of
parameters. Achieving the optimal convergence rate necessitates a careful
selection of these parameters in consideration of $\theta$. In the case of a
constant step size, $\alpha_{k}=[\frac{\alpha\log(K)}{K}]^{p}$, and a
polynomial step size, $\alpha_{k}=\frac{\alpha}{(k+\gamma)^{p}}$, optimal
performance is attained when $p=\varrho=\frac{2\theta}{(2\theta-1)\tau+1}$.
Similarly, for a cosine step size,
$\alpha_{k}=\alpha[\frac{1+\cos(\frac{k\pi}{K})}{2}]^{\beta}$, the optimal
rate is achieved when $\alpha\sim(\frac{\log(K)}{K})^{\varrho}$. Intriguingly,
the exponential step sizes rule,
$\alpha_{k}=\alpha(\frac{\beta}{K})^{\frac{pk}{K}}$, exhibits insensitivity to
the parameters $\alpha$, $\beta$, and $p$, consistently matching the optimal
convergence rate of other step size rules for any $\theta\in[\frac{1}{2},1]$
(up to a logarithmic term).

We conduct a numerical simulation to visually demonstrate this property. The
simulation involves the following recursion, representing the worst-case
scenario of equation (17) with $\ell_{1}=\ell_{2}=\ell_{3}=1$, $\tau=2$:

$y_{k+1}=(1+\alpha_{k}^{2})y_{k}-\alpha_{k}y_{k}^{2\theta}+\alpha_{k}^{2},\quad
k\in[K].$

We calculate $y_{K}$ using polynomial step sizes
$\alpha_{k}=\frac{\alpha}{(k+\gamma)^{p}}$ with
$p=1,\frac{4}{5},\frac{2}{3},\frac{1}{2}$, and an exponential step size
$\alpha_{k}=\alpha(\frac{1}{K})^{\frac{k}{K}}$, for
$\theta=\frac{1}{2},\frac{2}{3},1$, considering various total numbers of
iterations $K$. In Figure 2, the relationship between $\log_{2}(y_{K})$ and
$\log_{2}(K)$ is depicted for large $K$. The slope of each line represents the
sublinear convergence rate corresponding to each step size rule, where a
steeper slope indicates a faster sublinear convergence rate. Two important
facts are illustrated in this figure:

  * •

Polynomial step sizes achieve the optimal rate with different values of $p$
for different $\theta$. The optimal choice in our simulation is
$p=1,\frac{4}{5},\frac{2}{3}$ for $\theta=\frac{1}{2},\frac{2}{3},1$
respectively, which matches the optimal choice
$p=\varrho_{1}=\frac{2\theta}{4\theta-1}$ in Lemma 19.

  * •

For different values of $\theta$, exponential step sizes automatically attain
the optimal rate that can be achieved by the polynomial step size with optimal
$p$.

Figure 2: The relation between $\log_{2}(y_{K})$ and $\log_{2}(K)$ for
different $\theta$ with polynomial and exponential step sizes. A steeper slope
corresponds to a faster sublinear rate.

##  4 Conclusion

In this work, we propose a generalized version of Chung’s lemma, which can
serve as a simple yet powerful tool to obtain non-asymptotic convergence
results for sequences $\\{a_{k}\\}_{k}$ following the recursion

$a_{k+1}\leqslant\Big{(}1-\frac{1}{s(b_{k})}\Big{)}a_{k}+\frac{1}{t(b_{k})},$

where $s(b_{k})$ and $t(b_{k})$ are general terms controlling and capturing
the growth behavior of $\\{a_{k}\\}_{k}$. In the special setting
$s(b_{k})=\mathcal{O}(k^{p})$ and $t(b_{k})=\mathcal{O}(k^{p+q})$, the
classical Chung’s lemma is applicable yielding
$a_{k}=\mathcal{O}(k^{p}/k^{p+q})=\mathcal{O}(k^{-q})$. Our results expand
upon this classical case by providing mild and verifiable conditions on
$s(b_{k})$ and $t(b_{k})$ to ensure
$a_{k}=\mathcal{O}({s(b_{k})}/{t(b_{k})})$. We illustrate the broad
applicability of the generalized version of Chung’s lemma by developing a
unified framework for the convergence analysis of stochastic algorithms under
the $(\theta,\mu)$-PL condition and utilizing various step size rules and
sampling schemes.

Our generalized Chung’s lemma plays an important role in two aspects: (a) it
guides the construction of the auxiliary sequence $\\{u_{k}\\}_{k}$ when
addressing general $(\theta,\mu)$-PL conditions, as illustrated in Step 2 of
our roadmap detailed in Section 3.2; (b) by combining the generalized Chung’s
lemma with the extension lemma (refer to Lemma 5), we provide a unified
analysis path for exponential and cosine step size rules, which is summarized
as a splitting technique in Section 3.3. Intriguingly, we observe that
exponential step sizes can adapt to the geometry of the objective function
(determined by the PL parameters $(\theta,\mu)$). More specifically,
exponential step sizes can automatically achieve an optimal convergence rate
without explicitly knowing the PL exponent $\theta$ in the $(\theta,\mu)$-PL
condition. Further investigation of this geometric feature is left as a future
research direction.

Acknowledgments and Disclosure of Funding

Xiao Li was partly supported by the National Natural Science Foundation of
China under grant No. 12201534 and by the Shenzhen Science and Technology
Program under Grant No. RCYX20221008093033010. Andre Milzarek was partly
supported by the National Natural Science Foundation of China under grant No.
12150410304, by the Shenzhen Science and Technology Program under grant No.
RCYX20210609103124047 and RCYX20221008093033010, and by the Guangdong
Provincial Key Laboratory of Mathematical Foundations for Artificial
Intelligence (2023B1212010001).

##

##  Appendix A Preparatory Tools

In this first section, we list several well-known mathematical facts and tools
that will be used repeatedly in the later analysis.

######  Proposition 22 (Integral Test)

Let $I=[\iota,\infty)$, $\iota\in\mathbb{R}$, be a given interval and let
$f:I\to\mathbb{R}$ be continuous and non-increasing. Then, for all
$a,b\in\mathbb{N}\cap I$ with $a\leq b$, we have

$\int_{a}^{b+1}f(x)\,\mathrm{d}x\leq\sum_{k=a}^{b}f(k)\leq
f(a)+\int_{a}^{b}f(x)\,\mathrm{d}x.$

##  Appendix B Non-asymptotic Extension of Classic Chung’s Lemma

Classic Chung’s lemma focuses on the sequence
$\\{a_{k}\\}_{k}\subseteq\mathbb{R}_{++}$ satisfying the following recursion:

$a_{k+1}\leqslant\left(1-\frac{c}{(k+\gamma)^{p}}\right)a_{k}+\frac{d}{(k+\gamma)^{p+q}},\quad
p\in(0,1],\leavevmode\nobreak\ q>0,\leavevmode\nobreak\
c,d>0,\leavevmode\nobreak\ \gamma\geqslant c^{\frac{1}{p}}.$ (48)

In Chung (1954), Chung proposed several lemmas to obtain asymptotic estimates
for $a_{k}$, which are summarized as follows:

###### Lemma 23

[Asymptotic Chung’s Lemma Chung (1954); Polyak (1987)] Let the sequence
$\\{a_{k}\\}_{k}\subseteq\mathbb{R}_{++}$ be given as in (48). Then, the
following statements hold:

  1. (a)

When $p\in(0,1)$, we have $a_{k}=\mathcal{O}(k^{-q})$.

  2. (b)

When $p=1$, if $c=q$ we have $a_{k}=\mathcal{O}(k^{-q}\log(k))$; otherwise,
$a_{k}=\mathcal{O}(k^{-\min\\{c,q\\}})$.

There already have been several extensions to non-asymptotic versions of
certain subcases of Lemma 23 in previous literature, see Moulines and Bach
(2011); Ahn et al. (2020); Nguyen et al. (2021). In this paper, we utilize
Theorem 1 to derive a complete non-asymptotic extension of the classic Chung’s
lemma, which encompasses the previous extensions.

######  Theorem 24 (Non-asymptotic Chung’s Lemma)

Let the sequence $\\{a_{k}\\}_{k}\subseteq\mathbb{R}_{++}$ be given and
satisfy (48). Then, the following statements hold:

  1. (a)

If $p\in(0,1)$, $\gamma\geqslant c^{\frac{1}{p}}$ and
$\gamma>(\frac{q}{c})^{\frac{1}{1-p}}$, then

$\displaystyle a_{k+1}\leqslant\frac{\lambda
d}{c}(k+1+\gamma)^{-q}+\left(a_{0}-\frac{\lambda
d}{c\gamma^{q}}\right)^{+}\exp\left(\frac{c\gamma^{1-p}}{1-p}\right)\exp\left[-\frac{c(k+1+\gamma)^{1-p}}{1-p}\right],$

holds for all $k\in[K]$, where $\lambda=\frac{c\gamma^{1-p}}{c\gamma^{1-p}-q}$
and $(x)^{+}:=\max\\{x,0\\}$. Additionally, if we further assume
$\gamma\geqslant[\frac{(1+\varsigma)q}{c}]^{\frac{1}{1-p}}$ for some
$\varsigma>0$, then

$a_{k+1}\leqslant\frac{(1+\varsigma)d}{\varsigma
c}(k+1+\gamma)^{-q}+\left(a_{0}-\frac{\lambda
d}{c\gamma^{q}}\right)^{+}\exp\left[-\frac{c(k+1)}{(k+1+\gamma)^{p}}\right],$

holds for all $k\in[K]$.

  2. (b)

If $p=1$, then

$a_{k+1}\leqslant\begin{cases}\frac{d}{c-q}(k+1+\gamma)^{-q}+\gamma^{c}\left(a_{0}-\frac{d}{(c-q)\gamma^{q}}\right)^{+}(k+1+\gamma)^{-c},\hskip
39.83368pt&\text{for $c>q$, $\gamma\geqslant c$},\\\\[8.53581pt]
\left[\frac{d}{\gamma-c}+d\log(\frac{k+\gamma-c}{\gamma-c})+a_{0}\gamma^{c}\right](k+1+\gamma)^{-c},\hskip
79.6678pt&\text{for $c=q$, $\gamma>c$},\\\\[8.53581pt]
\left[\frac{d}{(q-c)(\gamma-q-1)^{q-c}}+a_{0}\gamma^{c}\right](k+\gamma+1)^{-c}-\frac{d}{q-c}(k+\gamma+1)^{-q},\hskip
14.22636pt&\text{for $c<q$, $\gamma>q+1$}.\end{cases}$

Proof  We now apply our main theorem (Theorem 1) to prove the non-asymptotic
version of the classical Chung’s lemma. To make use of Theorem 1, we first
specify the following sequences and functions:

$b_{k}:=k+\gamma,\quad s(x):=\frac{x^{p}}{c},\quad\text{and}\quad
t(x):=\frac{x^{p+q}}{d}.$

We now only need to check whether the conditions in Theorem 1 are fulfilled in
this setting. Let us notice that the rate mapping
$r(x):=s(x)/t(x)=\frac{d}{c}x^{-q}$ is convex on $\mathbb{R}_{++}$. In
addition, it holds that

$u(x):=s^{\prime}(x)-r(x)t^{\prime}(x)=\frac{p}{c}x^{p-1}-\frac{d}{c}x^{-q}\cdot\frac{p+q}{d}x^{p+q-1}=-\frac{q}{c}x^{p-1}.$

and $s(x)\geqslant 1$ for all $x\geqslant c^{\frac{1}{p}}$. Per assumption, we
have $\gamma\geqslant c^{\frac{1}{p}}$ which implies $b_{k}\in
I:=[c^{\frac{1}{p}},\infty)\subseteq\mathbb{R}_{++}$ for all $k\in[K]$. Hence,
we only need to verify the condition (7) or (8) in Theorem 1. To that end and
using $b_{k+1}-b_{k}=1$, we need to find a sequence
$\\{\lambda_{k}\\}_{k}\subseteq\mathbb{R}_{+}$ such that

$\lambda_{k+1}\left[\frac{(k+\gamma)^{p}}{c}-\frac{q(k+\gamma)^{p-1}}{c}\right]\geqslant\lambda_{k}\left[\frac{(k+\gamma)^{p}}{c}-1\right]+1,\quad\forall\;k\in[K]$
(49)

or a non-decreasing sequence $\\{\lambda_{k}\\}_{k}\subseteq\mathbb{R}_{+}$
such that

$-\frac{q}{c}(k+\gamma)^{p-1}\geqslant-1+\frac{1}{\lambda_{k+1}},\quad\forall\;k\in[K].$
(50)

Based on the parameter $p\in(0,1]$, we now discuss different cases.

Case I: $p\in(0,1)$. This has already been shown in Lemma 4 (a). Furthermore,
if we additionally have
$\gamma\geqslant[\frac{(1+\varsigma)q}{c}]^{\frac{1}{1-p}}$ for some
$\varsigma>0$, then it follows $\gamma^{1-p}\geqslant\frac{(1+\varsigma)q}{c}$
and
$\lambda=\frac{c\gamma^{1-p}}{c\gamma^{1-p}-q}\leqslant\frac{1+\varsigma}{\varsigma}$.
Using the concavity of the mapping $x\mapsto x^{1-p}$, it holds that

$(k+1+\gamma)^{1-p}-\gamma^{1-p}\geqslant\frac{1-p}{(k+1+\gamma)^{p}}[(k+1+\gamma)-\gamma]=(1-p)\frac{k+1}{(k+1+\gamma)^{p}}.$

Combining these last estimate, we obtain

$a_{k+1}\leqslant\frac{(1+\varsigma)d}{\varsigma
c}(k+1+\gamma)^{-q}+\left(a_{0}-\frac{\lambda
d}{c\gamma^{q}}\right)^{+}\exp\left(-\frac{c(k+1)}{(k+1+\gamma)^{p}}\right).$

Case II: $p=1$. Since the analysis technique depends on the relation between
the constants $t$ and $c$, we will split the following discussion into three
sub-cases.

Sub-Case 2-1: $c>q$ and $\gamma\geqslant c$. This has already been shown in
Lemma 4 (b).

Sub-Case 2-2: $c=q$ and $\gamma>c$. In this case, we can no longer ensure
existence of a sequence $\\{\lambda_{k}\\}_{k}\subseteq\mathbb{R}_{+}$
satisfying the (simpler) condition (50). To that end, we want to find
$\\{\lambda_{k}\\}_{k}\subseteq\mathbb{R}_{+}$ such that the (more general)
condition (49) is valid, i.e., the following inequality should hold

$\lambda_{k+1}\left[\frac{k+\gamma}{c}-1\right]\geqslant\lambda_{k}\left[\frac{k+\gamma}{c}-1\right]+1,\quad\forall\leavevmode\nobreak\
k\in[K].$

A feasible choice of $\\{\lambda_{k}\\}_{k}$ to guarantee the above condition
is $\lambda_{0}=0$ and $\lambda_{k+1}=\sum_{i=0}^{k}\frac{c}{i+\gamma-c}$ for
all $k\in[K]$. In fact, this choice satisfies

$\lambda_{k+1}\left[\frac{k+\gamma}{c}-1\right]=\left[\lambda_{k}+\frac{c}{k+\gamma-c}\right]\left[\frac{k+\gamma}{c}-1\right]=\lambda_{k}\left[\frac{k+\gamma}{c}-1\right]+1\quad\forall\leavevmode\nobreak\
k\in[K].$

Invoking the integral test, we further have
$\lambda_{k+1}\leqslant\frac{c}{\gamma-c}+c\int_{0}^{k}\frac{1}{x+\gamma-c}\,\mathrm{d}x=\frac{c}{\gamma-c}+c\,\log(\frac{k+\gamma-c}{\gamma-c}),$
for all $k\in[K]$. Hence, utilizing Theorem 1 (a) and this upper bound for
$\\{\lambda_{k}\\}_{k}$, we can conclude

$\displaystyle a_{k+1}\leqslant\leavevmode\nobreak\ $
$\displaystyle\lambda_{k+1}r(b_{k+1})+\left(a_{0}-\lambda_{0}r(b_{0})\right){\prod}_{i=0}^{k}\left(1-\frac{1}{s(b_{i})}\right)$
$\displaystyle\leqslant\leavevmode\nobreak\ $
$\displaystyle\left[\frac{d}{\gamma-c}+d\log\left(\frac{k+\gamma-c}{\gamma-c}\right)\right](k+1+\gamma)^{-c}+a_{0}\;{\prod}_{i=0}^{k}\left(1-\frac{c}{i+\gamma}\right)$
$\displaystyle\leqslant\leavevmode\nobreak\ $
$\displaystyle\left[\frac{d}{\gamma-c}+d\log\left(\frac{k+\gamma-c}{\gamma-c}\right)+\gamma^{c}a_{0}\right](k+1+\gamma)^{-c},$

where the last inequality follows again from the inequality
$1-x\leqslant\exp(-x)$ and the integral test (Proposition 22).

Sub-Case 2-3: $c<q$ and $\gamma>q+1$. Similar to Sub-Case 2-2, we need to find
a sequence $\\{\lambda_{k}\\}_{k}\subseteq\mathbb{R}_{+}$ such that the
condition (49) holds and to ensure applicability of Theorem 1 (a). We first
reformulate (49) as follows:

$\lambda_{k+1}\left[\frac{k+\gamma}{c}-\frac{q}{c}\right]\geqslant\lambda_{k}\left[\frac{k+\gamma}{c}-1\right]+1\quad\Longleftrightarrow\quad\lambda_{k+1}(k+\gamma-q)\geqslant\lambda_{k}(k+\gamma-c)+c.$

Defining $\lambda_{k}:=\zeta(k-1+\gamma-q)^{q-c}-\frac{c}{q-c}$ and
$\zeta:=\frac{c}{(q-c)(\gamma-q-1)^{q-c}}$, we then have

$\displaystyle\lambda_{k+1}(k+\gamma-q)\geqslant\lambda_{k}(k+\gamma-c)+c$
$\displaystyle\iff\quad\zeta(k+\gamma-q)^{q-c+1}\geqslant\lambda_{k}(k+\gamma-c)+c+\frac{c}{q-c}(k+\gamma-q)$
$\displaystyle\iff\quad\zeta(k+\gamma-q)^{q-c+1}\geqslant\zeta(k-1+\gamma-q)^{q-c}(k+\gamma-c)+\frac{c^{2}}{q-c}+c-\frac{cq}{q-c}$
$\displaystyle\iff\quad(k+\gamma-q)^{q-c+1}\geqslant(k-1+\gamma-q)^{q-c}(k+\gamma-c).$
(51)

Let us now verify (51). For any $x\geqslant 0,\eta>0$, by the mean value
theorem, there exists $\xi\in(0,1)$ such that
$(x+1)^{\eta}-x^{\eta}=\eta(x+\xi)^{\eta-1}\geqslant\frac{\eta
x^{\eta}}{x+1}$. Rearranging the terms in this inequality, it follows

$(x+1)^{\eta}-x^{\eta}\geq\frac{\eta
x^{\eta}}{x+1}\quad\Longleftrightarrow\quad(x+1)^{\eta+1}\geqslant
x^{\eta}(x+1+\eta).$

Choosing $\eta=q-c$ and $x=k-1+\gamma-q$ in the above estimate (and recalling
$\gamma>q+1$), this proves the condition (51). Finally, invoking Theorem 1 (a)
with such choice of $\\{\lambda_{k}\\}_{k}$, we obtain

$\displaystyle a_{k+1}$
$\displaystyle\leqslant\lambda_{k+1}r(b_{k+1})+(a_{0}-\lambda_{0}r(b_{0}))\,{\prod}_{i=0}^{k}\left(1-\frac{c}{i+\gamma}\right)$
$\displaystyle\leqslant\frac{\zeta
d}{c}(k+\gamma+1)^{-c}-\frac{d}{q-c}(k+\gamma+1)^{-q}+a_{0}\,{\prod}_{i=0}^{k}\left(1-\frac{c}{i+\gamma}\right)$
$\displaystyle\leqslant\left(\frac{c}{(q-c)(\gamma-q-1)^{q-c}}+a_{0}\gamma^{c}\right)(k+\gamma+1)^{-c}-\frac{d}{q-c}(k+\gamma+1)^{-q},$

where the second line holds owing to $(k+\gamma-q)\leq(k+\gamma+1)$ and
$\lambda_{0}=0$, and the last inequality utilizes the inequality
$1-x\leqslant\exp(-x)$ and the integral test (Proposition 22).

##  Appendix C Additional Derivations for Exponential and Cosine Step Sizes

We now study the convergence of ${\sf SGD}$ and ${\sf RR}$ under the general
$(\theta,\mu)$-PL condition when utilizing exponential, and cosine step size
schemes. We provide the details of the verification for Theorem 13 to 16 using
Lemma 12.

###  C.1 Exponential Step Sizes: Verifying Theorem 13 and 14

Proof of Theorem 13 By assumption, we have
$\alpha_{k}=\alpha\gamma^{k}\leqslant\alpha(\frac{1}{2})^{\frac{\varrho_{1}k}{K}}\leqslant\alpha\leqslant\frac{1}{{\sf
L}}$ for all $k\in[K]$. Hence, the descent property (15) is applicable for all
$k\in[K]$.

The remaining conditions on $\alpha$, $\beta$, and $K$ ensure that Lemma 12
(b) is applicable which establishes (30) by setting $\ell_{1}=\frac{{\sf
A}{\sf L}}{2}$, $\ell_{2}=\mu$, and $\ell_{3}=\frac{{\sf L}\sigma^{2}}{2}$ and
using

$\Big{(}\frac{2p\omega_{1}}{\varrho_{1}}\Big{)}^{\omega_{1}}\zeta^{-\omega_{1}}\left(\frac{\ell_{3}}{\ell_{2}}\right)^{\frac{1}{2\theta}}=\left(\frac{p}{\theta^{2}}\right)^{\omega_{1}}\mu^{-\frac{\omega_{1}+1}{2\theta}}\left(\frac{{\sf
L}\sigma^{2}}{2}\right)^{\frac{1-(2\theta-1)\omega_{1}}{2\theta}}=\left(\frac{p}{2\theta^{2}}\right)^{\omega_{1}}\mu^{-2\omega_{1}}({\sf
L}\sigma^{2})^{\omega_{1}},$

where the last equation is due to $\frac{\omega_{1}+1}{2\theta}=2\omega_{1}$
and $\frac{1-(2\theta-1)\omega_{1}}{2\theta}=\omega_{1}$.

Proof of Theorem 14 The inequality $\alpha\leqslant(2{\sf
L})^{-\frac{1}{\varrho_{2}}}$ ensures that $\alpha_{k}\leqslant\frac{1}{2{\sf
L}}$, which means that (16) is applicable. The first inequality (31) can be
obtained by applying Lemma 19 to (16) with $\ell_{1}=\frac{{\sf A}{\sf
L}^{2}}{2N}$, $\ell_{2}=\frac{\mu}{2}$, and $\ell_{3}=\frac{{\sf
L}^{2}\sigma^{2}}{2N}$. Furthermore, if we have
${K}\geqslant(\frac{4p}{\theta^{2}}\max\\{\frac{C_{3}}{\sqrt{N}},C_{4}N^{1-\frac{1}{2\theta}},1\\}){\log(\frac{K}{\beta})\log(NK)}$,
then

$y_{K}\leqslant
4\Big{(}\frac{4p}{\theta^{2}}\Big{)}^{\omega_{2}}\Big{(}\frac{{\sf
L}\sigma}{\mu^{{3}/{2}}}\Big{)}^{\omega_{2}}\left[\frac{\log(\frac{K}{\beta})}{\sqrt{N}K}\right]^{\omega_{2}}+y_{0}(NK)^{-\omega_{2}}.$

###  C.2 Cosine Step Sizes: Verifying Theorem 15 and 16

Proof of Theorem 15 The inequality $\alpha\leqslant{{\sf
L}}^{-\frac{1}{\varrho_{1}}}$ ensures that $\alpha_{k}\leqslant\frac{1}{{\sf
L}}$, which means that (15) is applicable. The first two inequalities (33) and
(34) can be obtained by applying Lemma 19 to (15) with $\ell_{1}=\frac{{\sf
A}{\sf L}}{2}$, $\ell_{2}=\mu$, $\ell_{3}=\frac{{\sf L}\sigma^{2}}{2}$, and
$\frac{\varrho_{1}}{\omega_{1}}=2\theta$. To establish (35), we substitute
$\alpha=2^{\max\\{\beta,\varrho_{1}\\}}(\frac{\omega_{1}\log(K)}{\zeta_{1}K})^{\varrho_{1}}$
into (33) and (34). To make sure that (33) and (34) available, we need to
guarantee that $\alpha\leqslant\min\\{(\frac{2\zeta_{1}}{{\sf A}{\sf
L}})^{2\theta},\zeta_{1}^{-\varrho_{1}},{\sf L}^{-1}\\}$, i.e., ${K}\geqslant
2^{\max\\{2,1+\frac{\beta}{\varrho_{1}}\\}}\omega_{1}(\max\\{{C_{1}},C_{2},1\\}{\log(K)})$,
and $K\geqslant\frac{2\pi^{2}\beta}{\theta\alpha^{1/\varrho}\zeta_{1}}$, i.e.,
$K\geqslant\exp[\frac{\pi^{2}\beta}{2^{\max\\{1,{\beta}/{\varrho_{1}}\\}}\omega_{1}}]$.
We summarize these requirements on $K$ as
${K}\geqslant\Theta(\max\\{{C_{1}},C_{2},1\\}{\log(K)})$. Then,

$y_{K}\leqslant\mathcal{O}\Big{(}\alpha^{\frac{\omega_{1}}{\rho_{1}}-\frac{2\beta\omega_{1}/\varrho_{1}}{2\beta+\varrho_{1}}}\Big{[}\frac{1}{K}\Big{]}^{\frac{2\beta\omega_{1}}{2\beta+\varrho_{1}}}\Big{)}+\mathcal{O}(y_{0}K^{-2\omega_{1}})=\mathcal{O}\Big{(}\Big{[}\frac{(\log(K))^{\frac{\varrho_{1}}{2\beta+\varrho_{1}}}}{K}\Big{]}^{\omega_{1}}\Big{)}.$

Proof of Theorem 16 The inequality $\alpha\leqslant(2{\sf
L})^{-\frac{1}{\varrho_{2}}}$ ensures that $\alpha_{k}\leqslant\frac{1}{2{\sf
L}}$, which means that (16) is applicable. The first two inequalities (36) and
(37) can be obtained by applying Lemma 12 to (16) with $\ell_{1}=\frac{{\sf
A}{\sf L}^{2}}{2N}$, $\ell_{2}=\frac{\mu}{2}$, $\ell_{3}=\frac{{\sf
L}^{2}\sigma^{2}}{2N}$, and $\frac{\varrho_{2}}{\omega_{2}}=\theta$. To
establish (38), we substitute
$\alpha=2^{\max\\{\varrho_{2},\beta\\}}(\frac{2\omega_{2}\log(NK)}{\zeta_{2}K})^{\varrho_{2}}$
into (36) and (37). To make sure (36) and (37) available, we need to guarantee
that $\alpha\leqslant\min\\{(\frac{2N\zeta_{2}}{{\sf A}{\sf
L}^{2}})^{\theta},\zeta_{2}^{-\varrho_{2}},(2{\sf L})^{-1}\\}$, i.e.,

${K}\geqslant\Big{(}2^{\max\\{2,1+\frac{\beta}{\varrho_{2}}\\}}\cdot\omega_{2}\max\Big{\\{}\frac{C_{3}}{\sqrt{N}},C_{4}N^{1-\frac{1}{2\theta}},1\Big{\\}}\Big{)}\log(NK),$

and $K\geqslant\frac{4\pi^{2}\beta}{\theta\alpha^{1/\varrho}\zeta_{2}}$, i.e.,
$K\geqslant\exp(\frac{2\pi^{2}\beta}{2^{\max\\{1,{\beta}/{\varrho_{2}}\\}}\theta\omega_{2}\log(NK)})$.
We summarize these requirements for $K$ as
$K\geqslant\Theta(\max\\{\frac{C_{3}}{\sqrt{N}},C_{4}N^{1-\frac{1}{2\theta}},1\\}\log(NK))$.
Recall that $\zeta_{2}=\frac{\theta}{2}\mu^{\frac{1}{2\theta}}(\frac{{\sf
L}^{2}\sigma^{2}}{N})^{1-\frac{1}{2\theta}}$, then,

$\displaystyle y_{K}\leqslant$
$\displaystyle\mathcal{O}\Big{(}N^{-\frac{1}{2\theta}}\alpha^{\frac{\omega_{2}}{\rho_{2}}}\Big{[}\frac{1}{\alpha^{1/\varrho_{2}}\zeta_{2}}\Big{]}^{\frac{2\beta\omega_{2}}{2\beta+\varrho_{2}}}\Big{)}+\mathcal{O}(y_{0}(NK)^{-2\omega_{2}})$
$\displaystyle=$
$\displaystyle\mathcal{O}\Big{(}N^{-\frac{1}{2\theta}}\Big{[}\frac{\log(NK)}{\zeta_{2}K}\Big{]}^{{\omega_{2}}}\Big{[}\frac{1}{\log(NK)}\Big{]}^{\frac{2\beta\omega_{2}}{2\beta+\varrho_{2}}}\Big{)}+\mathcal{O}(y_{0}(NK)^{-2\omega_{2}})$
$\displaystyle=$
$\displaystyle\mathcal{O}\Big{(}N^{-\frac{1}{2\theta}-(1-\frac{1}{2\theta})\omega_{2}}\Big{[}\frac{\log(NK)^{\frac{\varrho_{2}}{2\beta+\varrho_{2}}}}{K}\Big{]}^{{\omega_{2}}}\Big{)}+\mathcal{O}(y_{0}(NK)^{-2\omega_{2}})$
$\displaystyle=$
$\displaystyle\mathcal{O}\Big{(}\Big{[}\frac{\log(NK)^{\frac{\varrho_{2}}{2\beta+\varrho_{2}}}}{\sqrt{N}K}\Big{]}^{{\omega_{2}}}\Big{)},$

where in the last step, we utilize
$\frac{1}{2\theta}+(1-\frac{1}{2\theta})\omega_{2}=\frac{\omega_{2}}{2}$.

##  Appendix D Derivations for Constant Step Size

We now study convergence of ${\sf SGD}$ and ${\sf RR}$ under the general
$(\theta,\mu)$-PL condition when utilizing constant step size schemes. We
first proceed with a technical lemma and apply Chung’s lemma to sequences
$\\{y_{k}\\}_{k}$ that follow the key algorithmic recursion

$y_{k+1}\leqslant(1+\ell_{1}\alpha_{k}^{\tau})y_{k}-\ell_{2}\alpha_{k}y_{k}^{2\theta}+\ell_{3}\alpha_{k}^{\tau}$

from equation (17). In subsection E.2, we then utilize the obtained results to
provide proofs for Theorem 20 and Theorem 21.

###  D.1 A Technical Lemma for Constant Step Size

###### Lemma 25

Consider a non-negative sequence $\\{y_{k}\\}_{0\leqslant k\leqslant K}$
satisfying the recursion

$y_{k+1}\leqslant(1+\ell_{1}\alpha_{k}^{\tau})y_{k}-\ell_{2}\alpha_{k}y_{k}^{2\theta}+\ell_{3}\alpha_{k}^{\tau}$
(52)

for all $k\in[K-1]$, where $\ell_{1},\ell_{2},\ell_{3}>0$, $K\in\mathbb{N}$
and $K\geqslant 1$. Let us define

$\varrho:=\frac{2\theta}{(2\theta-1)\tau+1},\quad\omega:=\frac{\tau-1}{(2\theta-1)\tau+1},\quad\zeta:=\theta\ell_{2}^{\frac{1}{2\theta}}\ell_{3}^{\frac{2\theta-1}{2\theta}}.$

Suppose $\alpha_{k}=[\frac{\alpha\log(K)}{K}]^{\varrho}$ where $\alpha>0$ and
$K$ satisfy
$\frac{\alpha\log(K)}{K}\leqslant\min\\{(\frac{\zeta}{\ell_{1}})^{\frac{1}{\omega}},\zeta^{-1}\\}$;
then:

$y_{K}\leqslant
2\left(\frac{\ell_{3}}{\ell_{2}}\right)^{\frac{1}{2\theta}}\left[\frac{\alpha\log(K)}{K}\right]^{\omega}+y_{0}K^{-\zeta\alpha}.$

Proof  Recall that the preceding analysis outlined in the roadmap in Section
3.2 is applicable provided that
$\alpha_{k}\leq\min\\{(\frac{\zeta}{\ell_{1}})^{\frac{\varrho}{\omega}},\zeta^{-\varrho}\\}$.
As stated in the assumptions, suppose that the step sizes
$\\{\alpha_{k}\\}_{k}$ satisfy
$\alpha_{k}=[\frac{\alpha\log(K)}{K}]^{\varrho}$ and we have
$\frac{\alpha\log(K)}{K}\leqslant\min\\{(\frac{\zeta}{\ell_{1}})^{\frac{1}{\omega}},\zeta^{-1}\\}$.
Let us set $b_{k}=k$ and $\eta(x)=[\frac{\alpha\log(K)}{K}]^{\varrho}$, where
$b_{k}$ and $\eta$ follow the same definition in Section 3.2. Then, the rate
function $r$ is obviously non-increasing and convex and it holds that

$(b_{k+1}-b_{k})u(b_{k})=0\quad\forall\leavevmode\nobreak\ k\in[K-1].$

Hence, Theorem 1 (b) is applicable to (22) with $\lambda_{k}\equiv 1$ and we
obtain

$\displaystyle y_{K}\leqslant\leavevmode\nobreak\ $ $\displaystyle
r(K)+\left(y_{0}-r(0)\right){\prod}_{i=0}^{K-1}\left(1-\frac{1}{s(i)}\right)$
$\displaystyle=\leavevmode\nobreak\ $ $\displaystyle
2\left(\frac{\ell_{3}}{\ell_{2}}\right)^{\frac{1}{2\theta}}\left[\frac{\alpha\log(K)}{K}\right]^{\omega}+y_{0}{\prod}_{k=0}^{K-1}\left(1-\zeta\frac{\alpha\log(K)}{K}\right)$
$\displaystyle\leqslant\leavevmode\nobreak\ $ $\displaystyle
2\left(\frac{\ell_{3}}{\ell_{2}}\right)^{\frac{1}{2\theta}}\left[\frac{\alpha\log(K)}{K}\right]^{\omega}+y_{0}\exp\left(-K\zeta\frac{\alpha\log(K)}{K}\right)$
$\displaystyle=\leavevmode\nobreak\ $ $\displaystyle
2\left(\frac{\ell_{3}}{\ell_{2}}\right)^{\frac{1}{2\theta}}\left[\frac{\alpha\log(K)}{K}\right]^{\omega}+y_{0}K^{-\zeta\alpha},$

where we utilized $1-x\leqslant\exp(-x)$.

###  D.2 Verifying Theorem 17 and 18

Proof of Theorem 17 The inequality $\frac{\alpha\log(K)}{K}\leqslant{{\sf
L}}^{-\frac{1}{\varrho_{1}}}$ ensures that $\alpha_{k}\leqslant\frac{1}{{\sf
L}}$, and thus, the descent property (15) for ${\sf SGD}$ is valid. The rate
in (39) can be obtained by applying Lemma 19 in (15) with $\ell_{1}=\frac{{\sf
A}{\sf L}}{2}$, $\ell_{2}=\mu$, and $\ell_{3}=\frac{{\sf L}\sigma^{2}}{2}$. To
show (40), we substitute $\alpha=\frac{2\omega_{1}}{\zeta_{1}}$ into (39).
Then, we have

$\displaystyle y_{K}$ $\displaystyle\leqslant
2\Big{(}\frac{\ell_{3}}{\ell_{2}}\Big{)}^{\frac{1}{2\theta}}\Big{(}\frac{2\omega_{1}}{\zeta}\Big{)}^{\omega_{1}}\Big{[}\frac{\log(K)}{K}\Big{]}^{\omega_{1}}+\frac{y_{0}}{K^{2\omega_{1}}}=2\Big{(}\frac{\omega_{1}}{\theta}\Big{)}^{\omega_{1}}\Big{(}\frac{{\sf
L}\sigma^{2}}{\mu^{2}}\Big{)}^{\omega_{1}}\Big{[}\frac{\log(K)}{K}\Big{]}^{\omega_{1}}+\frac{y_{0}}{K^{2\omega_{1}}},$

when
$\frac{\log(K)}{K}\leqslant\frac{\zeta_{1}}{2\omega_{1}}\min\\{(\frac{2\zeta_{1}}{{\sf
A}{\sf L}})^{\frac{1}{\omega_{1}}},\zeta_{1}^{-1},{{\sf
L}}^{-\frac{1}{\varrho_{1}}}\\}$, i.e., for all
$K\geqslant({2\omega_{1}}\max\\{{C_{1}},C_{2},1\\})\log(K)$.

Proof of Theorem 18 The inequality $\frac{\alpha\log(K)}{K}\leqslant(2{\sf
L})^{-\frac{1}{\varrho_{2}}}$ ensures that $\alpha_{k}\leqslant\frac{1}{2{\sf
L}}$, which means that (16) is applicable. The first inequality (41) can be
obtained by applying Lemma 19 to (16) with $\ell_{1}=\frac{{\sf A}{\sf
L}^{2}}{2N}$, $\ell_{2}=\frac{\mu}{2}$, and $\ell_{3}=\frac{{\sf
L}^{2}\sigma^{2}}{2N}$. To establish (42), we substitute
$\alpha=\frac{2\omega_{2}}{\zeta_{2}}[1+\frac{\log(N)}{\log(K)}]$ into (41).
Then, we have

$\displaystyle y_{K}$ $\displaystyle\leqslant
2\Big{(}\frac{\ell_{3}}{\ell_{2}}\Big{)}^{\frac{1}{2\theta}}\Big{(}\frac{2\omega_{2}}{\zeta}\Big{)}^{\omega_{2}}\Big{[}\frac{\log(NK)}{K}\Big{]}^{\omega_{2}}+y_{0}K^{-2\omega_{2}(1+\frac{\log(N)}{\log(K)})}$
$\displaystyle=2\Big{(}\frac{4\omega_{2}}{\theta}\Big{)}^{\omega_{2}}\Big{(}\frac{{\sf
L}\sigma}{\mu^{{3}/{2}}}\Big{)}^{\omega_{2}}\Big{[}\frac{\log(NK)}{\sqrt{N}K}\Big{]}^{\omega_{2}}+y_{0}(NK)^{-2\omega_{2}},$

when $\frac{\alpha\log(K)}{K}\leqslant\min\\{(\frac{2N\zeta_{2}}{{\sf A}{\sf
L}^{2}})^{\frac{1}{\omega_{2}}},\zeta_{2}^{-1},(2{\sf
L})^{-\frac{1}{\varrho_{2}}}\\}$, which can be equivalently expressed as
${K}\geqslant({2\omega_{2}}\max\\{\frac{C_{3}}{\sqrt{N}},C_{4}N^{1-\frac{1}{2\theta}},1\\})\log(NK)$.

##  Appendix E Derivations for Polynomial Step Sizes

We now study the convergence of ${\sf SGD}$ and ${\sf RR}$ under the general
$(\theta,\mu)$-PL condition when utilizing polynomial step size schemes. We
first provide proof for the key technical lemma, i.e., Lemma 19. In subsection
E.2, we then utilize the obtained results to provide proofs for Theorem 20 and
Theorem 21.

###  E.1 Proof of Lemma 19

We will divide the proof into two core cases: $\theta=\frac{1}{2}$ and
$\theta\neq\frac{1}{2}$.

Case I: $\theta=\frac{1}{2}$. In this case, we have $\varrho=1$,
$\zeta=\frac{1}{2}\ell_{2}$, and $\mathcal{u}_{1}=p(\tau-1)$ and the recursion
(43) simplifies to

$y_{k+1}\leqslant[1+\ell_{1}\alpha_{k}^{\tau}-\ell_{2}\alpha_{k}]y_{k}+\ell_{3}\alpha_{k}^{\tau}.$
(53)

Sub-Case 1-1: $p\in(0,1)$. Using $\alpha_{k}=\frac{\alpha}{(k+\gamma)^{p}}$
and
$\gamma\geqslant(\frac{\ell_{1}}{\zeta})^{\frac{1}{\mathcal{u}_{1}}}\alpha^{\frac{1}{p}}=(\frac{2\ell_{1}}{\ell_{2}})^{\frac{1}{(\tau-1)p}}\alpha^{\frac{1}{p}}$,
(53) can be expressed as follows

$\displaystyle y_{k+1}$
$\displaystyle\leqslant\left[1+\frac{\ell_{1}\alpha^{\tau}}{(k+\gamma)^{\tau
p}}-\frac{\ell_{2}\alpha}{(k+\gamma)^{p}}\right]y_{k}+\frac{\alpha^{\tau}\ell_{3}}{(k+\gamma)^{\tau
p}}$
$\displaystyle=\left[1+\left(\frac{\ell_{1}\alpha^{\tau-1}}{\ell_{2}(k+\gamma)^{(\tau-1)p}}-1\right)\frac{\ell_{2}\alpha}{(k+\gamma)^{p}}\right]y_{k}+\frac{\alpha^{\tau}\ell_{3}}{(k+\gamma)^{\tau
p}}$
$\displaystyle\leqslant\left[1-\frac{\ell_{2}\alpha}{2(k+\gamma)^{p}}\right]y_{k}+\frac{\alpha^{\tau}\ell_{3}}{(k+\gamma)^{\tau
p}}.$ (54)

Noticing
$\gamma\geqslant\zeta^{\frac{\varrho}{p}}\alpha^{\frac{1}{p}}=(\frac{\ell_{2}\alpha}{2})^{\frac{1}{p}}$,
we can ensure $\frac{\ell_{2}\alpha/2}{(k+\gamma)^{p}}\leqslant 1$ for all
$k$. Invoking Theorem 24 (a) for (54) by setting $q=(\tau-1)p$,
$c=\frac{\ell_{2}\alpha}{2}$, $d=\ell_{3}\alpha^{\tau}$, and $\varsigma=1$, we
can infer

$y_{k+1}\leqslant\frac{4\ell_{3}}{\ell_{2}}\alpha^{\tau-1}(k+1+\gamma)^{-(\tau-1)p}+y_{0}\exp\left(-\frac{\alpha\ell_{2}(k+1)}{2(k+1+\gamma)^{p}}\right)$

provided that
$\gamma\geqslant[\frac{(1+\varsigma)q}{c}]^{\frac{1}{1-p}}=[\frac{4(\tau-1)p}{\alpha\ell_{2}}]^{\frac{1}{1-p}}=(\frac{2\mathcal{u}_{1}}{\zeta\alpha^{{1}/{\varrho}}})^{\frac{1}{1-{p}/{\varrho}}}$
(which holds by assumption).

Sub-Case 1-2: $p=1$. In this sub-case, we have $\mathcal{u}_{2}=\tau-1$ and
the recursion (43) reduces to

$y_{k+1}\leqslant\left[1+\frac{\ell_{1}\alpha^{\tau}}{(k+\gamma)^{\tau}}-\frac{\ell_{2}\alpha}{k+\gamma}\right]y_{k}+\frac{\alpha^{\tau}\ell_{3}}{(k+\gamma)^{\tau}}.$
(55)

As stated in the assumptions in part (b), let $\alpha$ and $\gamma$ be given
such that
$\alpha\geqslant(\frac{2\mathcal{u}_{2}}{\zeta})^{\varrho}=\frac{4(\tau-1)}{\ell_{2}}$
and
$\gamma\geqslant\max\\{(\frac{\ell_{1}}{\zeta})^{\frac{1}{\mathcal{u}_{2}}}\alpha^{\frac{1}{\varrho}},\zeta\alpha^{\frac{1}{\varrho}}\\}=\max\\{\alpha(\frac{2\ell_{1}}{\ell_{2}})^{\frac{1}{\tau-1}},\frac{\ell_{2}\alpha}{2}\\}$.
This implies

$\frac{\ell_{1}\alpha^{\tau}}{(k+\gamma)^{\tau}}-\frac{\ell_{2}\alpha}{k+\gamma}\leqslant\left(\frac{\ell_{1}\alpha^{\tau-1}}{\ell_{2}\gamma^{\tau-1}}-1\right)\frac{\ell_{2}\alpha}{k+\gamma}\leqslant-\frac{\ell_{2}\alpha}{2(k+\gamma)},\quad\frac{\ell_{2}\alpha}{2(k+\gamma)}\leqslant
1,$

and $\frac{\ell_{2}\alpha}{2}\geqslant 2(\tau-1)$ for all $k\geqslant 0$.
Then, (55) further simplifies to

$y_{k+1}\leqslant\left[1-\frac{\ell_{2}\alpha}{2(k+\gamma)}\right]y_{k}+\frac{\alpha^{\tau}\ell_{3}}{(k+\gamma)^{\tau}}.$

Applying Theorem 24 (b) (for the case $c>q$) with
$c=\frac{\ell_{2}\alpha}{2}$, $d=\alpha^{\tau}\ell_{3}$, $q=\tau-1$ and using
the inequality $c-q\geqslant\frac{c}{2}$, we have

$y_{k+1}\leqslant\frac{4\ell_{3}}{\ell_{2}}\alpha^{\tau-1}(k+1+\gamma)^{-(\tau-1)}+y_{0}\left(\gamma^{-1}(k+1+\gamma)\right)^{-\frac{\ell_{2}\alpha}{2}}.$

Case II: $\theta\neq\frac{1}{2}$. As a starting point, we consider the convex
function $x\mapsto h_{\theta}(x):=x^{2\theta}$. Then, applying the convexity
of $h_{\theta}$, it follows

$h_{\theta}(y)\geqslant h_{\theta}(x)+2\theta
x^{2\theta-1}(y-x)\quad\forall\leavevmode\nobreak\ x,y\geq 0.$ (56)

Introducing an auxiliary sequence $\\{u_{k}\\}_{k}$ (which we still need to
determine) and setting $y=y_{k}$ and $x=u_{k}$ in (56), we can relax (43) to

$\displaystyle y_{k+1}$
$\displaystyle\leqslant(1+\ell_{1}\alpha_{k}^{\tau})y_{k}-\ell_{2}\alpha_{k}h_{\theta}(y_{k})+\ell_{3}\alpha_{k}^{\tau}$
$\displaystyle\leqslant[1+\ell_{1}\alpha_{k}^{\tau}-2\theta\ell_{2}\alpha_{k}u_{k}^{2\theta-1}]y_{k}+[(2\theta-1)\ell_{2}u_{k}^{2\theta}\alpha_{k}+\ell_{3}\alpha_{k}^{\tau}].$
(57)

We will now discuss (57) and the explicit definition of $\\{u_{k}\\}_{k}$ in
several sub-cases depending on the choice of $p$.

Sub-Case 2-1: $p\in(0,1)$. We use the ansatz
$u_{k}=\nu(k+\gamma)^{-\mathcal{u}}$, where $\mathcal{u}$ and $\nu$ are to be
determined. Intuitively, the term $2\theta\ell_{2}\alpha_{k}u_{k}^{2\theta-1}$
should dominate $\ell_{1}\alpha_{k}^{\tau}$ and it should not decay faster
than $\frac{1}{k}$ (to ensure applicability of Theorem 24), i.e.,
$\mathcal{u}$ should be chosen such that

$\alpha_{k}u_{k}^{2\theta-1}\gtrsim\alpha_{k}^{\tau}\quad\text{and}\quad\alpha_{k}u_{k}^{2\theta-1}\gtrsim\frac{1}{k}.$
(58)

In terms of the exponents $\tau$, $s$, and $\theta$, (58) is equivalent to
$\mathcal{u}\leqslant\bar{\mathcal{u}}:=\min\\{\frac{p(\tau-1)}{2\theta-1},\frac{1-p}{2\theta-1}\\}$.
According to Theorem 24, the estimated convergence rate is
$O(k^{-\min\\{\mathcal{u},p(\tau-1)-(2\theta-1)\mathcal{u}\\}})$. Note that

$\min\\{\mathcal{u},p(\tau-1)-(2\theta-1)\mathcal{u}\\}=\begin{cases}\mathcal{u}&\text{if
}\mathcal{u}\leqslant\frac{p(\tau-1)}{2\theta},\\\
p(\tau-1)-(2\theta-1)\mathcal{u}&\text{if
}\mathcal{u}>\frac{p(\tau-1)}{2\theta},\end{cases}$

then,
$\min\\{\mathcal{u},p(\tau-1)-(2\theta-1)\mathcal{u}\\}\leqslant\frac{p(\tau-1)}{2\theta}$.
Moreover, due to
$\frac{p(\tau-1)}{2\theta}\leqslant\frac{p(\tau-1)}{2\theta-1}$, it holds that
$\frac{p(\tau-1)}{2\theta}\leq\bar{\mathcal{u}}$ if and only if
$s\leq\frac{2\theta}{(2\theta-1)\tau+1}=\varrho$. This shows that

$\operatorname*{argmax}_{\mathcal{u}\in(0,\bar{\mathcal{u}}]}\,\min\\{\mathcal{u},p(\tau-1)-(2\theta-1)\mathcal{u}\\}=\begin{cases}\frac{p(\tau-1)}{2\theta}&\text{if
}p\in(0,\varrho],\\\ \frac{1-p}{2\theta-1}&\text{if
}p\in(\varrho,1).\end{cases}$

Hence, depending on $p$ different optimal rates can be achieved and we
continue to split this case into additional sub-cases.

  * •

Case a): $p\in(0,\varrho)$. (The conditions in part (a) hold). We can set
$\mathcal{u}=\mathcal{u}_{1}:=\frac{p(\tau-1)}{2\theta}$ to obtain the optimal
rate. In this case, (57) can be expressed as

$y_{k+1}\leqslant\left[1+\frac{\ell_{1}\alpha^{\tau}}{(k+\gamma)^{\tau
p}}-\frac{2\theta\ell_{2}\nu^{2\theta-1}\alpha}{(k+\gamma)^{p/\varrho}}\right]y_{k}+\frac{(2\theta-1)\ell_{2}\nu^{2\theta}\alpha+\ell_{3}\alpha^{\tau}}{(k+\gamma)^{\tau
p}}.$

Assuming
$\gamma\geqslant(\frac{\ell_{1}\alpha^{\tau-1}}{\theta\ell_{2}\nu^{2\theta-1}})^{\frac{1}{\mathcal{u}_{1}}}$
and using $\tau
p-\frac{p}{\varrho}=\frac{p(\tau-1)}{2\theta}=\mathcal{u}_{1}$, this yields

$\displaystyle y_{k+1}$
$\displaystyle\leqslant\left[1+\left(\frac{\ell_{1}\alpha^{\tau-1}}{2\theta\ell_{2}\nu^{2\theta-1}(k+\gamma)^{\mathcal{u}_{1}}}-1\right)\frac{2\theta\ell_{2}\nu^{2\theta-1}\alpha}{(k+\gamma)^{p/\varrho}}\right]y_{k}+\frac{(2\theta-1)\ell_{2}\nu^{2\theta}\alpha+\ell_{3}\alpha^{\tau}}{(k+\gamma)^{\tau
p}}$
$\displaystyle\leqslant\left[1-\frac{\theta\ell_{2}\nu^{2\theta-1}\alpha}{(k+\gamma)^{p/\varrho}}\right]y_{k}+\frac{(2\theta-1)\ell_{2}\nu^{2\theta}\alpha+\ell_{3}\alpha^{\tau}}{(k+\gamma)^{\tau
p}}.$ (59)

To ensure
$\theta\ell_{2}\nu^{2\theta-1}\alpha(k+\gamma)^{-(p/\varrho)}\leqslant 1$ for
all $k\geqslant 0$, we further assume
$\gamma\geqslant(\alpha\theta\ell_{2}\nu^{2\theta-1})^{\frac{\varrho}{p}}$.
Noticing $p/\varrho<1$ and invoking Theorem 24 (a) for (59) with
$p\leftarrow\frac{p}{\varrho}$, $q=\mathcal{u}_{1}$,
$c=\theta\ell_{2}\nu^{2\theta-1}\alpha$,
$d=(2\theta-1)\ell_{2}\nu^{2\theta}\alpha+\ell_{3}\alpha^{\tau}$, and
requiring
$\gamma\geqslant[\frac{2\mathcal{u}_{1}}{\alpha\theta\ell_{2}\nu^{2\theta-1}}]^{\frac{1}{1-p/\varrho}}$,
we obtain

$y_{k+1}\leqslant\frac{2[(2\theta-1)\ell_{2}\nu^{2\theta}+\ell_{3}\alpha^{\tau-1}]}{\theta\ell_{2}\nu^{2\theta-1}}(k+1+\gamma)^{-\mathcal{u}_{1}}+y_{0}\exp\left(-\frac{\alpha\theta\ell_{2}\nu^{2\theta-1}(k+1)}{(k+1+\gamma)^{p/\varrho}}\right).$

We can choose
$\nu=(\frac{\ell_{3}\alpha^{\tau-1}}{\ell_{2}})^{\frac{1}{2\theta}}$ to make
the coefficient of the leading term to be optimal. Plugging this $\nu$ into
the different conditions on $\gamma$ and in the previous estimate, it follows

$\gamma\geqslant\max\left\\{(\tfrac{\ell_{1}}{\zeta})^{\frac{1}{\mathcal{u}_{1}}}\alpha^{\frac{1}{p}},\zeta^{\frac{\varrho}{p}}\alpha^{\frac{1}{p}},(\tfrac{2\mathcal{u}_{1}}{\alpha^{{1}/{\varrho}}\zeta})^{\frac{1}{1-p/\varrho}}\right\\}\quad\text{where}\quad\zeta=\theta\ell_{2}^{\frac{1}{2\theta}}\ell_{3}^{\frac{2\theta-1}{2\theta}},$
(60)

and

$y_{k+1}\leqslant
4(\tfrac{\ell_{3}}{\ell_{2}})^{\frac{1}{2\theta}}\alpha^{\frac{\tau-1}{2\theta}}(k+1+\gamma)^{-\mathcal{u}_{1}}+y_{0}\exp\left(-\frac{\alpha^{{1}/{\varrho}}\zeta(k+1)}{(k+1+\gamma)^{p/\varrho}}\right).$

The imposed conditions on $\gamma$ in (60) hold due to the assumptions in part
(a).

  * •

Case b): $p=\varrho$. (The conditions in part (b) hold). We can set
$\mathcal{u}=\mathcal{u}_{2}:=\frac{\varrho(\tau-1)}{2\theta}=\frac{\tau-1}{(2\theta-1)\tau+1}$
to achieve the optimal rate. In this case, (57) reduces to

$y_{k+1}\leqslant\left[1+\frac{\ell_{1}\alpha^{\tau}}{(k+\gamma)^{\tau\varrho}}-\frac{2\theta\ell_{2}\nu^{2\theta-1}\alpha}{k+\gamma}\right]y_{k}+\frac{(2\theta-1)\ell_{2}\nu^{2\theta}\alpha+\ell_{3}\alpha^{\tau}}{(k+\gamma)^{\tau\varrho}}.$

As before, if
$\gamma\geqslant\\{(\frac{\ell_{1}\alpha^{\tau-1}}{\theta\ell_{2}\nu^{2\theta-1}})^{\frac{1}{\mathcal{u}_{2}}},\alpha\theta\ell_{2}\nu^{2\theta-1}\\}$
and using $\tau\varrho-1=\mathcal{u}_{2}$, we can infer

$y_{k+1}\leqslant\left[1-\frac{\theta\ell_{2}\nu^{2\theta-1}\alpha}{k+\gamma}\right]y_{k}+\frac{(2\theta-1)\ell_{2}\nu^{2\theta}\alpha+\ell_{3}\alpha^{\tau}}{(k+\gamma)^{\tau\varrho}}$
(61)

and $\theta\ell_{2}\nu^{2\theta-1}\alpha(k+\gamma)^{-1}\leqslant 1$ for all
$k$. Invoking Theorem 24 (b) with $p=1$, $q=\tau\varrho-1=\mathcal{u}_{2}$,
$c=\theta\ell_{2}\nu^{2\theta-1}\alpha$,
$d=(2\theta-1)\ell_{2}\nu^{2\theta}\alpha+\ell_{3}\alpha^{\tau}$, and letting
$\theta\ell_{2}\nu^{2\theta-1}\alpha\geqslant 2\mathcal{u}_{2}$ to guarantee
$c-q\geqslant\frac{c}{2}$, we have

$y_{k+1}\leqslant\frac{2[(2\theta-1)\ell_{2}\nu^{2\theta}+\ell_{3}\alpha^{\tau-1}]}{\theta\ell_{2}\nu^{2\theta-1}}(k+1+\gamma)^{-\mathcal{u}_{2}}+y_{0}\left(\gamma^{-1}(k+1+\gamma)\right)^{-\theta\ell_{2}\nu^{2\theta-1}\alpha}$

Similar to the previous case, we can select
$\nu=(\frac{\ell_{3}\alpha^{\tau-1}}{\ell_{2}})^{\frac{1}{2\theta}}$ to
optimize the coefficient of the leading term. Then, the conditions on $\alpha$
and $\gamma$ reduce to
$\alpha\geqslant(\frac{2\mathcal{u}_{2}}{\zeta})^{\varrho}$,
$\gamma\geqslant\\{(\frac{\ell_{1}}{\zeta})^{\frac{1}{\mathcal{u}_{2}}}\alpha^{\frac{1}{\varrho}},\zeta\alpha^{\frac{1}{\varrho}}\\}$
and we have

$y_{k+1}\leqslant
4(\tfrac{\ell_{3}}{\ell_{2}})^{\frac{1}{2\theta}}\alpha^{\frac{\tau-1}{2\theta}}(k+1+\gamma)^{-\varrho}+y_{0}\left(\gamma^{-1}(k+1+\gamma)\right)^{-\zeta\alpha^{{1}/{\varrho}}}.$

  * •