Sheet 4

While there are in total, you may consider all points above the standard $24$ to be bonus points.

Exercise 1 (Lower Bounds).

In this exercise, we will bound the convergence rates of algorithms which pick their iterates $x_{k\mathrm{+}\mathrm{1}}$ from

$$span[\nabla f(x_0),\mathrm{\dots },\nabla f(x_k)]+x_0.$$

We consider the function

$$f_d(x)=\frac{1}{2}{(x^{(1)}-1)}^2+\frac{1}{2}\sum _{i=1}^{d-1}{(x^{(i)}-x^{(i+1)})}^2$$

1. To understand our function $f_d$ better, we want to view it as a potential on a graph. For this consider the undirected graph $G=(V,E)$ with vertices

   $$V=\{1,\mathrm{\dots },d\}$$

   and edges

   $$E=\{(i,i+1):1\le i\le d-1\}.$$

   Draw a picture of this graph.

   Solution.

   The graph is simply a chain

   

   ∎

2. We now interpret $x^{(i)}$ as a quantity (e.g. of heat) at vertex $i$ of our graph $G$. Our potential $f_d$ decreases, if the quantities at connected vertices $i$ and $i+1$ are of similar size. I.e. if ${(x^{(i)}-x^{(i+1)})}^2$ is small. Additionally there is a pull for $x^{(1)}$ to be equal to $1$. Use this intuition to find the minimizer $x_{*}$ of $f_d$.

   Solution.

   The minimizer is $x_{*}={(1,\mathrm{\dots },1)}^T\in {ℝ}^d$ since $f_d(x_{*})=0$ and $f_d(x)\ge 0$. ∎

3. The matrix $A^G\in {ℝ}^{d\times d}$ with

   is called the “Graph-Laplacian” of $G$. The degree of vertex $i$ are the number of connecting edges. Calculate $A^G$ for $G$ and prove that

   $$\nabla f_d(x)=A^{G}x+(x^{(1)}-1)e_1=(A^G+e_1{e}_1^T)x-e_1.$$

   Solution.

   The Graph-Laplacian of $G$ is given by

   Let $i\ne 1,d$ then

   $$\frac{\partial f_d}{\partial x_i}=[x^{(i)}-x^{(i+1)}]-[x^{(i-1)}-x^{(i)}]=2x^{(i)}-x^{(i-1)}-x^{(i+1)}={(A^{G}x)}_i$$

   similarly looking at the cases $i=1,d$ individually immediately reveals

   $$\nabla f_d(x)=A^{G}x+(x^{(1)}-1)e_1.\mathit{∎}$$

4. Prove that the Hessian $H={\nabla }^2{f}_d(x)$ is constant and positive definite to show that $f_d$ is convex. Prove that the operator norm of $H$ is smaller than $4$. Argue that

   $$g_d(x):=\frac{L}{4}{f}_d(x)$$

   is therefore $L$-smooth.

   Solution.

   Taking the derivative of the gradient we calculated previously yields

   $$H={\nabla }^2{f}_d(x)=A^G+e_1{e}_1^T.$$

   To show positive definiteness, let $y$ be arbitrary

   $$y^{T}Hy={(e_1^{T}y)}^2+y^T{A}^{G}y={(y^{(1)})}^2+\sum _{i=1}^{d-1}{(y^{(i)}-y^{(i+1)})}^2\ge 0.$$

   To find the largest eigenvalue of $H$ we want to calculate the operator norm. For this we use ${(a-b)}^2\le 2(a^2+b^2)$ to get

   $$⟨y,Hy⟩\le {(y^{(1)})}^2+2\sum _{i=1}^{d-1}{(y^{(i)})}^2+{(y^{(i+1)})}^2\le 4\sum _{i=1}^d{(y^{(i)})}^2=4{\parallel y\parallel }^2.$$

   Thus we get

   $$\parallel H\parallel =\underset{y:\parallel y\parallel =1}{sup}⟨y,Hy⟩\le 4.$$

   Since the operator norm coincides with the largest absolute eigenvalue for symmetric matrices, this proves our claim. Finally $L$-smoothness of $g_d$ follows from

   $$\parallel \nabla g_d(x)-\nabla g_d(y)\parallel =\frac{L}{4}\parallel \nabla f_d(x)-\nabla f_d(y)\parallel =\frac{L}{4}\parallel H(x-y)\parallel \le \underset{\le L}{\underbrace{\frac{L}{4}\parallel H\parallel }}\parallel x-y\parallel .\mathit{∎}$$

