# High Probability Convergence of Stochastic Gradient Methods

Zijian Liu Equal contribution. Stern School of Business, New York University,
<EMAIL_ADDRESS>Ta Duy Nguyen Equal contribution. Department of Computer
Science, Boston University<EMAIL_ADDRESS>Thien H. Nguyen Equal contribution.
Khoury College of Computer Sciences, Northeastern University,
<EMAIL_ADDRESS>Alina Ene Department of Computer Science,
Boston University<EMAIL_ADDRESS>Huy L. Nguyen Khoury College of Computer
Sciences, Northeastern University<EMAIL_ADDRESS>
###### Abstract

In this work, we describe a generic approach to show convergence with high
probability for both stochastic convex and non-convex optimization with sub-
Gaussian noise. In previous works for convex optimization, either the
convergence is only in expectation or the bound depends on the diameter of the
domain. Instead, we show high probability convergence with bounds depending on
the initial distance to the optimal solution. The algorithms use step sizes
analogous to the standard settings and are universal to Lipschitz functions,
smooth functions, and their linear combinations. This method can be applied to
the non-convex case. We demonstrate an
$O((1+\sigma^{2}\log(1/\delta))/T+\sigma/\sqrt{T})$ convergence rate when the
number of iterations $T$ is known and an
$O((1+\sigma^{2}\log(T/\delta))/\sqrt{T})$ convergence rate when $T$ is
unknown for SGD, where $1-\delta$ is the desired success probability. These
bounds improve over existing bounds in the literature. Additionally, we
demonstrate that our techniques can be used to obtain high probability bound
for AdaGrad-Norm (Ward et al., 2019) that removes the bounded gradients
assumption from previous works. Furthermore, our technique for AdaGrad-Norm
extends to the standard per-coordinate AdaGrad algorithm (Duchi et al., 2011),
providing the first noise-adapted high probability convergence for AdaGrad.

##  1 Introduction

Stochastic optimization is a fundamental area with extensive applications in
many domains, ranging from machine learning to algorithm design and beyond.
The design and analysis of iterative methods for stochastic optimization has
been the focus of a long line of work, leading to a rich understanding of the
convergence of paradigmatic iterative methods such as stochastic gradient
descent, mirror descent, and accelerated methods for both convex and non-
convex optimization. However, most of these works only establish convergence
guarantees that hold only in expectation. Although very meaningful, these
results do not fully capture the convergence behaviors of the algorithms when
we perform only a small number of runs of the algorithm, as it is typical in
modern machine learning applications where there are significant computational
and statistical costs associated with performing multiple runs of the
algorithm (Harvey et al., 2019; Madden et al., 2020; Davis et al., 2021).
Thus, an important direction is to establish convergence guarantees for a
single run of the algorithm that hold not only in expectation but also with
high probability.

Compared to the guarantees that hold in expectation, high probability
guarantees are significantly harder to obtain and they hold in more limited
settings with stronger assumptions on the problem settings and the stochastic
noise distribution. Most existing works that establish high probability
guarantees focus on the setting where the length of the stochastic noise
follows a light-tail (sub-Gaussian) distribution (Juditsky et al., 2011; Lan,
2012, 2020; Li and Orabona, 2020; Madden et al., 2020; Kavis et al., 2021).
Recent works also study the more challenging heavy-tail setting, notably under
a bounded variance (Nazin et al., 2019; Gorbunov et al., 2020; Cutkosky and
Mehta, 2021) or bounded $p$-moment assumption (Cutkosky and Mehta, 2021) on
the length of the stochastic noise. Both settings are highly relevant in
practice: Zhang et al. (2020) empirically studied the noise distribution for
two common tasks, training a ResNet model for computer vision and a BERT
transformer model for natural language processing, and they observed that the
noise distribution in the former task is well-approximated by a sub-Gaussian
distribution, and it appears to be heavy-tailed in the latter task.

Despite this important progress, the convergence of cornerstone methods is not
fully understood even in the more structured light-tailed noise setting.
Specifically, the existing works for both convex and non-convex optimization
rely on strong assumptions on the optimization domain and the gradients that
significantly limit their applicability:

_The problem domain is restricted to either the unconstrained domain or a
constrained domain with bounded Bregman diameter._ The convergence guarantees
established depend on the Bregman diameter of the domain instead of the
initial distance to the optimum. Even for compact domains, since the diameter
can be much larger than the initial distance, these guarantees are pessimistic
and diminish the benefits of good initializations. Thus an important direction
remains to establish high probability guarantees for general optimization that
scale only with the initial Bregman distance.

_The gradients or stochastic gradients are assumed to be bounded even in the
smooth setting._ These additional assumptions are very restrictive and they
significantly limit the applicability of the algorithm, e.g., they do not
apply to important settings such as quadratic optimization. Moreover, the
stochastic gradient assumption is more restrictive than other commonly studied
assumptions, such as the gradients and the stochastic noise being bounded
almost surely.

The above assumptions are not merely an artifact of the analysis, and they
stem from important considerations and technical challenges. The high
probability convergence guarantees are established via martingale
concentration inequalities that impose necessary conditions on how much the
martingale sequence can change in each step. However, the natural martingale
sequences that arise in optimization depend on quantities such as the distance
between the iterates and the optimum and the stochastic gradients, which are
not a priori bounded. The aforementioned assumptions ensure that the
concentration inequalities can be readily applied due to the relevant
stochastic terms being all bounded almost surely. These difficulties are even
more pronounced for adaptive algorithms in the AdaGrad family that set the
step sizes based on the stochastic gradients. The adaptive step sizes
introduce correlations between the step sizes and the update directions, and a
crucial component is the analysis of the evolution of the adaptive step sizes
and the cumulative stochastic noise. If the gradients are bounded, both of
these challenges can be overcome by paying error terms proportional to the
lengths of the gradients and stochastic gradients. Removing the bounded
gradient assumptions requires new technical insights and tools.

In addition to requiring stronger assumptions, due to the technical challenges
involved, several of the prior works are only able to establish convergence
guarantees that are slower than the ideal sub-Gaussian rates. For example, a
common approach is to control the relevant stochastic quantities across all
$T$ iterations of the algorithm via repeated applications of the concentration
inequalities, leading to convergence rates that have additional factors that
are poly-logarithmic in $T$. Additionally, achieving noise-adaptive rates that
improve towards the deterministic rate as the amount of noise decreases is
very challenging with existing techniques.

Our contributions: This work aims to contribute to this line of work and
overcome the aforementioned challenges. To this end, we introduce a novel
generic approach to show convergence with high probability under sub-Gaussian
gradient noise. Our approach is very general and flexible, and it can be used
both in the convex and non-convex setting. Using our approach, we establish
high-probability convergence guarantees for several fundamental settings:

In the _convex setting_ , we analyze stochastic mirror descent and stochastic
accelerated mirror descent for general optimization domains and Bregman
distances, and we analyze the classical algorithms without any changes. These
well studied algorithms encompass the main algorithmic frameworks for convex
optimization with non-adaptive step sizes (Lan, 2020). Our convergence
guarantees scale with only the Bregman distance between the initial point and
the optimum, and thus they leverage good initializations. Our high-probability
convergence rates are analogous to known results for convergence in
expectation (Juditsky et al., 2011; Lan, 2012). The algorithms are universal
for both Lipschitz functions and smooth functions.

In the _non-convex setting_ , we analyze the SGD as well as the AdaGrad-Norm
algorithm (Ward et al., 2019). Compared to existing works for SGD (Madden et
al., 2020; Li and Orabona, 2020), our rates have better dependency on the time
horizon and the success probability. For AdaGrad-Norm, our approach allows us
to remove the restrictive assumption on the gradients as made in previous work
(Kavis et al., 2021). More importantly, the technique employed to show high
probability convergence of AdaGrad-Norm readily extends to the standard
coordinate version of AdaGrad; we obtain the first results for the high
probability convergence guarantee for AdaGrad (Duchi et al., 2011).

Although we only focus on sub-Gaussian gradient noise – a more structured
setting where there still remain significant gaps in our understanding – we
believe our approach could potentially be applied in more general settings
such as heavy tails noise.

###  1.1 Our techniques

Compared to prior works that rely on black-box applications of martingale
concentration inequalities such as Freedman’s inequality and its extensions
(Freedman, 1975; Harvey et al., 2019; Madden et al., 2020), we introduce here
a “white-box” concentration argument that leverages existing convergence
analyses for first-order methods. The high-level approach is to define a novel
martingale sequence derived from the standard convergence analyses and analyze
its moment generating function from first principles. By leveraging the
structure of the optimization problem, we are able to overcome a key
difficulty associated with black-box applications of martingale concentration
results: these results pose necessary conditions on how much the martingale
sequence can change, which do not a priori hold for the natural martingales
that arise in optimization. By seamlessly combining the optimization and
probability tool-kits, we obtain a flexible analysis template that allows us
to handle general optimization domains with very large or even unbounded
diameter, general objectives that are not globally Lipschitz, and adaptive
step sizes.

Our technique is inspired by classical works in concentration inequalities,
specifically a type of martingale inequalities where the variance of the
martingale difference is bounded by a linear function of the previous value.
This technique is first applied by Harvey et al. (2019) to show high
probability convergence for SGD in the strongly convex setting. Our proof is
inspired by the proof of Theorem 7.3 by Chung and Lu (2006). In each time step
with iterate $x_{t}$, let $\xi_{t}:=\widehat{\nabla}f\left(x_{t}\right)-\nabla
f\left(x_{t}\right)$ be the stochastic error in our gradient estimate.
Classical proofs of convergence evolve around analyzing the sum of
$\left\langle\xi_{t},x^{*}-x_{t}\right\rangle$, which can be viewed as a
martingale sequence. Assuming a bounded domain, the concentration of the sum
can be shown via classical martingale inequalities. The key new insight is
that instead of analyzing this sum, we analyze a related sum where the
coefficients decrease over time to account for the fact that we have a looser
grip on the distance to the optimal solution as time increases. Nonetheless,
the coefficients are kept within a constant factor of each others and the same
asymptotic convergence is attained with high probability.

###  1.2 Related work

#### Convex optimization:

Nemirovski et al. (2009); Lan (2012) establish high probability bounds for
stochastic mirror descent and accelerated stochastic mirror descent with sub-
Gaussian noise. These rates match the best rates known in expectation, but
they depend on the Bregman diameter
$\max_{x,y\in\mathcal{X}}\mathbf{D}_{\psi}\left(x,y\right)$ of the domain,
which can be very large or even unbounded. Similarly, Kakade and Tewari
(2008); Rakhlin et al. (2011); Hazan and Kale (2014); Harvey et al. (2019);
Dvurechensky and Gasnikov (2016) study the high-probability convergence of SGD
that also assume that the domain has bounded diameter or the function is
strongly convex. In contrast, our work complements its predecessors with a
novel concentration argument that establishes convergence for the general
setting of convex functions under sub-Gaussian gradient noise (as considered
in Lan (2020)) that depends only on the distance
$\mathbf{D}_{\psi}\left(x^{*},x_{1}\right)$ from the initial point to the
optimum instead of the diameter of the problem or having to assume that the
objective is strongly convex.

On a different note, Nazin et al. (2019); Gorbunov et al. (2020) consider the
more general setting of bounded variance noise. However, their problem
settings are more restricted than ours. Specifically, Nazin et al. (2019)
analyze stochastic mirror descent only in the setting where the optimization
domain has bounded Bregman diameter. Gorbunov et al. (2020) analyze modified
versions of stochastic gradient descent and accelerated stochastic gradient
descent (such as with clipping), but only for unconstrained optimization with
the $\ell_{2}$ setup. In contrast, our work applies to a more general
optimization setup: we analyze the classical stochastic mirror descent and
accelerated mirror descent without any modifications under general Bregman
distances and arbitrary optimization domains that are possibly unbounded.
Finally,Davis et al. (2021) provides an algorithm to achieve high probability
convergence by solving an auxiliary optimization problem in each iteration.
However, their analysis is restricted to well-conditioned objectives that are
both smooth and strongly convex and the expensive optimization subroutine can
be impractical.

#### Non-convex optimization:

Li and Orabona (2020) demonstrate a high probability bound for an SGD
algorithm with momentum, while Madden et al. (2020) and Li and Liu (2022) show
high probability bounds for vanilla SGD that generalize to the family of sub-
Weibull noise. However, these existing bounds are not optimal due to the
multiplicative dependency $O\left(\log T\log\frac{1}{\delta}\right)$. In our
work, we improve the high-probability convergence for SGD in the non-convex
setting via our novel approach.

For algorithms with adaptive step size like AdaGrad, Li and Orabona (2020);
Kavis et al. (2021) provide some of the first high probability guarantees in
the non-convex setting. However, there still remains significant gaps in our
understanding: Li and Orabona (2020) is not fully adaptive due to the
dependence of the initial step size on the problem parameters, whereas Kavis
et al. (2021) requires that the gradients and/or stochastic gradients to be
uniformly bounded almost surely, a strong assumption that excludes even the
quadratic function. In contrast, we establish convergence in high probability
of AdaGrad-Norm (Ward et al., 2019; Faw et al., 2022) without further
restrictive assumptions. Notably, a key distinction from prior work is that
our does not involve the division by the step size: this allows a direct
extension of our analysis for AdaGrad-Norm (in which the step size is a
scalar) to the general AdaGrad (Duchi et al., 2011) algorithm (where the step
size varies for each coordinate). There, to the best of our knowledge,
Défossez et al. (2022) is the only work to provide an _in expectation_
guarantee for vanilla Adagrad albeit under strong assumptions. We provide a
more detailed comparison with prior work in the subsequent sections.

Convergence guarantees for the heavy tail noise regime has also been studied
for non-convex objectives. However, some form of gradient clipping is required
in most works to deal with the large variance. The work Zhang et al. (2020)
proposes a gradient clipping algorithm that can converge _in expectation_ for
noise distributions with heavier tail—that is the $p$-moment is bounded for
$1<p\leq 2$. Cutkosky and Mehta (2021) propose a more complex clipped SGD
algorithm with momentum under the same noise assumption, for which they show a
high probability convergence. However, Cutkosky and Mehta (2021) rely on the
bounded moments of the stochastic gradients for the non-convex setting; a
restrictive assumption that excludes quadratic objectives. In contrast, we
focus on standard algorithms (albeit under sub-Gaussian noise) that have been
more widely used: stochastic mirror descent, stochastic gradient descent, and
AdaGrad-Norm. Our technique is general and we believe that it is possible to
extend it to the heavy-tail noise setting.

##  2 Preliminaries

We consider the problem $\min_{x\in\mathcal{X}}f(x)$ where
$f:\mathbb{R}^{d}\to\mathbb{R}$ is the objective function and $\mathcal{X}$ is
the domain of the problem. In the convex case, we consider the general setting
where $f$ is potentially not strongly convex and the domain $\mathcal{X}$ is
convex but not necessarily compact. The distance between solutions in
$\mathcal{X}$ is measured by a general norm $\left\|\cdot\right\|$. Let
$\left\|\cdot\right\|_{*}$ denote the dual norm of $\left\|\cdot\right\|$. In
the non-convex case, we consider the setting where $\mathcal{X}$ is
$\mathbb{R}^{d}$ and $\left\|\cdot\right\|$ is the $\ell_{2}$ norm.

In this paper, we use the following assumptions:

(1) Existence of a minimizer: In the convex setting, we assume that there
exists $x^{*}=\arg\min_{x\in\mathcal{X}}f(x)$.

(1’) Existence of a minimizer: In the nonconvex setting, we assume that $f$
admits a finite lower bound $\inf_{x\in\mathcal{X}}f(x)\coloneqq
f_{*}>-\infty$.

(2) Unbiased estimator: We assume to have access to a history independent,
non-biased gradient estimator $\widehat{\nabla}f(x)$ for any
$x\in\mathcal{X}$, that is $\mathbb{\mathbb{E}}\left[\widehat{\nabla}f(x)\mid
x\right]=\nabla f(x)$.

(3) Sub-Gaussian noise: $\left\|\widehat{\nabla}f(x)-\nabla f(x)\right\|_{*}$
is a $\sigma$-sub-Gaussian random variable (Definition 2.1).

There are several equivalent definitions of sub-Gaussian random variables up
to an absolute constant scaling (see, e.g., Proposition 2.5.2 in Vershynin
(2018)). For convenience, we use the following property as the definition.

######  Definition 2.1.

A random variable $X$ is $\sigma$-sub-Gaussian if

$\mathbb{\mathbb{E}}\left[\exp\left(\lambda^{2}X^{2}\right)\right]\leq\exp\left(\lambda^{2}\sigma^{2}\right)\text{
for all }\lambda\text{ such that }\left|\lambda\right|\leq\frac{1}{\sigma}.$

We will also use the following helper lemma whose proof we defer to the
Appendix.

######  Lemma 2.2.

Suppose $X\in\mathbb{R}^{d}$ such that $\mathbb{\mathbb{E}}\left[X\right]=0$
and $\left\|X\right\|$ is a $\sigma$-sub-Gaussian random variable, then for
any $a\in\mathbb{R}^{d}$, $0\leq b\leq\frac{1}{2\sigma}$,

$\displaystyle\mathbb{\mathbb{E}}\left[\exp\left(\left\langle
a,X\right\rangle+b^{2}\left\|X\right\|^{2}\right)\right]$
$\displaystyle\leq\exp\left(3\left(\left\|a\right\|_{*}^{2}+b^{2}\right)\sigma^{2}\right).$

Especially, when $b=0$, we have

$\mathbb{\mathbb{E}}\left[\exp\left(\left\langle
a,X\right\rangle\right)\right]\leq\exp\left(2\left\|a\right\|_{*}^{2}\sigma^{2}\right).$

##  3 Convex case: Stochastic Mirror Descent and Accelerated Stochastic Mirror
Descent

In this section, we analyze the Stochastic Mirror Descent algorithm (Algorithm
1) and Accelerated Stochastic Mirror Descent algorithm (Algorithm 2) for
convex optimization. We define the Bregman divergence
$\mathbf{D}_{\psi}\left(x,y\right)=\psi\left(x\right)-\psi\left(y\right)-\left\langle\nabla\psi\left(y\right),x-y\right\rangle$
where $\psi:\mathbb{R}^{d}\to\mathbb{R}$ is an $1$-strongly convex mirror map
with respect to $\left\|\cdot\right\|$ on $\mathcal{X}$. We remark that the
domain of $\psi$ is defined as $\mathbb{R}^{d}$ for simplicity, though which
is not necessary.

###  3.1 Analysis of Stochastic Mirror Descent

Algorithm 1 Stochastic Mirror Descent Algorithm

Parameters: initial point $x_{1}\in\mathcal{X}$, step sizes
$\left\\{\eta_{t}\right\\}$, strongly convex mirror map $\psi$

for $t=1$ to $T$:

$x_{t+1}=\arg\min_{x\in\mathcal{X}}\left\\{\eta_{t}\left\langle\widehat{\nabla}f\left(x_{t}\right),x\right\rangle+\mathbf{D}_{\psi}\left(x,x_{t}\right)\right\\}$

return $\frac{1}{T}\sum_{t=1}^{T}x_{t}$

The end result of this section is the convergence guarantee of Algorithm 1 for
constant step sizes (when the time horizon $T$ is known) and time-varying step
sizes (when $T$ is unknown) presented in Theorem 3.1. However, we will
emphasize more on presenting the core idea of our approach, which will serve
as the basis for the analysis in subsequent sections. For simplicity, here we
consider the non-smooth setting, and assume that $f$ is $G$-Lipschitz
continuous, i.e., we have $\left\|\nabla f(x)\right\|_{*}\leq G$ for all
$x\in\mathcal{X}$. However, this is not necessary. The analysis for the smooth
setting follows via a simple modification to the analysis presented here as
well as the analysis for the accelerated setting given in the next section.

######  Theorem 3.1.

Assume $f$ is $G$-Lipschitz continuous and satisfies Assumptions (1), (2),
(3), with probability at least $1-\delta$, the iterate sequence
$(x_{t})_{t\geq 1}$ output by Algorithm 1 satisfies

(1) Setting
$\eta_{t}=\sqrt{\frac{\mathbf{D}_{\psi}\left(x^{*},x_{1}\right)}{6\left(G^{2}+\sigma^{2}\left(1+\log\left(\frac{1}{\delta}\right)\right)\right)T}}$,
then $\mathbf{D}_{\psi}\left(x^{*},x_{T+1}\right)\leq
4\mathbf{D}_{\psi}\left(x^{*},x_{1}\right)$, and

$\displaystyle\frac{1}{T}\sum_{t=1}^{T}\left(f\left(x_{t}\right)-f\left(x^{*}\right)\right)$
$\displaystyle\leq\frac{4\sqrt{6}}{\sqrt{T}}\sqrt{\mathbf{D}_{\psi}\left(x^{*},x_{1}\right)\left(G^{2}+\sigma^{2}\left(1+\log\left(\frac{1}{\delta}\right)\right)\right)}.$

(2) Setting
$\eta_{t}=\sqrt{\frac{\mathbf{D}_{\psi}\left(x^{*},x_{1}\right)}{6\left(G^{2}+\sigma^{2}\left(1+\log\left(\frac{1}{\delta}\right)\right)\right)t}}$,
then $\mathbf{D}_{\psi}\left(x^{*},x_{T+1}\right)\leq 2(2+\log
T)\mathbf{D}_{\psi}\left(x^{*},x_{1}\right)$, and

$\displaystyle\frac{1}{T}\sum_{t=1}^{T}\left(f\left(x_{t}\right)-f\left(x^{*}\right)\right)$
$\displaystyle\leq\frac{2\sqrt{6}}{\sqrt{T}}(2+\log
T)\sqrt{\mathbf{D}_{\psi}\left(x^{*},x_{1}\right)\left(G^{2}+\sigma^{2}\left(1+\log\left(\frac{1}{\delta}\right)\right)\right)}.$

We define $\xi_{t}:=\widehat{\nabla}f\left(x_{t}\right)-\nabla
f\left(x_{t}\right)$ and let
$\mathcal{F}_{t}=\sigma\left(\xi_{1},\dots,\xi_{t-1}\right)$ denote the
natural filtration. Note that $x_{t}$ is $\mathcal{F}_{t}$-measurable. The
starting point of our analysis is the following inequality that follows from
the standard stochastic mirror descent analysis (see, e.g., Lan (2020)). We
include the proof in the Appendix for completeness.

######  Lemma 3.2.

Lan (2020) For every iteration $t$, we have

$\displaystyle A_{t}$
$\displaystyle\coloneqq\eta_{t}\left(f\left(x_{t}\right)-f\left(x^{*}\right)\right)-\eta_{t}^{2}G^{2}+\mathbf{D}_{\psi}\left(x^{*},x_{t+1}\right)-\mathbf{D}_{\psi}\left(x^{*},x_{t}\right)$
$\displaystyle\leq\eta_{t}\left\langle\xi_{t},x^{*}-x_{t}\right\rangle+\eta_{t}^{2}\left\|\xi_{t}\right\|_{*}^{2}.$

