From Consensus-Based Optimization to Evolution Strategies: Proof of Global Convergence

1. Introduction

• CBO, MPPI, and Evolution Strategies [2] are shown to be globally convergent to global minimizers, with guaranteed convergence rates for nonconvex and nonsmooth objectives.The framework also provides practical guidance for implementing these highly parallelizable, zero-order methods.Source: §1 · p. 2

1.1. Main challenges.

• CBO can prematurely collapse to suboptimal Dirac states because vanishing noise creates arbitrary Dirac invariant measures, while Euler–Maruyama becomes unstable for sufficiently large time steps.Finite-time guarantees also do not fully capture small-population, large-timestep practice or infinite-horizon mean-field convergence from general initial data.Source: §1.2 · pp. 5–6, §1.1 · p. 5

1.2. Solution.

• δ-CBO uses fixed-variance noise and has a unique invariant measure, with global convergence in the joint regime t →∞ and α →∞ independently.This modification is designed to prevent premature convergence to suboptimal solutions.Source: §1.2 · p. 6
• Consensus Freezing freezes the consensus point between time steps, remains stable for arbitrarily large ∆t, converges globally, and approaches δ-CBO as ∆t →0.It avoids the accumulated discretization errors that can make Euler–Maruyama diverge at large time steps.Source: §1.2 · pp. 7–8
• Consensus Hopping arises from Consensus Freezing through time rescaling and is a (1,λ)-Evolution Strategy, enabling exponential convergence rates along the CBO ⇒ CF ⇒ CH connection.The scheme is also identified with MPPI, while the paper proves exponential rates largely absent from classical evolution-strategy convergence results.Source: §1.2 · p. 8

1.3. Methodological note.

• The analysis focuses on mean-field laws, transfers to finite particles through quantitative mean-field limits over finite horizons, and warns that isotropic noise can impose a dimensionality curse.Finite-particle and finite-time implementations follow from Consensus Freezing and Consensus Hopping asymptotics.Source: §1.3 · p. 10

1.4. Technical innovations and breakthroughs.

• Technical advances combine optimal-transport inequalities, refined quantitative Laplace principles, global-in-time moment bounds, invariant-measure contractivity, and a fixed-point argument.These tools yield complete distribution dynamics and expose the intrinsic global-optimization mechanisms of consensus-based dynamics.Source: §1.4 · p. 10

• δ-CBO converges exponentially toward a Gaussian centered at the global minimizer, with variance determined by δ and λ.The result is formulated through exponential decay of relative entropy rather than convergence to a Dirac mass, as in vanishing-noise CBO.Source: §2 · pp. 10, 14
• The proof combines optimal-transport tools, including Talagrand and log-Sobolev inequalities, with the near-Wasserstein-gradient-flow structure of the equation.These ingredients control relative entropy, Fisher information, and the consensus displacement from the minimizer.Source: §2 · pp. 10, 11, 14
• Under Assumptions A1–A2, sufficiently large α achieves prescribed relative-entropy accuracy while the consensus remains near x* over a finite horizon T*.The theorem requires continuity, a unique global minimizer, growth conditions, and a quantitative separation condition at infinity.Source: §2 · pp. 11, 14
• The exponential convergence rate depends only on the drift parameter λ, not on the diffusion variance δ^2/2 or dimension d.Fixing the diffusion variance both prevents concentration and avoids dominating, exploding diffusion.Source: §2 · p. 15
• The finite-horizon theorem does not characterize behavior after T*, so the paper proceeds to analyze Consensus Freezing and later establishes infinite-time δ-CBO convergence.This addresses the limitation that prescribed-accuracy convergence up to T* does not itself describe the asymptotic limit as t approaches infinity.Source: §2 · pp. 15–16

3. The Consensus Freezing Scheme

• Consensus Freezing freezes the consensus point over each time interval, so particles follow analytically solvable Ornstein–Uhlenbeck processes without restrictions from large Δt.This addresses Euler–Maruyama’s loss of fidelity when Δt approaches 1/λ or 1/δ.Source: §3 · p. 16

