From Consensus-Based Optimization to Particle Swarm Optimization: Convergence Guarantees under Drift-Diffusion Coupling
TL;DR
This work analyzes how the PSO parameter coupling affects existing convergence guarantees for CBO and its variant with memory effect and shows that the coupling still leaves a non-empty set of admissible parameters for these convergence guarantees to hold, but the admissible parameter ranges shrink in the limits used to recover PSO.
Abstract
Particle swarm optimization (PSO) is a widely used algorithm featured in many state-of-the-art optimization tool-kits. However, rigorous performance guarantees are still lacking. The standard PSO dynamics do not admit a natural mean-field description, which would provide an avenue for theoretical analysis. By modifying the PSO formulation, one can recover the consensus-based optimization (CBO) algorithm with memory, which admits a mean-field limit and facilitates rigorous convergence analysis. These theoretical guarantees rely heavily on the fact that for CBO, the drift and noise strengths can be chosen independently, whereas they are coupled for PSO. We analyze how the PSO parameter coupling affects existing convergence guarantees for CBO and its variant with memory effect. We show, by an explicit construction, that the coupling still leaves a non-empty set of admissible parameters for these convergence guarantees to hold. However, the admissible parameter ranges shrink in the limits used to recover PSO. The resulting convergence guarantees from CBO therefore do not directly extend to the classical PSO model. We provide numerical simulations illustrating the parameter tradeoffs shown in the theoretical analysis.