First-order methods almost always avoid saddle points: the case of vanishing step-sizes

Introduction

Non-convex optimization has been studied extensively the last years and has been one of the main focuses of Machine Learning community. The reason behind the interest of ML community is that in many applications of interest, one has to deal with the optimization of a non-convex landscape. One of the key obstacles of non-convex optimization is the saddle points (which can outnumber the local minima ) and avoiding them is a fundamental problem .

Recent progress has shown that under mild regularity assumptions on the objective function, first-order methods such as gradient descent can provably avoid the so-called strict saddle pointsThese are saddle points where the Hessian of the objective admits at least one direction of negative curvature. Such property has been shown to hold in a wide range of objective functions, see and references therein..

In particular, a unified theoretical framework is established in to analyze the asymptotic behavior of first-order optimization algorithms such as gradient descent, mirror descent, proximal point, coordinate descent and manifold descent. It is shown that under random initialization, the aforementioned methods avoid strict saddle points almost surely. The proof exploits a powerful theorem from the dynamical systems literature, the so-called Stable-manifold theorem (see supplementary material for a statement of this theorem). For example, given a $C^{2}$ (twice continuously differentiable function) $f$ with $L$-Lipschitz gradient, gradient descent method

avoids strict saddle points almost surely, under the assumption that the stepsize is constant and $0<\alpha<\frac{1}{L}$. The crux of the proof in is the use Stable-manifold theorem for the time-homogeneousThis means that $g$ does not depend on time. dynamical system $\mathbf{x}_{k+1}=g(\mathbf{x}_{k})$. Stable-manifold theorem implies that the dynamical system $g$ avoids its unstable fixed points and with the fact that the unstable fixed points of the dynamical system $g$ coincide with the strict saddles of $f$ the claim follows.

In many applications/algorithms however the stepsize is adaptive or vanishing/diminishing (meaning $\lim_{k}\alpha_{k}=0,$ e.g., $\alpha_{k}=\frac{1}{k}$ or $\frac{1}{\sqrt{k}}$). Such applications include stochastic gradient descent (see for analysis of SGD for convex functions), urn models and stochastic approximation , gradient descent , online learning algorithms like multiplicative weights update (which is an instantiation of Mirror Descent with entropy regularizer). It is also important to note that the choice of the stepsize is really crucial in the aforementioned applications as changing the stepsize can change the convergence properties (transition from convergence to oscillations/chaos ) and/or the rate of convergence .

The proof in does not carry over when the stepsize depends on time step, because the Stable-manifold theorem is not applicable. Yet it remains an open question whether the results of hold for vanishing step-sizes and the authors stated in as an open question. This work resolves this question in the affirmative. Our main result is stated below informally.

Gradient Descent, Mirror Descent, Proximal point and Manifold descent, with vanishing step-size $\alpha_{k}$ of order $\Omega\left(\frac{1}{k}\right)$ avoid the set of strict saddle points (isolated and non-isolated) almost surely under random initialization.

The paper is organized as follows: In Section 2 we give important definitions for the rest of the paper, in Section 3 we provide intuition and technical overview of our results, in Section 4 we show a new Stable-manifold theorem that is applicable to a class of time non-homogeneous dynamical systems and finally in Section 5 we show how this new manifold theorem can be applied to Gradient descent, Mirror Descent, Proximal point and Manifold Descent.

Notation.

Preliminaries

In this section we provide all necessary definitions that will be needed for the rest of the paper.

We call a dynamical system $x_{k+1}=g(x_{k})$ as time homogeneous since $g$ does not on step $k$. Furthermore, we call a dynamical system $x_{k+1}=g(k,x_{k})$ time non-homogeneous as $g$ depends on $k$.

A point $\mathbf{x}^{*}$ is a critical point of $f$ if $\nabla f(\mathbf{x}^{*})=0$.

A critical point is a local minimum if there is a neighborhood $U$ around $\mathbf{x}^{*}$ such that $f(\mathbf{x}^{*})\leq f(\mathbf{x})$ for all $\mathbf{x}\in U$, and a local maximum if $f(\mathbf{x}^{*})\geq f(\mathbf{x})$.

A critical point is a saddle point if for all neighborhoods $U$ around $\mathbf{x}^{*}$, there are $\mathbf{x},\mathbf{y}\in U$ such that $f(\mathbf{x})\leq f(\mathbf{x}^{*})\leq f(\mathbf{y})$.