3.1. Global Convergence of the Consensus Freezing scheme.

• For sufficiently large α, the consensus map is a contraction near the unique global minimizer x∗, and the dynamics has a unique invariant measure ρα∞.The contraction’s Lipschitz constant Lα tends to zero as α →∞.Source: §3.1 · p. 20
• The unique invariant measure is Gaussian, and its mean is a fixed point of Tα; for sufficiently large α, that fixed point is unique in Br(x∗).This invariant measure is also invariant for δ-CBO.Source: §3.1 · pp. 18, 21
• For arbitrary initial measures in Pp(Rd), sufficiently large α yields convergence of the Consensus Freezing and δ-CBO solutions under global-in-time higher-moment bounds.The result applies beyond the Gaussian initialization used in an earlier technical step.Source: §3.1 · p. 22
• The convergence rate can be made arbitrarily close to e^(-sλΔt), with constants and γ chosen uniformly for s ∈[s⋆, +∞), though quantitative α and Cα bounds are not derived.Obtaining explicit parameter bounds would require stronger assumptions and additional quantitative estimates.Source: §3.1 · pp. 22–23
• For fixed s, γ, σ, and Δt with e−sλΔt < γ < 1, there exists α0 such that for all α ≥ α0, W2(ρα_ti, ρ∞) ≤ Cαγi whenever ti ≤ T⋆.Source: §3.1 · p. 26
• The convergence result for δ-CBO recovers the exponential rate from Equation (20), which depends exclusively on λ.This follows because Lα → 0 as α → ∞, allowing any rate parameter γ with e^(-λ) < γ < 1 for sufficiently large α.Source: §3.1 · p. 27

3.1.2. Global-in-time bounds.

• The infinite-time analysis extends the global convergence framework by establishing global-in-time higher-moment bounds for both δ-CBO and the Consensus Freezing scheme.The bounds rely on uniform estimates over transformed measure classes and comparison with an Ornstein–Uhlenbeck reference process.Source: §3.1.2 · pp. 27–29
• For arbitrary initial measures ρ0, ϱ0 ∈ P2(Rd) and any T0 > 0, Lemma 3.19 provides α0 > 0 and S > 0 such that the solutions satisfy its stated condition.Source: §3.1.2 · p. 30

3.1.3. Extension to multiple minimizers.

• The framework is extended from a unique minimizer to a finite union M = ∪_{i=1}^m O_i of compact, connected global-minimizer sets, including isolated minimizers as a special case.Each O_i is flat at the common global minimum, and the analysis introduces neighborhoods Mε around the minimizer set.Source: §3.1.3 · p. 31
• For sufficiently large α, T_α restricted to M_r is a contraction, and the dynamics admits an invariant measure ρ_α.The contraction has Lipschitz constant L_α with L_α →0 as α →∞.Source: §3.1.3 · p. 32

3.2. Convergence of the Consensus Freezing scheme to the δ-CBO Scheme.

• With s = 1, Consensus Freezing converges to δ-CBO as Δt →0, uniformly on every finite interval [0,T].The result applies for initial data ρ_0 ∈ P4(R^d), α > 0, and the same initial data for both schemes.Source: §3.2 · p. 32
• The section concludes by taking s →∞ in Consensus Freezing to derive a further discrete-time global optimization scheme.This asymptotic analysis is developed in the following section.Source: §3.2 · p. 34

4. The Consensus Hopping Scheme

• The Consensus Hopping scheme is introduced as a new optimization scheme [65], with fixed parameter ˜σ.The scheme is defined in the section, where ˜σ is specified as fixed.Source: §4 · p. 34

4.1. Convergence of the Consensus Freezing scheme to the Consensus Hopping Scheme.

