Scalable Acceleration for Classification-Based Derivative-Free Optimization

Abstract

Derivative-free optimization algorithms play an important role in scientific and engineering design optimization problems, especially when derivative information is not accessible. In this paper, we study the framework of sequential classification-based derivative-free optimization algorithms. By introducing learning theoretic concept hypothesis-target shattering rate, we revisit the computational complexity upper bound of SRACOS (Hu, Qian, and Yu 2017). Inspired by the revisited upper bound, we propose an algorithm named RACE-CARS, which adds a random region-shrinking step compared with SRACOS. We further establish theorems showing the acceleration by region shrinking. Experiments on the synthetic functions as well as black-box tuning for language-model-as-a-service demonstrate empirically the efficiency of RACE-CARS. An ablation experiment on the introduced hyperparameters is also conducted, revealing the mechanism of RACE-CARS and putting forward an empirical hyper-parameter tuning guidance.

References in corpus (13)

• Practical Bayesian Optimization of Machine Learning Algorithms
• On Hyperparameter Optimization of Machine Learning Algorithms: Theory and Practice
• Character-level Convolutional Networks for Text Classification
• High-dimensional classification using features annealed independence rules
• BOHB: Robust and Efficient Hyperparameter Optimization at Scale
• Scalable Global Optimization via Local Bayesian Optimization
• Batched Large-scale Bayesian Optimization in High-dimensional Spaces
• ZO-AdaMM: Zeroth-Order Adaptive Momentum Method for Black-Box Optimization
• Truncated Variance Reduction: A Unified Approach to Bayesian Optimization and Level-Set Estimation
• Learning Search Space Partition for Black-box Optimization using Monte Carlo Tree Search
• Derivative free optimization via repeated classification
• Zeroth-order Optimization with Weak Dimension Dependency
• The Sampling-and-Learning Framework: A Statistical View of Evolutionary Algorithms