Consensus-Based Optimization Over the Sphere: Theoretical Guarantees and Applications in Machine Learning

Prof. Massimo Fornasier, Department of Mathematics, Technical University of Munich

We introduce a new stochastic Kuramoto-Vicsek type model for global optimization of nonconvex functions on the sphere. This model belongs to the class of Consensus-Based Optimization methods. In fact, particles move on the sphere driven by a drift towards an instantaneous consensus point, computed as a convex combination of the particle locations weighted by the cost function according to Laplace's principle, which represents an approximation to a global minimizer. The dynamics is further perturbed by a random vector field to favor exploration, whose variance is function of the distance of the particles with respect to the consensus point. In particular, as soon as consensus is reached the stochastic component vanishes. In the first part of the talk, we study the well-posedness of the model and we derive rigorously its mean-field approximation for large particle limit. The main results of the second part of the talk are about the proof of convergence of the numerical scheme to global minimizers provided conditions of well-preparation of the initial datum. The proof combines the previous results of mean-field limit with a novel asymptotic analysis, and classical convergence results
of numerical methods for SDE. We present several numerical experiments, which show that the algorithm scales well with the dimension and is extremely versatile. To quantify the performances of the new approach, we show that the algorithm is able to perform essentially as good as ad hoc state of the art methods and in some instances it obtains quantifiable better results in challenging problems in signal processing and machine learning, namely the phase retrieval problem and the robust subspace detection.