\appendix

\section{Proofs for Sections~\ref{sec:cltheory} and~\ref{sec:bias}}\label{sec:cltproofs}

\subsection{Preliminaries and Additional  Notations}

Note that the sequence of iterates $\{\iter_k\}_{k\ge 0}$ is a homogeneous Markov chain~\cite{dieuleveut2017}. 
We denote the (sub-)$\sigma$-algebra (of~$\mathcal{F}$) of events up to and including the $k$-th iteration as $\filtration_k.$
By definition, the discrete-time stochastic process defined in~\eqref{ref:sgd_org} is adapted to its natural filtration~$\{\filtration_k\}_{k\ge 0}$. 
We denote the Markov kernel on $(\rd,\mathcal{B}(\rd))$ associated with SGD iterates~\eqref{ref:sgd_org} by $\kernel$ with 
\begin{equation*}
\kernel(\iter_k,A)=\mpr(\iter_{k+1}\in A| \iter_{k}) ~~\mpr - a.s.,~~~\forall A\in\borel(\rd), k\ge 0\,.
\end{equation*}
Define the $k$-th power of this kernel iteratively: define $\kernel^1:=\kernel,$ and for $k\ge 1,$ for all $\tilde\theta\in\rd$ and $A\in\mathcal{B}(\rd),$ define
\begin{equation*}
\kernel^{k+1}(\tilde\theta,A):=\int_{\rd}\kernel(\tilde\theta,d\theta)\kernel^k (\theta,A)\,.
\end{equation*} 
For any function~$\phi:\rd\to \R$ and $k\ge 0,$ define the measurable function~$\kernel^k\phi(\theta):\rd\to \R$ for all $\theta\in\rd$ via
 \begin{equation*}
\kernel^k\phi(\theta)=\int \phi(\tilde\theta)\kernel^k(\theta,d\tilde\theta)\,.
\end{equation*}
Given the $L_\phi$-Lipschitz function~$\phi:\rd\to\R$ and the expectation of $\phi$ under the stationary measure $\pi_\eta,$ define the function $h$ as
\begin{align*}
h: \rd &\to \R \\
 \theta&\mapsto \phi(\theta)- \sdist(\phi)\,.
\end{align*}  
Note that $\sdist(h)=0$ and $h$ is $L_\phi$-Lipschitz. 
Define the partial sum~$S_n(\phi):=\sum_{k=0}^{n-1}h(\iter_{k}).$ Moreover, we define 
\begin{equation*}
\bariter :=\int _{\rd} \theta d\sdist (\theta)\,.
\end{equation*}  
\subsection{Proofs of Proposition~\ref{ergodicity} and Theorem~\ref{general_clt_arb_sdist}}
We start with some preliminary results required to prove the CLT.
\begin{lemma}\label{lyapunov}
Under Assumptions~\ref{asm:growth}-\ref{asm:noise}, it holds for any 
$\eta\in \left(0,\frac{\alpha-\sqrt{(\alpha^2-{(3L^2+L_\noise)})\vee 0 }}{{3L^2+L_\noise}}\right)$ and any fixed initial point~$\iter_0=\theta_0\in\rd$ that
\begin{equation*}
\E[\,\norm{\iter_{k+1}}^2+1|\filtration_k]\le \alpha_{\dagger}(\,\norm{\iter_k}^2+1)+\beta_{\dagger}\,.
\end{equation*}
Here, $\alpha_{\dagger}\in(0,1)$ and $\beta_{\dagger}\in(0,\infty)$ are constants depending on $\eta.$ 
The explicit formulas of $\alpha_{\dagger},\beta_{\dagger}$ are given in the proof.
\end{lemma}

\begin{proof}[Proof of Lemma~\ref{lyapunov}]
Define $U_{\eta}:=\frac{\alpha-\sqrt{\max \{\alpha^2-{(3L^2+L_\noise)},0 \}}}{  {3L^2+L_\noise} }.$
Given $\eta \in(0,U_{\eta}),$ define 
\begin{equation*}
\alpha_{\dagger}=1+\eta^2{(3L^2+L_\noise)}-2\eta\alpha
\end{equation*}
{and note that with this definition $\alpha_{\dagger} \in (0,1)$ whenever $\eta \in(0,U_{\eta})$.}
Then, with $\eta, \alpha_{\dagger}$, and the fixed initial point~$\iter_0=\theta_0\in\rd,$ we set 
\begin{equation*}
\beta_{\dagger}:={\kappa(\alpha_{\dagger}^{1/2}-\alpha_{\dagger}) }\,,
\end{equation*}
where
\begin{align*}
\kappa:=& \frac{4\eta(\alpha+\beta)+12\eta^2L^2}{ {\alpha_{\dagger}^{1/2}-\alpha_{\dagger}}}
\bigvee 1\,.
\end{align*}
It follows that $\beta_{\dagger}>0.$
Note that
\begin{align*}
&\E[1+\norm{\iter_{k+1}}^2|\filtration_{k}]\\
=&\E[1+\norm{\iter_{k} -\eta\bigl(\grad f(\iter_{k}) + {\noise_{k+1}(\iter_k)}  \bigr)}^2|\filtration_{k}]\\
=&1+\E\bigl[ \,\norm{\iter_{k}}^2 +\eta^2 \,\norm{\grad f(\iter_{k})}^2  +  \eta^2 \,\norm{ {\noise_{k+1}(\iter_k)}  }^2-2\eta\inprod{\iter_k}{\grad f(\iter_k)}|\filtration_k\bigr]\,.
\end{align*}
The last step follows from the Assumption~\ref{asm:noise}.
By Assumption~\ref{asm:growth}, we have
\begin{equation*}
\norm{\grad f(\iter_{k})}^2 \le L^2(1+\norm{\iter_{k}})^2\,.
\end{equation*}
Squaring both sides and using the fact that $(1+\norm{\iter_{k}})^2\le 3(\,\norm{\iter_{k}}^2+3)$ gives
\begin{equation*}
\norm{\grad f(\iter_{k})}^2 \le 3L^2(\,\norm{\iter_{k}}^2+3)\,.
\end{equation*}
By Assumption~\ref{asm:dissipativity}, we obtain
\begin{equation*}
\inprod{\iter_k}{\grad f(\iter_k)}\ge \alpha\,\norm{\iter_k}^2-\beta\,.
\end{equation*}
By Assumption~\ref{asm:noise}, it holds that  
\begin{equation*}
{\E[\,\norm{ \noise_{k+1}(\iter_k) }^2 |\filtration_k]\le L_{\noise}(1+\norm{\iter_k}^2 )\,. }
\end{equation*}
Plugging the previous three inequalities into the first display provides us with
\begin{equation}\label{re:2mom}
\E[1+\norm{\iter_{k+1}}^2|\filtration_{k}]
\le 1+9\eta^2L^2+{\eta^2L_\noise}+2\eta\beta+(1+3\eta^2L^2+{\eta^2L_\noise}-2\eta\alpha)\,\norm{\iter_{k}}^2\,.
\end{equation}
Recall that $\alpha_{\dagger}=1+\eta^2{(3L^2+L_\noise)}-2\eta\alpha.$
Plugging $\alpha_{\dagger}$ back into the previous display yields 
\begin{equation}\label{ref:drift1}
\E[\,\norm{\iter_{k+1}}^2+1|\filtration_k]\le \alpha_{\dagger}(\,\norm{\iter_k}^2+1)+2\eta(\alpha+\beta)+6\eta^2L^2\,.
\end{equation}
Note that $\beta_{\dagger}={\kappa(\alpha_{\dagger}^{1/2}-\alpha_{\dagger}) },$ where 
\begin{equation*}
\kappa\ge  \frac{4\eta(\alpha+\beta)+12\eta^2L^2}{ {\alpha_{\dagger}^{1/2}-\alpha_{\dagger} } }\,.
\end{equation*}
It then follows that $\E[\,\norm{\iter_{k+1}}^2+1|\filtration_k]\le \alpha_{\dagger}(\,\norm{\iter_k}^2+1)+\beta_{\dagger}$ as desired.
\end{proof}


\begin{corollary}[Bounded second moment]\label{bouned2moment}
Under the assumptions stated in Lemma~\ref{lyapunov}, with the constant step size 
$\eta\in \left(0,\frac{\alpha-\sqrt{(\alpha^2-{(3L^2+L_\noise)})\vee 0 }}{{3L^2+L_\noise}}\right)$
the stationary distribution $\sdist$ satisfies 
\begin{equation*}
\mu_{2,\eta} := \int\norm{\theta}^2\sdist(d\theta) \le {3+ \frac{2\beta}{\alpha}}\,.
\end{equation*}
\end{corollary}
\begin{proof}[Proof of Corollary~\ref{bouned2moment}]
Consider the chain~$\chain$ starting from the stationary distribution~$\sdist.$
	By display~\eqref{re:2mom}, it holds that 
	\begin{equation*}
	\E[\norm{\iter_{k+1}}^2]
	\le 9\eta^2L^2+{\eta^2L_\noise}+2\eta\beta+(1+3\eta^2L^2+{\eta^2L_\noise}-2\eta\alpha)\,\norm{\iter_{k}}^2\,.
	\end{equation*}
	Using the fact that by stationarity $\E[\norm{\iter_{k+1}}^2] = \E[\norm{\iter_{k}}^2]$ and rearranging the previous display gives
	\begin{equation*}
	\E[\norm{\iter_{k}}^2]
	\le \frac{9\eta L^2+{\eta L_\noise}+2\beta}{2\alpha-{\eta (3L^2+L_\noise)} }
	\le {3+ \frac{2\beta}{\alpha}}\,.
	\end{equation*}