We now turn our attention to our main concentration argument. Towards our goal
of obtaining a high-probability convergence rate, we analyze the moment
generating function for a random variable that is closely related to the left-
hand side of the inequality above. We let $\\{w_{t}\\}$ be a sequence where
$w_{t}\geq 0$ for all $t$. We define

$\displaystyle Z_{t}$
$\displaystyle=w_{t}A_{t}-v_{t}\mathbf{D}_{\psi}\left(x^{*},x_{t}\right),$
$\displaystyle\forall\,1\leq t\leq T$ $\displaystyle\mbox{where }v_{t}$
$\displaystyle=6\sigma^{2}\eta_{t}^{2}w_{t}^{2}$ $\displaystyle\text{and
}S_{t}$ $\displaystyle=\sum_{i=t}^{T}Z_{i},$ $\displaystyle\forall\,1\leq
t\leq T+1$

Before proceeding with the analysis, we provide intuition for our approach. If
we consider $S_{1}$, we see that it combines the gains in function value gaps
with weights given by the sequence $\left\\{w_{t}\right\\}$ and the losses
given by the Bregman divergence terms
$\mathbf{D}_{\psi}\left(x^{*},x_{t}\right)$ with coefficients $v_{t}$ chosen
based on the step size $\eta_{t}$ and $w_{t}$. The intuition here is that we
want to transfer the error from the stochastic error terms on the RHS of Lemma
3.2 into the loss term $v_{t}\mathbf{D}_{\psi}\left(x^{*},x_{t}\right)$ then
leverage the progression of the Bregman divergence
$\mathbf{D}_{\psi}\left(x^{*},x_{t+1}\right)-\mathbf{D}_{\psi}\left(x^{*},x_{t}\right)$
to absorb this loss. For the first step, we can do that by setting the
coefficient $v_{t}$ to equalize coefficient of divergence term that will
appear from the RHS of Lemma 3.2. For the second step, we can aim at making
all the divergence terms telescope, by selecting $v_{t}$ and $w_{t}$ such that
$w_{t}+v_{t}\leq w_{t-1}$ to have a telescoping sum of the terms
$w_{t}\mathbf{D}_{\psi}\left(x^{*},x_{t+1}\right)-w_{t-1}\mathbf{D}_{\psi}\left(x^{*},x_{t}\right)$.
In the end we will obtain a bound for the function value gaps in terms of only
the deterministic quantities, namely $\eta_{t},w_{t},G$ and the initial
distance. In Theorem 3.3, we upper bound the moment generating function of
$S_{1}$ and derive a set of conditions for the weights
$\left\\{w_{t}\right\\}$ that allow us to absorb the stochastic errors. In
Corollary 3.4, we show how to choose the weights $\left\\{w_{t}\right\\}$ and
obtain a convergence rate that matches the standard rates that hold in
expectation.

We now give our main concentration argument that bounds the moment generating
function of $S_{t}$ inspired by the proof of Theorem 7.3 in Chung and Lu
(2006).

######  Theorem 3.3.

Suppose that $w_{t}\eta_{t}^{2}\leq\frac{1}{4\sigma^{2}}$ for every $1\leq
t\leq T$. For every $1\leq t\leq T+1$, we have

$\displaystyle\mathbb{\mathbb{E}}\left[\exp\left(S_{t}\right)\mid\mathcal{F}_{t}\right]\leq$
$\displaystyle\exp\left(3\sigma^{2}\sum_{i=t}^{T}w_{i}\eta_{i}^{2}\right).$

###### Proof.

We proceed by induction on $t$. Consider the base case $t=T+1$. We have the
inequality holds true trivially. Next, we consider $1\leq t\leq T$. We have

$\displaystyle\mathbb{\mathbb{E}}\left[\exp\left(S_{t}\right)\mid\mathcal{F}_{t}\right]$
$\displaystyle=\mathbb{\mathbb{E}}\left[\exp\left(Z_{t}+S_{t+1}\right)\mid\mathcal{F}_{t}\right]$
$\displaystyle=\mathbb{\mathbb{E}}\left[\mathbb{\mathbb{E}}\left[\exp\left(Z_{t}+S_{t+1}\right)\mid\mathcal{F}_{t+1}\right]\mid\mathcal{F}_{t}\right].$
(1)

We now analyze the inner expectation. Conditioned on $\mathcal{F}_{t+1}$,
$Z_{t}$ is fixed. Using the inductive hypothesis, we obtain

$\displaystyle\mathbb{\mathbb{E}}\left[\exp\left(Z_{t}+S_{t+1}\right)\mid\mathcal{F}_{t+1}\right]$
$\displaystyle\leq\exp\left(Z_{t}\right)\exp\left(3\sigma^{2}\sum_{i=t+1}^{T}w_{i}\eta_{i}^{2}\right).$
(2)

Plugging into (1), we obtain

$\displaystyle\mathbb{\mathbb{E}}\left[\exp\left(S_{t}\right)\mid\mathcal{F}_{t}\right]$
$\displaystyle\leq\mathbb{\mathbb{E}}\left[\exp\left(Z_{t}\right)\mid\mathcal{F}_{t}\right]\exp\left(3\sigma^{2}\sum_{i=t+1}^{T}w_{i}\eta_{i}^{2}\right).$
(3)

By Lemma 3.2

$\displaystyle\exp\left(Z_{t}\right)$
$\displaystyle=\exp\bigg{(}w_{t}\big{(}\eta_{t}\left(f\left(x_{t}\right)-f\left(x^{*}\right)\right)-\eta_{t}^{2}G^{2}+\mathbf{D}_{\psi}\left(x^{*},x_{t+1}\right)-\mathbf{D}_{\psi}\left(x^{*},x_{t}\right)\big{)}-v_{t}\mathbf{D}_{\psi}\left(x^{*},x_{t}\right)\bigg{)}$
$\displaystyle\leq\exp\bigg{(}w_{t}\eta_{t}\left\langle\xi_{t},x^{*}-x_{t}\right\rangle+w_{t}\eta_{t}^{2}\left\|\xi_{t}\right\|_{*}^{2}\bigg{)}\exp\left(-v_{t}\mathbf{D}_{\psi}\left(x^{*},x_{t}\right)\right).$

Next, we analyze the first term in the last line of the above inequality in
expectation. Since
$\mathbb{\mathbb{E}}\left[\left\langle\xi_{t},x^{*}-x_{t}\right\rangle\mid\mathcal{F}_{t}\right]=0$
we can use Lemma 2.2 to obtain

$\displaystyle\mathbb{\mathbb{E}}\left[\exp\left(w_{t}\eta_{t}\left\langle\xi_{t},x^{*}-x_{t}\right\rangle+w_{t}\eta_{t}^{2}\left\|\xi_{t}\right\|_{*}^{2}\right)\mid\mathcal{F}_{t}\right]$
$\displaystyle\leq\exp\left(3\sigma^{2}\left(w_{t}^{2}\eta_{t}^{2}\left\|x^{*}-x_{t}\right\|^{2}+w_{t}\eta_{t}^{2}\right)\right)$
$\displaystyle\leq\exp\left(3\sigma^{2}\left(2w_{t}^{2}\eta_{t}^{2}\mathbf{D}_{\psi}\left(x^{*},x_{t}\right)+w_{t}\eta_{t}^{2}\right)\right)$
(4)

where in the last line we used that
$\mathbf{D}_{\psi}\left(x^{*},x_{t}\right)\geq\frac{1}{2}\left\|x^{*}-x_{t}\right\|^{2}$
from the strong convexity of $\psi$.

Plugging back into (3) and using that
$v_{t}=6\sigma^{2}\eta_{t}^{2}w_{t}^{2}$, we obtain the desired inequality

$\displaystyle\mathbb{\mathbb{E}}\left[\exp\left(S_{t}\right)\mid\mathcal{F}_{t}\right]\leq$
$\displaystyle\exp\left(\left(6\sigma^{2}\eta_{t}^{2}w_{t}^{2}-v_{t}\right)\mathbf{D}_{\psi}\left(x^{*},x_{t}\right)+3\sigma^{2}\sum_{i=t}^{T}w_{i}\eta_{i}^{2}\right)$
$\displaystyle=$
$\displaystyle\exp\left(3\sigma^{2}\sum_{i=t}^{T}w_{i}\eta_{i}^{2}\right).$

∎

Using Theorem 3.3 and Markov’s inequality, we obtain the following convergence
guarantee.

######  Corollary 3.4.

Suppose the sequence $\left\\{w_{t}\right\\}$ satisfies the conditions of
Theorem 3.3 and that $w_{t}+6\sigma^{2}\eta_{t}^{2}w_{t}^{2}\leq w_{t-1}.$ For
any $\delta>0$, with probability at least $1-\delta$:

$\displaystyle\sum_{t=1}^{T}w_{t}\eta_{t}\left(f\left(x_{t}\right)-f\left(x^{*}\right)\right)+w_{T}\mathbf{D}_{\psi}\left(x^{*},x_{T+1}\right)$
$\displaystyle\leq
w_{0}\mathbf{D}_{\psi}\left(x^{*},x_{1}\right)+\left(G^{2}+3\sigma^{2}\right)\sum_{t=1}^{T}w_{t}\eta_{t}^{2}+\log\left(\frac{1}{\delta}\right).$

With the above result in hand, we complete the convergence analysis by showing
how to define the sequence $\left\\{w_{t}\right\\}$ with the desired
properties. For the stochastic Mirror Descent algorithm with fixed step sizes
$\eta_{t}=\frac{\eta}{\sqrt{T}}$, we set
$w_{T}=\frac{1}{12\sigma^{2}\eta^{2}}$ and
$w_{t-1}=w_{t}+\frac{6}{T}\sigma^{2}\eta^{2}w_{t}^{2}$ for all $1\leq t\leq
T$. For Stochastic Mirror Descent algorithm with time-varying step sizes
$\eta_{t}=\frac{\eta}{\sqrt{t}}$, we set
$w_{T}=\frac{1}{12\sigma^{2}\eta^{2}\left(\sum_{t=1}^{T}\frac{1}{t}\right)}$
and $w_{t-1}=w_{t}+6\sigma^{2}\eta_{t}^{2}w_{t}^{2}$ for all $1\leq t\leq T$.
In the appendix, we show that these choices have the give us the results in
Theorem 3.1.

###  3.2 Analysis of Accelerated Stochastic Mirror Descent

Algorithm 2 Accelerated Stochastic Mirror Descent Algorithm Lan (2020).

Parameters: initial point $x_{0}=y_{0}=z_{0}\in\mathcal{X}$, step size $\eta$,
strongly convex mirror map $\psi$

for $t=1$ to $T$:

Set $\alpha_{t}=\frac{2}{t+1}$

$x_{t}=\left(1-\alpha_{t}\right)y_{t-1}+\alpha_{t}z_{t-1}$

$z_{t}=\arg\min_{x\in\mathcal{X}}\left(\eta_{t}\left\langle\widehat{\nabla}f(x_{t}),x\right\rangle+\mathbf{D}_{\psi}\left(x,z_{t-1}\right)\right)$

$y_{t}=\left(1-\alpha_{t}\right)y_{t-1}+\alpha_{t}z_{t}$

return $y_{T}$

In this section, we extend the analysis detailed in the previous section to
analyze the Accelerated Stochastic Mirror Descent Algorithm (Algorithm (2)).
We assume that $f$ satisfies the following condition: for all
$x,y\in\mathcal{X}$

$f(y)\leq f(x)+\left\langle\nabla
f\left(x\right),y-x\right\rangle+G\left\|y-x\right\|+\frac{L}{2}\left\|y-x\right\|^{2}.$
(5)

Note that $L$-smooth functions, $G$-Lipschitz functions, and their sums all
satisfy the above condition. The full convergence guarantees are given in
Theorem B.3. We will only highlight the application of the previous analysis
in this case. As before, we define
$\xi_{t}:=\widehat{\nabla}f\left(x_{t}\right)-\nabla f\left(x_{t}\right)$.

We also start with the inequalities shown in the standard analysis, e.g, from
Lan (2020) (proof in the Appendix).

######  Lemma 3.5.

Lan (2020) For every iteration $t$, we have

$\displaystyle B_{t}$
$\displaystyle\coloneqq\frac{\eta_{t}}{\alpha_{t}}\left(f\left(y_{t}\right)-f\left(x^{*}\right)\right)-\frac{\eta_{t}\left(1-\alpha_{t}\right)}{\alpha_{t}}\left(f\left(y_{t-1}\right)-f\left(x^{*}\right)\right)$
$\displaystyle\quad-\frac{\eta_{t}^{2}}{1-L\alpha_{t}\eta_{t}}G^{2}+\mathbf{D}_{\psi}\left(x^{*},z_{t}\right)-\mathbf{D}_{\psi}\left(x^{*},z_{t-1}\right)$
$\displaystyle\leq\eta_{t}\left\langle\xi_{t},x^{*}-z_{t-1}\right\rangle+\frac{\eta_{t}^{2}}{1-L\alpha_{t}\eta_{t}}\left\|\xi_{t}\right\|_{*}^{2}.$

We now turn our attention to our main concentration argument. Similar to the
previous section, we define

$\displaystyle Z_{t}$
$\displaystyle=w_{t}B_{t}-v_{t}\mathbf{D}_{\psi}\left(x^{*},z_{t-1}\right),$
$\displaystyle\forall\,1\leq t\leq T$ $\displaystyle\mbox{where }v_{t}$
$\displaystyle=6\sigma^{2}w_{t}^{2}\eta_{t}^{2}$ $\displaystyle\text{and
}S_{t}$ $\displaystyle=\sum_{i=t}^{T}Z_{i},$ $\displaystyle\forall\,1\leq
t\leq T+1$

Notice that here we are following the exact same step as before. By
transferring the error terms in the RHS of Lemma 3.5 into the Bregman
divergence terms $\mathbf{D}_{\psi}\left(x^{*},z_{t-1}\right)$, we can absorb
them by setting the coefficients appropriately. In the same manner, we can
show the following theorem.

######  Theorem 3.6.

Suppose that
$\frac{w_{t}\eta_{t}^{2}}{1-L\alpha_{t}\eta_{t}}\leq\frac{1}{4\sigma^{2}}$ for
every $0\leq t\leq T$. For every $1\leq t\leq T+1$, we have

$\displaystyle\mathbb{\mathbb{E}}\left[\exp\left(S_{t}\right)\mid\mathcal{F}_{t}\right]$
$\displaystyle\leq\exp\Bigg{(}3\sigma^{2}\sum_{i=t}^{T}w_{i}\frac{\eta_{i}^{2}}{1-L\alpha_{i}\eta_{i}}\Bigg{)}.$

######  Corollary 3.7.

Suppose the sequence $\left\\{w_{t}\right\\}$ satisfies the conditions of
Theorem 3.6. For any $\delta>0$, the following event holds with probability at
least $1-\delta$:

$\displaystyle\sum_{t=1}^{T}w_{t}\left(\frac{\eta_{t}}{\alpha_{t}}\left(f\left(y_{t}\right)-f\left(x^{*}\right)\right)-\frac{\eta_{t}\left(1-\alpha_{t}\right)}{\alpha_{t}}\left(f\left(y_{t-1}\right)-f\left(x^{*}\right)\right)\right)+w_{T}\mathbf{D}_{\psi}\left(x^{*},z_{T}\right)$
$\displaystyle\leq$ $\displaystyle
w_{0}\mathbf{D}_{\psi}\left(x^{*},z_{0}\right)+\left(G^{2}+3\sigma^{2}\right)\sum_{t=1}^{T}w_{t}\frac{\eta_{t}^{2}}{1-L\alpha_{t}\eta_{t}}+\log\left(\frac{1}{\delta}\right).$

With the above result in hand, we can complete the convergence analysis by
showing how to define the sequence $\left\\{w_{t}\right\\}$ with the desired
properties. Theorem B.3 can be obtained from corollaries B.4 and B.5 provided
in the appendix, for constant and time-varying step sizes.

##  4 Non-convex case: Stochastic Gradient Descent and AdaGrad

In this section, we consider non-convex objectives and analyze the Stochastic
Gradient Descent algorithm (Algorithm 3) along with two versions of AdaGrad:
(1) AdaGrad-Norm Ward et al. (2019) (Algorithm 4), where the step-size is a
scalar, and (2) the original AdaGrad algorithm Duchi et al. (2011) (Algorithm
(5)), where the step-size for each coordinates varies. Since AdaGrad-Norm is
simpler to analyze, most results for AdaGrad have been for this scalar version
either in-expectation Ward et al. (2019); Faw et al. (2022); Li and Orabona
(2020, 2019); Liu et al. (2022); Ene et al. (2021) or high-probability Kavis
et al. (2021). For the standard AdaGrad algorithm, to the best of our
knowledge, Défossez et al. (2022) is the only work that has analyzed the
standard version of AdaGrad in expectation, but their result does not adapt to
noise and requires a strong assumption: the stochastic gradients are uniformly
bounded. On the other hand, our high probability result for vanilla AdaGrad
adapts to noise and holds under relatively mild assumptions.

Recall that, we assume that the optimization problem has domain
$\mathcal{X}=\mathbb{R}^{d}$. As usual in non-convex analysis, we assume that
$f$ is an $L$-smooth function: $\left\|\nabla f(x)-\nabla f(y)\right\|\leq
L\left\|x-y\right\|$ for all $x,y\in\mathbb{R}^{d}$. Smoothness implies the
following quadratic upperbound that we will utilize: for all
$x,y\in\mathbb{R}^{d}$

$\displaystyle f(y)-f(x)$ $\displaystyle\leq\left\langle\nabla
f(x),y-x\right\rangle+\frac{L}{2}\left\|y-x\right\|^{2}.$ (6)

###  4.1 Analysis of Stochastic Gradient Descent

Algorithm 3 Stochastic Gradient Descent (SGD)

Parameters: initial point $x_{1}$, step sizes $\left\\{\eta_{t}\right\\}$

for $t=1$ to $T$ do

$x_{t+1}=x_{t}-\eta_{t}\widehat{\nabla}f(x_{t})$

In this section, we will prove the following convergence guarantee of
Algorithm 3.

######  Theorem 4.1.

Assume $f$ is $L$-smooth and satisfies Assumptions (1’), (2), (3). Let
$\Delta_{1}\coloneqq f(x_{1})-f_{*}$. With probability at least $1-\delta$,
the iterate sequence $(x_{t})_{t\geq 1}$ output by Algorithm 3 satisfies

(1) Setting
$\eta_{t}=\min\left\\{\frac{1}{L};\sqrt{\frac{\Delta_{1}}{\sigma^{2}LT}}\right\\}$,

$\displaystyle\frac{1}{T}\sum_{t=1}^{T}\left\|\nabla f(x_{t})\right\|^{2}$
$\displaystyle\leq\frac{2\Delta_{1}L}{T}+5\sigma\sqrt{\frac{\Delta_{1}L}{T}}+\frac{12\sigma^{2}\log\frac{1}{\delta}}{T};$

(2) Setting $\eta_{t}=\frac{1}{L\sqrt{t}}$,

$\displaystyle\frac{1}{T}\sum_{t=1}^{T}\left\|\nabla f(x_{t})\right\|^{2}$
$\displaystyle\leq\frac{2\Delta_{1}L+3\sigma^{2}\left(1+\log
T\right)+12\sigma^{2}\log\frac{1}{\delta}}{\sqrt{T}}.$

Comparison with prior works: When the time horizon $T$ is known to the
algorithm, by choosing the step size $\eta$ in part $(1)$ of Theorem 4.1, the
bound is adaptive to noise, i.e, when $\sigma=0$ we recover $O(\frac{1}{T})$
convergence rate of the (deterministic) gradient descent algorithm. Notice
that the bound in this case does not have a $\log T$ term incurred. When $T$
is unknown, the extra $\log T$ appears as a result of setting a time-varying
step size $\eta_{t}=\frac{1}{L\sqrt{t}}$. This $\log T$ appears as an additive
term to the $\log\frac{1}{\delta}$ term, as opposed to being multiplicative,
i.e, $\log T\log\frac{1}{\delta}$ as in previous works Li and Orabona (2020);
Madden et al. (2020); Li and Liu (2022).

Analysis: To proceed, we define for $t\geq 1$

$\displaystyle\Delta_{t}$
$\displaystyle:=f(x_{t})-f_{*};\quad\xi_{t}:=\widehat{\nabla}f(x_{t})-\nabla
f(x_{t}).$

We let $\mathcal{F}_{t}:=\sigma\left(\xi_{1},\dots,\xi_{t-1}\right)$ denote
the natural filtration. Note that $x_{t}$ is $\mathcal{F}_{t}$-measurable. The
following lemma serves as a fundamental step of our analysis; the proof of
which can be found in the appendix.

######  Lemma 4.2.

For $t\geq 1$, we have

$\displaystyle C_{t}$
$\displaystyle\coloneqq\eta_{t}\left(1-\frac{L\eta_{t}}{2}\right)\left\|\nabla
f(x_{t})\right\|^{2}+\Delta_{t+1}-\Delta_{t}$
$\displaystyle\leq\left(L\eta_{t}^{2}-\eta_{t}\right)\left\langle\nabla
f(x_{t}),\xi_{t}\right\rangle+\frac{L\eta_{t}^{2}}{2}\left\|\xi_{t}\right\|^{2}.$
(7)

Now we can follow the similar concentration argument from the convex setting.
The difference now is the error term in the RHS of (7) can be transferred into
the gradient term $\left\|\nabla f(x_{t})\right\|^{2}$ instead of a function
value gap term. This actually makes things easier since this term can be
readily absorbed by the gradient term in $C_{t}$, and we do not have to
carefully impose an additional condition on $w_{t}$ to make a telescoping sum.
For $w_{t}\geq 0$, we define

$\displaystyle Z_{t}$ $\displaystyle=w_{t}C_{t}-v_{t}\left\|\nabla
f(x_{t})\right\|^{2},$ $\displaystyle\forall\,1\leq t\leq T$
$\displaystyle\mbox{where }v_{t}$
$\displaystyle=3\sigma^{2}w_{t}^{2}\eta_{t}^{2}(\eta_{t}L-1)^{2}$
$\displaystyle\mbox{and }S_{t}$ $\displaystyle=\sum_{i=t}^{T}Z_{i}.$
$\displaystyle\forall\,1\leq t\leq T+1$

Using the same technique as in the previous Section, we can prove the
following key inequality.

######  Theorem 4.3.

