# Cyclic descents for Motzkin paths

Bin Han  Department of Mathematics, Royal institute of Technology (KTH), SE
100-44 Stockholm, Sweden<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

A notion of cyclic descents on standard Young tableaux (SYT) of rectangular
shape was introduced by Rhoades, and extended to certain skew shapes by Adin,
Elizalde and Roichman. The cyclic descent set restricts to the usual descent
set when the largest value is ignored, and has the property that the number of
SYT of a given shape with a given cyclic descent set D is invariant under
cyclic shifts of the entries of D. Adin, Reiner and Roichman proved that a
skew shape has a cyclic descent map if and only if it is not a connected
ribbon. Unfortunately, their proof is nonconstructive. Recently Huang
constructed an explicit cyclic descent map for all shapes where this is
possible.

In the earlier version of Adin, Elizalde and Roichman’s paper, they asked to
find statistics on combinatorial objects which are equidistributed with cyclic
descents on SYT of given shapes. In this paper, we explicitly describe cyclic
descent sets for Motzkin paths, which are equidistributed with cyclic descent
sets of SYT for three-row shapes. Moreover, in light of Stanley’s shuffling
theorem, we give a bijective proof of the shuffling property of descent
statistics for Motzkin paths.

Supported by the Israel Science Foundation, grant no. 1970/18 as a
postdoctoral fellow at Bar Ilan University, during which most of the work was
done. Currently supported by a Starting Grant (No. 2019-05195) from
Vetenskapsrådet (The Swedish Research Council)

MSC: 05A19, 05E10

Keywords: Cyclic descent, Motzkin path, Standard Young Tableaux, Bijection

###### Contents

  1. 1 Introduction
  2. 2 Proof of Theorem 1.10
  3. 3 A cyclic extension for a different order
  4. 4 Cyclic descents of Motzkin paths in terms of standard Young tableaux

##  1\. Introduction

Let ${\mathcal{S}}_{n}$ denote the symmetric group on $[n]=\\{1,\ldots,n\\}$.
For a permutation $\pi\in{\mathcal{S}}_{n}$, the descent set of $\pi$ is
defined by

$\operatorname{Des}(\pi):=\\{i\in[n-1]:\pi(i)>\pi(i+1)\\}.$

The notion of cyclic descent was introduced by Cellini [7] and further studied
by Dilks, Petersen, Stembridge [9]. The cyclic descent set is defined, for
$\pi\in{\mathcal{S}}_{n}$, by

$\operatorname{cDes}(\pi):=\begin{cases}\operatorname{Des}(\pi)\cup\\{n\\}&\pi(n)>\pi(1),\\\
\operatorname{Des}(\pi)&\pi(n)<\pi(1).\end{cases}$

Moreover, let $\phi:{\mathcal{S}}_{n}\mapsto{\mathcal{S}}_{n}$ be the cyclic
rotation function, such that

$(\phi\pi)(i)=\pi(i-1)$

for each $\pi\in{\mathcal{S}}_{n}$, where indices are taken modulo $n$. Then
$\phi$ has the property that for any $\pi\in{\mathcal{S}}_{n}$,

$\operatorname{cDes}(\pi)+1=\operatorname{cDes}(\phi\pi),$ (1)

where $\operatorname{cDes}(\pi)+1$ denotes the set obtained from
$\operatorname{cDes}(\pi)$ by adding $1\pmod{n}$ to each element. Property (1)
of the bijection $\phi$ implies that the multiset
$\\{\\{\operatorname{cDes}(\pi)|\pi\in{\mathcal{S}}_{n}\\}\\}$ is rotation-
invariant modulo $n$.

Rhoades introduced a cyclic descent notion for standard Young tableaux (SYT),
but only for rectangular shapes [15]; the definition of SYT is postponed to
Section 4. A generalization of this notion to other skew shapes, was
introduced in [1, 4, 13].

The following definition of cyclic extension is due to Adin, Reiner and
Roichman.

######  Definition 1.1.

[4, Definition 2.1] Let $\mathcal{F}$ be a finite set, equipped with a descent
map $\operatorname{Des}:\mathcal{F}\longrightarrow 2^{[n-1]}$. A cyclic
extension of $\operatorname{Des}$ is a pair $(\operatorname{cDes},p)$, where
$\operatorname{cDes}:\mathcal{F}\longrightarrow 2^{[n]}$ is a map and
$p:\mathcal{F}\longrightarrow\mathcal{F}$ is a bijection, satisfying the
following axioms: for all $F$ in $\mathcal{F}$,

$\begin{array}[]{rl}\text{(extension)}&\operatorname{cDes}(F)\cap[n-1]=\operatorname{Des}(F),\\\
\text{(equivariance)}&\operatorname{cDes}(p(F))=\operatorname{cDes}(F)+1,{\rm
with\,\,indices\,\,taken\,\,modulo}\,\,$n$.\\\ \text{(non-
Escher)}&\varnothing\subsetneq\operatorname{cDes}(F)\subsetneq[n].\\\
\end{array}$

In an earlier version of Adin, Elizalde and Roichman [1], they posed the
following problem.

######  Problem 1.2.

Find statistics on combinatorial objects which are equidistributed with cyclic
descents on SYT of given shapes.

Motivated by the above problem, we aim to find cyclic descent sets for Motzkin
paths in this paper.

A Motzkin path of length $n$ is a lattice path in the integer plane
${\mathbb{Z}}\times{\mathbb{Z}}$ from $(0,0)$ to $(n,0)$ which consists of
three kinds of steps $\textsc{U}=(1,1)$, $\textsc{D}=(1,-1)$ and
$\textsc{L}=(1,0)$ and never passes below the $x$-axis. A Dyck path is a
Motzkin path without L steps. Recently, Adin, Elizalde and Roichman [1,
Section 5] provided an explicit combinatorial description of a cyclic descent
extension for Dyck paths. It is natural to consider a cyclic descent extension
for Motzkin paths.

Let ${\mathbf{M}}_{n}$ denote the set of Motzkin paths with $n$ steps. A
return (resp. start) of a path in ${\mathbf{M}}_{n}$ is a D (resp. U) step
that ends (resp. starts) on the $x$-axis.

Consider the order $\textsc{U}>\textsc{D}>\textsc{L}$ on Motzkin path steps.
This order induces a descent map $\operatorname{Des}:{\mathbf{M}}_{n}\mapsto
2^{[n-1]}$ defined as follows.

######  Definition 1.3.

The step $i\in[n]$ is a descent of a path $M\in{\mathbf{M}}_{n}$ if one of the
following conditions holds:

  1. 1.

The $i$th step of $M$ is a U followed by a D.

  2. 2.

The $i$th step of $M$ is a U followed by a L.

  3. 3.

The $i$th step of $M$ is a D followed by a L.

Let $\operatorname{Des}\,(M)$ denote the set of descents of $M$.

######  Remark 1.4.

  1. 1.

For Motzkin paths without L steps, descent sets in Definition 3.4 coincide
with those of Dyck paths, see [1, Definition 5.1].

  2. 2.

Let $T_{3}(n)$ denote the set of SYTs with $n$ entries and at most $3$ rows.
Regev [14] proved that $|T_{3}(n)|$ is equal to the $n$-th Motzkin number. Eu
[10] provided a bijection between $T_{3}(n)$ and ${\mathbf{M}}_{n}$, but it
does not preserve the descent set in general. We give a bijection between
$T_{3}(n)$ and ${\mathbf{M}}_{n}$ preserving the descent set.

  3. 3.

We construct a cyclic extension of this descent map. In fact, we achieve this
for all of the orderings $\textsc{U}>\textsc{D}>\textsc{L}$,
$\textsc{U}>\textsc{L}>\textsc{D}$ and $\textsc{L}>\textsc{U}>\textsc{D}$.

For a finite set (alphabet) $A$ of size $a$, let ${\mathcal{S}}_{A}$ be the
set of all bijections $u:[a]\to A$, viewed as words $u=(u_{1},\ldots,u_{a})$.
If $A=[a]$ then ${\mathcal{S}}_{A}$ is the symmetric group
${\mathcal{S}}_{a}$, whose elements are permutations of $[a]$.

Richard Stanley’s theory of P-partitions [16] implies that the descent set
statistic has a remarkable property related to shuffles: for any two
permutations $\pi$ and $\sigma$ on disjoint alphabet $s$, the descent set over
all shuffles of $\pi$ and $\sigma$ depends only on $\operatorname{Des}(\pi)$,
$\operatorname{Des}(\sigma)$, and the lengths of $\pi$ and $\sigma$ [17,
Exercise 3.161]. The following classical result is due to Stanley.

######  Lemma 1.5.

([17, Exercise 3.161] and [12, Section 2.4]) Let A and B be two disjoint sets
of integers. For each $u\in{\mathcal{S}}_{A}$ and $v\in{\mathcal{S}}_{B}$, the
distribution of the descent set over all shuffles of $u$ and $v$ depends only
on $\operatorname{Des}(u)$, $\operatorname{Des}(v)$ and the lengths of $u$ and
$v$.

Every Motzkin path is a shuffle of a Dyck path and a horizontal path. By
suitable labelings, monotone on each type of step separately, we can view them
as permutations. Applying Lemma 1.5, we obtain the following proposition
immediately.

######  Proposition 1.6.

The descent distributions on all Motzkin paths are the same for the orderings
$\textsc{U}>\textsc{D}>\textsc{L}$, $\textsc{U}>\textsc{L}>\textsc{D}$ and
$\textsc{L}>\textsc{U}>\textsc{D}$.

We give a bijective proof for the above result in Section 3.

For motzkin paths with the order $\textsc{U}>\textsc{D}>\textsc{L}$, we define
the cyclic descent extension as follows.

######  Definition 1.7.

For $M\in{\mathbf{M}}_{n}$, let $n\in{\operatorname{cDes}}(M)$ if and only if
either of the following conditions holds:

  1. 1.

The first step of $M$ is L and the final step of $M$ is D.

  2. 2.

The first step of $M$ is U, the final step of $M$ is D and $M$ has no returns
before the rightmost D.

######  Remark 1.8.

  1. 1.

When $M\in{\mathbf{M}}_{n}$ has no L steps, Definition 1.7 coincides with that
of Adin, Elizalde and Roichman for Dyck paths, see [1, Definition 5.7].

  2. 2.

It is clear from Definition 1.3 and Definition 1.7 that having
$\\{n-1,n\\}\subseteq\operatorname{cDes}(M)$ forces
$1,n-2\notin\operatorname{cDes}(M)$ or
$\\{n,1\\}\subseteq\operatorname{cDes}(M)$ forces
$n-1,2\notin\operatorname{cDes}(M)$. That is consistent with the fact that a
Motzkin path can not have three descents in consecutive positions.

######  Example 1.9.

Figure 1 shows two instances of $M\in{\mathbf{M}}_{6}$ for which
$6\in{\operatorname{cDes}}(M)$.

$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$235{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}6}$

$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$134{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}6}$

Figure 1. Cyclic descent sets of two Motzkin paths in ${\mathbf{M}}_{6}$.

Let $\textsc{L}^{n}$ denote the path in ${\mathbf{M}}_{n}$ whose steps are all
L steps. Because of the non-Escher property of a cyclic extension, i.e.,
$\operatorname{cDes}(M)\neq\emptyset$ for $M\in{\mathbf{M}}_{n}$, we only
consider a cyclic descent extension on
${\mathbf{M}}^{*}_{n}:={\mathbf{M}}_{n}\setminus{\\{\textsc{L}^{n}\\}}$. For
any fixed $0\leq k<n$, define

${\mathbf{M}}_{n,k}:=\\{M\in{\mathbf{M}}_{n}:|M|_{\textsc{L}}=k\\},$

