\section{Convergence Guarantees for Gradient Descent}

This section will primarily focus on the convergence results for applications of \cref{algo:gradient-descent}. Note that this algorithm is essentially only one line, with barely any freedom to alter its procedure. We really only have leverage over the initial point, $x^0 \in \R^n$, the target accuracy $\eps > 0$, and the stepsizes $h_k$. This information alone will typically not guarantee much. We won't know how many iterations to run to ensure small suboptimality gap or small gradient norms. We may not even guarantee convergence at all! However, with \textit{known structure} of the function we are aiming to minimize, we can readily solve these issues.

\subsection{Smooth Functions}
For ease of notation, we will define the following classes of function. Later on, we will further restrict to \textbf{convex} functions with the same properties.
\begin{definition}{The Class of $L$-Smooth Functions}{}
    Let $C_{L}(\R^n)$ denote the class of differentiable functions $f: \R^n \to \R$ with Lipschitz continuous gradient $$\|\nabla f(x)-\nabla f(y)\| \leq L\|x-y\|, \quad \forall x,y \in \R^n \ .$$
\end{definition}
We first note a pleasant property of smooth functions. While there exist methods to generalize the notion of a gradient to nondifferntiable functions, $L$-smooth functions are always differentiable. Therefore, it makes sense to apply gradient descent to such functions.
Unpacking the above definition, it says that for $x$ and $y$ close together, say $y=x+hv$ for unit vector $v \in \R^n$ and $h$ small. Then $\|\nabla f(x+hv)-\nabla f(x)\| \leq hL$. When considering $v = -\nabla f(x)$, a gradient step, we note that $$\|\nabla f(x^{k+1})-\nabla f(x^k) \| \leq hL \ .$$
\textbf{That is, the gradient (or direction we are moving) where we end up each iteration is not too different from where we started}. In other words, we can ``trust our gradients'' each step. If $L$ is large, we just need to make $h$ smaller. In fact, we can \textit{optimize} this value of $h$ to guarantee the most descent each step!




There are many possible values of $h_k$ one can choose. However, let's start by considering three possible strategies.
\begin{remark}{Possible Stepsize Rules}{}
    \begin{enumerate}
        \item The sequence $h_k$ is chosen in advance. For example, \begin{align*}
            h_k &= h > 0, &\text{(constant step)}\\
            h_k &= \frac{h}{\sqrt{k+1}}, &\text{(decaying step)}
        \end{align*}
        \item Full relaxation (find the greastest functional decrease):
        \begin{align*}
            h_k &= \argmin_{h \geq 0}{f(x^k)-h \nabla f(x^k)}
        \end{align*}
        \item The Armijo Rule: find $x^{k+1}=x^k-h \nabla f(x^k)$ such that \begin{align}\label{armijo-rule}
            \alpha \inner{\nabla f(x^k)}{x^k-x^{k+1}} &\leq f(x^k)-f(x^{k+1}) \leq 
             \beta \inner{\nabla f(x^k)}{x^k-x^{k+1}}
        \end{align}
        where $0 < \alpha < \beta < 1$ are fixed
    \end{enumerate}
\end{remark}

Comparing these strategies, we note that the first is by far the simplest. It is used in many algorithms, especially ones where minimizer are guaranteed to be global if they exists (i.e., convex optimization). The second is completely theoretical as even in one-dimensional settings, finding the minimizer $h^\star$ may be infeasible. The third is complex, but used in the many practical algorithms. The geometric interpretation is explained below. 

Consider the iterates $x^k$ and $x^{k+1}= x^k-h_k \nabla f(x^k)$. Now consider the function value at $f(x^{k+1})$. This is a one-dimensional function of the stepsize $h_k$. Define \begin{equation}
    \phi(h) := f(x^{k+1})=f(x^k-h \nabla f(x^k)), \quad h \geq 0\ .
\end{equation}
Recall the conditions for the Armijo rule, as well as how we construct $x^{k+1}$ result in $h$ being a suitable stepsize if \begin{align}
    \phi_2(h) \leq \phi(h) \leq \phi_1(h), \quad \phi_1(h) = f(x^k)-\alpha h \|\nabla f(x^k)\|^2, \quad \phi_2(h) = f(x^k)-\beta h \|\nabla f(x^k)\|^2 \ .
\end{align}
\begin{exercise}[label = {exercise-armijo}]{}{}
    Check that the above condition implies the Armijo rule \labelcref{armijo-rule}. That is given $0 < \alpha < \beta < 1$, for any $h$ satisfying $$\phi_2(h) \leq \phi(h) \leq \phi_1(h) \ ,$$
    then \begin{align*}
            \alpha \inner{\nabla f(x^k)}{x^k-x^{k+1}} &\leq f(x^k)-f(x^{k+1}) \leq
             \beta \inner{\nabla f(x^k)}{x^k-x^{k+1}} 
        \end{align*}
