


\section{Introduction} \label{section-introduction}
\input{section/introduction}

\section{Gradient Descent} \label{section-gradient-descent}
\input{section/gradient-descent}

\section{Global Convergence Analysis without Summability} \label{section-no-summable}
\input{section/global-convergence-no-sum}

\section{Global Convergence Analysis with Summability} \label{section-summable}
\input{section/global-convergence-sum}

\section{An Example for Divergence} \label{section-divergence-example}
\input{section/divergence-example}

\section{Spuriousness of the Continuous Approximation} \label{section-continuous-approximation}
\input{section/continuous-approximation}

\section{Conclusion}
\label{section-conclusion}
\input{section/conclusion}


\bibliographystyle{siamplain}


\section{A detailed example}

Here we include some equations and theorem-like environments to show
how these are labeled in a supplement and can be referenced from the
main text.
Consider the following equation:
\begin{equation}
  \label{eq:suppa}
  a^2 + b^2 = c^2.
\end{equation}
You can also reference equations such as \cref{eq:matrices,eq:bb} 
from the main article in this supplement.

\lipsum[100-101]

\begin{theorem}
An example theorem.
\end{theorem}

\lipsum[102]
 
\begin{lemma}
An example lemma.
\end{lemma}

\lipsum[103-105]

Here is an example citation: \cite{KoMa14}.

\section[Proof of Thm]{Proof of \cref{thm:bigthm}}
\label{sec:proof}

\lipsum[106-112]

\section{Additional experimental results}
\Cref{tab:foo} shows additional
supporting evidence. 

\begin{table}[htbp]
\footnotesize
  \caption{Example table.}  \label{tab:smfoo}
\begin{center}
  \begin{tabular}{|c|c|c|} \hline
   Species & \bf Mean & \bf Std.~Dev. \\ \hline
    1 & 3.4 & 1.2 \\
    2 & 5.4 & 0.6 \\ \hline
  \end{tabular}
\end{center}
\end{table}


\bibliographystyle{siamplain}

\subsection{A Recursive Relationship for the Optimality Gap} \label{subsection-recursion-gap}

In order to establish a recursive relationship for the optimality gap between two sequential iterates, we study the behavior of the iterates prior to a stopping time. To define this stopping time, first let
\begin{equation}
\chi_{k}^z (R) = \begin{cases}
1 & \inlinenorm{ x_j - z }_2 \leq R,~ \forall j \leq k \\
0 & \text{otherwise},
\end{cases}
\end{equation}
where $k \in \mathbb{N}$; $R > 0$; and $z \in \mathbb{R}^p$. That is, $\chi_k^z(R)$ is one if all iterates up to $k$ remain with a radius $R$ of the point $z \in \mathbb{R}^p$, and is zero thereafter. Thus, $\lbrace \chi_k^z(R) \rbrace$ implicitly define a stopping time: the iterate at which $\chi_k^z(R)$ stops being $1$ (note, this iterate could be $k=0$).


To understand how $\chi_k^{z}(R)$ will be used, consider what happens if $\chi_k^z(R) = 1$ for all $k +1 \in \mathbb{N}$, for some $z\in\mathbb{R}^p$, and for some $R > 0$. Then, \cref{assumption-gradient} would imply that there is a universal Lipschitz constant for the gradient and we can proceed with the standard analysis to show that the gradient function goes to zero~\cite{zoutendijk1960}. However, owing to the loss of monotonic decay of the objective function and boundedness of level sets, we cannot guarantee that $\chi_k^z(R) = 1$ for all $ k + 1 \in \mathbb{N}$ and any $R > 0$ or any $z \in \mathbb{R}^p$; thus, we have no simple way of controlling the Lipschitz constant. To account for this, rather than establishing a relationship between $F(x_{k+1}) - F_{l.b.}$ and $F(x_k) - F_{l.b.}$, we establish a relationship between $[F(x_{k+1}) - F_{l.b.}]\chi_{k+1}^0(R)$ and $[F(x_k) - F_{l.b.}]\chi_{k}^0(R)$, which requires a careful proof.


\begin{lemma} \label{result-recursion-gap}
Suppose $F:\mathbb{R}^p \to \mathbb{R}$ satisfies \cref{assumption-lower-bound,assumption-gradient}. Let $x_0 \in \mathbb{R}^p$ and let $\lbrace x_k : k \in \mathbb{N} \rbrace$ be generated by \cref{eqn-recursion-iterate} satisfying \cref{property-spd}. Then, for all $ R \geq 0$ there exists a constant $C_R > 0$ such that
\begin{equation*}
[F(x_{k+1}) - F_{l.b.}]\chi_{k+1}^0(R) \leq \left[F(x_k) - F_{l.b.} - \dot F(x_k)^\intercal M_k \dot F(x_k) + C_R \norm{ M_k \dot F(x_k)}_2^2\right]\chi_{k}^0(R). 
\end{equation*}
\end{lemma}
\begin{proof}
First, for any $R \geq 0$ define $L_R$ to be the Lipschitz constant for the gradient in the closed ball of radius $R$ around the point $0 \in \mathbb{R}^p$, which is well defined by \cref{assumption-gradient}. It readily follows that $L_R \leq L_{R+1}$. Second, let $L(x,y)$ be the Lipschitz constant for the gradient in a closed ball of radius $\inlinenorm{ x - y}_2$ around the point $y$. Finally, for any $R \geq 0$, define $G_R$ to be the maximum  $\inlinenorm{ \dot F(x)}_2$ for all $x$ in a closed ball of radius $R$ around the point $0 \in \mathbb{R}^p$.

By Taylor's remainder theorem,
\begin{equation*}
\begin{aligned}
F(x_{k+1}) - F_{l.b.} &= F(x_k) - F_{l.b.} + \dot F(x_k)^\intercal (x_{k+1} - x_k) \\
&\quad + \int_0^1 \left[ \dot F(x_k + t(x_{k+1} - x_k)) - \dot F(x_k) \right]^\intercal (x_{k+1} - x_k) dt.
\end{aligned}
\end{equation*}
By applying \cref{assumption-gradient} to the last term and substituting $x_{k+1} - x_k$ with \cref{eqn-recursion-iterate},
\begin{equation}\label{eqn-no-lipschitz-control}
\begin{aligned}
    F(x_{k+1}) - F_{l.b.} &\leq F(x_k) - F_{l.b.} + \dot F(x_k)^\intercal (x_{k+1} - x_k) + \frac{L(x_{k+1},x_k)}{2} \norm{ x_{k+1} - x_k}_2^2\\
    &= F(x_k) - F_{l.b.} - \dot F(x_k)^\intercal M_k \dot F(x_k) + \frac{L(x_{k+1},x_k)}{2} \norm{M_k \dot F(x_k)}_2^2.