where $|M|_{\textsc{L}}$ is the number of L steps in a Motzkin path $M$. Our
main result for Motzkin paths is stated next; the precise definition of $\rho$
is postponed to Section 2.

######  Theorem 1.10.

For any $n\geq 3$ and $0\leq k<n$, the pair $({\operatorname{cDes}},\rho)$,
with $\operatorname{cDes}$ and $\rho$ determined by Definition 1.7 and
Definition 2.1, respectively, is a cyclic extension of ${\operatorname{Des}}$
on ${\mathbf{M}}_{n,k}$.

Note that for $n\leq 1$, $M_{n}^{*}=\varnothing$; and for $n=2$,
$M_{2}^{*}=\\{UD\\}$ has a single element and therefore $\operatorname{Des}$
has no (non-Escher) cyclic extension. By Theorem 1.10, we obtain the following
corollary immediately.

######  Corollary 1.11.

For any $n\geq 3$, the pair $({\operatorname{cDes}},\rho)$ is a cyclic
extension of $\operatorname{Des}$ on ${\mathbf{M}}^{*}_{n}$.

The paper is organized as follows. In Section 2, we prove Theorem 1.10. In
Section 3, we give another equivalent cyclic extension for Motzkin paths. In
Section 4, we describe the cyclic extension of Motzkin paths in terms of
standard Young tableaux.

##  2\. Proof of Theorem 1.10

Observation: $\operatorname{cDes}(M)=\varnothing$ if and only if $M=L^{n}$.
$\operatorname{cDes}(M)=[n]$ if and only if $M=\textsc{U}\textsc{D}$ (and
$n=2$). We construct a bijection
$\rho:{\mathbf{M}}^{*}_{n}\to{\mathbf{M}}^{*}_{n}$ such that
${\operatorname{cDes}}(\rho M)=1+{\operatorname{cDes}}(M)$ for all
$M\in{\mathbf{M}}^{*}_{n}\,(n\geq 3)$, with addition modulo $n$. Our
construction of $(\operatorname{cDes},\rho)$ comes from the idea that for all
$1\leq i\leq n$, we have that $i\in\operatorname{cDes}(M)$ if and only if
$i+1\in\operatorname{cDes}(\rho M)\pmod{n}$.

######  Definition 2.1.

Given $M\in{\mathbf{M}}^{*}_{n}$, define $\rho M$ by considering two cases:

  1. 1.

The final step of $M$ is L. Let $\rho M$ be the path obtained by moving the
last L of $M$ and inserting it as the first step of the path. In other words,
write $M=\textsc{P}\textsc{L}$ for any Motzkin path
$\textsc{P}\neq\textsc{L}^{n-1}$, and let $\rho M=\textsc{L}\textsc{P}$, see
Figure 2 for an example.

$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\operatorname{cDes}(M)=\\{2,4,5\\}$$\mapsto$$\rho$

$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\operatorname{cDes}(M^{\prime})=\\{3,5,{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}6}\\}$

Figure 2. Case 1: $\rho(M)=M^{\prime}$

  2. 2.

The final step of $M$ is D. Let $\rho M$ be the path obtained by two steps.

    1. (a)

First, move the last D of $M$ and insert it before the final start step of the
path.

    2. (b)

Second, move the last start step U of $M$ and insert it as the first step of
the path.

Write $M=\textsc{P}\textsc{U}\textsc{P}^{\prime}\textsc{D}$, where U is the
final start step of $M$, P and $\textsc{P}^{\prime}$ are any (possibly empty)
Motzkin paths. Let $\rho M=\textsc{U}\textsc{P}\textsc{D}\textsc{P}^{\prime}$,
see Figure 3 for an example.

$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\operatorname{cDes}(M)=\\{1,2,4\\}$$\mapsto$$\rho$

$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\operatorname{cDes}(M^{\prime})=\\{2,3,5\\}$

Figure 3. Case 2: $\rho(M)=M^{\prime}$

Observing all two cases of Definition 2.1, we obtain the following property of
$\rho$.

######  Proposition 2.2.

The number of horizontal steps is invariant under the shift operation $\rho$
on Motzkin paths.

###### Proof of Theorem 1.10.

By Proposition 2.2 $\rho$ maps $M_{n,k}$ into itself. To prove Theorem 1.10 we
need to show that $(\operatorname{cDes},\rho)$ satisfies the extension, non-
Escher and equivariance. Extension follows from Definition 1.3 and Definition
1.7. For $M\in{\mathbf{M}}^{*}_{n}$, $M$ has at least one U step (which cannot
be the last step), and thus by Definition 1.3, we have
$1\leq|\operatorname{cDes}(M)|$. By Remark 1.8, we have, for $n\geq 3$,
$|\operatorname{cDes}(M)|\leq n-1$. This implies the non-Escher property. To
prove the equivariance property, we need to show that
$\operatorname{cDes}(\rho M)=1+\operatorname{cDes}(M)$, with addition modulo
$n$, in all two cases of Definition 2.1. For example, in case $1$, we have
that $n\notin\operatorname{cDes}(M)$ and $1\notin\operatorname{cDes}(\rho
M)$(by Definition 1.3 and Definition 1.7), whereas
$n-1\in\operatorname{cDes}(M)$ if and only if the final step of P is D which
implies $n\in\operatorname{cDes}(\rho M)$; additionally, for all $1\leq i\leq
n-2$, we have that $i\in\operatorname{cDes}(M)$ if and only if
$i+1\in\operatorname{cDes}(\rho M)$ because all such descents must be inside
P, which is shifted one position to the right by $\rho$. Similarly for the
other case.

To prove that $\rho$ is a bijection, we describe its inverse in each of the
two cases above. For a given $M\in{\mathbf{M}}^{*}_{n}$, define $\rho^{-1}M$
as follows:

  1. 1.

The first step of $M$ is L. Let $\rho^{-1}M$ be the path obtained by moving
the first L of $M$ and inserting it as the last step of the path. In other
words, write $M=\textsc{L}\textsc{P}$ for any Motzkin path
$\textsc{P}\neq\textsc{L}^{n-1}$, and let $\rho^{-1}M=\textsc{P}\textsc{L}$.

  2. 2.

The first step of $M$ is U. Let $\rho^{-1}M$ be the path obtained by two
steps.

    1. (a)

First, move the first U of $M$ and insert it before the first return step of
the path.

    2. (b)

Second, move the first return step D of $M$ and insert it as the final step of
the path.

In other words, write $M=\textsc{U}\textsc{P}\textsc{D}\textsc{P}^{\prime}$,
where D is the first return step of $M$, P and $\textsc{P}^{\prime}$ are any
(possibly empty) Motzkin paths. Then we define
$\rho^{-1}M=\textsc{P}\textsc{U}\textsc{P}^{\prime}\textsc{D}$.

∎

##  3\. A cyclic extension for a different order

In this section, we construct a cyclic descent extension of the descent map on
Motzkin paths, for a different order between the $\textsc{U},\textsc{L}$ and D
step types. We first introduce the following two bijections, which preserve
the descent set under different orderings of the three step types U, L, D.

######  Lemma 3.1.

  1. 1.

For $M\in{\mathbf{M}}_{n}$, there is a descent set preserving bijection
$\varphi$ on Motzkin paths which transforms $\textsc{U}>\textsc{L}>\textsc{D}$
to $\textsc{U}>\textsc{D}>\textsc{L}$ and preserves the numbers of U, L and D
steps.

  2. 2.

For $M\in{\mathbf{M}}_{n}$, there is a descent set preserving bijection
$\varphi^{\prime}$ on Motzkin paths which transforms
$\textsc{L}>\textsc{U}>\textsc{D}$ to $\textsc{U}>\textsc{L}>\textsc{D}$ and
preserves the numbers of U, L and D steps.

###### Proof.

The map $\varphi:M\to M$ can be described as follows. Preserve the locations
of all U’s and all other descents (LD, which transform to DL). In all
intermediate intervals (between U’s and descents) reverse the (descent-free)
sequence of letters:
$\textsc{D}^{a}\textsc{L}^{b}\to\textsc{L}^{b}\textsc{D}^{a}$. It is easy to
see that $\varphi$ is a bijection by considering the inverse map. Clearly
$\varphi$ preserves the numbers of U, L and D steps.

Similarly, The map $\varphi^{\prime}:M\to M$ can be described as follows.
Preserve the locations of all D’s and all other descents (LU, which transform
to UL). In all intermediate intervals (between D’s and descents) reverse the
(descent-free) sequence of letters:
$\textsc{U}^{a}\textsc{L}^{b}\to\textsc{L}^{b}\textsc{U}^{a}$. It is easy to
see $\varphi^{\prime}$ is a bijection by considering the inverse map. Clearly
$\varphi^{\prime}$ preserves the numbers of U, L and D steps. ∎

######  Example 3.2.

For $M\in{\mathbf{M}}_{7}$, we have

$\displaystyle\textsc{U}\textsc{U}\textsc{D}\textsc{D}\textsc{L}\textsc{L}\textsc{L}\xrightarrow[]{\varphi}\textsc{U}\textsc{U}\textsc{L}\textsc{L}\textsc{L}\textsc{D}\textsc{D}\xrightarrow[]{\varphi}\textsc{U}\textsc{U}\textsc{L}\textsc{L}\textsc{D}\textsc{L}\textsc{D}$
$\displaystyle\xrightarrow[]{\varphi}\textsc{U}\textsc{U}\textsc{L}\textsc{D}\textsc{L}\textsc{D}\textsc{L}\xrightarrow[]{\varphi}\textsc{U}\textsc{U}\textsc{D}\textsc{L}\textsc{D}\textsc{L}\textsc{L}(\xrightarrow[]{\varphi}\textsc{U}\textsc{U}\textsc{D}\textsc{D}\textsc{L}\textsc{L}\textsc{L}),$

and

$\displaystyle\textsc{U}\textsc{U}\textsc{L}\textsc{L}\textsc{L}\textsc{D}\textsc{D}\xrightarrow[]{\varphi^{\prime}}\textsc{L}\textsc{L}\textsc{L}\textsc{U}\textsc{U}\textsc{D}\textsc{D}\xrightarrow[]{\varphi^{\prime}}\textsc{L}\textsc{L}\textsc{U}\textsc{L}\textsc{U}\textsc{D}\textsc{D}$
$\displaystyle\xrightarrow[]{\varphi^{\prime}}\textsc{L}\textsc{U}\textsc{L}\textsc{U}\textsc{L}\textsc{D}\textsc{D}\xrightarrow[]{\varphi^{\prime}}\textsc{U}\textsc{L}\textsc{U}\textsc{L}\textsc{L}\textsc{D}\textsc{D}(\xrightarrow[]{\varphi^{\prime}}\textsc{U}\textsc{U}\textsc{L}\textsc{L}\textsc{L}\textsc{D}\textsc{D}).$

Lemma 3.1 yields a bijective proof of Proposition 1.6.

By Corollary 1.11 and Proposition 1.6, we have the following result.

######  Proposition 3.3.

The descent map on ${\mathbf{M}}^{*}_{n}$ has a cyclic extension for each of
the orders $\textsc{U}>\textsc{D}>\textsc{L}$,
$\textsc{U}>\textsc{L}>\textsc{D}$ and $\textsc{L}>\textsc{U}>\textsc{D}$.

We shall find an explicit construction of a cyclic descent extension for the
order $\textsc{U}>\textsc{L}>\textsc{D}$. The construction for
$\textsc{L}>\textsc{U}>\textsc{D}$ is left to the interested reader.

######  Definition 3.4.

Assume that $\textsc{U}>\textsc{L}>\textsc{D}$. An index $i$ is a descent of a
path $M\in{\mathbf{M}}_{n}$ if one of the following conditions holds:

  1. 1.

