\subsection{Problem setup}
\label{sec:assumptions}

Throughout the sequel, we focus on the non-convex optimization problem
\begin{equation}
\label{eq:opt}
\tag{Opt}
\begin{aligned}
\textrm{minimize}_{x\in\points}
	& \
	\obj(\point),


\end{aligned}
\end{equation}
where $\obj\from\points\to\R$ is a $\vdim$-times differentiable function satisfying the following blanket assumptions.

\begin{assumption}
\label{asm:reg}
$\obj$ is \emph{$\lips$-Lipschitz and $\smooth$-smooth}, \ie
\begin{equation}


\dnorm{\nabla\obj(\point)}
	\leq \lips
	\quad
	\textrm{and}
	\;\;
\dnorm{\nabla\obj(\pointalt) - \nabla\obj(\point)}
	\leq \smooth \norm{\pointalt - \point}
	\;\;
	\text{for all $\point,\pointalt\in\points$}.
\end{equation}


\end{assumption}


\begin{assumption}
\label{asm:sublvl}
The \emph{sublevels}


\(
\flvl_{c}
	\equiv \setdef{\point\in\points}{\obj(\point) \leq c}
\)

of $\obj$ are bounded for all $c < \sup\obj$.
\end{assumption}

\begin{assumption}
\label{asm:gradlvl}
The \emph{gradient sublevels}

\(
\glvl_{\eps}
	\equiv \setdef{\point\in\points}{\dnorm{\nabla\obj(\point)} \leq \eps}
\)

of $\obj$
are bounded for some $\eps>0$.
\end{assumption}

\Cref{asm:reg,asm:sublvl,asm:gradlvl} are fairly standard in non-convex analysis and optimization.
Taken individually,

\cref{asm:reg} is a basic

regularity requirement for $\obj$;

\cref{asm:sublvl} guarantees the existence of solutions to \eqref{eq:opt} by ruling out vacuous cases like $\obj(\point) = -\point$;

and, finally,
\cref{asm:gradlvl} serves to exclude objectives with near-critical behavior at infinity such as  $\obj(\point) = -e^{-\point^{2}}$.
\footnote{Note that \cref{asm:gradlvl} only concerns near-critical points, not regions where $\dnorm{\nabla\obj(\point)}$ may be large.}
Taken together, \cref{asm:reg,asm:sublvl,asm:gradlvl} further imply that the critical set
\begin{equation}
\label{eq:crit}
\sols
	\equiv
	\crit(\obj)
	= \setdef{\point\in\points}{\nabla\obj(\point) = 0}
\end{equation}
of $\obj$ is nonempty, a fact that we use freely in the sequel.

Typical examples of \eqref{eq:opt} in machine learning comprise
neural networks with sigmoid activation functions,
underdetermined inverse problems,
empirical risk minimization models,
etc.
In such problems, obtaining accurate gradient input is impractical, so to solve \eqref{eq:opt}, we often rely on \acli{SG} information, obtained for example by taking a mini-batch of training instances.


\subsection{Assumptions on the oracle}
\label{sec:oracle}

With this in mind, we will assume throughout that the optimizer can access $\nabla\obj$ via a \acdef{SFO}.
Formally, this is a black-box feedback mechanism which, when queried at an input point $\point\in\points$, returns a random vector $\orcl(\point;\sample)$ with $\sample$ drawn from some (complete) probability space $\probspace$.
In more detail, decomposing the oracle's output at $\point$ as
\begin{equation}
\label{eq:SFO}
\tag{SFO}


\orcl(\point;\sample)
	= \nabla\obj(\point)
	+ \noise(\point;\sample)
	\,,
\end{equation}
we  make the following assumption.
\begin{assumption}
\label{asm:noise}
The \emph{error term} $\noise(\point;\sample)$ of \eqref{eq:SFO} has
\begin{subequations}
\label{eq:noise}
\begin{alignat}{2}
\label{eq:zeromean}
\textpar{\textit a}
\quad
	&\emph{Zero mean:}
	&\quad
	&\exof{\noise(\point;\sample)}
		= 0
	\\
\textpar{\textit b}
\quad
\label{eq:moment}
	&\emph{Finite $\qexp$-th moments:}
	&\quad
	&\exof{\dnorm{\noise(\point;\sample)}^{\qexp}}
		\leq \noisepar^{\qexp}
	\;\
	\text{for some $\qexp\geq2$ and $\noisepar\geq 0$}.
	\hspace{2.5em}
\end{alignat}
\end{subequations}


\end{assumption}

\Cref{asm:noise} is standard in stochastic optimization and is usually stated with $\qexp = 2$, \ie as a ``finite variance'' condition, \cf \citet{Nes04,Pol87,JNT11,Ben99}, and many others.
Allowing values of $\qexp$ greater than $2$ provides more flexibility in the choice of step-size policies, so we  keep \eqref{eq:moment} as a blanket assumption throughout.
We  also formally allow the value $\qexp=\infty$ in \eqref{eq:moment}, in which case we will say that the noise is \emph{bounded in $L^{\infty}$};
put simply, this corresponds to the standard assumption that the noise in \eqref{eq:SFO} is bounded almost surely.


\subsection{\Acl{SGD}}
\label{sec:SGD}

With all this in hand, the \acf{SGD} algorithm can be written as
\begin{equation}
\label{eq:SGD}
\tag{SGD}
\next
	= \curr
	- \curr[\step] \curr[\signal].
\end{equation}
In the above,
$\run = \running$ is the algorithm's iteration counter,
$\curr[\step]$ is the algorithm's step-size,
and
$\curr[\signal]$ is a sequence of gradient signals of the form
\begin{equation}
\label{eq:signal}
\curr[\signal]
	= \orcl(\curr;\curr[\sample])
	= \nabla\obj(\curr)
	+ \curr[\noise].
\end{equation}

Each gradient signal $\curr[\signal]$ is generated by querying the oracle at $\curr$ with some random seed $\curr[\sample]$.
For concision, we write $\curr[\noise] \equiv \noise(\curr,\curr[\sample])$ for the gradient error at the $\run$-th iteration

and
$\curr[\filter] = \sigma(\state_{\start},\dotsc,\curr)$ for the natural filtration of $\curr$;
in this notation, $\curr[\sample]$ and $\curr[\signal]$ are \emph{not} $\curr[\filter]$-measurable.


All our results for \eqref{eq:SGD} are stated in the framework of the basic assumptions above.
The price to pay for this degree of generality is that the analysis requires an intricate interplay between martingale limit theory and the theory of \acl{SA};
we review the relevant notions below.
{"config": "arxiv", "file": "2006.11144/Setup.tex"}