\Needspace{12\baselineskip}
\section{Main results}
\label{sec:main_results}

\begin{assumption}[Objective regularity]
\label{ass:objective}
\leavevmode\par\vspace{-4pt}
\begin{enumerate}[label=(\alph*),topsep=4pt,itemsep=5pt]
\item $F:\mathbb R^p\to\mathbb R$ is differentiable, $\mu$-strongly convex,
and $L$-smooth, with $0<\mu\le L$. Its unique minimizer is denoted by
$\theta^*$.
\item $F$ is twice continuously differentiable. Write
$H=\nabla^2F(\theta^*)\succ0$. For some finite $L_H\ge0$ and all
$\theta,\vartheta\in\mathbb R^p$, its Hessian satisfies
\begin{equation}\label{eq:hessian_lipschitz}
\|\nabla^2F(\theta)-\nabla^2F(\vartheta)\|_{\mathrm{op}}
\le L_H\|\theta-\vartheta\|.
\end{equation}
\end{enumerate}
\end{assumption}

Part (a) is used for convergence; part (b) additionally controls the
nonlinear remainder in the PR limit.

Let $(\mathcal F_t)_{t\ge1}$ be a filtration. We consider
\begin{equation}\label{eq:sgd}
\theta_{t+1}=\theta_t-\eta_t
\bigl[\nabla F(\theta_t)+\xi_{t+1}+b_t\bigr],
\qquad \eta_t=Dt^{-\alpha},
\end{equation}
where $\theta_t,b_t\in\mathbb R^p$ are $\mathcal F_t$-measurable and
$\xi_{t+1}$ is $\mathcal F_{t+1}$-measurable. The gradient error has the
weighted historical representation
\begin{equation}\label{eq:historical}
b_t=\sum_{s=1}^t W_{t,s}\varepsilon_s+\delta_t,
\qquad W_{t,s}\in\mathbb R^{p\times q}.
\end{equation}
The weights are deterministic; $\varepsilon_s$ is $\mathcal F_s$-measurable,
and $\delta_t$ is $\mathcal F_t$-measurable. All vector norms are Euclidean.

\begin{theorem}[Mean-square and almost-sure convergence]
\label{thm:convergence}
Suppose Assumption~\ref{ass:objective}(a) holds,
$a_1:=\mathbb E\|\theta_1-\theta^*\|^2<\infty$, and
$\eta_t=Dt^{-\alpha}$ with $D>0$ and $1/2<\alpha<1$.
Assume the following conditions:
\begin{enumerate}[label=(\roman*)]
\item The gradient noise satisfies, almost surely,
\[
\mathbb E[\xi_{t+1}\mid\mathcal F_t]=0,
\qquad
\mathbb E[\|\xi_{t+1}\|^2\mid\mathcal F_t]\le\sigma^2.
\]
\item The innovations $\varepsilon_s$ are independent, centered, and
have common finite covariance $Q$. For finite constants $B_W,B_\delta\ge0$,
\begin{equation}\label{eq:weight_bounds}
\sum_{s=1}^t\operatorname{tr}(W_{t,s}QW_{t,s}^{\top})\le\frac{B_W}{t},
\qquad
\mathbb E\|\delta_t\|^2\le\frac{B_\delta}{t},
\qquad t\ge1.
\end{equation}
\end{enumerate}
Then, with $a_t=\mathbb E\|\theta_t-\theta^*\|^2$, for every integer $t\ge n$,
\begin{equation}\label{eq:mse_bound}
\boxed{
 a_t\le C_{\mathrm{init}}
 \exp\!\left[-c_0\bigl(t^{1-\alpha}-n^{1-\alpha}\bigr)\right]
 +C_\xi t^{-\alpha}+C_b t^{-1}.
}
\end{equation}
In particular, $\theta_t\to\theta^*$ in mean square and almost surely.
\end{theorem}

The constants in \eqref{eq:mse_bound} may be chosen as
\begin{equation}\label{eq:constants}
\begin{gathered}
B=2(B_W+B_\delta),\qquad
c_0=\frac{\mu D}{2(1-\alpha)},\qquad
C_\xi=\frac{4D\sigma^2}{\mu},\qquad
C_b=\frac{12B}{\mu^2},\\
n=\max\!\left\{1,\left\lceil(DL)^{1/\alpha}\right\rceil,
\left\lceil\left(\frac{4}{\mu D}\right)^{1/(1-\alpha)}\right\rceil\right\},
\qquad C_{\mathrm{init}}=a_n.
\end{gathered}
\end{equation}
An entirely explicit bound for $C_{\mathrm{init}}$ in terms of $a_1$ is
provided in Appendix~\ref{app:convergence}.
The result allows biased remainders and history-dependent errors.
The same conclusion and constants hold for any adapted $b_t$ satisfying
$\mathbb E\|b_t\|^2\le B/t$.
If $\delta_t\equiv0$, one may use the sharper choice $B=B_W$ throughout.