\end{exercise}
Geometrically, the Armijo rule can be seen as finding an $h$ that lies in the black region. The thick red line is the objective function $f(x)$, and the thin black function is $\phi(x)$. The upper and bounding linear functions $\phi_1$ and $\phi_2$ are the dotted red and blue respectively. The {\color{blue}\href{https://www.desmos.com/calculator/oahkt7wzj1}{desmos link}} is attached if you wish to play around.
\begin{figure}[t]
    \centering
    \includegraphics[width=0.65\linewidth]{Images/armijo_rule.png}
    \caption{\href{https://www.desmos.com/calculator/oahkt7wzj1}{Geometric Interpretation of Armijo Rule}}
    \label{fig:enter-label}
\end{figure}


\subsubsection{Optimizing $h_k$ for the three different methods.}
Let's estimate the performance of gradient descent for $L$-smooth functions $f \in C_L(\R^n)$ that are bounded below. Consider a single gradient step $$x^{k+1} = x^k-h\nabla f(x^k) \ .$$
Recalling an equivalent characterization of $L$-smoothness, the result from \cref{descent-lemma} says \begin{align*}
    f(x^{k+1}) & \leq f(x^k) + \inner{\nabla f(x^k)}{x^{k+1}-x^k}+ \frac{L}{2}\|x^{k+1}-x^k\|^2\\
    &= f(x^k) + \inner{\nabla f(x^k)}{x^k-h\nabla f(x^k)-x^k}+ \frac{L}{2}\|x^k-h\nabla f(x^k)-x^k\|^2\\
    &= f(x^k)-h\|\nabla f(x^k)\|^2 + \frac{h^2}{2}L\|\nabla f(x^k)\|^2\\
    &=f(x^k)-h(1-\frac{h}{2}L)\|\nabla f(x^k)\|^2 \ .
\end{align*}
Therefore, to get the most decrease each step, we simply need to solve the one-dimensional problem: $$\min_h -h(1-\frac{h}{2}L) \Longrightarrow h^\star = \frac{1}{L} \ .$$
\begin{exercise}{}{}
    Verify that $h^\star$ is in fact the minimizer of $\Delta(h) = -h(1-\frac{h}{2}L)$ (hint: consider the first and second derivatives).
\end{exercise}
We have now proved the following lemma. 
\begin{lemma}{Descent Lemma II}{}
    For $f \in C_L(\R^n)$, one step of gradient descent decreases the value of the objective function $$f(x^{k+1}) \leq f(x^k) - \frac{1}{2L}\|\nabla f(x^k)\|^2$$
\end{lemma}
Considering our stepsize scheme, for constant stepsizes $h_k = h= \alpha/L$ for $\alpha \in (0,2)$, then $$f(x^{k+1}) \leq f(x^k) - \frac{1}{L}\alpha(1-\frac{\alpha}{2}) \|\nabla f(x_k)\|^2 \ .$$
Of course, the optimal choice is still $h_k = \frac{1}{L}$, or choosing $\alpha=1$, but we can guarantee descent for any $\alpha \in (0,2)$.
\begin{remark}{}{}
    Note that setting $q_{x^{k},\alpha}(x) := f(x^k)+\inner{\nabla f(x^k)}{x-x^k}+\frac{L}{2\alpha}\|x-x^k\|^2$ acts as a quadratic approximation for $f(\cdot)$ at $x^k$. For $\alpha = 1$, this is the precisely the descent lemma. Regardless, computing its minimizer $$\argmin q_{x^k,\alpha}(x) = x^k-\frac{\alpha}{L}\nabla f(x^k) $$
    demonstrates that minimizing the quadratic upper bound yields the exact method for gradient descent!
    \tcblower
    For $\alpha > 1$, we may overshoot the minimizer, but this is not an issue, as long as we make descent. Another \href{https://www.desmos.com/calculator/jzct403rnw}{desmos graph} to see this in action!
\end{remark}
Considering the Armijo rule, we note that from \cref{exercise-armijo} that $$f(x^{k+1}) \geq f(x^k)-\beta h_k \|\nabla f(x^k)\|^2 \ .$$
However, we have previously seen that $$f(x^{k+1}) \leq f(x^k)-h_k(1-\frac{h_k}{2})\|\nabla f(x^k)\|^2 \ ,$$
which concludes that $h_k \geq \frac{2}{L}(1-\beta)$. Using the other condition of \cref{exercise-armijo}, we have $$f(x^{k+1}) \leq f(x^k)-\alpha h_k \|\nabla f(x^k)\|^2 \leq f(x^k) - \frac{2}{L}\alpha(1-\beta)\|\nabla f(x^k)\|^2 \ .$$
Letting $\omega = 2\alpha(1-\beta)$, we again recover the notation that \begin{equation}\label{eq:iterate-descent-omega/L}f(x^{k+1}) \leq f(x^k) - \frac{\omega}{L}\|\nabla f(x^k)\|^2 \ ,\end{equation}
achieving the optimal decrease when $\alpha = \beta = \frac{1}{2}$. 
We are now ready to conclude something about gradient descent. 
\begin{theo}[label = {gradient-norm-bound-smooth}]{Gradient Norm Bound}{}
    For $f \in C_L(\R^n)$, running gradient descent with stepsizes $h_k$ resulting in \labelcref{eq:iterate-descent-omega/L} yields the following inequality \begin{equation}\label{eq:smooth-gradient-bound}
        g_N^\star \leq {\sqrt{\frac{L(f(x^0)-f^\star)}{\omega(N+1)}}} \ ,
    \end{equation} 
    where $g_N^\star := \min_{0 \leq k \leq N} \|\nabla f(x^k)\|$
\end{theo}
\begin{proof}
    Since \labelcref{eq:iterate-descent-omega/L} holds for each $k = 0, \dots, N$, we can sum each inequality \begin{align*}
        &f(x^1) \leq f(x^0) - \frac{\omega}{L}\|\nabla f(x^0)\|^2\\
        + \ &f(x^2) \leq f(x^1) - \frac{\omega}{L}\|\nabla f(x^1)\|^2\\
      + \ &f(x^3) \leq f(x^2) - \frac{\omega}{L}\|\nabla f(x^2)\|^2\\
      + \ & \hspace{2cm} \vdots \\
        + \ &f(x^{N+1}) \leq f(x^N) - \frac{\omega}{L}\|\nabla f(x^N)\|^2 \ ,
    \end{align*}
    noting that we can cancel most of the terms
    \begin{equation*}
    \begin{split}
        &  \cancel{f(x^1)} \leq f(x^0) - \frac{\omega}{L}\|\nabla f(x^0)\|^2\\
        + \ &\cancel{f(x^2)}\leq \cancel{f(x^1)} - \frac{\omega}{L}\|\nabla f(x^1)\|^2\\
      + \ &\cancel{f(x^3)} \leq \cancel{f(x^2)} - \frac{\omega}{L}\|\nabla f(x^2)\|^2\\
      + \  & \hspace{2cm} \vdots \\
        + \ &f(x^{N+1}) \leq \cancel{f(x^N)} - \frac{\omega}{L}\|\nabla f(x^N)\|^2 \\
        \Longrightarrow  \ &\boxed{ f(x^{N+1}) \leq f(x^0)-\frac{\omega}{L}\sum_{k=0}^N \|\nabla f(x^k)\|^2}
\end{split}
    \end{equation*}
Rearranging, we can conclude that \begin{equation}\label{eq:smooth-gradient-sum-bound}
    \frac{\omega}{L}\sum_{k=0}^N \|\nabla f(x^k)\|^2 \leq f(x^0)-f(x^{N+1}) \leq f(x^0)-f^*  \ ,
\end{equation}
as $f^*$ is a lower bound for all of $f(\cdot)$. Therefore, the series is bounded as $N \to \infty$, and consequently, $$\|\nabla f(x^k)\| \to 0, \quad \text{as} \quad k \to \infty \ .$$
However, we can say more than \textit{existence} of convergence, we can quantify the rate! Considering that an average of nonnegative values upper bounds the minimum (the average of a bunch of test scores clearly is higher than the lower score), we can rearrange \labelcref{eq:smooth-gradient-sum-bound} to conclude $$g_N^\star \leq \sqrt{\frac{L(f(x^0)-f^\star)}{\omega (N+1)}} \ .$$
\end{proof}
As we saw, the optimal decrease achieves $\omega = \frac{1}{2}$, so our first convergence bound says that running \cref{algo:gradient-descent} with $h_k = h = \frac{1}{L}$ results in $$\min_{0 \leq k \leq N} \|\nabla f(x^k)\| \leq \sqrt{\frac{2L(f(x^0)-f^\star)}{N+1}} \ .$$
If we want to guarantee that for a fixed $\eps > 0$, that we will find some iterate $x^k$ whose gradient is sufficiently small, we simply need to upper bound our convergence rate by $\eps$ and solve. That is, we consider $$\min_{0 \leq k \leq N} \|\nabla f(x^k)\| \leq \sqrt{\frac{2L(f(x^0)-f^\star)}{N+1}} < \eps 
\ ,$$ and conclude that for $$N \geq \frac{2L(f(x^0)-f^\star)}{\eps^2} \Longrightarrow \min_{0 \leq k \leq N} \|\nabla f(x^k)\| < \eps \ .$$

\begin{exercise}{}{}
    Let $A, C$ be $n \times n$ matrices and $b, d \in \R^n$. Consider $$f(x) = \|Ax-b\|^2+\|Cx-d\|^2 \ .$$ Explain how you would  find a vector $\bar{x}$ such that $\| \nabla f(\bar{x})\| < 0.001$ (hint: find a value $L$ such that $$\|\nabla f(y)-\nabla f(x)\| \leq L\|y-x\|, \quad \forall x, y \in \R^n$$ and an upper bound on $f(x^0)-f^\star$, for any chosen $x^0$).
    \tcblower
    It may be useful to know the definition of  norm of a matrix: $$\|A\| := \sup_{x \ne 0} \frac{\|Ax\|}{\|x\|} \ ,$$ and subsequently for all $x \in \R^n$, $$\|Ax\| \leq \|A\|\|x\| \ .$$
\end{exercise}

Note that in general, our goal is relatively tame: we only want to approach a \textit{local} minimum. Still, even this goal can be unreachable to gradient descent. If a function has a saddle point, that is $\nabla f(x) = 0$ yet $x$ is neither a local minimum or maximum, we very well may approach that point, and then stay there for any future iterate (why?). In order to achieve stronger goals, with perhaps faster rates of convergence, we need stronger assumptions on the function we aim to minimize.

\subsection{Smooth and \textit{Convex} Functions}
In this section, we still consider the general optimization problem \begin{equation}\label{eq:general-minimization-problem}
    \min_{x \in \R^n} f(x)
\end{equation}
where the objective function is $L$-smooth (and hence differentiable). Recall that previously, we had aimed to solve this problem under fairly weak assumptions on $f(\cdot)$. Adopting the same assumptions as Nesterov~\cite[Assumption 2.1.1-2.1.3]{nesterov_lectures}, we aim to construct a class of differentiable functions of differentiable functions $\Fscr$ we wish to work with. From the conclusion of the last section, we note that the optimality conditions was simply not strong enough to guarantee a global minimum. In fact, a zero gradient wasn't even strong enough to ensure a local one! Let's first address this issue. 
\begin{assumption}[label = {assumption 1}]{$\Fscr$ has nicer optimality conditions}{}
    For any $f \in \Fscr$, the first-order optimality condition is sufficient to ensure a global minimizer. That is, $$\nabla f(\bar x) = 0 \Longrightarrow f(\bar x) \leq f(y), \ \forall y \in \R^n \ . $$
\end{assumption}
The next property we would like to see is some level of \textit{invariance} for elements in our function class. That is, we would wish to be able to construct new functions from others in ``simple'' ways. Similar to the structure of vector spaces, we introduce only simple invariant operations for our function class. 
\begin{assumption}[label = {assumption 2}]{$\Fscr$ is a cone (like a vector space, but nonnegative scaling)}{}
    If $f_1, f_2 \in \Fscr$, and $\alpha, \beta \geq 0$, then $$\alpha f_1 + \beta f_2 \in \Fscr \ .$$
\end{assumption}
Note we only consider nonnegative scaling $\alpha$ and $\beta$, as we would like $x^2$ to be in our class and not $-x^2$. Essentially, negatives turn minimizers into maximizers, so we arbitrarily pick the former and restrict ourselves accordingly. 

Finally, let's add some basic functions to our class. 
\begin{assumption}[label = {assumption 3}]{$\Fscr$ contains affine (shifted linear) functions}{}
    For any $\alpha \in \R$ and $s \in \R^n$, $$f(x) := \alpha + \inner{s}{x} \in \Fscr \ .$$
\end{assumption}

Note that for linear functions $\nabla f(x) = 0$ if and only if $f$ was constant, meaning that any $x$ is a global minimizer.  

These three assumptions turn out to be exactly what we need to introduce our function class. Let $f \in \Fscr$ and consider the perturbed function (which is in $\Fscr$ by \cref{assumption 2,assumption 3}) for a fixed $x^0 \in \R^n$, $$\phi(y) = f(y) - \inner{\nabla f(x^0)}{y} \ .$$
Note that $$\nabla \phi(y) \biggr|_{y=x^0} = \nabla f(x^0)-\nabla f(x^0)=0\ , $$
so by \cref{assumption 1}, $x^0$ must be a global minimizer of $\phi(\cdot)$. Therefore, for any $y$, $$f(y)-\inner{\nabla f(x^0)}{y}=\phi(y) \geq \phi(x^0) = f(x^0)-\inner{\nabla f(x^0)}{x^0} ,$$
recovering the condition \begin{equation}\label{eq:lower-linearization}
    f(y) \geq f(x)+\inner{\nabla f(x)}{y-x},  \quad \forall x,y \in \R^n
\end{equation}
since $x^0$ was arbitrary. We note this result has the precise result of convex functions demonstrated by \cref{prop:lower-linearization}. In fact, these functions are precisely the convex ones described earlier.

\subsubsection{$\Fscr$ is the set of convex functions.} We already showed that these assumptions imply a lower linearization, so now we demonstrate the other direction. We will need a couple auxiliary lemmas to begin, showing the above condition is sufficient to satisfy all through assumptions. Therefore, functions that possess lower linearizations coincide with ones in $\Fscr$.
\begin{lemma}{\cref{assumption 1} is satisfied}{}
    Suppose differentiable $f : \R^n \to \R$ satisfies \labelcref{eq:lower-linearization} and $\nabla f(x^\star)=0$, then $x^\star$ is a global minimizer of $f(\cdot)$ on $\R^n$. 
\end{lemma}
\begin{proof}
    For any $y \in \R^n$, $$f(y) \geq f(x^\star)+\inner{ \nabla f(x^\star)}{y-x^\star} = f(x^\star) \ .$$
\end{proof}
\begin{lemma}{\cref{assumption 2} is satisfied}{}
    Suppose differentiable $f_1, f_2 : \R^n \to \R$ satisfies \labelcref{eq:lower-linearization} and $\alpha, \beta \geq 0$. Then $\alpha f_1+\beta f_2$ also satisfies \labelcref{eq:lower-linearization}.
\end{lemma}
\begin{proof}
    For any $x, y \in \R^n$, we have \begin{align*}
        f_1(y) \geq f_1(x)+\inner{\nabla f_1(x)}{y-x} \ .\\     
        f_2(y) \geq f_2(x)+\inner{\nabla f_2(x)}{y-x} \ .\\
    \end{align*}
    Multiplying the first line by $\alpha$ and the second by $\beta$ and adding the two inequalities shows the desired result. 
\end{proof}
\begin{lemma}{\cref{assumption 3} is satisfied}{}
    For any $f$ satisfying \labelcref{eq:lower-linearization}, linear map $A : \R^n \to \R^m$, and vector $b \in \R^m$, then the map $$\phi(x) = f(Ax+b)$$ also satisfies \labelcref{eq:lower-linearization}.
\end{lemma}
\begin{proof}
    Let $x, y \in \R^n$, $\bar x = Ax+b$, and $\bar y = Ay+b$. Note that from the chain rule, $$\nabla \phi(x) = A^T \nabla f(Ax+b)\ ,$$
    so we have \begin{align*}
        \phi(y) = f(\bar y) &\geq f(\bar x)+\inner{\nabla f(\bar x)}{\bar y - \bar x}\\
        &=\phi(x)+\inner{\nabla f(\bar x)}{Ay-Ax}\\
        &=\phi(x)+\inner{A^T\nabla f(\bar x)}{y-x}\\
        &= \phi(x) + \inner{ \nabla \phi(x)}{y-x} \ ,
    \end{align*}
    where the first inequality comes from $f$ satisfying \labelcref{eq:lower-linearization}, and the result follow from the definitions of $\bar{x}$, $\bar{y}$ and $A^T$ (one definition is that $\inner{x}{Ay}=\langle {A^Tx},{y}\rangle$ for all $x$ and $y$).
\end{proof}
With the first characterization that $$\Fscr = \{f : f \text{ satisfies } \labelcref{eq:lower-linearization}\}$$
out of the way, we can prove our characterization that this class of functions we want to analyze is precisely the set of convex functions.
\begin{theo}{$\Fscr$ is the set of differentiable convex functions}{}
    A function $f$ belongs to $\Fscr$ if and only if for any $x, y \in \R^n$ and $t \in [0,1]$ \begin{equation}\label{eq:convexity-def}
        f(tx+(1-t)y) \leq tf(x)+(1-t)f(y) \ .
    \end{equation}
\end{theo}
    \begin{proof}
        Given $x, y \in \R^n$ and any $t \in [0,1]$, define $x_t = tx+(1-t)y$. Let $f \in \Fscr$, then \begin{align*}
            f(x_t) &\leq f(y)-\inner{\nabla f(x_t)}{y-x_t} = f(y) - t\inner{\nabla f(x_t)}{y-x}\\
              f(x_t) &\leq f(x)-\inner{\nabla f(x_t)}{x-x_t} = f(x) + (1-t)\inner{\nabla f(x_t)}{y-x} \ .\\
        \end{align*}
Multiplying the first equation by $(1-t)$ and the second by $t$ and adding results, we cancel the inner product terms and get the result $$f(x_t)=f(tx+(1-t)y) \leq tf(x)+(1-t)f(y) \ .$$
On the other hand, if \labelcref{eq:convexity-def} holds for all $x, y \in \R^n$ and $\alpha \in [0,1]$, then for any $\alpha \in [0,1)$ we can rearrange the expression to yield \begin{align*}f(y) \geq \frac{1}{1-t}\left[f(tx+(1-t)y)-tf(x)\right]&=f(x)+\frac{1}{1-t}\left[f(tx+(1-t)y)-f(x)\right]\\
&=f(x) + \frac{f(x+(1-t)(y-x))-f(x)}{1-t} \ .
\end{align*}
This holds for all $t$, and letting $t \to 1$, we recover the directional derivative, which from \cref{cor:gradient-representation} shows that $$f(y) \geq f(x)+\inner{\nabla f(x)}{y-x} \ ,$$ and consequently $f \in \Fscr$.
    \end{proof}
    There are several other equivalent characterizations of convex functions, which we will now discuss.
\subsubsection{Equivalent Characterizations for Convex and Smooth Functions}
In order to analyze the convergence guarantees for gradient descent in the smooth and convex setting, it will be especially useful to utilize the following equivalent characterizations. All the proofs for the rates in which gradient descent converge have the same flavor: \begin{enumerate}
    \item Consider the gradient step $x^{k+1}=x^k-h_k\nabla f(x^k)$.
    \item Utilize one of the properties of smooth and convex functions.
    \item Substitute, rearrange, bound.
\end{enumerate}
Different results may utilize different characterizations, in that some will tell us how function values are behaved, others may indicate growth on the difference between gradients.. Regardless, the following characterizations will prove extremely useful in analyzing our algorithm. 

We begin by considering equivalences for convex functions.
\begin{theo}[label = {convexity-characterizations}]{Equivalent Characterizations of Convex Functions}{}
    For differentiable $f : \R^n \to \R$, any $x, y \in \R^n$ and parameter $t \in [0,1]$, the following are equivalent:\begin{enumerate}[i)]
        \item $f$ is convex, denoted $f \in \mathscr{F}(\R^n)$
        \item (Jensen's inequality) \  $f(tx+(1-t)y) \leq tf(x)+(1-t)f(y)$  
        \item (First-order lower bound)\ $f(y) \geq f(x)+\inner{\nabla f(x)}{y-x}$  
        \item (Monotonicity of the gradient) \ $\inner{f(x)-f(y)}{x-y} \geq 0$  
    \end{enumerate}
\end{theo}
\begin{proof}
    We have already demonstrated $i) \Longleftrightarrow ii) \Longleftrightarrow iii)$. It suffices to conclude $iii) \Longleftrightarrow iv)$. From the first-order lower bound, we have for any $x,y \in \R^n$ $$f(y) \geq f(x) + \inner{\nabla f(x)}{y-x}, \quad f(x) \geq f(y)+\inner{\nabla f(y)}{y-x} \ .$$
    Adding the two inequalities together yields $iv)$.

    Now suppose $iv)$ holds. Define $x_t = x + t(y-x)$ for $t \in [0,1]$. \begin{align*}
        f(y) &= f(x) + \int_0^1 \inner{\nabla f(\underbrace{x+t(y-x)}_{x_t})}{y-x}dt\\
        &= f(x) + \inner{\nabla f(x)}{y-x}+\int_0^1 \inner{\nabla f(x_t)-\nabla f(x)}{y-x}dt\\
        &= f(x) + \inner{\nabla f(x)}{y-x}+\int_0^1 \frac{1}{t}\inner{\nabla f(x_t)-\nabla f(x)}{x+t(y-x)-x}dt\\
        &= f(x) + \inner{\nabla f(x)}{y-x}+\underbrace{\int_0^1 \frac{1}{t}\inner{\nabla f(x_t)-\nabla f(x)}{x_t-x}dt}_{\geq 0}\\
        &\geq f(x)+\inner{f(x)}{y-x} \ ,
    \end{align*}
    where the first equation holds by the fundamental theorem of calculus (why?), the second equality adds and subtracts the linear term $\inner{\nabla f(x)}{y=x}$, and finally we simplify and utilize the monotonicty of the gradient.
