A multiscale Consensus-Based algorithm for multi-level optimization

Michaël Herty, Yuyang Huang, Dante Kalise, Hicham Kouhkouh

TL;DR

This paper introduces a multiscale Consensus-Based Optimization (CBO) algorithm designed to solve complex, hierarchical optimization problems (bi-level and tri-level). By evolving multiple populations of particles on different time scales—where lower-level populations "race" to find optima while upper-level populations move more deliberately—the authors provide a robust, derivative-free framework for tackling non-convex nested problems.

What Problem Does This Paper Address?

Many real-world problems are hierarchical: a "leader" makes a decision, and a "follower" optimizes their response based on that decision. This is known as multi-level optimization. Examples range from supply chain management (manufacturer vs. distributor) to machine learning tasks like coreset selection or hyperparameter tuning.

These problems are notoriously difficult (NP-hard even in simple linear cases) because the constraints of the upper-level problem are themselves optimization problems. Traditional gradient-based methods often struggle with non-convexity, discontinuities, or high-dimensional search spaces where gradients are unavailable or unreliable. While Consensus-Based Optimization (CBO) has proven effective for global, single-level optimization, extending it to these nested hierarchies remained a significant challenge.

Methods

The authors propose a multiscale CBO approach. Instead of a single group of particles, they use interacting populations that operate on different time scales:

  1. Singularly Perturbed Dynamics: The system is modeled using Stochastic Differential Equations (SDEs). A small parameter ($\epsilon$) creates a "fast-slow" dynamic. The lower-level particles (fast) reach a steady-state consensus quickly, providing the necessary input for the upper-level particles (slow) to update.
  2. Hierarchical Populations: For a bi-level problem, each "slow" $X$-particle is associated with its own "fast" population of $Y$-particles. The $Y$-particles explore the lower-level landscape to find the best response for their specific $X$-particle's current position.
  3. Averaging Principle: The authors theoretically prove that as the time-scale separation becomes infinite ($\epsilon \to 0$), the multiscale system converges to an "effective" dynamics.
  4. Forward-Looking Averaging (FLA): To make the algorithm computationally efficient, they use FLA (similar to an exponentially weighted moving average). This allows the algorithm to estimate the consensus of the fast particles without waiting for perfect convergence at every step.
  5. Derivative-Free: Like standard CBO, this method does not require gradient information, making it suitable for "black-box" objective functions.

Datasets

The algorithm was evaluated using standard global optimization benchmark functions adapted for multi-level structures:

  • Ackley Function: Known for having many local minima and a flat outer region.
  • Rastrigin Function: A highly multi-modal function used to test a solver's ability to escape local optima.
  • Levy Function: Another complex landscape used to evaluate global search capabilities.

The authors also tested the method on min-max (saddle point) problems, treating them as a special case of bi-level optimization.

Key Insights and Ideas

  • Time as a Hierarchy: The most elegant idea is using time-scale separation to mirror the logical hierarchy of the problem. By making the lower-level "faster," the algorithm naturally respects the "subject to" constraint of the upper level.
  • Model Reduction: The proof of convergence to "effective CBO" shows that a complex system of interacting particles can be simplified into a single-level update rule that accounts for the lower-level's behavior through an invariant measure.
  • Parallelization: Because each upper-level particle manages its own lower-level population independently, the algorithm is highly parallelizable, which is crucial for scaling.
  • Min-Max Superiority: The authors found that treating min-max problems as bi-level hierarchies (using their multiscale approach) actually performed better than existing CBO variants specifically designed for saddle points.

Key Results

  • Bi-level Success: In 100 Monte Carlo simulations across various benchmarks (Ackley, Rastrigin, Levy), the MS-CBO algorithm achieved a 100% success rate in finding the global optimum with very low error (often $10^{-4}$ or better).
  • Tri-level Performance: The algorithm successfully scaled to tri-level problems, maintaining success rates between 94% and 100%, even as the complexity of the hierarchy increased.
  • Comparison with SP-CBO: On a non-separable Rastrigin min-max problem, MS-CBO achieved a 97% success rate, vastly outperforming the existing SP-CBO method, which only managed a 5% success rate.
  • Efficiency: While the multiscale approach requires more total particles ($N \times M$), the authors demonstrate that $M$ (the lower-level population size) can be kept relatively small ($M \ll N$) without sacrificing accuracy.

Limitations and Future Work

  • Parameter Sensitivity: The performance is sensitive to the choice of noise ($\sigma$) and drift ($\lambda$) parameters. The authors noted that multi-level problems require more "exploration" (higher noise) than single-level ones.
  • Computational Overhead: Although parallelizable, the nested nature of the algorithm is inherently more expensive than single-level optimization.
  • Theoretical Gap: While the paper proves convergence to the averaged dynamics, it does not yet provide a rigorous proof that these dynamics will always converge to the global global optimizer of the multi-level problem (though numerical results are promising).
  • Future Directions: The authors suggest exploring more sophisticated ways to compute the invariant measure of the fast process and investigating the "mean-field limit" (where the number of particles goes to infinity) for the averaged model.

Summary updated

Abstract

A novel multiscale consensus-based optimization (CBO) algorithm for solving bi- and tri-level optimization problems is introduced. Existing CBO techniques are generalized by the proposed method through the employment of multiple interacting populations of particles, each of which is used to optimize one level of the problem. These particle populations are evolved through multiscale-in-time dynamics, which are formulated as a singularly perturbed system of stochastic differential equations. Theoretical convergence analysis for the multiscale CBO model to an averaged effective dynamics as the time-scale separation parameter approaches zero is provided. The resulting algorithm is presented for both bi-level and tri-level optimization problems. The effectiveness of the approach in tackling complex multi-level optimization tasks is demonstrated through numerical experiments on various benchmark functions. Additionally, it is shown that the proposed method performs well on min-max optimization problems, comparing favorably with existing CBO algorithms for saddle point problems.
BibTeX
@inproceedings{herty2025multiscale,
  author = {Michaël Herty and Yuyang Huang and Dante Kalise and Hicham Kouhkouh},
  title = {{A multiscale Consensus-Based algorithm for multi-level optimization}},
  booktitle = {Mathematical},
  year = {2025},
  doi = {10.1142/s021820252550037x},
}
Figure