Suppose for all $1\leq t\leq T$, $\eta_{t},w_{t}$ satisfying $0\leq
w_{t}\eta_{t}^{2}L\leq\frac{1}{2\sigma^{2}}$ then

$\mathbb{\mathbb{E}}\left[\exp\left(S_{t}\right)\mid\mathcal{F}_{t}\right]\leq\exp\left(3\sigma^{2}\sum_{s=t}^{T}\frac{w_{t}\eta_{t}^{2}L}{2}\right).$
(8)

Markov’s inequality gives us the following guarantee.

######  Corollary 4.4.

For all $1\leq t\leq T$, if $\eta_{t}L\leq 1$ and $0\leq
w_{t}\eta_{t}^{2}L\leq\frac{1}{2\sigma^{2}}$ then

$\displaystyle\sum_{t=1}^{T}\left[w_{t}\eta_{t}\left(1-\frac{\eta_{t}L}{2}\right)-v_{t}\right]\left\|\nabla
f(x_{t})\right\|^{2}+w_{T}\Delta_{T+1}$ $\displaystyle\leq$ $\displaystyle
w_{1}\Delta_{1}+\left(\sum_{t=2}^{T}(w_{t}-w_{t-1})\Delta_{t}+3\sigma^{2}\sum_{t=1}^{T}\frac{w_{t}\eta_{t}^{2}L}{2}\right)+\log\frac{1}{\delta}.$
(9)

Equipped with Lemmas 4.2 and 4.3, we are ready to prove Theorem 4.1 by
specifying the choice of $w_{t}$ that satisfy the condition of Lemma 4.3. In
the first case, we choose $\eta_{t}=\eta$, $w_{t}=w=\frac{1}{6\sigma^{2}\eta}$
where $\eta=\min\\{\frac{1}{L};\sqrt{\frac{\Delta_{1}}{\sigma^{2}LT}}\\}$. In
the second case, we set $\eta_{t}=\frac{\eta}{\sqrt{t}}$,
$w_{t}=w=\frac{1}{6\sigma^{2}\eta}$ where $\eta=\frac{1}{L}$. We show the full
proof in the appendix.

###  4.2 High probability convergence of AdaGrad-Norm and AdaGrad

In this section, we present our main results for the high probability
convergence for non-convex objectives of AdaGrad-Norm Ward et al. (2019)
(Algorithm 4) as well as the standard AdaGrad Duchi et al. (2011) algorithm
(Algorithm 5) that updates each coordinate separately. Here, $d\in\mathbb{N}$
denotes the dimension of the problem, $v_{i}$ denotes the $i$-th coordinate of
a vector $v$, and $\widehat{\nabla}_{i}f(x_{t})$ denotes the $i$-th coordinate
of the stochastic gradient at time $t$.

Algorithm 4 AdaGrad-Norm

Parameters: $x_{1},\eta>0$.

for $t=1$ to $T$

$b_{t}=\sqrt{b_{0}^{2}+\sum_{i=1}^{t}\|\widehat{\nabla}f(x_{i})\|^{2}}$

$x_{t+1}=x_{t}-\frac{\eta}{b_{t}}\widehat{\nabla}f(x_{t})$

Algorithm 5 AdaGrad

Parameters: $x_{1},b_{0}\in\mathbb{R}^{d}$ and $\eta\in\mathbb{R}$.

for $t=1$ to $T$ do

$b_{t,i}=\sqrt{b_{0,i}^{2}+\sum_{j=1}^{t}\widehat{\nabla}_{i}f(x_{j})^{2}},$
for $i\in[d]$.

$x_{t+1,i}=x_{t,i}-\frac{\eta}{b_{t,i}}\widehat{\nabla}_{i}f(x_{t})$, for
$i\in[d]$.

#### Comparison with prior works.

Ward et al. (2019); Faw et al. (2022) show the convergence of AdaGrad-Norm
with polynomial dependency on $\mathrm{poly}\left(\frac{1}{\delta}\right)$
where $1-\delta$ is the success probability. The latter relaxes several
assumptions made in the former, including the boundedness of the gradients and
noise variance. When assuming a sub-Gaussian noise, Kavis et al. (2021) show a
convergence in high probability, but still assume that the gradients are
bounded which circumvents many of the difficulties due to the error term. We
remove this assumption and establish the convergence of AdaGrad-Norm in the
theorem 4.5. Unlike existing work, the technique employed to prove this
theorem readily extends to the standard version of AdaGrad (Algorithm 5) with
per-coordinate update.

For simplicity, we let $\Delta_{t}:=f(x_{t})-f_{*}$, where $f_{*}$ is any
valid lower bound for $f$.

######  Theorem 4.5.

If $f$ is $L$-smooth and satisfies assumptions (1’), (2) and (3). With
probability at least $1-\delta$, the iterate sequence $(x_{t})_{t\geq 1}$
output by AdaGrad-Norm (Algorithm 4) satisfies

$\displaystyle\frac{1}{T}\sum_{t=1}^{T}\left\lVert\nabla
f(x_{t})\right\rVert^{2}$ $\displaystyle\leq g(\delta)\cdot
O\left(\frac{\sigma}{\sqrt{T}}+\frac{r(\delta)}{T}\right).$

where

$\displaystyle g(\delta)$
$\displaystyle:=O\left(\Delta_{1}+c(\delta)\sqrt{\log\frac{T}{\delta}}+L\log\left(\sigma\sqrt{T}+r(\delta)\right)\right)$
$\displaystyle c(\delta)$
$\displaystyle:=O\left(\sigma^{3}\log\left(\frac{1}{\delta}\right)+\sigma\log\left(1+\sigma^{2}T+\sigma^{2}\log\frac{1}{\delta}\right)+\sigma\log\left(\sigma\sqrt{T}+r(\delta)\right)\right),\text{
and }$ $\displaystyle r(\delta)$
$\displaystyle:=O(\Delta_{1}+\sigma^{2}\log\frac{1}{\delta}+L\log L)$

are polylog terms.

The next theorem show the first convergence result in high-probability for
vanilla AdaGrad in the non-convex regime.

######  Theorem 4.6.

If $f$ is $L$-smooth and satisfies assumptions (1’), (2) and (3). With
probability at least $1-\delta$, the iterate sequence $(x_{t})_{t\geq 1}$
output by AdaGrad (Algorithm 5) satisfies

$\displaystyle\frac{1}{T}\sum_{t=1}^{T}\left\|\nabla f(x_{t})\right\|_{1}^{2}$
$\displaystyle\leq g(\delta)\cdot
O\left(\frac{\left\|\sigma\right\|_{1}}{\sqrt{T}}+\frac{r(\delta)}{T}\right),$

where

$\displaystyle g(\delta)$
$\displaystyle:=O\left(\Delta_{1}+\left(d\sigma_{\max}+\sum_{i=1}^{d}c_{i}(\delta)\right)\sqrt{\log\frac{dT}{\delta}}+dL\log\left(\left\|\sigma\right\|_{1}\sqrt{T}+r(\delta)\right)\right),$
$\displaystyle c_{i}(\delta)$
$\displaystyle:=O\left(\sigma_{i}^{3}\log\left(\frac{d}{\delta}\right)+\sigma_{i}\log\left(1+\sigma_{i}^{2}T+\sigma_{i}^{2}\log\frac{d}{\delta}\right)+\left\|\sigma\right\|_{1}\log\left(\left\|\sigma\right\|_{1}\sqrt{T}+r(\delta)\right)\right),\text{
and }$ $\displaystyle r(\delta)$
$\displaystyle:=O\left(\Delta_{1}+\left\|\sigma^{2}\right\|_{1}\log\left(\frac{d}{\delta}\right)+\left\|\sigma\right\|_{1}\sqrt{\log\frac{d}{\delta}}+Ld\log
L\right),$

are polylog terms.

Both of these results are adaptive to noise: the rate
$\tilde{O}\left(\frac{1}{\sqrt{T}}\right)$ will improve to
$\tilde{O}\left(\frac{1}{T}\right)$ as the noise $\sigma$ approaches $0$.
Furthermore, these results hold regardless of how $\eta$ and $b_{0}$ is set.

#### Analysis overview.

The first key new technique is unlike prior works, we do not use the division
by the step size, which makes the analysis of AdaGrad-Norm and AdaGrad
virtually the same. We can thus focus on AdaGrad-Norm. To obtain a high
probability bound, our analysis of AdaGrad-Norm utilizes the same martingale
concentration technique as presented throughout this paper to bound the error
terms $\eta_{t}\left\langle\nabla f(x_{t}),\xi_{t}\right\rangle$. However, the
step size $\eta_{t}=\frac{\eta}{b_{t}}$ now has a dependency on the randomness
at time $t$ due to $b_{t}$, preventing us from applying Lemma 2.2. To
circumvent this, inspired by Ward et al. (2019), we introduce a proxy step
size $a_{t}:=b_{t-1}^{2}+\left\lVert\nabla f(x_{t})\right\rVert^{2}$ that
replaces the stochastic gradient with the true gradient at time $t$ for
analysis purposes. Using that along with standard smoothness analysis, we
obtain:

######  Lemma 4.7.

For $t\geq 1$, let $\xi_{t}=\widehat{\nabla}f(x_{t})-\nabla f(x_{t})$,
$a_{t}^{2}:=b_{t-1}^{2}+\left\lVert\nabla f(x_{t})\right\rVert^{2}$, and
$M_{t}=\max_{i\leq t}\left\|\xi_{i}\right\|$, then we have

$\displaystyle\sum_{t=1}^{T}\frac{\left\lVert\nabla
f(x_{t})\right\rVert^{2}}{b_{t}}$
$\displaystyle\leq\frac{\Delta_{1}}{\eta}+\frac{M_{T}}{2}\left[\sum_{t=1}^{T}\frac{\left\lVert\nabla
f(x_{t})\right\rVert^{2}}{a_{t}^{2}}+\sum_{t=1}^{T}\frac{\left\lVert\xi_{t}\right\rVert^{2}}{b_{t}^{2}}\right]-\sum_{t=1}^{T}\frac{1}{a_{t}}\left\langle\nabla
f(x_{t}),\xi_{t}\right\rangle+\sum_{t=1}^{T}\frac{L\eta}{2b_{t}^{2}}\left\lVert\widehat{\nabla}f(x_{t})\right\rVert^{2}.$

Now, the randomness at time $t$ of the error term
$\frac{1}{a_{t}}\left\langle\nabla f(x_{t}),\xi_{t}\right\rangle$ only depends
on $\xi_{t}$, which follows a sub-Gaussian distribution with mean $0$. Hence,
we can utilize our previous techniques to bound
$-\sum_{t=1}^{T}\frac{1}{a_{t}}\left\langle\nabla
f(x_{t}),\xi_{t}\right\rangle$ with high probability. Comparing to the
analysis in expectation from Ward et al. (2019), terms like
$\sum_{t=1}^{T}\frac{\left\lVert\nabla f(x_{t})\right\rVert^{2}}{a_{t}^{2}}$
must be handled more carefully to obtain a high probability bound. A bound for
$M_{T}$ has also been derived in previous works by Li and Orabona (2020); Liu
et al. (2022). Combining with Lemma 4.7, we obtain the following lemma.

######  Lemma 4.8.

With probability at least $1-2\delta$, we have

$\displaystyle\sum_{t=1}^{T}\frac{\left\lVert\nabla
f(x_{t})\right\rVert^{2}}{b_{t}}$
$\displaystyle\leq\frac{\Delta_{1}}{\eta}+\sigma\sqrt{\log\frac{T}{\delta}}\left[8\log\left(\frac{b_{T}}{b_{0}}\right)+5\sum_{t=1}^{T}\frac{\left\lVert\xi_{t}\right\rVert^{2}}{b_{t}^{2}}\right]+\sigma\sqrt{\log\frac{1}{\delta}}+L\eta\log\frac{b_{T}}{b_{0}}.$

Since, $\sum_{t=1}^{T}\frac{\left\lVert\nabla
f(x_{t})\right\rVert^{2}}{b_{t}}\geq\frac{1}{b_{T}}\sum_{t=1}^{T}\left\lVert\nabla
f(x_{t})\right\rVert^{2}$, it suffices to bound $b_{T}$ and
$\sum_{t=1}^{T}\frac{\left\lVert\xi_{t}\right\rVert^{2}}{b_{t}^{2}}$ from this
point on (see Lemma D.1 and Lemma D.6). The analysis for these terms utilize
similar martingale techniques throughout this paper, where the details are
deferred to Section D of the Appendix. For the coordinate version of AdaGrad,
since our techniques only rely on addition and scalar multiplication, we can
(with some effort) generalize our technique to the standard per-coordinate
AdaGrad algorithm. The full proofs for vanilla AdaGrad are presented in
Section E of the Appendix.

##  5 Conclusion

In this work, we present a generic approach to prove high probability
convergence of stochastic gradient methods under sub-Gaussian noise. In the
convex case, we show high probability bounds for stochastic and accelerated
stochastic mirror descent that depend on the distance from the initial
solution to the optimal solution and do not require the bounded domain or
bounded Bregman divergence assumptions. In the non-convex case, we apply the
same approach and obtain a high probability bound for SGD that improves over
existing works. We also show that the boundedness of the gradients can be
removed when showing high probability convergence of AdaGrad-Norm. Finally, we
show that our analysis for AdaGrad-Norm can be extended to the standard per-
coordinate AdaGrad algorithm to obtain one of the first high probability
convergence result for standard AdaGrad.

For future work, it would be interesting to see whether our method can be
applied to analyze AdaGrad-Norm and/or AdaGrad in the convex setting without
restrictive assumptions. Extending this approach to the heavy tail setting and
finding its applications in other problems are some of the potential future
directions.

## References

  * Chung and Lu (2006) Fan Chung and Linyuan Lu.  Concentration inequalities and martingale inequalities: a survey.  _Internet mathematics_ , 3(1):79–127, 2006.
  * Cutkosky and Mehta (2021) Ashok Cutkosky and Harsh Mehta.  High-probability bounds for non-convex stochastic optimization with heavy tails.  _Advances in Neural Information Processing Systems_ , 34:4883–4895, 2021.
  * Davis et al. (2021) Damek Davis, Dmitriy Drusvyatskiy, Lin Xiao, and Junyu Zhang.  From low probability to high confidence in stochastic convex optimization.  _Journal of machine learning research_ , 22(49), 2021.
  * Défossez et al. (2022) Alexandre Défossez, Léon Bottou, Francis Bach, and Nicolas Usunier.  A simple convergence proof of adam and adagrad.  _Transactions on Machine Learning Research_ , 2022.
  * Duchi et al. (2011) John Duchi, Elad Hazan, and Yoram Singer.  Adaptive subgradient methods for online learning and stochastic optimization.  _Journal of machine learning research_ , 12(7), 2011.
  * Dvurechensky and Gasnikov (2016) Pavel Dvurechensky and Alexander Gasnikov.  Stochastic intermediate gradient method for convex problems with stochastic inexact oracle.  _Journal of Optimization Theory and Applications_ , 171(1):121–145, 2016.
  * Ene et al. (2021) Alina Ene, Huy L Nguyen, and Adrian Vladu.  Adaptive gradient methods for constrained convex optimization and variational inequalities.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 35, pages 7314–7321, 2021.
  * Faw et al. (2022) Matthew Faw, Isidoros Tziotis, Constantine Caramanis, Aryan Mokhtari, Sanjay Shakkottai, and Rachel Ward.  The power of adaptivity in sgd: Self-tuning step sizes with unbounded gradients and affine variance.  _arXiv preprint arXiv:2202.05791_ , 2022.
  * Freedman (1975) David A Freedman.  On tail probabilities for martingales.  _the Annals of Probability_ , pages 100–118, 1975.
  * Gorbunov et al. (2020) Eduard Gorbunov, Marina Danilova, and Alexander Gasnikov.  Stochastic optimization with heavy-tailed noise via accelerated gradient clipping.  _Advances in Neural Information Processing Systems_ , 33:15042–15053, 2020.
  * Harvey et al. (2019) Nicholas JA Harvey, Christopher Liaw, Yaniv Plan, and Sikander Randhawa.  Tight analyses for non-smooth stochastic gradient descent.  In _Conference on Learning Theory_ , pages 1579–1613. PMLR, 2019\.
  * Hazan and Kale (2014) Elad Hazan and Satyen Kale.  Beyond the regret minimization barrier: optimal algorithms for stochastic strongly-convex optimization.  _The Journal of Machine Learning Research_ , 15(1):2489–2512, 2014.
  * Juditsky et al. (2011) Anatoli Juditsky, Arkadi Nemirovski, and Claire Tauvel.  Solving variational inequalities with stochastic mirror-prox algorithm.  _Stochastic Systems_ , 1(1):17–58, 2011.
  * Kakade and Tewari (2008) Sham M Kakade and Ambuj Tewari.  On the generalization ability of online strongly convex programming algorithms.  _Advances in Neural Information Processing Systems_ , 21, 2008.
  * Kavis et al. (2021) Ali Kavis, Kfir Yehuda Levy, and Volkan Cevher.  High probability bounds for a class of nonconvex algorithms with adagrad stepsize.  In _International Conference on Learning Representations_ , 2021.
  * Lan (2012) Guanghui Lan.  An optimal method for stochastic composite optimization.  _Mathematical Programming_ , 133(1):365–397, 2012\.
  * Lan (2020) Guanghui Lan.  _First-order and stochastic optimization methods for machine learning_.  Springer, 2020.
  * Li and Liu (2022) Shaojie Li and Yong Liu.  High probability guarantees for nonconvex stochastic gradient descent with heavy tails.  In _International Conference on Machine Learning_ , pages 12931–12963. PMLR, 2022.
  * Li and Orabona (2019) Xiaoyu Li and Francesco Orabona.  On the convergence of stochastic gradient descent with adaptive stepsizes.  In _The 22nd International Conference on Artificial Intelligence and Statistics_ , pages 983–992. PMLR, 2019.
  * Li and Orabona (2020) Xiaoyu Li and Francesco Orabona.  A high probability analysis of adaptive sgd with momentum.  _arXiv preprint arXiv:2007.14294_ , 2020.
  * Liu et al. (2022) Zijian Liu, Ta Duy Nguyen, Alina Ene, and Huy L Nguyen.  On the convergence of adagrad on $\mathbb{R}^{d}$: Beyond convexity, non-asymptotic rate and acceleration.  _arXiv preprint arXiv:2209.14827_ , 2022.
  * Madden et al. (2020) Liam Madden, Emiliano Dall’Anese, and Stephen Becker.  High probability convergence and uniform stability bounds for nonconvex stochastic gradient descent.  _arXiv preprint arXiv:2006.05610_ , 2020.
  * Nazin et al. (2019) Alexander V Nazin, Arkadi S Nemirovsky, Alexandre B Tsybakov, and Anatoli B Juditsky.  Algorithms of robust stochastic optimization based on mirror descent method.  _Automation and Remote Control_ , 80(9):1607–1627, 2019.
  * Nemirovski et al. (2009) Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro.  Robust stochastic approximation approach to stochastic programming.  _SIAM Journal on optimization_ , 19(4):1574–1609, 2009.
  * Rakhlin et al. (2011) Alexander Rakhlin, Ohad Shamir, and Karthik Sridharan.  Making gradient descent optimal for strongly convex stochastic optimization.  _arXiv preprint arXiv:1109.5647_ , 2011.
  * Vershynin (2018) Roman Vershynin.  _High-dimensional probability: An introduction with applications in data science_ , volume 47.  Cambridge university press, 2018.
  * Ward et al. (2019) Rachel Ward, Xiaoxia Wu, and Leon Bottou.  Adagrad stepsizes: Sharp convergence over nonconvex landscapes.  In _International Conference on Machine Learning_ , pages 6677–6686. PMLR, 2019.
  * Zhang et al. (2020) Jingzhao Zhang, Sai Praneeth Karimireddy, Andreas Veit, Seungyeon Kim, Sashank Reddi, Sanjiv Kumar, and Suvrit Sra.  Why are adaptive methods good for attention models?  _Advances in Neural Information Processing Systems (NeurIPS)_ , 33:15383–15393, 2020.

##  Appendix A Proof of Lemma 2.2

To prove Lemma 2.2, we will prove the following statement.

######  Lemma A.1.

For any $a\geq 0$, $0\leq b\leq\frac{1}{2\sigma}$ and an $\sigma$-sub-Gaussian
random variable $X$,

$\mathbb{\mathbb{E}}\left[1+b^{2}X^{2}+\sum_{i=2}^{\infty}\frac{1}{i!}\left(aX+b^{2}X^{2}\right)^{i}\right]\leq\exp\left(3\left(a^{2}+b^{2}\right)\sigma^{2}\right).$

Especially, when $b=0$, we have

$\mathbb{\mathbb{E}}\left[1+\sum_{i=2}^{\infty}\frac{1}{i!}\left(aX\right)^{i}\right]\leq\exp\left(2a^{2}\sigma^{2}\right).$

###### Proof of Lemma A.1.

Consider two cases either $a\geq 1/(2\sigma)$ or $a\leq 1/(2\sigma)$. First
suppose $a\geq 1/(2\sigma)$. We use the inequality
$uv\leq\frac{u^{2}}{4}+v^{2}$ here to first obtain

$\displaystyle\left(aX+b^{2}X^{2}\right)^{i}$
$\displaystyle\leq\left|aX+b^{2}X^{2}\right|^{i}\leq\left(a\left|X\right|+b^{2}X^{2}\right)^{i}\leq\left(\frac{1}{4\sigma^{2}}X^{2}+a^{2}\sigma^{2}+b^{2}X^{2}\right)^{i}.$

Thus, we have

$\displaystyle\mathbb{\mathbb{E}}\left[1+b^{2}X^{2}+\sum_{i=2}^{\infty}\frac{1}{i!}\left(aX+b^{2}X^{2}\right)^{i}\right]$
$\displaystyle\leq\mathbb{\mathbb{E}}\left[1+b^{2}X^{2}+\sum_{i=2}^{\infty}\frac{1}{i!}\left(\frac{1}{4\sigma^{2}}X^{2}+a^{2}\sigma^{2}+b^{2}X^{2}\right)^{i}\right]$
$\displaystyle=\mathbb{\mathbb{E}}\left[b^{2}X^{2}+\exp\left(\left(\frac{1}{4\sigma^{2}}+b^{2}\right)X^{2}+a^{2}\sigma^{2}\right)-\left(\frac{1}{4\sigma^{2}}+b^{2}\right)X^{2}-a^{2}\sigma^{2}\right]$
$\displaystyle=\mathbb{\mathbb{E}}\left[\exp\left(\left(\frac{1}{4\sigma^{2}}+b^{2}\right)X^{2}+a^{2}\sigma^{2}\right)-\frac{1}{4\sigma^{2}}X^{2}-a^{2}\sigma^{2}\right]$
$\displaystyle\leq\exp\left(\left(\frac{1}{4\sigma^{2}}+b^{2}\right)\sigma^{2}+a^{2}\sigma^{2}\right)$
$\displaystyle\leq\exp\left(2a^{2}\sigma^{2}+b^{2}\sigma^{2}\right)$
$\displaystyle\leq\exp\left(3\left(a^{2}+b^{2}\right)\sigma^{2}\right).$

