Source-linked AI summary
From Consensus-Based Optimization to Evolution Strategies: Proof of Global Convergence
Massimo Fornasier, Hui Huang, Jona Klemenc, Greta Malaspina
TL;DR
The paper addresses limited global-convergence theory and practical failures caused by vanishing noise, discretization error, and high-dimensional isotropic perturbations in CBO-like methods. It develops δ-CBO, Consensus Freezing, and Consensus Hopping, connects them through asymptotic limits, and proves global convergence with invariant-measure descriptions and convergence rates. The methods form a theoretically supported bridge from CBO and MPPI to Evolution Strategies, while isotropic noise leaves higher-dimensional performance limited by the curse of dimensionality.
Problem
Existing metaheuristics often lack robust quantitative convergence guarantees to global minima, while CBO additionally suffers from premature noise decay and discretization problems.
Method
The paper introduces fixed-variance δ-CBO, a Consensus Freezing discretization, and a Consensus Hopping limit, analyzing them through quantitative asymptotics and optimal-transport-based tools.
Results
The analyzed CBO, CF, and CH schemes have global convergence results, characterized invariant measures, stable large-step implementations, and guaranteed convergence rates.
Takeaways & Limitations
The resulting framework provides theoretical support for CBO, MPPI, and Evolution Strategies as globally convergent methods under the paper’s assumptions.
Takeaways & Limitations
Because the schemes use isotropic stochastic perturbations, their constants are generally affected by the curse of dimensionality and may limit performance on some high-dimensional problems.
Abstract
from arXiv · showhide
Consensus-based optimization (CBO) is a powerful and versatile zero-order multi-particle method designed to provably solve high-dimensional global optimization problems, including those that are genuinely nonconvex or nonsmooth. The method relies on a balance between stochastic exploration and contraction toward a consensus point, which is defined via the Laplace principle as a proxy for the global minimizer. In this paper, we introduce new CBO variants that address practical and theoretical limitations of the original formulation of this novel optimization methodology. First, we propose a model called $δ$-CBO}, which incorporates nonvanishing diffusion to prevent premature collapse to suboptimal states. We also develop a numerically stable implementation, the Consensus Freezing scheme, that remains robust even for arbitrarily large time steps by freezing the consensus point over time intervals. We connect these models through appropriate asymptotic limits. Furthermore, we derive from the Consensus Freezing scheme by suitable time rescaling and asymptotics a further algorithm, the Consensus Hopping scheme, which can be interpreted as a form of $(1,λ)$-Evolution Strategy. For all these schemes, we characterize for the first time the invariant measures and establish global convergence results, including exponential convergence rates.
1. Introduction
The paper develops and unifies globally convergent zero-order methods for difficult nonconvex and nonsmooth optimization, addressing premature noise decay and unstable discretization in CBO. It introduces δ-CBO, Consensus Freezing, and Consensus Hopping, and characterizes their convergence, invariant measures, and relationships to MPPI and Evolution Strategies.
- Contribution: The paper analyzes scalable, highly parallelizable zero-order methods for nonconvex and nonsmooth continuous optimization with guaranteed convergence rates.The unified class includes CBO, MPPI, and further Evolution Strategies such as CMA-ES.
- Motivation: 18? Metaheuristic methods often lack robust theoretical guarantees and quantitative rates to global minima, especially for high-dimensional nonconvex objectives.The paper positions provable global optimization as a response to this theoretical gap.
- CBO framework: CBO combines stochastic particle exploration with consensus-driven contraction toward an instantaneous proxy for the global minimizer.This interaction underlies CBO’s practical effectiveness and theoretical analysis.
- Main challenges: Vanishing noise can make every Dirac delta an invariant measure and create potential suboptimal attractors, while Euler–Maruyama errors grow at large time steps.These issues motivate modifications to both the noise model and numerical discretization.
- δ-CBO: δ-CBO uses fixed-variance noise and has a unique invariant measure, with convergence established even when time horizon and inverse temperature independently tend to infinity.The fixed variance is intended to prevent premature convergence to suboptimal solutions.
- Consensus Freezing and Hopping: Consensus Freezing remains well behaved for large time steps, converges to δ-CBO as the step size vanishes, and leads through time rescaling to Consensus Hopping.The resulting arch connects CBO to MPPI and Evolution Strategies while supplying convergence guarantees and stable implementations.
2. Global Convergence of the δ-CBO Scheme
The δ-CBO scheme converges toward a Gaussian invariant measure centered at the global minimizer, with exponential relative-entropy decay under stated assumptions. Its convergence rate depends only on the drift parameter, while later schemes address the finite-horizon limitation of the initial result.
- Invariant measure and convergence: The δ-CBO law converges toward a Gaussian distribution centered at the global minimizer, with variance determined by δ and λ.Unlike original CBO, whose vanishing noise yields convergence to a Dirac measure, δ-CBO has nonvanishing diffusion and is analyzed through relative entropy.
- Invariant measure and convergence: Under assumptions A1–A2 and sufficiently large α, relative entropy decreases exponentially and reaches any prescribed accuracy within a suitable finite horizon.The proof uses quantitative Laplace estimates together with entropy, log-Sobolev, Talagrand, and optimal-transport arguments.
- Rate and diffusion: The convergence rate is determined by λ and is independent of both the diffusion variance δ^2/2 and the dimension d.Fixing the diffusion variance prevents concentration and avoids dominating, exploding diffusion.
- Rate and diffusion: As the particle number N tends to infinity, δ-CBO's attractor depends on the global minimizer x* rather than on the entire objective function f.The paper interprets this behavior as a canonical convexification of the original nonconvex optimization problem.
- Scope and extension: The theorem does not characterize δ-CBO behavior after the finite horizon T*, motivating analysis of Consensus Freezing and infinite-time convergence.The finite-horizon result supports numerical convergence at prescribed accuracy but does not describe the asymptotic limit as t → +∞.
3. The Consensus Freezing Scheme
Consensus Freezing addresses Euler–Maruyama’s timestep restriction by freezing the consensus point, yielding analytically solvable Ornstein–Uhlenbeck particle dynamics and global convergence to a unique invariant Gaussian measure.
- Construction: Consensus Freezing freezes the consensus point over each interval, allowing particles to follow Ornstein–Uhlenbeck processes that can be solved analytically for large ∆t.This avoids the timestep-fidelity problem of direct Euler–Maruyama discretization.
- Contraction: For sufficiently large α, the consensus map is a contraction on any ball around x∗, with Lipschitz constant tending to zero as α increases.The contraction yields a unique fixed point through Banach’s fixed-point theorem.
- Global-in-time analysis: The scheme admits global-in-time moment bounds and convergence results for arbitrary initial measures in suitable moment classes.The bounds and convergence are established uniformly over specified parameter ranges.
4. The Consensus Hopping Scheme
Consensus Hopping emerges from Consensus Freezing through a large-speed asymptotic limit and provides a discrete-time scheme whose iterates progressively improve the approximation of the global minimizer.
- Asymptotic connection: Consensus Hopping is obtained by rescaling time in Consensus Freezing while keeping ∆t fixed.The limiting construction produces a discrete-time global optimization scheme.
- Asymptotic connection: As s tends to infinity, Consensus Freezing converges to the Consensus Hopping scheme, with discrepancies decaying exponentially in sλ∆t.The convergence holds uniformly over iteration indices in the stated estimates.
- Global convergence: For sufficiently large α, Consensus Hopping converges globally to the invariant measure associated with Consensus Freezing.The proof combines the freezing-to-hopping limit with convergence of Consensus Freezing to its invariant measure.
- Iterative improvement: The scheme improves the approximation step by step, making multiple iterations useful even when the first consensus point is already close to a global minimizer.This conclusion follows from the monotonic decrease up to a small error established in the theorem and remark.
- Iterative improvement: When the current iterate lies near x∗, repeated Consensus Hopping iterations reduce its distance to x∗ up to errors that can be made small by increasing α.The relevant constants become small and the contraction factor becomes less than one for sufficiently large α.
5. Numerical Experiments
The numerical experiments compare δ-CBO and Consensus Freezing across timestep regimes, assess fidelity to continuous-time dynamics through variance, and verify convergence from Consensus Freezing to Consensus Hopping.
- Experimental setup: In the Ackley experiment, both methods use N=5000 particles in dimension d=5 with initial particles outside the minimizer’s box.The setup varies ∆t over [10^-2, 10^2] and terminates after sustained proximity to x∗.
- Performance across timesteps: For small ∆t, δ-CBO and Consensus Freezing require similar iteration counts, but δ-CBO deteriorates near ∆t=1 and stops converging for larger stepsizes.Consensus Freezing retains convergence for all tested ∆t values while requiring fewer iterations as ∆t increases.
- Implementation fidelity: Consensus Freezing’s empirical variance remains close to the continuous-time theoretical variance for all considered ∆t values.The comparison uses particles after 500 iterations and evaluates fidelity through an unbiased variance estimator.
- Implementation fidelity: The discretized δ-CBO scheme approximates its continuous-time dynamics faithfully only for very small ∆t.This contrasts with the exact Consensus Freezing implementation under the same variance-based fidelity criterion.
- Freezing-to-hopping convergence: The empirical Wasserstein distance between Consensus Freezing and Consensus Hopping decreases as s increases and rapidly approaches 0 for sufficiently large s.This experiment uses the Ackley function in dimension d=2 with N=100 particles over 100 iterations.
6. Conclusion and outlook
The paper unifies CBO, Consensus Freezing, and Consensus Hopping through quantitative asymptotics and establishes global-minimizer convergence guarantees for nonsmooth and nonconvex objectives. It also identifies isotropic noise as an important remaining limitation affecting high-dimensional performance.
- CBO, Consensus Freezing, and Consensus Hopping are connected by quantitative asymptotics within a unified analysis.
- The analyzed methods admit complete descriptions and guaranteed convergence rates to global minimizers for nonsmooth and nonconvex objectives.
- The analysis considers exclusively isotropic noise, which is inherently affected by the curse of dimensionality.
- Without adaptive noise covariance, multiparticle algorithms can struggle on non-separable, ill-conditioned problems.
7. Appendix
The appendix develops technical estimates for the analyzed schemes and proves convergence statements through compactness, uniform convergence, and limiting arguments. It also concludes a key estimate using Gronwall’s inequality and establishes convergence of the Consensus Freezing scheme to δ-CBO as the time step vanishes.
- The appendix decomposes a key integral into three terms and bounds them over regions defined relative to the global minimizer.
- The regional estimates establish nonnegativity of the combined terms T1(x) + T2(x) across the relevant sets.
- Gronwall’s inequality converts the derived estimate into the lemma’s conclusion.
- The Consensus Freezing process converges to the solution of δ-CBO as the time step Δt tends to zero.
- Equicontinuity and Arzelà–Ascoli yield a uniformly convergent subsequence for the interpolated consensus trajectories.
- The limiting distribution is shown to satisfy the δ-CBO Fokker–Planck equation through convergence and dominated-convergence arguments.