\documentclass[11pt]{article}
\usepackage[T1]{fontenc}
\usepackage{amsmath}
\usepackage{amsxtra}
\usepackage{amsfonts}
\usepackage{enumerate}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{enumerate}
\usepackage{graphicx}
\usepackage{url}
\usepackage{color,hyperref}
\hypersetup{colorlinks,breaklinks,
             linkcolor=blue,urlcolor=blue,
           anchorcolor=blue,citecolor=blue}

\usepackage[margin=3cm]{geometry}

\usepackage{preamble}

\begin{document}

\section*{Math 5467 -- Final Exam (Due Wednesday May 11 by Midnight)}
\thispagestyle{empty}

\subsection*{Instructions:}

\begin{itemize}
\item  Complete the problems below, and submit your solutions by uploading them to the Google form \url{https://forms.gle/4t18ZzSMSqDhVt8E7}. 
\item You must submit your exam by Wednesday May 11 @ midnight Central time zone. 
  \item LaTeX is preferred, but you may also scan and upload legible handwritten solutions (with a good scanning app).
\end{itemize}


\subsection*{Problems:}

\begin{enumerate}
\item Let $a$ be a real number, with $|a|\neq 1$, and define $f\in \lz$ by $f(k)=a^k$. Show that
\[\D f(\ell) = \frac{a^n - 1}{ae^{-2\pi i \ell/n} - 1}.\]
Hint: Write the sum defining the DFT $\D f(\ell)$ as a geometric series and use the formula
\[\sum_{k=0}^{n-1} r^k = \frac{r^n - 1}{r-1}.\]
\item 
Assume $f$ is convex, and let $x(t)$ satisfy the gradient descent ODE
\[ x'(t) = -\nabla f(x(t))\]
with $x(0)=x_0$. Show that
\[f(x(t)) - f(x_*) \leq \frac{\|x_0-x_*\|^2}{2t}\]
where $x_*\in \R^n$ is any minimizer of $f$. Hint: Define the energy
\[e(t) = t(f(x(t)) - f(x_*)) + \frac{1}{2}\|x(t) - x_*\|^2\]
and show that $e'(t)\leq 0$ so that $e(t)\leq e(0)$. You will find the inequality below useful, which holds for convex functions $f$:
\begin{equation}\label{eq:convex_f}
f(x(t)) - f(x_*) \leq \nabla f(x(t))^T (x(t)-x_*).\qedhere
\end{equation}
\item Consider the version of Nesterov's accelerated gradient descent in the form
\begin{equation}\label{eq:nagd_alt_form}
\left\{
\begin{aligned}
y_{k+1} &= x_k - \alpha \nabla f(x_k)\\
x_{k+1} &= y_{k+1} + \frac{k-2}{k+1}(y_{k+1}-y_k).
\end{aligned}\right.
\end{equation}
\begin{enumerate}[(i)]
\item  Show that Nesterov's accelerated gradient descent given in \eqref{eq:nagd_alt_form}  satisfies
\[\frac{x_{k+1} - 2x_k + x_{k-1}}{\alpha} + a_k\frac{x_k - x_{k-1}}{ \sqrt{\alpha}} = -\nabla f(x_k) +  \frac{k-2}{k+1} (\nabla f(x_{k-1}) - \nabla f(x_k)),\]
where $a_k = \frac{3}{ \sqrt{\alpha}(k+1)}$.
\item Assume $x_k=x( \sqrt{\alpha}k)$ is the discretization of a smooth curve $x(t)$ for $t\geq 0$.  Explain why it follows from part (i) that when we send $\alpha\to 0$ we obtain that $x$ solves the ordinary differential equation (ODE)
\begin{equation}\label{eq:cont_time_nesterov}
x''(t) + \frac{3}{t}x'(t) = -\nabla f(x(t)).
\end{equation}
This ODE is sometimes called \emph{continuous time Nesterov}. From the continuum point of view, we can see that Nesterov's method is simlar to the heavy ball method with time-dependent friction $a(t)=\frac{3}{t}$. The friction starts off very large, but vanishes as $t\to \infty$, which allows for accelerated convergence for non-strongly convex functions that may be extremely flat near their minima.
\item Assume $f$ is convex and let $x(t)$ satisfy \eqref{eq:cont_time_nesterov} with $x(0)=x_0$ and $x'(0)=0$. Show that
\[f(x(t)) - f(x_*) \leq \frac{2\|x_0-x_*\|^2}{t^2},\]
where $x_*\in \R^n$ is any minimizer of $f$. Hint: Define the energy functional
\[e(t) = t^2(f(x(t)) - f(x_*)) + 2\left\|x(t) + \frac{t}{2}x'(t) - x_*\right\|^2.\]
Then show that
\[e'(t) = 2t(f(x(t)) - f(x_*)) + t^2 \nabla f(x(t))^Tx'(t) + 2t\left(x(t) + \frac{t}{2}x'(t) - x_*\right)^T\left(x''(t) + \frac{3}{t}x'(t)\right).\]
Apply the inequality \eqref{eq:convex_f} to the first term, and use the Nesterov ODE \eqref{eq:cont_time_nesterov} in the last term. After simplifying you should get that $e'(t)\leq 0$ for all $t\geq 0$, so that $e(t)\leq e(0)$, from which the result follows. 
\end{enumerate}
\end{enumerate}
\end{document}