\end{proof}

\begin{corollary}[Lyapunov condition]\label{drift}
Under the assumptions stated in Lemma~\ref{lyapunov}, {given the step size specified in Lemma~\ref{lyapunov}}, it holds that
\begin{equation*}
\E[V(\iter_{k+1})|\filtration_{k}]\le \alpha_{\dagger} V(\iter_k) +\beta_{\dagger}\,,
\end{equation*}
where the  Lyapunov function~$V(\theta)$ is defined via
\begin{equation}\label{ref:lyapunov_func}
V(\theta):=\norm{\theta}^2+1\,.
\end{equation}
{Observe that by the proof of Lemma {15.2.8} in~\cite{meyn2012} this also implies that the drift condition (V4) in~\cite{meyn2012} holds with $V$ defined above, $b = \beta_\dagger, \beta = (1-\alpha_\dagger)/2$ and the following set~$\mathcal{C}$
\begin{equation}\label{ref:smallset}
\mathcal{C}:= \Big\{\theta\in\rd:V(\theta)\le \frac{2\beta_{\dagger}}{\gamma-\alpha_{\dagger}} \Big\}\,,
\end{equation}
for an arbitrary but fixed $\gamma\in(\alpha_{\dagger}^{1/2},1).$ }
\end{corollary}

\begin{corollary}[Minorization condition]\label{remark:minorization}
Under  Assumptions~\ref{asm:growth}-\ref{asm:noise}, {given the step size specified in Lemma~\ref{lyapunov}},
there exists a constant~$\zeta>0$, and a probability measure~$\nu^{\dagger}$ (depending on $\eta$ which is suppressed in the notation) with $\nu^{\dagger}(\mathcal{C})=1$ and $\nu^{\dagger}(\mathcal{C}^c)=0,$ such that
\begin{equation*}
\kernel(\theta,A)\ge \zeta \nu^{\dagger}(A)
\end{equation*}
holds for any $A\in\mathcal{B}(\rd)$ and $\theta\in \mathcal{C}$ for the set $\mathcal{C}$ defined in~\eqref{ref:smallset}.
\end{corollary}

\begin{proof}[Proof of Corollary~\ref{remark:minorization}]
Recall the definition of the markov chain~\eqref{ref:sgd_org}, we have
\begin{equation*}
{\noise_{k+1}(\iter_k)}= \frac{\iter_k-\iter_{k+1}}{\eta}-\grad f(\iter_k)\,.
\end{equation*}
Recall that the distribution of {$\noise_1(\theta)$} can be decomposed as $\mu_{1,\theta} + \mu_{2,\theta}$ where $\mu_{1,\theta}$ has density $p_{\theta}$.
It then holds for any $\theta\in\rd$ that 
\begin{equation}\label{minor}
\kernel(\theta,\mathcal{C})=\mpr(\iter_{k+1}\in\mathcal{C}|\iter_k=\theta) \geq \int_{t\in\mathcal{C}} \frac{1}{\eta^d}\, {p_{\theta}}\Bigl(\frac{\theta-t}{\eta}-\grad f(\theta) \Bigr) dt>0\,.
\end{equation}
This implies every state in the state space is within reach of any other state over the set $\mathcal{C}.$
Define the probability measure~$\nu^{\dagger}$ with density
\[
p_{\nu^{\dagger}}(t) := I\{\theta \in \mathcal{C}\} \frac{\inf_{\theta\in\mathcal{C}} p(t|\theta) }{\int_{t\in\mathcal{C}} \inf_{\theta\in\mathcal{C}} p(t|\theta) dt}\,,
\]
and set the constant $\zeta:= \int_{t\in\mathcal{C}} \inf_{\theta\in\mathcal{C}} p(t|\theta) dt.$
By Assumption~\ref{asm:noise} and the display~\eqref{minor}, it holds that $\zeta>0,$  $\nu^{\dagger}(\mathcal{C})=1$ and $\nu^{\dagger}(\mathcal{C}^c)=0.$ 
Moreover, it holds that any $A\in\mathcal{B}(\rd)$ and $\theta\in \mathcal{C}$ that 
\begin{equation*}
\kernel(\theta,A)\ge \zeta \nu^{\dagger}(A)\,.
\end{equation*}
This implies the minorization condition is met {for all choices of $\eta$ given by Lemma~\ref{lyapunov}}.
\end{proof}

\begin{lemma}\label{aperiodic_harris}
Under Assumptions~\ref{asm:growth}-\ref{asm:noise}, the chain~$\chain$ is an aperiodic, $\psi$-irreducible, and Harris recurrent chain, with an invariant measure~$\sdist.$
\end{lemma}
\begin{remark}
This lemma implies the chain~$\chain$  is positive.
\end{remark}
\begin{proof}[Proof of Lemma~\ref{aperiodic_harris}]
\textbf{Step 1}: We show that the chain~$\chain$ is aperiodic.
By Assumption~\ref{asm:noise}, there does not exist $d\ge 2$ and a partition of size~$d+1$ such that $\borel(\rd) = (\dot\cup_{i=1}^d D_i) \dot\cup N,$ where $\dot\cup$ denotes the disjoint union, and $N$ is a $\psi$-null (transient) set, such that $\kernel(\theta, D_{i+1})=1$ holds for $\psi$-a.e. $\theta\in D_i.$
Thus, the largest \textit{period} of the chain defined in~\eqref{ref:sgd_org} is 1, which implies the chain is aperiodic.\\
\textbf{Step 2}: We show that the chain~$\chain$ is $\psi$-irreducible, and recurrent with an invariant probability measure.
We note that by Assumption~\ref{asm:noise}, there exists some non-zero $\sigma$-finite measure~$\psi$ on~$(\rd,\borel(\rd))$ such that for any $\theta\in\rd$ and any $A\in\borel(\rd)$ with $\psi(A)>0,$ it holds that 
\begin{equation*}
\mpr(\iter_{k+1}\in A|\iter_k=\theta) 
\geq \int_{\tilde\theta\in A} \frac{1}{\eta^d}\, {p_{\theta}}\Bigl(\frac{\theta-\tilde\theta}{\eta}-\grad f(\theta) \Bigr) d\tilde\theta >0\,,
\end{equation*}
where $p_{\theta}$ was defined in Assumption~\ref{asm:noise}. This implies the Markov chain defined in~\eqref{ref:sgd_org} is $\psi$-irreducible.
By the Lyapunov condition established in Corollary~\ref{drift}, part (iii) of Theorem 15.0.1 in~\cite{meyn2012} holds.
It then follows by condition (i) of this theorem that  the chain~$\chain$ is recurrent with an  invariant probability measure $\sdist.$\\
\textbf{Step 3}: We show that the chain is Harris recurrent.
Define the hitting time~$\tau_{\mathcal{C}}:=\inf\{n>0: \iter_n\in \mathcal{C}\},$ where the set~$\mathcal{C}$ is defined in~\eqref{ref:smallset}. 
By Corollary A.4 in \cite{mattingly2002}, it holds for any fixed $\iter_0=\theta_0\in\rd$ that
\begin{align*}
\mpr(\tau_{\mathcal{C}}<\infty) = 1\,.
\end{align*} 
By Proposition 10.2.4 in~\cite{douc2018}, the chain is Harris recurrent.
\end{proof}


\noindent Now, we are ready to prove Proposition~\ref{ergodicity}.
\vspace{-0.1in}
\begin{proof}[Proof of Proposition~\ref{ergodicity}]
(a) By Lemma~\ref{aperiodic_harris}, the chain~$\chain$ is an aperiodic Harris recurrent chain, with an invariant measure~$\sdist.$
Note that the chain is also positive. Thus condition (i) of Theorem 13.0.1 in~\cite{meyn2012} is satisfied and this implies the existence of a unique invariant measure~$\sdist$.  
The fact that this stationary distribution has a finite second moment was established in Corollary~\ref{bouned2moment}.
\\
(b)
By Lemma~\ref{aperiodic_harris}, the iterates~$\chain$ are realiztions from a $\psi$-irreducible and aperiodic chain. Note that 
\begin{align*}
|\phi(\theta)|\le& \kappa_{\phi}(1+\norm{\theta})\\
\le&2\kappa_{\phi}\sqrt{1+\norm{\theta}^2}\\
\le & 2\kappa_{\phi}V(\theta)\,.
\end{align*}
By Corollary~\ref{drift}, the condition (iv) of Theorem 16.0.1 in~\cite{meyn2012} with $V(\theta)=2\kappa_{\phi}(1+\norm{\theta}^2)$ is fulfilled.
By part (ii) in that theorem, it holds that for fixed $\iter_0=\theta_0\in\rd$
\begin{align*}
|\kernel^k\phi(\theta_0)-\sdist(\phi)|
 \le & \kappa \rho^{k} V(\theta_0)\,,