A critical point $\mathbf{x}^{*}$ is isolated if there is a neighborhood $U$ around $\mathbf{x}^{*}$, and $\mathbf{x}^{*}$ is the only critical point in $U$.

This paper will focus on saddle points that have directions of strictly negative curvature, that is the concept of strict saddle.

A critical point $\mathbf{x}^{*}$ of $f$ is a strict saddle if $\lambda_{\min}(\nabla^{2}f(\mathbf{x}^{*}))<0$ (minimum eigenvalue of the Hessian computed at the critical point is negative).

Let $\mathcal{X}^{*}$ be the set of strict saddle points of function $f$ and we follow the Definition 2 of for the global stable set of $\mathcal{X}^{*}$.

Given a dynamical system (e.g., gradient descent $\mathbf{x}_{k+1}=\mathbf{x}_{k}-\alpha_{k}\nabla f(\mathbf{x}_{k})$)

the global stable set $W^{s}(\mathcal{X}^{*})$ of $\mathcal{X}^{*}$ is the set of initial conditions where the sequence $\mathbf{x}_{k}$ converges to a strict saddle. This is defined as:

Moreover, $\mathbf{z}$ is called a fixed point of the system (1) if $\mathbf{z}=g(k,\mathbf{z})$ for all natural numbers $k$.

Intuition and Overview

In this section we will illustrate why gradient descent and related first-order methods do not converge to saddle points, even for time varying/vanishing step-sizes $\alpha_{k}$ of order $\Omega\left(\frac{1}{k}\right)$. Consider the case of a quadratic, $f(\mathbf{x})=\frac{1}{2}\mathbf{x}^{T}A\mathbf{x}$ where $A=\mathop{\mathbf{diag}}(\lambda_{1},...,\lambda_{d})$ is a $d\times d$, non-singular, diagonal matrix with at least a negative eigenvalue. Let $\lambda_{1},...,\lambda_{j}$ be the positive eigenvalues of $A$ (the first $j$) and $\lambda_{j+1},...,\lambda_{d}$ be the non-positive ones. It is clear that $\mathbf{x}^{*}=\mathbf{0}$ is the unique critical point of function $f$ and the Hessian $\nabla^{2}f$ is $A$ everywhere (and hence at the critical point). Moreover, it is clear that $\mathbf{x}^{*}$ is a strict saddle point (not a local minimum).

Gradient descent with step-size $\alpha_{k}$ (it holds that $\alpha_{k}\geq 0$ for all $k$ and $\lim_{k\to\infty}\alpha_{k}=0$) has the following form:

Assuming that $\mathbf{x}_{0}$ is the starting point, then it holds that $\mathbf{x}_{k+1}=\left(\prod_{t=0}^{k}(I-\alpha_{k-t}A)\right)\mathbf{x}_{0}$. We conclude that

We examine when it is true that $\lim_{k\to\infty}\mathbf{x}_{k}=\mathbf{x}^{*}$. It is clear that $\prod_{t=0}^{\infty}(1-\lambda\alpha_{t})=e^{\sum_{t=0}^{\infty}\ln(1-\lambda\alpha_{t})},$ and has the same convergence properties as

For $\lambda>0$, the term (3) converges to zero if and only if $\sum_{t=0}^{\infty}\alpha_{t}=+\infty$ which is true if $\alpha_{t}$ is $\Omega\left(\frac{1}{t}\right)$. Moreover, for $\lambda=0$ it holds that the term (3) remains a constant (independently of the choice of stepsize $\alpha_{k}$) and for $\lambda<0$ it holds that the term (3) diverges for $\alpha_{t}$ to be $\Omega\left(\frac{1}{t}\right)$. Therefore, for $\alpha_{k}$ being $\Omega\left(\frac{1}{k}\right)$ we conclude that $\lim_{k\to\infty}x_{k}=\mathbf{0}$ whenever the initial point $\mathbf{x}_{0}$ satisfies $x_{0}^{i}=0$ ($i$-th coordinate of $\mathbf{x}_{0}$) for $\lambda_{i}\geq 0$.

1italic-ϵO\left(\frac{1}{k^{1+\epsilon}}\right)). In the case $\alpha_{k}$ is a sequence of stepsizes that converges to zero with a rate $\frac{1}{k^{1+\epsilon}}$ for any $\epsilon>0$ (example $\frac{1}{k^{2}},\frac{1}{2^{k}}$ etc), then it holds that $\sum_{t=0}^{\infty}\alpha_{k}$ converges and hence in our example above we conclude that $\lim_{k\to\infty}\mathbf{x}_{k}$ exists, i.e., $\mathbf{x}_{k}$ converges but not necessarily to a critical point.

