Dual Variance Reduction with Momentum for Imbalanced Black-Box Discrete Prompt Learning

We appreciate the time and effort put into reviewing our manuscript. Please find our responses to your concerns below:

weakness 1: Thank you for your valuable feedback. Let us reiterate the technical novelty of our paper.

1. We acknowledge that our work is built upon the efforts of Zhangtong [1], who established a distribution optimization paradigm and introduced a policy gradient-based discrete prompt learning framework. We choose to follow it because it is one of the most influential frameworks in discrete prompt learning; however, we do not simply apply this framework in a straightforward manner. Despite the framework being a notable contribution, it also has significant shortcomings:

• The explicit formulation for gradient estimator in [1] is flawed.

• The policy gradient estimator used in the paper is biased, which introduces instability into the optimization process.

  We resolve these significant shortcomings, which constitutes a key novelty of our work, as detailed below:

• We correct the error in the explicit formulation for the gradient estimator in [1], with the detailed introduction provided in Appendix A of our paper

• We first to provide unbiased gradient estimator leading to a more stable optimization process.

2. We do not simply combine existing techniques; instead, we carefully consider the suitability of various variance reduction techniques for imbalanced black-box prompt learning. Various variance reduction techniques, such as SVRG, require computing the full gradient at checkpoints using a giant batch of data, which is computationally expensive for black-box optimization and contradicts the simplicity and efficiency principles of prompt learning. Therefore, we ultimately adopt the STORM technique, which avoids the aforementioned issues and effectively reduces the dual variance.

3. Additionally, our paper is the first to address the challenge of prompt learning in imbalanced scenarios, which more closely reflect real-world applications. Classification tasks in such imbalanced settings hold significant practical importance. For instance, sensitive speech detection stands as a prime example of the profound and practical applications of classification tasks in real-world scenarios and inherently poses a natural data imbalance challenge [2]. Furthermore, cutting-edge research [3] has turned its focus to utilizing LLMs for addressing deception detection, a task that inherently involves imbalanced classification. This research has culminated in the release of a series of novel high-quality datasets for the domain, highlighting the significance and industry-wide interest in advancing LLM-driven solutions for classification tasks under imbalanced data conditions.

weakness 2: Thanks for your suggestion. In the revised version, we have included more experimental results to verify the effectiveness of mDP-DPG. Specifically, we add the BB (Burfoot and Baldwin dataset) [2], Job Scams and SMS datasets [3] to show performance of our method in real-world applications. In addition, we include comparisons with the recent baselines, APE [4] and EvoPrompt [5]. In this experiment, we use GPT-4 to adapt our method to a true black-box model. The results are presented in the table below. For more details, please refer to the Appendix D.6 in the revision of our paper.

[1] Diao et al., Black-box prompt learning for pre-trained language models.

[2] Burfoot et al., Automatic Satire Detection: Are You Having a Laugh?

[3] Boumber et al., Domain-agnostic adapter architecture for deception detection: Extensive evaluations with the difraud benchmark.

[4] Zhou et al., Large language models are human-level prompt engineers.

[5] Guo et al., Connecting large language models with evolutionary algorithms yields powerful prompt optimizers.

Dear reviewer, thank you again for your time and effort put into reviewing our manuscript. Please let us know if our responses have addressed your concerns. If you have remaining concerns, please don't hesitate to let us know and we are happy to address them. Thank you!

Dear Reviewer xsUR,

Happy Thanksgiving!

We greatly appreciate your insights, which have significantly improved our work. We hope that our responses and summary have adequately addressed your concerns.

If you feel we've successfully addressed your points, we would be grateful for your support. Should you have any further questions, please don't hesitate to ask.

Thank you again for your time and expertise in reviewing our work.

Dear Reviewer xsUR,

Thank you once again for your time and effort in reviewing our paper. As the discussion phase is nearing its end, we kindly request that you confirm whether our responses have addressed your concerns. We would appreciate it if you could fulfill your responsibilities as a reviewer by providing your feedback.

Sincerely,

The Authors

Dear Reviewer xsUR,

Thank you for your support of our article. We acknowledge that our work follows these two works. However, unlike these works, the main contributions of our work are as follows:

• Our approach is the first to discuss how to learn discrete prompts for imbalanced data in LLM, which is a challenging task.
• Our method provides a comprehensive theoretical analysis, whereas Zhongtong et al. in [1] did not offer any theoretical analysis results.
• Following your suggestions, we conducted extensive experiments on the more realistically challenging GPT-4 model, and these experimental results demonstrate that our method has a performance advantage over BDPL [1].