• As s →∞, Consensus Freezing converges to Consensus Hopping, with error bounded by 4R · e^(-sλ∆t) and vanishing uniformly over iterations k.The convergence theorem gives the bound 4R · e^(-sλ∆t) → 0 as s →∞, and the corresponding measure bound is uniform in k.Source: §4.1 · pp. 34–35
• Consensus Hopping converges globally to the invariant measure ρα∞ for sufficiently large α, with the result derived from Consensus Freezing convergence or directly from the contraction property.Corollary 4.2 provides the global convergence result, while the section gives two proofs based on the asymptotic alignment and direct contraction.Source: §4.1 · p. 35
• When iterates remain near the global minimizer, increasing α makes the error terms arbitrarily small, so |x_CH_k − x∗| decreases approximately monotonically and improves step by step.Theorem 4.4 and Remark 4.5 show that Γ decays exponentially in α and that the approximation improves along iterations up to a small error.Source: §4.1 · pp. 36–37

5.1. Implementation of the Consensus Freezing scheme.

• Consensus Freezing is implemented by evolving finitely many particles with frozen consensus points over timestep intervals according to the finite-particle dynamics.The scheme samples initial particles from ϱ0 and updates them using the prescribed parameters and timestep Δt.Source: §5 · p. 37, §5.1 · p. 38

5. Numerical Experiments.

• The experiments assess the methods in finite-particle and discrete-time regimes rather than providing systematic benchmark comparisons for Consensus Freezing.Such comparisons would require appropriate noise adaptations, which were not analyzed in this work.Source: §5 · p. 37

5.2. Performance for different values of ∆t.

• Consensus Freezing converges for every tested timestep, whereas δ-CBO deteriorates near Δt = 1 and stops converging for larger stepsizes.For small Δt, both methods behave similarly; Consensus Freezing’s iteration count decreases as Δt increases.Source: §5.2 · pp. 38–39

5.3. Faithfulness of the implementations for different values of ∆t.

• Consensus Freezing reproduces the theoretical variance across all tested Δt, while Euler–Maruyama δ-CBO does so only for very small steps.The δ-CBO discrepancy grows rapidly as Δt approaches 1, whereas Consensus Freezing remains close to its continuous-time prediction.Source: §5.3 · pp. 39–40

5.4. Convergence of Consensus Freezing to the Consensus Hopping scheme.

• The Wasserstein distance between Consensus Freezing and Consensus Hopping decreases with s and rapidly approaches zero for sufficiently large s.This finite-particle, discrete-time experiment numerically reflects the proven mean-field convergence as s tends to infinity.Source: §5.4 · p. 41

• CBO, CF, and CH are connected by quantitative asymptotics and achieve guaranteed convergence rates to global minimizers for nonsmooth and nonconvex objectives.The analysis provides complete descriptions of all three zero-order global optimization methods.Source: §6 · p. 42
• The exclusive use of isotropic noise leaves the methods vulnerable to the curse of dimensionality and inefficient performance on non-separable, ill-conditioned problems without adaptive covariance.Future work targets covariance-modulated optimal transport, followed by efficient, parallelizable deployment on real-world problems.Source: §6 · p. 42

Proof of Lemma 2.4

• The proof of Lemma 2.4 partitions the relevant domain and bounds T1 and T2 to show their sum is nonnegative in each case.The argument treats regions inside Ωr, including A1 ∩ A2 and A1 ∩ A2^c, using geometric bounds, Cauchy–Schwarz, and conditions on c.Source: §7 · p. 43
• Combining the regional estimates yields the lemma’s differential bound, with p = max{p1 + p2, p3}, and Gronwall’s inequality completes the proof.The conclusion follows after assembling the bounds for T1 and T2.Source: §7 · p. 44

Lemma 7.1

• Lemma 7.1 proves that the Consensus Freezing measure ϱα,s,∆t converges to the solution of δ-CBO as ∆t → 0.The proof constructs a sequence with τn → 0, establishes uniform bounds and equicontinuity, and extracts a uniformly convergent subsequence via Arzelà–Ascoli.Source: §7 · p. 44
• The limiting trajectory and its derivative converge uniformly, allowing passage to the limit in the Fokker–Planck equation through continuity, boundedness, and dominated convergence.The argument verifies convergence of the consensus point and drift terms before taking limits in the weak formulation.Source: §7 · pp. 44–46