# FastAdaBelief: Improving Convergence Rate for Belief-based Adaptive
Optimizers by Exploiting Strong Convexity

Yangfan Zhou, Kaizhu Huang, Cheng Cheng, Xuguang Wang, Amir Hussain, and Xin
Liu Y. Zhou, C. Cheng, X. Wang, and X. Liu are with Suzhou Institute of Nano-
Tech and Nano-Bionics (SINANO), Chinese Academy of Sciences, 398 Ruoshui Road,
Suzhou Industrial Park, Suzhou City, Jiangsu Province, 215123 China.Y.Zhou and
X. Liu are also with School of Nano-Tech and Nano-Bionics, University of
Science and Technology of China, 96 Jinzhai Road, Hefei City, Anhui Province,
230026 China.K. Huang is with School of Advanced Technology, Xi’an Jiaotong-
Liverpool University, Suzhou, 215123, China.A. Hussain is with School of
Computing, Edinburgh Napier University, Edinburgh, EH11 4BN, UKE-mail
addresses<EMAIL_ADDRESS>(Y. Zhou<EMAIL_ADDRESS>(K.
Huang<EMAIL_ADDRESS>(C. Cheng<EMAIL_ADDRESS>(X. Wang),
<EMAIL_ADDRESS>(A. Hussain<EMAIL_ADDRESS>(X.
Liu).Corresponding author: Xin Liu (email: xliu2018@sinano.ac.cn).

###### Abstract

AdaBelief, one of the current best optimizers, demonstrates superior
generalization ability to the popular Adam algorithm by viewing the
exponential moving average of observed gradients. AdaBelief is theoretically
appealing in that it has a data-dependent $O(\sqrt{T})$ regret bound when
objective functions are convex, where $T$ is a time horizon. It remains
however an open problem whether the convergence rate can be further improved
without sacrificing its generalization ability. To this end, we make a first
attempt in this work and design a novel optimization algorithm called
FastAdaBelief that aims to exploit its strong convexity in order to achieve an
even faster convergence rate. In particular, by adjusting the step size that
better considers strong convexity and prevents fluctuation, our proposed
FastAdaBelief demonstrates excellent generalization ability as well as
superior convergence. As an important theoretical contribution, we prove that
FastAdaBelief attains a data-dependant $O(\log T)$ regret bound, which is
substantially lower than AdaBelief. On the empirical side, we validate our
theoretical analysis with extensive experiments in both scenarios of strong
and non-strong convexity on three popular baseline models. Experimental
results are very encouraging: FastAdaBelief converges the quickest in
comparison to all mainstream algorithms while maintaining an excellent
generalization ability, in cases of both strong or non-strong convexity.
FastAdaBelief is thus posited as a new benchmark model for the research
community.

###### Index Terms:

Adaptive Learning Rate, Stochastic Gradient Descent, Online Learning,
Optimization Algorithm, Strong Convexity

##  I Introduction

The training process is a significant part in many fields of artificial neural
networks such as deep learning [1], transfer learning [2] and meta learning
[3]. From an optimization perspective, the purpose of the training process is
to minimize (or maximize) the loss value (or reward value), and thus can be
considered as an optimization process [4, 5, 6]. As a popular paradigm, the
training process can be conducted in a supervised way that requires a large
number of labeled samples in order to achieve satisfactory performance [7, 8].
On one hand, it may however practically be very difficult due to the high cost
involving in annotating samples manually (or even automatically) [8]; on the
other hand, even in the case of sufficient label data, it is still a big
challenge on how to design both fast and accurate training or optimization
algorithms. To tackle this problem, many researchers have been paying great
efforts in improving the convergence speed of optimization algorithms, so as
to both reduce the need for labeled samples and speed up the training process
with available data at hand [9, 10]. Specifically, online learning is often
used to accomplish such training tasks because it does not require the
information to be collected in batches at the same time [11].

TABLE I: Comparison of performance on convergence and generalization ability of FastAdaBelief and the current mainstream optimizers. Optimizer | Loss Function | Regret Bound | Convergence | Generalization
---|---|---|---|---
SGD ([12]) | _convex_ | $O(\sqrt{T})$ | _slow_ | _excellent_
Adam([17]) | _convex_ | $O(\sqrt{T})$ | _medium_ | _poor_
SAdam ([25]) | _strongly convex_ | $O(\log T)$ | _fast_ | _poor_
AdaBelief ([24]) | _convex_ | $O(\sqrt{T})$ | _medium_ | _excellent_
FastAdaBelief (Ours) | _strongly convex_ | $O(\log T)$ | _fast_ | _excellent_

One classic online optimization algorithm is online Stochastic Gradient
Descent (SGD) [12]. SGD has been extensively applied over the last few decades
in many training tasks of deep learning owing to its simple logic and good
generalization ability [13, 14]. However, SGD has the limitation of slow
convergence. This disadvantage hinders its application especially in large-
scale problems which may take extremely long to converge. To address this
issue, researchers have developed various methods trying to speed up the
convergence rate for SGD. For example, one type of methods focus on exploring
the first-order momentum to accelerate SGD; such methods include SGD with
momentum [15] and Nesterov momentum [16]. Typically adopting a fixed step
size, these methods may not be conducive to accelerate the convergence rate.
To alleviate this problem, recent studies including the popular Adam [17] and
AMSGrad [18] attempt to apply the second-order momentum and prefer an adaptive
step size while maintaining the first-order momentum.

As one of the most successful adaptive online algorithms, Adam designs the
second-order momentum as
$\mathbf{v}_{t}=\beta_{2}\mathbf{v}_{t-1}+(1-\beta_{2})\mathbf{g}_{t}^{2}$,
where $\mathbf{g}_{t}$ is the gradient, and $t\in\\{1,\ldots,T\\}$. Adam
enjoys a fast convergence which is guaranteed with the regret bound of
$O(\sqrt{T})$. Despite the outstanding performance, Reddi _et al._ indicated
that Adam has the issue of non-convergence [18], which is caused by not
satisfying $\Gamma_{t}\succeq 0$ for all $t\in\\{1,\ldots,T\\}$, where
$\Gamma_{t}=\frac{\sqrt{\mathbf{v}_{t}}}{\alpha_{t}}-\frac{\sqrt{\mathbf{v}_{t-1}}}{\alpha_{t-1}}$.
Moreover, another limitation with Adam is that it could lead to a worse
generalization ability than SGD. To tackle this issue, many variants of Adam
have been further proposed. For instance, Luo _et al._ [19] proposed AdaBound
with a dynamic bound of learning rate; Zaheer _et al._ considered the effect
of increasing mini-batch size, and proposed Yogi [20]; Liu _et al._ developed
RAdam [21] to rectify the variance of the learning rate; Balles and Hennig
dissected Adam in the sign, magnitude, and variance of stochastic gradients,
and proposed MSVAG [22]; Loshchilov and Hutter invented AdamW [23] to decouple
the weight decay from the loss function.

Although these variants perform better than Adam in generalization ability,
there is still a generalization gap compared with SGD on large-scale datasets.
To fill this gap, Zhuang _et al._ proposed AdaBelief [24], which adapts the
step size by the belief in observed gradients and leads to an superior
generalization to Adam. Specifically, AdaBelief re-designs the second-order
momentum as
$\mathbf{s}_{t}=\beta_{2}\mathbf{s}_{t-1}+(1-\beta_{2})(\mathbf{g}_{t}-\mathbf{m}_{t})^{2}$,
where $\mathbf{m}_{t}$ is the first-order momentum. Moreover, the regret bound
of AdaBelief is proved to be $O(\sqrt{T})$ when loss functions are convex.

Albeit its success, it remains however as an open problem _if the convergence
rate of AdaBelief can be further improved while not sacrificing its
generalization ability_. To this end, in this work we design a novel
optimization algorithm called FastAdaBelief that aims to exploiting the strong
convexity in order to achieve an even faster convergence rate but maintaining
an excellent generalization ability. Particularly, by adjusting the step size
that better considers strong convexity, appropriately utilizes curvature
information, and prevents fluctuation, our proposed FastAdaBelief attains a
substantially lower data-dependant regret bound, which generally promotes
AdaBelief from a sublinear level $O(\sqrt{T})$ to a logarithmic level $O(\log
T)$. To our best knowledge, FastAdaBelief presents a first attempt in
designing a powerful optimizer that converges faster with a logarithmic regret
bound while maintaining an excellent generalization ability simultaneously.

It is noted that Wang _et al._ proposed SAdam [25] to implement Adam into
strong convexity, which is also able to accelerate the regret bound of Adam
from $O(\sqrt{T})$ to $O(\log T)$. Unfortunately, SAdam generally has a poor
generalization ability as rooted from Adam, which may hence limit its
application in practice. In a closer examination, FastAdaBelief adopts the new
second order form, i.e.
$\mathbf{s}_{t}=\beta_{2}\mathbf{s}_{t-1}+(1-\beta_{2})(\mathbf{g}_{t}-\mathbf{m}_{t})^{2}$
that is significantly different from the form
$\mathbf{v}_{t}=\beta_{2}\mathbf{v}_{t-1}+(1-\beta_{2})\mathbf{g}_{t}^{2}$ of
SAdam; this brings a brand new challenge for the convergence analysis of
FastAdaBelief. Additionally, in order to fit strongly convex conditions,
FastAdaBelief designs a tailored diagonal matrix of the second order momentum,
which also lead to non-trivial challenge in the convergence analysis compared
with Adam. For a simple summary, the performance on convergence and
generalization ability of FastAdaBelief and the current mainstream optimizers
can be seen in Table I.

Our major contributions are summarized below:

  * •

We propose a fast variant of AdaBelief, named FastAdaBelief, to further
improve the convergence rate under strongly convex conditions. We show that
FastAdaBelief can lead to adaptive stepsize that is more in line with an ideal
optimizer.

  * •

We provide a convergence analysis for FastAdaBelief that presents a data-
dependant $O(\log T)$ guaranteed regret bound, which is substantially better
than AdaBelief.

  * •

We conduct extensive experiments to demonstrate that FastAdaBelief outperforms
the other state-of-the-art main-stream optimization algorithms in a variety of
tasks. Interestingly, even in case of non-strong convexity, FastAdaBelief
shows superior performance to the other comparison algorithms consistently in
all the datasets.

##  II Notation and Preliminaries

###  II-A Notation

In this paper, we use lower case bold letters to denote vectors, such as
$\mathbf{x}$. Moreover, $\mathbf{x}_{t}$ denotes the value of vector
$\mathbf{x}$ at time $t$. Furthermore, the $i$-th coordinate of vector
$\mathbf{x}_{t}$ is denoted by vector $x_{t,i}$. In addition, matrices are
represented in capital letters, such as $M$. Let $\mathcal{M}_{+}^{n}$ denote
the set of $n$ dimensional positive definite matrices. The $\ell_{2}$-norm and
the $\ell_{\infty}$-norm are denoted by $\|\cdot\|$ and $\|\cdot\|_{\infty}$
respectively. The $M$-weighted $\ell_{2}$-norm is defined by
$\|\mathbf{x}\|_{M}^{2}=\mathbf{x}^{\mathsf{T}}M\mathbf{x}$. We denote the
loss function by $f_{t}(\cdot)$ at time $t$, and its gradient is represented
by $\mathbf{g}_{t}$. Moreover, we use
$\mathbf{g}_{1:T,i}=[g_{1,i},\ldots,g_{T,i}]$ to denote the sequence
consisting of the $i$-th element of the gradient sequence
$\\{\mathbf{g}_{1},\ldots,\mathbf{g}_{T}\\}$. The $M$-weighted projection
operation of $\mathbf{x}$ on $\mathcal{F}$ is represented by
$\prod_{\mathcal{F},M}(\mathbf{x})=\arg\min_{\mathbf{y}\in\mathcal{F}}\|\mathbf{y}-\mathbf{x}\|_{M}^{2}$
for $\mathbf{x}\in\mathbb{R}^{n}$. Furthermore, we use $\mathbf{x}^{2}$ to
denote element-wise square, $\frac{\mathbf{x}}{\mathbf{y}}$ for element-wise
division, and $\sqrt{\mathbf{x}}$ to represent element-wise square root, where
$\mathbf{x},\mathbf{y}\in\mathbb{R}^{n}$. Moreover, we take
$A=\mathrm{diag}\\{\mathbf{x}\\}$ to denote the fact that $A$ is a diagonal
matrix composed of the elements of vector $\mathbf{x}$. We denote $I_{d}$ as a
$d\times d$ identity matrix. Furthermore, $\mathbf{x}^{*}$ is used to denote
the best decision in hindsight, i.e.,
$\mathbf{x}^{*}=\min_{\mathbf{x}\in\mathcal{F}}\sum_{t=1}^{T}f_{t}(\mathbf{x})$.

###  II-B Online Learning

Machine learning (ML) plays an important role in the field of artificial
intelligence. Moreover, offline learning in ML is usually expected to enable a
batch of tasks at the same time, but this situation is difficult to meet. In
contrast, online learning based on regret considers a sequential setting in
which tasks are revealed one by one. Online learning can better adapt to
complex and changeable practical applications and has become a prominent
paradigm for machine learning, which is attractive in both theory and practice
[26], [27], [28]. Within this paradigm, a learner generates iteratively a
decision $\mathbf{x}_{t}$ from a convex and compact domain
$\mathcal{F}\subset\mathbb{R}^{n}$ in each round $t\in\\{1,\ldots,T\\}$. In
response, an adversary produces a convex loss function
$f_{t}(\cdot):\mathcal{F}\rightarrow\mathbb{R}$ in round $t$, which causes the
learner to suffer the loss $f_{t}(\mathbf{x}_{t})$. The goal of the learner is
to generate a decision $\mathbf{x}_{t}$ so that the regret can decrease
quickly as $T$. Moreover, the regret is defined as follows:

$R(T)=\sum_{t=1}^{T}f_{t}(\mathbf{x}_{t})-\min_{\mathbf{x}\in\mathcal{F}}\sum_{t=1}^{T}f_{t}(\mathbf{x}).$
(1)

To improve the generalization ability of the Adam optimizer family, AdaBelief
fully considers the curvature information of loss functions, which will be
introduced as one preliminary background in the next subsection.

###  II-C AdaBelief

Figure 1: An ideal optimizer considers the curvature of the loss function and
prefers adaptive stepsize. $\Delta_{t}$ denotes the stepsize. FastAdaBelief
selects a stepsize more in line with the ideal optimizer (see more details in
Table II).

Input: $\beta_{1},\beta_{2}$

Output: $\mathbf{x}_{t+1}$

1 Initialize: $\mathbf{x}_{0},\mathbf{m}_{0},\mathbf{s}_{0}$

2 for  _$t=1\ldots T$_ do

3 $t\leftarrow t+1$

4 $\alpha_{t}\leftarrow\frac{\alpha}{\sqrt{t}}$

5 $\mathbf{g}_{t}\leftarrow\nabla f_{t}(\mathbf{x}_{t})$

6
$\mathbf{m}_{t}\leftarrow\beta_{1}\mathbf{m}_{t-1}+(1-\beta_{1})\mathbf{g}_{t}$

7
$\mathbf{s}_{t}\leftarrow\beta_{2}\mathbf{s}_{t-1}+(1-\beta_{2})(\mathbf{g}_{t}-\mathbf{m}_{t})^{2}$

8
$\hat{\mathbf{s}}_{t}\leftarrow\max\\{\hat{\mathbf{s}}_{t-1},\mathbf{s}_{t}\\}$

9 $\hat{S}_{t}\leftarrow\mathrm{diag}\\{\hat{\mathbf{s}}_{t}\\}$

10
$\mathbf{x}_{t+1}\leftarrow\prod_{\mathcal{F},\sqrt{\hat{S}_{t}}}\left(\mathbf{x}_{t}-\frac{\alpha_{t}\mathbf{m}_{t}}{\sqrt{\hat{S}_{t}}}\right)$

11return _$\mathbf{x}_{t+1}$_

Algorithm 1 AdaBelief

The algorithm design of AdaBelief is shown in Algorithm 1. Note that the
second order momentum of AdaBelief is symbolized by $\mathbf{s}_{t}$, and that
of Adam by $\mathbf{v}_{t}$ [17].

To better illustrate the difference of various optimizers, we exploit one
illustrative example similarly utilized by AdaBelief as shown in Figure 1. In
region 1 where the loss function is flat, the gradient $\mathbf{g}_{t}$ and
$|\mathbf{g}_{t}(\mathbf{x_{1}})-\mathbf{g}_{t}(\mathbf{x_{2}})|$ are both
very small. Therefore, a large stepsize should be taken in this case for the
efficiency of the optimizer. In this case, AdaBelief and Adam both take large
stepsizes, but SGD takes a small one.

In region 2, the loss function is “steep". Hence the gradient $\mathbf{g}_{t}$
and $|\mathbf{g}_{t}(\mathbf{x_{4}})-\mathbf{g}_{t}(\mathbf{x_{5}})|$ are both
very large. For this reason, an ideal optimizer should take a small stepsize.
By the design of the second order momentums in AdaBelief and Adam, they take a
small stepsize in this case while SGD exploits a large stepsize.

In region 3 called the “large gradient, small curvature" case, the gradient
$\mathbf{g}_{t}$ and $\mathbf{v}_{t}$ are both large while
$|\mathbf{g}_{t}-\mathbf{g}_{t-1}|$ and $\mathbf{s}_{t}$ are both small.
Therefore, the stepsize of an ideal optimizer should be increased. To this
end, AdaBelief takes a large stepsize since that denominator
$\sqrt{\mathbf{s}_{t}}$ is small, and SGD also takes a large stepsize.
Instead, Adam takes a small stepsize because of the large denominator
$\sqrt{\mathbf{v}_{t}}$.

To sum up, AdaBelief fully considers all the above curvature situations, and
adopts a good stepsize selection strategy in each situation. For this reason,
AdaBelief has the same good generalization ability as the SGD optimizer
family. Though AdaBelief retains the same regret bound guarantee $O(\sqrt{T})$
as Adam, it is interesting to explore if it can be further sped up. To this
end, we propose to utilize the strong convexity and develop a new model that
is able to advance the regret bound of Adabelief to logarithmic convergence in
this paper.

##  III FastAdaBelief

In this section, we first present the detailed design of the proposed
algorithm, and then analyze the theoretical guarantee of its regret bound.

###  III-A Algorithm Design

Before presenting the proposed algorithm, we introduce some standard
definitions and general assumptions, which follow the previous successful
works including [17], [18], [24], [25], [29].

###### Definition 1

A function $f(\cdot):\mathcal{F}\rightarrow\mathbb{R}$ is $\sigma$-strongly
convex, where $\sigma$ is a positive constant, if for all
$\mathbf{x},\mathbf{y}\in\mathcal{F}$ the following equation is satisfied

$f(\mathbf{x})-f(\mathbf{y})\geq\nabla
f(\mathbf{y})^{\mathsf{T}}(\mathbf{x}-\mathbf{y})+\frac{\sigma}{2}\|\mathbf{x}-\mathbf{y}\|^{2}.$
(2)

###### Assumption 1

The feasible region $\mathcal{F}\in\mathbb{R}^{n}$ is bounded, that is, for
all $\mathbf{x},\mathbf{y}\in\mathcal{F}$,
$\max_{\mathbf{x},\mathbf{y}\in\mathcal{F}}\|\mathbf{x}-\mathbf{y}\|_{\infty}\leq
D_{\infty}$, where $D_{\infty}>0$ is a constant.

###### Assumption 2

For all $t\in\\{1,\ldots,T\\}$, the gradients of all loss functions,
$\\{\nabla f_{t}(\mathbf{x})\\}_{t=1}^{T}$, are bounded. Specially, there
exists a constant $G_{\infty}>0$ such that
$\max_{\mathbf{x}\in\mathcal{F}}\|\nabla f_{t}(\mathbf{x})\|_{\infty}\leq
G_{\infty}$.

Input: $\\{\beta_{1t}\\}_{t=1}^{T},\\{\beta_{2t}\\}_{t=1}^{T},\delta$

Output: $\mathbf{x}_{t+1}$

1 Initialize: $\mathbf{x}_{0},\mathbf{m}_{0},\mathbf{s}_{0}$

2 for  _$t=1\ldots T$_ do

3 $t\leftarrow t+1$

4 $\alpha_{t}\leftarrow\frac{\alpha}{t}$

5 $\mathbf{g}_{t}\leftarrow\nabla f_{t}(\mathbf{x}_{t})$

6
$\mathbf{m}_{t}\leftarrow\beta_{1t}\mathbf{m}_{t-1}+(1-\beta_{1t})\mathbf{g}_{t}$

7
$\mathbf{s}_{t}\leftarrow\beta_{2t}\mathbf{s}_{t-1}+(1-\beta_{2t})(\mathbf{g}_{t}-\mathbf{m}_{t})^{2}$

8
$\hat{\mathbf{s}}_{t}\leftarrow\max\\{\hat{\mathbf{s}}_{t-1},\mathbf{s}_{t}\\}$

9
$\hat{S}_{t}\leftarrow\mathrm{diag}\\{\hat{\mathbf{s}}_{t}\\}+\frac{\delta}{t}I_{n}$

10
$\mathbf{x}_{t+1}\leftarrow\prod_{\mathcal{F},{\hat{S}_{t}}}\left(\mathbf{x}_{t}-\alpha_{t}\hat{S}_{t}^{-1}\mathbf{m}_{t}\right)$

11return _$\mathbf{x}_{t+1}$_

Algorithm 2 FastAdaBelief

Now we present an accelerated and accurate belief-based optimization algorithm
for strongly convex functions based on the above standard definitions and
assumptions, called FastAdaBelief. The detailed design of the proposed
algorithm is shown in Algorithm 2, which follows the general design of [24].
In the proposed algorithm, $\beta_{1t}$ and $\beta_{2t}$ are time-variant non-
increasing hyper-parameters, and $\delta$ is a positive constant. Moreover,
the parameter of step size, $\alpha_{t}$, is assigned as
$\alpha_{t}=\frac{\alpha}{t}$, where $\alpha$ is a constant. Furthermore, the
gradient of loss function at time $t$, $\mathbf{g}_{t}$, is calculated by
$\mathbf{g}_{t}=\nabla f_{t}(\mathbf{x}_{t})$. Next, the proposed algorithm
computes the first-order momentum, $\mathbf{m}_{t}$, through Exponential
Moving Average (EMA) of $\mathbf{g}_{t}$, which is shown as follows:

$\mathbf{m}_{t}=\beta_{1t}\mathbf{m}_{t-1}+(1-\beta_{1t})\mathbf{g}_{t}.$ (3)

Then, the second-order momentum, $\mathbf{s}_{t}$, in the proposed algorithm
is calculated by EMA of the square of the observed gradient belief
$(\mathbf{g}_{t}-\mathbf{m}_{t})$, i.e.,

$\mathbf{s}_{t}=\beta_{2t}\mathbf{s}_{t-1}+(1-\beta_{2t})(\mathbf{g}_{t}-\mathbf{m}_{t})^{2}.$
(4)

Moreover, to satisfy the condition of convergence, i.e.,
$\Gamma_{t}=\frac{\sqrt{\mathbf{s}_{t}}}{\alpha_{t}}-\frac{\sqrt{\mathbf{s}_{t-1}}}{\alpha_{t-1}}\succeq
0$, the proposed algorithm further provides the following operation on the
second-order momentum:

$\hat{\mathbf{s}}_{t}=\max\\{\hat{\mathbf{s}}_{t-1},\mathbf{s}_{t}\\}.$ (5)

Furthermore, to avoid step size explosion caused by too small gradients, the
proposed algorithm adds a vanishing factor $\frac{\delta}{t}$ to the second-
order momentum, and obtains the following diagonal matrix:

$\hat{S}_{t}=\mathrm{diag}\\{\hat{\mathbf{s}}_{t}\\}+\frac{\delta}{t}I_{n}.$
(6)

Finally, the proposed algorithm updates the decision point,
$\mathbf{x}_{t+1}$, conditional on the projection to the feasible region, and
attains the following:

$\mathbf{x}_{t+1}=\prod_{\mathcal{F},{\hat{S}_{t}}}\left(\mathbf{x}_{t}-\alpha_{t}\hat{S}_{t}^{-1}\mathbf{m}_{t}\right).$
(7)

In general, the proposed algorithm has two main modifications compared with
AdaBelief. The first modification is about the step size, which is modified to
$\frac{\alpha}{t}\hat{S}^{-1}$. The motivation behind this modification is to
satisfy the property of strongly convex optimization. Moreover, the second
modification is to change $\beta_{2}$ of AdaBelief to $\beta_{2t}$. Such time-
varying parameter, $\beta_{2t}$, is set to constant $\beta_{2}$ in AdaBelief,
which simplifies application and convergence proof but may lead to stepsize
fluctuations. In this work, we apply $\beta_{2t}$ in its original form which
achieves good convergence [18].

The detailed design of the proposed algorithm has been introduced in this
section. Next, we interpret why the proposed FastAdaBelief can choose a better
stepsize and leads to faster convergence. After that, we theoretically prove
that when the strong convexity of the loss functions holds, the proposed
algorithm has a guaranteed regret bound, which is much better than AdaBelief.

###  III-B Why FastAdaBelief can choose a better stepsize?

From the design of $\hat{S}_{t}$ in FastAdaBelief, our algorithm adds a
regularization term to the stepsize, which is originally considered to meet
the strongly convex condition, but unexpectedly brings significant benefits to
the choice of step size. If we let $\Delta$ denote the stepsize, then
stepsizes of SGD, Adam, SAdam, AdaBelief, and FastAdaBelief are shown in the
following:

$\displaystyle\Delta_{t}(SGD)=-\alpha\mathbf{m}_{t};$
$\displaystyle\Delta_{t}(Adam)=-\alpha\mathbf{m}_{t}/\sqrt{\mathbf{v}_{t}};$
$\displaystyle\Delta_{t}(SAdam)=-\alpha\mathbf{m}_{t}/\sqrt{\mathbf{v}_{t}+\delta/t};$
$\displaystyle\Delta_{t}(AdaBelief)=-\alpha\mathbf{m}_{t}/\sqrt{\mathbf{s}_{t}};$
$\displaystyle\Delta_{t}(FastAdaBelief)=-\alpha\mathbf{m}_{t}/\sqrt{\mathbf{s}_{t}+\delta/t}.$

If we look back into Figure 1, in region 1, FastAdaBelief chooses a larger
stepsize than AdaBelief that is consistent with the ideal optimizer. Moreover,
in region 2, a big stepsize is desired in the ideal optimizer. As a matter of
fact, in this region, FastAdaBelief will generate a stepsize bigger than that
of Adabelief, SAdam, Adam, and SGD. In addition, in region 3, the ideal
optimizer would prefer a small stepsize. Indeed, FastAdaBelief takes a smaller
stepsize than that of AdaBelief in this region, which is due to the addition
of regularization terms. In a brief summary, comparison of stepsize selection
by FastAdaBelief, AdaBelief, SAdam, Adam and SGD can be seen in Table II. This
analysis shows that FastAdaBelief is more in line with the choice of the ideal
optimizer and therefore can lead to better performance than the other
mainstream optimizers.

TABLE II: Stepsize selected by the ideal optimizer, FastAdaBelief, AdaBelief, SAdam, Adam and SGD in three regions of Figure 1. FastAdaBelief is more in line with the idea optimizer. (Note that symbols $L$ and $S$ denote large and small stepsize, respectively. And $L^{+}$ denotes a larger stepsize than $L$; $S^{-}$ denotes a smaller stepsize than $S$.) Stepsize | Region 1 | Region 2 | Region 3
---|---|---|---
$\Delta_{t}(ideal)$ | Large value | Large value | Small value
$\Delta_{t}(SGD)$ | $S$ | $L$ | $L$
$\Delta_{t}(Adam)$ | $L$ | $S$ | $S$
$\Delta_{t}(SAdam)$ | $L^{+}$ | $S^{-}$ | $S^{-}$
$\Delta_{t}(AdaBelief)$ | $L$ | $L$ | $S$
$\Delta_{t}(FastAdaBelief)$ | $L^{+}$ | $L^{+}$ | $S^{-}$

###  III-C Theoretical Guarantee

In this section, we first review some convergence conditions as earlier
developed by Reddi [18], which solves the convergence issue for Adam [17]. Let
$\\{\beta_{2t}\\}$ satisfy the following conditions:

##### Condition 1

For some $\zeta>0$ and all $t\in\\{1,\ldots,T\\}$, $j\in\\{1,\ldots,n\\}$, we
have that

$\frac{\sqrt{t}}{\alpha}\sqrt{\sum_{j=1}^{t}\prod_{k=1}^{t-j}\beta_{2(t-k+1)}(1-\beta_{2j})g_{j,i}^{2}}\geq\frac{1}{\zeta}\sqrt{\sum_{j=1}^{t}g_{j,i}^{2}}.$

##### Condition 2.

For all $t\in\\{1,\ldots,T\\}$ and $i\in\\{1,\ldots,n\\}$, we have that

$\frac{\sqrt{t}}{\alpha}s_{t,i}^{1/2}\geq\frac{\sqrt{t-1}}{\alpha}s_{t-1,i}^{1/2}.$

As a matter of fact, Condition 1 is an important and standard condition for
convergence analysis of adaptive momentum algorithms, such as Adam and
AdaBelief. Furthermore, the intrinsic motivation for Condition 2 is to follow
the key condition of SGD, where its step size $\frac{\alpha}{\sqrt{t}}$
satisfies that $\frac{\sqrt{t}}{\alpha}-\frac{\sqrt{t-1}}{\alpha}\geq
0,\forall t\in[T]$. For this reason, we also follow this motivation, and
propose the following conditions with minor modifications:

##### Condition 3.

For some $\zeta>0$ and all $t\in\\{1,\ldots,T\\}$, $j\in\\{1,\ldots,n\\}$, we
have that

$\frac{t}{\alpha}\sqrt{\sum_{j=1}^{t}\prod_{k=1}^{t-j}\beta_{2(t-k+1)}(1-\beta_{2j})g_{j,i}^{2}}\geq\frac{1}{\zeta}\sqrt{\sum_{j=1}^{t}g_{j,i}^{2}}.$
(8)

##### Condition 4.

For all $t\in\\{1,\ldots,T\\}$ and $i\in\\{1,\ldots,n\\}$, we have that

$0\leq\frac{t}{\alpha}s_{t,i}^{1/2}-\frac{t-1}{\alpha}s_{t-1,i}^{1/2}\leq\sigma(1-\beta_{1}).$
(9)

Now, we present the main results in the following for the convergence analysis
when Conditions 3 and 4 are satisfied.

###### Theorem 1

Suppose that Assumptions 1 and 2 are satisfied, Conditions 3 and 4 hold, and
loss functions $f_{t}(\cdot)$ are $\sigma$-strongly convex. Moreover, let
parameter sequences $\\{\beta_{1t}\\},\\{\beta_{2t}\\}$ and $\\{\alpha_{t}\\}$
are generated by the proposed algorithm, where
$\beta_{1t}=\beta_{1}\lambda^{t},\beta_{1}\in[0,1),\lambda_{1}\in[0,1),\beta_{2t}\in[0,1),\delta>0,t\in\\{1,\ldots,T\\}$.
For decision point $\mathbf{x}_{t}$ generated by the proposed algorithm, we
have the following upper bound of the regret

$\displaystyle R(T)$ $\displaystyle\leq\frac{n\delta
D_{\infty}^{2}}{2\alpha(1-\beta_{1})}+\frac{\alpha
r^{2}\log{T}}{(1-\beta_{1})^{2}}\sum_{i=1}^{n}\left\|g_{1:T,i}^{2}\right\|$
$\displaystyle+\frac{2\alpha
r^{2}+\alpha\delta^{2}}{2(1-\beta_{1})^{2}}\sum_{i=1}^{n}\left\|g_{1:T,i}^{2}\right\|$
$\displaystyle+\frac{n\beta_{1}\lambda
D_{\infty}^{2}(G_{\infty}+\delta)}{2\alpha(1-\beta_{1})(1-\lambda)^{2}}.$

The proof of Theorem 1 is provided in Appendix A. Accordingly, Theorem 1
implies that our proposed algorithm converges with $O(\log
T\sum_{i=1}^{n}\left\|g_{1:T,i}^{2}\right\|)$ regret bound in the case of
strong convexity. Moreover, the regret bound of the worst case is $O(n\log
T)$. In addition, the bound of the regret can be more tighter if the gradients
are sparse or small such that $\left\|g_{1:T,i}^{2}\right\|\ll
G_{\infty}^{2}T$.

###### Corollary 1

Letting $\beta_{1t}=\beta_{1}\lambda^{t}$, where $\lambda\in(0,1)$ in Theorem
1, we have the following upper bound of the regret

$\displaystyle R(T)$ $\displaystyle\leq\frac{n\delta
D_{\infty}^{2}}{2\alpha(1-\beta_{1})}+\frac{\alpha
r^{2}\log{T}}{(1-\beta_{1})^{2}}\sum_{i=1}^{n}\left\|g_{1:T,i}^{2}\right\|$
$\displaystyle+\frac{2\alpha
r^{2}+\alpha\delta^{2}}{2(1-\beta_{1})^{2}}\sum_{i=1}^{n}\left\|g_{1:T,i}^{2}\right\|$
$\displaystyle+\frac{n\beta_{1}\lambda
D_{\infty}^{2}(G_{\infty}+\delta)}{2\alpha(1-\beta_{1})(1-\lambda)^{2}}.$

The above Corollary 1 also implies that our proposed algorithm has a
convergence guarantee $O(n\log T)$ for condition
$\beta_{1t}=\beta_{1}\lambda^{t},\lambda\in(0,1),t\in\\{1,\ldots,T\\}$. Then,
our proposed algorithm executes with
$\lim_{T\rightarrow+\infty}\frac{R(T)}{T}=0$. Therefore, our proposed
algorithm converges when loss functions are strongly convex, and its
theoretical proof is provided in Appendix A. In order to verify the
performance of our algorithm in specific applications, we present a series of
experiments on benchmark public datasets in the following section.

##  IV Experiments

In this section, we conduct two groups of experiments to verify that our
proposed algorithm works excellently for standard optimization problems in
both cases of strong and non-strong convexity. In the first group, we consider
a strongly convex optimization problem of mini-batch $\ell_{2}$-regularized
softmax regression; in the second group, we apply our algorithm into non
strongly convex cases of deep training tasks with the traditional softmax
function. To be specific, the traditional softmax function is generally convex
but not strongly convex when the data is uniformly distributed. In some
extreme cases such as sparse or imbalanced data, for example, when a certain
category does not appear in the training set, softmax may even not satisfy
convexity [31], [32]. To examine the effectiveness of FastAdaBelief in real
scenarios, we intentionally conduct the second group of experiments on image
classification with CNN and language modeling with LSTM respectively, both of
which are commonly seen in practice. In all of our experiments, the source
codes are implemented in the torch 1.1.0 module of python 3.6 and executed on
$4\times 1080$ti GPUs. Furthermore, we compare FastAdaBelief with other
algorithms in both experiments, including SGD [15], Adam [17], Yogi [20],
AdaBound [19], AdaBelief [24], SAdam [25].

###  IV-A Hyperparameter Tuning

We perform the following hyperparameter tuning in experiments of image
classification and language modeling.

_SGD:_ We follow the standard settings of ResNet [33] and DenseNet [34], and
set the momentum as $0.9$. We choose the learning rate from
$\\{10.0,1.0,0.1,0.01,0.001\\}$.

_Adam:_ We adopt the same parameter setting as the original article [17] where
the first-order momentum $\beta_{1}$ is set to $0.9$, and the second-order
momentum $\beta_{2}$ is set to $0.999$. Moreover, the step size $\alpha_{t}$
is set to $\alpha/\sqrt{t}$, where $\alpha$ is chosen from
$\\{0.1,0.01,0.001,0.0001\\}$.

_Yogi:_ Following [20], we set the first-order momentum $\beta_{1}$ to $0.9$
and set the second-order momentum $\beta_{2}$ to $0.999$. In addition, the
step size $\alpha_{t}$ is set to $\alpha/\sqrt{t}$, where $\alpha$ is chosen
from $\\{0.1,0.01,0.001,0.0001\\}$.

_AdaBound:_ We directly apply the default hyper-parameters following [19] for
AdaBound (i.e., $\beta_{1}=0.9$ and $\beta_{2}=0.999$). Moreover, the step
size $\alpha_{t}$ is set to $\alpha/\sqrt{t}$, where $\alpha$ is chosen from
$\\{0.1,0.01,0.001,0.0001\\}$.

_AdaBelief:_ We use the default hyperparameters as suggested in [24], i.e.,
$\beta_{1}=0.9$, $\beta_{2}=0.999$, and $\epsilon=10^{-8}$. In addition, the
step size $\alpha_{t}$ is set to $\alpha/\sqrt{t}$, where $\alpha$ is chosen
from $\\{0.1,0.01,0.001,0.0001\\}$.

_SAdam:_ We set the hyperparameters by following [25], i.e., $\beta_{1}=0.9$,
$\beta_{2t}=1-\frac{0.9}{t}$. The step size $\alpha_{t}$ is set to $\alpha/t$,
where $\alpha$ is chosen from $\\{0.1,0.01,0.001,0.0001\\}$.

_FastAdaBelief:_ We adopt the same hyperparameters as SAdam: $\beta_{1}=0.9$,
$\beta_{2t}=1-\frac{0.9}{t}$. Moreover, the step size is set to $\alpha/t$,
where $\alpha$ is chosen from $\\{0.1,0.01,0.001,0.0001\\}$.

It can be seen that, for fair comparison, all the above algorithms basically
follow a similar parameter setting.

###  IV-B Datasets

In the experiments of CNN based image classification, we perform evaluations
on the benchmark CIFAR-10 dataset. Moreover, we apply the algorithms on three
standard baseline models, i.e., DenseNet-121, ResNet-34, and VGG-11.
DenseNet-121 is a dense convolutional network, which connects each layer to
all other layers feed-forwardly; ResNet-34 is a residual learning framework;
VGG-11 is a deep network using an architecture with small convolution filters.
In the LSTM based language modeling experiments, we test the various
algorithms on Penn Treebank dataset. Furthermore, we compare the algorithms in
1,2,3-layer LSTM models. For clarity, we show the summary of datasets and
architectures used in our experiments in Table III.

TABLE III: Datasets and architectures used in our experiments. Task | Dataset | Architecture
---|---|---
Image Classification | MNIST | 4-layers CNN
Image Classification | CIFAR-10 | 4-layers CNN,DenseNet-121, ResNet-34, VGG-11
Image Classification | CIFAR-100 | 4-layers CNN
Language Modeling | Penn Treebank | 1,2,3-Layer LSTM.

###  IV-C Optimization with Strong Convexity

Figure 2: Loss _v.s._ iterations for mini-batch $\ell_{2}$-regularized softmax regression (strongly convex). FastAdaBelief converges the quickest. Figure 3: Comparison of loss of SGD, Adam, AdaBound, Yogi, AdaBelief, SAdam and FastAdaBelief. FastAdaBelief converges the quickest. Figure 4: Comparison of training accuracy of SGD, Adam, AdaBound, Yogi, AdaBelief, SAdam and FastAdaBelief. FastAdaBelief achieves the highest training accuracy. Figure 5: Comparison of test accuracy of SGD, Adam, AdaBound, Yogi, AdaBelief, SAdam and FastAdaBelief. FastAdaBelief achieves the highest test accuracy. Figure 6: Comparison of perplexity of SGD, Adam, AdaBound, Yogi, AdaBelief, SAdam and FastAdaBelief (Lower is better). FastAdaBelief converges the quickest. TABLE IV: Test perplexity (lower is better) of 1,2,3-layer LSTM on Penn Treebank. Note that the two best performing algorithms are marked in bold. Model | SGD | Adam | AdaBound | Yogi | AdaBelief | SAdam | FastAdaBelief
---|---|---|---|---|---|---|---
1-layer LSTM | 85.07 | 84.28 | 84.78 | 86.59 | 84.21 | 84.19 | 84.18
2-layer LSTM | 67.42 | 67.27 | 67.53 | 71.33 | 66.29 | 68.11 | 66.08
3-layer LSTM | 63.58 | 64.28 | 63.58 | 67.51 | 61.23 | 64.71 | 61.21

In this group of experiments, we consider a mini-batch task. In round $t$ of
this task, the optimizer receives a mini-batch of training samples denoted by
$\\{\mathbf{x}_{m},y_{m}\\}_{i=1}^{m}$, where $m$ is the batch size, $K$ is
the number of classes, and $y_{i}\in[K]$ and $\forall i\in[m]$. Then the
optimizer generates decision vectors denoted by
$\\{\mathbf{w}_{i},b_{i}\\}_{i=1}^{K}$. Finally, the generated result suffers
a loss. The loss function is then given as

$\displaystyle J(\mathbf{w})=$
$\displaystyle-\frac{1}{m}\sum_{i=1}^{m}\log\left(\frac{e^{\mathbf{w}_{y_{i}}^{\top}\mathbf{x}_{i}+b_{y_{i}}}}{\sum_{j=1}^{K}e^{\mathbf{w}_{j}^{\top}\mathbf{x}_{i}+b_{j}}}\right)+\sigma_{1}\sum_{k=1}^{K}\|\mathbf{w}_{k}\|^{2}$
$\displaystyle+\sigma_{2}\sum_{k=1}^{K}b_{k}^{2}.$ (10)

In our experiments, we set parameters $\sigma_{1}$ and $\sigma_{2}$ both to
$0.01$. In addition, we conduct the experiment on the loss _v.s._ iterations.
The results of this experiment are shown in Figure 2. As clearly observed, the
loss of our proposed algorithm decreases the quickest and FastAdaBelief leads
to the best convergence in all the mainstream algorithms. As guaranteed
theoretically, the strongly convex optimization algorithms (such as
FastAdaBelief and SAdam) outperform the convex optimization algorithms (like
Adam, AdaBelief, etc.) in the strongly convex case. When we inspect the
difference between the two strongly convex optimization algorithms,
FastAdaBelief generates much lower losses (particularly on CIFAR10 and
CIFAR100) than SAdam, which echos the advantages of FastAdaBelief than SAdam
regarding the generalization ability.

###  IV-D Training DNN with Non-strong Convexity

FastAdaBelief enjoys the theoretical superiority to the other mainstream
optimizers when strong convexity holds. On the empirical side, the current
DNNs may however adopt loss functions that are typically not strongly convex
(e.g. only convex). Thus it is both interesting and important to investigate
if the proposed fast algorithm can still work well. For this purpose, we
conduct a series of empirical study on the tasks of image classification and
language modeling in the following.

####  IV-D1 Image Classification

In the experiments of image classification, we take the CIFAR-10 as one
typical example and compare the various algorithms with DenseNet-121,
ResNet-34 and VGG-11. First, we compare the convergence rate for all the
algorithms used in our experiment. Such results are reported in Figure 3. As
clearly observed, though the strong convexity may not hold, FastAdaBelief
still leads to remarkable convergence, which is consistently faster than all
the other algorithms. In comparison, SAdam also converges well, which
empirically demonstrates the power of the strongly convex algorithms.
Furthermore, SGD converges the slowest; Adam and Adabelief are also much
slower than both SAdam and FastAdaBelief. All these empirical results are
consistent with the theoretical analysis as we discussed earlier in Section II
and Section III though the loss functions are not strongly convex.

Second, we record the training and test accuracy curves of all the algorithms
executed in our experiments, which are shown in Figure 4 and Figure 5. We can
see that FastAdaBelief outperforms the other comparison algorithms in 200
epochs on DenseNet-121, ResNet-34 and VGG-11. In more details, FastAdaBelief
demonstrates much faster convergence as well as the highest accuracy within
200 epochs than all the other comparison algorithms on the three baseline DNN
models. Additionally, it is also evident that AdaBelief and FastAdaBelief
generally lead to the best accuracy in the 200 epoch, which verifies the
excellent generalization ability of the belief-based adaptive algorithms. It
is noted that SGD did not converge actually due to its slow convergence rate
though it could still catch up with the accuracy of AdaBelief and
FastAdaBelief in the long run.

To sum up, the experiments of image classification with DenseNet-121,
ResNet-34 and VGG-11 on CIFAR-10 validate the fast convergence rate and
excellent accuracy performance of FastAdaBelief even when strong convexity
does not hold in the loss functions.

####  IV-D2 Language Modeling

We also conduct a group of experiments on the language modeling task. In this
group of experiments, we use a classic recurrent network (i.e., LSTM) and an
open dataset (i.e., Penn Treebank). Same as the previous works [24], [25],
[35], [36], we take the perplexity to measure the performance of all the
comparison algorithms. Note that the lower perplexity is better.

The perplexity curves of all the algorithms are shown in Figure 6. In the
figure, once again we can see that FastAdaBelief performs similar to SAdam on
1-layer LSTM, and these two algorithms both perform better than the rest of
the algorithms. However, on the 2,3-layer LSTM, FastAdaBelief performs better
than SAdam and the other algorithms. Moreover, the perplexity of FastAdaBelief
decreases the fastest among all the algorithms, which further validates the
convergence analysis of FastAdaBelief.

We also summarize the test perplexities of all the algorithms performed in
this group of experiments, which are shown in Table IV. From the table, we can
see that FastAdaBelief attains superior performance to the other algorithms on
all three models (i.e., 1,2,3-layer LSTM). In summary, FastAdaBelief also
keeps both excellent generalization ability and fast convergence rate for
language modeling tasks even when loss functions are not strongly convex.
These empirical results are very encouraging, suggesting that FastAdaBelief
has a high potential to be widely applied in real scenarios.

##  V Conclusion and Future Work

In this paper, we made a first attempt and presented an affirmative answer to
the question whether AdaBelief can be further improved on its convergence rate
under the strongly convex condition. Specifically, we exploited strong
convexity and proposed a new algorithm named FastAdaBelief, which exhibits an
even faster data-dependent regret bound of $O(\log T)$ while maintaining
excellent generalization ability. In light of our theoretical findings, we
carried out a series of empirical studies which validated the superiority of
our proposed algorithm. Importantly, we showed that FastAdaBelief converged
the fastest in not only strong convexity, but also non-strong convexity, hence
demonstrating its high potential as a new benchmark model that can be widely
utilised in various scenarios.

In our current work, by exploiting its strong convexity, FastAdaBelief has
empirically demonstrated excellent generalization as well as fast convergence
even when the loss functions are not strongly convex. We believe that such
phenomenon may be partially due to the regularization term $\delta/t$ as
engaged in the second order moment that enables a closer approximation to an
ideal step size. However, it remains unclear why this may happen strictly in
theory. We will leave this investigation as future work.

##  Appendix A Convergence Analysis in Strongly Convex Online Optimization

Before presenting the proof of Theorem 1, we first review the following Lemma
1.

###### Lemma 1

[30] For all $M\in\mathcal{M}_{+}^{n}$ and convex feasible region
$\mathcal{F}\in\mathbb{R}^{n}$, let

$\mathbf{y}_{1}=\min_{\mathbf{x}\in\mathcal{F}}\left\|M^{1/2}(\mathbf{x}-\mathbf{z}_{1})\right\|,$

and

$\mathbf{y}_{2}=\min_{\mathbf{x}\in\mathcal{F}}\left\|M^{1/2}(\mathbf{x}-\mathbf{z}_{2})\right\|,$

then we obtain the following:

$\left\|M^{1/2}(\mathbf{y}_{1}-\mathbf{y}_{2})\right\|\leq\left\|M^{1/2}(\mathbf{z}_{1}-\mathbf{z}_{2})\right\|.$

Theorem 1 Suppose that Assumptions 1 and 2 are satisfied, Conditions 3 and 4
hold, and loss functions $f_{t}(\cdot)$ are $\sigma$-strongly convex.
Moreover, let parameter sequences $\\{\beta_{1t}\\},\\{\beta_{2t}\\}$ and
$\\{\alpha_{t}\\}$ are generated by the proposed algorithm, where
$\beta_{1t}=\beta_{1}\lambda^{t},\beta_{1}\in[0,1),\lambda_{1}\in[0,1),\beta_{2t}\in[0,1),\delta>0,t\in\\{1,\ldots,T\\}$.
For decision point $\mathbf{x}_{t}$ generated by the proposed algorithm, we
have the following upper bound of the regret

$\displaystyle R(T)$ $\displaystyle\leq\frac{n\delta
D_{\infty}^{2}}{2\alpha(1-\beta_{1})}+\frac{\alpha
r^{2}\log{T}}{(1-\beta_{1})^{2}}\sum_{i=1}^{n}\left\|g_{1:T,i}^{2}\right\|$
$\displaystyle+\frac{2\alpha
r^{2}+\alpha\delta^{2}}{2(1-\beta_{1})^{2}}\sum_{i=1}^{n}\left\|g_{1:T,i}^{2}\right\|$
$\displaystyle+\frac{n\beta_{1}\lambda
D_{\infty}^{2}(G_{\infty}+\delta)}{2\alpha(1-\beta_{1})(1-\lambda)^{2}}.$

##### _Proof._

By the updating method of decision variable, i.e., Equation (7), we have:

$\displaystyle\mathbf{x}_{t+1}$
$\displaystyle=\prod_{\mathcal{F},{\hat{S}_{t}}}\left(\mathbf{x}_{t}-\alpha_{t}\hat{S}_{t}^{-1}\mathbf{m}_{t}\right)$
$\displaystyle=\min_{\mathbf{x}\in\mathcal{F}}\left\|\hat{S}_{t}^{1/2}\left[\mathbf{x}-(\mathbf{x}_{t}-\alpha_{t}\hat{S}_{t}^{-1}\mathbf{m}_{t})\right]\right\|.$
(11)

From the definitions of $\mathbf{x}^{*}$ and projection $\prod(\cdot)$, we
have that
$\mathbf{x}^{*}=\prod_{\mathcal{F},\hat{S}_{t}}(\mathbf{x}^{*})=\min_{\mathbf{x}\in\mathcal{F}}(\mathbf{x}-\mathbf{x}^{*})$.
In addition, if we apply Lemma 1, let
$\mathbf{y}_{1}=\mathbf{x}_{t+1},\mathbf{y}_{2}=\mathbf{x}^{*}$, by the update
rules of $\mathbf{x}_{t}$ and $\mathbf{m}_{t}$, we obtain the following:

$\displaystyle\left\|\hat{S}_{t}^{1/2}\left(\mathbf{x}_{t+1}-\mathbf{x}^{*}\right)\right\|^{2}$
$\displaystyle\leq\left\|\hat{S}_{t}^{1/2}\left(\mathbf{x}_{t}-\alpha_{t}\hat{S}_{t}^{-1}\mathbf{m}_{t}-\mathbf{x}^{*}\right)\right\|^{2}$
$\displaystyle=\left\|\hat{S}_{t}^{1/2}\left(\mathbf{x}_{t}-\mathbf{x}^{*}\right)\right\|^{2}-\hat{S}_{t}\left\langle\mathbf{x}_{t}-\mathbf{x}^{*},\alpha_{t}\hat{S}_{t}^{-1}\mathbf{m}_{t}\right\rangle$
$\displaystyle+\left\|\alpha_{t}\hat{S}_{t}^{-1/2}\mathbf{m}_{t}\right\|^{2}$
$\displaystyle=\left\|\hat{S}_{t}^{1/2}\left(\mathbf{x}_{t}-\mathbf{x}^{*}\right)\right\|^{2}+\alpha_{t}^{2}\left\|\hat{S}_{t}^{-1/2}\mathbf{m}_{t}\right\|^{2}$
$\displaystyle-2\alpha_{t}\left\langle\mathbf{x}_{t}-\mathbf{x}^{*},\mathbf{m}_{t}\right\rangle$
$\displaystyle=\left\|\hat{S}_{t}^{1/2}\left(\mathbf{x}_{t}-\mathbf{x}^{*}\right)\right\|^{2}+\alpha_{t}^{2}\left\|\hat{S}_{t}^{-1/2}\mathbf{m}_{t}\right\|^{2}$
$\displaystyle-2\alpha_{t}\left\langle\mathbf{x}_{t}-\mathbf{x}^{*},\beta_{1t}\mathbf{m}_{t-1}+(1-\beta_{1t})\mathbf{g}_{t}\right\rangle.$
(12)

Next, rearranging equation (A), we have that

$\displaystyle\left\langle\mathbf{g}_{t},\mathbf{x}_{t}-\mathbf{x}^{*}\right\rangle$
$\displaystyle\leq\frac{\left[\left\|\hat{S}_{t}^{1/2}\left(\mathbf{x}_{t}-\mathbf{x}^{*}\right)\right\|^{2}-\left\|\hat{S}_{t}^{1/2}\left(\mathbf{x}_{t+1}-\mathbf{x}^{*}\right)\right\|^{2}\right]}{2\alpha_{t}(1-\beta_{1t})}$
$\displaystyle+\frac{\alpha_{t}}{2(1-\beta_{1t})}\left\|\hat{S}_{t}^{-1/2}\mathbf{m}_{t}\right\|^{2}\underbrace{-\frac{\beta_{1t}}{1-\beta_{1t}}\left\langle\mathbf{m}_{t-1},\mathbf{x}_{t}-\mathbf{x}^{*}\right\rangle}_{(a)}.$
(13)

Applying Young’s inequality (i.e., $\langle
a,b\rangle\leq\frac{a^{2}\epsilon}{2}+\frac{b^{2}}{2\epsilon},\forall\epsilon>0$)
into the term $(a)$ of Equation (A), and considering
$\alpha_{t}>0,\beta_{1t}\in[0,1)$, we can attain

$\displaystyle(a)$
$\displaystyle=-\frac{\beta_{1t}}{1-\beta_{1t}}\left\langle\mathbf{m}_{t-1},\mathbf{x}_{t}-\mathbf{x}^{*}\right\rangle$
$\displaystyle\leq\frac{\alpha_{t}\beta_{1t}}{2(1-\beta_{1t})}\left(\hat{S}_{t}^{-1/2}\mathbf{m}_{t-1}\right)^{2}$
$\displaystyle+\frac{\beta_{1t}}{2\alpha_{t}(1-\beta_{1t})}\left(\hat{S}_{t}^{1/2}(\mathbf{x}_{t}-\mathbf{x}^{*})\right)^{2}.$
(14)

Furthermore, applying Cauchy-Schwartz inequality into Equation (A), we have

$\displaystyle(a)$
$\displaystyle\leq\frac{\alpha_{t}\beta_{1t}}{2(1-\beta_{1t})}\left\|\hat{S}_{t}^{-1/2}\mathbf{m}_{t-1}\right\|^{2}$
$\displaystyle+\frac{\beta_{1t}}{2\alpha_{t}(1-\beta_{1t})}\left\|\hat{S}_{t}^{1/2}(\mathbf{x}_{t}-\mathbf{x}^{*})\right\|^{2}.$
(15)

Then, plugging Equation (A) into Equation (A), we obtain the following

$\displaystyle\left\langle\mathbf{g}_{t},\mathbf{x}_{t}-\mathbf{x}^{*}\right\rangle$
$\displaystyle\leq\frac{\left[\left\|\hat{S}_{t}^{1/2}\left(\mathbf{x}_{t}-\mathbf{x}^{*}\right)\right\|^{2}-\left\|\hat{S}_{t}^{1/2}\left(\mathbf{x}_{t+1}-\mathbf{x}^{*}\right)\right\|^{2}\right]}{2\alpha_{t}(1-\beta_{1t})}$
$\displaystyle+\frac{\alpha_{t}}{2(1-\beta_{1t})}\left\|\hat{S}_{t}^{-1/2}\mathbf{m}_{t}\right\|^{2}+\frac{\alpha_{t}\beta_{1t}}{2(1-\beta_{1t})}\left\|\hat{S}_{t}^{-1/2}\mathbf{m}_{t-1}\right\|^{2}$
$\displaystyle+\frac{\beta_{1t}}{2\alpha_{t}(1-\beta_{1t})}\left\|\hat{S}_{t}^{1/2}(\mathbf{x}_{t}-\mathbf{x}^{*})\right\|^{2}.$
(16)

On the other hand, let $\mathbf{x}=\mathbf{x}^{*},\mathbf{y}=\mathbf{x}_{t}$
in Equation (2). With the strong convexity of $f_{t}(\cdot)$, we attain

$\displaystyle
f_{t}(\mathbf{x}_{t})-f_{t}(\mathbf{x}^{*})\leq\left\langle\mathbf{g}_{t},\mathbf{x}_{t}-\mathbf{x}^{*}\right\rangle-\frac{\sigma}{2}\|\mathbf{x}_{t}-\mathbf{x}^{*}\|^{2}.$
(17)

Therefore, from definition of the regret (i.e., Equation (1)), and Equation
(17), we obtain the following

$\displaystyle R(T)$
$\displaystyle=\sum_{t=1}^{T}f_{t}(\mathbf{x}_{t})-\min_{\mathbf{x}\in\mathcal{F}}\sum_{t=1}^{T}f_{t}(\mathbf{x})$
$\displaystyle=\sum_{t=1}^{T}f_{t}(\mathbf{x}_{t})-\sum_{t=1}^{T}f_{t}(\mathbf{x}^{*})$
$\displaystyle\leq\sum_{t=1}^{T}\left\langle\mathbf{g}_{t},\mathbf{x}_{t}-\mathbf{x}^{*}\right\rangle-\frac{\sigma}{2}\sum_{t=1}^{T}\|\mathbf{x}_{t}-\mathbf{x}^{*}\|^{2}.$
(18)

In addition, plugging Equation (A) into Equation (A), we can attain the
following

$\displaystyle R(T)$
$\displaystyle\leq\sum_{t=1}^{T}\frac{\left[\left\|\hat{S}_{t}^{1/2}\left(\mathbf{x}_{t}-\mathbf{x}^{*}\right)\right\|^{2}-\left\|\hat{S}_{t}^{1/2}\left(\mathbf{x}_{t+1}-\mathbf{x}^{*}\right)\right\|^{2}\right]}{2\alpha_{t}(1-\beta_{1t})}$
$\displaystyle+\sum_{t=1}^{T}\frac{\alpha_{t}}{2(1-\beta_{1t})}\left\|\hat{S}_{t}^{-1/2}\mathbf{m}_{t}\right\|^{2}$
$\displaystyle+\sum_{t=1}^{T}\frac{\alpha_{t}\beta_{1t}}{2(1-\beta_{1t})}\left\|\hat{S}_{t}^{-1/2}\mathbf{m}_{t-1}\right\|^{2}$
$\displaystyle+\sum_{t=1}^{T}\frac{\beta_{1t}}{2\alpha_{t}(1-\beta_{1t})}\left\|\hat{S}_{t}^{1/2}(\mathbf{x}_{t}-\mathbf{x}^{*})\right\|^{2}$
$\displaystyle-\frac{\sigma}{2}\sum_{t=1}^{T}\|\mathbf{x}_{t}-\mathbf{x}^{*}\|^{2}.$
(19)

Furthermore, since $0\leq s_{t-1,i}\leq
s_{t,i},0\leq\alpha_{t}\leq\alpha_{t-1},0\leq\beta_{1t}\leq\beta_{1}<1$, by
Equation (A), we have

$\displaystyle R(T)$
$\displaystyle\leq\underbrace{\sum_{t=1}^{T}\frac{\left[\left\|\hat{S}_{t}^{1/2}\left(\mathbf{x}_{t}-\mathbf{x}^{*}\right)\right\|^{2}-\left\|\hat{S}_{t}^{1/2}\left(\mathbf{x}_{t+1}-\mathbf{x}^{*}\right)\right\|^{2}\right]}{2\alpha_{t}(1-\beta_{1t})}}$
$\displaystyle\underbrace{-\frac{\sigma}{2}\sum_{t=1}^{T}\|\mathbf{x}_{t}-\mathbf{x}^{*}\|^{2}}_{E_{1}}$
$\displaystyle+\underbrace{\sum_{t=1}^{T}\frac{\alpha_{t}}{2(1-\beta_{1t})}\left\|\hat{S}_{t}^{-1/2}\mathbf{m}_{t}\right\|^{2}}$
$\displaystyle\underbrace{+\sum_{t=2}^{T}\frac{\beta_{1}\alpha_{t-1}}{2(1-\beta_{1})}\left\|\hat{S}_{t-1}^{-1/2}\mathbf{m}_{t-1}\right\|^{2}}_{E_{2}}$
$\displaystyle+\underbrace{\sum_{t=1}^{T}\frac{\beta_{1t}}{2\alpha_{t}(1-\beta_{1t})}\left\|\hat{S}_{t}^{1/2}(\mathbf{x}_{t}-\mathbf{x}^{*})\right\|^{2}}_{E_{3}}.$
(20)

Next, we consider the upper bounds of three parts ($E_{1},E_{2}$ and $E_{3}$)
in Equation (A) respectively. For part $E_{1}$, we attain the following

$\displaystyle E_{1}$
$\displaystyle=\frac{1}{2\alpha_{1}(1-\beta_{1})}\left\|\hat{S}_{1}^{1/2}\left(\mathbf{x}_{1}-\mathbf{x}^{*}\right)\right\|^{2}$
$\displaystyle+\sum_{t=2}^{T}\frac{1}{2\alpha_{t}(1-\beta_{1t})}\left\|\hat{S}_{t}^{1/2}\left(\mathbf{x}_{t}-\mathbf{x}^{*}\right)\right\|^{2}$
$\displaystyle-\sum_{t=2}^{T}\frac{1}{2\alpha_{t-1}(1-\beta_{1(t-1)})}\left\|\hat{S}_{t-1}^{1/2}\left(\mathbf{x}_{t}-\mathbf{x}^{*}\right)\right\|^{2}$
$\displaystyle-\frac{1}{2\alpha_{T}(1-\beta_{1T})}\left\|\hat{S}_{T}^{1/2}\left(\mathbf{x}_{T+1}-\mathbf{x}^{*}\right)\right\|^{2}$
$\displaystyle-\frac{\sigma}{2}\sum_{t=1}^{T}\|\mathbf{x}_{t}-\mathbf{x}^{*}\|^{2}$
$\displaystyle\leq\sum_{t=2}^{T}\frac{1}{1-\beta_{1t}}\Bigg{[}\frac{\left\|\hat{S}_{t}^{1/2}\left(\mathbf{x}_{t}-\mathbf{x}^{*}\right)\right\|^{2}}{2\alpha_{t}}$
$\displaystyle-\frac{\left\|\hat{S}_{t-1}^{1/2}\left(\mathbf{x}_{t}-\mathbf{x}^{*}\right)\right\|^{2}}{2\alpha_{t-1}}\Bigg{]}$
$\displaystyle+\frac{1}{2\alpha_{1}(1-\beta_{1})}\left\|\hat{S}_{1}^{1/2}\left(\mathbf{x}_{1}-\mathbf{x}^{*}\right)\right\|^{2}-\frac{\sigma}{2}\sum_{t=1}^{T}\|\mathbf{x}_{t}-\mathbf{x}^{*}\|^{2}.$
(21)

Since $\alpha_{t}=\frac{\alpha}{t}$ and from Equation (A), we have the
following

$\displaystyle E_{1}$
$\displaystyle\leq\sum_{t=2}^{T}\frac{1}{1-\beta_{1t}}\Bigg{[}\frac{t\left\|\hat{S}_{t}^{1/2}\left(\mathbf{x}_{t}-\mathbf{x}^{*}\right)\right\|^{2}}{2\alpha}$
$\displaystyle-\frac{(t-1)\left\|\hat{S}_{t-1}^{1/2}\left(\mathbf{x}_{t}-\mathbf{x}^{*}\right)\right\|^{2}}{2\alpha}\Bigg{]}$
$\displaystyle+\frac{1}{2\alpha_{1}(1-\beta_{1})}\left\|\hat{S}_{1}^{1/2}\left(\mathbf{x}_{1}-\mathbf{x}^{*}\right)\right\|^{2}$
$\displaystyle-\frac{\sigma}{2}\sum_{t=2}^{T}\|\mathbf{x}_{t}-\mathbf{x}^{*}\|^{2}-\frac{\sigma}{2}\|\mathbf{x}_{1}-\mathbf{x}^{*}\|^{2}$
$\displaystyle=\sum_{t=2}^{T}\frac{1}{2\alpha(1-\beta_{1t})}\underbrace{\Bigg{[}t\left\|\hat{S}_{t}^{1/2}\left(\mathbf{x}_{t}-\mathbf{x}^{*}\right)\right\|^{2}}$
$\displaystyle\underbrace{-(t-1)\left\|\hat{S}_{t-1}^{1/2}\left(\mathbf{x}_{t}-\mathbf{x}^{*}\right)\right\|^{2}-\sigma\alpha(1-\beta_{1t})\|\mathbf{x}_{t}-\mathbf{x}^{*}\|^{2}\Bigg{]}}_{E_{1}^{{}^{\prime}}}$
$\displaystyle+\underbrace{\frac{1}{2\alpha_{1}(1-\beta_{1})}\left\|\hat{S}_{1}^{1/2}\left(\mathbf{x}_{1}-\mathbf{x}^{*}\right)\right\|^{2}-\frac{\sigma}{2}\|\mathbf{x}_{1}-\mathbf{x}^{*}\|^{2}}_{E_{1}^{{}^{\prime\prime}}}.$
(22)

In addition, for term $E_{1}^{{}^{\prime}}$ of Equation (A), and from Equation
(6), we can obtain

$\displaystyle E_{1}^{{}^{\prime}}$
$\displaystyle=\sum_{i=1}^{n}(x_{t,i}-x^{*}_{,i})^{2}\Bigg{[}t\left(\hat{s}_{t,i}+\frac{\delta}{t}\right)^{1/2}$
$\displaystyle-(t-1)\left(\hat{s}_{t-1,i}+\frac{\delta}{t-1}\right)^{1/2}-\sigma\alpha(1-\beta_{1t})\Bigg{]},$
(23)

where $i\in\\{1,\ldots,n\\}$, and $n$ is the dimension of decision vectors.
Moreover, since $(a+b)^{1/2}\leq a^{1/2}+b^{1/2}$ and $1-\beta_{1}\leq
1-\beta_{1t}$, by Equation (9), we can have the following

$\displaystyle E_{1}^{{}^{\prime}}$
$\displaystyle\leq\sum_{i=1}^{n}(x_{t,i}-x^{*}_{,i})^{2}\Bigg{[}t\hat{s}_{t,i}^{1/2}-(t-1)\hat{s}_{t-1,i}^{1/2}-$
$\displaystyle\sqrt{\delta(t-1)}-\sigma\alpha(1-\beta_{1t})\Bigg{]}$
$\displaystyle\leq\sum_{i=1}^{n}(x_{t,i}-x^{*}_{,i})^{2}\Bigg{[}ts_{t,i}^{1/2}-(t-1)s_{t-1,i}^{1/2}-\sqrt{\delta(t-1)}$
$\displaystyle-\sigma\alpha(1-\beta_{1t})\Bigg{]}$
$\displaystyle\leq\sum_{i=1}^{n}(x_{t,i}-x^{*}_{,i})^{2}\Bigg{[}\sigma\alpha(1-\beta_{1})-\sqrt{\delta(t-1)}$
$\displaystyle-\sigma\alpha(1-\beta_{1t})\Bigg{]}$ $\displaystyle\leq 0.$ (24)

Next, for term $E_{1}^{{}^{\prime\prime}}$ of Equation (A), we have

$\displaystyle E_{1}^{{}^{\prime\prime}}$
$\displaystyle=\frac{1}{2\alpha_{1}(1-\beta_{1})}\left\|\hat{S}_{1}^{1/2}\left(\mathbf{x}_{1}-\mathbf{x}^{*}\right)\right\|^{2}-\frac{\sigma}{2}\|\mathbf{x}_{1}-\mathbf{x}^{*}\|^{2}$
$\displaystyle=\sum_{i=1}^{n}\left[\frac{s_{1}+\delta-\sigma\alpha_{1}(1-\beta_{1})}{2\alpha_{1}(1-\beta_{1})}\right](x_{1,i}-x^{*}_{,i})^{2}.$
(25)

By Equation (9), $s_{1}-\sigma\alpha_{1}(1-\beta_{1})\leq 0$ when $t=1$, and
from Equation (A), we obtain the following

$\displaystyle E_{1}^{{}^{\prime\prime}}$
$\displaystyle\leq\sum_{i=1}^{n}\frac{\delta}{2\alpha_{1}(1-\beta_{1})}(x_{1,i}-x^{*}_{,i})^{2}.$
(26)

Moreover, from Assumption 1, we have that $x_{1,i}-x^{*}_{,i}\leq D_{\infty}$.
Then, combining Equations (A), (A) and (26), we finally attain

$\displaystyle E_{1}\leq\sum_{i=1}^{n}\frac{\delta
D_{\infty}^{2}}{2\alpha_{1}(1-\beta_{1})}=\frac{n\delta
D_{\infty}^{2}}{2\alpha(1-\beta_{1})}.$ (27)

Therefore, we have obtained the upper bound of part $E_{1}$. Then we consider
part $E_{2}$ of the remaining two parts in Equation (A). Since
$\beta_{1t}\leq\beta_{1}$, we have the following

$\displaystyle E_{2}$
$\displaystyle\leq\sum_{t=1}^{T}\frac{\alpha_{t}}{2(1-\beta_{1})}\left\|\hat{S}_{t}^{-1/2}\mathbf{m}_{t}\right\|^{2}$
$\displaystyle+\sum_{t=2}^{T}\frac{\beta_{1}\alpha_{t-1}}{2(1-\beta_{1})}\left\|\hat{S}_{t-1}^{-1/2}\mathbf{m}_{t-1}\right\|^{2}.$
(28)

For Equation (A), we first consider the term
$\sum_{t=1}^{T}\alpha_{t}\left\|\hat{S}_{t}^{-1/2}\mathbf{m}_{t}\right\|^{2}$.
Moreover, assuming $0<r\leq s_{t,i}$ where $i\in\\{1,\ldots,n\\}$, we obtain

$\displaystyle\sum_{t=1}^{T}\alpha_{t}\left\|\hat{S}_{t}^{-1/2}\mathbf{m}_{t}\right\|^{2}$
$\displaystyle=\sum_{t=1}^{T-1}\alpha_{t}\left\|\hat{S}_{t}^{-1/2}\mathbf{m}_{t}\right\|^{2}+\alpha_{T}\left\|\hat{S}_{T}^{-1/2}\mathbf{m}_{T}\right\|^{2}$
$\displaystyle\leq\sum_{t=1}^{T-1}\alpha_{t}\left\|\hat{S}_{t}^{-1/2}\mathbf{m}_{t}\right\|^{2}+\underbrace{\alpha_{T}\left(r+\frac{\delta}{T}\right)^{2}\sum_{i=1}^{n}m_{T,i}^{2}}_{E_{2}^{{}^{\prime}}}.$
(29)

Applying the recursive algorithm to (3), and from term $E_{2}^{{}^{\prime}}$
of Equation (A), we have the following

$\displaystyle E_{2}^{{}^{\prime}}$
$\displaystyle=\alpha_{T}\left(r+\frac{\delta}{T}\right)^{2}\sum_{i=1}^{n}\left[\sum_{j=1}^{T}(1-\beta_{1,j})g_{j,i}\prod_{k=1}^{T-j}\beta_{1,(T-k+1)}\right]^{2}$
$\displaystyle\leq\alpha_{T}\left(r+\frac{\delta}{T}\right)^{2}\sum_{i=1}^{n}\left[\sum_{j=1}^{T}g_{j,i}\prod_{k=1}^{T-j}\beta_{1}\right]^{2}$
$\displaystyle\leq\alpha_{T}\left(r+\frac{\delta}{T}\right)^{2}\sum_{i=1}^{n}\left(\sum_{j=1}^{T}\beta_{1}^{T-j}g_{j,i}\right)^{2}.$
(30)

Furthermore, according to Cauchy-Schwarz inequality, i.e.,
$\left(\sum_{k=1}^{n}\langle
a_{k},b_{k}\rangle\right)^{2}\leq\left(\sum_{k=1}^{n}a_{k}^{2}\right)\left(\sum_{k=1}^{n}b_{k}^{2}\right)$,
and from Equation (A), we attain the following

$\displaystyle E_{2}^{{}^{\prime}}$
$\displaystyle\leq\alpha_{T}\left(r+\frac{\delta}{T}\right)^{2}\sum_{i=1}^{n}\left(\sum_{j=1}^{T}\sqrt{\beta_{1}^{T-j}}\sqrt{\beta_{1}^{T-j}}g_{j,i}\right)^{2}$
$\displaystyle\leq\alpha_{T}\left(r+\frac{\delta}{T}\right)^{2}\sum_{i=1}^{n}\left(\sum_{j=1}^{T}\beta_{1}^{T-j}\right)\left(\sum_{j=1}^{T}\beta_{1}^{T-j}g_{j,i}^{2}\right).$
(31)

Applying the sum formula of arithmetic sequence into Equation (A), we have the
following

$\displaystyle E_{2}^{{}^{\prime}}$
$\displaystyle\leq\alpha_{T}\left(r+\frac{\delta}{T}\right)^{2}\sum_{i=1}^{n}\frac{1-\beta_{1}^{T}}{1-\beta_{1}}\left(\sum_{j=1}^{T}\beta_{1}^{T-j}g_{j,i}^{2}\right)$
$\displaystyle\leq\frac{\alpha}{1-\beta_{1}}\left(\frac{r}{\sqrt{T}}+\frac{\delta}{T\sqrt{T}}\right)^{2}\sum_{i=1}^{n}\sum_{j=1}^{T}\beta_{1}^{T-j}g_{j,i}^{2}$
$\displaystyle\leq\frac{2\alpha}{1-\beta_{1}}\left(\frac{r^{2}}{T}+\frac{\delta^{2}}{T^{3}}\right)\sum_{i=1}^{n}\sum_{j=1}^{T}\beta_{1}^{T-j}g_{j,i}^{2}$
$\displaystyle\leq\frac{2\alpha
r^{2}}{1-\beta_{1}}\sum_{i=1}^{n}\sum_{j=1}^{T}\frac{\beta_{1}^{T-j}g_{j,i}^{2}}{T}+\frac{2\alpha\delta^{2}}{1-\beta_{1}}\sum_{i=1}^{n}\sum_{j=1}^{T}\frac{\beta_{1}^{T-j}g_{j,i}^{2}}{T^{3}}.$
(32)

Moreover, plugging Equation (A) into Equation (A), and applying recursive
algorithm, we attain

$\displaystyle\sum_{t=1}^{T}\alpha_{t}\left\|\hat{S}_{t}^{-1/2}\mathbf{m}_{t}\right\|^{2}\leq\sum_{t=1}^{T-1}\alpha_{t}\left\|\hat{S}_{t}^{-1/2}\mathbf{m}_{t}\right\|^{2}$
$\displaystyle+\frac{2\alpha
r^{2}}{1-\beta_{1}}\sum_{i=1}^{n}\sum_{j=1}^{T}\frac{\beta_{1}^{T-j}g_{j,i}^{2}}{T}+\frac{2\alpha\delta^{2}}{1-\beta_{1}}\sum_{i=1}^{n}\sum_{j=1}^{T}\frac{\beta_{1}^{T-j}g_{j,i}^{2}}{T^{3}}$
$\displaystyle\leq\frac{2\alpha
r^{2}}{1-\beta_{1}}\sum_{i=1}^{n}\sum_{t=1}^{T}\sum_{j=1}^{t}\frac{\beta_{1}^{t-j}g_{j,i}^{2}}{t}+\frac{2\alpha\delta^{2}}{1-\beta_{1}}\sum_{i=1}^{n}\sum_{i=1}^{n}\sum_{j=1}^{t}\frac{\beta_{1}^{t-j}g_{j,i}^{2}}{t^{3}}.$
(33)

Furthermore, transforming Equation (A), we obtain

$\displaystyle\sum_{t=1}^{T}\alpha_{t}\left\|\hat{S}_{t}^{-1/2}\mathbf{m}_{t}\right\|^{2}\leq\frac{2\alpha
r^{2}}{1-\beta_{1}}\sum_{i=1}^{n}\sum_{t=1}^{T}g_{t,i}^{2}\sum_{j=t}^{T}\frac{\beta_{1}^{t-j}}{j}$
$\displaystyle+\frac{2\alpha\delta^{2}}{1-\beta_{1}}\sum_{i=1}^{n}\sum_{t=1}^{T}g_{j,i}^{2}\sum_{j=t}^{T}\frac{\beta_{1}^{t-j}}{j^{3}}$
$\displaystyle\leq\frac{2\alpha
r^{2}}{(1-\beta_{1})^{2}}\sum_{i=1}^{n}\sum_{t=1}^{T}g_{t,i}^{2}\sum_{j=t}^{T}\frac{1}{t}$
$\displaystyle+\frac{2\alpha\delta^{2}}{(1-\beta_{1})^{2}}\sum_{i=1}^{n}\sum_{t=1}^{T}g_{j,i}^{2}\sum_{j=t}^{T}\frac{1}{t^{3}}$
$\displaystyle\leq\frac{2\alpha
r^{2}}{(1-\beta_{1})^{2}}\sum_{i=1}^{n}\sum_{t=1}^{T}\frac{g_{t,i}^{2}}{t}+\frac{2\alpha\delta^{2}}{(1-\beta_{1})^{2}}\sum_{i=1}^{n}\sum_{t=1}^{T}\frac{g_{j,i}^{2}}{t^{3}}.$
(34)

In addition, from Cauchy-Schwarz inequality and Equation (A), i.e., $\langle
x,y\rangle\leq\|x\|\|y\|$, we have the following

$\displaystyle\sum_{t=1}^{T}\alpha_{t}\left\|\hat{S}_{t}^{-1/2}\mathbf{m}_{t}\right\|^{2}\leq\frac{2\alpha
r^{2}}{(1-\beta_{1})^{2}}\sum_{i=1}^{n}\sum_{t=1}^{T}\|g_{t,i}^{2}\|\sum_{t=1}^{T}\frac{1}{t}$
$\displaystyle+\frac{2\alpha\delta^{2}}{(1-\beta_{1})^{2}}\sum_{i=1}^{n}\sum_{t=1}^{T}\|g_{t,i}^{2}\|\sum_{t=1}^{T}\frac{1}{t^{3}}$
$\displaystyle\leq\frac{2\alpha
r^{2}}{(1-\beta_{1})^{2}}\sum_{i=1}^{n}\|g_{1:T,i}^{2}\|\sum_{t=1}^{T}\frac{1}{t}$
$\displaystyle+\frac{2\alpha\delta^{2}}{(1-\beta_{1})^{2}}\sum_{i=1}^{n}\|g_{1:T,i}^{2}\|\sum_{t=1}^{T}\frac{1}{t^{3}}.$
(35)

Since $\sum_{t=1}^{T}\frac{1}{t}\leq\log{T}+1$ and
$\sum_{t=1}^{T}\frac{1}{t^{3}}\leq\frac{1}{2}-\frac{1}{2T^{2}}$, we can have
the upper bound of Equation (A) as follows

$\displaystyle\sum_{t=1}^{T}\alpha_{t}\left\|\hat{S}_{t}^{-1/2}\mathbf{m}_{t}\right\|^{2}\leq\frac{2\alpha
r^{2}}{(1-\beta_{1})^{2}}\sum_{i=1}^{n}\|g_{1:T,i}^{2}\|(\log{T}+1)$
$\displaystyle+\frac{2\alpha\delta^{2}}{(1-\beta_{1})^{2}}\sum_{i=1}^{n}\|g_{1:T,i}^{2}\|\left(\frac{1}{2}-\frac{1}{2T^{2}}\right)$
$\displaystyle\leq\frac{2\alpha
r^{2}(\log{T}+1)+\alpha\delta^{2}}{(1-\beta_{1})^{2}}\sum_{i=1}^{n}\|g_{1:T,i}^{2}\|.$
(36)

Then, plugging Equation (A) into Equation (A), we have the following

$\displaystyle E_{2}$ $\displaystyle\leq\frac{2\alpha
r^{2}(\log{T}+1)+\alpha\delta^{2}}{2(1-\beta_{1})^{3}}\sum_{i=1}^{n}\|g_{1:T,i}^{2}\|$
$\displaystyle+\frac{2\alpha\beta_{1}r^{2}(\log{T}+1)+\alpha\beta_{1}\delta^{2}}{2(1-\beta_{1})^{3}}\sum_{i=1}^{n}\|g_{2:T,i}^{2}\|$
$\displaystyle\leq\frac{2\alpha
r^{2}(1+\beta_{1})(\log{T}+1)+\alpha(1+\beta_{1})\delta^{2}}{2(1-\beta_{1})^{3}}\sum_{i=1}^{n}\|g_{1:T,i}^{2}\|$
$\displaystyle-\frac{2\alpha\beta_{1}r^{2}(\log{T}+1)+\alpha\beta_{1}\delta^{2}}{2(1-\beta_{1})^{3}}\sum_{i=1}^{n}\|g_{1,i}^{2}\|$
$\displaystyle\leq\frac{\alpha
r^{2}(\log{T}+1)}{(1-\beta_{1})^{2}}\sum_{i=1}^{n}\|g_{1:T,i}^{2}\|+\frac{\alpha\delta^{2}}{2(1-\beta_{1})^{2}}\sum_{i=1}^{n}\|g_{1:T,i}^{2}\|.$
(37)

Next, we consider the last term $E_{3}$ in Equation (A). From the definition
of $\hat{S}_{t}$ and Assumption 2, we obtain the following

$\displaystyle E_{3}$
$\displaystyle\leq\sum_{t=1}^{T}\frac{t\beta_{1t}}{2\alpha(1-\beta_{1t})}\left\|\left(\mathbf{s}_{t}+\frac{\delta}{t}\right)^{1/2}(\mathbf{x}_{t}-\mathbf{x}^{*})\right\|^{2}$
$\displaystyle\leq\sum_{i=1}^{n}\sum_{t=1}^{T}\frac{t\beta_{1t}}{2\alpha(1-\beta_{1t})}\left\|\left(s_{t,i}+\frac{\delta}{t}\right)^{1/2}(x_{t,i}-x_{,i}^{*})\right\|^{2}$
$\displaystyle\leq\frac{D_{\infty}^{2}(G_{\infty}+\delta)}{2\alpha}\sum_{i=1}^{n}\sum_{t=1}^{T}\frac{\beta_{1t}}{1-\beta_{1t}}t.$
(38)

Finally, combining Equations (A), (27), (A) and (A), we obtain the upper bound
of $R(T)$ as follows

$\displaystyle R(T)\leq$ $\displaystyle\frac{n\delta
D_{\infty}^{2}}{2\alpha(1-\beta_{1})}+\frac{\alpha
r^{2}\log{T}}{(1-\beta_{1})^{2}}\sum_{i=1}^{n}\left\|g_{1:T,i}^{2}\right\|$
$\displaystyle+\frac{2\alpha
r^{2}+\alpha\delta^{2}}{2(1-\beta_{1})^{2}}\sum_{i=1}^{n}\left\|g_{1:T,i}^{2}\right\|$
$\displaystyle+\frac{D_{\infty}^{2}(G_{\infty}+\delta)}{2\alpha}\sum_{i=1}^{n}\sum_{t=1}^{T}\frac{\beta_{1t}}{1-\beta_{1t}}t.$
(39)

Therefore, the proof of Theorem 1 is completed. $\hfill\blacksquare$

Corollary 1 Let $\beta_{1t}=\beta_{1}\lambda^{t}$, where $\lambda\in(0,1)$ in
Theorem 1. Then we have the following upper bound of the regret

$\displaystyle R(T)$ $\displaystyle\leq\frac{n\delta
D_{\infty}^{2}}{2\alpha(1-\beta_{1})}+\frac{\alpha
r^{2}\log{T}}{(1-\beta_{1})^{2}}\sum_{i=1}^{n}\left\|g_{1:T,i}^{2}\right\|$
$\displaystyle+\frac{2\alpha
r^{2}+\alpha\delta^{2}}{2(1-\beta_{1})^{2}}\sum_{i=1}^{n}\left\|g_{1:T,i}^{2}\right\|+\frac{n\beta_{1}\lambda
D_{\infty}^{2}(G_{\infty}+\delta)}{2\alpha(1-\beta_{1})(1-\lambda)^{2}}.$

##### _Proof._

Since $\beta_{1t}=\beta_{1}\lambda^{t}$, Equation (A) can be further bounded
as follows

$\displaystyle E_{3}$
$\displaystyle\leq\frac{\beta_{1}D_{\infty}^{2}(G_{\infty}+\delta)}{2\alpha(1-\beta_{1})}\sum_{i=1}^{n}\sum_{t=1}^{T}t\lambda^{t}$
$\displaystyle\leq\frac{\beta_{1}D_{\infty}^{2}(G_{\infty}+\delta)}{2\alpha(1-\beta_{1})}\sum_{i=1}^{n}\left[\frac{\lambda(1-\lambda^{T})}{(1-\lambda)^{2}}-\frac{T\lambda^{T+1}}{1-\lambda}\right]$
$\displaystyle\leq\frac{\beta_{1}D_{\infty}^{2}(G_{\infty}+\delta)}{2\alpha(1-\beta_{1})}\sum_{i=1}^{n}\frac{\lambda}{(1-\lambda)^{2}}$
$\displaystyle=\frac{n\beta_{1}\lambda
D_{\infty}^{2}(G_{\infty}+\delta)}{2\alpha(1-\beta_{1})(1-\lambda)^{2}}.$ (40)

In addition, plugging Equation (A) into Equation (A), we further attain the
upper bound of $R(T)$ as follows

$\displaystyle R(T)$ $\displaystyle\leq\frac{n\delta
D_{\infty}^{2}}{2\alpha(1-\beta_{1})}+\frac{\alpha
r^{2}\log{T}}{(1-\beta_{1})^{2}}\sum_{i=1}^{n}\left\|g_{1:T,i}^{2}\right\|$
$\displaystyle+\frac{2\alpha
r^{2}+\alpha\delta^{2}}{2(1-\beta_{1})^{2}}\sum_{i=1}^{n}\left\|g_{1:T,i}^{2}\right\|+\frac{n\beta_{1}\lambda
D_{\infty}^{2}(G_{\infty}+\delta)}{2\alpha(1-\beta_{1})(1-\lambda)^{2}}.$ (41)

Therefore, the proof of Corollary 1 is completed. $\hfill\blacksquare$

## Acknowledgment

This work was partially supported by Chinese Academy of Sciences (No.
Y9BEJ11001).

## References

  * [1] Huang, K., Zhang, S., Zhang, R., and Hussain, A. “Pattern Field Classification Using Deep Neural Networks," _Neural Networks_ , vol. 127, pp. 82-95, 2020.
  * [2] Jiang, Y., Wu, D., Deng, Z., etc. “Seizure Classification From EEG Signals Using Transfer Learning, Semi-Supervised Learning and TSK Fuzzy System," _IEEE Transactions on Neural Systems and Rehabilitation Engineering_ , vol. 25, no. 12, pp. 2270-2284, 2017 Dec.
  * [3] Wang, J., Hu, J., Min, G., Zomaya, A. Y., and Georgalas, N. “Fast Adaptive Task Offloading in Edge Computing Based on Meta Reinforcement Learning," _IEEE Transactions on Parallel and Distributed Systems_ , vol. 32, no. 1, pp. 242-253, 2021 Jan.
  * [4] Karabayir, I., Akbilgic, O., and Tas, N. “A Novel Learning Algorithm to Optimize Deep Neural Networks: Evolved Gradient Direction Optimizer (EVGO)," _IEEE Transactions on Neural Networks and Learning Systems_ , vol. 32, no. 2, pp. 685-694, 2021 Feb.
  * [5] Li, J., Ding, J., Chai, T., and Lewis, F. L. “Nonzero-Sum Game Reinforcement Learning for Performance Optimization in Large-Scale Industrial Processes," _IEEE Transactions on Cybernetics_ , vol. 50, no. 9, pp. 4132-4145, 2020 Sept.
  * [6] Jin, X., Zhang, X., Huang, K., Geng, G. “Stochastic Conjugate Gradient Algorithm with Variance Reduction," _IEEE Transactions on Neural Networks and Learning Systems_ , vol. 30, no. 5, pp. 1360-1369, 2019.
  * [7] Jia, X., Li, Z., Zheng, X., Li, W., and Huang, S. J. “Label Distribution Learning with Label Correlations on Local Samples," _IEEE Transactions on Knowledge and Data Engineering_ , vol. 33, no. 4, pp. 1619-1631, 2021 April.
  * [8] Niu, S., Li, B., Wang, X., and Lin, H. “efect Image Sample Generation With GAN for Improving Defect Recognition," _IEEE Transactions on Automation Science and Engineering_ , vol. 17, no. 3, pp. 1611-1622, 2020 July.
  * [9] Khan, M., Nielsen, D., Tangkaratt, V., Lin, W., Gal, Y. “Fast and Scalable Bayesian Deep Learning by Weight-Perturbation in Adam," in _International Conference on Machine Learning_ , 2018, vol. 80, pp. 2611-2620.
  * [10] Mukkamala, M. C. and Hein, M. “Variants of RMSProp and Adagrad with Logarithmic Regret Bounds," in International Conference on Machine Learning, 2017, vol. 70, pp. 2545-2553.
  * [11] Zhou, Y., Zhang, M., Zhu, J., Zheng, R., Wu, Q. “A Randomized Block-Coordinate Adam online learning optimization algorithm," _Neural Computing and Applications_ , vol. 32, pp. 12671-1268, 2020 Aug.
  * [12] Zinkevich, M. “Online convex programming and generalized infinitesimal gradient ascent," in _International Conference on Machine Learning_ , 2003, pp. 928-936.
  * [13] Lei, Y., Hu, T., Li, G., and Tang, K. “tochastic Gradient Descent for Nonconvex Learning Without Bounded Gradient Assumptions," _IEEE Transactions on Neural Networks and Learning Systems_ , vol. 31, no. 10, pp. 4394-4400, 2020 Oct.
  * [14] Gu, B., Shan, Y., Quan, X., and Zheng, G. “ccelerating Sequential Minimal Optimization via Stochastic Subgradient Descent," _IEEE Transactions on Cybernetics_ , vol. 51, no. 4, pp. 2215-2223, 2021 April.
  * [15] Sutskever, I., Martens, J., Dahl, G., and Hinton, G. “On the importance of initialization and momentum in deep learning," in _International conference on machine learning_ , 2013, pp. 1139-1147.
  * [16] Nesterov, Y. “A method of solving a convex programming problem with convergence rate $o(1/k^{2})$," in _Soviet Mathematics Doklady_ , 1983, vol. 27.
  * [17] Kingma, D.P. and Ba, J.L. “Adam: A method for stochastic optimization," in _International Conference on Learning Representations_ , 2015.
  * [18] Reddi, S. J., Kale, S., and Kumar, S. “On the convergence of adam and beyond," in _International Conference on Learning Representations_ , 2018.
  * [19] Luo, L., Xiong, Y., Liu, Y., Sun, X. “Adaptive gradient methods with dynamic bound of learning rate," in _International Conference on Learning Representations_ , 2019.
  * [20] Zaheer, M., Reddi, S., Sachan, D., Kale, S., and Kumar, S. “Adaptive methods for nonconvex optimization," in _Neural Information Processing Systems_ , 2018, pp. 9793-9803.
  * [21] Liu, L., Jiang, H., He, P., Chen, W., Liu, X., Gao, J., and Han, J. “On the variance of the adaptive learning rate and beyond," in _International Conference on Learning Representations_ , 2020.
  * [22] Balles, L. and Hennig, P. “Dissecting adam: The sign, magnitude and variance of stochastic gradients," in _International Conference on Machine Learning_ , 2018.
  * [23] Loshchilov, I. and Hutter, F. “Decoupled weight decay regularization," in _International Conference on Learning Representations_ , 2019.
  * [24] Zhuang, J., Tang, T., Ding, Y., Takiconda, S., Dvornek, N., Papademetris, X., and Duncan, J. “AdaBelief Optimizer: Adapting Stepsizes by the Belief in Observed Gradients," in _Neural Information Processing Systems_ , 2020.
  * [25] Wang, G., Lu, S., Tu, W., and Zhang, L. “SAdam: A Variant of Adam for Strongly Convex Functions," in _International Conference on Learning Representations_ , 2020.
  * [26] Shalev-Shwartz, S. “Online Learning and Online Convex Optimization," _Foundations & Trends in Machine Learning_, vol. 4, no. 2, pp. 107-194, 2011.
  * [27] Shai, S. and Yoram, S. “A primal-dual perspective of online learning algorithms," _Machine Learning_ , vol. 69, pp. 115-142, 2007.
  * [28] Joseph, A. and Bhatnagar, S. “An online prediction algorithm for reinforcement learning with linear function approximation using cross entropy method," _Machine Learning_ , vol. 107, pp. 1385-1429, 2018
  * [29] Boyd, S. and Vandenberghe, L. “Convex optimization," _Cambridge university press_ , 2004.
  * [30] McMahan, B. H. and Streeter, M. “Adaptive bound optimization for online convex optimization," arXiv preprint arXiv:1002.4908, 2010.
  * [31] Liu, W., Wen, Y., Yu, Z., and Yang, M. “Large-Margin Softmax Loss for Convolutional Neural Networks," in _Proceedings of The 33rd International Conference on Machine Learning_ , PMLR, vol. 48, pp. 507-516, 2016.
  * [32] Martins, A. and Astudillo, R. “From Softmax to Sparsemax: A Sparse Model of Attention and Multi-Label Classification," in _Proceedings of The 33rd International Conference on Machine Learning_ , PMLR, vol. 48, pp. 1614-1623, 2016.
  * [33] He, K., Zhang, X., Ren, S., and Sun, J. “Deep residual learning for image recognition," in _IEEE conference on computer vision and pattern recognition_ , 2016, pp. 770-778.
  * [34] Huang, G., Liu, Z., Maaten, L. V. D., and Weinberger, K., Q. “Densely connected convolutional networks," in _IEEE conference on computer vision and pattern recognition_ , 2017, pp. 4700-4708.
  * [35] Shuang, K., Li, R.,Gu, M.,Loo, J., and Su, S. “Major-Minor Long Short-Term Memory for Word-Level Language Model," in _IEEE Transactions on Neural Networks and Learning Systems_ , vol. 31, no. 10, pp. 3932-3946, Oct. 2020.
  * [36] Huang, S. and Renals, S. “Hierarchical Bayesian Language Models for Conversational Speech Recognition," in _IEEE Transactions on Audio, Speech, and Language Processing_ , vol. 18, no. 8, pp. 1941-1954, Nov. 2010.


# Counting subtrees of the branching process tree by the number of leaves

Boris Pittel  Department of Mathematics, Ohio State University, 231 West 18-th
Avenue, Columbus OH 43210-1175<EMAIL_ADDRESS>
###### Abstract.

We study the distribution of the number of leaves of the subtree chosen
uniformly at random among all the subtrees of the critical branching process
tree at extinction.

###### Key words and phrases:

Branching process, random tree, extinction, asymptotics

###### 1991 Mathematics Subject Classification:

60C05; 05C05, 92B10

##  1\. Introduction and results

Consider a branching process initiated by a single progenitor. This process is
visualized as a growing rooted tree. The root is the progenitor, connected by
edges to each of its immediate descendants (children), that are ordered, say
by seniority. Each of the children becomes the root of the corresponding
subtree, so that the children of all these roots are the grandchildren of the
progenitor. We obviously get a recursively defined process. It delivers a
nested sequence of trees, which is either infinite, or terminates at a moment
when none of the current leaves have children.

The classic Galton-Watson branching process is the case when the number of
each member’s children (a) is independent of those numbers for all members
from the preceding and current generations and (b) has the same distribution
$\\{p_{j}\\}_{j\geq 0}$, $(\sum_{j}p_{j}=1)$. It is well-known that if
$p_{0}>0$ and $\sum_{j\geq 0}jp_{j}=1$, then the process terminates with
probability $1$, Harris [7]. A standard example is $p_{0}=p_{2}=\tfrac{1}{2}$,
in which case we have a binary tree.

Let $T$ denote the terminal tree. Given a finite rooted tree $\mathcal{T}$, we
have

$\mathbb{P}(T=\mathcal{T})=\prod_{v\in\mathcal{V}(\mathcal{T})}p_{d(v,\mathcal{T})},$

where $\mathcal{V}(\mathcal{T})$ is the vertex set of $\mathcal{T}$, and
$d(v,\mathcal{T})$ is the out-degree of vertex $v\in V(\mathcal{T})$.
Introduce $L=L_{T}$ the total number of leaves of $T$, i.e. vertices of $T$
with out-degree $0$, and $X(t)=X_{T}(t)$ the total number of the (full)
subtrees of $T$ with $t$ leaves. So, the total number of subtrees $\sum_{t\geq
1}X(t)=V(T)=|\mathcal{V}(T)|$. Introduce $\mathcal{L}=\mathcal{L}(T)$, the
number of leaves in the subtree chosen uniformly at random among all $V=V(T)$
subtrees of $T$; so, conditionally on $T$, we have
$\mathbb{P}(\mathcal{L}=t|T)=\tfrac{X(t)}{V}$, and–conditionally on $L$
only–$\mathbb{P}(\mathcal{L}=t|L)=\mathbb{E}\bigl{[}\tfrac{X(t)}{V}|L\bigr{]}$.
It was proved in [15] that $f(x):=\mathbb{E}[x^{L}]=\sum_{k\geq
1}x^{k}\mathbb{P}(L=k)$ satisfies

(1.1) $f(x)=\sum_{j\geq 1}p_{j}f^{j}(x)+p_{0}x,\quad|x|\leq 1.$

Also $\mathbb{P}(L<\infty)=1$, and assuming that $\\{p_{j}\\}$ has a finite
variance $\sigma^{2}$,

(1.2)
$\mathbb{P}(L=\ell)=\tfrac{\gamma(2\ell-1)!!}{2^{\ell}\ell!}+O(\ell^{-2})=\tfrac{\gamma}{\ell^{3/2}}+O(\ell^{-2}),\quad\gamma:=\bigl{(}\tfrac{p_{0}}{2\pi\sigma^{2}}\bigr{)}^{1/2},$

$\sigma^{2}$ being the variance of $\\{p_{j}\\}$. (To be sure, we were
interested in the case $p_{1}=0$, but (1.2) holds for all $p_{1}<1$ as well.)
A less sharp formula $\mathbb{P}(L=\ell)=\tfrac{\gamma}{\ell^{3/2}}(1+o(1))$
has long been known, Kolchin [11] (Ch. 2, Lemma 4).

######  Theorem 1.1.

(i) For the binary case $p_{0}=p_{2}=1/2$,

$\mathbb{P}(\mathcal{L}=t|L=\ell)=\tfrac{t}{\ell(2\ell-1)}\cdot\tfrac{\binom{\ell}{t}^{2}}{\binom{2(\ell-1)}{2(t-1)}}.$

(ii) Consequently, for $t=o(\ell)$ we have

$\mathbb{P}(\mathcal{L}=t|L=\ell)=\tfrac{1+O(\ell^{-1/2}+t/\ell)}{2^{2t-1}t}\binom{2(t-1)}{t-1}\\!=\\!(1+O(\ell^{-1/2}+t/\ell))\mathbb{P}(L=t),$

implying tightness of the sequence of distributions
$\\{\mathbb{P}(\mathcal{L}=t|L=\ell)\\}_{t\geq 1}$. However,
$\mathbb{E}[\mathcal{L}|L=\ell]\sim\tfrac{\sqrt{\pi\ell}}{2}$, as
$\ell\to\infty$.

Note. So, for large $\ell$, the number of leaves in the subtree chosen at
random from all $(2\ell-1)$ subtrees of the extinction tree with $\ell$
leaves, is distributed asymptotically as the number of leaves in the
extinction tree.

Our second result is for a general critical distribution $\\{p_{j}\\}_{j\geq
0}$.

######  Theorem 1.2.

(i) For each fixed $t\geq 1$,

$\lim_{\ell\to\infty}\mathbb{P}(\mathcal{L}=t|L=\ell)=(1-p_{1})\mathbb{P}(L=t).$

Since $\sum_{t\geq 1}\mathbb{P}(L=t)=1$, we see that the sequence of the
distributions $\\{\mathbb{P}(\mathcal{L}=t|L=\ell)\\}_{1\leq t\leq\ell}$,
$(\ell\geq 1)$, is not tight, unless (like in the binary case) $\,p_{1}=0$. In
words, $p_{1}$ is the limiting deficit of the leaf-set size distribution for
the random subtree. (ii) More precisely,

$\mathbb{P}\Bigl{(}\mathcal{L}>\tfrac{\ell^{1/2}}{\log^{2}\ell}\Big{|}L=\ell\Bigr{)}=p_{1}+O(\ell^{-1/4}\log\ell),$

so that, conditioned on $\\{L=\ell\\}$, $\mathcal{L}$ exceeds
$\tfrac{\ell^{1/2}}{\log^{2}\ell}$ with conditional probability bounded away
from zero as $\ell\to\infty$.

Note. Since $p_{1}<1$, the equation (1.1) is equivalent to

$f(x)=\sum_{j\geq 2}p_{j}^{\prime}f^{j}(x)+p_{0}^{\prime}x,\quad
p_{j}^{\prime}=\tfrac{p_{j}}{1-p_{1}},\,\,j=0,2,3,\dots,$

and $p_{0}^{\prime},p_{2}^{\prime},p_{3}^{\prime},\dots$ is a probability
distribution, with $\sum_{j}jp_{j}^{\prime}=1$ again, but with
$p_{1}^{\prime}=0$. Therefore $L$ and $L^{\prime}$, the number of leaves in
the terminal tree $T^{\prime}$ associated with $\\{p_{j}^{\prime}\\}$, are
equidistributed. So, the part (i) can be interpreted as saying that,
conditioned on the event “no father has a single child”, the uniformly random
subtree of $T$, in the limit, has the number of leaves distributed as that for
the tree $T^{\prime}$.

As a source for our inspiration, we should mention the Russian mathematician
Valentin Kolchin who pioneered and championed the study of connection between
conditiional branching processes and combinatorics of random trees since the
mid-seventies, Kolchin [9], [10], and [11]. We refer the reader to David
Aldous [1] and Svante Janson [8] for two, $20$ years apart, encyclopedic
surveys of limit results for the conditioned and the simply generated trees,
without convergence rates, that analyze a rich variety of fringe
distributions. The distribution of random subtree size is listed in [1] as one
of the basic problems in this class of distributions.

##  2\. Generating functions identities

Here are two useful identities that follow from implicit differentiation of
(1.1) for $f(x)$:

(2.1) $\sum_{j\geq
1}jp_{j}f^{j-1}(x)=1-\tfrac{p_{0}}{f^{\prime}(x)},\quad\sum_{j\geq
1}j(j-1)p_{j}f^{j-2}(x)=\tfrac{p_{0}f^{{}^{\prime\prime}}(x)}{(f^{\prime}(x)^{3}}.$

In particular, since $f(0)=0$, we have $f^{\prime}(0)=\tfrac{p_{0}}{1-p_{1}}$.

Our first task is to derive an equation for
$f(\ell,t)=\mathbb{E}[X(t)\mathbb{I}(L=\ell)]$, where $\mathbb{I}(B)$ stands
for the indicator of an event $B$. Of course, $f(\ell,t)=0$ for $\ell<t$, and
$f(t,t)=\mathbb{P}(L=t)$. Consider $\ell>t$. With probability $p_{j}$ the root
has $j$ children; let $X_{i}(t)$ denote the number of subtrees with $t$ leaves
in the tree rooted at the $i$-th child. Then

$f(\ell,t)=\mathbb{E}\bigl{[}X(t)\mathbb{I}(L=\ell)\bigr{]}=\sum_{j\geq
1}p_{j}\mathbb{E}\biggl{[}\Bigl{(}\sum_{i\in[j]}X_{i}(t)\Bigr{)}\cdot\mathbb{I}\Bigl{(}\sum_{i^{\prime}\in[j]}L_{i^{\prime}}=\ell\Bigr{)}\biggl{]}\\\
=\sum_{j\geq
1}jp_{j}\mathbb{E}\biggl{[}X_{1}(t)\cdot\mathbb{I}\Bigl{(}\sum_{i\in[j]}L_{i}=\ell\Bigr{)}\biggl{]}\\\
=\sum_{j\geq
1}jp_{j}\sum_{\mu\leq\ell}\mathbb{E}\bigl{[}X(t)\mathbb{I}(L=\mu)\bigr{]}\cdot\mathbb{P}\Bigl{(}\sum_{i\in[j]\setminus\\{1\\}}L_{i}=\ell-\mu\Bigr{)}\\\
=\sum_{j\geq
1}jp_{j}\sum_{\mu\leq\ell}f(\mu,t)\cdot[x^{\ell-\mu}]f^{j-1}(x)\\\
=\sum_{\mu\leq\ell}f(\mu,t)\bigl{[}x^{\ell-\mu}\bigr{]}\sum_{j\geq
1}jp_{j}f^{j-1}(x).$

So, in combination with (2.1), we obtain

(2.2)
$f(\ell,t)=\sum_{\mu\leq\ell}f(\mu,t)\cdot\bigl{[}x^{\ell-\mu}\bigr{]}\bigl{(}1-\tfrac{p_{0}}{f^{\prime}(x)}\bigr{)},\quad\ell>t.$

And we remind that $f(t,t)=\mathbb{P}(L=t)$. The convolution on the RHS of
(2.2) positively dictates usage of generating functions. For $|y|<1$, using
$f^{\prime}(0)=\tfrac{p_{0}}{1-p_{1}}$, we have

$\sum_{\ell\geq
t}y^{\ell}f(\ell,t)=y^{t}\,\mathbb{P}(L=t)-y^{t}\,\mathbb{P}(L=t)\cdot[x^{0}]\bigl{(}1-\tfrac{p_{0}}{f^{\prime}(x)}\bigr{)}\\\
+\sum_{\ell\geq
t}y^{\ell}\sum_{\mu=t}^{\ell}f(\mu,t)\cdot[x^{\ell-\mu}]\bigl{(}1-\tfrac{p_{0}}{f^{\prime}(x)}\bigr{)}\\\
=(1-p_{1})y^{t}\,\mathbb{P}(L=t)+\sum_{\mu\geq
t}f(\mu,t)y^{\mu}\sum_{\ell\geq\mu}y^{\ell-\mu}\cdot[x^{\ell-\mu}]\bigl{(}1-\tfrac{p_{0}}{f^{\prime}(x)}\bigr{)}\\\
=(1-p_{1})y^{t}\,\mathbb{P}(L=t)+\bigl{(}1-\tfrac{p_{0}}{f^{\prime}(y)}\bigr{)}\sum_{\mu\geq
t}f(\mu,t)y^{\mu},\\\ $

implying that

(2.3) $\sum_{\ell\geq
t}y^{\ell}f(\ell,t)=\tfrac{1-p_{1}}{p_{0}}y^{t}f^{\prime}(y)\,\mathbb{P}(L=t).$

Recalling that $f(\ell,t)=f(\ell,t)=\mathbb{E}[X(t)\mathbb{I}(L=\ell)]$, and
using $[y^{s}]f^{\prime}(y)=(s+1)\cdot[y^{s+1}]f(y)$, we arrive at

######  Lemma 2.1.

$\displaystyle\mathbb{E}[X(t)|L=\ell]$
$\displaystyle=\tfrac{1-p_{1}}{p_{0}}\tfrac{[y^{\ell-t}]f^{\prime}(y)\times\mathbb{P}(L=t)}{\mathbb{P}(L=\ell)}=\tfrac{1-p_{1}}{p_{0}}\,\tfrac{(\ell-t+1)\mathbb{P}(L=\ell-t+1)\,\mathbb{P}(L=t)}{\mathbb{P}(L=\ell)}.$

##  3\. Proof of Theorem 1.1

Notice that $V=2\ell-1$ on the event $\\{L=\ell\\}$ for the binary case.

###### Proof.

By Lemma 2.1 (first identity), with a bit of elementary work, we have

$\mathbb{P}(\mathcal{L}=t|L=\ell)=\tfrac{1}{2\ell-1}\mathbb{E}[X(t)|L=\ell]=\tfrac{2}{2\ell-1}\tfrac{[y^{\ell-t}]f^{\prime}(y)\times[x^{t}]f(x)}{[x^{\ell}]f(x)}\\\
=\tfrac{1}{2\ell-1}\cdot\tfrac{[y^{\ell-t}](1-y)^{-1/2}\times[x^{t}](-(1-x)^{1/2})}{[x^{\ell}](-(1-x)^{1/2})}=\tfrac{t}{\ell(2\ell-1)}\cdot\tfrac{\binom{\ell}{t}^{2}}{\binom{2(\ell-1)}{2(t-1)}}.$

The asymptotic formula
$\mathbb{E}[\mathcal{L}|L=\ell]\sim\tfrac{\sqrt{\pi\ell}}{2}$ follows easily
from

$t\cdot\mathbb{P}(\mathcal{L}=t|L=\ell)=\tfrac{\ell}{2\ell-1}\tfrac{\binom{2(t-1)}{t-1}\binom{2(\ell-t)}{\ell-t}}{\binom{2(\ell-1)}{\ell-1}},$

the formula $\binom{2m}{m}\sim\tfrac{2^{2m}}{\sqrt{\pi m}}$, $(m\to\infty)$,
and $\int_{0}^{1}\tfrac{dx}{\sqrt{x(1-x)}}=\pi$. Finally, by (1.2) and the
second identity in Lemma 2.1, we have

$\mathbb{P}(\mathcal{L}=t|L=\ell)=\tfrac{1}{2\ell-1}\mathbb{E}[X(t)|L=\ell]\\\
=\tfrac{2(\ell-t+1)(\ell-t+1)^{-3/2}}{(2\ell-1)\ell^{-3/2}}\cdot\bigl{(}1+O((\ell-t+1)^{-1/2})\bigr{)}\mathbb{P}(L=t)\\\
=(1+O(\ell^{-1/2}+t/\ell))\mathbb{P}(L=t),$

provided that $t=o(\ell)$. ∎

##  4\. Proof of Theorem 1.2

For a general $\\{p_{j}\\}_{j\geq 0}$ with $p_{0}>0$, $\sum_{j}jp_{j}=1$,
$V=\sum_{s}X(s)$ is random on the event $\\{L=\ell\\}$, i.e. the number of the
subtrees of the extinction tree to choose from is random. So, here
$\mathbb{P}(\mathcal{L}=t|L=\ell)=\mathbb{E}\bigl{[}\tfrac{X(t)}{V}\big{|}L=\ell\bigr{]}.$
The ratios of dependent random variables can be problematic for evaluation,
precise or even asymptotic, of their moments. Fortunately, here we hope that,
for $\ell$ large, conditionally on $\\{L=\ell\\}$, the distribution of $V$ is
sharply concentrated around $\mathbb{E}[V|L=\ell]$. If so, we can expect that
for large $\ell$,
$\mathbb{P}(\mathcal{L}=t|L=\ell)\sim\tfrac{\mathbb{E}[X(t)|L=\ell]}{\mathbb{E}[V|L=\ell]}$
for a wide range of $t<\ell$. And the last fraction is perfectly amenable to
asymptotic analysis.

To prove concentration, let us introduce
$g(y,\ell)=\mathbb{E}[y^{V}\mathbb{I}(L=\ell)]$, $(\ell\geq 1)$, so that
$g(y,1)=p_{0}y$, and define $G(y,x):=\sum_{\ell\geq 1}x^{\ell}g(y,\ell)$. For
$\ell>1$, we have

$g(y,\ell)=y\sum_{j\geq
1}p_{j}\sum_{\ell_{1}+\cdots+\ell_{j}=\ell}\,\prod_{i\in[j]}g(y,\ell_{i})=[x^{\ell}]\,y\sum_{j\geq
1}p_{j}G^{j}(y,x).$

Consequently

(4.1) $G(y,x)=p_{0}yx+y\sum_{j\geq 1}p_{j}G^{j}(y,x).$

We use (4.1) to get $G^{\prime}_{y}(1,x)$ and
$G^{{}^{\prime\prime}}_{y}(1,x)$, since

(4.2) $\displaystyle G^{\prime}_{y}(1,x)$
$\displaystyle=\mathbb{E}[Vx^{L}]\Longrightarrow\mathbb{E}[V\mathbb{I}(L=\ell)]=[x^{\ell}]G^{\prime}_{y}(1,x),$
$\displaystyle G^{{}^{\prime\prime}}_{y}(1,x)$
$\displaystyle=\mathbb{E}[V(V-1)x^{L}]\Longrightarrow\mathbb{E}[V(V-1)\mathbb{I}(L=\ell)]=[x^{\ell}]G^{{}^{\prime\prime}}_{y}(1,x).$

We have

$\displaystyle G(1,x)$ $\displaystyle=\sum_{\ell\geq
1}x^{\ell}g(1,\ell)=\sum_{\ell\geq 1}x^{\ell}\mathbb{P}(L=\ell)=f(x),$
$\displaystyle G^{\prime}_{y}(1,x)$ $\displaystyle=\biggl{(}p_{0}x+\sum_{j\geq
1}p_{j}G^{j}(y,x)+y\sum_{j\geq
1}jp_{j}G^{j-1}(y,x)G^{\prime}_{y}(y,x)\Biggr{)}\Big{|}_{y=1}$
$\displaystyle=f(x)+\biggl{(}\sum_{j\geq
1}jp_{j}f^{j-1}(x)\biggr{)}G_{y}^{\prime}(1,x),$ $\displaystyle
G^{{}^{\prime\prime}}_{y}(1,x)$ $\displaystyle=\biggl{(}2\sum_{j\geq
1}jp_{j}G^{j-1}(y,x)G^{\prime}_{y}(y,x)$ $\displaystyle+y\sum_{j\geq
1}jp_{j}\bigl{[}(j-1)G^{j-2}(y,x)(G^{\prime}_{y}(y,x))^{2}+G^{j-1}(y,x)G^{{}^{\prime\prime}}_{y}(y,x)\bigr{]}\biggr{)}\Big{|}_{y=1}$
$\displaystyle=2G^{\prime}_{y}(1,x)\sum_{j\geq 1}jp_{j}f^{j-1}(x)$
$\displaystyle+(G^{\prime}_{y}(1,x))^{2}\sum_{j\geq
1}j(j-1)p_{j}f^{j-2}(x)+G^{{}^{\prime\prime}}_{y}(1,x)\sum_{j\geq
1}jp_{j}f^{j-1}(x).$

Therefore

(4.3) $\displaystyle G^{\prime}_{y}(1,x)$
$\displaystyle=\tfrac{f(x)}{1-\sum_{j}jp_{j}f^{j-1}(x)},$ $\displaystyle
G^{{}^{\prime\prime}}_{y}(1,x)$
$\displaystyle=\tfrac{\sum_{j}j(j-1)p_{j}f^{j}(x)}{\biggl{(}1-\sum_{j}jp_{j}f^{j-1}(x)\biggr{)}^{3}}+\tfrac{2\biggl{(}\sum_{j}jp_{j}f^{j}(x)\biggr{)}}{\biggl{(}1-\sum_{j}jp_{j}f^{j-1}(x)\biggr{)}^{2}}.$

So, combining (4.2), (4.3), and (2.1), we conclude that

(4.4) $\displaystyle\mathbb{E}[V\mathbb{I}(L=\ell)]$
$\displaystyle=[x^{\ell}]\tfrac{f(x)f^{\prime}(x)}{p_{0}},$
$\displaystyle\mathbb{E}[V(V-1)\mathbb{I}(L=\ell)]$
$\displaystyle=\tfrac{1}{p_{0}^{2}}\cdot[x^{\ell}]\bigl{(}f^{{}^{\prime\prime}}(x)f^{2}(x)\bigr{)},$
$\displaystyle\quad+2\cdot[x^{\ell}]\bigl{(}\tfrac{(f^{\prime}(x))^{2}f(x)}{p_{0}^{2}}-\tfrac{f^{\prime}(x)f(x)}{p_{0}}\bigr{)}.$

Let us evaluate these expectations. Time for some complex analysis. Using
Weierstrass preparation theorem, (see Ebeling [4], Krantz and Parks [12]) we
proved In [15] that $f(z)=\sum_{k\geq 1}z^{k}\,\mathbb{P}(L=k)$,
$z\in\mathbb{C}$, $|z|<1$, admits an analytic extension $F(z)$ to an open disc
$D$ centered at the origin, of radius $\rho>1$, minus a cut $[1,\rho)$ such
that, for $z\in D\setminus[1,\rho)$, $z\to 1$,

(4.5)
$F(z)=1-\gamma(1-z)^{1/2}+\sum_{s>1}\gamma_{s}(1-z)^{s/2},\,\,\gamma:=(2p_{0})^{1/2}\sigma^{-1}.$

Here $\xi^{1/2}:=|\xi|^{1/2}\exp(i\text{Arg}(\xi)/2)$,
$\text{Arg}(\xi)\in(-\pi,\pi)$. So, ever so slightly above the cut
$\\{z=x,x\in[1,\rho)\\}$, we have
$(1-z)^{1/2}=|1-z|^{1/2}e^{-i\pi/2}=-i|1-x|^{1/2}$. (We encourage the
interested reader to check Bender [2], Canfield [3], Meir and Moon [13], [14]
and Flajolet and Sedgewick [5], for a remarkable story of how classic complex
analysis techniques found their way into analytic combinatorics.)

Since $\tfrac{F(z)F^{\prime}(z)}{z^{\ell+1}}$ is integrable on the circular
contour $\mathcal{C}_{r}=\\{z=re^{i\theta},\,\theta\in(-\pi,\pi]\\}$, $r=1$,
we use the Cauchy integral theorem to write

$[x^{\ell}]\bigl{(}f(x)f^{\prime}(x)\bigr{)}=\tfrac{1}{2\pi
i}\oint_{\mathcal{C}_{1}}\tfrac{F(z)F^{\prime}(z)}{z^{\ell+1}}\,dz\\\
=\tfrac{1}{2\pi
i}\oint_{\mathcal{C}_{\rho}}\tfrac{F(z)F^{\prime}(z)}{z^{\ell+1}}+\tfrac{1}{2\pi
i}\int_{1}^{\rho}\tfrac{2i\,\text{Im}(F(x)F^{\prime}(x))}{x^{\ell+1}}\,dx.$

For the second line we replaced $\mathcal{C}_{1}$ with the limit contour. It
consists of the directed circle $z=\rho e^{i\alpha}$, $0\leq a\leq 2\pi$ with
the single point $z=\rho$ pinched out, and a detour part formed by two
opposite-directed line segments, one from $z=\rho e^{i(2\pi-0)}$ to
$z=e^{i(2\pi-0)}$, and another from $z^{i(+0)}$ to $z=\rho^{i(+0)}$. The
$2i\,\text{Im}(F(x)F^{\prime}(x))$ appears because the values of
$F(x)F^{\prime}(x)$ just above and just below $[1,\rho)$ are complex-
conjugate, so the real parts cancel each other, and
$\text{Im}(F(x)F^{\prime}(x))$ comes from $z$’s approaching $x\in[1,\rho)$
from above. The first integral at the bottom is of order $O(\rho^{-\ell})$.
Further, using (4.5) and the formula 3.191(2) from Gradschteyn and Ryzik [6],
we get

$\tfrac{1}{2\pi
i}\int_{1}^{\rho}\tfrac{2i\,\text{Im}(F(x)F^{\prime}(x))}{x^{\ell+1}}\,dx=\tfrac{\gamma}{2\pi}\int_{1}^{\rho}\tfrac{(x-1)^{-1/2}+O(1)}{x^{\ell+1}}\,dx\\\
=\tfrac{\gamma}{2\pi}\int_{1}^{\infty}\tfrac{(x-1)^{-1/2}}{x^{\ell+1}}\,dx+O(1/\ell)=\tfrac{\gamma(2\ell-1)!!}{2^{\ell+1}\ell!}+O(1/\ell);\\\
$

the explicit term is of order $\ell^{-1/2}$ exactly. Therefore

(4.6)
$\mathbb{E}[V\mathbb{I}(L=\ell)]=\tfrac{\gamma(2\ell-1)!!}{p_{0}2^{\ell+1}\ell!}+O(1/\ell).$

Now, by (1.2), we have
$\mathbb{P}(L=\ell)=\tfrac{\gamma(2\ell-3)!!}{2^{\ell}\ell!}+O(\ell^{-2})$.
This and (4.6) imply that

(4.7)
$\mathbb{E}[V|L=\ell]=\tfrac{\mathbb{E}[V\mathbb{I}(L=\ell)]}{\mathbb{P}(L=\ell)]}=\tfrac{\ell}{p_{0}}+O(\ell^{1/2}).$

Turn to the second identity in (4.4). Similarly to the above computation, we
obtain

$\displaystyle\tfrac{1}{p_{0}^{2}}\cdot[x^{\ell}]\bigl{(}f^{{}^{\prime\prime}}(x)f^{2}(x)\bigr{)}=\tfrac{\gamma(2\ell+1)!!}{(2p_{0})^{2}2^{\ell}\ell!}+O(1),$
$\displaystyle
2\cdot[x^{\ell}]\bigl{(}\tfrac{(f^{\prime}(x))^{2}f(x)}{p_{0}^{2}}-\tfrac{f^{\prime}(x)f(x)}{p_{0}}\bigr{)}=O(1),$
$\displaystyle\Longrightarrow\,$
$\displaystyle\mathbb{E}[V(V-1)\mathbb{I}(L=\ell)]=\tfrac{\gamma(2\ell+1)!!}{(2p_{0})^{2}2^{\ell}\ell!}+O(1),$
$\displaystyle\Longrightarrow\,$
$\displaystyle\mathbb{E}[V^{2}\mathbb{I}(L=\ell)]=\tfrac{\gamma(2\ell+1)!!}{(2p_{0})^{2}2^{\ell}\ell!}+O(1),$
(4.8) $\displaystyle\Longrightarrow\,$
$\displaystyle\mathbb{E}[V^{2}|L=\ell]=\bigl{(}\tfrac{\ell}{p_{0}}\bigr{)}^{2}+O(\ell^{3/2}).$

Putting (4.7) and (4.8), we conclude that

(4.9) $\displaystyle\text{var}(V|L=\ell)$
$\displaystyle:=\mathbb{E}\bigl{[}(V-\mathbb{E}[V|L=\ell])^{2}|L=\ell\bigr{]}$
$\displaystyle=\mathbb{E}[V^{2}|L=\ell]-\mathbb{E}^{2}[V|L=\ell]=O(\ell^{3/2}).$

Recall that $V$ is the number of vertices in the terminal tree $T$, and $X(t)$
is the number of vertices whose descendant tree has $t$ leaves. Thus
$\\{\tfrac{X(t)}{V}\\}_{t\geq 1}$ is the distribution of $Y$, the number of
leaves in the total descendant subtree rooted at the uniformly random vertex,
conditioned on $T$. We use (4.9), and $X(t)\leq\tfrac{\ell}{t}$, which holds
since no two subtrees each with $t$ leaves intersect, to estimate

$\mathbb{E}\biggl{[}\Bigl{(}\tfrac{X(t)}{V}-\tfrac{X(t)}{\mathbb{E}[V|L=\ell]}\Bigr{)}^{2}\,\Big{|}L=\ell\biggr{]}\leq\mathbb{E}\Bigl{[}\bigl{(}\tfrac{X(t)}{\ell^{2}}\bigr{)}^{2}\text{var}(V|L=\ell)\Bigr{]}=O(\ell^{-1/2}t^{-2}).\\\
$

So, by Cauchy-Schwartz inequality, we have: uniformly for all $t\geq 1$,

$\mathbb{E}\bigl{[}\tfrac{X(t)}{V}|L=\ell]-\tfrac{\mathbb{E}[X(t)|L=\ell]}{E[V|L=\ell]}=O(\ell^{-1/4}t^{-1}).$

or equivalently

$\mathbb{P}(\mathcal{L}=t|L=\ell)=\tfrac{\mathbb{E}[X(t)|L=\ell]}{E[V|L=\ell]}+O(\ell^{-1/4}t^{-1}).$

Combining this formula with Lemma 2.1 and (4.7), we obtain

(4.10)
$\mathbb{P}(\mathcal{L}=t|L=\ell)=(1-p_{1})\tfrac{(\ell-t+1)\,\mathbb{P}(L=\ell-t+1)\,\mathbb{P}(L=t)}{\ell\,\mathbb{P}(L=\ell)}+O(\ell^{-1/4}t^{-1}),$

uniformly for $t\leq\ell$. Applying the formula (1.2) to (4.10), we conclude

$\lim_{\ell\to\infty}\mathbb{P}(\mathcal{L}=t|L=\ell)=(1-p_{1})\mathbb{P}(A_{t}).$

Since $\sum_{t\geq 1}\mathbb{P}(A_{t})=1$, we see that the sequence of the
distributions $\\{\mathbb{P}(Y=t|L=\ell)\\}_{1\leq t\leq\ell}$, $(\ell\geq
1)$, is not tight, unless (as in the binary case) $\,p_{1}=0$. In words,
$p_{1}$ is the limiting deficit of the leaf-set size distribution for the
random subtree.

Let us make this claim more precise. Introduce
$\tau=\tfrac{\ell^{1/2}}{\log^{2}\ell}$. For $t\leq\tau$, it follows from
(1.2) that

$\tfrac{(\ell-t+1)\,\mathbb{P}(L=\ell-t+1)}{\ell\,\mathbb{P}(L=\ell)}=1+O(\tau\ell^{-1}+\ell^{-1/2})=1+O(\ell^{-1/2}),$

implying that

$(1-p_{1})\sum_{t\leq\tau}\tfrac{(\ell-t+1)\,\mathbb{P}(L=\ell-t+1)\,\mathbb{P}(L=t)}{\ell\,\mathbb{P}(L=\ell)}=(1-p_{1})\sum_{t\leq\tau}\mathbb{P}(L=t)+O(\ell^{-1/2})\\\
=1-p_{1}+O(\mathbb{P}(L>\tau))+O(\ell^{-1/2})=1-p_{1}+O\bigl{(}\ell^{-1/4}\log\ell\bigr{)}.$

Therefore

$\mathbb{P}(\mathcal{L}>\tau|L=\ell)=1-(1-p_{1})\sum_{t\leq\tau}\tfrac{(\ell-t+1)\,\mathbb{P}(L=\ell-t+1)\,\mathbb{P}(L=t)}{\ell\,\mathbb{P}(L=\ell)}\\\
+O(\ell^{-1/4}\log\ell)=p_{1}+O(\ell^{-1/4}\log\ell).$

This completes the proof of Theorem 1.2.

Acknowledgment. I am grateful to David Aldous for helping me to put this work
into a proper perspective.

## References

  * [1] D. Aldous, Asymptotic fringe distributions for general families of random trees, Ann. Appl. Probab., 1 (1991) 228–266.
  * [2] E. A. Bender, Asymptotic methods in enumeration, SIAM Review, 16 (1974) 485–515.
  * [3] E. R. Canfield, Remarks on an asymptotic method in combinatorics, J. Comb. Theory, A, 37 (1984) 348–352.
  * [4] W. Ebeling, Functions of Several Complex Variables and Their Singularities, American Mathematical Society (2007).
  * [5] P. Flajolet and R. Sedgewick, Analytic Combinatorics, Cambridge University Press (2009).
  * [6] L. S. Gradshteyn and I. M. Ryzhik, Table of Integrals, Series, and Products, 6th Edition, Academic Press (2000).
  * [7] T. E. Harris, The Theory of Branching Processes, Springer–Verlag (1963).
  * [8] S. Janson, Simply generated trees. conditioned Galton–Watson trees, random allocations and condensation, Probab. Surveys, 9 (2012) 103–252.
  * [9] V. F. Kolchin, Branching processes, random trees, and a generalized scheme of arrangements of particles, Math. Notes, 21 (1977) 386–394.
  * [10] V. F. Kolchin, Moment of degeneration of a branching process and height of a random tree, Math. Notes, 24 (1978), 954–961.
  * [11] V. F. Kolchin, Random Mappings, Optimization Software, New York, (Translation of Russian original) (1988).
  * [12] S. G. Krantz and H. R. Parks, The Implicit Function Theorem: History, Theory, and Applications, Birkhäuser (2013).
  * [13] A. Meir and J. W. Moon, On an asymptotic method in enumeration, J. Comb. Theory, A, 51 (1989) 77–89.
  * [14] A. Meir and J. W. Moon, Erratum: “On an asymptotic method in enumeration”, J. Comb. Theory, A, 52 (1989) 163.
  * [15] B. Pittel, Expected number of induced subtrees shared by two independent copies of a random tree, SIAM J. Discrete Math., 37 (2023), 1–16.