We once again thank you for the constructive review comments that have helped further improve the quality of our article and for your conscientious response.

[1] Diao et al., Black-box prompt learning for pre-trained language models.

We appreciate the time and effort put into reviewing our manuscript. Please find our responses to your concerns below:

weakness & question 1: Thanks for your valuable suggestion. In the revised version, we provide more discussion on how the VR-DPGE and STORM strategy can reduce the variance of gradient estimation and on what the theorem indicates about the resulting prompts. Then we define previously unclear notations. You can also find the relevant content below:

• Discussion about VR-DPGE: We implement VR-DPGE, which incorporates a baseline subtraction term to reduce variance [1]. Compared to the high variance of loss values, the difference between the loss value and the baseline term has a lower variance, which facilitates more stable gradient estimation.

• Discussion about STORM strategy: The content of Lemma 4 demonstrates that the momentum-based strategy effectively reduces the dual variance. The bound in Lemma 4 contains terms that decay with the momentum parameter $\theta_t$, showing that variance of the moving average $\boldsymbol{m}_{t+1}$ is systematically reduced over iterations, leading to a more stable and accurate approximation of the true gradient.

• Discussion about theoretical results: The theorems demonstrate that the proposed framework, with variance-reduction techniques and momentum-based updates, ensures convergence towards a prompt distribution that minimizes the empirical risk of the pairwise AUC loss. This implies that the learned prompts are expected to be optimal in terms of performance for the downstream task under the given black-box constraints.

• Definition of $T^{(k)}$: $T^{(k)}$ represents the $k$-th prompt obtained from $I$ prompt samplings.

• Definition of $proj_{\mathcal{C}}$: $proj_{\mathcal{C}}$ in the update step is a projection function that projects updated prompt distribution to the constraint set $\mathcal{C}$ following [2].

It is worth mentioning that the unbiased VR-DPGE estimator is first proposed in our paper, making it one of the key novelties of our work. As for the projection function $proj_{\mathcal{C}}$, we follow the approach in [2], and therefore is not elaborated upon in detail in the paper.

question 2: Thank you for pointing out this concern. The assumption of independent sampling from the marginal distribution is a simplification that facilitates optimization in black-box settings, especially when the goal is to learn discrete prompts effectively. In fact, each probability distribution in the final solution does not ideally converge to a delta distribution. In order to obtain a stable prompt, following the approach in [2], the token at a given position in the final prompt is selected as the token with the highest probability in its corresponding probability distribution.

question 3: Thanks for your question. For Manual Prompt, we attribute this phenomenon to the fact that Tables 1 and 2 in the original paper (Tables 1 and 7 in the revision) represent artificially constructed imbalanced scenarios, which lead to a deviation between the data distribution used in the experiments and the original distribution of the dataset. This deviation may cause the patterns learned by LLMs during pretraining to fail on the artificially constructed imbalanced data distribution. For BBT, BDPL, and GAP3, we believe the performance collapse of prompts learned on imbalanced data is due to the lack of techniques in these methods to handle imbalanced data, leading to the preference for majority class samples.

[1] Greensmith et al., Variance reduction techniques for gradient estimates in reinforcement learning.

[2] Diao et al., Black-box prompt learning for pre-trained language models.

Dear Reviewer pkzH,

Thank you once again for dedicating your time and effort to reviewing our manuscript. After our comprehensive replies and revisions, other reviewers have expressed increased support for our work and have improved their scores. If our responses meet your expectations, we hope you will consider offering further support for our work.

Moreover, allow me to outline the additions we made during the rebuttal period:

Importance of the scenario: We discuss the practical significance of classification tasks on imbalanced data and provide the example of recent advancement in the research community. For further details, please refer to our response to reviewer Ry7Y.

Additional experiments: Based on the suggestion of reviewer Ry7Y and xsUR, we add experiments on real-world tasks using the GPT-4 and compare our method with recent related works. Please refer to the Appendix D.6 in the revision for details.

Reiteration of contributions: To aid in better understanding of the paper, we have reiterated the contributions, which are threefold: 1. Theoretical and technical improvements to address the limitations of the original framework. 2. A proposed approach for reducing dual variance. 3. A practical perspective (imbalanced data) on the application of prompt learning. For further details, please refer to our responses to reviewer Ry7Y and xsUR.

