\section{Background}
A ubiquitous goal in many areas of study, application, and daily life is to find the best outcome, to optimize whatever situation is given to us. In a mathematical sense, this often resolves to minimizing an object (perhaps subject to constraints). That is, one may wish to solve the following general problem: 
\begin{prob}{General Model For Optimization}{}
    Given function $f \colon \R^n \to \R$ and constraint set $S \subseteq \R^n$, one wishes to solve the following: \begin{equation}\label{eq:General Opti Problem}
       p_\star = \inf_{x \in S} f(x) 
    \end{equation}
\end{prob}
In general, the minimum may not exists (i.e., $f(x) = e^{-x}$), which is why we use the \textit{infimum}, or the largest \textit{lower bound}. Note that $0 = \inf_{x \in \R} e^{-x}$, but there is no such $x$ attaining this value. If some point does attain the minimum, we call it a \textit{minimizer}. 
\begin{definition}{Global and Local Minimizers}{}
We say $x^\star$ is a global minimizer if \begin{equation*}
    f(x^\star) \leq f(x), \quad \forall x \in S \ .
\end{equation*}
      \tcblower
      \textit{If $x^\star$ is only a minimizer \textbf{nearby}, we say $x^\star$ is a local minimizer. That is, for some $r > 0$,} \begin{equation*}
          f(x^\star) \leq f(x), \quad \forall x \in S \cap \{x : \|x-x^\star\| \leq r\} \ .
      \end{equation*}
\end{definition}
However, even when a (local) minimizer exists, finding the solution $x^\star \in \argmin_{x \in S} f(x)$ often proves difficult. Instead, we often attempt to get \textit{close} to optimal using an \textbf{iterative method} (an algorithm). Such methods are defined in their full generality below, but the basic idea is we utilize an \textit{oracle} $\mathscr{O}$ to gather information about a point (i.e., evaluation of a function, its gradient, its hessian, if the point is included in a set, etc.). The information is then saved into an \textit{informational set}. The algorithm's rules $\mathscr{M}$ dictate how to generate the next point, and a stop criterion $\mathscr{S}_\eps$, based on the target accuracy, decides whether the loop repeats or returns (a possibly newly generated point) $\bar{x}$.
\begin{algo}[label={def:iterative-method}]{General Iterative Method (modified from~\cite[(1.1.3)]{nesterov_lectures})}{}
   {\normalfont \textbf{Input}: Starting point $x^0$ and target accuracy $\eps > 0$.}\\
    {\normalfont \textbf{Initialize}: $k = 0$, $\mathscr{I}_{-1}=\emptyset$. Here $k$ is the iteration counter and $\mathscr{I}_k$ is the \textit{informational set}.}
   \tcblower
   \begin{center}
       \textbf{Main Loop:}
   \end{center}
   \vspace{-0.7cm}
   \begin{enumerate}
       \item Call oracle $\mathscr{O}$ at point $x^k$.
       \item Update informational set $\mathscr{I}_{k} = \mathscr{I}_{k-1} \cup (x^k,\mathscr{O}(x^k)) $
       \item Apply rules $\mathscr{M}$ at $x^k$ to generate $x^{k+1}$
       \item Check stopping criterion $\mathscr{S}_\eps$. If \textbf{yes}, output $\bar{x}$. Otherwise $k \gets k+1$ and go to step 1.
   \end{enumerate}
\end{algo}
While there are many ways to measure ``close to optimal'', a common and perhaps natural concept is to look at function value.
\begin{definition}[label={def:optimality}]{Nearly Optimal (suboptimality gap)}{}
    Suppose $\bar{x} \in S$ is the output of some \textbf{iterative method}. Suppose $x^\star$ solve \labelcref{eq:General Opti Problem}. We say $\bar{x}$ is an \textit{$\eps$-optimal} solution if \begin{equation}
        f(\bar{x})-f(x^\star) \leq \eps \ .
    \end{equation}
\end{definition}
Of course, in general, we will not know $f(x^\star)$, so this will not act as a good stopping criterion. We will find ways to mitigate this problem, either with new stopping criterion or ones we can check that imply the above. 
\subsection{Preliminary Concepts} 
Before we begin, it is essential to understand the basics of linear algebra and calculus to proceed with gradient descent. Many results extend beyond standard Euclidean space. We really just need the structure of a \textit{Hilbert Space}\footnote{Simply put, a Hilbert Space is one where we can do fundamental calculus and linear algebra. Limits exist and act as we would expect. Distances, angles, orthogonality, linear operators all apply here too.}, but we can consider $\R^n$ for simplicity.
\subsubsection{Linear Algebra Review}
We begin with definition the fundamental place where all the ``stuff'' lives that we want to work with. In general, gradient descent will handle multiple-dimensional items: vectors. To ensure we're all on the same page, we will start from the beginning and define the necessary terms quite quickly. 
  
   In order to do linear algebra, we need numbers. Or at the very least, we need stuff to work with--something that looks familiar (to the real numbers) but is general enough to handle more {\it {complex}} settings. As we'll see, the {\it {linearity}} of {\it {linear}} algebra, needs us to be able to add, scale (multiply by a constant), and distribute the two operations. Thus, we need an ambient space to do these calculations.
 \begin{definition}{Field}{}
       A set $\F$ equipped with two operations $(+,\bcdot)$ is a \textit{field} if
        \begin{enumerate}
            \item Associativity: $\forall \ a,b,c \in \F, \quad \begin{cases}
                a+(b+c)=(a+b)+c\\
                a\bcdot(b\bcdot c)=(a \bcdot b)\bcdot c
            \end{cases}$
            \item Commutativity: $\forall \ a,b \in \F, \quad \begin{cases}
                a+b=b+a\\
                a\bcdot b = b\bcdot a
            \end{cases}$
            \item Identities: $\exists \ 0 \ne 1 \in \F$ such that $\forall x \in \F, \quad \begin{cases}
                x + 0 = 0 + x = x\\
                x \bcdot 1 = 1\bcdot x = x
            \end{cases}$
            \item Inverses: $\begin{cases}
                \forall \ a \in \F, \exists \ (-a) \in \F \  s.t.\ \  a+(-a)=(-a)+a=0\\
                \forall \ 0 \ne b \in \F, \exists \ (b^{-1}) \in \F  \ s.t. \ \ b\bcdot(b^{-1})=(b^{-1})\bcdot b=1\\
            \end{cases}$
            \item Distributivity: $\forall \ a,b,c \in F$, $a\bcdot(b+c)=a\bcdot b+a\bcdot c$ 
        \end{enumerate}
    \end{definition}
 