\end{align*}
where $\rho\in(0,1), \kappa > 0$ are constants depending on $\phi$.
\end{proof}

\noindent We now prove Theorem~\ref{general_clt_arb_sdist}. In order to do so, we first derive the central limit theorem for the function $h$ when the Markov chain starting from its stationary distribution $\sdist.$ 
\begin{lemma}[CLT with stationary initial distribution]
\label{general_clt_sdist}
Assume Assumptions~\ref{asm:growth}-\ref{asm:noise} hold.
For any step size~$\eta\in \left(0,\frac{\alpha-\sqrt{(\alpha^2-{(3L^2+L_\noise)})\vee 0 }}{{3L^2+L_\noise}}\right)$, it holds that 
\begin{equation*}
n^{-1/2}S_n(\phi) \underset{\mpr_{\sdist}}{\longrightarrow}\mathcal{N}(0,\sigma^2_{\sdist}(\phi))\,,
\end{equation*}  
where $\sigma^2_{\sdist}(\phi)= 2\sdist(h\hat h)-\sdist(h^2)$ with $\hat h = \sum_{k=0}^\infty \kernel^k h.$
\end{lemma}

\begin{proof}[Proof of Lemma~\ref{general_clt_sdist}]
We prove the claim by appealing to Theorem 17.0.1 in \cite{meyn2012}. 
In order to do so, we first show that the chain~$\chain$ is $V$-uniformly ergodic, 
where the function $V$ is defined in~\eqref{ref:lyapunov_func}. 
Then, we establish the CLT by employing Theorem 17.0.1 in \cite{meyn2012}. 
\\
\textbf{Step 1}: We show that the chain~$\chain$ is $V$-uniformly ergodic.
By Lemma~\ref{aperiodic_harris} and Proposition~\ref{ergodicity}, the chain~$\chain$ is positive Harris recurrent with a unique stationary distribution~$\sdist.$
Note that the chain~$\chain$ is also $\psi$-irreducible and aperiodic. 
By Corollary~\ref{drift}, condition (iv) of Theorem 16.0.1 in~\cite{meyn2012} is satisfied.
Then, it follows from part (i) of this theorem that the iterates~$\chain$ is $V$-uniformly ergodic.\\
\textbf{Step 2}: We now establish the CLT for the averaged SGD iterates starting from the stationary distribution~$\sdist$. 
Note that for the test function~$\phi(\theta),$ it holds for any $\theta\in\rd$ that
\begin{equation*}
|\phi(\theta)|\le \kappa_{\phi}(1+\norm{\theta})\le 2\kappa_{\phi}\sqrt{1+\norm{\theta}^2}\,,
\end{equation*}
which implies
\begin{equation*}
|\phi(\theta)|^2 \le 4\kappa^2_{\phi}V(\theta)\,.
\end{equation*}
Thus the conditions required to leverage Theorem 17.0.1 (ii), (iv) with $g(\theta) = \phi(\theta)$ in~\cite{meyn2012} are satisfied. Hence, by Theorem 17.0.1 in~\cite{meyn2012}, we obtain
\begin{equation*}
\frac{1}{\sqrt{n}}\sum_{k=0}^{n-1} h(\iter_k) \underset{\mpr_{\sdist}}{\longrightarrow}\mathcal{N}(0,\sigma^2_{\sdist}(\phi))\,,
\end{equation*}  
where $\sigma^2_{\sdist}(\phi)=2\sdist(h\hat h)-\sdist(h^2)>0.$
\end{proof}


\begin{proof}[Proof of Theorem~\ref{general_clt_arb_sdist}]
By Lemma~\ref{aperiodic_harris} and Lemma~\ref{general_clt_sdist}, the desired result follows readily from Proposition 17.1.6 in~\cite{meyn2012}.
\end{proof}

\subsection{Proofs of Proposition~\ref{bias_wo_local}, Theorems~\ref{bias_wz_disp},~\ref{bias_wz_loja}, and~\ref{bias_wz_convex}}
We need the following auxiliary lemma.

\begin{lemma}\label{dissipativity_global}
Assumptions~\ref{asm:growth} and~\ref{asm:dissipativity} implies
\begin{align*}
\inprod{\grad f(\theta)}{\theta-\theta^*}\ge 
\alpha'\norm{\theta-\theta^*}^2-\beta'  \,,
\end{align*}
where $\theta^*\in\rd$ is any critical point of function~$f$, and $\alpha',\beta'$ are positive constants.
\end{lemma}
\begin{proof}[Proof of Lemma~\ref{dissipativity_global}]
When $\theta^*=\mathbf{0},$ the result follows trivially from Assumption~\ref{asm:dissipativity}.
Assume $\norm{\theta^*}>0.$
Note that 
\begin{align*}
\inprod{\grad f(\theta)}{\theta-\theta^*} =   \inprod{\grad f(\theta)}{\theta}- \inprod{\grad f(\theta)}{\theta^*}\,.
\end{align*}
By Assumption~~\ref{asm:dissipativity}, it holds that
\begin{align*}
 \inprod{\grad f(\theta)}{\theta}&\ge \alpha\norm{\theta}^2-\beta\\
 &\ge  \alpha (\norm{\theta-\theta^*}^2+\norm{\theta^*}^2-2\norm{\theta^*}\norm{\theta-\theta^*})-\beta\,.
\end{align*}
By Assumption~~\ref{asm:growth}, Cauchy-Schwarz inequality and triangular inequality, it holds that
\begin{align*}
\inprod{\grad f(\theta)}{\theta^*}&\le \norm{\grad f(\theta)}\norm{\theta^*} \le  L\norm{\theta^*}(1+\norm{\theta-\theta^*}+\norm{\theta^*})\,.
\end{align*}
Combing the previous two displays yields 
\begin{align*}
&\inprod{\grad f(\theta)}{\theta-\theta^*} \\
\ge& \alpha (\norm{\theta-\theta^*}^2+\norm{\theta^*}^2-2\norm{\theta^*}\norm{\theta-\theta^*})-\beta -L\norm{\theta^*}(1+\norm{\theta-\theta^*}+\norm{\theta^*})  \\
\ge & \frac{\alpha}{2}\norm{\theta-\theta^*}^2-\beta-L\norm{\theta^*}^2-L\norm{\theta^*}\,.
\end{align*}
The desired result follows by setting $\alpha':=\frac{\alpha}{2}$ and $\beta':=\beta+\bigl(   \sqrt{\alpha } +\frac{2L}{\sqrt{\alpha}}\bigr)^2\norm{\theta^*}^2+L\norm{\theta^*}.$
\end{proof}

