Suppose we have i.i.d. samples $x\_i\sim N(0,\Sigma)$ and $y\_i\sim x\_i^T\omega^\*+\xi\_i,\xi\_i\sim N(0,1)$ where $\omega^\*$ is the fixed point of:
$$\omega\_{i+1} = \omega\_i − \eta\nabla\_\omega f(\omega\_i, x\_i
, y\_i), \quad \omega\_0 = 0$$
where $f(\omega, x\_i, y\_i) = \frac{1}{2}|y\_i − \omega^T x\_i|^2 $and $\eta$ is the step size. Formulate an appropriate range
of $\eta$ so that $\omega\_i$ will become an ergodic process. Also find mean and covariance under the equilibrium distribution.


So, I tried to calculate it and got another form of the expression:


$$\omega\_{i+1}-\omega^\*=(I-\eta x\_i x\_i^T)(\omega\_i-\omega^\*)+\eta\xi\_ix\_i$$


which could help to directly express $\omega\_i$ by a successive multiplication of $(I-\eta x\_i x\_i^T)$ and $\omega^\*$. Then I wanted to calculate $\frac{\sum \omega\_i}{n}$ to get the ergodicity, but I didn't make it.



Using gradient descent in probability case
Lets first assume $\zeta\_i=0$ and ask the following:


* under which conditions $w^\*$ is a stable fixed point?


If it's not a stable fixed point for noise-free case, then you won't end up with a fixed mean or stationary distribution after adding additive noise. This means $w^\*$ being a fixed point is a necessary condition for ergodicity. In the case of isotropic Gaussian noise, it might also be sufficient (needs checking)


Example
-------


Consider 2-dimensional problem with the following covariance:


\begin{equation}
\Sigma=\left(
\begin{matrix}
1 & 0 \\
0 & 2
\end{matrix}
\right)
\end{equation}


One condition on step size $\eta=\alpha$ which guarantees convergence


$$\frac{2}{\alpha}<\text{Tr}(\Sigma)+2\|\Sigma\|$$


This equation is derived in many places, ie 3.30 in Diniz "Adaptive Filtering". This produces the following condition on step size in our example:
$$\alpha<\frac{2}{7}$$


However, this condition is too strict and larger values of $\alpha$ work. The necessary and sufficient condition turns out to be the following:


$$\alpha<\frac {4} {9 + \sqrt {17}}$$


I extend the expression above for a general Gaussian in this [note](http://yaroslavvb.com/convergence.pdf). I haven't seen anyone else derive this, please correct me if this already occurs in literature.


General solution
----------------


For $x\_i$ sampled from a zero-centered Gaussian with covariance $\Sigma$, the necessary and sufficient condition for $w^\*$ to be a fixed point in a noiseless case is that


$$\alpha<\frac{2}{\rho(A)}$$


Where $\rho$ denotes spectral radius and $A$ is defined below. Let $s=(s\_1, s\_2, s\_3, \ldots)$ be the eigenvalues of $\Sigma$, then
\begin{equation}\label{defa}
A=
2 \left(
\begin{array}{cccc}
 s\_1 & 0 & 0 & \ldots \\
 0 & s\_2 & 0 & \ldots \\
 0 & 0 & s\_3 & \ldots \\
 \ldots & \ldots & \ldots & \ldots 
\end{array}
\right)
+
\left(
\begin{array}{cccc}
 s\_1 & s\_1 & s\_1 & \ldots \\
 s\_2 & s\_2 & s\_2 & \ldots \\
 s\_3 & s\_3 & s\_3 & \ldots \\
 \ldots & \ldots & \ldots & \ldots 
\end{array}
\right)
\end{equation}


I haven't found a simpler closed form expression for this, but a sequence of bounds can be derived by bounding spectral radius of $A$ with norm of $A^k$ for various values of $k$, [discussion](https://math.stackexchange.com/q/3846464/998).


I suspect that convergence to fixed point in noiseless case also implies convergence to stationary distribution in the case of isotropic additive noise. In the case of non-isotropic noise, may need to consider the ratio of $\Sigma$ and covariance of noise matrix, like is done in NQM [paper](https://proceedings.neurips.cc/paper/2019/hash/e0eacd983971634327ae1819ea8b6214-Abstract.html)


Existing results for non-Gaussian case:
---------------------------------------


It can be shown that in the case of 1 dimension and deterministic $x$, the following condition on $\alpha$ is necessary and sufficient for convergence
\begin{equation}\label{supersimple}
\alpha x^4 < 2 x^2
\end{equation}


Since we have $h=x^2$ for Hessian $h$, this reduces to the well known bound on convergent learning rate: $\alpha < 2/h$


In the case of stochastic x, the following is necessary and sufficient


\begin{equation}\label{eq:0}
 \alpha E[x^4] < 2 E[x^2]
\end{equation}


For the case of $x$ being distributed as standard normal, this gives $2/(3h)$ for the largest learning rate, three times smaller than what's allowed in deterministic case


For the case of $d$ dimensions, the following is a sufficient condition, with $\prec$ indicating Loewner order\footnote{assumption A.6 in Bach [paper](https://www.di.ens.fr/%7Efbach/aistats_defossez_bach_with_supp.pdf)


\begin{equation}\label{eq:1}
 \alpha E[xx'xx'] \prec E[xx'] 
\end{equation}


The right-hand side can be tightened to
\begin{equation}\label{eq:1x}
 \alpha E[xx'xx'] \prec 2 E[xx'] 
\end{equation}


Bach, Deffosez2015 [showed](https://www.di.ens.fr/%7Efbach/aistats_defossez_bach_with_supp.pdf) that the following optimization over symmetric matrices gives sufficient condition for convergence, and conjectured it to also be necessary (Lemma 1 of Defossez2015)


\begin{equation}\label{eq:2}
 \frac{1}{\alpha} < \sup\_{A\in \mathcal{S}(R^d)} \frac{E[(x'Ax)^2]}{2 E[x'A^2 x] }
\end{equation}


We can show this to be equivalent to the following positive semi-definite constraint
\begin{equation}\label{eq:3}
 \alpha E[xx' \otimes xx'] \prec E[xx'\otimes I] + E[I\otimes xx']
\end{equation}


Most recently, [Jain](https://arxiv.org/abs/1610.03774) generalized last Eq to batch sizes beyond 1 and formally showed it to be a necessary condition for monotonic convergence. When applied to Gaussian case, this is equivalent to $\text{Tr}(\Sigma)+2\|H\|$ condition derived earlier.


