Black-Box Tuning for Language-Model-as-a-Service

Introduction

Scaling pre-trained language models (PTMs) has shown increasing power on a wide range of NLP tasks (Devlin et al., 2019; Raffel et al., 2020; Brown et al., 2020; Fedus et al., 2021; Zhang et al., 2020, 2021b; Zeng et al., 2021; Sun et al., 2021; Qiu et al., 2020). Extremely large PTMs can easily generalize to various downstream tasks with a few labeled samples (Brown et al., 2020). However, making these large PTMs benefit everyone is a challenge. On the one hand, running such models can be very expensive or even infeasible for most users. On the other hand, the model parameters are often not open-sourced due to commercial considerations and the potential risk of misuse.https://openai.com/blog/openai-api/ Therefore, large PTMs such as GPT-3 (Brown et al., 2020), ERNIE 3.0 (Sun et al., 2021) and Yuan 1.0 (Wu et al., 2021) are usually released as a service, allowing users to access these powerful models through black-box APIs.

In this scenario, called Language-Model-as-a-Service (LMaaS), users can solve the language tasks of interest using the black-box APIs by crafting task-specific text prompts or including training samples in the input texts (a.k.a. in-context learning (Brown et al., 2020)). Due to the great power of the general-purpose PTMs underlying the APIs, such approaches can achieve considerable performance on simple language tasks, and therefore have powered many interesting applicationsSee https://gpt3demo.com/ for examples.. However, querying large PTMs through hand-crafted text prompts cannot fully exploit labeled data, resulting in unsatisfactory performance in many use cases.

Instead of designing discrete text prompts, recently much effort has been devoted to continuous prompt tuning (Li & Liang, 2021; Hambardzumyan et al., 2021; Liu et al., 2021b), which is to optimize the continuous prompt injected to the text while keeping the PTM parameters frozen. Such methods only require storing a small continuous prompt for each task, and therefore are highly deployment-efficient. Besides, tuning the continuous prompt can be as effective as fine-tuning the entire model when the PTM becomes large (Lester et al., 2021). However, in all the previous methods, the continuous prompts are learned through backpropagation, which is unavailable in the scenario of LMaaS.

Can we optimize the task-specific continuous prompts when we only have access to the PTM inference API? Since gradients are unavailable, we can only invoke derivative-free optimization (DFO)Also termed as black-box, zeroth-order or gradient-free optimization. (Kolda et al., 2003; Conn et al., 2009; Rios & Sahinidis, 2013). DFO involves a kind of optimization algorithms that do not depend on gradients, but only relies on function values (or fitness values) of sampled solutions. However, DFO algorithms are known to suffer from slow convergence rate when the dimensionality of the search space is high. Thus, it is intractable to optimize even only the continuous prompts, which can be tens of thousands of parameters, using DFO algorithms.

Fortunately, recent work found that common PTMs, despite their large numbers of parameters, have a very low intrinsic dimensionality (Aghajanyan et al., 2021; Qin et al., 2021). That means, there exists a low-dimensional reparameterization that is as effective for fine-tuning as the full parameter space. It has been demonstrated that optimizing only hundreds (Aghajanyan et al., 2021) or even dozens (Qin et al., 2021) of parameters can achieve non-trivial performance. Given that the intrinsic dimensionality of the objective function (in our case is the forward computation of PTMs) is low, the optimization can be effectively solved via DFO algorithms with random embedding (Wang et al., 2016; Qian et al., 2016; Letham et al., 2020).

Based on the these insights, this paper proposes the Black-Box Tuning (BBT) to solve various language understanding tasks by only accessing the PTM inference API. In particular, we manage to optimize the continuous prompt prepended to the input text by iteratively querying the PTM inference API, as briefly depicted in Figure 1. To handle the high dimensionality of the continuous prompt, we project the original prompt space using a random linear projection onto a much smaller subspace and solve this optimization problem with some derivative-free optimizer in that smaller subsapce. In contrast to conventional fine-tuning methods that can only be performed by the service side, black-box tuning allows users to optimize their task-specific prompts locally on resource-limited devices (even without GPUs). Our experimental results demonstrate that prompting RoBERTaLARGE (Liu et al., 2019) using BBT on a few labeled samples not only outperforms manual prompt and in-context learning (Brown et al., 2020), but also outperforms its gradient-based counterparts, namely prompt tuning (Lester et al., 2021) and full model tuning.

