CONSENSUS-BASED OPTIMIZATION ON THE SPHERE - MASSIMO FORNASIER - TECHNICAL UNIVERSITY OF MUNICH
I present new stochastic multi-particle models for global optimization of nonconvex functions on the sphere. These models belong to the class of Consensus-Based Optimization methods. In fact, particles move over the manifold driven by a drift towards an instantaneous consensus point, computed as a combination of the particle locations weighted by the cost function according to Laplace’s principle. The consensus point represents an approximation to a global minimizer. The dynamics is further perturbed by a random vector field to favor exploration, whose variance is a function of the distance of the particles to the consensus point. In particular, as soon as the consensus is reached, then the stochastic component vanishes.
In the first part of the talk, I present the well-posedness of the model on the sphere and we derive rigorously its mean-field approximation for large particle limit. In the second part I address the proof of convergence of numerical schemes to global minimizers provided conditions of well-preparation of the initial datum. The proof combines the 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 proposed 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 in challenging problems in signal processing and machine learning, namely the phase retrieval problem and the robust subspace detection.
A Joint work with H. Huang, L. Pareschi, and P. Sünnen
(1 MB)