5. Assume $x_0=0$ and and that ${(x_n)}_{n\in \mathbb{N}}$ is chosen with the restriction

   $$x_{n+1}\in {𝒦}_n:=span[\nabla g_d(x_0),\mathrm{\dots },\nabla g_d(x_n)].$$

   To make notation easier we are going to identify ${ℝ}^d$ with an isomorph subset of sequences

   $${ℝ}^d:=\{x\in {\mathrm{\ell }}^2:x^{(i)}=0\mathit{\hspace{1em}}\forall i>n\}$$

   then ${ℝ}^n$ is a subset of ${ℝ}^d$ for $n\le d$. Prove inductively that

   $${𝒦}_n\subseteq {ℝ}^{n+1}\subseteq {ℝ}^d$$

   Solution.

   We have the induction start $n=0$ by

   $$g_d(x_0)=-\frac{L}{4}{e}_1\in {ℝ}^1.$$

   Now assume

   $${𝒦}_{n-1}\subseteq {ℝ}^n,$$

   then by our selection process $x_n\in {ℝ}^n$. But then

   $$\frac{4}{L}\nabla g_d(x_n)=\underset{\in {ℝ}^{n+1}}{\underbrace{A^G{x}_n}}+\underset{\in {ℝ}^1}{\underbrace{(x_n-1)e_1}}\in {ℝ}^{n+1}.$$

   We therefore have ${𝒦}_n=span[{𝒦}_{n-1},\nabla g_d(x_n)]\subseteq {ℝ}^{n+1}$.

   Notice how the low connectedness of the graph $G$ limits the spread of our quantity $x_n$. A higher connectedness would allow for information to travel much quicker. ∎

6. We now want to bound the convergence speed of $x_n$ to $x_{*}$. For this we select $d=2n+1$.

   Note: We may choose a larger dimension $d$ by defining $f_{2n+1}$ on the subset ${ℝ}^{2n+1}$ in ${ℝ}^d$. The important requirement is therefore $2n+1\le d$. But without loss of generality we assume equality.

   Use the knowledge we have collected so far to argue

   $${\parallel x_{*}-x_n\parallel }^2\ge d-n\ge \frac{1}{2}{\parallel x_{*}-x_0\parallel }^2.$$

   Solution.

   Since $x_n\in {ℝ}^n$ we know that

   ${\parallel x_{*}-x_n\parallel }^2$ $={\displaystyle \sum _{i=1}^d}{(x_{*}^{(i)}-x_n^{(i)})}^2$

   $\ge {\displaystyle \sum _{i=n+1}^d}{(x_{*}^{(i)})}^2$

   $=d-n\stackrel{d=2n+1}{=}n+1=\frac{n+1}{2n+1}d\ge \frac{1}{2}d={\displaystyle \frac{1}{2}}{\displaystyle \sum _{i=1}^d}{1}^2=\frac{1}{2}{\parallel x_{*}-x_0\parallel }^2.\mathit{∎}$

7. To prevent the convergence of the loss $g_d(x_n)$ to $g_d(x_{*})$ we need a more sophisticated argument. For this consider

   $${\tilde{g}}_n(x):=\frac{L}{4}[f_n(x)+\frac{1}{2}{(x^{(n)}-0)}^2].$$

   Argue that on ${ℝ}^n\subset {ℝ}^d$ the functions ${\tilde{g}}_n$ and $g_d$ are identical. Use this observation to prove

   $$g_d(x_n)-\underset{x}{inf}{g}_d(x)\ge \underset{x}{inf}{\tilde{g}}_n(x).$$

   Solution.

   Let $x\in {ℝ}^n$. Then using $x^{(n+1)}=0$ we have

   $${\tilde{g}}_n(x)=\frac{L}{8}\left[{(x^{(1)}-1)}^2+\sum _{i=1}^n(x^{(i)}-x^{(i+1)})\right]=g_d(x)$$

   using $x^{(i)}=0$ for all $i>n$ for the second equality sign. Since $x_n\in {ℝ}^n$ we therefore can replace $g_d$ with $g_n$ at will to get

   $$g_d(x_n)-\underset{=0}{\underbrace{\underset{x}{inf}{g}_d(x)}}={\tilde{g}}_n(x_n)\ge \underset{x}{inf}\tilde{g}(x).\mathit{∎}$$

