Population Control meets Doob's Martingale Theorems: the Noise-free Multimodal Case

Marie-Liesse Cauwet, Olivier Teytaud

Abstract

This paper investigates the efficacy of Test-Based Population Size Adaptation (TBPSA), an algorithm originally designed for noisy optimization, in solving noise-free multimodal problems. By leveraging Doob’s Martingale Theorems, the authors provide a theoretical foundation for the algorithm's ability to escape flat plateaus in a fitness landscape with probability one. Empirical evaluations using the Nevergrad benchmark suite demonstrate that a modified version, NaiveTBPSA, is a top-tier performer in complex multimodal and parallel settings, offering a robust alternative to traditional restart strategies.

Introduction: Navigating Complex Landscapes

In global optimization, "multimodal" landscapes present a significant challenge: they are characterized by numerous local optima (valleys) that can trap an algorithm before it reaches the global optimum. Standard evolutionary algorithms often struggle with these traps, either converging prematurely or requiring inefficient "restarts" from scratch.

Visualizing common multimodal benchmark functions used to evaluate optimization algorithms.

This research addresses two primary hurdles in these landscapes:

  1. Local Minima: The risk of getting stuck in a sub-optimal valley.
  2. Plateaus: Perfectly flat regions where the absence of a gradient leaves the algorithm without direction.

Methodology: TBPSA and Martingale Analysis

The researchers focus on TBPSA and a variant termed NaiveTBPSA:

  • TBPSA: This algorithm doubles its population size ($\lambda$) whenever a statistical test indicates no significant difference between current and previous samples. In its original noisy-environment design, it recommends the center of its search distribution as the final solution.
  • NaiveTBPSA: For the noise-free case, the authors modify the recommendation strategy to return the best point ever visited during the run, which significantly improves performance.

The Plateau-Escaping Proof

A key contribution of this work is the theoretical analysis using Doob’s Martingale Theorems. The authors analyze the algorithm's "step-size" (the range of its exploration). They prove that on a plateau, the step-size does not collapse to zero. Because the population grows exponentially while the step-size remains stable, the algorithm eventually "mechanically" samples a point far enough away to find the edge of the plateau and continue its descent.

Key Results and Performance

The study utilized the Nevergrad optimization library to benchmark NaiveTBPSA against established methods like Covariance Matrix Adaptation Evolution Strategy (CMA-ES) and Differential Evolution (DE) variants across a wide range of functions (e.g., Rastrigin, Ackley, and DeceptiveMultimodal).

Performance comparison heatmap showing NaiveTBPSA (75.0%) as a leading algorithm among various competitors in Nevergrad benchmarks.

Insights

  • Top-Tier Performance: NaiveTBPSA emerged as a leading performer, particularly in "paramultimodal" experiments. It scales exceptionally well in parallel settings (e.g., 1000 concurrent evaluations), making it ideal for high-performance computing.
  • The Convergence Trap: Despite its strengths, the authors identified a limitation: if an algorithm converges too quickly (log-linearly) into a convex local minimum, population scaling alone cannot guarantee escape. The "pull" of the local minimum can outweigh the expansion of the population.
  • Recommendation Strategy: The shift from recommending the distribution center to the "best seen" point is critical for success in noise-free multimodal optimization.

Conclusion and Future Directions

The proof that TBPSA escapes plateaus with probability one provides a strong theoretical justification for its use in complex landscapes. While it faces limitations in escaping certain fast-converging local minima, its versatility across diverse problem types—including multiobjective optimization—is notable. Future work may involve hybridizing the TBPSA population control mechanism with other powerful algorithms like CMA-ES or Particle Swarm Optimization (PSO) to enhance their plateau-escaping capabilities.

Summary updated

BibTeX
@inproceedings{cauwet2020population,
  author = {Marie-Liesse Cauwet and Olivier Teytaud},
  title = {{Population Control meets Doob's Martingale Theorems: the Noise-free Multimodal Case}},
  booktitle = {GECCO Companion},
  year = {2020},
  doi = {10.1145/3377929.3389957},
}
Figure