Sheet 2

Exercise 1 (Descent Directions of a Maximum).

Let $x_{\mathrm{*}}\mathrm{\in }{ℝ}^d$ be a strict local maximum of $f\mathrm{:}{ℝ}^d\mathrm{\to }ℝ$. Prove that every $d\mathrm{\in }{ℝ}^d$ is a descent direction of $f$ in $x_{\mathrm{*}}$.

Solution.

Let $ϵ>0$ be such, that $x_{*}$ is a strict maximum in $B_{ϵ}(x_{*})\setminus \{x_{*}\}$, where existence of such an $ϵ$ is the strict local maximum property. We now have for any direction $d$ that it is a descent direction, because with $\overline{\alpha }=\frac{ϵ}{\parallel d\parallel }>0$ we have for all $\alpha \in (0,\overline{\alpha }]$

since $x_{*}+\alpha d\in B_{ϵ}(x_{*})\setminus \{x_{*}\}$ as $\parallel \alpha d\parallel \le \overline{\alpha }\parallel d\parallel =ϵ$. ∎

Exercise 2 (Convergence to Stationary Point).

Let $f\mathrm{:}{ℝ}^d\mathrm{\to }ℝ$ be a continuously differentiable function.

1. Let ${(x_k)}_{k\in \mathbb{N}}$ be defined by gradient descent

   $$x_{k+1}=x_k-{\alpha }_k\nabla f(x_k),x_0\in {ℝ}^d$$

   with diminishing step size ${\alpha }_k>0$ such that ${\sum }_{k=1}^{\mathrm{\infty }}{\alpha }_k=\mathrm{\infty }$. Suppose that ${(x_k)}_{k\in \mathbb{N}}$ converges to some $x_{*}\in {ℝ}^d$. Prove that $x_{*}$ is a stationary point of $f$ , i.e. $\nabla f(x_{*})=0$.

   Hint.

   You might want to prove for large enough $i\mathrm{,}j$

   $$⟨\nabla f(x_i),\nabla f(x_j)⟩\ge \parallel \nabla f(x_{*}){\parallel }^2-2ϵ\parallel \nabla f(x_{*})\parallel -{ϵ}^2=:p(ϵ).$$

   Solution.

   For any $ϵ>0$ there exists $n\ge 0$ such that for all $i,j\ge n$ we have by Cauchy-Schwarz and convergence of $\nabla f(x_i)$ to $\nabla f(x_{*})$ due to continuity of $\nabla f$

   $⟨\nabla f(x_i),\nabla f(x_j)⟩$

   $={\parallel \nabla f(x_{*})\parallel }^2+⟨\nabla f(x_i)-\nabla f(x_{*}),\nabla f(x_{*})⟩+⟨\nabla f(x_i),\nabla f(x_j)-\nabla f(x_{*})⟩$

   ≥∥∇f(x_*)∥^2 - ⏟ ∥∇f(x_i) - ∇f(x_*)∥ _≤ϵ ∥∇f(x_*)∥ - ⏟ ∥∇f(x_i)∥ _≤∥∇f(x_*)∥ + ϵ ⏟ ∥∇f(x_j)-∇f(x_*)∥ _≤ϵ

   $\ge \parallel \nabla f(x_{*}){\parallel }^2-2ϵ\parallel \nabla f(x_{*})\parallel -{ϵ}^2=:p(ϵ)$

   This results in

   ${\parallel x_n-x_m\parallel }^2$ $={\parallel {\displaystyle \sum _{k=n}^{m-1}}{\alpha }_k\nabla f(x_k)\parallel }^2={\displaystyle \sum _{i,j=n}^{m-1}}{\alpha }_i{\alpha }_j⟨\nabla f(x_i),\nabla f(x_j)⟩$

   $\ge {\left({\displaystyle \sum _{k=n}^{m-1}}{\alpha }_k\right)}^{2}p(ϵ)$

   Taking the limit over $m$ results in

   $$\mathrm{\infty }>{\parallel x_n-x_{*}\parallel }^2\ge \underset{=\mathrm{\infty }}{\underbrace{{\left(\sum _{k=n}^{\mathrm{\infty }}{\alpha }_k\right)}^2}}p(ϵ).$$

   So we necessarily need $p(ϵ)\le 0$. But as $ϵ$ was arbitrary, we have

   $$0\le {\parallel \nabla f(x_{*})\parallel }^2=\underset{ϵ\to 0}{lim}p(ϵ)\le 0.\mathit{∎}$$