8. Our goal is now to calculate ${inf}_x{\tilde{g}}_n(x)$. Prove convexity of ${\tilde{g}}_n$ and prove that

   is its minimum. Then plug our solution into ${\tilde{g}}_n$ (or $g_d$, since ${\widehat{x}}_n$ is in the subset ${ℝ}^n$ after all), to obtain the lower bound

   $$g_d(x_n)-\underset{x}{inf}{g}_d(x)\ge \frac{L{\parallel x_0-x_{*}\parallel }^2}{8(n+1)d}\ge \frac{L{\parallel x_0-x_{*}\parallel }^2}{16{(n+1)}^2}.$$

   Solution.

   We have

   $$\nabla {\tilde{g}}_n(x)=\frac{L}{4}[A^{G_n}x+(x^{(1)}-1)e_1+(x^{(n)})e_n]=\frac{L}{4}(A^{G_n}+e_1{e}_1^T+e_n{e}_n^T)x-e_1$$

   where $A^{G_n}$ is the Graph-Laplacian for $f_n$. Then the Hessian is obviously positive definite

   $${\nabla }^2{\tilde{g}}_n(x)=\frac{L}{4}(A^{G_n}+e_1{e}_1^T+e_n{e}_n^T)$$

   as we could apply the same arguments as for $f_n$. So ${\tilde{g}}_n$ is convex. We now plug ${\widehat{x}}_n$ into $\nabla {\tilde{g}}_n$ to verify the first order condition, proving it is a minimum

   ${\displaystyle \frac{4}{L}}{\displaystyle \frac{\partial {\tilde{g}}_n}{\partial x_i}}({\widehat{x}}_n)$ $={(A^{G_n}{\widehat{x}}_n)}_i+\underset{=-\frac{1}{n+1}}{\underbrace{({\widehat{x}}_n^{(1)}-1)}}{\delta }_{i1}+\underset{=\frac{1}{n+1}}{\underbrace{({\widehat{x}}_n^{(n)})}}{\delta }_{in}$

   $=\underset{-\frac{1}{n+1}}{\underbrace{[{\widehat{x}}_n^{(i)}-{\widehat{x}}_n^{(i+1)}]}}{\mathrm{𝟙}}_{i\ne n}-\underset{-\frac{1}{n+1}}{\underbrace{[{\widehat{x}}_n^{(i-1)}-{\widehat{x}}_n^{(i)}]}}{\mathrm{𝟙}}_{i\ne 1}-\frac{1}{n+1}{\delta }_{i1}+\frac{1}{n+1}{\delta }_{in}$

   $=0.$

   We now know that

   $\underset{x}{inf}{\tilde{g}}_n(x)$ $={\tilde{g}}_n({\widehat{x}}_n)={\displaystyle \frac{L}{8}}\left[{\left(-\frac{1}{n+1}\right)}^2+{\left(1-\frac{n}{n+1}\right)}^2+{\displaystyle \sum _{i=1}^{n-1}}{\left(\frac{i+1}{n+1}-\frac{i}{n+1}\right)}^2\right]$

   $={\displaystyle \frac{L}{8}}{\displaystyle \sum _{i=0}^n}{\left(\frac{1}{n+1}\right)}^2={\displaystyle \frac{L}{8(n+1)}}\stackrel{d={\parallel x_0-x_{*}\parallel }^2}{=}{\displaystyle \frac{L{\parallel x_0-x_{*}\parallel }^2}{8(n+1)d}}$

   $\ge {\displaystyle \frac{L{\parallel x_0-x_{*}\parallel }^2}{16{(n+1)}^2}}$

   using $d=2n+1$ again. ∎

9. Argue that we only needed

   $$x_n=x_0+\sum _{k=0}^{n-1}{A}_k\nabla f(x_k)$$

   with upper triangular matrices $A_k$ to make these bounds work. Since adaptive methods (like Adam) use diagonal matrices $A_k$, they are therefore covered by these bounds.

   Solution.

   We only needed ${𝒦}_n\subseteq {ℝ}^{n+1}$ which we proved by induction using only this fact about ${𝒦}_{n-1}$. Since upper triangular matrices do not change this fact, we may as well allow them. ∎

10. Bask in our glory! For we have proven that …? Summarize our results into a theorem.

    Solution.

    Theorem (Nesterov).

    Assume there exists upper triangular matrices $A_{k\mathrm{,}n}$ such that the sequence ${\mathrm{(}{x}_n\mathrm{)}}_{n\mathrm{\in }\mathbb{N}}$ in ${ℝ}^d$ is selected by the rule

    $$x_n=x_0+\sum _{k=0}^{n-1}{A}_{k,n}\nabla f(x_k)$$

    for a convex, $L$-smooth $f$ to minimize. Then up to $n\mathrm{\le }\frac{d\mathrm{-}\mathrm{1}}{\mathrm{2}}$ there exists a convex, $L$-smooth function $f$ such that

    $\parallel x_n-x_{*}\parallel$ $\ge \frac{1}{\sqrt{2}}\parallel x_0-x_{*}\parallel$

    $f(x_n)-\underset{x}{inf}f(x)$ $\ge {\displaystyle \frac{L{\parallel x_0-x_{*}\parallel }^2}{16{(n+1)}^2}}$

    for $f\mathit{}\mathrm{(}{x}_{\mathrm{*}}\mathrm{)}\mathrm{=}{\inf }_x\mathit{}f\mathit{}\mathrm{(}x\mathrm{)}$.

    ∎