The contribution of this paper is three folds:Our code is publicly available at https://github.com/txsun1997/Black-Box-Tuning

This paper proposes a novel scenario (LMaaS) where one should learn to prompt the PTMs by only accessing their inference APIs.

This paper offers a solution (BBT) for such a scenario to accomplish common language understanding tasks without access to model parameters and gradients, such that large-scale PTMs can better benefit users.

Empirical results show that DFO can successfully deal with real-world language tasks by learning to prompt large-scale PTMs with more than millions of parameters. Thus, this work pioneers the work of optimizing large-scale PTMs through DFO methods.

Background

It is a promising way to deploy large-scale PTMs to serve downstream applications by providing general-purpose APIs. For the service side, wrapping the computation of the PTM into an easy-to-use API has become a common practice (Brown et al., 2020; Sun et al., 2021; Wu et al., 2021). In contrast to training, the inference speed of large-scale PTMs can be highly optimized with acceleration techniques such as ORT and TensorRT. In addition, large-scale PTMs are often not open-sourced due to the commercial reasons and the potential risk of misuse. For the user side, even if the large-scale PTMs are available, it is expensive or even infeasible to locally run them. Thus, how to exploit the PTM inference API to solve conventional language tasks is a promising direction.

Intrinsic Dimensionality of PTMs.

The intrinsic dimensionality of an objective function is the minimum number of parameters needed to obtain satisfactory solutions (Li et al., 2018). In particular, the intrinsic dimensionality indicates the lowest dimensional reparameterization that is as effective for optimizing as the full parameter space. Li et al. (2018) propose to measure the intrinsic dimensionality of neural networks by finding the minimal dimensionality of the subspace that is randomly projected from the full trainable parameters, in which they can optimize the neural networks to achieve satisfactory solutions. Aghajanyan et al. (2021) empirically show that large-scale pre-training implicitly compresses the intrinsic dimensionality of downstream NLP tasks. By tuning only hundreds of parameters that are then randomly projected onto the full parameter space of RoBERTa, they can achieve 90% performance relative to full model tuning. Qin et al. (2021) show that intrinsic subspace on various tasks can be compressed to less than 100 dimensions with multi-task supervision. This line of research, along with the work of parameter-efficient tuning (Houlsby et al., 2019; Li & Liang, 2021; Lester et al., 2021; Sun et al., 2022; Hu et al., 2021a; He et al., 2021), demonstrate that PTMs can well adapt to downstream tasks by tuning a very small proportion of parameters, which implies the possibility of optimizing large-scale PTMs with derivative-free algorithms.

Prompt-Based Learning.

Prompt-based learning is to formulate downstream tasks as a (masked) language modeling task, and therefore reduces the gap between PTM pre-training and fine-tuning (Brown et al., 2020; Schick & Schütze, 2021a, b; Gao et al., 2021; Sun et al., 2022). For instance, one can use BERT (Devlin et al., 2019) to predict whether the sentence ”This is a fantastic movie” is positive or negative by appending the prompt ”It was [MASK]” and see if BERT predicts ”great” or ”terrible” at the masked position. Note that the prompt is not necessarily discrete, it can also be optimized efficiently in continuous space with gradient descent (Li & Liang, 2021; Hambardzumyan et al., 2021; Qin & Eisner, 2021; Liu et al., 2021b; Zhong et al., 2021). In the case of only tuning the continuous prompt while keeping the parameters of large PTMs untouched, one can retain the efficient serving benefits while matching the performance of full model tuning (Lester et al., 2021). Our work also proposes to optimize the continuous prompt while keeping the PTM parameters unchanged, but without gradient descent.

