Online Black-Box Prompt Optimization with Regret Guarantees under Noisy Feedback
Authors: Jinjie Fang
Runwen You
Wanli Shi
Wenkang Wang
Ganyu Wang
Haozhen Zhang
Yi Chang
Bin Gu
Venue: ICLR 2026 Poster (2026)
Keywords: Black-Box Prompt Optimization
Online Learning
Generative Al
Primary area: foundation or frontier models, including LLMs

Abstract: Generative AI excels in various tasks through advanced language modeling techniques, with its performance heavily influenced by input prompts. This has driven significant research into prompt optimization, particularly in commercial generative AI platforms, where prompt optimization is treated as a black-box optimization problem. Most existing research on black-box prompt optimization primarily focuses on offline learning and overlooks the randomness in outputs. However, in real-world applications, black-box prompt optimization typically operates in an online learning setting, which remains largely unexplored, especially given the noisy outputs. To address these challenges, we propose an \textbf{A}daptive \textbf{O}nline \textbf{Z}eroth-order \textbf{P}rompt \textbf{T}uning (AOZPT) approach which integrates zeroth-order optimization with online learning in the non-convex setting. Specifically, we developed an uncertainty-scale-adjustment mechanism to mitigate the noise inherent in generative AI and the high variance associated with zeroth-order estimates. We conducted a comprehensive regret analysis of the AOZPT approach, and the results indicate that sublinear regret convergence is achievable. Extensive generative experiments demonstrate that AOZPT outperforms existing black-box prompt tuning methods, particularly in terms of stability in online scenarios.

Published as a conference paper at ICLR 2026
ONLINE BLACK-BOX PROMPT OPTIMIZATION WITH REGRET GUARANTEES UNDER NOISY FEEDBACK
Jinjie Fang* Ganyu Wang 2
Runwen You"
Wanli Shi
Wenkang Wang' Bin Gu
Haozhen Zhang*
Yi Changl
School of Artificial Intelligence, Jilin University, China Western University. Canada
3 *International Center of Future Science, Jilin University, China
4 'Engincering Research Center of Knowledge-Driver Human-Machine Intelligence, MOE, China
[wanli_shh yichang, gubin jjl.. [fangij24, runwen25, wangwk25, haczhen23) Aaczien23)@mails @mails jlu. edu. cn
jlu. edu. cn (gwang382) // ca
ABSTRACT
Generative AI excels in various tasks through advanced language modeling tech- niques, with its performance heavily influenced by input prompts. This has driven significant research into prompt optimization, particularly in commercial generative Al platforms, where prompt optimization is treated as black-box optimization problem. Most existing research on black-box prompt optimization primarily focuses on offline learning and overlooks the randomness in outputs. However, in real-world applications, black-box prompt optimization typically operates an online learning setting, which remains largely unexplored, especially given the noisy outputs. address these challenges, we propose an Adaptive Online Zeroth-order Prompt Tuning (AOZPT) approach which integrates zeroth-order optimization with online learning in the non-convex setting. Specifically, we de- veloped mecrrainty-scalee scalc-adjustment mechanism to mitigate the noise inherent in generative AI and the high variance associated with zeroth-order estimates. We conducted comprehensive regret analysis of the AOZPT approach, and the results indicate that sublinear regret convergence is achievable. Extensive generative ex- periments demonstrate that AOZPT outperforms existing black-box prompt tuning methods, particularly in terms of stability in online scenarios.
INTRODUCTION
Generative artificial intelligence (AI) leverages advanced contextual understanding and language modeling techniques to excel across wide range of tasks (Feuerriegel et al., 2024 Brynjolfsson et al. 2023 Epstein et al.) 2023). These capabilities facilitate the generation of high-quality text, code, and multimodal content, with applications financial analysis. medical diagnosis support, and automated content creation (Li et al. 2023] Zhou et al. 2024 Ji et al.) (024). The generative process partially influenced by the model inherent randomness, which arises from random sampling, non-deterministic training elements, and variations in random seed initialization (Das & Varshney 2022 Liu et al., 2024a Gandee et al.) 2024). These mechanisms enhance flexibility, allowing the model generate diverse and creative content across various tasks and contexts.
Generative Al achieves diverse functionalities primarily through fine-tuning (FT) or prompt tuning (PT). FT involves adjusting all model weights to optimize performance for specific tasks; however, demands substantial computational resources, large datasets, and often leads to reduced generalization
and increased deployment complexity (Kenton & Toutanova 2019 Liu 2019 Liu al.. 2021). In contrast, PT updates only a small subset of parameters, significantly reducing computational and data requirements while preserving the model's inherent knowledge and adaptability (Lester al. 202T
Zhang et al., 2024 Gao et al. 2020). Traditional white-box prompt tuning methods rely on access to model's intermediate representations (Liu et al. 202T Li Liang
2021 Zhou al. 2022). while
Corresponding Author.

---

Published as a conference paper at ICLR 2026
black-box prompt tuning becomes essential when intermediate representations inaccessible (Sun) jet al,, 2022; Diao et al.) 2022; Cheng et al. 2023; Liu et al., [2024b] Wu et al. 2024). Notably, black- box prompt tuning enables the optimization of input prompts without requiring detailed understanding of the model's internal mechanisms.
Current research black-box prompt tuning predominantly focuses offline scenarios using pre- established datasets. For example, [Sun et al. (2022) proposed BBT, an offiin method that optimizes continuous prompts in a low-dimensional subspace using random projection and derivative-fre optimization techniques. Similarly, Deng et al. (2022) introduced RLPROMPT, which employs reinforcement learning to optimize discrete text prompts within an offline framework. Furthermore, Diao et al. (2022) presented BDPL, an offline method for adapting large pre-trained language models through the optimization of discrete prompts without accessing model parameters. For gradient- based optimization, [Zhan et al. (2024) developed the Zeroth-Order Tuning algorithm, designed for offline black-box prompt tuning using inference APIs exclusively. Additionally, (Zhang et al.) (2024) proposed zeroth-order prompt tuning framework that addresses high-dimensional prompt optimization challenges in offline settings through subspace learning and selection strategies. Hu et al. 2024) introduced the ZOPO method, designed for offline learning scenarios, which effectively optimizes discrete prompts through input domain transformation, WTTK-GP-enhance derivative optimization, and metaaiitt-inffommee local exploration. Collectively, these methods demonstrate flexibility and strong performance, providing effective solutions for offline black-box prompt tuning.
Offline black-box prompt tuning methods lack adaptability to dynamic data changes, posing signifi- cant limitation for applications that require real-time updates. For example, in real-time customer support systems, online learning dynamically refines prompts based on ongoing user interactions, improving response accuracy and relevance (Upadhyaya] 2024). Similarly, in e-commerce platforms, online learning analyzes user browsing behavior in real time to adjust recommendation content, providing more personalized and precise services (Nkwo et al. 2018). In such scenarios, which demand real-time interaction or feedback, offline black-box prompt optimization often ineffective or impractical. In contrast, online learning continuously optimizes prompts by integrating streaming data, enabling systems to dynamically adapt to evolving information. As a result, online black-box prompt tuning is more suitable for real-time applications, particularly those requiring rapid responses and dynamic adjustments, demonstrating substantial potential for practical implementation.
Nevertheless, implementing black-box prompt tuning for generative AI in online learning contexts presents notable challenges. First, the inherent randomness in generative Al models, while beneficial for enhancing content diversity, is often perceived noise. This noise introduces output uncertainty, complicating prompt optimization in online black-box scenarios. Second, conventional black-box prompt optimization techniques, such Bayesian optimization (Shahriari et al.) 2015) evolutionary algorithms
et al. 2014),, require frequent surrogate model updates or the evaluation of a large number of samples. These requirements render them impractical for online learning scenarios (Sun et al. 2022; Zhang et al. 2024 Chen et al.) [023 Zhao et al.) 2023 contrast, gradient estimation-
Guo et al. 2023 Lange al. (2024).
methods, particularly zeroth-order optimization (ZOO), offer more efficient, flexible, and robust framework for online black-box prompt tuning Zhan et al. 2024 Hu al., 2024 Zhhng al. 2024). However, ZOO approximates gradients using a limited number of function eva evaluations, often leading to high variance
during the search process (Gu et al. 2016 Liu et al.) 2018)] Feng & Wang 2023). This variance further exacerbates uncertainty in optimization, increasing its complexity.
To address the challenges of noise from gener- ative Al and high variance in zeroth-order es- timates in online black-box prompt optimiza- tion, we propose Adaptive Online Zeroth-order Prompt Tuning (AOZPT), the first method to combine black-box prompt tuning with online learning. In simulated streaming data scenarios, AOZPT continuously adjusts prompts for gen- crative AI based on incoming data, maintaining optimal performance throughout the learning process. Furthermore, to mitigate uncertainties arising from zeroth-order variance and genera-
Uncorsiinty scale adjustmour
Difforent ancertainty scaley
Noise
Varrinne
Reduce uncertainty
Increase uncertainty
X Eviimatd gradiens
Figure 1: The adaptive uncertainty scale adjust- ment mechanism.
2

---

