Analysis of two restart algorithms

Since the backpropagation algorithm used for neural network training suffers from a slow convergence and often sticking in local minima, the restart mechanism has been introduced, whose strategy is to cut off the training process and restart it with a fresh initialization when it seems unlikely to converge in a relatively short time. In this paper, we give detailed mathematical analysis on two versions of the restart algorithms. By deriving analytic expressions of the expected convergence time and the success rate, we illustrate why the restart algorithms work well and gain insights into the proper use of restarting. Numerical simulations are performed on the XOR problem, symmetry detection, parity problem and Arabic numeral recognition. We show the effectiveness of the restart algorithms, and compare them with simulated annealing. The analysis can also be applied to many other fields.