How to set the step size for stochastic gradient descent such that its provable it will converge

Question

Recall stochastic gradient descent (for regression):

$\theta = 0 $

$ \text{Randomly select } t \in [1,n]\{\\ \quad \theta^{(k+1)} = \theta^{k} + \eta_{k}(y^{(t)} - \theta \cdot x^{(t)})x^{(t)}\\ \}$

I was following some notes and it said that to have stochastic gradient descent converge it would be sufficient to set the learning rate to:

$$\eta_{k} = \frac{1}{k+1}$$

I normally post my attempts to a question, but I honestly don't know how to prove that setting that value will make stochastic gradient descent converge. If someone knows of a prove it would be awesome!

Also an answer that contains a proof, even if its for some special case, say "convex function" or in the case of linear regression or whatever the case is, but that provides some insight (or a proof) why this result holds for different setting of stochastic gradient descent, would be good answers!

I am aware that finding global minimum solutions is really hard anyway, so restricting your answer should be ok if it contains a good proof/argument and/or if it contains an example in machine learning.

Also, if you do not remember the proof but instead maybe have a good intuition on why that value is a good for stochastic gradient descent, that would also be a very useful response for me! :)

Thanks in advance!

Answer 1

First of all, you won't find a proof of this in the general case. Proofs of convergence in batch/stochastic gradient descent algorithms rely on convexity/strong convexity hypotheses.

In the case of stochastic gradient descent, a theorem is that if the objective function is convex and the learning rate $\eta_t$ is such that

$$\sum_t \eta_t = +\infty \quad \text{and} \quad \sum_t \eta_t^2 < + \infty$$

Then stochastic gradient converges almost surely to the global minimum. (Robbins-Siegmund theorem if I recall). The proof is nontrivial and makes use of results in the theory of stochastic process & martingale theory. This is the case for any convergence results for SGD.

Your stepsize clearly checks this condition, although typically one chooses a step of the form

$$\frac{\sigma}{(1 + \sigma \lambda t)^{3/4}}$$

Where $\sigma$ is the initial learning rate and $\lambda$ governs asymptotic convergence speed.

Answer 2

These are proofs which actually originate from adaptive filter theory.

History: Adaptive filters are online-optimization algorithms that gained popularity in the fields of Signal Processing (e.g. noise cancellation) and communications (e.g. channel estimation). The algorithm that you described in your question is referred to as the Least Mean Square (LMS) algorithm in the area of signal processing.

Since your data $x^{(t)}$ is assumed to be stochastic, we can only prove convergence in the statical sense. For example, we can only prove convergence in the mean or mean-square. As the proof for mean square convergence is a bit more involved, I'll include the proof for mean convergence.

Let's assume that your algorithm is trying to converge to an optimal parameter vector $\theta^{*}$.

Your stochastic gradient descent algorithm:

$$\theta^{(t+1)} = \theta^{(t)} + \eta (y^{(t)} - \theta^{(t)}x^{(t)} )x^{(t)}$$

Note that I did not assume a time-invariant step-size, $\eta$.

Here's the interesting part: Because you assume that there's an optimal parameter vector $\theta^{*}$, you can say that your desired target $y^{(t)}$ is generated form the this $\theta^{*}$ and your features $x^{(t)}$ as the following:

$$y^{(t)} = \theta^{*}x^{(t)} + \epsilon^{(t)} $$ where $\epsilon^{(t)} $ is a zero-mean white noise process that is independent to your features $x^{(t)}$. The noise factor $\epsilon^{(t)}$ is added to denote our uncertainty in the model.

Substituting this data model $y^{(t)}$ back into your SGD update queation gives

$$\theta^{(t+1)} = \theta^{(t)} + \eta \big(\theta^{*}x^{(t)} + \epsilon^{(t)} - \theta^{(t)}x^{(t)}\big )x^{(t)}$$

Instead of looking at the parameter update, it now becomes useful to study the error in the parameter estimate $v^{(t)} = \theta^{*} -\theta^{(t)} $. Subtracting the optimal vector $\theta^{*}$ from left and right hand sides above gives you

$$ \begin{align} v^{(t+1)} = {} & v^{(t)} - \eta \big( v^{(t)}x^{(t)} +\epsilon^{(t)} \big )x^{(t)} \\ = {} & v^{(t)} - \eta v^{(t)}(x^{(t)})^2 -\eta\epsilon^{(t)}x^{(t)} \end{align} $$

Now applying the statistical expectation operator gives $$ \begin{align} \mathbb{E}[v^{(t+1)}] = {} & \mathbb{E}[v^{(t)}] - \eta \mathbb{E}[v^{(t)}(x^{(t)})^2] -\eta \mathbb{E}[\epsilon^{(t)}x^{(t)}] \end{align} $$

• Since the zero-mean noise $\epsilon$ is independent to the features $x^{(t)}$, $\mathbb{E}[\epsilon^{(t)}x^{(t)}] = \mathbb{E}[\epsilon^{(t)}]\mathbb{E}[x^{(t)}] = 0$
• Also since $v^{(t)}$ is only function of past values of $x^{(t)}$ i.e. $v^{(t)} = \mathcal{F}(x^{(t-1)}, \ldots, x^0)$, and we assume that $x^{(t)}$ is independent of its past values $x^{(t-1)},\ldots, x^{(0)} $ we can say that $ \mathbb{E}[v^{(t)}(x^{(t)})^2] = \mathbb{E}[v^{(t)}] \mathbb{E}[(x^{(t)})^2]$.

This gives us

$$ \mathbb{E}[v^{(t+1)}] = (1 - \eta \mathbb{E}[(x^{(t)})^2])\mathbb{E}[v^{(t)}] $$

If we say that the variance of the features is $\mathbb{E}[(x^{(t)})^2] = \sigma^2_x$, we can write the mean error evolution as
$$\mathbb{E}[v^{(t+1)}] = \underbrace{(1 - \eta \sigma^2_x}_{= \alpha} )\mathbb{E}[v^{(t)}] $$

For the algorithm to convergence, $|\alpha| < 1 $. If $|\alpha|$ is greater than 1, at each iteration the error gets amplified (Think $v^{(t+1)} = 2v^{(t)}$). The $|\alpha| < 1 $ is satisfied if the learning rate is bounded by:

$$ 0 < \eta < \frac{2}{\sigma^2_x} $$

This completes the proof of convergence for the SGD algorithm.

In your case we can roughly say that as long as $\eta_t < \frac{2}{\sigma^2_x} \forall t$, your algorithm would convergence.

Disclaimer: Keep in mind that this only a guarantee for mean convergence - in practice, your step size would be much lower than this. The mean square convergence condition, for example, would give you a tighter bound.

Quick tip: From my experience, it's much neater and a hell of a lot quicker if you write your time indices as subscripts without brackets e.g. $\theta_{t+1} = \theta_t + \eta_t(y_t - \theta_tx_t)x_t$. ;)