Derivative-Free Optimization.

Derivative-free optimization (DFO) realizes optimization only via the function values $f(\mathbf{x})$ on the sampled solutions $\mathbf{x}$. Most DFO algorithms share a common structure of sampling-and-updating to enhance the quality of solutions. Representative DFO algorithms include evolutionary algorithms (Hansen et al., 2003), Bayesian optimization (Shahriari et al., 2016), etc. Due to their ability of addressing complex optimization tasks, DFO algorithms have achieved many impressive applications in automatic machine learning (Snoek et al., 2012), reinforcement learning (Salimans et al., 2017; Hu et al., 2017), objective detection (Zhang et al., 2015b), etc.

Approach

2 Black-Box Tuning

Note that directly projecting $\mathbf{z}$ onto the prompt space that is compatible with the PTM is non-trivial. To ease the optimization, we instead optimize the increment of some initial prompt $\mathbf{p}_{0}$. For simplicity, we randomly sample $n$ tokens from the PTM vocabulary as initialization. Thus, our objective becomes

where $\mathcal{Z}$ is the search space. Previous work (Wang et al., 2016; Qian et al., 2016; Letham et al., 2020) in derivative-free optimization usually sets each entry in the random matrix $\mathbf{A}$ by sampling from some normal distribution. However, this sampling strategy does not perform well in our scenario. Instead, we set values of the random matrix $\mathbf{A}$ by sampling from a uniform distribution adopted in He et al. (2015) (cf. Appendix A for the comparison). We restrict the search space to $\mathcal{Z}=^{d}$.

For hinge loss, we adopt a multi-class extension (Weston & Watkins, 1999),

In this work we set the margin $\gamma=2$. The performances of using cross entropy, hinge loss, and negative accuracy are compared in Figure 3.

3 The CMA Evolution Strategy

As demonstrated in Aghajanyan et al. (2021), the intrinsic dimensionality of PTMs like RoBERTaLARGE on various tasks can be hundreds. To handle optimization of such scale, we adopt the CMA-ES (Covariance Matrix Adaptation Evolution Strategy) (Hansen & Ostermeier, 2001; Hansen et al., 2003), which is a widely used evolutionary algorithm for non-convex black-box optimization in continuous domain.

In particular, CMA-ES maintains a parameterized search distribution model, i.e., multivariate normal distribution. In each iteration, CMA-ES samples a population of new query solutions (also referred to as individuals or offspring) from the multivariate normal distribution model

4 Pre-Training Prompt Embedding

Considering that sentence-pair tasks can share the same template and label words, as shown in Table 1, we can pre-train a prompt embedding $\mathbf{p}_{0}$ on some publicly available NLI task (in our experiments we use the MNLI (Williams et al., 2018) training set) for a better initialization. For other classification tasks we set $\mathbf{p}_{0}$ as word embeddings randomly drawn from the vocabulary of RoBERTaLARGE.

Experiments

We conduct experiments on several common language understanding tasks including sentiment analysis, topic classification, natural language inference (NLI), and paraphrase. For sentiment analysis, we choose SST-2 (Socher et al., 2013) and Yelp polarity (Zhang et al., 2015a). For topic classification, we choose AG’s News and DBPedia (Zhang et al., 2015a). For NLI, we choose SNLI (Bowman et al., 2015) and RTE (Wang et al., 2019). For paraphrase, we choose MRPC (Dolan & Brockett, 2005). The statistics, manual templates and label words of these datasets are shown in Table 1.

Few-Shot Setting.

For a broad range of users, the amount of labeled data can be limited, in which case they can resort to the deployed large PTMs due to their great power of few-shot learning (Brown et al., 2020). Hence, in this paper we conduct experiments in the few-shot setting. We randomly select $k$ samples for each class to construct a $k$-shot training set $\mathcal{D}_{\text{train}}$, and compose a development set $\mathcal{D}_{\text{dev}}$ by randomly drawing another $k$ samples from the original training set and ensure that $|\mathcal{D}_{\text{train}}|=|\mathcal{D}_{\text{dev}}|$ to simulate the true few-shot learning setting (Perez et al., 2021). Following Zhang et al. (2021a), Gao et al. (2021), and Gu et al. (2021), we use the original development sets as the test sets. For datasets without development sets, we use the original test sets. Hence, in our experiments $|\mathcal{D}_{\text{test}}|\gg|\mathcal{D}_{\text{train}}|=|\mathcal{D}_{\text{dev}}|$.