The $i$th step of $M$ is a U followed by a D.

  2. 2.

The $i$th step of $M$ is a U followed by an L.

  3. 3.

The $i$th step of $M$ is an L followed by a D.

Let $\widehat{\operatorname{Des}}(M)$ denote the set of descents of $M$.

We now define the following cyclic descents.

######  Definition 3.5.

For $M\in{\mathbf{M}}_{n}$, let $n\in\widehat{\operatorname{cDes}}(M)$ if and
only if either of the following conditions holds:

  1. 1.

The first step of $M$ is L and the step preceding the rightmost return is not
an L.

  2. 2.

The first step of $M$ is U, $M$ has only one return, and the step preceding
the return is not an L.

######  Example 3.6.

By Definition 3.4 and Definition 3.5, we give two examples in Figure 4.

$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$24{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}6}$

$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$134{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}6}$

Figure 4. Cyclic descent sets of two Motzkin paths in ${\mathbf{M}}_{6}$

We construct a bijection
$\hat{\rho}:{\mathbf{M}}^{*}_{n}\to{\mathbf{M}}^{*}_{n}$ such that
$\operatorname{cDes}(\hat{\rho}M)=1+\operatorname{cDes}(M)$ for all
$M\in{\mathbf{M}}^{*}_{n}\,(n\geq 3)$, where addition is modulo $n$.

######  Definition 3.7.

Given $M\in{\mathbf{M}}^{*}_{n}$, define $\hat{\rho}M$ by considering three
cases:

  1. 1.

If the step before the last return of $M$ is U. Write
$M=\textsc{P}\textsc{L}^{i}\textsc{U}\textsc{D}\textsc{L}^{j}\,(i,j\geq 0)$,
where P may be empty or the final step of
$\textsc{P}\in{\mathbf{M}}_{n-2-i-j}$ is D. There are two cases.

    1. (a)

When $j=0$, let $\hat{\rho}M$ be the path obtained by two steps.

      1. (i)

First, move the last U of $M$ and insert it as the first step of the path.

      2. (ii)

Second, move the last D of $M$ and insert it after the second D step of the
path from right to left.

In other words, let
$\hat{\rho}M=\textsc{U}\textsc{P}\textsc{D}\textsc{L}^{i}$. See Figure 5 for
an example.

$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\operatorname{cDes}(M)=\\{2,5,{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}6}\\}$$\mapsto$$\hat{\rho}$

$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\operatorname{cDes}(M^{\prime})=\\{1,3,{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}6}\\}$

Figure 5. Case 1(a): $\hat{\rho}(M)=M^{\prime}$

    2. (b)

When $j\geq 1$, let
$\hat{\rho}M=\textsc{U}\textsc{P}\textsc{L}^{i+1}\textsc{D}\textsc{L}^{j-1}$.
See Figure 6 for an example.

$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\operatorname{cDes}(M)=\\{2,4,{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}6}\\}$$\mapsto$$\hat{\rho}$

$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\operatorname{cDes}(M^{\prime})=\\{1,3,5\\}$

Figure 6. Case 1(b): $\hat{\rho}(M)=M^{\prime}$

  2. 2.

If the step before the last return of $M$ is L. Write
$M=\textsc{P}\textsc{L}^{i}\textsc{D}\textsc{L}^{j}\,(i\geq 1,j\geq 0)$, where
the final step of $\textsc{P}\in{\mathbf{M}}_{n-1-i-j}$ is not L. There are
two cases.

    1. (a)

When $j=0$, let $\hat{\rho}M$ be the path obtained by two steps.

      1. (i)

First, move the last L of $M$ and insert it as the first step of the path.

      2. (ii)

Second, move the last D of $M$ and insert it after the second non L step of
the path from right to left.

In other words, let
$\hat{\rho}M=\textsc{L}\textsc{P}\textsc{D}\textsc{L}^{i-1}$. See Figure 7 for
an example.

$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\operatorname{cDes}(M)=\\{2,4,5\\}$$\mapsto$$\hat{\rho}$

$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\operatorname{cDes}(M^{\prime})=\\{3,5,{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}6}\\}$

Figure 7. Case 2(a): $\hat{\rho}(M)=M^{\prime}$

    2. (b)

when $j\geq 1$, Let $\hat{\rho}M$ be the path obtained by moving the last L of
$M$ and inserting it as the first step of the path. In other words, let
$\hat{\rho}M=\textsc{L}\textsc{P}\textsc{L}^{i}\textsc{D}\textsc{L}^{j-1}$.
See Figure 8 for an example.

$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\operatorname{cDes}(M)=\\{2,4\\}$$\mapsto$$\hat{\rho}$

$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\operatorname{cDes}(M^{\prime})=\\{3,5\\}$

Figure 8. Case 2(b): $\hat{\rho}(M)=M^{\prime}$

  3. 3.

The step before the last return of $M$ is D. Write
$M=\textsc{P}\textsc{L}^{i}\textsc{U}\textsc{L}^{k}\textsc{P}^{\prime}\textsc{D}\textsc{L}^{j}\,(i,j,k\geq
0)$, where U is the final start U step, the final step of
$\textsc{P}\in{\mathbf{M}}_{n-2-|\textsc{P}^{\prime}|-i-j-k}$ (possibly empty)
is D, and the first step and the final step of $\textsc{P}^{\prime}$ are U and
D. There are two cases.

    1. (a)

When $k=0$, let $\hat{\rho}M$ be the path obtained by two steps.

      1. (i)

First, move the final D of $M$ and insert it after the second return of the
path from right to left.

      2. (ii)

Second, move the final start U step of $M$ and insert it as the first step of
the path.

In other words, let
$\hat{\rho}M=\textsc{U}\textsc{P}\textsc{D}\textsc{L}^{i}\textsc{P}^{\prime}\textsc{L}^{j}$
. See Figure 9 for an example.

$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\operatorname{cDes}(M)=\\{1,5\\}$$\mapsto$$\hat{\rho}$

$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\operatorname{cDes}(M^{\prime})=\\{2,6\\}$

Figure 9. Case 3(a): $\hat{\rho}(M)=M^{\prime}$

    2. (b)

When $k\geq 1$, let
$\hat{\rho}M=\textsc{U}\textsc{P}\textsc{L}^{i+1}\textsc{D}\textsc{L}^{k-1}\textsc{P}^{\prime}\textsc{L}^{j}$.
See Figure 10 for an example.

$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\operatorname{cDes}(M)=\\{2,4,{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}6}\\}$$\mapsto$$\hat{\rho}$

$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\operatorname{cDes}(M^{\prime})=\\{1,3,5\\}$

Figure 10. Case 3(b): $\hat{\rho}(M)=M^{\prime}$

######  Lemma 3.8.

[1, Observation 1.4] Let $T_{1}$ and $T_{2}$ be finite sets, let
$\theta:T_{2}\mapsto T_{1}$ be a bijection, and let ${\rm
Stat}_{1}:T_{1}\mapsto 2^{[n-1]}$ and ${\rm Stat}_{2}:T_{2}\mapsto 2^{[n-1]}$
be maps such that ${\rm Stat}_{2}={\rm Stat}_{1}\circ\theta$. If $({\rm
cStat}_{1},\phi_{1})$ is a cyclic extension of ${\rm Stat}_{1}$, then $({\rm
cStat}_{2},\phi_{2})$ with ${\rm cStat}_{2}=:{\rm cStat}_{1}\circ\theta$ and
$\phi_{2}:=\theta^{-1}\circ\phi_{1}\circ\theta$ is a cyclic extension of ${\rm
Stat}_{2}$.

Using the bijection $\varphi$ in Lemma 3.1, it is easy to check that
$\operatorname{cDes}=\widehat{\operatorname{cDes}}\circ\varphi^{-1}$ and
$\rho=\varphi\circ\hat{\rho}\circ\varphi^{-1}$. By Lemma 3.8 and Corollary
1.11, we obtain the following equivalent cyclic extension.

######  Theorem 3.9.

The pair $(\widehat{\operatorname{cDes}},\hat{\rho})$, with
${\widehat{\operatorname{cDes}}}$ and $\hat{\rho}$ determined by Definition
3.5 and Definition 3.7, respectively, is a cyclic extension of
${\widehat{\operatorname{Des}}}$ on ${\mathbf{M}}^{*}_{n}$.

##  4\. Cyclic descents of Motzkin paths in terms of standard Young tableaux

Another important family of combinatorial objects, called standard Young
tableaux (SYT), have a well-studied notion of descent set. Recall that the
Young diagram corresponding to a partition
$\lambda=(\lambda_{1},\ldots,\lambda_{k})$ with
$\lambda_{1}\geq\cdots\geq\lambda_{k}$ consists of left-justified rows so that
the $i$-th ($1\leq i\leq k$) row from the top contains $\lambda_{i}$ cells.
Let $\lambda/\mu$ denote a skew shape, where $\lambda$ and $\mu$ are
partitions such that the Young diagram of $\mu$ is contained in that of
$\lambda$, see Figure 11 for an example.

The standard Young tableaux of skew shape $\lambda/\mu$ are the labelings of
the cells of the diagram $\lambda/\mu$ with positive integers from $1$ to the
number of cells, such that each number appears once, row entries are
increasing from north to south, and column entries are increasing from west to
east. Let ${\rm SYT}(\lambda/\mu)$ denote the set of standard Young tableaux
of shape $\lambda/\mu$. For a straight shape
$\lambda=(\lambda_{1},\lambda_{2},\dots)$, we write ${\rm
SYT}(\lambda_{1},\lambda_{2},\dots)$ instead of ${\rm
SYT}((\lambda_{1},\lambda_{2},\dots))$ for simplicity. The descent set of
$T\in{\rm SYT}(\lambda/\mu)$ is

$\operatorname{Des}(T):=\\{i\in[n-1]\,:\,i+1\text{ is in a lower row than $i$
in $T$}\\},$

where $n$ is the size of skew shape. For example, the descent set of the SYT
in Figure 11 is $\\{1,4,7,8\\}$.

$\young(::147,2368,59)$ Figure 11. A SYT of shape $(5,4,2)/(2)$.

We introduce the Schützenberger promotion operator.

######  Definition 4.1.

The action of the promotion operator on $T\in{\rm SYT}(\lambda/\mu)$ is as
follows. Add $1\pmod{n}$ to each entry of $T$; this turns the $n$ into a $1$
and increments the remaining entries. Repeatedly swap $1$ with the larger of
its northern neighbor (if it exists) and its western neighbor (if it exists),
until the cell containing $1$ has neither northern nor western neighbor.

It is not difficult to show that the resulting tableau is standard. Let ${\rm
pro}$ be the (Schützenberger) promotion operator111In our notation, the
definition of promotion is consistent with that in the literature [13, 15]..

Recall that the skew shape $(n-k,n-k,n-2k)/(n-2k,n-2k)\,(0<k\leq\lfloor
n/2\rfloor)$ has the following form

mathmode, boxsize=1.5em & […]

[…]

[…] .

######  Lemma 4.2.

There exists a bijection

$\Gamma:{\mathbf{M}}_{n}\mapsto\sum_{0\leq k\leq\lfloor n/2\rfloor}{\rm
SYT}(n-k,n-k,n-2k)/(n-2k,n-2k)$

with the property that
${\operatorname{Des}}(M)=\operatorname{Des}(\Gamma(M))\,\,\,\,{\forall}\,\,\,\,M\in{\mathbf{M}}_{n}.$

###### Proof.

