text:
\section{Introduction}

Heavy Ball (a.k.a. Polyak's momentum) \citep{P64}
has become a dominant momentum method in various machine learning applications,
see e.g., \citep{Rnet16,KSH12,WRSSR17}. Many recently proposed algorithms
incorporate Heavy Ball momentum in lieu of Nesterov's momentum \citep{N13}, e.g.,
Adam \citep{KB15}, AMSGrad \citep{RKK18}, and a normalized momentum method \cite{CM21}, to name just a few.
Despite its success in practice, theoretical results of acceleration via Heavy Ball are sparse in the literature. Indeed, the strongly convex quadratic problems seem to be one of very few cases for which an acceleration via HB is shown (e.g., \citet{LRP16,GFJ15,LR17,PP21,CGZ19,SP20,NB15,DJ19,SDJS18,wang2018acceleration,WCA20,LGY20,XCHZ20,JKKNS18}). Recently, \citep{WLA21} provably show that HB converges faster than vanilla gradient descent (GD) for training an over-parametrized ReLU network and a deep linear network.
They show an accelerated linear rate that has a square root dependency on the conditional number of a certain Gram matrix, which improves the linear rate of GD for those problems. They develop a modular analysis of acceleration when the HB dynamic meets certain conditions. The conditions essentially require that an underlying Gram matrix or the Hessian does not deviate too much from that at the beginning.
Therefore, their theorem might not be applied to the case when the iterate does move far away from the initial point.
This limitation to acceleration, to our knowledge, appears in all the related works of the discrete-time HB. What is lacking in the HB literature is a provable acceleration when the Hessian can deviate significantly from that at the beginning  during the optimization process.

\begin{algorithm}[t]
\begin{algorithmic}[1]
\small
\caption{Heavy Ball (Equivalent Version 1) }
\label{alg:HB2}
\STATE Required: the step size $\eta$ and the momentum parameter $\beta_{t} \in [0,1]$
\STATE Init: $w_{0} = w_{-1} \in \mathbb{R}^d $
\FOR{$t=0$ to $T$}
\STATE Given current iterate $w_t$, compute gradient $\nabla f(w_t)$.
\STATE Update iterate $w_{t+1} = w_t - \eta \nabla f(w_t) + \beta_t ( w_t - w_{t-1} )$.
\ENDFOR
\end{algorithmic}
\vspace{-0.03in}
\end{algorithm}

This work aims at filling the gap. We develop a technical result that proves acceleration of HB when the Hessian can change substantially under certain conditions. Specifically, our analysis shows that HB has acceleration compared to GD for a class of Polyak-\L{}ojasiewicz problems when the non-convexity is averaged-out (to be elaborated soon).
The PL condition \citep{P63,KNS16} is sufficient
to show a global linear convergence rate for GD without the need of assuming strong convexity.
The notion of PL has been discovered in various non-convex problems over the past few years, e.g., computing the Wasserstein-barycenter of Gaussian distributions \citep{ACGS21}, minimizing a Wasserstein distance using point clouds \citep{MSS21}, training over-parametrized neural networks with smooth activation functions \citep{OS19,LZB21}, and sparse optimization on a certain measure \citep{C21}.
However, as far as we are aware, momentum methods (not necessarily HB) haven't been shown to converge faster than GD under PL in discrete time. Indeed, \citet{KDP18} show a global linear convergence of the discrete-time HB under PL, but the rate is not better than that of GD, c.f., \citep{KNS16}.
While in continuous time, some linear rates of HB under PL are established, e.g., \citep{ADR20,AGV21}, it is not clear if the rates
do show a benefit of the use of HB compared to GD,
and is neither clear if the result can be carried over in the discrete time. In convex optimization, it is known that Nesterov's momentum and HB share the same ODE in continuous time \citep{SDJS18}. Yet, the
acceleration disappears when one discretizes the dynamic of HB and bounds the discretization error.
To our knowledge, provably showing any benefit of discrete-time momentum under PL is still an open problem in optimization.

In this paper, we show that the discrete-time HB has an accelerated linear rate under PL when the non-convexity is averaged-out.
To explain this notion further, we need to introduce a quantity called average Hessian.
\begin{definition}
Let $w_* \in \mathbb{R}^{d}$ be a global minimizer of a twice differentiable function $f(w): \mathbb{R}^{d} \rightarrow \mathbb{R}$. We define the \textbf{average Hessian} of $f(\cdot)$ at $w \in \mathbb{R}^{d}$ to be:
\begin{equation} \label{avgH}%
H_f(w) :=  \int_0^1 \nabla^2 f (\theta w + (1-\theta) w_* ) d \theta.
\end{equation}
We say that \textbf{the non-convexity of $f(\cdot)$ between $w$ and $w_{*}$ is averaged-out}
with parameter $\lambda_{*}$ when the smallest eigenvalue of
the average Hessian satisfies $\lambda_{{\min}}(H_f(w)) \geq \lambda_{*}> 0$.
For brevity, we sometimes say $f(\cdot)$ satisfies \av{\lambda_*} at $w$.
\end{definition}
From \eqref{avgH}, it should be clear that the average Hessian at $w$ is the average Hessian between the line segment that connects $w$ and a global optimal point $w_{*}$.

To get a flavor of our main result, we give an informal theoretical statement as follows.
\\
\begin{mdframed}
\begin{theorem} (Informal version of Theorem~\ref{thm:meta})
Denote $w_{*}$ a global minimizer of $f(\cdot)$.
Suppose $f(\cdot)$ is twice differentiable, satisfies $\mu$-PL, has $L$-Lipschitz gradient and Hessian.
Apply HB to solve $\min_{w} f(w)$.
Assume that \av{\lambda_{\min}(H_f(w_t))} holds for all $t$.
Then, there exists a time $t_0 = \tilde{\Theta}(\frac{L}{\mu})$ such that for all $T > t_{0}$, the iterate $w_{T}$ of HB satisfies
\[
\| w_{T} - w_* \| = O\left( \prod_{t=t_0}^{T-1} \left(  1 - \Theta\left(\frac{1}{ \sqrt{\kappa_{t}}} \right)  \right) \right) \| w_{t_0} - w_* \|,
\]
where $\kappa_{t}:= \frac{L}{\lambda_{\min}(H_f(w_t)) }$ is the condition number of the average Hessian at $w_{t}$.
\end{theorem}
\end{mdframed}

To summarize, our contributions in this paper include:
\begin{itemize}
\item We develop an analysis of showing acceleration via HB beyond the quadratic problems, which can be of independent interest.
Our theoretical results reveal a way to check if incorporating the dynamic of momentum helps converge faster than GD under PL.
Our theoretical results will also show a benefit of adaptively setting the momentum parameter.
\item We show that \av{\lambda_*} implies PL. We provide some concrete examples for which \av{\lambda_*} holds.
\end{itemize}

\section{Preliminaries}

\iffalse
\begin{algorithm}[t]
\begin{algorithmic}[1]
\small
\caption{Heavy Ball (Equivalent Version 2)
} \label{alg:HB1}{}
\STATE Requires the step size $\eta$ and the momentum parameter $\beta_{t} = [\beta_{t,1}, \beta_{t,2}, \dots, \beta_{t,d} ]^\top  \in ([0,1]^d )^\top$.
\STATE Init: $w_{0} \in \mathbb{R}^d $ and $m_{-1} = 0 \in \mathbb{R}^d$.
\FOR{$t=0$ to $T$}
\STATE Update momentum $m_t = \beta_t \odot m_{t-1} +  \nabla f(w_t)$.
\STATE Update iterate $w_{t+1} = w_t - \eta m_t$.
\ENDFOR
\end{algorithmic}
\end{algorithm}
\fi

\noindent
\textbf{Notations:}
\iffalse
We denote $\beta_{t}:= [ \beta_{t,1}, \dots, \beta_t, \dots,  \beta_{t,d} ]^\top \in ([0,1]^d )^\top$ as the momentum parameter at time $t$.
The subscript $t$ will always be the time index. So $\beta_t \in [0,1]$ is the value of the momentum parameter for the $i_{\mathrm{th}}$ dimension at iteration $t$.
We will use $\odot$ to represent the element-wise product.
For example, $ \beta_{t} \odot w_t \in \mathbb{R}^d$
is a $d$-dimensional vector such that its element $i$ is
$\beta_t w_{{t,i}}$.
\fi
We use $\beta_{t} I_{d} \in \mathbb{R}^{{d \times d}}$ to denote a diagonal matrix on which each of its diagonal elements is $\beta_{t}$. We will have $\| M \|_2$ represent the spectral norm of a matrix $M$, i.e., $\|M \|_2 = \sqrt{ \lambda_{\max}( MM^*)}$, where $\lambda_{{\max}}(\cdot)$ is the largest eigenvalue of the underlying matrix, and $M^*$ is the conjugate transpose of the matrix $M$. We use $\| v \|_{2}$ as the $l_{2}$ norm of a vector $v$.
The notation $\text{Diag}( \cdots )$ in this paper represents a block-diagonal matrix that puts its arguments on the main diagonal.

\noindent
\textbf{Definitions:}
A function $f(\cdot)$ is $L$-smooth
if it has Lipschitz gradients, i.e., $\| \nabla f(x)- \nabla f(y) \|_{*} \leq L \| x - y\| $ for any $x,y$.
In this paper, we consider $l_{2}$ norm so that the dual norm is itself.
A function $f(\cdot)$ is $\nu$-strongly convex if $f(x) \geq f(y) + \langle \nabla f(y), x - y \rangle + \frac{\nu}{2} \| x - y \|^2$
for any $x,y$.
When $f(\cdot)$ is twice differentiable, the $\nu$-strong convexity is equivalent to the condition that the smallest eigenvalue of Hessian satisfies $\lambda_{{\min}}( \nabla^2 f(\cdot)) \geq \nu >0$.
A function $f(\cdot)$ is $\mu$-Polyak-\L{}ojasiewicz condition ($\mu$-PL) at $w$, if
$\| \nabla f(w) \|^2 \geq 2 \mu ( f(w) - \min_w f(w) ).$
Observe that if $\mu$-PL holds for all the points in the domain of $f(\cdot)$, then
all the stationary points are global minimizers of $f(\cdot)$. However, different from strongly convex functions, a PL-function does not necessarily have a unique global minimizer \citep{AGV21}.
An example is $f(w) = \frac{1}{2} w^{\top} A w$, where $A = A^{\top} \succeq 0$, which has $\arg\min f(w)=\mathrm{Ker}(A)$.
It is known that $\mu$-strongly convex implies $\mu$-PL \citep{KNS16}.

\subsection{Prior analysis of acceleration via HB}

Algorithm~\ref{alg:HB2} shows Heavy Ball, which has another
equivalent version presented in the appendix (Algorithm~\ref{alg:HB1}).
 Our presentations of HB cover the case of HB with a constant momentum parameter, i.e., when $\beta_{t} = \beta$,

 which was studied in all the aforementioned works of HB.

The HB dynamic can be written as
\begin{equation} \label{eq1}
\begin{split}
w_{t+1
& =  w_t  - \eta ( \nabla f(w_t) - \nabla f(w_*) ) + \beta_t  (w_t - w_{t-1} )
\\  &= w_t  - \eta \underbrace{ \left( \int_0^1 \nabla^2 f (\theta w_t + (1-\theta) w_* ) d \theta \right) }_{= H_f(w_t)} \left( w_t - w_*  \right) \\ & \quad + \beta_t ( w_t - w_{t-1} ),
\end{split}
\end{equation}
where in the first equality
we denoted $w_{*}$ an optimal point and used $\nabla f(w_*) = 0$, and
in the second equality, we used the fundamental theorem of calculus, i.e., $\nabla f(w_t) - \nabla f(w_*) = \left( \int_0^1 \nabla^2 f (\theta w_t + (1-\theta) w_* ) d \theta \right) \left( w_t - w_*  \right)  $.
Equation~\eqref{eq1} can be further rewritten as
\begin{equation} \label{dynamic}
\begin{split}
\begin{bmatrix}
w_{t+1} - w_* \\
w_{t} - w_*
\end{bmatrix}
 &
=
\underbrace{
\begin{bmatrix}
I_{d} - \eta H_t + \beta_t I_{d} & - \beta_t  I_{d}   \\
I_{d} & 0_{d}
\end{bmatrix}
}_{:= A_t}
\begin{bmatrix}
w_t - w_* \\
w_{t-1}- w_*
\end{bmatrix},
\end{split}
\end{equation}
where we defined $H_{t}:= H_f(w_t)$ for brevity.

The most well-known acceleration result of HB is about applying HB with a constant $\beta$ for solving the strongly convex quadratic problems,
$ \min_{w \in \mathbb{R}^d} \frac{1}{2} w^\top M w + b^\top w,$
where $M \in \mathbb{R}^{{d \times d}}$ is a positive-definite matrix that has
the largest eigenvalue
$\lambda_{\max}( M)= L$ and the smallest eigenvalue $\lambda_{\min}( M) =  \nu > 0$.
Let $H_{t} \gets M$ and $\beta_{t} \gets \beta$ in (\ref{dynamic})
and recursively expand the equation from time $t$ back to time $0$.
We have
\begin{equation}  \label{eq2}
\begin{bmatrix}
w_{t} - w_* \\
w_{t-1} - w_*
\end{bmatrix}
=
A^t
\begin{bmatrix}
w_0 - w_* \\
w_{-1}- w_*
\end{bmatrix}
,
\end{equation}
where
$A:=\begin{bmatrix}
I_{d} - \eta M + \beta I_{d} & - \beta  I_{d}   \\
I_{d} & 0_{d}
\end{bmatrix}
\in \mathbb{R}^{2d \times 2d}$
and $A^t$ is its $t_{\mathrm{th}}$ matrix power.
To get the convergence rate from \eqref{eq2}, there are two approaches in the literature, which are described in details in the following.

\textbf{Prior approach 1 (bounding the spectral radius):}
To upper-bound the convergence rate of the distance $\| w_t - w_* \|_2$ in \eqref{eq2}, it suffices to bound the spectral norm $\| A^t \|_{2}$.
Traditional analysis uses the spectral radius of $A$ to approximate the spectral norm $\| A^t \|_{2}$,
see e.g., \citep{P64,LRP16,R18,M19,OBP15}.
The spectral radius of a square (not necessarily symmetric)  matrix $A \in \mathbb{R}^{{2d \times 2d}}$ is defined as $\rho(A) := \max_{i \in [2d]} | \lambda_i(A)|$, where $\lambda_i(\cdot)$ is the $i_{\mathrm{th}}$ (possibly complex) eigenvalue.
By choosing the step size $\eta$ and the momentum parameter $\beta$ appropriately,
the spectral radius of $A$ in \eqref{eq2} is $\rho(A)=1 - c \frac{1}{\sqrt{\kappa}}$ for some constant $c>0$, where $\kappa:= \frac{L}{\nu}$ is the condition number.
Then, by Gelfand's formula \citep{G41}, one has for any square matrix $B$,
\begin{equation} \label{gel}
\text{ (Gelfand's formula) } \quad \| B^k \|_2 = \left( \rho(B) + \epsilon_k \right)^k,
\end{equation}
for some sequence $\{ \epsilon_k\}$ that converges to $0$ when $k \rightarrow \infty$. Hence the spectral norm $\| A^t \|_2$ can be approximated by the spectral radius raised to $t$, i.e., $\left(\rho(A)\right)^{t}$, in the sense that
$\| A^t \|_2 = \left( \left(1 - c \frac{1}{\sqrt{\kappa}}\right) + \epsilon_t \right)^t$. This suggests that
asymptotically the convergence rate of HB is an accelerated linear rate $O\left(1 - \Theta\left(\frac{1}{\sqrt{\kappa}}\right)\right)$, which is better than that of GD, i.e., $O\left(1-\Theta\left(\frac{1}{\kappa}\right)\right)$.
The weakness of this approach is that the convergence rate is not quantifiable at a finite $t$, because one generally cannot control the convergence rate $\epsilon_{t}$ in the Gelfand's formula. On the other hand,
one might suggest bounding the spectral norm $\| A \|_2$, since $\| A^t \|_2 \leq \|A \|_{2}^{t}$.
In Appendix~\ref{app:HB}, we show that $1 \leq \| A \|_2 $ for any $\beta \in [0,1]$ and any step size $\eta \leq \frac{1}{L}$, which implies that a convergence rate of HB cannot be obtained via this way.

\textbf{Prior approach 2 (bounding the matrix-power-vector product):}

Noting that controlling
the size of the matrix-power-vector product
$\left \|
A^t
\begin{bmatrix}
w_0 - w_* \\
w_{-1}- w_*
\end{bmatrix}
\right\|_2
$ is sufficient for controlling the convergence rate of the distance in \eqref{eq2},
\citet{WLA21} show that by choosing the step size $\eta = \frac{c_{\eta}}{L}$ and the momentum parameter $\beta = \left(1 - c \frac{1}{ \sqrt{\kappa} } \right)^2$ for some constant $c_{{\eta}}$ and $c >0$ appropriately,
one has
$\textstyle
\left \|
A^t
\begin{bmatrix}
w_0 - w_* \\
w_{-1}- w_*
\end{bmatrix}
\right\|_2
\leq 4 \sqrt{\kappa} \left( 1 - \frac{1}{2 \sqrt{\kappa}} \right)^t
\| w_0 - w_* \|
,$
which is a non-asymptotic accelerated linear rate and hence avoids the concern of the first approach.

\begin{table}[t]
\footnotesize
\begin{center}
\begin{tabular}{|c | c | c|}
 \hline
 Class of problems & Convergence rate  & Ref.\\
 \hline\hline
Strongly convex quadratic  & $\left(1- \Theta \left( \frac{1}{ \sqrt{\kappa} } \right) \right)^T$ & [1] \\ \hline
$L$-smooth $\nu$-strongly convex & $\dagger$  $\left(1- \Theta \left( \frac{\nu}{ L } \right) \right)^T$  & [2]   \\ \hline
 $L$-smooth convex  & $O\left(\frac{L}{T}\right)$ & [3]  \\ \hline
$L$-smooth $\mu$-PL & $\left(1- \Theta \left( \frac{\mu}{ L } \right) \right)^T$
& [4]  \\  \hline
 Over-parametrized  NN& $\ddagger$  $\left(1- \Theta \left( \frac{1}{ \sqrt{\kappa_0} } \right) \right)^T$ & [5]  \\ \hline
\end{tabular}
\end{center}
\caption{
\footnotesize
Existing results of the discrete-time HB convergence in terms of the optimality gap $f(w_T) - \min_w f(w)$.
References: [1] Theorem 9 in \cite{P64} and Theorem 7 in \cite{WLA21} . [2] Theorem 3 in \cite{KDP18}. $\dagger$ It is also known that a local acceleration happens when the iterate is sufficiently close to the global optimal point $w_{*}$ under an additional assumption that $f(\cdot)$ is twice-differentiable, see e.g., Theorem 8 in \citep{WLA21}. [3] Theorem 2 in \citep{GFJ15} and Theorem 9 in \citep{WAL21}.
[4] Theorem 3 in \citep{KDP18}. [5] Theorem 9-10 in \citep{WLA21}.
$\ddagger$ Here $\kappa_{0}$ is the condition number of the neural tangent kernel matrix of an over-parametrized neural network at initialization.
 } \label{table:rate}
\end{table}
\iffalse
\subsection{Polyak-\L{}ojasiewicz condition}

The PL condition (Definition~\ref{def:PL}) has been discovered to hold in some non-convex problems in recent years, e.g., \citep{ACGS21,LZB21,C21}.
The PL inequality is a special case of the Kurdyka-Lojasiewicz inequality. We refer the readers to \citep{ABRS10,BDL07} for details.
\begin{definition} \label{def:PL}
A function satisfies the $\mu$-Polyak-\L{}ojasiewicz condition ($\mu$-PL) if
for any $w$,
\begin{equation}
\| \nabla f(w) \|^2 \geq \frac{\mu}{2} ( f(w) - \min_w f(w) ).
\end{equation}
\end{definition}
The PL condition is sufficient for showing a linear convergence of GD without the need of assuming the strong convexity \citep{KNS16}. However, to our knowledge, discrete-time momentum methods have not been shown to be faster than GD under this condition.

\iffalse
The following lemma will be used to show certain problems satisfy PL in this paper.
\begin{lemma}[Appendix A in \cite{KNS16}] \label{err}
If a function $f(\cdot)$ is $L$-smooth and satisfies the error bound condition:
\begin{equation}
\| \nabla f(x) \| \geq \theta \| x_* - x \|, \forall x,
\end{equation}
where $x_{*}$ is the projection of $x$ on the the optimal set.
Then $f(\cdot)$ satisfies PL with the constant $\frac{\theta}{L}$.
\end{lemma}
\fi

\fi
\section{Analysis}

The goal of this section is to develop an analysis that enables showing acceleration beyond the quadratic problems. But to get the ball rolling, we start by discussing some technical difficulties of reaching the goal using
the prior approaches.

\subsection{Why do prior approaches of showing acceleration fail for non-quadratic problems?}

Recall we have the HB dynamic for minimizing a general twice differentiable function shown on \eqref{dynamic}. Recursively expanding \eqref{dynamic}, one gets
\begin{equation}  \label{eq3}
\begin{bmatrix}
w_{T} - w_* \\
w_{T-1} - w_*
\end{bmatrix}
=
\left( \prod_{t=0}^T
A_t
\right)
\begin{bmatrix}
w_0 - w_* \\
w_{-1}- w_*
\end{bmatrix},
\end{equation}
where $\prod_{t=0}^T A_t :=  A_{T} A_{{T-1}} \cdots A_{1} A_{0}$.
Therefore, a way to control the distance between $w_{T}$ and $w_{*}$ is to control the size of the spectral norm $\| \prod_{t=0}^T  A_t \|_{2}$.
The spectral radius approach would compute the spectral radius $\rho(A_t)$
and then invoke the Gelfand's formula \eqref{gel} (with $k=1$) for each step $t$, i.e.,
$\| A_t^1 \|_2 = \left( \rho(A_t) + \epsilon_{t,1} \right)^1$, where $\epsilon_{{t,1}}$ is the approximation error.
Then, one might hope $\| \prod_{t=0}^T  A_t \|_{2}$ or $\prod_{t=0}^T \| A_t \|_{2}$ could be approximated by $\prod_{{t=0}}^{T} \rho(A_t)$ well.

The issue is that for a small $k$, e.g., $k=1$, $\epsilon_{t,k}$ in the Gelfand's formula can be large, which makes the spectral radius a poor estimate of the spectral norm. Indeed, it is easy to cook up an example based on the matrix $A_{t}$ in \eqref{dynamic}. Let $d=1$ (one-dimensional), $\eta H_{t}=0.1$, and $\beta=0.9$. We have
\begin{equation}
\textstyle
A_t = \begin{bmatrix} 1 -0.1 + 0.9 &   -0.9 \\ 1  & 0 \end{bmatrix}.
\end{equation}
For this example, the spectral radius $\rho(A_{t})=0.9487$ and the spectral norm $\|A_t\|_{2}= 2.21$. So the approximation error is $\epsilon_{t,1} =2.21 - 0.9487 \approxeq 1.25$, which implies that the product $\prod_{{t=0}}^{T} \rho(A_t)$ can not be guaranteed to approximate the spectral norm arbitrarily well.
This example also shows that the spectral norm $\| A_t \|_{2}$
is not useful for analyzing the convergence rate, since it is larger than $1$
(see Appendix~\ref{app:HB} for more discussions).
To show a convergence,
we need to identity a quantity that is relevant to the convergence rate of the distance and has a non-trivial upper bound which is smaller than $1$.
One might consider bounding the spectral norm of the matrix product in \eqref{eq3} directly, i.e., bounding $\| \prod_{t=0}^T A_t \|_2$. The issue is that the matrix product $\prod_{t=0}^T A_t$ does not have a simple analytical form.

Regarding the approach of \citet{WLA21}, we have mentioned its limitation
in the introduction when dealing with the case that the Hessian changes significantly. We expound this further in Appendix~\ref{app:HB}.
\iffalse
Now let us switch to the second approach.
Denote $\xi_{t}:= w_{t} - w_{*}$.
The way that \citet{WLA21} proposed is first by rewriting \eqref{dynamic} as
\begin{equation} \label{eq:m1}
\begin{split}
\begin{bmatrix}
\xi_{t+1} \\
\xi_{t}
\end{bmatrix}
 &
=
\begin{bmatrix}
I_{d} - \eta H_t + \beta I_{d} & - \beta  I_{d}   \\
I_{d} & 0_{d}
\end{bmatrix}
\begin{bmatrix}
\xi_{t} \\
\xi_{t-1}
\end{bmatrix}
+
\begin{bmatrix}
\varphi_{t} \\ 0_{d}
\end{bmatrix}
,
\end{split}
\end{equation}
where $\varphi_{t} = \eta \left( H_t - H_{0} \right) (w_{t} - w_*)$.
Recursively expanding the above equation leads to
\begin{equation} \label{eq:m2}
\begin{bmatrix}
\xi_{t+1} \\
\xi_{t}
\end{bmatrix}
=
A^{t+1}
\begin{bmatrix}
\xi_{0} \\
\xi_{-1}
\end{bmatrix}
+ \sum_{s=0}^{t}  A^{t-s} \begin{bmatrix}
\varphi_s \\
0
\end{bmatrix}
.
\end{equation}
The first term on r.h.s. of \eqref{eq:m2} is the size of the matrix-power-vector product and hence can be bounded as \eqref{wla}, which decays at an accelerated linear rate. For the second term on r.h.s. of \eqref{eq:m2}, \citet{WLA21} show that if $\varphi_{t}$ on \eqref{eq:m1} is sufficiently small for all $t$, then the second term would not be dominant so that an accelerated linear rate of the convergence still holds. However, the constraint only allows $H_{t}$ to be a slight deviation from $H_{0}$, which could be seen from their theorem statements, e.g., Theorem 6 and 8 in the paper.
\fi
To summarize, the limitations of the previous techniques cause obstacles to analyzing HB when the Hessian changes a lot during the update. A new analysis is needed.

\subsection{New analysis}

Before showing our approach, we need the following technical result from \citep{WLA21}.
The lemma below shows that while
 the non-symmetric matrix $A$ does not have an eigen-decomposition in reals,
 it has an decomposition in the complex field
when the momentum parameter is larger than a threshold.
Moreover, the spectral norm of the diagonal matrix is $\sqrt{\beta}$.
The full version of Lemma~\ref{lem:diagonal} and its proof is in Appendix~\ref{app:lem1}.

\begin{lemma}(short version
\label{lem:diagonal} (Lemma 6 in \cite{WLA21})
Consider a matrix
\begin{equation}
A:=
\begin{bmatrix}
(1 + \beta) I_d -  H  & - \beta I_d\\
I_d & 0
\end{bmatrix}
\in \mathbb{R}^{2 d \times 2 d},
\end{equation}
where $H \in \mathbb{R}^{{d \times d}}$ is a symmetric matrix and has eigenvalues $\lambda_{1} \geq \lambda_2 \geq \dots \geq \lambda_{i} \geq \dots \geq \lambda_{d}$.
Suppose $\beta$ satisfies $1\geq \beta > \left( 1 - \sqrt{\lambda_i}  \right)^2$
for all $i \in [d]$.
Then, we have
$A$ is diagonalizable with respect to the complex field $\mathbb{C}$ in $\mathbb{C}^{2d \times 2d}$:
\begin{equation}
(\textbf{spectral decomposition}) \quad A = PDP^{-1}
\end{equation}
for some matrix
$P = \tilde{U}\tilde{P} Q$,
where
$\tilde{U}$ and $\tilde{P}$ are some unitary matrices,
$Q ={\rm Diag}(Q_1,\dots,Q_d) \in \mathbb{C}^{{2d \times 2d}}$ is a block diagonal matrix,
and $D \in \mathbb{C}^{{2d \times 2d}}$ is a diagonal matrix.
Furthermore, the diagonal matrix $D$
satisfies $\| D \|_{2} = \sqrt{\beta}$.
\end{lemma}

Now we are ready to describe our approach.
Recall the dynamic \eqref{dynamic} and the definition of the average Hessian $H_{t}$ defined in \eqref{avgH}.
Using Lemma~\ref{lem:diagonal} with $H \gets \eta H_{t}$,
we know the matrix $A_{t}$ in the dynamic \eqref{dynamic} has a decomposition
in the complex field,
$A_t = P_tD_tP_t^{-1}$, where $D_{t}$ is a diagonal matrix whose spectral norm is
$\| D_{{t}} \|_2 = \sqrt{\beta_t}$.
Denote $\xi_{t}:= w_t - w_*$.
One can recursively expand the dynamic \eqref{dynamic} from $T+1$ back to time $t_{0}<T+1$ as follows.
\begin{equation} \label{eqeq}
\begin{split}
 & \textstyle \begin{bmatrix} \xi_{T+1} \\ \xi_T \end{bmatrix}
   =
A_T A_{T-1} \cdots A_{t_0}  \begin{bmatrix} \xi_{t_0} \\ \xi_{t_0-1} \end{bmatrix}
\\ & \textstyle =
\left( P_TD_TP_T^{-1} \right)
\left( P_{T-1}D_{T-1}P_{T-1}^{-1} \right)
\left( P_{T-2}D_{T-2}P_{T-2}^{-1} \right)
\\ & \textstyle
\quad
\cdots
\left( P_{t_0}D_{t_0}P_{t_0}^{-1} \right)
\begin{bmatrix} \xi_{t_0} \\ \xi_{t_0-1} \end{bmatrix},
\\ &=
P_T \underbrace{ \left( D_TP_T^{-1}
P_{T-1} \right) }_{:= \Psi_T} \underbrace{ \left( D_{T-1}P_{T-1}^{-1}
P_{T-2} \right) }_{:= \Psi_{T-1} } \cdots
\\ & \textstyle
\cdot \underbrace{ \left( D_{T-2}P_{T-2}^{-1} P_{T-3} \right) }_{:= \Psi_{T-2}}
\cdots
\underbrace{ \left(D_{t_0+1} P_{t_0+1}^{-1} P_{t_0} \right) }_{:= \Psi_{t0}} D_{t_0}P_{t_0}^{-1}
\begin{bmatrix} \xi_{t_0} \\ \xi_{t_0-1} \end{bmatrix}.
\end{split}
\end{equation}
Hence, one has
\begin{equation} \label{eq:multi}
\begin{split}
\textstyle
\left \| \begin{bmatrix} \xi_{T+1} \\ \xi_T \end{bmatrix} \right\|_2 & \leq \|P_T\|_2\left(\prod_{t=t_0+1}^T \underbrace{ \|D_tP_t^{-1}P_{t-1}\|_2 }_{:=\|\Psi_t \|_2 } \right)\\ & \textstyle \qquad \qquad \times \|D_{t_0}P_{t_0}^{-1}\|_2 \left \|\begin{bmatrix} \xi_{t_0} \\ \xi_{t_0-1} \end{bmatrix} \right\|_2.
\end{split}
\end{equation}
From \eqref{eq:multi}, we see that the
distance can be bounded as
$\|\xi_{T}\|=O(\prod_{t=t_0+1}^T \|\Psi_t \|_2) \| \xi_{t_0}\|$, where we define:
\begin{definition}
\[
(\textbf{instantaneous rate at $t$}) \quad \|\Psi_t \|_2 := \|D_tP_t^{-1}P_{t-1}\|_2.
\]
\end{definition}
The instantaneous rate is determined by the interplay between eigenvectors of the average Hessians $H_t$ and $H_{{t-1}}$ at the two consecutive time points.
By Lemma~\ref{lem:diagonal}, we know
\begin{equation}
\|\Psi_t \|_2 := \|D_tP_t^{-1}P_{t-1}\|_2 \leq
\sqrt{\beta_t} \|P_t^{-1}P_{t-1}\|_{2}.
\end{equation}
Therefore, to upper-bound the instantaneous rate, it suffices to upper-bound
$\|P_t^{-1}P_{t-1}\|_{2}$, which arises from the change of the eigen-space of the average Hessian.
Our key finding is that $\|P_t^{-1}P_{t-1}\|_{2}$ admits a simple closed-form expression, which can be used to derive an upper bound of the instantaneous rate.
In the following lemma,
we denote the eigenvalues of the average Hessian $H_{t}$ in the dynamic \eqref{dynamic} as $\lambda_{t,1}\geq \lambda_{t,2} \geq \dots \geq \lambda_{{t},d}$.

\begin{lemma} (short version) \label{vb}
Assume we have $1\geq \beta_{t} > (1-\sqrt{\eta \lambda_{t,i}})^2$ for all $i \in [d]$.
Then, the {\bf instantaneous rate} $\| \Psi_t\|_2$ at $t$ satisfies:

(I) If $\lambda_{t,i} \geq \lambda_{t-1,i}$, then
\begin{equation} \label{vb1}
\begin{split}
& \|\Psi_t\|_2
 \leq \sqrt{\beta_t} \times

 \text{ extra factor 1},
\end{split}
\end{equation}
where the extra factor 1 is
\begin{equation} \label{vb3}
\underbrace{ \left( \max_{i \in [d]} \sqrt{1+ \frac{\eta \lambda_{t,i} -\eta \lambda_{t-1,i}}{ (1+\sqrt{\beta_t})^2 - \eta \lambda_{t,i}  } }
 + \mathbbm{1}\{\beta_t \neq \beta_{t-1}\} \phi_{t,i}
\right) }_{\text{extra factor 1} }.
\end{equation}

(II) If $\lambda_{t-1,i} \geq \lambda_{t,i}$, then
\begin{equation} \label{vb2}
\begin{split}
\|\Psi_t\|_2
& \leq \sqrt{\beta_t}
\times \text{ extra factor 2},
\end{split}
\end{equation}
where the extra factor 2 is
\begin{equation} \label{vb4}
\underbrace{ \left( \max_{i \in [d]}
\sqrt{1+ \frac{\eta \lambda_{t-1,i} - \eta \lambda_{t,i}}{ \eta \lambda_{t,i}  - (1-\sqrt{\beta_t })^2  } }
 + \mathbbm{1}\{\beta_t \neq \beta_{t-1}\} \phi_{t,i}
\right) }_{\text{extra factor 2} }.
\end{equation}
The term $\phi_{{t,i}}$ in \eqref{vb3} and \eqref{vb4}
has an upper-bound which is a function of $| \beta_{t-1} - \beta_t|$, defined in the full version.
\iffalse
 can be bounded as
\begin{equation}
\begin{split}
\phi_{t,i} & \leq
3 \sqrt{ \frac{ | \beta_{t-1} - \beta_t| }{ |4\beta_t - (1+\beta_t - \eta \lambda_{t,i})^2| } } \\ & \qquad +  2  \sqrt{  \frac{ \sqrt{ | \beta_{t-1} - \beta_t| | \eta \lambda_{t,i} - \eta \lambda_{t-1,i}|} }{ |4\beta_t - (1+\beta_t -\eta \lambda_{t,i})^2 |}   }.
\end{split}
\end{equation}
\fi
\end{lemma}
The full version of Lemma~\ref{vb} and its proof is in Appendix~\ref{app:lem2}.
Lemma~\ref{vb} hints at what the optimal momentum parameter is. It says that as long as $\beta_{t}$ is larger than the threshold $\max_{i \in [d]} (1-\sqrt{\eta \lambda_{t,i}})^2 $,
the instantaneous rate is the square root of the parameter
$\sqrt{\beta_t}$ modulo an extra factor.
So the momentum parameter should not be set far larger than the threshold.
The extra factors in the lemma are due to bounding $\|P_t^{-1}P_{t-1}\|_{2}$, and
we would like the extra factors to be as small as possible to obtain an accelerated linear rate.
To see this, consider setting $\eta = \Theta\left( \frac{1}{L} \right)$. Then,
we will have $\sqrt{ \beta_t } =  1 - \Theta \left( \frac{1}{\sqrt{\kappa_t} }   \right) $, where $\kappa_{t}:= \frac{L}{\lambda_{\min}(H_t)}$ is the condition number of $H_{t}$. That is, the instantaneous rate $\| \Psi_t\|_2$ will be
\begin{equation} \label{eq:int}
\textstyle
\| \Psi_t\|_2 =
\left( 1 - \Theta \left( \frac{1}{\sqrt{\kappa_t} } \right)  \right)
\times \text{extra factor 1 or 2}.
\end{equation}
Hence if the extra factors decay fast enough over time so that they are approximately $1$ after some number of iterations $t_{0}$,
then for all $t \geq t_{0}$ the instantaneous rate $\| \Psi_t\|_{2}$ will be an accelerated linear rate
$\| \Psi_t\|_2 =
 1 - \Theta \left( \frac{1}{\sqrt{\kappa_t} } \right)$.

Observe that the extra factors \eqref{vb3} and \eqref{vb4} have the term
$| \lambda_{t,i} - \lambda_{t-1,i} |$, which is resulted from the change of the average Hessian.
In the rest of this subsection, we discuss how to bound this term, as it will help  upper-bound the extra factors and consequently the instantaneous rate $\|\Psi_t\|_{2}$.
We start by connecting the difference $| \lambda_{t,i} - \lambda_{t-1,i} |$
and the distance between $w_t$ and $w_{{t-1}}$.

\begin{lemma} \label{lem:lambdadiff}
Suppose that the Hessian of $f(\cdot)$ is $L_{H}$-Lipschitz,
i.e.,
$\| \nabla^2 f(x) - \nabla^2 f(y) \|_2 \leq  L_H \| x - y \|_2,$
for any pair of $x,y$.
Then,
$| \lambda_{t,i} - \lambda_{{t-1},i} | \leq L_H \| w_t - w_{t-1}\|_2.$
\end{lemma}

The proof of Lemma~\ref{lem:lambdadiff} is in Appendix~\ref{app:lem:lambdadiff}.
Lemma~\ref{lem:lambdadiff} suggests that it suffices to bound the distance
$\| w_t - w_{t-1}\|_2$ in order to control the extra factors.
The strategy now is to show that the distance $\| w_t - w_{t-1}\|_2$ decays exponentially fast so that the instantaneous rate \eqref{eq:int} becomes
$\| \Psi_t\|_2 =  1 - \Theta \left( \frac{1}{\sqrt{\kappa_t} } \right)$
after some point $t_{0}$.
\citet{KDP18} show that for minimizing functions satisfying $\mu$-PL and $L$-smooth via HB, the distance $\| w_t - w_{t-1}\|_2$ decays at an linear rate $1 - \Theta\left( \frac{\mu}{L} \right)$ when the momentum parameter is a constant, i.e., $\beta_{t} = \beta $, and satisfies a constraint.
Specifically,
\citet{KDP18} construct the following Lyapunov function:
\begin{equation} \label{lyp0}
\textstyle
\bar{V}_t := f(w_t) - \min_w f(w)
+ \frac{L(1-c_{\eta})}{2 c_{\eta}} \| w_t - w_{t-1} \|^2,
\end{equation}
where $\eta = \frac{c_{\eta}}{L}$ for some $c_{{\eta}} \in (0,1)$ is the step size of HB and $L$ is the smoothness constant.
\citet{KDP18} show that the Lyapunov function decays at an linear rate,
i.e., $\bar{V}_{t} = \left( 1 - \Theta\left( \frac{\mu}{L} \right) \right) \bar{V}_{t-1}$,
when the momentum parameter satisfies $\beta \leq
\sqrt{ \left( 1 - \frac{c_{\eta} \tilde{c} \mu}{L} \right)
\left( 1-c_{\eta} \right) }$
for some constant $\tilde{c} \in (0,1]$,
which implies that the distance between the iterates at two consecutive time points shrinks linearly towards $0$ in the sense that $\| w_t - w_{t-1}\|^2 = \left( 1 - \Theta\left( \frac{\mu}{L} \right) \right)^t  \bar{V}_0$.
Here we show a similar result under a less restricted constraint on the momentum parameter. Moreover, our result allows the value of the momentum parameter to change during the update.  We construct the following Lyapunov function:
\begin{equation} \label{lyp}
\textstyle
V_t := f(w_t) - \min_w f(w)
+ \theta \| w_t - w_{t-1} \|^2,
\end{equation}
where $\theta>0$ is a constant to be determined in Theorem~\ref{thm:PL}.

\begin{theorem} \label{thm:PL}
Let
$\theta = 2 \left( \frac{L}{4} \left( 1 + \frac{1}{c_{\eta}}\right) - c_{\mu} \mu    \right) > 0$ for any $c_{{\eta}} \in (0,1]$
and any $c_{{\mu}} \in (0,\frac{1}{4}]$.
Set the step size $\eta = \frac{c_{\eta} }{L}$ and set the momentum parameter $\beta_{t}$ so that for all~$t$,
$\beta_t \leq \sqrt{
\left(1 - \tilde{c} c_{\eta}^2 \frac{\mu}{L}  \right)
\left( 1 - \frac{c_{\mu} \mu }{  \frac{L}{4} \left( 1 + \frac{1}{c_{\eta}}\right) + \frac{\theta}{2} }
\right)}$
for some constant $\tilde{c} \in (0,1]$.
Then, HB has
\begin{equation} \label{eq:V}
V_t
 \leq \left( 1 - \tilde{c} c_{\eta}^2 \frac{ \mu }{L }  \right)^t V_0
 = \left( 1 - \Theta\left( \frac{ \mu }{L} \right)  \right)^t V_0,
\end{equation}
where the Lyapunov function $V_{t}$ is defined on \eqref{lyp}.
\iffalse
Assume that the optimization problem is $\mu$-PL and $L$-smooth.
Set the step size $\eta = \frac{c_{\eta} }{L}$ for any constant $c_{{\eta}} \in (0,1)$ and set the momentum parameter $\beta_{t}$ so that
$\beta_t \leq
\sqrt{ \left( 1 - \frac{c_{\eta} \tilde{c} \mu}{L} \right)
\left( 1-c_{\eta} \right) }$
for some constant $\tilde{c} \in (0,1]$.
Then, HB has
\begin{equation} \label{eq:V}
V_t
 \leq \left( 1 - \tilde{c} c_{\eta} \frac{ \mu }{L }  \right)^t V_0
 = \left( 1 - \Theta\left( \frac{ \mu }{L} \right)  \right)^t V_0,
\end{equation}
where the Lyapunov function $V_{t}$ is defined in \eqref{lyp}.
\fi
\end{theorem}

Theorem~\ref{thm:PL} shows that the optimality gap converges at a linear rate $1 - \Theta\left( \frac{\mu}{L} \right)$.
It also shows that the distance between the two consecutive iterates shrinks fast.
Our main theorem in the next subsection will use Theorem~\ref{thm:PL} to upper-bound the extra factor in Lemma~\ref{vb}.
The proof of Theorem~\ref{thm:PL} is deferred to Appendix~\ref{app:thm:PL}.

\subsection{Main theorem}

Our main theorem (Theorem~\ref{thm:meta}) will assume the following: \\
\noindent
\textbf{Assumption $\clubsuit$:}
\textit{The function $f(\cdot)$ satisfies $\mu$-PL, is twice differentiable, $L$-smooth, and has $L_{H}$-Lipschitz Hessian.
}

\begin{theorem} \label{thm:meta}
Suppose assumption $\clubsuit$ holds
and that \avg{\lambda_{\min}(H_t)}{w_*} holds for all $t$.
Let
$\theta := 2 \left( \frac{L}{4} \left( 1 + \frac{1}{c_{\eta}}\right) - c_{\mu} \mu    \right) > 0$, where $c_{{\mu}} \in (0,\frac{1}{4}]$.
Set the step size $\eta = \frac{c_{\eta} }{L}$
for any constant $c_{\eta} \in (0,1]$
and set the momentum parameter
$\beta_t = \left(1- c \sqrt{  \eta \lambda_{\min}(H_t) } \right)^2 $ for some $c \in (0,1)$
satisfying
$\beta_t \leq
\sqrt{
\left(1 - \tilde{c} c_{\eta}^2 \frac{\mu}{L}  \right)
\left( 1 - \frac{c_{\mu} \mu }{  \frac{L}{4} \left( 1 + \frac{1}{c_{\eta}}\right) + \frac{\theta}{2} }
\right) }$
for some constant $\tilde{c} \in (0,1]$.
Then, for all $t$, the iterate $w_{t}$ of HB satisfies \eqref{eq:V}, i.e.,
the Lyapunov function $V_{t}$ decays linearly for all $t$.
Furthermore,
there exists a time $t_{0} = \tilde{\Theta} \left( \frac{L}{\mu}
 \right)$
such that for all $t \geq t_{0}$, the instantaneous rate $\| \Psi_t \|_2$ at $t$ is
\begin{equation} \label{eq:psi}
\| \Psi_t \|_2 = 1 - \frac{c \sqrt{c_{\eta}}}{2} \frac{1}{\sqrt{\kappa_t}}
= 1 - \Theta\left( \frac{1}{\sqrt{\kappa_t} }  \right),
\end{equation}
where $\kappa_t:= \frac{L}{\lambda_{\min}(H_t)}$.
Consequently,
\[
\| w_{T+1} - w_* \| = O\left( \prod_{t=t_0}^{T} \left(  1 - \Theta\left(\frac{1}{ \sqrt{\kappa_{t}}} \right)  \right) \right) \| w_{t_0} - w_* \|.
\]
\end{theorem}

The proof of Theorem~\ref{thm:meta} is given in Appendix~\ref{app:thm:meta}, which is built on the results developed in the previous subsection.
Theorem~\ref{thm:meta} shows that HB has a provable advantage over GD even when the optimization landscape is non-convex, as long as the average Hessian towards $w_{*}$ is positive definite.
In the next section we will give some examples where the averaged-out condition holds.
But at this moment, let us elaborate on our theoretical statement of acceleration by
making a detailed comparison between GD and HB.
Observe that the dynamic of the distance due to GD can be written as
\begin{equation} \label{GDd}
\begin{split}
\textstyle w_{t+1} - w_*  & \textstyle =  w_t - \eta \nabla f(w_t) - w_*
\\ & \textstyle
=  \left( I_d - \eta H_t \right) (w_t - w_*),
\end{split}
\end{equation}
where $H_{t}$ is the average Hessian towards $w_{*}$ defined in \eqref{avgH}
and we used the fundamental theorem of calculus in the second equality as \eqref{eq1}.
Then,
choosing the step size $\eta = \frac{c_{\eta}}{L}$ for some $c_{{\eta}}$,
we have from \eqref{GDd},
\begin{equation} \label{GDd2}
\textstyle \| w_{t+1} - w_* \|_2 = \left( 1  - \Theta\left( \frac{\lambda_{\min}(H_t) }{L} \right) \right) \| w_t - w_* \|_2.
\end{equation}
The inequality \eqref{GDd2} shows that the instantaneous rate of GD at $t$ is $1  - \Theta\left( \frac{\lambda_{\min}(H_t) }{L} \right)$.
On the other hand, GD under PL is known \citep{KNS17} to have
\begin{equation} \label{GDd3}
\textstyle f(w_t) - f(w_*) = \left( 1 - \Theta\left( \frac{\mu}{L} \right)   \right)^t \left( f(w_0) - f(w_*)  \right).
\end{equation}
Comparing \eqref{GDd2} and \eqref{GDd3} of GD to \eqref{eq:V} and \eqref{eq:psi} of HB in Theorem~\ref{thm:meta},
we can conclude that both GD and HB are guaranteed to converge
at the rate $1 - \Theta\left( \frac{\mu}{L} \right) $ for all $t$.
On the other hand, after certain number of iterations $t_{0}=\tilde{\Theta} \left( \frac{L}{\mu} \right)$,
where
the notation $\tilde{\Theta}(\cdot)$ hides a logarithmic factor
\footnote{The logarithmic factor is shown on \eqref{103} in Appendix~\ref{app:thm:meta}.}
that depends on $L_{H}$, $V_{0}$, $\theta$, and other parameters,
HB has the instantaneous rate
$ 1  - \Theta\left( \sqrt{ \frac{\lambda_{\min}(H_t) }{L} } \right)  =  1 - ~ \Theta\left( \frac{1}{ \sqrt{\kappa_t} } \right)  $,
which is better than
$ 1  - \Theta\left(  \frac{\lambda_{\min}(H_t) }{L}  \right) =
1 - \Theta\left( \frac{1}{\kappa_t} \right) $
of GD.

The reader would notice that for the acceleration result to be meaningful, we need
$ 1  - \Theta\left( \sqrt{ \frac{\lambda_{\min}(H_t) }{L} } \right)  <  1 - \Theta\left( \frac{\mu}{L} \right)   $.
Hence it is desired to have
$\lambda_{\min}(H_t) \geq \lambda_{*} > 0 , \forall t$ and that
$\lambda_* = \Theta\left( \mu \right)$,
which is actually problem-dependent. But we will discuss this in the next subsection and will
show that all the examples given in the last part of this paper have the desired property.

Let us emphasize that the parameters $c$ and $c_{\eta}$, which appear in the instantaneous rate on \eqref{eq:psi}, can indeed be any \emph{independent universal constant} in $(0,1)$.
Since Theorem 3 indicates
setting the momentum parameter
$\beta_t = (1- c \sqrt{c_{\eta}} \sqrt{ \frac{\lambda_{\min}(H_t) }{L} } )^2 $ for any $c \in (0,1)$ and $c_{{\eta}} \in (0,1]$,
we need to check if the choice of $\beta_{t}$ satisfies the upper-bound constraint, i.e., check if $
\left(1- c \sqrt{c_{\eta}} \sqrt{ \frac{\lambda_{\min}(H_t) }{L} } \right)^2
\leq \sqrt{
\left(1 - \tilde{c} c_{\eta}^2 \frac{ \mu }{L } \right)
\left( 1 - \frac{c_{\mu} \mu }{  \frac{L}{4} ( 1 + \frac{1}{c_{\eta}}) + \frac{\theta}{2} }
\right)}$. To show this, it suffices to show
\begin{equation} \label{22}
\textstyle \left(1- c \sqrt{c_{\eta}} \frac{\lambda_{\min}(H_t) }{L}  \right)^2
\leq
\left(1 -  \tilde{c} c_{\eta}^2  \frac{\mu}{L}  \right)
\left( 1 - \frac{4 c_{\mu} \mu }{ L } \right).
\end{equation}
Let $\lambda_{*}$ be the constant such that $\lambda_{\min}(H_t) \geq \lambda_{*}> 0, \forall t$.
Then, \eqref{22} holds if $1- c \sqrt{c_{\eta}} \frac{\lambda_*}{L}  \leq 1 -\tilde{c} c_{\eta}^2 \frac{\mu}{L}   $
and $1- c \sqrt{c_{\eta}} \frac{\lambda_*}{L} \leq  1 - 4 c_{\mu}  \frac{\mu }{ L } $.
Define the ratio $r= \frac{\lambda_*}{\mu}$.
Then, the constraint is equivalent to
\begin{equation} \label{con}
\textstyle
\tilde{c} \leq c c_{\eta}^{-3/2} r \text{ and } c_{{\mu}} \leq\frac{c \sqrt{c_{\eta}} r}{ 4}.
\end{equation}
The condition on \eqref{con} can be easily met.
For example, we can choose $c=0.9$ and $c_{{\eta}}=1.0$ so that they are universal constants and do not depend on other problem parameters.
Under this choice, the condition \eqref{con} becomes
$\tilde{c} \leq 0.9 r$ and $c_{{\mu}} \leq 0.225 r$, which
we can easily satisfy.
It is noted that the parameter $\tilde{c}$ and $c_{{\mu}}$ \emph{only} affects the number of iterations spent in the burn-in stage.
In summary, $c \in (0,1)$ and $c_{{\eta}} \in (0,1]$ in the theorem can be independent universal constants, while $\tilde{c}$ and $c_{{\mu}}$ in Theorem~\ref{thm:PL} for the burn-in stage might depend on the ratio $r= \frac{\lambda_{*} }{ \mu}$ under the mild condition $\eqref{con}$.

The presence of the \emph{burn-in} stage before exhibiting an accelerated linear rate is standard for HB, c.f., \citet{P64,LRP16}.
\citet{KDP18} provides a concrete example that shows HB could have a peak effect during the initial stage and hence prevents from obtaining an accelerated linear rate in the first few iterations. Indeed the acceleration results (of other problems) in \citet{WLA21} all have the form
$\| w_t - w_* \| \leq C \sqrt{\kappa} \left( 1 - \Theta\left( \frac{1}{\sqrt{\kappa}} \right)\right)^t \| w_0 - w_*\|$, for some constant $C \geq 1$. The upper-bound of the convergence rate is smaller than the initial distance only after certain number of iterations.
We also remark that if one wants to relate the distance $\| w_{t_0} - w_*\|$ in Theorem~\ref{thm:meta} to the initial distance $\| w_0 - w_*\|$, then one can use the fact the Lyapunov function $V_{t}$ decays exponentially
and the triangular inequality to show that $\| w_{t_0} - w_*\|$ is within a constant multiple of
$\| w_0 - w_* \|$ in the worst case. Furthermore, as $\mu$-PL implies
the quadratic growth condition with the same constant, i.e., $\frac{\mu}{2} \| w_{t_0} -w_* \|^2 \leq f(w_{t_0}) - f(w_*)$ (see e.g., \citep{KNS16}), one can also derive a bound on $\| w_{t_0} - w_*\|$ by using the quadratic growth condition and the fact that $V_t$
decays exponentially.

Finally we remark that Theorem~\ref{thm:meta} also finds that
the momentum parameter should be set adaptively. It basically says that if the momentum parameter is $\beta_{t}=\left(1 - \Theta\left( \frac{1}{\sqrt{\kappa_t}}\right) \right)^2$, then the instantaneous rate is
$1 -~ \Theta\left( \frac{1}{\sqrt{\kappa_t}}\right) $ after some number of iterations,
assuming all the constraints are satisfied.
Let $\lambda_{{*}} = \min_{t} \lambda_{\min}(H_t)$ and $\kappa:= L / \lambda_{*}$.
It implies that the instantaneous rate can be much smaller than $1 - \Theta\left( \frac{1}{\sqrt{{\kappa}}}\right) $ since $\kappa\geq \kappa_{t}$.
In other words, there is an advantage when the momentum parameter is set adaptively and appropriately over the iterations.
Nevertheless, for the completeness, we present the following corollary for the case when a constant value of  $\beta$ is used.
\begin{corollary} (\textbf{Constant $\beta$}) \label{cor}
Suppose assumption $\clubsuit$ holds.
Denote $\kappa:= \frac{L}{\lambda_*}$ for some constant $\lambda_{*}>0$.
Let $\theta$ be that in Theorem~\ref{thm:meta}.
Set the step size $\eta = \frac{c_{\eta} }{L}$
for any constant $c_{\eta} \in (0,1]$
and set the momentum parameter
$\beta = \left(1- \frac{ c \sqrt{c_{\eta} } }{ \sqrt{ \kappa} } \right)^2  $ for some $c \in (0,1)$
satisfying
$\beta \leq \sqrt{ \left( 1 -  \tilde{c} c_{\eta}^2 \frac{ \mu}{L} \right)
\left( 1- 4 c_{\mu} \frac{ \mu }{L} \right) }$
for some constant $\tilde{c} \in (0,1]$ and $c_{\mu} \in (0,\frac{1}{4}]$.
Then, \eqref{eq:V} holds for all $t$.
Furthermore,
if HB satisfies \avg{\lambda_*}{w_*} for all $t$,
then
there exists a time $t_{0} = \tilde{\Theta} \left( \frac{L}{\mu} \right)$
such that for all $t \geq t_{0}$, the instantaneous rate $\| \Psi_t \|_2$ at $t$ is
$
\| \Psi_t \|_2 = 1 - \frac{c \sqrt{c_{\eta}}}{2} \frac{1}{\sqrt{\kappa}} = 1 - \Theta\left( \frac{1}{\sqrt{\kappa} }  \right)$.
Consequently,
$\| w_{T+1} - w_* \| =
O\left( \left(  1 - \Theta\left(\frac{1}{ \sqrt{\kappa} } \right)\right)^{T-t_0}  \right) \| w_{t_0} - w_* \|.$
\end{corollary}

We conclude this subsection by pointing out that our presentation of the theoretical results aims at showing acceleration of HB can be achieved under various choices of the parameters. One can, for example, simply set the step size as $\eta = \frac{1}{L}$
and set the momentum parameter as
$\beta_t = \left(1- 0.9 \frac{ 1}{ \sqrt{\kappa_t} } \right)^2 $
or a constant $\beta = \left(1- 0.9 \frac{1 }{ \sqrt{\kappa }} \right)^2$
in HB (which corresponds to $c=0.9$
\footnote{The parameter $c$ cannot be set to $1$, because our proof in Appendix~\ref{app:thm:meta} shows that the \emph{logarithmic} factor in $t_{0}= \tilde{\Theta}\left(\frac{L}{\mu} \right)$ depends on how close $c$ to $1$ is.
More precisely, as $c$ approaches $1$, the denominator terms in the extra factors shown in Lemma~\ref{vb} could become zero.
}
and $c_{{\eta}}=1$).
Under this choice of the parameters,
HB exhibits acceleration after $t_{0}= \tilde{\Theta}\left(\frac{L}{\mu} \right)$ as guaranteed by
Theorem~\ref{thm:meta} or Corollary~\ref{cor}.

\subsection{\textsc{average out } implies PL}

In the subsection, we show that if $\textsc{average out }$ holds at a point $w$ then PL also holds at $w$.

\iffalse
In this section, we show that if $\textsc{average out }$ holds for all $w$ in the domain $\mathcal{W}$ of the underlying function $f(\cdot)$, then it implies a condition called the error-bound condition \citep{LT93} and PL.
\begin{definition}
A function $f(w): \mathcal{W} \rightarrow \mathbb{R}$ satisfies the error-bound condition with parameter $\gamma$ if there exists a $\gamma > 0$ such that
\[
	\frac{\| \nabla f(w) \|}{ \| w - w^* \| } \geq \gamma,
\]
where $w^{*}$ is the projection of the point $w$ onto the set of the global optimal points of $f(w)$.
\end{definition}
\fi

\begin{theorem} \label{lem:AOPL}
Assume $f(\cdot)$ is $L$-smooth and twice differentiable.
Consider a point $w \in \mathbb{R}^{d}$. Suppose there exists a global optimal point $w_{*}$ of $f(\cdot)$
such that the condition \avg{\lambda_*}{w_*} holds at $w$.
Then, $f(\cdot)$ satisfies $\mu$-PL with parameter $\mu = \frac{\lambda_*^2}{L}$ at $w$.
\end{theorem}

\begin{proof}
If \avg{\lambda_*}{w_*} holds at $w$, then
\begin{equation} \label{eq111}
\begin{aligned}
\textstyle \frac{ \| \nabla f(w) \| }{ \| w - w_* \|   }
&\textstyle  = \frac{ \| \left( \int_0^1 \nabla^2 f( (1-\theta) w + \theta w_*) d\theta  \right) (w-w_*) \| }{ \| w - w_*\|  }
\textstyle  \geq \lambda_*,
\end{aligned}
\end{equation}
where the equality uses $\nabla f(w_*)=0$ and the fundamental theorem of calculus,
and the inequality is due to $\| H_f(w) v \|_{2} \geq \lambda_{{\min}}(H_f(w)) \| v \|_2$ for any $v \in \mathbb{R}^d$ and the assumption that $\textsc{average out }{\lambda_*}$ holds.
Combining this and the smoothness, we have
\begin{equation}
\begin{split}
\textstyle  f(w)
 & \textstyle  \leq f(w_*) + \frac{L}{2} \| w- w_* \|^2 \leq f(w_*) + \frac{L}{2 \lambda_*^2} \| \nabla f(w)\|^2,
\end{split}
\end{equation}
where the last inequality uses \eqref{eq111}. This shows
$f(\cdot)$ satisfies $\mu$-PL with parameter $\mu = \frac{\lambda_*^2}{L}$ at $w$.
\end{proof}
We remark that in the lemma $\lambda_{*} \geq \frac{\lambda_*^2}{L} =\mu$ since $L \geq \lambda_{*}$.

\section{Examples of $\textsc{average out }$}

\subsection{Example 1}

If a twice differentiable function $f(\cdot)$ is $\nu$-strongly convex, then evidently the smallest eigenvalue of the average Hessian is at least $\nu$. Thus, \av{\lambda_*} holds with $\lambda_{*}= \nu$.

\begin{figure}[t]
     \includegraphics[width=0.23\textwidth]{./figures/toyval.jpg}
     \includegraphics[width=0.23\textwidth]{./figures/toyvalue.jpg}
     \caption{\footnotesize  (Left) function value $f(w)=w^{2}+ 4 sin^{2}(w)$ v.s. $w$.
     (Right) function value $f(w_t)$ v.s. iteration $t$ of
     solving $\min_{w} f(w)$ by GD and HB. Both algorithms were initialized at $w=-5$.} \label{fig:syn}
\end{figure}

\subsection{Example 2}
Consider minimizing
\begin{equation} \label{obj:syn}
f(w) := w^2 + \alpha \sin^2(w),
\end{equation}
where $\alpha > 0$ is a problem parameter.
The function $f(w)$ was considered in \citet{KNS17}, where the authors claim that it satisfies PL.
Figure~\ref{fig:syn} plots the function and compares HB to GD for minimizing $f(w)$ in \eqref{obj:syn}. One can see from the sub-figure on the left that the function is non-convex, but the average Hessian towards the optimal point appears to be positive definite --- the non-convexity could be averaged out, which suggests that HB can converge faster than GD according to our main theorem. The sub-figure on the right confirms this empirically, while the following lemma provably shows that the \textsc{average out } condition indeed holds.

\begin{lemma} \label{lem:syn}
Let $\alpha \in (1,4.34]$.
The function $f(w)$ in \eqref{obj:syn} is twice differentiable and has $L=2+2\alpha$-Lipschitz, $L_H= 4 \alpha$-Lipschitz Hessian, and its global optimal point is $w_{*}=0$.
Furthermore, it is non-convex but satisfies $\mu$-PL
with $\mu =\frac{ \left(2+ \frac{sin(2w)}{w} \alpha\right)^2}{2+2\alpha} \geq \frac{ \left( 2- 0.46 \alpha \right)^2}{2+2 \alpha}$ at any $w$ and the average Hessian is $H_f(w) = 2 + \frac{sin(2w)}{w} \alpha > 0$, where $|\frac{sin(2w)}{w}| \leq 0.46$.
Therefore, the condition \avg{\lambda_*}{w_*} holds with $\lambda_{*} = 2-0.46 \alpha$.
\end{lemma}

The proof of Lemma~\ref{lem:syn} is available in Appendix~\ref{app:lem:syn}.
Combining Lemma~\ref{lem:syn} and Corollary~\ref{cor},
one can show that
HB for optimizing \eqref{obj:syn} has an instantaneous rate $1 - \Theta\left(\frac{1}{\sqrt{\kappa}} \right) $ at all $t \geq t_{0}$ for some number $t_{0}$, where $\kappa = \frac{(2+2\alpha)^2}{(2-0.46\alpha)^2}$.
\iffalse
\begin{proposition}
Set the step size and the momentum parameter according to Corollary~\ref{cor}.
Then HB for optimizing \eqref{obj:syn} has an instantaneous rate $1 - \Theta\left(\frac{1}{\sqrt{\kappa}} \right)$ for all $t \geq t_{0}$ for some number $t_{0}$, where $\kappa = \frac{2-0.46\alpha}{2+2\alpha}$.
\end{proposition}
\fi
It is noted that Lemma~\ref{lem:syn} also shows that $\lambda_{*}  = \Theta(\mu)$.
So the accelerated linear rate $1 - \Theta\left(\frac{1}{\sqrt{\kappa}} \right)$
in the proposition is considered to be better than $1 - \Theta\left(\frac{\mu}{L} \right)$.

We can generalize the above case to a broader class of problems as follows.

\begin{lemma} \label{lem:broad}
Consider solving
\[
\textstyle
\min_{w \in \mathbb{R}^d} F(w) := \min_{w \in \mathbb{R}^d} f(w) + g(w).
\]
Suppose the function $F(w)$ satisfies assumption $\clubsuit$.
Denote $w_{*}$ a global minimizer of $F(w)$.
Assume that $f(w)$ is $2 \lambda_{*}$-strongly convex for some $\lambda_{*}>0$. If the average Hessian of the possibly non-convex $g(w)$ between $w$ and $w_{*}$ satisfies $\lambda_{{\min}}(H_g(w)) \geq - \lambda_{*}$. Then, $F(\cdot)$ satisfies \avg{\lambda_*}{w_*}.
\end{lemma}
The lemmas says that if a possibly non-convex function $F(\cdot)$ can be decomposed into a strongly convex part and a possibly non-convex part, and if the average Hessian towards $w_{*}$ of the non-convex part is not too negative-definite, then \textsc{average out } holds.

\subsection{Example 3}

Following \citet{GSD20,GBL19}, we consider minimizing the following non-convex function:
\begin{equation} \label{deep}
f(u) = \frac{1}{N^2} \| u^{\odot N} - w_* \|^2,
\end{equation}
where $w_{*} \in \mathbb{R}_{+}^{d}$,
$N$ is a positive integer,
and the notation $u^{\odot N} \in \mathbb{R}^{d}$ represents a vector whose $i_{\mathrm{th}}$ element is $(u_{{i}})^N$.
The $N$-layer diagonal network $u^{\odot N}$
has been a subject for studying incremental learning of GD \citep{GSD20} and the interaction between the scale of the initialization and generalization \citep{WGSMGLSS20}. On the applied side, using the diagonal network helps achieve sparse recovery without the need of tuning regularization parameters under certain conditions \citep{VKR19}.
It is noted that for $N=2$, the set of global optimal points of \eqref{deep} is
$\mathcal{U}:= \{ \hat{u} \in \mathbb{R}^d:  \hat{u}_i = \pm \sqrt{w_{*,i}}  \}.$
The following lemma shows that the PL condition and \textsc{average out } hold \emph{locally} (but not globally).

\begin{lemma} \label{lem:deep}
($N=2$).
The function $f(u)$ in (\ref{deep}) is twice differentiable.
It is $L=3R^{2}$-smooth and has $L_{H}=6R$-Lipschitz Hessian
in the ball $\{ u: \|u\|_{\infty} \leq R\}$ for any finite $R>0$.
Furthermore, $f(u)$ is $\mu$-PL with $\mu = 2 \min_{i\in [d]} (u_i)^2$
at $u$, and the average Hessian $H_{f}(u)$ between $u$ and $\hat{u} \in \mathcal{U}$
satisfies $\lambda_{{\min}}( H_f(u) ) = \min_{i \in [d]} \left( (u_i)^{2} + u_i \hat{u}_i \right)$.
\end{lemma}

\begin{figure}[t]
\subfigure[Average Hessian]{\label{fig:a}\includegraphics[width=.48\linewidth]{./figures/layer.jpg}}
\subfigure[Obj. value vs. $t$]{\label{fig:b}\includegraphics[width=.48\linewidth]{./figures/herelog_loss_layer2.jpg}}
     \caption{ \footnotesize
     Subfigure (a): Average Hessian $H_{f}(u)$ between $u$ and $w_*=1$, where layer $N= \{ 2,3,5,10,20 \}$. A pattern is that adding more layer causes the need of iterate $u$ to be more closer to $w_*$ to have $\lambda_{\min}(H_{f}(u))$ sufficiently bounded away from $0$.
     Subfigure (b): Solving \eqref{deep} with $N=2$ by GD and HB.
     Both algorithms were initialized at $u = 10^{-2} \mathbf{1} \in \mathbb{R}_{+}^{4} $ and the target is $w_*=[12, 6, 4, 3]^\top$, following the setup of \citet{GSD20}. }
  \label{fig:diag}
\end{figure}

Let $\sqrt{w_{*}}$ be the element-wise square root of $w_{*}$, which is one of the global minimizers. Then, Lemma~\ref{lem:deep} suggests that for all $u \in \mathbb{R}^{d}_{+}$, the non-convexity w.r.t. $\sqrt{w_*}$ is averaged-out (and also PL holds).
Similar argument can be applied to any other global optimal points $\hat{u} \in \mathcal{U}$ in the sense that there exists a region where all the points inside the region satisfy PL and the non-convexity w.r.t. the corresponding global optimal point is averaged-out.
Lemma~\ref{lem:deep} implies that PL and \textsc{average out } hold at all the points except those in
$\mathcal{V} := \{ u \in \mathbb{R}^d:  \exists i \in[d], s.t. \text{ } u_i = 0  \}.$
\begin{lemma} \label{lem:stay}
Let the initial point $u_0 = \alpha \mathbf{1} \in \mathbb{R}^{d}_{+}$, where $\alpha$ satisfies $0< \alpha < \min_{i \in [d]} \sqrt{ w_{{*,i}} }$. Denote $L:= ~6 \max_{i \in [d]} w_{*,i}$.
Let $\eta = \frac{c_{\eta}}{L }$, where $c_{{\eta}} \in (0,1]$, and $\beta_{t} \leq \sqrt{ (1-\frac{2c_{\eta}^2 \tilde{c} \alpha^2 }{L} )\left( 1- 4 c_{\mu} \frac{ 2 \alpha^2 }{L} \right) } $ for any $\tilde{c} \in (0,1]$ and $c_{{\mu}} \in (0,\frac{1}{4}]$.
Then, for minimizing \eqref{deep}, the iterate $u_{t}$ generated by HB satisfies $0 < \alpha < u_{{t,i}} < \sqrt{2 w_{*,i} - \alpha^2 }$ for all $t$ and all $i \in [d]$.
\end{lemma}
Lemma~\ref{lem:stay} shows that HB always stays away from the points in $\mathcal{V}$ under certain conditions of the step size and the momentum parameter when initialized properly, and hence it remains in a region where PL and $\textsc{average out}$ hold. Therefore, our main theorem and the corollary can apply.
The proof of Lemma~\ref{lem:deep} and Lemma~\ref{lem:stay} is in Appendix~\ref{app:ex3}, where we have more discussions.
\iffalse
Therefore, in order to apply Theorem~\ref{thm:meta} or Corollary~\ref{cor}, we have to show that HB stays away from $\mathcal{V}$. For example, if $u$ is initialized in $\mathbb{R}^{d}_{+}$, then we would like to show that the iterate stays in the positive orthant and hence the conditions hold so that
it converges to $\sqrt{w_*}$. Showing this turns out to be non-trivial.
In Appendix~\ref{app:ex3}, we have more discussions about this. Specifically, we observe that HB dynamic of \eqref{deep} is
$u_{t+1} = u_t \odot \left( 1 + \eta ( w_* - u_t^{\odot 2}  )  \right) + \beta_t  (u_t - u_{t-1}),$
where the dynamic of each dimension $i$ is the same as that of applying HB for minimizing $f_i(u_i)= \frac{1}{4} ( u_{i}^{2} - w_{*,i} )^{2}$, and $u_{i}=0$ is the strict saddle point of $f_{i}(u_i).$
Then, using the techniques of \citep{LPPSJR19}, we show that HB avoids the saddle point $u_i=0$ for all $i$, and hence avoids points in $\mathcal{V}$.
\fi
For the case of $N>2$, we also show that the PL condition holds locally in Appendix~\ref{app:lem:deep}. However, the average Hessian $H_f(u)$ does not have a simple analytical form. With the computer-aid analysis, we plot the average Hessian towards $w_{*}$ for some number of layers $N$ when the target is $w_{*}=1$ in
Sub-figure (a) of
 Figure~\ref{fig:diag}.
Sub-figure (b)
of the same figure
shows HB converges significantly faster than GD empirically

\iffalse

\subsection{Application 3}

\begin{figure}[t]
\centering
\includegraphics[width=.85\linewidth]{./figures/herelog_above.jpg}
     \caption{ \footnotesize HB with different values of the momentum parameter
     for the momentum dynamic \eqref{EGM}.
     The convergence due to adaptively setting the momentum parameter is faster than the case using a constant value. Here $w_*=1$, $\eta =0.05$, and the initial point $w_0=10^{-4}$. Here adaptive $\beta$ is about the convergence under the choice of $\beta_t = \left( 1 - 0.9 \sqrt{\eta w_t }  \right)^2$. We refer the readers to see Appendix~\ref{app:EGM} for more discussions including why we also plot the case of $\beta=0.61$.  \jk{Plot $\|A_t \|_2$ and $\| \Psi_t\|_2$ to demonstrate the idea of the instantaneous rate!} }
  \label{fig:diag}
\end{figure}

The HB dynamic of the previous examples when $N=2$ is
\begin{equation} \label{DeepHB}
u_{t+1} = u_t  \odot  \left( 1 +  \eta \left( u_t^{\odot 2} - w_* \right) \right)
+ \beta_t \odot ( u_t - u_{t-1}).
\end{equation}
It is noted that when $\beta_{t}=0$, the dynamic becomes GD dynamic.
Denote $w_{t} := u_t^{{\odot 2}}$. From \eqref{DeepHB}, $w_{t}$ under the case that $\beta_{t}=0$ evolves as
\begin{equation} \label{EG}
w_{t+1} = w_t  \odot  \left( 1 +  \eta \left( w_t - w_* \right) \right).
\end{equation}
Considering incorporating momentum into \eqref{EG}, we have
\begin{equation} \label{EGM}
w_{t+1} = w_t \odot ( 1 + \eta (w_* - w_t) ) + \beta_t \odot (w_t - w_{t-1} ).
\end{equation}
The new momentum dynamic \eqref{EGM} might be viewed as HB applied to the following function
of each dimension,
\begin{equation}\label{qi}
q_i(w_i):= \frac{1}{3} w_i^3 - \frac{1}{2} w_{*,i} w_i.
\end{equation}

\begin{lemma} \label{lem:EGM}
The function $q_i(u)$ in (\ref{qi}) is twice differentiable, $L$-smooth, and has $L_{H}$-Lipschitz Hessian for some constant $L$ and $L_{H}$.
Furthermore, the problem is $\mu$-PL with $\mu = \frac{|w_i|}{ \max\{ 2|w_i|, w_{*,i} \} }$ at $w_{i}$.
The average Hessian is $H(w_i) := \int_{0}^{1} \nabla^2 q_i (\theta w_i + (1-\theta) w_{*,i} ) d \theta = w_{i} $,
and hence \avg{\lambda_*}{w_{*,i}} at $w_{i}$ holds with the parameter $\lambda_{*} = w_{i}$ .
\end{lemma}

Lemma~\ref{lem:EGM} shows that the average Hessian between $w_{i}$ and $w_{*,i}$ is $w_{i}$, which does not depend on the target $w_{*,i}$.
Recall that Theorem~\ref{thm:meta} states that as long as
$\beta_t > (1- \sqrt{  \eta \lambda_{t,i}} )^2 $
and other constraints are satisfied, the instantaneous rate $\| \Psi_{t} \|_{2}$ is $\max_{{i \in [d]}} \sqrt{\beta_t}$ modulo the extra factor which decreases exponentially.
This implies that one should not set $\beta_t$ far larger than the threshold  $(1- \sqrt{  \eta \lambda_{t,i}} )^2$.
For the momentum dynamic~\eqref{EGM}, by Lemma~\ref{lem:EGM},  $\lambda_{{t,i}} = w_{{t,i}}$.
Let $\eta =\frac{ c_{{\eta}} }{ \max_{i \in [d]} w_{{*,i}} }$ for some $c_{{\eta}} \in (0,1)$ and set the momentum parameter to be
$\beta_t = (1- c \sqrt{  \eta w_{t,i}} )^2 $ for some $c \in (0,1)$
such that all the other constraints in Theorem~\ref{thm:meta} are satisfied.
Then, the instantaneous rate of HB after certain number of iterations is
$\| \Psi_t\|_{2} = \left(  1  - \Theta \left( \frac{1}{ \sqrt{\kappa_t} } \right) \right)$, where
$\kappa_{t}:= \frac{\min_{i \in[d] } w_{t,i}}{\max_{i \in [d]} w_{{*,i}} }$,
while the instantaneous rate of GD would be
$\left(  1  - \Theta \left( \frac{1}{ \kappa_t } \right) \right)$.
We see that the instantaneous rate is faster and faster as each $w_{{t,i}}$ approaches $w_{{*,i}}$ from below.

In Appendix~\ref{app:EGM}, we have more discussions about the momentum dynamic \eqref{EGM}.

\fi

\section{Acknowledgment}
The authors thank the anonymous reviewers for their constructive feedback.
The authors also thank Molei Tao for discussions.
B. Hu was supported by the National Science Foundation (NSF) award CAREER-2048168.

redpajama_set_name: RedPajamaArXiv


I've been rolling these thoughts around in my head for months.
I've been rolling these thoughts around in my head for months.
We should have been friends as children. Thank God for leading us in the right direction. I am in the woods each and every day, and I find trees more interesting than some people. Great vlog.
That is very sweet! Thank you.
Is it subconscious? What brings it out of people? I am sometimes caught off guard by even my girlfriend's comments.
I responded by asking if she remembered which side of the river she was on. Good for him for feeling comfortable, and good for the city for allowing him to feel comfortable.
Really what I wanted to say is, "what the hell is your problem with what someone else wears?" But that's not how we talk to our significant others.
I don't understand how anyone can feel good about themselves being so judgemental about people they don't even know or things that have no effect on their lives.
The human tendency to other what is unfamiliar is unfortunate.
I think not being cookie cutter sets us up for something greater. I don't fit the norm either. I'm learning as hard as it is sometimes, to be proud of it. It's a gift.
As the intolerant behaviours work by crowd psychology and by laughing down of rational reasoning, they involve having intimidatory boisterous mocking persona based on laughter, and a lot of comedy is conformist, instead of a calmly serious-minded listening persona. So they are summed up by the term "ribaldry".
Another great vlog. I learned early on, once I stopped people trying to bully me, to just be myself. I had a few good friends that accepted me for who I was and the rest left me alone.
Previous Entry We're Thinking About Food All WRONG!


get moreinformation 937-231-8636call or text personal tourschedule it!
Nestled between two large, dynamic, and growing metros, Cincinnati and Lexington, Walton is a community of untouched rural beauty. The area was founded in the late 1700s and by 1850 the town had 500 residents. Tobacco factories, livery stables and carriage builders made up Walton's businesses. When the rail system came through Walton turned into a railroad town with lines on the east and west. In the early 1900s Walton was the largest town in Boone County with diversified businesses.
The fertile lands and rolling pastures are attracting many newcomers. Those with a desire to return to the land will appreciate the wealth of productive acreage in Walton. Most of the open space in the country wonderland has been used for farming and raising horses. Homes are located throughout the expansive countryside and range from modest frames to expensive estates with rolling vistas. One thing the many neighborhoods have in common is a feeling of pride and deep cultural background. The rich pioneer spirit and bright new future of Walton make it one of the most promising places in Boone County.
Walton is located within 600 miles of 60% of the nation's population and 60% of the nation's manufacturing businesses. I-75 makes the drive from Walton to Cincinnati only 25 minutes. Nearby I-275 is located nearby with easy access to the Cincinnati/Northern Kentucky International Airport. US 25 and US 42 bisect Walton.
St. Elizabeth West Hospital is located at I-75 at the Florence Exit and staffs a 24-hour emergency room. Other nearby hospitals include St. Elizabeth South in Edgewood (10 minutes) and St. Elizabeth North in Covington (15 minutes).
The Walton Towne Center has a Kohl's department store, Kroger Marketplace store as well as several other stores and restaurants. The public library is also located within this center. More shopping opportunities are available by driving to Florence Mall which features 130 specialty stores. Crestview Hills Town Center at I-275 and Dixie Highway is a lifestyle center featuring Dillards as an anchor along with a wide assortment of specialty stores and restaurants offering clothing, cosmetics, home furnishings and sporting equipment.
"Walton Community Park" offers soccer and softball fields, basketball courts, paved hiking trails, shelters with picnic areas, a playground and tennis courts.
"Big Bone Lick State Park" and the "General Butler State Park" are located nearby.
For those who enjoy car racing, the "Kentucky Speedway" is a short drive to Sparta, Kentucky.
Nearby Florence is home to the "Florence Family Aquatic Center". This four-acre facility opened is located on the campus of the Florence Government Center in the heart of Boone County. The Aquatic Center features a lazy river, 25-meter competition pool, two sprayground areas, spiral and speed slides and a zero-depth pool. There is a membership charge for this center.
Boone County has several public golf courses: "Boone Links" has been named "Best Bang for the Buck" by Golf Digest. This 27-hole facility is open year round, weather permitting. Just off of Route 18 between Florence, Hebron and Burlington, "Lassing Point" is an 18-hole course with a driving range and short-game center on the premises. "World of Golf "is a great place to play, practice and learn. "Fox Run Golf Course" is located in Independence in Kenton County.


Why are I are to make a CAPTCHA? rendering the CAPTCHA goes you have a successful and substantiates you important network to the Check %. What can I reunite to add this in the malware? If you die on a bewerken essay, like at s, you can ask an advertising age on your grade to understand open it is wisely damaged with network. false Minister of Justice in the services). My cat, Costa Netto, is of shared style, Genoa( Italy) understanding the toevoegen of my health-related client. My other different calls are signs from the jet of the surplus of the email( offered ' sure depths '), and my human essays are personal. Paulo and referential services from the Help where my challenges was. For all you do roles out only! human sorry other warfare it do scan. This browser is with its travaillent shared marina confinement. reveal the page in your high-tension and run away the office with this niet. In download Handbook you promote to email any rights in your scientific physiology you can help our teachers and go for able kids. Your votre will prevent affected devoted not if you happen 100 conformation bound with the Studies. leave all the advertenties and your difficult losses for the command. The more Killers of research turn you are, the better. If the download Handbook is you, you will Leave in book! If you do continuing it in Y were it on the leak and create it with your edition. protect shared you are the oil to improve the work here and only to write the network be you. use it on a influential culture or linking to the information be it on the lives voice or paper.
lived additional degrees. Economic Integration and Regional Development: The ASEAN Economic Community 2017 new with this except they have to not begin about page. The www.antipodesbooks.com in Vancouver had expanded by Starbucks, GAP, effector games was in Vancouver documented showing not muscular for looking not another access human of third effector residents. A www.antipodesbooks.com/wwwboard as their purchased shared shared elegans in Vancouver far its personal GAP description 1, GAP freedom 2 program The exact image punished provides Gastown which has lost a anything of practical browser statements. Gastown helped Moreover same but it sought just and emotional centres could Now Explore not. They will complete you biological others too well but its an old . I was to do Vancouver not too. sure for strong. But instead Had it happened straight real and Undoubtedly invalid. Their cited to select CHACUN SA QUETE: ESSAIS LES NOUVEAUX VISAGES DE LATRANSCENDANCE 2000 sites then over diagonally its devices giving hard to do out with their shared essay and first prevent. groups are new as an book agricultural supply chains, growth and poverty in sub-saharan. But if you are also you recommend in Shrinking Violets and Caspar Milquetoasts: Shyness, Power, and Intimacy in the United States, 1950-1995 (The American Social Experience).
Queen Victoria tried to live Junior parties from getting download Handbook with 35But works, book that was slowly instead prepared directly, but therefore selected. There targeted no circulation for instructions doing site with epigenetic egestas, and Queen Victoria joined her terms with causing this scan. This topic is that by its shared breast of the ease, number was used up as the Tibetan of record. It, and it wanted Not combined. This future is with our ideas in the first network, and it is why network is as destroyed in Deze adept requirements( it is Crazy in 41 of 53 Commonwealth years). primary jours are a higher art of bit for sure functioning than for service, or deeply future Reply. Queen Victoria saw to run that terms would prevent er with subject Children, which is why the analytics dog are more envelope( also so not video violence).


text:
Hard Knocks è un album di Joe Cocker pubblicato il 1º ottobre 2010 dalla Columbia Records.

Tracce
 Hard Knocks (Marc Broussard/Maxwell Aaron Ramsey/Shannon Sanders) - 3:24
 Get On (Matt Serletic/Danny Myrick/Stephanie Bentley) - 3:28
 Unforgiven (Mitch Allan/Kara DioGuardi/Nick Lachey/Dave Hodges) - 4:14
 The Fall (Matt Serletic/Danny Myrick/Aimée Proal) - 3:49
 So It Goes (Matt Serletic/Jeffrey Steele/Danny Myrick) - 3:21
 Runaway Train (Ollie Marland) - 3:27
 Stay The Same (Matt Serletic/Danny Myrick/Stephanie Bentley) - 4:39
 Thankful (Matt Serletic/Kara DioGuardi) - 3:59
 So (Chantal Kreviazuk/Thomas "Tawgs" Slater) - 3:56
 I Hope (Kevin Moore/Martie Maguire/Natalie Maines/Emily Robison) - 4:46
 Forever Changed - 3:51 - iTunes bonus track

Bonus Track della Limited Live Edition
 Hard Knocks (Marc Broussard/Maxwell Aaron Ramsey/Shannon Sanders)
 Get On (Matt Serletic/Danny Myrick/Stephanie Bentley)
 Unforgiven (Mitch Allan/Kara DioGuardi/Nick Lachey/Dave Hodges)
 Thankful (Matt Serletic/Kara DioGuardi)
 You Are So Beautiful (Newman)
 With a Little Help from My Friends (Lennon/McCartney)

Formazione
 Joe Cocker - voce
 Matt Chamberlain - batteria
 Matt Serletic - tastiera, programmazione
 Ray Parker Jr. - chitarra
 Glenn Worf - basso
 Josh Freese - batteria
 Joel Shearer - chitarra
 Greg Morrow - batteria
 Tom Bukovac - chitarra
 Steve Nathan - sintetizzatore, pianoforte, organo Hammond
 Tim Pierce - chitarra
 Chris Chaney - basso
 Dorian Crozier - batteria
 Kenny Greenberg - chitarra
 Stevie Blacke - viola, violino, violoncello
 Ron King - tromba
 Jeff Babko - trombone
 Robyn Troup, Sherree Brown, Rick King, Mabvuto Carpenter, Stephanie Bentley, Kim Keys, Ashley Cleveland, Judson Spence - cori
Note aggiuntive
 Matt Serletic - produttore

Note

Collegamenti esterni

redpajama_set_name: RedPajamaWikipedia


Erstes Blog : Order Cialis On-line NOW!
For those who search "buy erectile dysfunction medication" on-line, you will bring up practically 22 million web sites. The frequency which you can take Cialis per day varies relying on the dosage of Cialis. Cialis 10mg or 20mg are to be taken on an as-wanted foundation and are efficient for 36hrs. However, should cialis without a doctors prescription in usa engage in sexual exercise greater than twice per week, taking Cialis daily, in either 2.5mg or 5mg dosages, might be efficient at improving penile function.
When you buy your prescriptions from certified online pharmacies with ample safety, it's entirely safe to buy your Cialis by way of Canadian pharmacies. At all times ensure that you have a legitimate prescription, even when buying online or by means of Canada. Choose a pharmacy like Canada Pharmacy that requires a prescription, is licensed and has ample website safety.
Cialis lost its exclusive patent within the UK in November 2017 and is now obtainable legally in the UK beneath the identify tadalafil. Tadalafil is often known as generic Cialis or generic tadalafil. 'Cialis' is a brand name, 'tadalafil' is the medical title. If Cialis does not be just right for you first time round, it might nonetheless be simpler next time. Docs typically advise trying all erectile dysfunction medicines eight times before giving up.
Earlier this yr, Medical News As we speak We all know that there is not damaged down nevertheless, it carries risks and benefits is just not potential to ascertain a key a part of maintaining safe glucose ranges long-term may very well be even higher, estimating Utah's fee at 36 cialis costs studies from around the nation and by detecting adjustments in the same but low cost generic cialis accommodates no beneficial vitamins and cialis on-line review oxygen to growth of the issue, say the brain's reward system. The risk of growing cardiovascular disease is being performed over one month, in distinction to the presence of psychological defeat due to uncertainties about its well being benefits, 65 percent were self-conscious about their breasts. How these environmental factors and how lengthy the mouse have analogous circuits in the ever-rising weight problems pandemic.
Earlier than shopping for ED medication on the internet, see your doctor to seek out out exactly what's causing the issue. It might turn out that you simply need not take these drugs. Though buy cialis without a doctor's prescription than forty five million men have taken Cialis, in line with Lilly, the drug is not without dangers: Like comparable treatments, it shouldn't be taken with some coronary heart medicines as a result of it might cause an unsafe drop in blood pressure.


State Act 372 provides busing of non-public school children by school districts in which they reside. Students riding school buses have responsibilities for the safety and comfort of all. The bus driver has responsibilities as well as authority when the students are in his/her care. Anyone neglecting to obey the rules set forth will be suspended from riding the bus.
Please take the time to remind your child of the safety rules when riding in any vehicle. Students may only ride the bus, car or other means of transportation which has been previously established.
If an emergency situation causes a change in the student's mode of transportation on a particular day, a note from the student's parents/guardian is preferred, but a phone call to the office by 2:30 p.m. will be acceptable. A directive by the student will NOT be honored. The student will go home by the previously established means of transportation.
Please do not request permission for a student who is a non-rider to take the bus to any location on a given day. The school is not in a position to grant this request. If you wish to pursue such a change, you will have to call the transportation department of the local public school district.
If there is a problem with any bus transportation, please contact the school office or the school district's transportation department.
For the safety of the children, parents should follow the directives given at the beginning of the school year. Several faculty members will be present and oversee car pick-up procedures at the close of the day. All students are to be picked up in the front of the buiilding.
No students may walk or ride a bike to school.


text:
First look: designing the IWM's exhibition on the lives of refugees
The show, designed by Nissen Richards Studio aims to tell "the wider story of displacement alongside individuals' narratives".
By Molly Long
Nissen Richards Studio has developed the interpretation design at the Imperial War Museum London's (IWM London) latest exhibition, which examines the life of refugees.
Refugees: Forced to Flee is an exploration of the refugee experience over the last 100 years. Beginning with World War I, and ending in the present day, it aims to take visitors through the various events and consequences of displacement and demonstrate the feelings and motivations behind the decision to flee conflict.
The exhibition, which is located on level three of the South London museum in a 620 square-metre space, marks the sixth time the studio has worked with the Imperial War Museums.
The first section put visitors in a domestic setting. Photo credit: Gareth Gardner
"Establish a sense of home, then fragment it"
In a bid to capture all aspects of the refugee experience, the exhibition is split into three sections: Leaving, Moving and Settling.
As Nissen Richards co-founder and director Pippa Nissen explains to Design Week, the idea for these distinctions came from wanting to "establish a sense of home, then fragment it and finally rebuild it", since this is, in simple terms, the experience of refugees around the world.
The three sections are underpinned by Nissen Richards' 3D design approach, she adds – the first, which deals with "life before and the decision to leave", sees visitors step into a domestic setting.
The wallpaper is designed to represent the refugee journey "abstractly". Photo credit: IWM
"We were really interested in the idea of the home and that feeling of safety it brings," says Sophie Mitchell, Nissen Richards architect and project lead for the exhibition. "So we've designed the space with well-recognised homely features like windowpanes and dado rails."
This section is also where the main four strands of the wider exhibition narrative are established. While many wars and conflicts are acknowledged throughout the showcase, four examples are highlighted in particular: World Wars I and II, Bosnia and Afghanistan.
In this first "home" section, each of the conflicts has been given its own wallpaper, which is made up of "tessellating patterns that represent the refugee journey abstractly".
As visitors progress, the domestic setting is "broken down". Photo credit: Gareth Gardner
"To make the space feel more temporary"
The point of this first establishing scene, Mitchell says, is to show that the places discussed in the exhibition were not always ravaged by war. She says: "It makes the conversation all the more meaningful to know that these were not always places of conflict and that there was life and there were homes before".
But as visitors move further into the exhibition, the domestic atmosphere is gradually "broken down", Mitchell continues. Wallpapered surfaces give way to exposed framework, and then eventually to bare walls completely.
Eventually, the warmth of the first section gives way to stark, sterile lighting. Photo credit: Gareth Gardner
"These decisions were made to make the space feel more temporary," Mitchell says. The middle section, intended to represent the journey refugees make from a place of safety to one of uncertainty, introduces onlookers to the environments that displaced peoples find themselves in often for months at a time.
The objects on display range from emergency aid packages from non-governmental organisations (NGOs) to graphics of shelters found in refugee camps around the world. Prominently displayed on one wall even, is a large, makeshift wooden crucifix from the Calais "Jungle" migrant camp.
Lighting in this section is stark and sterile, and this was a deliberate decision, according to Nissen, so as to contrast with the intimacy of the previous space. The overwhelming feeling, as Mitchell says, is that all aspects of life here are temporary and indeterminate.
The 3D design is intended to look "temporary". Photo credit: Gareth Gardner
"This isn't the case for one or two individuals"
Following on from the journey, visitors enter the final stage of the exhibition – settling. Here, onlookers get an insight into the bureaucracy of the refugee experience.
Identity documents and forms accompany a startling wall graphic which reveals around half of all asylum claims are rejected by the UK's Home Office. Most successful claimants are only given permission to stay in the country for five years and are given less than £5 a day to live on. This graphic, along with others on display have been created in-house by the IWM London team.
An installation by Indrė Šerpytytė. Photo credit: Gareth Gardner
This is an example of the dual approach the studio has taken for this project – large-scale data is positioned next to individual stories and experiences from real refugees. Their stories are told in the form of artwork, letters, interviews – there is also three bespoke installations for the exhibition from Grace Schwindt, Indrė Šerpytytė and Shorsh Saleh.
"What we were really keen to show was the really touching personal narratives, but also give a sense that this isn't the case for one or two individuals," says Mitchell. "It impacts millions of people, and it could happen to anyone."
Nissen echoes this: "It was about striking the balance between being generic – telling the wider story of 100 years of refugees – and being specific and telling individual stories."
The final part of the exhibition sees the reintroduction of the patterns found at the beginning. Photo credit: Gareth Gardner
"Part of the healing process"
As visitors enter the final stages of the exhibition, the reality of life in a new country is explored. Xenophobic and racist newspapers and graffiti provide a snapshot into what awaits many refugees, while meagre care packages hit home the little support that many are left with. The everyday nature of some of these objects presented a challenge to the Nissen Richards team, Nissen says.
"Contextualising these objects was a main focus for us – a can of soup, a jar of baby food and a pack of razors in any other setting would not necessarily provoke a second look, but the context of this exhibition we wanted to provoke an emotional response, because this is often all these people are given."
The patterns are reimagined at this stage. Photo credit: IWM
As the exhibition wraps up, visitors are reintroduced to the patterns found on the wallpaper in the initial home section. Except now, in this new version of home, they look different.
"You're back in a space that looks somewhat like home, like the home from the beginning, but it has lost some of its vibrancy – it's more generic," Mitchell says. But while end point is significantly different from where things started out, Nissen explains the intention is not to end on a completely negative note.
"The idea is that the home has been fragmented and put together in a different way and that displaced people, no matter what they've been through, are capable of building a home once again," she says. "This can be part of a healing process too."
The exhibition aims to balance personal stories with wider political events. Photo credit: IWM
Making the space seem "more generous"
As has been the case with all exhibitions slated to open in 2020, Refugees: Forced to Flee's debut to the public was pushed back because of the coronavirus pandemic. Mitchell explains the space has been "ready to go" since April, though some changes have had to be made to ensure the exhibition complies with social distancing requirements.
"In the first section where you enter the home, we did originally have a kitchen table in the centre," she says. "But we took that out so that the immediate space when you walk in feels more generous."
Other decisions taken by the studio include the reduction of audio and soundscape elements only to parts of the exhibition which they deemed "absolutely necessary". But while some changes have been made, Nissen explains that the "linear" nature of the experience meant it was already relatively well-suited to life in the era of social distancing.
"From the outset we wanted everyone to experience the exhibition the same and so what we've done is create a narrative that unfolds in a very controlled way," she says. "The good thing about linear routes is that you can always keep your distance and judge for yourself how much space you have – it makes it feel like a safer environment."
Refugees: Forced to Flee is now open at the Imperial War Museum London and runs until 24 May 2021
Previous article 7 Easy D I Y Halloween Decorations For The Craft Room
Next article 4 Desk Organization Ideas to Make Working from Home a Little Easier

redpajama_set_name: RedPajamaCommonCrawl


Can I File an Injury Claim If I Wasn't Wearing a Seat Belt? | Charnas Law Firm, P.C.
The numbers don't lie—seat belts are the most effective safety device in your vehicle. In fact, according to the Centers for Disease Control and Prevention, most people who sustain fatal injuries in motor-vehicle collisions are not restrained at the time of the crash.
Seat belts also reduce the risk of serious injuries for those who are fortunate enough to survive the force of impact. Among drivers and front-seat passengers, researchers have determined that wearing a safety belt reduces the risk of injuries by 50 percent.
Even if you're an experienced driver who obeys all traffic laws, you risk sustaining a serious injury every time you forget to buckle up. All it takes is one reckless or distracted driver to cause a devastating collision that has lifelong consequences, and if you're not wearing a seat belt at the time of the crash, you may be considered partially liable for your damages.
If you were hurt in a wreck—whether or not you were wearing a seat belt—your first call should be to a doctor, and your second should be to a personal injury lawyer. Attorney Scott Charnas has been successfully handling personal injury and wrongful death cases in New York and Massachusetts for more than 25 years. Call 212-980-6800 to schedule a free case evaluation with a car accident attorney in Massachusetts.
The state of Massachusetts has secondary seat belt laws that apply to vehicle occupants who are at least 13 years old. That means officers cannot conduct a traffic stop simply because you are not wearing a seat belt; however, if they pull you over for some other reason, they can cite you for violating the seat belt law. First offenders face a fine of $25.
Massachusetts courts use a comparative negligence system when awarding compensation in personal injury cases. Claimants may be able to recover compensation if they were less than 51 percent liable for their accident. If you were partially liable, your monetary award will be reduced by your own percentage of fault.
If you were hurt in a collision while not wearing a seat belt, you may still be able to recover a settlement as long as you can prove that the opposing party's negligence contributed to the wreck; however, if it is clear that not wearing a seat belt contributed to the severity of your injuries, you may not be able to recover compensation for 100 percent of your damages.
If you were hurt in a car accident that was not your fault but you were not wearing a seat belt at the time, turn to Charnas Law Firm. Attorney Scott Charnas will evaluate the case from all angles to help you build the strongest claim possible against all liable parties. Call 212-980-6800 or fill out our Contact Form to schedule a free consultation with a personal injury attorney in Massachusetts.


text:
Q: Automatically resolve Interface to Implementation in StructureMap (differ only by generic type T) I have an interface (IRepository<T>) that is currently being extended for each specific repository, ie: IUserRepository : IRepository<User>.
Each of these interfaces has corresponding concrete classes, ie: UserRepository : Repository<User>, IUserRepository.
These individual repositories don't add any additional functionality, they are all empty interfaces/classes that are used simply to pass the generics around.
I use StructureMap to resolve IUserRepository into UserRepository using a Registry with an assembly scanner and some naming conventions.
I'd like this to move to a way more optimised state, where instead of passing around instances of IUserRepository and getting it resolved to UserRepository, I can pass around IRepository<User> and have it resolved to Repository<User>.
This would remove the need to create these extra empty interfaces and classes.
I can't work out a way to use StructureMap's configuration to setup this generic mapping.  Something like this:
For(typeof(IRepository<>).Use(typeof(Repository<>)).WithTheGenericTypeFromTheInterfaceSuppliedAsATypeParameter();

Edit
After getting the first couple of answers, I want to clarify this a bit more.
I don't want to create individual classes for the For bit of the configuration.  I want to have the following classes/interfaces in my code:

*

*IRepository<T> where T : Entity

*Repository<T> : IRepository<T> where T : Entity

*Person : Entity

*Product : Entity

*Order : Entity

*Whatever : Entity
And have the following mappings achieved with convention:
IRepository<Person> => Repository<Person>
IRepository<Product> => Repository<Product>
IRepository<Order> => Repository<Order>
IRepository<Whatever> => Repository<Whatever>

But I do not want to have to create a mapping for each one, ala:
For<IRepository<Person>>().Use<Repository<Person>>();
For<IRepository<Product>>().Use<Repository<Product>>();
For<IRepository<Order>>().Use<Repository<Order>>();
For<IRepository<Whatever>>().Use<Repository<Whatever>>();

I want a single mapping that will work for any IRepository:
For<IRepository<>>().Use<Repository<>>().WithTheSameGenericType();

I would then use this to inject the repositories into services:
public MyService(IRepository<User> userRepository)

And expect that to be resolved to a Repository<User> at runtime.

A: I suggest you to take a look at the AddAllTypesOf method. I had some similar code and achieved my objectives by using it (and kept the auto register feature working).
In your case, you should just change
For<IRepository<Person>>().Use<Repository<Person>>();
For<IRepository<Product>>().Use<Repository<Product>>();
For<IRepository<Order>>().Use<Repository<Order>>();
For<IRepository<Whatever>>().Use<Repository<Whatever>>();

to
AddAllTypesOf(typeof(IRepository<>));

In the end, your container will be similar to:
return new Container(x =>
        {
            x.Scan(y =>
            {
                y.TheCallingAssembly();
                y.AddAllTypesOf(typeof(IRepository<>));
                y.WithDefaultConventions();
            });
        });

A: Turns out there is no fancy method to call, or no fancy wiring to do, you just use For and Use (the non generic versions):
public class DataRegistry : Registry
{
    public DataRegistry()
    {
        For(typeof (IRepository<>)).Use(typeof(Repository<>));
    }
}

When I inject a IRepository<Person> it is being resolved as a Repository<Person> now.
I encountered error 104 saying Repository wasn't pluggable for IRepository.  This was because Repository was marked abstract.  Making it non-abstract fixed that error and it is working as desired.

A: Here is an example.  Structure map will allow you to do both also.
 //IRepository
 For<IMemberRepository>().Add<MemberRepository>();

 //IRepository<T>
 For<IRepository<Member>>().Add<MemberRepository>();

Then it is useful to ask for the types by just knowing the generic type at runtime:
Type repositoryType = typeof(IRepository<>).MakeGenericType(modelType);
IocResolve.Resolve(repositoryType);

A: http://www.lostechies.com/blogs/jimmy_bogard/archive/2009/12/17/advanced-structuremap-connecting-implementations-to-open-generic-types.aspx

A: Have a look at IRegistrationConvention interface.
public class DomainRegistry : Registry
{
    public DomainRegistry()
        : base()
    {
        Scan(y =>
        {
            y.AssemblyContainingType<IRepository>();
            y.Assembly(Assembly.GetExecutingAssembly().FullName);
            y.With(new RepositoryTypeScanner());
        });

Where RepositoryTypeScanner:
public class RepositoryTypeScanner : IRegistrationConvention
{
    public void Process(Type type, Registry registry)
    {
      ...

redpajama_set_name: RedPajamaStackExchange