The above definitions may look a bit gnarly, but simply put, a field is a set with two operations that keep elements in the set. This is called \textit{closure}. These operations then come with the standard properties that real numbers possess (and both rational numbers and complex numbers as they are fields too). They can be undone with inverses, and there are elements that have seemingly no effect, called identities. We will find all these properties are especially useful when considered \textbf{vector spaces}. We begin with extending the concept to \textbf{lists}.

\begin{definition}{List}{}
    For a fixed natural number $n \in \N$, define an {\it n-dimensional list over field} $\F$ to be $$\F^n=\{(x_1,x_2,...,x_n) : x_j \in \F \ \ 1 \leq j \leq 1\}$$
\end{definition}
\begin{remark}{Coordinates}{}
    We call $x_j$ the $j^{th}$-coordinate
\end{remark}

We can then define operations over a list directly from the structure of the field. 
  \begin{definition}{Operations in $\F^n$}{}
        \begin{itemize}
           \item \textbf{Addition}: ($+ : \F^n \times \F^n \to \F^n$) is defined component-wise:\\
        \begin{equation*}
            (x_1,...,x_n)+(y_1,...,y_n) := (x_1+y_1,...,x_n+y_n)
        \end{equation*}
        \item \textbf{Scalar multiplication}: ($\bcdot : \F \times \F^n \to \F^n$) is component wise too:
        $$\underbrace{\lambda}_{\in \F}\bcdot \underbrace{(x_1, ..., x_n)}_{\in \F^n} := (\lambda x_1, ..., \lambda x_n)$$
        \item  \textbf{(additive) Identity}: needs to hold that $0+{\bf x}={\bf x}+0={\bf x}$, so we define
        ${\bf 0}=(0,0, ..., 0)$
        \item  \textbf{(additive) Inverse}: need for ${\bf x}+{\bf -x}={\bf 0}$, so we define
        ${\bf -x}=(-x_1, ..., -x_n)$
        \end{itemize}

    \end{definition}

Very naturally, lists let us handle multiple elements of a field simultaneously. If we consider an objects location at a particular time, we may consider the list $(x,y,z,t)$, where $(x,y,z)$ are the three coordinate positions. If this object moves 2 units to the left and 3 units vertically over the period of 4 seconds, we can add $(-2,0,3,4)$ to its previous value. Lists gives us the precisely analog to be able to handle \textbf{Vector Spaces}. For the most part, these are going to be analogous, but for mathematical maturity, we should understand that \textbf{vector spaces} are the more precise tool we want to utilize. 

   \begin{definition}{Vector Space (over a field)}{}
        A \textbf{Vector Space} over a field $\F$ is a set $V$ along with 
        $\begin{cases}
            + : V \times V \to V\\
            \bcdot : \F \times V \to V 
        \end{cases}$
        such that the following holds
        \begin{enumerate}

            \item $\textbf{u}+\textbf{v}=\textbf{v}+\textbf{u}$ for all $\textbf{u},\textbf{v} \in V$
            \item $(\textbf{u}+\textbf{v})+\textbf{w}=\textbf{u}+(\textbf{v}+\textbf{w})$ for all $\textbf{u},\textbf{v},\textbf{w} \in V$
            \item  There exists $\textbf{0} \in V$ such that $\textbf{0}+\textbf{v}=\textbf{v}+\textbf{0}=\textbf{v}$ for all $\textbf{v} \in V$
            \item For all $\textbf{v} \in V$ there exists a $(-\textbf{v})=\textbf{v}^{-1} \in V$ (\textcolor{red}{simply notational}) such that $\textbf{v}+(-\textbf{v})=(-\textbf{v})+\textbf{v}=0$
            \item $1\textbf{v}=\textbf{v}$ for all $\textbf{v} \in V$ (1 being the multiplicative identity in $\F$)
            \item  $\begin{cases}
                a(\textbf{u}+\textbf{v})=a\textbf{u}+a\textbf{v} & \forall a \in \F, \ \textbf{u},\textbf{v} \in V\\
                (a+b)\textbf{v}=a\textbf{v}+b\textbf{v} & \forall a,b \in \F, \ \textbf{v} \in V
            \end{cases}$
        \end{enumerate}
    \end{definition}    

 \begin{remark}{Notation}{}
        The condition that these functions exist can also be called ``closure under addition (linearity) and closure under scalar multiplication (homogeneity)'' 
        $$ \begin{cases}
            + : V \times V \to V\\
            \bcdot : \F \times V \to V 
        \end{cases}$$
    \begin{itemize}
        \item  Just for ease, we typically can drop the boldness of vectors based on context. Sometimes we put an arrow over, sometimes a bar (I dislike because a bar looks like conjugation). It really just depends on what notation you choose. 
        \item We also drop the $\bcdot$ for scalar multiplication typically.
        \item  Therefore $v={\bf v}=\bar{v}=\vec{v}$
        \item  and $a\bcdot v = av$ going forward.
    \end{itemize}

    \end{remark}