For $M\in{\mathbf{M}}_{n}$, let $k$ be the number of U steps (equivalently, D
steps) in $M$. Define $\Gamma\,(M)$ by inserting the entries from $1$ to $n$
into the shape ${\rm SYT}((n-k,n-k,n-2k)/(n-2k,n-2k))$ as follows: insert $i$
in the first (resp. second, third) row if the $i$th step is a U step (resp. D
step, L step), It is easy to see that $\Gamma$ is a bijection. By Definition
1.3 $i\in{\operatorname{Des}}(M)$ if and only if $i+1$ is in a lower row than
$i$ in $\Gamma(M)$, namely $i\in\operatorname{Des}(\Gamma(M))$. This completes
the proof. ∎

An important concept is the jeu de taquin (jdt) construction; see [18,
Appendix A1.2] for a detailed description. For any SYT $T$ of skew shape,
denote by $\operatorname{jdt}(T)$ the SYT of straight shape obtained from $T$
by performing a sequence of jdt slides. Jeu de taquin has the following well-
known property.

######  Lemma 4.3.

[18, p.431] For any SYT $T$ of skew shape,

$\operatorname{Des}(\operatorname{jdt}(T))=\operatorname{Des}(T).$

Combining Lemma 4.2 and Lemma 4.3, we obtain the following theorem.

######  Proposition 4.4.

There exists a bijection $\tilde{\Gamma}:=\operatorname{jdt}\circ\Gamma$,
which maps the set of Motzkin paths ${\mathbf{M}}_{n}$ to the set of SYT of
straight shape of size $n$ and at most $3$ rows, with the property that

$\operatorname{Des}(M)=\operatorname{Des}(\tilde{\Gamma}(M))\,\,\,\,{\forall}\,\,\,\,M\in{\mathbf{M}}_{n}.$

For the ${\rm SYT}$ of shape $(n-k,n-k,n-2k)/(n-2k,n-2k)$, define the cyclic
descent map as follows.

######  Definition 4.5.

For $T\in{\rm SYT}((n-k,n-k,n-2k)/(n-2k,n-2k))\,(0<k\leq\lfloor n/2\rfloor)$,
let $n\in\operatorname{cDes}(T)$ if and only if either of the following
conditions holds:

  1. 1.

$1$ and $n$ are in the third row and second row of $T$, respectively.

  2. 2.

$1$ and $n$ are in the first row and second row of $T$, respectively, and for
every $1<i<k$, $T_{2,i-1}>T_{1,i}$, where $T_{i,j}$ denotes the entry in row
$i$ (from the top) and column $j$ (from the left) of $T$.

######  Example 4.6.

According to Definition 4.5,
$6\in\operatorname{cDes}\left(\young(::25,::46,13)\right)$ and
$6\in\operatorname{cDes}\left(\young(::13,::46,25)\right)$.

######  Proposition 4.7.

For $n\geq 1$, we have

${\rm pro}\circ\Gamma=\Gamma\circ{\rho}.$ (2)

###### Proof.

For $M\in{\mathbf{M}}_{n}$, combining the definition of $\Gamma$ in the proof
of Lemma 4.2 and that of ${\rm pro}$ in Definition 4.1, it is easy to check
that Eq. (2) holds for all the cases in Definition 2.1. For example, in case
$1$, for $M=\textsc{P}\textsc{L}$ and ${\rho}(M)=\textsc{L}\textsc{P}$, the
entries $T_{i,j}+1$ of $\Gamma({\rho}(M))$ from the segment P lie in the $j$th
($1\leq j\leq 3$) row if the enries $T_{i,j}$ of $\Gamma(M)$ from the segment
P lie in the $j$th row. Since the entry $n$ of $\Gamma(M)$ lies in the third
row and the entry $1$ of $\Gamma(\rho(M))$ lies in the third row, it is easy
to check that the ${\rm pro}\circ\Gamma(T)$ coincides with
$\Gamma({\rho}(M))$.

∎

Our cyclic extension for ${\rm SYT}$ of shape $(n-k,n-k,n-2k)/(n-2k,n-2k)$ is
stated as follows.

######  Theorem 4.8.

For each $0<k\leq\lfloor n/2\rfloor$, $\operatorname{Des}$ on ${\rm
SYT}((n-k,n-k,n-2k)/(n-2k,n-2k))$ has a cyclic extension
$(\operatorname{cDes},\phi)$. The map $\operatorname{cDes}$ is defined by
Definition 4.5. The bijection $\phi:{\rm
SYT}((n-k,n-k,n-2k)/(n-2k,n-2k))\mapsto{\rm SYT}((n-k,n-k,n-2k)/(n-2k,n-2k))$
is defined by $\phi:={\rm pro}$.

###### Proof.

By Definition 1.7 and Definition 4.5, it is easy to check that the bijection
$\Gamma$ satisfies the property

$\operatorname{cDes}(\Gamma(M))={\operatorname{cDes}}(M)\,\,\,\quad\textit{for}\,\,\,\quad
M\in{\mathbf{M}}_{n}.$

Using Proposition 4.7, the map $\phi$ is the composition of bijections
$\Gamma\circ{\rho}\circ\Gamma^{-1}$ described directly in terms of ${\rm
SYT}$. By Lemma 3.8 and Lemma 4.2, we obtain the cyclic descent extension
$(\operatorname{cDes},\phi)$ of $\operatorname{Des}$ on ${\rm
SYT}((n-k,n-k,n-2k)/(n-2k,n-2k))$. ∎

######  Remark 4.9.

Recall [13, Corollary 6.4], the cyclic extension $(\operatorname{cDes},\phi)$
in Theorem 4.8 coincides with the cyclic descent extension in [13, Theorem
1.9].

######  Example 4.10.

Below are two of the orbits of the ${\mathbb{Z}}$-actions on SYT((6-k, 6-k,
6-2k)/(6-2k, 6-2k)) for $k=1,2$ generated by $\phi$, respectively.

$\text{ \begin{tabular}[]{l}$\young(::::1,::::3,2456)$\\\\[10.03749pt]
13\end{tabular} }{\overset{\phi}{\mapsto}}$$\text{
\begin{tabular}[]{l}$\young(::::2,::::4,1356)$\\\\[10.03749pt] 24\end{tabular}
}{\overset{\phi}{\mapsto}}$$\text{
\begin{tabular}[]{l}$\young(::::3,::::5,1246)$\\\\[10.03749pt] 35\end{tabular}
}{\overset{\phi}{\mapsto}}$$\text{
\begin{tabular}[]{l}$\young(::::4,::::6,1235)$\\\\[10.03749pt]
4{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}6}\end{tabular}
}{\overset{\phi}{\mapsto}}$$\text{
\begin{tabular}[]{l}$\young(::::1,::::5,2346)$\\\\[10.03749pt] 15\end{tabular}
}{\overset{\phi}{\mapsto}}$ $\young(::::2,::::6,1345)$ 26 $\phi$$\text{
\begin{tabular}[]{l}$\young(::14,::26,35)$\\\\[10.03749pt] 124\end{tabular}
}{\overset{\phi}{\mapsto}}$$\text{
\begin{tabular}[]{l}$\young(::12,::35,46)$\\\\[10.03749pt] 235\end{tabular}
}{\overset{\phi}{\mapsto}}$$\text{
\begin{tabular}[]{l}$\young(::23,::46,15)$\\\\[10.03749pt]
34{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}6}\end{tabular}
}{\overset{\phi}{\mapsto}}$$\text{
\begin{tabular}[]{l}$\young(::14,::35,26)$\\\\[10.03749pt] 145\end{tabular}
}{\overset{\phi}{\mapsto}}$$\text{
\begin{tabular}[]{l}$\young(::25,::46,13)$\\\\[10.03749pt]
25{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}6}\end{tabular}
}{\overset{\phi}{\mapsto}}$ $\young(::13,::56,24)$ 136 $\phi$

## Acknowledgement

The author thanks Prof. Adin and Prof. Roichman for their helpful suggestions.
The author also thanks the anonymous referees for their valuable comments.

## References

  * [1] R. M. Adin, S. Elizalde, Y. Roichman, Cyclic descents for near-hook and two-row shapes, European J. Combin. 79 (2019) 152–178.
  * [2] R. M. Adin, I. M. Gessel, V. Reiner, Y. Roichman, Cyclic quasi-symmetric functions, Israel J. Math. 243 (2021), no. 1, 437–500.
  * [3] R. M. Adin, P. Hegedüs, Y. Roichman, Higher Lie characters and cyclic descent extension on conjugacy classes, arxiv:1909.04460
  * [4] R. M. Adin, V. Reiner, Y. Roichman, On cyclic descents of tableaux, Int. Math. Res. Not. IMRN 2020, no. 24, 10231–10276.
  * [5] R. M. Adin, Y. Roichman, Standard young tableaux, in: M. Bóna (Ed.), Handbook of Enumerative Combinatorics, in: Discrete Math. Appl., Chapman $\&$ Hall/CRC, 2015, pp. 895–974.
  * [6] J. Bloom, S. Elizalde, Y. Roichman, On cyclic Schur-positive sets of permutation, Electron. J. Combin. 27 (2020), no. 2, Paper No. 2.6, 28 pp.
  * [7] P. Cellini, Cyclic Eulerian elements, European. J. Combin. 19 (1998), 545–552.
  * [8] X. Chen, Enumeration of row-increasing tableaux of two-row skew shapes, Discrete Math. 344 (2021), no. 3, Paper No. 112254, 8 pp.
  * [9] K. Dilks, K. Petersen, J. Stembridge, Affine descents and the Steinberg torus, Adv. in Applied Math. 42 (2009), 423–444.
  * [10] S.-P. Eu, Skew-standard tableaux with three rows, Adv. in Appl. Math. 45 (2010), 463–469.
  * [11] S.-P. Eu, T.-S. Fu, J. T. Hou, T.-W. Hsu, Standard Young tableaux and colored Motzkin paths, J. Combin. Theory Ser. A 120 (2013), no. 7, 1786–1803.
  * [12] I. M. Gessel, Y. Zhuang, Shuffle-compatible permutation statistics, Adv. Math. 332 (2018), 85–141.
  * [13] B. Huang, Cyclic descents for general skew tableaux, J. Combin. Theory Ser. A 169 (2020), 45 pages.
  * [14] A. Regev, Asymptotic values for degrees associated with strips of Young diagrams, Adv. Math. 41 (1981) 115–136.
  * [15] B. Rhoades, Cyclic sieving, promotion, and representation theory, J. Combin. Theory Ser. A 117 (2010) 38–76.
  * [16] R. P. Stanley, Ordered Structures and Partitions, Memoirs of the American Mathematical Society, vol. 199, American Mathematical Society, Providence (1972).
  * [17] R. P. Stanley, Enumerative combinatorics. Vol. 1, Cambridge Studies in Adv. Math. 49. Cambridge Univ. Press, Cambridge, 1997.
  * [18] R. P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge Studies in Adv. Math. 62, Cambridge Univ. Press, Cambridge, 1999\.


b_{T}\left[\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\left(\frac{b_{T}}{b_{0}}\right)\right].$

Combining this with the event from Lemma D.6 that bounds
$\sum_{t=1}^{T}\frac{\left\lVert\xi_{t}\right\rVert^{2}}{b_{t}^{2}}$ and Lemma
D.1 that bounds $b_{T}$ gives us the Theorem. ∎

###  D.1 Additional helper lemmas

######  Lemma D.2.

For $t\geq 1$ and $a_{t}$, $\xi_{t}$ defined in Lemma 4.7, we have

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

###### Proof.

We have

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

Since
$b_{t}=\sqrt{b_{t-1}^{2}+\left\lVert\widehat{\nabla}f(x_{t})\right\rVert^{2}}\geq\left\lVert\widehat{\nabla}f(x_{t})\right\rVert$
and $a_{t}=\sqrt{b_{t-1}^{2}+\left\lVert\nabla
f(x_{t})\right\rVert^{2}}\geq\left\lVert\nabla f(x_{t})\right\rVert$, we have

