Hasty Congregational Gradient Descent for Online Optimisation
Stepwise Gradient Descent (SGD) algorithms for online optimization converge to local minima of the relevant cost function. In this paper a globally convergent modification of SGD is proposed, in which several solutions of SGD are run in parallel, together with online estimates of the cost function and its gradient. As each SGD estimate reaches a local minimum of the cost, the fitness of the member is evaluated and the member is immediately restarted unless it is the current best estimate. A number of results concerning the convergence behaviour of the proposed algorithm are derived using results from dynamical systems theory and probability theory. The efficacy of the algorithm is demonstrated via simulations and heuristic argument.