# The Implicit Bias for Adaptive Optimization Algorithms on Homogeneous Neural
Networks

Bohan Wang
Microsoft Research Asia,
Beijing, China
<EMAIL_ADDRESS>
&Qi Meng
Microsoft Research Asia,
Beijing, China
<EMAIL_ADDRESS>
&Wei Chen
Microsoft Research Asia,
Beijing, China
<EMAIL_ADDRESS>

###### Abstract

Despite their overwhelming capacity to overfit, deep neural networks trained
by specific optimization algorithms tend to generalize relatively well to
unseen data. Recently, researchers explained it by investigating the implicit
bias of optimization algorithms. A remarkable progress is the work [18], which
proves gradient descent (GD) maximizes the margin of homogeneous deep neural
networks. Except the first-order optimization algorithms like GD, adaptive
algorithms such as AdaGrad, RMSProp and Adam are popular owing to its rapid
training process. Meanwhile, numerous works have provided empirical evidence
that adaptive methods may suffer from poor generalization performance.
However, theoretical explanation for the generalization of adaptive
optimization algorithms is still lacking. In this paper, we study the implicit
bias of adaptive optimization algorithms on homogeneous neural networks. In
particular, we study the convergent direction of parameters when they are
optimizing the logistic loss. We prove that the convergent direction of
RMSProp is the same with GD, while for AdaGrad, the convergent direction
depends on the adaptive conditioner. Technically, we provide a unified
framework to analyze convergent direction of adaptive optimization algorithms
by constructing novel and nontrivial _adaptive gradient flow_ and _surrogate
margin_. The theoretical findings explain the superiority on generalization of
exponential moving average strategy that is adopted by RMSProp and Adam. To
the best of knowledge, it is the first work to study the convergent direction
of adaptive optimizations on non-linear deep neural networks.

_Keywords_ Adaptive Optimizer $\cdot$ Implicit Bias $\cdot$ Margin

##  1 Introduction

Deep learning techniques have been very successful in several domains, like
computer vision [26], speech recognition [5] and natural language processing
[30]. In practice, deep neural networks (DNN) learned by some optimization
algorithms such as gradient descent (GD) and its variants can generalize well
to unseen data [28]. However, deep neural networks are non-convex. The non-
convex deep neural networks have been found to have large amount of global
minima [4], while only few of them can guarantee satisfactory generalization
property [3]. Explaining why the highly non-convex model trained by a specific
algorithm can generalize has become an important open question in deep
learning.

Regarding the above question, one plausible explanation is that optimization
algorithms implicitly bias training [22]. That is, the optimization algorithm
tends to drive parameters to certain kinds of global minima which generalize
well, although no explicit regularization is enforced. Recently, exciting
results have been shown for vanilla gradient descent. For linear classifier,
GD is proved to converge to minimum $L_{2}$ norm solution for squared loss and
max-margin solution for logistic loss [25]. [10] extend the result for GD to
deep linear neural networks. A remarkable progress is the work [18], which
proves GD maximizes the margin of homogeneous deep neural networks.

On the other hand, adaptive algorithms such as AdaGrad [6], RMSProp [9], and
Adam [13] have been in spotlight these years. These algorithms are proposed to
improve the convergence rate of GD (or SGD) by using second-order moments of
historical gradients and have been widely applied in deep learning [24].
Despite the rapid convergence of adaptive methods, numerous works have
provided empirical evidence that adaptive methods may suffer from poor
generalization performance [27, 17]. Specifically, it has been observed that
first-order method such as SGD can outperform adaptive methods on the test
set, even when the adaptive methods achieve the same or lower training loss.
Several works try to improve the performance of adaptive optimization
algorithms such as AdamW [16], AdaBound [17], AdaBelief [32]. However, there
is little theoretical analysis for generalization of adaptive algorithms.
These observations and the research for GD motivate us to study the implicit
bias for adaptive algorithms.

The key factor for the success of adaptive algorithms is to design better
conditioners of the gradient. There are two popular kinds of conditioners: one
is the simple average of the squared values of past gradients that is used in
AdaGrad, and the other is the exponential moving average that is used in
RMSProp, Adam, etc. In this paper, we aim to study the influence of these two
kinds of conditioners on convergent direction of parameters on deep neural
networks. Specifically, we work on the homogeneous neural networks with
separable data under logistic regression setting. Unlike the squared loss, the
logistic doss does not admit a finite global minimizer on separable data: the
iterates will diverge in order to drive the loss to zero. Therefore,
researchers use the asymptotic direction of algorithms (i.e.,
$\lim_{t\rightarrow\infty}\frac{w_{t}}{\|w_{t}\|_{2}}$) for logistic loss
instead of characterizing the exact limit of parameters [25, 8].

The main result and our technical contributions are summarized as follows.

######  Theorem 1.

(Informal) We use $\Phi(\bm{w},\bm{x})$ to denote the homogeneous neural
network model with parameter $\bm{w}$ and input $x$. (1) For AdaGrad, any
limit point of $w_{t}/\|w_{t}\|_{2}$ is the KKT point of the optimization
problem

$\displaystyle\min\|\bm{h}^{1/2}_{\infty}\odot\bm{w}\|\quad\textit{subject to
}y_{i}\Phi(\bm{w},\bm{x}_{i})\geq 1,\forall i,$ (1)

where $\bm{h}_{\infty}=\lim_{t\rightarrow\infty}\bm{h}(t)$ is the limit of the
conditioner in AdaGrad. (2) For RMSProp, any limit point of
$\bm{w}(t)/\|\bm{w}(t)\|_{2}$ is the KKT point of the optimization problem

$\displaystyle\min\|\bm{w}\|^{2}\quad\textit{subject to
}y_{i}\Phi(\bm{w},\bm{x}_{i})\geq 1,\forall i.$ (2)

Theorem 1 provides several interesting insights. RMSProp converges to the
direction which is independent with the conditioner while AdaGrad does not.
The limit direction of RMSProp is the same with gradient descent, which is the
max-margin solution and indicates good generalization. It matches the
empirical observations that RMSProp generalize better than AdaGrad on deep
neural networks [27]. The reason is the exponential weighted average strategy
(i.e., $\bm{m}(t+1)=b\bm{m}(t)+(1-b)\bar{\partial}\mathcal{L}^{2}$, where
$\sqrt{\bm{m}(t)+\varepsilon}=\bm{h}(t)^{-1}$) in RMSProp makes the part
$\bm{m}(t)$ converge to zero, while in AdaGrad, the update rule is
$\bm{m}(t+1)=\bm{m}(t)+\bar{\partial}\mathcal{L}^{2}$, which makes $\bm{m}(t)$
keep growing and rely on the optimization process. Therefore, adaptive
algorithms that adopt exponential weighted average strategy achieves tradeoff
between optimization efficiency and generalization guarantee, i.e., it
accelerates the training process at early stage of optimization by adaptively
adjusting the learning rate, but it still converges to low-complexity model
(i.e., max margin solution) because the conditioner converges to constant at
later stage.

In order to prove the Theorem 1, we first propose adaptive gradient flow,
which is a unified framework to deal with adaptive gradients. It transforms
original parameter space to a parameter space normalized by the conditioners.
Second, in the normalized parameter space, we construct surrogate margin for
the adaptive algorithms. The surrogate margin is defined as the ratio of
negative logarithmic loss normalized by parameter norm. We prove that
surrogate margin is lower bounded, and then the increasing rate of parameter
norm can then be bounded by the decreasing rate of loss [8], which together
drive the loss to zero. At last, we can prove any limit direction of the
normalized parameter flow is the KKT point of the margin maximization problem
in normalized parameter space. Moreover, we prove the convergent direction is
unique if the neural network is definable [14].

Technically, although we adopt the framework of [18], the techniques for
vanilla GD can no longer be applied to adaptive algorithms. We highlight our
technical contributions as: (1) we construct adaptive gradient flow, which is
novel and non trivial. With the adaptive gradient flow, the analysis of
convergent direction is transformed from original parameter space to a
normalized parameter space. The adaptive gradient flow can be applied into
analysis of other adaptive algorithms. (2) Previous works [25, 18] prove for
vanilla GD, smoothed margin defined as
$\frac{\log\frac{1}{\mathcal{L}(\bm{w})}}{\|\bm{w}\|^{L}}$ monotonously
increases, which however, in adaptive methods, no longer holds. Instead, we
define the surrogate margin which take the conditioner into account, and prove
the surrogate margin (i) is lower bounded; (ii) has the same limit with the
normalized margin.

##  2 Related Work

Implicit Bias of First-order Optimization Methods. [25] proved that gradient
descent on linear logistic regression with separable data converges in the
direction of the max $L^{2}$ margin solution of the corresponding hard-margin
Support Vector Machine, and motivate a line of works on the bias of GD on
linear model. For example, [20] studied other loss with different tails; [11]
proved similar result without assuming separable data; [15] worked on the
problem in the adversarial scenario; [29] analyzed the case when there is only
a ReLU neuron.

Then, there are some works study the implicit bias of GD on deep neural
networks. The asymptotic direction of the product of weights in a deep linear
network is studied in [10, 8]. [25] studied the implicit bias of two-layer
neural network with ReLU activation. [19] proved the asymptotic direction is
along a KKT point of the $L^{2}$ max margin problem for homogeneous deep
neural networks. [18] independently proved similar result for homogeneous
neural networks with simplified assumptions. Based on [18], [12] further prove
that parameters have only one asymptotic direction.

There are also works considering implicit bias of other first-order
optimization algorithms. [21] worked on Stochastic Gradient Descent for linear
logistic regression. [7] studied the implicit bias of mirror descent, natural
gradient descent, and steepest descent on linear model. [1] proved gradient
descent on Neural Tangent Kernel will converge linearly to a global minimum
near the initial point.

Theoretical Evidence of Generalization of Adaptive Algorithms. [27]
constructed a linear regression task where AdaGrad, RMSProp, and ADAM converge
to a solution that incorrectly classifies new data with probability
arbitrarily close to half and SGD finds a solution with zero error on new
data. [31] modeled the distribution of stochastic noise in Adam, and they
showed that SGD tends to converge to flatter local minima. Another viewpoint
is to study the implicit bias of adaptive optimization algorithms. To the best
of our knowledge, the only work on the bias of adaptive algorithms is [23],
which proves AdaGrad has different asymptotic direction with GD on linear
logistic regression. In this paper, we study the asymptotic direction of
adaptive optimization algorithms on deep neural networks which requires
different techniques due to high non-convex of deep networks.

##  3 Preliminaries

In this paper, we study the logistic regression problem with homogeneous
neural networks. Let training set $\bm{S}$ defined as
$\bm{S}=\\{(\bm{x}_{i},y_{i})\\}_{i=1}^{N}$, where $\bm{x}_{i}\in\mathcal{X}$
($i=1,2,\cdots,N$) are inputs, $y_{i}\in\mathbb{R}$ ($i=1,2,\cdots,N$) are
labels, and $N$ is the size of $\bm{S}$. The empirical loss $\mathcal{L}$ with
training set $\bm{S}$, neural network classifier $\Phi$, individual loss
$\ell(x)=e^{-f(x)}$ and parameters $\bm{w}\in\mathbb{R}^{p}$ can be written as
follows:

$\mathcal{L}(\bm{w},\bm{S})=\sum_{i=1}^{N}\ell\left(y_{i}\Phi(\bm{w},\bm{x}_{i})\right).$

In an optimization process, the training set $\bm{S}$ is fixed. Therefore,
without loss of generality, we abbreviate
$\mathcal{L}(\bm{w},\bm{S})=\mathcal{L}(\bm{w})$, and
$y_{i}\Phi(\bm{w},\bm{x}_{i})=q_{i}(\bm{w})$. In this paper, we consider the
exponential loss, i.e., $f(q_{i}(\bm{w}))=q_{i}(\bm{w})$, and the logistic
loss, i.e., $f(q_{i}(\bm{w}))=-\log\log(1+e^{-q_{i}(\bm{w})})$. Both of $f$
are monotonously increasing and have an inverse.

As for optimization methods, we consider AdaGrad and RMSProp. The update rule
for the two algorithms can be written as

$\bm{w}(t+1)-\bm{w}(t)=-\eta(t)\bm{h}(t)\odot\bar{\partial}\mathcal{L}(\bm{w}(t)),$
(3)

where $\bm{h}(t)$ is called the conditioner which adaptively assigns different
learning rates for different coordinates. For AdaGrad,
$\bm{h}(t)^{-1}=\sqrt{\varepsilon\mathbf{1}_{p}+\sum_{\tau=0}^{t}\bar{\partial}\mathcal{L}(\bm{w}(\tau))^{2}}$
where $\epsilon$ is a positive constant. Here,
$\bar{\partial}\mathcal{L}(\bm{w}(\tau))^{2}=\mathcal{L}(\bm{w}(\tau))\odot\mathcal{L}(\bm{w}(\tau))$
and $\odot$ denotes the element-wised product of a vector. Different from
AdaGrad, RMSProp adopts exponential weighted average stategy in $\bm{h}(t)$,
i.e.,
$\bm{h}(t)^{-1}=\sqrt{\varepsilon\mathbf{1}_{p}+\sum_{\tau=0}^{t}(1-b)b^{t-\tau}\bar{\partial}\mathcal{L}(\bm{w}(\tau))^{2}}$.
For clarity, we use $\bm{h}^{A}(t)$ and $\bm{h}^{R}(t)$ to distinguish the
term $\bm{h}(t)$ in AdaGrad and RMSProp, respectively.

We consider the flow of the two optimization algorithms, i.e.,

$\frac{d\bm{w}(t)}{\mathrm{d}t}=-\bm{h}(t)\odot\bar{\partial}\mathcal{L}(\bm{w}(t)),$
(4)

which is the continuous version of Eq.3. For the flow, the conditioner has the
form
$\bm{h}^{A}(t)^{-1}=\sqrt{\varepsilon\mathbf{1}_{p}+\int_{0}^{t}\bar{\partial}\mathcal{L}(\bm{w}(\tau))^{2}\mathrm{d}\tau}$
and
$\bm{h}^{R}(t)^{-1}=\sqrt{\varepsilon\mathbf{1}_{p}+\int_{0}^{t}(1-b)e^{-(1-b)(t-\tau)}\bar{\partial}\mathcal{L}(\bm{w}(\tau))^{2}\mathrm{d}\tau}$.
Our study will start with the continuous version of the two algorithms, which
is easier to analyze.

Specifically, for the continuous case, we focus on the following scenario:

######  Assumption 1.

The empirical loss is defined as
$\mathcal{L}(\bm{w})=\sum_{i=1}^{N}e^{-f(q_{i}(\bm{w}))}$. The following
propositions hold:

  1. I

(Regularity). For any $i$, $q_{i}$ is locally Lipchitz and admits a chain
rule;

  2. II

(Homogeneity). There exists $L>0$ such that $\forall\alpha>0$ and $i$,
$q_{i}(\alpha\bm{w})=\alpha^{L}q_{i}(\bm{w})$;

  3. III

(Separability). There exists a time $t_{0}$ such that
$f^{-1}(\log\frac{1}{\mathcal{L}(t_{0})})>0$.

I, II in Assumption 1 holds for a board class of networks allowing for ReLU,
max pooling, and convolutional layers; Assumption 1.III holds generally for
over-parameterized neural networks, which can achieve complete correct
classification in training set.

At the end of this section, we give a brief introduction to KKT conditions and
KKT points. For a constrained optimization problem defined as

$\min f(\bm{v})\text{ subject to: }g_{i}(\bm{v})\leq 0,\text{ }\forall
i\in[N],$

KKT conditions are necessary conditions for a feasible point $\bm{v}_{0}$ to
be an optimal point. Concretely, KKT conditions require that there exists non-
negative reals $\lambda_{i}$, such that

$\displaystyle\bar{\partial}f(\bm{v}_{0})+\sum_{i=1}^{N}\lambda_{i}\bar{\partial}g_{i}(\bm{v}_{0})=0;$
(5) $\displaystyle\sum_{i=1}^{N}\lambda_{i}g_{i}(\bm{v}_{0})=0.$ (6)

A feasible point is said to be a KKT point if it satisfies KKT condition.

A weaker notion of KKT condition is $(\varepsilon,\delta)$ KKT condition,
which only requires left sides of eq. (5) and (6) to be respectively smaller
than $\varepsilon$ and $\delta$. We will formally define
$(\varepsilon,\delta)$ KKT points and give some of their properties in
Appendix A.2.

Notations. In this paper, we use $\mathcal{O}$, $\Theta$, and $\Omega$ to hide
the absolute multiplicative factors. We also use $\bar{\partial}f$ to denote
the subgradient of a function $f$.

##  4 Adaptive Gradient Flow: Definition and Verification

In this section, we will prove some common properties of AdaGrad flow and
RMSProp flow. Based on these properties, we will define the general adaptive
gradient flow, and present our convergent direction results on adaptive
gradient flows. Then, the convergent direction of AdaGrad and RMSProp can be
derived as a special case of adaptive gradient flow. In the end of this
section, we will show that under additional assumptions, the convergent
direction is unique.

We first prove the following properties of AdaGrad flow.

######  Theorem 2.

For AdaGrad flow defined as eq. (4) with $\bm{h}(t)=\bm{h}^{A}(t)$, we have
that

  * •

$\bm{h}^{A}(t)$ converges as $t\rightarrow\infty$. Furthermore,
$\lim_{t\rightarrow\infty}\bm{h}^{A}(t)$ has no zero component.

  * •

If we let $\bm{h}_{\infty}=\lim_{t\rightarrow\infty}\bm{h}^{A}(t)$, and define

$\displaystyle\bm{v}^{A}(t)=\bm{h}_{\infty}^{-1/2}\odot\bm{w}(t),$
$\displaystyle\bm{\beta}^{A}(t)=\bm{h}_{\infty}^{-1}\odot\bm{h}(t),$
$\displaystyle\tilde{\mathcal{L}}^{A}(\bm{v}^{A})=\mathcal{L}(\bm{h}_{\infty}^{\frac{1}{2}}\odot\bm{v}^{A}),$

we have

$\frac{\mathrm{d}\bm{v}^{A}(t)}{\mathrm{d}t}=-\bm{\beta}^{A}(t)\odot\bar{\partial}\tilde{\mathcal{L}}^{A}(\bm{v}^{A}(t)).$

  * •

$\frac{d\log\bm{\beta}^{A}(t)}{\mathrm{d}t}$ is Lebesgue integrable with
respect to $t$.

We make some explanations to above properties: The former part of the first
property is natural, since $\bm{h}^{A}(t)$ is non-increasing with respect to
$t$. However, the latter part yields that integration of square of the
gradient converges to a positive real, which is non-trivial; the second
property is obtained by component-wisely scaling $\bm{w}$ and direct
verification; the last property can be obtained by Newton-Leibnz formula for
absolutely continuous function since
$\frac{\mathrm{d}\bm{\beta}^{A}(t)}{\mathrm{d}t}$ is non-negative, and
guarantees that the change of $\bm{\beta}^{A}$ will not be too severe. We
defer the detailed proof to Appendix B.1.

Similar properties also hold for RMSProp as the following lemma.

######  Theorem 3.

For RMSProp flow defined as eq. (4) with $\bm{h}(t)=\bm{h}^{R}(t)$, we have
that

  * •

$\bm{h}^{R}(t)$ converges as $t\rightarrow\infty$. Furthermore,
$\lim_{t\rightarrow\infty}\bm{h}^{R}(t)=\varepsilon^{-\frac{1}{2}}\mathbf{1}_{p}^{T}$.

  * •

If we let $\bm{h}_{\infty}=\lim_{t\rightarrow\infty}\bm{h}^{R}(t)$, and define

$\displaystyle\bm{v}^{R}(t)=\varepsilon^{\frac{1}{4}}\bm{w}(t),$
$\displaystyle\bm{\beta}^{R}(t)=\varepsilon^{\frac{1}{2}}\bm{h}(t),$
$\displaystyle\tilde{\mathcal{L}}^{R}(\bm{v}^{R})=\mathcal{L}(\varepsilon^{-\frac{1}{4}}\bm{v}^{R}),$

we have

$\frac{\mathrm{d}\bm{v}^{R}(t)}{\mathrm{d}t}=-\bm{\beta}^{R}(t)\odot\bar{\partial}\tilde{\mathcal{L}}^{R}(\bm{v}^{R}(t)).$

  * •

$\frac{d\log\bm{\beta}^{R}(t)}{\mathrm{d}t}$ is Lebesgue integrable with
respect to $t$.

The conditioner $\bm{h}^{R}$ has a decay term $e^{-(t-\tau)(1-b)}$, which
drives
$\int_{\tau=0}^{t}(1-b)e^{-(1-b)(t-\tau)}\bar{\partial}\mathcal{L}(\bm{w}(\tau))^{2}d\tau$
to zero, and the conditioner to isotropy. The detailed proof requires a more
careful analysis in measure than the AdaGrad flow. We defer them to Section
B.1.

Based on the properties they share, we can define the following adaptive
gradient flow for more general adaptive optimizers.

######  Definition 1.

A function $\bm{w}(t)$ is called to obey an adaptive gradient flow
$\mathcal{F}$ with loss $\mathcal{L}$ and component learning rate
$\bm{\beta}(t)$, if it can be written as the following form

$\frac{d\bm{w}(t)}{\mathrm{d}t}=-\bm{\beta}(t)\odot\bar{\partial}\mathcal{L}(\bm{w}(t)),$

where $\bm{\beta}(t)$ satisfies that
$\lim_{t\rightarrow\infty}\bm{\beta}(t)=\mathbf{1}_{p}$, and
$\frac{\mathrm{d}\log\bm{\beta}(t)}{\mathrm{d}t}$ is Lebesgue Integrable.

By Theorems 2 and 3, AdaGrad flow and RMSProp can both be transferred into
adaptive gradient flows: $\bm{v}^{A}$ obeys an adaptive gradient flow with
loss $\tilde{\mathcal{L}}^{A}$ and conditioner $\bm{\beta}^{A}$, while
$\bm{v}^{R}$ obeys an adaptive gradient flow with loss
$\tilde{\mathcal{L}}^{R}$ and conditioner $\bm{\beta}^{R}$. Furthermore,
Assumption 1 also holds for $\tilde{\mathcal{L}}^{A}$ and
$\tilde{\mathcal{L}}^{R}$: for both AdaGrad and RMSProp, we can uniformly
represent $\tilde{\mathcal{L}}^{A}(\bm{v}^{A})$ and
$\tilde{\mathcal{L}}^{R}(\bm{v}^{R})$ as
$\mathcal{L}(\tilde{\bm{h}}^{\frac{1}{2}}\odot\bm{v})$, where $\tilde{\bm{h}}$
is a component-wisely positive constant vector. By Assumption 1,
$\tilde{\mathcal{L}}(\bm{v})$ can be further written as

$\displaystyle\tilde{\mathcal{L}}(\bm{v})=$
$\displaystyle\mathcal{L}(\tilde{\bm{h}}^{\frac{1}{2}}\odot\bm{v})$
$\displaystyle=$
$\displaystyle\sum_{i=1}^{N}e^{-f(q_{i}(\tilde{\bm{h}}^{\frac{1}{2}}\odot\bm{v}))}.$

If we denote
$\tilde{q}_{i}(\bm{v})=q_{i}(\tilde{\bm{h}}^{\frac{1}{2}}\odot\bm{v})$, we
have $\tilde{q}_{i}$ is also an $L$ homogeneous function, and
$\tilde{\mathcal{L}}(\bm{v})=\sum_{i=1}^{N}e^{-f(\tilde{q}_{i}(\bm{v}))}$.