The challenging part of proving our main result is the lack of generic theory for time non-homogeneous dynamical systems, either for continuous or discrete time. Moreover, as far as gradient descent, mirror descent, etc are concerned, the corresponding dynamical system that needs to be analyzed is more complicated when the objective function is not quadratic and the analysis of previous subsection does not apply.

Suppose we are given a function $f$ that is $C^{2}$, and $\mathbf{0}$ is a saddle point of $f$. The Taylor expansion of the gradient descent in a neighborhood of $\mathbf{0}$ is as follows:

where $\eta(k,\mathbf{0})=\mathbf{0}$ and $\eta(k,\mathbf{x})$ is of order $o(\left\|\mathbf{x}\right\|)$ around $\mathbf{0}$ for all naturals $k$.

Due to the error term $\eta(k,\mathbf{x}_{k})$, the approach for quadratic functions does not imply the existence of the stable manifold. Inspired by the proof of Stable-manifold theorem for time homogeneous ODEs, we prove a Stable-manifold theorem for discrete time non-homogeneous dynamical system (4). In words, we prove the existence of a manifold $W^{s}$ that is not of full dimension (it has the same dimension as $E^{s}$, where $E^{s}$ denotes the subspace that is spanned by the eigenvectors with corresponding positive eigenvalues of matrix $\nabla^{2}f(\mathbf{0})$).

To show this, we derive the expression of (2) for the general function $f$ to be:

Stable Manifold Theorem for Time Non-homogeneous Dynamical Systems

We start this section by showing the main technical result of this paper. This is a new stable manifold theorem that works for time non-homogeneous dynamical systems and is used to prove our main result (Theorem 1.1) for Gradient Descent, Mirror Descent, Proximal Point and Manifold Descent. The proof of this theorem exploits the structure of the aforementioned first-order methods as dynamical systems.

Let $H$ be a $d\times d$ real diagonal matrix with at least one negative eigenvalue, i.e. $H=diag\{\lambda_{1},...,\lambda_{d}\}$ with $\lambda_{1}\geq\lambda_{2}\geq...\lambda_{s}>0\geq\lambda_{s+1}\geq...\geq\lambda_{d}$ and assume $\lambda_{d}<0$. Let $\eta(k,\mathbf{x})$ be a continuously differentiable function such that $\eta(k,\mathbf{0})=\mathbf{0}$ and for each $\epsilon>0$, there exists a neighborhood of $\mathbf{0}$ in which it holds

We can generalize Theorem 4.1 to the case where matrix $H$ is diagonalizable and for any fixed point $\mathbf{x}^{*}$ (instead of $\mathbf{0}$, using a shifting argument). The statement is given below.

$D_{\mathbf{x}}g(k,\mathbf{x}^{*})=I-\alpha_{k}G,$ $G$ real diagonalizable with at least one negative eigenvalue;

Since $G$ is diagonalizable, there exists invertible matrix $Q$ such that $G=Q^{-1}HQ$, hence $QGQ^{-1}=H,$ where $H=diag\{\lambda_{1},...,\lambda_{d}\}$ (i.e., $H$ is a diagonal matrix with entries $\lambda_{1},...,\lambda_{d}$). Consider the map $\mathbf{z}=\varphi(\mathbf{x})=Q(\mathbf{x}-\mathbf{x}^{*})$. $\varphi$ induces a new dynamical system in terms of $\mathbf{z}$ as follows:

Multiplying by $Q$ from the left on both sides, we have

and the inverse transformation is given by

Applications

In this section, we apply Theorem 4.1 (or its corollary 4.2) to the four of the most commonly used first-order methods and we prove that each one of them avoids strict saddle points even with vanishing stepsize $\alpha_{k}$ of order $\Omega\left(\frac{1}{k}\right)$.

is a time non-homogeneous dynamical system.

We need to verify that the Taylor expansion of $g(k,\mathbf{x})$ at $\mathbf{x}^{*}$ satisfies the conditions of Corollary 4.2. Condition 1 is obvious since the Hessian $\nabla^{2}f(\mathbf{x}^{*})$ is diagonalizable and has at least one negative eigenvalue. It suffice to verify condition 2. Consider the Taylor expansion of $g(k,\mathbf{x})$ in a neighborhood $U$ of $\mathbf{x}^{*}$:

