Analysis of the Computational Complexity of Backpropagation and Neuroevolution

This work examines the computational complexity of two algorithms to perform machine learning. The first algorithm is the well-known backpropagation, based on stochastic gradient descent, where a network of neurons alter their weights based on an error signal passed back from the output. The second algorithm, called neuroevolution, is based on the genetic algorithm. In it, many weight sets are ranked based on how well the network solves the problem, and the best of them combine together to form new weight sets, in a process inspired by biological evolution. We find that the forward computations are the same. Analyzing the number of operations for both weight adjustment algorithms, we find that backpropagation requires more operations to create a new weight set, but that neuroevolution requires many iterations.