Typically in reviewing linear algebra, one would want to study fundamental aspects like linear independence, span, bases, linear maps, eigenvalues, etc. However, we don't need any of those for standard gradient descent! We really just need to following ways to measure how close two vectors are to each other. That is, we want to measure some form of ``distance'' and ``orthogonality'' (or angle).  
\begin{definition}{Norms}{}
    A \textbf{norm} over a vector space $V$ is a function $\|\cdot\| : V \to \F$ satisfying 
    \begin{itemize}
        \item (nonnegativity): $\|x\| \geq 0$, for all $x \in V$. $\|x\| = 0$ if and only if $x = 0$.
        \item (positive homogeneity): $\|\lambda x \| = |\lambda|\cdot\|x\|$ for any $x \in V$ and $\lambda \in \F$.
        \item (triangle inequality): $\|x+y\| \leq \|x\|+\|y\|$ for all $x,y \in F$.
    \end{itemize}
\end{definition}
The above definition gives us a notion of length of a vector. Since vector spaces have addition operations and suitable inverses, we can ``subtract'' two vectors to produce a new one. Applying the norm to that vector yields a proper distance. \begin{definition}{Distance}{}
    Given $x, y \in V$, the distance between $x$ and $y$, induced by norm $\|\cdot\|$, is defined as $$d_{\|\cdot\|}(x,y) = \|y-x\| \ .$$
\end{definition}
\begin{remark}{Examples of Norms}{}
    The following are all norms in $\R^n$:
    \begin{itemize}
        \item $\|x\|_1 := \sum_{j=1}^n |x_j|$
        \item $\|x\|_2 := \sqrt{(\sum_{j=1}^n x_j^2)}$
        \item $\|x\|_\infty := \max_j |x_j|$
        \item $\|x\|_p := (\sum_{j=1}^n |x_j|^p)^\frac{1}{p}$, \ $p \geq 1$
    \end{itemize}
\end{remark}
The final object we will need from linear algebra is a way of relating two vectors to each other. In a sense, this next tool is all we need, as we can then suitably \textit{induce} a norm. As we'll see, an \textbf{inner product} will be the best tool to associate two (possibly non-distinct) vectors. 
\begin{definition}{Inner Product}{}
    An \textbf{inner product} over a vector space $V$ is a function $\inner{\cdot}{\cdot} : V \times V \to \R$ satisfying
    \begin{enumerate}
        \item (positive definiteness): $\inner{x}{x} \geq 0$ for any $x \in V$. $\inner{x}{x}=0$ if and only if $x = 0$.
        \item (linearity): $\inner{ax + by}{z} = a\inner{x}{z}+b\inner{y}{z}$ for $a, b \in F$ and $x,y,z \in V$.
        \item (quasi-symmetry): $\inner{x}{y} = \overline{\inner{y}{x}}$ for $x,y \in V$
    \end{enumerate}
\end{definition}
The last requirement says that flipping the order in the inner product \textit{conjugates} the value. This is really only notable when the underlying field in complex. We will only consider $\R^n$ going forward, in which the inner product (now just a dot product) is now linear in both components and fully symmetric!
\begin{remark}{Inducing a norm}{}
    Earlier mentioned, the inner product is all we need. In a similar vain to inducing a distance from a norm, one can induce a norm from an inner product: $$\|x\| := \sqrt{\inner{x}{x}}$$
\end{remark}
Given this relationship between inner products and (induced) norms, we can derive an incredibly powerful and useful result that lets us bound the size of an inner product (an ``association'' of two vectors) to the product of their magnitudes.
\begin{prop}[label = {cauchy-schwarz}]{Cauchy Schwarz Inequality}{}
    The inner product and norms of two vectors are related as follows:
    \begin{equation}\label{eq:cauchy-schwarz}
        |\inner{x}{y}| \leq \|x\|\|y\|
    \end{equation}
\end{prop}
\begin{proof}
    We will consider the case where $\F=\R$ and $V=\R^n$. However, the result holds in generality. Consider $x,y  \in \R^n$ and $t \in \R$. Then, \begin{align*}
        0 &\leq \inner{x+ty}{x+ty} \quad &\text{(by positive definiteness)}\\
        &= \|x\|^2+2t\inner{x}{y}+t^2\|y\|^2 \ . \quad &\text{(linearity and definition of the induced norm)}
    \end{align*}
    Note the above is a quadratic in $t$. Here, $x$, $y$, and thus their norms are just fixed scalars. Since the quadratic is facing upwards $(t^2 \geq 0)$ and is nonnegative for all $t$, it must hold that the discriminant (the $b^2-4ac$ part in the square root of the quadratic formula) is \textit{nonpositive}. Therefore: \begin{align*}
        (2\inner{x}{y})^2-4\|x\|^2\|y\|^2 &\leq 0\\
        4(\inner{x}{y})^2 &\leq 4\|x\|^2\|y\|^2 \ .
    \end{align*}
    Dividing by 4 and taking the square root of both sides yields the desired result.