and then the differential of $\theta(k,\mathbf{x})$ with respect to $\mathbf{x}$ is

From the Fundamental Theorem of Calculus and chain rule for multivariable functions, we have

the verification completes. By Corollary 4.2 and Corollary 4.3, we conclude that the stable set of strict saddle points has Lebesgue measure zero. ∎

2 Mirror Descent

where $h(\mathbf{x})=\text{argmax}_{\mathbf{z}\in M}\langle\mathbf{z},\mathbf{x}\rangle-\Phi(\mathbf{z})$.

We say that $\Phi$ is a mirror map if it satisfies the following properties.

$\nabla_{R}\Phi$ diverges on the relative boundary of $M$, that is $\lim_{x\rightarrow\partial M}||\nabla_{R}\Phi(x)||=\infty$.

The fact that $g(k,\mathbf{x})$ satisfies the condition 1 of Corollary 4.2 follows from the proof of Proposition 10, , i.e. $\nabla^{2}_{R}\Phi(\mathbf{x}^{*})^{-1}\nabla^{2}_{R}f(\mathbf{x}^{*})$ is similar to a symmetric linear operator (so diagonalizable) with at least one negative eigenvalue. Next, we verify that $g(k,\mathbf{x})$ satisfies the condition 2 of Corollary 4.2. From the Taylor expansion, we have

By the continuity of $\nabla^{2}_{R}f$ and $\nabla^{2}_{R}\Phi(\mathbf{x})^{-1}$, the same argument as the proof of Theorem 5.1 implies that the condition 2 of Corollary 4.2 is satisfied. Combing Corollary 4.2 and Corollary 4.3, we conclude that the stable set of saddle points has Lebesgue measure zero. ∎

3 Proximal Point

The proximal point algorithm is given by the iteration

Different from the other First-order methods, the results is not a direct consequence of Corollary 4.3, but instead, we need to apply part of the proof of Theorem 4.1. It is still necessary to verify that the Taylor expansion of $g(k,\mathbf{x})$ at $\mathbf{x}^{*}$ satisfies condition 1 and 2 of Corollary 4.2. From the proof of Proposition 3, , $g(k,\mathbf{x})+\alpha_{k}\nabla f(g(k,\mathbf{x}))=\mathbf{x}$. By implicit differentiation, $Dg(k,\mathbf{x})+\alpha_{k}\nabla^{2}f(g(k,\mathbf{x}))Dg(k,\mathbf{x})=I$, and

At saddle point $\mathbf{x}^{*}$, $Dg(k,\mathbf{x}^{*})=(I+\alpha_{k}\nabla^{2}f(g(k,\mathbf{x}^{*})))^{-1}$ that is diagonalizable since $\nabla^{2}f(\mathbf{x}^{*})$ is diagonalizable. Suppose under the matrix $Q$, $Q\nabla^{2}f(\mathbf{x}^{*})Q^{-1}=H$ that is diagonal. Then

where $\lambda_{i}$ are the eigenvalues of $H$. Notice that $\frac{1}{1+\alpha_{k}\lambda_{i}}=1-\frac{\alpha_{k}\lambda_{i}}{1+\alpha_{k}\lambda_{i}}$, the stable-unstable decomposition in the proof of Corollary 4.1 holds. Furthermore, since $\alpha_{k}\in\Omega\left(\frac{1}{k}\right)$, $\frac{\alpha_{k}\lambda_{i}}{1+\alpha_{k}\lambda_{i}}$ is also of $\Omega\left(\frac{1}{k}\right)$. To see this, we can assume $\alpha_{k}\lambda_{i}\geq\frac{1}{k-1}=\frac{1}{k}\cdot\frac{k}{k-1}$, and then $\frac{k-1}{k}\alpha_{k}\lambda_{i}\geq\frac{1}{k}$ or $\left(1-\frac{1}{k}\right)\alpha_{k}\lambda_{i}\geq\frac{1}{k}$, and thus $\alpha_{k}\lambda_{i}\geq\frac{1}{k}(1+\alpha_{k}\lambda_{i})$, implying that $\frac{\alpha_{k}\lambda_{i}}{1+\alpha_{k}\lambda_{i}}\geq\frac{1}{k}$. So the proof for Lemma C.1 and Lemma C.2 holds for the existence of stable manifold of proximal point algorithm if condition 2 of Corollary 4.2 is satisfied. To verify this, we consider the Taylor expansion of $g(k,\mathbf{x})$ at $\mathbf{x}^{*}$ has the form of