$\displaystyle\left|\frac{1}{a_{t}}-\frac{1}{b_{t}}\right|$
$\displaystyle\leq\left|\frac{\left\lVert\widehat{\nabla}f(x_{t})\right\rVert-\left\lVert\nabla
f(x_{t})\right\rVert}{a_{t}b_{t}}\right|$
$\displaystyle\leq\frac{\left\lVert\widehat{\nabla}f(x_{t})-\nabla
f(x_{t})\right\rVert}{a_{t}b_{t}}$
$\displaystyle=\frac{\left\lVert\xi_{t}\right\rVert}{a_{t}b_{t}}.$

∎

######  Lemma D.3.

With prob $\geq 1-\delta$, for any $0\leq t\leq T$, we have

$\sum_{s=1}^{t}\|\xi_{s}\|^{2}\leq\sum_{s=1}^{t}\|\widehat{\nabla}f(x_{s})\|^{2}+4\sigma^{2}\log\frac{1}{\delta}.$

###### Proof.

Note that

$\displaystyle\|\widehat{\nabla}f(x_{t})\|^{2}$ $\displaystyle=\|\nabla
f(x_{t})\|^{2}+2\langle\xi_{t},\nabla f(x_{t})\rangle+\|\xi_{t}\|^{2}$
$\displaystyle\Rightarrow\|\nabla
f(x_{t})\|-\|\widehat{\nabla}f(x_{t})\|^{2}+\|\xi_{t}\|^{2}$
$\displaystyle=2\langle\xi_{t},\nabla f(x_{t})\rangle.$

Define for $t\in\left\\{0,1,\cdots,T\right\\}$

$\displaystyle U_{t+1}$
$\displaystyle=\exp\left(\sum_{s=1}^{t}w_{s}\left(\|\nabla
f(x_{s})\|^{2}-\|\widehat{\nabla}f(x_{s})\|^{2}+\|\xi_{s}\|^{2}\right)-v_{s}\|\nabla
f(x_{s})\|^{2}\right);\quad v_{s}=4\sigma^{2}w_{s}^{2}.$

Let $\mathcal{F}_{t}=\sigma(\xi_{i\leq t-1})$. We know
$U_{t}\in\mathcal{F}_{t}$. Note that $U_{t}$ is a supermartingale

$\displaystyle\mathbb{\mathbb{E}}\left[U_{t+1}\mid\mathcal{F}_{t}\right]$
$\displaystyle=U_{t}\exp\left(-v_{t}\|\nabla
f(x_{t})\|^{2}\right)\mathbb{\mathbb{E}}\left[\exp\left(2w_{t}\langle\xi_{t},\nabla
f(x_{t})\rangle\right)\mid\mathcal{F}_{t}\right]$ $\displaystyle\leq
U_{t}\exp\left(-v_{t}\|\nabla
f(x_{t})\|^{2}\right)\mathbb{\mathbb{E}}\left[\exp\left(4\sigma^{2}w_{t}^{2}\|\nabla
f(x_{t})\|^{2}\right)\mid\mathcal{F}_{t}\right]$ $\displaystyle=U_{t}$

By Doob’s supermartingale inequality, there is

$\Pr\left[\max_{t\in\left[T+1\right]}U_{t}\geq\delta^{-1}\right]\leq\delta\mathbb{\mathbb{E}}\left[U_{1}\right]=\delta$

which implies w.p. $\geq 1-\delta$, $\forall 0\leq t\leq T$

$\displaystyle\sum_{s=1}^{t}w_{s}\left(\|\nabla
f(x_{s})\|^{2}-\|\widehat{\nabla}f(x_{s})\|^{2}+\|\xi_{s}\|^{2}\right)-v_{s}\|\nabla
f(x_{s})\|^{2}$ $\displaystyle\leq\log\frac{1}{\delta}$
$\displaystyle\sum_{s=1}^{t}\left(w_{s}-4\sigma^{2}w_{s}^{2}\right)\|\nabla
f(x_{s})\|^{2}+w_{s}\|\xi_{s}\|^{2}$
$\displaystyle\leq\sum_{s=1}^{t}w_{s}\|\widehat{\nabla}f(x_{s})\|^{2}+\log\frac{1}{\delta}.$

Set $w_{s}=\frac{1}{4\sigma^{2}}$ to get

$\sum_{s=1}^{t}\|\xi_{s}\|^{2}\leq\sum_{s=1}^{t}\|\widehat{\nabla}f(x_{s})\|^{2}+4\sigma^{2}\log\frac{1}{\delta}.$

∎

######  Lemma D.4.

With probability $\geq 1-\delta$, we have

$\sum_{t=1}^{T}\|\xi_{t}\|^{2}\leq\sigma^{2}T+\sigma^{2}\log\frac{1}{\delta}.$

###### Proof.

Note that

$\displaystyle\Pr\left[\sum_{t=1}^{T}\|\xi_{t}\|^{2}\geq u\right]$
$\displaystyle=\Pr\left[\exp\left(\sum_{t=1}^{T}\frac{\|\xi_{t}\|^{2}}{\sigma^{2}}\right)\geq\exp\left(\frac{u}{\sigma^{2}}\right)\right]$
$\displaystyle\leq\frac{\mathbb{\mathbb{E}}\left[\exp\left(\sum_{t=1}^{T}\frac{\|\xi_{t}\|^{2}}{\sigma^{2}}\right)\right]}{\exp\left(\frac{u}{\sigma^{2}}\right)}$
$\displaystyle\leq\frac{\exp(T)}{\exp\left(\frac{u}{\sigma^{2}}\right)}$

where we choose

$u=\sigma^{2}T+\sigma^{2}\log\frac{1}{\delta}.$

∎

######  Lemma D.5.

For AdaGrad stepsize $b_{t}$ and $\sigma$-subgaussian noise
$\left\lVert\xi_{t}\right\rVert$, with probability at least $1-\delta$

$\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}}.$

###### Proof.

First, Lemma D.3 gives that with probability at least $1-\delta$, for all
$t\leq T$

$\displaystyle\sum_{i=1}^{t}\left\lVert\xi_{i}\right\rVert^{2}$
$\displaystyle\leq\sum_{i=1}^{t}\left\lVert\widehat{\nabla}f(x_{i})\right\rVert^{2}+4\sigma^{2}\ln\left(\frac{1}{\delta}\right)$
$\displaystyle=b_{t}^{2}-b_{0}^{2}+4\sigma^{2}\ln\left(\frac{1}{\delta}\right)$
$\displaystyle\implies b_{t}^{2}$
$\displaystyle\geq\sum_{i=1}^{t}\left\lVert\xi_{i}\right\rVert^{2}-\underbrace{\left[4\sigma^{2}\ln\left(\frac{1}{\delta}\right)-b_{0}^{2}\right]}_{=:C}.$

This means that

$b_{t}\geq\max\left\\{b_{0},\sqrt{\left(\sum_{i=1}^{t}\left\lVert\xi_{i}\right\rVert^{2}-C\right)^{+}}\right\\}.$

Let $\tau=\max\left(\left\\{0\right\\}\cup\left\\{t\in\mathbb{N}_{\leq
T}\mid\sum_{i=1}^{t}\left\lVert\xi_{i}\right\rVert^{2}\leq
2C\right\\}\right)$. Then

$\displaystyle\sum_{t=1}^{T}\frac{1}{b_{t}}\left\lVert\xi_{t}\right\rVert^{2}$
$\displaystyle\leq\sum_{t=1}^{\tau}\frac{1}{b_{t}}\left\lVert\xi_{t}\right\rVert^{2}+\sum_{t=\tau+1}^{T}\frac{1}{b_{t}}\left\lVert\xi_{t}\right\rVert^{2}$
$\displaystyle\leq\frac{1}{b_{0}}\sum_{t=1}^{\tau}\left\lVert\xi_{t}\right\rVert^{2}+\sum_{t=\tau+1}^{T}\frac{\left\lVert\xi_{t}\right\rVert^{2}}{\max\left\\{b_{0},\sqrt{\sum_{i=1}^{t}\left\lVert\xi_{i}\right\rVert^{2}-C}\right\\}}$
$\displaystyle\leq\frac{2C}{b_{0}}+\sum_{t=\tau+1}^{T}\frac{\left\lVert\xi_{t}\right\rVert^{2}}{\sqrt{\sum_{i=1}^{t}\left\lVert\xi_{i}\right\rVert^{2}-C}}$
$\displaystyle\leq\frac{2C}{b_{0}}+\sum_{t=\tau+1}^{T}\frac{\left\lVert\xi_{t}\right\rVert^{2}}{\sqrt{\frac{1}{2}\sum_{i=1}^{t}\left\lVert\xi_{i}\right\rVert^{2}}}\quad\left(\mbox{since}\right)$
($\sum_{i=1}^{t}\left\lVert\xi_{i}\right\rVert^{2}>2C$ for $t>\tau$)
$\displaystyle\leq\frac{2C}{b_{0}}+2\sum_{t=1}^{T}\frac{\left\lVert\xi_{t}\right\rVert^{2}}{\sqrt{\sum_{i=1}^{t}\left\lVert\xi_{i}\right\rVert^{2}}}$
$\displaystyle\leq\frac{2C}{b_{0}}+4\sqrt{\sum_{t=1}^{T}\left\lVert\xi_{t}\right\rVert^{2}}.$

Hence, with probability at least $1-\delta$,

$\sum_{t=1}^{T}\frac{\left\lVert\xi_{t}\right\rVert^{2}}{b_{t}}\leq\frac{8}{b_{0}}\sigma^{2}\ln\left(\frac{1}{\delta}\right)-b_{0}+4\sqrt{\sum_{t=1}^{T}\left\lVert\xi_{t}\right\rVert^{2}}.$

Combining with Lemma D.4, we get with probability at least $1-2\delta$

$\sum_{t=1}^{T}\frac{\left\lVert\xi_{t}\right\rVert^{2}}{b_{t}}\leq\frac{8}{b_{0}}\sigma^{2}\ln\left(\frac{1}{\delta}\right)-b_{0}+4\sigma\sqrt{T+\log\frac{1}{\delta}}.$

∎

######  Lemma D.6.

For AdaGrad-Norm stepsize $b_{t}$ and $\sigma$-subgaussian noise
$\left\lVert\xi_{t}\right\rVert$, with probability at least $1-\delta$,

$\displaystyle\sum_{t=1}^{T}\frac{\left\lVert\xi_{t}\right\rVert^{2}}{b_{t}^{2}}$
$\displaystyle\leq\frac{4\sigma^{2}}{b_{0}^{2}}\log\left(\frac{2}{\delta}\right)+2\log\left(1+\sigma^{2}T+\sigma^{2}\log\frac{2}{\delta}\right)$
$\displaystyle=O\left(\sigma^{2}\log\left(\frac{1}{\delta}\right)+\log\left(1+\sigma^{2}T+\sigma^{2}\log\frac{1}{\delta}\right)\right).$

###### Proof.

Lemma D.3 gives that with probability at least $1-\delta$

$\displaystyle\sum_{i=1}^{t}\left\lVert\xi_{i}\right\rVert^{2}$
$\displaystyle\leq\sum_{i=1}^{t}\left\lVert\widehat{\nabla}f(x_{i})\right\rVert^{2}+4\sigma^{2}\ln\left(\frac{1}{\delta}\right)$
$\displaystyle=b_{t}^{2}-b_{0}^{2}+4\sigma^{2}\ln\left(\frac{1}{\delta}\right)$
$\displaystyle\implies b_{t}^{2}$
$\displaystyle\geq\sum_{i=1}^{t}\left\lVert\xi_{i}\right\rVert^{2}-\underbrace{\left[4\sigma^{2}\ln\left(\frac{1}{\delta}\right)-b_{0}^{2}\right]}_{=:C}.$

