Insights

# SGD with vanishing correlated gradient errors ## Model and result contracts Let $F:\mathbb R^p\to\mathbb R$ be $\mu$-strongly convex and $L$-smooth, with minimizer $\theta^*$. For a filtration $(\mathcal F_t)$, consider $$ \theta_{t+1}=\theta_t-\eta_t[\nabla F(\theta_t)+\xi_{t+1}+b_t],\qquad \eta_t=Dt^{-\alpha},\quad D>0,\quad 1/2<\alpha<1, $$ $$ b_t=\sum_{s=1}^tW_{t,s}\varepsilon_s+\delta_t. $$ Here $W_{t,s}\in\mathbb R^{p\times q}$ are deterministic; $\theta_t,b_t,\delta_t$ are adapted; $\mathbb E\|\theta_1-\theta^*\|^2<\infty$. An adapted historical error need not be conditionally centered given the current past. **Convergence (Theorem 1).** Assume $\mathbb E[\xi_{t+1}\mid\mathcal F_t]=0$, $\mathbb E[\|\xi_{t+1}\|^2\mid\mathcal F_t]\le\sigma^2$, and independent centered $\varepsilon_s$ of common covariance $Q$. If $$ \sum_{s\le t}\operatorname{tr}(W_{t,s}QW_{t,s}^\top)\le B_W/t,\qquad \mathbb E\|\delta_t\|^2\le B_\delta/t, $$ then with $B=2(B_W+B_\delta)$, $$ \mathbb E\|\theta_t-\theta^*\|^2\le a_n\exp[-c_0(t^{1-\alpha}-n^{1-\alpha})] +\frac{4D\sigma^2}{\mu}t^{-\alpha}+\frac{12B}{\mu^2}t^{-1}, \quad c_0=\frac{\mu D}{2(1-\alpha)}. $$ One admissible start is $$ n=\max\{1,\lceil(DL)^{1/\alpha}\rceil, \lceil(4/(\mu D))^{1/(1-\alpha)}\rceil\}. $$ Convergence holds almost surely and in mean square. If $\delta_t=0$, use $B=B_W$. The proof also applies to any adapted error with $\mathbb E\|b_t\|^2\le B/t$. **PR CLT (Theorem 2).** Additionally assume a globally Lipschitz Hessian, and i.i.d. centered joint innovations $Z_s=(\xi_s^\top,\varepsilon_s^\top)^\top$ independent of $\mathcal F_{s-1}$, of finite covariance $$ \mathcal Q=\begin{pmatrix}S&C_0\\ C_0^\top&Q\end{pmatrix}. $$ Require $\mathbb E\|b_t\|^2\le Bt^{-\beta}$ with $\beta>\max\{1/2,2\alpha-1\}$ and $T^{-1/2}\sum_{t\le T}\delta_t\to_p0$. Define $$ K_{T,s}=\sum_{t=s}^TW_{t,s},\qquad \frac1T\sum_{s\le T}K_{T,s}QK_{T,s}^\top\to\Gamma,\quad \frac1T\sum_{s\le T}K_{T,s}\to K,\quad \max_{s\le T}\frac{\|K_{T,s}\|_{\rm op}}{\sqrt T}\to0. $$ For $H=\nabla^2F(\theta^*)$ and $\bar\theta_T=T^{-1}\sum_{t\le T}\theta_t$, $$ \sqrt T(\bar\theta_T-\theta^*)\Rightarrow N(0,H^{-1}\Sigma_{\rm eff}H^{-\top}),\qquad \Sigma_{\rm eff}=S+\Gamma+C_0K^\top+KC_0^\top. $$ The matrix $\Gamma$ describes the limiting historical contribution in distribution. Identifying it with the limit of the actual cumulative covariance also requires the cumulative $\delta_t$ to vanish in $L^2$, not only in probability. When $\beta>1$, Minkowski's inequality already makes the total historical error negligible in $L^2$; the usual covariance $H^{-1}SH^{-\top}$ follows without the weight-limit conditions. ## Core mechanisms and essential derivations ### 1. Absorb adapted historical bias into contraction (Appendix A.1) Write $e_t=\theta_t-\theta^*$ and $V_t=\|e_t\|^2$. Cocoercivity and strong convexity, for $\eta_t\le1/L$, give $$ \|e_t-\eta_t\nabla F(\theta_t)\|^2\le(1-\mu\eta_t)V_t. $$ The historical cross term does not vanish; use Young's inequality. Only the fresh $\xi_{t+1}$ term is conditionally centered. The resulting recursion is $$ \mathbb E[V_{t+1}\mid\mathcal F_t] \le(1-\mu\eta_t/2)V_t+(3\eta_t/\mu)\|b_t\|^2+\sigma^2\eta_t^2. $$ Its scalar comparison has forcing orders $t^{-2\alpha}$ and $t^{-\alpha-1}$, yielding the two MSE terms. Moreover, $$ \mathbb E\sum_t[\eta_t\|b_t\|^2+\eta_t^2]<\infty. $$ Tonelli gives almost-sure summability; the almost-supermartingale argument yields a limit and $\sum_t\eta_tV_t<\infty$. Since $\sum_t\eta_t=\infty$, that limit is zero. Mere one-step unbiasedness of an auxiliary estimator would not replace this adapted-bias argument. ### 2. Swap sums before estimating cumulative noise (Appendix A.2) An individual estimate may have MSE $O(t^{-1})$ while repeatedly reusing old innovations. The decisive identity is $$ \frac1{\sqrt T}\sum_{t\le T}b_t =\frac1{\sqrt T}\sum_{s\le T}K_{T,s}\varepsilon_s+o_p(1). $$ The relevant variance is governed by column sums $K_{T,s}$, not the rowwise variance of $b_t$. Minkowski alone shows $$ \left\|T^{-1/2}\sum_{t\le T}b_t\right\|_{L^2} \le\sqrt{B/T}\sum_{t\le T}t^{-\beta/2}. $$ Thus $\beta>1$ forces negligible cumulative error, $\beta=1$ only gives bounded covariance, and $0<\beta<1$ permits zero, finite nonzero, divergent, or bounded oscillatory behavior. These possibilities do not assert the extra CLT hypotheses. Taylor expansion and summation by parts give the exact decomposition $$ H\frac1{\sqrt T}\sum_{t\le T}e_t =A_T-\frac1{\sqrt T}\sum_{t\le T}(\xi_{t+1}+b_t) -\frac1{\sqrt T}\sum_{t\le T}r_t, $$ $$ A_T=\frac1{\sqrt T}\left[\frac{e_1}{\eta_1}-\frac{e_{T+1}}{\eta_T} +\sum_{t=2}^T(\eta_t^{-1}-\eta_{t-1}^{-1})e_t\right],\qquad \|r_t\|\le(L_H/2)\|e_t\|^2. $$ The generalized MSE bound is $O(t^{-\alpha}+t^{-\beta})$. It makes $A_T\to0$ in $L^2$ when $\beta>2\alpha-1$, and the nonlinear sum vanish in $L^1$ when $\alpha,\beta>1/2$. These explain the exponent condition rather than treating it as an arbitrary cutoff. Replacing $\sum\xi_{t+1}$ by $\sum\xi_t$ leaves only an $o_{L^2}(1)$ endpoint term. Apply a joint triangular-array CLT to $(\xi_s,K_{T,s}\varepsilon_s)/\sqrt T$. Finite second moments, vanishing maximum weight and bounded summed covariance imply Lindeberg. If $\mathcal Q$ is singular, factor it on its positive-rank range and use its pseudoinverse there; full invertibility is unnecessary. The cross terms $C_0K^\top+KC_0^\top$ must be retained unless justified to vanish. ### 3. Single-step MSE and downstream efficiency choose different gains (Examples 1–2) For running means $b_t=t^{-1}\sum_{s\le t}\varepsilon_s$, put $h_t=\sum_{j\le t}j^{-1}$. Then $$ K_{T,s}=(h_T-h_{s-1})I,\quad \frac1T\sum_sK_{T,s}=I,\quad \frac1T\sum_sK_{T,s}QK_{T,s}^\top=(2-h_T/T)Q. $$ With $C_0=0$, one-step covariance is $Q/t$ but PR covariance is $H^{-1}(S+2Q)H^{-\top}$. For a fixed $c>1/2$ and deterministic $b_0$, $$ b_t=(1-c/t)b_{t-1}+(c/t)\varepsilon_t,\quad w_{t,s}=\frac cs\prod_{j=s+1}^t(1-c/j). $$ The deterministic initial remainder is $O(t^{-c})$ and cumulatively negligible. Product estimates give $w_{t,s}\asymp c s^{c-1}t^{-c}$ away from a finite initial segment; the cumulative kernel is $$ k_c(x)=c x^{c-1}\int_x^1v^{-c}\,dv =\begin{cases}\dfrac c{c-1}(1-x^{c-1}),&c\ne1,\\ \log(1/x),&c=1.\end{cases} $$ Boundary envelopes, not just pointwise limits, justify integrating its square. Consequently $$ t\,\mathbb E[b_tb_t^\top]\to\frac{c^2}{2c-1}Q,\qquad \int_0^1k_c=1,\qquad \int_0^1k_c^2=\frac{2c}{2c-1}. $$ For $Q\ne0$, the first coefficient is minimized at $c=1$; the downstream coefficient strictly decreases with $c$ and tends to $1$. Limits are for fixed $c$ as $T\to\infty$, not a uniform theorem for $c=c_T$. ### 4. Normalize rows, flatten columns, attain the sharp bound (Section 4; Appendices A.4–A.5) Restrict to deterministic scalar historical weights with $\sum_{s\le t}w_{t,s}=1$, applied to independent centered innovations with covariance $Q$. For $k_{T,s}=\sum_{t=s}^Tw_{t,s}$, row normalization gives $\sum_sk_{T,s}=T$. Therefore $$ \Gamma_T-Q=\frac QT\sum_{s\le T}(k_{T,s}-1)^2\succeq0. $$ For $Q\ne0$, convergence to $Q$ is equivalent to mean-square flattening of these cumulative column weights. This is a sharp lower bound in the stated estimator class. The downstream inequality $\Sigma_{\rm PR}\succeq H^{-1}(S+Q)H^{-\top}$ additionally uses $C_0=0$ and the PR hypotheses; it is not a universal SGD lower bound. To attain it, initialize $b_1=\varepsilon_1$, then use $\gamma_t=at^{-\rho}$ with $0<a\le1$, $1/2<\rho<1$. Equivalently $\gamma_1=1$. The weights remain nonnegative and exactly normalized. A scalar unit-variance innovation recursion $z_t$ has $$ v_t=\mathbb Ez_t^2=(1-\gamma_t)^2v_{t-1}+\gamma_t^2=O(t^{-\rho}). $$ Let $d_t=\gamma_t^{-1}-1$, $d_1=0$. The decisive Abel identity is $$ \sum_{t=1}^T(z_t-u_t)=-d_Tz_T+\sum_{t=1}^{T-1}(d_{t+1}-d_t)z_t. $$ Since $d_T=O(T^\rho)$, $d_{t+1}-d_t=O(t^{\rho-1})$, and $\|z_t\|_2=O(t^{-\rho/2})$, dividing by $\sqrt T$ yields $L^2$ order $O(T^{(\rho-1)/2})$. Independence of $u_s$ then gives the deterministic estimate $$ T^{-1}\sum_s(k_{T,s}-1)^2=O(T^{\rho-1})\to0. $$ It also implies the maximum-weight condition, because $$ \max_s|k_{T,s}|/\sqrt T\le T^{-1/2}+ [T^{-1}\sum_s(k_{T,s}-1)^2]^{1/2}\to0. $$ Thus $\Gamma_T\to Q$. If $\rho>2\alpha-1$ and the stated joint/objective assumptions hold with $C_0=0$, the optimal class covariance is attained, even though the single-step MSE is $\Theta(t^{-\rho})$ for $Q\ne0$, slower than $t^{-1}$. Numerical experiments were not rerun for this upload; the derivation and the executed finite-weight checks are recorded separately.