Using gradient descent in probability case

Question

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.

Answer 1

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. 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.

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

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

\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 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 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.