Convergence Behavior of Sequence with Diminishing Contraction

Question

Lets say for a given positive sequence $(h_n)_n$ and starting points $a_0, a_1>0$ we define the recursive sequence $$ a_{n+1} = \left(1- \frac{h_n}{\sqrt{\sum_{k=0}^{n-1}a_k^2}}\right)a_n $$ Can we say anything about the convergence behaviour of $a_n$ for

1. constant $h=h_n$? (eventually the bracket will be smaller than one, as the sum of squares increases. I.e. we have an asymptotic contraction. So we definitely get convergence. But do we get convergence towards zero?)
2. for $h_n$ we are allowed to select without knowledge of the $a_n$?

(Context: I am trying to understand a very special case of the AdaGrad algorithm).

Answer 1

I will only consider the case $h_n = h > 0$ is constant. Let $b_n = a_n^2$ and $s_n = \sum_{k=0}^{n} b_k$. Then

$$ b_{n+1} = \left( 1 - \frac{h}{\sqrt{s_{n-1}}}\right)^2 b_n. $$

Also, since $(s_n)$ is nondecreasing, $s_{\infty} := \lim_n s_n = \sup_n s_n \in (0, +\infty]$.

Claim 1. $s_{\infty} > h^2/4$.

Suppose otherwise. Then $s_n \leq h^2/4$ for all $n$, and so,

$$ \left| 1 - \frac{h}{\sqrt{s_{n-1}}} \right| = \frac{h}{\sqrt{s_{n-1}}} - 1 \geq \frac{h}{\sqrt{h^2/4}} - 1 = 1. $$

This implies that $b_{n+1} \geq b_n$ holds for all $n \geq 1$, and so, $s_n \geq n b_1$ holds. Then this contradicts the assumption that $(s_n)$ is bounded. $\square$

Claim 2. There exist $C, \gamma > 0$ such that $$b_n \leq C e^{-\gamma n}$$ for all $n$.

Case 1. Suppose $s_{\infty} \leq h^2$ for all $n$. Then by fixing $N$ such that $s_N > h^2/4$, for $n > N$ we have

$$ \left| 1 - \frac{h}{\sqrt{s_{n-1}}} \right| = \frac{h}{\sqrt{s_{n-1}}} - 1 \leq \frac{h}{\sqrt{s_{N}}} - 1 < 1 $$

So, for $k \geq 1$ we conclude

$$ b_{N+k} \leq \left( 1 - \frac{h}{\sqrt{s_{N}}} \right)^{2(k-1)} b_{N+1} $$

and we are done in this case.

Case 2. Suppose $s_{\infty} > h^2$. Let $N$ be such that $s_n > h^2$ for all $n \geq N$. Note that $b_n$ is non-decreasing for $n > N$. Then by noting that

$$ 0 < 1 - \frac{h}{\sqrt{s_{N+k-1}}} \leq \exp\biggl(-\frac{h}{\sqrt{s_{N+k-1}}}\biggr) \leq \exp\biggl(- \frac{h}{\sqrt{s_{N-1} + k b_N}}\biggr) $$

for all $k \geq 1$, we get

$$ b_{N+k} \leq \exp\biggl(- \sum_{j=1}^{k-1} \frac{2h}{\sqrt{s_{N-1} + j b_N}}\biggr) b_{N+1}. $$

However, since

$$ \sum_{j=1}^{k-1} \frac{h}{\sqrt{s_{N-1} + j b_N}} \sim c\sqrt{k} \qquad \text{as} \quad k \to \infty $$

with the constant $ c = 4h/\sqrt{b_N} > 0$, it follows that $ (b_n) $ decays at least as fast as a stretched exponential function. This then implies that $s_{\infty} $ is finite, and so,

$$ b_{N+k} \leq \left( 1 - \frac{h}{\sqrt{s_{\infty}}} \right)^{2(k-1)} b_{N+1}. $$

Answer 2

Interesting question, I can convince you that if $a_0$ and $a_1$ are sufficiently large (under the setting that $h_n \equiv h$ is a fixed positive constant), $a_n \to 0$. Because in this case $a_n \geq 0$ for all $n$, and the infinite series $\sum_{n\geq 0} a_n$ converges (just use the ratio test), so one must have $a_n \to 0$ as $n \to \infty$. The case for $a_0, a_1$ near $0$ or not that large might be trickier, as $a_n$ will be negative at least for some small values of $n$.