Technical Summary: Mixed-Categorical Black-Box Optimization via Information-Geometric Bilevel Decomposition

Problem Definition

The paper addresses Mixed-Categorical Black-Box Optimization (MC-BBO), a class of problems where the objective function $f(c, x)$ must be minimized over a heterogeneous domain comprising categorical variables $c$ and continuous variables $x$. Specifically, the study focuses on the case where $c$ consists of discrete categorical variables (modeled as one-hot vectors or binary bits) and $x \in \mathbb{R}^{d_x}$.

The core challenge identified is the presence of strong categorical-continuous interactions. Existing state-of-the-art Evolution Strategy (ES) approaches, such as CatCMA and ICatCMA, model the search distribution as a product of a multivariate Gaussian (for $x$) and a categorical distribution (for $c$). This product distribution assumption implicitly enforces independence between $c$ and $x$, preventing these methods from learning complex dependencies where the optimal continuous configuration depends heavily on the categorical choice. While Bayesian methods exist, they often suffer from scalability issues in high-dimensional spaces.

Methodology: IGBD

The authors propose Information-Geometric Bilevel Decomposition (IGBD), a framework that explicitly models the dependency between categorical and continuous variables by reformulating the problem as a bilevel optimization task:

$$\min_{c} f(c, x^\star) \quad \text{s.t.} \quad x^\star = \arg\min_{x} f(c, x)$$

The method employs Information-Geometric Optimization (IGO) to formulate stochastic relaxations for both levels of the hierarchy:

1. Upper Level (Categorical Optimization):

   • Optimizes the probability vector $q$ governing the categorical distribution.
   • Uses the Adaptive Stochastic Natural Gradient (ASNG) method.
   • Updates $q$ along the natural gradient using rank-based fitness shaping to ensure invariance to monotonic transformations.
   • Adapts the step size (trust radius) using a cumulative step-size adaptation (CSA) mechanism analogous to CMA-ES.

2. Lower Level (Continuous Optimization):

   • Optimizes the continuous variables $x$ conditioned on a fixed categorical configuration $c$.
   • Uses dd-CMA-ES (a diagonal variant with active update) to minimize the objective $f(c, x)$.
   • The lower-level solver is treated as a stateful process that provides an estimate of the optimal $x^\star(c)$ to the upper level.

3. Warm-Starting Strategy (Cache Mechanism):

   • To mitigate the prohibitive computational cost of solving the lower-level problem to convergence for every upper-level candidate, IGBD introduces a warm-starting strategy.
   • A cache of $N_\omega$ lower-level configurations $\{(x_k, \omega_k, p_k)\}$ is maintained, where $\omega_k$ represents the CMA-ES parameters (mean and covariance) and $p_k$ is a quality score.
   • Selection: For each upper-level candidate $c_i$, the algorithm selects the best cached configuration $k^\star_i$ based on the current objective value.
   • Initialization: The lower-level solver for $c_i$ is initialized with the parameters from the selected cache entry.
   • Update: After the lower-level search, the cache is updated. Selected entries are refreshed with the new solver state, and their scores are incremented; unselected entries have their scores decremented. Entries falling below a threshold are re-initialized randomly to promote exploration.

Key Contributions

1. IGBD Framework: The proposal of a bilevel optimization framework for MC-BBO where each level is a stochastic relaxation under IGO. This explicitly captures categorical-continuous interactions that product-distribution methods miss.
2. Novel Interaction Type: The introduction of a fourth type of interaction (Type-IV) where categorical variables govern the interactions within the continuous domain itself (e.g., by changing the covariance structure or rotation of the continuous landscape), in addition to determining the optimal location.
3. Benchmarking: Comprehensive evaluation against CatCMA and ICatCMA on binary-continuous domains, including existing interaction types (I, II, III) and the newly proposed Type-IV, across varying dimensionalities ($d_c=d_x=5$ and $10$) and interaction strengths.

Experimental Results

The experiments demonstrate that IGBD outperforms existing methods in handling strong interactions while maintaining computational efficiency:

• Interaction Handling: IGBD achieves a 100% success rate across almost all tested interaction types and strengths, including the challenging Type-IV interactions where CatCMA and ICatCMA fail significantly.
  • CatCMA: Performs well only when interactions are weak or absent (independence assumption holds). It fails on Type-III and Type-IV interactions as interaction strength increases.
  • ICatCMA: Improves over CatCMA on Type-II (affine mapping) interactions due to its hyper-representation but fails on Type-III (non-linear masking) and Type-IV interactions. Its performance degrades sharply as interaction complexity grows.
• Computational Efficiency:
  • IGBD is generally more efficient than ICatCMA, which incurs high costs due to its affine hyper-representation parameters.
  • While CatCMA is faster on simple problems (weak interactions), IGBD becomes more robust and efficient as interaction strength ($a$) increases, avoiding the massive restart cycles and failure rates seen in baselines.
• Scalability: The proposed method maintains high success rates at higher dimensions ($d=10$), whereas baselines struggle significantly, particularly with Type-IV interactions.

Significance and Claims

The paper claims that IGBD represents a significant step forward in mixed-variable black-box optimization by addressing the fundamental limitation of independence assumptions in current Evolution Strategies. By leveraging a bilevel structure with information-geometric principles and a warm-starting cache, the method effectively models complex dependencies between discrete and continuous variables.

The authors note that while the current implementation is restricted to the binary-continuous domain, the approach naturally extends to general mixed-categorical optimization. They acknowledge that the method's high computational cost in extreme interaction regimes is primarily due to the function evaluation budget rather than a fundamental algorithmic flaw. Future work is suggested to include extending to non-binary categories, handling low-effective-dimension subspaces, and integrating lower-cost heuristics to further alleviate the bilevel optimization burden.