Justification of the assumption: To address the concerns of reviewer 4JE3 and you, we explain the justification of the assumption that the token distributions are independent in our response to them.

Extension to multi-class problem: We have previously addressed the extension to multi-class tasks in the original paper, which can be found in Appendix D.1 of original paper (Appendix D.2 of the revision).

Clarification of distribution convergence: To address the concerns of reviewer 4JE3 and you, we clarify the distribution convergence effect in the experiments and explain how a stable final prompt is obtained.

Explanation of how the described problem is addressed: Based on your suggestion, we provide more discussion on how the VR-DPGE and STORM strategy can reduce the variance of gradient estimation and on what the theorem indicates about the resulting prompts.

Discussion on experimental results: In our response to you, we have added a discussion on the original experimental data and observations.

We appreciate the time and effort you have invested in reviewing our work. Your comments have significantly strengthened our submission, and we hope that our responses address your concerns comprehensively.

Thank you again for your thoughtful feedback and consideration.

Best regards,

The Authors

We appreciate the time and effort put into reviewing our manuscript. Please find our responses to your concerns below:

weakness 1 & question 1: Thank you for pointing out this concern. The assumption of independent sampling from the marginal distribution is a simplification that facilitates optimization in black-box settings, especially when the goal is to learn discrete prompts effectively. While this approach does not explicitly capture potential semantic relationships between tokens, we believe this assumption aligns with the broader objective of black-box optimization: improving downstream task performance without imposing additional constraints from token-level semantic relations. We acknowledge that this assumption may limit interpretability. Exploring techniques to model token relationships explicitly, while preserving the efficiency and simplicity of the current framework, is an exciting avenue for future work. Thank you for highlighting this potential direction.

weakness 2 & question 2: Thanks for your question. Indeed, we have previously addressed the extension to multi-class tasks in the original paper, which can be found in Appendix D.1 of original paper (Appendix D.2 of the revision). Specifically, our method can be extended to multi-class datasets using micro-averaging. This involves calculating the AUC loss for each class against all others and average them over all classes.

question 3: Really appreciate this question. In fact, each probability distribution in the final solution does not ideally converge to a delta distribution. In order to obtain a stable prompt, following the approach in [1], the token at a given position in the final prompt is selected as the token with the highest probability in its corresponding probability distribution.

[1] Diao et al., Black-box prompt learning for pre-trained language models.

We appreciate the time and effort put into reviewing our manuscript. Please find our responses to your concerns below:

weakness 1: Thank you for pointing out this important consideration regarding the scenario. We acknowledge that generative tasks have emerged as a pivotal focus in contemporary research. Nevertheless, classification tasks continue to hold paramount significance in the exploration of large language models, owing to their indispensable role in a wide array of practical applications, particularly in the context of more practical scenarios involving imbalanced data. Sensitive speech detection stands as a prime example of the profound and practical applications of classification tasks in real-world scenarios and inherently poses a natural data imbalance challenge [1]. Furthermore, cutting-edge research [2] has turned its focus to utilizing LLMs for addressing deception detection, a task that inherently involves imbalanced classification. This research has culminated in the release of a series of novel high-quality datasets for the domain, highlighting the significance and industry-wide interest in advancing LLM-driven solutions for classification tasks under imbalanced data conditions. To demonstrate the superiority of our method and highlight its significance and performance in practical applications, we have conducted additional experiments on the aforementioned datasets. For detailed information, please refer to our response to weakness 2.

weakness 2: Thanks for your suggestion. In the revised version, we have included more experimental results to verify the effectiveness of mDP-DPG. Specifically, we add the BB (Burfoot and Baldwin dataset) [1], Job Scams and SMS datasets [2] to show performance of our method in real-world applications. In addition, we include comparisons with the recent baselines, APE [3] and EvoPrompt [4]. As for ZOPO [5], since we can not access its source code, evaluating this method within the limited time available is challenging, and thus we have not included it in our comparisons for now. In this experiment, we use GPT-4 to adapt our method to a true black-box model. The results are presented in the table below. For more details, please refer to the Appendix D.6 in the revision of our paper.

[1] Burfoot et al., Automatic Satire Detection: Are You Having a Laugh?

[2] Boumber et al., Domain-agnostic adapter architecture for deception detection: Extensive evaluations with the difraud benchmark.