Since $f$ is of $C^{2}$, $g(k,\mathbf{x})$ and $\nabla^{2}f(\mathbf{x})$ are continuous, and then $\left\|\theta(k,\mathbf{x})-\theta(k,\mathbf{y})\right\|\leq\alpha_{k}\epsilon\left\|\mathbf{x}-\mathbf{y}\right\|$ follows from the same argument as the proof of Theorem 5.1. So the verification completes and by Corollary 4.2 and Corollary 4.3, we conclude that the stable set of strict saddle points is of Lebesgue measure zero. ∎

4 Manifold Gradient Descent

According to the proof of Proposition 8, , for $\mathbf{v}\in T_{\mathbf{x}^{*}}M$,

Let $\mathbf{x}-\mathbf{x}^{*}\in T_{\mathbf{x}^{*}}M$, the Taylor expansion in the tangent space can be written as

Using equation 4, , $P_{T_{\mathbf{x}}M}D(P_{T_{\mathbf{x}}M}\nabla\bar{f})(\mathbf{x})=\nabla^{2}_{R}f(\mathbf{x})$, which is exactly the Riemannian Hessian, and thus it is diagonalizable. So this verifies the condition 1 of Corollary 4.2. Furthermore, the Taylor expansion gives

The continuity of $\nabla^{2}f$ implies that for each $\epsilon>0$, there exist neighborhood of $\mathbf{x}^{*}$, such that $\left\|D_{\mathbf{x}}\theta(k,\mathbf{x})\right\|\leq\epsilon$. Apply the argument in the proof of Theorem 5.1 (Fundamental Theorem of Calculus and Cauchy-Schwarz inequality), we can conclude that condition 2 of Corollary 4.2 is satisfied. then combing with Corollary 4.3, we have that the stable set of strict saddle points has measure (induced by metric $R$) zero. ∎

Let $\mathbf{x}^{*}\in\mathcal{X}^{*}$, then $\nabla f(\mathbf{x}^{*})=0$, and $g(k,\mathbf{x}^{*})=\mathbf{x}^{*}$. To show that $\mathbf{x}^{*}$ is unstable, consider the differential

Since at $\mathbf{x}^{*}$, $\nabla f(\mathbf{x}^{*})=0$, i.e. $\frac{\partial f}{\partial x_{j}}=0$ for all $j$, we have

Recall that $\left(R^{ij}\right)=\left(R_{ij}\right)^{-1}$, and as it is shown in , by the similar transformation under $\left(R_{ij}\right)^{\frac{1}{2}}$, we have

that is a symmetric matrix, so it is diagonalizable. And thus, $D_{\mathbf{x}}\left(\left(R^{ij}\right)\cdot\nabla f(\mathbf{x}^{*})\right)$ is diagonalizable and has the same eigenvalue with $\left(\frac{\partial^{2}f}{\partial x_{i}\partial x_{j}}\right)$, meaning that it has negative eigenvalues. So the Riemmanian Hessian at $\mathbf{x}^{*}$ as at least one negative eigenvalue. The Taylor expansion of $g(k,\mathbf{x})$ at $\mathbf{x}^{*}$ is

By the continuity of $\left(\frac{\partial^{2}f}{\partial x_{i}\partial x_{j}}(\mathbf{x})\right)$, the same argument as the verification of condition 2 in the proof of Theorem 5.1 implies that $\theta(k,\mathbf{x})$ satisfies the condition 2 of Corollary 4.2. Combining with Corollary 4.3, we conclude that the stable set of strict saddle points has measure (induced by metric $R$) zero. ∎

Conclusion

In this paper, we generalize the results of for the case of vanishing stepsizes. We showed that if the stepsize $\alpha_{k}$ converges to zero with order $\Omega\left(\frac{1}{k}\right)$, then gradient descent, mirror descent, proximal point and manifold descent still avoid strict saddles. We believe that this is an important result that was missing from the literature since in practice vanishing or adaptive stepsizes are commonly used. Our main result boils down to the proof of a Stable-manifold theorem 4.1 that works for time non-homogeneous dynamical systems and might be of independent interest. We leave as an open question the case of Block Coordinate Descent (as it also appears in ).