2. Assume that $f$ is also $L$-smooth. Prove for $x_n$ generated by gradient descent with constant step size $\alpha \in (0,\frac{2}{L})$ we have

   $$\sum _{k=n}^m{\parallel \nabla f(x_k)\parallel }^2\le \frac{f(x_n)-f(x_m)}{\alpha (1-\frac{L}{2}\alpha )}\le \frac{f(x_n)-{\min }_{x}f(x)}{\alpha (1-\frac{L}{2}\alpha )}$$

   for any $n,m\in \mathbb{N}$. Deduce for the case ${\min }_{x}f(x)>-\mathrm{\infty }$, that we have

   $$\underset{k\le n}{\min }{\parallel \nabla f(x_k)\parallel }^2\in o(1/n).$$

   Hint.

   Consider the minimizer from Sheet 1, Ex. 6(i).

   Solution.

   By $L$-smoothness of $f$, we have

   $f(x_{k+1})$ $\le f(x_k)+⟨\nabla f(x_k),\stackrel{-\alpha \nabla f(x_k)}{\overbrace{x_{k+1}-x_k}}⟩+\frac{L}{2}{\parallel x_{k+1}-x_k\parallel }^2$

   $=f(x_k)-(\alpha -\frac{L}{2}{\alpha }^2){\parallel \nabla f(x_k)\parallel }^2$

   and therefore

   $$\sum _{k=n}^m{\parallel \nabla f(x_k)\parallel }^2\le \sum _{k=n}^m\frac{f(x_k)-f(x_{k+1})}{\alpha (1-\frac{L}{2}\alpha )}\stackrel{\text{telescope}}{=}\frac{f(x_n)-f(x_m)}{\alpha (1-\frac{L}{2}\alpha )}.$$

   Now $a_n:={\min }_{k\le n}{\parallel \nabla f(x_k)\parallel }^2$ is non-increasing, therefore

   $$n{a}_{2n}\le \sum _{k=n}^{2n}{a}_k\le \sum _{k=n}^{\mathrm{\infty }}{a}_k\to 0\mathit{\hspace{1em}}(n\to \mathrm{\infty }).$$

   Thus $a_{2n}\in o(1/n)$. And we can simply bound the odd elements of the sequence

   $$a_{2n+1}\le a_{2n}\in o(1/n).\mathit{∎}$$

   Exercise 3 (Optimizing Quadratic Functions).

   In this exercise we consider functions of type

   $$f(x)=x^{T}Ax+b^{T}x+c,$$

   where $x\mathrm{\in }{ℝ}^d\mathrm{,}A\mathrm{\in }{ℝ}^{d\mathrm{\times }d}\mathrm{,}b\mathrm{\in }{ℝ}^d\mathrm{,}c\mathrm{\in }ℝ$.

   1. Let $H:=A^T+A$ be invertible. Prove that $f$ can be written in the forms

      $f(x)$ $={(x-x_{\ast })}^{T}A(x-x_{\ast })+\tilde{c}$ (1)

      $=\frac{1}{2}{(x-x_{\ast })}^T\underset{=:H}{\underbrace{(A^T+A)}}(x-x_{\ast })+\tilde{c}$ (2)

      for some $x_{\ast }\in {ℝ}^d$ and $\tilde{c}\in ℝ$. Argue that $H$ is always symmetric. Under which circumstances is $x_{\ast }$ a minimum?

      Solution.

      We want for some $x_{\ast }$

      $$f(x)\stackrel{!}{=}{(x-x_{\ast })}^{T}A(x-x_{\ast })+\tilde{c}=x^{T}Ax\underset{=-x_{\ast }^T(A+A^T)x\stackrel{!}{=}{b}^{T}x}{\underbrace{-x^{T}A{x}_{\ast }-x_{\ast }^{T}Ax}}+\underset{\stackrel{!}{=}c}{\underbrace{x_{\ast }^{T}A{x}_{\ast }+\tilde{c}}}$$

      So we simply select

      $$x_{\ast }:=-{(A+A^T)}^{-1}b\mathit{\hspace{1em}}\text{and}\mathit{\hspace{1em}}\tilde{c}:=c-x_{\ast }^{T}A{x}_{\ast }.$$

      This proves our first representation (1). For (2) we simply note

      $$y^{T}Ay=⟨y,Ay⟩\stackrel{\text{symm.}}{=}⟨Ay,y⟩=y^T{A}^{T}y.$$

      Applying this to $y=x-x_{\ast }$ in (1) we are done.

      Symmetry of $H$ follows directly from its definition as $H_{ij}=A_{ji}+A_{ij}=H_{ji}$.

      Now $x_{\ast }$ is a minimum iff $H$ is positive definite. If it is positive definite, then $x_{\ast }$ is a minimum by ${\nabla }^{2}f(x)=H$ and the lecture. If $H$ is not positive definite, we need to show that there exists some $x$ such that $f(x)\le m$ for all $m\le \tilde{c}$. Since $H$ is not positive definite, there exists some $y$ such that

      define $x=x_{\ast }+y\sqrt{\frac{\tilde{c}-m}{\epsilon }}$. Then

      $$f(x)=\frac{\tilde{c}-m}{\epsilon }{y}^{T}Hy+\tilde{c}=m.\mathit{∎}$$

   2. Argue that the Newton Method (with step size ${\alpha }_n=1$) applied to $f$ would jump to $x_{\ast }$ in one step and then stop moving.

      Solution.

      Taking the derivative of (2) we get

      $$\nabla f(x)=H(x-x_{\ast }).$$ (3)

      So with ${\nabla }^{2}f(x)=H$ and

      $$x_{\ast }=x-H^{-1}H(x-x_{\ast })=x-{[{\nabla }^{2}f(x)]}^{-1}\nabla f(x),$$

      we have that the Newton Method finds $x_{\ast }$ in one step. By (3) we also get $\nabla f(x_{\ast })=0$ which stops the Newton method afterwards. ∎

   3. Let $V=(v_1,\mathrm{\dots },v_d)$ be an orthonormal basis such that

      $$H=Vdiag[{\lambda }_1,\mathrm{\dots },{\lambda }_d]V^T$$

      with and write

      $$y^{(i)}:=⟨y,v_i⟩.$$

      Express ${(x_n-x_{\ast })}^{(i)}$ in terms of ${(x_0-x_{\ast })}^{(i)}$, where $x_n$ is given by the gradient descent recursion

      $$x_{n+1}=x_n-h\nabla f(x_n).$$

      For which step size $h$ do all the components ${(x_n-x_{\ast })}^{(i)}$ converge to zero? Which component has the slowest convergence speed? Find the optimal learning rate $h^{*}$ and deduce for this learning rate

      $$\parallel x_n-x_{\ast }\parallel \le {(1-\frac{2}{1+\kappa })}^n\parallel x_0-x_{\ast }\parallel .$$

      with the condition number $\kappa =\frac{{\lambda }_d}{{\lambda }_1}$.

      Solution.

      Using the representation (3) of the gradient again and subtracting $x_{\ast }$ from our recursion, we get

      $$x_{n+1}-x_{\ast }=x_n-x_{\ast }-hH(x_n-x_{\ast })=[𝕀-hH](x_n-x_{\ast })$$

      Therefore