CatCMA : Stochastic Optimization for Mixed-Category Problems

Ryoki Hamano, Shota Saito, Masahiro Nomura, Kento Uchida, Shinichi Shirakawa

Introduction

In real-world engineering and machine learning, optimization problems rarely involve a single type of variable. Designing a new hardware architecture or tuning a neural network often requires balancing continuous variables (like voltage or learning rates) with categorical variables (like material types or choice of activation functions). This is known as Mixed-Category Black-Box Optimization (MC-BBO).

Categorical variables are particularly challenging because they lack an inherent order; you cannot simply "round" a choice between two different optimizers. While Bayesian Optimization (BO) is a standard approach, it often fails to scale as the number of dimensions increases, becoming computationally prohibitive and prone to local optima.

The CatCMA Framework

To bridge this gap, the authors propose CatCMA, a stochastic optimization algorithm built on the foundation of Information Geometric Optimization (IGO). CatCMA maintains a joint probability distribution: a multivariate Gaussian for continuous variables and categorical distributions for discrete ones. It updates this distribution using natural gradients, which provide robustness against parameterization choices.

CatCMA integrates several key enhancements from the Covariance Matrix Adaptation Evolution Strategy (CMA-ES), such as rank-one updates and step-size adaptation ($\sigma$). It also employs an adaptive learning rate mechanism to balance the update speeds between continuous and categorical components.

The "Promising Margin" Innovation

A critical challenge in categorical optimization is premature convergence. If the probability of a specific category drops too low, the algorithm may "forget" it, leading to stagnation. Conversely, if the probability remains too high, the resulting "noise" can stall the optimization of continuous variables.

The authors derived an analytical formula for a "promising margin"—a lower bound for categorical probabilities that ensures the algorithm remains exploratory without drowning out the continuous search signal.

Figure 2: Comparison of different margin settings. The proposed margin (right) allows for simultaneous convergence of categorical probabilities (bottom row) and continuous eigenvalues (middle row), leading to superior best evaluation performance (top row).

As shown in Figure 2, a margin that is too large (left) causes continuous optimization to stall because the categorical noise is too high. A margin that is too small (middle) causes categorical variables to converge too slowly. The proposed analytical margin (right) balances these factors, enabling efficient global convergence.

Performance and Scalability

CatCMA was evaluated against state-of-the-art methods like CASMOPOLITAN and TPE on synthetic benchmarks including SphereCOM, RosenbrockCLO, and MCProximity. A key finding was CatCMA's superior scalability. Unlike BO methods, which slow down significantly as evaluations accumulate, CatCMA maintains a consistent internal computational cost.

Figure 4: Scalability of CatCMA across different problem dimensions (N) and number of categories (K). The proposed margin (orange circles) consistently outperforms larger (blue triangles) or smaller (green triangles) margin settings across varying levels of complexity.

Figure 4 demonstrates that CatCMA’s performance remains robust even as the dimensionality ($N_{co}, N_{ca}$) and the number of categories ($K_n$) increase. In complex tasks like MCProximity, which features strong dependencies between continuous and categorical variables, CatCMA successfully optimized functions where other methods stalled completely.

Conclusion

CatCMA represents a significant step forward for mixed-type optimization. By combining the strengths of CMA-ES with a mathematically grounded approach to categorical margins, it offers a scalable and efficient alternative to Bayesian Optimization for high-dimensional problems. Future work includes extending the framework to natively support integer variables and validating the algorithm on large-scale real-world applications like neural architecture search.

Summary updated

BibTeX
@inproceedings{hamano2024catcma,
  author = {Ryoki Hamano and Shota Saito and Masahiro Nomura and Kento Uchida and Shinichi Shirakawa},
  title = {{CatCMA : Stochastic Optimization for Mixed-Category Problems}},
  booktitle = {GECCO},
  year = {2024},
  doi = {10.1145/3638529.3654198},
}
Figure