TL;DR
This paper introduces "accelerated EGO," a novel batch sequential adaptive design method that significantly speeds up expensive global optimization problems by leveraging parallel computing and a randomized quasi-random sampling technique. It demonstrates superior performance in both speed and optimization quality compared to existing methods, particularly in high-dimensional scenarios and for hyper-parameter tuning of Support Vector Machines.
What Problem Does This Paper Address?
Computer experiments, often involving complex simulations, are crucial for scientific and engineering advancements. However, these experiments can be computationally expensive, making traditional optimization methods inefficient. Efficient global optimization (EGO) is a popular sequential adaptive design (SAD) method that iteratively refines an approximation of the objective function to find its global minimum. A key limitation of standard EGO is its serial nature, preventing the use of modern parallel computing. While batch EGO methods exist, they often suffer from heavy computational burdens and issues with points clustering. This paper addresses the need for a more efficient and parallelizable SAD that can effectively explore complex, expensive black-box optimization problems.
Methods
The core contribution is the accelerated EGO algorithm. It builds upon the Efficient Global Optimization (EGO) framework, which uses a Kriging model to approximate the expensive objective function and an Expected Improvement (EI) criterion to guide the search for the next experimental point.
The novelty lies in how accelerated EGO selects multiple points for parallel evaluation in each iteration:
- Randomized Quasi-Random Sampling/Importance Resampling (RQSIR): Instead of optimizing the EI function directly for multiple points (which is computationally intensive), RQSIR is employed.
- Candidate Pool Generation: It starts with a pool of candidate points generated using quasi-Monte Carlo (QMC) sequences (e.g., Sobol sequences), known for their good low-discrepancy properties in high dimensions.
- Randomization: A random shift is applied to the QMC points to introduce randomness and ensure that all points have a chance to be selected.
- Resampling: Points are then sampled from this randomized pool based on their EI values, effectively prioritizing points with high potential for improvement while maintaining diversity. This resampling step is computationally much lighter than direct optimization.
This approach aims to achieve the benefits of batch sampling (speedup through parallelism) without the drawbacks of computational cost and point clustering.
Datasets
The paper evaluates its proposed method on:
- Nine classic multi-modal test functions: These functions vary in dimensionality from 2 to 12.
- Five real-world Support Vector Machine (SVM) datasets: 'heart', 'german.n', 'australian', 'svmguide2', and 'glass'. These datasets are used to demonstrate the algorithm's effectiveness in hyper-parameter tuning.
Key Insights and Ideas
- Parallelism is Key for Expensive Optimization: The paper strongly advocates for parallelizing optimization algorithms when dealing with computationally intensive simulations.
- RQSIR as an Efficient Batch Point Selection Strategy: The RQSIR technique offers a computationally tractable way to select multiple promising and diverse points for parallel evaluation, overcoming the limitations of traditional batch EGO methods.
- Trade-off Between Speed and Exploration: Accelerated EGO demonstrates that by intelligently selecting points, the time saved through parallelization can be reinvested to find better solutions, rather than just achieving a faster but potentially suboptimal result.
- High-Dimensional Performance: The method shows particular promise in high-dimensional optimization problems, where traditional methods struggle significantly.
- Practical Application in Hyper-parameter Tuning: The successful application to SVM hyper-parameter tuning highlights the algorithm's real-world utility in machine learning.
Key Results
- Speedup: Accelerated EGO significantly reduces the number of stages (iterations) required to reach a desired accuracy compared to single-point EGO and even the parallel CL(min) algorithm, especially in low-dimensional cases. For instance, for the Branin function, accelerated EGO with 12 updating points needs only 2.45 iterations on average, compared to 13.89 for EGO.
- Computational Cost: CPU time is dramatically reduced. For the Levy10 function in high dimensions, accelerated EGO takes approximately 10 minutes, while CL(min) takes nearly 1.5 hours.
- Optimization Quality: In high-dimensional scenarios, accelerated EGO often achieves better or comparable minimum response values compared to CL(min) and EGO. For the "german.n" SVM dataset, accelerated EGO achieved the highest cross-validation accuracy.
- Robustness: The method is shown to be robust, with sampling points not flocking together, leading to better exploration.
Limitations and Future Work
- Non-Linear Speedup: The paper acknowledges that the speedup of accelerated EGO is not strictly linear with the number of updating points. This means the number of evaluations to reach a certain error might be greater than a perfectly linear speedup would suggest.
- Sensitivity to Pool Size: While the number of cycles is not overly sensitive to the QMC pool size, the paper recommends a pool size of roughly 50s to 100s, where 's' is the problem dimension. Further investigation into optimal pool sizing might be beneficial.
- Further Experiments: The authors suggest that additional experiments could lead to even better results, implying that exploring longer run times or different stopping criteria could yield further improvements.
- Exploration of Other QMC Sequences: While Sobol sequences are used, exploring other QMC sequences or space-filling designs could be a future direction.
Summary updated