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

Abstract

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.

I problemi di ottimizzazione in dimensione elevata con una funzione costo non convessa sono oggi un argomento trattato in varie discipline, dall'elaborazione di segnali e immagini all'apprendimento automatico. Oltre ai ben noti metodi basati sul gradiente, un'altra popolare classe di metodi per affrontare questi problemi di ottimizzazione su larga scala è la cosiddetta meta-euristica. In questa tesi, ci concentreremo su una sottoclasse di metodi meta-euristici basati sulla nozione di intelligenza di sciame. Più precisamente, considereremo i metodi di ottimizzazione a sciame di particelle (PSO) e di ottimizzazione basata sul consenso (CBO), ossia due metodi che sfruttano le iterazioni collettive tra un certo numero di agenti che popolano il dominio della funzione di costo da minimizzare. Ogni agente bilancia la tendenza a esplorare lo spazio di ricerca e la tendenza a condividere le informazioni sulla posizione (e sulla velocità). Mentre il metodo CBO è stato formulato in termini di un sistema di equazioni differenziali stocastiche (SDE) del primo ordine, in questa tesi introduciamo una nuova formulazione per il metodo PSO attraverso un sistema di SDE del secondo ordine. Questo ci permette non solo di progettare metodi PSO più generali con prestazioni migliori, ma anche di studiare rigorosamente, a costo di lievi assunzioni sulla funzione di costo, la convergenza del campo medio e i limiti di piccola inerzia, fornendo così una teoria matematica robusta e chiarendo le relazioni tra i due metodi. Come risultato collaterale della nostra analisi, abbiamo derivato un nuovo metodo basato sul consenso con effetti di memoria, che tiene traccia della migliore posizione che ogni particella ha incontrato nel corso della sua storia. Discutiamo poi gli aspetti implementativi, cercando di migliorare le prestazioni numeriche con l'introduzione di una tecnica di selezione casuale che migliora notevolmente l'efficienza dei metodi. Dimostriamo la convergenza della soluzione al minimizzatore globale anche in quest'ultimo caso. Oltre ai comuni problemi di benchmark, applichiamo gli algoritmi ottenuti a tre importanti problemi applicativi: la segmentazione di immagini, l'approssimazione di funzioni e la classificazione di caratteri sul dataset MNIST.