\begin{theorem}[Polyak--Ruppert averaging under weighted historical errors]
\label{thm:pr}
Consider \eqref{eq:sgd}--\eqref{eq:historical}, with the adaptedness and
deterministic-weight conventions above. Suppose
Assumption~\ref{ass:objective}(a) holds,
$\mathbb E\|\theta_1-\theta^*\|^2<\infty$, and
$\eta_t=Dt^{-\alpha}$, where $D>0$ and $1/2<\alpha<1$.
Assume the following conditions:
\begin{enumerate}[label=(\roman*)]
\item The joint innovations $Z_s=(\xi_s^\top,\varepsilon_s^\top)^\top$
are i.i.d., centered, and have finite covariance
\begin{equation}\label{eq:joint_covariance}
\mathcal Q=\operatorname{Cov}(Z_s)=
\begin{pmatrix}S&C_0\\ C_0^\top&Q\end{pmatrix}.
\end{equation}
For every $t\ge1$, $Z_{t+1}$ is independent of $\mathcal F_t$.
\item For some $B<\infty$ and $\beta>0$, the error and remainder satisfy
\begin{equation}\label{eq:beta_bound}
\mathbb E\|b_t\|^2\le B t^{-\beta}\quad(t\ge1),
\qquad
\frac1{\sqrt T}\sum_{t=1}^T\delta_t\xrightarrow{p}0.
\end{equation}
\end{enumerate}
Define the cumulative weights and their covariance matrix by
\begin{equation}\label{eq:cumulative_weights}
K_{T,s}=\sum_{t=s}^TW_{t,s},\qquad
V_T=\frac1T\sum_{s=1}^TK_{T,s}QK_{T,s}^\top.
\end{equation}
Write $B_T=T^{-1/2}\sum_{t=1}^Tb_t$ and
$\Gamma_T^{(b)}=\operatorname{Cov}(B_T)$.
For the PR central limit theorem, suppose additionally that
Assumption~\ref{ass:objective}(b) holds,
$\beta>\max\{1/2,2\alpha-1\}$, and
\begin{equation}\label{eq:weight_clt}
V_T\to\Gamma,\qquad
\frac1T\sum_{s=1}^TK_{T,s}\to K,\qquad
\max_{1\le s\le T}\frac{\|K_{T,s}\|_{\mathrm{op}}}{\sqrt T}\to0.
\end{equation}
Then, for $\bar\theta_T=T^{-1}\sum_{t=1}^T\theta_t$,
\begin{equation}\label{eq:pr_clt}
\boxed{
\sqrt T(\bar\theta_T-\theta^*)\ \Rightarrow\ N(0,\Sigma_{\mathrm{PR}}),
\qquad
\Sigma_{\mathrm{PR}}=H^{-1}\Sigma_{\mathrm{eff}}H^{-\top},
}
\end{equation}
where
\begin{equation}\label{eq:effective_covariance}
\Sigma_{\mathrm{eff}}=S+\Gamma+C_0K^\top+KC_0^\top.
\end{equation}
If $\beta>1$, the cumulative error is negligible and the PR limit holds
with $\Sigma_{\mathrm{PR}}=H^{-1}SH^{-\top}$ even without
\eqref{eq:weight_clt}.

The cumulative error covariance has the following classification under
the second-moment bound in \eqref{eq:beta_bound}:
\begin{center}
\normalfont\small
\begin{tabular}{@{}ll@{}}
\toprule
Decay exponent & Behavior of $\Gamma_T^{(b)}$ \\
\midrule
$\beta>1$ & Necessarily converges to zero \\
$\beta=1$ & Bounded; convergence is not guaranteed \\
$0<\beta<1$ & May vanish, have a finite nonzero limit, or diverge \\
\bottomrule
\end{tabular}
\end{center}
For $0<\beta<1$, nonconvergence without divergence is also possible.
\end{theorem}

The table follows from the second-moment bound on $b_t$.
For the PR limit, $\beta>\max\{1/2,2\alpha-1\}$ controls the
nonlinear and summation-by-parts remainders and holds in the principal
regime $\beta=1$. The matrix $\Gamma$ determines the distributional
limit of $B_T$; it also equals $\lim_T\Gamma_T^{(b)}$ if the cumulative
remainder in \eqref{eq:beta_bound} converges to zero in $L^2$.


\subsection{Examples}
\label{sec:examples}

Both examples use $\varepsilon_t\in\mathbb R^p$ and the joint innovation
conditions of Theorem~\ref{thm:pr}, with
$C_0=\operatorname{Cov}(\xi_t,\varepsilon_t)=0$.
Here $\xi_t$ is the SGD sampling noise and $\varepsilon_t$ is the fresh
innovation of the auxiliary estimator. Independent data streams are one
way to ensure this condition. The objective, initial
iterate, and SGD step size satisfy the PR conditions of
Theorem~\ref{thm:pr}. The calculations below verify its remaining
error and weight conditions. Detailed derivations are given in
Appendix~\ref{app:examples}.