Backbone Model.

We choose RoBERTaLARGE (Liu et al., 2019) as our backbone model because: (1) We mainly focus on language understanding tasks; (2) Aghajanyan et al. (2021) have demonstrated that RoBERTaLARGE has a very small intrinsic dimensionality (about hundreds) on many tasks. It is worth noting that generative PTMs such as GPT (Brown et al., 2020), T5 (Raffel et al., 2020) and BART (Lewis et al., 2020) are also compatible with our framework if we convert downstream tasks into a unified text-to-text format. We leave for future work the applications of generative PTMs.

Baselines.

We compare our proposed black-box tuning with two kinds of methods: gradient-based methods and gradient-free methods. For gradient-based methods, we consider three baselines: (1) Prompt Tuning: Following Lester et al. (2021), we only train the continuous prompts prepended to the input texts while keeping the PTM frozen. We use an Adam optimizer (Kingma & Ba, 2015) with learning rate of 5e-4 and batch size of 16 for 1000 epochs. For fair comparison, we use the same prompt length, manual template, label words, and the same pre-trained prompt embedding for initialization on sentence-pair tasks as black-box tuning. (2) P-Tuning v2 (Liu et al., 2021a) is an improved variant of prompt tuning. Instead of injecting continuous prompts merely into the input layer, P-Tuning v2 prepends and optimizes continuous prompts at every layer of the PTM. We optimize the prompts of length 128 at each layer using an Adam optimizer with learning rate of 5e-4 and batch size of 32 for 2000 epochs. (3) Model Tuning: We fine-tune the entire PTM on each task using an Adam optimizer with learning rate of 1e-5 and batch size of 16 for 200 epochs. For gradient-free methods, we consider three baselines: (1) Manual Prompt: We directly use the templates and label words in Table 1 to conduct zero-shot evaluation. The results of manual prompt can be seen as initial points of our method. (2) In-context Learning: Following Brown et al. (2020), we randomly select up to 32 training samples and concatenate them with the input texts. (3) Feature-based Methods: Feature-based methods (Peters et al., 2019) is also a competitive baseline for LMaaS, where one can request the features encoded by the large PTM and locally train a classifier to accomplish the task of interest. Here we consider two implementations: (a) Feature-MLP: We train a two-layered MLP classifier on the [CLS] representation of the PTM. (b) Feature-BiLSTM: We train a bidirectional LSTM (Hochreiter & Schmidhuber, 1997) on the representations of the sequence of tokens, followed by a linear classifier on the top. For both implementations of feature-based methods, we use an Adam optimizer with learning rate of 3e-4 and batch size of 16 to train the attached classifiers for 1000 epochs. For black-box tuning, we give in Table 2 the default configuration of hyper-parameters used in our experiments. The effect of each hyper-parameter is explored in § 4.3.

2 Results

We first demonstrate the experimental results of black-box tuning and the baselines across 7 datasets in Table 3. The proposed black-box tuning significantly outperforms the other four gradient-free methods. We observe that in-context learning performs even worse than manual prompt on some tasks, and suffers from high variance. That means, in-context learning cannot effectively utilize labeled samples included in the context. Feature-based methods perform slightly better than manual prompt and in-context learning. Meanwhile, Feature-BiLSTM outperforms Feature-MLP due to its advantage of using more informative features. Surprisingly, black-box tuning also outperforms its gradient-based counterparts, namely prompt tuning, p-tuning v2, and model tuning, on average performance of the 7 tasks. Note that the only difference between prompt tuning and black-box tuning is whether we use gradient descent (i.e., Adam optimizer) or DFO algorithm (i.e., CMA-ES). Based on the experimental results, we suspect that gradient-based optimization tends to overfit the small training data while DFO tends to find better solutions due to its exploration mechanism. In addition, we find that model tuning performs much better than prompt tuning and black-box tuning when number of classes is large (e.g., DBPedia). On NLI tasks (i.e., SNLI and RTE), when using pre-trained prompt embedding (§ 3.4), prompt tuning and black-box tuning significantly outperform model tuning, which also confirms the effectiveness of prompt pre-training (Gu et al., 2021) in the context of black-box tuning.

