FedOne: Query-Efficient Federated Learning for Black-box Discrete Prompt Learning

Authors: Ganyu Wang, Jinjie Fang, Maxwell Juncheng Yin, Xi Chen, Boyu Wang, Bin Gu, Charles Ling
Primary area: foundation or frontier models, including LLMs
Keywords: Federated Learning, Black-box Prompt Learning, Large Language Model

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 *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.

Decision: reject
Reviewer scores: 5, 5, 5, 5

Reviews and discussion:
<thread>
creation date:
1730641313499

thread_type:
official_review

<thread_object>
creator: reviewer_xxa2

<content>
summary:
This paper presents a prompt tunning method in federated learning system, incorporated with black-box LLMs on the cloud. The method, FedOne, is proposed to reduce the cost on APIs usage. Theoretical analyses and experiments are conducted to support the main claims.

strengths:
- This work focuses on a new perspective of federated learning with LLMs, APIs usage cost reduction.
- The experiments' results seem positive, and the proposed FedOne's overall generalization ability is validated on various datasets.
- The discussion about the weaknesses of white-box prompt learning is interesting in the literature of federated learning.

weaknesses:
- Considering that the computational cost on the entire LLM of white-box prompt learning is transfer to the cost on APIs usage of black-box prompt learning, the overall motivation is questionable. More detailed cost-benefit analyses and related facts would explain this well.
- The claim and the proof of Corollary 2, which support the main idea that 1 client is needed, is naive and questionable either. $K_{*}$ is related to aggregation and overall variance (e.g., $\lambda$ in Assumption 3) due to the fact that larger $K$ reduce the aggregation noise in federated learning setting. Even if small stepsize can be use to minimize it, as claimed in Line 269, the training process in slower, leading more global epochs. Thus, the bound, from Line 1519 to 1595, seems vaccum and the claim do not make sense. A more comprehensive analysis could help, which takes into account the trade-offs between reduced aggregation noise from larger $K$ and the increased number of global epochs.
- In the reported results, Fune-tuning works better than FedOne. A more detailed analysis of this result and the compatibility of the two methods would help to explain the underlying reasons.

questions:
- Can $\lambda$ the gradient diversity and $K$ be decoupled in the analyses?
- Are there any facts supporting that cost on a local LLM is larger than cost on APIs usage? Could you please provide a more detailed cost-benefit analysis comparing the computational costs of white-box prompt learning v.s. the API usage costs of black-box prompt learning?
- Are there scenarios where FedOne might be preferable despite lower performance? Could you please discuss potential improvements to FedOne that could help close the performance gap with fine-tuning.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730645378902

thread_type:
official_review

<thread_object>
creator: reviewer_qmks

<content>
summary:
This paper proposes a more cost-efficient federated learning framework called **FedOne** to optimize query efficiency when interacting with the cloud large language model (LLM). A convergence analysis for Federated BDPL is also been explored in this paper. Extensive experiments demonstrate the effectiveness of the proposed method.

strengths:
1. Improving the query cost efficiency is important in federated learning scenarios. The proposed method is simple and reasonable with a theoretical guarantee. 

2. The paper is well-written and easy to understand.

weaknesses:
1. More details on optimizing $K_{*}$ from "$>1$" to "$=1$" for improving query efficiency in Section 3.2 should be provided, as it is the most important part in the whole paper. According to the current version, the proposed method is too simple and too straightforward.  The effect of the value of $K_{\*}$ on model convergence should be also analyzed in this section.

2. The experiment does not contain related baselines to compare with, such as [1],[2]. As a result, it is very hard to evaluate whether the **FedOne** reflects the SOTA performance.

[1] Black-box Prompt Tuning for Vision-Language Model as a Service. IJCAI 2023.

[2] Fedbpt: Efficient federated black-box prompt tuning for large language models. ICML 2024.

3. It is unclear whether the number of clients has an effect on the performance of FedOne.

questions:
Please refer to the Weakness section.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730709097108

thread_type:
official_review

<thread_object>
creator: reviewer_4cvb

<content>
summary:
This paper focuses on federated Black-Box Discrete Prompt Learning (BDPL) and offers the first theoretical analysis of this approach, uncovering valuable insights from the findings. Specifically, the authors demonstrate that utilizing FedAvg with a single client in each training round yields the highest query efficiency. The numerical results corroborate this theoretical conclusion, reinforcing the validity of the proposed method.

strengths:
1. The paper presents a convergence error analysis of federated BDPL.
2. Building on these theoretical results, the authors optimized federated BDPL by strategically determining the number of participating clients for each training round.

weaknesses:
1. The paper builds upon an existing federated BDPL framework.
2. The rationale behind the FedONE algorithm is not adequately explained.

questions:
1. The rationale behind the FedONE algorithm lacks a proper explanation. Specifically, if I understand correctly, FedONE aggregates only one client in each round. Does this imply that, in each round, the clients will set their local model parameters $\alpha$ to match those of the selected client? Intuitively, this could lead to significant fluctuations in model training, particularly when the local data across clients are highly heterogeneous. Further clarification on how to interpret and address this phenomenon is needed.

2. Additional experiments should be included to assess the impact of data heterogeneity across clients.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730763528154

thread_type:
official_review

<thread_object>
creator: reviewer_pv8j

<content>
summary:
This paper addresses Black-box Discrete Prompt Learning (BDPL) in Federated Learning and proposes FedOne. The proposed FedOne selects one client at each round, and the selected client updates the sample probability for each token at different positions. This work provides a theoretical analysis and shows the convergence rate of the proposed algorithm. Extensive experiments show the remarkable performance of the proposed work.

strengths:
1. This work proposes an interesting solution to addressing BDPT in federated learning. 
2. The work discloses an interesting discovery that sampling one client at every round can provide remarkable performance. 
3. The experience is conducted on the GLUE dataset and two pretrained models, i.e., Roberta and GPT-3.5. And the experimental results are promising.

weaknesses:
1. The proposed method requires each client to store a size of $n \times N$ $\alpha$s. Nowadays, the pretrained embedding layer of an LLM gets larger, e.g., from 32k in LLaMA-2 to 128k in LLaMA-3. Therefore, it costs a large amount of computation and communication overhead. 
2. This paper does not explicitly discuss the effect of $n$. This should be part of the ablation study. 
3. The review of FL is insufficient. I see there are a number of works addressing LLM fine-tuning under federated learning. The authors should concretely discuss why the existing works are infeasible. 
4. $\eta^*$ goes to an order of $O(\sqrt{T})$. This sounds really weird. I think the author should justify the reason.

questions:
See **Weaknesses**.
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper proposes a novel method for federated black-box discrete prompt learning. The paper analyses the convergence in terms of the number of LLM queries, and shows that sampling a single client in every iteration is the optimal choice to achieve the best sample efficiency in terms of the number of LLM API queries.

The reviewers commended that the paper provides a novel perspective of focusing on the LLM API query efficiency in federated prompt learning, and the proposed theory-inspired approach of sampling one client in every round is interesting.

However, the reviewers also expressed important concerns about the paper, which I agree with. For example, the theoretical analysis focusing on the API query efficiency may have overlooked the noise from sampling a small number of clients in every round. As a result, the resulting conclusion that sampling a single client in every round is optimal may have been misled. In addition, the resulting algorithm may be overly simple. The fact that the theoretical results do not depend on the number of clients also seem a little unconventional to me. Also, the important factor of heterogeneity is not considered yet in analysis and algorithm.

As a result, the paper still has room for improvement. I believe a careful revision of the analysis and the algorithm would greatly benefit the paper, and hence recommend rejection.