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 classification-based derivative-free optimization algorithms. By introducing a concept called hypothesis-target shattering rate, we revisit the computational complexity upper bound of this type of algorithms. Inspired by the revisited upper bound, we propose an algorithm named "RACE-CARS", which adds a random region-shrinking step compared with "SRACOS" (Hu et al., 2017).. We further establish a theorem showing the acceleration of 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 hyperparameter-tuning guidance.

该研究论文介绍了无导数优化算法的框架及分类导数优化算法，通过引入假设目标破碎率的概念，重新审视了该类算法的计算复杂性上界，并提出了一种名为“RACE-CARS”的算法，相较于“SRACOS”（Hu等人，2017），增加了随机区域缩小步骤。通过在合成函数和黑盒调优的实验中证明了“RACE-CARS”的效率，并进行了关于引入的超参数的消融实验，揭示了“RACE-CARS”的机制并提出了一种经验超参数调优指导。

基于区域缩小的加速分类导数优化方法