{
\begin{lemma}\label{noise_local}
Under Assumptions~\ref{asm:dissipativity} and~\ref{asm:noise_bias}, it holds for any $k\ge 1$ and $\theta\in\rd$ that
\begin{align*}
\E[\norm{\noise_{k+1}(\theta)}^{r}]\le {L'_{\noise}}^{r/4}(1+\norm{\theta-\theta^*}^r)\,, \ \text{ for }\ \ r \in\{2,3,4\},
\end{align*}
 where $\theta^*\in\rd$ is any critical point of function~$f$, and $L'_\noise :=8L_\noise(1+(\beta/\alpha)^4).$
 \end{lemma}
\begin{proof}[Proof of Lemma~\ref{noise_local}]
By Assumptions~\ref{asm:dissipativity} and~\ref{asm:noise_bias}, it holds that
\begin{align*}
 \E[\norm{\noise_{k+1}(\theta)}^4]
 &\le L_{\noise}(1+\norm{\theta}^4)\\
 &\le L_{\noise}(1+8\norm{\theta-\theta^*}^4+8\norm{\theta^*}^4)\\
 &\le L_{\noise}(1+8\norm{\theta-\theta^*}^4+8(\beta/\alpha)^4)\\
 &\le L'_\noise (1+\norm{\theta-\theta^*}^4 )\,,
\end{align*}
where $L'_\noise :=8L_\noise(1+(\beta/\alpha)^4).$
Similarly, for $r\in \{2,3\}$ we have
\begin{align*}
 \E[\norm{\noise_{k+1}(\theta)}^r]
 &\leq  \E[\norm{\noise_{k+1}(\theta)}^4]^{r/4}\\
 &\le L_{\noise}^{r/4}(1+\norm{\theta}^4)^{r/4}\\
  &\le L_{\noise}^{r/4}(1+\norm{\theta}^r)\\
 &\le L_{\noise}^{r/4}(1+2^{r-1}\norm{\theta-\theta^*}^r+2^{r-1}\norm{\theta^*}^r)\\
 &\le L_{\noise}^{r/4}(1+2^{r-1}\norm{\theta-\theta^*}^r+2^{r-1}(\beta/\alpha)^r)\\
 &\le {L'_\noise}^{r/4} (1+\norm{\theta-\theta^*}^r )\,,
\end{align*}
where ${L'_\noise}$ is defined above.
\end{proof}
}

\begin{lemma}\label{4mom_decomp}
Under Assumptions~\ref{asm:growth},~\ref{asm:dissipativity}, and~\ref{asm:noise_bias}, {with step size~$\eta< 1\wedge \frac{1}{10 \bar L}$,} it holds for any $k\ge 0$ that
\begin{align}
&\E[\norm{\iter_{k+1}-\theta^*}^4|\filtration_k]\\
 \le&  (1-4\eta\alpha'+32L_\dagger\eta^2) \norm{\iter_k-\theta^*}^4
     + \eta (4\beta'+24\bar L^2+12{ {L'_\noise}^{1/2}} +64)\norm{\iter_k-\theta^*}^2\\
     &+ \eta^2(64\bar L^4 + 8{L'_\noise}   + 32( 4\bar L^3)^2 + 32  {(L'_\noise)^{3/2}}) \label{eq:bound4mom}\,.
\end{align}
where {$L_\dagger:= \bar L^2+ 16\Bigl( L_\noise^{3/4}(1+(\beta/\alpha)^3 )\vee 
L_\noise^{1/2}(1+(\beta/\alpha)^2 )\vee
L_\noise(1+(\beta/\alpha)^4 )
\Bigr) $ 
with $\bar L:=L(1+\norm{\theta^*})$, $L'_\noise$ is from  Lemma~\ref{noise_local}, and $\theta^*$ is any critical points of fuction~$f.$}
\end{lemma}
\begin{proof}[Proof of Lemma~\ref{4mom_decomp}]
Define $\Delta_k:=\norm{\iter_k-\theta^*}.$
It holds by Assumption~\ref{asm:growth} that
\begin{equation*}
\norm{\grad f(\iter_k)}\le \bar L\Delta_k+\bar L\,,
\end{equation*}
where $\bar L=L(\norm{\theta^*}+1).$
Note that
\begin{align}
\label{ref:4mom_decp}
\begin{split}
\Delta_{k+1}^4
=& (\Delta_k^2+\eta^2\,\norm{\grad f(\iter_k)+{\noise_{k+1}(\iter_k)} }^2-2\eta\inprod{\grad f(\iter_k)+{\noise_{k+1}(\iter_k)}}{\iter_k-\theta^*})^2\\
=&\Delta_k^4+\eta^4\,\norm{\grad f(\iter_k)+{\noise_{k+1}(\iter_k)}}^4+4\eta^2 \inprod{\grad f(\iter_k)+{\noise_{k+1}(\iter_k)}}{\iter_k-\theta^*}^2\\
&+2\eta^2\Delta_k^2\,\norm{\grad f(\iter_k)+{\noise_{k+1}(\iter_k)}}^2-4\eta\Delta_k^2\inprod{\grad f(\iter_k)+{\noise_{k+1}(\iter_k)} }{\iter_k-\theta^*}\\
&-4\eta^3 \,\norm{\grad f(\iter_k)+{\noise_{k+1}(\iter_k)} }^2\inprod{\grad f(\iter_k)+{\noise_{k+1}(\iter_k)} }{\iter_k-\theta^*}\\
=&\Delta_k^4+ \RN{1}+\RN{2}+\RN{3}+\RN{4}+\RN{5}\,,
\end{split}
\end{align}
where
\begin{align*}
\RN{1}&:=\eta^4\,\norm{\grad f(\iter_k)+{\noise_{k+1}(\iter_k)}}^4\\
\RN{2}&:=4\eta^2 \inprod{\grad f(\iter_k)+{\noise_{k+1}(\iter_k)}}{\iter_k-\theta^*}^2\\
\RN{3}&:=2\eta^2\Delta_k^2\,\norm{\grad f(\iter_k)+{\noise_{k+1}(\iter_k)}}^2\\
\RN{4}&:=-4\eta\Delta_k^2\inprod{\grad f(\iter_k)+{\noise_{k+1}(\iter_k)}}{\iter_k-\theta^*}\\
\RN{5}&:=-4\eta^3 \,\norm{\grad f(\iter_k)+{\noise_{k+1}(\iter_k)}}^2\inprod{\grad f(\iter_k)+{\noise_{k+1}(\iter_k)}}{\iter_k-\theta^*}\,.
\end{align*}
To obtain the expectation~$\E[\Delta_{k+1}^4],$ we first calculate the conditional expectation~$\E[\Delta_{k+1}^4|\filtration_k]$.
For this, we proceed the conditional expectation of the above five terms separately.
Note that 
\begin{align*}
\E[\RN{1}|\filtration_k]=&\eta^4\E[\,\norm{\grad f(\iter_k)+{\noise_{k+1}(\iter_k)}}^4|\filtration_k]\\
\le &\eta^4\E[8\,\norm{\grad f(\iter_k)}^4 +8\,\norm{{\noise_{k+1}(\iter_k)}}^4|\filtration_k]\\
\le& 8\eta^4 (8\bar L^4\Delta_k^4+ 8\bar L^4 +{ L'_\noise \Delta_k^4 +L'_\noise} )\,.
\end{align*}
The first inequality follows from the fact that $(x+y)^4\le 8(x^4+y^4), \forall x, y >0.$
The last inequality follows from Assumptions~\ref{asm:growth} and Lemma~\ref{noise_local}.
Using the same trick and invoking Cauchy-Schwarz inequality gives 
\begin{align*}
\E[\RN{2}|\filtration_k]=&4\eta^2\E[ \inprod{\grad f(\iter_k)+{\noise_{k+1}(\iter_k)} }{\iter_k-\theta^*}^2|\filtration_k]\\
\le & 4\eta^2\Delta_k^2 \E[\,\norm{\grad f(\iter_k)+{\noise_{k+1}(\iter_k)} }^2|\filtration_k] \\
\le & 8\eta^2\Delta_k^2 (2\bar L^2 \Delta_k^2+2\bar L^2+{ {L'_\noise}^{1/2} \Delta_k^2 + {L'_\noise}^{1/2}}  )\,.
\end{align*}
Similarly, we have
\begin{align*}
\E[\RN{3}|\filtration_k]=& 2\eta^2\Delta_k^2\E[ \,\norm{\grad f(\iter_k)+{\noise_{k+1}(\iter_k)} }^2|\filtration_k]\\
\le &  4\eta^2\Delta_k^2(2\bar L^2 \Delta_k^2+2\bar L^2+{ {L'_\noise}^{1/2} \Delta_k^2 + {L'_\noise}^{1/2}} )\,.
\end{align*}
Using Cauchy-Schwarz inequality again, we obtain
\begin{align*}
\E[\RN{5}|\filtration_k]
=& \E[ -4\eta^3 \,\norm{\grad f(\iter_k)+{\noise_{k+1}(\iter_k)}}^2\inprod{\grad f(\iter_k)+{\noise_{k+1}(\iter_k)}}{\iter_k-\theta^*}|\filtration_k]\\
\le & 4\eta^3 \E[\norm{\grad f(\iter_k)+{\noise_{k+1}(\iter_k)}}^3\norm{\iter_k-\theta^*}|\filtration_k] \\
= & 4\eta^3 \Delta_k\E\bigl[\norm{\grad f(\iter_k)+{\noise_{k+1}(\iter_k)}}^3|\filtration_k\bigr] \\
\le & 4\eta^3 \Delta_k\E\bigl[4\norm{\grad f(\iter_k)}^3+4\norm{{\noise_{k+1}(\iter_k)}}^3|\filtration_k\bigr]\,.
\end{align*}
{Note that by Lemma~\ref{noise_local}, it holds for any $k\ge 1$ and $\theta\in\rd$ that 
\begin{align*}
\E[\norm{\noise_k(\theta)}^3] \le {L'_{\noise}}^{3/4} (1+\norm{\theta-\theta^*}^3)\,.
\end{align*}
Combining this with the previous display yields
\begin{align*}
\E[\RN{5}|\filtration_k]
\le & 16\eta^3\Delta_k(4\bar L^3\Delta_k^3+ 4\bar L^3+{L'_{\noise}}^{3/4}+{L'_{\noise}}^{3/4}\Delta_k^3) \\
=& 64\bar L^3\eta^3\Delta_k^4+ 16\eta^3{L'_{\noise}}^{3/4}\Delta_k^4 + 16\eta^2(\Delta_k\eta 4\bar L^3+\Delta_k\eta{L'_{\noise}}^{3/4})\,.
\end{align*}
}
Collecting pieces gives 
\begin{align}
\begin{split}
\E[\Delta_{k+1}^4|\filtration_k] 
\le& \Delta_{k}^4(1+64\eta^4\bar L^4+64\eta^3\bar L^3+24\eta^2\bar L^2 +{8\eta^2L'_\noise+ 12 \eta^2{L'_\noise}^{1/2} +16\eta^2 {L'_{\noise}}^{3/4}})\\
        &-4\eta\Delta_k^2\inprod{\grad f(\iter_k)}{\iter_k-\theta^*}\\
       &+\eta^2\bigl(64\eta^2\bar L^4+ 8\eta^2{L'_\noise}+ 24\bar L^2 \Delta_{k}^2+12{L'_\noise}\Delta_{k}^2
       + 64 \Delta_{k}^2 + 32(\eta 4\bar L^3)^2 + 32 (\eta{{L'_\noise}^{3/4}})^2\bigr)\\
\le & \Delta_{k}^4[1 +32\eta^2(\bar L^2+ {L'_{\noise}+{L'_\noise}^{1/2} +{L'_{\noise}}^{3/4}  })]-4\eta\Delta_k^2\inprod{\grad f(\iter_k)}{\iter_k-\theta^*}\\
    &+\eta\bigl(64\bar L^4 \eta+ 8{L'_\noise} \eta + 24\bar L^2 \Delta_{k}^2+12{ {L'_\noise}^{1/2}}\Delta_{k}^2
    + 64 \Delta_{k}^2 + 32( 4\bar L^3)^2 \eta+ 32 {(L'_\noise)^{3/2}}\eta\bigr)\,.
\end{split}
\end{align}
The above inequalities are based on the fact that $\eta<\frac{1}{10\bar L} \wedge 1$ and $xy\le 2x^2+ 2y^2,\forall x, y >0.$
By Lemma~\ref{dissipativity_global}, we handle the term~$\RN{4}$ as following  
\begin{align*}
\E[\Delta_{k+1}^4|\filtration_k]
\le &\Delta_{k}^4 \bigl(1-4\eta\alpha'+32\eta^2(\bar L^2+  {L'_{\noise}+{L'_\noise}^{1/2} +{L'_{\noise}}^{3/4}  }) \bigr) \\
&+ \eta\bigl(4\beta'\Delta_{k}^2+ 64\bar L^4 \eta+ 8{L'_\noise} \eta + 24\bar L^2 \Delta_{k}^2+12{{L'_\noise}^{1/2}}\Delta_{k}^2
    + 64 \Delta_{k}^2 + 32( 4\bar L^3)^2 \eta+ 32 {{L'_\noise}^{3/2}}\eta\bigr)\,.
\end{align*}
{Define $L_\dagger:= \bar L^2+ 16\Bigl( L_\noise^{3/4}(1+(\beta/\alpha)^3 )\vee 
L_\noise^{1/2}(1+(\beta/\alpha)^2 )\vee
L_\noise(1+(\beta/\alpha)^4 )
\Bigr) $.
Note that $L_\dagger>\bar L^2+  L'_{\noise}+{L'_{\noise}}^{1/2}+{L'_{\noise}}^{3/4}.$ 
Combing this with the previous display gives
\begin{align}
&\E[\Delta_{k+1}^4|\filtration_k]\\
\le &\Delta_{k}^4 (1-4\eta\alpha'+32\eta^2L_\dagger ) \\
&+ \eta\bigl(4\beta'\Delta_{k}^2+ 64\bar L^4 \eta+ 8{L'_\noise} \eta + 24\bar L^2 \Delta_{k}^2+12{ {L'_\noise}^{1/2}}\Delta_{k}^2
    + 64 \Delta_{k}^2 + 32( 4\bar L^3)^2 \eta+ 32 {{L'_\noise}^{3/2}}\eta\bigr) \\
 \le&  (1-4\eta\alpha'+32L_\dagger\eta^2) \Delta_{k}^4 
     + \eta (4\beta'+24\bar L^2+12{ {L'_\noise}^{1/2}} +64) \Delta_{k}^2
     + \eta^2(64\bar L^4 + 8{L'_\noise}   + 32( 4\bar L^3)^2 + 32  {{L'_\noise}^{3/2}})   \,. 
\end{align}}

\end{proof}


\begin{lemma}\label{bound4mom}
Assume Assumptions~\ref{asm:growth}-\ref{asm:noise} holds. With the step size~
\begin{equation*}
\eta \le  \frac{\alpha-\sqrt{(\alpha^2-{(3L^2+L_\noise)})\vee 0 }}{{3L^2+L_\noise}} 
\wedge  \frac{\alpha}{64 L_\dagger} 
\wedge 1\,,
\end{equation*}
 the chain~\eqref{ref:sgd_org} has the stationary distribution~$\sdist$, and the chain has finite 4-th moment:
\begin{align*}
&\E[\norm{\iter_{k+1}}^4] \le \mu_{4,\eta}\,,
\end{align*}
where
\begin{align*}
\mu_{4,\eta}:=\frac{8}{7\alpha}\Bigl( (\beta+6 L^2+3  {L_\noise^{1/2}}  +16) \mu_{2,\eta} +   16 L^4 + 2  {L_\noise} + 128 L^6 + 8  {L_\noise^{3/2}} \Bigr)\,
\end{align*}
with $\mu_{2,\eta}$ defined in Corollary~\ref{bouned2moment},
and  { $L_\dagger$ defined in Lemma~\ref{4mom_decomp}. }
\end{lemma}
\begin{proof}[Proof of Lemma~\ref{bound4mom}]
Similar to display~\eqref{eq:bound4mom}, we can derive 
\begin{align*}
\E[\norm{\iter_{k+1}}^4|\filtration_k]
\le & (1-4\eta\alpha+32  {L_0^\dagger}\eta^2) \norm{\iter_{k}}^4 \\
&+ \eta\bigl[(4\beta+24 L^2+12 {L_\noise^{1/2}} +64)\norm{\iter_{k}}^2+ \eta(64 L^4 + 8 {L_\noise}   + 32( 4 L^3)^2 + 32 {L_\noise^{3/2}} )\bigr]\,,
\end{align*}
{where $L_0^\dagger:= L^2+  L_{\noise}+L_{\noise}^{1/2}+L_{\noise}^{3/4}$.
Recall the definition of $L_\dagger$ in Lemma~\ref{4mom_decomp}, it holds that $L_\dagger\ge L_0^\dagger,$ which implies  
\begin{align*}
\E[\norm{\iter_{k+1}}^4|\filtration_k]
\le & (1-4\eta\alpha+32 {L_\dagger}\eta^2) \norm{\iter_{k}}^4 \\
&+ \eta\bigl[(4\beta+24 L^2+12{L_\noise^{1/2}} +64)\norm{\iter_{k}}^2+ \eta(64 L^4 + 8 {L_\noise}   + 32( 4 L^3)^2 + 32 {L_\noise^{3/2}} )\bigr]\,,
\end{align*}
 }
Note that the chain starts from the stationary distribution~$\sdist$, taking the expectation on both sides gives 
\begin{align*}
&(4\eta\alpha-32 {L_\dagger}\eta^2) \E[\norm{\iter_{k}}^4]\\
\le &  \eta(4\beta+24 L^2+12 {L_\noise^{1/2}} +64)\E[\norm{\iter_{k}}^2]+ \eta^2 (64 L^4 + 8 {L_\noise}   + 32( 4 L^3)^2 + 32 {L_\noise^{3/2}}  )\,.
\end{align*}
We also note that $\E[\norm{\iter_{k}}^2] = \mu_{2,\eta}$ for $\mu_{2,\eta}$ from Corollary~\ref{bouned2moment}. 
Plugging this into the previous display and rearranging the inequality gives
\begin{align*}
&\E[\norm{\iter_{k+1}}^4]\\
\le & \frac{\eta}{4\eta\alpha-32 {L_\dagger} \eta^2}(4\beta+24 L^2+12 {L_\noise^{1/2}} +64) \mu_{2,\eta}+ \frac{\eta^2}{4\eta\alpha-32 {L_\dagger} \eta^2} (64 L^4 + 8 {L_\noise} 
 + 32( 4 L^3)^2 + 32  {L_\noise^{3/2}} )\\
 \le &  \frac{\eta}{4\eta\alpha-32 {L_\dagger}\eta^2}(4\beta+24 L^2+12 {L_\noise^{1/2}} +64) \mu_{2,\eta}+ \frac{\eta}{4\eta\alpha-32 {L_\dagger}\eta^2} (64 L^4 + 8 {L_\noise}
 + 32( 4 L^3)^2 + 32 {L_\noise^{3/2}} )\\
 \le & \frac{2}{7\alpha}\Bigl[(4\beta+24 L^2+12 {L_\noise^{1/2}}  +64) \mu_{2,\eta} +   (64 L^4 + 8 {L_\noise} + 32( 4 L^3)^2 + 32 {L_\noise^{3/2}} ) \Bigr]
\end{align*}
as desired.
\end{proof}

We are now ready to prove Proposition~\ref{bias_wo_local}.
\begin{proof}[Proof of Proposition~\ref{bias_wo_local}]
Define $\Delta_k:=\norm{\iter_k-\theta^*}.$
By Lemma~\ref{4mom_decomp}, we have
\begin{align}
&\E[\Delta_{k+1}^4|\filtration_k]\\
 \le&  (1-4\eta\alpha'+32L_\dagger\eta^2) \Delta_{k}^4
     + \eta (4\beta'+24\bar L^2+12{ {L'_\noise}^{1/2}} +64)\Delta_{k}^2\\
     &+ \eta^2(64\bar L^4 + 8{L'_\noise}   + 32( 4\bar L^3)^2 + 32  {{L'_\noise}^{3/2}}) \,.
\end{align}
Taking expectation on both sides then gives
\begin{align} 
&\E[\Delta_{k+1}^4]\\
\le & (1-4\eta\alpha'+32 {L_\dagger}\eta^2) \E[\Delta_{k}^4]
      + \eta(4\beta'+24\bar L^2+12{ {L'_\noise}^{1/2}} +64)\E[\Delta_{k}^2]\\
      &+ \eta^2(64\bar L^4 + 8{L'_\noise}  + 32( 4\bar L^3)^2 + 32 {{L'_\noise}^{3/2}})\,.
\end{align}
Set 
\begin{align*}
\varrho&:= 1-4\eta\alpha'+32{L_\dagger}\eta^2\\
A_1&:= 64\bar L^4+8{L'_\noise}+32(4\bar L^3)^2 + 32{{L'_\noise}^{3/2}} \\
A_2&:= 4\beta'+24\bar L^2+12{ {L'_\noise}^{1/2}}+64\,.
\end{align*}
By Cauchy-Schwatz inequality, we then have
\begin{align*}
\E[\Delta_{k+1}^4]
\le \varrho\E[\Delta_{k}^4]+ A_1\eta^2 + A_2 \E^{1/2}[\Delta_{k}^4]\eta\,.
\end{align*}
Note that when   $0<\eta< \frac{\alpha'-\sqrt{(\alpha'^2-4{L_\dagger})}}{16{L_\dagger}}\1(\alpha'^2> 8 {L_\dagger})
+\frac{\alpha'}{32{L_\dagger}}\1(\alpha'^2\le 8 {L_\dagger}),$ it follows that 
\begin{equation*}
\varrho > \frac{1}{2}\1 (\alpha'^2\ge 8{L_\dagger}) + (1-\frac{3\alpha'^2}{32{L_\dagger^2}})\1 (\alpha'^2< 8{L_\dagger})\ge\frac{1}{4}\,.
\end{equation*}
Set $D:=\sqrt{A_1}\vee A_2.$
We then find 
\begin{align*}
\E^{1/2}[\Delta_{k+1}^4] \le \sqrt{\varrho}\, \E^{1/2}[\Delta_{k}^4] + D\eta\,.
\end{align*}
By a straightforward induction, we have
\begin{align*}
\E^{1/2}[\Delta_{k}^4] \le \varrho^{k/2}\E^{1/2}[\Delta_{0}^4] + \frac{D\eta}{1-\sqrt{\varrho}}\,.
\end{align*}
Notice that $\eta\le \frac{\alpha'}{16{L_\dagger}},$ it then follows that
\begin{align*}
\varrho &= 1-4\eta\alpha'+32{L_\dagger}\eta^2 \le 1-2\eta\alpha'\,,
\end{align*}
which implies
\begin{align*}
\frac{1}{1-\sqrt{\varrho}}\le  \frac{1}{1-\sqrt{1-2\eta\alpha'}} \le  \frac{1}{\eta\alpha'}\,.
\end{align*}
Combining this with previous display gives 
\begin{align*}
\E^{1/2}[\Delta_{k}^4] \le \varrho^{k/2}\E^{1/2}[\Delta_{0}^4] + \frac{D}{\alpha'}\,.
\end{align*}
By Proposition~\ref{ergodicity}, there exists a unique stationary distribution~$\sdist$.

Consider the chain starting from the stationary distribution~$\sdist.$
Note that $\E[\Delta_{0}^4]\le 8(\E[\norm{\iter_0}^4]+\norm{\theta^*}^4).$
By Lemma~\ref{bound4mom}, it follows that 
\begin{equation*}
\E[\Delta_{0}^4]\le 8\mu_{4,\eta} + 8\norm{\theta^*}^4\,,
\end{equation*}
where the constant~$\mu_{4,\eta}$ is defined in Lemma~\ref{bound4mom}.
Plugging this into previous display provides us with

\begin{equation*}
\Bigl(\int\norm{\theta-\theta^*}^4\sdist(d\theta)\Bigr)^{1/4}=\mathcal{O}(1)\,.
\end{equation*}
Note that it holds for the $L_\phi$-Lipschitz continuous test function $\phi$ that
\begin{align*}
|\sdist(\phi)-\phi(\theta^*)|&\le L_{\phi}\int\norm{\theta-\theta^*}\sdist(d\theta) \\
&\le L_{\phi}\Bigl[\int\norm{\theta-\theta^*}^4\sdist(d\theta)\Bigr]^{1/4}\,,
\end{align*}
Thus, we obtain
\begin{align*}
|\sdist(\phi)-\phi(\theta^*)|=\bigo(1)
\end{align*}
as desired.


\end{proof}


\begin{lemma}\label{truncation}
For any $a,b,\delta>0,$ it holds for any $x\ge \frac{\delta}{a}+\sqrt{\frac{b}{a}}$ that 
\begin{equation*}
ax^2-b\ge \delta x\,.
\end{equation*}
\end{lemma}
\begin{proof}[Proof of Lemma~\ref{truncation}]
Define the function~$h(x):= ax^2-b-\delta x.$
When $x\ge \frac{\delta+\sqrt{\delta^2+4ab}}{2a},$ it holds that $h(x)\ge 0.$
Note that $\sqrt{\delta^2+4ab}\le \delta+\sqrt{4ab},$ it follows that when 
\begin{equation*}
x\ge \frac{\delta +\delta+\sqrt{4ab}}{2a}\,,
\end{equation*}
it holds that $h(x)\ge 0$.
The desired result then follows readily.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{bias_wz_disp}]
  Consider the chain~$\chain$ starting from the stationary distribution~$\sdist.$
  Define~$\Delta_{k}:= \norm{\iter_{k}-\theta^*}.$
  Note that under Assumptions~\ref{asm:dissipativity2} and~\ref{asm:noise_bias}, Lemma~\ref{noise_local} still holds.
  By Assumptions~\ref{asm:growth},~\ref{asm:noise_bias}, and Lemma~\ref{noise_local} , we have
\begin{align*}
&\E\bigl[\Delta_{k+1}^2|\filtration_{k}\bigr]\\
=&\E\bigl[\Delta_{k}^2 +\eta^2 \,\norm{\grad f(\iter_{k})}^2  +  \eta^2 \,\norm{{\noise_{k+1}(\iter_k)} }^2-2\eta\inprod{\grad f(\iter_k)}{\iter_k-\theta^*}|\filtration_k\bigr]\\
\le &   \Delta_{k}^2 +\eta^2\bigl(3L^2(2\Delta_k^2 +2\norm{\theta^*}^2+3) + {{L'_\noise}^{1/2}(1+\Delta_{k}^2)} \bigr)-2\eta\inprod{\grad f(\iter_k)}{\iter_k-\theta^*}\\
=&  \Delta_{k}^2 +6L^2\eta^2\Delta_k^2 +{{L'_\noise}^{1/2} \eta^2 \Delta_k^2  }+\eta^2C_1-2\eta\inprod{\grad f(\iter_k)}{\iter_k-\theta^*}  
\end{align*}
where $C_1:= 6\norm{\theta^*}^2L^2+9L^2+{{L'_\noise}^{1/2}}.$
Note that the chain starts from the stationary distribution~$\sdist,$ which implies $\E[\Delta_{k+1}^2]=\E[\Delta_k^2]$ for all $k\ge 0.$
Taking the expectation on both sides and rearranging the inequality yields
\begin{equation}
\E[\inprod{\grad f(\iter_k)}{\iter_k-\theta^*}]\le {\eta (3L^2+{L'_\noise}^{1/2})}\E[\Delta_{k}^2]+\frac{\eta}{2}C_1\,.
\end{equation}
By Corollary~\ref{bouned2moment}, it follows that
\begin{equation}\label{bias_inq}
\E[\inprod{\grad f(\iter_k)}{\iter_k-\theta^*}]\le  C_2\eta\,,
\end{equation}
where $C_2 := { 2(3L^2+{L'_\noise}^{1/2})(\mu_{2,\eta} +\norm{\theta^*}^2)}+ C_1/2$ and $\mu_{2,\eta}$ is defined in Corollary~\ref{bouned2moment}.
Moreover, by Assumption~\ref{asm:dissipativity2}, Lemma~\ref{truncation}, and Jensen's inequality, we have
  \begin{equation*}
    \E[\inprod{\grad f(\iter_k)}{\iter_k-\theta^*}]\ge \delta\E[\Delta_{k}\1 (\Delta_{k}\ge R)]+ g(\E[\Delta_{k}\1 (\Delta_{k}< R)])\,.
  \end{equation*}
  Combining this with previous display provides us with
  \begin{align*}
    \E[\Delta_{k}\1 (\Delta_{k}\ge R)]\le \frac{C_2}{\delta}\eta \,,
  \end{align*}
  and 
  \begin{align*}
    \E[\Delta_{k}\1 (\Delta_{k}< R)]\le g^{-1}(C_2\eta)\,.
  \end{align*}
  Collecting pieces then gives
  \begin{align*}
    \E\bigl[\Delta_{k}\bigr]=&\E\bigl[\Delta_{k}\1 (\norm{\iter_k-\theta^*}<R)\bigr]+\E\bigl[\Delta_{k}\1 (\norm{\iter_k-\theta^*}\ge R)\bigr]\\
    \le &  \frac{C_2}{\delta}\eta+ g^{-1}( C_2\eta)\,.
  \end{align*}
  Thus, it holds for the $L_\phi$-Lipschitz continuous test function $\phi$ that
  \begin{equation*}
    |\sdist(\phi)-\phi(\theta^*)|\le L_{\phi}\int\norm{\theta-\theta^*}\sdist(d\theta)
    \leq L_{\phi} \Big( \frac{C_2}{\delta}\eta+ g^{-1}( C_2\eta) \Big)\,.
  \end{equation*}
\end{proof}

\begin{proof}[Proof of Theorem~\ref{bias_wz_loja}]

Consider the chain~$\chain$ starting from the stationary distribution~$\sdist.$
Note that by the assumption that~$\norm{\grad^2 f(\theta)}\le \tilde L(1+\norm{\theta})$ and Taylor expansion, we have
\begin{align*}
f(\iter_{k+1})
=& f(\iter_k)+\inprod{\grad f(\iter_k)}{\iter_{k+1}-\iter_k}+\frac{1}{2} (\iter_{k+1}-\iter_k)^\top\grad^2 f(\tilde\theta) (\iter_{k+1}-\iter_k)\\
\le &  f(\iter_k)+\inprod{\grad f(\iter_k)}{\iter_{k+1}-\iter_k} +\frac{1}{2}\tilde L\norm{ \iter_{k+1}-\iter_k}^2 (1+\norm{\tilde\theta})\,,
\end{align*}
where $\tilde\theta\in\rd$ is a convex combination between $\iter_{k+1}$ and $\iter_{k}.$
By definition of SGD iterates in~$\eqref{ref:sgd_org},$ it follows that 
\begin{align*}
f(\iter_{k+1})
\le &  f(\iter_{k})-\eta\inprod{\grad f(\iter_{k})}{\grad f(\iter_{k})+{\noise_{k+1}(\iter_k)} }+\frac{\tilde L}{2}\eta^2\norm{\grad f(\iter_{k})+{\noise_{k+1}(\iter_k)} }^2(1+\norm{\tilde\theta})\\
=&  f(\iter_{k})-\eta\inprod{\grad f(\iter_{k})}{\grad f(\iter_{k})+{\noise_{k+1}(\iter_k)} }\\
    &+\frac{\tilde L}{2}\eta^2 \bigl(\norm{\grad f(\iter_{k}}^2+\norm{{\noise_{k+1}(\iter_k)} }^2+2\inprod{\grad f(\iter_{k})}{{\noise_{k+1}(\iter_k)}}\bigr)(1+\norm{\tilde\theta})\\
\le &  f(\iter_{k})-\eta\inprod{\grad f(\iter_{k})}{\grad f(\iter_{k})+{\noise_{k+1}(\iter_k)}}\\
    &+\frac{\tilde L}{2}\eta^2\bigl(\norm{\grad f(\iter_{k}}^2+\norm{{\noise_{k+1}(\iter_k)}}^2+2\inprod{\grad f(\iter_{k})}{{\noise_{k+1}(\iter_k)}}\bigr)(1+\max\{\norm{\iter_k},\norm{\iter_{k+1}}\})\\
 \le&  f(\iter_{k})-\eta\norm{\grad f(\iter_{k})}^2-\eta \inprod{\grad f(\iter_{k})}{{\noise_{k+1}(\iter_k)}}\\
    &+\frac{\tilde L}{2}\eta^2\bigl(\norm{\grad f(\iter_{k}}^2+\norm{{\noise_{k+1}(\iter_k)}}^2
    +2\inprod{\grad f(\iter_{k})}{{\noise_{k+1}(\iter_k)}}\bigr)\\
    &+\frac{\tilde L}{2}\eta^2\bigl(\norm{\grad f(\iter_{k}}^2+\norm{{\noise_{k+1}(\iter_k)}}^2
    +2\inprod{\grad f(\iter_{k})}{{\noise_{k+1}(\iter_k)}}\bigr)(\norm{\iter_k}+\norm{\iter_{k+1}})\,.
\end{align*}
Taking the conditional expectation on both sides, using Cauchy-Schwarz inequality, Assumption~\ref{asm:noise_bias} and the fact that~$(1+x^4)^{1/2}\le 1+x^2,\forall x>0 $ gives
\begin{align*}
&\E[f(\iter_{k+1})|\filtration_k]\\
\le &  f(\iter_{k}) + (\frac{\tilde L}{2}\eta^2 -\eta)\norm{\grad f(\iter_{k})}^2
          + \frac{\tilde L}{2} L_\noise\eta^2 (1+\norm{\iter_k}^2)+0\\
        &+ \frac{\tilde L}{2}\eta^2 \E\Bigl[\norm{\grad f(\iter_{k})}^2(\norm{\iter_{k}}+\norm{\iter_{k+1}})|\filtration_k \Bigr]\\
        &+ \frac{\tilde L}{2}\eta^2 \E^{1/2}\Bigl[\norm{\noise_{k+1}({\iter_k})}^4|\filtration_k\Bigr]\E^{1/2}\Bigl[(\norm{\iter_{k}}+\norm{\iter_{k+1}})^2|\filtration_k \Bigr] \\
       &+0+ \tilde L\eta^2 \E[ \norm{\grad f(\iter_{k})} \norm{\noise_{k+1}(\iter_k)} \norm{\iter_{k+1}} |\filtration_k]\\
      \le&  f(\iter_{k}) + (\frac{\tilde L}{2}\eta^2 -\eta)\norm{\grad f(\iter_{k})}^2
          + \frac{\tilde L}{2} L_\noise \eta^2(1+\norm{\iter_k}^2)\\
        &+ \frac{\tilde L}{2}\eta^2 \E\Bigl[\norm{\grad f(\iter_{k})}^2(\norm{\iter_{k}}+\norm{\iter_{k+1}})|\filtration_k \Bigr]\\
        & + \frac{\tilde L}{2}\eta^2L_\noise ^{1/2} (1+\norm{\iter_k}^2)\E^{1/2}\Bigl[(\norm{\iter_{k}}+\norm{\iter_{k+1}})^2|\filtration_k \Bigr] \\
               &+ \tilde L\eta^2 \E[ \norm{\grad f(\iter_{k})} \norm{\noise_{k+1}(\iter_k)} \norm{\iter_{k+1}} |\filtration_k]\,.
\end{align*}
We then take expectation on both sides. 
For this, we bound the last three terms separately.
Note that the chain starts from the initial distribution~$\sdist$.
By H\"{o}lder's inequality, we have 
\begin{align*}
& \E[\norm{\grad f(\iter_{k})}^2(\norm{\iter_{k}}+\norm{\iter_{k+1}})]\\  
\le &  \E[\norm{\grad f(\iter_{k})}^2\norm{\iter_k}]+\E[\norm{\grad f(\iter_{k})}^2\norm{\iter_{k+1}}]\\
\le & \E^{1/2}[\norm{\grad f(\iter_{k})}^4]\E^{1/2}[\norm{\iter_k}^2]+\E^{1/2}[\norm{\grad f(\iter_{k})}^4]\E^{1/2}[\norm{\iter_{k}}^2]\,.
\end{align*}
By Assumption~\ref{asm:growth} and the fact that $(x+y)^4\le 9(x^4+y^4),\forall x,y\in\R$, we have
\begin{align*}
 \E^{1/2}[\norm{\grad f(\iter_{k})}^4]
 &\le  L^2\E^{1/2}[(1+\norm{\iter_{k}})^4]
 \le 3L^2\sqrt{1+\E[\norm{\iter_k}^4]}\,.
\end{align*}
By Lemma~\ref{bound4mom}, it holds that $\E[\norm{\iter_k}^4]<\mu_{4,\eta},$ 
where the constant $\mu_{4,\eta}$ is defined in Lemma~\ref{bound4mom}.
Moreover, by  Corollary~\ref{bouned2moment}, we also have $\E[\norm{\iter_{k}}^2]\le \mu_{2,\eta},$ 
where the constant $\mu_{2,\eta}$ is defined in Corollary~\ref{bouned2moment}. 
Combining these with previous display gives
\begin{align*}
&  \E[\norm{\grad f(\iter_{k})}^2(\norm{\iter_{k}}+\norm{\iter_{k+1}})]
\le 6L^2\sqrt{1+\mu_{4,\eta}} \sqrt{\mu_{2,\eta}}\,.
\end{align*}
Using the same trick, we obtain
\begin{align*}
&\E \Bigl[ (1+\norm{\iter_k}^2) \E^{1/2}[ (\norm{\iter_k}+\norm{\iter_{k+1}})^2|\filtration_k]\Bigr] \\
\le & \E^{1/2}[(1+\norm{\iter_k}^2)^2] \E^{1/2} \Bigl[\E[ (\norm{\iter_k}+\norm{\iter_{k+1}})^2 |\filtration_k]  \Bigr]\\
\le & \E^{1/2}[2+2\norm{\iter_k}^4] \E^{1/2} \Bigl[\E[ 2\norm{\iter_k}^2+2\norm{\iter_{k+1}}^2 |\filtration_k]  \Bigr]\\
\le & {4}\E^{1/2} [1+\norm{\iter_k}^4]\E^{1/2}[\norm{\iter_k}^2]\\
\le & {4}\sqrt{\mu_{2,\eta}}\sqrt{1+\mu_{4,\eta}}\,.
\end{align*}
By Assumptions~\ref{asm:growth} and~\ref{asm:noise_bias}, we have
\begin{align*}
&\E\Bigl[\E[ \norm{\grad f(\iter_{k})} \norm{\noise_{k+1}(\iter_k)} \norm{\iter_{k+1}} |\filtration_k] \Bigr]\\
\le& \E\Bigl [\norm{\grad f(\iter_k)}\E^{1/2}[\norm{\noise_{k+1}(\iter_k)}^2 |\filtration_k]\E^{1/2}[\norm{\iter_{k+1}}^2|\filtration_k] \Bigr]\\
\le&L_\noise^{1/2} L \E\Bigl [(1+\norm{\iter_k})(1+\norm{\iter_k}^2)^{1/2}\E^{1/2}[\norm{\iter_{k+1}}^2|\filtration_{k}]\Bigr]\\
\le & L L_\noise^{1/2} \E\Bigl [(1+\norm{\iter_k})^2 \E^{1/2}[\norm{\iter_{k+1}}^2|\filtration_k]\Bigr] \\
\le & L L_\noise^{1/2} \E^{1/2} [(1+\norm{\iter_k})^4]  \E^{1/4}[\norm{\iter_k}^4]\\
\le & L L_\noise^{1/2}\sqrt{8+8\mu_{4,\eta}} (\mu_{4,\eta})^{1/4} \\
=&3 L L_\noise^{1/2}(\mu_{4,\eta} +\mu_{4,\eta}^{3/4})\,.
\end{align*}
Collecting pieces then gives 
\begin{align*}
&\E[f(\iter_{k+1})]\\
\le & \, \E[f(\iter_{k})]
+(\frac{\tilde L}{2}\eta^2-\eta)\E[\norm{\grad f(\iter_{k})}^2]
+ \tilde L L_\noise\eta^2(1+\mu_{2,\eta})\\
&+ 3\tilde L L^2 \eta^2 \mu_{2,\eta}^{1/2}\sqrt{1+\mu_{4,\eta}}
+ 2\tilde L L_\noise^{1/2} \eta^2 \mu_{2,\eta}^{1/2} \sqrt{1+\mu_{4,\eta}}
+3 \tilde LL L_\noise^{1/2}\eta^2(\mu_{4,\eta} +\mu_{4,\eta}^{3/4})\\
\le &  \, \E[f(\iter_{k})]
+(\frac{\tilde L}{2}\eta^2-\eta)\E[\norm{\grad f(\iter_{k})}^2] 
+ 12\eta^2\tilde L (L + L_\noise^{1/2}+L_\noise^{1/4})^2\Bigl( 1+\mu_{2,\eta} + \mu_{4,\eta}+\mu_{4,\eta}^{3/4}\Bigr)\,.
\end{align*}
Recall that the iterates~$\chain$ starts from the stationary distribution~$\sdist$ and $\eta< \frac{2}{\tilde L}.$ 
Rearranging the above display gives
\begin{align*}
\E[\norm{\grad f(\iter_{k})}^2] 
\le \frac{2\tilde M \eta}{2-\tilde L\eta} \,,
\end{align*}
where 
\begin{equation*}
\tilde M:=12\tilde L (L + L_\noise^{1/2}+L_\noise^{1/4})^2\Bigl( 1+\mu_{2,\eta}+ \mu_{4,\eta}+\mu_{4,\eta}^{3/4}\Bigr)\,.
\end{equation*}
By Assumption~\ref{asm:loja} and Jensen's inequality,
it holds that 
\begin{align*}
\E[\norm{\grad f(\iter_k)}^2]
\ge & \E[g(f(\iter_k)-f^*)\1 (\norm{\iter_k-\theta^*}\le R) ]+ \gamma\E[(f(\iter_k)]-f^*) \1(\norm{\iter_k-\theta^*}>R)]  \\
\ge & g(\E[(f(\iter_k)]-f^*)\1 (\norm{\iter_k-\theta^*}\le R) ])+ \gamma\E[(f(\iter_k)]-f^*) \1(\norm{\iter_k-\theta^*}>R)] \,.
\end{align*}
Combing this with previous display gives
\begin{align*}
0 \leq \E[(f(\iter_k)]-f^*)\1 (\norm{\iter_k-\theta^*}\le R) ] &\le  g^{-1}\Bigl(\frac{2\tilde M \eta}{2-\tilde L\eta}\Bigr)
\\
0 \leq \E[(f(\iter_k)]-f^*) \1(\norm{\iter_k-\theta^*}>R)]  &\le \frac{2\tilde M \eta}{2-\tilde L\eta}\,.
\end{align*}
This implies
\begin{align*}
0 \leq \sdist(f) -f^*
&=\E[(f(\iter_k)]-f^* \\
&= \E[(f(\iter_k)-f^*)\1 (\norm{\iter_k-\theta^*}\le R)]+\E[(f(\iter_k)-f^*)\1 (\norm{\iter_k-\theta^*}>R)]\\
 &\le  g^{-1}\Bigl( \frac{2\tilde M \eta}{2-\tilde L\eta} \Bigr) +\frac{2\tilde M \eta}{2-\tilde L\eta}\,.
\end{align*}
When the test function~$\phi$ satisfies $\phi=\tilde\phi\circ f$ with the $L_{\tilde\phi}$-Lipschitz function~$\tilde\phi$, we obtain
\begin{align*}
|\sdist(\phi)-\phi(\theta^*)|
\le& L_{\tilde\phi} (\sdist(f)-f^*) \le L_{\tilde\phi}\Big( g^{-1}\Bigl( \frac{2\tilde M \eta}{2-\tilde L\eta} \Bigr) +\frac{2\tilde M \eta}{2-\tilde L\eta} \Big)
\end{align*}
as desired.
\end{proof}


\begin{proof}[Proof of Theorem~\ref{bias_wz_convex}]
Consider the chain~$\chain$ starting from the stationary distirbution~$\sdist.$
By display~\eqref{bias_inq},  it holds that
\begin{equation}
\E[\inprod{\grad f(\iter_k)}{\iter_k-\theta^*}]\le  C_2\eta\,,
\end{equation}
where $C_2$ is a positive constant defined in Theorem~\ref{bias_wz_disp}. 
Note that $f$ is convex, this implies
\begin{equation*}
0 \leq  f(\iter_k)-f^* \le \inprod{\grad f(\iter_k)}{\iter_k-\theta^*}\,.
\end{equation*}
Taking the expectation on both sides and combing this with the previous display gives
\begin{align*}
0 \leq  \sdist(f)-f^* \le C_2\eta\,.
\end{align*}
The desired result readily follows for the test function~$\phi$ satisfies $\phi=\tilde\phi\circ f$ with the $L_{\tilde\phi}$-Lipschitz function~$\tilde\phi.$
\end{proof}
{"config": "arxiv", "file": "2006.07904/Sections/proofs.tex"}