11. (Bonus) If you wish, you may want to try and repeat those steps for

    $$G_d(x)=\frac{L-\mu }{L}{g}_d(x)+\frac{\mu }{2}{\parallel x\parallel }^2$$

    to prove an equivalent result for $\mu$-strongly convex functions. Unfortunately finding $x_{*}$ is much more difficult in this case. Letting $d\to \mathrm{\infty }$ makes this problem tractable again with solution

    $$x_{*}^{(i)}={\left(\frac{\sqrt{\kappa }-1}{\sqrt{\kappa }+1}\right)}^i.$$

Exercise 2 (Conjugate Gradient Descent).

Consider a quadratic function

$$f(x)=\frac{1}{2}{(x-x_{*})}^{T}H(x-x_{*})$$

for some symmetric and positive definite $H$ and consider the hilbert space $\mathscr{H}\mathrm{=}\mathrm{(}{ℝ}^d\mathrm{,}{\mathrm{⟨}\mathrm{\cdot }\mathrm{,}\mathrm{\cdot }\mathrm{⟩}}_H\mathrm{)}$ with

$${⟨x,y⟩}_H=⟨x,Hy⟩$$

1. Prove that ${⟨\cdot ,\cdot ⟩}_H$ is a well-defined scalar product. Convince yourself that

   $$f(x)=\frac{1}{2}{\parallel x-x_{*}\parallel }_H^2.$$

   Solution.

   Bilinearity is trivial, the positive-definiteness follows from this property of $H$. We have

   $$f(x)=\frac{1}{2}⟨x-x_{*},H(x-x_{*})⟩=\frac{1}{2}{⟨x-x_{*},(x-x_{*})⟩}_H=\frac{1}{2}{\parallel x-x_{*}\parallel }_H^2.\mathit{∎}$$

2. Determine the derivative ${\nabla }_{H}f(x)$ of $f$ in $\mathscr{H}$

   Hint.

   Recall that ${\mathrm{\nabla }}_H\mathit{}f\mathit{}\mathrm{(}x\mathrm{)}$ is the unique vector satisfying

   $$0=\underset{v\to 0}{lim}\frac{|f(x+v)-f(x)-{⟨{\nabla }_{H}f(x),v⟩}_H|}{{\parallel v\parallel }_H}.$$

   Solution.

   We need

   $0$= lim_v→0 —f(x+v) - f(x) - ⟨∇ H f(x) , v⟩ H — ∥v∥ H

   $=\underset{v\to 0}{lim}{\displaystyle \frac{|f(x+v)-f(x)-⟨H{\nabla }_{H}f(x),v⟩|}{\parallel v\parallel }}\underset{\ge c}{\underbrace{{\displaystyle \frac{\parallel v\parallel }{{\parallel v\parallel }_H}}}}.$

   We can bound the fraction of norms by a constant $c>0$ from below due to equivalence of all norms in ${ℝ}^d$. This lower bound on the second fraction forces the first fraction to converge to zero. But this implies that

   $$\nabla f(x)=H{\nabla }_{H}f(x)$$

   by the definition (and uniqueness) of $\nabla f(x)$. Thus the gradient we are looking for is

   $${\nabla }_{H}f(x)=H^{-1}\nabla f(x).\mathit{∎}$$

3. Since gradient descent in the space $\mathscr{H}$ is therefore computationally the Newton method, we want to find a different method of optimization. Consider an arbitrary set of conjugate ($H$-orthogonal) directions $(v_1,\mathrm{\dots }{v}_d)$, i.e. ${⟨v_i,v_j⟩}_H={\delta }_{ij}$, and for some starting point $x_0\in {ℝ}^d$ the following descent algorithm:

   $$x_{k+1}=x_k-{\alpha }_k{v}_{k+1}\mathit{\hspace{1em}}\text{with}\mathit{\hspace{1em}}{\alpha }_k:=\underset{\alpha }{argmin}f(x_k-\alpha v_{k+1}).$$

   Optimizing over $\alpha$ in this manner is known as “line-search”. Using $y^{(i)}:=⟨y,v_i⟩$ prove that

   $$(x_k-x_{*})=\sum _{i=k+1}^d{(x_0-x_{*})}^{(i)}{v}_i=\underset{x}{argmin}\{f(x):x\in x_0+span[v_1,\mathrm{\dots },v_k]\}-x_{*}.$$

   Deduce that conjugate descent (CD) converges in $d$ steps.

   Solution.

   We proceed by induction. The induction start with $k=0$ is obvious. Let us now consider $x_{k+1}$. By its definition we have

   $2f(x_{k+1})$ $=\underset{\alpha }{\min }2f(x_k-\alpha v_{k+1})$

   $=\underset{\alpha }{\min }{\parallel x_k-\alpha v_{k+1}\parallel }_H$

   $=\underset{\alpha }{\min }{\parallel {\displaystyle \sum _{i=1}^d}{(x_k-x_{*})}^{(i)}{v}_i-\alpha v_{k+1}\parallel }_H$

   $=\underset{\alpha }{\min }{[{(x_k-x_{*})}^{(k+1)}-\alpha ]}^2\parallel v_{k+1}{\parallel }_H^2+{\displaystyle \sum _{i=k+2}^d}{[{(x_k-x_{*})}^{(i)}]}^2\parallel v_i{\parallel }_H^2$

   $={\displaystyle \sum _{i=k+2}^d}{[{(x_k-x_{*})}^{(i)}]}^2.$

   the minimizer is therefore ${\alpha }_k={(x_k-x_{*})}^{(k+1)}$. This removes the $v_{k+1}$ component leaving us with the components $v_{k+2}$ and up. Note that ${(x_k-x_{*})}^{(i)}={(x_0-x_{*})}^{(i)}$ for all $i\ge k+1$ by induction. Similarly we can see that this is a minimum in the span of $v_1,\mathrm{\dots },v_{k+1}$, as we have removed those components completely and

   $$f(x)={\parallel x-x_{*}\parallel }_H^2=\sum _{i=1}^d{[{(x-x_{*})}^{(i)}]}^2.$$

   Since we can not touch the other components due to $H$-orthogonality, this is the best we can do. ∎

