New Bilevel Optimization Method Beats CMA-ES on Mixed-Variable Problems
A clever bilevel decomposition captures categorical-continuous interactions that stump existing methods...
Mixed categorical-continuous optimization is common in engineering, hyperparameter tuning, and design, but standard evolution strategies like CMA-ES struggle when categorical and continuous variables interact strongly—they assume independence. To overcome this, the authors from University of Tsukuba and RIKEN introduce a bilevel decomposition: an outer loop explores categorical configurations while an inner loop optimizes continuous variables conditioned on that specific categorical choice. This captures interactions explicitly, and the method is grounded in information-geometric optimization for stable convergence.
The computational cost of bilevel optimization can be high, so they implement a warm-starting strategy: maintain a cache of continuous solutions for each categorical configuration, and at each outer iteration, select the best cached configuration to initialize the inner loop. This dramatically reduces the number of function evaluations. In experiments on binary-continuous test problems (including several new interaction types), the method outperformed existing CMA-ES variants—like the one-hot encoding approach and the VSR-CMA-ES—in both solution quality and computational efficiency. The paper was accepted at PPSN 2026, a top conference in evolutionary computation. This advance could improve real-world applications like automated machine learning and control system tuning where mixed variables are common.
- Proposes a bilevel optimization framework that explicitly models interactions between categorical and continuous variables, unlike standard CMA-ES that assumes independence.
- Uses information-geometric stochastic relaxation for both outer (categorical) and inner (continuous) optimization loops.
- Achieves better performance and lower computational cost on binary-continuous benchmarks through a warm-starting strategy that caches and reuses configurations.
Why It Matters
Better optimization of mixed-variable problems means faster, more reliable tuning in engineering, ML, and design automation.