Stochastic approximation to gradient descent

What are the problems with standard gradient descent?

1.

Slow convergence (Work out a measure for 1000 iterations, 100 training examples and 100 weights).

2.

May settle into local minima

A stochastic approximation to gradient descent has been proposed by Widrow and Hoff (1960).

Instead of computing $\Delta w_i$ over all training examples, update w_i after considering each training example. So as we iterate through the training examples, we update each weight w_i according to:

$$w_i \leftarrow w_i + \eta(t-o)x_i$$

where t, o and x_i are the target value, unit output and the ith input for this training example alone. This is called the delta rule.

This can be imagined to be an attempt to minimize the training error E_d for each individual training example d, where

$$E_d(\vec{w}) = \frac{1}{2}(t_d - o_d)^2$$

• Stochastic gradient descent updates weights more frequently (m times more frequently) than standard gradient descent.
• If there are multiple local minima on the surface $E(\vec{w})$, stochastic gradient descent can sometimes pull itself out of them due to the effects of the various different $\nabla E_d(\vec{w})$.

Important observation: The training examples for a perceptron (thresholded unit) have target values of $\pm 1$. So if we train the pre-threshold stage of the perceptron (which is the unthresholded unit) to fit these target values using the delta rule, then clearly the perceptron has been trained to fit the given target values as well.