Detailed Comparison.

In the scenario of LMaaS, there are many other factors to be considered. In Table 4 we compare black-box tuning and the baseline methods in terms of deployment efficiency, viability of as-a-service, training time, memory usage on the user side and the server side, and the amount of data to be uploaded and downloaded. Model tuning is not deployment-efficient because it needs to maintain a copy of the entire model for each user. Gradient-based methods cannot make the PTM serve as a service due to the requirement of gradients. Feature-based methods and black-box tuning are suitable for LMaaS. However, feature-based methods cannot achieve competitive results when labeled data is limited. Therefore, among all the considered methods, only black-box tuning can achieve satisfactory performance while maintaining reasonable training time, memory footprint, and network load. Unlike gradient-based methods, in which the optimization cost is proportional to the size of the PTM, the optimization cost of black-box tuning is decoupled from the scale of the PTM, and only relies on the subspace dimensionality. For fair comparison of training time, we perform early stopping for all the compared methods, i.e., we stop learning if the development accuracy does not increase after 1000 steps. All the methods are implemented with PyTorch (Paszke et al., 2019) and experimented on a single NVIDIA GTX 3090 GPU. Note that the process of model inference can be further accelerated via better implementations (e.g., using ONNX and TensorRT). In Table 4 we also report the training time of black-box tuning using ONNX Runtime. Detailed calculation of the amount of data to be uploaded/downloaded can be found in Appendix C.

3 Ablation Study

In this section, we conduct ablation experiments on various hyper-parameters. To control experimental variables, we explore the effect of each hyper-parameter while keeping the other hyper-parameters as default as listed in Table 2. To stablize the experimental results and reduce the variance over different runs, we conduct ablation experiments in 64-shot setting. Each run is performed on the same data split with different random seeds. Experimental results of ablations on loss functions $\mathcal{L}$, subspace dimensionality $d$, and prompt length $L$ are demonstrated in Figure 3. Additional ablation studies on the effect of the random projection $\mathbf{A}$, the effect of the population size $\lambda$, and the ablations in the 16-shot setting are in Appendix A.

For each ablation, we show results under different budget, which is measured by the number of PTM inference API calls. In each API call, one can provide a continuous prompt $\mathbf{p}$ and query the results of the PTM forward computation on a batch of training data. In our few-shot setting, we can put all the training data into one batch, and therefore the objective function to be optimized is deterministic instead of stochastic.

We compare our used derivative-free optimizer, CMA-ES, with a competitive first-order optimizer, Adam (Kingma & Ba, 2015). For fair comparison, we update the continuous prompt using Adam with the gradients over the entire training data (i.e., batch size equals to $|\mathcal{D}_{\text{train}}|$). We use learning rate of 1e-3 for Adam optimizer. As shown in the top row of Figure 3, Adam optimizer achieves faster convergence on both SST-2 and AG’s News due to the gradients it used. On the development sets, Adam performs slight worse than CMA-ES with cross entropy on SST-2 but better on AG’s News. But as demonstrated in Table 3, using Adam optimizer performs worse than CMA-ES on the average performance across seven task test sets.

Loss Functions.

We consider three loss functions: cross entropy, hinge loss, and negative accuracy. As depicted in the top row of Figure 3, cross entropy and hinge loss significantly outperform the negative accuracy. In the few-shot setting, the accuracy as a reward can be sparse, and cannot provide informative directions for optimization. On SST-2 and AG’s News, we obtain that cross entropy performs slightly better than hinge loss.