References

Appendix A Statement of theorems used and for completion

Let $(X,d)$ be a complete metric space, then each contraction map $T:X\rightarrow X$ has unique fixed point.

Let $x^{*}$ be a fixed point for the $C^{r}$ local diffeomorphism $g:\mathcal{X}\to\mathcal{X}$. Suppose that $E=E_{s}\oplus E_{u}$, where $E_{s}$ is the span of the eigenvectors corresponding to eigenvalues of magnitude less than or equal to one of $Dg(x^{*})$, and $E_{u}$ is the span of the eigenvectors corresponding to eigenvalues of magnitude greater than one of $Dg(x^{*})$Jacobian of function $g$.. Then there exists a $C^{r}$ embedded disk $W^{cs}_{loc}$ of dimension $dim(E^{s})$ that is tangent to $E_{s}$ at $x^{*}$ called the local stable center manifold. Moreover, there exists a neighborhood $B$ of $x^{*}$, such that $g(W^{cs}_{loc})\cap B\subset W^{cs}_{loc}$, and $\cap_{k=0}^{\infty}g^{-k}(B)\subset W^{cs}_{loc}$.

Appendix B Lyapunov-Perron Method

whose linear approximation at $\mathbf{0}$ is

By a change of coordinate system, $A$ is assumed to be decomposed to stable-unstable blocks respectively. Consider the operator $T$ defined as follows:

where $\mathbf{x}_{0}$ is the initial point, $U(t)$ and $V(t)$ are integral operators from the block decomposition of $A$. The stable manifold is the fixed point of $T$ following from the Banach fixed point theorem.

Appendix C Proof of Theorem 4.1

Denote $A\left(m,n\right)=\left(I-\alpha_{m}H\right)...\left(I-\alpha_{n}H\right)$ for $m\geq n$, and $A\left(m,n\right)=I$ if $m<n$. Then the dynamical system can be written as

Since $H$ is diagonal, the matrix $A\left(m,n\right)$ has the form of

where $B_{k}$ and $C_{k}$ are diagonal as well and corresponding to stable and unstable subspaces of $I-\alpha_{k}H$ at . Using the same notation of denoting $A\left(m,n\right)$, we denote

Let $v$ be a vector, we denote $v^{+}$ the stable component of $v$ and $v^{-}$ the unstable component of $v$. Then the solution (43) can be written in terms of stable and unstable components as

If $x_{k+1}\rightarrow 0$ as $k\rightarrow\infty$, then $x_{k+1}^{-}\rightarrow 0$ as $k\rightarrow\infty$. So we let $k\rightarrow\infty$, the following limit must holds:

and then by taking limit as $k\rightarrow\infty$,

where $C(m,n)^{-1}$ denotes the inverse of $C(m,n)$. So the initial condition $x_{0}$, if written as a column vector, has the form of

Written as a column vecto, the solution of the dynamical system is of the form of

Plugging the equation (44) back to the above expression, we have

Use spectrum norm $\left\|\cdot\right\|$ for matrices, we have

Denote $\lambda$ the least negative eigenvalue, then the spectrum norm of $C(k+1+i,k+1)^{-1}$ is

Since the sequence $\alpha_{i}$ is chosen to be small, we have

Using the inequality $1+x\leq e^{x}$, we have

Since by assumption, $\alpha_{j}\in\Omega\left(\frac{1}{j^{p}}\right)$ and $\lambda<0$, so $1-\alpha_{j}\lambda$ is positive and bounded, i.e. $1<1-\alpha_{j}\lambda<c$. And then the following inequalities hold:

Multiplying by the negative number $\lambda$, we have

Combining with the inequality 82, we obtain

By definition of definite integral, we notice that

which implies that $\int_{k}^{\infty}\exp(-t^{1-p})dt$ converges, so does the series 89. Since the incomplete Gamma function $\Gamma(s,x)$ has the property

let $s=\frac{1}{1-p}$ and $x=k^{1-p}$ so that $x^{s-1}=(k^{1-p})^{\frac{1}{1-p}-1}=k^{p}$, we have that

as $k\rightarrow\infty$. This implies that $R_{k}$ is bounded as $k\rightarrow\infty$. ∎

Since $B(k,i+1)$ is diagonal, denote $\lambda$ the least positive eigenvalue of $H$, by definition of $B(k,i+1)$, we have that