Let $\tau=\max\left(\left\\{0\right\\}\cup\left\\{t\in\mathbb{N}_{\leq
T}\mid\sum_{i=1}^{t}\left\lVert\xi_{i}\right\rVert^{2}\leq
2C\right\\}\right)$. We have

$\displaystyle\sum_{t=1}^{T}\frac{\left\lVert\xi_{t}\right\rVert^{2}}{b_{t}^{2}}$
$\displaystyle\leq\sum_{t=1}^{\tau}\frac{\left\lVert\xi_{t}\right\rVert^{2}}{b_{t}^{2}}+\sum_{t=\tau+1}^{T}\frac{\left\lVert\xi_{t}\right\rVert^{2}}{b_{t}^{2}}$
$\displaystyle\leq\frac{1}{b_{0}^{2}}\sum_{t=1}^{\tau}\left\lVert\xi_{t}\right\rVert^{2}+\sum_{t=\tau+1}^{T}\frac{\left\lVert\xi_{t}\right\rVert^{2}}{\sum_{i=1}^{t}\left\lVert\xi_{i}\right\rVert^{2}-C}$
( $\left(\mbox{since
}\sum_{i=1}^{t}\left\lVert\xi_{i}\right\rVert^{2}>2C\mbox{ for
}t>\tau\right)$)
$\displaystyle\leq\frac{2C}{b_{0}^{2}}+2\sum_{t=\tau+1}^{T}\frac{\left\lVert\xi_{t}\right\rVert^{2}}{\sum_{i=1}^{t}\left\lVert\xi_{i}\right\rVert^{2}}$
$\displaystyle\leq\frac{2C}{b_{0}^{2}}+2\sum_{t=1}^{T}\frac{\left\lVert\xi_{t}\right\rVert^{2}}{\sum_{i=1}^{t}\left\lVert\xi_{i}\right\rVert^{2}}$
$\displaystyle\leq\frac{2C}{b_{0}^{2}}+2+2\log\left(1+\sum_{t=1}^{T}\left\lVert\xi_{t}\right\rVert^{2}\right)$
$\displaystyle=\frac{4\sigma^{2}}{b_{0}^{2}}\log\left(\frac{1}{\delta}\right)+2\log\left(1+\sum_{t=1}^{T}\left\lVert\xi_{t}\right\rVert^{2}\right).$

Then, we can combine this with Lemma D.4 to get that with probability at least
$1-2\delta$

$\sum_{t=1}^{T}\frac{\left\lVert\xi_{t}\right\rVert^{2}}{b_{t}^{2}}\leq\frac{4\sigma^{2}}{b_{0}^{2}}\log\left(\frac{1}{\delta}\right)+2\log\left(1+\sigma^{2}T+\sigma^{2}\log\frac{1}{\delta}\right).$

Replacing $\delta$ with $\delta/2$ yields the result. ∎

##  Appendix E AdaGrad (coordinate) analysis

In this section, we show that our same technique can be generalized to the
standard (per-coordinate) version of AdaGrad. The analysis is analogous to our
AdaGrad-norm analysis but with the coordinates taken into account.

###  E.1 Preliminaries and notations

Let $d\in\mathbb{N}$ be the dimension of the problem. We let $v_{i}$ denote
the $i$-th coordinate of a vector $v\in\mathbb{R}^{d}$. If a vector like
$x_{t}$ is already indexed as part of a sequence of vectors (where $x_{t}$
denotes the $t$-th update) then we use $x_{t,i}$ to denote $x_{t}$’s $i$-th
coordinate. For gradients, we let $\nabla_{i}f(x):=\frac{\partial f}{\partial
x_{i}}$ denote the partial derivative wrt the $i$-th coordinate. Similarly,
for stochastic gradients $\widehat{\nabla}f(x)$, we let
$\widehat{\nabla}_{i}f(x)$ denotes its $i$-th coordinate. For simplicity, in
our analysis, we will use
$\widehat{\nabla}_{t,i}:=\widehat{\nabla}_{i}f(x_{t})$ and
$\nabla_{t,i}:=\nabla_{i}f(x_{t})$ to denote the $i$-th coordinate of the
stochastic gradients and gradients at iterate $t$, respectively. If
$a,b\in\mathbb{R}^{d}$, then $ab$ and $a/b$ denotes coordinate-wise
multiplication and division, respectively i.e. $(ab)_{i}=a_{i}b_{i}$ and
$(a/b)_{i}=a_{i}/b_{i}$.

If we denote the noise as $\xi_{t}:=\widehat{\nabla}f(x_{t})-\nabla f(x_{t})$
and $\xi_{t,i}$ as the $i$-th coordinate of $\xi_{t}$, then we assume the
noise is per-coordinate sub-gaussian i.e. there exists $\sigma_{i}>0$ for
$i\in[d]$ such that $\xi_{t}$ satisfies

$\mathbb{\mathbb{E}}\left[\exp\left(\lambda^{2}\xi_{t,i}^{2}\right)\right]\leq\exp\left(\lambda^{2}\sigma_{i}^{2}\right),\forall\left|\lambda\right|\leq\frac{1}{\sigma_{i}},\forall
i\in\left[d\right].$

Note that $\left\|\xi_{t}\right\|$ being $\sigma$-subgaussian implies that
each $\xi_{t,i}$ is also $\sigma$-subgaussian, thus the assumption above is
more general.

###  E.2 Analysis

Similarly to our Adagrad-norm analysis in Section D, we define a proxy step
size $a_{t}$ that replaces the stochastic gradient at time $t$ with the true
gradient: $a_{t,i}^{2}:=b_{t-1,i}^{2}+\nabla_{t,i}^{2}$, for $i\in[d]$. First,
we present an analogous starting point to Lemma 4.7 in the Lemma below:

######  Lemma E.1.

For $t\geq 1$, let $\xi_{t,i}=\widehat{\nabla}_{t,i}-\nabla_{t,i}$,
$a_{t,i}^{2}:=b_{t-1,i}^{2}+\nabla_{t,i}^{2}$ and $M_{t,i}=\max_{j\leq
t}\left|\xi_{j,i}\right|$, then we have

$\sum_{t=1}^{T}\sum_{i=1}^{d}\frac{\nabla_{t,i}^{2}}{b_{t,i}}\leq\frac{\Delta_{1}}{\eta}-\sum_{t=1}^{T}\sum_{i=1}^{d}\frac{\nabla_{t,i}\xi_{t,i}}{a_{t,i}}+\sum_{t=1}^{T}\sum_{i=1}^{d}\left|\xi_{t,i}\right|\left[\frac{\nabla_{t,i}^{2}}{2a_{t,i}^{2}}+\frac{\xi_{t,i}^{2}}{2b_{t,i}^{2}}\right]+\frac{\eta
L}{2}\sum_{t=1}^{T}\sum_{i=1}^{d}\frac{\widehat{\nabla}_{t,i}^{2}}{b_{t,i}^{2}}.$

###### Proof.

We start with the smoothness of $f$

