Swarm and consensus based methods for global optimization: mean-field convergence and applications to machine learning

High dimensional optimization problems with a non-convex cost function are a popular topic in various disciplines today ranging from signal/image processing to machine learning. In addition to the well-known gradient based methods, another popular class of methods for dealing with such large scale optimization problems is the so-called metaheuristics. In this thesis, we will focus on a subclass of metaheuristic methods based on the notion of swarm intelligence. More precisely, we will consider particle swarm optimization (PSO) and consensus-based optimization (CBO) methods, i.e. two methods that exploit the collective iterations between a number of agents populating the domain of the cost function to be minimized. Each agent balances the tendency to explore the search space and the tendency to share position (and velocity) information. While the CBO method have been formulated in terms of a system of first-order stochastic differential equations (SDEs), in this thesis we introduce a novel formulation for the PSO method through a second-order system of SDEs. This allows us not only to design more general PSO methods with better performances, but also to rigorously study, at the cost of mild assumptions on the cost function, its mean-field convergence and small inertia limits, thus providing a robust mathematical theory and clarifying the relationships between the two methods. As a side result of our analysis, we derive a novel consensus based method with memory effects, which keeps track of the best position each particle has encountered throughout its history. We then further discuss implementation aspects, trying to improve numerical performance with the introduction of a random selection technique which greatly improve the efficiency of the methods. We demonstrate the convergence of the solution to the global minimizer even in this latter case. In addition to common benchmark problems we apply the resulting algorithms to three important application problems: image segmentation, function approximation and character classification on the MNIST dataset.