\end{aligned}
\end{equation}
Note, to understand why we must keep going at this point in the proof, see \cref{discussion-no-lipschitz-control}. We now introduce $\chi_{k+1}^0(R)$ into \cref{eqn-no-lipschitz-control}. That is,
\begin{equation*}
\begin{aligned}
&[F(x_{k+1}) - F_{l.b.}] \chi_{k+1}^0(R) \\
&\quad \leq \left[F(x_k) - F_{l.b.} - \dot F(x_k)^\intercal M_k \dot F(x_k) + \frac{L(x_{k+1},x_k)}{2} \norm{M_k \dot F(x_k)}_2^2\right] \chi_{k+1}^0(R).
\end{aligned}
\end{equation*}
If $\chi_{k+1}^0(R) = 1$, then $\inlinenorm{x_{k+1}}_2 \leq R$ and $\inlinenorm{x_k}_2 \leq R$. Thus, $L(x_{k+1},x_k) \leq L_R \leq L_{R+1}$. When $\chi_{k+1}^0(R) = 0$, then both sides are trivially zero. Therefore,
\begin{equation*}
\begin{aligned}
&[F(x_{k+1}) - F_{l.b.}] \chi_{k+1}^0(R) \\
& \quad \leq \left[F(x_k) - F_{l.b.} - \dot F(x_k)^\intercal M_k \dot F(x_k) + \frac{L_{R+1}}{2} \norm{M_k \dot F(x_k)}_2^2\right] \chi_{k+1}^0(R).
\end{aligned}
\end{equation*}
However, we want $\chi_{k}^0(R)$ on the right hand side. So, we simply add and subtract $\chi_{k}^0(R)$ and then study the difference term. That is,
\begin{equation} \label{eqn-add-subtract-event}
\begin{aligned}
&[F(x_{k+1}) - F_{l.b.}] \chi_{k+1}^0(R) \\
&\quad \leq \left[F(x_k) - F_{l.b.} - \dot F(x_k)^\intercal M_k \dot F(x_k) + \frac{L_{R+1}}{2} \norm{M_k \dot F(x_k)}_2^2\right] \chi_{k}^0(R) \\
&\qquad  + \left[F(x_k) - F_{l.b.} - \dot F(x_k)^\intercal M_k \dot F(x_k) + \frac{L_{R+1}}{2} \norm{M_k \dot F(x_k)}_2^2\right] [\chi_{k+1}^0(R) - \chi_{k}^0(R)].
\end{aligned}
\end{equation}
We now have two cases to upper bound the last term of \cref{eqn-add-subtract-event}.
\paragraph{Case 1} Since $\chi_{k+1}^0(R) \leq \chi_{k}^0(R)$, if
\begin{equation*}
F(x_k) - F_{l.b.} - \dot F(x_k)^\intercal M_k \dot F(x_k) + \frac{L_{R+1}}{2} \norm{M_k \dot F(x_k)}_2^2 > 0,
\end{equation*}
then
\begin{equation*}
\left[F(x_k) - F_{l.b.} - \dot F(x_k)^\intercal M_k \dot F(x_k) + \frac{L_{R+1}}{2} \norm{M_k \dot F(x_k)}_2^2\right] [\chi_{k+1}^0(R) - \chi_{k}^0(R)] \leq 0.
\end{equation*}
Hence, in this case, we can upper bound the last term in \cref{eqn-add-subtract-event} by any non-negative term.
\paragraph{Case 2} If
\begin{equation} \label{eqn-add-subtrct-event-case-2}
F(x_k) - F_{l.b.} - \dot F(x_k)^\intercal M_k \dot F(x_k) + \frac{L_{R+1}}{2} \norm{M_k \dot F(x_k)}_2^2 \leq 0,
\end{equation}
then, since $\chi_{k+1}^0(R) \leq \chi_{k}^0(R)$,
\begin{equation*}
\left[F(x_k) - F_{l.b.} - \dot F(x_k)^\intercal M_k \dot F(x_k) + \frac{L_{R+1}}{2} \norm{M_k \dot F(x_k)}_2^2\right] [\chi_{k+1}^0(R) - \chi_{k}^0(R)] \geq 0.
\end{equation*}
Thus, we need only find a lower bound for the first term in the product to upper bound the entire term. Specifically, 
\begin{equation*}
- \norm{ \dot F(x_k)}_2 \norm{ M_k \dot F(x_k)}_2 \leq F(x_k) - F_{l.b.} - \dot F(x_k)^\intercal M_k \dot F(x_k) + \frac{L_{R+1}}{2} \norm{M_k \dot F(x_k)}_2^2.
\end{equation*}
Now, when $\chi_{k+1}^0(R) < \chi_k^0(R)$, $\inlinenorm{x_k}_2 \leq R$. Moreover, \cref{eqn-add-subtrct-event-case-2} is only true if $R+1 \leq \inlinenorm{ x_{k+1}}_2$. Using \cref{eqn-recursion-iterate} and the triangle inequality, $R+1 \leq \inlinenorm{x_k}_2 + \inlinenorm{M_k \dot F(x_k)}_2 \leq R + \inlinenorm{M_k \dot F(x_k)}_2$. That is, $1 \leq \inlinenorm{ M_k \dot F(x_k)}_2 \leq \inlinenorm{ M_k \dot F(x_k)}_2^2$.

Hence,
\begin{align*}
&\left[F(x_k) - F_{l.b.} - \dot F(x_k)^\intercal M_k \dot F(x_k) + \frac{L_{R+1}}{2} \norm{M_k \dot F(x_k)}_2^2\right] [\chi_{k+1}^0(R) - \chi_{k}^0(R)] \nonumber \\
 & \quad \leq \norm{\dot F(x_k)}_2 \norm{ M_k \dot F(x_k)}_2^2 \left[ \chi_{k}^0(R) - \chi_{k+1}^0(R)\right] \\
 & \quad \leq G_R  \norm{ M_k \dot F(x_k)}_2^2 \chi_{k}^0(R).
\end{align*}

Putting these two cases together in \cref{eqn-add-subtract-event}, we conclude,
\begin{equation*}
\begin{aligned}
&[F(x_{k+1}) - F_{l.b.}] \chi_{k+1}^0(R) \\
 &\quad \leq \left[F(x_k) - F_{l.b.} - \dot F(x_k)^\intercal M_k \dot F(x_k) + \left(\frac{L_{R+1}}{2} + G_R \right) \norm{M_k \dot F(x_k)}_2^2\right] \chi_{k}^0(R).
\end{aligned}
\end{equation*}
Letting $C_R = L_{R+1}/2 + G_R$, the conclusion follows.
\end{proof}

If \cref{property-diminishing} holds, then we can simplify \cref{result-recursion-gap} as follows.

\begin{corollary} \label{result-recursion-gap-simplified}
Suppose the conditions of \cref{result-recursion-gap} hold. If \cref{property-diminishing} holds, then there exists $ K \in \mathbb{N}$ such that for all $k \geq K$, 
\begin{equation*}
[F(x_{k+1}) - F_{l.b.}]\chi_{k+1}^0(R) \leq \left[F(x_k) - F_{l.b.} - \frac{1}{2}\lambda_{\min}(M_k) \norm{\dot F(x_k)}_2^2 \right]\chi_{k}^0(R).
\end{equation*}
\end{corollary}
\begin{proof}
From \cref{result-recursion-gap}, we need to show that $\exists K \in \mathbb{N}$ such that $\forall k \geq K$, 
\begin{equation} \label{eqn-recursion-gap-simplified-sufficient}
- \dot F(x_k)^\intercal M_k \dot F(x_k) + C_R \norm{ M_k \dot F(x_k)}_2^2 \leq -\frac{1}{2} \lambda_{\min}(M_k) \norm{ \dot F(x_k)}_2^2.
\end{equation}
To this end, we prove, if $M$ is symmetric positive definite with $\lambda_{\max}(M) < 2/C_R$ then
\begin{equation*}
\max_{ v : \inlinenorm{v}_2 = 1} - v^\intercal M v + C_R v^\intercal MM v \leq - \frac{1}{2} \lambda_{\min}(M).
\end{equation*}
Let $0 < \lambda_{\min}(M) = \lambda_p \leq \lambda_{p-1} \leq \cdots \leq \lambda_2 \leq \lambda_1 = \lambda_{\max}(M) < 2/C_R$. Using the Schur Decomposition, there exists an orthogonal matrix $Q$ such that
\begin{equation*}
- v^\intercal M v + C_R v^\intercal MM v = \sum_{\ell=1}^p ( - \lambda_\ell + C_R \lambda_{\ell}^2 ) w_\ell^2,
\end{equation*}
where $w_\ell$ is the $\ell^\mathrm{th}$ component of $Qv$ (note, $\inlinenorm{w}_2 = \inlinenorm{Qv}_2 = \inlinenorm{v}_2 = 1$). Since $\lambda_{\ell} < 2/C_R$, it follows that $C_R \lambda_{\ell}^2 < \lambda_{\ell}/2$. Subtracting $\lambda_{\ell}$ from both sides, $-\lambda_{\ell} + C_R \lambda_{\ell}^2 < - \lambda_{\ell}/2 \leq -\lambda_{\min}(M)/2$. Thus,
\begin{equation*}
- v^\intercal M v + C_R v^\intercal MM v \leq - \lambda_{\min}(M)/2 \sum_{\ell=1}^p w_\ell^2 = - \lambda_{\min}(M)/2.
\end{equation*}
Since $\lambda_{\max}(M_k) \to 0$, there exists a $K \in \mathbb{N}$ such that $\forall k \geq K$, \cref{eqn-recursion-gap-simplified-sufficient} holds.
\end{proof}