Therefore, we only consider adaptive gradient flow satisfying Assumption 1.
Our main result is the following theorem:

######  Theorem 4.

Let $\bm{v}$ satisfy an adaptive gradient flow $\mathcal{F}$ which satisfies
Assumption 1. Let $\bar{\bm{v}}$ be any limit point of
$\\{\hat{\bm{v}}(t)\\}_{t=0}^{\infty}$ (where
$\hat{\bm{v}}(t)=\frac{\bm{v}(t)}{\|\bm{v}(t)\|}$ is normalized parameter).
Then $\bar{\bm{v}}$ is along the direction of a KKT point of the following
$L^{2}$ max-margin problem $(P)$:

$\displaystyle\min\frac{1}{2}\|\bm{v}\|^{2}$ $\displaystyle\text{subject to
}\tilde{q}_{i}(\bm{v})\geq 1,\forall i\in[N].$

$(P)$ is equivalent to the $L^{2}$ max-margin problem: suppose $\bm{v}_{0}$ is
an optimal point of $(P)$. Then there exists an $i\in[N]$, such that,
$\tilde{q}_{i}(\bm{v}_{0})=1$ (otherwise, we can let
$\bm{v_{0}}^{\prime}=\bm{v}_{0}/\tilde{q}_{\min}(\bm{v}_{0})^{\frac{1}{L}}$.
Then $\bm{v_{0}}^{\prime}$ is also a fixed point of $(P)$ and have a smaller
$L^{2}$ norm than $\bm{v_{0}}^{\prime}$, which leads to contradictory).
Therefore, $\tilde{q}_{\min}(\bm{v}_{0})=1$
($\tilde{q}_{\min}(\bm{v})\overset{\triangle}{=}\min_{i}\\{\tilde{q}_{i}(\bm{v})\\}$),
and maximizing the normalized margin
$\frac{\tilde{q}_{\min}(\bm{v})}{\|\bm{v}\|^{L}}$ is equivalent to minimize
$\|\bm{v}\|^{L}$.

Theorem 4 shows that the adaptive gradient flow actually drives the parameters
to solutions of $L^{2}$ max-margin problem. We will give the proof skeleton of
Theorem 4 in Section 5.

Combining Theorem 4 with Theorems 2 and 3, one can obtain convergent
directions of AdaGrad flow and RMSProp flow by simple parameter substitution
of $(P)$.

######  Theorem 5.

Let $\bm{w}$ satisfy AdaGrad flow defined as eq. (4) with
$\bm{h}(t)=\bm{h}^{A}(t)$. Then, any limit point of
$\\{\hat{\bm{w}}(t)\\}_{t=0}^{\infty}$ (where
$\hat{\bm{w}}(t)=\frac{\bm{w}(t)}{\|\bm{w}(t)\|}$ is normalized parameter) is
along the direction of a KKT point of the following optimization problem
$(P^{A})$:

$\displaystyle\min\frac{1}{2}\|\bm{h}_{\infty}^{-\frac{1}{2}}\odot\bm{w}\|$
$\displaystyle\text{Subject to: }q_{i}(\bm{w})\geq 1.$

######  Theorem 6.

Let $\bm{w}$ satisfy RMSProp flow defined as eq. (4) with
$\bm{h}(t)=\bm{h}^{R}(t)$. Then, any limit point of
$\\{\hat{\bm{w}}(t)\\}_{t=0}^{\infty}$ (where
$\hat{\bm{w}}(t)=\frac{\bm{w}(t)}{\|\bm{w}(t)\|}$ is normalized parameter) is
along the direction of a KKT point of the following optimization problem
$(P^{R})$:

$\displaystyle\min\frac{1}{2}\|\bm{w}\|$ $\displaystyle\text{Subject to:
}q_{i}(\bm{w})\geq 1.$

Intuitively, $(P^{R})$ is the $L^{2}$ max-margin problem, which means RMSProp
flow biases parameters to a local minimum with good generalization property;
on the other hand, the target of $(P^{A})$ has a reliance of
$\bm{h}_{\infty}$, which can be influenced by the optimization process and
initialization, and may further lead to worse generalization. We will discuss
the difference between convergent directions of AdaGrad and RMSProp in detail
in Section 6.1.

##  5 Proof Sketch of Theorem 4

In this section, we present the proof sketch of Theorem 4. The proof can be
divided into three stages: (I). An surrogate margin is constructed, and we
prove it is lower bounded and equivalent to normalized margin as time tends to
infinity; (II). We use this surrogate margin to lower bound the decreasing
rate of empirical loss $\mathcal{L}$, and prove
$\lim_{t\rightarrow\infty}\tilde{\mathcal{L}}(\bm{w}(t))=0$; (III). For every
convergent direction $\bar{\bm{v}}$, a series of
$(\varepsilon_{i},\delta_{i})$ KKT point which converges to $\bar{\bm{v}}$
with
$\lim_{i\rightarrow\infty}\varepsilon_{i}=\lim_{i\rightarrow\infty}\delta_{i}=0$
is constructed. We then show every convergent direction is a KKT point of
optimization problem $(P)$.

###  5.1 surrogate margin on adaptive gradient flow

By homogeneity of $\tilde{q}_{i}$, for any parameter $\bm{v}$,
$\langle\bar{\partial}\tilde{q}_{i}(\bm{v}),\bm{v}\rangle=L\tilde{q}_{i}(\bm{v})$.
Therefore, the inner product between
$\bar{\partial}\tilde{\mathcal{L}}(\bm{v})=-\sum_{i\in[N]}e^{-f(\tilde{q}_{i}(\bm{v}))}f^{\prime}(\tilde{q}_{i}(\bm{v}))\bar{\partial}\tilde{q}_{i}(\bm{v})$
and $\bm{v}$ has a clear form that
$-\langle\bar{\partial}\tilde{\mathcal{L}}(\bm{v}),\bm{v}\rangle=L\sum_{i\in[N]}e^{-f(\tilde{q}_{i}(\bm{v}))}f^{\prime}(\tilde{q}_{i}(\bm{v}))\tilde{q}_{i}(\bm{v})$.
However, for adaptive gradient flow,
$\bar{\partial}\tilde{\mathcal{L}}(\bm{v}(t))=-\bm{\beta}(t)\odot\frac{\mathrm{d}\bm{v}(t)}{\mathrm{d}t}$,
and we can no longer adopt the above method to calculate the change of
$\|\bm{v}\|$. To solve the problem, we study the surrogate norm
$\rho(t)\overset{\triangle}{=}\|\bm{\beta}(t)^{-\frac{1}{2}}\odot\bm{v}(t)\|$.
Since $\lim_{t\rightarrow\infty}\bm{\beta}=\mathbf{1}$,
$\rho(t)=\Theta(\|\bm{v}(t)\|)$.

The normalized margin
$\gamma(t)=\frac{\tilde{q}_{\min}(t)}{\|\bm{v}(t)\|^{L}}$ connects margin
$\tilde{q}_{\min}(t)$ with parameter norm $\|\bm{v}(t)\|$. However, since
normalized margin is derived by taking minimum among all $\tilde{q}_{i}$, it
requires huge efforts to calculate and estimate derivative of $\gamma(t)$.
Fortunately, the next lemma admits us to define an surrogate margin defined
using $\tilde{\mathcal{L}}$.

######  Lemma 1.

If $\lim_{t\rightarrow\infty}\tilde{\mathcal{L}}=0$, we have that
$\frac{g(\log\frac{1}{\tilde{\mathcal{L}(\bm{v}(t))}})}{\rho(t)}=\Theta(\gamma(t))$,
where $g$ is the inverse of function $f$ in Assumption 1.

Based Lemma 1, we can defined our surrogate margin as follows:

######  Definition 2.

Let a function $\bm{v}(t)$ satisfies an adaptive gradient flow $\mathcal{F}$
with loss $\tilde{\mathcal{L}}$ and component learning rate $\bm{\beta}(t)$,
where $\tilde{\mathcal{L}}$ satisfies Assumption 1. Then the surrogate margin
$\tilde{\gamma}$ is defined as

$\tilde{\gamma}(t)=\frac{g(\log\frac{1}{\tilde{\mathcal{L}}(\bm{v}(t))})}{\rho(t)^{L}}.$

Since $\rho(t)=\Theta(\|\bm{v}(t)\|)$, $\tilde{\gamma}$ actually bridge the
norm of parameters with empirical loss. A desired property for
$\tilde{\gamma}$ is to have a positive lower bound, since with this property,
one can further bound parameter norm using empirical loss. The following lemma
shows that $\tilde{\gamma}$ is lower bounded for adaptive gradient flow
$\mathcal{F}$ with empirical loss $\tilde{\mathcal{L}}$ satisfying Assumption
1.

######  Lemma 2.

Let a function $\bm{v}(t)$ satisfies an adaptive gradient flow $\mathcal{F}$
with loss $\tilde{\mathcal{L}}$ and component learning rate $\bm{\beta}(t)$,
where $\tilde{\mathcal{L}}$ satisfies Assumption 1. Then there exists a time
$t_{1}\geq t_{0}$, such that, for any time $t\geq t_{1}$,
$\tilde{\gamma}(t)\geq e^{-\frac{1}{2}}\tilde{\gamma}(t_{1})$.

Here we briefly give a road map of the proof. The derivative of norm $\rho(t)$
can be split into two parts: one is the increasing of parameter $\bm{v}$ along
the direction of $\bm{\beta}^{-\frac{1}{2}}(t)$, and another is the change of
component learning rate $\bm{\beta}^{-\frac{1}{2}}(t)$. Applying homogeneity
of $\tilde{q}_{i}$ and Cauchy Inequality, we bound the first term using the
increasing rate of
$g\left(\log\left(\frac{1}{\tilde{\mathcal{L}}(t)}\right)\right)$, which is
exactly derivative of numerator of $\tilde{\gamma}$; while for the second
term, we show that it can be lower bounded by
$\sum_{i=1}^{p}\left(\frac{d\log\bm{\beta}_{i}^{-\frac{1}{2}}(t)}{\mathrm{d}t}\right)_{+}$.
By the definition of adaptive gradient flow, integration of the second term
tend to zero as time approaches infinity. The proof is completed by putting
two parts together.

By the discussion above, one can observe that derivative of
$\tilde{\gamma}(t)$ can be calculated by subtracting a small enough term
$\sum_{i=1}^{p}\left(\frac{d\log\bm{\beta}_{i}^{-\frac{1}{2}}(t)}{\mathrm{d}t}\right)_{+}$
from a non-negative term. This observation leads to the the convergence of
$\tilde{\gamma}(t)$.

######  Lemma 3.

Suppose a function $\bm{v}$ obey an adaptive gradient flow $\mathcal{F}$,
which satisfies Assumption 1. Then the surrogate margin $\tilde{\gamma}(t)$
converges.

###  5.2 Convergence of Empirical Loss and Parameters

By Lemma 2, we have that for an adaptive gradient flow $\mathcal{F}$ with
Assumption 1, the norm $\rho(t)$ can be bounded as $\rho(t)\leq
e^{\frac{1}{2L}}g(\log(\frac{1}{\tilde{\mathcal{L}}(\bm{v}(t))}))^{\frac{1}{L}}$.
On the other hand, by chain rule, the derivative of empirical loss with
respect to time can be calculated as

$\displaystyle\frac{\mathrm{d}\tilde{\mathcal{L}}(\bm{v}(t))}{\mathrm{d}t}$
$\displaystyle=\langle\bar{\partial}\tilde{\mathcal{L}}(\bm{v}(t)),\frac{\mathrm{d}\bm{v}(t)}{\mathrm{d}t}\rangle=-\|\bm{\beta}^{\frac{1}{2}}(t)\odot\bar{\partial}\tilde{\mathcal{L}}(\bm{v}(t))\|^{2}\leq-\frac{\langle\bar{\partial}\tilde{\mathcal{L}}(\bm{v}(t)),\bm{v}(t)\rangle^{2}}{\rho(t)^{2}},$

where the last inequality is derived by the Cauchy inequality applying to
$\langle\bm{\beta}^{\frac{1}{2}}\odot\bar{\partial}\tilde{\mathcal{L}},\bm{\beta}^{-\frac{1}{2}}\odot\bm{v}\rangle$.
By the homogeneity of $\tilde{q}_{i}$, we can further lower bound
$\frac{\langle\bar{\partial}\tilde{\mathcal{L}},\bm{v}\rangle^{2}}{\rho^{2}}$
using $\tilde{\mathcal{L}}$. In other words, Lemma 2 ensures that the
decreasing rate of the empirical loss $\tilde{\mathcal{L}}$ can be lower
bounded by a function of itself. Based on the above methodology, we can prove
the following lemma and show that empirical loss will decrease to zero, while
parameter norm will converge to infinity.

######  Lemma 4.

Let a function $\bm{v}(t)$ satisfies an adaptive gradient flow $\mathcal{F}$
with loss $\tilde{\mathcal{L}}$ and component learning rate $\bm{\beta}(t)$,
where $\tilde{\mathcal{L}}$ satisfies Assumption 1. Then,
$\lim_{t\rightarrow\infty}\tilde{\mathcal{L}}(\bm{v}(t))=0$, and consequently,
$\lim_{t\rightarrow\infty}\|\bm{v}(t)\|=\infty$.

Here the proposition that parameter norm goes to infinity can be derived
naturally by empirical loss going to zero, since $f(\tilde{q}_{i}(\bm{v}))$ is
upper bounded within any bounded set of $\bm{v}$.

###  5.3 Convergence to KKT point

We start by proving for any $t\geq t_{1}$,
$\hat{\bm{v}}(t)=\frac{\bm{v}(t)}{\|\bm{v}(t)\|}$ is an approximate KKT point.
Based on the surrogate margin that we construct in Section 5.1, we can provide
a construction of coefficients $\lambda_{i}$ as follows:

######  Lemma 5.

Let $\hat{\bm{v}}$ and $\widehat{\bar{\partial}\tilde{\mathcal{L}}(\bm{v})}$
be $\bm{v}$ and $\bar{\partial}\tilde{\mathcal{L}}(\bm{v})$ respectively
normalized by their $L^{2}$ norms. Then $\hat{\bm{v}}(t)$ is a
$\left(\mathcal{O}(1-\langle\hat{\bm{v}}(t),\widehat{-\bar{\partial}\tilde{\mathcal{L}}(t)}\rangle),\mathcal{O}\left(\frac{1}{\log\frac{1}{\tilde{\mathcal{L}}(\bm{t})}}\right)\right)$
KKT point of optimization problem $(P)$ in Theorem 4.

We made some explanations to Lemma 5: by the results in Section 5.2, we have
$\lim_{t\rightarrow\infty}\mathcal{O}\left(\frac{1}{\log\frac{1}{\tilde{\mathcal{L}}(t)}}\right)=0$.
Therefore, we only need to find a convergent series $\tilde{\bm{v}}(t)$ with
$1+\langle\hat{\bm{v}}(t),\widehat{\bar{\partial}\tilde{\mathcal{L}}(t)}\rangle$
goes to zero.

For this purpose, we construct another approximate norm

$\tilde{\rho}(t)=\sqrt{\left\|\bm{\beta}^{-\frac{1}{2}}(t)\odot\bm{v}(t)\right\|^{2}-2\int_{t_{1}}^{t}\left\langle\bm{v}(\tau),\bm{\beta}^{-\frac{1}{2}}(\tau)\odot\frac{d\bm{\beta}^{-\frac{1}{2}}}{\mathrm{d}t}(\tau)\odot\bm{v}(\tau)\right\rangle}d\tau,$

which measures the increasing of $\bm{v}(t)$. Recall that we separate the
change of $\rho$ into two parts: change of $\bm{v}$ and change of $\bm{\beta}$
in order to prove that the surrogate margin is lower bounded. While keeping
the second part in $\tilde{\rho}(t)$, we combine the change of $\bm{v}$ (which
is $-\Theta(\frac{d\log\tilde{\rho}}{\mathrm{d}t})$) with the increasing of
$g(\log(\frac{1}{\mathcal{L}}))$ (which is
$\Theta(\frac{d\log\tilde{\rho}}{\mathrm{d}t}\langle\hat{v}(t),-\widehat{\bar{\partial}\tilde{\mathcal{L}}(t)}\rangle^{-2})$).
Combining the methodology above together, we have the following lemma:

######  Lemma 6.

For any $t_{3}>t_{2}\geq t_{1}$, there exists a $\xi\in[t_{2},t_{3}]$, such
that

$\displaystyle\left(\langle\hat{v}(\xi),-\widehat{\bar{\partial}\tilde{\mathcal{L}}(\xi)}\rangle^{-2}-1\right)(\log\tilde{\rho}(t^{2})-\log\tilde{\rho}(t^{1}))\leq$
$\displaystyle
C_{1}\log\frac{\tilde{\gamma}\left(t_{3}\right)}{\tilde{\gamma}\left(t_{2}\right)}$
$\displaystyle+$ $\displaystyle
C_{2}\sum_{i=1}^{p}\int_{t_{2}}^{t_{3}}\sum_{i=1}^{p}\left(\frac{\mathrm{d}\log\bm{\beta}^{-\frac{1}{2}}_{i}(t)}{\mathrm{d}t}\right)_{+}\mathrm{d}t,$
(7)

where $C^{1}$, $C^{2}$ are positive constants which is independent of $t_{2}$
and $t_{3}$.

The right side of inequality 7 is bounded and goes to zero as
$t_{2}\rightarrow\infty$ although
$\log\tilde{\rho}(t_{3})-\log\tilde{\rho}(t_{2})$ can be arbitrarily large,
which indicates that there exists $\xi\in[t_{2},t_{3}]$ that makes
$\left(\langle\hat{v}(\xi),-\widehat{\bar{\partial}\tilde{\mathcal{L}}(\xi)}\rangle^{-2}-1\right)$
is small enough, which is equivalent to
$\left(1-\langle\hat{v}(\xi),-\widehat{\bar{\partial}\tilde{\mathcal{L}}(\xi)}\rangle\right)$
is small enough.

However, $\xi$ is guaranteed by First Mean Value Theorem, and does not have a
close form. Therefore, we further introduce another lemma to bound
$\|\hat{\bm{v}}(\xi)-\hat{\bm{v}}(t_{2})\|$.

######  Lemma 7.

For any time $t\geq t_{1}$, we have that

$\left\|\frac{d\hat{\bm{v}}(t)}{\mathrm{d}t}\right\|\leq\frac{3\cdot
2^{L-1}}{(1-\frac{e^{\frac{1}{2}}}{2})}\frac{e^{\frac{1}{2}}B_{1}}{L}\frac{\mathrm{d}\log\tilde{\rho}}{\mathrm{d}t}\frac{1}{\tilde{\gamma}(t_{1})}.$

Combining Lemma 5, 6, and 7, for any convergent direction $\bar{\bm{v}}$, we
can construct a series of $\\{t_{i}\\}_{i=1}^{\infty}$, such that
$\hat{\bm{v}}(t_{i})$ is $(\varepsilon_{i},\delta_{i})$ KKT point, with
$\lim_{i\rightarrow\infty}\hat{\bm{v}}(t_{i})=\bar{\bm{v}}$, and
$\lim_{i\rightarrow\infty}\varepsilon_{i}=\lim_{i\rightarrow\infty}\delta_{i}=0$.
On the other hand, constraints of $(P)$ satisfies Mangasarian-Fromovitz
constraint qualification (see Appendix A.2), which ensures that $\bar{\bm{v}}$
is a KKT point of $(P)$, and complete the proof.

##  6 Discussions

###  6.1 RMSProp generalizes better than AdaGrad

In this section, we make some discussions on the results derived in section 4.

First, Theorem 6 and Theorem 5 shows that RMSProp implicitly bias the solution
to ones with maximized surrogate margin, while AdaGrad may drive the
parameters to a different direction. The corresponding optimization problem of
AdaGrad has a reliance on $\bm{h}_{\infty}$, which is shown to be sensitive to
the optimization path before convergence. Because the normalized margin is
used as a complexity norm in generalization literature (i.e., larger
normalized margin indicating better generalization performance) [2], we
conclude that RMSProp generalizes better than AdaGrad. This conclusion matches
the empirical observations [17].

Second, two key factors that guarantee generalization of RMSProp are
exponential weighted average strategy and the added constant $\epsilon$ in
$\bm{h}(t)$. Our results show the benefit of the two factors: it accelerates
the training process at early stage of optimization by adaptively adjusting
the learning rate, but it still converges to max margin solution because the
denominator of conditioner tends to constant $\epsilon$ at later stage. Most
of previous works explain $\epsilon$ to ensure positivity of $\bm{h}(t)$. Our
results show that $\epsilon$ is important for the convergent direction of the
parameters and the generalization ability. Our results also indicates
generalization guarantee for other adaptive optimization algorithms such as
Adam, AdamW which adopts the same design of $\bm{h}(t)$ with RMSProp.

###  6.2 Gap between continuous flow and discrete update rule

Our main results are proved for the continuous flow. In this section, we show
that the results can be extended to the discrete update rules.

As for the discrete case, two additional assumptions are needed as follows
(For brevity, we put the complete assumption to the appendix):

######  Assumption 2.

  1. I

(smooth). For any fixed $x$, $\Phi(\cdot;x)$ is $M$ smooth;

  2. II

(Learning Rate). For $t>t_{0}$, $\eta_{t}\leq C(t)$, where $C(t)$ is a non-
decreasing function. Also, $\eta_{t}$ is lower bounded by a positive real,
that is, there exists a constant $\tilde{\eta}>0$, such that, for any
$t>t_{0}$, $\eta_{t}\geq\tilde{\eta}$.

We make the following explanations for Assumption 2. Assumption 2(I) is needed
technically because we need to consider second order Taylor expansion around
each point along the training $\\{\bm{w}(t);t=1,\cdots,\\}$. Assumption 2(II)
guarantees that the second order Taylor expansion is upper bounded and the
step size is not too small. With Assumption 2, we can get the main results in
section 4.5 for discrete update rules of AdaGrad and RMSProp. The proof of
discrete case bears great similarity with the continuous case, and we defer
them to Appendix D.

###  6.3 Definability can guarantee convergence of direction

Note that Theorems 4, 5, and 6 do not guarantee the uniqueness of convergent
direction. To solve this problem, we introduce one additional assumption as
follows:

######  Assumption 3.

For any $i$, $q_{i}$ is definable in some o-minimal structure including the
exponential function;

We defer the formal definition of definable to Appendix C, but point out here
that Assumption 3(I) allows for linear, ReLU, polynomial activations, max
pooling and convolutional layers, and skip connections. Furthermore, for
locally Lipchitz definable function, chain rule holds almost everywhere (Lemma
13). With Assumption 1 and Assumption 1, we can prove direction of parameters
does converge:

######  Theorem 7.

Let $\bm{v}$ satisfy an adaptive gradient flow $\mathcal{F}$ which satisfies
Assumption 3. Then $\\{\hat{\bm{v}}(t)\\}$ converges.

The proof can be derived by bounding the curve length of
$\\{\hat{\bm{v}}(t)\\}$ using $\tilde{\gamma}(t)$ and Kurdyka-Lojasiewicz
inequality, and we defer the details to Appendix C.

##  7 Conclusion

In this paper, we study the convergent direction of AdaGrad and RMSProp on
homogeneous deep neural networks with the logistic loss. We prove RMSProp will
converge to the KKT points of the $L^{2}$ max margin problem, while AdaGrad
does not. The main technical contribution of this paper is to propose a
general framework for analyses of adaptive optimization algorithms’ convergent
direction. In future, the following topics regarding implicit bias of
optimization algorithms are deserved to investigate.

  * •

