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” 的机制并提出了一种经验超参数调优指导。

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

A Region-Shrinking-Based Acceleration for Classification-Based  Derivative-Free Optimization

Black-box prompt tuning uses derivative-free optimization algorithms to learn
prompts in low-dimensional subspaces instead of back-propagating through the
network of Large Language Models (LLMs). Recent studies have found that
black-box prompt tuning lacks versatility across tasks and LLMs, which we
believe is related to the inappropriate choice of subspaces. In this paper, we
propose Black-box prompt tuning with Subspace Learning (BSL) to improve the
versatility of black-box prompt tuning. Based on the assumption that nearly
optimal prompts for similar tasks exist in a common subspace, we propose
identifying such subspaces by meta-learning on a set of similar source tasks.
Therefore, for a target task that shares similarities with source tasks, we
guarantee that optimizing in the subspace can find a prompt that performs well
on the target task. Experiments confirm that our BSL framework consistently
achieves competitive performance regardless of downstream tasks and LLMs.

本文提出使用子空间学习来改进黑盒提示微调的灵活性，并证明该模型在不同任务和大型语言模型中均具有竞争力的性能表现。