Next, let $c=\max(a,b)\leq 1/(2\sigma)$. We have

$\displaystyle\mathbb{\mathbb{E}}\left[1+b^{2}X^{2}+\sum_{i=2}^{\infty}\frac{1}{i!}\left(aX+b^{2}X^{2}\right)^{i}\right]$
$\displaystyle=\mathbb{\mathbb{E}}\left[\exp\left(aX+b^{2}X^{2}\right)-aX\right]$
$\displaystyle\leq\mathbb{\mathbb{E}}\left[\left(aX+\exp\left(a^{2}X^{2}\right)\right)\exp\left(b^{2}X^{2}\right)-aX\right]$
$\displaystyle=\mathbb{\mathbb{E}}\left[\exp\left(\left(a^{2}+b^{2}\right)X^{2}\right)+aX\left(\exp\left(b^{2}X^{2}\right)-1\right)\right]$
$\displaystyle\leq\mathbb{\mathbb{E}}\left[\exp\left(\left(a^{2}+b^{2}\right)X^{2}\right)+c\left|X\right|\left(\exp\left(c^{2}X^{2}\right)-1\right)\right]$
$\displaystyle\leq\mathbb{\mathbb{E}}\left[\exp\left(\left(a^{2}+b^{2}\right)X^{2}\right)+\exp\left(2c^{2}X^{2}\right)-1\right]$
$\displaystyle\leq\mathbb{\mathbb{E}}\left[\exp\left(\left(a^{2}+b^{2}+2c^{2}\right)X^{2}\right)\right]$
$\displaystyle\leq\exp\left(\left(a^{2}+b^{2}+2c^{2}\right)\sigma^{2}\right)$
$\displaystyle\leq\exp\left(3\left(a^{2}+b^{2}\right)\sigma^{2}\right).$

In the first inequality, we use the inequality $e^{x}-x\leq e^{x^{2}}\forall
x$. In the third inequality, we use $x\left(e^{x^{2}}-1\right)\leq
e^{2x^{2}}-1\ \forall x$. This inequality can be proved with the Taylor
expansion.

$\displaystyle x\left(e^{x^{2}}-1\right)$
$\displaystyle=\sum_{i=1}^{\infty}\frac{1}{i!}x^{2i+1}$
$\displaystyle\leq\sum_{i=1}^{\infty}\frac{1}{i!}\frac{x^{2i}+x^{2i+2}}{2}$
$\displaystyle=\frac{x^{2}}{2}+\sum_{i=2}^{\infty}\left(\frac{1+i}{2i!}\right)x^{2i}$
$\displaystyle\leq\frac{x^{2}}{2}+\sum_{i=2}^{\infty}\left(\frac{2^{i}}{i!}\right)x^{2i}$
$\displaystyle\leq e^{2x^{2}}-1.$

The case when $b=0$ simply follows from the above proof. ∎

###### Proof of Lemma 2.2.

Using Taylor expansion of $e^{x}$ and the fact that
$\mathbb{\mathbb{E}}\left[X\right]=0$ we have

$\displaystyle\mathbb{\mathbb{E}}\left[\exp\left(\left\langle
a,X\right\rangle+b^{2}\left\|X\right\|^{2}\right)\right]$
$\displaystyle=\mathbb{\mathbb{E}}\left[1+\left\langle
a,X\right\rangle+b^{2}\left\|X\right\|^{2}+\sum_{i=2}^{\infty}\frac{1}{i!}\left(\left\langle
a,X\right\rangle+b^{2}\left\|X\right\|^{2}\right)^{i}\right]$
$\displaystyle=\mathbb{\mathbb{E}}\left[1+b^{2}\left\|X\right\|^{2}+\sum_{i=2}^{\infty}\frac{1}{i!}\left(\left\langle
a,X\right\rangle+b^{2}\left\|X\right\|^{2}\right)^{i}\right]$
$\displaystyle\leq\mathbb{\mathbb{E}}\left[1+b^{2}\left\|X\right\|^{2}+\sum_{i=2}^{\infty}\frac{1}{i!}\left(\left\|a\right\|_{*}\left\|X\right\|+b^{2}\left\|X\right\|^{2}\right)^{i}\right]$

where for the last line we use Cauchy-Schwartz to obtain $\left\langle
a,X\right\rangle\leq\left\|a\right\|_{*}\left\|X\right\|$. Now applying Lemma
A.1, we obtain

$\displaystyle\mathbb{\mathbb{E}}\left[\exp\left(\left\langle
a,X\right\rangle+b^{2}\left\|X\right\|^{2}\right)\right]$
$\displaystyle\leq\exp\left(3\left(\left\|a\right\|_{*}^{2}+b^{2}\right)\sigma^{2}\right).$

Similarly, we obtain the corresponding bound for the case $b=0$. ∎

##  Appendix B Missing Proofs from Section 3

###  B.1 Stochastic Mirror Descent

###### Proof of Lemma (3.2).

By the optimality condition, we have

$\left\langle\eta_{t}\widehat{\nabla}f(x_{t})+\nabla_{x}\mathbf{D}_{\psi}\left(x_{t+1},x_{t}\right),x^{*}-x_{t+1}\right\rangle\geq
0$

and thus

$\left\langle\eta_{t}\widehat{\nabla}f(x_{t}),x_{t+1}-x^{*}\right\rangle\leq\left\langle\nabla_{x}\mathbf{D}_{\psi}\left(x_{t+1},x_{t}\right),x^{*}-x_{t+1}\right\rangle.$

Note that

$\displaystyle\left\langle\nabla_{x}\mathbf{D}_{\psi}\left(x_{t+1},x_{t}\right),x^{*}-x_{t+1}\right\rangle$
$\displaystyle=\left\langle\nabla\psi\left(x_{t+1}\right)-\nabla\psi\left(x_{t}\right),x^{*}-x_{t+1}\right\rangle$
$\displaystyle=\mathbf{D}_{\psi}\left(x^{*},x_{t}\right)-\mathbf{D}_{\psi}\left(x_{t+1},x_{t}\right)-\mathbf{D}_{\psi}\left(x^{*},x_{t+1}\right),$

and thus

$\displaystyle\eta_{t}\left\langle\widehat{\nabla}f(x_{t}),x_{t+1}-x^{*}\right\rangle$
$\displaystyle\leq\mathbf{D}_{\psi}\left(x^{*},x_{t}\right)-\mathbf{D}_{\psi}\left(x^{*},x_{t+1}\right)-\mathbf{D}_{\psi}\left(x_{t+1},x_{t}\right)$
$\displaystyle\leq\mathbf{D}_{\psi}\left(x^{*},x_{t}\right)-\mathbf{D}_{\psi}\left(x^{*},x_{t+1}\right)-\frac{1}{2}\left\|x_{t+1}-x_{t}\right\|^{2},$

where we have used that
$\mathbf{D}_{\psi}\left(x_{t+1},x_{t}\right)\geq\frac{1}{2}\left\|x_{t+1}-x_{t}\right\|^{2}$
by the strong convexity of $\psi$.

By convexity, we have

$f\left(x_{t}\right)-f\left(x^{*}\right)\leq\left\langle\nabla
f\left(x_{t}\right),x_{t}-x^{*}\right\rangle=\left\langle\xi_{t},x^{*}-x_{t}\right\rangle+\left\langle\widehat{\nabla}f\left(x_{t}\right),x_{t}-x^{*}\right\rangle.$

Combining the two inequalities, we obtain

$\displaystyle\eta_{t}\left(f\left(x_{t}\right)-f\left(x^{*}\right)\right)+\mathbf{D}_{\psi}\left(x^{*},x_{t+1}\right)-\mathbf{D}_{\psi}\left(x^{*},x_{t}\right)$
$\displaystyle\leq\eta_{t}\left\langle\xi_{t},x^{*}-x_{t}\right\rangle+\eta_{t}\left\langle\widehat{\nabla}f(x_{t}),x_{t}-x_{t+1}\right\rangle-\frac{1}{2}\left\|x_{t+1}-x_{t}\right\|^{2}$
$\displaystyle\leq\eta_{t}\left\langle\xi_{t},x^{*}-x_{t}\right\rangle+\frac{\eta_{t}^{2}}{2}\left\|\widehat{\nabla}f(x_{t})\right\|_{*}^{2}.$

Using the triangle inequality and the bounded gradient assumption
$\left\|\nabla f(x)\right\|_{*}\leq G$ , we obtain

$\left\|\widehat{\nabla}f(x_{t})\right\|_{*}^{2}=\left\|\xi_{t}+\nabla
f(x_{t})\right\|_{*}^{2}\leq 2\left\|\xi_{t}\right\|_{*}^{2}+2\left\|\nabla
f(x_{t})\right\|_{*}^{2}\leq
2\left(\left\|\xi_{t}\right\|_{*}^{2}+G^{2}\right).$

Thus

$\eta_{t}\left(f\left(x_{t}\right)-f\left(x^{*}\right)\right)+\mathbf{D}_{\psi}\left(x^{*},x_{t+1}\right)-\mathbf{D}_{\psi}\left(x^{*},x_{t}\right)\leq\eta_{t}\left\langle\xi_{t},x^{*}-x_{t}\right\rangle+\eta_{t}^{2}\left(\left\|\xi_{t}\right\|_{*}^{2}+G^{2}\right)$

as needed. ∎

###### Proof of Corollary 3.4.

Let

$K=3\sigma^{2}\sum_{t=1}^{T}w_{t}\eta_{t}^{2}+\log\left(\frac{1}{\delta}\right).$

By Theorem 3.3 and Markov’s inequality, we have

$\displaystyle\Pr\left[S_{1}\geq K\right]$
$\displaystyle\leq\Pr\left[\exp\left(S_{1}\right)\geq\exp\left(K\right)\right]$
$\displaystyle\leq\exp\left(-K\right)\mathbb{\mathbb{E}}\left[\exp\left(S_{1}\right)\right]$
$\displaystyle\leq\exp\left(-K\right)\exp\left(3\sigma^{2}\sum_{t=1}^{T}w_{t}\eta_{t}^{2}\right)$
$\displaystyle=\delta.$

Note that since $v_{t}+w_{t}\leq w_{t-1}$

$\displaystyle S_{1}$
$\displaystyle=\sum_{t=1}^{T}Z_{t}=\sum_{t=1}^{T}w_{t}\eta_{t}\left(f\left(x_{t}\right)-f\left(x^{*}\right)\right)-G^{2}\sum_{t=1}^{T}w_{t}\eta_{t}^{2}+\sum_{t=1}^{T}\left(w_{t}\mathbf{D}_{\psi}\left(x^{*},x_{t+1}\right)-(v_{t}+w_{t})\mathbf{D}_{\psi}\left(x^{*},x_{t}\right)\right)$
$\displaystyle\geq\sum_{t=1}^{T}w_{t}\eta_{t}\left(f\left(x_{t}\right)-f\left(x^{*}\right)\right)-G^{2}\sum_{t=1}^{T}w_{t}\eta_{t}^{2}+\sum_{t=1}^{T}\left(w_{t}\mathbf{D}_{\psi}\left(x^{*},x_{t+1}\right)-w_{t-1}\mathbf{D}_{\psi}\left(x^{*},x_{t}\right)\right)$
$\displaystyle=\sum_{t=1}^{T}w_{t}\eta_{t}\left(f\left(x_{t}\right)-f\left(x^{*}\right)\right)-G^{2}\sum_{t=1}^{T}w_{t}\eta_{t}^{2}+w_{T}\mathbf{D}_{\psi}\left(x^{*},x_{T+1}\right)-w_{0}\mathbf{D}_{\psi}\left(x^{*},x_{1}\right).$

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

$\sum_{t=1}^{T}w_{t}\eta_{t}\left(f\left(x_{t}\right)-f\left(x^{*}\right)\right)+w_{T}\mathbf{D}_{\psi}\left(x^{*},x_{T+1}\right)\leq
w_{0}\mathbf{D}_{\psi}\left(x^{*},x_{1}\right)+\left(G^{2}+3\sigma^{2}\right)\sum_{t=1}^{T}w_{t}\eta_{t}^{2}+\log\left(\frac{1}{\delta}\right).$

∎

With the above result in hand, we complete the convergence analysis by showing
how to define the sequence $\left\\{w_{t}\right\\}$ with the desired
properties. Theorem 3.1 can be obtained from the two following corollaries.

######  Corollary B.1.

Suppose we run the Stochastic Mirror Descent algorithm with fixed step sizes
$\eta_{t}=\frac{\eta}{\sqrt{T}}$. Let $w_{T}=\frac{1}{12\sigma^{2}\eta^{2}}$
and $w_{t-1}=w_{t}+\frac{6}{T}\sigma^{2}\eta^{2}w_{t}^{2}$ for all $1\leq
t\leq T$. The sequence $\left\\{w_{t}\right\\}$ satisfies the conditions
required by Corollary 3.4. By Corollary 3.4, for any $\delta>0$, the following
events hold with probability at least $1-\delta$:
$\mathbf{D}_{\psi}\left(x^{*},x_{T+1}\right)\leq
2\mathbf{D}_{\psi}\left(x^{*},x_{1}\right)+12\left(G^{2}+\sigma^{2}\left(1+\log\left(\frac{1}{\delta}\right)\right)\right)\eta^{2}$,
and

$\displaystyle\frac{1}{T}\sum_{t=1}^{T}\left(f\left(x_{t}\right)-f\left(x^{*}\right)\right)$
$\displaystyle\leq\frac{1}{\sqrt{T}}\frac{2\mathbf{D}_{\psi}\left(x^{*},x_{1}\right)}{\eta}+\frac{12}{\sqrt{T}}\left(G^{2}+\sigma^{2}\left(1+\log\left(\frac{1}{\delta}\right)\right)\right)\eta.$

In particular, setting
$\eta_{t}=\sqrt{\frac{\mathbf{D}_{\psi}\left(x^{*},x_{1}\right)}{6\left(G^{2}+\sigma^{2}\left(1+\log\left(\frac{1}{\delta}\right)\right)\right)T}}$
we obtain the first case of Theorem 3.1.

###### Proof of Corollary (B.1) .

Recall from Corollary 3.4 that the sequence $\left\\{w_{t}\right\\}$ needs to
satisfy the following conditions for all $1\leq t\leq T$:

$\displaystyle w_{t}+6\sigma^{2}\eta_{t}^{2}$ $\displaystyle w_{t}^{2}\leq
w_{t-1}$ $\displaystyle w_{t}\eta_{t}^{2}$
$\displaystyle\leq\frac{1}{4\sigma^{2}}.$

Let $C=6\sigma^{2}\eta^{2}$. We set
$w_{T}=\frac{1}{C+6\sigma^{2}\eta^{2}}=\frac{1}{2C}$. For $1\leq t\leq T$, we
set $w_{t}$ so that the first condition holds with equality

$w_{t-1}=w_{t}+6\sigma^{2}w_{t}^{2}\eta_{t}^{2}=w_{t}+\frac{6}{T}\sigma^{2}\eta^{2}w_{t}^{2}.$

We can show by induction that, for every $1\leq t\leq T$, we have

$w_{t}\leq\frac{1}{C+\frac{6}{T}\sigma^{2}\eta^{2}t}.$

The base case $t=T$ follows from the definition of $w_{T}$. Consider $1\leq
t\leq T$. Using the definition of $w_{t-1}$ and the inductive hypothesis, we
obtain

$\displaystyle w_{t-1}$
$\displaystyle=w_{t}+\frac{6}{T}\sigma^{2}\eta^{2}w_{t}^{2}$
$\displaystyle\leq\frac{1}{C+\frac{6}{T}\sigma^{2}\eta^{2}t}+\frac{6\sigma^{2}\eta^{2}}{T\left(C+\frac{6}{T}\sigma^{2}\eta^{2}t\right)^{2}}$
$\displaystyle\leq\frac{1}{C+\frac{6}{T}\sigma^{2}\eta^{2}t}+\frac{\left(C+\frac{6}{T}\sigma^{2}\eta^{2}t\right)-\left(C+\frac{6}{T}\sigma^{2}\eta^{2}(t-1)\right)}{\left(C+\frac{6}{T}\sigma^{2}\eta^{2}\left(t-1\right)\right)\left(C+\frac{6}{T}\sigma^{2}\eta^{2}t\right)}$
$\displaystyle=\frac{1}{C+\frac{6}{T}\sigma^{2}\eta^{2}\left(t-1\right)}$

as needed.

Using this fact, we now show that $\left\\{w_{t}\right\\}$ satisfies the
second condition. Indeed, for every $1\leq t\leq T$, we have

$w_{t}\eta_{t}^{2}=w_{t}\frac{\eta^{2}}{T}\leq\frac{\eta^{2}}{6\sigma^{2}\eta^{2}t}=\frac{1}{6\sigma^{2}}.$

Thus, by Corollary 3.4, with probability $\geq 1-\delta$, we have

$\displaystyle\sum_{t=1}^{T}w_{t}\eta_{t}\left(f\left(x_{t}\right)-f\left(x^{*}\right)\right)+w_{T}\mathbf{D}_{\psi}\left(x^{*},x_{T+1}\right)$
$\displaystyle\leq
w_{0}\mathbf{D}_{\psi}\left(x^{*},x_{1}\right)+\left(G^{2}+3\sigma^{2}\right)\sum_{t=1}^{T}w_{t}\eta_{t}^{2}+\log\left(\frac{1}{\delta}\right).$

Note that $w_{T}=\frac{1}{2C}$ and $\frac{1}{2C}\leq w_{t}\leq\frac{1}{C}$ for
all $0\leq t\leq T$. Thus we obtain

$\displaystyle\frac{\eta}{\sqrt{T}}\sum_{t=1}^{T}\left(f\left(x_{t}\right)-f\left(x^{*}\right)\right)+\mathbf{D}_{\psi}\left(x^{*},x_{T+1}\right)$
$\displaystyle\leq
2\mathbf{D}_{\psi}\left(x^{*},x_{1}\right)+2\left(G^{2}+3\sigma^{2}\right)\eta^{2}+2C\log\left(\frac{1}{\delta}\right)$
$\displaystyle=2\mathbf{D}_{\psi}\left(x^{*},x_{1}\right)+2\left(G^{2}+3\sigma^{2}\right)\eta^{2}+12\sigma^{2}\log\left(\frac{1}{\delta}\right)\eta^{2}$
$\displaystyle\leq
2\mathbf{D}_{\psi}\left(x^{*},x_{1}\right)+12\left(G^{2}+\sigma^{2}\left(1+\log\left(\frac{1}{\delta}\right)\right)\right)\eta^{2}.$

Thus we have

$\frac{1}{T}\sum_{t=1}^{T}\left(f\left(x_{t}\right)-f\left(x^{*}\right)\right)\leq\frac{1}{\sqrt{T}}\left(\frac{2\mathbf{D}_{\psi}\left(x^{*},x_{1}\right)}{\eta}+12\left(G^{2}+\sigma^{2}\left(1+\log\left(\frac{1}{\delta}\right)\right)\right)\eta\right)$

and

$\mathbf{D}_{\psi}\left(x^{*},x_{T+1}\right)\leq
2\mathbf{D}_{\psi}\left(x^{*},x_{1}\right)+12\left(G^{2}+\sigma^{2}\left(1+\log\left(\frac{1}{\delta}\right)\right)\right)\eta^{2}.$

∎

The analysis extends to the setting where the $T$ is not known and we use the
step sizes $\eta_{t}=\frac{\eta}{\sqrt{t}}$.

######  Corollary B.2.

Suppose we run the Stochastic Mirror Descent algorithm with time-varying step
sizes $\eta_{t}=\frac{\eta}{\sqrt{t}}$. Let
$w_{T}=\frac{1}{12\sigma^{2}\eta^{2}\left(\sum_{t=1}^{T}\frac{1}{t}\right)}$
and $w_{t-1}=w_{t}+6\sigma^{2}\eta_{t}^{2}w_{t}^{2}$ for all $1\leq t\leq T$.
The sequence $\left\\{w_{t}\right\\}$ satisfies the conditions required by
Corollary 3.4. By Corollary 3.4, for any $\delta>0$, the following events hold
with probability at least $1-\delta$:
$\mathbf{D}_{\psi}\left(x^{*},x_{T+1}\right)\leq
2\mathbf{D}_{\psi}\left(x^{*},x_{1}\right)+12\left(G^{2}+\sigma^{2}\left(1+\log\left(\frac{1}{\delta}\right)\right)\right)\eta^{2}(1+\log
T)$, and

$\displaystyle\frac{1}{T}\sum_{t=1}^{T}\left(f\left(x_{t}\right)-f\left(x^{*}\right)\right)$
$\displaystyle\leq\frac{1}{\sqrt{T}}\frac{2\mathbf{D}_{\psi}\left(x^{*},x_{1}\right)}{\eta}+\frac{12}{\sqrt{T}}\left(G^{2}+\sigma^{2}\left(1+\log\left(\frac{1}{\delta}\right)\right)\right)\eta(1+\log
T).$

In particular, setting
$\eta_{t}=\sqrt{\frac{\mathbf{D}_{\psi}\left(x^{*},x_{1}\right)}{6\left(G^{2}+\sigma^{2}\left(1+\ln\left(\frac{1}{\delta}\right)\right)\right)t}}$
we obtain the second case of Theorem 3.1.

###### Proof of Corollary (B.2).

Recall from Corollary 3.4 that the sequence $\left\\{w_{t}\right\\}$ needs to
satisfy the following conditions for all $1\leq t\leq T$:

$\displaystyle w_{t}+6\sigma^{2}\eta_{t}^{2}$ $\displaystyle w_{t}^{2}\leq
w_{t-1}$ $\displaystyle w_{t}\eta_{t}^{2}$
$\displaystyle\leq\frac{1}{4\sigma^{2}}.$

Let $M_{t}=6\sigma^{2}\sum_{i=1}^{t}\eta_{i}^{2}$ and
$C=M_{T}=6\sigma^{2}\eta^{2}\left(\sum_{t=1}^{T}\frac{1}{t}\right)$. We set
$w_{T}=\frac{1}{C+M_{T}}$. For $1\leq t\leq T$, we set $w_{t}$ so that the
first condition holds with equality

$w_{t-1}=w_{t}+6\sigma^{2}\eta_{t}^{2}w_{t}^{2}.$

We can show by induction that, for every $1\leq t\leq T$, we have

$w_{t}\leq\frac{1}{C+M_{t}}.$