Subspace Dimensionality.

The subspace of dimensionality $d$ is the space where the optimization actually performs. According to the intrinsic dimensionality found in Aghajanyan et al. (2021), we explore the subspace dimensionality of {100, 200, 500, 1000} within the budget of {2k, 4k, 6k, 8k}. Accordingly, we set population size $\lambda=4+3\log(d)$. As shown in the middle row of Figure 3, the best subspace dimensionality can be different on different tasks ($d=200$ performs the best on SST-2 development set and $d=500$ performs the best on AG’s News development set), which is related to the observation that intrinsic dimensionality varies across different tasks (Aghajanyan et al., 2021). In general, a small subspace (e.g., $d=100$) is hard to cover a good solution, while a large subspace (e.g., $d=1000$) may lead to poor generalization.

Prompt Length.

Prompt length $L$ determines the dimensionality of the original parameter space (in our case $D=L\times 1024$). We evaluate black-box tuning under each budget in {2k, 4k, 6k, 8k} while varying the prompt length in {10, 20, 50, 100}. As shown in the bottom row of Figure 3, shorter prompt confers faster convergence on the training sets but does not yield better generalization on the development sets. $L=50$ achieves the best accuracy on both SST-2 and AG’s News development sets.

Discussion and Future Work

In this section we discuss our proposed method in the context of (1) derivative-free optimization and (2) prompt-based learning, respectively. By drawing comparisons with these two lines of research, we highlight some directions that could improve this work in future.

Our proposed method lies in the same framework of previous work that solves high-dimensional derivative-free optimization problems via random embedding (Wang et al., 2016). In contrast, we set the random embedding $\mathbf{A}$ by sampling from a uniform distribution instead of normal distributions, and use the CMA-ES to perform optimization in the generated subspace. In previous work, the target black-box functions are usually synthetic functions where only a few dimensions can affect the function values, and therefore most of the dimensions are strictly non-effective. In our real-world scenario, the intrinsic dimension can be approximate. In the context of PTMs, a more appropriate substitution for the term intrinsic dimensionality can be $\epsilon$-effective dimensionality (Qian et al., 2016). Considering the relaxation to the intrinsic dimensionality of PTMs, more suitable approaches such as sequential random embedding (Qian et al., 2016) and other more advanced methods of constructing the random projection matrix (Letham et al., 2020) should be explored in future work. Besides, the subspace generated by random projection can be sub-optimal. As demonstrated in Qin et al. (2021), training the projection $\mathbf{A}$ with multi-task supervision can result in better and smaller subspace. Besides, larger PTMs generally have lower intrinsic dimensionalities (Aghajanyan et al., 2021), as a result, we can use smaller subspace and more efficient DFO algorithms such as Bayesian optimization on larger PTMs.

Comparison with Previous Prompt-Based Learning Approaches.

From the perspective of prompt-based learning, our method is similar to prompt-tuning (Lester et al., 2021), where only the continuous prompt prepended to the input text is tuned, so our method also retains the benefits of efficient serving and mixed-task inference. In addition to the continuous prompt, we also insert some hard prompt tokens (e.g., ”It was [MASK]”) in the input text, which has been demonstrated to be effective in previous work (Gu et al., 2021) in the name of hybrid prompt tuning. Different from previous prompt-based learning approaches, our prompt tuning does not require backpropagation and gradient descent. Considering our used templates and label words are hand-crafted without trial-and-error, the performance reported in this paper is just a lower bound. More advanced techniques such as prompt engineering (Gao et al., 2021), label words engineering (Schick et al., 2020; Shin et al., 2020; Hu et al., 2021b), prompt pre-training (Gu et al., 2021), and prompt ensembling (Lester et al., 2021) are orthogonal to this work and therefore can further improve the performance. For simplicity, we do not integrate these methods and leave for future work.

Acknowledgements