\end{proof}
We discussed extensively properties $ii)$ and $iii)$, but $iv)$ also shares some insight on convex functions. This characterization roughly states that the gradients are increasing. That is, if $y > x$ then $\nabla f(y) > \nabla f(x)$. This can work in higher-dimensions too by considering only increasing one component and keeping the rest static. 

Now we move onto smooth functions. There are several more properties of smooth functions, but below are the ones we will find particularly useful. 
\begin{theo}[label={equiv_char_smooth}]{Equivalent Characterizations of Smooth and Convex Functions}{}
    For differentiable $f : \R^n \to \R$ and any $x, y \in \R^n$, the following are equivalent:\begin{enumerate}[i)]
        \item $f$ is $L$-smooth and convex over $\R^n$, denoted $f \in \mathscr{F}_L(\R^n)$
        \item (Lipschitz continuous gradient) \ $\|\nabla f(x)-\nabla f(y)\| \leq L\|x-y\|$ 
        \item (Quadratic upper bound) \  $f(y) \leq f(x)+\inner{\nabla f(x)}{y-x}+\frac{L}{2}\|y-x\|^2$
        \item (Upper bounded monotonicity) \ $\inner{\nabla f(x)- \nabla f(y)}{x-y} \leq L\|x-y\|^2$
        \item (Cocoercivity) \ $f(y) \geq f(x)+\inner{\nabla f(x)}{y-x}+\frac{1}{2L}\|\nabla f(x)-\nabla f(y)\|^2$
        \item (Lower bounded monotonicity) \ $\inner{\nabla f(x) - \nabla f(y)}{x-y} \geq \frac{1}{L}\|\nabla f(x)-\nabla f(y)\|^2$
    \end{enumerate}