Consider the difference between $S_{k+1}$ and $S_{k}$, we have

If $S_{k}=\frac{1}{\lambda}$, then $S_{k}=S_{k+1}\equiv\frac{1}{\lambda}$.

If $S_{k}<\frac{1}{\lambda}$, or equivalently $1-\lambda S_{k}>0$, then $S_{k+1}-S_{k}>0$, and $S_{k}$ increases until $S_{k}>\frac{1}{\lambda}$.

So $S_{k}$ decreases or increases to $\frac{1}{\lambda}$ (meaning that $S_{k}$ is bounded), or $S_{k}$ oscillates around $\frac{1}{\lambda}$. Suppose that $S_{k}<\frac{1}{\lambda}$ and $S_{k+1}>\frac{1}{\lambda}$, we have that

when $k$ is large so that $\alpha_{k}<\frac{1}{\lambda}$. Then in conclusion, $S_{k}$ is bounded, and the proof completes. ∎

Denote $(Tx)_{k+1}^{+}$ and $(Tx)_{k+1}^{-}$ the stable and unstable component of $(Tx)_{k+1}$ respectively. We prove $\lim_{k\rightarrow\infty}(Tx)_{k+1}^{+}=0$ and $\lim_{k\rightarrow\infty}(Tx)_{k+1}^{-}=0$ separately. 1. $\lim_{k\rightarrow\infty}(Tx)_{k+1}^{+}=0$: According to the definition of $T$ in 57,

Since $\left\|B(k,0)\right\|\rightarrow 0$ as $k\rightarrow\infty$, it is enough to show that

as $k\rightarrow\infty$. From the Lipschitz condition on $\eta$, we have that

From the proof of Lemma C.2, we know that $S_{k}$ is bounded, and thus $\left|S_{k+1}-S_{k}\right|\rightarrow 0$ as $k\rightarrow\infty$. Similar to proof of C.2, we have the following observation:

If $S_{k+1}-S_{k}>0$, then $\left|x_{k+1}\right|-\lambda S_{k}>0$, or $S_{k}<\frac{\left|x_{k}\right|}{\lambda}$;

If $S_{k+1}-S_{k}<0$, then $\left|x_{k+1}\right|-\lambda S_{k}<0$, or $S_{k}>\frac{\left|x_{k}\right|}{\lambda}$;

If $S_{k+1}-S_{k}=0$, then $S_{k}=\text{constant}$.

decreasing but $S_{k}>\frac{\left\|x_{k}\right\|}{\lambda}$,

oscillating around $\frac{\left\|x_{k}\right\|}{\lambda}$.

If $S_{k}$ is of case 1, then $\lim_{k}S_{k}$ exists. Suppose that this limit is positive, but since we have $\sum\alpha_{k}=\infty$ and

implying that $S_{k}\rightarrow\infty$. So we conclude that $\lim_{k}S_{k}=0$, contradicting to the fact that $\lim_{k}S_{k}$ exists. So the $\lim_{k}S_{k}$ must be if $S_{k}$ is of case 1. If $S_{k}$ is of case 2, then immediately $\liminf S_{k}=0$. Suppose that $\limsup S_{k}>0$. Since $S_{k}$ decreases whenever $S_{k}>\frac{\left\|x_{k}\right\|}{\lambda}$ and $S_{k}$ increases whenever $S_{k}<\frac{\left\|x_{k}\right\|}{\lambda}$, we can find a subsequence $S_{k_{m}}$, with $S_{k_{m}-1}<S_{k_{m}}$, converging to $\limsup S_{k}$ as $m\rightarrow\infty$. But this is impossible since $S_{k_{m}-1}<\frac{\left\|x_{k}\right\|}{\lambda}$ and then $S_{k_{m}-1}\rightarrow 0$ as $m\rightarrow\infty$, which means $\lim_{m}\left|S_{k_{m}-1}-S_{k_{m}}\right|$ is positive, contradicting to the fact that $\lim_{k}\left|S_{k}-S_{k+1}\right|=0$. And thus, we have $\limsup_{k}S_{k}=0$, meaning that $\lim_{k}S_{k}=0$. So we conclude that either in case 1 or 2, the limit $\lim_{k}S_{k}=0$, which completes the proof of part 1. 2. $\lim_{k\rightarrow\infty}(Tx)_{k+1}^{-}=0$: According to the equation 57,

