Imagine trying to optimize a system where the parameters look like this: a continuous learning rate ($0.001$ to $0.1$), an integer number of layers ($2$ to $16$), and a categorical choice of optimizer (Adam, SGD, or RMSprop).
This is the reality of mixed-variable black-box optimization. As highlighted by Koch et al. and Franceschi et al., modern machine learning and engineering landscapes are fundamentally heterogeneous. This heterogeneity breaks the core mathematical assumptions of standard optimization algorithms.
To understand why this space is so challenging—and how modern research solves it—we must look at the topological mismatch between different variable types and the clever mechanisms used to unify them.
The Topological Mismatch
Standard optimization techniques are built for uniform spaces. Gradient-based methods require smooth, continuous surfaces where a small step in any direction yields a predictable change. Combinatorial solvers, on the other hand, operate on discrete graphs or grids.
When these spaces mix, traditional strategies fail for deep structural reasons:
- The Failure of Rounding: A common naive approach is to treat integer variables as continuous during optimization and round them to the nearest whole number before evaluation. However, as Watanabe points out, this creates artificial plateaus and step-like structures in the landscape. Continuous optimizers get trapped on these flat steps because the local gradient drops to zero.
- The Absence of Distance Metrics: Categorical variables (like choosing between a convolutional or a recurrent layer) have no natural ordering or distance metric.
Adamis not "closer" toSGDthan it is toRMSprop. Treating them as ordered integers introduces false spatial relationships, while treating ordinal variables (like layer width) as unordered categories discards valuable structural geometry, causing an unnecessary explosion in search space size (Akimoto et al.). - The Combinatorial Explosion: Conversely, trying to discretize the continuous variables to fit a purely combinatorial solver causes the search space to expand exponentially with the number of bins, making the optimization computationally intractable (Ravkic et al.).
The Failure of Traditional Surrogates
In black-box optimization, we often use Bayesian Optimization (BO), which relies on a probabilistic surrogate model—typically a Gaussian Process (GP)—to predict the performance of unsampled points.
GPs rely on kernels that measure the similarity between points based on distance. Because categorical variables lack a distance metric, standard GPs struggle to natively model them. To circumvent this, practitioners often split the problem: using a multi-armed bandit to pick the categorical discrete choices and a separate GP for the continuous parameters.
However, Zuo et al. demonstrate that this splitting introduces severe inconsistencies. The acquisition function (the metric deciding where to sample next) cannot reason about the global space simultaneously, often trapping the search in local optima. Furthermore, Maraval et al. note that relying on separate models forces practitioners to manually engineer expert-tuned kernels or specific priors for every unique combination of data types, destroying the generalizability of the optimization framework.
Joint Stochastic Search and the Margin Mechanism
To solve this, one direction focuses on building stochastic search algorithms that natively maintain a joint representation of the entire space.
Instead of separating variables, Hamano et al. (CatCMA) propose maintaining a unified joint probability distribution. This distribution pairs a multivariate Gaussian (for the continuous parameters) with independent categorical distributions (for the discrete choices). In each iteration, the algorithm samples candidates from this joint distribution, evaluates them, and uses natural gradients to shift the entire distribution toward higher-utility regions.
Joint Distribution
├── Continuous Dimensions ──► Multivariate Gaussian
└── Categorical Dimensions ──► Independent Categorical Distributions
However, stochastic search in discrete spaces faces a unique failure mode: premature convergence. In a continuous space, a mutation step can become infinitely small but remain fluid. In a discrete or categorical space, if the probability of choosing a specific category drops too low, it hits a hard zero—the algorithm permanently "locks out" that choice and stops exploring it.
To fix this, researchers introduced the margin mechanism (Watanabe; Nomura et al.). The margin enforces a lower bound on the probability of any discrete choice or mutation step. By preventing these probabilities from decaying to absolute zero, the margin ensures that the algorithm retains a baseline level of exploration across the discrete components, stabilizing the mutation rates and preventing the search from stagnating in sub-optimal structural configurations.
Bypassing Gaussian Processes: Trees and Density Ratios
Another powerful paradigm abandons Gaussian Processes entirely, replacing them with surrogate models that are natively indifferent to variable types.
Tree Ensembles
Tree-based models, such as Random Forests or Gradient-Boosted Trees, do not rely on spatial distance metrics. Instead, they navigate spaces by making orthogonal splits (e.g., if optimizer == Adam or if learning_rate < 0.01).
By utilizing tree ensembles as surrogates, frameworks like ENTMOOT (Thebelt et al.) can optimize highly constrained, mixed-variable spaces without mathematical transformations. Zuo et al. leverage this property in Value Proposal Trees (VPT), applying a single, global acquisition function across both categorical and continuous variables simultaneously, ensuring that structural choices and numerical parameters are refined in tandem.
Density-Ratio Estimation
An alternative approach reframes the entire optimization problem to bypass the need for a regression surrogate altogether. Klein introduces BORE (Bayesian Optimization by Density-Ratio Estimation), which converts the problem into simple binary classification.
Instead of trying to predict the exact objective value of a mixed-variable candidate, BORE splits past evaluations into two groups: the top $\gamma$-quantile ("good" points) and the rest ("bad" points).
Objective Values: [ 92, 85, 71, 43, 22, 12 ]
│ │ ───────────────────
▼ ▼ ▼
Classification: [ Good, Good, Bad, Bad, Bad, Bad ]
By training an off-the-shelf classifier (like a Gradient-Boosted Tree or a Neural Network) to distinguish between these two classes, the model computes the probability that a new point belongs to the "good" target group. This probability functions directly as the acquisition function. Because standard classifiers are exceptionally robust at handling mixed inputs out of the box, this density-ratio trick allows Bayesian optimization to scale seamlessly to heterogeneous spaces.
Universal Interfaces via String Embeddings
The most recent shift in mixed-variable optimization bypasses explicit geometric modeling altogether by leveraging the universal interface of language.
When humans describe a mixed-variable candidate, we use text: "learning rate: 0.01, optimizer: Adam, layers: 4". Nguyen et al. introduced the "Embed-then-Regress" framework to exploit this. Instead of designing custom kernels for non-tabular geometries, they serialize every candidate into a string representation.
Candidate Config ──► "lr: 0.01, opt: Adam" ──► [Frozen LLM] ──► Continuous Vector ──► Standard Regressor
This string is passed through a frozen, pre-trained Large Language Model (like T5) to extract its text embedding. Because language models are trained on vast amounts of structured text, their embedding spaces already capture the semantic relationships between categorical tokens and numerical values. This projects the heterogeneous candidate into a smooth, continuous vector space. A standard continuous regressor can then be trained on top of these embeddings, providing a universal interface capable of optimizing permutations, graphs, and continuous variables within a single, unified pipeline.