The authors would like to thank Yang Yu for the valuable suggestions of the methods and presentation of the paper, and the anonymous reviewers for their constructive comments. This work was supported by the National Key Research and Development Program of China (No. 2020AAA0108702), the National Natural Science Foundation of China (No. 62022027), the major key project of PCL (No. PCL2021A12), and the Natural Science Foundation of Shanghai (No. 21ZR1420300).

References

Appendix A Additional Experimental Results

Population Size.

In each iteration of the CMA-ES, a population of solutions are sampled from a multivariate normal distribution model. The evaluation of the population is then used to update the parameters of the multivariate normal distribution model. Here we study the effect of the population size on SST-2. In our experiments, we sequentially evaluate each solution in a population, and therefore larger population size will result in more API calls given the same CMA-ES iterations. As shown in Figure 5, smaller population size confers faster convergence in terms of number of API calls. We also demonstrate the comparison in terms of the CMA-ES iterations, which can be found in the following section.

Ablation of Subspace Dimensionality and Prompt Length in 16-shot Setting.

In § 4.3, we conduct ablation experiments in the 64-shot setting to reduce the variance over different runs. To keep consistent with the experimental setting in Table 3, we demonstrate in Figure 6 the ablation results on subspace dimensionality and prompt length in the 16-shot setting.

CMA-ES vs. Adam in Subspaces.

In Figure 3, we compare the convergence of prompt tuning (with Adam optimizer) and black-box tuning (with CMA-ES), where Adam performs optimization in the original prompt space ($\mathcal{P}$) while CMA-ES performs in the generated subsapce ($\mathcal{Z}$). Here we also compare the effectiveness and efficiency of Adam and CMA-ES in subspaces. As shown in Figure 7, CMA-ES is more efficient and stable than Adam in low-dimensional subspaces. When the dimensionality of the subsapce becomes large (e.g., $d=1000$), Adam with a appropriate learning rate can perform on par with CMA-ES. Note that CMA-ES does not require back-propagation, so the computation cost of one iteration for CMA-ES and Adam can be very different. For fair comparison, we convert the number of iterations into FLOPs. The FLOPs of one iteration of Adam is estimated to be three times greater than CMA-ES.

Appendix B Parallel Evaluation

If the training data is smaller, or the server allows larger batches, a promising way to improve training efficiency is to use parallel evaluation. That is, we can evaluate the entire population in parallel, as depicted in Figure 8(a). As demonstrated in Figure 8(b), we can achieve 100% accuracy on the SST-2 training set with population size of 20 and 25 in 300 iterations (API calls). In case of the batch size per API call is limited, we can also use asynchronous queries to simulate the parallel evaluation.

Appendix C Estimation of Uploaded/Downloaded Data Size

In this section we describe how we estimate the amount of data to be uploaded and downloaded (Table 4).

For black-box tuning, there are two kinds of data to be uploaded: (1) training samples, and (2) continuous prompt. A training sample is comprised of two parts: input_ids and attention_mask. We can use the unsigned short (representation range: 0$\sim$65535, 2 bytes per value) for input_ids and use the bool type (1 byte per value) for attention_mask. For continuous prompt, which contains hundreds of values, we can use the float type (4 bytes per value) for representation. Take SST-2 16-shot split as an example, the input_ids and attention_mask are in shape of $32\times 47$, where 32 is the batch size and 47 is the maximum sequence length, so there are $\sim$2.9KB data for input_ids and $\sim$1.5KB data for attention_mask. Assume the prompt is 500-dimensional, we need to upload additional $\sim$2KB data for prompt. The data to be downloaded is the output logits of the candidate words, which is a dictionary containing $\mid\mathcal{Y}\mid$ float values. Take SST-2 16-shot split as an example, the size of data to be downloaded is $32\times 2\times 4\text{bytes}=0.25$KB.

For feature-based methods we use similar estimation methods. The data size for upload is the same for Feature-MLP and Feature-BiLSTM. The data to be downloaded for Feature-MLP is the representation of the [CLS] token while the data to be downloaded for Feature-BiLSTM is the representation of all the tokens. Note that this estimation, without any data compression, is an upper bound of the real scenario.