In this paper we provide a rigorous convergence analysis for the renowned Particle Swarm Optimization method using tools from stochastic calculus and the analysis of partial differential equations. Based on a time-continuous formulation of the particle dynamics as a system of stochastic differential equations, we establish the convergence to a global minimizer in two steps. First, we prove the consensus formation of the dynamics by analyzing the time-evolution of the variance of the particle distribution. Consecutively, we show that this consensus is close to a global minimizer by employing the asymptotic Laplace principle and a tractability condition on the energy landscape of the objective function. Our results allow for the usage of memory mechanisms, and hold for a rich class of objectives provided certain conditions of well-preparation of the hyperparameters and the initial datum are satisfied. To demonstrate the applicability of the method we propose an efficient and parallelizable implementation, which is tested in particular on a competitive and well-understood high-dimensional benchmark problem in machine learning.
翻译:在本文中,我们利用随机微积分法和局部差异方程分析工具,对著名的粒子蒸汽优化法进行了严格的趋同分析。根据粒子动态作为随机差异方程系统的持续时间设计,我们分两个步骤将粒子动态与全球最小化器相趋同。首先,我们通过分析粒子分布差异的时间变化,证明动态的协商一致形成。接着,我们通过采用无药可乐拉普原则以及目标功能的能源景观的可移动性条件,表明这一共识接近全球最小化器。我们的结果允许使用记忆机制,并保留了丰富的目标类别,为高分量计和初始数据提供了某些良好的预测条件。为了证明我们提议的高效和平行实施方法的实用性,特别是在机器学习中的竞争性和精深的高维基准问题上进行了测试。