How does momentum influence the convergent direction of parameters? With
momentum term, optimization algorithms may have an update with direction quite
different from negative gradient. Therefore, whether the empirical loss is
decreasing with respect to iterations for optimization algorithms with
momentum is not been studied yet.

  * •

How does regularization techniques such as weight decay influence the
convergent direction of parameters? In practice, regularized losses are more
popular, which may have an optimal point with finite norm. It will be
interesting to investigate implicit bias of optimizers in this circumstance.

## References

  * [1] S. Arora, S. S. Du, W. Hu, Z. Li, R. R. Salakhutdinov, and R. Wang.  On exact computation with an infinitely wide neural net.  In Advances in Neural Information Processing Systems, pages 8141–8150, 2019.
  * [2] P. Bartlett and J. Shawe-Taylor.  Generalization performance of support vector machines and other pattern classifiers.  Advances in Kernel methods—support vector learning, pages 43–54, 1999.
  * [3] A. Brutzkus, A. Globerson, E. Malach, and S. Shalev-Shwartz.  Sgd learns over-parameterized networks that provably generalize on linearly separable data.  arXiv preprint arXiv:1710.10174, 2017.
  * [4] A. Choromanska, M. Henaff, M. Mathieu, G. B. Arous, and Y. LeCun.  The loss surfaces of multilayer networks.  In Artificial intelligence and statistics, pages 192–204, 2015\.
  * [5] L. Deng, G. Hinton, and B. Kingsbury.  New types of deep neural network learning for speech recognition and related applications: An overview.  In 2013 IEEE international conference on acoustics, speech and signal processing, pages 8599–8603. IEEE, 2013.
  * [6] J. Duchi, E. Hazan, and Y. Singer.  Adaptive subgradient methods for online learning and stochastic optimization.  Journal of machine learning research, 12(7), 2011.
  * [7] S. Gunasekar, J. Lee, D. Soudry, and N. Srebro.  Characterizing implicit bias in terms of optimization geometry.  arXiv preprint arXiv:1802.08246, 2018.
  * [8] S. Gunasekar, J. D. Lee, D. Soudry, and N. Srebro.  Implicit bias of gradient descent on linear convolutional networks.  In Advances in Neural Information Processing Systems, pages 9461–9471, 2018.
  * [9] G. Hinton, N. Srivastava, and K. Swersky.  Neural networks for machine learning lecture 6a overview of mini-batch gradient descent.  Cited on, 14(8), 2012.
  * [10] Z. Ji and M. Telgarsky.  Gradient descent aligns the layers of deep linear networks.  arXiv preprint arXiv:1810.02032, 2018.
  * [11] Z. Ji and M. Telgarsky.  The implicit bias of gradient descent on nonseparable data.  In Conference on Learning Theory, pages 1772–1798, 2019.
  * [12] Z. Ji and M. Telgarsky.  Directional convergence and alignment in deep learning.  arXiv preprint arXiv:2006.06657, 2020.
  * [13] D. P. Kingma and J. Ba.  Adam: A method for stochastic optimization.  arXiv preprint arXiv:1412.6980, 2014.
  * [14] K. Kurdyka.  On gradients of functions definable in o-minimal structures.  In Annales de l’institut Fourier, volume 48, pages 769–783, 1998\.
  * [15] Y. Li, E. X. Fang, H. Xu, and T. Zhao.  Implicit bias of gradient descent based adversarial training on separable data.  In International Conference on Learning Representations, 2019.
  * [16] I. Loshchilov and F. Hutter.  Decoupled weight decay regularization.  arXiv preprint arXiv:1711.05101, 2017.
  * [17] L. Luo, Y. Xiong, Y. Liu, and X. Sun.  Adaptive gradient methods with dynamic bound of learning rate.  arXiv preprint arXiv:1902.09843, 2019.
  * [18] K. Lyu and J. Li.  Gradient descent maximizes the margin of homogeneous neural networks.  arXiv preprint arXiv:1906.05890, 2019.
  * [19] M. S. Nacson, S. Gunasekar, J. D. Lee, N. Srebro, and D. Soudry.  Lexicographic and depth-sensitive margins in homogeneous and non-homogeneous deep models.  arXiv preprint arXiv:1905.07325, 2019.
  * [20] M. S. Nacson, J. Lee, S. Gunasekar, P. H. P. Savarese, N. Srebro, and D. Soudry.  Convergence of gradient descent on separable data.  In The 22nd International Conference on Artificial Intelligence and Statistics, pages 3420–3428. PMLR, 2019.
  * [21] M. S. Nacson, N. Srebro, and D. Soudry.  Stochastic gradient descent on separable data: Exact convergence with a fixed learning rate.  In The 22nd International Conference on Artificial Intelligence and Statistics, pages 3051–3059. PMLR, 2019.
  * [22] B. Neyshabur, R. R. Salakhutdinov, and N. Srebro.  Path-sgd: Path-normalized optimization in deep neural networks.  In Advances in Neural Information Processing Systems, pages 2422–2430, 2015.
  * [23] Q. Qian and X. Qian.  The implicit bias of adagrad on separable data.  In Advances in Neural Information Processing Systems, pages 7761–7769, 2019.
  * [24] S. Ruder.  An overview of gradient descent optimization algorithms.  arXiv preprint arXiv:1609.04747, 2016.
  * [25] D. Soudry, E. Hoffer, M. S. Nacson, S. Gunasekar, and N. Srebro.  The implicit bias of gradient descent on separable data.  The Journal of Machine Learning Research, 19(1):2822–2878, 2018\.
  * [26] A. Voulodimos, N. Doulamis, A. Doulamis, and E. Protopapadakis.  Deep learning for computer vision: A brief review.  Computational intelligence and neuroscience, 2018, 2018.
  * [27] A. C. Wilson, R. Roelofs, M. Stern, N. Srebro, and B. Recht.  The marginal value of adaptive gradient methods in machine learning.  In Advances in neural information processing systems, pages 4148–4158, 2017.
  * [28] I. H. Witten, E. Frank, M. A. Hall, and C. J. Pal.  Data Mining: Practical machine learning tools and techniques.  Morgan Kaufmann, 2016.
  * [29] T. Xu, Y. Zhou, K. Ji, and Y. Liang.  When will gradient methods converge to max-margin classifier under relu models?  arXiv preprint arXiv:1806.04339, 2018.
  * [30] T. Young, D. Hazarika, S. Poria, and E. Cambria.  Recent trends in deep learning based natural language processing.  ieee Computational intelligenCe magazine, 13(3):55–75, 2018.
  * [31] P. Zhou, J. Feng, C. Ma, C. Xiong, S. HOI, et al.  Towards theoretically understanding why sgd generalizes better than adam in deep learning.  arXiv preprint arXiv:2010.05627, 2020.
  * [32] J. Zhuang, T. Tang, S. Tatikonda, N. Dvornek, Y. Ding, X. Papademetris, and J. S. Duncan.  Adabelief optimizer: Adapting stepsizes by the belief in observed gradients.  arXiv preprint arXiv:2010.07468, 2020.

##  Appendix A Preliminaries

###  A.1 Property of Exponential and Logistic Loss

In this subsection, we prove several properties which both exponential and
logistic loss possess. The properties of exponential and logistic loss can be
described as the following Lemma.

######  Lemma 8.

For $\ell\in\\{\ell_{exp},\ell_{\log}\\}$:

  * •

There exists a $C^{1}$ function $f$, such that $\ell=e^{-f}$;

  * •

For any $x\in\mathbb{R}$, $f^{\prime}>0$. Therefore, $f$ is reversible, and
$f^{-1}\in C^{1}$;

  * •

$f^{\prime}(x)x$ is non-decreasing for $x\in(0,\infty)$, and
$\lim_{x\rightarrow\infty}f^{\prime}(x)x=\infty$;

  * •

There exists a large enough $x_{f}$ and a constant $K\geq 1$ ,such that,

    * –

$\forall\theta\in[\frac{1}{2},1),$ $\forall x\in(x_{f},\infty)$, and $\forall
y\in f^{-1}(x_{f},\infty)$: $(f^{-1})^{\prime}(x)\leq
K(f^{-1})^{\prime}(\theta x)$ and $f^{\prime}(y)\leq Kf^{\prime}(\theta y)$;

    * –

For all $y\in[x_{f},\infty)$,
$\frac{f(x)}{f^{\prime}(x)}\in[\frac{1}{2K}x,2Kx]$;

    * –

For all $x\in[f^{-1}(x_{f}),\infty)$,
$\frac{f^{-1}(x)}{(f^{-1})^{\prime}(x)}\in[\frac{1}{2K}x,2Kx]$.

    * –

$f(x)=\Theta(x)$ as $x\rightarrow\infty$.

All the properties are easy to verify in Lemma 8 and we omit it here. For
brevity, we will use $g(x)=f^{-1}(x)$ in the following proofs.

###  A.2 KKT Condition

Being a KKT point is a first order necessary condition for being an optimal
point. We first give the definition of approximate KKT point for general
optimization problem $(Q)$.

######  Definition 3.

Consider the following optimization problem $(Q)$ for
$\bm{x}\in\mathbb{R}^{d}$:

$\displaystyle\min f(\bm{x})$ $\displaystyle\text{subject to }g_{i}(x)\leq
0,\forall i\in[N],$

where $f,g_{i}$ ($i=1,\cdots,N$): $\mathbb{R}^{d}\rightarrow\mathbb{R}$ are
locally Lipschitz functions. We say that $x\in\mathbb{R}^{d}$ is a feasible
point of $(P)$ if $x$ satisfies $g_{i}(x)\leq 0$ for all $i\in[N]$.

For any $\varepsilon,\delta>0$, a feasible point of $(Q)$ is an
$(\varepsilon,\delta)$-KKT point if there exists $\lambda_{i}\geq 0$,
$\mathbf{k}\in\partial^{\circ}f(\bm{x})$, and
$\bm{h}_{i}\in\partial^{\circ}g_{i}(\bm{x})$ for all $i\in[N]$ such that

1\.
$\left\|\bm{k}+\sum_{i\in[N]}\lambda_{i}\bm{h}_{i}(\bm{x})\right\|_{2}\leq\varepsilon$;

2\. $\forall i\in[N]:\lambda_{i}g_{i}(\bm{x})\geq-\delta$.

Specifically, when $\varepsilon=\delta=0$, we call $\bm{x}$ a KKT point of
$(Q)$.

The following Mangasarian-Fromovitz constraint qualification (MFCQ) bridges
$(\varepsilon,\delta)$ KKT points with KKT points.

######  Definition 4.

A feasible point $x$ of $(Q)$ is said to satisfy MFCQ if there exists
$\bm{a}\in\mathbb{R}^{d}$ such that for every $i\in[N]$ with $g_{i}(x)=0$,

$\forall\bm{h}\in\partial^{\circ}g_{i}(\bm{x}):\langle\bm{h},\bm{a}\rangle>0.$

The MFCQ guarantees the limit of approximate KKT point with convergent
$\varepsilon$ and $\delta$ is a KKT point.

######  Lemma 9.

Suppose for any $k\in\mathbb{N}$ $x_{k}$ is a
$(\varepsilon_{k},\delta_{k})$-KKT point of $(Q)$ defined in Definition 3. If
$\lim_{k\rightarrow\infty}\varepsilon_{k}=0$,
$\lim_{k\rightarrow\infty}\delta_{k}=0$, and
$\lim_{k\rightarrow\infty}x_{k}=x$, where the limit point $x$ satisfies MFCQ,
then $x$ is a KKT point of $(Q)$.

In our setting, the constraints $g_{i}$ is $1-\tilde{q}_{i}$, and by the
homogeneity of $\tilde{q}_{i}$, we can easily verify that every feasible point
of $(P)$ satisfies MFCQ.

###  A.3 How is the Continuous Form of Conditioner Formulated?

In this subsection, we explain the relationship between conditioners of the
discrete case and the continuous case. As for AdaGrad,

$\bm{h}(t+1)^{-2}-\bm{h}(t)^{-2}=\bar{\partial}\mathcal{L}(\bm{w}(t))^{2},$

which is apparently a discretization of

$\frac{d\bm{h}(t)^{-2}}{\mathrm{d}t}=\bar{\partial}\mathcal{L}(\bm{w}(t))^{2}.$

As for RMSProp, the discrete update can be written as

$\bm{h}(t+1)^{-2}-\bm{h}(t)^{-2}=(1-b)(\bar{\partial}\mathcal{L}(\bm{w}(t))^{2}-\bm{h}(t)^{-2}),$

which is a discretization of

$\frac{d\bm{h}(t)^{-2}}{\mathrm{d}t}=(1-b)(\bar{\partial}\mathcal{L}(\bm{w}(t))^{2}-\bm{h}(t)^{-2}).$

By solving the above differential equation, we have

$\frac{\mathrm{d}e^{(1-b)t}\bm{h}(t)^{-2}}{\mathrm{d}t}=e^{(1-b)t}(1-b)\bar{\partial}\mathcal{L}(\bm{w}(t))^{2},$

which implies by integration

$\bm{h}(t)^{-2}=\varepsilon+\int_{0}^{t}e^{-(1-b)(t-\tau)}(1-b)\bar{\partial}\mathcal{L}(\bm{w}(\tau))^{2}\mathrm{d}\tau,$

which is exactly $\bm{h}^{R}$.

###  A.4 o-Minimal Structure and Definable functions

Here we define o-Minimal structure and definable functions which we omit in
Assumption 3.

######  Definition 5 (Appendix B, [12]).

An o-minimal structure is a collection
$\mathcal{S}=\\{\mathcal{S}_{n}\\}_{n=1}^{\infty}$, where each
$\mathcal{S}_{n}$ is a set of subsets of $\mathbb{R}_{n}$ satisfying the
following conditions: 1\. $\mathcal{S}_{1}$ is the collection of all finite
unions of open intervals and points;
2\. $\mathcal{S}_{n}$ includes the zero sets of all polynomials on
$\mathbb{R}_{n}$;
3\. $\mathcal{S}_{n}$ is closed under finite union, finite intersection, and
complement;
4\. $\mathcal{S}$ is closed under Cartesian products: if $A\in\mathcal{S}_{m}$
and $B\in\mathcal{S}_{n}$, then $A\times B\in\mathcal{S}_{m+n}$;
5\. $\mathcal{S}$ is closed under projection $\Pi_{n}$ onto the first $n$
coordinates: if $A\in\mathcal{S}_{n+1}$, then $\Pi_{n}(A)\in\mathcal{S}_{n}$.

A definable function on above o-Minimal Structure can be defined as follows:

######  Definition 6 (Appendix B, [12]).

A function $f:D\rightarrow\mathbb{R}^{m}$ with $D\subset\mathbb{R}^{n}$ is
definable if the graph of $f$ is in $\mathcal{S}_{n+m}$.

A natural question is: which function is definable? The next Lemma helps to
solve this question.

######  Lemma 10 (Lemma B.2, [12]).

  * •

All polynomials are definable, therefore, linear or other polynomial
activation is definable;

  * •

If both $f(x)$ and $g(x)$ are definable, $\min{f(x),g(x)}$ and
$\max{f(x),g(x)}$ are definable, therefore, ReLU activation is definable;

  * •

If $f_{i}(x):D\rightarrow\mathbb{R}$ ($i=1,2,\cdots,n$) is definable, then
$\bm{f}(x)=(f_{1}(x),f_{2}(x),\cdots,f_{n}(x))$ is definable.

  * •

Suppose there exists $k,d_{0},d_{1},\cdots,d_{L}>0$, and $L$ definable
functions $(g_{1},g_{2},\cdots,g_{L})$, where
$g_{j}:\rightarrow\mathbb{R}^{d_{0}}\times\cdots\times\mathbb{R}^{d_{j-1}}\times\mathbb{R}^{k}\rightarrow\mathbb{R}^{d_{j}}$.
Let $h_{1}(x,W)\overset{\triangle}{=}g_{1}(x,W)$, and for $2\leq j\leq L$,

$h_{j}(x,W):=g_{j}\left(x,h_{1}(x,W),\ldots,h_{j-1}(x,W),W\right),$

then all $h_{j}$ are definable. Therefore, neural networks with polynomial and
ReLU activation, convolutional and max-pooling layers, and skip connections
are definable.

An important property for definable function is Kurdyka-Lojasiewicz
inequality, which can bound gradient of definable function in a small region.
Here we present two Kurdyka-Lojasiewicz inequalities given by [12]:

######  Lemma 11 (Lemma 3.6, [12]).

Given a locally Lipschitz definable function $f$ with an open domain
$D\in\\{x|\|x\|>1\\}$, for any $c$, $\eta>0$, there exists $a>0$ and a
definable desingularizing function $\Psi$ on $[0,a)$ (that is, $\Psi(x)\in
C^{1}((0,a))\cap C^{0}([0,a))$ with $\Psi(0)=0$), such that,

$\Psi^{\prime}(f(x))\|x\|\|\bar{\partial}f(x)\|\geq 1,\text{ if
}f(x)\in(0,a),\text{ and }\left\|\bar{\partial}_{\perp}f(x)\right\|\geq
c\|x\|^{\eta}\left\|\bar{\partial}_{\backslash\backslash}f(x)\right\|.$

######  Lemma 12 (Lemma 3.7, [12]).

Given a locally Lipschitz definable function $f$ with an open domain
$D\subset\\{x|\|x\|>1\\}$, for any $\lambda>0$, there exists $a>0$, and a
definable desingularizing function $\Psi$ on $[0,a)$ such that

$\max\left\\{1,\frac{2}{\lambda}\right\\}\Psi^{\prime}(f(x))\|x\|^{1+\lambda}\|\bar{\partial}f(x)\|\geq
1,\text{ if }f(x)\in(0,a).$

###  A.5 Locally Lipchitz Definable Functions Admit Chain Rule

Assumption 3 actually guarantees that $\Phi$ admits a chain rule, which is
formally stated as following:

######  Lemma 13 (Lemma B.9, [12]).

Given a locally Lipschitz definable $f:D\rightarrow\mathbb{R}$ with an open
domain $D$, for any interval $I$ and any arc $z:I\rightarrow D$, it holds for
a.e. $t\in I$ that

$\frac{\mathrm{d}f\left(z_{t}\right)}{\mathrm{d}t}=\left\langle
z_{t}^{*},\frac{\mathrm{d}z_{t}}{\mathrm{d}t}\right\rangle,\quad\text{ for all
}z_{t}^{*}\in\partial f\left(z_{t}\right).$

##  Appendix B Proof of AdaGrad Flow and RMSProp Flow

###  B.1 Proof of Lemma 2 and 3

We first prove Lemma 2. The claim of Lemma 2 can be split into two parts:
convergence of $\bm{h}_{1}(t)$ and construction of $\bm{v}^{A}$,
$\bm{\beta}^{A}$, and $\tilde{\mathcal{L}}^{A}$.

######  Lemma 14.

For AdaGrad flow defined as eq. (4) with $\bm{h}=\bm{h}^{A}$,

$\int_{0}^{\infty}(\bar{\partial}\mathcal{L}(\bm{w}(t)))_{i}^{2}\mathrm{d}\tau<\infty,i=1,\cdots,p.$

###### Proof.

We use reduction of absurdity. If there exists an $i$, such that,
$\int_{0}^{\infty}g_{i}(\tau)^{2}\mathrm{d}\tau$ diverges, by equivalence of
integral convergence, then

$\int_{0}^{\infty}\frac{(\bar{\partial}\mathcal{L}(\bm{w}(t)))_{i}^{2}}{\varepsilon+\int_{0}^{t}(\bar{\partial}\mathcal{L}(\bm{w}(\tau)))_{i}^{2}\mathrm{d}\tau}\mathrm{d}t=\infty.$

Since
$\int_{0}^{\infty}(\bar{\partial}\mathcal{L}(\bm{w}(\tau)))_{i}^{2}\mathrm{d}\tau=\infty$,
when $t$ is large enough,

$\varepsilon+\int_{0}^{t}(\bar{\partial}\mathcal{L}(\bm{w}(\tau)))_{i}^{2}\mathrm{d}\tau>\sqrt{\varepsilon+\int_{0}^{t}(\bar{\partial}\mathcal{L}(\bm{w}(\tau)))_{i}^{2}}\mathrm{d}\tau.$

Therefore,

$\int_{0}^{\infty}\frac{(\bar{\partial}\mathcal{L}(\bm{w}(t)))_{i}^{2}}{\sqrt{\varepsilon+\int_{0}^{t}(\bar{\partial}\mathcal{L}(\bm{w}(\tau)))_{i}^{2}\mathrm{d}\tau}}\mathrm{d}t=\infty.$

However,

$\displaystyle\mathcal{L}(\bm{w}(0))-\mathcal{L}(\bm{w}(t))$
$\displaystyle=\int_{0}^{t}\langle\bar{\partial}\mathcal{L}(\bm{w}(t)),\bm{h}^{A}(t)\odot\bar{\partial}\mathcal{L}(\bm{w}(t))\rangle\mathrm{d}t$
$\displaystyle=\sum_{i=1}^{p}\int_{0}^{t}\frac{(\bar{\partial}\mathcal{L}(\bm{w}(t)))_{i}^{2}}{\sqrt{\varepsilon+\int_{0}^{t}(\bar{\partial}\mathcal{L}(\bm{w}(\tau)))_{i}^{2}\mathrm{d}\tau}}\mathrm{d}t$
$\displaystyle=\infty,$

which leads to a contradictory, since
$\mathcal{L}(\bm{\omega}(0))-\mathcal{L}(\bm{\omega}(t))$ is upper bounded by
$\mathcal{L}(\bm{\omega}(0))$.

The proof is completed. ∎

######  Lemma 15.

Define $\bm{h}_{\infty}=\lim_{t\rightarrow\infty}\bm{h}^{A}(t)$. Let

$\displaystyle\bm{v}^{A}(t)=\bm{h}_{\infty}^{-1/2}\odot\bm{w}(t),$
$\displaystyle\bm{\beta}^{A}(t)=\bm{h}_{\infty}^{-1}\odot\bm{h}^{A}(t),$
$\displaystyle\tilde{\mathcal{L}}^{A}(\bm{v})=\mathcal{L}(\bm{h}_{\infty}^{\frac{1}{2}}\odot\bm{v}).$

We have

$\frac{\mathrm{d}\bm{v}^{A}(t)}{\mathrm{d}t}=-\bm{\beta}^{A}(t)\odot\bar{\partial}\tilde{\mathcal{L}}^{A}(\bm{v}^{A}(t)),$
(8)

$\lim_{t\rightarrow\infty}\bm{\beta}^{A}(t)=1$, and
$\frac{\mathrm{d}\log\bm{\beta}^{A}(t)}{\mathrm{d}t}$ is Lebesgue integrable.

###### Proof.

We prove 8 by direct calculation.

$\displaystyle\frac{\mathrm{d}\bm{v}^{A}(t)}{\mathrm{d}t}$
$\displaystyle=\bm{h}_{\infty}^{-1/2}\odot\frac{d\bm{w}(t)}{\mathrm{d}t}$
$\displaystyle=-\bm{h}_{\infty}^{-1/2}\odot\bm{h}^{A}(t)\odot\bar{\partial}\mathcal{L}(\bm{w}(t))$
$\displaystyle=-\bm{h}_{\infty}^{-1/2}\odot\bm{h}^{A}(t)\odot\bm{h}_{\infty}^{-1/2}\odot\bm{h}_{\infty}^{1/2}\odot\bar{\partial}_{\bm{w}}\tilde{\mathcal{L}}^{A}(\bm{h}_{\infty}^{-1/2}\odot\bm{w}(t))$
$\displaystyle=-\bm{\beta}^{A}(t)\odot\bar{\partial}_{\bm{h}_{\infty}^{-1/2}\odot\bm{w}(t)}\tilde{\mathcal{L}}^{A}(\bm{h}_{\infty}^{-1/2}\odot\bm{w}(t))$
$\displaystyle=-\bm{\beta}^{A}(t)\odot\bar{\partial}_{\bm{v}(t)}\tilde{\mathcal{L}}^{A}(\bm{v}(t)),$