\subsection{Applying Zoutendjik's Analysis Approach} \label{subsection-zoutendjik}

We now apply the recursive relationship established in \cref{result-recursion-gap-simplified} to study the gradient using Zoutendjik's analysis method \cite{zoutendijk1960}. As a minor bonus, we also add a statement about the behavior of the optimality gap.

\begin{theorem} \label{result-zoutendjik}
Suppose $F:\mathbb{R}^p \to \mathbb{R}$ satisfies \cref{assumption-lower-bound,assumption-gradient}. Let $x_0 \in \mathbb{R}^p$ and let $\lbrace x_k : k \in \mathbb{N} \rbrace$ be generated by \cref{eqn-recursion-iterate} satisfying \cref{property-spd,property-diverge,property-diminishing}. Then, for all $ R \geq 0$,
\begin{equation}
\lim_{k \to \infty} F(x_k)\chi_k^0(R) ~\text{exists and is finite, and}~
\liminf_{k \to \infty} \norm{ \dot F(x_k) }_2 \chi_k^0(R) = 0.
\end{equation}
If $\sup_{k} \inlinenorm{ x_k}_2 < \infty$ then $\lim_{k \to \infty} F(x_k)$ exists and is finite, and $\liminf_{k \to \infty} \inlinenorm{ \dot F(x_k) }_2 = 0$.
\end{theorem}
\begin{proof}
Let $R \geq 0$. The hypotheses of \cref{result-recursion-gap-simplified} are satisfied, and its conclusion is used freely herein. For the objective function, $\exists K \in \mathbb{N}$ such that for all $k \geq K$, $[ F(x_{k+1}) - F_{l.b.} ] \chi_{k+1}^0(R) \leq [F(x_k) - F_{l.b.}] \chi_k^0(R)$. As $\lbrace [ F(x_k) - F_{l.b.} ] \chi_k^0(R) : k \geq K \rbrace$ is a nonincreasing sequence bounded from below, it converges. Now, if we further assume that $\sup_k \inlinenorm{x_k}_2 < \infty$, then there exists an $R > 0$ such that $\chi_k^0(R) = 1$ $\forall k+1 \in \mathbb{N}$. Hence, $\lim_{k \to \infty} F(x_k) - F_{l.b.}$ exists and is finite.

For the gradient function, applying the conclusion of \cref{result-recursion-gap-simplified} and rearranging terms, for all $k \geq K$,
\begin{equation*}
\frac{1}{2}\lambda_{\min}(M_k) \norm{ \dot F(x_k) }_2^2 \chi_k^0(R) \leq [F(x_{k}) - F_{l.b.}] \chi_{k}^0(R) - [ F(x_{k+1}) - F_{l.b.} ] \chi_{k+1}^0(R).
\end{equation*}
Letting $j \geq K$ and using $F(x_{j+1}) - F_{l.b.} \geq 0$, 
\begin{equation} \label{eqn-zoutendjik-telescoping-sum}
\sum_{k=K}^j \frac{1}{2}\lambda_{\min}(M_k) \norm{ \dot F(x_k) }_2^2 \chi_k^0(R) \leq [F(x_{K}) - F_{l.b.}] \chi_{K}^0(R).
\end{equation}
Now for a contradiction, suppose $\exists \; c > 0$ such that $\liminf_{k \to \infty} \inlinenorm{ \dot F(x_k)}_2^2 \chi_k^0(R) > c$. Then, there exists a $K' > K$ such that 
\begin{equation*}
\frac{c}{2} \sum_{k=K'}^j \lambda_{\min}(M_k) \leq \sum_{k=K'}^j \frac{1}{2}\lambda_{\min}(M_k) \norm{ \dot F(x_k) }_2^2 \chi_k^0(R) \leq [F(x_{K}) - F_{l.b.}] \chi_{K}^0(R) < \infty.
\end{equation*}
By \cref{property-diverge}, we have a contradiction. This part of the result follows for any $R \geq 0$.

Now, if $\sup_{k} \inlinenorm{x_k}_2 < \infty$ then there exists an $R > 0$ such that $\sup_{k} \inlinenorm{ x_k}_2 < R$. Therefore, $\chi_k^0(R) = 1$ for all $k+1 \in \mathbb{N}$, and, thus, the final part of the result follows.
\end{proof}

\begin{remark} \label{discussion-no-lipschitz-control}
Suppose we directly attempt to use Zoutendjik's analysis approach in \cref{eqn-no-lipschitz-control}. We begin by rearranging \cref{eqn-no-lipschitz-control} and summing up to $j \in \mathbb{N}$ to conclude,
\begin{equation*}
\sum_{k=0}^j \dot F(x_k)^\intercal M_k \dot F(x_k) - \frac{L(x_{k+1},x_k)}{2} \norm{M_k \dot F(x_k)}_2^2 \leq  F(x_0) - F_{l.b.}.
\end{equation*}
Thus, we conclude
\begin{equation*}
\lim_{k \to \infty} \dot F(x_k)^\intercal M_k \dot F(x_k) - \frac{L(x_{k+1},x_k)}{2} \norm{M_k \dot F(x_k)}_2^2 = 0.
\end{equation*}
Unfortunately, this conclusion does not imply that $\dot F(x_k) \to 0$ as $k \to 0$. For instance, suppose as $k \to \infty$, $L(x_{k+1},x_k) \to \infty$. If $M_k = 2L(x_{k+1},x_k)^{-1} I$ for all $k$, then a straightforward substitution will show that the limit is satisfied yet $\dot F(x_k)$ does not have to be zero. Hence, using Zoutendjik's analysis method on this line of logic would not produce the desired conclusion. However, as shown in \cref{result-zoutendjik}, using Zoutendjik's analysis method on the conclusion of \cref{result-recursion-gap} is fruitful.
\end{remark}

\subsection{Convergence of the Gradient}

One of the limitations of \cref{result-zoutendjik} is that it only states that the limit infimum of the gradient function goes to zero. By using \cref{property-summable} in place of \cref{property-diminishing}, we can show that the limit supremum agrees with the limit infimum, which we establish in the next result. 

\begin{theorem} \label{result-gradient-convergence}
Suppose $F:\mathbb{R}^p \to \mathbb{R}$ satisfies \cref{assumption-lower-bound,assumption-gradient}. Let $x_0 \in \mathbb{R}^p$ and let $\lbrace x_k : k \in \mathbb{N} \rbrace$ be generated by \cref{eqn-recursion-iterate} satisfying \cref{property-spd,property-diverge,property-summable}. Then, for all $ R \geq 0$,
\begin{equation}
\lim_{k \to \infty} \norm{ \dot F(x_k) }_2 \chi_k^0(R) = 0.
\end{equation}
Moreover, if $\sup_{k} \inlinenorm{ x_k}_2 < \infty$ then $\lim_{k \to \infty} \inlinenorm{ \dot F(x_k) }_2 = 0$.
\end{theorem}
\begin{proof}
By \cref{result-zoutendjik}, for every $R \geq 0$, $\liminf_{k} \inlinenorm{ \dot F(x_k) }_2 \chi_k^0(R) = 0$. For a contradiction, suppose $\exists \  \delta > 0$ such that $\limsup_{k} \inlinenorm{ \dot F(x_k) }_2 \chi_k^0(R) > \delta$. Then, for some $\gamma > 0$ sufficiently small, there exists a subsequence $\lbrace k_j : j \in \mathbb{N} \rbrace \subset \mathbb{N}$ such that $\inlinenorm{ \dot F(x_{k_j+1})}_2 \chi_{k_j+1}^0(R) \geq \delta + \gamma$ while $\inlinenorm{ \dot F(x_{k_j})}_2 \chi_{k_j}^0(R) \leq \delta$. Thus,
\begin{align*}
\delta + \gamma &\leq \norm{ \dot F(x_{k_j+1})}_2 \chi_{k_j+1}^0(R) \\
			   &\leq \norm{ \dot F(x_{k_j+1}) - \dot F(x_{k_j})}_2 \chi_{k_j+1}^0(R) + \norm{ \dot F(x_{k_j} }_2 \chi_{k_j+1}^0(R) \\
			   &\leq L(x_{k_j+1},x_{k_j}) \norm{ x_{k_j+1} - x_{k_j}}_2 \chi_{k_j + 1}^0(R) + \norm{ \dot F(x_{k_j})}_2 \chi_{k_j}^0(R) \\
			   &\leq L_R \norm{ M_{k_j} \dot F(x_{k_j})}_2 \chi_{k_j + 1}^0(R) + \delta \\
			   &\leq L_R \delta \lambda_{\max}(M_{k_j}) + \delta.
\end{align*}
Subtracting $\delta$ from both sides we have $\gamma < L_R \delta \lambda_{\max}(M_{k_j})$, from which it follows that $\gamma^q < L_R^q \delta^q \lambda_{\max}(M_{k_j})^q$, for $q\geq 0$. Summing over all $j$, $\sum_{j=1}^\infty \gamma^q < L_R^q \delta^q \sum_{j=1}^\infty \lambda_{\max}(M_{k_j})^q$. The sum on the left diverges while the sum on the right is finite by \cref{property-summable} for any appropriate choice of $q$, which leads to a contradiction. Hence, the limit supremum and the limit infimum must agree and the first conclusion of the statement follows.


Finally, when $\sup_{k} \inlinenorm{ x_k}_2 < \infty$, there exists an $R > 0$ such that $\chi_{k}^0(R) = 1$ for all $k+1 \in \mathbb{N}$, and thus the final conclusion of the statement follows.
\end{proof}


\subsection{Convergence of the Iterates}

Using a nearly identical argument as for the convergence of the gradient, we show that the iterates either converge to a point or they diverge. Again, \cref{property-summable} is essential to this conclusion.

\begin{theorem} \label{result-iterate-convergence}
Suppose $F:\mathbb{R}^p \to \mathbb{R}$ satisfies \cref{assumption-gradient}. Let $x_0 \in \mathbb{R}^p$ and let $\lbrace x_k : k \in \mathbb{N} \rbrace$ be generated by \cref{eqn-recursion-iterate} satisfying \cref{property-spd,property-summable}. Then, $\lbrace x_k : k+1 \in \mathbb{N} \rbrace$ converges to a fixed point or it diverges.
\end{theorem}
\begin{proof}
Let $z \in \mathbb{R}^p$. We study the sequence $\lbrace \inlinenorm{ x_k - z}_2 \rbrace$. Suppose for the purposes of a  contradiction that  $\exists \ R > 0$ such that $\liminf_k \inlinenorm{ x_k - z}_2 < R < \limsup_k \inlinenorm{ x_k - z}_2$. Then,  $\exists \ \gamma > 0$ and a subsequence $\lbrace k_j : j \in \mathbb{N} \rbrace$ such that $\inlinenorm{ x_{k_j} - z }_2 \leq R < R + \gamma \leq \inlinenorm{ x_{k_j + 1} - z }_2$. Notice,
\begin{align*}
R + \gamma 
&\leq \inlinenorm{ x_{k_j + 1} - z }_2 \\
&\leq \inlinenorm{ x_{k_j + 1 } - x_{k_j} }_2 + \inlinenorm{ x_{k_j} - z}_2 \\
&\leq \inlinenorm{ M_{k_j} \dot F(x_{k_j})}_2 + R \\
&\leq \lambda_{\max}(M_{k_j}) G_{R,z} + R,
\end{align*}
where $G_{R,z} = \max_{ x : \inlinenorm{x - z}_2 \leq R} \inlinenorm{ \dot F(x)}_2$, which is finite by continuity and compactness. Hence, $\gamma \leq \lambda_{\max}(M_{k_j}) G_{R,z}$. In particular, $\sum_{j=1}^\infty \gamma^q \leq G_{R,z}^q \sum_{j=1}^\infty \lambda_{\max}(M_{k_j})^q$, for $q\geq0$. The sum on the left hand side is infinite, while the sum on the right hand side is finite by \cref{property-summable} for any appropriate choice of $q$, which is a contradiction. Therefore, the limit supremum and limit infimum must agree.

This leaves two possibilities: $\lim_{k \to \infty} \inlinenorm{ x_k - z}_2$ is either infinite or finite. In the case that the limit is infinite, there is nothing more that we need to do as this implies that $\lbrace x_k \rbrace$ must diverge. In the case that the limit is finite, we can replace $z$ by any $p+1$ distinct points, $z_1,\ldots,z_{p+1} \in \mathbb{R}^p$, whose affine hull is $\mathbb{R}^p$. Then $\lim_{k \to \infty} \inlinenorm{x_k - z_j }_2 < \infty$ for $j=1,\ldots,p+1$. By triangulation, we conclude that $\lbrace x_k \rbrace$ must converge to a fixed point.
\end{proof}

Combining the conclusions of  \cref{result-zoutendjik,result-gradient-convergence,result-iterate-convergence}, we have the following summary.
\begin{corollary} \label{result-zoutendjik-summable}
Suppose $F:\mathbb{R}^p \to \mathbb{R}$ satisfies \cref{assumption-lower-bound,assumption-gradient}. Let $x_0 \in \mathbb{R}^p$ and let $\lbrace x_k : k \in \mathbb{N} \rbrace$ be generated by \cref{eqn-recursion-iterate} satisfying \cref{property-spd,property-diverge,property-summable}. Then, either $\lbrace x_k : k+1 \in \mathbb{N} \rbrace$ converges to a stationary point or diverges.
\end{corollary}
\begin{proof}
By \cref{result-iterate-convergence}, $\lbrace x_k \rbrace$ either converges to a point, $x^*$, or diverges. Moreover, if $\lbrace x_k \rbrace$ converges to $x^*$, then the iterates remain bounded.  By \cref{result-gradient-convergence} and \cref{assumption-gradient}, $\dot F(x_k) \to 0$ and $\dot F(x_k) \to \dot F(x^*)$, which implies $\dot F(x^*) = 0$. 
\end{proof}

\subsection{Optimization Problem}

Consider the optimization problem 
\begin{equation} \label{eqn-problem}
\min_{x \in \mathbb{R}^p} F(x),
\end{equation}
under the following assumptions.
\begin{assumption} \label{assumption-lower-bound}
The objective function, $F:\mathbb{R}^p \to \mathbb{R}$, is bounded from below by a constant $F_{l.b.}$.
\end{assumption}
\begin{assumption} \label{assumption-gradient}
The gradient function, $\dot F(x) = \nabla F(z) \vert_{z = x}$, exists $\forall x \in \mathbb{R}^p$, and is locally Lipschitz continuous. 
\end{assumption}

The optimization problem, \cref{eqn-problem}, that satisfies \cref{assumption-lower-bound,assumption-gradient} is relatively general, and applies to a variety of problems in data science \cite[see Appendix A]{patel2021global}. Importantly, any optimization problem whose objective function is twice continuously differentiable immediately satisfies \cref{assumption-gradient}, as is proven in the next well-known lemma.

\begin{lemma} \label{result-hessian-implies-lipschitz}
Suppose $F$ is twice continuously differentiable for all $x \in \mathbb{R}^p$. Then $\dot F(x)$ is locally Lipschitz continuous.
\end{lemma}
\begin{proof}
Let $\ddot F(x)$ denote the Hessian of $F$. Then, by assumption, $\inlinenorm{ \ddot F(x)}_2$ is a continuous function and it is bounded over any compact region. By Taylor's theorem, for any $x,y \in \mathbb{R}^p$,
$\dot F(x) - \dot F(y) = \int_{0}^1 \ddot{F}(y + t (x - y) ) (x -y) dt$.
Let $K \subset \mathbb{R}^p$ be compact. By continuity and compactness, there exists an $L$ for $K$ such that $\inlinenorm{ \ddot F(x)}_2 \leq L$ for all $x \in K$. Hence, by H\"{o}lder's inequality, for any $x, y \in K$,
$\inlinenorm{ \dot F(x) - \dot F(y) } \leq L\inlinenorm{x - y}_2$.
As $K$ is arbitrary, the result follows.
\end{proof}

\subsection{Gradient Descent with Diminishing Step Sizes}

Now, suppose we apply gradient descent with diminishing step-sizes to solve \cref{eqn-problem}. Specifically, given $x_0 \in \mathbb{R}^p$, we generate a sequence $\lbrace x_k : k \in \mathbb{N} \rbrace$ according to
\begin{equation} \label{eqn-recursion-iterate}
x_{k+1} = x_k - M_k \dot F(x_k),
\end{equation}
where $M_k$ satisfies some of the following properties:
\begin{property} \label{property-spd}
$\lbrace M_k : k + 1 \in \mathbb{N} \rbrace \subset \mathbb{R}^{p \times p}$ are symmetric positive definite matrices;
\end{property}
\begin{property} \label{property-diverge}
$\sum_{k=0}^\infty \lambda_{\min}(M_k)$ diverges, where $\lambda_{\min}(M_k)$ denotes the smallest eigenvalue of $M_k$; and \textbf{either}
\end{property}
\begin{property} \label{property-diminishing}
$\lim_{k \to \infty} \lambda_{\max}(M_k) = 0$ where $\lambda_{\max}(M_k)$ denotes the largest eigenvalue of $M_k$, \textbf{or}
\end{property} 
\begin{property} \label{property-summable}
$\exists q > 1$ such that $\sum_{k=0}^\infty \lambda_{\max}(M_k)^q < \infty$.
\end{property}

\cref{property-spd,property-diverge,property-diminishing} are a natural generalization of classical diminishing step size requirements \cite[Proposition 1.2.4]{bertsekas2016}. Moreover, owing to its contrast with \cref{property-summable}, we refer to requiring properties \cref{property-spd,property-diverge,property-diminishing} as the \textit{without summability} case. \cref{property-spd,property-diverge,property-summable}  have their roots in the Robbins-Monro conditions \cite{robbins1951} and are closely related to the properties in \cite{patel2020,patel2021global,patel2021}. Despite its heritage, \cref{property-summable} is an important generalization to those of \cite{robbins1951,patel2020,patel2021global,patel2021} as we can choose any $q > 2$. Indeed, \cref{property-summable} is not enough for the stochastic gradient case, as summability for $q = 2$ is required.\footnote{This is the case when we assume the variances of the stochastic gradients exist. While we can permit even lower order moments to exist (i.e., less than the second moment of the stochastic gradient), we would then need more stringent requirements on the value of $q$ in \cref{property-summable}. See \cite{patel2021global,patel2021}.} Thus, \cref{property-summable} allows for a much larger selection of step sizes. 

To be concrete, consider $M_k = (k+1)^{-1/4} I$, where $I \in \mathbb{R}^{p \times p}$ is the identity matrix. Then, $\lbrace M_k \rbrace$ satisfies \cref{property-diverge} and \cref{property-summable} with $q > 4$, but does not satisfy \cref{property-summable} for $q = 2$ as would be needed for stochastic gradient descent. As an informative counterexample, \cref{property-summable} does not apply to all decaying sequences of $\lbrace M_k \rbrace$, as the next proposition shows.
\begin{proposition}
For all $k + 1\in \mathbb{N}$, let $M_k = \log(k+1)^{-1} I$, where $I \in \mathbb{R}^{p \times p}$ is the identity matrix. Then, $\lbrace M_k : k+1 \in \mathbb{N} \rbrace$ satisfies \cref{property-diverge}, but fails to satisfy \cref{property-summable}.
\end{proposition}
\begin{proof}
It is enough to show that for all $q \geq 1$, $\sum_{k=1}^\infty \log(k)^{-q}$ diverges. For any $q \geq 1$, it is straightforward to verify that $\log(k)^q / k \to 0$ as $k \to \infty$. Therefore, there exists a $K \in \mathbb{N}$, such that $\log(k)^{-q} \geq k^{-1}$ for all $k \geq K$. Since $\sum_{k=K}^\infty k^{-1}$ diverges, the result follows.
\end{proof}

We now analyze the global convergence of gradient descent with diminishing step sizes on nonconvex functions specified by \cref{assumption-lower-bound,assumption-gradient}. We will split our analysis into two cases: the case without summability (\cref{property-spd,property-diverge,property-diminishing}; \cref{section-no-summable}) and the case with summability (\cref{property-spd,property-diverge,property-summable}; \cref{section-summable}).

\subsection{Construction of the Objective Function}
Let $\lbrace m_k : k+1 \in \mathbb{N}\rbrace$ be a sequence of scalars such that $m_k > 0$, $\sum_k m_k = \infty$, and $m_k \to 0$ as $k \to \infty$. Define $S_0 = 0$ and $S_{k+1} = \sum_{j=0}^k m_k$ for all integers $k \geq 0$. 

For the objective function, define $F: \mathbb{R} \to \mathbb{R}$ by
\begin{equation} \label{eqn-divergence-objective}
F(x) = \begin{cases}
-x & x \leq 0 \\
f_j(x) & x \in (S_j, S_{j+1}], ~\forall j+1 \in \mathbb{N},
\end{cases}
\end{equation}
where $\lbrace f_j: (S_j, S_{j+1}] \to \mathbb{R} : j + 1\in\mathbb{N} \rbrace$ are defined iteratively as follows. Let
\begin{equation} \label{eqn-divergence-component-base}
f_0(x) = \begin{cases}
-x & x \in (0, \frac{m_0}{16}) \\
\frac{8}{m_0}(x- \frac{m_0}{8})^2 - \frac{3m_0}{32} & x \in [\frac{m_0}{16}, \frac{3m_0}{16}) \\
- \frac{5m_0}{16} \exp\left( \frac{5m_0/16}{x - m_0/2 } + 1 \right) + \frac{m_0}{4} & x \in [\frac{3m_0}{16}, \frac{ m_0}{2}) \\
\frac{m_0}{4} & x = \frac{m_0}{2} \\
\frac{5m_0}{16} \exp \left( -\frac{5m_0/16}{x - m_0/2} + 1 \right) + \frac{m_0}{4} & x \in (\frac{m_0}{2}, \frac{13m_0}{16}) \\
\frac{-8}{m_0}(x - \frac{7m_0}{8})^2 + \frac{19m_0}{32} & x \in [\frac{13 m_0}{16}, \frac{15m_0}{16}) \\
-x + \frac{3 m_0}{2} & x \in [\frac{15 m_0}{16}, m_0],
\end{cases}
\end{equation}
which is plotted for a particular choice of $m_0$ in \cref{plot-divergent-example-component}. Now, for $j \in \mathbb{N}$, let
\begin{equation} \label{eqn-divergence-component-general}
f_j(x) = \begin{cases}
-x + S_j + f_{j-1}(S_j) & x \in (S_j, S_j + \frac{m_j}{16}) \\
\frac{8}{m_j}(x - S_j - \frac{m_j}{8})^2 - \frac{3m_j}{32} + f_{j-1}(S_j) & x \in [S_j + \frac{m_j}{16}, S_j + \frac{3m_j}{16}) \\
- \frac{5m_j}{16} \exp\left( \frac{5m_j/16}{x - S_j - m_j/2} + 1\right) + \frac{m_j}{4} + f_{j-1}(S_j) & x \in [S_j + \frac{3m_j}{16}, S_j + \frac{m_j}{2}) \\
\frac{m_j}{4} + f_{j-1}(S_j) & x = S_j + \frac{m_j}{2} \\
\frac{5m_j}{16} \exp\left( \frac{-5m_j/16}{x - S_j - m_j/2} + 1\right) + \frac{m_j}{4} + f_{j-1}(S_j) & x \in (S_j + \frac{m_j}{2}, S_j + \frac{13m_j}{16}) \\
\frac{-8}{m_j}(x - S_j - \frac{7m_j}{8})^2 + \frac{19m_j}{32} + f_{j-1}(S_j) & x \in [S_j + \frac{13m_j}{16}, S_j + \frac{15m_j}{16}) \\
-x + S_j + \frac{3m_j}{2} + f_{j-1}(S_j) & x \in [S_j + \frac{15m_j}{16}, S_{j+1}].
\end{cases}
\end{equation}

\begin{figure}[h]
\centering
\input{figure/tikz-divergent-example-component}
\caption{Plot of $f_0(x)$ with $m_0 = 8.0$ with each component shown in a different color.}
\label{plot-divergent-example-component}
\end{figure}

\subsection{Properties of the Objective Function}

We show that $F: \mathbb{R} \to \mathbb{R}$ as defined in \cref{eqn-divergence-objective}--\cref{eqn-divergence-component-general} satisfies \cref{assumption-lower-bound,assumption-gradient}. We begin by proving that each component, $f_j: (S_j, S_{j+1}] \to \mathbb{R}$, satisfies \cref{assumption-lower-bound,assumption-gradient} on its domain. 

\begin{remark}
Below, we define the continuous extension of $f_j$ on $[S_j, S_{j+1}]$ by the value of $f_j(x)$ on $(S_j, S_{j+1}]$ and by $\lim_{x \downarrow S_j} f_j(x)$ for the point $x= S_j$. Moreover, at the ends of the interval, we use differentiability and the corresponding notation, $\dot f_j$, to mean the one-sided derivatives.
\end{remark}
\begin{proposition} \label{result-divergence-component-properties}
The continuous extension $f_0: (S_0, S_1] \to \mathbb{R}$ $($as defined in \cref{eqn-divergence-component-base}$)$ to $[S_0,S_1]$ is continuous on its domain, bounded from below by $-3m_0/32$, differentiable on its domain with $\dot f_0(S_0) = \dot f_0(S_1) = -1$, and its derivative is locally Lipschitz continuous. Similarly, the continuous extension of $f_j: (S_j, S_{j+1}] \to \mathbb{R}$ $($as defined in \cref{eqn-divergence-component-general}$)$ to $[S_j,S_{j+1}]$ is continuous on its domain, bounded from below by $f_{j-1}(S_j) - 3m_j/32$, differentiable on its domain with $\dot f_j(S_j) = -1$ and $\dot f_j(S_{j+1}) = -1$, and its derivative is locally Lipschitz continuous.
\end{proposition}
\begin{proof}
We only look at an arbitrary $j \in \mathbb{N}$ as the proof is identical for $f_0$. Moreover, since $f_j$ is equal to its reflection across the vertical axis $x = S_j + m_j/2$ followed by a reflection over the horizontal axis $y = m_j/4 + f_{j-1}(S_j)$, it is enough to show continuity and differentiability on $[S_j, S_j + m_j/2]$. 

To establish continuity, we need to show that the left sided limits of $f_j$ agree with the function value at $S_j + \delta m_j/16$ for $\delta = 1, 3, 8$. Starting with $\delta = 1$, $\lim_{x \uparrow S_j + m_j/16} -x + S_j + f_{j-1}(S_j) = -m_j/16 + f_{j-1}(S_j)$. By direct substitution,
\begin{equation*}
f_j(S_j + m_j/16) = \frac{8}{m_j}\left( \frac{m_j}{16} \right)^2 - \frac{3m_j}{32} + f_{j-1}(S_j) = \frac{m_j}{32} - \frac{3m_j}{32} + f_{j-1}(S_j).
\end{equation*}
Hence, the left limit agrees with the function value at $\delta = 1$. For $\delta = 3$, the symmetry and continuity of the quadratic function implies $\lim_{ x \uparrow S_j + 3m_j/16} f_j(x) = -m_j/16 + f_{j-1}(S_j)$. By direct substitution,
\begin{equation*}
f_j(S_j + 3m_j/16) = -\frac{5m_j}{16} \exp\left( \frac{5m_j/16}{-5m_j/16} + 1 \right) + \frac{4m_j}{16} + f_{j-1}(S_j) = -\frac{m_j}{16} + f_{j-1}(S_j).
\end{equation*}
Hence, the left limit agrees with the function value at $\delta = 3$. For $\delta = 8$,
\begin{equation*}
\lim_{ x \uparrow S_j + m_j/2} -\frac{5m_j}{16} \exp\left( \frac{5m_j/16}{x - S_j - m_j/2} + 1 \right) + \frac{m_j}{4} + f_{j-1}(S_j) = \frac{m_j}{4} + f_{j-1}(S_j), 
\end{equation*} 
which is just $f_j(S_j + m_j/2)$. Hence, the continuous extension of $f_j$ is continuous on $[S_j, S_{j+1}]$. 

We now compute the derivatives of the components of $f_j$ on $[S_j, S_{j+1}]$ with the convention of assigning the one-sided derivative to the component function that includes its end point.
\begin{equation} \label{eqn-divergence-component-derivatives}
\dot f_j(x) =\begin{cases}
-1 & x \in [S_j, S_j + \frac{m_j}{16}) \\
\frac{16}{m_j}(x - S_j - \frac{m_j}{8}) & x \in [S_j + \frac{m_j}{16}, S_j + \frac{3m_j}{16}) \\
\left( \frac{5m_j/16}{x - S_j - m_j/2} \right)^2 \exp\left( \frac{5m_j/16}{x - S_j - m_j/2} + 1 \right) & x \in [S_j + \frac{3m_j}{16}, S_j + \frac{m_j}{2}) \\
\left( \frac{5m_j/16}{x - S_j - m_j/2} \right)^2 \exp\left( \frac{-5m_j/16}{x - S_j - m_j/2} + 1 \right) & x \in (S_j + \frac{m_j}{2}, S_j + \frac{13m_j}{16}) \\
-\frac{16}{m_j}(x - S_j - \frac{7m_j}{8}) & x \in [S_j + \frac{13m_j}{16}, S_j + \frac{15m_j}{16}) \\
-1 & x \in [S_j + \frac{15m_j}{16}, S_{j+1}].
\end{cases}
\end{equation}
In order to extend these component derivatives to the continuous extension of $f_j$, we need to verify that the left hand limits of the derivatives agree with the right side derivatives at $S_j + \delta m_j/16$ for $\delta=1,3$ of \cref{eqn-divergence-component-derivatives}, and we need to verify that the left hand limit of the derivative is $0$ at $\delta = 8$ of \cref{eqn-divergence-component-derivatives}. Starting with $\delta = 1$, the left hand limit is $-1$ and, by direct calculation,
\begin{equation*}
\frac{16}{m_j}\left(S_j + \frac{m_j}{16} - S_j - \frac{m_j}{8} \right) = -1.
\end{equation*}
For $\delta = 3$, the left hand limit is
\begin{equation*}
\lim_{ x \uparrow S_{j} + {3m_j/16} } \frac{16}{m_j}\left(x - S_j - \frac{m_j}{8} \right) = 1,
\end{equation*}
and a direct evaluation of the third component \cref{eqn-divergence-component-derivatives} is 
\begin{equation*}
\left( \frac{5m_j/16}{S_{j} + {3m_j/16} - S_j - m_j/2} \right)^2 \exp\left( \frac{5m_j/16}{S_{j} + {3m_j/16} - S_j - m_j/2} + 1 \right) = 1.
\end{equation*}
For $\delta = 8$, we need to check that the left hand limit is zero, which can be confirmed by checking that the argument of the exponential term goes to $-\infty$ as $x \uparrow S_j + 8m_j/16$.

Overall, the derivative of the continuous extension of $f_j$ is well defined at every point on its interval, is continuous, and is given by
\begin{equation} \label{eqn-divergence-component-derivative-definition}
\dot f_j(x) = \begin{cases}
-1 & x \in [S_j, S_j + \frac{m_j}{16}) \\
\frac{16}{m_j}(x - S_j - \frac{m_j}{8}) & x \in [S_j + \frac{m_j}{16}, S_j + \frac{3m_j}{16}) \\
\left( \frac{5m_j/16}{x - S_j - m_j/2} \right)^2 \exp\left( \frac{5m_j/16}{x - S_j - m_j/2} + 1 \right) & x \in [S_j + \frac{3m_j}{16}, S_j + \frac{m_j}{2}) \\
0 & x = S_j + m_j/2 \\
\left( \frac{5m_j/16}{x - S_j - m_j/2} \right)^2 \exp\left( \frac{-5m_j/16}{x - S_j - m_j/2} + 1 \right) & x \in (S_j + \frac{m_j}{2}, S_j + \frac{13m_j}{16}) \\
-\frac{16}{m_j}(x - S_j - \frac{7m_j}{8}) & x \in [S_j + \frac{13m_j}{16}, S_j + \frac{15m_j}{16}) \\
-1 & x \in [S_j + \frac{15m_j}{16}, S_{j+1}].
\end{cases}
\end{equation}

Using this derivative, we can calculate the lower bound for the function. By the derivative of the extension of $f_j$, \cref{eqn-divergence-component-derivative-definition}, we see that the function is decreasing only on $[S_j, S_j + m_j/8]$ and $[S_j + 7m_j/8, S_{j+1}]$. Moreover, $f_j(S_j + m_j/8) = -3m_j/32 + f_{j-1}(S_j)$ and $f_j(S_{j+1}) = m_j/2 + f_{j-1}(S_j)$. Thus, the lower bound of the extension of $f_j$ is as stated.

Our last step is to verify the local Lipschitz continuity of the derivative. It is easy to verify that within its interval, the components are twice continuously differentiable. As a result, we can use \cref{result-hessian-implies-lipschitz}. Similarly, if we define the second derivative at $S_j + m_j/2$ to be $0$, we can verify that the objective is twice continuously differentiable at $S_j + m_j/2$. Then, we can use \cref{result-hessian-implies-lipschitz} again. To conclude, we need to examine what happens around the points $S_j + \delta m_j/16$ for $\delta = 1, 3$.

Starting with $\delta = 1$, consider the points $S_j + m_j/16 - \epsilon_1 m_j/16$ and $S_j + m_j/16 + \epsilon_2 m_j/16$ for $\epsilon_1, \epsilon_2 > 0$ sufficiently small. Then the difference in the derivatives at these points divided by the distance between the points is
\begin{align*}
\frac{\left\vert \frac{16}{m_j}\left(-\frac{m_j}{16} + \epsilon_2 \frac{m_j}{16}\right) + 1  \right\vert }{(\epsilon_2 + \epsilon_1) m_j/16} = \frac{\epsilon_2}{(\epsilon_2 + \epsilon_1) m_j/16} \leq \frac{16}{m_j}.
\end{align*} 
Therefore, we conclude that the derivative is locally Lipschitz near $S_j + m_j/16$. For $\delta=3$, we compute the same ratio at the points $S_j + 3m_j/16 - \epsilon_1 m_j/16$ and $S_j + 3m_j/16 + 5 \epsilon_2 m_j/16$ for $\epsilon_1, \epsilon_2 \in [0,1/4]$ where at most either $\epsilon_1$ or $\epsilon_2$ is zero. The ratio of the difference in the derivatives and the points is
\begin{align*}
\frac{\left\vert \frac{1}{(1 - \epsilon_2)^2} \exp\left( \frac{\epsilon_2}{\epsilon_2 - 1}\right) -1 + \epsilon_1 \right\vert}{(5 \epsilon_2 + \epsilon_1) m_j/16} \leq \frac{\epsilon_2 + \epsilon_2^2/2 + \epsilon_1}{(5 \epsilon_2 + \epsilon_1) m_j/16} \leq \frac{16}{m_j}.
\end{align*}
Therefore, we conclude that the derivative is locally Lipschitz near $S_j + 3m_j/16$. 
\end{proof}

With this calculation complete, we can now verify that $F$ satisfies \cref{assumption-lower-bound,assumption-gradient}.

\begin{proposition} \label{result-divergence-objective-properties}
The function $F : \mathbb{R} \to \mathbb{R}$ is continuous and differentiable on its domain, is lower bounded, and its derivative is locally Lipschitz continuous. Moreover, $F(S_j) = S_j/2$ and $\dot F(S_j) = -1$ for all $j + 1 \in \mathbb{N}$. 
\end{proposition}
\begin{proof}
By \cref{result-divergence-component-properties}, we need only verify the continuity of $F$ and the differentiability of $F$ at $x = S_j$. Note, $F(S_j) = f_{j-1}(S_j)$. We need to verify that the right side limit converges to $f_{j-1}(S_j)$. That is,
\begin{equation*}
\lim_{ x \downarrow S_j } F(x) = \lim_{x \downarrow S_j} f_j(x) = \lim_{x \downarrow S_j} -x + S_j + f_{j-1}(S_j) = f_{j-1}(S_j). 
\end{equation*} 
Thus, $F$ is continuous at all $S_j$ for $j \in \mathbb{N}$. We check $x = S_0 = 0$ as well. $F(0) = 0$ by definition. Moreover,
\begin{equation*}
\lim_{ x\downarrow 0 } F(x) = \lim_{x \downarrow 0} f_0(x) = \lim_{ x \downarrow 0} -x = 0.
\end{equation*}
Hence, $F$ is continuous on its domain.

For differentiability, by  \cref{result-divergence-component-properties} it follows that the derivative at each $S_j$ is $-1$ from the left and the right for $j \in \mathbb{N}$. Hence, the derivative exists at each $S_j$ for $j \in \mathbb{N}$. Moreover, the left hand derivative at $S_0$ is $-1$, which agrees with the right hand derivative. Hence, $F$ is continuously differentiable on its domain. Since the derivative is constant in a small neighborhood of $S_j$, it is Lipschitz continuous in this region. Finally, $\dot F(S_j) = -1$ for all $j+1 \in \mathbb{N}$. 

To show that $F$ is lower bounded, we will first calculate the values of $F(S_j)$. We proceed by induction. $F(S_0) = 0 = S_0/2$. Now suppose the statement holds up to $j$. Then $F(S_{j}) = S_{j}/2$. By construction, $f_{j-1}(S_j) = F(S_{j}) = S_j/2$. Now, 
\begin{align*}
F(S_{j+1}) = f_j(S_{j+1}) &= -S_{j+1} + S_j + \frac{3m_j}{2} + f_{j-1}(S_j) \\
&= -S_j - m_j + S_j + \frac{3m_j}{2} + \frac{S_j}{2} = \frac{S_{j+1}}{2}.
\end{align*}
To show the lower bound property, recall that $f_j(x) \geq f_{j-1}(S_j) - 3m_j/32 = F(S_{j}) - 3m_j/32 = S_j/2 - 3m_j/32$. Since $S_j \to \infty$ and $m_j \to 0$ by construction, $F(x) \geq \inf_{j} S_j/2 - 3m_j/32 > -\infty$.
\end{proof}

\subsection{Properties of Gradient Descent on the Objective Function}

We are now ready to show that gradient descent with diminishing step sizes generates iterates that diverge, and whose objective function diverges and  gradient function remains bounded away from zero.

\begin{proposition} \label{result-divergence}
Let $\lbrace m_k : k+1 \in \mathbb{N} \rbrace$ be any positive sequence such that $\sum_{k} m_k$ diverges and $m_k \to 0$. Define $F : \mathbb{R} \to \mathbb{R}$ as in \cref{eqn-divergence-objective}. Suppose $x_0 = 0$ and let $\lbrace x_k : k \in \mathbb{N} \rbrace$ be generated according to \cref{eqn-recursion-iterate} with $M_k = m_k I$ for all $k+1 \in \mathbb{N}$. Then, $\lbrace M_k \rbrace$ satisfies \cref{property-spd,property-diverge,property-diminishing}. Moreover, (a) $\lim_k x_k = \infty$, (b) $\lim_k F(x_k) = \infty$, and (c) $\lim_k |\dot F(x_k)| = 1$. 
\end{proposition}
\begin{proof}
To prove the result, we need only show that $x_k = S_k$ where we recall that $S_0 = 0$ and $S_k = \sum_{j=0}^{k-1} m_j$. For $k=0$, $x_0 = 0 = S_0$. Suppose this holds up to $k$. Then, by \cref{result-divergence-objective-properties},
\begin{equation*}
x_{k+1} = x_k - M_k \dot F(x_k) = S_k - m_k (-1) = S_{k+1}.
\end{equation*}
Now, since $S_k$ diverges, the iterates diverge (part $(a)$). Moreover, by \cref{result-divergence-objective-properties}, since $F(x_k) = F(S_k) = S_k/2$, the objective function also diverges (part $(b)$). Finally, by \cref{result-divergence-objective-properties}, $\dot F(x_k) = \dot F(S_k) = -1$ (part $(c)$).
\end{proof}

In summary, as the example from \cref{result-divergence} and the example of $F(x) = \exp(-x^2)$ show, under our assumptions about the objective function and properties of gradient descent, we cannot conclude anything additional about the objective behavior of the function or the  gradient in the regime where the iterates generated by gradient descent with diminishing step sizes diverge.


\subsection{Continuous Gradient Descent}
Let $x \in \mathbb{R}^p$ be arbitrary. Consider the initial value problem,
\begin{equation} \label{eqn-ivp}
\begin{cases}
\frac{dy}{dt} &= - \dot F(y(t)), ~ t \geq 0 \\
y(0) &= x.
\end{cases}
\end{equation}
To explicitly show the dependence on the initial value, $x$, we will write $\Phi_h(x)$ to be the solution (if it exists) to \cref{eqn-ivp} at time $h \geq 0$ that is initialized at $x \in \mathbb{R}^p$. If $F$ satisfies \cref{assumption-gradient}, we can apply the Picard-Lindel\"{o}f theorem to conclude that $\Phi_h(x)$ exists and is unique for any finite, non-negative choice of $h$. Therefore, we define continuous gradient descent initialized at $x \in \mathbb{R}^p$ to be $\lbrace \Phi_h(x) : h \geq 0 \rbrace$.

\subsection{Limit Cycles of Continuous Gradient Descent}
There are many possible choices for the asymptotics of continuous gradient descent; two particularly interesting cases are cycles and limit cycles. Recall, a cycle cannot be a solution for continuous gradient descent. To see why, suppose such a cycle exists and $x$ is a point on this cycle. Then there would exist a $t > 0$ such that $F(\Phi_t(x)) = F(x)$, but
\begin{equation*}
0 = F(\Phi_t(x)) - F(x) = \int_0^t \dot F(\Phi_s(x))^\intercal \left( \frac{d}{dr} \Phi_r(x) \vert_{r=s} \right) ds = \int_0^t - \norm{ \dot F(\Phi_s(x))}_2^2 ds < 0.
\end{equation*}
Hence, a cycle cannot be a solution for continuous gradient descent. 

However, it is possible for continuous gradient descent to have a limit cycle. To see how, consider a small modification of the Palis-de Melo function \cite[\S 1, Example 3]{palis2012}, $F: \mathbb{R}^2 \to \mathbb{R}$, specified by
\begin{equation} \label{eqn-pdm}
F(x) = \begin{cases}
\exp\left(\frac{1}{\norm{x}_2^2 - 1}  \right) & \norm{x}_2 < 1 \\
0 & \norm{x}_2 = 1 \\
-\exp\left(\frac{-1}{\norm{x}_2^2 - 1} \right) \left[ \sin\left( \frac{1}{\norm{x}_2-1}  \right) \frac{\cmp{x}{1}}{\norm{x}_2} -  \cos\left( \frac{1}{\norm{x}_2-1}  \right) \frac{\cmp{x}{2}}{\norm{x}_2} \right] & \norm{x}_2 > 1,
\end{cases}
\end{equation}
where $\cmp{x}{j}$ is the $j^\mathrm{th}$ component of $x$. The zero set of the Palis-de Melo function is plotted in \cref{figure-palis-de-melo-zero}, and a profile of the function when $\cmp{x}{2} = 0$ is plotted in \cref{figure-palis-de-melo-profile}. Importantly, the Palis-de Melo function satisfies \cref{assumption-lower-bound,assumption-gradient}.

\begin{proposition} \label{result-pdm-assumptions}
The Palis-de Melo function, \cref{eqn-pdm}, is bounded from below, is differentiable at every point in $\mathbb{R}^2$, and its gradient is locally Lipschitz continuous at every point in $\mathbb{R}^2$. 
\end{proposition}
\begin{proof}
To verify that the Palis-de Melo function is bounded from below, we look at the three components separately. When $\inlinenorm{x}_2 < 1$, $F(x) \geq 0$. When $\inlinenorm{x}_2 = 1$, $F(x) = 0$. When $\inlinenorm{x}_2 > 1$, define
\begin{equation}
\theta = \begin{cases}
\arcsin\left( \frac{\cmp{x}{2}}{\norm{x}_2} \right) & \cmp{x}{1} \geq 0 \\
\pi - \arcsin\left( \frac{\cmp{x}{2}}{\norm{x}_2} \right) & \cmp{x}{1} < 0
\end{cases}
\end{equation}
Then, when $\inlinenorm{x}_2 > 1$,
\begin{equation}
F(x) = - \exp\left(\frac{-1}{\norm{x}_2^2 - 1} \right) \sin\left( \frac{1}{\norm{x}_2 -1} - \theta \right) \geq - \exp\left(\frac{-1}{\norm{x}_2^2 - 1} \right) \geq -1.
\end{equation}
Thus, $F$ is bounded from below.

We now show that $F$ is continuously differentiable. When $\inlinenorm{x}_2 < 1$, we can differentiate to conclude
\begin{equation}
\dot F(x) = \exp\left( \frac{1}{\norm{x}_2^2 - 1} \right) \frac{-2}{\left( \norm{x}_2^2 - 1  \right)^2} x.
\end{equation}
Next, let $x \in \mathbb{R}^2$ such that $\inlinenorm{x}_2 = 1$. Then,
\begin{equation}
\dot F(x) = \lim_{x_n \to x} \frac{|F(x_n)|}{\norm{x_n - x}_2} \leq \lim_{x_n \to x } \frac{\min\left\lbrace \exp\left( \frac{1}{\norm{x_n}_2^2 -1 }  \right),\exp\left( \frac{-1}{\norm{x_n}_2^2 -1 }  \right) \right\rbrace}{\norm{x_n - x}_2} = 0.
\end{equation}
When $\inlinenorm{x}_2 > 1$, we can differentiate to conclude
\begin{equation*}
\begin{aligned}
\dot F(x) & = 
\exp\left( \frac{-1}{\norm{x}_2^2 - 1} \right) \frac{2}{\left( \norm{x}_2^2 - 1  \right)^2}  \left[ \sin\left( \frac{1}{\norm{x}_2-1}  \right) \frac{\cmp{x}{1}}{\norm{x}_2} -  \cos\left( \frac{1}{\norm{x}_2-1}  \right) \frac{\cmp{x}{2}}{\norm{x}_2} \right]x \\
&\quad + 
\exp\left( \frac{-1}{\norm{x}_2^2 - 1} \right)\left[ 
\frac{-\cmp{x}{1}}{(\norm{x}_2 - 1)^2 \norm{x}_2^2}  \cos\left( \frac{1}{\norm{x}_2-1}  \right) x 
- \sin\left( \frac{1}{\norm{x}_2-1}  \right)\frac{\cmp{x}{1}}{\norm{x}_2^3}x \right. \\
&\quad + \sin\left( \frac{1}{\norm{x}_2-1}  \right) \frac{1}{\norm{x}_2}\begin{bmatrix} 1 \\ 0 \end{bmatrix} 
-\frac{\cmp{x}{2}}{(\norm{x}_2 - 1)^2 \norm{x}_2^2}  \sin\left( \frac{1}{\norm{x}_2-1}  \right) x  \\
&\quad \left. + \cos\left( \frac{1}{\norm{x}_2-1}  \right)\frac{\cmp{x}{2}}{\norm{x}_2^3}x
-\cos\left( \frac{1}{\norm{x}_2-1}  \right) \frac{1}{\norm{x}_2}\begin{bmatrix} 0 \\ 1 \end{bmatrix}\right].
\end{aligned}
\end{equation*}
Finally, notice that when when $\norm{x}_2$ is near $1$, $\dot F(x)$ is dominated by the exponential term which goes to zero. Hence, $\dot F$ is continuously differentiable.

We can do the identical, yet more tedious calculation to conclude that the second derivative of $F(x)$ exists for all $x \in \mathbb{R}^2$ and is continuous. We can then apply \cref{result-hessian-implies-lipschitz} to conclude that $\dot F(x)$ is locally Lipschitz continuous.
\end{proof}

By \cref{result-pdm-assumptions}, continuous gradient descent is well-defined on the Palis-de Melo function. There is an appropriate initialization of continuous gradient descent that results in a path whose limit cycle is the circle of radius one, which we show next.

\begin{proposition} \label{result-pdm-limit-cycle}
Let $\mathcal{S} = \lbrace z \in \mathbb{R}^2 : \inlinenorm{z}_2 = 1 \rbrace$. Let $\lbrace \Phi_t(x): t \geq 0 \rbrace$ denote continuous gradient descent on \cref{eqn-pdm} when initialized at $x \in \mathbb{R}^2$. Let
\begin{equation}
\mathcal{U} = \left\lbrace \begin{bmatrix} r\cos(\theta) \\ r \sin(\theta) \end{bmatrix}: ~r\geq 0, ~\theta \geq 0, 1+ \frac{1}{2\pi+\theta} < r < 1 + \frac{1}{\pi + \theta}  \right\rbrace \subset \mathbb{R}^2.
\end{equation}
There exists an $x \in \mathbb{R}^2$ for which $\cmp{x}{1} \in (1+\frac{1}{2\pi}, 1 + \frac{1}{\pi})$ and $\cmp{x}{2} = 0$ such that $\Phi_h(x) \in \mathcal{U}$ for all $h \geq 0$. Moreover, for all $ z \in \mathcal{S}$,  $\exists \lbrace t_i : i \in \mathbb{N} \rbrace \subset \mathbb{R}_{\geq 0}$ such that $\lim_{i \to \infty} \Phi_{t_i}(x) = z$.
\end{proposition}
\begin{proof}
The proof is a small modification of that given in \cite[\S 1, Example 3]{palis2012}.
\end{proof}

The basic idea of the proof is best understood geometrically. Consider the initialization of continuous gradient descent between the purple points in \cref{figure-palis-de-melo-zero} (equivalently, \cref{figure-palis-de-melo-profile}). From \cref{figure-palis-de-melo-profile}, the initialization is in a region where the objective function is positive. Hence, as continuous gradient descent attempts to reduce the objective function value, continuous gradient descent initialized in this region should go towards the black spiral or orange spiral in \cref{figure-palis-de-melo-zero}, or towards another point between the purple points in \cref{figure-palis-de-melo-zero}. Hence, by the Picard-Lindel\"{o}f theorem (which can be applied by \cref{result-pdm-assumptions}), there is a point between the set of initializations going towards the black spiral and the other two alternatives. Thus, if continuous gradient descent is initialized at one of these points, it must remain between the black and orange spirals (i.e., stay within $\mathcal{U}$) and must have a limit cycle of $\mathcal{S}$.


\begin{figure}[hbt]
\centering
\input{figure/tikz-palis-de-melo}
\caption{A plot of the zero set of the Palis-de Melo function, \cref{eqn-pdm}. The lines indicate the sets where the function is zero. The green line corresponds to $\inlinenorm{x}_2 = 1$; the black line corresponds to one branch of the zero set of the sinusoidal term (when $\inlinenorm{x}_2 > 1$); and the orange line corresponds to the another branch of the zero set of the sinusoidal term with a phase shift of $\pi$. The pluses and minuses indicate where $F$ is positive and negative, respectively. The two purple points correspond to $(1+\frac{1}{2\pi},0)$ and $(1+\frac{1}{\pi},0)$.} \label{figure-palis-de-melo-zero}
\end{figure}

\begin{figure}[hbt]
\centering
\input{figure/tikz-palis-de-melo-profile}
\caption{A profile plot of the Palis-de Melo function, \cref{eqn-pdm}, when $\cmp{x}{2} = 0$.} \label{figure-palis-de-melo-profile}
\end{figure}

\subsection{Spurious Solution for the Palis-de Melo Function} \label{subsection-pdm-spurious}

Now, suppose we apply gradient descent to any initialization with scalar step sizes satisfying \cref{property-spd,property-diverge,property-summable}, and that the iterates generated by gradient descent remain in $\mathcal{U}$. Then, the iterates are finite and \cref{result-zoutendjik-summable} implies that they must converge to a stationary point. Thus, we have a contradiction. To conclude, continuous gradient descent has a spurious solution for gradient descent with diminishing, summable step sizes. In other words, the properties of continuous gradient descent, \textit{regardless of our initialization}, do not all apply to gradient descent with diminishing, summable step sizes. 

While this proof is completely sufficient, we can provide some geometric insight into why we should expect this to hold. In particular, recall that we effectively need to spiral around the circle, $\mathcal{S}$, using a discrete method that only uses gradient information. As we get closer and closer to this circle, our gradient will be perpendicular to the circle and so, no matter our step size, we must deviate from the tracing of this circle.