4. If we had $v_i=\nabla f(x_{i-1})$, then this algorithm would be optimal in the set of algorithms we considered in the previous exercise. Unfortunately the gradients $\nabla f(x_{i-1})$ are generally not conjugate. So while we may select an arbitrary set of conjugate $v_i$, we cannot select the gradients directly.

   Instead we are going to do the next best thing and inductively select $v_{k+1}$ such that

   $${𝒦}_k:=span[\nabla f(x_0),\mathrm{\dots }\nabla f(x_k)]=span[v_1,\mathrm{\dots },v_{k+1}]$$

   using the Gram-Schmidt procedure to make $v_{k+1}$ conjugate to $v_1,\mathrm{\dots },v_k$. Since Gram-Schmidt is still computationally too expensive for our tastes, you please inductively prove

   $${𝒦}_k=span[H^1(x_0-x_{*}),\mathrm{\dots },H^{k+1}(x_0-x_{*})].$$

   assuming ${𝒦}_k$ is $(k+1)$-dimensional. I.e. ${𝒦}_k$ is a “$H$-Krylov subspace”.

   Solution.

   The induction start $k=0$ follows directly from

   $$\nabla f(x_0)=H(x_0-x_{*})$$

   and the definition of ${𝒦}_0$. Assume we have the claim for $k-1$, then

   $$\nabla f(x_k)=H(x_k-x_{*})=H(x_{k-1}-{\alpha }_{k-1}{v}_k-x_{*})=\underset{=\nabla f(x_{k-1})\in {𝒦}_{k-1}}{\underbrace{H(x_{k-1}-x_{*})}}-{\alpha }_{k-1}H\underset{\in {𝒦}_{k-1}}{\underbrace{v_k}}.$$

   As ${𝒦}_{k-1}=span[H^1(x_0-x_{*}),\mathrm{\dots },H^k(x_0-x_{*})]$ by the induction hypothesis, we therefore have

   $$\nabla f(x_k)\in span[H^1(x_0-x_{*}),\mathrm{\dots },H^{k+1}(x_0-x_{*})].$$

   Since $\nabla f(x_0),\mathrm{\dots },\nabla f(x_{k-1})\in {𝒦}_{k-1}$ they are by the induction hypothesis also in the span

   $${𝒦}_k=span[\nabla f(x_0),\mathrm{\dots },\nabla f(x_k)]\subseteq span[H^1(x_0-x_{*}),\mathrm{\dots },H^{k+1}(x_0-x_{*})].$$

   Since the space on the left is $k+1$ dimensional, we have equality. ∎

