FedOne: Query-Efficient Federated Learning for Black-box Discrete Prompt Learning
Authors: Ganyu Wang
Jinjie Fang
Maxwell Juncheng Yin
Bin Gu
Xi Chen
Boyu Wang
Yi Chang
Charles Ling
Venue: ICML 2025 poster (2025)
Keywords: Federated Learning
Discrete Prompt Learning
Optimization
Query Efficiency
Primary area: optimization->large_scale_parallel_and_distributed

Abstract: Black-Box Discrete Prompt Learning (BDPL) is a prompt-tuning method that optimizes discrete prompts without accessing model parameters or gradients, making the prompt tuning on a cloud-based Large Language Model (LLM) feasible.
Adapting Federated Learning (FL) to BDPL could further enhance prompt tuning performance by leveraging data from diverse sources. 
However, all previous research on federated black-box prompt tuning had neglected the substantial query cost associated with the cloud-based LLM service. 
To address this gap, we conducted a theoretical analysis of query efficiency within the context of federated black-box prompt tuning. Our findings revealed that degrading FedAvg to activate only one client per round, a strategy we called \textit{FedOne}, enabled optimal query efficiency in federated black-box prompt learning. 
Building on this insight, we proposed the FedOne framework, a federated black-box discrete prompt learning method designed to maximize query efficiency when interacting with cloud-based LLMs.
We conducted numerical experiments on various aspects of our framework, demonstrating a significant improvement in query efficiency, which aligns with our theoretical results.