[3] Zhou et al., Large language models are human-level prompt engineers.

[4] Guo et al., Connecting large language models with evolutionary algorithms yields powerful prompt optimizers.

[5] Hu et al., Localized Zeroth-Order Prompt Optimization.

Dear reviewer, thank you again for your time and effort put into reviewing our manuscript. Please let us know if our responses have addressed your concerns. If you have remaining concerns, please don't hesitate to let us know and we are happy to address them. Thank you!

Thank you again for your time and effort dedicated to reviewing our paper. To better address your concerns, let us reiterate the contribution of our paper.

1. Our work is built upon the efforts of Zhangtong [1], who established a distribution optimization paradigm and introduced a policy gradient-based discrete prompt learning framework. We choose to follow it because it is one of the most influential frameworks in discrete prompt learning; however, we do not simply apply this framework in a straightforward manner. Despite the framework being a notable contribution, it also has significant shortcomings:

• The explicit formulation for gradient estimator in [1] is flawed.

• The policy gradient estimator used in the paper is biased, which introduces instability into the optimization process.

• [1] lacks a theoretical analysis of algorithmic convergence, indicating that the framework is not theoretically comprehensive.

We resolve these significant shortcomings, which some of the key innovations in our work, as detailed below:

• We correct the error in the explicit formulation for the gradient estimator in [1], with the detailed introduction provided in Appendix A of our paper

• We first to provide unbiased gradient estimator leading to a more stable optimization process.

• We have established a unique theoretical analysis framework for black-box discrete prompt learning with policy gradient, which makes the original framework's theoretical comprehensive.

2. We do not simply combine existing techniques; instead, we carefully consider the suitability of various variance reduction techniques for imbalanced black-box prompt learning. Various variance reduction techniques, such as SVRG, require computing the full gradient at checkpoints using a giant batch of data, which is computationally expensive for black-box optimization and contradicts the simplicity and efficiency principles of prompt learning. Therefore, we ultimately adopt the STORM technique, which avoids the aforementioned issues and effectively reduces the dual variance. The content of Lemma 4 demonstrates that STORM strategy effectively reduces the dual variance. The bound in Lemma 4 contains terms that decay with the momentum parameter $\theta_t$, showing that variance of the moving average $\boldsymbol{m}_{t+1}$ is systematically reduced over iterations, leading to a more stable and accurate approximation of the true gradient.

3. Additionally, our paper is the first to address the challenge of prompt learning in imbalanced scenarios, which more closely reflect real-world applications. Classification tasks in such imbalanced settings hold significant practical importance. For instance, sensitive speech detection stands as a prime example of the profound and practical applications of classification tasks in real-world scenarios and inherently poses a natural data imbalance challenge [2]. Furthermore, cutting-edge research [3] has turned its focus to utilizing LLMs for addressing deception detection, a task that inherently involves imbalanced classification. This research has culminated in the release of a series of novel high-quality datasets for the domain, highlighting the significance and industry-wide interest in advancing LLM-driven solutions for classification tasks under imbalanced data conditions. Our latest supplementary experiments on GPT-4 indicate that our method has advantages in handling the aforementioned tasks.

[1] Diao et al., Black-box prompt learning for pre-trained language models.

[2] Burfoot et al., Automatic Satire Detection: Are You Having a Laugh?

[3] Boumber et al., Domain-agnostic adapter architecture for deception detection: Extensive evaluations with the difraud benchmark.

Dear Reviewer Ry7Y,

Happy Thanksgiving!

We greatly appreciate your insights, which have significantly improved our work. We hope that our responses and summary have adequately addressed your concerns.

If you feel we've successfully addressed your points, we would be grateful for your support. Should you have any further questions, please don't hesitate to ask.

Thank you again for your time and expertise in reviewing our work.

Dear Reviewer Ry7Y,

Thank you once again for your time and effort in reviewing our paper. As the discussion phase is nearing its end, we kindly request that you confirm whether our responses have addressed your concerns. We would appreciate it if you could fulfill your responsibilities as a reviewer by providing your feedback.

Sincerely,

The Authors

Dear Reviewer Ry7Y,

Thank you once again for dedicating your time and effort to reviewing our paper. The other reviewers have already affirmed the value of our work, and we believe we have sufficiently addressed your concerns. As the discussion phase is nearing its end, we hope you can further reconsider your evaluation of our manuscript.

Sincerely,

The Authors