5. Argue that $\nabla f(x_{k+1})$ is orthogonal to every vector in ${𝒦}_k$ and inductively deduce either

   $$\nabla f(x_{k+1})=0$$

   which implies $x_{k+1}=x_{*}$, or ${𝒦}_{k+1}$ has full rank. Deduce from the $H$-Krylov-subspace property, that $\nabla f(x_{k+1})$ is already $H$-orthogonal to ${𝒦}_{k-1}$.

   Hint.

   $x_{k+1}={argmin}_x\{f(x):x\in {𝒦}_k+x_0\}$.

   Solution.

   By the selection process of $x_{k+1}$, we have

   $$x_{k+1}=\underset{x}{argmin}\{f(x):x\in {𝒦}_k+x_0\}.$$

   assume $\nabla f(x_{k+1})$ were not orthogonal to ${𝒦}_k$. Then there would exist $v\in {𝒦}_k$ such that

   $$⟨\nabla f(x_{k+1}),v⟩>0$$

   By the Taylor approximation we therefore have

   $$f(x_{k+1}-\delta v)=f(x_{k+1})-\delta \underset{>0}{\underbrace{⟨\nabla f(x_{k+1}),v⟩}}+O({\delta }^2)$$

   so there exists a small $\delta >0$ such that . But this is a contradiction since $x_{k+1}$ was optimal.

   $\nabla f(x_{k+1})$ is therefore orthogonal to ${𝒦}_k$. So if it is not zero, ${𝒦}_{k+1}$ has (as the span of both) full rank. $\nabla f(x_{k+1})$ being orthogonal to ${𝒦}_k$ also implies it is orthogonal to $H{𝒦}_{k-1}$, since that is a subspace of ${𝒦}_k$ by the Krylov property. But this implies $\nabla f(x_{k+1})$ is $H$-orthogonal to ${𝒦}_{k-1}$. ∎

6. Collect the ideas we have gathered to prove the recursively defined

   $$v_{k+1}=\nabla f(x_k)-\frac{{⟨\nabla f(x_k),v_k⟩}_H}{{\parallel v_k\parallel }_H^2}{v}_k$$

   are $H$-conjugate and have the same span as the gradients up to $\nabla f(x_k)$.

   Solution.

   These $v_k$ are the same $v_k$ we would obtain using Gram-Schmidt on the gradients. In fact this is Gram-Schmidt together with the fact that $\nabla f(x_k)$ is already $H$-orthogonal to the $v_1,\mathrm{\dots },v_{k-1}\in {𝒦}_{k-2}$. So only the last summand remains. ∎

7. To make our procedure truly computable, we want to show

   $$\frac{{⟨\nabla f(x_k),v_k⟩}_H}{{\parallel v_k\parallel }_H^2}=-\frac{{\parallel \nabla f(x_k)\parallel }^2}{{\parallel \nabla f(x_{k-1})\parallel }^2}.$$

   Hint.

   Proving

   $$\nabla f(x_k)=\nabla f(x_{k-1})-{\alpha }_{k-1}H{v}_k$$

   should allow you to conclude ${\mathrm{⟨}\mathrm{\nabla }\mathit{}f\mathit{}\mathrm{(}{x}_k\mathrm{)}\mathrm{,}{v}_k\mathrm{⟩}}_h\mathrm{=}\mathrm{-}\frac{{\mathrm{\parallel }\mathrm{\nabla }\mathit{}f\mathit{}\mathrm{(}{x}_k\mathrm{)}\mathrm{\parallel }}^{\mathrm{2}}}{{\alpha }_{k\mathrm{-}\mathrm{1}}}\mathrm{.}$ Then it makes sense to calculate

   $${\alpha }_{k-1}=-\frac{⟨\nabla f(x_{k-1}),v_k⟩}{{\parallel v_k\parallel }_H^2}$$

   by solving its optimization problem. Finally you may want to consider $v_k\mathrm{=}\mathrm{\nabla }\mathit{}f\mathit{}\mathrm{(}{x}_{k\mathrm{-}\mathrm{1}}\mathrm{)}\mathrm{-}c\mathit{}{v}_{k\mathrm{-}\mathrm{1}}$ and $v_{k\mathrm{-}\mathrm{1}}\mathrm{\in }{𝒦}_{k\mathrm{-}\mathrm{2}}$.

   Solution.

   We have

   $$\nabla f(x_k)=H(\stackrel{x_k}{\overbrace{x_{k-1}-{\alpha }_{k-1}{v}_k}}-x_{*})=\nabla f(x_{k-1})-{\alpha }_{k-1}H{v}_k.$$

   This implies $v_k=\frac{1}{{\alpha }_{k-1}}{H}^{-1}[\nabla f(x_{k-1})-\nabla f(x_k)]$ and therefore

   $${⟨\nabla f(x_k),v_k⟩}_H=\frac{1}{{\alpha }_{k-1}}⟨\nabla f(x_k),[\nabla f(x_{k-1})-\nabla f(x_k)]⟩=-\frac{{\parallel \nabla f(x_k)\parallel }^2}{{\alpha }_{k-1}},$$

   where we have used $⟨\nabla f(x_k),\nabla f(x_{k-1})⟩=0$, which follows from $\nabla f(x_{k-1})\in {𝒦}_{k-1}$ and $\nabla f(x_k)⟂{𝒦}_{k-1}$.

   Now we need to find ${\alpha }_{k-1}$. But the first order condition

   $0$= d dα f(x_k-1 - αv_k)

   $=-⟨\nabla f(x_{k-1}-\alpha v_k),v_k⟩$

   $=-⟨H(x_{k-1}-x_{*}-\alpha v_k),v_k⟩$

   $=-⟨\nabla f(x_{k-1}),v_k⟩+\alpha {\parallel v_k\parallel }_H^2.$

   implies

   $${\alpha }_{k-1}=\frac{⟨\nabla f(x_{k-1}),v_k⟩}{{\parallel v_k\parallel }_H^2}.$$

   Before we put things together, note that by definition of $v_k$

   $$⟨\nabla f(x_{k-1}),v_k⟩=⟨\nabla f(x_{k-1}),\nabla f(x_{k-1})-c{v}_{k-1}⟩={\parallel \nabla f(x_{k-1})\parallel }^2,$$

   since $\nabla f(x_{k-1})$ is orthogonal to $v_{k-1}\in {𝒦}_{k-2}$. From this we get

   $${\alpha }_{k-1}=\frac{{\parallel \nabla f(x_{k-1})\parallel }^2}{{\parallel v_k\parallel }_H^2},$$

   So we finally get

   $$\frac{{⟨\nabla f(x_k),v_k⟩}_H}{{\parallel v_k\parallel }_H^2}=-\frac{{\parallel \nabla f(x_k)\parallel }^2}{{\parallel v_k\parallel }_H^2}\frac{{\parallel v_k\parallel }_H^2}{{\parallel \nabla f(x_{k-1})\parallel }^2}=-\frac{{\parallel \nabla f(x_k)\parallel }^2}{{\parallel \nabla f(x_{k-1})\parallel }^2}.\mathit{∎}$$