The base case $t=T$ follows from the definition of $w_{T}$. Consider $1\leq
t\leq T$. Using the definition of $w_{t}$ and the inductive hypothesis, we
obtain

$\displaystyle w_{t-1}$ $\displaystyle=w_{t}+6\sigma^{2}\eta_{t}^{2}w_{t}^{2}$
$\displaystyle\leq\frac{1}{C+M_{t}}+\frac{6\sigma^{2}\eta_{t}^{2}}{\left(C+M_{t}\right)^{2}}$
$\displaystyle\leq\frac{1}{C+M_{t}}+\frac{\left(C+M_{t}\right)-\left(C+M_{t-1}\right)}{\left(C+M_{t}\right)\left(C+M_{t-1}\right)}$
$\displaystyle=\frac{1}{C+M_{t-1}}$

as needed.

Using this fact, we now show that $\left\\{w_{t}\right\\}$ satisfies the
second condition. For every $1\leq t\leq T$, we have

$w_{t}\eta_{t}^{2}\leq\frac{\eta_{t}^{2}}{C}\leq\frac{\eta_{t}^{2}}{6\sigma^{2}\eta_{t}^{2}}=\frac{1}{6\sigma^{2}}$

as needed.

Thus, by Corollary 3.4, with probability $\geq 1-\delta$, we have

$\displaystyle\sum_{t=1}^{T}w_{t}\eta_{t}\left(f\left(x_{t}\right)-f\left(x^{*}\right)\right)+w_{T}\mathbf{D}_{\psi}\left(x^{*},x_{T+1}\right)$
$\displaystyle\leq
w_{0}\mathbf{D}_{\psi}\left(x^{*},x_{1}\right)+\left(G^{2}+3\sigma^{2}\right)\sum_{t=1}^{T}w_{t}\eta_{t}^{2}+\log\left(\frac{1}{\delta}\right).$

Note that $w_{T}=\frac{1}{2C}$ and $\frac{1}{2C}\leq w_{t}\leq\frac{1}{C}$ for
all $1\leq t\leq T$. Thus we obtain

$\frac{1}{2C}\eta_{T}\sum_{t=1}^{T}\left(f\left(x_{t}\right)-f\left(x^{*}\right)\right)+\frac{1}{2C}\mathbf{D}_{\psi}\left(x^{*},x_{T+1}\right)\leq\frac{1}{C}\mathbf{D}_{\psi}\left(x^{*},x_{1}\right)+\left(G^{2}+3\sigma^{2}\right)\frac{1}{C}\sum_{t=1}^{T}\eta_{t}^{2}+\log\left(\frac{1}{\delta}\right).$

Plugging in $\eta_{t}=\frac{\eta}{\sqrt{t}}$ and simplifying, we obtain

$\displaystyle\frac{\eta}{\sqrt{T}}\sum_{t=1}^{T}\left(f\left(x_{t}\right)-f\left(x^{*}\right)\right)+\mathbf{D}_{\psi}\left(x^{*},x_{T+1}\right)$
$\displaystyle\leq
2\mathbf{D}_{\psi}\left(x^{*},x_{1}\right)+\left(2G^{2}+6\sigma^{2}\right)\eta^{2}\left(\sum_{t=1}^{T}\frac{1}{t}\right)+2C\log\left(\frac{1}{\delta}\right)$
$\displaystyle=2\mathbf{D}_{\psi}\left(x^{*},x_{1}\right)+\left(2G^{2}+6\sigma^{2}\left(1+2\log\left(\frac{1}{\delta}\right)\right)\right)\eta^{2}\left(\sum_{t=1}^{T}\frac{1}{t}\right).$

Thus we have

$\frac{1}{T}\sum_{t=1}^{T}\left(f\left(x_{t}\right)-f\left(x^{*}\right)\right)\leq\frac{1}{\sqrt{T}}\left(\frac{2\mathbf{D}_{\psi}\left(x^{*},x_{1}\right)}{\eta}+\left(2G^{2}+6\sigma^{2}\left(1+2\log\left(\frac{1}{\delta}\right)\right)\right)\eta\left(\sum_{t=1}^{T}\frac{1}{t}\right)\right)$

and

$\mathbf{D}_{\psi}\left(x^{*},x_{T+1}\right)\leq
2\mathbf{D}_{\psi}\left(x^{*},x_{1}\right)+\left(2G^{2}+6\sigma^{2}\left(1+2\log\left(\frac{1}{\delta}\right)\right)\right)\eta^{2}\left(\sum_{t=1}^{T}\frac{1}{t}\right).$

∎

###  B.2 Accelerated Stochastic Mirror Descent

The convergence of Algorithm 2 is given in the following Theorem.

######  Theorem B.3.

Assume $f$ satisfies Assumptions (1), (2), (3) and condition (5), with
probability at least $1-\delta$,

(1) Setting
$\eta_{t}=\min\left\\{\frac{t}{4L},\frac{\sqrt{\mathbf{D}_{\psi}\left(x^{*},z_{0}\right)}t}{\sqrt{6}\sqrt{G^{2}+\sigma^{2}\left(1+\log\left(\frac{1}{\delta}\right)\right)}T^{3/2}}\right\\}$,
then $\mathbf{D}_{\psi}\left(x^{*},z_{T}\right)\leq
4\mathbf{D}_{\psi}\left(x^{*},z_{0}\right)$ and

$\displaystyle f\left(y_{T}\right)-f\left(x^{*}\right)$
$\displaystyle\leq\frac{16L\mathbf{D}_{\psi}\left(x^{*},z_{0}\right)}{T^{2}}+\frac{8\sqrt{6}}{\sqrt{T}}\sqrt{\mathbf{D}_{\psi}\left(x^{*},z_{0}\right)\left(G^{2}+\left(1+\log\left(\frac{1}{\delta}\right)\right)\sigma^{2}\right)}.$

(2) Setting
$\eta_{t}=\min\left\\{\frac{t}{4L},\frac{\sqrt{\mathbf{D}_{\psi}\left(x^{*},z_{0}\right)}}{\sqrt{6}\sqrt{G^{2}+\sigma^{2}\left(1+\log\left(\frac{1}{\delta}\right)\right)}t^{1/2}}\right\\}$,
then $\mathbf{D}_{\psi}\left(x^{*},z_{T}\right)\leq 2(2+\log
T)\mathbf{D}_{\psi}\left(x^{*},z_{0}\right)$ and

$\displaystyle f\left(y_{T}\right)-f\left(x^{*}\right)$
$\displaystyle\leq\frac{16L\mathbf{D}_{\psi}\left(x^{*},z_{0}\right)}{T^{2}}+\frac{4\sqrt{6}(2+\log
T)}{\sqrt{T}}\sqrt{\mathbf{D}_{\psi}\left(x^{*},z_{0}\right)\left(G^{2}+\left(1+\log\left(\frac{1}{\delta}\right)\right)\sigma^{2}\right)}.$

###### Proof of Lemma 3.5.

Starting with smoothness, we obtain

$\displaystyle f\left(y_{t}\right)$ $\displaystyle\leq
f\left(x_{t}\right)+\left\langle\nabla
f\left(x_{t}\right),y_{t}-x_{t}\right\rangle+G\left\|y_{t}-x_{t}\right\|+\frac{\beta}{2}\left\|y_{t}-x_{t}\right\|^{2}\
\forall x\in\mathcal{X}$ $\displaystyle=f\left(x_{t}\right)+\left\langle\nabla
f\left(x_{t}\right),y_{t-1}-x_{t}\right\rangle+\left\langle\nabla
f\left(x_{t}\right),y_{t}-y_{t-1}\right\rangle+G\left\|y_{t}-x_{t}\right\|+\frac{\beta}{2}\left\|y_{t}-x_{t}\right\|^{2}$
$\displaystyle=\left(1-\alpha_{t}\right)\underbrace{\left(f\left(x_{t}\right)+\left\langle\nabla
f\left(x_{t}\right),y_{t-1}-x_{t}\right\rangle\right)}_{\text{convexity}}+\alpha_{t}\underbrace{\left(f\left(x_{t}\right)+\left\langle\nabla
f\left(x_{t}\right),y_{t-1}-x_{t}\right\rangle\right)}_{\text{convexity}}$
$\displaystyle+\alpha_{t}\left\langle\nabla
f\left(x_{t}\right),z_{t}-y_{t-1}\right\rangle+G\left\|y_{t}-x_{t}\right\|+\frac{\beta}{2}\left\|y_{t}-x_{t}\right\|^{2}$
$\displaystyle\leq\left(1-\alpha_{t}\right)f\left(y_{t-1}\right)+\alpha_{t}f\left(x_{t}\right)+\alpha_{t}\left\langle\nabla
f\left(x_{t}\right),z_{t}-x_{t}\right\rangle+G\underbrace{\left\|y_{t}-x_{t}\right\|}_{=\alpha_{t}\left\|z_{t}-z_{t-1}\right\|}+\frac{\beta}{2}\underbrace{\left\|y_{t}-x_{t}\right\|^{2}}_{=\alpha_{t}^{2}\left\|z_{t}-z_{t-1}\right\|^{2}}$
$\displaystyle=\left(1-\alpha_{t}\right)f\left(y_{t-1}\right)+\alpha_{t}f\left(x_{t}\right)+\alpha_{t}\left\langle\nabla
f\left(x_{t}\right),z_{t}-x_{t}\right\rangle+G\alpha_{t}\left\|z_{t}-z_{t-1}\right\|+\frac{\beta}{2}\alpha_{t}^{2}\left\|z_{t}-z_{t-1}\right\|^{2}.$

By the optimality condition for $z_{t}$,

$\eta_{t}\left\langle\widehat{\nabla}f(x_{t}),z_{t}-x^{*}\right\rangle\leq\left\langle\nabla_{x}\mathbf{D}_{\psi}\left(z_{t},z_{t-1}\right),x^{*}-z_{t}\right\rangle=\mathbf{D}_{\psi}\left(x^{*},z_{t-1}\right)-\mathbf{D}_{\psi}\left(z_{t},z_{t-1}\right)-\mathbf{D}_{\psi}\left(x^{*},z_{t}\right).$

Rearranging, we obtain

$\displaystyle\mathbf{D}_{\psi}\left(x^{*},z_{t}\right)-\mathbf{D}_{\psi}\left(x^{*},z_{t-1}\right)+\mathbf{D}_{\psi}\left(z_{t},z_{t-1}\right)$
$\displaystyle\leq\eta_{t}\left\langle\widehat{\nabla}f\left(x_{t}\right),x^{*}-z_{t}\right\rangle=\eta_{t}\left\langle\nabla
f\left(x_{t}\right)+\xi_{t},x^{*}-z_{t}\right\rangle.$

By combining the two inequalities, we obtain

$\displaystyle
f\left(y_{t}\right)+\frac{\alpha_{t}}{\eta_{t}}\left(\mathbf{D}_{\psi}\left(x^{*},z_{t}\right)-\mathbf{D}_{\psi}\left(x^{*},z_{t-1}\right)+\mathbf{D}_{\psi}\left(z_{t},z_{t-1}\right)\right)$
$\displaystyle\leq\left(1-\alpha_{t}\right)f\left(y_{t-1}\right)+\alpha_{t}\underbrace{\left(f\left(x_{t}\right)+\left\langle\nabla
f\left(x_{t}\right),x^{*}-x_{t}\right\rangle\right)}_{\text{convexity}}$
$\displaystyle+G\alpha_{t}\left\|z_{t}-z_{t-1}\right\|+\frac{\beta}{2}\alpha_{t}^{2}\left\|z_{t}-z_{t-1}\right\|^{2}+\alpha_{t}\left\langle\xi_{t},x^{*}-z_{t}\right\rangle$
$\displaystyle\leq\left(1-\alpha_{t}\right)f\left(y_{t-1}\right)+\alpha_{t}f\left(x^{*}\right)+G\alpha_{t}\left\|z_{t}-z_{t-1}\right\|+\frac{\beta}{2}\alpha_{t}^{2}\left\|z_{t}-z_{t-1}\right\|^{2}+\alpha_{t}\left\langle\xi_{t},x^{*}-z_{t}\right\rangle.$

Subtracting $f\left(x^{*}\right)$ from both sides, rearranging, and using that
$\mathbf{D}_{\psi}\left(z_{t},z_{t-1}\right)\geq\frac{1}{2}\left\|z_{t}-z_{t-1}\right\|^{2}$,
we obtain

$\displaystyle
f\left(y_{t}\right)-f\left(x^{*}\right)+\frac{\alpha_{t}}{\eta_{t}}\left(\mathbf{D}_{\psi}\left(x^{*},z_{t}\right)-\mathbf{D}_{\psi}\left(x^{*},z_{t-1}\right)\right)$
$\displaystyle\leq\left(1-\alpha_{t}\right)\left(f\left(y_{t-1}\right)-f\left(x^{*}\right)\right)+\alpha_{t}\left\langle\xi_{t},x^{*}-z_{t}\right\rangle+G\alpha_{t}\left\|z_{t}-z_{t-1}\right\|-\alpha_{t}\frac{1-\beta\alpha_{t}\eta_{t}}{2\eta_{t}}\left\|z_{t}-z_{t-1}\right\|^{2}$
$\displaystyle=\left(1-\alpha_{t}\right)\left(f\left(y_{t-1}\right)-f\left(x^{*}\right)\right)+\alpha_{t}\left\langle\xi_{t},x^{*}-z_{t-1}\right\rangle+\alpha_{t}\left\langle\xi_{t},z_{t}-z_{t-1}\right\rangle+G\alpha_{t}\left\|z_{t}-z_{t-1}\right\|-\alpha_{t}\frac{1-\beta\alpha_{t}\eta_{t}}{2\eta_{t}}\left\|z_{t}-z_{t-1}\right\|^{2}$
$\displaystyle\leq\left(1-\alpha_{t}\right)\left(f\left(y_{t-1}\right)-f\left(x^{*}\right)\right)+\alpha_{t}\left\langle\xi_{t},x^{*}-z_{t-1}\right\rangle+\alpha_{t}\left\|z_{t}-z_{t-1}\right\|\left(\left\|\xi_{t}\right\|_{*}+G\right)-\alpha_{t}\frac{1-\beta\alpha_{t}\eta_{t}}{2\eta_{t}}\left\|z_{t}-z_{t-1}\right\|^{2}$
$\displaystyle\leq\left(1-\alpha_{t}\right)\left(f\left(y_{t-1}\right)-f\left(x^{*}\right)\right)+\alpha_{t}\left\langle\xi_{t},x^{*}-z_{t-1}\right\rangle+\frac{\alpha_{t}\eta_{t}}{2\left(1-\beta\alpha_{t}\eta_{t}\right)}\left(\left\|\xi_{t}\right\|_{*}+G\right)^{2}.$

Finally, we divide by $\frac{\alpha_{t}}{\eta_{t}}$, and obtain

$\displaystyle\frac{\eta_{t}}{\alpha_{t}}\left(f\left(y_{t}\right)-f\left(x^{*}\right)\right)+\mathbf{D}_{\psi}\left(x^{*},z_{t}\right)-\mathbf{D}_{\psi}\left(x^{*},z_{t-1}\right)$
$\displaystyle\leq\frac{\eta_{t}}{\alpha_{t}}\left(1-\alpha_{t}\right)\left(f\left(y_{t-1}\right)-f\left(x^{*}\right)\right)+\eta_{t}\left\langle\xi_{t},x^{*}-z_{t-1}\right\rangle+\frac{\eta_{t}^{2}}{2\left(1-\beta\alpha_{t}\eta_{t}\right)}\left(\left\|\xi_{t}\right\|_{*}+G\right)^{2}$
$\displaystyle\leq\frac{\eta_{t}}{\alpha_{t}}\left(1-\alpha_{t}\right)\left(f\left(y_{t-1}\right)-f\left(x^{*}\right)\right)+\eta_{t}\left\langle\xi_{t},x^{*}-z_{t-1}\right\rangle+\frac{\eta_{t}^{2}}{1-\beta\alpha_{t}\eta_{t}}\left(\left\|\xi_{t}\right\|_{*}^{2}+G^{2}\right).$

∎

###### Proof of Theorem 3.6.

We proceed by induction on $t$. Consider the base case $t=T+1$, the inequality
trivially holds. Next, we consider $t\leq T$. We have

$\displaystyle\mathbb{\mathbb{E}}\left[\exp\left(S_{t}\right)\mid\mathcal{F}_{t}\right]$
$\displaystyle=\mathbb{\mathbb{E}}\left[\exp\left(Z_{t}+S_{t+1}\right)\mid\mathcal{F}_{t}\right]=\mathbb{\mathbb{E}}\left[\mathbb{\mathbb{E}}\left[\exp\left(Z_{t}+S_{t+1}\right)\mid\mathcal{F}_{t+1}\right]\mid\mathcal{F}_{t}\right].$
(10)

We now analyze the inner expectation. Conditioned on $\mathcal{F}_{t+1}$,
$Z_{t}$ is fixed. Using the inductive hypothesis, we obtain

$\displaystyle\mathbb{\mathbb{E}}\left[\exp\left(Z_{t}+S_{t+1}\right)\mid\mathcal{F}_{t+1}\right]$
$\displaystyle\leq\exp\left(Z_{t}\right)\exp\left(3\sigma^{2}\sum_{i=t+1}^{T}w_{i}\frac{\eta_{i}^{2}}{1-L\alpha_{i}\eta_{i}}\right).$
(11)

Let $X_{t}=\eta_{t}\left\langle\xi_{t},x^{*}-z_{t-1}\right\rangle$. By Lemma
3.5, we have

$\displaystyle\frac{\eta_{t}}{\alpha_{t}}\left(f\left(y_{t}\right)-f\left(x^{*}\right)\right)-\frac{\eta_{t}}{\alpha_{t}}\left(1-\alpha_{t}\right)\left(f\left(y_{t-1}\right)-f\left(x^{*}\right)\right)-\frac{\eta_{t}^{2}}{1-L\alpha_{t}\eta_{t}}G^{2}$
$\displaystyle\quad+\mathbf{D}_{\psi}\left(x^{*},z_{t}\right)-\mathbf{D}_{\psi}\left(x^{*},z_{t-1}\right)$
$\displaystyle\leq
X_{t}+\frac{\eta_{t}^{2}}{\left(1-L\alpha_{t}\eta_{t}\right)}\left\|\xi_{t}\right\|_{*}^{2}$

and thus

$\displaystyle Z_{t}$ $\displaystyle\leq
w_{t}X_{t}+w_{t}\frac{\eta_{t}^{2}}{1-L\alpha_{t}\eta_{t}}\left\|\xi_{t}\right\|_{*}^{2}-v_{t}\mathbf{D}_{\psi}\left(x^{*},z_{t-1}\right).$

Plugging into (11), we obtain

$\displaystyle\mathbb{\mathbb{E}}\left[\exp\left(Z_{t}+S_{t+1}\right)\mid\mathcal{F}_{t+1}\right]$
$\displaystyle\leq\exp\left(w_{t}X_{t}-v_{t}\mathbf{D}_{\psi}\left(x^{*},z_{t-1}\right)+w_{t}\frac{\eta_{t}^{2}}{1-L\alpha_{t}\eta_{t}}\left\|\xi_{t}\right\|_{*}^{2}+3\sigma^{2}\sum_{i=t+1}^{T}w_{i}\frac{\eta_{i}^{2}}{1-L\alpha_{i}\eta_{i}}\right).$

Plugging into (10), we obtain

$\displaystyle\mathbb{\mathbb{E}}\left[\exp\left(S_{t}\right)\mid\mathcal{F}_{t}\right]$
$\displaystyle\leq\exp\left(-v_{t}\mathbf{D}_{\psi}\left(x^{*},z_{t-1}\right)+3\sigma^{2}\sum_{i=t+1}^{T}w_{i}\frac{\eta_{i}^{2}}{1-L\alpha_{i}\eta_{i}}\right)\mathbb{\mathbb{E}}\left[\exp\left(w_{t}X_{t}+w_{t}\frac{\eta_{t}^{2}}{1-L\alpha_{t}\eta_{t}}\left\|\xi_{t}\right\|_{*}^{2}\right)\mid\mathcal{F}_{t}\right].$
(12)

Next, we analyze the expectation on the RHS of the above inequality. Note that
$X_{t}=\eta_{t}\left\langle\xi_{t},x^{*}-z_{t-1}\right\rangle$ and
$\mathbb{\mathbb{E}}\left[X_{t}\mid\mathcal{F}_{t}\right]=0$. Applying Lemma
2.2, we obtain

$\displaystyle\mathbb{\mathbb{E}}\left[\exp\left(w_{t}X_{t}+w_{t}\frac{\eta_{t}^{2}}{1-L\alpha_{t}\eta_{t}}\left\|\xi_{t}\right\|_{*}^{2}\right)\mid\mathcal{F}_{t}\right]$
$\displaystyle\leq\exp\left(3\left(w_{t}^{2}\eta_{t}^{2}\left\|x^{*}-z_{t-1}\right\|^{2}+w_{t}\frac{\eta_{t}^{2}}{1-L\alpha_{t}\eta_{t}}\right)\sigma^{2}\right)$
$\displaystyle\leq\exp\left(3\left(2w_{t}^{2}\eta_{t}^{2}\mathbf{D}_{\psi}\left(x^{*},z_{t-1}\right)+w_{t}\frac{\eta_{t}^{2}}{1-L\alpha_{t}\eta_{t}}\right)\sigma^{2}\right).$
(13)

On the last line we used that
$\mathbf{D}_{\psi}\left(x^{*},z_{t-1}\right)\geq\frac{1}{2}\left\|x^{*}-z_{t-1}\right\|^{2}$,
which follows from the strong convexity of $\psi$.

Plugging in (13) into (12) and using that
$v_{t}=6\sigma^{2}w_{t}^{2}\eta_{t}^{2}$, we obtain

$\mathbb{\mathbb{E}}\left[\exp\left(S_{t}\right)\mid\mathcal{F}_{t}\right]\leq\exp\left(3\sigma^{2}\sum_{i=t}^{T}w_{i}\frac{\eta_{i}^{2}}{1-L\alpha_{i}\eta_{i}}\right)$

as needed. ∎

###### Proof of Corollary 3.7.

Let

$K=3\sigma^{2}\sum_{t=1}^{T}w_{t}\frac{\eta_{t}^{2}}{1-L\alpha_{t}\eta_{t}}+\log\left(\frac{1}{\delta}\right).$

By Theorem 3.6 and Markov’s inequality, we have

$\displaystyle\Pr\left[S_{1}\geq K\right]$
$\displaystyle\leq\Pr\left[\exp\left(S_{1}\right)\geq\exp\left(K\right)\right]$
$\displaystyle\leq\exp\left(-K\right)\mathbb{\mathbb{E}}\left[\exp\left(S_{1}\right)\right]$
$\displaystyle\leq\exp\left(-K\right)\exp\left(3\sigma^{2}\sum_{t=1}^{T}w_{t}\frac{\eta_{t}^{2}}{1-L\alpha_{t}\eta_{t}}\right)$
$\displaystyle=\delta.$