which completes the proof 8.

The last two claims can be derived directly by convergence of $\bm{h}^{A}(t)$
and non-increasing monotonicity of $\bm{\beta}^{A}(t)$.

∎

As for RMSProp flow, the convergence of $\bm{h}^{R}$ requires more effort. We
start from the following lemma, which bound
$F_{i}(t)\overset{\triangle}{=}\int_{0}^{t}(1-b)b^{t-\tau}(\bar{\partial}\mathcal{L}(\bm{w}(t)))_{i}^{2}\mathrm{d}\tau$.

######  Lemma 16.

For RMSProp flow defined as eq. (4) with $\bm{h}=\bm{h}^{R}$ , $F_{i}(t)$ is
bounded ($i=1,2,\cdots,p$), that is,

$\overline{\lim}_{t\rightarrow\infty}F_{i}(t)<\infty.$

###### Proof.

When $b=1$, $F_{i}(t)=0$ for all $t$ and $i$, which trivially yields the
claim. When $b\neq 1$, we use reduction of absurdity. If there exists an $i$,
such that, $\overline{\lim}_{t\rightarrow\infty}F_{i}(t)=\infty$, then
$t_{k}\overset{\triangle}{=}\inf\\{t:F_{i}(t)\geq k\\}<\infty$ holds.
Furthermore, since $\mathcal{L}$ is locally lipchitz with respect to $\bm{w}$,
$g_{i}(t)$ is locally bounded for any $t$, which leads to the absolute
continuity of $F_{i}$. Therefore, since $F_{i}(0)=0$, $t_{k}$ monotonously
increases.

Therefore, we have that

$\displaystyle\int_{t_{k}}^{t_{k+1}}\frac{(\bar{\partial}\mathcal{L}(\bm{w}(t)))_{i}^{2}}{\sqrt{\varepsilon+F_{i}(t)}}\mathrm{d}t$
$\displaystyle\geq\int_{t_{k}}^{t_{k+1}}\frac{(\bar{\partial}\mathcal{L}(\bm{w}(t)))_{i}^{2}}{\sqrt{\varepsilon+k+1}}\mathrm{d}t$
$\displaystyle=\frac{1}{\sqrt{\varepsilon+k+1}}\int_{t_{k}}^{t_{k+1}}(\bar{\partial}\mathcal{L}(\bm{w}(t)))_{i}^{2}\mathrm{d}t$
$\displaystyle\geq\frac{1}{\sqrt{\varepsilon+k+1}}\int_{t_{k}}^{t_{k+1}}(1-b)e^{-(1-b)(t_{k+1}-t)}(\bar{\partial}\mathcal{L}(\bm{w}(t)))_{i}^{2}\mathrm{d}t$
$\displaystyle=\frac{1-b}{\sqrt{\varepsilon+k+1}}(F_{i}(t_{k+1})-e^{-(1-b)(t_{k+1}-t_{k})}F_{i}(t_{k}))$
$\displaystyle\geq\frac{1-b}{\sqrt{\varepsilon+k+1}}(k-e^{-(1-b)(t_{k+1}-t_{k})}(k-1))$
$\displaystyle\geq\frac{1-b}{\sqrt{\varepsilon+k+1}}.$

Adding all $k\geq K$, we then have

$\mathcal{L}(t_{K})\geq\int_{t_{K}}^{\infty}\frac{(\bar{\partial}\mathcal{L}(\bm{w}(t)))_{i}^{2}}{\sqrt{\varepsilon+F_{i}(t)}}\mathrm{d}t=\infty,$

which leads to a contradictory.

The proof is completed. ∎

The next lemma shows that $\int_{0}^{\infty}g_{i}(t)^{2}\mathrm{d}t$
converges, which indicates that $\lim_{t\rightarrow\infty}F_{i}(t)=0$.

######  Lemma 17.

For RMSProp flow defined as eq. (4) with $\bm{h}=\bm{h}^{R}$ ,
$\int_{0}^{\infty}g_{i}(t)^{2}\mathrm{d}t$ converges ($i=1,2,\cdots,p$).
Consequently, $\lim_{t\rightarrow\infty}F_{i}(t)=0$ and
$\lim_{t\rightarrow\infty}\bm{h}^{R}(t)=\frac{1}{\sqrt{\varepsilon}}\mathbf{1}_{p}$.

###### Proof.

Similar to Lemma 16, when $b=1$, the claim trivially holds. When $b\neq 1$, by
Lemma 16, there exist $M_{i}>0$ $(i=1,2,\cdots,p)$, such that, $F_{i}(t)\leq
M_{i}$ for any $t>0$. Therefore,

$\mathcal{L}(0)\geq\sum_{i=1}^{p}\int_{0}^{\infty}\frac{(\bar{\partial}\mathcal{L}(\bm{w}(t)))_{i}^{2}}{\sqrt{\varepsilon+F_{i}(t)}}\mathrm{d}t\geq\sum_{i=1}^{p}\int_{0}^{\infty}\frac{(\bar{\partial}\mathcal{L}(\bm{w}(t)))_{i}^{2}}{\sqrt{M_{i}+\varepsilon}}\mathrm{d}t,$

which proves
$\int_{0}^{\infty}(\bar{\partial}\mathcal{L}(\bm{w}(t)))_{i}^{2}\mathrm{d}t<\infty$.

Therefore, for any positive real $\varepsilon>0$ and a fixed index $i\in[p]$,
there exists a time $T$, such that,

$\int_{t=T}^{\infty}(\bar{\partial}\mathcal{L}(\bm{w}(t)))_{i}^{2}\mathrm{d}t\leq\varepsilon.$

Thus, for any $t\geq T$,

$F_{i}(t)\leq e^{-(t-T)(1-b)}F_{i}(T)+\varepsilon,$

which leads to

$\overline{\lim}_{t\rightarrow\infty}F_{i}(t)\leq\varepsilon.$

Since $\varepsilon$ and $i$ can be picked arbitrarily, the proof is completed.
∎

Similar to the proof of Lemma 15, we can rewrite the RMSProp flow as

$\frac{\mathrm{d}\bm{v}^{R}(t)}{\mathrm{d}t}=-\bm{\beta}^{R}(t)\odot\bar{\partial}\tilde{\mathcal{L}}^{R}(\bm{v}^{R}(t)),$

where

$\displaystyle\bm{v}^{R}(t)=\sqrt[4]{\varepsilon}\bm{w}(t),$
$\displaystyle\bm{\beta}^{R}(t)=\sqrt{\varepsilon}\bm{h}(t),$
$\displaystyle\tilde{\mathcal{L}}^{R}(\bm{v})=\mathcal{L}(\sqrt[4]{\varepsilon^{-1}}\bm{v}),$

and $\lim_{t\rightarrow\infty}\bm{\beta}^{R}(t)=\mathbf{1}_{p}$. We only need
to prove $\frac{d\log\bm{\beta}^{R}(t)}{\mathrm{d}t}$ is Lebesgue integrable
in the rest of this subsection.

######  Lemma 18.

Let $(x)_{+}=x\mathbb{I}_{x>0}$, and $(x)_{-}=x\mathbb{I}_{x<0}$. Then, for
any $i=1,2,\cdots,p$, we have that

$\displaystyle\int_{0}^{\infty}\left(\frac{d\log\sqrt{\frac{\varepsilon+F_{i}(t)}{\varepsilon}}}{\mathrm{d}t}\right)_{+}\mathrm{d}t<\infty,$
$\displaystyle\int_{0}^{\infty}\left(\frac{d\log\sqrt{\frac{\varepsilon+F_{i}(t)}{\varepsilon}}}{\mathrm{d}t}\right)_{-}\mathrm{d}t>-\infty.$

###### Proof.

For any fixed $i=1,2,\cdots,p$, by Lemma 17,

$\int_{0}^{\infty}\frac{d\log\sqrt{\frac{\varepsilon+F_{i}(t)}{\varepsilon}}}{\mathrm{d}t}\mathrm{d}t=0.$

Since

$\int_{0}^{\infty}\frac{d\log\sqrt{\frac{\varepsilon+F_{i}(t)}{\varepsilon}}}{\mathrm{d}t}\mathrm{d}t=\int_{0}^{\infty}\left(\frac{d\log\sqrt{\frac{\varepsilon+F_{i}(t)}{\varepsilon}}}{\mathrm{d}t}\right)_{+}\mathrm{d}t+\int_{0}^{\infty}\left(\frac{d\log\sqrt{\frac{\varepsilon+F_{i}(t)}{\varepsilon}}}{\mathrm{d}t}\right)_{-}\mathrm{d}t,$

we only need to prove the convergence of
$\int_{0}^{\infty}\left(\frac{d\log\sqrt{\frac{\varepsilon+F_{i}(t)}{\varepsilon}}}{\mathrm{d}t}\right)_{+}\mathrm{d}t$.

For any $k\in\mathcal{Z}^{+}$, denote
$B_{k}=(k,k+1)\cap\\{t:\frac{d\log\sqrt{\frac{\varepsilon+F_{i}(t)}{\varepsilon}}}{\mathrm{d}t}>0\\}$.
Since
$\frac{d\log\sqrt{\frac{\varepsilon+F_{i}(t)}{\varepsilon}}}{\mathrm{d}t}$ is
measurable, we have that $B_{k}$ is a measurable set. Denote $M_{k}$ as an
upper bound for
$\frac{d\log\sqrt{\frac{\varepsilon+F_{i}(t)}{\varepsilon}}}{\mathrm{d}t}$ on
$[k,k+1)$ (which is guaranteed since $\mathcal{L}$ is locally Lipchitz ).
Since $B_{k}$ is a measurable set, there exists an open set
$\tilde{B}_{k}\subset(k,k+1)$, such that
$m(\tilde{B}_{k}/B_{k})\leq\frac{1}{k^{2}M_{k}}$, where $m$ is Lebesgue
measure on $\mathbb{R}$.

Therefore, we have

$\displaystyle\int_{t\in[k,k+1)}\left(\frac{d\log\sqrt{\frac{\varepsilon+F_{i}(t)}{\varepsilon}}}{\mathrm{d}t}\right)_{+}\mathrm{d}t=$
$\displaystyle\int_{t\in
B_{k}}\left(\frac{d\log\sqrt{\frac{\varepsilon+F_{i}(t)}{\varepsilon}}}{\mathrm{d}t}\right)\mathrm{d}t$
$\displaystyle\leq$
$\displaystyle\int_{t\in\tilde{B}_{k}}\left(\frac{d\log\sqrt{\frac{\varepsilon+F_{i}(t)}{\varepsilon}}}{\mathrm{d}t}\right)\mathrm{d}t+M_{k}\cdot\frac{1}{k^{2}M_{k}}$
$\displaystyle=$
$\displaystyle\int_{t\in\tilde{B}_{k}}\left(\frac{d\log\sqrt{\frac{\varepsilon+F_{i}(t)}{\varepsilon}}}{\mathrm{d}t}\right)\mathrm{d}t+\frac{1}{k^{2}}.$

Furthermore, let
$\tilde{B}_{k}=\cup_{j=1}^{\infty}(t_{k,j},t^{\prime}_{k,j})$. Then we have

$\displaystyle\int_{t\in\tilde{B}_{k}}\left(\frac{d\log\sqrt{\frac{\varepsilon+F_{i}(t)}{\varepsilon}}}{\mathrm{d}t}\right)\mathrm{d}t$
$\displaystyle=$
$\displaystyle\sum_{j=1}^{\infty}\int_{t_{k,j}}^{t^{\prime}_{k,j}}\frac{d\log\sqrt{\frac{\varepsilon+lF_{i}(t)}{\varepsilon}}}{\mathrm{d}t}\mathrm{d}t$
$\displaystyle=$
$\displaystyle\sum_{j=1}^{\infty}\left(\log\sqrt{\frac{\varepsilon+F_{i}(t_{k,j}^{\prime})}{\varepsilon}}-\log\sqrt{\frac{\varepsilon+F_{i}(t_{k,j})}{\varepsilon}}\right)$
$\displaystyle=$
$\displaystyle\frac{1}{2}\sum_{j=1}^{\infty}\log\frac{\varepsilon+F_{i}(t_{k,j}^{\prime})}{\varepsilon+F_{i}(t_{k,j})}$
$\displaystyle=$
$\displaystyle\frac{1}{2}\sum_{j=1}^{\infty}\log\frac{\varepsilon+e^{-(t_{k,j}^{\prime}-t_{k,j})(1-b)}F_{i}(t_{k,j})+\int_{t_{k,j}}^{t_{k,j}^{\prime}}(1-b)e^{-(t_{k,j}^{\prime}-t)(1-b)}(\bar{\partial}\mathcal{L}(\bm{w}(t)))_{i}^{2}\mathrm{d}t}{\varepsilon+F_{i}(t_{k,j})}$
$\displaystyle\leq$
$\displaystyle\frac{1}{2}\sum_{j=1}^{\infty}\log\frac{\varepsilon+F_{i}(t_{k,j})+\int_{t_{k,j}}^{t_{k,j}^{\prime}}(1-b)e^{-(t_{k,j}^{\prime}-t)(1-b)}(\bar{\partial}\mathcal{L}(\bm{w}(t)))_{i}^{2}\mathrm{d}t}{\varepsilon+F_{i}(t_{k,j})}$
$\displaystyle\leq$
$\displaystyle\frac{1}{2}\sum_{j=1}^{\infty}\frac{\int_{t_{k,j}}^{t_{k,j}^{\prime}}(1-b)e^{-(t_{k,j}^{\prime}-t)(1-b)}(\bar{\partial}\mathcal{L}(\bm{w}(t)))_{i}^{2}\mathrm{d}t}{\varepsilon+F_{i}(t_{k,j})}$
$\displaystyle\leq$
$\displaystyle\frac{1}{2}\sum_{j=1}^{\infty}\frac{\int_{t_{k,j}}^{t_{k,j}^{\prime}}(\bar{\partial}\mathcal{L}(\bm{w}(t)))_{i}^{2}\mathrm{d}t}{\varepsilon}$
$\displaystyle\leq$
$\displaystyle\frac{1}{2}\frac{\int_{t\in\tilde{B}_{k}}(\bar{\partial}\mathcal{L}(\bm{w}(t)))_{i}^{2}\mathrm{d}t}{\varepsilon}<\infty.$

The proof is completed. ∎

###  B.2 Proof of surrogate margin Lemmas: Lemma 1 and 2

In the beginning, we first prove that the normalized margin $\gamma$ is upper
bounded:

######  Lemma 19.

For any $\bm{v}\in\mathbb{R}^{p}/\\{\bm{0}\\}$, the normalized margin
$\gamma=\frac{\tilde{q}_{\min}(\bm{v})}{\|\bm{v}\|^{L}}$ and normalized
gradients $\frac{\bar{\partial}\tilde{q}_{i}(\bm{v})}{\|\bm{v}\|^{L-1}}$
($i=1,2,\cdots,p$) is upper bounded universally.

###### Proof.

By homogeneity of $\tilde{q}_{i}$ ($i=1,2,\cdots,p$), only parameters with
unit norm needed to be considered. That is,

