# Nesterov's momentum derivation

On page 75 in Sutskever's thesis http://www.cs.utoronto.ca/~ilya/pubs/ilya_sutskever_phd_thesis.pdf

In equation (7.5) setting $a_0=1$,

$a_{t+1} = (1+\sqrt{4 a_t^2 + 1})/2$

The author said, "to understand the sequence $a_t$ we note that the function $x \rightarrow (1+ \sqrt{4x^2+1})/2$ quickly approaches $x \rightarrow x + 0.5$ from below as $x \rightarrow \infty$,"

then he claims

"so $a_t \approx (t+4)/2$ for large $t$ "

I couldn't figure out how he made the deduction here. It is not at all obvious to me how one might even guess the express. If we brute-force it we could probably guess $t/2$ but the $t+4$ term seems to come from nowhere at the large number limit.

• That's not considered good practise, here, sorry! If you want to make updates to your question math.stackexchange.com/questions/2602028/…, you're welcome to do so, but don't pollute this space with innumerable identical questions, please! – Professor Vector Jan 12 '18 at 9:17
• I have deleted the duplicate question. – Patrick Jan 12 '18 at 9:19
• Well, "from below" is funny, because $(1+ \sqrt{4x^2+1})/2>(1+ \sqrt{4x^2})/2=x+1/2$, but otherwise, I can't see much of a problem. – Professor Vector Jan 12 '18 at 9:29
• How does one get the approximation $a_t \approx (t+4)/2$? – Patrick Jan 12 '18 at 9:37
• Please, validate answers to your questions. Consider that, after, say, 2 monthes , there will be no more activity on the past questions. It is a service to the community who tries to help you heartily to say : well, among all the answers, this one is the best, or at least this one has brought me information. It will direct further readers to the "good answer". – Jean Marie Feb 2 at 14:30

(see image below)

Let $f(x):=(1+ \sqrt{4x^2+1})/2$. It is the cartesian equation of a hyperbola (H) ; the interesting half branch being represented in black in Fig. 1 ; its asymptote (A), represented in red, has equation $y=g(x):=x+1/2$ (for $x>0$).

The other line, let us call it (L), has equation $y=x$. Its usage is classical in geometric representation of iterative methods $u_{n+1}=\varphi(u_n)$. take a look for instance to (http://wwwf.imperial.ac.uk/metric/metric_public/numerical_methods/iteration/fixed_point_iteration.html) which gives different instances of staircase patterns generated by sequences of points $(u_k, u_k), (u_k,\varphi(u_k)$.

Comparison between the two iterations $$\begin{cases}a_{n+1}=f(a_n)\\ t_{n+1}=g(t_n)\end{cases}$$ can be transferred to a comparison of the staircase pattern (in blue) between (H) and (L) and the stair case pattern (in black) between (A) and (L) ; for the

The second staircase pattern (blue points with coordinates $(1,3/2), (3/2,3/2), (3/2,2),...$ is asymptotic to the first one.

In the case of the second iteration, it is clear that the increasing rate is constant, i.e., it's an arithmetic progression, thus given by the formula you desired to understand.

• Is my solution understandable for you ? – Jean Marie Jan 12 '18 at 21:56
• @Claude Leibovici Bonjour Claude ! How would you deal with this question ? – Jean Marie Jan 13 '18 at 5:47

The claim "$a_t \approx (t+4)/2$ for large $t$" is not actually true.

Writing $a_t = (t+c_t)/2$, one finds $c_{t+1}>c_t$ for all $t$, since $$t+c_{t+1} = \sqrt{(t+c_t)^2 +1}>t+c_t.$$ Claim: $c_t\to\infty$ as $t\to\infty$. Suppose instead $\{c_t\}$ is bounded by $M$. Then upon squaring and factoring we find $$1 = (t+c_{t+1})^2-(t+c_t)^2 = (c_{t+1}-c_t)(2t+c_{t+1}+c_t)<(c_{t+1}-c_t)(2t+2M),$$ hence $$c_{t+1} - c_t > \frac12 \frac1{t+M} ,$$ and it follows $c_t\to\infty$ (albeit slowly) due to divergence of the harmonic series.