Note that since $v_{t}+w_{t}\leq w_{t-1}$

$\displaystyle S_{1}$ $\displaystyle=\sum_{t=1}^{T}Z_{t}$
$\displaystyle=\sum_{t=1}^{T}w_{t}\left(\frac{\eta_{t}}{\alpha_{t}}\left(f\left(y_{t}\right)-f\left(x^{*}\right)\right)-\frac{\eta_{t}\left(1-\alpha_{t}\right)}{\alpha_{t}}\left(f\left(y_{t-1}\right)-f\left(x^{*}\right)\right)\right)$
$\displaystyle\quad+\sum_{t=1}^{T}w_{t}\mathbf{D}_{\psi}\left(x^{*},z_{t}\right)-(v_{t}+w_{t})\mathbf{D}_{\psi}\left(x^{*},z_{t-1}\right)-G^{2}\sum_{t=1}^{T}w_{t}\frac{\eta_{t}^{2}}{1-L\alpha_{t}\eta_{t}}$
$\displaystyle\geq$
$\displaystyle\sum_{t=1}^{T}w_{t}\left(\frac{\eta_{t}}{\alpha_{t}}\left(f\left(y_{t}\right)-f\left(x^{*}\right)\right)-\frac{\eta_{t}\left(1-\alpha_{t}\right)}{\alpha_{t}}\left(f\left(y_{t-1}\right)-f\left(x^{*}\right)\right)\right)$
$\displaystyle\quad+\sum_{t=1}^{T}w_{t}\mathbf{D}_{\psi}\left(x^{*},z_{t}\right)-w_{t-1}\mathbf{D}_{\psi}\left(x^{*},z_{t-1}\right)-G^{2}\sum_{t=1}^{T}w_{t}\frac{\eta_{t}^{2}}{1-L\alpha_{t}\eta_{t}}$
$\displaystyle=$
$\displaystyle\sum_{t=1}^{T}w_{t}\left(\frac{\eta_{t}}{\alpha_{t}}\left(f\left(y_{t}\right)-f\left(x^{*}\right)\right)-\frac{\eta_{t}\left(1-\alpha_{t}\right)}{\alpha_{t}}\left(f\left(y_{t-1}\right)-f\left(x^{*}\right)\right)\right)$
$\displaystyle\quad+w_{T}\mathbf{D}_{\psi}\left(x^{*},z_{T}\right)-w_{0}\mathbf{D}_{\psi}\left(x^{*},z_{0}\right)-G^{2}\sum_{t=1}^{T}w_{t}\frac{\eta_{t}^{2}}{1-L\alpha_{t}\eta_{t}}.$

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

$\displaystyle\sum_{t=1}^{T}w_{t}\left(\frac{\eta_{t}}{\alpha_{t}}\left(f\left(y_{t}\right)-f\left(x^{*}\right)\right)-\frac{\eta_{t}\left(1-\alpha_{t}\right)}{\alpha_{t}}\left(f\left(y_{t-1}\right)-f\left(x^{*}\right)\right)\right)+w_{T}\mathbf{D}_{\psi}\left(x^{*},z_{T}\right)$
$\displaystyle\leq
w_{0}\mathbf{D}_{\psi}\left(x^{*},z_{0}\right)+\left(G^{2}+3\sigma^{2}\right)\sum_{t=1}^{T}w_{t}\frac{\eta_{t}^{2}}{1-L\alpha_{t}\eta_{t}}+\log\left(\frac{1}{\delta}\right).$

∎

######  Corollary B.4.

Suppose we run the Accelerated Stochastic Mirror Descent algorithm with the
standard choices $\alpha_{t}=\frac{2}{t+1}$ and $\eta_{t}=\eta t$ with
$\eta\leq\frac{1}{4L}$. Let
$w_{T}=\frac{1}{3\sigma^{2}\eta^{2}T\left(T+1\right)\left(2T+1\right)}$ and
$w_{t-1}=w_{t}+6\sigma^{2}\eta_{t}^{2}w_{t}^{2}$ for all $1\leq t\leq T$. The
sequence $\left\\{w_{t}\right\\}_{0\leq t\leq T}$ satisfies the conditions
required by Corollary 3.7. By Corollary 3.7, with probability at least
$1-\delta$, $\mathbf{D}_{\psi}\left(x^{*},z_{T}\right)\leq
2\mathbf{D}_{\psi}\left(x^{*},z_{0}\right)+12\left(G^{2}+\left(1+\log\left(\frac{1}{\delta}\right)\right)\sigma^{2}\right)\eta^{2}T^{3}$
and

$\displaystyle f\left(y_{T}\right)-f\left(x^{*}\right)\leq$
$\displaystyle\frac{4\mathbf{D}_{\psi}\left(x^{*},z_{0}\right)}{\eta
T^{2}}+24\left(G^{2}+\left(1+\log\left(\frac{1}{\delta}\right)\right)\sigma^{2}\right)\eta
T$

In particular, setting
$\eta=\min\left\\{\frac{1}{4L},\frac{\sqrt{\mathbf{D}_{\psi}\left(x^{*},z_{0}\right)}}{\sqrt{6}\sqrt{G^{2}+\sigma^{2}\left(1+\log\left(\frac{1}{\delta}\right)\right)}T^{3/2}}\right\\}$,
we obtain the first case of Theorem B.3.

###### Proof of Corollary B.4.

Recall from Corollary 3.7 that the sequence $\left\\{w_{t}\right\\}$ needs to
satisfy the following conditions:

$\displaystyle w_{t}+6\sigma^{2}\eta_{t}^{2}w_{t}^{2}$ $\displaystyle\leq
w_{t-1}\quad\forall 1\leq t\leq T$ (14)
$\displaystyle\frac{w_{t}\eta_{t}^{2}}{1-L\alpha_{t}\eta_{t}}$
$\displaystyle\leq\frac{1}{4\sigma^{2}}\quad\forall 0\leq t\leq T$ (15)

We will set $\left\\{w_{t}\right\\}$ so that it satisfies the following
additional condition, which will allow us to telescope the sum on the RHS of
Corollary 3.7:

$w_{t-1}\frac{\eta_{t-1}}{\alpha_{t-1}}\geq
w_{t}\frac{\eta_{t}\left(1-\alpha_{t}\right)}{\alpha_{t}}\quad\forall 1\leq
t\leq T.$ (16)

Given $w_{T}$, we set $w_{t-1}$ for every $1\leq t\leq T$ so that the first
condition (14) holds with equality:

$w_{t-1}=w_{t}+6\sigma^{2}\eta_{t}^{2}w_{t}^{2}=w_{t}+6\sigma^{2}\eta^{2}t^{2}w_{t}^{2}.$

Let $C=\sigma^{2}\eta^{2}T\left(T+1\right)\left(2T+1\right)$. We set

$w_{T}=\frac{1}{C+6\sigma^{2}\eta^{2}\sum_{i=1}^{T}i^{2}}=\frac{1}{C+\sigma^{2}\eta^{2}T\left(T+1\right)\left(2T+1\right)}=\frac{1}{2\sigma^{2}\eta^{2}T\left(T+1\right)\left(2T+1\right)}.$

Given this choice for $w_{T}$, we now verify that, for all $0\leq t\leq T$, we
have

$w_{t}\leq\frac{1}{C+6\sigma^{2}\eta^{2}\sum_{i=1}^{t}i^{2}}=\frac{1}{C+\sigma^{2}\eta^{2}t\left(t+1\right)\left(2t+1\right)}.$

We proceed by induction on $t$. The base case $t=T$ follows from the
definition of $w_{T}$. Consider $t\leq T$. Using the definition of $w_{t-1}$
and the inductive hypothesis, we obtain

$\displaystyle w_{t-1}$
$\displaystyle=w_{t}+6\sigma^{2}\eta^{2}t^{2}w_{t}^{2}$
$\displaystyle\leq\frac{1}{C+6\sigma^{2}\eta^{2}\sum_{i=1}^{t}i^{2}}+\frac{6\sigma^{2}\eta^{2}t^{2}}{\left(C+6\sigma^{2}\eta^{2}\sum_{i=1}^{t}i^{2}\right)^{2}}$
$\displaystyle\leq\frac{1}{C+6\sigma^{2}\eta^{2}\sum_{i=1}^{t}i^{2}}+\frac{\left(C+6\sigma^{2}\eta^{2}\sum_{i=1}^{t}i^{2}\right)-\left(C+6\sigma^{2}\eta^{2}\sum_{i=1}^{t-1}i^{2}\right)}{\left(C+6\sigma^{2}\eta^{2}\sum_{i=1}^{t}i^{2}\right)\left(C+6\sigma^{2}\eta^{2}\sum_{i=1}^{t-1}i^{2}\right)}$
$\displaystyle=\frac{1}{C+6\sigma^{2}\eta^{2}\sum_{i=1}^{t-1}i^{2}}$

as needed.

Let us now verify that the second condition (15) also holds. Using that
$\frac{2t}{t+1}\leq 2$, $L\eta\leq\frac{1}{4}$, and $T\geq 2$, we obtain

$\displaystyle\frac{w_{t}\eta_{t}^{2}}{1-L\alpha_{t}\eta_{t}}$
$\displaystyle=\frac{w_{t}\eta^{2}t^{2}}{1-L\eta\frac{2t}{t+1}}\leq
2w_{t}\eta^{2}t^{2}\leq\frac{2\eta^{2}t^{2}}{C+6\sigma^{2}\eta^{2}t^{2}}$
$\displaystyle=\frac{t^{2}}{\sigma^{2}T\left(T+1\right)\left(2T+1\right)+3\sigma^{2}t^{2}}$
$\displaystyle\leq\frac{1}{\sigma^{2}\left(2T+1\right)+3\sigma^{2}}\leq\frac{1}{4\sigma^{2}}$

as needed.

Let us now verify that the third condition (16) also holds. Since
$\eta_{t}=\eta t$ and $\alpha_{t}=\frac{2}{t+1}$, we have
$\frac{\eta_{t-1}}{\alpha_{t-1}}=\frac{\eta_{t}\left(1-\alpha_{t}\right)}{\alpha_{t}}=\frac{\eta
t\left(t-1\right)}{2}$. Since $w_{t}\leq w_{t-1}$, it follows that condition
(16) holds.

We now turn our attention to the convergence. By Corollary 3.7, with
probability $\geq 1-\delta$, we have

$\displaystyle\sum_{t=1}^{T}w_{t}\left(\frac{\eta_{t}}{\alpha_{t}}\left(f\left(y_{t}\right)-f\left(x^{*}\right)\right)-\frac{\eta_{t}\left(1-\alpha_{t}\right)}{\alpha_{t}}\left(f\left(y_{t-1}\right)-f\left(x^{*}\right)\right)\right)+w_{T}\mathbf{D}_{\psi}\left(x^{*},z_{T}\right)$
$\displaystyle\leq
w_{0}\mathbf{D}_{\psi}\left(x^{*},z_{0}\right)+\left(G^{2}+3\sigma^{2}\right)\sum_{t=1}^{T}w_{t}\frac{\eta_{t}^{2}}{1-L\alpha_{t}\eta_{t}}+\log\left(\frac{1}{\delta}\right).$

Grouping terms on the LHS and using that $\alpha_{1}=1$, we obtain

$\displaystyle\sum_{t=1}^{T-1}\left(w_{t}\frac{\eta_{t}}{\alpha_{t}}-w_{t+1}\frac{\eta_{t+1}\left(1-\alpha_{t+1}\right)}{\alpha_{t+1}}\right)\left(f\left(y_{t}\right)-f\left(x^{*}\right)\right)+w_{T}\frac{\eta_{T}}{\alpha_{T}}\left(f\left(y_{T}\right)-f\left(x^{*}\right)\right)+w_{T}\mathbf{D}_{\psi}\left(x^{*},z_{T}\right)$
$\displaystyle\leq
w_{0}\mathbf{D}_{\psi}\left(x^{*},z_{0}\right)+\left(G^{2}+3\sigma^{2}\right)\sum_{t=1}^{T}w_{t}\frac{\eta_{t}^{2}}{1-L\alpha_{t}\eta_{t}}+\log\left(\frac{1}{\delta}\right).$

Since $\left\\{w_{t}\right\\}$ satisfies condition (16), the coefficient of
$f\left(y_{t}\right)-f\left(x^{*}\right)$ is non-negative and thus we can drop
the above sum. We obtain

$\displaystyle
w_{T}\frac{\eta_{T}}{\alpha_{T}}\left(f\left(y_{T}\right)-f\left(x^{*}\right)\right)+w_{T}\mathbf{D}_{\psi}\left(x^{*},z_{T}\right)$
$\displaystyle\leq
w_{0}\mathbf{D}_{\psi}\left(x^{*},z_{0}\right)+\left(G^{2}+3\sigma^{2}\right)\sum_{t=1}^{T}w_{t}\frac{\eta_{t}^{2}}{1-L\alpha_{t}\eta_{t}}+\log\left(\frac{1}{\delta}\right).$

Using that $w_{T}=\frac{1}{2C}$ and $w_{t}\leq\frac{1}{C}$ for all $0\leq
t\leq T-1$, we obtain

$\displaystyle\frac{1}{2C}\frac{\eta_{T}}{\alpha_{T}}\left(f\left(y_{T}\right)-f\left(x^{*}\right)\right)+\frac{1}{2C}\mathbf{D}_{\psi}\left(x^{*},z_{T}\right)$
$\displaystyle\leq\frac{1}{C}\mathbf{D}_{\psi}\left(x^{*},z_{0}\right)+\frac{1}{C}\left(G^{2}+3\sigma^{2}\right)\sum_{t=1}^{T}\frac{\eta_{t}^{2}}{1-L\alpha_{t}\eta_{t}}+\log\left(\frac{1}{\delta}\right).$

Thus

$\displaystyle\frac{\eta_{T}}{\alpha_{T}}\left(f\left(y_{T}\right)-f\left(x^{*}\right)\right)+\mathbf{D}_{\psi}\left(x^{*},z_{T}\right)$
$\displaystyle\leq
2\mathbf{D}_{\psi}\left(x^{*},z_{0}\right)+2\left(G^{2}+3\sigma^{2}\right)\sum_{t=1}^{T}\frac{\eta_{t}^{2}}{1-L\alpha_{t}\eta_{t}}+2C\log\left(\frac{1}{\delta}\right)$
$\displaystyle=2\mathbf{D}_{\psi}\left(x^{*},z_{0}\right)+2\left(G^{2}+3\sigma^{2}\right)\sum_{t=1}^{T}\frac{\eta_{t}^{2}}{1-L\alpha_{t}\eta_{t}}+2\sigma^{2}\log\left(\frac{1}{\delta}\right)\eta^{2}T\left(T+1\right)\left(2T+1\right).$

Using that $L\eta\leq\frac{1}{4}$ and $\frac{2t}{t+1}\leq 2$, we obtain

$\sum_{t=1}^{T}\frac{\eta_{t}^{2}}{1-L\alpha_{t}\eta_{t}}=\sum_{t=1}^{T}\frac{\eta^{2}t^{2}}{1-L\eta\frac{2t}{t+1}}\leq\sum_{t=1}^{T}2\eta^{2}t^{2}=\frac{1}{3}\eta^{2}T\left(T+1\right)\left(2T+1\right).$

Plugging in and using that $\eta_{T}=\eta T$ and $\alpha_{T}=\frac{2}{T+1}$,
we obtain

$\displaystyle\eta\frac{T\left(T+1\right)}{2}\left(f\left(y_{T}\right)-f\left(x^{*}\right)\right)+\mathbf{D}_{\psi}\left(x^{*},z_{T}\right)$
$\displaystyle\leq
2\mathbf{D}_{\psi}\left(x^{*},z_{0}\right)+\left(\frac{2}{3}G^{2}+2\left(1+\log\left(\frac{1}{\delta}\right)\right)\sigma^{2}\right)\eta^{2}T\left(T+1\right)\left(2T+1\right)$
$\displaystyle\leq
2\mathbf{D}_{\psi}\left(x^{*},z_{0}\right)+2\left(G^{2}+\left(1+\log\left(\frac{1}{\delta}\right)\right)\sigma^{2}\right)\eta^{2}T\left(T+1\right)\left(2T+1\right).$

We can further simplify the bound by lower bounding $T\left(T+1\right)\geq
T^{2}$ and upper bounding $T\left(T+1\right)\left(2T+1\right)\leq 6T^{3}$. We
obtain

$\displaystyle\eta
T^{2}\left(f\left(y_{T}\right)-f\left(x^{*}\right)\right)+2\mathbf{D}_{\psi}\left(x^{*},z_{T}\right)$
$\displaystyle\leq
4\mathbf{D}_{\psi}\left(x^{*},z_{0}\right)+24\left(G^{2}+\left(1+\log\left(\frac{1}{\delta}\right)\right)\sigma^{2}\right)\eta^{2}T^{3}.$

Thus we obtain

$f\left(y_{T}\right)-f\left(x^{*}\right)\leq\frac{4\mathbf{D}_{\psi}\left(x^{*},z_{0}\right)}{\eta
T^{2}}+24\left(G^{2}+\left(1+\log\left(\frac{1}{\delta}\right)\right)\sigma^{2}\right)\eta
T$

and

$\displaystyle\mathbf{D}_{\psi}\left(x^{*},z_{T}\right)$ $\displaystyle\leq
2\mathbf{D}_{\psi}\left(x^{*},z_{0}\right)+12\left(G^{2}+\left(1+\log\left(\frac{1}{\delta}\right)\right)\sigma^{2}\right)\eta^{2}T^{3}.$

∎

######  Corollary B.5.

Suppose we run the Accelerated Stochastic Mirror Descent algorithm with the
standard choices $\alpha_{t}=\frac{2}{t+1}$ and
$\eta_{t}=\min\left\\{\frac{t}{4L},\frac{\eta}{\sqrt{t}}\right\\}$. Let
$w_{T}=\frac{1}{12\sigma^{2}\sum_{i=1}^{T}\eta_{t}^{2}}$ and
$w_{t-1}=w_{t}+6\sigma^{2}\eta_{t}^{2}w_{t}^{2}$ for all $1\leq t\leq T$. The
sequence $\left\\{w_{t}\right\\}_{0\leq t\leq T}$ satisfies the conditions
required by Corollary 3.7. By Corollary 3.7, with probability at least
$1-\delta$, $\mathbf{D}_{\psi}\left(x^{*},z_{T}\right)\leq
2\mathbf{D}_{\psi}\left(x^{*},z_{0}\right)+12\left(G^{2}+\left(1+\log\left(\frac{1}{\delta}\right)\right)\sigma^{2}\right)\eta^{2}(1+\log
T)$ and

$\displaystyle
f\left(y_{T}\right)-f\left(x^{*}\right)\leq\frac{16L}{T^{2}}\mathbf{D}_{\psi}\left(x^{*},z_{0}\right)+\frac{2}{T^{1/2}\eta}\left(2\mathbf{D}_{\psi}\left(x^{*},z_{0}\right)+12\left(G^{2}+\left(1+\log\left(\frac{1}{\delta}\right)\right)\sigma^{2}\right)\eta^{2}(1+\log
T)\right)$

In particular, setting
$\eta_{t}=\min\left\\{\frac{t}{4L},\frac{\sqrt{\mathbf{D}_{\psi}\left(x^{*},z_{0}\right)}}{\sqrt{6}\sqrt{G^{2}+\sigma^{2}\left(1+\log\left(\frac{1}{\delta}\right)\right)}t^{1/2}}\right\\}$,
we obtain the second case of Theorem B.3.

###### Proof of Corollary B.5.

Recall from Corollary 3.7 that the sequence $\left\\{w_{t}\right\\}$ needs to
satisfy the following conditions:

$\displaystyle w_{t}+6\sigma^{2}\eta_{t}^{2}w_{t}^{2}$ $\displaystyle\leq
w_{t-1}\quad\forall 1\leq t\leq T,$ (17)
$\displaystyle\frac{w_{t}\eta_{t}^{2}}{1-L\alpha_{t}\eta_{t}}$
$\displaystyle\leq\frac{1}{4\sigma^{2}}\quad\forall 0\leq t\leq T.$ (18)

We will set $\left\\{w_{t}\right\\}$ so that it satisfies the following
additional condition, which will allow us to telescope the sum on the RHS of
Corollary 3.7:

$w_{t-1}\frac{\eta_{t-1}}{\alpha_{t-1}}\geq
w_{t}\frac{\eta_{t}\left(1-\alpha_{t}\right)}{\alpha_{t}}\quad\forall 1\leq
t\leq T-1.$ (19)

Given $w_{T}$, we set $w_{t-1}$ for every $1\leq t\leq T$ so that the first
condition (17) holds with equality:

$w_{t-1}=w_{t}+6\sigma^{2}\eta_{t}^{2}w_{t}^{2}=w_{t}+6\sigma^{2}\eta^{2}t^{2}w_{t}^{2}.$

Let $C=6\sigma^{2}\sum_{i=1}^{T}\eta_{t}^{2}$. We set

$w_{T}=\frac{1}{12\sigma^{2}\sum_{i=1}^{T}\eta_{t}^{2}}=\frac{1}{2C}.$

Given this choice for $w_{T}$, we now verify that, for all $0\leq t\leq T$, we
have

$w_{t}\leq\frac{1}{C+6\sigma^{2}\sum_{i=1}^{t}\eta_{i}^{2}}.$

We proceed by induction on $t$. The base case $t=T$ follows from the
definition of $w_{T}$. Consider $t\leq T$. Using the definition of $w_{t-1}$
and the inductive hypothesis, we obtain

$\displaystyle w_{t-1}$ $\displaystyle=w_{t}+6\sigma^{2}\eta_{t}^{2}w_{t}^{2}$
$\displaystyle\leq\frac{1}{C+6\sigma^{2}\sum_{i=1}^{t}\eta_{i}^{2}}+\frac{6\sigma^{2}\eta_{t}^{2}}{\left(C+6\sigma^{2}\sum_{i=1}^{t}\eta_{i}^{2}\right)^{2}}$
$\displaystyle\leq\frac{1}{C+6\sigma^{2}\sum_{i=1}^{t}\eta_{i}^{2}}+\frac{\left(C+6\sigma^{2}\sum_{i=1}^{t}\eta_{i}^{2}\right)-\left(C+6\sigma^{2}\sum_{i=1}^{t-1}\eta_{i}^{2}\right)}{\left(C+6\sigma^{2}\sum_{i=1}^{t}\eta_{i}^{2}\right)\left(C+6\sigma^{2}\sum_{i=1}^{t-1}\eta_{i}^{2}\right)}$
$\displaystyle=\frac{1}{C+6\sigma^{2}\sum_{i=1}^{t-1}\eta_{i}^{2}}$