\end{proof}
We can then immediately define the notion of an \textit{angle} between two vectors. The above inequality gives us that $$\frac{|\inner{x}{y}|}{\|x\|\|y\|} \leq 1, \quad \forall x,y \in V \ .$$
In other words, $$-1 \leq \frac{\inner{x}{y}}{\|x\|\|y\|} \leq 1 \ .$$
Therefore, we can define the angle as follows:
\begin{definition}{Angle Between Vectors}{}
    For any $x,y \in V$, define the angle $\theta_{x,y}$ as $$\theta_{x,y} = \cos^{-1}\left(\frac{\inner{x}{y}}{\|x\|\|y\|} \right)\ . $$ 
\end{definition}
We use cosine in the above definition for two reasons. The first is that this result naturally extends from {\color{blue} \href{https://proofwiki.org/wiki/Cosine_Formula_for_Dot_Product}{law of cosines}}. Secondly, we get a natural association for two vectors forming a ``right angle''. When the inner product of two (non-zero) vectors is zero, then the angle between them is precisely $90^o$ (or $\pi/2$ in radians).
Lastly, we introduce the notion of orthogonality. In a sense, this means that two vectors are ``as independent'' as they can get. However, for our application, orthogonality will tie to the idea of \textit{descent}.
\begin{definition}{Orthogonality}{}
    Two vectors $x,y \in V$ are said to be \textbf{orthogonal} if $$\inner{x}{y}=0$$
\end{definition}

\subsubsection{Calculus Review}
With the basic notions of linear algebra out of the way, we can relax ourselves to consider a more familiar setting: $\R^n$. However, I would recommend keeping in mind that almost all of the following will extend to any setting that allows a suitable inner product (even infinite dimensional spaces!). With our restriction to $\R^n$, we will also consider the standard \textit{Euclidean inner product}:
\begin{equation}
    \inner{x}{y} = x_1y_1 + \dots + x_ny_n \ .
\end{equation}
Note that the induced norm is then \begin{equation}
    \|x\| = \sqrt{\inner{x}{x}} = \sqrt{x_1^2 + \dots + x_n^2} \ .
\end{equation}
We can now move onto defining the star of the show. The \textbf{gradient}. Note that the following definition is not entirely useful for us as is. It doesn't quite explain why gradient leads to descent, nor does it imply anything about ``pointing in the steepest direction.'' We will observe the latter two claims more in the following sections, but without further ado:
\begin{definition}{Multidimension Derivatives}{}
The \textbf{partial derivative} of a function $f : \R^n \to \R$, at the point $x = (x_1, \dots, x_n)$ is defined as \begin{equation}\label{eq:partial-derivative}
    \frac{\partial f(x)}{\partial x_j} := \lim_{h \to 0} \frac{f(x_1, \dots, x_j+h, \dots , x_n)-f(x_1, \dots, x_n)}{h} \ .
\end{equation}
If each partial derivative exists for all $j = 1, \dots, n$, the the function is said to be \textbf{differentiable} at $x$. If all the partials exist for all $x \in \R^n$, the function itself is said to be differentiable.
\tcblower
    Given differentiable function $f : \R^n \to \R$, the gradient is itself a function $\nabla f(\cdot) : \R^n \to \R^n$ 
    defined as $$\nabla f(x) = {\displaystyle \begin{bmatrix}
            \vspace{0.1cm}
        \frac{\partial f(x)}{\partial x_1}\\
        \frac{\partial f(x)}{\partial x_2}\\
        \vdots \\
                \vspace{0.1cm}
        \frac{\partial f(x)}{\partial x_n}
    \end{bmatrix}}$$
\end{definition}

Note that the partial derivative above is defined in the following way: how much does the function value change if we move a small amount in the direction of a single coordinate, relative to how much we moved?
In a sense, this is very similar to the standard ``rise over run'' calculation of a slope, but just pointing in a particular direction. This direction is entirely arbitrary, but useful because of how we constructed our function (if you know further linear algebra, this is precisely by focusing on a particular basis element). However, we could have perturbed in any direction, and found the relative change in function value. 
\begin{definition}[label = {directional-derivative}]{Directional Derivative}{}
Given a function $f : \R^n \to \R$ and unit vector  $v \in \R^n$ (that is, $\|v\|=1$), the directional derivative at $x \in \R^n$ is defined as \begin{equation}\label{def:directional-derivate}
    f'(x;v) := \lim_{h \to 0}\frac{f(x+hv)-f(x)}{h}
\end{equation}
    
\end{definition}

While the definition of a gradient might not seem immediately useful, we do get for free a multidimensional Taylor's theorem. In a similar way to constructing the linear model of a one-dimensional function to pass through the function at a point and have the same slope, we can approximate a differentiable function at a point analogously. \begin{definition}{Linear Approximation}{}
    The \textbf{linear approximation} of a differentiable function $f: \R^n \to \R$ at $x \in \R^n$ is $$\ell_{f,x}(y) := f(x)+\inner{\nabla f(x)}{y-x} \ .$$
\end{definition}
Note that $\ell_{f,x}(x)=f(x)$ and $\nabla \ell_{f,x}(x)=\nabla f(x)$. It can further be shown that the error is of order $o(t)$. That is, for small distances away from $x$, the error is shrinking faster than linear.
\begin{prop}[label = {prop:taylor}]{Taylor's Theorem (first order)}{}
    Given differentiable function $f$ and its linear approximation, the error is \textbf{first order}.
    $$f(y) = \ell_{f,x}(y)+o(\|y-x\|)$$
    where $o(h)$ implies that $\lim_{h \to 0^+}o(h)/h = 0$  and $o(0)=0$.
\end{prop}
This proposition leads to a rather nice result about gradients. While the definition of a gradient may seem like a useful tool for collecting all the partial derivatives, the following corollary highlights the relationship between gradients and \textit{directional derivatives}. That is, the gradient is the precise vector that \textbf{represents} the directional derivatives.

\begin{cor}[label =  {cor:gradient-representation}]{Representation of Directional Derivatives}{}
Given differentiable $f : \R^n \to \R$, $x \in \R^n$ and unit vector $v \in \R^n$ the following relationship holds:
    \begin{equation}
        f'(x;v) = \inner{\nabla f(x)}{v}
    \end{equation}
\end{cor}
\begin{proof}
    Simply unpacking definitions, \begin{align*}
        f'(x;v) & = \lim_{h \to 0} \frac{f(x+hv)-f(x)}{h}\\
        &=\lim_{h \to 0} \frac{f(x)+\inner{\nabla f(x)}{(x+hv)-x}+o(\|(x+hv)-x\|)-f(x)}{h}\\
        &= \lim_{h \to 0} \frac{\inner{\nabla f(x)}{hv}+o(\|hv\|)}{h}\\
        &= \lim_{h \to 0} \inner{\nabla f(x)}{v}+\frac{o(h)}{h} = \inner{\nabla f(x)}{v}
    \end{align*}
\end{proof}

We conclude this section with a few more definitions that will be useful for our analysis. First, we define a neighborhood around a point. Often, as a consequence of the calculus involved and (lack of) structure of the function we aim to minimize, conditions are only considered locally. 
\begin{definition}{Ball Neighborhood $B_{\|\cdot\|}(x,r)$}{}
    Given a point $x \in \R^n$, a radius $r \geq 0$ and a norm $\|\cdot\|$, we define the ball around that point:
    $$B_{\|\cdot\|}(x,r) := \{y \in \R^n : \|y-x\| < r\} \ .$$
\end{definition}
When we consider the standard Euclidean norm $\|\cdot\|_2$, we can drop the subscript. We can consider the slightly larger set $\hat{B}_{\|\cdot\|}(x,r) := \{y \in \R^n : \|y-x\| \leq r\}$ as well. Below are visualizations of different normed balls in $\R^2$.
\begin{figure}[h]
    \centering
    \includegraphics[width=0.6\linewidth]{Images/p_norms.png}
    \caption{\href{https://ozanerhansha.medium.com/when-pi-doesnt-equal-3-14-73be75b2b90f}{p-norms in $\R^2$}}
    \label{fig:p_norms}
\end{figure}
Again, we will really only consider the $2$-norm, as the standard inner product induces it, and we will drop the subscript to mean $\|\cdot\| = \|\cdot\|_2$ unless otherwise noted. However, it is worth noting that other settings do utilize different norms.

As we run our iterative method, we will naturally obtain a sequence of values. If we utilize the optimality condition outlined in \labelcref{def:optimality}, it makes sense to look at the sequence $f(x^k)-f(x^\star)$ where $x^k$ is the $k^{th}$ iterate of some method. 
\begin{definition}{Relaxation Sequence}{}
    If a sequence $\{a_k\}_{k=0}^\infty$ satisfies $$a_{k+1} \leq a_k \ ,$$
    we call the sequence a \textbf{relaxation sequence}.
\end{definition}
Note that since $x^\star$ is a minimizer, it should hold that $f(x^k)-f(x^\star) \geq 0$. That is, the sequence $\{f(x^k)-f(x^\star)\}_{k=0}^\infty$ is bounded below. If it is also a relaxation sequence, then the following lemma states the sequence must converge! If zero is the \textit{best lower bound}. That is, if for any $\delta > 0$, there is some $N$ where $f(x^N)-f(x^\star) < \delta$, then $\{f(x^k)-f(x^\star)\}_{k=0}^\infty$ converges to $0$ and the iterative method converges to a minimizer!
\begin{prop}{Monotone Convergence Theorem}{}
    Let $\{a_k\}_{k=0}^\infty$ be a relaxation sequence of real numbers with $\inf_k a_k = 0$ then the sequence converges to zero and we write $$a_k \to 0 \ .$$
\end{prop}
To conclude this section, we must define notions of convergence. We can suppress the rigorous definitions for an real analysis course, but in optimization, it is useful to characterize how quickly a sequence converges. 
\begin{definition}[label = {def:notions-of-cnvergence}]{Notions of Convergence}{}
    Suppose $a_k \to 0$. If there exists constant $0 < \tau < 1$ and $C > 0$ such that $$a_k \leq C\tau^k \ ,$$
    we say $\{a_k\}_{k=0}^\infty$ convergence \textbf{linearly}.
    \tcblower
    If instead there are constants $C > 0$ and $q > 0$ such that $$a_k \leq \frac{C}{k^q} \ ,$$ we say the sequence converges \textbf{sublinearly} with rate $q$.
\end{definition}Some may note that this would imply exponential decay, and it does! However, we say the convergence is linear because $a_{k+1}=\tau a_k$. For sublinear rates, we do not guarantee as good of convergence, but unfortunately, most iterative schemes we see will be sublinear. 

\subsubsection{(Structured) Classes of Functions}
The above tools will allow us to analyze methods like gradient descent, but so far, we have no guarantees that any iterative method will converge. Certain classes of functions behave better than others; gradient descent converges faster given structure. While optimizers aim to find the best solution to the most accurate-to-reality model, we often must sacrifice the precision of the model for the convergence of a solution. Aspects like continuity and differentiability help, but we can do better.
\begin{definition}{Convex Function}{}
    A function $f:\R^n \to \R$ is said to be \textbf{convex} if for any $t \in [0,1]$
    $$f(tx+(1-t)y) \leq tf(x)+(1-t)f(y), \quad \forall x,y \in \R^n \ .$$
\end{definition}
The above can be written slightly differently, one can say equivalently, that $$f(y+t(y-x)) \leq f(y)+t(f(y)-f(x)) \ .$$
That is, if one draws a line segment from $f(y)$ to $f(x)$ it will always upper bound the function evaluated at any point between $y$ and $x$.
\begin{figure}
    \centering
    \includegraphics[width=0.5\linewidth]{Images/Convex_vs._Not-convex.jpg}
    \caption{Convex Functions}
    \label{fig:Convex Function}
\end{figure}
For an interactive 3-D plot of a convex function, click {\color{blue}\href{https://www.desmos.com/3d/cnmbsrrcki}{here}}. 

In general, convex functions are a great place to start. While they need not be differentiable, they must be continuous. Furthermore, minima are unique, and when a local minimizer exists, it must also be a global one. One way to think about convex functions is that they ``curve upwards.'' However, there is a more rigorous characteristic of convex functions.

\begin{prop}[label = {prop:lower-linearization}]{Lower Linearization}{}
    Suppose $f: \R^n \to R$ is convex and differentiable. Then for any $x \in \R^n$, $$f(y) \geq f(x)+\inner{\nabla f(x)}{y-x}, \quad \forall y \in \R^n .$$
\end{prop}

\begin{proof}
    Suppose $f$ is convex. Then, for all $t \in (0,1)$, $tf(y)+(1-t)f(x) \geq f(ty+(1-t)x)$. In other words, $$f(y) \geq \frac{f(x+t(y-x))-f(x)}{t}+f(x) \ .$$
    Letting $t \to 0$ and using \cref{cor:gradient-representation} gives the desired characterization.
\end{proof}
What the above proposition states is that the local linear approximation outlined in \cref{prop:taylor} is a \textit{lower bound}. That is, for any convex function $f$, the linear approximation $\ell_{f,x}$ gives a \textbf{global lower bound} on the function itself. That means that any minima must lower \textit{above} that line. As we will see, many iterative methods utilize this idea of successively maximizing lower bounds and minimizing upper bounds to squeeze in on the optimal value. 

While convex function give a great place to start, often they do not proving rich enough structure for gradient descent to work effectively. The following class of functions really sets the stone for gradient descent to work well. 
\begin{definition}{$L$-smooth Functions}{}
    A function $f : \R^n \to \R$ is \textbf{$L$-smooth} if there exists an $L < \infty$ such that $$\|\nabla f(x)-\nabla f(y)\| \leq L\|x-y\|, \quad \forall x,y \in \R^n \ .$$ 
\end{definition}
There is another way to state the above definition. Utilizing the class of \textit{Lipschitz} functions: \begin{equation*}
    |f(x)-f(y)| \leq L\|x-y\|, \quad x,y \in \R^n .
\end{equation*} One can say that $f$ is $L$-smooth if and only if $\nabla f$ is $L$-Lipschitz. In essence, Lipschitz functions are ones whose gradients are bound in size. That is, the function isn't doesn't change too rapidly. For $L$-smooth functions, one can say that its gradients don't change too rapidly. In short:  \begin{equation*}
  \tcbhighmath{f \text{ is } L-\text{smooth}\Longrightarrow \text{we can trust nearby gradients}.}
  \end{equation*}
  This will be the key to utilizing gradient descent! If the gradients change at a controlled pace, then when we ``move in the direction of a gradient'' we can ensure that this movement is in the ``right direction'' for a enough time to take that step. More to see later,

  Notably $L$-smooth functions possess many properties. One of the more useful characterizations is that they can be bounded above \textit{globally} by a quadratic. What globally means in this context is that the curvature, or the coefficient attached to the analogous $x^2$ term, is precisely related to $L$. 

  \begin{lemma}[label = {descent-lemma}]{Descent Lemma}{}
   Suppose $f : \R^n \to \R$ is $L$-smooth and convex. Then,
   $$f(y) \leq f(x) + \inner{\nabla f(x)}{y-x}+\frac{L}{2}\|y-x\|^2, \quad \forall x,y \in \R^n \ .$$
  \end{lemma}
  That is, once we know $f$ has $L$-Lipschitz continuous gradient, and it is convex, we can immediately know that any quadratic centers at the point $(x,f(x))$ with the exact same gradient at $x$, and curvature $L$, will upper bound the entire function. We will utilize this proposition in the next chapter to motive \textbf{gradient descent}. To play around with this quadratic upper bound, click {\color{blue} \href{https://www.desmos.com/calculator/sybazxt9yh}{here}}.
\begin{proof}
    Consider the function $\phi_x(t) = f(x+t(y-x))$ for $t \in [0,1]$. Note that $\phi_x(0)=f(x)$ and $\phi_x(1)=f(y)$. Furthermore, the chain rule gives us that $\phi_x'(t)=\inner{\nabla f(x+t(y-x))}{y-x}$. Therefore, by fundamental theorem of calculus, $$f(y)-f(x)=\phi(1)-\phi(0)= \int_0^1 \phi'(t)dt = \int_0^1 \inner{\nabla f(x+t(y-x))}{y-x}dt$$
    Subtracting $\inner{\nabla f(x)}{y-x}$ from both sides, we get \begin{align*}
        f(y)-f(x)-\inner{\nabla f(x)}{y-x} &= \int_0^1 \inner{\nabla f(x+t(y-x))-\nabla f(x)}{y-x}dt\\
        &\leq \int_0^1 \|\nabla f(x+t(y-x))-\nabla f(x)\|\|y-x\|dt\\
        &\leq \int_0^1 L\|(x+t(y-x))-x\|\|y-x\|dt\\
        &=\int_0^1 Lt\|y-x\|^2dt\\
        &= \frac{L}{2}\|y-x\|^2
    \end{align*}
    Where the first inequality comes from Cauchy Schwarz \cref{eq:cauchy-schwarz}. The second comes from the Lipschitz continuous gradient. And the rest is simple rearrangement. 
\end{proof}
\begin{remark}{}{}
    While $L$-smooth functions are always differentiable, they may not admit a second derivative. However, if a function is $L$-smooth and twice differentiable, then the following holds: $$\|f''(x)\| \leq L, \quad \forall x \in \R^n \ .$$
    \tcblower
    Note that this $L$ isn't unique! If $f$ is $L$-smooth, then it is $\hat{L}$-smooth for any $\hat{L} \geq L$.
\end{remark}
Conversely, we define strongly convex functions as those possessing a uniform quadratic lower bound. 
\begin{definition}{Strongly Convex Functions}{}
    A function $f : \R^n \to \R$ is $\mu$-strongly if there exists a $\mu \geq 0$ such that 
    $$f(y) \geq f(x) + \inner{\nabla f(x)}{y-x} + \frac{\mu}{2}\|y-x\|^2, \quad \forall x,y \in \R^n \ . $$
\end{definition}
There are plenty of other characterizations of strong convexity, but the following helps visualize the lower bound on its curvature, while sharing a dual perspective to $L$-smoothness.
\begin{remark}{}{}
    If a function is $\mu$-strongly convex and twice differentiable, then the following holds: $$\|f''(x)\| \geq \mu, \quad \forall x \in \R^n \ .$$
    \tcblower
    Note that this $\mu$ isn't unique! If $f$ is $\mu$ -strongly convex, then it is $\hat{\mu}$-smooth for any $\hat{\mu} \leq \mu$.
\end{remark}
Below illustrates smooth and strong convexity. The function $f(x)$ (in orange) can be lower bounded by any linear approximation (in blue). This is a property of convexity. However, it can further be lower bounded by a quadratic approximation (in red), as well as upper bounded by a quadratic (in green). If the center point, that is where all the curves intersect, were shifted, we would still get lower/upper bounds with the same curvature! You can play around with strongly convex functions {\color{blue} \href{https://www.desmos.com/calculator/f2nvtdsza2}{here}}. Note that unlike smooth functions, strongly convex ones need \textit{not} be differentiable!
\begin{figure}[h]
    \centering
    \includegraphics[width=0.35\linewidth]{Images/smooth and strong convexity.png}
    \caption{Smoothness and Strong Convexity}
    \label{fig:Smooth-Strong-Convexity}
\end{figure}

\subsection{Why \textit{Gradient} Descent}
Let's begin with mentioning two important properties of the gradient. The first will require some new work (and a quite technical definition), but the second we have already seen before. 
\begin{definition}{Sublevel Sets and their Tangents}{}
    We denote the \textbf{sublevel set} for given function $f : \R^n \to \R$ at $\alpha \in \R$ by $$\mathscr{L}_f(\alpha) := \{x \in \R^n : f(x) \leq \alpha\}$$
    \tcblower
    Consider the set of directions \textbf{tangent} to $\mathscr{L}_f(f(x))$ at $x$:
        $$S_f(x) := \left\{s\in \R^n : s=\lim_{k \to \infty}\frac{y_k-x}{\|y_k-x\|}, \text{ for some } y_k \to x \text{ with } f(y_k) = f(x) \ \forall k \right\}$$
\end{definition}
The above definition is fairly involved, but the general idea is that $\mathscr{L}_f(\alpha)$ denotes all the points in $\R^n$ that get \textit{mapped} to a value at most $\alpha$. Consider the pair $(x,f(x))$, we can consider all the directions that do not change the function value. 

Considering a mountain range, the sublevel set are all the places you could stand that would be below a specific altitude, and the tangents are direction you could walk without changing your elevation!
\begin{lemma}{Gradients Point away from Level Sets}{}
    If $s \in S_f(x)$, then $\inner{\nabla f(x)}{s}=0$. That is, \begin{center}
        $\nabla f(x)$ is \textbf{orthogonal} to the level sets at $x$
    \end{center}
\end{lemma}
\begin{proof}
    Since $f(y_k)=f(x)$, we have $$f(y_k)=f(x)+\inner{\nabla f(x)}{y_k-x}+o(\|y_k-x\|)=f(x) \ .$$
    Therefore, $\inner{\nabla f(x)}{y_k-x}+o(\|y_k-x\|)=0$. Dividing by $\|y_k-x\|$ and taking limits yields the result.
\end{proof}
The above lemma states the gradient points away from the directions that \textit{don't} change the function value. In particular, they point \textit{away as much as they can}. \begin{remark}{}{}
    \begin{center}
        Thus, if we want to change function value (either increase or decrease), we should move in the direction of the gradient (or perhaps its negative).
    \end{center}
\end{remark} The following property will further justify this claim. Recall from \cref{cor:gradient-representation} that the gradient of a function $f : \R^n \to \R$ ``represents'' all the directional derivatives. That is, given a gradient at a point, $\nabla f(x)$, one can evaluate the ``rate of change'' in any direction by simply evaluating an inner product: \begin{equation*}
    f'(x;v) = \inner{\nabla f(x)}{v} \ .
\end{equation*}
If we apply Cauchy Schwarz inequality \labelcref{cauchy-schwarz}, we see that $$-\|\nabla f(x)\|\|v\| \leq \inner{\nabla f(x)}{v} \leq \|\nabla f(x)\|\|v\| \ .$$
Since $\|v\|$ is a unit vector, we can see that the most we can decrease (or increase) is $\|\nabla f(x)\|$, and this value can be achieved by choosing $$v = -\frac{\nabla f(x)}{\|\nabla f(x)\|} \ .$$
\begin{remark}{Steepest Descent}{}
    \centering Moving in the direction of the negative gradient, $-\nabla f(x)$, gives the \textit{fastest local decrease} of the function $f(\cdot)$ at the point $x$! 
\end{remark}

We can now conclude this section with perhaps the \textbf{most fundamental} fact in optimization theory.
\begin{theo}{First-Order (local) Optimality Conditions}{}
    Let $x^\star$ be a local minimum to a differentiable function $f(\cdot)$. Then $$\nabla f(x^\star) = 0 \ .$$
\end{theo}
\begin{proof}
    Since $x^\star$ is a local minimizer of $f(\cdot)$, there exists an $r > 0$ where $f(y) \geq f(x^\star)$ for all $y \in B(x^\star;r)$. Since $f$ is differentiable, by \cref{prop:taylor}, $$f(y) = f(x^\star) + \inner{\nabla f(x^\star)}{y-x^\star}+o(\|y-x^\star\|)\geq f(x^\star), \quad \forall y \in B(x^\star;r) .$$
    Considering the inequality, subtracting $f(x^\star)$ and again dividing by $\|y-x^\star\|$ and taking limits as needed, we see that \begin{equation}\label{eq:nonneg-dir-derivate}0 \leq \inner{\nabla f(x^\star)}{v}=f'(x;v), \quad \forall v \in \R^n!\end{equation}
    Considering $v = -\nabla f(x^*)/\|\nabla f(x^*)$ implies that $$\|\nabla f(x^*)\| \leq 0 \ .$$
    By the nonnegativity of the norm, it must hold that $$\|\nabla f(x^*)\| = 0 \Longrightarrow \nabla f(x^\star)=0 \ .$$
\end{proof}
Note that \labelcref{eq:nonneg-dir-derivate} implies that all directional derivatives are nonnegative. That is, any direction that one moves from the local minimizer must increase (or remain constant) the function value.

Further note that the converse may not hold in general. The gradient could be zero at $x$, but $f(x)$ may not be a minimum. Consider the function $$f(x,y) = x^2-y^2,  \quad \nabla f(0,0) = \begin{bmatrix}
    0 \\ 0
\end{bmatrix}$$
\begin{figure}[h]
    \centering
    \includegraphics[width=0.5\linewidth]{Images/saddlepoint.png}
    \caption{Graph of $f(x,y)=x^2-y^2$}
    \label{fig:saddle-point}
\end{figure}
However, if $f$ is also assumed to be convex, then the converse holds! Convexity ensures that $$f(y) \geq f(x^\star)+\inner{\nabla f(x^\star)}{y-x^\star}, \quad \forall y \in \R^n\ ,$$
and when $\nabla f(x^\star)=0$, we get $$f(y) \geq f(x^\star), \quad \forall y \in \R^n \ .$$
Since this holds for all $y$, not just in a small neighborhood around $x^\star$, this result implies that local minimizers for convex function are in fact global.
Thus, we get our second big theorem.
\begin{theo}{First-Order Optimality Conditions}{}
   Let $f(\cdot)$ be a \textbf{convex} differentiable function. Then the following are equivalent.
    \begin{enumerate}
        \item $x^\star$ is a local minimum
        \item $x^\star$ is a global minimum
        \item $\nabla f(x^\star) = 0$
    \end{enumerate}
\end{theo}
Therefore, we can describe the second way to check for optimality, one we can actually perform in an algorithm as it assumes no knowledge of $x^\star$.
\begin{definition}{Nearly Optimal (gradient norm)}{}
    Let $\bar{x}$ be the output of some iterative method. Given target accuracy $\eps > 0$, we say $\bar{x}$ is $\eps$-optimal if $$\|\nabla f(\bar x)\| \leq \eps$$
\end{definition}

We now have all the tools and knowledge to introduce our \textbf{Gradient Descent} method. The concept is simple, but the theory goes very deep. There are many ways we can tweak this method to ensure better convergence rates. Further assumptions on $f(\cdot)$ can also speed up there algorithm. However, in its base form, the algorithm works as follows:
\begin{algo}[label =  {algo:gradient-descent}]{Gradient Descent}{}
    {\normalfont \textbf{Input}: $x^0 \in \R^n$, target accuracy $\eps > 0$ and stepsizes $h_k$}
    \tcblower
    \textbf{For} $k = 0, 1, 2, \dots$
    \begin{enumerate}
        \item  \indent $ x^{k+1} \gets x^k-h_k \nabla f(x^k)$
    \end{enumerate}
   
\end{algo}
One may ask: when does \cref{algo:gradient-descent} terminate? How many iterations does it take? What structure and geometry of $f(\cdot)$ is desired? How must we choose stepsizes $h_k$? Can we guarantee anything about the suboptimality gap (how close is $f(\bar{x})$ to $f(x^\star))$? What about size of the gradients $\| \nabla f(\bar{x})\|$? All of this will be discussed in the next section.
\begin{figure}[h]
    \centering
    \includegraphics[width=0.5\linewidth]{Images/gd_image.png}    \caption{\href{https://medium.com/@ilyasaoudata/you-should-understand-backpropagation-in-regression-before-diving-into-neural-networks-5e08d48d69e6}{Medium}}
    \label{fig:Gradient-Descent}
\end{figure}
