Online learning via congregational gradient descent
Kim L. Blackmore, Robert C. Williamson, Iven Mareels, William A. Sethares · 1995
We propose and analyse a populational version of stepwise gradient descent suitable for a wide range of learning problems. The algorithm is motivated by genetic algorithms which update a population of solutions rather than just a single representative asistypical for gradient descent. This modi cation of traditional gradient descent (as used for example in the backpropagation algorithm) avoids getting trapped in local minima. We use an averaging analysis of the algorithm to relate its behaviour to an associated ordinary di erential equation. We derivea result concerning how long one has to wait in order that with a given high probability, the algorithm is within a certain neighbourhood of the global minimum. We also analyse the e ect of di erent population sizes. An example is presented which corroborates our theory very well. 1