FedOne: Query-Efficient Federated Learning for Black-box Discrete Prompt Learning
Ganyu Wang" !
Jinjie Fang" * Maxwell J. Yin
Bin Gu Xi Chen
Boyu Wang 14 Yi Chang² Charles Ling'
Abstract
representations (Brown et al., 2020; Li & Liang, 2021; Liu et al., 2021; Lester et al.. 2021), categorizing them as white- box approaches. However, when such access is unavailable, black-box prompt tuning becomes essential. This approach focuses on tuning the input prompts without access to the internal processes of the model (Sun et al., 2022; Diao et al., 2022; Deng et al., 2022; Xiao et al., 2023).
Black-Box Discrete Prompt Learning is prompt- tuning method that optimizes discrete prompts without accessing model parameters or gradients, making the prompt tuning on a cloud-based Large Language Model (LLM) feasible. Adapting fed- erated learning to BDPL could further enhance prompt tuning performance by leveraging data from diverse sources, However, all previous re- search on federated black-box prompt tuning had neglected the substantial query cost associated with the cloud-based LLM service. To address this gap, we conducted a theoretical analysis of query efficiency within the context of federated black-box prompt tuning. Our findings revealed that degrading FedAvg to activate only one client per round, a strategy we called FedOne, enabled optimal query efficiency in federated black-box prompt learning. Building this insight, we pro- posed the FedOne framework, federated black- box discrete prompt learning method designed to maximize query efficiency when interacting with cloud-based LLMs. We conducted numerical ex- periments on various aspects of our framework, demonstrating significant improvement query efficiency, which aligns with our theoretical re- sults.
Federated Learning (FL) (McMahan et al., 2017; Li et al., 2020; 2021; Karimireddy et al., 2020; Gu et al., 2020; Mishchenko et al., 2022) has emerged as a promising ap- proach for leveraging decentralized data from multiple clients while preserving privacy. Applying federated learn- ing to prompt tuning offers a valuable opportunity to im- prove client capabilities and enhance model performance. Most federated prompt tuning methods to date have focused white-box scenarios where clients have access to model parameters (Zhao et al., 2023; Zhang et al., 2023). In those approaches, only the trainable parameters (prompts) are trained by the client and shared with the server, significantly reducing both the number of trainable parameters and the communication costs compared to fine-tuning baselines.
However, several practical limitations hinder the applica- bility of federated prompt tuning that relies on white-box access. First, white-box prompt learning is not applicable to closed-source LLM that are accessed via APIs, as these models are not openly shared. In such scenarios, users are restricted interacting with the model through the API end- points without access the internal structure or weights of the LLM. This limitation prevents the application of white- box prompt learning techniques. Second, FL is typically applied in scenarios involving thousands of edge devices, each with limited computational resources. However, white- box prompt learning demands substantial computational power, as it requires devices to perform computation on the entire LLM. These operations are computationally in- tensive, rendering them impractical for edge devices with constrained capabilities. This presents a significant chal- lenge when trying to implement white-box prompt learning in FL. environments, as it can lead to excessive resource demands on the participating devices.
1. Introduction
Prompt tuning has emerged as a vital technique for adapting LLMs (Liu et al., 2019; Brown et al., 2020) to specific tasks without retraining the entire model. Traditionally, many tuning methods require access to the model's intermediate
'Equal contribution 'Westem University, London, Ontario, Canada *Jilin University, Changchun. Jilin, China MMeGill Univer- sity, Montreal, Quebec, Canada 'ector Institute, Toronto, Ontario, Canada. Correspondence to: Bin Gu <jsgubin gmail.com>> Charles Ling <charles. Scharlcs.ling@ere lingslio.ca..... uwo.ca>.
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
In contrast, applying black-box prompt tuning to FL offers several distinct benefits (Lin al., 2023; Zhang et al., 2023;

---

FedOne: Query-Efficient Federated Learning for Black-box Discrete Prompt Learning
Querying the LLM incurs higher costs!
FL Aggregation Server
Cloud-based LLM
FL Aggregation Server
α
á
k
a
Low query efficiency
High query efficiency
Client
Client K
Client
Federated Black-box Prompt Tuning (Others)
FedOne-BDPL (Ours)
Figure 1: Query-Efficienge Comparison of FedOne and Federated BDPL
Che et al., 2023), enhancing both the practicality and ef- fectiveness. First, this approach preserves the privacy of closed-source LLMs by not requiring access their inter- nal model weights architecture. For example, Diao et al. (2022) proposed Black-box Discrete Prompt Learning (BDPL)* which exclusively utilizes discrete prompts as in- puts and optimizes them based solely on the model's output loss. Besides, black-box prompt tuning reduces the com- putational burden on the client, as it eliminates the need for computation on the entire model, thereby enabling par- ticipation from edge devices with limited computational resources. Moreover, the communication costs associated with discrete prompts are lower compared to white-box prompt tuning methods, as the white-box prompt tuning require transmitting large matrices of numerical values.
approach particularly well-suited for scenarios involving limited computational resources, such as mobile devices or IoT systems, where local training of LLMs is impractical.
Formally, this paper makes the following key contributions:
We identify that existing federated black-box prompt tun- ing methods overlook the significant costs associated with querying cloud-bases LLM services.
To address this gap, present the first theoretical anal- ysis of federated BDPL, with a focus on understanding and evaluating the query efficiency when interacting with cloud-based LLMs.
Based on our theoretical result, we introduce the FedOne framework, a novel approach designed to optimize query efficiency in federated black-box prompt tuning by acti- vating only one client per round.
Despite these advantages, the application of black-box prompt tuning in FL still faces two significant unresolved challenges, tempering its overall promise. First, previous research (Lin et al., 2023; Sun et al., 2023) has neglected the substantial cost associated with queries to the LLM cloud service (Figure 1, left). Second, convergence analysis of Federated BDPL for optimizing discrete prompts has not yet been conducted.
2. Method
2.1. Federated Black-box Prompt Learning Framework
In the federated black-box prompt tuning framework, there is one central aggregation server and K clients. Each client, indexed by k, possesses a dataset D* consisting of input sentences & and their corresponding labels Y i.e., D* k y*J. The dataset v contains a total of M input sentences, each represented as wht i.e., T = { { M*
Targeting the above problems, we introduce novel fed- erated learning framework, FedOne, designed optimize query efficiency in federated BDPL. We offer the first con- vergence analysis of federated BDPL in this context and further extend the analysis of the query efficiency towards the cloud-based LLM server. The results demonstrate that by limiting activation single client per round, FedOne achieves optimal query efficiency (Figure right). Our
m=1" Similarly, the corresponding labels yy. comprise Y i.e. M
y -= [ m
Each client generates a discrete sequence of prompt to- kens &² = of .f. ... of from trainable parameter h E R This learnable parameter, a² J, is transmitted to the FL aggregation server for averaging. Details how to generate the discrete prompt th from a and the local train-
'The term "BDPL." is explicitly used to refer to the work by Diao et al. (2022). whereas "black-box prompt tuning" is used to denote the broader research area.
2

---

FedOne: Query-Efficient Federated Learning for Black-box Discrete Prompt Learning
ing of a through interaction with the cloud-based LLM service will be discussed in the next subsection regarding the local black-box prompt learning on the client.
Optimizing the Learnable Parameter o To compute the gradient with respect the learnable parameter a*, we first define the expected loss over the sequence of prompts in Eq. 3. The i-th token of is generated from the vocabulary by sampling the prompt index from the categorical distribution, i.c. of = V[j.], where j ~ C.t(p,)) For brevity, this sampling process is denoted as of ~ p.". We can define the expectation of the loss for the distribution of the prompt as follows:
The server and clients collaboratively solve minimization problem, aiming to reduce global loss function that aggre- gates the local loss functions from the clients. This can be expressed as:
K
M
min 4
((2:V) -
L"
(
wh)
Exprppt [C(0*, wh]]]
M
k=1
where: (T; =
Σ M
1
M+
e ( wm))
(1)
v(
(3)
where L(;; V) represents the global objective function of K
Following the same steps in (Diao et al.. 2022, Eq. (2)), we can estimate the gradient w.r.t. ag by:
the FL, = { {wv |
k=1- C² ) is the local objective function client k. E(5-) denotes the loss function.
Va (itna [c(0=, v²)]
2.2. Black-box Discrete Prompt Learning on the Client
= BgtnGs(a*)
C(0), V at log P(o
(4)
We now discuss the local training process of the client through interactions with the cloud-based L.LM service. In this section, all variables have the superseript k, indicating that they belong to the k-th client. However, the reader can ignore this superscript and treat it standalone training process on single machine.
The j-th component of V log could be explicitly computed as follows (with detailed steps provided in Ap- pendix A.2):
1-
j j=
a log P(o!) V
aats logyist
i i
Generating the Discrete Prompt Sequence th The quence of the discrete prompt & is generated from cabulary V = (V[))) which contains a total of N token options. Each token of in the prompt sequence @² is se- lected from the vocabulary, i.e., &* of of ......... PDt ... "" [. For the i-th token oft the prompt index J is sampled from the categorical distribution p.,
(5)
Then, we employ the mini-batch stochastic variance-reduced policy MB-SVRP) estimator (Diao et al., 2022; Williams, 1992) to reduce the variance of the sampling when com- puting the gradient. This involves sampling the prompt sequence Φ from the distribution p multiple times, with the number of samplings denoted by I. The MB-SVRP estimator is then computed as follows:
i.e., jft ~ Cat(p?). Note that p. .f,, where the element pi,, represents the probability that the token of is selected as Vbj from the vocabulary V.
V Vay (aattaaaa (B*
Directly optimizing the p may cause trouble in the con- vergence analysis as the gradient of the categorical dis- tribution is biased. To address this, we re-parameterize the categorical distribution P using the Humbel-Softtaat technique (Jang al., 2016) and introduce the parameter at [a ...,,, [ as the learnable parameter. The re- parameterization is shown below:
(((g)rr; - Lovo) Vat log ((o
(6)
where lavg + (( and { ( sampled independently from pt = Ga*a The mini-batch Bh, with size B², is sampled from the dataset Ta Note that the clients are unable to directly compute E( B*) their own. They must transmit both the sampled prompt & and the mini-batch B* to the cloud-based LLM service, which then computes the loss E( x BB*) and returns the result. Finally, with the learning rate set to the update of at at the 1-th iteration is expressed as follows:
} are
log(a 6 +
exp
pis
En -=1 exp
Inglat (1
where T > 0 is the temperature parameter, gh. Gumbel(0, 1) is the Gumbel random variable. We denote the SuffellSoftmax function as GS, i.e. p² = G)(a*).
a(.o+1)) = a.,00) - n Vat (a",
(7)
3

---

FedOne: Query-Efficient Federated Learning for Black-box Discrete Prompt Learning
2.3. Algorithm
gradient is unbiased and has bounded variance.
Algorithm outlines the Fed-BDPL framework, which in- tegrates federated averaging with local client training with Gumbel-Softmax--DDPP (GS-BDPL The FL aggregation server randomly selects a subset of clients and broadcasts the trainable parameters to them. Each selected client k then performs local training on the parameters and return the updated parameters a to the server. The local train- ing of the selected client is conducted through black-box prompt learning by querying the cloud-based LLM service, as detailed in Section 2.2. Finallyy the server aggregates the updates by averaging the parameters from all participat- ing clients. This process is iteratively repeated throughout the training. Specifically, in the FedOne framework, the number activated clients is set to 1, as highlighted in the light green box. The reasons behind FedOne's 's high query efficiency on cloud-based LLM services will be formally analyzed in the next section.
Eis [Va (a" (4mmm VatFla* vet) Eggt a vim) - Estt (a w w
(8)
o
(9)
Assumption 3.1 is the basic assumption for solving non- convex optimization problems using stochastic gradient de- scent (Ghadimi & Lan, 2013; Hazan & Kale, 2014; Xu et al., 2019; Liu et al., 2020).
Assumption 3.2. Bounded Loss: At the k-th client, v t E f and gh sampled by p", the loss function I(.,)) is upper bounded by constant G, i.e.
|e(T S
(10)
Assumption 3.2 ensures that the loss value is bounded, pri- marily to regulate the loss during T-sample estimation in stochastic policy gradient, thereby facilitating thcoretical analysis (Ghadimi & Lan, 2013; Zhang et al., 2019; Liu et al., 2022).
Algorithm Fed-BDPL. C' denotes the sampling ratio of the clients. K. represents the number of selected clients, and U is the set of selected clients.
Assumption 3.3. Bounded Clients' Heterogeneity: For client h = 1,... with sampling probability vector q { k= and Vot wr is local gradient of a; w.r.t. all input sentence in client k. We assume that À is the upper bound on the weighted gradient diversity across local objectives, i.e.
1: Server executes:
2: Initialize a
3: for 0.1,.... do
4: FedAvg: K, + max(C'. (C,KK)) 1)
5: FedOne: K. +-1
6: U. t (sampling K, clients)
M(a:; q) 2 Ek=1 glk).
V (a" wA)l D glkl- V (*ta,, w*)
K
7:
for k E U, in parallel do a ta
SA (I)
8:
9:
a + Clientt a*)
10: end for
Assumption 3.3 states that the gradient diversity among clients is bounded. Following Yin el al. (2018) and Haddad- pour et al. (2019), we use gradient diversity as a measure of client heterogeneity and assume an upper bound on it.
11: a K, Exev, a
12: end for
13: Client executes:
function Client Update(k, a
15: for 1,.,, do
3.2. The Convergence of Federated BDPL
16: Re- ne-paaramterize the categorical distribution pa
(S(a*) ) using Eq. 2.
Theorem 3.4. Suppose that assumption 3.1, 3.2 and 3.3 hold, algorithm is used to solve the FedBDPL problem defined in Eq. 1. Let = min { {B',.., B*) where B represents the local mini-batch size for each client. Set asj 2 v > The variance of the variance-reduced policy |C(4* wh
17:
Query the cloud-based LLM server to obtain (C(ghir, (((phir.BB)))
18:
Compute Vat s (Ba),B))) using Eq. 6.
19: af + a. - az ((a)B))))))))))
gradient is given by o²=
- = Exh-as(a*)
20: end for
is L-smooth w.r.t. a where L = nGN(r+1). The learn- ing rate T) < min { ( t). Then, the expected gradient V F V²) of Fed- can be bounded as follows:
21: Return *
72y²
3. Convergence Analysis
1
Va F F(a,, v*)12
3.1. Assumptions
T
Assumption 3.1. Unbiasedness and Bounded Variance of Stochastic Gradient: We assume that the stochastic
4G nT
2(E + 1)no (1 + h.) + 2no

---

FedOne: Query-Efficient Federated Learning for Black-box Discrete Prompt Learning
2(E + 1)no (1 + ) + 2no
100
(12)
The proof of Theorem 3.4 is provided in Appendix A. Corollary 3.5. Convergence Rate of Fed-BDPL: Let v) min LA I 11, achieves a sub-linear convergence rate, i.e.
Validation Accuracy
70
LJ. B = vT and I Tá, Fed-BDPL
60
K. =1
K.
50
T-1
10
1 T VaF D)1 / O(
1
Σ
(13)
40
20
VT
K. 40
30
Corollary 3.6. The Impact of K, (FedOne): Let Qu denote the minimum number of queries submitted to the cloud- based LLM service to achieve an e-solution, formulated as a function of K., ie., (K.). We derive its form in Eq. 45 (in Appendix A.4):
2000
3000
Model Query
Figure 2: Toy Example on the Intuition of FedOne
Multilayer Perceptron (MLP). It includes flattening input layer, fully connected layer with 512 neurons and ReLU activation, a dropout layer with 0.2 dropout rate, and fi- nal fully connected layer that outputs to 10 classes via a Softmax function. As illustrated in Figure 2, utilizing the minimum number of activated clients (FedOne) achieved optimal query efficiency for convergence."
Q.(K.) = 0c(K.)=c CI =c( C2 VK.
(14)
and establish that the minimum of Qe (K.) is achieved when K. < Consequently, Qe(K.) ) a monotonically increasing function within the feasible region of K., for
K, = 1.2...., K. Thus, to minimize query overhead and achieve optimal efficiency, the optimal choice is K, 1.
It is widely held belief that, in traditional federated learn- ing scenarios, increasing the number of participating clients accelerates convergence by leveraging more local updates per round (Li et al., 2019). However, in the context of fed- crated black-box prompt tuning, the number of queries to the LLM server increases linearly with the number of par- ticipating clients. This rise in query numbers outpaces the benefits gained from faster convergence due to increased client participation. As result, FedOne provides a more efficient trade-off by reducing query overhead while still enabling effective model training.
Remark 3.7. The intuition behind Corollary 3.6 is that while increasing the number of activated clients K. leads to sublinear improvement in the convergence rate, it simultanc- ously incurs a linear increase in the number of queries to the cloud-based LLM in Fed-BDPL. As a result, the marginal gains in convergence do not justify the increasing query overhead in the LLM model. A toy experiment in the next section will further illustrate this trade-off.
4. Experiment
4.1. Experiment Setup
The experiment aimed to evaluate the performance Fed- BDPL, analyze various aspects of the framework, and ex- amine the query efficiency advantages of FedOne. The im- plementation is available https: //g::////tt// htt.bbbttttt.tttg/////// com/ BanyuWang/Fedonn Feddne-BDDP.e..
For our experiment, we utilized the GLUE bench- mark (Wang et al., 2018), which includes a wide range of tasks including MNLI (Williams et al., 2018), QQP (Iyer et al., 2017), SST-2 (Socher et al., 2013), MRPC (Dolan Brockett, 2005), CoLA (Warstadt al., 2019), QNLI (Wang et al., 2018), and RTE (Dagan et al., 2005; Haim et al., 2006; Giampiccolo al., 2007; Bentivogli et al., 2009).
A Toy Experiment on the Intuition of FedOne trate the intuition behind FedOne, we began with a toy experiment examining the trade-off between query effi- ciency and the number of activated clients K, in a federated learning setting using the MNIST dataset (LeCun et al., 2010).2 2 The dataset evenly distributed across 100 clients. We train for 2 epochs with learning rate of 0.01 and batch size of 32, varying the number of active clients, i.c., K, E {1, 10, 40). The model for each client is
To illus-
In the baseline experiment within the federated learning framework, we employed 100 clients. In the FedOne frame- work, there was only one client activated per round for training and aggregation. We adopted the k-shot framework from (Perez et al.. 2021). adapting to a federated learning context. Each client received k-shot dataset comprising samples per class.
?A similar experiment the impact of K. using the SST-2 dataset for Federated BDPL. presented in Appendix C.I.
Additional experiments on varying levels of client heterogene- ity are provided in Appendix C.3.
5

---

FedOne: Query-Efficient Federated Learning for Black-box Discrete Prompt Learning
Table 1: The overall performance on the RoBERTa-large. Each trial runs across three random seeds.
Dataset
MNLI
QQP
SST-2
MRPC
CoLAA
QNLI
RTE
Avg.
Manual Prompt
35.91.3
49.8o.9
77.21.1
70.41.
0.60.0
49.21.1
48.20.6
47.33
Context Leurning
37.21.6
50.1o.9
82.82.1
72.1g.3
1.10.4
50.80.5
49.32.3
49.06
FineTTuning
50.81.2
60.81.
86.52.0
78.41a
20.41.9
53.21.8
55.62.
57.96
FedOne- Men0ne-ProompTTningg
41.50.9
66.40.2
77.92.
79.50.5
0.81.1
49.61.0
53.1o.6
52.69
FedOne-P- P-nnning v2
42.76.7
66.70.1
82.90.3
80.60.1
1.01.0
52.4
56.40.4
54.67
FedOne-BBl BBT
41.90.4
66.30.2
76.81.
80.6g.3
2.51.3
51.1o.4
55.31.0
53.50
WedOne-BDPP
41.01.2
66.76.1
80.8 80.8s.o
81.10.1
5.22.4
51.71.4
57.11.
54.80
FedOne-GG--BDPL
41.10.4
66.90.2
80.80.4
81.0p.1
5.31.1
52.1o.s
57.11.1
54.90
The model architecture employed is RoBERTa-large (Liu et al., 2019). The trainable prompts were placed at differ- ent positions in the model depending on the algorithm of the baselines. For the training procedure, we conducted a hyperparameter tuning phase using grid search approach explore learning rates of [3e- 4, ll 4, 3e 5, le 5]. The batch size was set 32, and the optimization algorithm employed was AdamW (Loshchilov& & Hutter, 2017). Fur- ther details about the dataset and evaluation metrics of them are available in Appendix B.1.
4.3. Result
Test Accuracy The performance results were summarized in Table 1, we observed significant variations in the effec- tiveness of different learning approaches when applied to the RoBERTa-large model across various NLP tasks. Tra- ditional fine-tuning methods outperformed both Manual Prompt and In-Context Learning techniques, achieving the highest average score of 37.96 across all datasets. This result underscores the effectiveness of complete model re- training over other methods that involve fewer parameter updates or rely solely on contextual adjustments. Although Manual Prompt performed well on some datasets, its perfor- mance lacks stability. White-box federated prompt tuning methods demonstrate improvements over Manual Prompt and In Context Learning techniques. Generally, the black- box method (BDPL and GS- exhibits performance that is comparable to, or slightly better than, the white-bor box tuning method (PromptTuning and P-Tuning v2).
4.2. Baselines
We evaluated several approaches categorized as standalone and federated learning models. The standalone model base- line includes Manual Prompt Tuning, In-Context Learn- ing (Brown et al., 2020), and Fine-tuning (Diao et al., 2022, Table 7). In the domain of Federated Prompt Tuning for adapted two established white-box
white-box scenarios, prompt tuning methods to federated learning. Specifically, we implemented prompt-tuning (Lester et al., 2021) and prefix-tuning v2 (Liu et al., 2021) across distributed clients. In the prompt tuning approach, a prompt was integrated into the embedding layer of the model for each client. Each client then undertook local training solely on their respec- tive prompt. In prefix-tuning v2, the prompt was utilized across all embedding layers of the model, providing more trainable parameters and enhancing the capability to adapt to downstream tasks. In the federated prompt tuning for the black-box scenario, we adapted the Black-Box Box Tuning (BBT) (Sun et al., 2022) to FedOne, incorporating projec- tion from a low-dimensional vector and the Covariance Matrix Adaptation Evolution Strategy (CMA-ES) into feder- ated blxck-box prompt learning. Each client held a distinct low-dimensional vector, while the projection matrix A was shared among all clients. For every client, the population size of CMA-ES is set to 20, and the dimension of the low- dimensional vector is set to 500, as recommended by (Sun et al., 2022). Finally, we adapted the BDPL (Diao et al., 2022) and Gumbel-Softmax BDPL (GS-BDPL) to the Fed- erated Learning, employing policy gradient methods and Gumbel-Softmau as outlined in Algorithm 1.
Computational Efficiency and Resource Utilization Ta- ble 2 presents the performance metrics for various federated prompt tuning methods, focusing on the computational and communication efficiencies of these methods. We measured the computation time required for model training. Notably, in the white-box method, training occurs on the client side. We only measure the time for forward and backward propa- gation of the local model, along with the time for parameter updates. In the black-box prompt learning method, the computation time for model training includes both the ex- ecution of the black-box algorithm and the wait time for responses from the LLM model. Regarding GPU memory usage, white-box methods require substantial computational resources, such as GPUs, which may not be feasible in FL environments. In contrast. black-box methods signifi- cantly reduce GPU memory consumption. A comparison between the FedOne framework and the federated frame- work with 10 activated clients demonstrates that FedOne reduces both computation time and FL server communica- tion costs compared with traditional FL. Within black-bor box prompt learning. although BBT has a slightly smaller train- able parameter size, requires significantly longer training
6

---

FedOne: Query-Efficient Federated Learning for Black-box Discrete Prompt Learning
Table 2: Evaluation of computational efficiency and resource utilization
FL. Server
Per Client Trainable Parameter (MB)
Baseline
Comp. Time for Training (8)
Comm. Cost
FL. Server Queries
I.I. Server Query
Per Client Loaded
GPU Mcmory (MB)
(MB)
Red-Prompt-Tunine
224.26
156.25
1000
7.8 10
3564 (Model, Grad., Prompt)
Fed-P-Tuning v2
276.23
11417.20
1000
5.7
3636 (Model, Grad., Prompt)
Fed-BBT
24501.83
3.81
1000
200000
19 10
1.90 10
(Prompt Only)
Fed-BDPL.
2407.05
30.52
1000
20000
1.5 10
1.52 10 (Prompi Only)
Fod-GS-BDPL
2400.60
30.52
1000
20000
1.5 x 10-2
1.52 x 10-2 (Prompt Only)
FedOne- PedOOne-rrumpt---
16,99
15.63
100
7.8 10"2
3564 (Model, Grad., Prompt)
FedOne--PTTnnin v2
19.95
1141.72
100
5.7
3656 (Model, Grad., Prompt)
FedOne-BBT
5036.15
0.38
100
20000
1.9 10-3
1.90 x 10
(Prompt Only)
FedOne-BDPL
234.92
3.05
100
2000
1.5 10
1.52 10 2 (Prompt Only)
FedOne-CIS- CS-BDPP.
234.73
3.05
100
2000
1.5 10-2
1.52 10
(Prompi Only)
Table 3: Federated discrete black-box prompt learning on GPT-3.5 Turbo
MNLI
QQP
SST-2
MRPC
CoLA
QNLI
RTE
Avg.
No Prompt
14.05p.00
68.04a.on
91.35a.00
79.620.00
36.01a.00
56,22
72.20o.o
59.64
Prompt w/o. Training
9.171.31
62.944.94
79.472.71
79.881.94
25.531.10
56.694.76
72.162.51
54.41
FedOne-BDD
13. 13.67o.17
68. 253.05
87.773.82
81.690.70
32. 22.16
70.58
77. 77.62, 1.62
61.67
FedOne-GS-BDPL.
16.00
69.92 29.922.85
92.58
82.93p.07
36.20
72.05
80.33
64.28
time, making it less practical. In contrast, BDPL achieves a more balanced trade-off between computational efficiency and training performance.
no" to the end of the input sentence. This allowed us to retrieve the top probabilities for all class label tokens ("yes", "no") in the top 20 probability. and use the probability of the target token as the logit output, for the following procedure.
The advantage of black-box prompt learning lies primarily in its reduced communication costs and the efficiency of the trainable parameter size, well in avoiding the need to store and train the entire LLM on the client. As illustrated in the table, the federated black-box prompt tuning method features a significantly smaller parameter size and eliminates the GPU requirement on the client. This allows devices with limited computational resources, such as edge devices, to participate in the federated prompt learning process.
The results were presented in table 3, indicating that GPT- 3.5 Turbo achieves certain level of performance without any prompts. Introducing a random, untrained prompt led to a performance decline, while prompt tuning significantly improved results, surpassing the no- no-prompt baseline. Ad- ditionally, the table highlights that the GS-BDPL method consistently outperforms other black-box approaches. In summary, this method enables prompt tuning in Federated Learning with minimal computational resources while lever- aging advanced cloud-based LLMs.
4.4. Experiment on Real-world Cloud-based LLM
We implemented the Fed-BDPL framework using GPT-3.5 Turbo, a widely recognized and powerful closed-source language model. We leveraged the OpenAl API (OpenAI, 2024) to enable individual clients to conduct local training. In this implementation of the federated black-box prompt learning, clients sent prompts and input sentences to GPT- 3.5, which returns the logarithm of the token probabilities at each position. key challenge was that OpenAl API only provides probabilities for the top 20 tokens for each position. Consequently, we needed transform the predic- tions on these tokens into the categorical prediction of the input sentence, instead of using the straightforward model output as we did in the RoBERTa experiment. To solve this problem, we appended a template question at the end of the input sentence to query the target label token. For example, in the QQP task, we added the phrase "equivalent? yes or
5. Related Works
5.1. White-box and Black-box Prompt Tuning
Prompt tuning is a technique for adapting LLM down- stream tasks. It tailors the model's responses to specific tasks styles without requiring the retraining of the entire model. In white-box prompt tuning, the learner is granted full access to the LLM, allowing them to modify and ac- cess intermediate results of the model and acquire the gra- dient. Li et al. (2021) and Lester et al. (2021) proposed a lightweight and modular alternative to full model fine-tuning for natural language generation tasks, which optimizes a sequence of continuous soft prompts, prepend in the em- bedding layers of the LLM. Liu et al. (2021) proposed the P-tuning v2. Instead of only applying the prompt in the input
7

---

FedOne: Query-Efficient Federated Learning for Black-box Discrete Prompt Learning
layer as used in Li et al. (2021), they adapt trainable param- eters on all layers' inputs, which can effectively match the performance of fine-tuning across wide range of models.
lacked formal theoretical convergence guarantees. As a result, researchers have made significant efforts to estab- lish and demonstrate its convergence (Zhou & Cong, 2017; Stich, 2018).
In situations where the learner cannot access the intermedi- ate result of the LLM model, the learner has to use a black- box prompt tuning method. In the black-box prompt tuning, the learner can only query the output of the LLM with the input of the model. Most of the research assumes the input is at the soft prompt layer of the LLM (Sun et al., 2022: Chen et al., 2023). Others research use the discrete prompt which is concrete with the input text, which is more portable, and is usable for any -boud LLM API (Diao et al., 2022). efficient
Partial client activation is a key area of research in federated learning and has gained significant attention due to its im- pact on improving convergence rates and system efficiency, Stich et al. (2018) shows that in the convex case, increas- ing the number of activated clients significantly improves convergence rates in federated learning with independent and identically distributed (IID) data, achieving a linear speed-up. Li et al. (2019) extended the understanding of federated learning by analyzing the convergence of the Fe- dAvg algorithm, under the convex case. They demonstrate that under the non-IlD setting, the convergence rate has a weak dependence on the number of activated clients. This implies that FedAvg cannot achieve linear speedup in this scenario, allowing for a lower participation ratio to mitigate the straggler effect without compromising convergence.
Xiao et al. (2023) presented a transfer learning method that adapts large foundation mod- els specific tasks. This method does not require access to the full model compromise data privacy. It utilizes lightweight adapter and a compressed emulator for model tuning. Chen et al. (2023) introduces an efficient method for optimizing instructions for black-box LLMs using Bayesian optimization of soft prompts. This approach significantly improves LLM performance across a variety of tasks with- out requiring direct access to the model's internals. Deng et al. (2022) proposed efficient method to optimize discrete text prompts using reinforcement learning, demonstrating superior performance compared to other prompt optimiza- tion techniques across a variety of tasks. Sun et al. (2022) proposed black-bos box tuning (BBT), a method that optimizes continuous prompts by optimizing a lower-dimensional vec- tor and projecting them to the prompt searching space. They use the Covariance Matrix Adaptation Evolution Strategy (CMA-ES) for optimizing the vector. Diao et al. (2022) introduced BDPL which optimizes the discrete prompt with the policy gradient method.
5.3. Federated Prompt Tuning
Applying federated learning to prompt tuning can enhance the model by incorporating additional data, This approach leverages distributed datasets to improve model performance while adhering to data privacy. To apply white-box prompt tuning in FL, each client maintains the entire model but trains only the prompt parameters. These parameters then shared and aggregated across clients (Zhao et al., 2023; Zhang et al., 2023; Che et al., 2023). However, this method assumes white-box access to LLM, which is impractical for closed-source LLMs. Consequently, black-box prompt learning has been adapted for FL to address these limita- tions (Lin et al., 2023; Sun et al., 2023). Lin et al. (2023), applied the BDPL (Diao et al., 2022) to the FL, where the client can train the probability matrix for the discrete prompt via querying the cloud- based LLM API. Sun et al. (2023) applied the BBT to FL. In this approach, clients train only low-dimensional vectors using CMA-ES via querying the cloud-based LLM API.
The black-box prompt tuning method is versatile and appli- cable to various tasks and models without model-specific modifications. However, its major drawback is compu- tational inefficiency, requiring multiple forward passes through the model, which leads to high costs and ex- tended training times. Additionally, the convergence of the derivation-free optimization method is often slow.
For federated prompt tuning, most existing research has fo- cused conventional issues in FI., such as data heterogene- ity (Zhao et al., 2023), privacy (Zhang et al., 2023), security (Zhao et al., 2023), and client computation-com communication efficiency (Lin et al., 2023; Sun et al., 2023). However, the query efficiency of federated black-box prompt tuning, a novel challenge arising from deploying black-box prompt tuning via cloud-based APIs, remains unexplored.
5.2. Federated Learning
Federated learning (McMahan et al., 2017: Karimireddy et al., 2020; Li et al., 2020; 2021; Marfoq et al., 2022: Mishchenko et al., 2022; Chen et al., 2020; Wang et al., 2023; Zhang et al., 2024; Wang et al., 2024; 2025), first introduced by Memahan et al. (2017), is a paradigm that enables devices to collaboratively train shared predictive model by locally aggregating updates. In this framework, each client maintains copy of the model for local train- ing, and the server selects a subset of clients in each round for aggregation. Since the introduction of FedAvg, it has
6. Discussions and Future Works
Heterogeneous Clients Theorem 3.4 and Corollary 3.6 explicitly consider bounded client heterogeneity, and the
8

---

FedOne: Query-Efficient Federated Learning for Black-box Discrete Prompt Learning
result that K, achieves optimal query cost (FedOne) remains valid under the heterogeneous case. This is because the core intuition behind FedOne continues to hold: the query cost to the LLM increases linearly with the number of activated clients, while increasing K. is not able to provide a linear speedup in convergence (Haddadpour & Mahdavi, 2019; Li et al., 2019). However, the trade-off is that fewer activated clients per round lead slower convergence rate. Besides, we further include additional experiment in Ap- pendix C.3 to evaluate FedOne's performance under varying levels of client heterogeneity, demonstrating consistency with the theoretical results.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
References
Bentivogli, L.., Clark, P., Dagan, I., and Giampiccolo, D. The fifth pascal recognizing textual entailment challenge. In TAC, 2009.
Brown, T., Mann, B.,, Ryder, N., Subbiah, M., Kaplan, J. D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., et al. Language models are few-shot learners. Advances in neural information processing systems, 33:
Cost-aware Client Participation FL In conventional FL, increasing the number of participating clients typically improves per-round convergence and is generally considered beneficial. However, when the per-client cost (queries black-box oracle, communication, computation, encryption, etc.) becomes significant, new trade-off arises between convergence rate and the overall system cost. This trade-off becomes particularly important as FL systems transition from small, local models to interactions with lcage-scale models, such as LLMs. Consequently, rising per-client costs have motivated the development of strategies like FedOne, which prioritize cost-efficiency by limiting client participa- tion. Importantly, FedOne is not limited to scenarios involv- ing cloud-based LLM query costs; it is broadly applicable to any FL setting where per-client costs are non-negligible. Exploring the general balance between convergence and system-level efficiency remains an important direction for future work.
1877-1901, 2020.
Che, T., Liu. J., Zhou, Y., Ren. J., Zhou, J., Sheng, V. S.. Dai, H., and Dou, D. Federated learning of large lan- guage models with parameter-efficient prompt tuning and adaptive optimization. arXiv preprint arXiv:2310.15080 2023.
Chen, L., Chen, J., Goldstein, T., Huang, H., and Zhou, T. Instructzero: Efficient instruction optimization for black-hox large language models. arXiv preprint 1xXi::300003082. 2023.
Chen, T., Jin, X., Sun, Y., and Yin, W. Vafi: method of vertical asynchronous federated learning. arXiv preprint arXiv:2007.06081, 2020.
Dagan, I., Glickman, O., and Magnini, B. The pascal recog- nising textual entailment challenge. In Machine Learning Challenges Workshop, pp. 177-190, Springer, 2005.
7. Conclusion
We identified that previous research on federated black-box prompt tuning had overlooked the significant query costs associated with cloud-based LLM services. To address this issue, we conducted theoretical analysis of query effi- ciency in the context of federated black-box prompt tuning. revealing the relationship between query efficiency and the number of activated clients. Based on our theoretical result, we propose the FedOne framework, which achieves optimal query efficiency with respect to the number of activated clients. We conducted extensive numerical experiments on various aspects of its performance and further validated its advantage through real-world experiments using GPT-3.55.
Deng, M., Wang, J., Hsieh, C.-P., Wang, Y., Guo, H., Shu, T., Song, M., Xing, E. P., and Hu, Z. Riprompt: Optimizing discrete text prompts with reinforcement learning. arXiv preprint arXiv: 12548, 2022.
Diao, S., Huang, Z., Xu, R., Li, X., Lin, Y., Zhou, X., and Zhang, T. Black-box prompt learning for pre-trained lan- guage models. arXiv preprint arXiv:2201.0853/1 2022.
Dolan, W. B. and Brockett, C. Automatically construct- ing a corpus of sentential paraphrases. In Proceedings of the Third International Workshop on Paraphrasing (IWP200S). 2005. URL httpa: https////caatthoogggo org org/105-5002.
Acknowledgments
This work has been supported by the Natural Sciences and Engineering Research Council of Canada (NSERC), Dis- covery Grants program.
Ghadimi, S. and Lan, G. Stochastic first-and zeroth-orde methods for nonconvex stochastic programming. SIAM journal on optimization, 23(4):2341-236) 2013.

---

FedOne: Query-Efficient Federated Learning for Black-box Discrete Prompt Learning
Giampiccolo, D., Magnini, B., Dagan, and Dolan, B. The third PASCAL recognizing textual entailment challenge. In Proceedings of the ACL-PASCAL Workshop Textual Entailment and Paraphrasing, pp. 1-9, Prague, 2007. Association for Computational Linguistics. httst // //aclanthology org/ 1907-14011
normalization. In International Conference on Learning
Representations, 2021. URL http:::://///..... /ttp:://///peeeeieeeee Tttp/pddFiid-YYEEE0n
Li, X. L. and Liang. P. Prefix-tuning: Optimizing continuous prompts for generation. arXiv preprint arX1v:2101.00110, 2021.
Gu, B., Xu, A., and Deng, C. heng huang. 2020. privacy- preserving asynchronous federated learning algorithms for multi-pann party vertically collaborative learning. arXiv preprint arXiv:2008.00 06233, 2020.
Lin, T., Kong, L., Stich, S. U., and Jaggi, M. Ensemble distillation for robust model fusion in federated learning. Advances in neural information processing systems, 33: 2351-2363, 2020.
Haddadpour, and Mahdavi, M. On the convergence of lo- cal descent methods in federated learning. arXiv preprint arXiv: 1910. 14425, 2019.
Lin, Z., Sun, Y., Shi, Y., Wang, X., Huang, L., Shen, L., and Tao, D. Efficient federated prompt tuning for black-box large pre-trained models. arXiv preprint arXiv:2310.03122 2023.
Haim, R. B., Dagan, I., Dolan, B., Ferro, L., Giampiccolo, D., Magnini, B., and Szpektor, The second paseal recog- nising textual entailment challenge. In Proceedings of the Second PASCAL Challenges Workshop Recognising Textual Entailment, volume 7, 2006.
Liu, M., Zhuang. Z., Lei, Y., and Liao, C. A communication efficient distributed gradient clipping algorithm for train- ing deep neural networks. Advances in Neural Informa- tion Processing Systems, 35:26204-2622 2022.
Hazan, E. and Kale, S. Beyond the regret minimization barrier: optimal algorithms for stochastic strongly-conver optimization. The Journal of Machine Learning Research, 15(1):2489-23) 25122 2014.
Liu, X., Ji, K., Fu, Y., Tam, W. L., Du, Z., Yang, Z., and Tang, J. P-tuning v2: Prompt tuning can be comparable to fine-tuning universally across scales and tasks. arXiv preprint arXiv:2110.07602, 2021.
Iyer, S., Dandekar, N., Csernai, K., et al. First quora dataset release: Question pairs. data, quora. com, 2017.
Liu, Y., Ott, M., Goyal, N., Du, J., Joshi, M., Chen, D., Levy, O., Lewis, M., Zettlemoyer, L., and Stoyanov, V. Roberta: A robustly optimized BERT pretraining approach. arXiv preprint arXiv: 1rXiv:1977.11692 2019.
Jang. E., Gu, S., and Poole, B. rameterization with gumbel-softmax. arXiv preprint 1444 2016.
Categorical repa-
Liu, Y., Gao, Y., and Yin, W. An improved analysis of stochastic gradient descent with momentum. Advances in Neural Information Processing Systems, 33:18261- 18271, 2020.
Karimireddy, S. P., Kale, S., Mohri, M., Reddi, S., Stich, S., and Suresh, A. T. Scaffold: Stochastic controlled averag- ing for federated learning. In International Conference on Machine Learning, pp. 5132-5143, PMLR, 2020.
Loshchilov, and Hutter, F. Decoupled weight decay regu- larization. arXiv preprini
2017.
LeCun, Y., Cortes, C., and Burges, C. Mnist hand- written digit database. ATT Labs [Online]. Available: 2, 2010.
Marfoq, O., Neglia, G., Vidal, R., and Kameni, L. Per- sonalized federated learning through local memorization. In International Conference on Machine Learning, pp. 15070-15092. PMLR, 2022.
Lester, B., Al-Rfou, R., and Constant, N. The power of scale for parameter-efffcient prompt tuning. arXiv preprint arXiv:2104.08611, 2021.
McMahan, B., Moore, E., Ramage. D., Hampson, S., and y Arcas, B. A. Communication-efiin networks from decentralized data. In Artificial intelli- gence and statistics, pp. 1273-1282. PMLR, 2017.
learning of deep
Li, T., Sahu, A. K., Zaheer, M., Sanjabi, M., Talwalkar, A., and Smith, V. Federated optimization in heterogeneous networks. Proceedings of Machine Learning and Systems, 2:429-4500 450, 2020.
Mishchenko, K., Malinovsky, G., Stich, S., and Richtárik. P. Proxskip: Yes! local gradient steps provably lead to com- munication acceleration! finally! In International Con- ference on Machine Learning, pp. 15750-15769, PMLR, 2022.
X., Huang, K., Yang, W., Wang, S., and Zhang, Z. On the convergence of FedAvg non-iid data. arXiv preprint 1907.0220 2019.
Li, X., Jiang, M., Zhang, X., Kamp, M., and Dou, Q. FedBN: Federated learning on non-llI) features via local batch
Nesterov, Y. et al. Lectures on convex optimization, volume 137. Springer, 2018
10

---

FedOne: Query-Efficient Federated Learning for Black-box Discrete Prompt Learning
OpenAl. Openai api, 2024. URL htttps://opend Accessed: 2024-09-30.
Warstadt, A., Singh, A., and Bowman, S. R. Neural network acceptability judgments. Transactions of the Association for Computational Linguistics, 7:625-641, 2019, doi: 10. 1 1622/aal URL https: http::::/aalaanhooooyy... o arg/019-1044
Perez, E., Kiela, D., and Cho, K. True few-shot learning with language models. Advances in neural information processing systems, 34:1 1054-11070) 2021.
Williams, A., Nangia, N., and Bowman, S. A broad- coverage challenge corpus for sentence understanding through inference. In Proceedings of the 2018 Con- ference of the North American Chapter of the Associ- ation for Computational Linguistics: Human Language Technologies, Volume (Long Papers), pp. 1112-1122, New Orleans, Louisiana, 2018. Association for Compu- tational Linguistics. doi: 11L11865//1/NN18111 URL https: httaaaaaaanttttooooocccaaaa org/Ni8 1
Reddi, S. J., Hefny, A., Sra, S., Poczos, B., and Smola, A. Stochastic variance reduction for nonconvex optimization. In Balcan, M. F. and Weinberger, K. Q. (eds.), Proceed- ings The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learn- ing Research, pp. 314-323, New York, New York, USA, 20-22 Jun 2016. PMLR.
Socher, R., Perelygin, A., Wu, J., Chuang, J., Manning, C. D., Ng, A., and Potts, C. Recursive deep models for semantic compositionality over sentiment treebank. In Proceedings of the 2013 Conference on Empirical Meth- ods in Natural Language Processing, pp. 1631-1642, Seattle, Washington, USA, 2013. Association for Compu- tational Linguistics. URL https://///// /ttte::://aacaaatii haclaattoaatooyy.... org/D13 11011000
Williams, R. J. Simple statistical gradient-followiin algo- rithms for connectionist reinforcement learning. Machine learning, 8:229-255 1992.
Xiao, G., Lin, J., and Han, S. Offsite-tuning: Transfer learn- ing without full model. arXiv preprint -XXv:2302.048700 2023.
Stich, S. U. Local sgd converges fast and communicates little. arXiv preprint arXiv:1805.0976.. 2018.
Xu, Y., Jin, R., and Yang, T. Non-asymptotic analysis of stochastic methods for non-smooth non-convex regular- ized problems. Advances in Neural Information Process- ing Systems, 32, 2019.
Sun, J. Xu, Z., Yin, H., Yang, D., Xu, D., Chen, Y., and Roth, H. R. Fedbpt: Efficient federated black-box prompt tuning for large language models. arXiv preprint arXiv:2310.01-00 230.01166, 2023.
Yin, D., Pananjady, A., Lam, M., Papailiopoulos, D., Ram- chandran, K., and Bartlett, P. Gradient diversity: a key ingredient for scalable distributed learning. In Storkey, A. and Perez-Cruz, F. (eds.), Proceedings of the Twenty- First International Conference on Artificial Intelligence and Statistics, volume 84 of Proceedings of Machine Learn- ing Reseurch, pp. 1998-2007. PMLR, 09-11 Apr 2018. URL pett::::/proceeeeee yinl Ba hhmml.
Sun, T., Shao, Y., Qian, H., Huang, X., and Qiu, X. Black- box tuning for geguag--oddella---servivii In Inter- national Conference on Machine Learning, pp. 20841- 20855. PMLR, 2022.
Wang, A., Singh, A., Michael, J., Hill, F., Levy, O., and Bowman, S. R. Glue: A multi-task benchmark and anal- ysis platform for natural language understanding. arXiv preprint arXiv:1804. 804.007611 2018
mlr www.:mmw....................eeee pr8ss/v84/
Yurochkin, M., Agarwal, M., Ghosh, S., Greenewald, K., Hoang, N., and Khazaeni, Y. Bayesian nonparametric federated learning of neural networks. In International conference on machine learning, pp. 7252-7261. PMLR, 2019.
Wang, G., Gu, B., Zhang, Q., Li, X., Wang, B., and Ling, C. A unified solution for privacy and communication efficiency in vertical federated learning. In -hireth-eeenth Conference on Neural Information Processing Systems, 2023.
Zhang, J., He, T., Sra, S., and Jadbabaie, A. Why gradient clipping accelerates training: A theoretical justification for adaptivity. In International Conference on Learning Representations, 2019.
Wang, G., Zhang, Q., Li, X., Wang, B., Gu, B., and Ling, C. X. Secure and fast asynchronous vertical federated learning via cascaded hybrid optimization. Machine Learning, 1 113())66413 64511 2024.
Zhang, K., Wang, G., Li, H., Wang, Y., Chen, H., and Gu, B. Asynchronous vertical federated learning for kernelized auc maximization. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 4244 4255, 2024.
Wang, G., Wang, B., Gu, B., and Ling, C. Event-driven online vertical federated learning. In Thirteenth Interna- tional Conference on Learning Representations, 2025.

---

FedOne: Query-Efficient Federated Learning for Black-box Discrete Prompt Learning
Zhang, Z.,, Yang, Y., Dai, Y., Wang, Q.. Yu, Y., Qu, L., and Xu, Z. FedPETuning: When federated learning meets the parameter-efficient tuning methods of pre-trained lan- guage models. In Annual Meeting of the Association of Computational Linguistics 2023, pp. 9963-9977. Associ- ation for Computational Linguistics (ACL), 2023.
Zhao, H., Du, W. Li, F., Li, P., and Liu, G. Fedprompt: Communication-effe -efficcent and privacy-pres preserving prompt tuning in federated learning. In ICASSP 2023-2023 IEEE International Conference on Acoustics, Speech and Sig- nal Processing (ICASSP), pp. 1-5. IEEE, 2023.
Zhou, F. and Cong, G. On the convergence properties of a k-step averaging stochastic gradient descent al- gorithm for nonconvex optimization. arXiv preprint arX1v:1708.01012, 2017.
12

---

FedOne: Query-Efficient Federated Learning for Black-box Discrete Prompt Learning
A. Convergence Analysis
A.I. Notations and Omitted Mathematical Steps
1 0 ... T
Number of global iterations
..... E
Number of local iterations
8 O, O,... S
Number of client-server interactions
||-1
The default 2-norm in this paper Categorical distribution function
Cat(.)
6 pi
Abbreviation for j: Cat(p:)
D
Dataset for client
As
{ jim m=1
Input sentence
y = vm M
The category corresponding to the input sentence
K m=1
The number of all clients
q = {q M1] K K.
Probability of each client being selected
kml
The number selected clients.
The set of selected clients.
a a i=1
Gumbel-Softmax parameters for k-th client Average of *
a K. 2keu a
t of
Prompt
Vocabulary list of total N tokens choice
p = I
The probability distribution over the N token indexes.
V P (s))
The local full gradient of the client & (17)
V at ((.))
The local stochastic mini-batch gradient of the client & (16)
(())
The local stochastic mini-batch variance- reduced policy gradient of the client & (6)
The average full gradient of the client group Ue (31)
(tf"()))
The average stochastic mini-batch gradient of the client group Ug (32)
()))
The average stochastic mini-batch variance-reduced policy gradient of the client group U4 (33)
V a F(a",
The average full gradient of all K clients for {a*) K
k= ) }
(30)
a. F(a,,)
The average full gradient of all K clients for a (29)
Table 4: Notation Table
For i 1,..., n, we define the stochastic gradient, stochastic mini-batch gradient and full gradient with respect to at as
following:
V (a w
def Bagh.
at
[ (()
(15)
V (a daf
V a B
E Bothassaa wh
(16)
th EB
V TatF w def
Vat
Σ
E v
(17)
M
1ot Eok
A.2. The Omitted Derivative Process for Eq.
log(at light
alog
exp
a
log
datt
dat'
1 + tt
Σm" exp
13

---

FedOne: Query-Efficient Federated Learning for Black-box Discrete Prompt Learning
loxta 2.t 1.
lapto 1lto
log(at,))
Σim
exp
Pi.t
log(n ,)
Oas
log(ak 3to 113f ti
exp
i
loseca 2
>n exp
(18)
According to the derivation rule of the Softmax function, when j :/:
Op
(1- px
(1- phatt -r.st
(19)
Da
Ta
when j - :
0p 1
vhis Tok
(-piis p/..)
(20)
dat Toitt
A.3. Lemmas
The following lemma shows that the unbiasedness and bounded variance of variance-reduced policy gradient. This is important for bounding the randomness introduced by prompt sampling.
Lemma A.1. Unbiasedness and bounded variance of variance-reduced policy gradient: At the k-th client, V thth E w
r .I denotes the r-th sampling of t from p w.n.t {ophrr]_ ) ~p" p GS(a"), as, v 0 for I...., and j 1,.,, N, >> is the temperature parameter, and o 80 P then the variance-reduced policy gradient
unbiased and bounded by:
Eqptir sa v/n)
Vaz S wb))
(21)
02 E E(at Fat (at w E Eiotr paatt((" w/th ]1y]
(22)
1
Proof. We abbreviate poo E( as Egas.r
The unbiasedness of variance-reduced policy gradient:
(V x (at vv
E Epo
= =B
C(pkir, ((
Σ
cloktre w/th w
Vat log P(otti)
m=
T-1 1
= =E(oro
L( 2ith -
Σ
L( w/
Vat log P(ater))
w
= -(
7 Σ
(C(okir w/)) Vaz log P(ot.T)
14

---

FedOne: Query-Efficient Federated Learning for Black-box Discrete Prompt Learning
Σ
Σ
c( vm)
Va: log P(ottr)
T
w = 1 w + r
1
(C(etirr whtt) Vaz log :r
E Expt.rr
Σ
En L(g sl
Eep Vax log P))
1-1
w
W
+ r
Es
(((D w/mi) Vot log P(()
1
Σ
[C(Tption w/t ]]
Ear (vat log P(ottir)) }
I
--1
w = 1
w +
Vag VatP(o P(
Vot
Σ
Egg
1 r=1
W 1
W + r
1 Σ
(VatPiof
V a
fha with)
Egn [C with ]]
Σ
P((t)))
1
1-1
P(
W 1
W F r
(aatt with)
1
Σ
Σ
Eg [C(abkiw [Whi]]
Σ (VotP())i))
1-1
W 1
W + r
(2)
Vay (" w/)
-
Σ
1
Σ
Eqn [C(ptio w]t
Vaa Σ P(otin)
T-1
W 1
+ r
Vat (a with
Σ
1 T-1
Σ
Egu [Ceptirr whhi]l
Vat (1)
7
W- 1
w + r
-Va (aat 2)
=
15

---

FedOne: Query-Efficient Federated Learning for Black-box Discrete Prompt Learning
where (1) uses independence of each sampling for oh; (2) is because infinite and the GS function is continuous and derivable with respect a;; (3) uses the property that the elements of probability vector sum to 1.
2) The bounded variance of variance-reduced policy gradient:
Var C Pay (a wth
(((+))
Vayt (a w//)
Vaz ia wmm)
L(Blir, p
Σ
aaphi w/th) Vat log P(of.i) - V Vat aat (a wtth
w=1
B(ptrry 1=1
Σ
(C(@tir, witt L(Btt." wtti)) Voz log P(o Vat. (" (at,
1
(1)
E Egg
1
Σ
(C(O"T, (m L( v(m) Voz log P(o Vaz (aatt(aa, vin)
72
T-1
w *
(2)
1
Σ Equ,
Σ
(L(okrr ()) - L( wwm) Vap log P(
[2[T 1)2
pm
10 1
W + r
(3)
4G
4G2N (5) 8G
5
Eautr
Σ
Vay log P(
I[1 1) S 127222
( - 1)2
W
W A
where (1) uses
E
1-1 Σ
(C(atir, - L(Oki.w ((h))) Vat log P(o - Val (
W = 1
w Fr r
Σ
Egttrr ab. woter ((c(@bir, L( ( Vat log P(ofiT)
1-1
W-
W +
Σ
Egg.r C(pkir .vth Vay log P(ottrt]
1
w #
16

---

FedOne: Query-Efficient Federated Learning for Black-box Discrete Prompt Learning
and the independence of each sampling for th (2) inequality IE l|a uses 1 2 // and (5);
Eal 2
E |a]] (3) uses Assumption 3.2; (4)
fir Li Ta 2,jo
Vat log ) S
N max
P
N
v2
Ta. 2,
is because when 7 2 2:
2
S
I[I - I
The following lemma shows that the (g(n))((**)) [<(** [ is L-smooth for a. This is crucial for the later convergence analysis of BDPL and Fed-BDPL and is necessity for convergence proofs.
Lemma A.2. L-smooth for a At the k-th client, the & is sampled from probability matrix p", and pd GS(a")) Oij 2 >> 0 ffori = I,.,, and = 1, N, > 0 is the lemperature parameter, Bar~as(a**) [[( v²) is L-smooth for a and L +GN(++1) and then for 1-th iteration, the following inequality is satisfied:
T²v²
Exgt 1 -os(at) 1) [C( w²]] Eogg ((o==))(a))) [c(0) w*)]
V Egg
mos(at) Eggras(a)))
[C(0) ] at) + L 2
||a - -
Proof. The objective function:
(((0 uhy Mp(oo))
E Ex(~a [C(**, w(]] = Σ
Σ
Φf )
We can compute the Hessian of the objective function, Vi, 1" E 1, and J' El, E1, N:: If i' o i":
82
Eapa B.paa(S((a*)
[C(T*] wh)
doy .² ",00a"g" 5"
0² dav y dam 5" i=1
Σ
C(Tb wa)
II
p(o))
pf
di dhrpph
Σ
pt
8²
II
day day 5"
1h p/y
Σ
si~pi
1
4 shrpph
C( vph 0² [ p(()))( gow. B0ss "
12 II P(o
i
i * 8 i 1"
17

---

FedOne:
Query-Efficient Federated Learning for Black-box Discrete Prompt Learning
Then:
1 1-Plis
1-P2r
'f - j; and j" = 3
1-P9
j' = J and j" + j
8a [P(O)) P(()))) Dav,y00s 5"
ra
Taf
(23)
pl
if + J and j" = 5%
Ta V.
pl
j + f and j" * 5²
3m
Based on o. 2 > 0:
82 [P(O))
1
(24)
Dav.g.0ax
-2n2
Further, based Assumption 3.2:
@²
Cisaat)) [C(0*) )
day 5r ;da 3r'
<
Σ
Σ
Σ
... Σ
E
Σ
L( TF
II
P()
72
p
P
& Po 04/144 P
rpr
i=
i x
i x
G
< y2
1 = :::
02
E (
IC(0* )b
do y Soy. lr'
c(@*, )² O2 [P(tt)]]
Σ
Σ
Σ
II
P()
day y Jav
0 xpp
dh
xk
@k x
i i=
i +
Similar to the analysis in case
+ H", we can get:
82 [P(
(++1)
++1
max {p, 1 p}
72 <
day ,.ay
72,2
(++
Eg E [L( v+(]] S
(25)
day y Soy.
r2n2
Finally, with (a)) denoting the Hessian matrix of (xpaass(a*) [((Ø vk)]] we can get:
G 2
(T+1) 2
nGN(T 1)
[H()) 12 < [|H(())) S mnnn-))N3 72y2
1)N2
+ nnN2
(26)
?2y²
?2p²
According Lemma 1.2.2 in (Nesterov et al., 2018), EspAnos(aa*)
[C(T Tpt) is L-soooth for * and I,
nTN(++1)
7202
18

---

FedOne: Query-Effiiiet Federated Learning for Black-box Discrete Prompt Learning
Lemma A.3. Convergence of BDPL: Suppose Assumption 3.1 and 3.2 hold, for I. i ,,..., n and j 1,,... N,
1, aa. u 0 for
> 0 is the temperature parameter, GStaa) [[(T*, Th)] is I-smooth for a and I == x) o% is the variance of the stochastic gradient, o² = SG x²
-- is the variance of the variance- policy gradient. Lei S i. then the BDPL's full gradient Fa wh) satisfies the following inequality:
1 T
4G
2n
21pLo a
7
Σ
V Fr (at (at, 1² S
+
4
(27)
Tn
B
12
Proof. According to Lemma A.2:
Exp Eatt, [ y*]] - [ ]
V Va E (e [C(0 w²]] a - at) + L
| - -ftll
2
Vat at Fr (at; ) -n- Vat l (at, B8)) + Luf
|| S (a B3 |1?)
2
Both sides take expectations for 1o; |M and Es, at the same time, we abbreviate E (ooraas as Borry.m
B Es, (Rats,, (asta, [C( 2+1, w² - B [A(0)) wti]]
+ LT₁
(a B3b ||}
< E (ar)) Es,
Fr (at v -n Vat (a (Ba) )
| (a
2
E Borry EB, (Vaz F (at )²,, -n a. (a BB))
+ LM²
| (at BB})
2
a)
For a):
E ) Mizi Es, (Vo: (at; v²), -n Pa (B)) BB))
Tnf² 1 ( 13,)1 (at,B,)
Vo at Fd (a 1 E( 1/11 Es, fot (a, b²))) |)
Ln²
E E Es, || (a BB) 27
2
Vot r (at ; vpt) -17 EB, E ( Sha BB3))
Ln²
E Bior)/_ Es, (oaz I' B²)) |/ + Varrs. (Tat M
2
2
-17 (V (Vat (ati, w²t,, Vaz Vay (a w+)) + Tay²
Vag (at, wt/l?
2
2np
E 1io0 Es, MagsM(at B+) - E Eiory Es, [Vaz ( (at Bt)] 11")
+
2
(8)
La7
11 )) // nat (at w+yl?
5
2
+ Tnp² E Es, \att BB)) - Es, Vat BB)} |1")
+ +Li - E(or) [Bs, (a , - - Es, (Vat p (ati B 1"]
Laj² -n)=-) V Vot (* wP/ || + Lnj² Biory Vars, (aap B+)]
2 2
+ Tnj² .Es, Var Bs, Vot BB}]]]
19

---

FedOne: Query-Efficient Federated Learning for Black-box Discrete Prompt Learning
(9) Lnj²
1)
Vot (at, w+)l² Lnj
o + Lnj²
Ln²² Es, Var [a. (af vn1)
+
2
(6)
Lnj - 2 1) n) Fot (at /²/ + Lnj
o
o² I
B
where (1) uses the independence between V sampling and & sampling; (2) use the unbiasedness of stochastic gradient and
variance-reduced policy gradient in Assumption 3.1 and Lemma A.1; (3) use the inequality ||a + bll - ||a]]* + [[6]² (4) and (5) use the bounded variance stochastic gradient and variance-reduced policy gradient in Assumption 3.1 and Lemma A.I.
Then:
[C( E 1
w²]] Eog~osiaat) [<(Ø) D*)]
Laj²
-n) Voy I+ (at, wt/l² Lij. o
o² d2
Lni
2
B
We combine the gradient of a; for each prompt token:
~GS(ar))))) [c( =²]] (osat) [C( wh)
< LTp² -n
1) V w/yl? + nLaz
o
0h + nLn²
B
1
where a = (at ... a ........ #)
We let 17 S 7, then both sides accumulate with respect to = 0, 1, .. T - and divide by T:
Lad 11 F* (a v²1l²
1
nLn22 nIn
Egg~os(aa [C v[)] Egg, os( (( wt]]] +
B
12
Then,
Σ V ph (at ||²
Egg Bøg~asiatt
[Ceg w²)] E ussaa)) [C v²]
2
2n
nLo
nLo?
+
T
21 - LTi²
- Ln
B
1
(
[C( v²)]
Egg mis(at)) [C(0,, v²4)
2o
2nmLo²s
<
Tn
B
12
According to Assumption 3.2, Egzg
[C(T]] w/]]] inf, Byg ~os(a))
[C(T)) vM)]]
s 2G, then:
1
T
VaL Vat (at w/1112 S
4G
2m 4
2mpLo?
T
Tn
B
12
t=
Remark A.4. The convergence term of BDPL consists of three parts. The first term is typical of first-order optimization algorithms converging to non-convex functions. The second term is the stochasticity due to random mini-batch gradients. The first term and second term can be combined when 1) vT and /
2B
n..
4G
2o
4
2n
+
Tnj
Bb
VT
B
20

---

FedOne: Query-Efficient Federated Learning for Black-box Discrete Prompt Learning
which decrease the number of iterations and mini-batch size increase (Reddi al., 2016); and the third term is the stochasticity due to prompt sampling, which decreases with the number of prompt samples.
Remark A.S. According to the definition of Gumbel-Softmax (2), there is randomness about u = {wi Uniform(O, I,)
in Va (af, w*) i.c. p GS(a*, u) in fact and d p², we can further discuss the result in Lemma A.3:
Eu V 1r (at, w 1V (at w->l" dh s V F Fa 1=
Considering the randomness of u, we can still obtain the convergence of BDPL. subsequent analyzes of Fed-BDPI,, we can obtain similar result for u.
Corollary A.6. Convergence rate of BDPL: Let
min
{
+
1 we can get the following convergence rate for BDPL: T VT) ).
T-1
(a 1/)1 s 0o 1
V a
PK
(28)
T
Proof. Convergence rate:
4G
2nLo
2nLo
V V (at
0
T
VT
VT
B
VT
12
A.4. Convergence Analysis of Federated Prompt Tuning
Definition the Federated Black-box Discrete Prompt Learning:
Data slicing: The data slices in each client are defined as D* {D*}
K A=1 = (w,,, y*jk Ik=1 where T { {wit ] m=1 denote
M
M** the input sentence and Y { f m= denote the label, the index of the client, and m is the index of the sample, there
are totally M samples in the dataset D The clients hold the sampling probability vector q { K = M k==
A1 K
K, is the number of clients selected and U, is the set of corresponding clients. Average parameter a:
Σ a
K.
kEt!
(.,(t)) K. KEU,
Average loss:
(s,,)s(a))
[C(0, 4/]
Σ
| (otaas(aa)) [C(0* wb)
1=1
Average gradient:
Va, F(a def Σ
[k]
Va, (a, w²)
(29)
k=1
V VatF(a 4/) def Σ d
V a.
Ft
(a", W²)
(30)
V Fr FatF V
def
Vay w+)
(31)
K.
keti
21

---

FedOne: Query-Efficient Federated Learning for Black-box Discrete Prompt Learning
Vatf B*) BB) des 1 K. kEt.
Σ
(at, B
(32)
V F BB)
def
Σ
(a,t
(33)
K.
REU,
Average mini-batch stochastic variance-reducee policy gradient descent:
(t(((+1) = (1) -1 77 V (a B²)
Note that when * EE, although the above some definitions don't It exist in algorithm and experiment, we can still calculate and analyze them. In order to facilitate the analysis of the iteration process, we assume that they exist.
The following lemma shows that the local gradient is biased compared to the global gradient due to the fact that the distribution of data on different clients may be different (heterogeneity), and the bias of the gradient can be analyzed using the bias about a (HHaddadporr & Mahdavi, 2019)).
Lemma A.7. Bound bias between local and average a. Let aij こV> for i = L,... n and j = -...,, N. is the learning rate, let E represents E ( and Egy, the bias between the local and the average a can be bounded:
T-1 1
K
[.]
aii(1)) - -ai
T
t= k=1
3 Enj²
20 V
+
20
I+
1
)
20p2
(1
1+ K.
Σ
V Voz F Flaaa
wtyl
B
12
K.
T
Proof. Define:
te P E
F.
1 Σ a.
ac(te)
Kx NEU
Then, for f. 11+1 < E:
t-1
(,11) = (t,,
t
- Σ n.
Var Ba)
(34)
p=le
(1,(1) (i,())) K
Σ kEU, p=te
n1
V Vat f BB)
(35)
For the k-th client, let E represents E and Egg, and we take E for |a.,00) at.co 12
E
1-1 n a (a 1%) - at,(ttt) + Σ n Va, (a
E
(1.c)))) K= kEUp p=te
p=to
t-1
E
Σ 11 v
Vo
f* BB)
Σ
Σ
n
V a.
8
(at. (Bt))
K.
kEUp p=te
2
(1)
2
E
Σ 7 4 a
1 (at BBh)
+E
I
Σ
Σ
4
pZ (a B%)
Kr
pomt
KeU, p=te
22

---

FedOne: Query-Effiiient Federated Learning for Black-box Discrete Prompt Learning
1-1
[-1
2
(-1
(2)
23
Σ "
1 (a), Bb) - E a
Σ po
Va
B%)
+ E
Σ
n
Vaz
1 B8))
Lomrc
1-1
2E
Σ
n V (a
- E
Σ
Vat (a Bb:)
K_
K.
kEU p=tz
kEU pate
2
+2 2
E
K Σ
Σ
n
Ma B8)
KEU, f=te
1-1
[-1
22
1-1
2
( 2E
Σ
V f (a Bb))
- En
n. Vat (a), p: yni
+2
E p=to
n V Vat F v.()
p=te
p=to
[-1
2E
Σ n (a
- K. kEUi pote
ΣΣ
n7- V at Ff (a va()
K KEU, p p=tz
2
+2
Σ n. Vat p: )nl)
Kr KEU, p=le
1
2 ( s (a BBy) - Vot po wiy]
= 2E
Σ 11
+2
+
n
V a (a th Val))
p=t
pate
2
-2E
Σ n (aa - V Vat (a ps
(a
votl]
-2
n. V at F* (at) Unl
Ka KEU, p=te
K. KEU, p=te
(1) 2n² Σ
1-1
E
4
a
pk:
(a B+) - V Vor (af. w 1² +2
Σ
[-1
17-
V
Fr (a )
p=le
p=te
2n²
E (a - at F
(a F
+2
1
Σ
n Va F* (a whii
K?
K₂
kEU to
KEU, patt
( 2n
Σ E
1-1
Vat
(a p: By) - V (a w 1 + +2n (t-
Σ
1-1
V Vat F (a w
p=le
p=te
2n1²
(a : B3)) - at Fk (att p: w/////
271² le) +
Vay F (a (a /2
E
K?
a
K.
kEU, p=te
KEUp p=le
(6)
1-1
20
202
2/²² 2
20
202
S 2n²
Σ
+
+
BB +
Bk
12
K2
12
P=le
KEU, p=le
-217(t - te)
Σ
1-1
V x
pkk
(at w+)|| ||
207 (t tc)
Σ
Σ
V Va
F* (a st/s1
K.
p=to
KEU,
200
202
) (1+ K. )
= 227² Σ p=te
+
Bk
|?
21 - 1x)
Σ
1-1
V x
pk (a p: wuy) 1|
Σ
pk (at o. war a
+ K.
p fc
kEU, putt
where (1) use inequality I|a - b/2 2 < 2 ||a|| 2 +2 11b1;: (2) use E 1|0 Ex]] = E ||0|| -|E [=]]] (3) use the unbiasednesss
of stochastic gradient and variance-reduced policy gradient in Assumption 3.1 and Lemma 1, (4) use the independence
23

---

FedOne: Query-Efficient Federated Learning for Black-box Discrete Prompt Learning
Z of mini-batch and prompt sampling in each client; (5) use inequality || ا dz|l² < E ||= variance of stochastic gradient and variance-reduced policy gradient in Assumption 3.1 and Lemma A. Then, we sum both sides with respect to & E Up:
(6) use the bounded
Σ E
2
(())
k
S 2nj²
Σ
t-1
20
+
20 (K.+1)+
2n te) (1 (1+k.)
K2 k.)
1
Σ kEU, p=to
V F* (a w
Bk
p
p=to
We take the expectation of both sides about Bu,
EU
Σ
E
a
o af!llll
KEUp
K.
[N).
E o41(11) ({
12
(1)
1-1
20
20 +
K 1-1
(a vpb) 1
$ 2n)
Σ p=te
(K, + +) (t- te) (K, + 1)
Σ
Σ
M
Bk
I
k=
p=te
where (1) is because we sample client set U, uniformly at random where client is is sampled with probability glh) for 1 S k S K with replacement, and we define U, {Ki,, my kib, ...: kk.). then
EU,
Σ KEUP
V a
F.
(a woh) 1|2
K.
Vot
F* ko spht) [1]
b=1
K.
(ik)
Va Fa (at uudi|/
K
K.
[k]
Va r* (at vp() 1
Thus:
Σ [kl E aas att" ||
< 2m 2 Σ
1-1
20
+
202
(1+ 1
20 + te)
(1+
1
Σ
K t-1
Σ
dl
Vat (a wt)
BL
1
K.
p=to
k= p=te
We take
tor 7
t - ter and add iteration on both sides:
T-1 K
R. .E |la..00 - at.oo
E- K
[4] E |a..00E)) - x ((ttt))))) |
20
20
(+
1
1
Bh
12
K.
0=0
0=0
24

---

FedOne: Query-Efficient Federated Learning for Black-box Discrete Prompt Learning
1
w²yl² 2
27 + 1) (7+
[1
voz F
K.
==0
y=0
k=
v=
1)
2002 Bk
20
(1+
1
S (E+ + 1)Tr)
+
T2
K.
R
K E-1
1
(kk) , Vo. F+ (a vott ||²
+ Σ
21 F²
1 K₂
==0
k=1 w=0
$ (E+ + 1)T
200
+
20
(1+ 1
+ 27 E²
1+ 1
ΣΣ
|
Vot w
12
K.
K,
where (1) use - E and 1+ ... + E E(E+1)
Finally multiply both sides simultaneously by ::
M E
as.(1)
t=
< (F++ +
2
+
20
1 + K,
+
20
1 +
K T
V
F* (a : w//
Bh
12
T
K2
k=
(
20
20
1
1+ EdX
T
Σ [kl Vot (ati vot) 11
S (E 1)m?
V
1 +
B
1
K.
T
K.
k=
2002 B&
202
1
2n E
T
V a Play w+) |?
= (E + =E++1yp 1
+
1+
1+
1
K.
T
K,
where (1) use Assumption 3.3.
Theorem 3.4. Suppose Assumption 3.1, 3.2 and 3.3 hold, for = 0, -.,.,,,-,,.mmmin min (B' ...,, B*} where B is the
local mini-batch size. Oii.j 2 v >>>00 0 for = 1,..., n and j I,..,, N, I is the sampling times for prompt. o 8GNN is the variance of the variance-reduced policy gradient, oi is the variance of the stochastic gradient, (pa
[c( v()] is
L-smooth for a and L mGI((++1) and 77 satisfies the following incquality:
72y2
1
0< < LA
(36)
Then, the Fed-BDPL's full gradient V. F(ss, v²) satisfies the following inequality:
T
Va F F(a )1
T
1= 0
4G
2(E + I)n (1 + At,) + 2no 2(E + 1) + xt) + 2no²
+
n/T
B
12
Proof. According to Lemma A.2:
Eg [[ 4)) - Egg,-SS(a.) [[( 1)
1
< (V V Valla, [[ U)] a++1 a.) + _/ ||a+11 - ax 1
Va, F(a,, V*), aat 1 (a BB))
Ln²
V (att |"]
25

---

FedOne: Query-Efficient Federated Learning for Black-box Discrete Prompt Learning
We take the expectations about {ght)) Jr Bi and Uy on both sides respectively:
E (ot.r) rrm Big Bu, {Es,,1 G [1( D) - Es, [ D)]}
Bioear BBy Bu, (Va,Flar. Vh), -1 Vat (at BB)
<
7
Lyp
Dat S BB E p By Ru,
+
2
/=1
6)
For a):
E po Bu (Va. w²)) -n- Va (a BBt)
Va, F(a,, V²), -1 B Beyiing Bog Bu,
\oa l (a BB:)
Va, Fas, w²), -n By, ponnn Egg
1
Var (att wty)
K.
kEU,
Vas F(as, T/), -n7 -n-BU,
1
F* (at, w at
K2
kEU.
-7- Va: F(a,, )
K. Σ gM Vot 5041
Kx
k
||Va, w/>11² - V. Flat wt) |+)
Va, Flar, Th)) - Σ
glll Vax F (a, vtA)
2
k=1
K +
| Far, w* )² - V at Faat w//
Σ
qlol
(V ( w/y V Va Ft wt))
(2) 17
|/, F(a,, v²>11²
v o Flat,, v/t)
Σ |
Va, F* (ac: w/h) Vas 1r (at wt)
7
VV.FFla, 112
Vot |/
K
+
1
Va, Bor vinl]
1
Σ
Boy with
2
ME
ME
1=1
vht EVe
with
eV
(3)
"
Va Farr V )|² T Flat, w+y|²
Σ
[+] 1,2.
(a.(1))
at.00 ||]
2
Lk=1
where (1) use inequality 2(a, b) = ||a|12 |16112 |la -b12: (2) use the convexity of Eg norm: (3) use L-smooth in Lemma A.2.
For b):
[| (a 10,)
E B Egg Ev,
2
{
Lmp
E (pttir) Egg Fat BBt)) [1]]
-Ee,
2
26

---

FedOne: Query-Efficient Federated Learning for Black-box Discrete Prompt Learning
①
Ln
|| f" B+) - Eggary Ess [Va fa Bb)
Eu,
E
2
L
( f (af B+) }|}
+ 1B
E
Ess
2
Laj
|at B+) - Vat F" (at, wt |+)
Eu.
E
/
Egg
Lnp²
V aat f Fa (af, (af, |1]
+ EB.
2
(3)
2
FM (at w&)) |
Ev,
V a
2
|aat/ (at, B() - -Broe.rj Vas Ma, BB)) |"}
+ EE,
Laj B Broarry
Eas
[E Vas F' BB)) - -Baani) Eas Vay f (a, /35) }1}}
+ Ev.
La
2 E (q 11
E8g
(1)
2
Ryg
|o F (a w////
+ Lnp² Re,
02
+ Inp²
BBu,
[o3
2
T
B
Lr7²
K
[b]l | pa (at w+/l/² 1|2
Va.
Lni²0a
Lnj²
+
+
2
12
B
k=1
(5)
Lni²>
K
Lipoaa
Lnpo2 a
/
Vat n (at, )+(t
+
(37)
2
12
B
where (1) use E || E = E -E |I [x]]:: (2) use the unbiasedness of stochastic gradient and variance-reduced
policy gradient in Assumption 3.1 and Lemma A. (3) use ||a stochastic gradient and variance-reduced policy gradient in Assumption 3.1 and Lemma A.l; (5) use Assumption 3.3. Combining a) and b):
bij² < 2 ||a| + [|B|] (4) use the bounded variance of
T
( [4(D++1, V)] - Es Ess [6(0,, w]]}
T
0=
1
V Flar, )²² + Vo Flat, wb)y 1/////
+ 1
Σ
K
t 1
oi,(1) - aftes 12)
T
2
2
0= i=1
-==1
LTI²> A
K
Lnio3a
Tnpa v
[4
V Var yt)
+
2
12
B
t=0 ==1
1=1
2 7 1 T-1
VaF v+111 +
+ 11
1
V a Fla 1
2T
K.
T
+ E 1E+1) (E+1)L
no 3 (1 R.)
+ oLapoz
(E 11111 (1 R.
+ nLaj
B
12
where (1) use Lemma A.7.
Then, we can get:
Σ Val Vas, v²
E (o00))))) [L(D0: 40] - EB [C(DT, V)]
nT
+
- 1 + XLy +2 + K.
Σ
V a- F Fat w
T 1=0
27

---

FedOne: Query-Efficient Federated Learning for Black-box Discrete Prompt Learning
+ 2 + 10 (1 + K. + 2nLno 2 + 1) + xt.) + 2nLno
B
Based on Assumption 3.2, G((a))((a))
(L V) - inf, F.p,a)((a)) [,(0,, v) - 2G and:
-1 -1+ AL + L2E11 + 1
K 0
-XI+ 12122 - 812F 1 K.
0 <<nS
4L2E 1 +.,
According to Taylor's inequality:
+++x2 1 for 20:
X2L2 8L2E
1 K.
8L2E
|+
+
K.
-LL
1+
X2L2
4E
[
1
K.
TX
1
(38)
X2
Then, we can get:
-XL +
X212 + 8L2E (1+ R.
4L2E [1 kr.
AL A AL 1+ 1B(1+
4LPE' 11 +
(39)
LA
Finally:
V (at, 1²
T
4G
2EE + 1) n no (1 + 2.) + 2n
2(E 1) no? (1 + 1 + 2nLno
K.
+
T/T
12
4G
2
1)mo?
k.) 2n B
2(E+1) (1 + x.) 2no
+
+
(40)
n/T'
12
Corollary 3.5. Convergence Rate of Fed-BDPL:
Let 17 min
TT L B VT and Tå, the following holds:
LA
1 TT
V. F Fla,, v)1 0
(41)
28

---

FedOne: Query-Efficient Federated Learning for Black-box Discrete Prompt Learning
Proof. Let 1) = min
LA vT 1.. B = VT and I = -'', plunging in Eq. 40, then we have:
1
T
1
V (a,, )1
T
$ (1G) +
VT (2n + 2no
2 + 1)+ | 2(E 1)no K. VT
(42)
K.
Therefore, + E Va = (+7))
Corollary 3.6. The Impact of K, (FedOne): Let Q. denote the minimum number of queries submitted to the cloud-based LLM service to achieve an e-solution, formulated as a function of K., i... Qe(K.). We derive its explicit form in Eq. 45 and show that Qe(K) a monotonically increasing function of K, for K, = 1,2...., ... K. Therefore, to minimize query overhead and achieve optimal efficiency, the optimal choice is K. 1.
Proof. Considering the iterative complexity based on Eq. 42, to obtain an e-solution satisfying
T-1 VaF
1 [AG] + (2no 2no + 2(F + 1)no +
-) K. + 2 1)moa
1 [
s
T 1=
VT
K.
(43)
the minimum number of iterations, Te, to achieve the c-solution can be derived as follows
2(E + 1)no (1 + At) + 2no 2(E 1)no + k..) + 2no 12
4G 2
T. =
(44)
22
22
Note that the minimum number of LLM queries Qe required to achieve an e-solution is given by Q. = c- T.T.K. where e a constant representing the number of query per iteration per client." 5 The term T.K, can be represented as the following:
4G 2
2(E + D)no (1+ r.) 2no 2(E + D)no' (1 R.) 2no
Q = CT.KK =0
+
K.
2
2
4G
2(E + no
2(E + 2)no
2(E + 1)no?
2(E + 1)no'
+
V Ks +
2
2²
2²
22
e²
VK,
1 1
1)
civ K. + C2 VK,
(45)
where 1) substituting e 4G Eq. 45 is a function of K,. Analyzing its main form, a GvK, + C2 -ス. and considering its graph and solving using calculus, we determine that its minimum occurs at kopt 22, i.c.:
2 + 2(E 2
2(E+ and C2 = 2(E+ 1)no? e²
+
2(E+1)no for brevity. Observe that 2²
2(E+1)no'
+[=+1)oo 1) 2(E+2)n03
c2
Kopt_
<
cl
4G
2[E+2)no
where 1) note that C1 = C2 +
1G 22
2
2ng
therefore the denominator (c1) is greater than the numerator (c2).
Finally, considering K, E N+, we observe that Q. increases monotonically within the feasible region of K,. This implies that the optimal K, for query efficiency is K. 1.
*T, can be regarded as a function of K., treating all other variables as constants.
$Q. c. T.K. can be expressed (number of query per iteration per client) (number of iteration to achieve e-solution) (numher of activated clients per iteration)
29

---

FedOne: Query-Efficient Federated Learning for Black-box Discrete Prompt Learning
B. Experiment Details
B.1. GLUE Dataset Metrics
Below is the table for the detail of the dataset we use, and their associated tasks, metrics, and data domains.
Dataset
[
Train]
Dev
[Test]
Type
Metrics
Domain
MNLI
3
393K
9.8K
9.8K
NLI
acc.
fiction, reports Quora
QQP
364K
40K
391K
paraphrase
SST-2
2
6.7K
872
1.8K
sentiment
acc.
movie reviews news
MRPC
2
3.7K
408
1.7K
paraphrase
Fl
CoLA
2
8.6K
1K
1K
acceptability
Matthews corr.
books, articles Wikipedia
QNLI
2
105K
5.5K
5,5K
NLI
acc.
RTE
2.5K
277
3K
NLI
acc. news, Wikipedia
Table 5: The statistics and metrics of seven datasets in GLUE benchmark, [L]: number of classes for classification tasks.
C. Supplement Experiment
C.1. Impact of Activated Clients K, on Query Efficiency in Federated Black-Box Prompt Learning
We also evaluated the impact of K, on query efficiency in Federated Black-box Prompt Tuning, as presented in Table 6. The SST2 dataset was used to explore how varying the number of activated clients per round affects model convergence efficiency in FL. environments. We tested the number of activated clients per round within the range of [1,3, 10, 30). For each configuration, we monitored the number of queries required to achieve target accuracy on the validation dataset, reached,
Specifically, evaluated the prompt the end of each epoch and stop training once the target accuracy reporting the number of L.M queries at that point. To ensure reliability and account for variability in the learning process, each experimental setup was replicated 20 times, and outliers in the number of queries were removed. The primary aim of our study was to explore how the number of activated clients affects the speed and efficiency of model convergence in FL, specifically to demonstrate the query efficiency of the FedOne approach.
The results presented in Table 6 demonstrate a clear trend where fewer activated clients are associated with greater query efficiency. This relationship is evidenced by consistent decrease in the number of cloud-based LLM queries as the number of activated clients is reduced, pattern observed across both the Federated BDPL and Federated BBT.
Table 6: Query Efficiency in Federated Black-Bos Box Prompt Learning
Fcd-BDPL
Fed-BBT
AC
# Epoch
LLM Queries
# Epoch
LLM Queries
25.4
13826
10.8
2350.01570.
13.8
889. 44310.9
5.442.3
3825.0 1356.2
10
11.5
2430.8 1378.8
4.2
10444.4 36644.3
30
3.542.8
2672.741626.4
1.740.9
16000.0456564
C.2. Impact of Prompt Length n on Federated BDPL
To explore the impact of prompt length on the performance of the FedOne framework, we conducted additional experiments using various prompt lengths across multiple tasks from the GLUE benchmark. We varied the length of the discrete prompts by increasing the number of prompt tokens while keeping other hyperparameters constant. The tested prompt lengths included E (10, 20, 40, 60).
Figure presents the results these experiments, where test accuracy is reported as the mean across five independent runs with different random seeds, and error bars represent the standard deviation. The results indicate that the overall performance remains relatively stable across different prompt lengths, with minor fluctuations. Notably, the shortest prompt lengths
30

---

FedOne: Query-Efficient Federated Learning for Black-box Discrete Prompt Learning
(n 10) and largest prompt lengths (n 60) explore larger variance, the medium prompt length explores a more stable
result.
0.86
Mean + Std Dev
Test Accuracy
0.84
0.82
0.81
0.80
10
20
30
40
50
60
Prompt Length
Figure 3: The impact of prompt length
C.3. Experiments on Heterogeneous Client
We further included an additional experiment to demonstrate FedOne's performance under varying levels of client hetero- geneity. Following prior works from Lin et al. (2020) and Yurochin et al. (2019), we model heterogeneity using Dirichlet distribution with concentration parameters a = 0.5 for medium heterogeneity and a = 0.1 for high heterogeneity. Each experiment conducted independently three times. The full results, including three figures corresponding to varying levels of heterogeneity, are presented Figures 4, and As observed from the results, activating a single client consistently yields the optimal query efficiency, which is aligned with the theoretical result.
Zoomn:f6 (0, Ski
Validation Accuracy
K-
K. 55
K 10
K. 20
K. 40
20000
40000
60000
80000
100000
120000
140000
160000
Total API Calls
Figure 4: IID client
31

---

FedOne: Query-E.ficient Federated Learning for Black-box Discrete Prompt Learning
80
Zoom:: [0, Skl
Validation Accuracy
K
K.
20
K.
K.
K.
20000
40000
60000
80000
100000
120000
140000 160000
Total API Calls
Figure 5: Medium Heterogeneity Clients
90
Zoom: (0. 15k]
Validation Accuracy
60
20000
40000
60000
80000
100000
120000
140000
160000
Total Calls
Figure 6: High Heterogeneity Clients
C.4. Test Metrics for the RoBERTa-Large Experiment for FedAvg
To complement our main results in table 1, we present the detailed test metrics for the RoBERTa-Large experiment using the FedAvg algorithm with 10 activated clients per round. Table serves as a supplementary to Table 1, providing the FedAvg result of each prompt tuning methods.
32

---

FedOne: Query-Effiiiet Federated Learning for Black-box Discrete Prompt Learning
Table 7: The test metrics on the RoBERTa-large of FedAvg (K, = 10). Each trial runs across three random seeds.
Dataset
MNLI
QQP
SST-2
MRPC
CoLA
QNLI
RTE
Avg.
Pead-Promp'luunngg Fed-P-Tuning v2
41.8p.o
66.30.1
78.3p.2
80.7p.2
0.66.0
51.1p.0
51.4g.3
52.89
42.4p.1
66.60.1
82.4g.5
80.60.4
0.9b.1
52.96.1
53.7o.4
54.21
Fed-BBT
41.41.2
66.70.2
77.6p.4
80.11.2
2.7p.6
51.9p.6
52.3a.7
53.24
Fed-BDPL.
40.81.0
67.0o.2
82.92.
80.51.
5.9p.2
52.0p.o
53.80.5
54.70
Bed-GG--DPL
41.2p.4
67.4o.1
82.81.4
80.51.0
5.80.5
52.30.2
54.50.4
54.89
C.5. Test Accuracy for Various Total Number of Clients
To demonstrate the scalability of FedOne, we further report the test accuracy of FedOne-BDPL. and FedOne-GS-BDPL on the SST-2 dataset under varying total numbers of clients (100, 1, 1,000, and 10,000). Both methods exhibit stable performance as the number of clients increases, demonstrating strong scalability.
Table 8: Performance of FedOne on SST-2 with varying total number of clients
Framework
100 clients
1000 clients
10000 clients
FedOne-BDPL
80.8t.b
79.9 79.71.6
79.72.4
FedOne-GS-BDDA
80.8p.4
79.81.0
33


Reviews:
[{"review_id": "mxywN6kto0", "reviewer": "Reviewer_BZU1", "summary": "This paper introduces a federated learning framework for black-box discrete prompt learning (BDPL), specifically suitable for cloud-based LLMs. The core idea of FedOne is to optimize query efficiency by degrading the traditional FedAvg algorithm to activate only a single client per round. The authors claim to provide the first theoretical analysis of query efficiency in federated BDPL, demonstrating that FedOne achieves optimal query efficiency in this context. Empirical results from numerical experiments are presented to support these theoretical findings, showing significant improvements in query efficiency compared to existing federated black-box prompt tuning approaches.\n\n## update after rebuttal\n\nI feel my concerns are addressed and I have increased my score.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful comments and for recognizing the contribution of our work. Your feedback has been invaluable in enhancing the quality and clarity of our manuscript. We reply to the questions and weaknesses. \n\n>**Q1&W1**: Impact of heterogeneity\n\nWhen the client‘s data distribution is highly heterogeneous, **the theoretical result that activating one client per round yields the highest query efficiency in Fed-BDPL still holds**. This is because the core intuition behind FedOne remains valid under such conditions: the query cost to the LLM increases linearly with the number of activated clients (since each activated client issues one query), while increasing K is not able to provide a linear speedup in convergence ([1, 2]).\n\nWe have also included an additional experiment to evaluate FedOne's performance under highly heterogeneous client distributions. Following prior works [3, 4], we simulated heterogeneity using a Dirichlet distribution with the concentration parameter $\\alpha=0.1$, representing a highly non-IID setting. The result demonstrates that, **even under highly non-IID conditions, activating a single client per round ($K_*=1$) still achieves the highest query efficiency**, which is aligned with the theoretical result. The result figure can be found at this anonymous link ( https://anonymous.4open.science/r/ICML-Rebuttal-FedOne-649F/Converge3-High_Hetero.png )\n\nWe will include this experiment in Appendix C. \n\n>**Q1**: Potentially slow convergence\n\nAs demonstrated in [2], activating more clients per round under non-IID settings can improve the convergence rate, but it does not yield a linear speedup. By setting $K_*=1$ in FedOne, **our approach intentionally trades off this marginal gain in convergence rate in favor of query efficiency**. \n\nHowever, the primary goal of our work is not to maximize convergence rate per round, but to **identify an optimal query-efficient strategy within the Fed-BDPL framework that still guarantees convergence**. Both our theoretical analysis and empirical results confirm that activating a single client per round achieves this objective, offering the best trade-off when considering the high cost and rate limits associated with querying cloud-based LLMs.\n\nWe will add a discussion of this trade-off in the Appendix to provide a more balanced view of the design choice.\n\n>**Q2&W3**: Adaptive strategy of $K_*$\n\nRegarding the adaptive strategy, this work provides **two key insights into the trade-off** between the number of activated clients $K_*$, convergence speed, and query efficiency:\n1. Increasing $K_*$ leads to higher query costs (scaling linearly with $K_*$) while yielding only sublinear improvements in convergence rate.\n2. Reducing the number of activated clients K improves query efficiency but may result in slower convergence. Notably, setting $K_*=1$ achieves optimal query efficiency.\n\nOur research provides the above principles for tuning $K_*$, enabling practitioners to adjust $K_*$ according to their specific system constraints and performance objectives. \n\n \n>**Q3&W2**: Uniform query cost assumption\n\nWe acknowledge that query costs may vary in practice due to factors like input length or client-specific characteristics. However, the uniform cost assumption allows us to simplify the theoretical analysis without significantly compromising realism.\n\nSince clients are randomly selected at each round, **variations in individual query costs are expected to average out over time**. Even if we modeled client query costs as a distribution, the inherent randomness in selection would mitigate the overall impact. Therefore, the uniform cost assumption offers a practical balance between analytical tractability and real-world applicability. \n\nWe will add the above discussion to the manuscript. \n\n---\nReferences\n\n*[1] Haddadpour, Farzin, and Mehrdad Mahdavi. \"On the convergence of local descent methods in federated learning.\" arXiv:1910.14425 (2019)*\n\n*[2] Li, Xiang, et al. \"On the convergence of fedavg on non-iid data.\" ICLR 2020.*\n\n*[3] Lin, Tao, et al. \"Ensemble distillation for robust model fusion in federated learning.\" NeurIPS 33 (2020): 2351-2363.*\n\n*[4] Yurochkin, Mikhail, et al. \"Bayesian nonparametric federated learning of neural networks.\" ICML. PMLR, 2019.*", "claims_and_evidence": "The paper's central claim about the optimality of $K^*=1$ for query efficiency.\n\nE1: The theoretical analysis in Sec. 3 provides a foundation for the claim, the authors derive the convergence rate of Fed-BDPL (Corollary 3.5) and the query complexity function (Corollary 3.6), showing that it achieves minimum at $K^* < 1$.\nE2: The empirical validation includes\n- A toy experiment demonstrating that $K^*=1$ achieves better query efficiency on MNIST data\n- Evaluations on GLUE benchmark tasks.\n\nThe claim about comparable performance despite reduced query cost is well-supported by the experimental results in Table 1 and Table 3, where FedOne-BDPL and FedOne-GS-BDPL achieve performance metrics similar to other methods while reducing queries by orders of magnitude.", "methods_and_evaluation_criteria": "The proposed method, FedOne, which is essentially FedAvg with client selection restricted to one client per round, is a sensible approach to potentially improve query efficiency. By activating only one client, the number of queries to the cloud-based LLM per round is directly reduced.\n\nFor evaluation, this paper focuses on query efficiency as a primary criterion. The authors also consider query cost for cloud-based LLM APIs.\n\nFor benchmark datasets, GLUE is a standard choice for evaluating LLM performance across diverse tasks.", "theoretical_claims": "I did not verify the details in the proof. I do not find apparent flaws with high-level theoretical analysis.", "experimental_designs_or_analyses": "The toy experiment (figure 2) appropriately demonstrates the relationship between query efficiency and $K^*$ in a controlled setting.\n\nFor the GLUE benchmark evaluation, the use of 100 clients with $k$-shot datasets simulates a FL scenario, and the hyper parameter tuning with grid search is thorough and follows standard practice.\n\nI appreciate that the authors also provided computational efficiency experiment (table 2), including direct comparison of white-box vs. black-box approaches.", "relation_to_broader_scientific_literature": "This paper should be positioned within three interconnected areas: prompt tuning for LLMs, federated learning, and federated prompt tuning.", "essential_references_not_discussed": "I am not an expert in FL, and I am not able to identify clear missing references.", "other_strengths_and_weaknesses": "I summarize the strengths and weaknesses I identified below. They may overlap with the previously discussed points:\n\n### strengths\n\n1. The paper introduces a counter-intuitive but well-substantiated insight that fewer activated clients leads to better query efficiency in federated black-box prompt learning.\n2. The theoretical analysis establishes connections between convergence rates and query complexity\n3. The experimental validation covers both synthetic data and real-world LLM APIs.\n4. The topic being studied is timely and important.\n\n### Weaknesses:\n1. Limited analysis of the impact of heterogeneity across clients.\n2. The analysis assumes uniform query costs across all clients, but in practice, query complexity might vary based on input length, client location, and other factors.\n3. It appears that the paper does not explore adaptive strategies for determining $K^*$ based on system conditions.", "other_comments_or_suggestions": "N/A.", "questions_for_authors": "1. How does the FedOne approach perform when client data distributions are highly heterogeneous? Since only one client is activated per round, does this potentially slow convergence in highly non-IID settings compared to traditional FL approaches?\n2. Have you explored adaptive strategies for setting K* based on observed convergence patterns or system conditions?\n3. The paper assumes uniform query costs across clients. How would varying query costs (due to different prompt lengths, computation time, etc.) affect the theoretical analysis and the optimality of $K^*=1$?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4ggeou5ejT", "reviewer": "Reviewer_jBwD", "summary": "The paper introduces a federated learning (FL) framework designed to improve the query efficiency of Black-Box Discrete Prompt Learning (BDPL) when interacting with cloud-based Large Language Models (LLMs). Traditional federated black-box prompt tuning approaches incur high query costs due to multiple clients querying the cloud-based LLM in each training round. To address this, the authors propose FedOne, a specific case of FedAvg framework that activates only one client per round.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful comments and for recognizing the contribution of our work. Your feedback has been invaluable in enhancing the quality and clarity of our manuscript. We reply to the weaknesses and questions. \n\n>**W1&Q1**: Impact of heterogeneity on theoretical analysis\n\nThanks for pointing that out. We will add more discussion on the heterogeneity in the theoretical analysis. \n\nRegarding the theoretical result under heterogeneity, the conclusion that activating one client per round yields the highest query efficiency in Fed-BDPL still holds. However, the trade-off is a slower convergence rate per round, as fewer clients contribute updates in each iteration. \n\n1. Theorem 3.4, Theorem 3.5, and Corollary 3.6 explicitly consider bounded client heterogeneity, and the result that **$K_*=1$ achieves optimal query cost remains valid in this context**. This is because the core intuition behind FedOne continues to hold: the query cost to the LLM increases linearly with the number of activated clients (as each client issues one query), while increasing $K_*$ is not able to provide a linear speedup in convergence ([1,2]). \n2. The trade-off is that fewer activated clients per round lead to a slower convergence rate (e.g., $O(\\frac{1}{\\sqrt{K T}})$ convergence in [1]), even though it improves overall query efficiency. \n\n>**W2&Q2**: Experiment on heterogeneity\n\nWe have also included an additional experiment to demonstrate **FedOne’s performance under varying levels of client heterogeneity**, supporting the points discussed in W1&Q1. Following prior works [3, 4], we simulate heterogeneity using a Dirichlet distribution with concentration parameters $\\alpha=0.5$ for medium heterogeneity and $\\alpha = 0.1$ for high heterogeneity. Each experiment is run three times independently. The complete results, including three figures corresponding to different heterogeneity levels, are available at the following anonymous link ( https://anonymous.4open.science/r/ICML-Rebuttal-FedOne-649F/Converge2-Medium_Hetero.png ). We will include the above experiments in Appendix C. \n\nThe experiment shows that across all levels of heterogeneity, when the trials converge to a similar stationary point (i.e., approaching the same validation accuracy), **activating a single client per round ($K_*=1$) consistently achieves the lowest query cost**.\n\nThe trade-off is that: \n1. Activating fewer clients increases variance in training, which can lead to greater fluctuations. \n2. Activating fewer clients also lowers the convergence rate, and conversely, increasing K can speed up convergence at the cost of higher query overhead. \n\nBased on the above trade-off established in our work, practitioners can tune $K_*$ according to their specific system constraints and performance goals.\n\nDespite these trade-offs, the **primary objective of our work is to identify the optimal query-efficient strategy within the Fed-BDPL framework that still guarantees convergence**. Both our theoretical analysis and empirical results demonstrate that activating a single client per round achieves this goal, providing the best balance in settings constrained by the high cost and rate limits associated with querying cloud-based LLMs.\n\n>**Other comments**\n\nThank you very much for pointing out these helpful corrections! We have revised them accordingly. \n\n---\nReferences\n\n*[1] Haddadpour, Farzin, and Mehrdad Mahdavi. \"On the convergence of local descent methods in federated learning.\" arXiv preprint arXiv:1910.14425 (2019)*\n\n*[2] Li, Xiang, et al. \"On the convergence of fedavg on non-iid data.\" ICLR 2020.*\n\n*[3] Lin, Tao, et al. \"Ensemble distillation for robust model fusion in federated learning.\" Advances in neural information processing systems 33 (2020): 2351-2363.*\n\n*[4] Yurochkin, Mikhail, et al. \"Bayesian nonparametric federated learning of neural networks.\" International conference on machine learning. PMLR, 2019.*", "claims_and_evidence": "The convergence of Fed-BDPL (theorem 3.4, Coro 3.5). Activating one client in Fed-BDPL framework can achieve $\\epsilon$-solution with least queries (corollary 3.6).", "methods_and_evaluation_criteria": "The proposed method is well-motivated and aligns with intuitive reasoning. The evaluation follows standard practices. However, further experiments on non-IID settings would strengthen the generalizability of the results.", "theoretical_claims": "I checked the proof of Theorem 3.4. It makes sense to me.", "experimental_designs_or_analyses": "The experiment looks pretty standard (benchmark, baselines). It uses the GLUE dataset and demonstrates results on the white-box RoBERTa and the black-box GPT-3.5, covering standard tuning methods such as prompt-tuning, prefix-tuning, and black-box tuning. Additionally, it includes an analysis of computational and communication costs. The toy experiment also aligns well with the theoretical findings.", "relation_to_broader_scientific_literature": "The backbone of this paper is Fed-BDPL (Lin et al., 2023), which applies BDPL (Diao et al., 2022) to FedAvg (McMahan et al., 2017).\n1. This paper identifies the previously overlooked query cost problem in cloud-based LLMs within Fed-BDPL. \n2. This paper presents the first convergence analysis of Fed-BDPL (Theorem 3.4) and further explores query efficiency and convergence behavior (Corollary 3.6), providing a rigorous theoretical foundation for fed-BDPL.\n3. Building on these theoretical results, the author demonstrate that activating only one client per round achieves optimal query efficiency in Fed-BDPL, leading to the proposed FedOne framework.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "Strengths:\n1. Though the idea of FedOne is quite simple, the author provides rigorous proof by deriving the explicit form of the number of queries required to achieve the $\\epsilon$-solution (Corollary 3.6) effectively justifying the underlying principles of the approach. This finding is interesting and novel. \n2. The paper identifies a previously overlooked research problem, the substantial query cost on cloud-based LLM using convention FedAvg. \n3. The paper presents the first theoretical analysis of Fed-BDPL, providing a rigorous foundation for understanding its convergence and query efficiency. This analysis provides valuable insights in the optimization of Fed-BDPL. \n4. The presentation is clear. The core idea is simple, with no unnecessary components added to the framework to artificially increase system complexity. Theoretical analysis and algorithmic design are seamlessly integrated, contributing to the paper's overall coherence.\n\n\nWeaknesses:\n1. While heterogeneity is not the research focus of this paper, a discussion on heterogeneity and its potential impact on the FedOne framework could be further explored in the theoretical analysis. This would provide deeper insights into how FedOne performs under varying degrees of client heterogeneity. I am very curious about this question.\n2. The experiment is also solely based on the IID case. The theoretical analysis suggests that under bounded client heterogeneity, one client is most query-efficient. I suggest that the authors should also include additional experiments on heterogeneous data to evaluate whether the FedOne framework remains efficient under some level of heterogeneity, which make the experiment section more align with the theorem.", "other_comments_or_suggestions": "1. #016, Large Language Model (LLM). \n2. For table 1 you can also bold the highest, which makes a consistent format as table 3. \n3. #220, the footnote 2 is not complete. \n4. #325, in table 1. We observed...", "questions_for_authors": "How can heterogeneity affect the result of Corollary 3.6, FedOne? How does heterogeneity affect the results in the experiments?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4EJLljUi7B", "reviewer": "Reviewer_vcwQ", "summary": "This paper explores Federated Black-Box Discrete Prompt Learning and introduces FedOne, a novel approach that selects a single client per round. The chosen client updates the sampling probability for each token at different positions, optimizing prompt learning in a federated setting. Comprehensive experiments confirm the effectiveness.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank you for your insightful comments and constructive criticisms. Below, we address the weaknesses.\n>**W1**: Rationale of Fed-BDPL\n\nThe rationale for employing **Black-box** Discrete Prompt Learning is grounded in two key real-world constraints:\n\n1. **Lack of Access to Model Internals**: The white-box federated prompt learning approaches (reference [1–4] you mentioned) assume direct access to model weights or gradients, which is infeasible in realistic scenarios when we want to leverage the most advance commercial, closed-source LLMs (e.g., GPT, Claude), that are only accessible via APIs. Our work specifically targets this black-box setting, where the prompt tuning is conducted without model access—a practical and increasingly common constraint in modern applications.\n2. **Resource Constraints on FL Clients**: In typical FL scenarios, clients are resource-constrained devices (e.g., mobile phones) with limited compute and memory. However, white-box methods ([1-4]) require storing and training on the LLM model locally, which is computationally infeasible for such device. In contrast, black-box prompt tuning offloads the computation to the LLM API, making it scalable and deployable in realistic FL scenario.\n\nWe will revise the introduction (par. 3, 4) to make the above rationale more explicit, and ensure that references [1–4] you mentioned are properly cited in the Related Work section.\n\n>**W2**: Motivation of FedOne\n\nThe motivation to activate only one client per round is not heuristic, but rather **grounded in our theoretical analysis of query efficiency in Fed-BDPL**, which includes the convergence of Fed-BDPL (Theorems 3.4, 3.5) and query efficiency (Corollary 3.6). Specifically, **Corollary 3.6 demonstrates that setting K=1 achieves optimal query efficiency for reaching an $\\epsilon$-solution in the Fed-BDPL framework**. The FedOne framework is directly derived from this theoretical result to achieve optimal query efficiency.\n\nThe **intuition** behind FedOne is further elaborated in **Remark 3.7**: the query cost to the LLM increases linearly with the number of activated clients (since each activated client issues one query), while increasing $K_*$ is not able to provide a linear speedup in convergence rate. Consequently, **the marginal gain in convergence rate does not compensate for the linear increase in query cost, making $K_*=1$ the most query-efficient choice under this framework.**\n\nWe further empirically validate this in **Figure 2**, where different client selection strategies ($K_*=1,5,10,20,40$) are compared. The results show that activating a single client per round consistently achieves the optimal query efficiency, aligning with our theory. \n>**W3**: The Impact of Prompt Length\n\nWhile prompt length is not the primary focus, we agree that it is an important factor. As shown in Fig. 3, performance remains relatively stable across a moderate range of prompt lengths, with the average accuracy staying in $0.83\\pm0.005$. This suggests **no statistically significant performance drop** when increasing the prompt length.\n\nHowever, it is worth noting that very short or very long prompts introduce larger variance due to the properties of BDPL.\n1. Very short prompts lack sufficient capacity to instruct the LLM effectively.\n2. Very long prompts lead to a larger search space and increased training difficulty.\n\nBased on these observations, we selected a prompt length of 20 in our main experiments, as it offers a good trade-off, with the lowest variance. We will clarify this rationale in Appendix C.\n>**W4**: Compare with FedBPT\n\nThank you for raising this important point. We would like to clarify that **FedBPT is already included in our experiments under the name \"Fed-BBT\"**. *(For context, FedBPT (Sun et al. 2023) applies BBT (Sun et al. 2022) to FL, with adaptation designs to enhance its performance in FL.)* Specifically, our Fed-BBT baseline implements the FedBPT, where the CMA-ES parameters are aggregated across clients, instead of full model parameters. \n\nWe chose the name \"Fed-BBT\" (instead of \"FedBPT\") to help the reader compare methods intuitively. E.g., using **\"Fed-BBT vs. FedOne-BBT\"** immediately tells that they share the same backbone but differ in client activation mechanisms (Fed- vs. FedOne-). In contrast, naming \"FedBPT vs. FedOne-BBT\" requires additional prior knowledge to recognize that they are comparable.\n\nWe will revise Section 4.2 to explicitly state that Fed-BBT is adapted from FedBPT, with BBT as the underlying prompt tuning method.\n>**W4**: The rationale difference between FedBPT and ours\n\nThe main rationale difference between FedBPT and our work lies in the **research focus**: FedBPT focuses on adapting BBT to the federated learning setting, with specific designs to improve optimization performance across clients. In contrast, our work focuses on query efficiency, a crucial and underexplored challenge in federated black-box prompt learning with cloud-based LLMs.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "The notation in the paper is relatively complex, even for standard federated learning pipelines, as seen in Eq. (1) and (2). The authors could simplify the notation to enhance clarity and readability.", "experimental_designs_or_analyses": "Yes.", "relation_to_broader_scientific_literature": "Adapting federated learning to Black-Box Discrete Prompt Learning could further enhance prompt tuning performance by leveraging data from di\u0002verse sources, which provides the chance for multi-clients to collaboratively learn the large model in a parameter-efficient way.", "essential_references_not_discussed": "Yes.", "other_strengths_and_weaknesses": "The author provides detailed theory analysis and experimental comparison.\n\nWeakness.\n\n1.\tBackground Introduction\nThe rationale for employing Black-Box Discrete Prompt Learning in a federated setting is unclear. Given the popularity of Federated Prompt Learning, as demonstrated in prior works [1,2,3,4], why not leverage standard federated prompt learning approaches? The authors should refine the paper’s logical structure to better justify the proposed approach.\nReferences:\n\t•\t[1] Tao Guo et al., PromptFL: Let Federated Participants Cooperatively Learn Prompts Instead of Models—Federated Learning in the Age of Foundation Models, IEEE TMC, 2023.\n\t•\t[2] Guoyizhe Wei et al., Dual Prompt Tuning for Domain-Aware Federated Learning, arXiv preprint arXiv:2310.03103, 2023.\n\t•\t[3] Hongxia Li et al., Global and Local Prompts Cooperation via Optimal Transport for Federated Learning, CVPR, 2024.\n\t•\t[4] Hangchao Su et al., Federated Adaptive Prompt Tuning for Multi-Domain Collaborative Learning, AAAI, 2024.\n\n2.\tClient Selection Strategy\nThe motivation behind selecting only one client per round is unclear. Why not select multiple clients (e.g., two or three) to balance convergence speed and robustness? The rationale for this design choice should be explicitly discussed, and a convergence comparison with alternative selection strategies would strengthen the justification.\n\n3.\tPrompt Length Impact\nThe effect of prompt length is not sufficiently discussed. In Section C1, the authors examine different prompt lengths but do not explain why increasing the prompt length leads to worse performance. A detailed analysis of this phenomenon is needed.\n\n4.    Lack comparison. As far as I know, the FedBPT is the closest with your work. Could you explain the rationale difference and compare with them?\n\n[1] FedBPT: Efficient Federated Black-box Prompt Tuning for Large Language Models", "other_comments_or_suggestions": "Refer to weakness.", "questions_for_authors": "Refer to weakness.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "d4IhQAuGsY", "reviewer": "Reviewer_kF7d", "summary": "The authors propose FedOne to increase the query efficiency prompt learning method for cloud-based LLM, which activates only one client per round for optimal efficiency. The proposed method is shown to be effective by extensive experiments.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank you for your insightful comments and constructive criticisms. Your feedback has been invaluable in improving the quality and clarity of our manuscript. Below, we address the **Weaknesses and Essential Reference part**.\n\n>**W1**: Motivation behind optimizing query efficiency\n\nThe motivation for improving query efficiency is to **reduce the monetary cost and practical constraints associated with training federated black-box prompt learning models using cloud-based LLMs**. Each query to commercial APIs incurs usage fees and is subject to rate limits, both of which scale with the number of active clients and training iterations in Fed-BDPL. (e.g. GPT-4o is \\\\$2.5/1M input tokens, \\\\$10/1M output tokens, with rate limits depending on the usage tier.)\n\nOur goal is to make federated black-box prompt tuning cost-effective and scalable in real-world deployments. To that end, our analysis and design focus on the FL framework’s query behavior to cloud-based LLM, rather than how the LLM server handles concurrent API calls.\n\nWe will revise the introduction to emphasize the motivation behind optimizing query efficiency.   \n\n>**W2**: Experiment on heterogeneity\n\nWe provide an additional experiment to **demonstrate FedOne’s performance under varying levels of client heterogeneity**. Following prior works [1, 2], we simulate heterogeneity using a Dirichlet distribution with concentration parameters $\\alpha=0.5$ for medium heterogeneity and $\\alpha = 0.1$ for high heterogeneity. Each experiment is run three times independently. The complete results, including three figures corresponding to different heterogeneity levels, are available at this anonymous link ( https://anonymous.4open.science/r/ICML-Rebuttal-FedOne-649F/Converge2-Medium_Hetero.png ).\n\nThese experiments further support our theoretical results. **Activating a single client per round ($K_*=1$) consistently achieves the highest query efficiency, even in highly heterogeneous settings**. This is because the core intuition behind FedOne remains valid under the heterogeneous case: the query cost to the LLM increases linearly with the number of activated clients (since each client issues one query), while increasing K is not able to provide a linear speedup in convergence rate. Our original submission did not include these heterogeneity results because our primary goal was to theoretically identify and validate the optimal query-efficient strategy for Federated Black-box Prompt Learning. Heterogeneity is outside the core scope of this work.\n\nWe appreciate the reviewer’s suggestion, and we will add the heterogeneity experiments to the Appendix C. \n\n>**W3**: Fed-X result for Table 1\n\nThe corresponding result is provided at this anonymous link ( https://anonymous.4open.science/r/ICML-Rebuttal-FedOne-649F/kF7d_Fed-X_in_table1.jpg ), and it demonstrates that FedOne-X and Fed-X achieve comparable test metrics. We did not include the test metrics for Fed-X in the main text because the **primary goal of our research is to improve the query efficiency of Fed-BDPL; optimizing test accuracy is beyond the scope of this work**. Our theoretical results also specifically focus on convergence behavior and query efficiency, and do not deal with generalization errors.\n\nWe will include the results of Fed-X of Table 1 in Appendix C for completeness.\n\n>**Essential References**: Experiment comparison with FedBPT\n\nThank you for raising this important point. We would like to clarify that **FedBPT is already included in our experiments under the name Fed-BBT**. *(For context, FedBPT (Sun et al., 2023) applies BBT (Sun et al., 2022) to federated learning, with specific adaptations to enhance performance in FL.)* Specifically, our Fed-BBT baseline implements the FedBPT, where the CMA-ES parameters are aggregated across clients, instead of full model parameters. \n\nWe chose the name \"Fed-BBT\" (instead of \"FedBPT\") to help the reader intuitively compare methods within our framework. The naming convention **\"Fed-BBT vs. FedOne-BBT\"** makes it immediately clear that the two methods share the same prompt tuning backbone (BBT) but differ in client activation mechanisms (Fed- vs. FedOne-). In contrast, naming \"FedBPT vs. FedOne-BBT\" requires additional prior knowledge to recognize that they shared the same backbone.\n\nWe will revise Section 4.2 to explicitly state that Fed-BBT is adapted from FedBPT, with BBT as the underlying prompt tuning method.\n\n---\n**References**\n\n*[1] Lin, Tao, et al. \"Ensemble distillation for robust model fusion in federated learning.\" NeurIPS 33 (2020): 2351-2363.*\n\n*[2] Yurochkin, Mikhail, et al. \"Bayesian nonparametric federated learning of neural networks.\" ICML. PMLR, 2019.*", "claims_and_evidence": "Good.", "methods_and_evaluation_criteria": "Fair.", "theoretical_claims": "Good.", "experimental_designs_or_analyses": "Good.", "relation_to_broader_scientific_literature": "Good.", "essential_references_not_discussed": "This paper is cited by not referenced and compared in the experiments:\n[1] Sun, Jingwei, et al. \"Fedbpt: Efficient federated black-box prompt tuning for large language models.\" arXiv preprint arXiv:2310.01467 (2023).", "other_strengths_and_weaknesses": "Strengths:\n1. The authors provide theoretical analysis.\n2. The authors conduct experiments on multiple datasets.\n\nWeaknesses:\n1. The motivation behind query efficiency is unclear. What is the main purpose of optimizing it? I would assume that a server-deployed LLM would have sufficient system capacity and tailored algorithms to handle concurrent queries efficiently, such as through parallelization techniques.\n2. The authors make assumption on client heterogeneity but ignore the experiments for heterogeneous FL settings.\n3. In Table 1, what are the preformance of Fed-X, i.e., sampling multiple active clients?", "other_comments_or_suggestions": "Please refer to Strengths And Weaknesses.", "questions_for_authors": "Please refer to Strengths And Weaknesses.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This work addresses the overlooked query cost problem to cloud-based LLM-server in federated black-box prompt tuning. Targeting this problem, the author presents a counterintuitive yet well-justified finding (FedOne): activating only one client per round in Fed-BDPL leads to optimal query efficiency when interacting with cloud-based LLM servers. The paper identified an important but overlooked research problem in Federated black-box prompt tuning. The proposed solution has a solid theoretical foundation in optimizing the query cost. The core intuition is thoroughly discussed via theoretical result, intuition and empirical experiment.

A major concern raised by the reviewers was the impact of client heterogeneity. Specifically, three reviewers (BZU1, jBwD, kF7d) questioned how heterogeneity might affect the theoretical result. In response, the authors provided additional experiments and a detailed discussion on the intuition and trade-offs involved. Additional concerns were raised about the setting (vcwQ) and motivation (kF7d) of the research. The authors articulated the relevance of federated black-box prompt tuning and the importance of minimizing query cost when interacting with LLM APIs.

All reviewers raised their scores after the rebuttal and are in favor of acceptance. After carefully reviewing the paper and the authors' responses, I find the work to be solid, and the overall discussion to be thorough and convincing.
Decision: Accept (poster)