Technical Summary: Convergence Analysis of Evolution Strategies for Mixed-Integer Optimization

Problem Statement

Mixed-integer optimization problems involve minimizing objective functions over domains containing both continuous and integer variables. Evolution Strategies (ES), particularly the Covariance Matrix Adaptation ES (CMA-ES), are powerful tools for continuous black-box optimization. To extend these to mixed-integer domains, a common approach involves sampling continuous vectors and discretizing selected coordinates to generate integer values.

A critical challenge in this extension is preventing "premature convergence" of integer variables. If the standard deviation ($\sigma$) of the search distribution in integer dimensions becomes too small relative to the integer intervals, the generated integers may fixate on a single value, halting exploration. To counter this, existing methods (e.g., (1+1)-CMA-ES with Margin) impose a lower bound ($\sigma_{LB}$) on the standard deviation of integer variables.

However, the theoretical impact of this lower bound on the convergence of continuous variables remains unclear. A large $\sigma_{LB}$ prevents integer fixation but increases the probability of mutating optimal integers to suboptimal values, potentially degrading the convergence of continuous variables. Conversely, a small $\sigma_{LB}$ risks integer fixation. While empirical studies suggest trade-offs, there is a lack of rigorous theoretical analysis regarding how these integer-handling mechanisms affect the convergence rate of the continuous component, particularly in high-dimensional settings.

Methodology

The authors analyze two variants of the (1+1)-ES algorithm applied to mixed-integer spaces, focusing on the optimization phase after the integer variables have reached their optimal values.

1. Algorithms Analyzed:

   • (1+1)-LB-ES: A (1+1)-ES variant that enforces a lower bound $\sigma_{LB}$ on the standard deviation for integer variables to prevent fixation.
   • (1+1)-LUB-ES: An extension of the above that introduces an upper bound on the standard deviation for integer dimensions where the integer mutation was not successful. This upper bound is designed to prevent the mutation rate of non-optimal integers from increasing unnecessarily, thereby protecting the convergence of continuous variables.

2. Benchmark Function:
   To isolate the effects of integer handling on continuous convergence, the authors introduce LexicoSphereInt. This is a lexicographic variant of the Sphere function ($f(\mathbf{x}, \mathbf{z}) = \|\mathbf{x}\|^2 + \|\mathbf{z}\|^2$).

   • Solutions are ranked first by the integer component ($\|\mathbf{z}\|^2$) and second by the continuous component ($\|\mathbf{x}\|^2$).
   • This setup ensures that once the optimal integer vector is found, it remains optimal, allowing the analysis to focus strictly on the dynamics of the continuous mean vector $\mathbf{m}_t$ and the step-size $\sigma_t$.

3. Analytical Approach:

   • The analysis assumes the integer part of the elitist solution is already optimal ($\boldsymbol{\mu}_t = 0$).
   • The authors employ drift analysis (specifically additive and truncated drift theorems) on the logarithm of the ratio between the distance to the optimum and the step-size.
   • They utilize properties of the normal distribution to bound the probability of generating optimal vs. non-optimal integers under different step-size conditions.
   • The analysis considers the limit where the number of integer variables ($d_{in}$) is large relative to the continuous variables ($d_{co}$).

Key Contributions and Results

1. Premature Convergence of (1+1)-LB-ES

The paper rigorously proves that (1+1)-LB-ES suffers from premature convergence in high-dimensional mixed-integer problems.

• Mechanism: When the number of integer variables ($d_{in}$) is large, the probability of generating the optimal integer vector decreases rapidly as the step-size increases. Consequently, the algorithm frequently experiences "unsuccessful" updates, causing the step-size $\sigma_t$ to decrease.
• Result: The step-size decreases faster than the distance to the optimum ($\|\mathbf{m}_t\|$). The authors prove that there exists a constant $C_{lower} > 0$ such that the expected distance to the optimum remains bounded below:
  $$E[\|\mathbf{m}_{s\tau}\|] \geq C_{lower} \cdot \|\mathbf{m}_0\|$$
  for any iteration count $\tau$. This implies the algorithm fails to achieve linear convergence and stagnates at a suboptimal distance from the solution.

2. Linear Convergence of (1+1)-LUB-ES

The paper demonstrates that (1+1)-LUB-ES, which incorporates the upper bound on the standard deviation for unsuccessful integer mutations, achieves linear convergence.

• Mechanism: The upper bound prevents the standard deviation in integer dimensions from growing excessively when integer mutations fail. This stabilizes the step-size adaptation, allowing the continuous variables to continue optimizing even when integer mutations are occasionally unsuccessful.
• Result: Under suitable parameter settings (specifically regarding the target success rate $1/s$), the expected first hitting time to find an $\epsilon$-neighbor of the optimum is:
  $$E[T_\epsilon] \in \Theta(d_{co} \cdot \log(1/\epsilon))$$
  This matches the convergence rate of standard (1+1)-ES on continuous sphere functions, proving that the upper bound effectively mitigates the negative impact of integer handling.

3. Parameter Conditions

The analysis derives a specific condition for the target success rate parameter $s$ required to achieve linear convergence in (1+1)-LUB-ES:
$$s > \frac{2}{p_{succ, in, LB}}$$
where $p_{succ, in, LB}$ is the probability of generating the optimal integer vector when the standard deviation is at the lower bound. This provides a theoretical guideline for tuning $s$ based on the dimensionality of the problem.

Significance and Claims

The paper claims to provide the first rigorous theoretical account of how integer handling mechanisms impact the convergence of continuous variables in mixed-integer Evolution Strategies.

• Theoretical Insight: It clarifies that simply imposing a lower bound on the standard deviation (a common practice to prevent integer fixation) is insufficient for high-dimensional problems and can actively hinder continuous optimization.
• Design Guidance: The results suggest that the upper bound mechanism (preventing excessive step-sizes in dimensions with failed integer mutations) is essential for achieving linear convergence in mixed-integer domains.
• Practical Implication: The derived condition for the success rate parameter $s$ offers a concrete, theoretically grounded method for hyperparameter tuning in mixed-integer ES algorithms, moving beyond purely empirical heuristics.

The authors note that their analysis focuses on the phase where integer variables are already optimized. Future work is suggested to analyze the runtime for optimizing the integer variables themselves and to extend these findings to mixed-category optimization problems.