Consensus-Based Optimization with Truncated Noise

Massimo Fornasier, Peter Richtárik, Konstantin Riedl, Lukang Sun

Abstract

Consensus-based optimization (CBO) is a versatile multi-particle metaheuristic method for nonconvex and nonsmooth global optimization in high dimensions. While effective, standard CBO can suffer from instability due to heavy-tailed statistics in its noise term. This paper introduces a variant of CBO incorporating truncated noise to enhance the well-behavedness of the particle dynamics. By capping stochastic fluctuations, we ensure that higher moments of the particle system's law remain bounded, specifically achieving sub-Gaussianity. We rigorously prove the convergence in expectation of this variant using Wasserstein-2 distance analysis. Numerical experiments demonstrate that truncated CBO offers significantly greater flexibility in hyperparameter tuning and superior performance in high-dimensional benchmark problems compared to the original formulation.

Introduction

Global optimization is a fundamental challenge across engineering and machine learning, often requiring the identification of global minima in landscapes characterized by numerous local minima and non-differentiable regions. Metaheuristics like Particle Swarm Optimization (PSO) are popular but frequently lack rigorous convergence guarantees. Consensus-Based Optimization (CBO) was designed to bridge this gap, utilizing a swarm of particles that move toward a weighted average (consensus) of their positions, where weights are determined by the objective function values.

However, standard CBO faces a critical limitation: its exploration noise is proportional to the distance between a particle and the consensus point. In high-dimensional spaces or during early iterations, this can lead to "heavy-tailed" distributions. If the noise parameter $\sigma$ is too high relative to the drift $\lambda$, the system can diverge, making the algorithm highly sensitive to hyperparameter selection.

Methodology: Truncated Noise and Projected Consensus

To address these stability issues, we propose two primary modifications to the governing Stochastic Differential Equations (SDEs) of CBO:

  1. Truncated Noise: We introduce a threshold $M$ that caps the noise intensity. The noise term is modified from being purely proportional to distance to $\sigma (|v - \bar{v}| \wedge M)$, where $v$ is the particle position and $\bar{v}$ is the consensus. This prevents the stochastic fluctuations from becoming unbounded when particles are far from the consensus.
  2. Projected Consensus: To prevent the consensus point from diverging during the initial search phase, we project it onto a large ball $B_R(v_b)$ that is assumed to contain the global minimizer.

These modifications allow us to employ Mean-Field Analysis, treating the swarm as a continuous probability density in the limit of infinite particles. By ensuring the distribution remains sub-Gaussian, we can bound higher moments and rigorously prove that the expected error decreases over time, converging to a neighborhood of the global minimizer.

Experimental Results and Robustness

The benefits of noise truncation are most visible when examining the algorithm's sensitivity to hyperparameters. In standard CBO, there is a strict stability constraint where $\sigma^2 d < 2\lambda$ (with $d$ being the dimension). Truncated CBO effectively removes this hard constraint.

Success rate phase diagram for a benchmark function (e.g., Ackley) comparing truncated CBO across various $M$ and $\sigma$ values against standard CBO (rightmost bar).

As shown in the phase diagrams, the truncated version ($M < \infty$) maintains a high success rate (yellow regions) across a much wider range of noise levels $\sigma$ than the standard CBO (represented by the narrow success band in the rightmost "CBO" bar). This expanded stability region is consistent across different complex landscapes.

Success rate phase diagram for a second benchmark function (e.g., Rastrigin), further illustrating the robustness provided by noise truncation.

In high-dimensional tests (15D and 20D), the performance gap becomes even more pronounced. For instance, on the 15D Griewank function with 1,200 particles, the truncated CBO achieved a 79.1% success rate, whereas the standard version collapsed to a 3.2% success rate under the same conditions.

Conclusion

By truncating the noise in CBO, we achieve a more robust optimization metaheuristic that is both theoretically sound and practically superior. The truncation ensures sub-Gaussianity of the particle distribution, allowing for rigorous convergence proofs and providing practitioners with a wider range of stable hyperparameters. Future work may explore extending this truncation approach to anisotropic noise settings or other swarm-based optimization methods.

Summary updated

Abstract

Consensus-based optimization (CBO) is a versatile multi-particle metaheuristic optimization method suitable for performing nonconvex and nonsmooth global optimizations in high dimensions. It has proven effective in various applications while at the same time being amenable to a theoretical convergence analysis. In this paper, we explore a variant of CBO, which incorporates truncated noise in order to enhance the well-behavedness of the statistics of the law of the dynamics. By introducing this additional truncation in the noise term of the CBO dynamics, we achieve that, in contrast to the original version, higher moments of the law of the particle system can be effectively bounded. As a result, our proposed variant exhibits enhanced convergence performance, allowing in particular for wider flexibility in choosing the noise parameter of the method as we confirm experimentally. By analyzing the time-evolution of the Wasserstein-$2$ distance between the empirical measure of the interacting particle system and the global minimizer of the objective function, we rigorously prove convergence in expectation of the proposed CBO variant requiring only minimal assumptions on the objective function and on the initialization. Numerical evidences demonstrate the benefit of truncating the noise in CBO.
BibTeX
@inproceedings{fornasier2024consensus,
  author = {Massimo Fornasier and Peter Richtárik and Konstantin Riedl and Lukang Sun},
  title = {{Consensus-Based Optimization with Truncated Noise}},
  booktitle = {European},
  year = {2024},
  doi = {10.1017/s095679252400007x},
}
Figure