\end{theo}
\begin{proof}
    As $i) \Longleftrightarrow ii)$ by definition, we can prove the result by showing $$ii) \Longrightarrow iii) \Longrightarrow iv) \Longrightarrow v) \Longrightarrow vi) \Longrightarrow ii) \ .$$
    \begin{itemize}
        \item $ii) \Longrightarrow iii)$: Fundamental theorem of calculus.
        \item $iii) \Longrightarrow iv)$: Swap the roles of $x$ and $y$ and add the inequalities.
        \item $iv) \Longrightarrow v)$: Fix $x \in \R^n$ and define $\phi_x(y) := f(y) - \inner{\nabla f(x)}{y}$ (this should look familiar). We have already seen this function is convex with a minimizer at $y^\star = x$. Furthermore, \begin{align*}
            \inner{\nabla \phi_x (y_1)-\nabla \phi_x(y_2)}{y_1-y_2} &= \inner{(\nabla f(y_1)-\nabla f(x))-(\nabla f(y_2)-\nabla f(x))}{y_1-y_2}\\
            &= \inner{\nabla f(y_1)-\nabla f(y_2)}{y_1-y_2}\\
            &\leq L\|y_1-y_2\|\ .
        \end{align*}
        Therefore, $\phi_x$ satisfies $iv)$. Again using fundamental theorem of calculus (see exercise below to fix this missing details), we can obtain $iii)$ from $iv)$. Consequently, it also holds that $$\phi_x(y_2) \leq \phi_x(y_1)+\inner{\nabla \phi_x(y_1)}{y_2-y_1}+\frac{L}{2}\|y_2-y_1\|^2 \ .$$
        Simply renaming, we have that for any $y \in \R^n$, consider $$\phi_x(z) \leq \phi_x(y) + \inner{ \nabla \phi_x(y)}{z-y}+\frac{L}{2}\|z-y\|^2$$
        and minimizing over $z$. We know that left hand side is minimized at $z^\star = x$, so we just need to minimize the right hand side. That is \begin{equation}\label{eq:cocoercivity-bound-prelim}
            f(x)-\inner{\nabla f(x)}{x} = \phi_x(x) \leq \phi_x(z) \leq  \phi_x(y) + \inner{ \nabla \phi_x(y)}{z-y}+\frac{L}{2}\|z-y\|^2 \ .
        \end{equation}

        Recall, to minimize a (convex) function, it suffices to sets its gradient equal to zero, so consider the equation on the right hand side $$Q_{x,y}(z) = \phi_x(y)+\inner{\nabla \phi_x(y)}{z-y}+\frac{L}{2}\|z-y\|^2$$
        where we again recall {$x$ and $y$} are fixed. Thus, $$\nabla Q_{x,y}(z^\star) = \nabla \phi_x(y) + L(z^\star-y) = 0 \ .$$
        To find $z^\star$, we substitute $\nabla \phi_x(y)=\nabla f(y)-\nabla f(x)$ and solve \begin{align*}
           & \nabla f(y)-\nabla f(x)+L(z^\star-y) =  0 \\ \Longrightarrow & z^\star = y - \frac{\nabla f(y)-\nabla f(x)}{L} 
        \end{align*}
        Substituting this value in \labelcref{eq:cocoercivity-bound-prelim} yields the desired bound
        \begin{align*}
            \phi_x(x) &\leq Q_{x,y}(z^\star) = \phi_x(y)+\inner{\nabla\phi_x(y)}{z^\star-y}+\frac{L}{2}\|z^\star-y\|^2\\
            &=\phi_x(y)+\inner{\nabla\phi_x(y)}{\left(y-\frac{\nabla f(y)-\nabla f(x)}{L}\right)-y}+\frac{L}{2}\left\|\left(y-\frac{\nabla f(y)-\nabla f(x)}{L}\right)-y\right\|^2\\
            &=\phi_x(y)+\inner{\nabla\phi_x(y)}{\frac{\nabla f(y)-\nabla f(x)}{L}}+\frac{L}{2}\left\|\frac{\nabla f(y)-\nabla f(x)}{L}\right\|^2\\
        \end{align*}
        Recall $\phi_x(y) = f(y)-\inner{\nabla f(x)}{y}$ and $\nabla \phi_x(y)=\nabla f(y)-\nabla f(x)$, so \begin{align*}
            f(x)-\inner{\nabla f(x)}{x} &\leq f(y)-\inner{\nabla f(x)}{y}+\frac{1}{L}\|\nabla f(y)-\nabla f(x)\|^2+\frac{1}{2L}\|\nabla f(y)-\nabla f(x)\|^2 \ .
        \end{align*}
        Rearranging yields $$f(y) \geq f(x)+\inner{ \nabla f(x)}{y-x}+\frac{1}{2L}\|\nabla f(y)-\nabla f(x)\|^2 \ .$$
        \item $v) \Longrightarrow vi)$: Swap the roles of $x$ and $y$ and add the inequalities.
        \item $vi) \Longrightarrow ii)$: Considering the bound in $iv)$ and Cauchy Schwarz inequality, $$\frac{1}{L}\|\nabla f(x)-\nabla f(y)\| \leq \inner{ \nabla f(x)-\nabla f(y)}{x-y} \leq \|x-y\|\|\nabla f(x)-\nabla f(y)\| \ .$$
        Multiplying both sides by $L$ and dividing by $\|\nabla f(x)-\nabla f(y)\|$ yields $$\|\nabla f(y)-\nabla f(y)\| \leq L\|x-y\| \ .$$
    \end{itemize}