as needed.

Let us now verify that the second condition (18) also holds. Using that
$L\eta_{t}\leq\frac{t}{4}$, and $T\geq 2$, we obtain

$\frac{w_{t}\eta_{t}^{2}}{1-L\alpha_{t}\eta_{t}}\leq\frac{w_{t}\eta_{t}^{2}}{1-\frac{t}{4}\frac{2}{t+1}}\leq
2w_{t}\eta_{t}^{2}\leq\frac{2\eta_{t}^{2}}{6\sigma^{2}\sum_{i=1}^{T}\eta_{t}^{2}+6\sigma^{2}\sum_{i=1}^{t}\eta_{i}^{2}}\leq\frac{2\eta_{t}^{2}}{12\sigma^{2}\eta_{t}^{2}}\leq\frac{1}{4\sigma^{2}}$

as needed.

Let us now verify that the third condition (19) also holds. Since
$\alpha_{t}=\frac{2}{t+1}$, we have

$\displaystyle\frac{\eta_{t-1}}{\alpha_{t-1}}$
$\displaystyle=\frac{\eta_{t-1}t}{2},$
$\displaystyle\frac{\eta_{t}\left(1-\alpha_{t}\right)}{\alpha_{t}}$
$\displaystyle=\frac{\eta_{t}\left(t-1\right)}{2}.$

If $\eta_{t-1}=\frac{t-1}{4L}$ then we have $\eta_{t}\leq\frac{t}{4L}$ and
$\frac{\eta_{t}\left(1-\alpha_{t}\right)}{\alpha_{t}}\leq\frac{\eta_{t-1}}{\alpha_{t-1}}=\frac{t(t-1)}{8L}$.
If $\eta_{t-1}=\frac{\eta}{\sqrt{t-1}}$ then
$\eta_{t}=\frac{\eta}{\sqrt{t}},$we also have
$\frac{\eta_{t}\left(1-\alpha_{t}\right)}{\alpha_{t}}\leq\frac{\eta_{t-1}}{\alpha_{t-1}}$.
Since $w_{t}\leq w_{t-1}$, it follows that condition (19) holds.

We now turn our attention to the convergence. By Corollary 3.7, with
probability $\geq 1-\delta$, we have

$\displaystyle\sum_{t=1}^{T}w_{t}\left(\frac{\eta_{t}}{\alpha_{t}}\left(f\left(y_{t}\right)-f\left(x^{*}\right)\right)-\frac{\eta_{t}\left(1-\alpha_{t}\right)}{\alpha_{t}}\left(f\left(y_{t-1}\right)-f\left(x^{*}\right)\right)\right)+w_{T}\mathbf{D}_{\psi}\left(x^{*},z_{T}\right)$
$\displaystyle\leq
w_{0}\mathbf{D}_{\psi}\left(x^{*},z_{0}\right)+\left(G^{2}+3\sigma^{2}\right)\sum_{t=1}^{T}w_{t}\frac{\eta_{t}^{2}}{1-L\alpha_{t}\eta_{t}}+\log\left(\frac{1}{\delta}\right).$

Grouping terms on the LHS and using that $\alpha_{1}=1$, we obtain

$\displaystyle\sum_{t=1}^{T-1}\left(w_{t}\frac{\eta_{t}}{\alpha_{t}}-w_{t+1}\frac{\eta_{t+1}\left(1-\alpha_{t+1}\right)}{\alpha_{t+1}}\right)\left(f\left(y_{t}\right)-f\left(x^{*}\right)\right)+w_{T}\frac{\eta_{T}}{\alpha_{T}}\left(f\left(y_{T}\right)-f\left(x^{*}\right)\right)+w_{T}\mathbf{D}_{\psi}\left(x^{*},z_{T}\right)$
$\displaystyle\leq
w_{0}\mathbf{D}_{\psi}\left(x^{*},z_{0}\right)+\left(G^{2}+3\sigma^{2}\right)\sum_{t=1}^{T}w_{t}\frac{\eta_{t}^{2}}{1-L\alpha_{t}\eta_{t}}+\log\left(\frac{1}{\delta}\right).$

Since $\left\\{w_{t}\right\\}$ satisfies condition (19), the coefficient of
$f(y_{t})-f(x^{*})$ is non-negative and thus we can drop the above sum. We
obtain

$\displaystyle
w_{T}\frac{\eta_{T}}{\alpha_{T}}\left(f\left(y_{T}\right)-f\left(x^{*}\right)\right)+w_{T}\mathbf{D}_{\psi}\left(x^{*},z_{T}\right)$
$\displaystyle\leq
w_{0}\mathbf{D}_{\psi}\left(x^{*},z_{0}\right)+\left(G^{2}+3\sigma^{2}\right)\sum_{t=1}^{T}w_{t}\frac{\eta_{t}^{2}}{1-L\alpha_{t}\eta_{t}}+\log\left(\frac{1}{\delta}\right).$

Using that $w_{T}=\frac{1}{2C}$ and $w_{t}\leq\frac{1}{C}$ for all $0\leq
t\leq T-1$, we obtain

$\displaystyle\frac{1}{2C}\frac{\eta_{T}}{\alpha_{T}}\left(f\left(y_{T}\right)-f\left(x^{*}\right)\right)+\frac{1}{2C}\mathbf{D}_{\psi}\left(x^{*},z_{T}\right)$
$\displaystyle\leq\frac{1}{C}\mathbf{D}_{\psi}\left(x^{*},z_{0}\right)+\frac{1}{C}\left(G^{2}+3\sigma^{2}\right)\sum_{t=1}^{T}\frac{\eta_{t}^{2}}{1-L\alpha_{t}\eta_{t}}+\log\left(\frac{1}{\delta}\right).$

Thus,

$\displaystyle\frac{\eta_{T}}{\alpha_{T}}\left(f\left(y_{T}\right)-f\left(x^{*}\right)\right)+\mathbf{D}_{\psi}\left(x^{*},z_{T}\right)$
$\displaystyle\leq
2\mathbf{D}_{\psi}\left(x^{*},z_{0}\right)+2\left(G^{2}+3\sigma^{2}\right)\sum_{t=1}^{T}\frac{\eta_{t}^{2}}{1-L\alpha_{t}\eta_{t}}+2C\log\left(\frac{1}{\delta}\right).$

Using that $L\eta_{t}\leq\frac{t}{4}$, we obtain

$\sum_{t=1}^{T}\frac{\eta_{t}^{2}}{1-L\alpha_{t}\eta_{t}}=\sum_{t=1}^{T}\frac{\eta_{t}^{2}}{1-\frac{t}{4}\frac{2}{t+1}}\leq\sum_{t=1}^{T}2\eta_{t}^{2}=\frac{C}{3\sigma^{2}}.$

Plugging in and using that $\eta_{T}=\eta T$ and $\alpha_{T}=\frac{2}{T+1}$,
we obtain

$\displaystyle\frac{\eta_{T}\left(T+1\right)}{2}\left(f\left(y_{T}\right)-f\left(x^{*}\right)\right)+\mathbf{D}_{\psi}\left(x^{*},z_{T}\right)$
$\displaystyle\leq
2\mathbf{D}_{\psi}\left(x^{*},z_{0}\right)+\left(2G^{2}+6\left(1+\log\left(\frac{1}{\delta}\right)\right)\sigma^{2}\right)\frac{C}{3\sigma^{2}}.$

If $\frac{T}{4L}\leq\frac{\eta}{\sqrt{T}}$ which means $T^{3/2}\leq 4L\eta$,
then $\eta_{T}=\frac{T}{4L}$. We have

$\displaystyle C$
$\displaystyle=6\sigma^{2}\sum_{i=1}^{T}\eta_{t}^{2}=\frac{6\sigma^{2}}{16L^{2}}\sum_{i=1}^{T}t^{2}\leq\frac{3\sigma^{2}T^{3}}{8L^{2}}\leq
6\sigma^{2}\eta^{2}.$

Hence

$\displaystyle\frac{\eta_{T}\left(T+1\right)}{2}\left(f\left(y_{T}\right)-f\left(x^{*}\right)\right)+\mathbf{D}_{\psi}\left(x^{*},z_{T}\right)$
$\displaystyle\leq
2\mathbf{D}_{\psi}\left(x^{*},z_{0}\right)+\left(G^{2}+\left(1+\log\left(\frac{1}{\delta}\right)\right)\sigma^{2}\right)\frac{3T^{3}}{4L^{2}},$

which entails

$\displaystyle f\left(y_{T}\right)-f\left(x^{*}\right)$
$\displaystyle\leq\frac{16L}{T^{2}}\mathbf{D}_{\psi}\left(x^{*},z_{0}\right)+\left(G^{2}+\left(1+\log\left(\frac{1}{\delta}\right)\right)\sigma^{2}\right)\frac{6T}{L}$
$\displaystyle=\frac{16L}{T^{2}}\mathbf{D}_{\psi}\left(x^{*},z_{0}\right)+\frac{6}{\sqrt{T}}\left(G^{2}+\left(1+\log\left(\frac{1}{\delta}\right)\right)\sigma^{2}\right)\frac{T^{3/2}}{L}$
$\displaystyle\leq\frac{16L}{T^{2}}\mathbf{D}_{\psi}\left(x^{*},z_{0}\right)+\frac{24}{\sqrt{T}}\left(G^{2}+\left(1+\log\left(\frac{1}{\delta}\right)\right)\sigma^{2}\right)\eta,$

and

$\displaystyle\mathbf{D}_{\psi}\left(x^{*},z_{T}\right)$ $\displaystyle\leq
2\mathbf{D}_{\psi}\left(x^{*},z_{0}\right)+12\left(G^{2}+\left(1+\log\left(\frac{1}{\delta}\right)\right)\sigma^{2}\right)\eta^{2}.$

If $\frac{\eta}{\sqrt{T}}\leq\frac{T}{4L}$ then
$\eta_{T}=\frac{\eta}{\sqrt{T}}$. Let $T_{0}$ be the largest $t$ such that
$\frac{\eta}{\sqrt{t}}\geq\frac{t}{4L}$, we have $T_{0}^{3}\leq
16L^{2}\eta^{2}$

$\displaystyle C$ $\displaystyle=6\sigma^{2}\sum_{i=1}^{T}\eta_{t}^{2}$
$\displaystyle=6\sigma^{2}\sum_{i=1}^{T_{0}}\eta_{t}^{2}+6\sigma^{2}\sum_{i=T_{0}+1}^{T}\eta_{t}^{2}$
$\displaystyle=\frac{6\sigma^{2}}{16L^{2}}\sum_{i=1}^{T_{0}}t^{2}+6\sigma^{2}\eta^{2}\sum_{i=T_{0}+1}^{T}\frac{1}{t}$
$\displaystyle\leq\frac{6\sigma^{2}}{16L^{2}}T_{0}^{3}+6\sigma^{2}\eta^{2}\sum_{i=T_{0}+1}^{T}\frac{1}{t}$
$\displaystyle\leq 6\sigma^{2}\eta^{2}\sum_{i=1}^{T}\frac{1}{t}\leq
6\sigma^{2}\eta^{2}(1+\log T).$

Hence

$\displaystyle f\left(y_{T}\right)-f\left(x^{*}\right)$
$\displaystyle\leq\frac{2}{T^{1/2}\eta}\left(2\mathbf{D}_{\psi}\left(x^{*},z_{0}\right)+12\left(G^{2}+\left(1+\log\left(\frac{1}{\delta}\right)\right)\sigma^{2}\right)\eta^{2}(1+\log
T)\right)$

and

$\displaystyle\mathbf{D}_{\psi}\left(x^{*},z_{T}\right)$ $\displaystyle\leq
2\mathbf{D}_{\psi}\left(x^{*},z_{0}\right)+12\left(G^{2}+\left(1+\log\left(\frac{1}{\delta}\right)\right)\sigma^{2}\right)\eta^{2}(1+\log
T).$

Overall, we have

$\displaystyle f\left(y_{T}\right)-f\left(x^{*}\right)$
$\displaystyle\leq\frac{16L}{T^{2}}\mathbf{D}_{\psi}\left(x^{*},z_{0}\right)+\frac{2}{T^{1/2}\eta}\left(2\mathbf{D}_{\psi}\left(x^{*},z_{0}\right)+12\left(G^{2}+\left(1+\log\left(\frac{1}{\delta}\right)\right)\sigma^{2}\right)\eta^{2}(1+\log
T)\right).$

∎

##  Appendix C Missing Proofs from Section 4

###### Proof of Lemma 4.2.

We start from the smoothness of $f$

$\displaystyle f(x_{t+1})-f(x_{t})$ $\displaystyle\leq\left\langle\nabla
f(x_{t}),x_{t+1}-x_{t}\right\rangle+\frac{L}{2}\left\|x_{t+1}-x_{t}\right\|^{2}$
$\displaystyle=-\eta_{t}\left\langle\nabla
f(x_{t}),\widehat{\nabla}f(x_{t})\right\rangle+\frac{L\eta_{t}^{2}}{2}\left\|\widehat{\nabla}f(x_{t})\right\|^{2}.$

By writing $\widehat{\nabla}f(x_{t})=\xi_{t}+\nabla f(x_{t})$ we have

$\displaystyle f(x_{t+1})-f(x_{t})$
$\displaystyle\leq-\eta_{t}\left\langle\nabla f(x_{t}),\xi_{t}+\nabla
f(x_{t})\right\rangle+\frac{L\eta_{t}^{2}}{2}\left\|\xi_{t}+\nabla
f(x_{t})\right\|^{2}$ $\displaystyle=-\eta_{t}\left\|\nabla
f(x_{t})\right\|^{2}-\eta_{t}\left\langle\nabla f(x_{t}),\xi_{t}\right\rangle$
$\displaystyle\quad+\frac{L\eta_{t}^{2}}{2}\left\|\xi_{t}\right\|^{2}+\frac{L\eta_{t}^{2}}{2}\left\|\nabla
f(x_{t})\right\|^{2}+L\eta_{t}^{2}\left\langle\nabla
f(x_{t}),\xi_{t}\right\rangle.$

We obtain the inequality (7) by rearranging the terms. ∎

###### Proof of Theorem 4.3.

We prove by induction. The base case $t=T+1$ trivially holds. Consider $1\leq
t\leq T$, we have

$\displaystyle\mathbb{\mathbb{E}}\left[\exp\left(S_{t}\right)\mid\mathcal{F}_{t}\right]$
$\displaystyle=\mathbb{\mathbb{E}}\left[\mathbb{\mathbb{E}}\left[\exp\left(Z_{t}+S_{t+1}\right)\mid\mathcal{F}_{t+1}\right]\mid\mathcal{F}_{t}\right]$
$\displaystyle=\mathbb{\mathbb{E}}\left[\exp\left(Z_{t}\right)\mathbb{\mathbb{E}}\left[\exp\left(S_{t+1}\right)\mid\mathcal{F}_{t+1}\right]\mid\mathcal{F}_{k}\right].$

From the induction hypothesis we have
$\mathbb{\mathbb{E}}\left[\exp\left(S_{t+1}\right)\mid\mathcal{F}_{t+1}\right]\leq\exp\left(3\sigma^{2}\sum_{i=t+1}^{T}\frac{w_{i}\eta_{i}^{2}L}{2}\right)$,
hence

$\displaystyle\mathbb{\mathbb{E}}\left[\exp\left(S_{t}\right)\mid\mathcal{F}_{t}\right]$
$\displaystyle\leq\exp\left(3\sigma^{2}\sum_{i=t+1}^{T}\frac{w_{i}\eta_{i}^{2}L}{2}\right)\mathbb{\mathbb{E}}\left[\exp\left(Z_{t}\right)\mid\mathcal{F}_{t}\right].$

We have then

$\displaystyle\mathbb{\mathbb{E}}\left[\exp\left(Z_{t}\right)\mid\mathcal{F}_{t}\right]$
$\displaystyle=\mathbb{\mathbb{E}}\left[\exp\left(w_{t}\left(\eta_{t}\left(1-\frac{\eta_{t}L}{2}\right)\left\|\nabla
f(x_{t})\right\|^{2}+\Delta_{t+1}-\Delta_{t}\right)-v_{t}\left\|\nabla
f(x_{T})\right\|^{2}\right)\mid\mathcal{F}_{t}\right]$
$\displaystyle\leq\mathbb{\mathbb{E}}\left[\exp\left(w_{t}\left(\eta_{t}(\eta_{t}L-1)\left\langle\nabla
f(x_{t}),\xi_{t}\right\rangle+\frac{\eta_{t}^{2}L}{2}\left\|\xi_{t}\right\|^{2}\right)-v_{t}\left\|\nabla
f(x_{t})\right\|^{2}\right)\mid\mathcal{F}_{t}\right]$
$\displaystyle=\exp\left(-v_{t}\left\|\nabla
f(x_{t})\right\|^{2}\right)\mathbb{\mathbb{E}}\left[\exp\left(w_{t}\left(\eta_{t}(\eta_{t}L-1)\left\langle\nabla
f(x_{t}),\xi_{t}\right\rangle+\frac{\eta_{t}^{2}L}{2}\left\|\xi_{t}\right\|^{2}\right)\right)\mid\mathcal{F}_{t}\right]$
$\displaystyle\leq\exp\left(-v_{t}\left\|\nabla
f(x_{t})\right\|^{2}\right)\exp\left(3\sigma^{2}\left(w_{t}^{2}\eta_{t}^{2}(\eta_{t}L-1)^{2}\left\|\nabla
f(x_{t})\right\|^{2}+\frac{w_{t}\eta_{t}^{2}L}{2}\right)\right)$
$\displaystyle=\exp\left(3\sigma^{2}\frac{w_{t}\eta_{t}^{2}L}{2}\right).$

where the second line is due to (7) in Lemma 4.2 and the second to last line
is due to Lemma 2.2.Therefore

$\displaystyle\mathbb{\mathbb{E}}\left[\exp\left(S_{t}\right)\mid\mathcal{F}_{t}\right]$
$\displaystyle\leq\exp\left(3\sigma^{2}\sum_{i=t}^{T}\frac{w_{i}\eta_{i}^{2}L}{2}\right)$

which is what we want to show. ∎

###### Proof of Corollary 4.4.

In Lemma 4.3, Let $t=1$ we obtain

$\displaystyle\mathbb{\mathbb{E}}\left[\exp\left(S_{1}\right)\right]$
$\displaystyle\leq\exp\left(3\sigma^{2}\sum_{t=1}^{T}\frac{w_{t}\eta_{t}^{2}L}{2}\right).$

Hence, by Markov’s inequality, we have

$\Pr\left[S_{1}\geq\left(3\sigma^{2}\sum_{t=1}^{T}\frac{w_{t}\eta_{t}^{2}L}{2}\right)+\log\frac{1}{\delta}\right]\leq\delta.$

In other words, with probability $\geq 1-\delta$ (once the condition in Lemma
4.3 is satisfied)

$\displaystyle\sum_{t=1}^{T}\left[w_{t}\eta_{t}\left(1-\frac{\eta_{t}L}{2}\right)-v_{t}\right]\left\|\nabla
f(x_{t})\right\|^{2}+w_{t}\left(\Delta_{t+1}-\Delta_{t}\right)$
$\displaystyle\leq
3\sigma^{2}\sum_{t=1}^{T}\frac{w_{t}\eta_{t}^{2}L}{2}+\log\frac{1}{\delta}.$

This gives

$\displaystyle\sum_{t=1}^{T}\left[w_{t}\eta_{t}\left(1-\frac{\eta_{t}L}{2}\right)-v_{t}\right]\left\|\nabla
f(x_{t})\right\|^{2}+w_{T}\Delta_{T+1}$ $\displaystyle\leq
w_{1}\Delta_{1}+\left(\sum_{t=2}^{T}(w_{t}-w_{t-1})\Delta_{t}+3\sigma^{2}\sum_{t=1}^{T}\frac{w_{t}\eta_{t}^{2}L}{2}\right)+\log\frac{1}{\delta}$

as needed. ∎

###### Proof of Theorem 4.1 .

First case.

Starting from this inequality, we will specify the choice of $\eta_{t}$ and
$w_{t}$ to obtain the bound. Consider $\eta_{t}=\eta$ with $\eta L\leq 1$,
$w_{t}=w=\frac{1}{6\sigma^{2}\eta}$. Note that $w_{t}\eta_{t}^{2}L=\frac{\eta
L}{6\sigma^{2}}\leq\frac{1}{2\sigma^{2}}$ satisfies the condition of Lemma
4.3, we have

LHS of (9)
$\displaystyle=w\Delta_{T+1}+\sum_{t=1}^{T}\left[w\eta\left(1-\frac{\eta
L}{2}\right)-3\sigma^{2}w^{2}\eta^{2}(\eta L-1)^{2}\right]\left\|\nabla
f(x_{t})\right\|^{2}$
$\displaystyle=w\Delta_{T+1}+w\eta\sum_{t=1}^{T}\left[1-\frac{\eta
L}{2}-\frac{1}{2}(\eta L-1)^{2}\right]\left\|\nabla f(x_{t})\right\|^{2}$
$\displaystyle\geq w\Delta_{T+1}+\frac{w\eta}{2}\sum_{t=1}^{T}\left\|\nabla
f(x_{t})\right\|^{2}$

where the last inequality is due to $1-\frac{\eta L}{2}-\frac{(1-\eta
L)^{2}}{2}\geq\frac{1}{2}$ when $0\leq\eta L\leq 1$. Besides,

$\displaystyle\mbox{RHS of \eqref{eq:sgd-general-bound}}=$ $\displaystyle
w\Delta_{1}+\frac{3\sigma^{2}}{2}w\eta^{2}LT+\log\frac{1}{\delta}.$

Hence with probability $\geq 1-\delta$

$\displaystyle\sum_{t=1}^{T}\left\|\nabla
f(x_{t})\right\|^{2}+\frac{2\Delta_{T+1}}{\eta}$
$\displaystyle\leq\frac{2\Delta_{1}}{\eta}+3\sigma^{2}\eta
LT+\frac{2}{w\eta}\log\frac{1}{\delta}$
$\displaystyle=\frac{2\Delta_{1}}{\eta}+3\sigma^{2}\eta
LT+12\sigma^{2}\log\frac{1}{\delta}.$

Finally, by choosing
$\eta=\min\left\\{\frac{1}{L};\sqrt{\frac{\Delta_{1}}{\sigma^{2}LT}}\right\\}$
and noticing $\Delta_{T+1}\geq 0$, we obtain the desired inequality.

Second case.