\paragraph{Example 1: Running average.}
Let
\begin{equation}\label{eq:running_average}
b_t=\frac1t\sum_{s=1}^t\varepsilon_s.
\end{equation}
Then $W_{t,s}=t^{-1}I$, $\delta_t=0$, and
\[
\mathbb E[b_tb_t^\top]=\frac Qt,
\qquad \mathbb E\|b_t\|^2=\frac{\operatorname{tr}(Q)}t.
\]
Thus the error lies in the critical regime $\beta=1$.
Writing $h_t=\sum_{j=1}^t j^{-1}$ and $h_0=0$, the cumulative weights are
$K_{T,s}=(h_T-h_{s-1})I$. They satisfy the exact identities
\begin{equation}\label{eq:running_weight_identities}
\frac1T\sum_{s=1}^TK_{T,s}=I,
\qquad
\frac1T\sum_{s=1}^TK_{T,s}QK_{T,s}^\top
=\left(2-\frac{h_T}{T}\right)Q.
\end{equation}
Moreover, $\max_s\|K_{T,s}\|_{\mathrm{op}}/\sqrt T=h_T/\sqrt T\to0$.
Consequently, $K=I$, $\Gamma=2Q$, and
\begin{equation}\label{eq:running_pr_covariance}
\boxed{
\sqrt T(\bar\theta_T-\theta^*)\Rightarrow
N\!\left(0,H^{-1}(S+2Q)H^{-\top}\right).
}
\end{equation}
Although the one-step error covariance is $Q/t$, temporal reuse of the
innovations produces a cumulative covariance of $2Q$.

\paragraph{Example 2: Recursive weighted average.}
For a fixed gain $c>1/2$ and a deterministic initial value $b_0$, let
\begin{equation}\label{eq:recursive_average}
b_t=\left(1-\frac ct\right)b_{t-1}+\frac ct\varepsilon_t.
\end{equation}
The gain $c$ controls the weight $c/t$ of the new innovation. For $t>c$,
this is a convex combination of the previous estimate and the new
innovation; the finitely many earlier steps are included in the
initial-transient analysis. Expanding the recursion gives
\begin{equation}\label{eq:recursive_weights}
W_{t,s}=\frac cs\prod_{j=s+1}^t\left(1-\frac cj\right)I,
\qquad
\delta_t=\prod_{j=1}^t\left(1-\frac cj\right)b_0,
\end{equation}
with empty products equal to one. The initial term is $O(t^{-c})$, so
$T^{-1/2}\sum_{t=1}^T\delta_t\to0$. Furthermore,
\begin{equation}\label{eq:recursive_single_covariance}
t\,\mathbb E[b_tb_t^\top]\longrightarrow\frac{c^2}{2c-1}Q,
\qquad \mathbb E\|b_t\|^2=O(t^{-1}).
\end{equation}
For $s/T\to x\in(0,1]$, the cumulative weights converge to
$k_c(x)I$, where
\begin{equation}\label{eq:recursive_kernel}
k_c(x)=c x^{c-1}\int_x^1v^{-c}\,dv
=\begin{cases}
\displaystyle\frac c{c-1}(1-x^{c-1}),&c\ne1,\\[2mm]
\log(1/x),&c=1.
\end{cases}
\end{equation}
The condition $c>1/2$ ensures square integrability at $x=0$ and yields
\begin{equation}\label{eq:recursive_weight_limits}
K=\left(\int_0^1k_c(x)\,dx\right)I=I,
\qquad
\Gamma=\left(\int_0^1k_c(x)^2\,dx\right)Q
=\frac{2c}{2c-1}Q.
\end{equation}
The maximal weight condition also holds. Therefore
\begin{equation}\label{eq:recursive_pr_covariance}
\boxed{
\sqrt T(\bar\theta_T-\theta^*)\Rightarrow
N\!\left(0,H^{-1}\left[S+\frac{2c}{2c-1}Q\right]H^{-\top}\right).
}
\end{equation}
At $c=1$, \eqref{eq:recursive_average} is exactly the running average,
regardless of $b_0$, and both covariance formulas agree.

\paragraph{Single-step and downstream parameter choices.}
For fixed $Q,S,H$, the gain-dependent coefficients in the single-step
and downstream asymptotic covariances are, respectively,
\begin{equation}\label{eq:gain_objectives}
f_{\mathrm{single}}(c)=\frac{c^2}{2c-1},
\qquad f_{\mathrm{PR}}(c)=\frac{2c}{2c-1},\qquad c>1/2.
\end{equation}
Their derivatives are
\[
f_{\mathrm{single}}'(c)=\frac{2c(c-1)}{(2c-1)^2},
\qquad f_{\mathrm{PR}}'(c)=-\frac2{(2c-1)^2}.
\]
When $Q\ne0$, the single-step asymptotic MSE is minimized at $c=1$,
whereas the downstream PR covariance decreases in the positive
semidefinite order as $c$ increases. Its infimum is
$H^{-1}(S+Q)H^{-\top}$ as $c\to\infty$ and is not attained at a finite
gain. The two asymptotic criteria therefore favor different gain
choices. These limits hold for fixed $c$ as $T\to\infty$.