And from the Lipschitz condition of on $\eta$, we have that

Since $\{x_{n}\}$ converges to 0 as $n\rightarrow\infty$, $\sup_{n>k}\left|x_{n}\right|\rightarrow 0$ as $k\rightarrow\infty$. And this completes the proof of part 2. ∎

There exists a real number $\delta>0$ such that the operator $T$ given by equation 57

From Lemma C.1 and Lemma C.2, we know that in equation (78),

Since $B(k,0)$ is on the stable subspace and whose norm is calculated by

Then we can choose small positive $\epsilon$ so that

and by the choice of $\epsilon$, we know that $K<1$. Let $\delta>0$ be the radius corresponding to $\epsilon$ so that the Lipschitz condition is satisfied. Combining 78, 103 and 104, we have that

Since above $k$ is taken arbitrarily, we conclude that

If we consider the sequence $x$ as a sequence of functions with the initial condition as the variable, the general term $x_{n}$ is written as $x_{n}(x_{0})$, then the equation (106) is written as

This means that if the some initial condition $x_{0}$ goes to 0 through the discrete time process $\{x_{n}(x_{0})\}$, its stable and unstable component must satisfy following relation:

and the equation $x_{0}^{-}=\Phi(x_{0}^{+},x_{0}^{-})$ defines an implicit function $x_{0}^{-}=\varphi(x_{0}^{+})$ by the uniqueness of Banach fixed point. Next we will show that $\varphi$ is differentiable with respect to $x_{0}^{+}$. Since it is enough to show the function $\Phi(x_{0}^{+},x_{0}^{-})$ is differentiable with respect to $x_{0}^{+}$. And it is enough to show that each $x_{n}(x_{0})$, if considered as a function of initial condition $x_{0}$, is differentiable with respect to $x_{0}^{+}$.

The solution $x_{n}(x_{0}^{+},x_{0}^{-})$ is of $C^{1}$ with respect to $x_{0}^{+}$ provided $\eta(n,x)$ is of $C^{1}$.

Proof. It is equivalent to show that $\frac{\partial x_{n}}{\partial x_{0,j}}$, $j=1,..,d$, where $d$ is the dimension of stable vector space, exist and are continuous for small $\left|x_{0}\right|$. Let $P^{+}$ and $P^{-}$ be the projection operators to the stable and unstable subspaces respectively, then the solution (with initial condition $x_{0}$) of the dynamical system can be written as

Let $h$ be a scalar and $e_{j}$ be the $j$th standard basis. Denote

Plugging above identity to 107, we can compute the difference quotient $q(k+1,x_{0},h)=\frac{x_{k+1}(x_{0}+he_{j})-x_{k+1}(x_{0})}{h}$

Since for the solution $x(n,x_{0})$, $x(n,x_{0})\rightarrow 0$ as $n\rightarrow\infty$, and $\left\|\eta(n,x)-\eta(n,\bar{x})\right\|\leq\epsilon\left\|x-\bar{x}\right\|$, we have that

Given $\delta>0$, $\left|h\right|$ can be chosen small that by the mean value theorem and the continuity of $D\eta$, we have

where $x_{n}^{\prime}$ is a point on the line segment joining $x_{n}(x_{0}+he_{j})$ and $x_{n}(x_{0})$. Since

so $\left\|q(n,x_{0},h)\right\|$ is bounded, denoted as

And then $\left\|\Delta_{n}\right\|\leq\delta M$. Define the operator as

Notice that the part of infinite sum converges to 0 as $k\rightarrow\infty$, one can choose $k$ large enough so that the norm of the infinite sum to be small, and then we have for any small $\epsilon^{\prime}>0$, the $\sup\left\|q-\psi\right\|$ satisfies

Where $K^{\prime\prime}$ is the bound from that $|\Delta_{i}|\rightarrow 0$ as $i\rightarrow\infty$. One choose neighborhood small enough so that $K^{\prime}\epsilon d<\frac{1}{2}$ and then we have

Since $\left\|\eta^{-}(k,x_{k})\right\|\rightarrow 0$ as $k\rightarrow\infty$ due to $\alpha_{k}$, and $\left\|C_{k+1}x_{k}^{-}\right\|\rightarrow\infty$ as $k\rightarrow\infty$ by assumption that $x_{k}^{-}$ is bounded away from . But this contradicts to the assumption $x_{k+1}^{-}$ is bounded in $U$. The proof completes. ∎