Published as a conference paper at ICLR 2026
tive Al noise, incorporate adaptive uncertainty scaling mechanism (Figure into the update process, effectively reducing gradient uncertainty.
The key contributions are summarized as follows:
This paper proposes the AOZPT approach, the first to integrate black-box prompt tuning with online learning. AOZPT dynamically optimizes prompts based on streaming data, maintaining optimal performance throughout continuous learning.
The AOZPT approach incorporates an adaptive uncertainty scaling mechanism to mitigate the noise in outputs of generative AI and the high variance arising from zeroth-order gradient estimates.
We present a formal regret analysis of AOZPT in non-convex settings, demonstrating that sublinear regret convergence is achievable. Additionally, we evaluate the AOZPT method on both text-to-text and to-maee- tasks, with results consistently showing that AOZPT outperforms baseline models.
2
RELATED WORKS
2.1 WHITE-BOX AND BLACK-BOX PROMPT TUNING
Prompt tuming, powerful paradigm originating in natural language processing, has recently gained significant attention. This approach focuses on designing and optimizing prompts to adapt models for diverse downstream tasks. Early efforts in prompt tuning relied on manually crafted prompts to guide language models toward desired outputs (Petroni et al.. (019). However, this method both time-intensive and resource-demanding (Jiang et al. 2020). To address these challenges, researchers developed automatic prompt tuning techniques, which optimize prompts by learning effective representations (Shin al. 2020). Automatic prompt tuning can be broadly categorized into two types: white-box and black-boy prompt tuning. White-box prompt tuning assumes full access to the model, enabling direct interaction with its parameters and gradients (Li & Liang 202T Liu et al. 2021: Lester et al., (021). Conversely, when access to a model's internal mechanisms districted-sude as when language model provided as a service through an APl-black- box prompt tuning becomes necessary. Recent advancements in black-box prompt tuning have introduced methods such as reinforcement learning (Deng et al. (022), policy gradient (Diao et al., 2022), and genetic algorithms (Zhang et al. 2024 Sun al. 2022). These methods are highly versatile, accommodating a wide range of tasks and models without requiring any modifications to the underlying model architecture.
2.2 ONLINE NONCONVEX LEARNING
Online learning is paradigm where models are continuously updated in response to new data, as opposed to being trained in batch mode on static datascts. Traditional approaches to online learning have primarily relied shallow models to address convex optimization problems. However, recent research has increasingly focused on non-convex scenarios. For instance, Hazan et al. (0077) introduced the concept of local regret online learning. Unlike the standard regret used in online convex optimization, local regret is confined a sliding window, making it "local" in nature. AAyore et al. (2019) extended this concept by proposing dynamic local regret to address concept drift in data streams. Their method incorporates an exponential average over the sliding window of local regret and leverages past gradients within the window, enhancing computational efficiency. Gao et al. (2020) presented an online normalized gradient descent algorithm for cases where gradient information is available and a bandit online normalized gradient descent algorithm for scenarios where only loss function values can be accessed. Additionally, Roy et al.] (2019) explored the application of Gaussian Bandit Gradient Descent to zeroth-
alternative traditional regret analysis in non-convex
online non-convex optimization. Kaya et al. (2023) proposed communication-efficii order distributed online optimization algorithm, which integrates an eтror feedback mechanism with federated learning framework to enable multi-agent target tracking and optimization in communication con.riiinnnonttiinedddeee. environments. Most recently, Hua et al.] (2024) proposed a residual feedback-base single-point distributed online non-convex optimization algorithm.
3

---

Published as a conference paper at ICLR 2026
3 METHOD
3.1 ONLINE BLACK-BOX BOX PROMPT OPTIMIZATION
Online black-box prompt tuning: In an online learning scenario, stream sample ç is received at each round & = ",.., - comprising an input sentence x' and its corresponding true label y². i.e. ç = (x', y²) Let represent the black-box generative model and l denote the loss function. The online black-box prompt tuning task involves minimizing the objective function ft by optimizing the prompt Φ:
8' =
(1)
Based on the preceding discussion, mainstream black-box optimization methods, such as Bayesian and evolutionary algorithms, are impractical in online learning scenarios, necessitating gradient-based methods. However, directly applying gradient- maddentt-bsedd methods to optimize é presents challenges, as ø represents natural language sentence involving numerous discrete structures, rendering gradient- based methods unsuitable.
In-context Learning Prompt Generator To address the challenge of optimizing discrete prompts with gradient- based methods, we employ the INSTRUCTZERO framework for prompt genera- tion (Chen et al. 2023). Within this framework, optimize low-dimensional continuous vector 2' RR referred to as soft prompt, to generate high-quality discrete semantic instruction ø', represent a frozen open-source LLM as J and use random projection matrix A IR Pxd (D > d) to project the oow-dimesiiona vector 2' E IR into the high- high-dimensional embedding space IR D of F.. The resulting concatenated embedding is then input into F for generating semantic prompts. This process can be mathematically expressed as follows:
known as hard prompt. Specifically,
8' = F (Az' + do: E*)
This approach simplifies the process and enhances flexibility by optimizing soft prompts, represented as diweninnsional continuous vectors, instead of directly optimizing discrete hard prompts. Ad- ditionally, it effectively leverages the LLM's contextual understanding capabilities, facilitating the generation of high-quality prompts.
3.2 ADAPTIVE UNCERTAINTY SCALE ADJUSTMENT MECHANISM
The implementation of black-box prompt tuning for generative Al in online learning scenarios poses significant challenges. First, the intrinsic output noise of generative Al models generates unstable outputs, introducing uncertainty into the optimization process. Second, zero-order methods rely on limited function evaluations to approximate gradients, often resulting high variance.
Noise of generative AI output: even with fixed model parameters and inputs, the outputs may still vary. We define the randomness as 8 (z"), ), and the objective function with randomness can be defined as:
The output of the generative AI is often accompanied by randomness,
f/ (=)) ff (2') + 8 (x').
(3)
High variance of zeroth-order optimization: ZOO estimates function gradients by sampling random perturbations within the domain and analyzing the resulting changes in output, providing a flexible framework for gradient estimation in black-box scenarios (Shamir 2017)). However, zero- order methods, which rely on a limited number of function evaluations for gradient approximation, often suffer from high variance during the search process (Liu al., 2018). In the context of prompt tuning for generative AI, the inherent noise in the model's 's output renders this gradient estimation process noisy zeroth-order approximation. To compute the partial derivative with respect to the soft prompt z, we utilize the noisy central two-point random gradient estimator:
fb (2* paa')
(2 (2' prc)) u'
V (x*)
24
where / is the smoothing parameter, and u is the direction vector sampled from the unit sphere Sd = {u E Rd ||u||2 1).
Adaptive uncertainty scale adjustment: To address the uncertainty caused by the noise in generative Al and the variance in zeroth-order estimates, introduce an adaptive uncertainty scaling mechanism.
4

---

Published as a conference paper at ICLR 2026
Update
AOZPT
+
Soft Prompt
Streaming Data
Noisy Zeroth-order Optimization Oracle
Open-source LLM
Uncertainty Scale Adjustment
Streaming Data
Semantically Prompt
Figure 2: The architecture diagram of AOZPT model.
This mechanism incorporates the exponentially weighted moving average of squared gradients into the update process, effectively reducing gradient uncertainty. We define the gradient update as follows:
241
m
(5)
V +
Here, m, can be interpreted as a "momentum", incorporating the exponentially weighted moving average of historical gradients to facilitate smoother and more stable gradient updates. The term m, defined as follows:
m, Σ a V= (s*-1),
and V, can be regarded as an "adaptive term", incorporating the exponentially weighted moving average of squared historical gradients. Including this the denominator enables the scaling of estimated gradients across dimensions, effectively balancing gradient magnitudes and reducing overall uncertainty. The term V; defined as follows:
M Σ
where 0 < a, 3 < 1, and the superscript of the a and 3 indicates the exponent to assign more weights to the most recent values; W = Σ a and 2---1 3 serve as the normalization parameter for the exponential average, ensuring that w
- a = and 1 Enr 8 1;
f (z') 0 for / < 0.
3.3 ADAPTIVE ONLINE ZEROTH-ORDER ORDER PROMPT TUNING
The AOZPT approach optimizes prompts in online black-box scenario (Figure During the prompt generation phase, we utilize a frozen open- LLM for instance optimization refine the prompt tuning. This approach capitalizes on the LLM's 's robust capabilities in contextual learning and language comprehension. Specifically, we leverage the model's deep understanding of linguistic patterns and context to generate high-quality, semantically rich prompts by optimizing its soft prompts. In the prompt update phase, we introduce perturbations to the soft prompts to compute the differential of the output loss function, thereby approximating the gradient using zeroth- gradient estimation. Additionally, we incorporate an adaptive uncertainty scale adjustment mechanism to address the uncertainty of online black-box prompt tuning (Algorithm) T)

---

Published as a conference paper at ICLR 2026
Algorithm 1 AOZPT
Input: learning rate 77. smooth parameter the length of the sliding window weighting parameter a and 8, normalization parameter W and M, a small constant e, initialize w-dimensional zero-initialized gradient vector A.
Output: {=')² It=1
Initialize soft prompt =
for / 0 to 7 do
Receive _ (x'.g'}
Get u² by sampled from unit sphere S
Compute: of F (A (2* puu) + Po: { and o'_ =F (A (A pee') + 2o: E.)
Compute f3 (z* + put) and få (z* uu²);
f/ (x* + pu") = l (g (o4;x") w/) + (z* + pu'),
f3 (2' mmi") = l (g (o';x") v8) + (st - ma²)
Compute the estimation gradient 4z53 (z'):
V2l (x²) 18 (z + pu²)
- f3 (z' )mx")
2p
Update gradient vector:
A V=Sb-w (s VzLk- (2)) ,..., VzSz (2))
Compute m, >w- a' Vel.s (x*-1) and V: 1 Ei1 Bi (5alz' (st-1)²
Update 2111 z 1) vv.tt*
end for
4 ANALYSIS
4.1 DEFINITIONS
Definition 4.1. Local regret for online non-convex optimization: The sliding window mechanism provides effective means of evaluating online learning algorithms by calculating the exponentially weighted moving average of the loss, assigning greater weight to more recent losses (Hazan et al. The exponentially weighted Hiding-window average function defined as follows:
2017).
1 W
w.a
a' (*
(8)
The local regret for online black-box prompt tuning is formally defined by the accumulated squared norm of the gradient of the exponentially weighted sliding- window average (Aydore et al. 2019):
sliding-window
R(T)&
F (2')
(9)
where V,Ft a. -"
Definition 4.2. Temporal variability: Many researchers have imposed additional constraints on the variation of the loss function between successive iterations, which is crucial for regret analysis in the ouline nonconvex case. Drawing on the principle of heper-regularity, the concept of variation is defined as follows (Jadbabaie et al. 2015 Xu & Zhang 2024):
T
VT
llf((z) - f=-1(=)],,
(10)
where we denote [19(z) 1((=)] A sup 1g(=) h((=)l

---

Published as a conference paper at ICLR 2026
4.2 ASSUMPTIONS
Assumption 4.3. Lipschitz gradient of (z"):: v is L-Lipschitz continuuus, i.e., there exists constant L for V21, 22 Rd, such that:
V. (z1) V (22))l2 I
- 11111-22112
(11)
Assumption 4.4. Bounded of f(=): For all Z, fa is bounded:
[fa(2)] S H.
(12)
Assumption 4.5. Bounded of noise: For all z 2, the following inequality is satisfied:
[8(z) A.
(13)
Assumption 4.6. Bounded of gradient For all E Z, V.Jh (z) and V (z) is bounded:
V (
S Goot
( S.
(14)
Assumption 1.3 and 4.4 are the basic assumptions for solving non-convex optimization prob- lems (Ghadimi Lan 2013 Hazan & Kale 2014 Xu et al. 2019, Liu et al. 2020), Assumption 4.5 is a common assumption just claim the gap between the noisy function fs(z) and the true function f(z). such as random output, different data distributions, and adversarial perturbation (Berahas et al. 2022 Gasnikov et al. 2023 Dvinskikh et al. 2022). In this study, refer specifically to the noisy output of the generative AI. Assumption 4.6 is critical in non-convex stochastic optimization, as ensures the fundamental effectiveness of the stochastic gradient (Duchi et al. [001]] Zhou et al., 2018 Chen et al. 2018). Additionally, in experimental settings, it is common practice to impose constraints on the gradients used for updates, such gradient clipping.
4.3 LEMMAS
Building on the above assumptions, we further constrain the uncertainty in noisy zeroth-order gradient estimation. Unlike traditional zeroth-order methods (Ghadimi & Lan 2013 Nesterov & Spokoiny 2017). Lemma|4.7 and Lemma 4.8 account for the effects of noise in Specifically, Lemma 4.7 bounds the norm of the estimated gradient, while Lemma 4.8 limits the discrepancy between the estimated and true gradients. This noise stems from the inherent randomness in generative AI outputs, introducing additional variability into the objective function. These lemmas are fundamental to the regret analysis of the subsequent AOZPT algorithm.
gradient estimation.
Lemma 4.7. Bound of the noisy zeroth-order gradient: If 2f is L-Lipschitz continuous, and ut the direction vector sampled from the unit sphere Sa {ur Rd =|ull|2 = 1}. Then, the noisy zeroth-order gradient satisfies the following inequality:
Bus [
(c) S Lu (d+ +d (z9112
AdF
(15)
Lemma 4.8. Bound of the difference between the true gradient and noisy zeroth-order gradient: If V v is L-Lipschitz continuous, and ue is the direction vector sampled from the unit sphere Sá = [uE Rd ||ul|| = 1}. Then, the following inequality satisfies:
Euu Verl (2)) (V (3))
Vafh (=)
2d
(d
L
+
(16)
4
4.4 THE REGRET ANALYSIS FOR AOZPT ALGORITHM
Theorem 4.9. Under Assumption
4.3
Assumption 4.6 solving the online Black-box prompt learning
problem with Algorithm 7 Fort is satisfied:
T, we suppose 7 = =zirz= E (0, 1]. The following inequality
R(T < E E3.
(17)
7

---

Published as a conference paper at ICLR 2026
where
(4H + +2V)) Go0
TGx
(2dA²
L pd
81-
7
We
112
2
E3 = LTTM A dd
Lu(d+ +3)
d=A
+
dG
2W - -7)et
2
1
Futher, we can get:
T W
TM W
R(T) -
(18)
Remark 4.10. The & captures the error associated with the standard first-order gradient in regret analysis. The & represents the cumulative zeroth-order variance and generative Al noise encountered during the update process of the AOZPT algorithm, which can be mitigated by adjusting the window length E3 is common term in adaptive algorithms, is similarly influenced by zeroth-order variance and generative AI noise. This highlights the significant impact these factors on convergence performance. The AOZPT algorithm leverages the adaptive uncertainty scale adjustment adjust parameters such as a, 33 and w, effectively limiting their influence. For instance, by setting a, 8 + 1 with 3 I S 8 and w = T this term can be reduced to a sublinear with respect to T. Under these conditions, the AOZPT algorithm can also achieve sublinear regret.
We begin by establishing the Lipschitz smoothness of the true objective function with respect to the parameters (Assumption 4.3p, a fundamental prerequisite for analyzing the nonconvex optimization problem. In the online nonconvex setting, we further consider the exponentially weighted sliding-window average function to facilitate local regret analysis. Subsequently, we address two primary sources of uncertainty: the variance introduced by zeroth-order gradient and the output noise of the generative AI, analyzed in Lemmas (4.7 and 4.8) Building upon these assumptions and lemmas, we establish the sublinear regret the AOZPT algorithm. The detailed proofs of Lemmas 4.7 4.8 and Theorem a.9 provided in Appendix A.2
Proof skeleton of Theorem 4.9;
5
EXPERIMENT
5.1 EXPERIMENT SETUP
Dataset. We conducted experiments across a range of generative tasks, including text-to-text generation tasks (CNN/DailyMail (Hermann et al. 2015) and GSM8K (Cobbe al. 2021) datasets) and text-to-image generation tasks (Anime and Painting datasets). For performance evaluation, we selected 500 samples from the CNN/DailyMail and GSM8K datasets, and 150 samples from the Anime and Painting datasets.
Baselines. The baselines consist of an online zeroth-order approach and four commonly used classical basclines adapted from an offline setup. The online zeroth-ordae approach, referred to as "ZO-OGD"
for brevity, serves the primary comparison method, was described in detail by Algorithm 2 For text-to-text generation tasks, the classical baselines include MANUAL PROMPT (MP), In-Context Learning (ICL) (Brown al. 2020). BDPL (Diao et 2022), and RLPROMPT (Deng et 2022
For text-to-image generation tasks, the classical baselines are MP, ICL, SFT (Hao et al.) 2024).
and Promptist (Hao et al. 2024). Additional details regarding the baselines are provided in the Appendix B
Evaluation Metries. For the text summarization task. the Fl-score served the primary evaluation metric. For the mathematical problem-solving task, accuracy (inverting cumulative binary 0-1 losses) metric was used. For the text-to-image generation task, aesthetic quality was evaluated using the Aesthetic Score Predicto [ which utilizes CLIP embeddings as input and is trained on the Aesthetic Visual Analysis dataset (Murray et al. 2012).
Implementation Details. The experiments are conducted on machine equipped with a cluster of NVIDIA RTX A6000 GPUs. For text-to-text generation tasks, the open-source model Vicuna-
8

---

Published as a conference paper at ICLR 2026
7 was used to generate semantically meaningful prompts. The Llama-3.1-1 GPT-3.5- Qwen2.5-14BB and Qwen3-235B mmdeels are then employed, with each experiment repeated three times using different random seeds to ensure robustness. For text-to-image generation tasks, the open- source model Vicuna-1315 is utilized to produce semantically meaningful prompts. Subsequently, the Mheamiike-photoreal-2 and Stable Diffusion v models employed, with each experiment similarly repeated three times using different random seeds for consistency. The implementation code is publicly available at http:///ghuu..oomm//gnnno/o///// AAZPT 2026
models
5.2 TEXT-TO-TEXT GENERATION TASKS
We report the average cumulative Fl scores for the summarization task and the average cu- mulative accuracy for the mathematical problem task using the Llama-3.1-8B, GPT--3.5-urbe and Qwen2.5-14B models, based on experiments conducted with three random seeds (14, 42, 81). The comparative results for each algorithm across different datasets and models are presented in Table [ Table demonstrates that AOZPT outperforms four widely used classical algorithms in most cases, highlighting its effectiveness in online settings. Moreover, AOZPT surpasses ZO-OGD, further validating the advantages of its adaptive uncertainty scale adjustment mechanism. In addition, Table A includes the results of the Qwen3-235B model the GSM8K dataset, which further demonstrate the effectiveness our method. We also conducted ablation experiments to demonstrate the necessity of open-source LLMs in Table T0
Table 1: The average cumulative F1 score accuracy + standard deviation using Llama-3. 1.1ma. GPT-3.5-turbo and Qwen2.5-14B models for CNN//ailyMaii,, GSM8K Datasets. Each result is reported based on three Monte Carlo experiments. The best results are in bold.
Dataset
MaNi
GSM8K
Method
Llama-3.I-B
GPT-3.5-turbo
Qwen2.5-14B
Llama-3.1-8B
GPT-3.5-turbo
Qwen2.5-14B
MP
24.753+:00079 34.269::0.035
22.068=00.038
60.533:10.471
69.200+:2.209
80.200+00.588
ICL
23.500=0.6001 32.364+0.259
23.064=0.028
60.667::0.20
69.933=0.806
86.733:10:416
BDPL
23.885++0220
35.372++0008
21.700+=3.909
34.667=11.055
36.406=1.7665
89.000-100.48
RIPROMP
13.618+0.175
34.681+00081
20.098-0.579
66.867+-0.71
23.800+2.1168
81.867+00.99
Z0-OGD
24.667100027 14.6821102211
22.034-10:551
65.06715.705
69.533
92.533-10.99 929
AOZPT(Ours)
24.707+00004 35.399-10.297 24.767=0.502
69.733-11511
78.13311.588
92.933:10.822
Table 2: The average cumulative aesthetic + standard deviation using preamlike-hootrreal- and
Stable Diffusion v1.5 models for Anime, Painting Datasets. Each result is reported based on three Monte Carlo experiments. The best results are in bold.
Dataset
Anime
Painting
Method
Dreamlik-2.0
Stable Diffusion v1.5
Dreamlike-2.0
Stable Diffusion v1.5
MP 5.785+10000
5.336=00.010
6.364
5.858=0.011
ICL
6.133:10.008
5.710:10.021
6.521110.016
6.074=:0.015
SFT
6.117:10.04
5.621+0.025
6.645=00.004
6.103=0.023
Promptist
6.093110.010
5.579=#0.006
6.552+:0.04
6.011=0.022
ZO-OGD
6.263:10.024
5.892:10.039
6.602-10.053
6.287=:0.013
AOZPT (Ours)
6.282:10.021
5.930=10.015
6.656=10.015
6.313=00009
5.3
TEXT-TO-IMAGE GENERATION TASKS
We present the average cumulative aesthetic score for the Dreamlike- -0ammlikk--hotorra-2200000 and Stable
Diffusion v1.5 models on the text-to-image generation tasks (Anime and Painting datasets), based
htts://uuginggfcce http://aww....aosss/ccaaaaaaaaaa
https:/hugggingface co/meta- Ilama/LLama-3.1 11----8-BBne
https://opeaa..com// www/iidex//ppcaaiaapp/
https://uuggingface.cm
wwwwwo/ww/wwwm//wn///e/eeoo 5-BBB Instruct-1M

---

Published as a conference paper at ICLR 2026
on experiments conducted with three random seeds. The comparative results for each algorithm across different datasets and models are provided in 2 2 shows that AOZPT outperforms baseline methods in most cases, demonstrating its effectiveness in online scenarios. Table O presents text-to-image experiments conducted under data drift conditions. The results indicate that under varying levels of data drift (10, 50, 75, 150), the online black-box optimization algorithms achieve higher aesthetic. In Table 7 ablation experiments are also included to illustrate the role of the adaptive uncertainty scale adjustment mechanism and the online zero-order gradient method in prompt optimization. Additionally, we provide performance comparison between our adaptive uncertainty scale adjustment mechanism and several widely-used adaptive gradient algorithms in Table 12 Lastly, we present case study of the Anime and Painting dataset in Table I6]and Table 17
6 DISCUSSION
6.1 ONLINE LEARNING VS. OFFLINE LEARNING
Offline learning offers distinct advantages, particularly for fixed-task datasets, by enabling stable training processes and achieving high accuracy. However, its primary application lies in developing deployable model products, as it lacks adaptability to evolving data. When confronted with dynamic data streams, offline learning requires retraining the model on the entire dataset, encompassing both historical and newly acquired data. This process incurs substantial computational costs and training inefficiencies. Each time the data changes, the model must be retrained from scratch, rendering this approach unsuitable for scenarios demanding real-time responses and frequent updates. This limitation stems not from the model itself but from the offline learning paradigm. By contrast, online learning provides a more effective alternative. It incrementally processes streaming data and updates the model in real time, enabling dynamic adaptation to data changes. Rather than retraining the entire model, online learning continuously updates and optimizes it based on current inputs, thereby reducing computational overhead and enhancing responsiveness.
6.2 REAL-WORLD, NON-IYYPOHHETICA APPLICATION SCENARIOS
Emmotinn-rspoonse chatbots and intelligent tutoring systems are not hypothetical constructs, but are grounded in real product requirements. These systems must adapt their response styles and content in real time based on user feedback, rendering long-cycle model fine-tuning or manual prompt redesign impractical. Consequently, online black-box prompt optimization presents broadly applicable solution for real-world deployment. For instance, emotion-aware chathots such as Replika and Woebot adjust their tone in response to users' emotional states. despite lacking access to internal model weights. Similarly, language learning platforms like Duolingo Max and Socratic dynamically tailor instructional content and tone based on student performance. In both cases, real- time model adaptation is infeasible, necessitating input-side prompt adjustments to enable responsive and personalized behavior. To further illustrate the practical applicability of our method, we present additional examples from high-stakes domains such as healthcare, finance, and law in Appendix where the feature distribution of input data is rarely stationary.
7 CONCLUSION
In this paper, we propose AOZPT, a novel approach that combines black-box prompt tuning with online learning. This method utilizes frozen open-source LLM for instance optimization, leveraging the LLM's advanced understanding of language patterns and context to optimize soft prompts for generating high-quality, semantically rich prompts. During the prompt updating phase, AOZPT dynamically adjusts prompts for generative AI based on streaming data, eliminating the need for retraining on the entire dataset. To address the variance in zeroth-order gradient estimation and the noise in generative AI, we introduce an adaptive uncertainty scaling mechanism. This mechanism incorporates the exponentially weighted moving average of gradients into the update process, ef- fectively reducing gradient uncertainty. To validate the effectiveness of AOZPT, we performed formal regret analysis in non-convex settings, demonstrating that sublinear regret convergence is achievable. Furthermore, and text-to- sat-to-image (Anime and Painting) tasks in simulated online scenarios, with results consistently indicating that AOZPT outperforms baseline models.
evaluated AOZPT on both text-to-text (CNN/Daily and GSM8K)
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENTS
Dr. Yi Chang was supported by the National Key R&D Program of China (Grant No. 2023YFF090540)), the National Natural Science Foundation of China (Grant No. U2341229), the Fundamental and Interdisciplinary Disciplines Breakthrough Plan of the Ministry of Education of China (/YB202XXDXM903, and the New Cornerstone Science Foundation through the XPLORER PRIZE.
ETHICS STATEMENT
All participants in this work, as well as the paper submission, adhere to the ICLR Code of Ethics ( https//ict.cc/ubbbiicCooooEEEest
REPRODUCIBILITY STATEMENT
We affirm that the results of this work are fully reproducible. Appendix A.2 provides the theoretical proofs. Appendix B details the experimental implementations, and the source code will be publicly released after publication of the paper.
REFERENCES
Sergul Aydore, Tianhao Zhu, and Dean P Foster. Dynamic local regret for non-convex online forecasting, Advances in neural information processing systems, 32, 2019.
Thomas Bartz-Beielstein, Jürgen Branke, Jörn Mehnen, and Olaf Mersmann. Evolutionary algorithms.
Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 4(3):178-195, 2014.
Albert Berahas, Liyua Cao, Krzysztof Choromanski, and Katya Scheinberg. A theoretical and empirical comparison of gradient approximations in derivative-free optimization. Foundations of Computational Mathematics, 22(2):507-560, 2022.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et Language models are few-shot learners. Advances in neural information processing systems, 33:1877-1901, 2020.
Erik Brynjolfsson, Danielle Li, and Lindsey R Raymond. Generative ai at work. Technical report, National Bureau of Economic Research, 2023.
Lichang Chen, Jiuhai Chen, Tom Goldstein, Heng Huang, and Tianyi Zhou. Instructzero: Efficient instruction optimization for black-box large language models. arXiv preprint arXiv:2306003082 2023.
Xiangyi Chen, Sijia Liu, Ruoyu Sun, and Mingyi Hong. On the convergence of a class of adam-type algorithms for non-convex optimization. arXiv preprint arXiv: 02941, 2018.
Jiale Cheng, Xiao Liu, Kehan Zheng, Pei Ke, Hongning Wang, Yuxiao Dong, Jie Tang, and Minlic Huang. Black-box prompt optimization: Aligning large language models without model training. arXiv preprint arXiv:2311.04555 2023.
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, al. Training verifiers solve math word problems. arXiv preprint arXiv:2110.144 141168, 2021.
Payel Das and Lav R Varshney. Explaining artificial intelligence generation and creativity: Human interpretability for novel ideas and artifacts. IEEE Signal Processing Magazine, 39(4)855 2022.
Mingkai Deng, Jianyu Wang, Cheng-Pine Ping Hsieh, Yihan Wang, Han Guo, Tianmin Shu, Meng Song, Eric P Xing, and Zhiting Hu. Rlprompt: Optimizing discrete text prompts with reinforcement learning. arXiv preprint arXiv:2205. / /2548, 2022.

---

Published as a conference paper at ICLR 2026
Shizhe Diao, Zhichao Huang, Ruijia Xu, Xuechun Li, Yong Lin, Xiao Zhou, and Tong Zhang. Black-box prompt learning for pre-trained language models. arXiv preprint arXiv:2201.083. 2022.
Kingma Diederik. Adam: A method for stochastic optimization. (No Title), 2014.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7), 2011.
Darina Dvinskikh, Vladislav Tominin, Iaroslav Tominin, and Alexander Gasnikov. Noisy zeroth-order optimization for non-smooth saddle point problems. In International Conference on Mathematical Optimization Theory and Operations Research, pp- 18-33. Springer, 2022.
Ziv Epstein, Aaron Hertzmann, Investigators of Human Creativity, Memo Akten, Hany Farid, Jessica Fjeld, Morgan R Frank, Matthew Groh, Laura Herman, Neil Leach, al. Art and the science of generative ai. Science, 13006650):1110-11111 2023.
Yasong Feng and Tianyu Wang. Stochastic zeroth-order gradient and hessian estimators: variance reduction and refined bias bounds. Information and Inference: A Journal of the IMA, 12(3): 1514-1545, 2023.
Stefan Feuerriegel, Jochen Hartmann, Christian Janiesch, and Patrick 7schech. Generative ai. Business & Information Systems Engineering, 66(1):111-125 2024.
Tyler J Gandee, Sean C Glaze, and Philippe J Giabbanelli. A visual analytics environment for navigating large conceptual models by leveraging generative artificial intelligence. Mathematics, 12(13):1946, 2024.
Tianyu Gao, Adam Fisch, and Danqi Chen. Making pre-trained language models better few-shot learners. arXiv preprint arXiv:2012. 15723, 2020.
Alexander Gasnikov, Darina Dvinskikh, Pavel Dvurechensky, Eduard Gorbunov, Aleksandr Beznosikov, and Alexander Lobanov. Randomized gradient-free methods in convex optimization. In Encyclopedia of Optimization, pp. 1-15. Springer, 2023.
Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM journal on optimization, 23(4):2341-2366 2013.
Bin Gu, Zhouyuan Huo, and Heng Huang. Zeroth-order asynchronous doubly stochastic algorithm with variance reduction. arXiv preprint arXiv:1612.01425, 2016.
Qingyan Guo, Rui Wang, Junliang Guo, Bei Li, Kaitao Song, Xu Tan, Guoqing Liu, Jiang Bian, and Yujiu Yang. Connecting large language models with evolutionary algorithms yields powerful prompt optimizers. arXiv preprint 200iv:2309008533 2023.
Yaru Hao, Zewen Chi, Li Dong, and Furu Wei. Optimizing prompts for text-to-image generation. Advances in Neural Information Processing Systems, 36, 2024.
Elad Hazan and Satyen Kale. Beyond the regret minimization barrier: optimal algorithms for stochastic strongly-convex optimization. The Journal of Machine Learning Research, 15(1): 2489-2512, 2014.
Elad Hazan, Karan Singh, and Cyril Zhang. Efficient regret minimization non-convex games. In International Conference Machine Learning, pp. 1433-1441. PMLR, 2017.
Karl Moritz Hermann, Tomas Kocisky, Edward Grefenstette, Lasse Espeholt, Will Kay, Mustafa Suleyman, and Phil Blunsom. Teaching machines to read and comprehend. Advances in neural information processing systems, 28, 2015.
Wenyang Hu, Yao Shu, Zongmin Yu, Zhaoxuan Wu, Xiangqiang Lin, Zhongxiang Dai, See-Kiong Ng. and Bryan Kian Hsiang Low. Localized zeroth-order prompt optimization. arXiv preprint arXiv:2403.080 029993 2024.
12

---

Published as a conference paper at ICLR 2026
Youqing Hua, Shuai Liu, Yiguang Hong, Karl Henrik Johansson, and Guangehen Wang. Distributed online bandit nonconvex optimization with one-point residual feedback via dynamic regret. arXiv preprint arXiv:2409.15680, 2024.
Ali Jadbabaie, Alexander Rakhlin, Shahin Shahrampour, and Karthik Sridharan, Online optimization: Competing with dynamic comparators. In Artificial Intelligence and Statistics, pp. 398 406. PMLR, 2015.
Jianchao Ji, Zelong Li, Shuyuan Xu, Wenyue Hua, Yingqiang Ge, Juntao Tan, and Yongfeng Zhang. Genrec: Large language model for generative recommendation. In European Conference on Information Retrieval, pp. 502- Springer, 2024.
Zhengbao Jiang, Frank Xu, Jun Araki, and Graham Neubig. How can we know what language models know? Transactions of the Association for Computational Linguistics, 8:423-438, 2020.
Ege C Kaya, Mehmet Berk Sahin, and Abolfazl Hashemi. Communication-efficienn zeroth-order distributed online optimization: Algorithm, theory, and applications. IEEE Access, 11:61173- 61191, 2023.
Pre-training of deep Jacob Devlin Ming-Wei Chang Kenton and Lee Kristina Toutanova. Bert:
bidirectional transformers for language understanding. In Proceedings of naacL-HLT, volume 1. Minneapolis, Minnesota, 2019.
Salma Kharrat, Fares Fourati, and Marco Canini. Acing:
Actor-critic for instruction learning in black-box llms. In Proceedings of the 2025 Conference on Empirical Methods Natural Language Processing, pp. 19086-19113, 2025.
Robert Lange, Yingtao Tian, and Yujin Tang. Large language models as evolution strategies. In Proceedings of the Genetic and Evolutionary Computation Conference Companion, pp. 579-582, 2024.
Brian Lester, Rami Al-Rfou, and Noah Constant. The power of scale for parameter-efficient prompt tuning. arXiv preprint (XXx:220440069/ 2021.
Xiang Lisa Li and Percy Liang. Prefix-tuning: Optimizing continuous prompts for generation. arXiv preprint wxXiv:2001.0099. 2021.
Yuan Li, Yixuan Zhang, and Lichao Sun. Metaagents: Simulating interactions of human behaviors for llm-based task- orienteee coordination via collaborative generative agents. arXiv preprint 2:Xiv:3310006500 2023.
Shen Liu, Jinglong Chen, Yong Feng, Zongliang Xie, Tongyang Pan, and Jingsong Xie. Generative artificial intelligence and data augmentation for prognostic and health management: taxonomy, progress, and prospects. Expert Systems with Applications, 255:124511 2024a.
Shihong Liu, Samuel Yu, Zhiqiu Lin, Deepak Pathak, and Deva Ramanan. Language models as black-box optimizers for vision-language models. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 12687-12697, 2024b.
Sijia Liu, Bhavya Kailkhura, Pin-Yu Chen, Paishun Ting, Shiyu Chang, and Lisa Amini. Zeroth- order stochastic variance reduction for nonconvex optimization. Advances in Neural Information Processing Systems, 31, 2018.
Xiao Liu, Kaixuan Ji, Yicheng Fu, Weng Lam Tam, Zhengxiao Du Zhilin Yang, and Jie Tang. P-tuning v2: Prompt tuning can be comparable to fine-tuning universally across scales and tasks. arXiv preprint arXiv: 10.00602, 2021.
Yanli Liu, Yuan Gao, and Wotao Yin. An improved analysis of stochastic gradient descent with momentum. Advances in Neural Information Processing Systems, 33:18261-18271, 2020.
Yinhan Liu. Roberta: A robustly optimized bert pretraining approach. arXiv preprint arXiv: / 1692, 364, 2019.
13

---

Published as a conference paper at ICLR 2026
Naila Murray, Luca Marchesotti, and Florent Perronnin. Ava: A large- database for aesthetic visual analysis. In 2012 IEEE conference on computer vision and pattern recognition, pp. 2408 2415. IEEE, 2012.
Yurii Nesterov and Vladimir Spokoiny. Random gradient-free minimization convex functions. Foundations of Compulational Mathematics, 17(2):527-566, 2017.
Makuochi Nkwo, Rita Orji, Joshua C Nwokejj, and Chinenye Ndulue. E-commerce personalization in africa: A comparative analysis of jumia and konga. In PPT@ PERSUASIVE, pp. 68-76, 2018.
Fabio Petroni, Tim Rocktäschel, Patrick Lewis, Anton Bakhtin, Yuxiang Wu, Alexander H Miller, and Sebastian Riedel. Language models as knowledge bases? arXiv preprint 19X9, 0066,, 2019.
Abhishek Roy, Krishnakumar Balasubramanian, Saeed Ghadimi, and Prasant Mohapatra. Multi- point bandit algorithms for nonstationary online nonconvex optimization. arXiv preprint arXiv: 2019.
Bobak Shahriari, Kevin Swersky, Ziyu Wang, Ryan P Adams, and Nando De Freitas. Taking the human out of the loop: A review of bayesian optimization. Proceedings of the IEEE, 104(1): 148-175, 2015.
Ohad Shamir. An optimal algorithm for bandit and zero-order convex optimization with two-point feedback. Journal of Machine Learning Research, 18(52):1-11, 2017. URL http::/
exc/paperssvv1/116-66 html
Taylor Shin, Yasaman Razeghi, Robert L Logan IV, Eric Wallace, and Sameer Singh. Autoprompt: Eliciting knowledge from language models with automatically generated prompts. arXiv preprint arXiv:2010. 15980, 2020.
Tianxiang Sun, Yunfan Shao, Hong Qian, Xuanjing Huang, and Xipeng Qiu. Black-box tuning for language-model-ang -eseeeeiee In International Conference on Machine Learning, pp. 20841-20855. PMLR, 2022.
Nitesh Upadhyaya. Enhancing real-time customer service through adaptive machine learning. Ma- chine Learning, 1(5):17, 2024.
Junda Wu, Tong Yu, Rui Wang, Zhao Song, Ruiyi Zhang, Handong Zhao, Chaochao Lu, Shuai Li, and Ricardo Henao. Infoprompt: Information-theoretic soft prompt tuning for natural language understanding. Advances in Neural Information Processing Systems, 36, 2024.
Yi Xu, Rong Jin, and Tianbao Yang. Non-asymptotic analysis of stochastic methods for non-smooth non-convex regularized problems. Advances in Neural Information Processing Systems, 32, 2019.
Zhipan Xu and Lijun Zhang. Online non-convex learning in dynamic environments. In The Thirty- eighth Annual Conference on Neural Information Processing Systems, 2024.
Heshen Zhan, Congliang Chen, Tian Ding, Ziniu Li, and Ruoyu Sun. Unlocking black-hox prompt tuning efficiency via zeroth-order optimization. In Findings of the Association for Computational Linguistics: EMNLP 2024, pp. 14825-14838, 2024.
Haozhen Zhang, Hualin Zhang, Bin Gu, and Yi Chang. Subspace selection based prompt tuning with nonconvex nonsmooth black-box optimization. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 4190, 2024.
Jiangjiang Zhao, Zhuoran Wang, and Fangchun Yang. Genetic prompt search via exploiting language model probabilities. In IJCAI, pp. 5296-5305, 2023.
Dongruo Zhou, Jinghui Chen, Yuan Cao. Ziyan Yang, and Quanquan Gu. On the convergence of adaptive gradient methods for nonconvex optimization. arXiv preprint Stti::/80000567.1 2018.
Kaiyang Zhou, Jingkang Yang, Chen Change Loy, and Ziwei Liu. Learning to prompt for vision- language models. International Journal of Computer Vision, 130(9))2337-2344 2022.
14

---

Published as a conference paper at ICLR 2026
Pengyuan Zhou, Lin Wang, Zhi Liu, Yanbin Hao, Pan Hui, Sasu Tarkoma, and Jussi Kangasharju. A survey on generative ai and Ilm for video generation, understanding, and streaming. arXiv preprins 160388 2024.
Fangyu Zou, Li Shen, Zequn Jie, Weizhong Zhang, and Wei Liu. A sufficient condition for conver- gences of adam and rmsprop. In Proceedings of the IEEE/CVF Conference on computer vision and pattern recognition, pp. 11127-11135, 2019.
15

---

Published as a conference paper at ICLR 2026
A CONVERGENCE ANALYSIS SIS
A.1 NOTATION
Table 3: Notations.
Symbolic
Meaning
t 1,... T
Number of iterations p-norm
||
Noise of model's output Expectation
fz, y}
Sample
F
Open-source LLM Random projection matrix
A E TR Dxd
2 Rd
Optimized low-dimensional vector The initial prompt
do
de E
The discrete prompt
Generative model
Loss function
I
Objective function
F
Sliding-window average function
w
Length of window
Weight
v.
The full gradient
The zeroth-order gradient
V..8
The noisy zeroth-order gradient
V.fo
V
diag(v
A.2 PROOFS IMPORTANT LEMMAS AND THEOREMS
Proof of Lemma 4.7
Proof.
According to the definition 4
V f. (z [1)
E,
(2" + +um²)
f3 (2* - prre)
E,
24c
1
E., [fl (z' + ) - fb (2' - pru)))
2μ
@ 1
E,, [f (2* + prtt)
1th (2t fmm") me [
2μ E,,, [ll (8 (z* + putt) - 5 (2² - mu²))
ut [e]]]
24
0)
6) (19)
16

---

Published as a conference paper at ICLR 2026
where (1) use the inequality ||a + bll2 - ||a|l2 + ||6||2 and definition e Then, for a):
Eu [1( (z' + pux) ft (z' -uu')) n' u2112
Eu [f (z* +mu)) - fl (2)) (V.f² (z") pau)) w
+ Eu
[f' (x' mmm) - 14 (z4) + (V=l" (z") -ume u011 Eu 112 (0),,m') ull12
(2)
L
2Bn
1/2 || md
2., || [V (2') mmm)) u'112
= Lu || + 2r | -f l (z') 2²))) || ||02|12
Lu (d 3) + 2nd V v=f' (z') 1|
(20)
where (1) use inequality ||a + + c|ا |el|2 + |6112 + ||c||2: (2) uses the Assumption 4.3 (3) use the Lemma in Nesterov & Spokoiny (2017).
For (b), using Assumption
4.5 and the inequalities (A.1)-(A.2) we have
B (8 (=* + pnd) 5 - (z'=)n²') u [12]
[65 (2* + mu²) 5 (s* ) $ (Es || (22) $
1A
Eu,5
20d
where (1) follows from (A.2), and from Lemma in Nesterov & Spokoiny (211)).
Finally, we take a) and b) into (19:
En V (zt)
1
(LD2 +3) 2nd V
1
2od
2p
24
Lu
tdo
(d + 3)
+ v (59)12= +
2
Proof of Lemma 4.8
Proof.
Ex
V 1/ (39)
Vzft (2 2
< 2 E.
V Fal3 (2))
En [ (z²)
1 +2
2
Eu [ (z))
V (2
||-
(1)
8(Et uuu")
8(2² prrt)
1
L2
(2
v/
< 2 E.
24r
2
2
(2) 202d
I.2 p2
112
2
where (1) uses Jensen's inequality and Lemma 3 in Nesterov & Spokoiny (011); (2) uses inequali- ties (A.1) derived from Assumption 4.5
17

---

Published as a conference paper at ICLR 2026
Lemma A.I. For =I..... T, a. are the weight parameters, and y aa/B12 To simplify the expression, denote Vaf (z') as g". And denote V Ut Suppose that y S 1, then have the following inequality for:
/ 2W (1 - 7)
m
| 112
(21)
Proof of Lemma A.I
Proof. Recall that Vr.i me.i It. denote the j-th coordinate of V2, m. and g*. We have
m
U
+
j=1
m
20
5=1 [i
d
mi.j
25a 1=1
2
M
d
2i 1 a ge-io
Σ
(22)
2W
/=1
i==
m-- 1
3 3igZ-in) bib
where (1) is use inequality + b 2/ab. Next have
n 2
ww-1 -i=0
a
gi-
2
d
i==
ww-1 a²)
Emmo ae lg 1211
2
2
vw-
3igZ
j=l
Eiz
ww-1
Bi 3
1
Σ w- 1== a 29
2
1=0 Big
1
d
2W
(
>1 1 ii
2We
J=1
1=0
d Σ
w-1
72
(23)
2We1
1=1
18

---

Published as a conference paper at ICLR 2026
where the first inequality holds due to Cauchy inequality. The last equality holds due to the definition of r.. Telescoping for = 1 to T, we have:
M
Σ
m 11
gr i
2W
M
2We
tm j=1 1=0
M
d
T
2W
Ø=1 t=1
E=
M
T
2W(1 -7)c
1=1
f=1
1/2
(3)
M
T
d
I
2W(1 - 7
d1/2M1
1
(24)
2W - 7)
where (1) because f1 (x*) = 0 for < 0: (2) is because
S 1; (3) holds due to Hölder's
inequality.
L
Proof Theorem
Proof. Since & (x*) is L-Lipschitz continuous, V VgPt (2*) is also L-Lipschitz continuous, then can get:
Ftt w,a (2+t1) Firaa (z')
L 11= ||2441- 2-112- -
V Ft. Fr. (21),2(t1 2²)
(25)
We take the expectation about {u" H 11=--w41 for both sides, then we simplify B(w to E,
Ey [Fu (11 Fr (z')]
< Eng ((V Frt wia (z²), 2141 2011 =²"]] + L E, || - 2=112]
(26)
6)
For a):
Ey [Fr (2(41)
Fe (2²)
Flt w.o (2(+1)- - Ft
w.ox (z²)
Fr Fu (gt+1)
(2++1)
+ F++1 (2441) - Fd. (2t).
(27)
wsa
19

---

Published as a conference paper at ICLR 2026
For b):
Ey [V= Fr. wia (="), - =
V Pr w. (z"), : -1 . Ex V : 4 F. a, (=9]
Bu (V=
FF w.a (z') 11 V, : Fi (t)))]
+ +Bu
( (V 1
a. (z') 17 V & (V (2') - .m.))
E. ( (V=T' (29) 11 V : V F (i))
+ 17 Eu { (==F (>1) V V F= (z*) - -m))
(1)
F V w.a (z*) -t- v Fr (z)) + Eu I(v= (z') 7 vi Fi wa (+
P w0, (z') m+) V, _ 2
+ 2
Eu
Eu
(v= w.a (z") : 2
"
V オ
v Ft a (z))
+ 2
En
[ (z)) (z))- m.) . V. 1
(28)
where (1) is use inequality (a, b) Organizing the
S
|| 1
2
27 and
28 into
26
we can get:
Ft Fu.a
(2
F++1 (z ) +
Fitl (2
Fr. (2))
u.a
w.a
< Eu
wia (xt) V=Fi
V
? Vi V Ft. wia (24)
2
+ 7 Bu
||( waa (2') m.) V
+
Lnp
Eu,
V
3 m:
(29)
2
2
Because of V, s G I, refer to Lemma 6.4 in Zhou et al. (2018). 2018).we we get:
Ft w,a
(1)
ptt1 (24+1)= +
(1(+))=
- Fet ",a (z9)
wia
1 E,
\ w.a (z') [[]]
+ 7R E
(V= (z') - -m:) V1 v
2G
2
Lnd
2
Vi } m
2
+
En
(30)
2
2
and for both sides take f 1,... T in
30
gives:
Σ Eu F. u.a (z') < Σ Ft a. (2)
Ftt1 (2(+1)= + Ft+1 (2442) Ft Fr (2))
2Go0 1=1
n)
+
En
[V Ft. w.a
(x*) -m:) V
2 1=1
8)
T
E,
v.
m
(31)
2
t=1
6)
20

---

Published as a conference paper at ICLR 2026
For (a):
T
Ft
(+tt1)
Ftt1 (2(+1) + F
(zl+1)
Fr (z*)
w.o
wiac
T
T
Σ
(F 1,a (z²) - Pott (2(+1)
+ Σ
petl
(z+t1) - Pi (2++2)
u.a
t=1
T
(2 (z ju+l (z(t1-1)
1=0
t=1
w-1
( (stt1-t) gr (z+t1-1))
2H + VT.
(32)
where (1) use Assumption 4.4 For (b):
Definition 1T
7
T
V Frt w.a (z²) - m.) V; $ |
Eu
2
1=1
(1)
T
V F w.a (z') V.liz (z') /
En
267
t=1
T
w-1
En
Σ a²
[ (x- - - (s-11)
202
W
1=1
1)
(at)²
Eye- V (2 V. (s 1
23
(3)
nT
22d
3d))3
+
(33)
n²
2
where (1) is because V, 2 el; (2) is because the sampling of w is independent; (3) uses W
Ee a', 0 < a and Lemma 4.8
Finally, we can get:
-mel[]] s TT
(2doz
(2))(
Eg
V aia (2))
12 +
(34)
2Web
2
For (c):
Lai²
En
V
2 1=1
(1)
LIy²
d
E,, [|19"]]]]]
2 21(1-
7) t=1
Ly (d (d+ 3))
od!
V. (>1)
41 7))c
11
(3)
LT
Lu((d + 3)3
dG dio
(35)
7))+
2
p
21

---

Published as a conference paper at ICLR 2026
where (1) uses Lemma A.1 (2) uses Lemma 4.7 (3) uses Assumption 4.6 We take a). b) and c) into (31):
T
7
Eu
V wia (2')113
2G
T/T
(2d0² 122
M
[Iu(d+3)) 2
+ dG + dža
S 2H +
VT
+
2We
2
2W 2W 7)e
Divide both sides simultaneously by a
2G
T
Σ
F aa (2))1
1=1
(4H + +2V
Go
TGx
2do
L'
+
Wei
122
2
Lu((d + 3)3
dia
+ dG
+
(1 7
2
/1
A.3 THEORETICAL ANALYSIS UNDER SUB-GAUSSIAN NOISE
Sub-Gaussian noise: At each round the learner observes noisy function value
= f
where 5(2") denotes the observation noise round f. We assume that {5(="))(21 forms martingale difference sequence and is uniformly -uub-Gausiinn: there exists a constant >> O such that for all t and all À R.
[F s exp 12
E E[8(2') 00
E E[cxp (Ao(='))
where {Fi} denotes the filtration generated by all randomness and observations up to round /
Although this modification alters the statements and proofs of Lemma 4.7 and Lemma 4.8 and affects the final regret bounds, it does not compromise the convergence guarantees of the proposed algorithm. We now proceed to provide a detailed analysis of the specific adjustments required in the theoretical derivations.
Proof of Lemma 4.7
Proof. According to the definition (4):
F (z") [[]
E,
f/ (z" + +um²)
f8 (2* - mrre)
E,
24c
1
E., [fl (z' + ) - fb (2' - pru))
2μ
@ 1
E,, [f (z* + prr)) 1t (at fmm") me [
2μ E,, [ll (6 (z* + puu)) - 58( ((2 - mmu)))
ut v2]
24
0)
6)
(36)
22

---

Published as a conference paper at ICLR 2026
where (1) use the inequality ||a + bll2 - ||a|l2 + ||6||2 and definition e Then, for a):
E. [1 (s' + pma)) - fr (2' -uue)) u' ul112
RR |1(5 (+* + (rx') - 1r (x1) - (V=J* (=*) ,pmn)) )) u² ll112
+ E, (f (x' pul - fr (x) + (Vef' (z') prr)) )) u(' + B,, (V (z*), nu²) u'llz
(2)
L
2.
2 ||"d u'
2 VV (z') per)) 22112
= E, ||0012 1 + Bn 11 1V ft (2) - ||02112
T (d 3) + 2nd V 8 (z')
(37)
where (1) use inequality || + + c|ا < |a 2 + |b|l2 + ||c||2: (2) uses the Assumption 4.3 (3) use
the Lemma in Nesterov & Spokoiny (2017).
For (b), using Assumption 4.5 and the inequalities (A.1),(A.2), we have
Eu,8 [8 (2* + uu") 5 (z'-xe²) u [12]
[Ens [60 (z' + uu²) 8 (x* mat)) ) 3 (En [ll' 122) 3 (1)
20d2
where (1) follows from (A.2), and from Lemma 1 in Nesterov & Spokoiny (2117). Finally, we take a) and b) into 19
Em F (zt) []
$ 2p
(Ip²(d 3)
(2))
2nd
2/
Lu
(d + 3) + V (=))12 + tdo 2
p
Proof of Lemma 4.8
Proof.
E2 4 2 (z9) V. (zt) 1
2
$ 2 E.
V.S% (2))
E. [ (z")
2 + Eu V. (z')
| 2 L
V
(1)
8(2t + uuu)
8(2² prr²)
12
12 3)3
2 2
2t
24
2
202d
L (d ( 333
112
2
where (1) uses Jensen's inequality and Lemma 3 in Nesterov & Spokoiny (0017) (2) uses inequali- ties ((A.)) derived from Assumption 4.5
Proof of Lemma 4.8
23

---

Published as a conference paper at ICLR 2026
Proof.
E, V 1 (#t) v (z') :
2 2 2 E. V. (3)) - Eu - (z))
+ Em V. [+)) - V (=)(()))3
6(21 + pm1) 8(2² - pur") 21
1.a 1 (d (d+ 3)3
BB
2/
2
(2) 20
1 (22 33
41
2
where (1) uses Jensen's inequality and Lemma in Nesterov & Spokoiny (017) (2) uses inequali- ties (A.1)-A.22 derived from Assumption 4.5
Combining the above bounds, we obtain the following result:
T
Σ
v= Fr aa (+))1E]
1=1
(4H + 2V
Go
TG
22o
(2p
+
Wet
112
2
..T.Mad&G& 2W ()>
+3]
dēa
+ dG
2
B EXPERIMENTAL SUPPLEMENTATION
To more accurately emulate real-world online scenarios, the data are streamed from the download URL to the local environment rather than preloaded. This streaming setup more faithfully reflects the conditions under which online prompt optimization methods operate. The learning rate is selected from the {0.01, 0.05, 0.1, 0.2, 0.5) and the zeroth-order parameter from (0.01, 0.05, 0.1), both determined through grid search. For the INSTRUCTZERO parameters, we set the intrinsic dimension to 10 and the prompt token length distribution, following the original paper (Chen et al. (003).. In the adaptive uncertainty scaling mechanism, the window size is selected from the set [10, 30, 50, 70, 100). with a selected from (0.8, 0.9, 0.95] and /3 from {0.9, 0.95, 0.99}.
and initialize the random projection matrix using uniform
We report all decoding and generation configurations used our experiments. Vicuna-7B and Vicuna- 13B use greedy decoding by default (do.ample = false), and although they include sampling values such as temperature 0.6, top p = 0.9, and lop = 50, these values do not take effect under greedy decoding. GPT-3.5-turbo is used with its default sampling configuration (temperature 1.0, top - p= 1.0). For Llama-3. 18B. Qwen2.5-14B, and Qwen3-235B, we follow each model's default settings. For Dreamlike-Phhttoraal Photoreal-2.0 and Stable Diffusion v1.5, which do not provide unified global defaults, we follow commonly adopted Diffusers settings, using classifier-free guidance (CFG) 7.0, 50 sampling steps, and Euler/Euler-A samplers.
For all baseline models, we use the default parameter settings provided in their official implementa- tions without modification.
MANUAL PROMPT: directly use the initial prompt without optimizing it during the process.
2020 directly inputs the selected examples into the LLM to rewrite the original prompt, providing AOZPT with an unoptimized initial performance point.
ICL Brrwnn al.
(Diao et al. 2022): uses policy gradient method estimate the gradients of the prompt token probability distributions and employs a variance-reduced policy gradient estimator to improve training stability.
BDPL
24

---

Published as a conference paper at ICLR 2026
ILPROMPT (Deng et al. (022):: proposes reinforcement sorming--ased method for optimizing discrete text prompts by training a small policy network (MLP) to generate optimized discrete prompt sequences that maximize downstream task rewards, while enhancing training stability and effectiveness through reward normalization and piecewise reward design.
SFT (Hao al. 2024):
performs supervised fine-tuning of pretrained language model using 360k source-target prompt pairs (original inputs and manually optimized prompts), enabling the model to learn to generate high-quality optimized prompts from user inputs.
Promptist (Hao et al. 2024): builds upon SFT by further training the prompt generation policy using reinforcement learning (PPO algorithm), maximizing reward function that combines the relevance and aesthetic scores of generated images, thereby enabling automatic exploration and generation of higher-quality prompts that better align with user intentions to improve text-to-image generation.
Algorithm 2 -errtthoorder Online Gradient Descent (Z0-OGD)
Input: learning rate smooth parameter μr, number of samples Q-
Output: {=²)²= Jt=1"
Initialize 20.
for 1= 7 do
Receive D2 = (²)
Get {ur] Q by sampled uniformly from unit sphere St == {u E Rd :/ulll2 = 1}.
Compute f3 (z* + yay) and f3 (z'-nuu) by 3
Compute the estimation gradient V=f3
Q
fb (2 + pml)))
f3 (2* put)) (e'-ptt)) U
(x) = -2
Σ
(38)
2/
9=1
Update end for
21+1 +- 2' n (z))
B. LARGER LLMS
We conduct experiments on text-to-text generation tasks using the Qwen3-235B and GPT-4o-mini model and compare AOZPT with several baseline methods. As shown in Table AOZPT achieves the best performance the GSM8K dataset (accuracy), outperforming all baselines including MP, ICL, BDPL, RLPROMPT, and ZO-OGD, As shown in Table AOZPT achieves the best performance on both the CNN//ailyMan Mail dataset (FI score) and the GSM8K dataset (accuracy), outperforming all baselines including MP, ICL, BDPL, RLPROMPT, and ZO-OGD. These results demonstrate that AOZPT consistently delivers superior performance across different text generation and reasoning tasks.
Table 4: The experiments with the Qwen3-235B model for GSM8K dataset
Model
Method
Cumulative Accuracy
MP
83.267 + 0.987
ICL
88.133 + 0.833
BDPL
83.446 = 1.453
Qwen3-235B
RLPROMPT
83.600 + 0.200
ZO-OGD
88.733 + 0.998
AOZPT
90.800 + 0.993
B.2 DATA DRIFT EXPERIMENTS
To further emphasize this need, have incorporated text-to-image experiment under data-drift conditions. Specifically, we simulated a dynamic data stream by arranging samples from the Anime and Painting categories in the text-to-image task at intervals of 15, 50, 75 and 150 for Stable Diffusion
25

---

Published as a conference paper at ICLR 2026
Table 5: Performance comparison of different methods on CNN/DailyMail and GSM8K datasets
using GPT-44-mini model.
Method
CNN/Daily.Mail (Fl score)
GSM8K (Accuracy)
MP
25,424
86.400 1.587
ICL
29.254 + 0.187
0.187
91.048 # 0.641
BDPL
26,246 + 0.184
90.314 = 0.116
RLPROMPT
27.363 0.059
89.867 1.206
ZO-OGD
30,308 0.142
90.533 # 1.007
AOZPT
31.016 0.058
91.667 = 0.757
v1.5 model, the results demonstrate that under varying degrees of data drift (L. 10, 50, 75, 150), the online black-box optimization algorithm, ZO-OGD and AOZPT, consistently achieves higher accuracy than traditional baselines, including MP, ICL, SFT, and Promptist.
Table 6: Data drift experiments with multiple intervals (L) for Stable Diffusion v1.5 model.
Method
Average aesthetic quality
Method
Average aesthetic quality
MP ICL SFT
5.597 + 0.007
Z0-OGD (L=50)
6.134 + 0.015
5,892 + 0.013
AOZPT (L=50)
6.143 + 0.014
5.862 + 0.016
ZOOGD (L=75)
6.115 = 0.007
Promptist
5.795 + 0.011
AOZPT (L=75)
6.126 + 0.014
ZO-OGD (L=10)
6.092 + 0.015
Z0-OGD (L=150)
6.037 = 0.080
AOZPT (L=10)
6.110 + 0.024
AOZPT (L=150)
6.117 = 0.010
B.3 ABLATION STUDY
We added ablation experiments in Table and Table 8 The results show that due the high variance of zero-order optimization and the output uncertainty of generative models, the performance improvement of online zero-order prompt tuning is limited. However, after incorporating our proposed Adaptive Uncertainty Scale Adjustment mechanism, the performance improvement becomes more pronounced. A₃ denotes the Adaptive Uncertainty Scale Adjustment mechanism and A₂ denotes online zero-order prompt tuning.
Table 7: Ablation Study for Anime and Painting datasets. A₁ denotes the Adaptive Uncertainty Scale Adjustment mechanism and A₂ denotes online zero-order prompt tuning.
Datasets
Anime
Painting
Method
Dreamlike-2.0
Stable Diffusion v1.5
Dreamlike-2.0
Stable Diffusion v1.55
AOZPPT w/o A, & A2
5.855+0.011
5.601+0.006
6.179+0.002
5.902-+0.011
AOZPT w/o
5.861+0.005
5.613++.0116
6.173++0.020
5.930++0.013
AOZPT
6.282.10.021
5.930-10.015
6.656:10.015
6.313-10.009
Table 8: Ablation Study for CNN/DailyMail and GSM8K datasets for Llama-3., 3.1-aB model. A
denotes the Adaptive Uncertainty Scale Adjustment mechanism and Ag denotes online zero-order prompt tuning.
Dataset
Method
Fl score accuracy
AOZPT w/o A₁ A2
23,500 0.601
CNN/DailyMail
AOZPT w/ A
25.089 3.884
AOZPT
27.966 0.153
AOZPT w/o A & A
69.267 0.462
GSM8K
AOZPT w/ A
74.000 5.415
AO7PTT
75.533 0.643
26

---

Published as a conference paper at ICLR 2026
We also conducted ablation studies the single-point gradient estimation method in the text-to- timage generation task to analyze the contribution of each component. As shown in Table 9 removing the Adaptive Uncertainty Scale Adjustment mechanism leads to noticeable performance drop, while the full model (with consistently achieves the highest aesthetic scores on both the Anime and Painting datasets. These results indicate that the performance gains primarily come from our Adaptive Uncertainty Scale Adjustment mechanism rather than from the gradient estimation alone.
Table 9: Experimental results of the single-point method the Anime and Painting datasets using the Stable Diffusion v1.5 model. A denotes the Adaptive Uncertainty Scale Adjustment mechanism and 2₂ denotes online zero-order prompt tuning.
Datasets
Methods
Aesthetic
Anime
AOZPT
(single-poin point method) w/o A1 & A2
5.710 = 0.021
AOZPT
(single-point method) w/o A
5.815 0.026
AOZPT
(single-point method)
5,872 + 0.021
Painting
AOZPT
(single-poing method) w/o A & A2
6.074 + 0.015
AOZPT (single-point method) w/o A
6.184 + 0.028
AOZPT (single-poin method)
6.219 + 0.016
We project optimized soft prompts onto the vocabulary via nearest-neighbor search in the embedding space. Retaining the soft-prompt configuration described in the manuscript, we replace the discrete prompts generated by the frozen open-source LLM with these projected tokens; results for LLama3.1- 8B and Qwen2.5-14B models on CNl dataset are reported the Table I0
Table 10: Directly mapping experiments for LLaMA3.1-88 1-8B and Owen2.5-14BB models. "without open-source LLMs" means directly mapping the soft prompts onto the vocabulary instead of using an open-source LLM.
Model
Method
Cumulative F1 score
ICL without open-source LLMs
9.890 + 0.028
ICL
23.500 + 0.601
LLaMA3.1-8B
AOZPT without open-source LLMs
9.911 + 0.023
AOZPT
24.707 + 0.047
ICL without open-source LLMs
21.67 + 0.015
ICL
23.064 + 0.028
Qwen2.5-14B
AOZPT without open-source LLMs
21.84 + 0.152
AOZPT
24.767 + 0.502
We conduct experiments on the text-to-image generation task using different open-source LLMs, including WizardLM-13B and OpenChat-3.5-0100 to evaluate the generality of AOZPT. As shown in Table I1 AOZPT consistently achieves the best or near-best aesthetic scores across all LLM configurations, outperforming baseline methods such MP, SFT, Promptist, ICL, and ZO-OGD. These results demonstrate that AOZPT performs robustly and effectively across various open-source LLMs, highlighting its strong adaptability and general applicability.
Table 11: Experiments on the Anime dataset are conducted using the Stable Diffusion v1.5 model, with WizardL and OpenChat-3.5-0106 serving the open-source LLMs.
Non-LLM
WizardL
openchat-3.5-0106
Method
Aesthetic
Method
Aesthetic
Method
Aesthetic
MP
5.336 = 0.010
ICL
5.515 + 0.017
MP
5.479 + 0.003
SFT
5.621 = 0.025
ZO-OGD
5.635 # 0.053
ZO-OGD
5.710 + 0.081
Promptist
5.579 = 0.006
AOZPT
5.734 = 0.028
AOZPT
5.828 + 0.064
27

---

Published as a conference paper at ICLR 2026
B.4 AOZPT VS. ADAPTIVE GRADIENT ALGORITHM
To overcome this limitation of Adam-like algorithms with all historical gradients, introduce forgetting window mechanism. This approach uses an adjustable sliding window to focus on the most recent data, enabling better adaptation dynamic input streams. Theoretically, the proposed AOZPT algorithm exhibits sublinear regret convergence. In experiments, we compare the performance of Adam, Nadam, RMSProp with AOZPT across various window sizes (w 10, 20, 50) using the Anime and Painting dataset under new experimental setup. The experimental results (TTale T2 ) demonstrate that by appropriately adjusting the sliding window size, the performance of AOZPT consistently outperforms the Adam, Nadam, and RMSProp algorithms. Moreover, in the majority of cases, the AOZPT algorithm with the sliding window configuration yields optimal performance.
Table 12: Performance comparison across adaptive gradient algorithms and AOZPT with varying window size.
Datasets
Anime
Painting
Method
Dreamlike-2.0
Stable Diffusion v1.5
Dreamlike-2.0
Stable Diffussio v1.5
Adam Kaya et al.
2003
5.866 0.007
5.609 0.023
6.179 = 0.011
5.927 + 0.025
Nadam NadamDDederrik Diederik
2014
5.863 0.005
5.594 0.015
6.168 = 0.009
5.929 + 0.005
RMSProp Zou
2019
5.860 0.007
5.608 0.024
6.168 0.013
5,924 0.022
AOZPT (w I0)
5,879 0.016
5.616 0.026
6.140 = 0.034
5,928 0.011
AOZPT (w 20)
5,881 0.005
5.617 0.012
6.180 = 0.013
5,938 0.012
AOZPT (w 50)
5,871 0.008
5.621 0.003
6.181 = 0.017
5.935 1 0.011
B.5 DE-EN TRANSLATION TASK
We additionally evaluate the methods on the English-to-Germe (De-En) translation task using both GPT-4o-mini and Llama-3. 3.18B, evaluated with the BLEU score. As shown in Table 13 AOZPT achieves the highest BLEU scores across both models, outperforming MP, ICL, and ZO-OGD, These results indicate that AOZPT delivers the best performance the machine translation task as well.
Table 13: Experiments on WMT/WMT14 De-En translation task using the GPT-4o-mini and Llama-3.1-8B models, evaluated with the BLEU score.
Model
MP
ICL
Z0-OGD
AOZPT
4Pm--o-mini 37.651 + 0.172
37.929 + 0.349
37.697 = 0.253
38.975 + 0.195
Llama-3.1-8B
30.498 + 0.221
30.728 + 1.110
30.722 + 1.629
32.510 + 0.334
B.6 PARAMETERS SENSITIVITY ANALYSIS
We conducted a parameter sensitivity analysis of the AOZPT algorithm on the text-to-image gener- ation task, examining key hyperparameters including the learning rate (1), smooth parameter (p), sliding window (w), weighting parameter (a and B). As shown in Figure 3 although the curves exhibit some local fluctuations across different parameter ranges, the overall performance consis- tently remains at a high level without any significant degradation. These results demonstrate that AOZPT exhibits strong robustness to hyperparameter variations, maintaining high-quality generation performance across a wide range of configurations without requiring precise parameter tuning.
B.7 INFERENCE LATENCY AND MEMORY CONSUMPTION
We evaluate the training and inference latency as well as memory consumption for text-to-text tasks on the Llama-3. 1--8B model, summarized in Table 14 During the training phase, AOZPT and ZO-OGD exhibit higher latency and memory usage due to the cost of performing zero-order gradient estimation. However, during inference, The semantic-rich prompts generated by the open-source LLM can be directly concatenated with the input sequence and fed into the target model, resulting in additional inference latency memory
AOZPT approach does not require additional computation.
28

---

Published as a conference paper at ICLR 2026
5.86
5.87
5.85
5.84
5.86
5.84
5.83
5.83
5.82
5.02
5.81
5.00
5.64
5.85
2esthatic
5.82
5.83
5.82
0.2
0.4
0.6
0.8
1.0
0.2
0.4
0.0
0.0
1.0
Figure 3: Parameter sensitivity experiments using Stable Diffusion v1.5 in Anime dataset: learning rate (17), smooth parameter (μ), sliding window (w), weighting parameter (a and B).
consumption. In summary, although AOZPT introduces higher cost during training, it maintains efficient inference with negligible overhead, making it practical for real-world deployment.
Table The inference latency and memory of the AOZPT algorithm on Llama-3.1 1-8B model for text-to-text tasks.
Train Latency (s)
Train Memory (MiB)
Inference Latency
Inference Memory
Datasets
Methods
(s)
(MiB)
Mail
MP
6.8668
16592
ICL
4.8849
42108
6.7638
15595
ZO-OGD
16,8986
41972
6,8645
16542
AOZPT
17.6268
42324
6.9658
15492
GSM8K
MP
4.9864
15902
ICI 7.6808
41824
4.7865
15904
ZO-OGD 24.6097
41828
4.9987
15933
AOZPT
24.4819
41826
4.8687
15722
B.8 NEW ONLINE PROMPT OPTIMIZATION BASELINE
To further contextualize AOZPT's performance, we additionally evaluated against ACING Kharrat et al. (2025), a recently proposed reinforcement-learinng based cntrructionootimizaaii method, and adapted it to online interaction setup for consistent comparison. The results (Table (15) show that AOZPT achieves superior performance on text-generation tasks under this online setting, demonstrating its effectiveness dynamic, real-time scenarios. We plan to incorporate state-of- the-art online baselines in future work.
Table 15: The supplementary baseline experiments conducted with GPT-3.5-turbo on the CNN/DailyMail and GSM8K datasets.
Method
CNN/DailyMaiil (F1 score)
GSM8K (Accuracy)
AhhNGk et al. 2025 AOZPT (Ours)
28.632 + 2.225
72.746 2.376
35.399 + 0.297
78.133 + 3.583
29

---

Published as a conference paper at ICLR 2026
B.9 CASE STUDY
Table 16: Case study of the images generated by Dreamlikc-phottrral-22 model, where these images are generated based on the original and optimized prompts. We generate 3 images for each prompt.
Original Prompt
Optimized Prompt
There is an image that represents the balance between yin and yang, harmonious, balanced, complementary, contrasting, dynamic, equilibrium, opposing forces, yin-yang symbol, balance of nature, yin-yang theory, traditional Chinese art, digital painting, artstation, concept art, smooth, sharp focus, illustration.
There is an image that represents the balance between yin and yang.
A floral portrait of Herzl, with a focus on his botanical interests and the beauty of nature. The image is highlydetailed and intricate, with a smooth and sharp focus Herzl's face and the flowers he is holding. The background is soft and subtle, with a hint of hdri lighting to create
Portrait of Herzl florist.
of depth and dimension. The overall style is elegant and sophisticated, with a touch of fantasy and imagination.
A group of fairies playing cards on table moonlit forest next pond filled with water lilies, digital painting, artstation, concept art, soft light, hdri, smooth, sharp focus, illustration, fantasy, inspired by the artwork of Ida Rentoul Outhwaite.
A group fairies playing cards on a table in moonlit forest next to pond filled with water lilies, artwork by Ida Rentoul Outhwaite.
A serene landscape depicting garden of Eden with lake reflections, fruit trees, and animals, captured in vivid and psychedelic style, digital painting, artstation, concept art, soft light, hdri, smooth, sharp focus, illustration, fantasy.
A serene landscape depicting a garden of Eden with lake reflections, fruit trees, and animals, captured in vivid and psychedelic style.
30

---

Published as a conference paper at ICLR 2026
Table Case study of the images generated by Stable Diffusion v1.5 model, where these images are generated based on the original and optimized prompts. We generate 3 images for each prompt.
Original Prompt
Optimized Prompt
young wizard is practicing spell while holding spell book and a black ball in a large room, wearing intricate leather armor, in comic cover art style with plain background
Young wizard practicing spell while holding a spell book and black ball in large room, wearing intricate leather armor, in a comic cover style with a plain background.
digital painting, artstation, concept art, soft light, hdri, smooth, sharp
fantasy.
of radiation, digital art, ArtStation, featuring unique and intricate design, with smooth and sharp focus, creating a sense depth and dimension. The painting highly detailed and elegant, showcasing the artist's creativity and skill.
neoclassic painting
A neoclassic painting of box of radiation featured on ArtStation.
The of soft light and HDRi creates sense of realism and atmosphere, transporting the viewer into the world of the painting.
cosmic portal with a beach at dusk on the other side, digital painting, artstation, concept art, soft light, hdri smooth, sharp focus, illustration, fantasy, surrealism.
Description, An artistic rendering of cosmie portal with beach dusk on the other side.
A movie poster featuring chicken, cow, capybara, and pig in an epic cinematic style, digital painting, artstation, concept art, highly detailed, smooth, sharp focus, illustration, fantasy, bold colors, dynamic composition, inspired by classic movie posters.
A movie poster featuring chicken, cow, capybara, and pig in epic cinematic style.
O'RIAA
CYALAL
31

---

Published as a conference paper at ICLR 2026
C ADDITIONAL EXAMPLES OF ONLINE BLACK-BOX PROMPT OPTIMIZATION
To further illustrate the practical applicability of our method, we present additional examples from high-stakes domains such as healthcare, finance, and law, where the feature distribution of input data is rarely stationary. Instead, it evolves continuously due to external factors.
In healthcare, for example, the emergence of new díseases, viral mutations, and updates clinical guidelines can shift the statistical properties of diagnostic data. In finance, market volatility, policy changes, and geopolitical events may rapidly alter user behavior and transaction patterns. In the legal domain, regulatory revisions, judicial reinterpretations, and evolving precedent can significantly affect document analysis and compliance workflows. Collectively, these dynamic factors contribute to data drift- a phenomenon where previously effective prompts become misaligned with current data distributions.
Data drift poses substantial challenge for prompt-based language models: prompts that once yielded reliable outputs may no longer meet evolving task requirements, leading to degraded performance or even high-risk errors. To maintain model reliability in such non-stationary environments, prompts must be continually adapted to reflect changes in user needs and input characteristics. This necessitates online learning capabilities during deployment.
However, many real-world applications- such as clinical decision-suppon systems, enterprise com- pliance tools, and mobile-edge putational capacity for backpropagation--asee fine-tuning. In such environments, traditional gradient- based methods are impractical.
in resource-constrained settings that lack the com-
To address this limitation, we propose online black-box prompt optimization as a lightweight yet effective alternative. This approach does require access model gradients internals. Instead, it leverages expert feedback to iteratively refine prompts. For example, physicians can assess the accuracy of generated diagnoses, auditors may flag anomalous transactions, and legal professionals can evaluate or correct machine-genedd supervisory signal, enabling models to adapt prompts in real time without backpropagation to maintain robustness in the presence of streaming, non-stationary data.
legal advice. These expert feedback signals serve as
D USE OF LLMS
In this work, LLMs are employed solely for polishing grammar checking text that is originally written by us.
32


Reviews:
[{"review_id": "e9cCmQGlGs", "reviewer": "Reviewer_rb5E", "summary": "This paper introduces AOZPT, an online black-box prompt optimization method thta uses a two-point zeroth-order gradient estimator with an adaptive uncertainty scaling to counter both LLM output noise and ZO variance. It proves a sublinear local regret bound under noise and shows consistent empirical improvements across text2text and text2image tasks.", "questions": "Please refer to Weakness).", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1) It is an interesting idea to move black-box prompt optimization from offline to online learning, this might be useful in training agentic systems that interacts with real environment.\n2) The proposed method is clearly presented and very practical.\n3) A mostly sound theory (maybe with some assumptions being a little bit too ideal) is built to support the effectiveness of the method.", "weaknesses": "1) Some assumptions, for example the Lipschitzness of \\nabla f_t in z, can be too optimistic. Is it possible if the authors can further verify how much we can expect these assumptions to hold in practice, and when these assumptions fail to hold, how much impact does this have on the effectiveness of the method in practices?\n\n2) I would recommend the authors to consider more baselines besides ZO-OGD. This can help isolating gains from the adaptive scaling agaisnt the two-point estimator.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "SvrfVmMmdF", "reviewer": "Reviewer_DxWc", "summary": "This paper proposes an adaptive online zeroth-order prompt tuning, a novel approach integrating zeroth-order optimization with online learning for non-convex settings. It can be applied to real-world scenarios where generative AI operates on streaming data and requires dynamic prompt adjustment.  This approach fills the gap of online learning for black-box prompt optimization, enabling dynamic adaptation to streaming data.", "questions": "The paper uses frozen open-source LLMs to generate discrete prompts, but what if such LLMs are unavailable ?   Can authors explain why there is no evaluation of the proposed method under adversarial noise in generative AI outputs ?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "This paper addresses a timely problem of great importance.  It can effectively tackle two core uncertainties in online black-box scenarios: noise from generative AI outputs and high variance in zeroth-order gradient estimates. This paper comes with rigorous theoretical foundations such as formal regret analysis for non-convex settings and comprehensive experiment results.", "weaknesses": "While the proposed method claims efficiency for online scenarios, it lacks details on inference latency and scalability. The framework involves two point gradient estimation and sliding-window gradient averaging but no data is provided on how these steps may affect runtime. In addition,  this paper compares AOZPT to offline baselines and a basic online method but it seems authors omit recent online prompt optimization and adaptive zeroth-order methods for LLMs. Therefore, it is difficult to assess AOZPT’s novelty against state-of-the-art online approaches.  Finally, the proposed method depends on frozen open-source LLMs to convert soft prompts to discrete prompts. Experiments show that removing this component may causes a significant drop in performance. This creates a dependency on high-quality open-source LLMs, which limits its deployment in scenarios where such models are unavailable.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "nKaXErAhnl", "reviewer": "Reviewer_nVJH", "summary": "This paper proposes AOZPT, a method that integrates black-box prompt optimization with online learning. It introduces an adaptive uncertainty scaling mechanism to handle noise from generative models and high variance in zeroth-order gradient estimation. Theoretical analysis shows sublinear regret convergence, and experiments demonstrate superior performance and stability over existing methods.", "questions": "see weakness.", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. Novel and timely topic that bridges black-box prompt optimization and online learning, addressing an underexplored area\n\n2. The adaptive uncertainty scaling mechanism is innovative and effectively mitigates output noise and gradient variance, improving robustness in practice\n\n3. The paper combines theoretical rigor with empirical validation, providing regret guarantees and solid experimental results across multiple tasks", "weaknesses": "1. While the methodological presentation is generally clear, the description of the adaptive scaling mechanism could benefit from additional implementation details or algorithmic steps to enhance reproducibility.\n\n2. The experimental evaluation would be strengthened by including a wider range of baselines, particularly reinforcement learning–based prompt optimization methods.\n\n3. The theoretical analysis is solid, though a deeper discussion of hyperparameter sensitivity and computational complexity in practical deployments could provide valuable insights into the method’s applicability.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "MRxR8VgQgC", "reviewer": "Reviewer_wCmh", "summary": "This paper considers black-box prompt optimization problem. It proposes AOZPT, an online algorithm, to update the prompt as the streaming data comes in and provides sublinear regret guarantees. The method regards the soft prompt as optimization variables and update them according to the feedback of the generated results in an Adam-style optimization process, in order to reduce the noise. Experiments on CNN/DailyMai, GSM8k and Anime, Paining tasks on Llama-3.1-8B, GPT-3.5-Turbo, and Stable Diffusion are carried out to demonstrate its performance.", "questions": "- Under Assumption 3.5, since the regret bound depends linearly on the noise level $\\Delta$, can the authors quantify or empirically estimate the typical scale of $\\Delta$ in practice? Given the autoregressive nature of LLMs, small perturbations in input can amplify downstream variance.\n- Given similar computational/latency budgets, could a larger model (e.g., GPT-4) achieve comparable or superior performance without AOZPT? For instance, in Table 1, Qwen2.5-14B (MP) outperforms Llama-3.1-8B (AOZPT) on GSM8K—can the authors clarify this discrepancy?\n- As the instruct models usually have better instruction following abilities, it is appreciated that the performance on these models (e.g., Qwen2.5-14B-Instruct) can be included to further demonstrate the necessity and benefit of the proposed method. For instance, Qwen2.5-14B-Instruct can achieve 94.8 on GSM8K, better than the results reported in Table 1.", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- The paper explores an interesting intersection between online learning and black-box prompt tuning, extending zeroth-order optimization methods to an emerging and practically relevant domain.\n- The proposed adaptive uncertainty-scaling mechanism—inspired by Adam—offers a principled way to stabilize noisy gradient-free updates.\n- The paper provides theoretical guarantees on local regret under noisy feedback.", "weaknesses": "- The noise model (Assumption 3.5) assumes uniform boundedness rather than a stochastic model (e.g., sub-Gaussian), which restricts theoretical generality.\n- The anonymous GitHub link has expired, preventing code verification and reproducibility assessment.\n- The prompt optimization is motivated by ongoing interactions with users (Lines 65-74). However, the online nature is simulated rather than true sequential feedback. And it is a bit unclear to me how it is simulated in the paper. It would be great if real streaming or non-stationary benchmarks would better justify “online”.\n- The computational overhead and latency introduced by the two function calls per iteration are not evaluated.\n- The empirical study require more results. For instance, (1) the prompt generating model is fixed for each task,  (2) important configuration details are not reported, e.g., the temperature and decoding strategy, which can greatly influence the final outcome. (3) the tested tasks are limited. (4) the original performance of the models should be included. According to the official report, Llama 3.1 8B (8 shots) achieve 84.5 on GSM8K. (5) Additional ablation studies on text-to-text tasks is appreciated.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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:

Decision: Accept (Poster)