Consider $\eta_{t}=\frac{\eta}{\sqrt{t}}$ with $\eta L\leq 1$,
$w_{t}=w=\frac{1}{6\sigma^{2}\eta}$ . Again, we have
$w_{t}\eta_{t}^{2}L=\frac{\eta L}{6\sigma^{2}t}\leq\frac{1}{2\sigma^{2}}$,
then

$\displaystyle\mbox{LHS of \eqref{eq:sgd-general-bound}}=$
$\displaystyle\sum_{t=1}^{T}\left[\frac{w\eta}{\sqrt{t}}\left(1-\frac{\eta
L}{2\sqrt{t}}\right)-\frac{3\sigma^{2}w^{2}\eta^{2}}{t}\left(1-\frac{\eta
L}{\sqrt{t}}\right)^{2}\right]\left\|\nabla
f(x_{t})\right\|^{2}+w\Delta_{T+1}$ $\displaystyle=$
$\displaystyle\sum_{t=1}^{T}\frac{w\eta}{\sqrt{t}}\left[1-\frac{\eta
L}{2\sqrt{t}}-\frac{3\sigma^{2}w\eta}{\sqrt{t}}\left(1-\frac{\eta
L}{\sqrt{t}}\right)^{2}\right]\left\|\nabla
f(x_{t})\right\|^{2}+w\Delta_{T+1}$ $\geq$
$\displaystyle\sum_{t=1}^{T}\frac{w\eta}{\sqrt{t}}\left[1-\frac{\eta
L}{2\sqrt{t}}-3\sigma^{2}w\eta\left(1-\frac{\eta
L}{\sqrt{t}}\right)^{2}\right]\left\|\nabla
f(x_{t})\right\|^{2}+w\Delta_{T+1}$ $\displaystyle=$
$\displaystyle\sum_{t=1}^{T}\frac{w\eta}{\sqrt{t}}\left[1-\frac{\eta
L}{2\sqrt{t}}-\frac{1}{2}\left(1-\frac{\eta
L}{\sqrt{t}}\right)^{2}\right]\left\|\nabla
f(x_{t})\right\|^{2}+w\Delta_{T+1}$ $\displaystyle\geq$
$\displaystyle\sum_{t=1}^{T}\frac{w\eta}{2\sqrt{t}}\left\|\nabla
f(x_{t})\right\|^{2}+w\Delta_{T+1}\geq\frac{w\eta}{2\sqrt{T}}\sum_{t=1}^{T}\left\|\nabla
f(x_{t})\right\|^{2}+w\Delta_{T+1}$

where the second inequality is due to $1-\frac{\eta
L}{2\sqrt{t}}-\frac{1}{2}\left(1-\frac{\eta
L}{\sqrt{t}}\right)^{2}\geq\frac{1}{2}$ when $0\leq\frac{\eta L}{\sqrt{t}}\leq
1$. Besides,

$\displaystyle\mbox{RHS of \eqref{eq:sgd-general-bound}}=$ $\displaystyle
w\Delta_{1}+\frac{3\sigma^{2}}{2}w\eta^{2}L\sum_{t=1}^{T}\frac{1}{t}+\log\frac{1}{\delta}$
$\displaystyle\leq$ $\displaystyle
w\Delta_{1}+\frac{3\sigma^{2}}{2}w\eta^{2}L(1+\log T)+\log\frac{1}{\delta}.$

Therefore with probability $\geq 1-\delta$

$\displaystyle\sum_{t=1}^{T}\left\|\nabla
f(x_{t})\right\|^{2}+\frac{2\sqrt{T}\Delta_{T+1}}{\eta}$ $\displaystyle\leq$
$\displaystyle\sqrt{T}\left(\frac{2\Delta_{1}}{\eta}+3\sigma^{2}\eta
L\left(1+\log T\right)+\frac{2}{w\eta}\log\frac{1}{\delta}\right)$
$\displaystyle=$
$\displaystyle\sqrt{T}\left(\frac{2\Delta_{1}}{\eta}+3\sigma^{2}\eta
L\left(1+\log T\right)+12\sigma^{2}\log\frac{1}{\delta}\right).$

Choose $\eta=\frac{1}{L}$, and notice $\Delta_{T+1}\geq 0$, we obtain

$\displaystyle\frac{1}{T}\sum_{t=1}^{T}\left\|\nabla f(x_{t})\right\|^{2}$
$\displaystyle\leq\frac{2\Delta_{1}L+3\sigma^{2}\left(1+\log
T\right)+12\sigma^{2}\log\frac{1}{\delta}}{\sqrt{T}}.$

∎

##  Appendix D AdaGrad-Norm omitted proofs

We first provide the proofs for some of the Lemmas in Section 4.2.

###### Proof of Lemma 4.7.

We start by using the smoothness of $f$

$\displaystyle f(x_{t+1})-f(x_{t})$ $\displaystyle\leq\left\langle\nabla
f(x_{t}),x_{t+1}-x_{t}\right\rangle+\frac{L}{2}\left\|x_{t+1}-x_{t}\right\|^{2}$
$\displaystyle=-\frac{\eta}{b_{t}}\left\langle\nabla
f(x_{t}),\widehat{\nabla}f(x_{t})\right\rangle+\frac{L\eta^{2}}{2b_{t}^{2}}\left\|\widehat{\nabla}f(x_{t})\right\|^{2}$
$\displaystyle=-\frac{\eta}{b_{t}}\left\|\nabla
f(x_{t})\right\|^{2}-\frac{\eta}{b_{t}}\left\langle\nabla
f(x_{t}),\xi_{t}\right\rangle+\frac{L\eta^{2}}{2b_{t}^{2}}\left\|\widehat{\nabla}f(x_{t})\right\|^{2}$
$\displaystyle=\eta\left(\frac{1}{a_{t}}-\frac{1}{b_{t}}\right)\left\langle\nabla
f(x_{t}),\xi_{t}\right\rangle-\frac{\eta}{a_{t}}\left\langle\nabla
f(x_{t}),\xi_{t}\right\rangle-\frac{\eta}{b_{t}}\left\lVert\nabla
f(x_{t})\right\rVert^{2}+\frac{L\eta^{2}}{2b_{t}^{2}}\left\lVert\widehat{\nabla}f(x_{t})\right\rVert^{2}$
(20)

First, by Lemma D.2, we have

$\left|\frac{1}{a_{t}}-\frac{1}{b_{t}}\right|\leq\frac{\left\lVert\xi_{t}\right\rVert}{a_{t}b_{t}}.$

This gives

$\displaystyle\left(\frac{1}{a_{t}}-\frac{1}{b_{t}}\right)\left\langle\nabla
f(x_{t}),\xi_{t}\right\rangle$
$\displaystyle\leq\left|\frac{1}{a_{t}}-\frac{1}{b_{t}}\right|\left\lVert\nabla
f(x_{t})\right\rVert\left\lVert\xi_{t}\right\rVert$
$\displaystyle\leq\frac{\left\lVert\xi_{t}\right\rVert}{a_{t}b_{t}}\left\lVert\nabla
f(x_{t})\right\rVert\left\lVert\xi_{t}\right\rVert$
$\displaystyle\leq\left\lVert\xi_{t}\right\rVert\left(\frac{\left\lVert\nabla
f(x_{t})\right\rVert^{2}}{2a_{t}^{2}}+\frac{\left\lVert\xi_{t}\right\rVert^{2}}{2b_{t}^{2}}\right).$

Plugging this back into 20, we have

$\displaystyle f(x_{t+1})-f(x_{t})$
$\displaystyle\leq\eta\left\lVert\xi_{t}\right\rVert\left(\frac{\left\lVert\nabla
f(x_{t})\right\rVert^{2}}{2a_{t}^{2}}+\frac{\left\lVert\xi_{t}\right\rVert^{2}}{2b_{t}^{2}}\right)-\frac{\eta\left\langle\nabla
f(x_{t}),\xi_{t}\right\rangle}{a_{t}}-\frac{\eta}{b_{t}}\left\lVert\nabla
f(x_{t})\right\rVert^{2}+\frac{L\eta^{2}}{2b_{t}^{2}}\left\lVert\widehat{\nabla}f(x_{t})\right\rVert^{2}$

After summing up, rearranging the terms, using
$\left\lVert\xi_{t}\right\rVert\leq M_{T}$ and
$f(x_{1})-f(x_{T+1})\leq\Delta_{1}$, we obtain

$\displaystyle\sum_{t=1}^{T}\frac{\left\lVert\nabla
f(x_{t})\right\rVert^{2}}{b_{t}}$
$\displaystyle\leq\frac{\Delta_{1}}{\eta}+\frac{M_{T}}{2}\left[\sum_{t=1}^{T}\frac{\left\lVert\nabla
f(x_{t})\right\rVert^{2}}{a_{t}^{2}}+\sum_{t=1}^{T}\frac{\left\lVert\xi_{t}\right\rVert^{2}}{b_{t}^{2}}\right]-\sum_{t=1}^{T}\frac{\left\langle\nabla
f(x_{t}),\xi_{t}\right\rangle}{a_{t}}+\sum_{t=1}^{T}\frac{L\eta}{2b_{t}^{2}}\left\lVert\widehat{\nabla}f(x_{t})\right\rVert^{2}.$

∎

###### Proof of Lemma 4.8.

By Lemma 2.2 with some $w>0$, we have

$\mathbb{\mathbb{E}}\left[\exp\left(\left\langle-w\frac{\nabla
f(x_{t}),\xi_{t}}{a_{t}}\right\rangle-2\sigma^{2}w^{2}\frac{\left\lVert\nabla
f(x_{t})\right\rVert^{2}}{a_{t}^{2}}\right)\mid\mathcal{F}_{t}\right]\leq 1.$

Thus it is not difficult to verify that

$\mathbb{\mathbb{E}}\left[\exp\left(\sum_{t=1}^{T}\left\langle-w\frac{\nabla
f(x_{t}),\xi_{t}}{a_{t}}\right\rangle-2\sigma^{2}w^{2}\frac{\left\lVert\nabla
f(x_{t})\right\rVert^{2}}{a_{t}^{2}}\right)\right]\leq 1.$

By Markov’s inequality we obtain, with probability at least $1-\delta$,

$\sum_{t=1}^{T}-\frac{\left\langle\nabla
f(x_{t}),\xi_{t}\right\rangle}{a_{t}}\leq
2\sigma^{2}w\sum_{t=1}^{T}\frac{\left\lVert\nabla
f(x_{t})\right\rVert^{2}}{a_{t}^{2}}+\frac{1}{w}\log\frac{1}{\delta}.$

It is also known that with probability at least $1-\delta$,
$M_{T}\leq\sigma\sqrt{1+\log\frac{T}{\delta}}\leq
2\sigma\sqrt{\log\frac{T}{\delta}}$ Li and Orabona (2020); Liu et al. (2022)
for $T\geq 1$ and $\delta\in(0,1)$. Thus by a union bound and setting
$w:=\frac{\sqrt{\log\frac{1}{\delta}}}{\sigma}$, we can bound Lemma 4.7 with
probability at least $1-2\delta$

$\displaystyle\sum_{t=1}^{T}\frac{\left\lVert\nabla
f(x_{t})\right\rVert^{2}}{b_{t}}$
$\displaystyle\leq\frac{\Delta_{1}}{\eta}+M_{T}\sum_{t=1}^{T}\frac{\left\lVert\nabla
f(x_{t})\right\rVert^{2}}{2a_{t}^{2}}+M_{T}\sum_{t=1}^{T}\frac{\left\lVert\xi_{t}\right\rVert^{2}}{2b_{t}^{2}}-\sum_{t=1}^{T}\frac{\left\langle\nabla
f(x_{t}),\xi_{t}\right\rangle}{a_{t}}+\sum_{t=1}^{T}\frac{L\eta}{2b_{t}^{2}}\left\lVert\widehat{\nabla}f(x_{t})\right\rVert^{2}$
$\displaystyle\leq\frac{\Delta_{1}}{\eta}+\sigma\sqrt{\log\frac{T}{\delta}}\left[2\underbrace{\sum_{t=1}^{T}\frac{\left\lVert\nabla
f(x_{t})\right\rVert^{2}}{a_{t}^{2}}}_{B}+\sum_{t=1}^{T}\frac{\left\lVert\xi_{t}\right\rVert^{2}}{b_{t}^{2}}\right]+\sigma\sqrt{\log\frac{1}{\delta}}+\frac{L\eta}{2}\underbrace{\sum_{t=1}^{T}\frac{\left\lVert\widehat{\nabla}f(x_{t})\right\rVert^{2}}{b_{t}^{2}}}_{A}.$

Let us consider the term $A$. We have

$\displaystyle\sum_{t=1}^{T}\frac{\left\lVert\widehat{\nabla}f(x_{t})\right\rVert^{2}}{b_{t}^{2}}$
$\displaystyle=\sum_{t=1}^{T}\frac{b_{t}^{2}-b_{t-1}^{2}}{b_{t}^{2}}=\sum_{t=1}^{T}1-\frac{b_{t-1}^{2}}{b_{t}^{2}}$
$\displaystyle\leq
2\sum_{t=1}^{T}\log\frac{b_{t}}{b_{t-1}}=2\log\frac{b_{T}}{b_{0}}.$

For $B$, note that since $\left\lVert\nabla f(x_{t})\right\rVert^{2}\leq
2\left\lVert\widehat{\nabla}f(x_{t})\right\rVert^{2}+2\left\lVert\xi_{t}\right\rVert^{2}$,
we have

$\displaystyle\sum_{t=1}^{T}\frac{\left\lVert\nabla
f(x_{t})\right\rVert^{2}}{a_{t}^{2}}$
$\displaystyle=\sum_{t=1}^{T}\frac{\left\lVert\nabla
f(x_{t})\right\rVert^{2}}{b_{t-1}^{2}+\left\lVert\nabla
f(x_{t})\right\rVert^{2}}$
$\displaystyle\overset{(*)}{\leq}\sum_{t=1}^{T}\frac{2\left\lVert\widehat{\nabla}f(x_{t})\right\rVert^{2}+2\left\lVert\xi_{t}\right\rVert^{2}}{b_{t-1}^{2}+2\left\lVert\widehat{\nabla}f(x_{t})\right\rVert^{2}+2\left\lVert\xi_{t}\right\rVert^{2}}$
$\displaystyle=\sum_{t=1}^{T}\frac{2\left\lVert\widehat{\nabla}f(x_{t})\right\rVert^{2}}{b_{t-1}^{2}+2\left\lVert\widehat{\nabla}f(x_{t})\right\rVert^{2}+2\left\lVert\xi_{t}\right\rVert^{2}}+\sum_{t=1}^{T}\frac{2\left\lVert\xi_{t}\right\rVert^{2}}{b_{t-1}^{2}+2\left\lVert\widehat{\nabla}f(x_{t})\right\rVert^{2}+2\left\lVert\xi_{t}\right\rVert^{2}}$
$\displaystyle\leq
2\sum_{t=1}^{T}\frac{\left\lVert\widehat{\nabla}f(x_{t})\right\rVert^{2}}{b_{t}^{2}}+2\sum_{t=1}^{T}\frac{\left\lVert\xi_{t}\right\rVert^{2}}{b_{t}^{2}}$
$\displaystyle\leq
4\log\left(\frac{b_{T}}{b_{0}}\right)+2\sum_{t=1}^{T}\frac{\left\lVert\xi_{t}\right\rVert^{2}}{b_{t}^{2}}.$

For $(*)$ we use the fact that $\frac{x}{c+x}$ is an increasing function.
Combining the bound for $A$ and $B$, we obtain, with probability at least
$1-2\delta$,

$\displaystyle\sum_{t=1}^{T}\frac{\left\lVert\nabla
f(x_{t})\right\rVert^{2}}{b_{t}}$
$\displaystyle\leq\frac{\Delta_{1}}{\eta}+\sigma\sqrt{\log\frac{T}{\delta}}\left[8\log\left(\frac{b_{T}}{b_{0}}\right)+5\sum_{t=1}^{T}\frac{\left\lVert\xi_{t}\right\rVert^{2}}{b_{t}^{2}}\right]+\sigma\sqrt{\log\frac{1}{\delta}}+L\eta\log\frac{b_{T}}{b_{0}}.$

∎

######  Lemma D.1.

For AdaGrad-Norm stepsizes $b_{t}$, if $f$ is $L$-smooth and the stochastic
gradients have $\sigma$-subgaussian noise, then with probability at least
$1-\delta$

$\displaystyle b_{T}$ $\displaystyle\leq
4b_{0}+4\frac{\Delta_{1}}{\eta}+\frac{32}{\eta^{2}b_{0}}\sigma^{2}\ln\left(\frac{2}{\delta}\right)+\frac{16\sigma}{\eta^{2}}\sqrt{T+\log\frac{2}{\delta}}+4L\eta\log\frac{L\eta}{b_{0}}$
$\displaystyle=O\left(\Delta_{1}+\sigma\sqrt{T}+\sigma^{2}\log\frac{1}{\delta}+L\log
L\right).$

###### Proof.

We start from function value analysis

$\displaystyle f(x_{t+1})-f(x_{t})$ $\displaystyle\leq\left\langle\nabla
f(x_{t}),x_{t+1}-x_{t}\right\rangle+\frac{L}{2}\left\lVert
x_{t+1}-x_{t}\right\rVert^{2}$
$\displaystyle=\frac{1}{b_{t}}\left\langle\widehat{\nabla}f(x_{t}),\xi_{t}\right\rangle+\eta\left(\frac{L\eta}{2b_{t}^{2}}-\frac{1}{2b_{t}}\right)\left\lVert\widehat{\nabla}f(x_{t})\right\rVert^{2}-\frac{\eta}{2b_{t}}\left\lVert\widehat{\nabla}f(x_{t})\right\rVert^{2}.$

We can bound
$\sum_{t=1}^{T}\left(\frac{L\eta}{2b_{t}^{2}}-\frac{1}{2b_{t}}\right)\left\lVert\widehat{\nabla}f(x_{t})\right\rVert^{2}$via
a standard argument. Let $\tau=\max\left\\{t\leq T\mid b_{t}\leq\eta
L\right\\}$ so that $t\geq\tau$ implies $b_{t}\geq\eta
L\iff\frac{L\eta}{b_{t}^{2}}\leq\frac{1}{b_{t}}$ . Then

$\displaystyle\sum_{t=1}^{T}\left(\frac{L\eta}{2b_{t}^{2}}-\frac{1}{2b_{t}}\right)\left\lVert\widehat{\nabla}f(x_{t})\right\rVert^{2}$
$\displaystyle\leq\sum_{t=1}^{\tau}\left(\frac{L\eta}{2b_{t}^{2}}-\frac{1}{2b_{t}}\right)\left\lVert\widehat{\nabla}f(x_{t})\right\rVert^{2}$
$\displaystyle\leq\frac{L\eta}{2}\sum_{t=1}^{\tau}\frac{1}{b_{t}^{2}}\left\lVert\widehat{\nabla}f(x_{t})\right\rVert^{2}$
$\displaystyle=L\eta\log\frac{b_{\tau}}{b_{0}}\leq
L\eta\log\frac{L\eta}{b_{0}}.$

Summing and plugging in the above gives

$\displaystyle f(x_{T+1})-f(x_{1})$
$\displaystyle\leq\sum_{t=1}^{T}\frac{1}{b_{t}}\left\langle\widehat{\nabla}f(x_{t}),\xi_{t}\right\rangle+L\eta^{2}\log\frac{L\eta}{b_{0}}-\frac{\eta}{2}\sum_{t=1}^{T}\frac{\left\lVert\widehat{\nabla}f(x_{t})\right\rVert^{2}}{b_{t}}$
$\displaystyle\leq\frac{1}{\eta}\sum_{t=1}^{T}\frac{\left\lVert\xi_{t}\right\rVert^{2}}{b_{t}}-\frac{\eta}{4}\sum_{t=1}^{T}\frac{\left\lVert\widehat{\nabla}f(x_{t})\right\rVert^{2}}{b_{t}}+L\eta^{2}\log\frac{L\eta}{b_{0}},$

where we use
$\frac{1}{b_{t}}\left\langle\widehat{\nabla}f(x_{t}),\xi_{t}\right\rangle\leq\frac{\left\lVert\xi_{t}\right\rVert^{2}}{\eta
b_{t}}+\frac{\eta\left\lVert\widehat{\nabla}f(x_{t})\right\rVert^{2}}{4b_{t}}$
in the second inequality. Rearranging and dividing by $\eta$, we get

$\sum_{t=1}^{T}\frac{\left\lVert\widehat{\nabla}f(x_{t})\right\rVert^{2}}{4b_{t}}\leq\frac{f(x_{1})-f(x_{T+1})}{\eta}+\frac{1}{\eta^{2}}\sum_{t=1}^{T}\frac{\left\lVert\xi_{t}\right\rVert^{2}}{b_{t}}+L\eta\log\frac{L\eta}{b_{0}}.$

On the LHS, we have

$\displaystyle\sum_{t=1}^{T}\frac{\left\lVert\widehat{\nabla}f(x_{t})\right\rVert^{2}}{b_{t}}$
$\displaystyle=\sum_{t=1}^{T}\frac{b_{t}^{2}-b_{t-1}^{2}}{b_{t}}\geq\sum_{t=1}^{T}b_{t}-\frac{b_{t-1}^{2}}{b_{t-1}}=b_{T}-b_{0}.$

Combining this with Lemma D.5 where
$\sum_{t=1}^{T}\frac{\left\lVert\xi_{t}\right\rVert^{2}}{b_{t}}\leq\frac{8}{b_{0}}\sigma^{2}\ln\left(\frac{2}{\delta}\right)-b_{0}+4\sigma\sqrt{T+\log\frac{2}{\delta}}$,
we get the result. ∎

Now, we can prove Theorem 4.5.

###### Proof of Theorem 4.5.

From Lemma 4.8, we have with probability at least $1-2\delta$

$\sum_{t=1}^{T}\frac{\left\lVert\nabla
f(x_{t})\right\rVert^{2}}{b_{t}}\leq\frac{\Delta_{1}}{\eta}+\sigma\sqrt{\log\frac{T}{\delta}}\left[8\log\left(\frac{b_{T}}{b_{0}}\right)+5\sum_{t=1}^{T}\frac{\left\lVert\xi_{t}\right\rVert^{2}}{b_{t}^{2}}\right]+\sigma\sqrt{\log\frac{1}{\delta}}+L\eta\log\frac{b_{T}}{b_{0}}.$

Since $b_{t}$ is increasing, we have $\sum_{t=1}^{T}\frac{\left\lVert\nabla
f(x_{t})\right\rVert^{2}}{b_{t}}\geq\sum_{t=1}^{T}\frac{\left\lVert\nabla
f(x_{t})\right\rVert^{2}}{b_{T}}$. That means

$\sum_{t=1}^{T}\left\lVert\nabla f(x_{t})\right\rVert^{2}\leq