\end{proof}
The missing part of the proof above uses the fact that $iv) \Longrightarrow iii)$ as well. The following exercise completes the proof. 
\begin{exercise}{}{}
    Suppose for $f : \R^n \to \R$ $$\inner{ \nabla f(x)-\nabla f(y)}{x-y} \leq L\|x-y\|^2, \quad \forall x,y \in \R^n \ .$$
    Show that $$f(y) \leq f(x) + \inner{ \nabla f(x)}{y-x}+\frac{L}{2}\|y-x\|^2\, \quad \forall x,y \in \R^n $$
    (hint: use fundamental theorem of calculus similar to the proof of \cref{convexity-characterizations}, except this time upper bound the inner product).
\end{exercise}
To summarize, the first two characterizations are how we defined $L$-smooth. The third and fourth handle upper bounding the function, either with a quadratic upper bound on the function itself or bounding the amount the gradients can change direction. The fifth and sixth bound handle the converse, bounding the function below (not by a quadratic in $x$, but by relating to the change in gradients) and the change in direction of the gradient. Combining the results, we get two two-way bounds (not symmetric, yet) stating $$f(x)+\inner{\nabla f(x)}{y-x}+\frac{1}{2L}\|\nabla f(x)-\nabla f(y)\|^2 \leq f(y) \leq f(x)+\inner{\nabla f(x)}{y-x}+\frac{L}{2}\|y-x\|^2$$
as well as $$\frac{1}{L}\|\nabla f(x)-\nabla f(y)\|^2 \leq \inner{ \nabla f(x)-\nabla f(y)}{x-y} \leq L\|x-y\|^2 \ .$$
We can then see, both of these results conclude $$\|\nabla f(x)-\nabla f(y)\|^2 \leq L^2\|y-x\|^2 \Longrightarrow \|\nabla f(x)-\nabla f(y)\| \leq L\|x-y\| \ ,$$
which is precisely the definition of $L$-smoothness.
Note that $L$-smooth functions are rather restrictive, but this will be useful for ensuring that gradient descent works well. 
\subsubsection{Equivalent Characterizations of Strongly Convex Functions}
We now explore a dual characteristic of $L$-smoothness. Here, we use the word dual for multiple reasons, some more complex and rich in theory than others. At the very least, we will see that the characterizations ``mimic'' those of $L$-smooth functions quite visually. That is, when a function is smooth and strongly convex, we will now see two-sided \textit{symmetric bounds}.

