TL;DR
This paper introduces MVRSM, a novel surrogate modeling technique for optimizing expensive black-box functions with both continuous and integer variables. MVRSM efficiently finds optimal solutions by ensuring its internal model's local optima inherently satisfy integer constraints, unlike previous methods that required costly workarounds. This leads to competitive performance on real-world problems and superior accuracy on large-scale synthetic benchmarks, all while maintaining a constant computational cost per iteration.
What Problem Does This Paper Address?
Many real-world optimization problems involve functions that are difficult to evaluate (e.g., simulations, complex algorithms) and have parameters that are a mix of continuous (like learning rates) and discrete or integer (like the number of layers in a neural network). Traditional optimization methods struggle with these "black-box" mixed-variable problems. Existing surrogate-based methods, which build cheaper models to approximate the expensive function, are often designed for purely continuous or purely discrete variables. Adapting them to mixed variables typically involves either discretizing continuous variables (losing precision) or rounding integer variables (leading to suboptimal solutions and inefficiency). This paper tackles the challenge of developing a surrogate modeling approach that can efficiently and accurately handle mixed-variable optimization problems without these drawbacks.
Methods
The core of this paper is the Mixed-Variable ReLU-based Surrogate Modelling (MVRSM) algorithm. MVRSM uses a surrogate model composed of a linear combination of rectified linear units (ReLUs), a common building block in neural networks. The key innovation lies in how these ReLUs are constructed and combined:
- Integer z-functions: These basis functions are designed such that their local optima are guaranteed to fall on integer values for the integer variables.
- Mixed z-functions: These functions combine both continuous and integer variables. Crucially, they are designed to be parallel to specific vectors, ensuring that when combined with integer z-functions, all local optima of the overall surrogate model satisfy the integer constraints.
- Fixed Model Size: Unlike some Bayesian optimization methods where the surrogate model grows with each iteration, MVRSM maintains a fixed number of basis functions. This ensures a constant computational cost per iteration, preventing the algorithm from slowing down over time.
- Efficient Optimization: Because the surrogate model is linear in its parameters and its local optima satisfy integer constraints, continuous optimization techniques (like L-BFGS) can be used to find the minimum of the surrogate model, avoiding the need for expensive mixed-integer programming solvers.
Datasets
The paper evaluates MVRSM on:
- Real-life benchmarks:
- XGBoost hyperparameter tuning.
- Electrostatic Precipitator (ESP) optimization.
- Synthetic benchmarks:
- Ackley53 (50 binary, 3 continuous variables).
- Rosenbrock238 (119 integer, 119 continuous variables).
- A randomly generated MiVaBO synthetic benchmark (119 integer, 119 continuous variables).
- Func3C (3 categorical, 2 continuous variables).
- Rosenbrock10 (3 integer, 7 continuous variables).
- 8 randomly generated MiVaBO synthetic benchmarks (8 integer, 8 continuous variables).
The synthetic benchmarks are designed to test scalability and the ability to handle a large number of mixed variables, with some being scaled versions of problems used in related literature.
Key Insights and Ideas
- Integer Constraints as a Feature, Not a Bug: The most significant insight is the development of a surrogate model whose structure inherently enforces integer constraints at its local optima. This elegantly sidesteps the need for post-hoc rounding or complex mixed-integer solvers, which are common but inefficient workarounds.
- Constant Iteration Time is Crucial: For expensive black-box functions, the computational cost of the optimization algorithm itself can become significant. MVRSM's fixed iteration time is a major practical advantage, especially when function evaluations are on the order of seconds or minutes.
- ReLUs as a Versatile Tool: The paper demonstrates the power of ReLUs not just for their approximation capabilities but also for their structural properties that can be leveraged to satisfy specific optimization constraints.
- Surprising Performance on Mixed Variables: The paper shows that standard Bayesian optimization (BO), often considered unsuitable for discrete or mixed problems, can perform well when applied to mixed variables, though it is significantly slower than MVRSM.
Key Results
- Competitive Performance on Real-life Benchmarks: MVRSM achieved competitive performance on XGBoost hyperparameter tuning and Electrostatic Precipitator optimization, often matching or exceeding other state-of-the-art methods.
- Superior Accuracy on Large-Scale Synthetic Benchmarks: MVRSM significantly outperformed other methods in terms of accuracy on large-scale synthetic problems (e.g., > 50 variables), including those with up to 238 mixed variables.
- Efficiency Advantage: MVRSM consistently maintained a constant computation time per iteration, while other methods (like BO and CoCaBO) showed a noticeable slowdown as the number of iterations increased. This made MVRSM more efficient overall, especially on problems with many variables or when the objective function evaluation time was comparable to the algorithm's iteration time.
- Outperforms State-of-the-Art: On several synthetic benchmarks, MVRSM clearly outperformed other methods in terms of accuracy, with computation times for BO and CoCaBO becoming prohibitively large.
Limitations and Future Work
- Exploration Strategy: The authors suggest future work could investigate the exploration part of the algorithm, potentially by applying techniques with stronger theoretical guarantees, such as Thompson sampling.
- Categorical and Conditional Variables: The current MVRSM primarily handles continuous and integer variables. Future work could extend the method to efficiently deal with categorical and conditional variables, as well as other types of constraints.
- Multi-objective Problems: The paper focuses on single-objective optimization. Extending MVRSM to multi-objective mixed-variable problems is a potential avenue for future research.
Summary updated