8. Summarize everything into a pseudo-algorithm for conjugate gradient descent (CGD) and compare it to heavy-ball momentum with

   $${\beta }_k=\frac{{\alpha }_k{\parallel \nabla f(x_k)\parallel }^2}{{\alpha }_{k-1}{\parallel \nabla f(x_{k-1})\parallel }^2}$$

   using identical ${\alpha }_k$ as CGD.

   Solution.

   We set $v_1=\nabla f(x_0)$ or later

   $$v_{k+1}=\nabla f(x_k)+\frac{{\parallel \nabla f(x_k)\parallel }^2}{{\parallel \nabla f(x_{k-1})\parallel }^2}{v}_k$$

   determine the step-size

   $${\alpha }_k=\underset{\alpha }{argmin}f(x_k-\alpha v_{k+1})$$

   and finally make our step

   $$x_{k+1}=x_k-{\alpha }_k{v}_{k+1}.$$

   Using the fact $v_k=\frac{x_{k-1}-x_k}{{\alpha }_{k-1}}$ and inserting $v_{k+1}$ into the last equation, we notice

   $x_{k+1}$ $=x_k-{\alpha }_k\left[\nabla f(x_k)+{\displaystyle \frac{{\parallel \nabla f(x_k)\parallel }^2}{{\parallel \nabla f(x_{k-1})\parallel }^2}}{\displaystyle \frac{x_{k-1}-x_k}{{\alpha }_{k-1}}}\right]$

   $=x_k-{\alpha }_k\nabla f(x_k)+\underset{={\beta }_k}{\underbrace{{\displaystyle \frac{{\alpha }_k}{{\alpha }_{k-1}}}{\displaystyle \frac{{\parallel \nabla f(x_k)\parallel }^2}{{\parallel \nabla f(x_{k-1})\parallel }^2}}}}(x_k-x_{k-1})$

   that CGD is identical to HBM with certain parameters ${\alpha }_k$, ${\beta }_k$. ∎

   Exercise 3 (Momentum).

   In this exercise, we take a closer look at heavy-ball momentum

   $$x_{k+1}=x_k+{\beta }_k(x_k-x_{k-1})+{\alpha }_k\nabla f(x_k)$$

   1. Find a continuous function $f:ℝ\to ℝ$ such that

      Prove that $f$ is $\mu$-strongly convex with $\mu =1$, $L$-smooth with $L=25$ and has a minimum in zero.

      Solution.

      We define

      note that it is continuous in $1$ and $2$ and therefore everywhere, and that it has the correct derivative. Further note that

      is the derivative of $f^{\prime }(x)$ in the following sense:

      $$f^{\prime }(x)={\int }_0^x{f}^{\prime \prime }(t)𝑑t,$$

      which follows from differentiability of $f^{\prime }$ on its segments with the fundamental theorem of calculus and continuity between segments. Thus we have

      $f(y)$ $=f(x)+{\displaystyle {\int }_x^y}{f}^{\prime }(t)𝑑t=f(x)+f^{\prime }(x)(y-x)+{\displaystyle {\int }_x^y}{f}^{\prime }(t)-f^{\prime }(x)dt$

      $=f(x)+f^{\prime }(x)(y-x)+{\displaystyle {\int }_x^y}{\displaystyle {\int }_x^t}{f}^{\prime \prime }(s)𝑑s𝑑t.$

      For the Bregman divergence this implies

      $$\frac{1}{2}{\parallel y-x\parallel }^2\le D_f^{(B)}(y,x)={\int }_x^y{\int }_x^t{f}^{\prime \prime }(s)𝑑s𝑑t\le \frac{25}{2}{\parallel y-x\parallel }^2,$$

      thus $f$ is $\mu =1$-strongly convex and $L=25$-smooth. ∎

   2. Recall, we required for convergence of HBM

      $$1>\beta \ge \max \{{(1-\sqrt{\alpha \mu })}^2,{(1-\sqrt{\alpha L})}^2\}.$$

      Calculate the optimal $\alpha$ and $\beta$ to minimize the rate $\sqrt{\beta }$.

      Solution.

      To minimize $\sqrt{\beta }$, we first set

      $$\beta =\max \{{(1-\sqrt{\alpha \mu })}^2,{(1-\sqrt{\alpha L})}^2\}$$

      and then proceed to minimize this over $\alpha$. Which results in

      ${\alpha }^{*}$ $=\underset{\alpha }{argmin}\max \{{(1-\sqrt{\alpha \mu })}^2,{(1-\sqrt{\alpha L})}^2\}$

      $=\underset{\alpha }{argmin}\max \{|1-\sqrt{\alpha \mu }|,|1-\sqrt{\alpha L}|\}$

      $=\underset{\alpha }{argmin}\max \{(1-\sqrt{\alpha \mu }),-(1-\sqrt{\alpha \mu }),(1-\sqrt{\alpha L}),-(1-\sqrt{\alpha L})\}$

      $=\underset{\alpha }{argmin}\max \{(1-\sqrt{\alpha \mu }),-(1-\sqrt{\alpha L})\}$

      which is monotonously falling for

      $$1-\sqrt{\alpha \mu }>\sqrt{\alpha L}-1$$

      and monotonously increasing otherwise. Therefore its minimum is at equality. Thus

      $$1-\sqrt{{\alpha }^{*}\mu }=\sqrt{{\alpha }^{*}L}-1\iff 2=\sqrt{{\alpha }^{*}}(\sqrt{\mu }+\sqrt{L})\iff {\alpha }^{*}=\frac{4}{{(\sqrt{\mu }+\sqrt{L})}^2}.$$

      This results in

      $${\beta }^{*}={\left(1-\frac{2}{1+\sqrt{L/\mu }}\right)}^2.\mathit{∎}$$

   3. Prove, using heavy ball momentum on $f$ with the optimal parameters results in the recursion

      $$x_{k+1}=\frac{13}{9}{x}_k-\frac{4}{9}{x}_{k-1}-\frac{1}{9}\nabla f(x_k).$$

      Solution.

      Using our previous results about optimal rates we have for $f$

      $${\alpha }^{*}=\frac{4}{{(1+5)}^2}=\frac{1}{9}\mathit{\hspace{1em}\hspace{1em}}{\beta }^{*}={(1-\frac{2}{1+5})}^2=\frac{4}{9}.$$

      Thus

      $$x_{k+1}=\underset{=\frac{13}{9}{x}_k-\frac{4}{9}{x}_{k-1}}{\underbrace{x_k+\frac{4}{9}(x_k-x_{k-1})}}+\frac{1}{9}\nabla f(x_k).$$

      ∎

   4. We want to find a cycle of points $p\to q\to r\to p$, such that for $x_0=p$ we have

      $$x_{3k}=p\mathit{\hspace{1em}}{x}_{3k+1}=q\mathit{\hspace{1em}}{x}_{3k+2}=r\mathit{\hspace{1em}\hspace{1em}}\forall k\in {\mathbb{N}}_0.$$

      Assume , and $r>2$ and use the heavy-ball recursion to create linear equations for $p,q,r$. Solve this linear equation. What does this mean for convergence?

      Solution.

      We have

      Multiplying both sides by $9$, using $\nabla f(r)=25r-24$ and $\nabla f(p)=25p$ and similarly $q$ and reordering, we get

      solving this system of equations results in

      $$p=\frac{792}{1225}\approx 0.65,q=-\frac{2208}{1225}\approx -1.80,r=\frac{2592}{1225}\approx 2.12.$$

      As we have managed to find a cycle of points, HBM does not converge to the minimum at zero in this case. Note: it is also possible to show that this cycle is attractive if you start in an epsilon environment away from these points. ∎

   5. Implement Heavy-Ball momentum, Nesterov’s momentum and CGD https://classroom.github.com/a/f3PnRxTs.