The proof of the following theorem is very similar to the previous, so we leave it without proof. However, note that some techniques need to be reversed. That is, we need to be careful (as always) with which way bounds go. That is, with Cauchy Schwarz for example, the inner products is bounded \textit{above} by the product of the norms. 
\begin{theo}[]{Equivalent Characterizations of Strongly Convex Functions}{}
      For differentiable $f : \R^n \to \R$ and any $x, y \in \R^n$, the following are equivalent
      \begin{enumerate}[i)]
          \item $f$ is $\mu$-strongly convex
          \item $f(y) \geq f(x) + \inner{\nabla f(x)}{y-x}+\frac{\mu}{2}\|y-x\|^2$
          \item $\inner{\nabla f(x)-\nabla f(y)}{x-y} \geq \mu\|x-y\|^2$
          \end{enumerate}
          \tcblower
          Furthermore, if $f$ is $\mu$-strongly convex, then the following hold
          \begin{enumerate}[a)]
              \item $f(y) \leq f(x) + \inner{ \nabla f(x)}{y-x}+\frac{1}{2\mu}\|\nabla f(x)-\nabla f(y)\|^2$
              \item $\inner{ \nabla f(x)-\nabla f(y)}{x-y} \leq \frac{1}{\mu}\|\nabla f(x)-\nabla f(y)\|^2$
              \item  $\|\nabla f(x)-\nabla f(y)\| \geq \mu \|y-x\|$
          \end{enumerate}
\end{theo}

We note that for a $\mu$-strongly convex function, similar two sides bound hold, but now the roles are reverse. Still, these bound aren't quite symmetric. That is, considering the monotonicity of the gradient $$\mu\|x-y\|^2 \leq \inner{ \nabla f(x)-\nabla f(y)}{x-y}\leq \frac{1}{\mu}\|\nabla f(x)-\nabla f(y)\|^2  \ ,$$
where on the left hand side, we consider the squared distance of the points $x$ and $y$, while the right hand side considers the squared distance of their gradients. Regardless, strongly convex functions are very useful. In particular, the always admit a unique global minimizer!
\begin{exercise}{}{}
    Suppose differentiable $f : \R^n \to \R$ is $\mu$-strongly convex. Suppose a minimizer exists, show that it is unique. 
\end{exercise}

It will turn out that the class of functions we really would benefit from are those possessing both qualities. In this case, we get symmetric bounds \begin{equation}\label{eq:two-sided-bound-smooth-SC}
    f(x)+\inner{ \nabla f(x)}{y-x}+\frac{\mu}{2}\|y-x\|^2 \leq f(y) \leq f(x) + \inner{ f(x)}{y-x}+\frac{L}{2}\|y-x\|^2 \ .