$\displaystyle\Delta_{t+1}-\Delta_{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=-\eta\sum_{i=1}^{d}\frac{\nabla_{t,i}\widehat{\nabla}_{t,i}}{b_{t,i}}+\frac{\eta^{2}L}{2}\sum_{i=1}^{d}\frac{\widehat{\nabla}_{t,i}^{2}}{b_{t,i}^{2}}$
$\displaystyle=-\eta\sum_{i=1}^{d}\frac{\nabla_{t,i}^{2}}{b_{t,i}}-\eta\sum_{i=1}^{d}\frac{\nabla_{t,i}\xi_{t,i}}{b_{t,i}}+\frac{\eta^{2}L}{2}\sum_{i=1}^{d}\frac{\widehat{\nabla}_{t,i}^{2}}{b_{t,i}^{2}}$
$\displaystyle=-\eta\sum_{i=1}^{d}\frac{\nabla_{t,i}^{2}}{b_{t,i}}-\eta\sum_{i=1}^{d}\frac{\nabla_{t,i}\xi_{t,i}}{a_{t,i}}+\eta\sum_{i=1}^{d}\left(\frac{1}{a_{t,i}}-\frac{1}{b_{t,i}}\right)\nabla_{t,i}\xi_{t,i}+\frac{\eta^{2}L}{2}\sum_{i=1}^{d}\frac{\widehat{\nabla}_{t,i}^{2}}{b_{t,i}^{2}}.$

Similarly to Lemma D.2, we have:

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

Then

$\displaystyle\Delta_{t+1}-\Delta_{t}$
$\displaystyle\leq-\eta\sum_{i=1}^{d}\frac{\nabla_{t,i}^{2}}{b_{t,i}}-\eta\sum_{i=1}^{d}\frac{\nabla_{t,i}\xi_{t,i}}{a_{t,i}}+\eta\sum_{i=1}^{d}\left(\frac{1}{a_{t,i}}-\frac{1}{b_{t,i}}\right)\nabla_{t,i}\xi_{t,i}+\frac{\eta^{2}L}{2}\sum_{i=1}^{d}\frac{\widehat{\nabla}_{t,i}^{2}}{b_{t,i}^{2}}$
$\displaystyle\leq-\eta\sum_{i=1}^{d}\frac{\nabla_{t,i}^{2}}{b_{t,i}}-\eta\sum_{i=1}^{d}\frac{\nabla_{t,i}\xi_{t,i}}{a_{t,i}}+\eta\sum_{i=1}^{d}\frac{\left|\xi_{t,i}\right|}{a_{t,i}b_{t,i}}\left|\nabla_{t,i}\xi_{t,i}\right|+\frac{\eta^{2}L}{2}\sum_{i=1}^{d}\frac{\widehat{\nabla}_{t,i}^{2}}{b_{t,i}^{2}}$
$\displaystyle\leq-\eta\sum_{i=1}^{d}\frac{\nabla_{t,i}^{2}}{b_{t,i}}-\eta\sum_{i=1}^{d}\frac{\nabla_{t,i}\xi_{t,i}}{a_{t,i}}+\eta\sum_{i=1}^{d}\left|\xi_{t,i}\right|\left[\frac{\nabla_{t,i}^{2}}{2a_{t,i}^{2}}+\frac{\xi_{t,i}^{2}}{2b_{t,i}^{2}}\right]+\frac{\eta^{2}L}{2}\sum_{i=1}^{d}\frac{\widehat{\nabla}_{t,i}^{2}}{b_{t,i}^{2}}.$

Rearranging and summing give us the Lemma. ∎

Next, we present an analogous per-coordinate result to Lemma D.

######  Lemma E.2.

With $M_{T,i}=\max_{t\leq
T}\left|\xi_{t,i}\right|,\sigma_{\max}=\max_{i\in[d]}\sigma_{i}$, and for any
$w>0$, we have with probability at least $1-2d\delta$

$\frac{1}{\left\|b_{T}\right\|_{1}}\sum_{t=1}^{T}\left\|\nabla
f(x_{t})\right\|_{1}^{2}\leq\frac{\Delta_{1}}{\eta}+d\sigma_{\max}\sqrt{\log\frac{1}{\delta}}+\left(8\left\|\sigma\right\|_{1}\sqrt{\log\frac{T}{\delta}}+d\eta
L\right)\log\left(\frac{\left\|b_{T}\right\|_{1}}{\min
b_{0,i}}\right)+\sum_{i=1}^{d}6\sigma_{i}\sqrt{\log\frac{T}{\delta}}\sum_{t=1}^{T}\frac{\xi_{t,i}^{2}}{b_{t,i}^{2}}.$

###### Proof.

We first take care of the term
$\sum_{t=1}^{T}\sum_{i=1}^{d}\frac{\widehat{\nabla}_{t,i}^{2}}{b_{t,i}^{2}}$
from Lemma E.1:

$\sum_{t=1}^{T}\sum_{i=1}^{d}\frac{\widehat{\nabla}_{t,i}^{2}}{b_{t,i}^{2}}=\sum_{i=1}^{d}\sum_{t=1}^{T}\frac{\widehat{\nabla}_{t,i}^{2}}{b_{t,i}^{2}}=\sum_{i=1}^{d}\sum_{t=1}^{T}\frac{b_{t,i}^{2}-b_{t-1,i}^{2}}{b_{t,i}^{2}}\leq\sum_{i=1}^{d}2\log\frac{b_{T,i}}{b_{0,i}}.$

Next, we deal with
$-\sum_{t=1}^{T}\sum_{i=1}^{d}\frac{\nabla_{t,i}\xi_{t,i}}{a_{t,i}}$ via our
martingale argument. For any $w>0$, we have for each $i\in[d]$:

$\displaystyle\mathbb{\mathbb{E}}\left[\exp\left(-w\frac{\nabla_{t,i}\xi_{t,i}}{a_{t,i}}-2w^{2}\frac{\sigma_{i}^{2}\nabla_{t,i}^{2}}{a_{t,i}^{2}}\right)\mid\mathcal{F}_{t}\right]$
$\displaystyle=\exp\left(-2w^{2}\frac{\sigma_{i}^{2}\nabla_{t,i}^{2}}{a_{t,i}^{2}}\right)\mathbb{\mathbb{E}}\left[\exp\left(-w\frac{\nabla_{t,i}\xi_{t,i}}{a_{t,i}}\right)\mid\mathcal{F}_{t}\right]$
$\displaystyle\leq 1.$

Then a simple inductive argument gives with probability at least $1-\delta$:

$-w\sum_{t=1}^{T}\frac{\nabla_{t,i}\xi_{t,i}}{a_{t,i}}\leq
2w^{2}\sum_{t=1}^{T}\frac{\sigma_{i}^{2}\nabla_{t,i}^{2}}{a_{t,i}^{2}}+\log\frac{1}{\delta}.$

By a union bound across all coordinate $d$, we have w.p. at least $1-d\delta$:

$-\sum_{t=1}^{T}\sum_{i=1}^{d}\frac{\nabla_{t,i}\xi_{t,i}}{a_{t,i}}\leq\sum_{t=1}^{T}\sum_{i=1}^{d}\frac{w\sigma_{i}^{2}\nabla_{t,i}^{2}}{a_{t,i}^{2}}+\frac{d}{w}\log\frac{1}{\delta}.$
(21)

Let’s call the event that (21) happens $E_{1}$. Now, we deal with
$\sum_{t=1}^{T}\sum_{i=1}^{d}\frac{\nabla_{t,i}^{2}}{a_{t,i}^{2}}$. Note that

$\frac{\nabla_{t,i}^{2}}{a_{t,i}^{2}}=\frac{\nabla_{t,i}^{2}}{b_{t-1,i}^{2}+\nabla_{t,i}^{2}+\sigma_{i}^{2}}\leq\frac{2\widehat{\nabla}_{t,i}^{2}+2\xi_{t,i}^{2}}{b_{t-1,i}^{2}+2\widehat{\nabla}_{t,i}^{2}+2\xi_{t,i}^{2}+\sigma_{i}^{2}}\leq
2\frac{\widehat{\nabla}_{t,i}^{2}}{b_{t,i}^{2}}+2\frac{\xi_{t,i}^{2}}{b_{t,i}^{2}}.$

Under the even $E_{1}$ and the above result, we can bound Lemma E.1 with
probability at least $1-d\delta$:

$\displaystyle\sum_{t=1}^{T}\sum_{i=1}^{d}\frac{\nabla_{t,i}^{2}}{b_{t,i}}$
$\displaystyle\leq\frac{\Delta_{1}}{\eta}+w\sum_{t=1}^{T}\sum_{i=1}^{d}\frac{\sigma_{i}^{2}\nabla_{t,i}^{2}}{a_{t,i}^{2}}+\frac{d}{w}\log\frac{1}{\delta}+\sum_{t=1}^{T}\sum_{i=1}^{d}\frac{M_{T,i}}{2}\left[\frac{\nabla_{t,i}^{2}}{a_{t,i}^{2}}+\frac{\xi_{t,i}^{2}}{b_{t,i}^{2}}\right]+\frac{\eta
L}{2}\sum_{i=1}^{d}2\log\frac{b_{T,i}}{b_{0,i}}$
$\displaystyle=\frac{\Delta_{1}}{\eta}+\frac{d}{w}\log\frac{1}{\delta}+\sum_{t=1}^{T}\sum_{i=1}^{d}\left(2w\sigma_{i}^{2}+M_{T,i}\right)\frac{\widehat{\nabla}_{t,i}^{2}}{b_{t,i}^{2}}+2\sum_{t=1}^{T}\sum_{i=1}^{d}\left(M_{T,i}+w\sigma_{i}^{2}\right)\frac{\xi_{t,i}^{2}}{b_{t,i}^{2}}+\eta
L\sum_{i=1}^{d}\log\frac{b_{T,i}}{b_{0,i}}$
$\displaystyle=\frac{\Delta_{1}}{\eta}+\frac{d}{w}\log\frac{1}{\delta}+\sum_{i=1}^{d}\left(4w\sigma_{i}^{2}+2M_{T,i}+\eta
L\right)\log\frac{b_{T,i}}{b_{0,i}}+2\sum_{i=1}^{d}\left(M_{T,i}+w\sigma_{i}^{2}\right)\sum_{t=1}^{T}\frac{\xi_{t,i}^{2}}{b_{t,i}^{2}}.$

Note that

$\displaystyle\left(\sum_{i=1}^{d}\frac{\nabla_{t,i}^{2}}{b_{t,i}}\right)\left(\sum_{i=1}^{d}b_{t,i}\right)$
$\displaystyle\geq\left(\sum_{i=1}^{d}\left\|\nabla_{t,i}\right\|\right)^{2}=\left\|\nabla
f(x_{t})\right\|_{1}^{2}$
$\displaystyle\Rightarrow\left(\sum_{i=1}^{d}\frac{\nabla_{t,i}^{2}}{b_{t,i}}\right)$
$\displaystyle\geq\frac{\left\|\nabla
f(x_{t})\right\|_{1}^{2}}{\left\|b_{t}\right\|_{1}}\geq\frac{\left\|\nabla
f(x_{t})\right\|_{1}^{2}}{\left\|b_{T}\right\|_{1}}.$

Hence, we have

$\frac{1}{\left\|b_{T}\right\|_{1}}\sum_{t=1}^{T}\left\|\nabla
f(x_{t})\right\|_{1}^{2}\leq\sum_{t=1}^{T}\sum_{i=1}^{d}\frac{\nabla_{t,i}^{2}}{b_{t,i}}.$

Since it is known that with probability at least $1-\delta$,
$\max_{t\in\left[T\right]}\left|\xi_{t,i}\right|\leq\sigma_{i}\sqrt{1+\log\frac{T}{\delta}}$
for each $i\in[d]$ Li and Orabona (2020); Liu et al. (2022), a union bound
over all $d$ gives us that w.p.$\geq 1-d\delta$

$M_{T,i}\leq 2\sigma_{i}\sqrt{\log\frac{T}{\delta}},\forall
i\in\left[d\right].$ (22)

Condition under this event and choosing
$\frac{1}{w}=\frac{\sigma_{\max}}{\sqrt{\log\frac{1}{\delta}}}$ gives us with
probability at least $1-2d\delta$

$\displaystyle\frac{1}{\left\|b_{T}\right\|_{1}}\sum_{t=1}^{T}\left\|\nabla
f(x_{t})\right\|_{1}^{2}$
$\displaystyle\leq\frac{\Delta_{1}}{\eta}+d\sigma_{\max}\sqrt{\log\frac{1}{\delta}}+\sum_{i=1}^{d}\left(\frac{4\sigma_{i}^{2}}{\sigma_{\max}}\sqrt{\log\frac{1}{\delta}}+4\sigma_{i}\sqrt{\log\frac{T}{\delta}}+\eta
L\right)\log\frac{b_{T,i}}{b_{0,i}}$
$\displaystyle\quad+2\sum_{i=1}^{d}\left(2\sigma_{i}\sqrt{\log\frac{T}{\delta}}+\frac{\sigma_{i}^{2}}{\sigma_{\max}}\sqrt{\log\frac{1}{\delta}}\right)\sum_{t=1}^{T}\frac{\xi_{t,i}^{2}}{b_{t,i}^{2}}$
$\displaystyle\leq\frac{\Delta_{1}}{\eta}+d\sigma_{\max}\sqrt{\log\frac{1}{\delta}}+\left(8\left\|\sigma\right\|_{1}\sqrt{\log\frac{T}{\delta}}+d\eta
L\right)\log\left(\frac{\left\|b_{T}\right\|_{1}}{\min
b_{0,i}}\right)+\sum_{i=1}^{d}6\sigma_{i}\sqrt{\log\frac{T}{\delta}}\sum_{t=1}^{T}\frac{\xi_{t,i}^{2}}{b_{t,i}^{2}}.$

∎

Finally, it remains to bound $\left\lVert b_{T}\right\rVert_{1}$ and
$\sum_{t=1}^{T}\frac{\xi_{t,i}^{2}}{b_{t,i}^{2}}$. For this we use Lemma E.6
to show the following bound on $\left\lVert b_{T}\right\rVert_{1}$:

######  Lemma E.3.

With probability at least $1-2d\delta$

$\displaystyle\left\|b_{T}\right\|_{1}$ $\displaystyle\leq
2\left\|b_{0}\right\|_{1}+\frac{4\Delta_{1}}{\eta}+\log\left(\frac{2}{\delta}\right)\sum_{i=1}^{d}\frac{8\sigma_{i}^{2}}{b_{0,i}}+4\sum_{i=1}^{d}\sqrt{\sigma_{i}^{2}T+\sigma_{i}^{2}\log\frac{2}{\delta}}+4\eta^{2}L\sum_{i=1}^{d}\log\frac{4\eta^{2}L}{b_{0,i}}$
$\displaystyle=O\left(\left\|\sigma\right\|_{1}\sqrt{T}+\left\|b_{0}\right\|_{1}+\frac{\Delta_{1}}{\eta}+\left\|\frac{\sigma^{2}}{b_{0}}\right\|_{1}\log\left(\frac{1}{\delta}\right)+\left\|\sigma\right\|_{1}\sqrt{\log\frac{1}{\delta}}+\eta^{2}L\sum_{i=1}^{d}\log\frac{\eta^{2}L}{b_{0,i}}\right).$

###### Proof.

We start via 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\lVert
x_{t+1}-x_{t}\right\rVert^{2}$
$\displaystyle=-\frac{\eta}{b_{t}}\left\langle\nabla
f(x_{t}),\widehat{\nabla}f(x_{t})\right\rangle+\frac{\eta^{2}L}{2}\sum_{i=1}^{d}\frac{\widehat{\nabla}_{t,i}^{2}}{b_{t,i}^{2}}$
$\displaystyle=-\eta\sum_{i=1}^{d}\frac{\widehat{\nabla}_{t,i}^{2}}{b_{t,i}}+\eta\sum_{i=1}^{d}\frac{\xi_{t,i}\widehat{\nabla}_{t,i}}{b_{t,i}}+\frac{\eta^{2}L}{2}\sum_{i=1}^{d}\frac{\widehat{\nabla}_{t,i}^{2}}{b_{t,i}^{2}}$
$\displaystyle\leq-\frac{\eta}{2}\sum_{i=1}^{d}\frac{\widehat{\nabla}_{t,i}^{2}}{b_{t,i}}+\frac{\eta}{2}\sum_{i=1}^{d}\frac{\xi_{t,i}^{2}}{b_{t,i}}+\frac{\eta^{2}L}{2}\sum_{i=1}^{d}\frac{\widehat{\nabla}_{t,i}^{2}}{b_{t,i}^{2}}.$

Summing up over $t$ we obtain

$\displaystyle\sum_{t=1}^{T}\sum_{i=1}^{d}\frac{\widehat{\nabla}_{t,i}^{2}}{b_{t,i}}$
$\displaystyle\leq\frac{2\Delta_{1}}{\eta}+\sum_{t=1}^{T}\sum_{i=1}^{d}\frac{\xi_{t,i}^{2}}{b_{t,i}}+\sum_{t=1}^{T}\sum_{i=1}^{d}\eta^{2}L\frac{\widehat{\nabla}_{t,i}^{2}}{b_{t,i}^{2}}$
$\displaystyle\leq\frac{2\Delta_{1}}{\eta}+\sum_{t=1}^{T}\sum_{i=1}^{d}\frac{\xi_{t,i}^{2}}{b_{t,i}}+\sum_{i=1}^{d}2\eta^{2}L\log\frac{b_{T,i}}{b_{0,i}}.$

Note that the LHS of the above inequality is lower-bounded by
$\left\|b_{T}\right\|_{1}-\left\|b_{0}\right\|_{1}$. Thus

$\displaystyle\left\|b_{T}\right\|_{1}-\left\|b_{0}\right\|_{1}$
$\displaystyle\leq\frac{2\Delta_{1}}{\eta}+\sum_{t=1}^{T}\sum_{i=1}^{d}\frac{\xi_{t,i}^{2}}{b_{t,i}}+\sum_{i=1}^{d}2\eta^{2}L\log\frac{b_{T,i}}{b_{0,i}}$
$\displaystyle\leq\frac{2\Delta_{1}}{\eta}+\sum_{t=1}^{T}\sum_{i=1}^{d}\frac{\xi_{t,i}^{2}}{b_{t,i}}+\sum_{i=1}^{d}2\eta^{2}L\left(\log\frac{b_{T,i}}{4\eta^{2}L}+\log\frac{4\eta^{2}L}{b_{0,i}}\right)$
$\displaystyle\leq\frac{2\Delta_{1}}{\eta}+\sum_{t=1}^{T}\sum_{i=1}^{d}\frac{\xi_{t,i}^{2}}{b_{t,i}}+\frac{\left\|b_{T}\right\|_{1}}{2}+\sum_{i=1}^{d}2\eta^{2}L\log\frac{4\eta^{2}L}{b_{0,i}};$
$\displaystyle\left\|b_{T}\right\|_{1}$ $\displaystyle\leq
2\left\|b_{0}\right\|_{1}+\frac{4\Delta_{1}}{\eta}+2\sum_{t=1}^{T}\sum_{i=1}^{d}\frac{\xi_{t,i}^{2}}{b_{t,i}}+4\eta^{2}L\sum_{i=1}^{d}\log\frac{4\eta^{2}L}{b_{0,i}}.$

Note that by Lemma E.6, with probability at least $1-2d\delta$

$\displaystyle\sum_{t=1}^{T}\sum_{i=1}^{d}\frac{\xi_{t,i}^{2}}{b_{t,i}}$
$\displaystyle\leq\sum_{i=1}^{d}\frac{8\sigma_{i}^{2}\log\frac{1}{\delta}}{b_{0,i}}+4\sqrt{\sigma_{i}^{2}T+\sigma_{i}^{2}\log\frac{1}{\delta}}$
$\displaystyle=O\left(\left\|\frac{\sigma^{2}}{b_{0}}\right\|_{1}\log\frac{1}{\delta}+\left\|\sigma\right\|_{1}\left(\sqrt{\log\frac{1}{\delta}}+\sqrt{T}\right)\right).$

Hence, under this event, we have that with probability at least $1-2d\delta$

$\displaystyle\left\|b_{T}\right\|_{1}$ $\displaystyle\leq
2\left\|b_{0}\right\|_{1}+\frac{4\Delta_{1}}{\eta}+O\left(\left\|\frac{\sigma^{2}}{b_{0}}\right\|_{1}\log\frac{1}{\delta}+\left\|\sigma\right\|_{1}\left(\sqrt{\log\frac{1}{\delta}}+\sqrt{T}\right)\right)+4\eta^{2}L\sum_{i}\log\frac{4\eta^{2}L}{b_{0,i}}.$

∎

Now we are ready to prove Theorem 4.6.

###### Proof of Theorem 4.6.

Combining Lemma E.1 with Lemma E.6, we get with probability at least
$1-4d\delta$

$\displaystyle\frac{1}{\left\|b_{T}\right\|_{1}}\sum_{t=1}^{T}\left\|\nabla
f(x_{t})\right\|_{1}^{2}$
$\displaystyle\leq\frac{\Delta_{1}}{\eta}+d\sigma_{\max}\sqrt{\log\frac{1}{\delta}}+\left(8\left\|\sigma\right\|_{1}\sqrt{\log\frac{T}{\delta}}+d\eta
L\right)\log\left(\frac{\left\|b_{T}\right\|_{1}}{\min
b_{0,i}}\right)+\sum_{i=1}^{d}6\sigma_{i}\sqrt{\log\frac{T}{\delta}}\sum_{t=1}^{T}\frac{\xi_{t,i}^{2}}{b_{t,i}^{2}}.$
$\displaystyle\leq\frac{\Delta_{1}}{\eta}+d\sigma_{\max}\sqrt{\log\frac{1}{\delta}}+\left(8\left\|\sigma\right\|_{1}\sqrt{\log\frac{T}{\delta}}+d\eta
L\right)\log\left(\frac{\left\|b_{T}\right\|_{1}}{\min b_{0,i}}\right)$
$\displaystyle\quad+6\sqrt{\log\frac{T}{\delta}}\sum_{i=1}^{d}\sigma_{i}\left(\frac{8\sigma_{i}^{2}}{b_{0,i}^{2}}\log\frac{1}{\delta}+2\log\left(1+\frac{\sigma_{i}^{2}T+\sigma_{i}^{2}\log\frac{1}{\delta}}{2b_{0,i}^{2}}\right)\right).$

Rearranging, combining this with the bound for $\left\|b_{T}\right\|_{1}$, and
replacing $\delta$ with $\frac{\delta}{6d}$ yield the Theorem. ∎

###  E.3 Additional helper lemmas

######  Lemma E.4.

We have w.p. $\geq 1-d\delta$

$\sum_{t=1}^{\tau}\xi_{t,i}^{2}\leq\sum_{t=1}^{\tau}\widehat{\nabla}_{t,i}^{2}+4\sigma_{i}^{2}\log\frac{1}{\delta},\forall\tau\in\left[T\right],\forall
i\in\left[d\right].$

###### Proof.

We apply Lemma D.3 to each coordinate individually and then union bound over
all the dimensions to get the result. ∎

######  Lemma E.5.

We have w.p.$\geq 1-d\delta$

$\sum_{t=1}^{T}\xi_{t,i}^{2}\leq\sigma_{i}^{2}T+\sigma_{i}^{2}\log\frac{1}{\delta},\forall
i\in\left[d\right].$

###### Proof.

We apply Lemma D.4 to each coordinate individually and then union bound over
all the dimensions to get the result. ∎

We can show a bound on $\sum_{t=1}^{T}\frac{\xi_{t,i}^{2}}{b_{t,i}}$ and
$\sum_{t=1}^{T}\frac{\xi_{t,i}^{2}}{b_{t,i}^{2}}$ for each $i\in[d]$:

######  Lemma E.6.

We have

  1. 1.

With probability at least $1-2d\delta$, we have for all $i\in[d]$

$\displaystyle\sum_{t=1}^{T}\frac{\xi_{t,i}^{2}}{b_{t,i}}$
$\displaystyle\leq\frac{8\sigma_{i}^{2}\log\frac{1}{\delta}}{b_{0,i}}+4\sqrt{\sigma_{i}^{2}T+\sigma_{i}^{2}\log\frac{1}{\delta}}.$

  2. 2.

With probability at least $1-2d\delta$, we have for all $i\in[d]$

$\displaystyle\sum_{t=1}^{T}\frac{\xi_{t,i}^{2}}{b_{t,i}^{2}}$
$\displaystyle\leq\frac{8\sigma_{i}^{2}}{b_{0,i}^{2}}\log\frac{1}{\delta}+2\log\left(1+\frac{\sigma_{i}^{2}T+\sigma_{i}^{2}\log\frac{1}{\delta}}{2b_{0,i}^{2}}\right).$

###### Proof.

For (1), we have with probability at least $1-2d\delta$

$\displaystyle\sum_{t=1}^{T}\frac{\xi_{t,i}^{2}}{b_{t,i}}$
$\displaystyle=\sum_{t=1}^{T}\frac{\xi_{t,i}^{2}}{\sqrt{b_{0,i}^{2}+\sum_{s=1}^{t}\widehat{\nabla}_{s,i}^{2}}}$
$\displaystyle\overset{(1)}{\leq}\sum_{t=1}^{T}\frac{\xi_{t,i}^{2}}{\sqrt{b_{0,i}^{2}+\left(\sum_{s=1}^{t}\xi_{s,i}^{2}-4\sigma_{i}^{2}\log\frac{1}{\delta}\right)^{+}}}$
$\displaystyle\leq\frac{8\sigma_{i}^{2}\log\frac{1}{\delta}}{b_{0,i}}+2\sqrt{2}\sqrt{\sum_{s=1}^{T}\xi_{s,i}^{2}}$
$\displaystyle\overset{(2)}{\leq}\frac{8\sigma_{i}^{2}\log\frac{1}{\delta}}{b_{0,i}}+4\sqrt{\sigma_{i}^{2}T+\sigma_{i}^{2}\log\frac{1}{\delta}},$

where (1) is due to Lemma E.4 and (2) is due to Lemma E.5.

For (2), we have with probability at least $1-2d\delta$

$\displaystyle\sum_{t}\frac{\xi_{t,i}^{2}}{b_{t,i}^{2}}$
$\displaystyle=\sum_{t}\frac{\xi_{t,i}^{2}}{b_{0,i}^{2}+\sum_{s=1}^{t}\widehat{\nabla}_{s,i}^{2}}$
$\displaystyle\overset{(1)}{\leq}\sum_{t}\frac{\xi_{t,i}^{2}}{b_{0,i}^{2}+\left(\sum_{s=1}^{t}\xi_{s,i}^{2}-4\sigma_{i}^{2}\log\frac{1}{\delta}\right)^{+}}$
$\displaystyle\leq\frac{8\sigma_{i}^{2}\log\frac{1}{\delta}}{b_{0,i}^{2}}+2\log\left(1+\frac{\sum_{t=1}^{T}\xi_{t,i}^{2}}{2b_{0,i}^{2}}\right)$
$\displaystyle\overset{(2)}{\leq}\frac{8\sigma_{i}^{2}\log\frac{1}{\delta}}{b_{0,i}^{2}}+2\log\left(1+\frac{\sigma_{i}^{2}T+\sigma_{i}^{2}\log\frac{1}{\delta}}{2b_{0,i}^{2}}\right),$

where (1) is due to Lemma E.4 and (2) is due to Lemma E.5. ∎