$\displaystyle\left\\{\gamma(\bm{v}):\bm{v}\in\mathbb{R}^{p}/\\{\bm{0}\right\\}$
$\displaystyle=$ $\displaystyle\left\\{\gamma(\bm{v}):\|\bm{v}\|=1\right\\}.$

Since $\tilde{q}_{i}$ is continuous and $\\{\bm{v}:\|\bm{v}\|=1\\}$ is a
compact set, normalized margin is upper bounded.

Normalized gradients
$\frac{\bar{\partial}\tilde{q}_{i}(\bm{v})}{\|\bm{v}\|^{L-1}}$ are also
bounded following similar routine since $\tilde{q}_{i}$ is locally Lipchitz. ∎

We restate Lemma 1 as follows:

######  Lemma 20.

Let a function $\bm{v}(t)$ satisfy an adaptive gradient flow $\mathcal{F}$
which satisfies Assumption 1, with loss $\tilde{\mathcal{L}}$ and component
learning rate $\bm{\beta}(t)$. Then we have
$\lim_{t\rightarrow\infty}\frac{\rho(t)}{\|\bm{v}(t)\|}=1$. Furthermore, if
further $\lim_{t\rightarrow\infty}\tilde{\mathcal{L}}(t)=\infty$, we have
$\tilde{\gamma}(t)=\Theta(\gamma(t))$ and
$\lim_{t\rightarrow\infty}\frac{\gamma(t)}{\|\tilde{\gamma}(t)\|}=1$

###### Proof.

By the definition of approximate norm
$\rho(t)=\|\bm{\beta}(t)^{-\frac{1}{2}}\odot\bm{v}(t)\|$ and
$\lim_{t\rightarrow\infty}\bm{\beta}(t)=\mathbf{1}_{p}$, we have that

$1=\underline{\lim}_{t\rightarrow\infty}\min_{i}\bm{\beta}^{-\frac{1}{2}}_{i}(t)\leq\underline{\lim}_{t\rightarrow\infty}\frac{\rho(t)}{\|\bm{v}(t)\|}\leq\overline{\lim}_{t\rightarrow\infty}\frac{\rho(t)}{\|\bm{v}(t)\|}\leq\overline{\lim}_{t\rightarrow\infty}\max_{i}\bm{\beta}^{-\frac{1}{2}}_{i}(t)=1,$

which leads to $\lim_{t\rightarrow\infty}\frac{\rho(t)}{\|\bm{v}(t)\|}=1$.

By the definition of $\tilde{\mathcal{L}}(\bm{v})$, we have

$e^{-f(\tilde{q}_{\min}(\bm{v}))}\leq\tilde{\mathcal{L}}(\bm{v})=\sum_{i=1}^{N}e^{-f(\tilde{q}_{i}(\bm{v}))}\leq
Ne^{-f(\tilde{q}_{\min}(\bm{v}))}.$

Rearranging the above equation, we have

$\displaystyle\tilde{q}_{\min}(\bm{v})\geq
g\left(\log\frac{1}{\tilde{\mathcal{L}}(\bm{v})}\right)\geq
g(f(\tilde{q}_{\min}(\bm{v}))-\log N)$ $\displaystyle=$ $\displaystyle
g(f(\tilde{q}_{\min}(\bm{v})))-\log
Ng^{\prime}(\xi)=\tilde{q}_{\min}(\bm{v})-\log Ng^{\prime}(\xi),$

where $\xi\in(f(\tilde{q}_{\min}(\bm{v}))-\log
N,f(\tilde{q}_{\min}(\bm{v})))$.

Therefore, the surrogate margin can be bounded as

$\displaystyle\frac{\tilde{q}_{\min}(\bm{v}(t))-\log
Ng^{\prime}(\xi)}{\|\bm{v}(t)\|^{L}}\frac{\|\bm{v}(t)\|^{L}}{\rho(t)^{L}}=\frac{\tilde{q}_{\min}(\bm{v}(t))-\log
Ng^{\prime}(\xi)}{\rho(t)^{L}}$ $\displaystyle\leq$
$\displaystyle\tilde{\gamma}(t)\leq\frac{\tilde{q}_{\min}}{\rho(t)^{L}}=\gamma(t)\left(\frac{\|\bm{v}\|}{\rho(t)}\right)^{L}.$
(9)

By the assumption that $\lim_{t\rightarrow\infty}\tilde{\mathcal{L}}=0$, there
exists a large enough time $\tilde{t}$, such that, any time $t\geq\tilde{t}$,
$g(\xi)>0$. The left side of the above equation 9 can be further rearranged as

$\displaystyle\frac{\tilde{q}_{\min}(\bm{v}(t))-\log
Ng^{\prime}(\xi)}{\|\bm{v}(t)\|^{L}}\frac{\|\bm{v}(t)\|^{L}}{\rho(t)^{L}}=$
$\displaystyle\left(\gamma(t)-\frac{\log
Ng^{\prime}(\xi)}{\|\bm{v}(t)\|^{L}}\right)\frac{\|\bm{v}(t)\|^{L}}{\rho(t)^{L}}$
$\displaystyle=$ $\displaystyle\left(\gamma(t)-\frac{\log
Ng^{\prime}(\xi)g(\xi)}{\|\bm{v}(t)\|^{L}g(\xi)}\right)\frac{\|\bm{v}(t)\|^{L}}{\rho(t)^{L}}$
$\displaystyle\geq$ $\displaystyle\left(\gamma(t)-\frac{\log
Ng^{\prime}(\xi)\gamma(t)}{g(\xi)}\right)\frac{\|\bm{v}(t)\|^{L}}{\rho(t)^{L}}$
$\displaystyle=$ $\displaystyle\left(\gamma(t)-\frac{\log
N\gamma(t)}{g(\xi)f^{\prime}(g(\xi))}\right)\frac{\|\bm{v}(t)\|^{L}}{\rho(t)^{L}}.$

By the assumption that $\lim_{t\rightarrow\infty}\tilde{\mathcal{L}}(t)=0$,
$\underline{\lim}_{t\rightarrow\infty}\xi\geq\underline{\lim}_{t\rightarrow\infty}\log\frac{1}{\tilde{\mathcal{L}}(t)}-\log
N=\infty$, which further indicates
$\lim_{t\rightarrow\infty}g(\xi)f^{\prime}(g(\xi))=0$ by Lemma 8. The proof is
completed by taking $t$ to infinity of eq. (9).

∎

By Lemmas 19 and 20, we have that if
$\lim_{t\rightarrow\infty}\tilde{\mathcal{L}}(t)\rightarrow 0$,
$\tilde{\gamma}(t)$ is upper bounded. We then lower bound $\tilde{\gamma}(t)$
by proving Lemma 2. As a warm-up, we first calculate the derivative of
$\rho^{2}$.

######  Lemma 21.

The derivative of $\rho^{2}$ is as follows:

$\frac{1}{2}\frac{\mathrm{d}\rho(t)^{2}}{\mathrm{d}t}=L\nu(t)+\left\langle\bm{v}(t),\bm{\beta}^{-\frac{1}{2}}(t)\odot\frac{\mathrm{d}\bm{\beta}^{-\frac{1}{2}}}{\mathrm{d}t}(t)\odot\bm{v}(t)\right\rangle,$

where $\nu(t)$ is defined as
$\sum_{n=1}^{N}e^{-f\left(\tilde{q}_{i}(\bm{v}(t))\right)}f^{\prime}\left(\tilde{q}_{i}(\bm{v}(t))\right)\tilde{q}_{i}(\bm{v}(t))$.
Furthermore, we have that
$\nu(t)>\frac{g\left(\log\frac{1}{\tilde{\mathcal{L}}(\bm{v}(t))}\right)}{g^{\prime}\left(\log\frac{1}{\tilde{\mathcal{L}}(\bm{v}(t))}\right)}\tilde{\mathcal{L}}(\bm{v}(t))$.

###### Proof.

By taking derivative directly, we have that

$\displaystyle\frac{1}{2}\frac{d\rho(t)^{2}}{\mathrm{d}t}$
$\displaystyle=\left\langle\bm{\beta}^{-\frac{1}{2}}(t)\odot\bm{v}(t),\frac{\mathrm{d}\bm{\beta}(t)^{-\frac{1}{2}}\odot\bm{v}(t)}{\mathrm{d}t}\right\rangle$
$\displaystyle=\left\langle\bm{\beta}(t)^{-\frac{1}{2}}\odot\bm{v}(t),\bm{v}(t)\odot\frac{\mathrm{d}\bm{\beta}(t)^{-\frac{1}{2}}}{\mathrm{d}t}+\bm{\beta}(t)^{-\frac{1}{2}}\odot\frac{\mathrm{d}\bm{v}(t)}{\mathrm{d}t}\right\rangle$
$\displaystyle=-\left\langle\bm{v}(t),\bar{\partial}\tilde{\mathcal{L}}(\bm{v}(t))\right\rangle+\left\langle\bm{\beta}^{-\frac{1}{2}}(t)\odot\bm{v}(t),\bm{v}(t)\odot\frac{\mathrm{d}\bm{\beta}(t)^{-\frac{1}{2}}}{\mathrm{d}t}\right\rangle$
$\displaystyle\overset{(*)}{=}L\sum_{i=1}^{N}e^{-f\left(\tilde{q}_{i}(\bm{v}(t))\right)}f^{\prime}\left(\tilde{q}_{i}(\bm{v}(t))\right)\tilde{q}_{i}(\bm{v}(t))+\left\langle\bm{\beta}(t)^{-\frac{1}{2}}\odot\bm{v}(t),\bm{v}(t)\odot\frac{\mathrm{d}\bm{\beta}(t)^{-\frac{1}{2}}}{\mathrm{d}t}\right\rangle,$

where eq. $(*)$ comes from Homogeneity Assumption 1. I.

Furthermore, since
$\tilde{q}_{i}(\bm{v}(t))\geq\tilde{q}_{\min}(\bm{v}(t))\geq
g(\log\frac{1}{\tilde{\mathcal{L}}(\bm{v}(t))})$ for all $i\in[N]$ and
$f^{\prime}(x)x$ keeps increasing on $(0,\infty)$ by Lemma 8,

$f^{\prime}\left(\tilde{q}_{i}(\bm{v}(t))\right)\tilde{q}_{i}(\bm{v}(t))\geq
f^{\prime}\left(g\left(\log\frac{1}{\tilde{\mathcal{L}}(\bm{v}(t))}\right)\right)\cdot
g\left(\log\frac{1}{\tilde{\mathcal{L}}(\bm{v}(t))}\right)=\frac{g\left(\log\frac{1}{\tilde{\mathcal{L}}(\bm{v}(t))}\right)}{g^{\prime}\left(\log\frac{1}{\tilde{\mathcal{L}}(\bm{v}(t))}\right)}.$

Therefore,

$\displaystyle\sum_{i=1}^{N}e^{-f\left(\tilde{q}_{i}(\bm{v}(t))\right(\bm{v}(t)))}f^{\prime}\left(\tilde{q}_{i}(\bm{v}(t))\right)\tilde{q}_{i}(\bm{v}(t))$
$\displaystyle\geq$
$\displaystyle\frac{g\left(\log\frac{1}{\tilde{\mathcal{L}}(\bm{v}(t))}\right)}{g^{\prime}\left(\log\frac{1}{\tilde{\mathcal{L}}(\bm{v}(t))}\right)}\sum_{i=1}^{N}e^{-f\left(\tilde{q}_{i}(\bm{v}(t))\right)}=\frac{g\left(\log\frac{1}{\tilde{\mathcal{L}}(\bm{v}(t))}\right)}{g^{\prime}\left(\log\frac{1}{\tilde{\mathcal{L}}(\bm{v}(t))}\right)}\tilde{\mathcal{L}}(\bm{v}(t)).$

The proof is completed. ∎

With the estimation of $\frac{d\rho^{2}}{\mathrm{d}t}$ above, we come to the
proof of Lemma 2.

###### Proof of Lemma 2.

We first construct time $t_{1}$ as follows: by properties of $\bm{\beta}(t)$
in Definition 1, there exists some large enough time $t_{1}>t_{0}$, such that
for any $t>t_{1}$,

$\displaystyle\sum_{i=1}^{p}\int_{t_{1}}^{\infty}\left(\frac{\mathrm{d}\log\left(\bm{\beta}^{-\frac{1}{2}}_{i}(t)\right)}{\mathrm{d}t}\right)_{+}\leq\min\\{\frac{1}{2L},\frac{1}{4}\\},$
$\displaystyle\sum_{i=1}^{p}\int_{t_{1}}^{\infty}\left(\frac{\mathrm{d}\log\left(\bm{\beta}^{-\frac{1}{2}}_{i}(t)\right)}{\mathrm{d}t}\right)_{-}\geq-\min\\{\frac{1}{2L},\frac{1}{4}\\},$

and

$\frac{1}{2}\leq\|\bm{\beta}^{-\frac{1}{2}}(t)\|_{\infty}\leq\frac{3}{2}.$

Taking logarithmic derivative to $\tilde{\gamma}(\bm{v}(t))$, we have

$\displaystyle\frac{\mathrm{d}}{\mathrm{d}t}\log\tilde{\gamma}(t)$
$\displaystyle=$
$\displaystyle\frac{\mathrm{d}}{\mathrm{d}t}\left(\log\left(g\left(\log\frac{1}{\tilde{\mathcal{L}}(\bm{v}(t))}\right)\right)-L\log\rho(t)\right)$
$\displaystyle=$
$\displaystyle\frac{g^{\prime}\left(\log\frac{1}{\tilde{\mathcal{L}}(\bm{v}(t))}\right)}{g\left(\log\frac{1}{\tilde{\mathcal{L}}(\bm{v}(t))}\right)}\cdot\frac{1}{\tilde{\mathcal{L}}(\bm{v}(t))}\cdot\left(-\frac{\mathrm{d}\tilde{\mathcal{L}}(\bm{v}(t))}{\mathrm{d}t}\right)-L^{2}\cdot\frac{\nu(t)}{\rho(t)^{2}}-\frac{L\left\langle\bm{v}(t),\bm{\beta}^{-\frac{1}{2}}(t)\odot\frac{\mathrm{d}\bm{\beta}^{-\frac{1}{2}}}{\mathrm{d}t}(t)\odot\bm{v}(t)\right\rangle}{\rho(t)^{2}}.$

Let
$A=\frac{g^{\prime}\left(\log\frac{1}{\tilde{\mathcal{L}}(\bm{v}(t))}\right)}{g\left(\log\frac{1}{\tilde{\mathcal{L}}(\bm{v}(t))}\right)}\cdot\frac{1}{\tilde{\mathcal{L}}(\bm{v}(t))}\cdot\left(-\frac{\mathrm{d}\tilde{\mathcal{L}}(\bm{v}(t))}{\mathrm{d}t}\right)-L^{2}\cdot\frac{\nu(t)}{\rho(t)^{2}}$
and
$B=\frac{L\left\langle\bm{v}(t),\bm{\beta}^{-\frac{1}{2}}(t)\odot\frac{\mathrm{d}\bm{\beta}^{-\frac{1}{2}}}{\mathrm{d}t}(t)\odot\bm{v}(t)\right\rangle}{\rho(t)^{2}}$.
We then have

$\displaystyle A$
$\displaystyle\geq\frac{1}{\nu(t)}\cdot\left(-\frac{\mathrm{d}\tilde{\mathcal{L}}(\bm{v}(t))}{\mathrm{d}t}\right)-L^{2}\cdot\frac{\nu(t)}{\rho(t)^{2}}$
$\displaystyle\geq\frac{1}{\nu(t)}\cdot\left(-\frac{\mathrm{d}\tilde{\mathcal{L}}(\bm{v}(t))}{\mathrm{d}t}-\frac{L^{2}\nu(t)^{2}}{\rho(t)^{2}}\right)$
$\displaystyle=\frac{1}{\nu(t)}\left(\left\langle\frac{\mathrm{d}\bm{v}(t)}{\mathrm{d}t},\bm{\beta}(t)^{-1}\odot\frac{\mathrm{d}\bm{v}(t)}{\mathrm{d}t}\right\rangle-\left\langle\bm{\beta}(t)^{-\frac{1}{2}}\odot\frac{\mathrm{d}\bm{v}(t)}{\mathrm{d}t},\widehat{\bm{\beta}(t)^{-\frac{1}{2}}\odot\bm{v}(t)}\right\rangle^{2}\right)$
$\displaystyle=\frac{1}{\nu(t)}\left\|\left(\bm{I}-\left(\widehat{\bm{\beta}(t)^{-\frac{1}{2}}\odot\bm{v}(t)}\right)\left(\widehat{\bm{\beta}(t)^{-\frac{1}{2}}\odot\bm{v}(t)}\right)^{\top}\right)\bm{\beta}(t)^{-\frac{1}{2}}\odot\frac{\mathrm{d}\bm{v}(t)}{\mathrm{d}t}\right\|_{2}^{2}>0.$

As for $B$, we have that

$\displaystyle B$
$\displaystyle=-\frac{L\left\langle\bm{v}(t),\bm{\beta}^{-\frac{1}{2}}\odot\frac{\mathrm{d}\bm{\beta}^{-\frac{1}{2}}(t)}{\mathrm{d}t}(t)\odot\bm{v}(t)\right\rangle}{\rho^{2}}$
$\displaystyle=-L\frac{\sum_{i=1}^{p}v_{i}^{2}(t)\beta_{i}^{-\frac{1}{2}}(t)\frac{d\beta_{i}^{-\frac{1}{2}}(t)}{\mathrm{d}t}}{\sum_{i=1}^{p}v_{i}^{2}(t)\beta_{i}^{-1}(t)}$
$\displaystyle\geq-L\sum_{i=1}^{p}\left(\frac{\mathrm{d}\log\bm{\beta}^{-\frac{1}{2}}_{i}(t)}{\mathrm{d}t}\right)_{+}.$

Combining the estimation of $A$ and $B$, we then have

$\displaystyle\frac{\mathrm{d}}{\mathrm{d}t}\log\tilde{\gamma}\geq
A+B\geq-L\sum_{i=1}^{p}\left(\frac{\mathrm{d}\log\bm{\beta}^{-\frac{1}{2}}_{i}(t)}{\mathrm{d}\tau}\right)_{+},$
(10)

and integrating both sides leads to

$\log\tilde{\gamma}(t)-\log\tilde{\gamma}(t_{1})\geq-\frac{1}{2}.$

The proof is completed.

∎

By the proof of Lemma 3, we can then prove convergence of surrogate margin
$\tilde{\gamma}$.

###### Proof of 3.

By eq. (10),
$\log\tilde{\gamma}(t)+\int_{t_{1}}^{t}L\sum_{i=1}^{p}\left(\frac{\mathrm{d}\log\bm{\beta}^{-\frac{1}{2}}_{i}(\tau)}{\mathrm{d}\tau}\right)_{+}\mathrm{d}\tau$
is non-decreasing. Furthermore, since
$g(\log\frac{1}{\tilde{\mathcal{L}}(\bm{v}(t))})\leq\tilde{q}_{\min}(\bm{v}(t))$,
we have that

$\overline{\lim}_{t\rightarrow\infty}\tilde{\gamma}(t)\leq\overline{\lim}_{t\rightarrow\infty}\frac{\tilde{q}_{\min}(\bm{v}(t))}{\rho(t)^{L}}=\overline{\lim}_{t\rightarrow\infty}\frac{\tilde{q}_{\min}(\bm{v}(t))}{\|\bm{v}(t)\|^{L}},$

which by Lemma 19, the last term is bounded.

Therefore,
$\log\tilde{\gamma}(t)+\int_{t_{1}}^{t}L\sum_{i=1}^{p}\left(\frac{\mathrm{d}\log\bm{\beta}^{-\frac{1}{2}}_{i}(\tau)}{\mathrm{d}t}\right)_{+}\mathrm{d}\tau$
is bounded, which further indicates that it converges due to its monotony. The
proof is completed by the convergence of
$\int_{t_{1}}^{t}L\sum_{i=1}^{p}\left(\frac{\mathrm{d}\log\bm{\beta}^{-\frac{1}{2}}_{i}(\tau)}{\mathrm{d}\tau}\right)_{+}\mathrm{d}\tau$.

∎

###  B.3 convergent Property of $\tilde{\mathcal{L}}$ and $\rho$: Proof of
Lemma 4

Here we restate the complete Lemma 4.

######  Lemma 22.

Let $\bm{v}$ obey an adaptive gradient flow which satisfies Assumption 1. Let
$t_{1}$ be constructed as Lemma 2. Then, for any $t\geq t_{1}$, define

$G(t)=\int_{\frac{1}{\tilde{\mathcal{L}}(t_{1})}}^{\frac{1}{\tilde{\mathcal{L}}(t)}}\frac{g^{\prime}\left(\log
x\right)^{2}}{g\left(\log x\right)^{2-2/L}}\cdot dx.$

Then, for any $t\geq t_{1}$, the following inequality holds:

$G(t)-G(t_{1})\geq\int_{\frac{1}{\tilde{\mathcal{L}}(t_{1})}}^{\frac{1}{\tilde{\mathcal{L}}(t)}}\frac{g^{\prime}\left(\log
x\right)^{2}}{g\left(\log x\right)^{2-2/L}}\cdot
dx\geq(t-t_{1})e^{-\frac{1}{L}}L^{2}\tilde{\gamma}\left(t_{1}\right)^{2/L}.$

Consequently, $\lim_{t\rightarrow\infty}\tilde{\mathcal{L}}=0$ and
$\lim_{t\rightarrow\infty}\rho=\infty$.

###### Proof.

$-\frac{\mathrm{d}\tilde{\mathcal{L}}(\bm{v}(t))}{\mathrm{d}t}=\left\|\bm{\beta}^{-\frac{1}{2}}(t)\odot\frac{\mathrm{d}\bm{v}(t)}{\mathrm{d}t}\right\|_{2}^{2}\geq\langle\bm{\beta}(t)^{-\frac{1}{2}}\odot\frac{\mathrm{d}\bm{v}(t)}{\mathrm{d}t},\widehat{\bm{\beta}^{-\frac{1}{2}}(t)\odot\bm{v}(t)}\rangle^{2}=L^{2}\cdot\frac{\nu(t)^{2}}{\rho^{2}}.$

Furthermore, we have that

$\displaystyle L^{2}\frac{\nu(t)^{2}}{\rho(t)^{2}}$ $\displaystyle\geq
L^{2}\cdot\left(\frac{g\left(\log\frac{1}{\tilde{\mathcal{L}}(\bm{v}(t))}\right)}{g^{\prime}\left(\log\frac{1}{\tilde{\mathcal{L}}(\bm{v}(t))}\right)}\tilde{\mathcal{L}}(\bm{v}(t))\right)^{2}\cdot\left(\frac{\tilde{\gamma}(t)}{g\left(\log\frac{1}{\tilde{\mathcal{L}}(\bm{v}(t))}\right)}\right)^{2/L}$
$\displaystyle\geq
L^{2}\cdot\left(\frac{g\left(\log\frac{1}{\tilde{\mathcal{L}}(\bm{v}(t))}\right)}{g^{\prime}\left(\log\frac{1}{\tilde{\mathcal{L}}(\bm{v}(t))}\right)}\tilde{\mathcal{L}}(\bm{v}(t))\right)^{2}\cdot\left(\frac{e^{-1/2}\tilde{\gamma}(t_{1})}{g\left(\log\frac{1}{\tilde{\mathcal{L}}(\bm{v}(t))}\right)}\right)^{2/L}.$

By simple calculation, we have that

$\frac{g^{\prime}\left(\log\frac{1}{\tilde{\mathcal{L}}(\bm{v}(t))}\right)^{2}}{g\left(\log\frac{1}{\tilde{\mathcal{L}}(\bm{v}(t))}\right)^{2-2/L}}\cdot\frac{\mathrm{d}}{\mathrm{d}t}\frac{1}{\mathcal{L}(\bm{v}(t))}\geq
e^{-\frac{1}{L}}L^{2}\tilde{\gamma}\left(t_{1}\right)^{2/L}.$

Taking integration to both sides, we have

$\int_{\frac{1}{\tilde{\mathcal{L}}(t_{1})}}^{\frac{1}{\tilde{\mathcal{L}}(t)}}\frac{g^{\prime}\left(\log
x\right)^{2}}{g\left(\log x\right)^{2-2/L}}\cdot
dx\geq(t-t_{1})e^{-\frac{1}{L}}L^{2}\tilde{\gamma}\left(t_{1}\right)^{2/L}.$

Since
$\lim_{t\rightarrow\infty}(t-t_{1})e^{-\frac{1}{L}}L^{2}\tilde{\gamma}\left(t_{1}\right)^{2/L}=\infty$,
we have that
$\lim_{t\rightarrow\infty}\frac{1}{\tilde{\mathcal{L}}(t)}=\infty$.

The proof is completed. ∎

###  B.4 Verification of KKT Condition

In Lemma 5, we omit the construction of coefficients $\lambda_{i}$ to
highlight the key factors of coefficients
$(\mathcal{O}(1-\langle\hat{v}(t),\widehat{-\bar{\partial}\tilde{\mathcal{L}}(t)}\rangle),\mathcal{O}\left(\log\frac{1}{\tilde{\mathcal{L}}(\bm{v}(t))}\right))$.
We restate Lemma 5 and provide the detailed construction as follows:

######  Lemma 23.

Let $\bm{v}$ obey adaptive gradient flow $\mathcal{F}$ with empirical loss
$\tilde{\mathcal{L}}$ satisfying Assumption 1. Let time $t_{1}$ be constructed
as Lemma 2. Then, define coefficients in Definition 3 as
$\lambda_{i}(t)=\tilde{q}_{\min}(\bm{v}(t))^{1-2/L}\|\bm{v}(t)\|\cdot
e^{-f\left(\tilde{q}_{i}(\bm{v}(t))\right)}f^{\prime}\left(\tilde{q}_{i}(\bm{v}(t))\right)/\|\bar{\partial}\mathcal{L}(\bm{v}(t))\|_{2}$.
Then, for any time $t\geq t_{1}$,
$\tilde{\bm{v}}(t)=\tilde{q}_{\min}(\bm{v}(t))^{-\frac{1}{L}}\bm{v}(t)$ is an
$(\varepsilon(t),\delta(t))$ KKT point of $(\tilde{P})$, where
$\varepsilon(t)$, $\delta(t)$ are defined as follows:

$\displaystyle\varepsilon(t)$
$\displaystyle=8e\frac{1}{\tilde{\gamma}(t_{1})^{2/L}}(1-\cos(\bm{\theta}))$
$\displaystyle\delta(t)$
$\displaystyle=\frac{2e^{1+\frac{1}{L}}KN}{L}K^{\log_{2}\left(2^{L+1}e^{\frac{1}{2}}B_{1}/\tilde{\gamma}(t_{1})\right)}\tilde{\gamma}(t_{1})^{-2/L}\frac{1}{\log\frac{1}{\tilde{\mathcal{L}}(\bm{v}(t))}},$

where $\cos(\bm{\theta}(t))$ is defined as inner product of $\hat{\bm{v}}(t)$
and $-\widehat{\bar{\partial}\tilde{\mathcal{L}}(\bm{v}(t))}$.

###### Proof.

We verify the definition of approximate KKT point directly.

$\displaystyle\quad\left\|\tilde{\bm{v}}(t)-\sum_{i=1}^{N}\lambda_{i}(t)\bar{\partial}\tilde{q}_{i}\left(\tilde{\bm{v}}(t)\right)\right\|_{2}^{2}$
$\displaystyle=\left\|\tilde{q}_{\min}(\bm{v}(t))^{-1/L}\|\bm{v}(t)\|\hat{\bm{v}}(t)-\frac{\tilde{q}_{\min}(\bm{v}(t))^{-1/L}\|\bm{v}(t)\|e^{-f\left(\tilde{q}_{i}(\bm{v}(t))\right)}f^{\prime}\left(\tilde{q}_{i}(\bm{v}(t))\right)\bar{\partial}\tilde{q}_{i}\left(\tilde{\bm{v}}(t)\right)}{\|\bar{\partial}\tilde{\mathcal{L}}(\bm{v}(t))\|_{2}}\right\|_{2}^{2}$
$\displaystyle=\tilde{q}_{\min}(\bm{v}(t))^{-2/L}\|\bm{v}(t)\|^{2}\left\|\hat{\bm{v}}(t)+\frac{\bar{\partial}\tilde{\mathcal{L}}(\bm{v}(t))}{\|\bar{\partial}\tilde{\mathcal{L}}(\bm{v}(t))\|_{2}}\right\|_{2}^{2}$
$\displaystyle=\tilde{q}_{\min}(\bm{v}(t))^{-2/L}\|\bm{v}(t)\|^{2}\left(2-2\left\langle\hat{\bm{v}}(t),\widehat{-\bar{\partial}\tilde{\mathcal{L}}(\bm{v}(t))}\right\rangle\right)$
$\displaystyle\leq
2g\left(\log\left(\frac{1}{\tilde{\mathcal{L}}(\bm{v}(t))}\right)\right)^{-2/L}\|\bm{v}(t)\|^{2}(1-\cos(\bm{\theta}(t)))$
$\displaystyle\leq
8g\left(\log\left(\frac{1}{\tilde{\mathcal{L}}(\bm{v}(t))}\right)\right)^{-2/L}\rho(t)^{2}(1-\cos(\bm{\theta}(t)))$
$\displaystyle=8\frac{1}{\tilde{\gamma}(t)^{2/L}}(1-\cos(\bm{\theta}(t)))\leq
8\frac{1}{\tilde{\gamma}(t)^{2/L}}(1-\cos(\bm{\theta}(t)))$ $\displaystyle\leq
8e\frac{1}{\tilde{\gamma}(t)^{2/L}}(1-\cos(\bm{\theta}(t))).$

As for $\delta$, we have that

$\displaystyle\sum_{i=1}^{N}\lambda_{i}\left(\tilde{q}_{i}(\tilde{\bm{v}}(t))-1\right)$
$\displaystyle=$
$\displaystyle\frac{\sum_{i=1}^{N}\tilde{q}_{\min}^{1-2/L}(\bm{v}(t))\|\bm{v}(t)\|\cdot
e^{-f\left(\tilde{q}_{i}(\bm{v}(t)\right)}f^{\prime}\left(\tilde{q}_{i}(\bm{v}(t)\right)\left(\frac{\tilde{q}_{i}(\bm{v}(t))}{\tilde{q}_{\min}(\bm{v}(t))}-1\right)}{\|\bar{\partial}\tilde{\mathcal{L}}(\bm{v}(t)\|_{2}}$
$\displaystyle=$
$\displaystyle\frac{\sum_{i=1}^{N}\tilde{q}_{\min}(\bm{v}(t))^{-2/L}\|\bm{v}(t)\|\cdot
e^{-f\left(\tilde{q}_{i}(\bm{v}(t))\right)}f^{\prime}\left(\tilde{q}_{i}(\bm{v}(t))\right)\left(\tilde{q}_{i}(\bm{v}(t))-\tilde{q}_{\min}(\bm{v}(t))\right)}{\|\bar{\partial}\tilde{\mathcal{L}}(\bm{v}(t))\|_{2}}$
$\displaystyle\overset{(*)}{\leq}$
$\displaystyle\sum_{i=1}^{N}\frac{2K}{L}\tilde{q}_{\min}(\bm{v}(t))^{-2/L}\|\bm{v}(t)\|^{2}e^{f\left(\tilde{q}_{\min}(\bm{v}(t))\right)-f\left(\tilde{q}_{i}(\bm{v}(t))\right)}f^{\prime}\left(\tilde{q}_{i}(\bm{v}(t))\right)$
$\displaystyle\cdot$
$\displaystyle\left(\tilde{q}_{i}(\bm{v}(t))-\tilde{q}_{\min}(\bm{v}(t))\right)\frac{1}{\log\frac{1}{\tilde{\mathcal{L}}(\bm{v}(t))}},$

where inequality $(*)$ is because

$\displaystyle\|\bar{\partial}\tilde{\mathcal{L}}(\bm{v}(t))\|$
$\displaystyle\geq\left\langle\bar{\partial}\tilde{\mathcal{L}}(\bm{v}(t)),\hat{\bm{v}}(t)\right\rangle=\frac{L\nu(t)}{\|\bm{v}(t)\|}$
$\displaystyle\geq$
$\displaystyle\frac{L}{\|\bm{v}(t)\|}\frac{g\left(\log\frac{1}{\tilde{\mathcal{L}}(\bm{v}(t))}\right)}{g^{\prime}\left(\log\frac{1}{\tilde{\mathcal{L}}(\bm{v}(t))}\right)}\tilde{\mathcal{L}}(\bm{v}(t))\geq\frac{L}{\|\bm{v}(t)\|}\frac{1}{2K}\log\frac{1}{\tilde{\mathcal{L}}(\bm{v}(t))}\cdot\tilde{\mathcal{L}}(\bm{v}(t))$
$\displaystyle\geq$
$\displaystyle\frac{L}{\|\bm{v}(t)\|}\frac{1}{2K}e^{-f\left(\tilde{q}_{\min}(\bm{v}(t))\right)}\log\frac{1}{\tilde{\mathcal{L}}(\bm{v}(t))}.$

Bounding $\|\bm{v}\|$ using $\rho$ and applying the definition of surrogate
margin $\tilde{\gamma}$, we further have

$\displaystyle\sum_{i=1}^{N}\lambda_{i}\left(\tilde{q}_{i}(\tilde{\bm{v}}(t))-1\right)$
$\displaystyle\leq$
$\displaystyle\sum_{i=1}^{N}\frac{8K}{L}\tilde{q}_{\min}^{-2/L}(\bm{v}(t))\rho(t)^{2}e^{f\left(\tilde{q}_{\min}(\bm{v}(t))\right)-f\left(\tilde{q}_{i}(\bm{v}(t))\right)}f^{\prime}\left(\tilde{q}_{i}(\bm{v}(t))\right)$
$\displaystyle\left(\tilde{q}_{i}(\bm{v}(t))-\tilde{q}_{\min}(\bm{v}(t)\right)\frac{1}{\log\frac{1}{\tilde{\mathcal{L}}(\bm{v}(t))}}$
$\displaystyle\leq$
$\displaystyle\sum_{i=1}^{N}\frac{8K}{L}\tilde{\gamma}(t)^{-2/L}\cdot
e^{f\left(\tilde{q}_{\min}(\bm{v}(t))\right)-f\left(\tilde{q}_{i}(\bm{v}(t))\right)}f^{\prime}\left(\tilde{q}_{i}(\bm{v}(t))\right)$
$\displaystyle\left(\tilde{q}_{i}(\bm{v}(t))-\tilde{q}_{\min}(\bm{v}(t))\right)\frac{1}{\log\frac{1}{\tilde{\mathcal{L}}(\bm{v}(t))}}$
$\displaystyle\leq$
$\displaystyle\sum_{i=1}^{N}\frac{8e^{\frac{1}{L}}K}{L}\tilde{\gamma}(t_{1})^{-2/L}\cdot
e^{f\left(\tilde{q}_{\min}(\bm{v}(t))\right)-f\left(\tilde{q}_{i}(\bm{v}(t))\right)}f^{\prime}\left(\tilde{q}_{i}(\bm{v}(t))\right)$
$\displaystyle\left(\tilde{q}_{i}(\bm{v}(t))-\tilde{q}_{\min}(\bm{v}(t))\right)\frac{1}{\log\frac{1}{\tilde{\mathcal{L}}(\bm{v}(t))}}.$

Since
$f(\tilde{q}_{\min}(\bm{v}(t))(\bm{v}(t)))-f(\tilde{q}_{i}(\bm{v}(t)))=(\tilde{q}_{\min}(\bm{v}(t))-\tilde{q}_{i}(\bm{v}(t)))f^{\prime}(\xi_{i}(t))$
($\xi_{i}(t)\in[\tilde{q}_{\min}(\bm{v}(t)),\tilde{q}_{i}(\bm{v}(t))]$ is
guaranteed by Mean Value Theorem), we then have

$\displaystyle\sum_{i=1}^{N}\lambda_{i}\left(\tilde{q}_{i}(\tilde{\bm{v}}(t))-1\right)$
$\displaystyle\leq$
$\displaystyle\sum_{i=1}^{N}\frac{2e^{\frac{1}{L}}K}{L}\tilde{\gamma}(t_{1})^{-2/L}\cdot
e^{f\left(\tilde{q}_{\min}(\bm{v}(t))\right)-f\left(\tilde{q}_{i}(\bm{v}(t))\right)}f^{\prime}\left(\tilde{q}_{i}(\bm{v}(t))\right)$
$\displaystyle\left(\tilde{q}_{i}(\bm{v}(t))-\tilde{q}_{\min}(\bm{v}(t))\right)\frac{1}{\log\frac{1}{\tilde{\mathcal{L}}(\bm{v}(t))}}$
$\displaystyle=$
$\displaystyle\sum_{i=1}^{N}\frac{2e^{\frac{1}{L}}K}{L}\tilde{\gamma}(t_{1})^{-2/L}\cdot
e^{(\tilde{q}_{\min}(\bm{v}(t))-\tilde{q}_{i}(\bm{v}(t)))f^{\prime}(\xi_{i}(t))}f^{\prime}\left(\tilde{q}_{i}(\bm{v}(t))\right)$
$\displaystyle\left(\tilde{q}_{i}(\bm{v}(t))-\tilde{q}_{\min}(\bm{v}(t))\right)\frac{1}{\log\frac{1}{\tilde{\mathcal{L}}(\bm{v}(t))}}$
$\displaystyle\leq$
$\displaystyle\sum_{i=1}^{N}\frac{2e^{\frac{1}{L}}K}{L}\tilde{\gamma}(t_{1})^{-2/L}\cdot
e^{(\tilde{q}_{\min}(\bm{v}(t))-\tilde{q}_{i}(\bm{v}(t)))f^{\prime}(\xi_{i}(t))}K^{\left\lceil\log_{2}\left(\tilde{q}_{i}(\bm{v}(t))/\xi_{i}(t)\right)\right\rceil}f^{\prime}\left(\xi_{i}(t)\right)$
$\displaystyle\left(\tilde{q}_{i}(\bm{v}(t))-\tilde{q}_{\min}(\bm{v}(t))\right)\frac{1}{\log\frac{1}{\tilde{\mathcal{L}}(\bm{v}(t))}}$
$\displaystyle\overset{(*)}{\leq}$
$\displaystyle\sum_{i=1}^{N}\frac{2e^{\frac{1}{L}}K}{L}\tilde{\gamma}(t_{1})^{-2/L}\cdot
e^{(\tilde{q}_{\min}(\bm{v}(t))-\tilde{q}_{i}(\bm{v}(t)))f^{\prime}(\xi_{i}(t))}K^{\log_{2}\left(2e^{\frac{1}{2}}B_{1}/\tilde{\gamma}(t_{1})\right)}f^{\prime}\left(\xi_{i}(t)\right)$
$\displaystyle\left(\tilde{q}_{i}(\bm{v}(t))-\tilde{q}_{\min}(\bm{v}(t))\right)\frac{1}{\log\frac{1}{\tilde{\mathcal{L}}(\bm{v}(t))}}$
$\displaystyle\overset{(**)}{\leq}$
$\displaystyle\frac{2e^{1+\frac{1}{L}}KN}{L}K^{\log_{2}\left(2^{L+1}e^{\frac{1}{2}}B_{1}/\tilde{\gamma}(t_{1})\right)}\tilde{\gamma}(t_{1})^{-2/L}\frac{1}{\log\frac{1}{\tilde{\mathcal{L}}(\bm{v}(t))}},$

where eq. $(*)$ is because

$\displaystyle\left\lceil\log_{2}\left(\tilde{q}_{i}(\bm{v}(t))/\xi_{i}(t)\right)\right\rceil$
$\displaystyle\leq\log_{2}\left(\tilde{q}_{i}(\bm{v}(t))/\tilde{q}_{\min}(\bm{v}(t))\right)+1$
$\displaystyle\leq\log_{2}\left(\tilde{q}_{i}(\bm{v}(t))\|\bm{v}(t)\|^{L}/\|\bm{v}(t)\|^{L}\tilde{q}_{\min}(\bm{v}(t))\right)+1$
$\displaystyle\leq\log_{2}\left(2^{L+1}B_{1}\rho(t)^{L}/\tilde{q}_{\min}\right)\leq\log_{2}\left(2^{L+1}B_{1}/\tilde{\gamma}(t)\right)$
$\displaystyle\leq\log_{2}\left(2^{L+1}e^{\frac{1}{2}}B_{1}/\tilde{\gamma}(t_{1})\right),$

and eq. $(**)$ is because $e^{-x}x\leq e$.

The proof is completed. ∎

By Lemma 4, we have proved that
$\lim_{t\rightarrow\infty}\tilde{\mathcal{L}}(t)=0$, which leads to
$\lim_{t\rightarrow\infty}\delta(t)=0$. As stated in the main text, we only
need to bound $\varepsilon(t)$, or equivalently $(1-\cos(\bm{\theta}))$.

Before moving forward, we introduce an equivalent proposition of that
$(1-\cos(\bm{\theta}))$ goes to zero.

######  Lemma 24.

If there exists a time sequence $\\{t_{i}\\}_{i=1}^{\infty}$, such that,
$\lim_{i\rightarrow\infty}t_{i}=\infty$ and
$\lim_{i\rightarrow\infty}\left\langle\widehat{\bm{\beta}^{-\frac{1}{2}}\odot\bm{v}},\widehat{\bm{\beta}^{\frac{1}{2}}\odot\bar{\partial}\tilde{\mathcal{L}}}\right\rangle=-1$,
then

$\lim_{i\rightarrow\infty}\cos(\bm{\theta}(t_{i}))=1.$

###### Proof.

$\displaystyle-\cos(\bm{\theta}(t))$ $\displaystyle=$
$\displaystyle\left\langle\widehat{\bm{\beta}(t)^{-\frac{1}{2}}\odot\bm{v}(t)}+\left(\hat{\bm{v}}(t)-\widehat{\bm{\beta}(t)^{-\frac{1}{2}}\odot\bm{v}}(t)\right),\widehat{\bm{\beta}(t)^{\frac{1}{2}}\odot\bar{\partial}\tilde{\mathcal{L}}(t)}+\left(\widehat{\bar{\partial}\tilde{\mathcal{L}}(t)}-\widehat{\bm{\beta}(t)^{\frac{1}{2}}\odot\bar{\partial}\tilde{\mathcal{L}}(t)}\right)\right\rangle$
$\displaystyle=$
$\displaystyle\left\langle\widehat{\bm{\beta}(t)^{-\frac{1}{2}}\odot\bm{v}(t)},\widehat{\bm{\beta}(t)^{\frac{1}{2}}\odot\bar{\partial}\tilde{\mathcal{L}}(t)}\right\rangle+\left\langle\widehat{\bm{\beta}(t)^{-\frac{1}{2}}\odot\bm{v}(t)},\left(\widehat{\bar{\partial}\tilde{\mathcal{L}}(t)}-\widehat{\bm{\beta}(t)^{\frac{1}{2}}\odot\bar{\partial}\tilde{\mathcal{L}}(t)}\right)\right\rangle$
$\displaystyle+$
$\displaystyle\left\langle\left(\hat{\bm{v}}(t)-\widehat{\bm{\beta}(t)^{-\frac{1}{2}}\odot\bm{v}(t)}\right),\widehat{\bm{\beta}(t)^{\frac{1}{2}}\odot\bar{\partial}\tilde{\mathcal{L}}(t)}\right\rangle$
$\displaystyle+$
$\displaystyle\left\langle\left(\hat{\bm{v}}(t)-\widehat{\bm{\beta}(t)^{-\frac{1}{2}}\odot\bm{v}(t)}\right),\left(\widehat{\bar{\partial}\tilde{\mathcal{L}}(t)}-\widehat{\bm{\beta}(t)^{\frac{1}{2}}\odot\bar{\partial}\tilde{\mathcal{L}}(t)}\right)\right\rangle.$

Furthermore,

$\lim_{i\rightarrow\infty}\left\|\widehat{\bar{\partial}\tilde{\mathcal{L}}(t)}-\widehat{\bm{\beta}(t)^{\frac{1}{2}}\odot\bar{\partial}\tilde{\mathcal{L}}(t)}\right\|=2-\lim_{i\rightarrow\infty}\left\langle\widehat{\bar{\partial}\tilde{\mathcal{L}}(t)},\widehat{\bm{\beta}(t)^{\frac{1}{2}}\odot\bar{\partial}\tilde{\mathcal{L}}(t)}\right\rangle=0.$

Following the same routine, we have
$\lim_{i\rightarrow\infty}\left\|\hat{\bm{v}}(t)-\widehat{\bm{\beta}(t)^{-\frac{1}{2}}\odot\bm{v}(t)}\right\|=0$.

The proof is completed. ∎

Let
$\cos(\tilde{\bm{\theta}}(t))=-\left\langle\widehat{\bm{\beta}(t)^{-\frac{1}{2}}\odot\bm{v}(t)},\widehat{\bm{\beta}(t)^{\frac{1}{2}}\odot\bar{\partial}\tilde{\mathcal{L}}(t)}\right\rangle=\left\langle\widehat{\bm{\beta}(t)^{-\frac{1}{2}}\odot\bm{v}(t)},\widehat{\bm{\beta}(t)^{-\frac{1}{2}}\odot\frac{\mathrm{d}\bm{v}(t)}{\mathrm{d}t}}\right\rangle$.
Then we only need to bound $1-\cos(\tilde{\bm{\theta}}(t))$.

In Section 5.3, we briefly state the methodology of proving the convergence of
$\varepsilon(t)$. We will make it more clear here: In the proof Lemma 2, we
show that sum of the derivative of $g(\log\frac{1}{\tilde{\mathcal{L}}(t)})$
and $\frac{1}{\rho(t)^{L}}$ with $\bm{\beta}(t)$ fixed can be bounded as

$\displaystyle\frac{\mathrm{d}}{\mathrm{d}t}\left(\log\left(g\left(\log\frac{1}{\tilde{\mathcal{L}}(t)}\right)\right)\right)-L\left(\bar{\partial}_{\bm{v}}\log\rho(t)\right)\frac{\mathrm{d}\bm{v}(t)}{\mathrm{d}t}$
$\displaystyle=$
$\displaystyle\frac{g^{\prime}\left(\log\frac{1}{\tilde{\mathcal{L}}(t)}\right)}{g\left(\log\frac{1}{\tilde{\mathcal{L}}(t)}\right)}\cdot\frac{1}{\tilde{\mathcal{L}}(t)}\cdot\left(-\frac{\mathrm{d}\tilde{\mathcal{L}}(t)}{\mathrm{d}t}\right)-L^{2}\cdot\frac{\nu(t)}{\rho(t)^{2}}$
$\displaystyle\geq$
$\displaystyle\frac{1}{\nu(t)}\left(\left\langle\frac{\mathrm{d}\bm{v}(t)}{\mathrm{d}t},\bm{\beta}(t)^{-1}\odot\frac{\mathrm{d}\bm{v}(t)}{\mathrm{d}t}\right\rangle-\left\langle\bm{\beta}(t)^{-\frac{1}{2}}\odot\frac{\mathrm{d}\bm{v}(t)}{\mathrm{d}t},\widehat{\bm{\beta}(t)^{-\frac{1}{2}}\odot\bm{v}(t)}\right\rangle^{2}\right)$
$\displaystyle=$
$\displaystyle\frac{\left\langle\bm{\beta}(t)^{-\frac{1}{2}}\odot\frac{\mathrm{d}\bm{v}(t)}{\mathrm{d}t},\widehat{\bm{\beta}(t)^{-\frac{1}{2}}\odot\bm{v}(t)}\right\rangle^{2}}{\nu(t)}(\cos(\tilde{\bm{\theta}}(t))^{-2}-1)$
$\displaystyle=$
$\displaystyle\frac{L^{2}\nu(t)}{\rho(t)^{2}}(\cos(\tilde{\bm{\theta}}(t))^{-2}-1)$
$\displaystyle=$ $\displaystyle
L\left\langle\bar{\partial}_{\bm{v}}\log\rho(t),\frac{\mathrm{d}\bm{v}}{\mathrm{d}t}\right\rangle(\cos(\tilde{\bm{\theta}}(t))^{-2}-1).$
(11)

Eq. (11) indicates that, intuitively, $(\cos(\tilde{\bm{\theta}}(t))^{-2}-1)$
can be bounded by the division of change of $\tilde{\gamma}$ to change of
parameter part $\bm{v}$ in $\rho$. For this purpose, we define $\tilde{\rho}$
in Section 5.3 to describe the accumulated change of $\bm{v}$ in $\rho$. The
following lemma describe the basic property of $\tilde{\rho}$ and its
relationship with $\rho$.

######  Lemma 25.

(1). The derivative of $\tilde{\rho}^{2}$ is as follows:

$\frac{1}{2}\frac{d\tilde{\rho}(t)^{2}}{\mathrm{d}t}=\langle\bar{\partial}\tilde{\mathcal{L}}(\bm{v}(t)),\bm{v}(t)\rangle=L\nu(t);$

(2). $\rho(t)$ satisfies that, for any $t^{2}>t^{1}>t_{1}$,

$\rho(t_{2})\geq e^{-\frac{1}{2}}\rho(t_{1});$

(3). For any $t>t_{1}$,
$\sqrt{1-\frac{e^{\frac{1}{2}}}{2}}\leq\frac{\rho(t)}{\tilde{\rho}(t)}\leq\sqrt{1+\frac{e^{\frac{1}{2}}}{2}}$.

###### Proof.

(1). can be directly verified similar to Lemma 21. As for (2)., since
$\frac{d\log\rho(t)}{\mathrm{d}t}=\frac{1}{2}\frac{\frac{d\rho(t)^{2}}{\mathrm{d}t}}{\rho(t)^{2}}$,
we have that

$\displaystyle\frac{d\log\rho(t)}{\mathrm{d}t}$
$\displaystyle=\frac{L\sum_{i=1}^{N}e^{-f\left(\tilde{q}_{i}(\bm{v}(t))\right)}f^{\prime}\left(\tilde{q}_{i}(\bm{v}(t))\right)\tilde{q}_{i}(\bm{v}(t))+\left\langle\bm{\beta}(t)^{-\frac{1}{2}}\odot\bm{v}(t),\bm{v}(t)\odot\frac{\mathrm{d}\bm{\beta}(t)^{-\frac{1}{2}}}{\mathrm{d}t}\right\rangle}{\rho(t)^{2}}$
$\displaystyle\geq\frac{\left\langle\bm{\beta}(t)^{-\frac{1}{2}}\odot\bm{v}(t),\bm{v}(t)\odot\frac{\mathrm{d}\bm{\beta}(t)^{-\frac{1}{2}}}{\mathrm{d}t}\right\rangle}{\rho(t)^{2}}$
$\displaystyle\geq\frac{\sum_{i=1}^{p}\bm{\beta}_{i}(t)^{-\frac{1}{2}}(t)\frac{\mathrm{d}\bm{\beta}_{i}^{-\frac{1}{2}}(t)}{\mathrm{d}t}\bm{v}_{i}(t)^{2}}{\sum_{i=1}^{p}\bm{\beta}_{i}^{-1}(t)\bm{v}_{i}(t)^{2}}$
$\displaystyle=\frac{\sum_{i=1}^{p}\bm{\beta}_{i}^{\frac{1}{2}}(t)\frac{\mathrm{d}\bm{\beta}_{i}^{-\frac{1}{2}}(t)}{\mathrm{d}t}\bm{\beta}_{i}^{-1}(t)\bm{v}_{i}(t)^{2}}{\sum_{i=1}^{p}\bm{\beta}_{i}^{-1}(t)\bm{v}_{i}(t)^{2}}$
$\displaystyle=\frac{\sum_{i=1}^{p}\frac{d\log\bm{\beta}_{i}^{-\frac{1}{2}}(t)}{\mathrm{d}t}\bm{\beta}_{i}^{-1}(t)\bm{v}_{i}(t)^{2}}{\sum_{i=1}^{p}\bm{\beta}_{i}^{-1}(t)\bm{v}_{i}(t)^{2}}$
$\displaystyle\geq\sum_{i=1}^{p}\left(\frac{d\log\bm{\beta}_{i}^{-\frac{1}{2}}(t)}{\mathrm{d}t}\right)_{-}.$

The proof for (2). is completed by integration.

As for (3)., by expanding
$\langle\bm{v}(t),\bm{\beta}^{-\frac{1}{2}}(t)\odot\frac{\mathrm{d}\bm{\beta}^{-\frac{1}{2}}(t)}{\mathrm{d}t}\odot\bm{v}(t)\rangle$,
we have that

$\displaystyle\int_{t_{1}}^{t}\langle\bm{v}(\tau),\bm{\beta}^{-\frac{1}{2}}(\tau)\odot\frac{\mathrm{d}\bm{\beta}^{-\frac{1}{2}}(\tau)}{\mathrm{d}\tau}\odot\bm{v}(\tau)\rangle\mathrm{d}\tau$
$\displaystyle=$
$\displaystyle\sum_{i=1}^{p}\int_{t_{1}}^{t}\bm{v}_{i}^{2}(\tau)\bm{\beta}_{i}^{-1}(\tau)\bm{\beta}_{i}^{\frac{1}{2}}(\tau)\frac{\mathrm{d}\bm{\beta}_{i}^{-\frac{1}{2}}(\tau)}{\mathrm{d}t}\mathrm{d}\tau$
$\displaystyle\leq$
$\displaystyle\sum_{i=1}^{p}\int_{t_{1}}^{t}\bm{\beta}_{i}^{-1}(\tau)\bm{v}_{i}^{2}(\tau)\left(\bm{\beta}_{i}^{\frac{1}{2}}(\tau)\frac{\mathrm{d}\bm{\beta}_{i}^{-\frac{1}{2}}(\tau)}{\mathrm{d}t}\right)_{+}\mathrm{d}\tau$
$\displaystyle\leq$
$\displaystyle\int_{t_{1}}^{t}\left(\sum_{i=1}^{p}\bm{\beta}_{i}^{-1}\bm{v}_{i}^{2}(\tau)\right)\left(\sum_{i=1}^{p}\left(\bm{\beta}_{i}^{\frac{1}{2}}(\tau)\frac{\mathrm{d}\bm{\beta}_{i}^{-\frac{1}{2}}(\tau)}{\mathrm{d}t}\right)_{+}\right)\mathrm{d}\tau$
$\displaystyle\overset{(*)}{=}$
$\displaystyle\|\bm{\beta}(\tau_{0})^{-\frac{1}{2}}\odot\bm{v}(\tau_{0})\|^{2}\int_{t_{1}}^{t}\left(\sum_{i=1}^{p}\left(\bm{\beta}_{i}^{\frac{1}{2}}(\tau)\frac{\mathrm{d}\bm{\beta}_{i}^{-\frac{1}{2}}(\tau)}{\mathrm{d}t}\right)_{+}\right)\mathrm{d}\tau$
$\displaystyle\leq$
$\displaystyle\frac{1}{4}\|\bm{\beta}(\tau_{0})^{-\frac{1}{2}}\odot\bm{v}(\tau_{0})\|^{2}$
$\displaystyle\leq$
$\displaystyle\frac{e^{\frac{1}{2}}}{4}\|\bm{\beta}(t)^{-\frac{1}{2}}\odot\bm{v}(t)\|^{2},$

where $\tau_{0}$ in eq. $(*)$ is in $[t_{1},t]$ and First Mean Value Theorem
guarantees its existence.

The second inequality follows by lower bound
$\int_{t_{1}}^{t}\langle\bm{v}(\tau),\bm{\beta}^{-\frac{1}{2}}(\tau)\odot\frac{\mathrm{d}\bm{\beta}^{-\frac{1}{2}}(\tau)}{\mathrm{d}\tau}\odot\bm{v}(\tau)\rangle\mathrm{d}\tau$
similarly.

The proof is completed. ∎

With Lemma 25, we integrate the analysis of the change of $\tilde{\gamma}$
into the following Lemma.

######  Lemma 26.

For any time $t_{3}>t_{2}\geq t_{1}$,

$\displaystyle\int_{t_{2}}^{t_{3}}\left(\cos(\tilde{\bm{\theta}}(\tau))^{-2}-1\right)\cdot\frac{\mathrm{d}}{d\tau}\log\tilde{\rho}(\tau)d\tau\leq$
$\displaystyle\frac{1}{L\left(1-\frac{e^{\frac{1}{2}}}{2}\right)}\log\frac{\tilde{\gamma}\left(t_{3}\right)}{\tilde{\gamma}\left(t_{2}\right)}$
$\displaystyle+$
$\displaystyle\frac{L}{\left(1-\frac{e^{\frac{1}{2}}}{2}\right)}\sum_{i=1}^{p}\int_{t_{2}}^{t_{3}}\sum_{i=1}^{p}\left(\frac{\mathrm{d}\log\bm{\beta}^{-\frac{1}{2}}_{i}(t)}{\mathrm{d}t}\right)_{+}\mathrm{d}t.$

###### Proof.

Recall that

$\frac{d\log\tilde{\rho}(t)}{\mathrm{d}t}=\frac{L\nu(t)}{\tilde{\rho}(t)^{2}}=\frac{\left\langle\bm{v}(t),\bm{\beta}(t)^{-1}\odot\frac{\mathrm{d}\bm{v}(t)}{\mathrm{d}t}\right\rangle}{\tilde{\rho}(t)^{2}},$

and

$\displaystyle\frac{\mathrm{d}}{\mathrm{d}t}\log\tilde{\gamma}(t)\geq$
$\displaystyle\frac{1}{\nu(t)}\left(\left\langle\frac{\mathrm{d}\bm{v}(t)}{\mathrm{d}t},\bm{\beta}(t)^{-1}\odot\frac{\mathrm{d}\bm{v}(t)}{\mathrm{d}t}\right\rangle-\left\langle\bm{\beta}(t)^{-\frac{1}{2}}\odot\frac{\mathrm{d}\bm{v}(t)}{\mathrm{d}t},\widehat{\bm{\beta}(t)^{-\frac{1}{2}}\odot\bm{v}(t)}\right\rangle\right)$
$\displaystyle-$ $\displaystyle
L\sum_{i=1}^{p}\left(\frac{\mathrm{d}\log\bm{\beta}_{i}(t)^{-\frac{1}{2}}(t)}{\mathrm{d}t}\right)_{+}.$

We then have

$\displaystyle\frac{\mathrm{d}}{\mathrm{d}t}\log\tilde{\gamma}(t)\geq$
$\displaystyle\frac{1}{\nu(t)}\left(\left\langle\frac{\mathrm{d}\bm{v}(t)}{\mathrm{d}t},\bm{\beta}(t)^{-1}\odot\frac{\mathrm{d}\bm{v}(t)}{\mathrm{d}t}\right\rangle-\left\langle\bm{\beta}(t)^{-\frac{1}{2}}\odot\frac{\mathrm{d}\bm{v}(t)}{\mathrm{d}t},\widehat{\bm{\beta}(t)^{-\frac{1}{2}}\odot\bm{v}(t)}\right\rangle^{2}\right)$
$\displaystyle-$ $\displaystyle
L\sum_{i=1}^{p}\left(\frac{\mathrm{d}\log\bm{\beta}(t)^{-\frac{1}{2}}_{i}(t)}{\mathrm{d}t}\right)_{+}$
$\displaystyle=$ $\displaystyle
L\frac{\tilde{\rho}(t)^{2}}{L^{2}\nu(t)^{2}}\frac{d\log\tilde{\rho}(t)}{\mathrm{d}t}\left(\left\langle\frac{\mathrm{d}\bm{v}(t)}{\mathrm{d}t},\bm{\beta}(t)^{-1}\odot\frac{\mathrm{d}\bm{v}(t)}{\mathrm{d}t}\right\rangle-\left\langle\bm{\beta}(t)^{-\frac{1}{2}}\odot\frac{\mathrm{d}\bm{v}(t)}{\mathrm{d}t},\widehat{\bm{\beta}(t)^{-\frac{1}{2}}\odot\bm{v}(t)}\right\rangle^{2}\right)$
$\displaystyle-$ $\displaystyle
L\sum_{i=1}^{p}\left(\frac{\mathrm{d}\log\bm{\beta}(t)^{-\frac{1}{2}}_{i}(t)}{\mathrm{d}t}\right)_{+}$
$\displaystyle\geq$ $\displaystyle
L\left(1-\frac{e^{\frac{1}{2}}}{2}\right)\frac{\rho(t)^{2}}{L^{2}\nu(t)^{2}}\frac{d\log\tilde{\rho}(t)}{\mathrm{d}t}\left(\left\langle\frac{\mathrm{d}\bm{v}(t)}{\mathrm{d}t},\bm{\beta}(t)^{-1}\odot\frac{\mathrm{d}\bm{v}(t)}{\mathrm{d}t}\right\rangle\right.$
$\displaystyle-$
$\displaystyle\left.\left\langle\bm{\beta}(t)^{-\frac{1}{2}}\odot\frac{\mathrm{d}\bm{v}(t)}{\mathrm{d}t},\widehat{\bm{\beta}^{-\frac{1}{2}}\odot\bm{v}(t)}\right\rangle^{2}\right)$
$\displaystyle-$ $\displaystyle
L\sum_{i=1}^{p}\left(\frac{\mathrm{d}\log\bm{\beta}^{-\frac{1}{2}}_{i}(t)}{\mathrm{d}t}\right)_{+}$
$\displaystyle=$ $\displaystyle
L\left(1-\frac{e^{\frac{1}{2}}}{2}\right)\frac{d\log\tilde{\rho}}{\mathrm{d}t}(\cos(\tilde{\bm{\theta}}(t))^{-2}-1)-L\sum_{i=1}^{p}\left(\frac{\mathrm{d}\log\bm{\beta}^{-\frac{1}{2}}_{i}(t)}{\mathrm{d}t}\right)_{+}.$

The proof is completed. ∎

Applying the First Mean Value Theorem together with Lemmas 24 and 26, one can
easily obtain Lemma 6. To make the following proof simpler, we restate Lemma 6
as the following corollary, while using $\cos(\tilde{\bm{\theta}}(t))$ instead
of $\cos(\bm{\theta}(t))$.

######  Corollary 1.

For any time $t_{3}>t_{2}\geq t_{1}$, there exists a time
$\xi\in(t_{2},t_{3})$, such that,

$\displaystyle\left(\cos(\tilde{\bm{\theta}}(\xi))^{-2}-1\right)(\log\tilde{\rho}(t_{2})-\log\tilde{\rho}(t_{1}))\leq$
$\displaystyle\frac{1}{L\left(1-\frac{e^{\frac{1}{2}}}{2}\right)}\log\frac{\tilde{\gamma}\left(t_{3}\right)}{\tilde{\gamma}\left(t_{2}\right)}$
$\displaystyle+$
$\displaystyle\frac{L}{\left(1-\frac{e^{\frac{1}{2}}}{2}\right)}\sum_{i=1}^{p}\int_{t_{2}}^{t_{3}}\sum_{i=1}^{p}\left(\frac{\mathrm{d}\log\bm{\beta}^{-\frac{1}{2}}_{i}(t)}{\mathrm{d}t}\right)_{+}\mathrm{d}t.$

There is still a gap that $\xi$ is guaranteed by First Mean Value Theorem and
do not apparently converge to limit points. For this purpose, we introduce the
following lemma 7, which helps to bound the change of $\hat{\bm{v}}(t)$ by
$\tilde{\rho}(t)$.

###### Proof of Lemma 7.

By direct calculation, we have that

$\left\|\frac{d\hat{\bm{v}}(t)}{\mathrm{d}t}\right\|=\frac{1}{\|\bm{v}(t)\|}\left\|\left(\bm{I}-\hat{\bm{v}}(t)\hat{\bm{v}}(t)^{\top}\right)\frac{\mathrm{d}\bm{v}(t)}{\mathrm{d}t}\right\|\leq\frac{1}{\|\bm{v}(t)\|}\left\|\frac{\mathrm{d}\bm{v}(t)}{\mathrm{d}t}\right\|\leq\frac{2}{\|\bm{v}(t)\|}\left\|\bm{\beta}(t)^{-1}\odot\frac{\mathrm{d}\bm{v}(t)}{\mathrm{d}t}\right\|.$

Furthermore,

$\displaystyle\quad\left\|\bm{\beta}(t)^{-1}\odot\frac{\mathrm{d}\bm{v}(t)}{\mathrm{d}t}\right\|=\left\|\bar{\partial}\tilde{\mathcal{L}}(t)\right\|$
$\displaystyle\leq\sum_{i\in[N]}e^{-f\left(\tilde{q}_{i}(\bm{v}(t))\right)}f^{\prime}\left(\tilde{q}_{i}(\bm{v}(t))\right)\left\|\bar{\partial}\tilde{q}_{i}(\bm{v}(t))\right\|$
$\displaystyle\leq\sum_{i\in[N]}e^{-f\left(\tilde{q}_{i}(\bm{v}(t))\right)}f^{\prime}\left(\tilde{q}_{i}(\bm{v}(t))\right)\tilde{q}_{i}(\bm{v}(t))\frac{1}{\tilde{q}_{i}(\bm{v}(t))}B_{1}\|\bm{v}(t)\|^{L-1}$
$\displaystyle\leq\sum_{i\in[N]}2^{L-1}e^{-f\left(\tilde{q}_{i}(\bm{v}(t))\right)}f^{\prime}\left(\tilde{q}_{i}(\bm{v}(t))\right)\tilde{q}_{i}(\bm{v}(t))\frac{1}{\tilde{q}_{i}(\bm{v}(t))}B_{1}\rho(t)^{L-1}$
$\displaystyle\leq\sum_{i\in[N]}2^{L-1}e^{-f\left(\tilde{q}_{i}(\bm{v}(t))\right)}f^{\prime}\left(\tilde{q}_{i}(\bm{v}(t))\right)\tilde{q}_{i}(\bm{v}(t))\frac{1}{g\left(\log\frac{1}{\tilde{\mathcal{L}}(t)}\right)}B_{1}\rho(t)^{L-1}$
$\displaystyle=2^{L-1}\frac{\nu(t)}{\rho(t)}\frac{\rho(t)^{L}}{g\left(\log\frac{1}{\tilde{\mathcal{L}}(t)}\right)}B_{1}=2^{L-1}\frac{\nu(t)}{\rho(t)}\frac{1}{\tilde{\gamma}(t)}B_{1}$

Therefore,

$\displaystyle\left\|\frac{d\hat{\bm{v}}(t)}{\mathrm{d}t}\right\|$
$\displaystyle\leq
2^{L}\frac{\nu(t)}{\rho(t)\|\bm{v}(t)\|}\frac{1}{\tilde{\gamma}(t)}B_{1}\leq
3\cdot
2^{L-1}\frac{\nu(t)}{\rho(t)^{2}}\frac{1}{\tilde{\gamma}(t)}B_{1}\leq\frac{3\cdot
2^{L-1}}{(1-\frac{e^{\frac{1}{2}}}{2})}\frac{\nu(t)}{\tilde{\rho}(t)^{2}}\frac{1}{\tilde{\gamma}(t)}B_{1}$
$\displaystyle=\frac{3\cdot
2^{L-1}}{(1-\frac{e^{\frac{1}{2}}}{2})}\frac{B_{1}}{L}\frac{\mathrm{d}\log\tilde{\rho}(t)}{\mathrm{d}t}\frac{1}{\tilde{\gamma}(t)}\leq\frac{3\cdot
2^{L-1}}{(1-\frac{e^{\frac{1}{2}}}{2})}\frac{e^{\frac{1}{2}}B_{1}}{L}\frac{\mathrm{d}\log\tilde{\rho}(t)}{\mathrm{d}t}\frac{1}{\tilde{\gamma}(t_{1})}.$

The proof is completed. ∎

Applying Corollary 1 and Lemma 7, we can then prove Theorem 4.

###### Proof of Theorem 4.

Let $\bar{\bm{v}}$ be any limit point of series
$\\{\bm{v}(t)\\}_{t=0}^{\infty}$. We construct a series of approximate KKT
point which converges to $\bar{\bm{v}}$ by induction.

Let $t^{1}=t_{1}$. Now suppose $t^{k-1}$ has been constructed. By Lemma 3 and
that $\bar{\bm{v}}$ is a limit point, there exists $s_{k}>t^{k-1}$ such that,
for any $t>s_{k}$

$\left\|\hat{\bm{v}}\left(s_{k}\right)-\bar{\bm{v}}\right\|_{2}\leq\frac{1}{k},\text{
}\frac{2}{L}\log\frac{\tilde{\gamma}(t)}{\tilde{\gamma}(s_{k})}\leq\frac{1}{2k^{3}},\text{
and},L\sum_{i=1}^{p}\int_{s_{m}}^{\infty}\left(\frac{\mathrm{d}\log\bm{\beta}_{i}(t)^{-\frac{1}{2}}}{\mathrm{d}t}\right)_{+}\mathrm{d}t\leq\frac{1}{2k^{3}}.$

Let $s^{\prime}_{k}>s_{k}$ satisfy
$\log\tilde{\rho}\left(s_{k}^{\prime}\right)=\log\tilde{\rho}\left(s_{k}\right)+\frac{1}{k}$
(which is guaranteed as $\lim_{t\rightarrow\infty}\rho=\infty$ and Lemma 25).
Therefore, by Corollary 1, there exists
$t^{k}\in\left(s_{k},s_{k}^{\prime}\right)$, such that

$\cos(\tilde{\bm{\theta}}\left(t^{k}\right))^{-2}-1\leq\frac{1}{k^{2}(1-\frac{e^{\frac{1}{2}}}{2})}.$
(12)

Furthermore,

$\left\|\hat{\bm{v}}\left(t^{k}\right)-\bar{\bm{v}}\right\|_{2}\leq\left\|\hat{\bm{v}}\left(t^{k}\right)-\hat{\bm{v}}\left(s_{k}\right)\right\|_{2}+\left\|\hat{\bm{v}}\left(s_{k}\right)-\overline{\bm{v}}\right\|_{2}\leq\frac{3\cdot
2^{L-1}}{(1-\frac{e^{\frac{1}{2}}}{2})}\frac{e^{\frac{1}{2}}}{L}\frac{1}{\tilde{\gamma}(t_{1})}\frac{1}{k}+\frac{1}{k}\rightarrow
0.$

Therefore, $\lim_{t\rightarrow\infty}\hat{\bm{v}}(t^{k})=\bar{\bm{v}}$.
Furthermore, by eq. (12) and Lemma 23, we have that
$\bm{v}(t^{k})/\tilde{q}_{\min}^{\frac{1}{L}}(\bm{v}(t^{k}))$ is an
($\varepsilon_{i}$, $\delta_{i}$) KKT point with
$\lim_{i\rightarrow\infty}\varepsilon_{i}=\lim_{i\rightarrow\infty}\delta_{i}=0$.
Since

$\bm{v}(t^{k})/\tilde{q}_{\min}^{\frac{1}{L}}(\bm{v}(t^{k}))=\hat{\bm{v}}(t^{k})/\gamma(t^{k}),$

and $\gamma(t^{k})$ converges to a positive number, we further have

$\lim_{k\rightarrow\infty}\bm{v}(t^{k})/\tilde{q}_{\min}^{\frac{1}{L}}(\bm{v}(t^{k}))=\bar{\bm{v}}/\lim_{k\rightarrow\infty}\gamma(t^{k})^{\frac{1}{L}},$

is a KKT point of $(P)$, and along the same direction of $\bar{\bm{v}}$.

The proof is completed. ∎

###  B.5 convergent Direction of AdaGrad and RMSProp: Theorems 5 and 6

First of all, we prove Theorem 5 by substitute $\bm{v}$ in Theorem 4 with
$\bm{h}_{\infty}\odot\bm{w}$.

###### Proof of Theorem 5.

Let $\bar{\bm{w}}$ be any limit point of series
$\\{\hat{\bm{w}}(t)\\}_{t=0}^{\infty}$. Since
$\bm{v}(t)=\bm{h}^{-\frac{1}{2}}_{\infty}\odot\bm{w}(t)$,
$\widehat{\bm{h}^{-\frac{1}{2}}_{\infty}\odot\bar{\bm{w}}}$ is a limit point
of $\\{\hat{\bm{v}}(t)\\}$. By Theorem 4,
$\widehat{\bm{h}^{-\frac{1}{2}}_{\infty}\odot\bar{\bm{w}}}/\tilde{q}_{\min}\left(\widehat{\bm{h}^{-\frac{1}{2}}_{\infty}\odot\bar{\bm{w}}}\right)^{1/L}=\bm{h}^{-\frac{1}{2}}_{\infty}\odot\bar{\bm{w}}/q_{\min}(\bar{\bm{w}})^{1/L}$
is a KKT point of $(\tilde{P})$. Therefore, there exist non-negative reals
$\\{\lambda_{i}\\}_{i=1}^{N}$, such that

$\displaystyle\bm{h}^{-\frac{1}{2}}_{\infty}\odot\bar{\bm{w}}/q_{\min}(\bar{\bm{w}})^{1/L}=\sum_{i=1}^{N}\lambda_{i}\partial^{\circ}\tilde{q}_{i}(\bm{h}^{-\frac{1}{2}}_{\infty}\odot\bar{\bm{w}}/q_{\min}(\bar{\bm{w}})^{1/L}),$
$\displaystyle\sum_{i=1}^{N}\lambda_{i}(\tilde{q}_{i}(\bm{h}^{-\frac{1}{2}}_{\infty}\odot\bar{\bm{w}}/q_{\min}(\bar{\bm{w}})^{1/L})-1)=0.$

Applying the relationship between $\tilde{q}_{i}$ and $q_{i}$, we then have

$\displaystyle\bm{h}^{-1}_{\infty}\odot\bar{\bm{w}}/q_{\min}(\bar{\bm{w}})^{1/L}=\sum_{i=1}^{N}\lambda_{i}\partial^{\circ}q_{i}(\bar{\bm{w}}/q_{\min}(\bar{\bm{w}})^{1/L}),$
$\displaystyle\sum_{i=1}^{N}\lambda_{i}(q_{i}(\bar{\bm{w}}/q_{\min}(\bar{\bm{w}})^{1/L})-1)=0.$

The proof is completed. ∎

Theorem 6 can be obtained in the same way.

###### Proof of Theorem 6.

The claim holds since $\bm{v}^{R}$ is just $\bm{w}$ with a positive scaling
factor, $\bm{v}^{R}$ and $\bm{w}$ share the same direction.

The proof is completed.

∎

###  B.6 Convergence Rate of Empirical Loss and Parameter Norm

In this section, we will give a tight bound for the convergence rate of
empirical loss and parameter norm, which is derived by estimating $G(x)$ in
Lemma 22.

######  Theorem 8.

Let $\bm{v}$ obey an adaptive gradient flow $\mathcal{F}$ with empirical loss
$\tilde{L}$ satisfying Assumption 1. Let $G(x)$ be defined as Lemma 22, i.e.,

$G(x)=\int_{\frac{1}{\tilde{\mathcal{L}}(t_{1})}}^{x}\frac{g^{\prime}\left(\log
z\right)^{2}}{g\left(\log z\right)^{2-2/L}}\cdot dz.$

Then $G(x)=\Theta(x(\log x)^{\frac{2}{L}-2})$, and $G^{-1}(x)=\Theta(x(\log
x)^{2-\frac{2}{L}})$. Consequently,

$\tilde{\mathcal{L}}(t)=\Theta\left(\frac{1}{t\log
t^{2-\frac{2}{L}}}\right),\text{ and }\|\bm{v}(t)\|=\Theta\left(\frac{1}{\log
t^{\frac{1}{L}}}\right).$

###### Proof.

For any large enough $x$,

$\displaystyle G(x)$
$\displaystyle=\int_{\frac{1}{\tilde{\mathcal{L}}(t_{1})}}^{x}\frac{g^{\prime}\left(\log
z\right)^{2}}{g\left(\log z\right)^{2-2/L}}\cdot dz$
$\displaystyle\overset{(*)}{=}\Theta\left(\int_{\frac{1}{\tilde{\mathcal{L}}(t_{1})}}^{x}\frac{g\left(\log
z\right)^{2/L}}{(\log z)^{2}}\cdot dz\right)$
$\displaystyle=\Theta\left(\int_{\frac{1}{\tilde{\mathcal{L}}(t_{1})}}^{x}\frac{1}{(\log
z)^{2-\frac{2}{L}}}\cdot dz\right)$ $\displaystyle=\Theta\left(x(\log
x)^{\frac{2}{L}-2}\right),$

where eq. $(*)$ is due to Lemma 8.

Since $G(x)$ is monotonously increasing, and
$\lim_{x\rightarrow\infty}G(x)=\infty$, we have $x=\Theta\left(G^{-1}(x)(\log
G^{-1}(x))^{\frac{2}{L}-2}\right)$, which further leads to
$G^{-1}(x)=\Theta(x(\log x)^{2-\frac{2}{L}})$.

Since $\frac{1}{\tilde{\mathcal{L}}(t)}=G^{-1}(\Omega(t))$, we have
$\frac{1}{\tilde{\mathcal{L}}(t)}=\Omega(t(\log t)^{2-\frac{2}{L}})$, which
further leads to $\tilde{\mathcal{L}}(t)=\mathcal{O}\left(\frac{1}{t(\log
t)^{2-\frac{2}{L}}}\right)$.

On the other hand,

$-\frac{\mathrm{d}\tilde{\mathcal{L}}(\bm{v}(t))}{\mathrm{d}t}=\left\|\bm{\beta}^{\frac{1}{2}}(t)\odot\bar{\partial}\tilde{\mathcal{L}}(t)\right\|_{2}^{2}\leq
2\left\|\bar{\partial}\tilde{\mathcal{L}}(t)\right\|_{2}^{2}=\mathcal{O}\left(\tilde{\mathcal{L}}(\bm{v}(t))g\left(\log\frac{1}{\tilde{\mathcal{L}}(t)}\right)^{1-\frac{1}{L}}\right),$

which leads to $\frac{1}{\tilde{\mathcal{L}}(t)}=G^{-1}(\mathcal{O}(t))$, and
$\tilde{\mathcal{L}}(t)=\Omega\left(\frac{1}{t(\log
t)^{2-\frac{2}{L}}}\right)$. Therefore,
$\tilde{\mathcal{L}}(t)=\Theta\left(\frac{1}{t(\log
t)^{2-\frac{2}{L}}}\right)$

By Lemma 19,
$\|\bm{v}(t)\|^{L}=\Theta\left(\log\frac{1}{\tilde{\mathcal{L}}(t)}\right)$,
which leads to $\|\bm{v}(t)\|=\Theta\left(\frac{1}{\log
t^{\frac{1}{L}}}\right)$.

The proof is completed. ∎

The convergent behavior of $\bar{\partial}\tilde{\mathcal{L}}(\bm{v}(t))$ can
be derived immediately by the above Theorem.

######  Corollary 2.

Let $\bm{v}$ obey an adaptive gradient flow $\mathcal{F}$ with empirical loss
$\tilde{L}$ satisfying Assumption 1. Then,
$\|\bar{\partial}\tilde{\mathcal{L}}(\bm{v}(t))\|=\Theta\left(\frac{1}{t(\log
t)^{1-\frac{1}{L}}}\right)$.

###### Proof.

Since

$\Omega\left(\tilde{\mathcal{L}}(\bm{v}(t))\|\bm{v}(t)\|^{L-1}\right)=\langle\bar{\partial}\tilde{\mathcal{L}}(\bm{v}(t)),\hat{\bm{v}}(t)\rangle\leq\|\bar{\partial}\tilde{\mathcal{L}}(\bm{v}(t))\|=\mathcal{O}\left(\tilde{\mathcal{L}}(\bm{v}(t))\|\bm{v}(t)\|^{L-1}\right),$

the proof is completed.

∎

##  Appendix C Proof of Theorem 7

In this section, we will prove that direction of parameters converges, that
is, $\lim_{t\rightarrow\infty}\frac{\bm{v}(t)}{\|\bm{v}(t)\|}$ exists.
Concretely, define the length swept by $\frac{\bm{v}(t)}{\|\bm{v}(t)\|}$ as
$\zeta(t)$, i.e.,

$\zeta(t)=\int_{0}^{t}\left\|\frac{\mathrm{d}\hat{\bm{v}}(\tau)}{\mathrm{d}\tau}\right\|\mathrm{d}\tau.$

We will upper bound $\zeta(t)$ in rest of this section.

To begin with, we define another surrogate margin $\bar{\gamma}$ as

$\bar{\gamma}(\bm{v})=\frac{\log\frac{1}{\mathcal{L}(\bm{v})}}{\|\bm{v}\|^{L}}+e^{-\tilde{\mathcal{L}}(\bm{v})}.$

The following Lemma then lower bound the derivative of $\bar{\gamma}$.

######  Lemma 27.

For large enough $t$, we have

$\frac{\mathrm{d}\bar{\gamma}(\bm{v}(t))}{\mathrm{d}t}\geq\frac{1}{2}\left(\left\|\bar{\partial}_{\backslash\backslash}\bar{\gamma}\left(\bm{v}(t)\right)\right\|\left\|\bar{\partial}_{\backslash\backslash}\tilde{\mathcal{L}}\left(\bm{v}(t)\right)\right\|+\left\|\bar{\partial}_{\perp}\bar{\gamma}\left(\bm{v}(t)\right)\right\|\left\|\bar{\partial}_{\perp}\tilde{\mathcal{L}}\left(\bm{v}(t)\right)\right\|\right),$

and

$\frac{\mathrm{d}\zeta(t)}{\mathrm{d}t}=\frac{\left\|(\bm{\beta}(t)\odot\bar{\partial}\tilde{\mathcal{L}}\left(\bm{v}(t)\right))_{\perp}\right\|}{\left\|\bm{v}(t)\right\|}.$

###### Proof.

To begin with, we calculate the rate of $\bm{\beta}$ converging to
$\mathbf{1}_{p}$. For AdaGrad, given a fixed index $i\in[N]$, we have that,

$\displaystyle 0\leq\bm{\beta}_{i}(t)-1=$
$\displaystyle(\bm{h}_{\infty})^{-1}_{i}(\bm{h}_{i}(t)-(\bm{h}_{\infty})_{i})$
$\displaystyle=$ $\displaystyle\Theta(\bm{h}_{i}(t)-(\bm{h}_{\infty})_{i})$
$\displaystyle=$
$\displaystyle\Theta\left(\int_{t}^{\infty}\bar{\partial}\mathcal{L}(\bm{w}(\tau))^{2}d\tau\right)$
$\displaystyle=$
$\displaystyle\Theta\left(\int_{t}^{\infty}\frac{1}{\tau^{2}(\log\tau)^{2-\frac{2}{L}}}d\tau\right)$
$\displaystyle=$ $\displaystyle\mathcal{O}\left(\frac{1}{t(\log
t)^{2-\frac{2}{L}}}\right).$ (13)

Similarly, for RMSProp, given a fixed index $i\in[N]$,

$\displaystyle 0$ $\displaystyle\leq
1-\frac{\sqrt{\varepsilon}}{\sqrt{\varepsilon+(1-b)\int_{0}^{t}e^{-(1-b)(t-\tau)}(\bar{\partial}\mathcal{L}(\tau))_{i}^{2}\mathrm{d}\tau}}=\Theta\left((1-b)\int_{0}^{t}e^{-(1-b)(t-\tau)}(\bar{\partial}\mathcal{L}(\tau))_{i}^{2}\mathrm{d}\tau\right)$
$\displaystyle=$
$\displaystyle\Theta\left((1-b)\int_{0}^{t-\sqrt{t}}e^{-(1-b)(t-\tau)}(\bar{\partial}\mathcal{L}(\tau))_{i}^{2}\mathrm{d}\tau\right)+\Theta\left((1-b)\int_{t-\sqrt{t}}^{t}e^{-(1-b)(t-\tau)}(\bar{\partial}\mathcal{L}(\tau))_{i}^{2}\mathrm{d}\tau\right)$
$\displaystyle=$
$\displaystyle\mathcal{O}\left((1-b)e^{-(1-b)\sqrt{t}}\int_{0}^{\infty}(\bar{\partial}\tilde{\mathcal{L}}(\tau))_{i}^{2}\mathrm{d}\tau\right)+\mathcal{O}\left((1-b)\frac{\sqrt{t}}{(t-\sqrt{t})^{2}}\right)$
$\displaystyle=$
$\displaystyle\mathcal{O}\left(\frac{1}{t^{\frac{3}{2}}}\right)=\mathcal{O}\left(\frac{1}{t(\log
t)^{2-\frac{2}{L}}}\right).$

We then directly calculate the derivative of $\bar{\gamma}$:

$\displaystyle\frac{\mathrm{d}\bar{\gamma}(\bm{v}(t))}{\mathrm{d}t}=$
$\displaystyle\langle\bar{\partial}\bar{\gamma}(\bm{v}(t)),\frac{d\bm{v}(t)}{dt}\rangle$
$\displaystyle=$
$\displaystyle\left\langle-\frac{\bar{\partial}\tilde{\mathcal{L}}}{\tilde{\mathcal{L}}\|\bm{v}(t)\|^{L}}-L\frac{\log\frac{1}{\mathcal{L}}}{\|\bm{v}(t)\|^{L+1}}\hat{\bm{v}}(t)-e^{-\tilde{\mathcal{L}}}\bar{\partial}\tilde{\mathcal{L}},\frac{d\bm{v}(t)}{dt}\right\rangle$
$\displaystyle=$
$\displaystyle\left\langle\frac{\bar{\partial}\tilde{\mathcal{L}}}{\tilde{\mathcal{L}}\|\bm{v}(t)\|^{L}}+L\frac{\log\frac{1}{\mathcal{L}}}{\|\bm{v}(t)\|^{L+1}}\hat{\bm{v}}(t)+e^{-\tilde{\mathcal{L}}}\bar{\partial}\tilde{\mathcal{L}},\bm{\beta}(t)\odot\bar{\partial}\tilde{\mathcal{L}}\right\rangle$
$\displaystyle=$
$\displaystyle\left\langle\frac{\bar{\partial}\tilde{\mathcal{L}}}{\tilde{\mathcal{L}}\|\bm{v}(t)\|^{L}}+L\frac{\log\frac{1}{\mathcal{L}}}{\|\bm{v}(t)\|^{L+1}}\hat{\bm{v}}(t),\bar{\partial}\tilde{\mathcal{L}}\right\rangle+\left\langle
e^{-\tilde{\mathcal{L}}}\bar{\partial}\tilde{\mathcal{L}},\bm{\beta}(t)\odot\bar{\partial}\tilde{\mathcal{L}}\right\rangle$
$\displaystyle+$
$\displaystyle\left\langle\frac{\bar{\partial}\tilde{\mathcal{L}(\bm{v}(t))}}{\tilde{\mathcal{L}}\|\bm{v}(t)\|^{L}}+L\frac{\log\frac{1}{\mathcal{L}}}{\|\bm{v}(t)\|^{L+1}}\hat{\bm{v}}(t),(\mathbf{1}-\bm{\beta}(t))\odot\bar{\partial}\tilde{\mathcal{L}}\right\rangle.$

The final term can be further bounded as follows:

$\displaystyle\left|\left\langle\frac{\bar{\partial}\tilde{\mathcal{L}}}{\tilde{\mathcal{L}}\|\bm{v}(t)\|^{L}}+L\frac{\log\frac{1}{\mathcal{L}}}{\|\bm{v}(t)\|^{L+1}}\hat{\bm{v}},(\mathbf{1}-\bm{\beta}(t))\odot\bar{\partial}\tilde{\mathcal{L}}\right\rangle\right|$
$\displaystyle\leq$
$\displaystyle\|\mathbf{1}-\bm{\beta}(t)\|_{\infty}\left\|\frac{\bar{\partial}\tilde{\mathcal{L}}}{\tilde{\mathcal{L}}\|\bm{v}(t)\|^{L}}+L\frac{\log\frac{1}{\mathcal{L}}}{\|\bm{v}(t)\|^{L+1}}\hat{\bm{v}}\right\|\|\bar{\partial}\tilde{\mathcal{L}}\|$
$\displaystyle\leq$ $\displaystyle\mathcal{O}\left(\frac{1}{t(\log
t)^{2-\frac{2}{L}}}\right)\mathcal{O}\left(\frac{1}{\|\bm{v}(t)\|}\right)\|\bar{\partial}\tilde{\mathcal{L}}\|$
$\displaystyle=$
$\displaystyle\mathcal{O}\left(\tilde{\mathcal{L}}(\bm{v}(t))\right)\mathcal{O}\left(\frac{1}{\|\bm{v}(t)\|}\right)\|\bar{\partial}\tilde{\mathcal{L}}\|$
$\displaystyle=$
$\displaystyle\mathcal{O}\left(\frac{1}{\|\bm{v}(t)\|^{L}}\right)\|\bar{\partial}\tilde{\mathcal{L}}\|^{2}.$

On the other hand,

$\left\langle
e^{-\tilde{\mathcal{L}}(\bm{v}(t))}\bar{\partial}\tilde{\mathcal{L}}(\bm{v}(t)),\bm{\beta}(t)\odot\bar{\partial}\tilde{\mathcal{L}}(\bm{v}(t))\right\rangle=\Theta(\|\bar{\partial}\tilde{\mathcal{L}}(\bm{v}(t))\|^{2}).$

Therefore, there exists a large enough $T$, such that, any $t\geq T$,

$\displaystyle\left\langle
e^{-\tilde{\mathcal{L}}}\bar{\partial}\tilde{\mathcal{L}}(\bm{v}(t)),\bm{\beta}(t)\odot\bar{\partial}\tilde{\mathcal{L}}(\bm{v}(t))\right\rangle+\left\langle\frac{\bar{\partial}\tilde{\mathcal{L}}}{\tilde{\mathcal{L}}\|\bm{v}(t)\|^{L}}+L\frac{\log\frac{1}{\mathcal{L}}}{\|\bm{v}(t)\|^{L+1}}\hat{\bm{v}},(\mathbf{1}-\bm{\beta}(t))\odot\bar{\partial}\tilde{\mathcal{L}}(\bm{v}(t))\right\rangle$
$\displaystyle\geq$ $\displaystyle\frac{1}{2}\left\langle
e^{-\tilde{\mathcal{L}}(\bm{v}(t))}\bar{\partial}\tilde{\mathcal{L}}(\bm{v}(t)),\bar{\partial}\tilde{\mathcal{L}}(\bm{v}(t))\right\rangle,$

which further leads to

$\frac{\mathrm{d}\bar{\gamma}(\bm{v}(t))}{\mathrm{d}t}\geq\frac{1}{2}\left\langle
e^{-\tilde{\mathcal{L}}(\bm{v}(t))}\bar{\partial}\tilde{\mathcal{L}}(\bm{v}(t)),\bar{\partial}\tilde{\mathcal{L}}(\bm{v}(t))\right\rangle+\left\langle\frac{\bar{\partial}\tilde{\mathcal{L}}(\bm{v}(t))}{\tilde{\mathcal{L}}(\bm{v}(t))\|\bm{v}(t)\|^{L}}+L\frac{\log\frac{1}{\tilde{\mathcal{L}}(\bm{v}(t))}}{\|\bm{v}(t)\|^{L+1}}\hat{\bm{v}},\bar{\partial}\tilde{\mathcal{L}}(\bm{v}(t))\right\rangle.$

We then calculate axial component and radial component of
$e^{-\tilde{\mathcal{L}}(\bm{v})}\bar{\partial}\tilde{\mathcal{L}}(\bm{v})$,
$\frac{\bar{\partial}\tilde{\mathcal{L}}(\bm{v})}{\tilde{\mathcal{L}}(\bm{v})\|\bm{v}\|^{L}}+L\frac{\log\frac{1}{\tilde{\mathcal{L}}(\bm{v})}}{\|\bm{v}\|^{L+1}}\hat{\bm{v}}$,
and $\bar{\partial}\tilde{\mathcal{L}}(\bm{v})$ respectively as follows:

$\displaystyle\left(e^{-\tilde{\mathcal{L}}(\bm{v})}\bar{\partial}\tilde{\mathcal{L}}(\bm{v})\right)_{\backslash\backslash}=\langle
e^{-\tilde{\mathcal{L}}(\bm{v})}\bar{\partial}\tilde{\mathcal{L}}(\bm{v}),\hat{\bm{v}}\rangle\hat{\bm{v}},$
$\displaystyle\left(e^{-\tilde{\mathcal{L}}(\bm{v})}\bar{\partial}\tilde{\mathcal{L}}(\bm{v})\right)_{\perp}=e^{-\tilde{\mathcal{L}}(\bm{v})}(\bar{\partial}\tilde{\mathcal{L}}(\bm{v})-\langle\bar{\partial}\tilde{\mathcal{L}}(\bm{v}),\hat{\bm{v}}\rangle\hat{\bm{v}}),$
$\displaystyle\left(\frac{\bar{\partial}\tilde{\mathcal{L}}(\bm{v})}{\tilde{\mathcal{L}}(\bm{v})\|\bm{v}\|^{L}}+L\frac{\log\frac{1}{\tilde{\mathcal{L}}(\bm{v})}}{\|\bm{v}\|^{L+1}}\hat{\bm{v}}\right)_{\backslash\backslash}=L\frac{\log\frac{1}{\mathcal{L}}(\bm{v})}{\|\bm{v}\|^{L+1}}\hat{\bm{v}}+\frac{\langle\bar{\partial}\tilde{\mathcal{L}}(\bm{v}),\hat{\bm{v}}\rangle}{\tilde{\mathcal{L}}(\bm{v})\|\bm{v}\|^{L}}\hat{\bm{v}},$
$\displaystyle\left(\frac{\bar{\partial}\tilde{\mathcal{L}}(\bm{v})}{\tilde{\mathcal{L}}(\bm{v})\|\bm{v}\|^{L}}+L\frac{\log\frac{1}{\tilde{\mathcal{L}}(\bm{v})}}{\|\bm{v}\|^{L+1}}\hat{\bm{v}}\right)_{\perp}=\frac{\bar{\partial}\tilde{\mathcal{L}}(\bm{v})-\langle\bar{\partial}\tilde{\mathcal{L}}(\bm{v}),\hat{\bm{v}}\rangle\hat{\bm{v}}}{\tilde{\mathcal{L}}\|\bm{v}\|^{L}},$
$\displaystyle\left(\bar{\partial}\tilde{\mathcal{L}}(\bm{v})\right)_{\backslash\backslash}=\langle\bar{\partial}\tilde{\mathcal{L}}(\bm{v}),\hat{\bm{v}}\rangle\hat{\bm{v}}$
$\displaystyle\left(\bar{\partial}\tilde{\mathcal{L}}(\bm{v})\right)_{\perp}=\bar{\partial}\tilde{\mathcal{L}}(\bm{v})-\langle\bar{\partial}\tilde{\mathcal{L}}(\bm{v}),\hat{\bm{v}}\rangle\hat{\bm{v}}.$

Therefore,

$\displaystyle\frac{1}{2}\left\langle
e^{-\tilde{\mathcal{L}}(\bm{v}(t))}\bar{\partial}\tilde{\mathcal{L}}(\bm{v}(t)),\bar{\partial}\tilde{\mathcal{L}}(\bm{v}(t))\right\rangle+\left\langle\frac{\bar{\partial}\tilde{\mathcal{L}}(\bm{v}(t))}{\tilde{\mathcal{L}}(\bm{v}(t))\|\bm{v}(t)\|^{L}}+L\frac{\log\frac{1}{\tilde{\mathcal{L}}(\bm{v}(t))}}{\|\bm{v}\|^{L+1}}\hat{\bm{v}}(t),\bar{\partial}\tilde{\mathcal{L}}(\bm{v}(t))\right\rangle$
$\displaystyle=$
$\displaystyle\frac{1}{2}\left\langle\left(e^{-\tilde{\mathcal{L}}(\bm{v}(t))}\bar{\partial}\tilde{\mathcal{L}}(\bm{v}(t))\right)_{\backslash\backslash}+\left(e^{-\tilde{\mathcal{L}}(\bm{v}(t))}\bar{\partial}\tilde{\mathcal{L}}(\bm{v}(t))\right)_{\perp},\left(\bar{\partial}\tilde{\mathcal{L}}(\bm{v}(t))\right)_{\backslash\backslash}+\left(\bar{\partial}\tilde{\mathcal{L}}(\bm{v}(t))\right)_{\perp}\right\rangle$
$\displaystyle+$
$\displaystyle\left\langle\left(\frac{\bar{\partial}\tilde{\mathcal{L}}(\bm{v}(t))}{\tilde{\mathcal{L}}(\bm{v}(t))\|\bm{v}(t)\|^{L}}+L\frac{\log\frac{1}{\tilde{\mathcal{L}}(\bm{v}(t))}}{\|\bm{v}(t)\|^{L+1}}\hat{\bm{v}}(t)\right)_{\backslash\backslash}+\left(\frac{\bar{\partial}\tilde{\mathcal{L}}(\bm{v}(t))}{\tilde{\mathcal{L}}(\bm{v}(t))\|\bm{v}(t)\|^{L}}+L\frac{\log\frac{1}{\tilde{\mathcal{L}}(\bm{v}(t))}}{\|\bm{v}(t)\|^{L+1}}\hat{\bm{v}}(t)\right)_{\perp},\right.$
$\displaystyle\left.\left(\bar{\partial}\tilde{\mathcal{L}}(\bm{v}(t))\right)_{\backslash\backslash}+\left(\bar{\partial}\tilde{\mathcal{L}}(\bm{v}(t))\right)_{\perp}\right\rangle$
$\displaystyle\overset{(*)}{=}$
$\displaystyle\frac{1}{2}\left(\left\|\left(e^{-\tilde{\mathcal{L}}(\bm{v}(t))}\bar{\partial}\tilde{\mathcal{L}}(\bm{v}(t))\right)_{\backslash\backslash}\right\|\left\|\left(\bar{\partial}\tilde{\mathcal{L}}(\bm{v}(t))\right)_{\backslash\backslash}\right\|+\left\|\left(e^{-\tilde{\mathcal{L}}(\bm{v}(t))}\bar{\partial}\tilde{\mathcal{L}}(\bm{v}(t))\right)_{\perp}\right\|\left\|\left(\bar{\partial}\tilde{\mathcal{L}}(\bm{v}(t))\right)_{\perp}\right\|\right)$
$\displaystyle+$
$\displaystyle\left\|\left(\frac{\bar{\partial}\tilde{\mathcal{L}}(\bm{v}(t))}{\tilde{\mathcal{L}}(\bm{v}(t))\|\bm{v}(t)\|^{L}}+L\frac{\log\frac{1}{\tilde{\mathcal{L}}(\bm{v}(t))}}{\|\bm{v}(t)\|^{L+1}}\hat{\bm{v}}(t)\right)_{\backslash\backslash}\right\|\left\|\left(\bar{\partial}\tilde{\mathcal{L}}(\bm{v}(t))\right)_{\backslash\backslash}\right\|$
$\displaystyle+$
$\displaystyle\left\|\left(\frac{\bar{\partial}\tilde{\mathcal{L}}(\bm{v}(t))}{\tilde{\mathcal{L}}(\bm{v}(t))\|\bm{v}(t)\|^{L}}+L\frac{\log\frac{1}{\tilde{\mathcal{L}}(\bm{v}(t))}}{\|\bm{v}(t)\|^{L+1}}\hat{\bm{v}}(t)\right)_{\perp}\right\|\left\|\left(\bar{\partial}\tilde{\mathcal{L}}(\bm{v}(t))\right)_{\perp}\right\|$
$\displaystyle\geq$
$\displaystyle\frac{1}{2}\left\|\left(e^{-\tilde{\mathcal{L}}(\bm{v}(t))}\bar{\partial}\tilde{\mathcal{L}}(\bm{v}(t))+\frac{\bar{\partial}\tilde{\mathcal{L}}(\bm{v}(t))}{\tilde{\mathcal{L}}(\bm{v}(t))\|\bm{v}(t)\|^{L}}+L\frac{\log\frac{1}{\tilde{\mathcal{L}}(\bm{v}(t))}}{\|\bm{v}(t)\|^{L+1}}\hat{\bm{v}}(t)\right)_{\backslash\backslash}\right\|\left\|\left(\bar{\partial}\tilde{\mathcal{L}}(\bm{v}(t))\right)_{\backslash\backslash}\right\|$
$\displaystyle+$
$\displaystyle\frac{1}{2}\left\|\left(e^{-\tilde{\mathcal{L}}(\bm{v}(t))}\bar{\partial}\tilde{\mathcal{L}}(\bm{v}(t))+\frac{\bar{\partial}\tilde{\mathcal{L}}(\bm{v}(t))}{\tilde{\mathcal{L}}(\bm{v}(t))\|\bm{v}(t)\|^{L}}+L\frac{\log\frac{1}{\tilde{\mathcal{L}}(\bm{v}(t))}}{\|\bm{v}(t)\|^{L+1}}\hat{\bm{v}}(t)\right)_{\perp}\right\|\left\|\left(\bar{\partial}\tilde{\mathcal{L}}(\bm{v}(t))\right)_{\perp}\right\|,$

where eq. $(*)$ is because

$\displaystyle\langle
e^{-\tilde{\mathcal{L}}(\bm{v}(t))}\bar{\partial}\tilde{\mathcal{L}}(\bm{v}(t)),\hat{\bm{v}}(t)\rangle=-e^{-\tilde{\mathcal{L}}(\bm{v}(t))}\langle-\bar{\partial}\tilde{\mathcal{L}}(\bm{v}(t)),\hat{\bm{v}}(t)\rangle<0,$
$\displaystyle e^{-\tilde{\mathcal{L}}(\bm{v}(t))}>0,$ $\displaystyle