\end{equation}
We will see soon how to leverage this fact. 
\subsubsection{Properties of Smooth and Strongly Convex Functions}
The below exercises demonstrate the many properties of smooth and strong convex functions. When $f$ is convex and both $L$-smooth and $\mu$-strongly convex, we denoted $f \in \mathscr{F}_{L,\mu}(\R^n)$.
\begin{exercise}{}{}
    Suppose $f_1$ is $L_1$-smooth and $f_2$ is $L_2$-smooth. Is $f_1+f_2$ smooth? If so, what is the value of the Lipschitz constant?
\end{exercise}

\begin{exercise}{}{}
    Suppose $f_1$ is $\mu$-strongly convex and $f_2$ is $L_2$-strongly convex. Is $f_1+f_2$ strongly convex? If so, what is the value of the modulus (i.e. $f_1$ has modulus $\mu_1$)?
\end{exercise}

\begin{exercise}{}{}
    Suppose $f$ is $L$-smooth and $\mu$-strongly convex. Show that $\mu \leq L$.
\end{exercise}

\begin{exercise}{}{}
    What class of functions attain equality. That is, what functions are $L$-smooth and $\mu$-strongly convex with $L=\mu$?
\end{exercise}

\begin{exercise}{}{}
     Suppose $f$ is $L$-smooth and $\mu$-strongly convex. Show that $\phi(x) = f(x)-\frac{\mu}{2}\|x\|^2$ is convex and $(L-\mu)$-smooth.
\end{exercise}

\begin{exercise}[label = {strengthened-monotonicity-result}]{}{}
    Suppose $f$ is $L$-smooth and $\mu$-strongly convex. Show that the bound for the monotonicity for the gradient can be tightened $$\inner{ \nabla f(x)-\nabla f(y)}{x-y} \geq \frac{\mu L}{\mu+L}\|x-y\|^2 + \frac{1}{\mu+L}\|\nabla f(x)-\nabla f(y)\|^2 \ .$$
    It will be useful to consider the function $\phi(x)=f(x)-\frac{\mu}{2}\|x\|^2$ and the previous exercise. 
\end{exercise}

\subsection{Proofs for Gradient Descent Convergence Guarantees}
We finally now have the tools to present the performance of gradient descent applied to the problem $$\min_{x \in \R^n} f(x)$$
with $f \in \mathscr{F}_L(\R^n),$ the set of convex and $L$-smooth functions. Recall the method below.
\begin{algo*}{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*}

In this section, we only consider the constant step size $h_k=h > 0$, but it is possible to show that different schemes exhibit similar rates of convergence. Denote $x^\star$ as an optimal point, with $f^\star = f(x^\star)$. 
\begin{theo}{Convergence Guarantees for Smooth and Convex Functions}{Adapted from Theorem 2.1.14 from \cite{nesterov_lectures}}
Let $f \in \mathscr{F}_L(\R^n)$ and $0 < h < \frac{2}{L}$. Then the iterations of gradient descent $\{x^k\}$, with corresponding function values satisfy $$f(x^k)-f^\star \leq \frac{2(f(x^0)-f^\star)\|x^0-x^\star\|^2}{2L\|x^0-x^\star\|^2+kh(2-Lh)(f(x^0)-f(x^\star))}, \quad \forall k \geq 0.$$
\end{theo}

The proof of this will be the most technical one we've seen so far, combining many characteristics of convex and smooth functions. The following is aimed to be as digestible as possible, but it still may take a few read-throughs to fully understand. Regardless, the above theorem states that the suboptimality gap decreases at a \textit{sublinear} rate of order $\mathcal{O}(1/k)$. That is, in the long run, the distance to optimal looks at most, inversely proportional to the number of steps taken. This turns out to be far from optimal, in which a modified version of gradient descent can achieve a rate of $\mathcal{O}(1/k^2)$, implying that the distance to optimal is proportional to the \textit{squared} number of iterates. 
\begin{proof}
    Let $r_k = \|x^k-x^\star\|$. Then \begin{align*}
        r_{k+1}^2 &= \|x^{k+1}-x^\star\|^2\\
        &= \|x^k - h \nabla f(x^k)-x^\star\|^2\\
        &= \|x^k-x^\star\|^2 - 2h\inner{\nabla f(x^k)}{x^k-x^\star}+h^2\|\nabla f(x^k)\|^2\\
        &= \|x^k-x^\star\|^2 - 2h\inner{\nabla f(x^k)-\nabla f(x^\star)}{x^k-x^\star}+h^2\|\nabla f(x^k)\|^2\\
        &\leq \|x^k-x^\star\|^2-\frac{2h}{L}\|\nabla f(x^k)-\nabla f(x^\star)\|^2+h^2\|\nabla f(x^k)\|^2\\
        &= r_k^2 - h\left(\frac{2}{L}-h\right)\|\nabla f(x^k)\|^2 \,
    \end{align*}
    where we use the gradient step in the first equality, we ``FOIL'' in the next equality, we add $\nabla f(x^\star)=0$ in the next equality, we apply the ``lower bounded monotonicity'' from $vi)$ in \cref{equiv_char_smooth}, and we conclude by simplfying the algebra and again noting that $\nabla f(x^\star)=0$. Notably $r_0 \geq r_1 \geq ... \geq r_k$ for all $k \geq 0$.
    
    Considering  \cref{descent-lemma}, we recall the ``upper bounding quadratic'' nature of smooth functions to note that \begin{align*}
        f(x^{k+1}) & \leq f(x^k) + \inner{\nabla f(x^k)}{x^{k+1}-x^k}+\frac{L}{2}\|x^{k+1}-x^k\|^2\\
        &= f(x^k) - \omega \|\nabla f(x^k)\|^2 \ ,
    \end{align*}
    where $\omega = h\left(1-\frac{L} {2}h\right)$. Then by convexity and Cauchy-Schwarz, $$\underbrace{f(x^k)-f^\star}_{\Delta_k} \leq \inner{\nabla f(x^k)}{x^k-x^\star} \leq \|\nabla f(x^k)\|\|x^k-x^\star\| \leq r_0\|\nabla f(x^k)\| \ ,$$ where we recall $r_0 \geq r_k = \|x^k-x^\star\|$.
    Considering the above inequalities (subtracting $f^\star$ on both sides, we conclude $$\underbrace{f(x^{k+1})-f^\star}_{\Delta_{k+1}} \leq \underbrace{f(x^k)-f^\star}_{\Delta_k}-\omega\|\nabla f(x^k)\|^2 \leq \Delta_k - \frac{\omega}{r_0^2}\Delta_k^2 \ .$$
    Rearranging (and dividing by $\frac{1}{\Delta_k\Delta_{k+1}}$) yields the recurrence $$\frac{1}{\Delta_{k+1}} \geq \frac{1}{\Delta_k}-\frac{\omega}{r_0^2}\cdot \frac{\Delta_k}{\Delta_{k+1}} \geq \frac{1}{\Delta_k}+\frac{\omega}{r_0^2} \ ,$$
    where the last inequality uses the fact that $\Delta_k$ is non-increasing (from the descent lemma). Summing up all the inequalities, we again get a string of telescoping cancellations, and conclude that $$\frac{1}{\Delta_{k+1}} \geq \frac{1}{\Delta_0}+\frac{\omega}{r_0^2}(k+1) \ .$$
    Considering $\Delta_{k+1}=f(x^{k+1})-f^\star$, $\Delta_0= f(x^0)-f^\star$, $r_0 = \|x^0-x^\star\|$, and $\omega = h\left(1-\frac{L}{2}h\right) $, all we need to do is rearrange the expression to conclude  $$f(x^k)-f^\star \leq \frac{2(f(x^0)-f^\star)\|x^0-x^\star\|^2}{2L\|x^0-x^\star\|^2+kh(2-Lh)(f(x^0)-f(x^\star))} \ ,$$
    where we are looking at iterate $k$ for simplicity.
\end{proof}
    Recall that we can maximize the amount of decrease each gradient step by setting $$h = \frac{1}{L} , $$ and we can further note that $$f(x^0)-f^* \leq \frac{L}{2}\|x^0-x^\star\|^2$$ by the descent lemma (again) and noting that $\nabla f(x^\star)=0$ (again). Therefore, we can greatly simplify the expression above. Simply plugging in $h=\frac{1}{L}$ and bounding $\|x^0-x^\star\|^2 \geq \frac{2}{L}(f(x^0)-f(x^\star))$ in the convergence guarantee, we prove the following corollary.  
    \begin{cor}[label = {cor:GD-smooth}]{}{}
        If $h_k = h = \frac{1}{L}$ and $f \in \mathscr{F}_L(\R^n)$, then $$f(x^k) - f^\star \leq \frac{2L \|x^0-x^\star\|^2}{k+4} $$
    \end{cor}

    We can now turn our attention to that of smooth \textit{and strongly convex} functions. Recall that a consequence of $f : \R^n \to \R$ being $L$-smooth and $\mu$-strongly convex is the two sided bound $$f(x)+\inner{\nabla f(x)}{y-x}+\frac{\mu}{2}\|y-x\|^2 \leq f(y) \leq f(x)+\inner{\nabla f(x)}{y-x}+\frac{L}{2}\|y-x\|^2 . $$
    We can then leverage these bounds against each other. Notably, it can be shown that every $\frac{8L}{\mu}-4$ iterations of gradient descent with \textit{halve} the function gap. 
    \begin{exercise}{}{}
        Suppose $f \in \mathscr{F}_{L,\mu}(\R^n)$ (i.e., $f$ is $L$-smooth and $\mu$-strongly convex). Suppose $f(x^0)-f^\star \leq R$. Show that after $k=\frac{8L}{\mu}-4$ iterations $f(x^k)-f^\star \leq \frac{R}{2}$. Conclude that  $$f(x^N)-f^\star \leq \eps$$for any $N \geq \left(\frac{8L}{\mu}-4\right)\log_2\left(\frac{R}{\eps}\right)$ (hint. use \cref{cor:GD-smooth} and bound $\|x^0-x^\star\|$ w.r.t. $R$).
    \end{exercise}
    For a more explicit (and classical) convergence guarantee that doesn't require an inductive arguement we move to the following theorem.
    \begin{theo}{}{}
        Let $f \in \mathscr{F}_{L,\mu}(\R^n)$ and $0 < h \leq \frac{2}{\mu+L}$. The the iterations of gradient descent $\{x^k\}$, with corresponding function values satisfy $$\|x^k-x^\star\|^2 \leq \left(1-\frac{2h\mu L}{\mu+L}\right)^k\|x^0-x^\star\|^2 \ .$$
        If $h = \frac{2}{\mu+L}$ then the following hold for all $k \geq 0$ \begin{align*}
            \|x^k-x^\star\|^2 &\leq \left(\frac{L-\mu}{L+\mu}\right)^{2k}\|x^0-x^\star\|^2\\
            f(x^k)-f^\star &\leq \frac{L}{2}\left(\frac{L-\mu}{L+\mu}\right)^{2k}\|x^0-x^\star\|^2\\
            f(x^k)-f^\star &\leq \frac{L}{\mu}\left(\frac{L-\mu}{L+\mu}\right)^{2k}(f(x^0)-f^\star)
        \end{align*}
    \end{theo}
\begin{proof}
    Let $r_k = \|x^k-x^\star\|$. Then \begin{align*}
        r_{k+1}^2 &= \|x^k-h\nabla f(x^k)-x^\star\|^2\\
        &= r_k^2-2h\inner{\nabla f(x^k)}{x^k-x^\star}+h^2\|\nabla f(x^k)\|^2\\
        &= r_k^2-2h\inner{\nabla f(x^k)-\nabla f(x^\star)}{x^k-x^\star}+h^2\|\nabla f(x^k)\|^2\\
        &\leq r_k^2-2h\left[\frac{\mu L}{\mu+L}\|x^k-x^\star\|^2+\frac{1}{\mu+L}\|\nabla f(x^k)-\nabla f(x^\star)\|^2\right]+h^2\|\nabla f(x^k)\|^2\\
        &=\left(1-\frac{2h \mu L}{\mu+L}\right)r_k^2-h\left(\frac{2}{\mu+L}-h\right)\|\nabla f(x^k)\|^2 \ ,
    \end{align*}
    where we utilize similar technique to the prove of the smooth convergence guarantee, while also utilizing the strengthened result from \cref{strengthened-monotonicity-result}. We note that $h \leq \frac{2}{\mu+L}$ to achieve our first result, and the rest follow immediately from $\nabla f(x^\star)=0$ and the upper and lower quadratic bounds.
\end{proof}
    \begin{remark}{}{}
        Often the ratio between the smoothness and strong convexity parameters is useful to consider. As shown early, if a function is $L$-smooth and $\mu$-strongly convex, then $L \geq \mu$, so $Q_f := L/\mu \geq 1$. We can reformulate our convergence guarantees with this value instead
        \begin{align*}
            \|x^k-x^\star\|^2 &\leq \left(\frac{Q_f-1}{Q_f+1}\right)^{2k}\|x^0-x^\star\|^2\\
            f(x^k)-f^\star &\leq \frac{L}{2}\left(\frac{Q_f-1}{Q_f+1}\right)^{2k}\|x^0-x^\star\|^2\\
            f(x^k)-f^\star &\leq Q_f\left(\frac{Q_f-1}{Q_f+1}\right)^{2k}(f(x^0)-f^\star)
        \end{align*}
    \end{remark}