Zeroth-Order Optimization Meets Human Feedback: Provable Learning via Ranking Oracles
Authors: Zhiwei Tang
Dmitry Rybin
Tsung-Hui Chang
Venue: ICLR 2024 poster (2024)
Keywords: Learng from human feedback
zeroth-order optimization
Stable Diffusion
ranking and preferences
Primary area: optimization
TL;DR: We invent the first zeroth-order algorithm for solving optimization problems with only ranking oracles of the objective function available.

Abstract: In this study, we delve into an emerging optimization challenge involving a black-box objective function that can only be gauged via a ranking oracle—a situation frequently encountered in real-world scenarios, especially when the function is evaluated by human judges. A prominent instance of such a situation is Reinforcement Learning with Human Feedback (RLHF), an approach recently employed to enhance the performance of Large Language Models (LLMs) using human guidance [Ouyang et al. 2022, Liu et al. 2023, OpenAI et al. 2022, Bai et al. 2022]. We introduce ZO-RankSGD, an innovative zeroth-order optimization algorithm designed to tackle this optimization problem, accompanied by theoretical assurances. Our algorithm utilizes a novel rank-based random estimator to determine the descent direction and guarantees convergence to a stationary point. Moreover, ZO-RankSGD is readily applicable to policy optimization problems in Reinforcement Learning (RL), particularly when only ranking oracles for the episode reward are available. Last but not least, we demonstrate the effectiveness of ZO-RankSGD in a novel application: improving the quality of images generated by a diffusion generative model with human ranking feedback. Throughout experiments, we found that ZO-RankSGD can significantly enhance the detail of generated images with only a few rounds of human feedback. Overall, our work advances the field of zeroth-order optimization by addressing the problem of optimizing functions with only ranking feedback, and offers a new and effective approach for aligning Artificial Intelligence (AI) with human intentions.

Published as a conference paper at ICLR 2024
ZEROTH-ORDER OPTIMIZATION MEETS HUMAN FEEDBACK: PROVABLE LEARNING VIA RANKING
ORACLES
Zhiwei Tang!.3,, Dmitry Rybin', Tsung-Hui Chang School Science and Engineering'. School of Data Science? The Chinese University of Hong Kong, Shenzhen, China Shenzhen Research Institute of Big Data', Shenzhen, China {zhiweitange dmit amiiryyyyin] ) link. cuhk. edu. cn changtsunghul Saccchuu@@uhhhc @uhhk. edu. cn
Dmmitry
ABSTRACT
In this study, we delve into an emerging optimization challenge involving a black- box objective function that only be gauged via ranking oracle-a situa- tion frequently encountered in real-world scenarios, especially when the function is evaluated by human judges. Such challenge is inspired from Reinforcement Learning with Human Feedback (RLHF), an approach recently employed to en- hance the performance of Large Language Models (LLMs) using human guid- ance (Ouyang et al.] 2022 Liu et al. 2023] OpenAl 2022 Bai et al. 2022). We introduce RD-Ran an innovative zeroth-order optimization algorithm designed to tackle this optimization problem, accompanied by theoretical assur- ances. Our algorithm utilizes a novel rank-based random estimator to determine the descent direction and guarantees convergence to stationary point. More- over, ZO-RankSGD readily applicable to policy optimization problems Rein- forcement Learning (RL), particularly when only ranking oracles for the episode reward are available. Last but not least, we demonstrate the effectiveness of ZO- RankSGD in novel application: improving the quality of images generated by a diffusion generative model with human ranking feedback. Throughout experi- ments, found that ZO-RankSGD erated images with only a few rounds of human feedback. Overall, our work advances the field of zeroth-order optimization by addressing the problem of op- timizing functions with only ranking feedback, and offers a new and effective approach for aligning Artificial Intelligence (AI) with human intentions.
significantly enhance the detail of gen-
INTRODUCTION
Ranking data an omnipresent feature the internet, appearing on a variety of platforms and ap- plications, such search engines, social media feeds, online marketplaces, and review sites. It plays a crucial role in how we navigate and make sense of the vast amount information avail- able online. Moreover, ranking information has unique appeal to humans, it enables them to express their personal preferences in straightforward and intuitive way (Ouyang et al. 2022 Liu al. 2023 OpenAl 2022 Bai al. 2022). The significance of ranking data becomes even more apparent when some objective functions are evaluated through human beings, which is becoming increasingly common in various applications. Assigning an exact score or rating can often require significant amount of cognitive burden or domain knowledge, making it impractical for human eval- uators provide precise feedback. contrast, ranking- based approach can be more natural and straightforward allowing human evaluators to express their preferences and judgments with ease (eeney Raiffa 1993). In this context, our paper makes the first attempt to study an important optimization problem where the objective function can only be accessed via ranking oracle.
Problem formulation. With an objective function f IRd + R, we focus on the optimization problem mingeR f(), where is black-box function, and oracle that can sort every input based on the values of f. this work, we focus on a particular
only query it via ranking
"Correspondence Zhiwei Tang tangl @1 i cukk. edu.

---

Published as a conference paper at ICLR 2024
family of ranking oracles where only the sorted indexes of top elements returned. Such oracles are acknowledged to be natural for human decision decision-making (Keeney & Raiffa 1993). We formally define this kind of oracle follows:
Definition 1 ((m,, k--ranning oracle). Given a function / Rd + I and m points , Tm to query, an (m,k) ranking oracle 0mm.k) returns k smallest points sorted in their order. For example, k) O (m (I1, (11,"iyn Tm) = (i1;.., 0k); then [(x,,) S s.. 3 (11...))))
min [(xz)-
Applications. The optimization problem minzer" ((x) with an (m, k--ranking oracle a com- mon feature in many real-world applications, especially when the objective function f is evaluated by human judges. One prominent inspiration for this type of problem is the growing field of Rein- forcement Learning with Human Feedback (RLHF) (Ouyang et al. 2022 Liu et al. 2023 OpenAl 2022 Bai et al. 2022). where human evaluators are asked to rank the outputs of large Al mod- els according to their personal preferences, with aim to improve the generation quality of these models. Inspired by these works, in Section + we propose a similar application which human feedback is used enhance the quality of images generated by Stable Diffusion (Rombach et al.) 2022). a text-to-image generative model. An overview of this application is demonstrated in Figure Beyond human feedback, ranking oracles have the potential to be useful in many other applica- tions. For instance, in cases where the exact episode reward in reinforcement learning, or the precise values of the objective function must remain private, ranking data may provide a more secure and confidential option for data sharing and analysis. This is particularly relevant in sensitive domains, such healthcare or finance, where the exact value of personal information must protected.
Stable
Diffusion
Initial Image
optimized Image
10-2
Figure 1: Application our proposed algorithm on enhancing the quality of images generated from Stable Diffusion with human ranking feedback. At each iteration of this human-in-the mization, we use Stable Diffusion to generate multiple images by perturbing the latent embedding with random noise, which are then ranked by humans based on their quality. After that, the ranking information leveraged to update the latent embedding.
opti-
1.1 RELATED WORKS
Zeroth-Order Optimization. Zeroth-order optimization has been rigorously explored in the opti- mization literature over several decades (Nelder & Mead 1965] Frazier 2018 Golovin et al. 2019 Nesterov & Spokoiny] 2017). Despite this, most existing works make a significant assumption that the value of the objective function is directly accessible-an assumption ill-suited for our con- text, where only ranking data of the function value is available. Existing heuristic algorithms like CMA-ES (Loshchilov & Hutter 2016).. which exclusively rely on ranking information, often lack theoretical guarantees and may underperform in real-world scenarios. A notable exception is the recent study by (Cai et al., 2022), which investigates a setting where a pairwise comparison oracle of the objective function available. This comparison oracle is indeed (2, 1) -ranninn oracle, mak- ing it a special case within our work's s scope. (Cai et al. (002)) attempts to uncover the gradient of the objective function using the 1-bit compressive sensing method. Beyond (Cai et al. 2022). (Yue) & Joachims 2009 Ding & Zhou 2018 Kumagai 2017) also study the use of comparison oracle, but in the context of online bandit optimization. One major problem all these existing works on which
comparison oracles is that the underlying objective is confined to be convex/strongly-comme particularly unrealistic in some applications involving human preference. Our work, in contrast, contemplates a more general (m, k)-ranking oracle and focuses primarily non-convex functions. Rather than relying on compressive sensing techniques, our work introduces a novel theoretical analysis capable of characterizing the expected convergence behavior of our proposed algorithm.
Bayesian Optimization with Comparison Oracles. Another relevant topic is Bayesian optimiza- tion using pairwise comparison oracles, demonstrated in (Asuudillo & Frazier 2020) and (Lin
2

---

the paper Published as a conference paper at ICLR 2024
Compared to the approach studied in this work, their approaches have two key is- sues. Firstly, unlike suddient-based algorithms, these works lack strong theoretical guarantees for optimization. Moreover, similar to the CMA-ES algorithm (Loshchilov & Hutter 2016), Bayesian Optimization faces scalability issues and struggles with high-dimensional optimization, which not problem for gradient-based algorithms, shown in (Duchi et al. 2013).
al. 2022
Reinforcement Learning with Human Feedback (RLHF). The general approach in existing RLHF procedures involves collecting human ranking data to train a reward model, which then used to finetune a pre-trained model with policy gradients (Ouyang et al. [222)) Liu et al.] [203]] OpenAT 2022; Bai et al., 2022]. J. this work, we explore an alternative setting that fuses reinforce- ment learning with ranking feedback, where ranking occurs online and is based on the total reward of the entire episode. Our proposed zeroth-order algorithm can be directly employed to optimize the policy within this context.
Contributions in this work. Our main contributions are summarized as follows:
(1) First rank-based zeroth-order optimization algorithm with theoretical guarantee. We present novel method for optimizing objective functions via their ranking oracles. Our pro- posed algorithm ZO-RankSGD is based on new rank-based stochastic estimator for descent direction and is proven to converge to a stationary point. Additionally, we provide a rigorous analysis of how various ranking oracles can impact the convergence rate by employing a novel variance analysis. Last but not least, ZO-RankSGD is also directly applicable to the policy search problem in reinforcement learning with only ranking oracle of the episode reward available.
(2) A new method for using human feedback guide AI models. ZO-RankSGD offers fresh and effective strategy for aligning human objectives with AI systems. We demonstrate its utility by applying our algorithm to a novel task: enhancing the quality of images generated by Stable Diffusion with human ranking feedback. We anticipate that our approach will stimulate further exploration of such applications in the field of Al alignment.
Notations. For any x E R. we define the sign operator as Sign(x) = if x 2 0 and -1 otherwise, and extend vectors by applying it element-wise. For d-dimensional vector æs, we denote the d-dimensional standard Gaussian distribution by (0, Ta). The notation |S] refers to the number of elements in the set S.
Paper organization. The rest of this paper is structured as follows: Section introduces how to estimate descent direction based on ranking information, with a theoretical analysis of how different ranking oracles relate to the variance of the estimated direction. Built on the foundations in Section 2. Section 3 presents the main algorithm, ZO-RankSGD, along with the corresponding convergence analysis. In Section 4 demonstrate the effectiveness of ZO-RankSOn through various experi- ments, ranging from synthetic data to real-world applications. Finally, by summarizing our findings and suggesting future research directions.
FINDING DESCENT DIRECTION FROM THE RANKING INFORMATION
Assumption 1. Throughout this paper, have these assumptions the function J: (1) f is twice continuously differentiable. (2) f L-smooth, meaning that [| [x)]] L. (3) f is lower bounded by value f², that is. f fxx) f* for all x.
2.1 A COMPARISON- COMPARISON-BASED ESTIMATOR FOR DESCENT DIRECTION
In contrast to the prior work CCai et al. 2022), which relies on one-bit bit compressive sensing to recover the gradient, we propose a simple yet effective estimator for descent direction without requiring solving any compressive sensing problem. Given objective function f and point æ, we estimate the descent direction of using two independent Gaussian random vectors & and & as follows:
((x) = Sy(r, E1, ()1 - E2),
where μ 0 is constant, and Sy (2, E1, E2, 11) Rdd
Rd Rdd R4, (1, is defined as:
Sy(a. E2, det Sign ((f(z + m&n)= - f(z + +(Z)))
(2)
We prove in Lemma [ which is one the most important technical tools in this work, that (xx) is an effective estimator for descent direction.
3

---

Published as a conference paper at ICLR 2024
Lemma 1. For any R we have
(VI()) 2 [Vf())] Caul.
(3)
where Cs 2 0 is some constant that only depends on d.
Denote > 0 as the step size. With the L-smoothness of f and Lemma | we can show that
( + --1 [[]
E f1,52
S -->1V/(>)) + -Caul + +7
(4)
where note that B[]0(=)) Bilk Ezll 2d. Therefore, whenever [+)( * O,
the value [f [=))] would be strictly smaller than f(x) with sufficiently small y and ju. More importantly, unlike the comparison-base based gradient estimator proposed in (Cai et al. (022), our estimator (1 can be directly incorporated with ranking oracles, as we will see in the next section.
2.2 FROM RANKING INFORMATION TO PAIRWISE COMPARISON
We first observe that ranking information can be translated into pairwise comparisons. For instance, knowing that x1 is the best among #1:42; T3 can be represented using two pairwise comparisons: Ij is better than z3. Therefore, we propose to represent the input and output of (m, k-)ranking oracles as directed acyclic graph (DAG), G = (N,
is better than 222 and
2
where the node set N = (1....,m) and the directed edge set = (i.j)
(x,) f(xz)) {. An example of such a DAG is shown in Figure Given
access to an (m, k) -ranking oracle 0 (m.k)) and a starting point 2, we query mmmmk) with the inputs
x + +E, & ~ (O0 Ia), for i = L,...,, m. With the graph G constructed from the ranking information of Ommkk) we propose the following rank-based gradient estimator:
Figure 2: The cor- responding DAG for the ranking result ( (2,, 13, (5) rb (1,3,
g(x) =
Σ (iJ)EE
Σ (5; - E.). (1.))EE
Remark 1. Notice that (5) can be simply expressed as a linearly weighted combination of E1, Em We provide the specific form in Appendix
We note that ① is a special case of (5) with m and A: 1, and it can be easily shown that [z](z)) ] [[](=]] and [[]l)(=)]]* S Ell [()]( indicating that the benefit of using ranking information over a single comparison is a reduced variance of the gradient estimator. However, to determine the extent of variance reduction, we must examine the graph topology of G.
Graph topology of G. The construction of the DAG 9 described above reveals that the graph topology of G is uniquely determined by and k. There are two important statistics in this graph topology. The first one is the number of edges (8). which is related to the number of pairwise comparisons, extracted from the ranking result. In the precedent work (Cai et al. 2022), the number of pairwise comparisons can be used to determine the variance of the gradient estimator. However, this is insufficient for our case, as the pairwise comparisons in (5) are not independent. Therefore, we require the second statistic of the DAG, which is the number of neighboring edge pairs in E. We define a neighboring edge pair as pair of edges that share the same node. For instance, in Figure 2. one neighboring edge pair is (01, .a) and (2).))). We denote this number as N(E) and define it formally as NEE) def. ((.
E E i i'}l, where E is the undirected copy of E, ie, (i.j) E if and if only (j.1) in E (i,j) in E. As mentioned, the graph topology of G is determined by m and k. Therefore, we can analytically compute |E] and NE) using m and k. We
state these calculations in the following lemma:
Lemma 2. Let G = (N,E) be the DAG constructed from the ranking information of (m)))) Then,
|3] = km (R22 + k))/ [E) m²k + mk? - 3.3 + k2 4mk + 2k.
(6)
(7)
4

---

Published as a conference paper at ICLR 2024
Variance analysis of (5) based the graph topology. To analyze the variance of the estimator G]. we introduce two important metrics M1(f. (t) and M2(f. ff po) on the function f.
Definition 2.
Mi 14) def max E [5 E2, - E2)l E1
(8)
M2(f,1) def. max Er.Ea.sa
E [S,(2, C2, ( E1, C3, 1) E2, Ea)
(9)
where Eτ, E2 and Ea are three independent random vectors drawn frawn.from N (0, Ia).
We also provide some useful upper bounds on M1 (4) and M2 11) in Lemma which help to understand the scale of these quantities.
Lemma 3. For any function f and μ
have Mi p)) 2d, M2(f. I 2d. Moreover if
satisfies that 4² f(x) = cla where E R is some constant, we have Mi(f. S 32/T.
With (1) and M2(S, p)), we can bound the second order moment of 5 as shown in Lemma Lemma 4, For any x E R4, we have
2d [
N(E)
M2(..P) + M1(.,1). E8
(10)
Discussion on Lemma 4 With Lemma and Lemma 3 we observe that the first variance term in [T). namely, [eT
O (mm)) and thus vanishes as m + oc. contrast, the second variance term
N(E)
M2(s (1) does not disappear as m grows, because RT
N(E)
lim k + mk? - K3 - 1.2 4mnk + 2k
lim
(11)
EE
(km (I:2 + 1))2)²
K.'
and thus only vanishes when both & and m tend to infinity. However, there non-diminishing term M,(f.r (f) remaining in (TO). Fortunately, as shown in Lemma M, (f (1) is smaller than 2d
and can be bounded by a dimension dimeeniioninneeeedden constant for a certain family of quadratic functions.
Finally, it is worth noting that approach for the variance analysis can be directly extended to any ranking oracles beyond the (m, k)-rnnknng oracle.
ZO-RANKSGD: ZEROTH-ORDER RANK-BASED STOCHASTIC GRADIENT DESCENT
With all of our findings in Sections 2 now we are ready to introduce our proposed algorithm, ZO-
RankSGD. The pseudocode for Z0-RankSGD is outlined Algorithm
Algorithm ZZO-RanKGGD
Require: Initial point zp. stepsize numher of iterations T, smoothing parameter (m, k) -ranking oracle 0 (m.k)
1: for t= to T do
2: Sample i.i.d. random vectors () E(e,m) from N(0, Ia).
3: Query the (m, k))ranking oracle (fm.k) with input {x+-1 + + (( ".. .. - (E(),))) ). and constuct
the corresponding DAG G (N, E) as described in Section 2.2
4:
Compute the gradient estimator using: ge فe Eb.))e (E(r,) Ea.9)
5:
Jt-1 719t-
6:
end for
3.1 THEORETICAL GUARANTEE ZO-RANKSGD
Now we present the convergence result of Algorithm D
in the following Theorem
Theorem 1. For any > 0, > 0, T N, after running Algorithm 7 for T iterations, we have:
min (E
[Vf((=->)||
(mx) - S" + CapL + TL
2d
+
N(E)
Ma(f. + Ma(f.w)). (12)
nT
E
where Ca is some constant that only depends d.
5

---

Published as a conference paper at ICLR 2024
Corollary 1. By taking = V d7 and
C in Theorem I
we have
min (E....))))
| [[ 1)]| =0
(13)
Effect of m and & on the convergence speed of Algorithm[] As we have discussed in Section 2.2
m and & affect the convergence speed through the variance of the gradient estimator. Specifically, in the upper bound of 12] we have
[e]
2d
+
NIE
12)2 M2(f, - 0 km d)
How to choose in Algorithm 1 As we can see from 12) a smaller generally leads to a tighter bound as the estimated gradient aligns better with the true gradient. However, practical implementation demands striking balance, instances that are extremely similar to humans, making the ranking decision of them challenging. Therefore, practical rule for choosing μ is: While we should try to minimize J., it should remain within the range of human discriminability.
excessively small μ might result in perturbed
3.2 LINE SEARCH VIA RANKING ORACLE
In this section, we discuss two potential issues that may arise when implementing Algorithm I Firstly, it can be cumbersome to manually tune the step size r, required for each iteration. Secondly, may be challenging for users to know whether the objective function is decreasing in each iteration as the function values and effective line search method that leverages the (1, -rranking oracle to determine the optimal step size for each iteration. The method involves querying the oracle with set of inputs { -t-1 779.:....III11 "yn'111 9r where (0, 1) represents a scaling factor that controls the rate of step size reduction. By monitoring whether or not Ie equal to It-1, users can observe the progress of Algorithm|| [1] while simultaneously selecting suitable step size to achieve the best results. It worth noting that this line search technique not unique to Algorithm and can be applied to any gradient-based optimization algorithm, including those in (Nesterov & Spokoiny] [017]] Cai cct al. 2022). To reflect this, we present the proposed line search method as Algorithm| 2 under the assumption that the gradient estimator Sr has already been computed.
accessible. In order address these challenges, we propose simple
Algorithm Line search strategy for gradient-based optimization algorithms
Require: Initial point wo. stepsize number of iterations T', shrinking rate 7 E (0, 1). number of trials
I: for t= 1 to 7' do
2: Compute the gradient estimator 9t-
3: 3 arg exx (x), where X. {It-1, Tt-1 1919.. ... I1-1 /1 9:
4: end for
20550
2D-50
4
EXPERIMENTS
SCO20
SCOBO
20
DMA-E
4.1 SIMPLE FUNCTIONS
In this section, we present experimental re- sults demonstrating the effectiveness of Al- gorithm [ on two simple functions: (l) Quadratic function: f(z)
|| I E
(a) Quadratic function
(b) Rosenbrock function
R100 (2) Rosenbrock function: f(x) =
EE ((1 (1-x;)² )2 100( - =²?)). x = Figure 3: Performance of different algorithms.
[r,,..,, E IR 100, To demonstrate the effectiveness of our algorithm and verify our theoretical
claims, we conduct two experiments, and all figures are obtained by averaging over independent runs and are visualized in the form of msdd
Comparing Algorithm I with existing algortihms. In this first experiment, we compare Algo- rithm I with the following algorithms in the existing literature: (1) ZZ-SGD (Nestrrvv & Spokoiny
2017): : A zeroth-order optimization algorithm for valuing oracle. (2) SCOBO (Cai et al. 2022):
A zeroth-order algorithm for pairwise comparing oracle. (3) GLD-Fast (Golovin et al. 2019): A
direct search algorithm for top-1 oracle, namely, (m, 1)-ranking oracle. (4) CMA-ES (Loshchllov
& Hutter 2016, Hansen al. 2019: : A heuristic optimization algorithm for ranking oracle.
To ensure a meaningful comparison, we fix the number of queries m = 15 at each iteration for all algorithms. For gradient-based algorithms, Z0-SGD, SCOBO, and our ZO-RankSGD, we

---

Published as a conference paper at ICLR 2024
query points for gradient estimation and 5 points for the line search. In this experiment, set m = k for ZO-RankSGD, i.c. it can receive the full ranking information. Moreover, we tune the hyperparameters such as stepsize, smoothing parameter, and line search parameter via grid search for each algorithm, and the details are provided in Appendix C_1 A high-dimensional experiment is also included in Appendix C.2 Our experiment results in Figure on the two functions show that the gradient- -based algorithm can outperform the direct search algorithm GLD-Fast and the heuristic algorithm CMA-ES. Besides, Algorithm can outperform SCOBO because the ranking oracle contains more information than the pairwise comparison oracle. Additionally, Algorithm behaves similarly to ZO-SGD, indicating that the ranking oracle can be almost as informative as the valuing oracle for zeroth-order optimization.
Investigating the impact of m and & on Algo- rithm | In this part, we aim to validate the findings presented in Lemma f and Theorem by running Algorithm [ with various values of m and k. To keep the setup simple, we set the step size 7) to 50 and the smoothing param- eter μ to 0.01 for Algorithm [ with line search (where 1 5 and 7 0.1). Figure illus- trates the performance of ZO-RankSGD under different combinations of m and k on the two functions, which confirm our theoretical find- ings presented in Lemma 4 For example, we observe that (m 10, 10) yields better perfor- mance than (m 100, k 1), as predicted by the second variance term in (10), which dominates and scales as (1//k).
me 10 t=
M 28
(B 10 1-3
18,2
260.
(a) Quadratic function
(b) Rosenbrock function
Figure 4: Performance of ZO-RankSGD under
different combinations of m and k.
Noisy ranking oracles. In practice, the ranking feedback we receive from human evaluators may have some mistakes or inaccuracies. In Appendix C.3] we also present experimental results with noisy ranking oracles, namely, these oracles do not always give the correct ranking feedback. Remarkably, our proposed ZO-RankSGD algorithm shows robustness in handling this kind of noisy feedback, making it well-suited for real-world applications. Looking forward, an interesting area for further exploration is the theoretical understanding of these noisy ranking oracles. This involves understanding how to formally represent the inaccuracy inherent in such oracles, similar to what
(Cai et al. (022) did for comparison oracles.
20:00
(a) Reacher-v2
(b) Swimmer-v2
(c) HallCheetah--2
Figure 5: Perfomance of ZO-RankSGD and CMA-ES on three MuJoCo environments
4.2 REINFORCEMENT LEARNING WITH RANKING ORACLES
Motivation. In this section, we illustrate how ZO- RankSGD can be seamlessly employed for policy optimization in reinforcement learning, given only a ranking oracle of the episode reward. Such a setting especially captures the scenario where human evaluators are asked rank multiple episodes
based on their expertise. Specifically, we adopt a similar experimental setup as (Cai et al. 2022] Duan et al. 2016). where the goal to learn a policy for simulated robot control with several problems from the MuJoCo suite of benchmarks (Todorov et al., 2012).. We compare ZO- SD-RankSGD to the CMA-ES algorithm, a commonly used optimization baseline in reinforcement learning (Bengs et al. 2021) that also solely relies on ranking oracle. Both algorithms are restricted to query the episode reward via a (5, -raanking oracle. To demonstrate the performance gap between ranking oracle and value oracle, we also include ZO-SGD for comparison. To make a fair comparison, ZO-SGD is designed to receive value feedback of points for each query. Additionally, we draw comparison between ZO-RankSGD and SCOBO; however, given the disparate nature of their query oracles, the comparison is intricate. For a comprehensive discussion of this aspect and more experiment details, refer the readers to Appendix C.4
7

---

Published as a conference paper at ICLR 2024
Results. The experiment results shown in Figure where the x-axis is the number of queries to the ranking oracle, and the y-axis is the ground-truth episode reward. In these experiments, we do not line search for ZO-RankSGD, instead, we let 1) = la, and decay them exponentially after every rollout. As can be seen from Figure 5] our algorithm can outperform CMA-ES by a significant margin all three tasks, exhibiting better ability to incorporate ranking information. Additionally, DDDRRnkSGD exhibits performance on par with ZO-SGD, reinforcing our findings from the experiment illustrated in Figure and underscoring the effectiveness of the ranking oracle in providing substantial ceamiizationrelevann information.
(a) Original
(b) Perturbed 1
(c) Perturbed 2
(d) Perturbed 3
Figure 6: Continuous property of reverse diffussin process. The used text prompt is A teddy bear is skiing, detailed, realistic, 4K, 3D.
4.3 TAMING DIFFUSION GENERATIVE MODEL WITH HUMAN FEEDBACK
In recent years, there has been growing interest in diffusion generative models, which have demon- strated remarkable performance in generating high-quality images (Ho et al. 2020 Song et al. 2020b Dhariwal & Nichol 202I). I). Despite these advancements, these models often struggle with capturing intricate details, such as human fingers or key elements in prompts, and sometimes fail to align with user aesthetics. To address this issue, we draw inspiration from recent successes in aligning Language Models with human feedback (Ouyang et al. 2022 Liu et al.] 2023] OpenAl 2022 Bai et al. 2022), and propose utilize human ran ranking feedback to enhance the generated images. We noticed a concurrent work (Lee et al.) (023) sharing a similar motivation with us. Specifically, their method is based on the existing approach of RLHF and utilizes considerable amount of pre-collected data for fine-tuning the diffusion model. Despite this shared motivation, our method tackles distinet problem from theirs, as our proposed method is not designed for fine- tuning, but to help the model better adapt to the need of new users at inference time, and the human feedback is collected in an online fashion. In this experiment, we aim to demonstrate the ability of ZO-RankSGD to improve the model's output at inference time by optimizing the control variables of generation, such as the latent embedding, with the underlying model fixed. A detailed description is provided below.
Experimental Setting. We focus on the task of text-to-image generation, using the state-of-the-ar Stable Diffusson model (Rombach et al. 2022) to generate images based on given text prompts. Firstly, we observe that a common practice for generating high-quality images in the community of Stable Diffusion is run the sampling process multiple times with different random seeds, and then pick the optimal one. Inspired by this, we choose to optimize the latent noise embedding, which is equivalent to random seed, using human ranking feedback through our proposed Algorithm [ with an aim to produce images that are more appealing to humans. This experimental setting offers several advantages, including: (1) The latent embedding a low-dimensional vector and thus requires only few rounds of human feedback for optimization. (2) It can also serve as a data- collecting step before fine-tuning the model. also worth noting that any continuous parameter in the diffusion model can be optimized similarly using human feedback.
Reverse diffusion process as a continuous mapping. Firstly, we remark that only bDEeb diffusion samplers, like DDIM (Song et al. (220a) and DPM-solver (Lu et al. (022). are used in this study, as now the reverse diffusion process will be deterministic and only depends on the latent embedding. We demonstrate that optimizing the latent embedding is a valid continuous optimization problem by showing that, with slight perturbations of the latent embedding, diffusion samplers can usually generate multiple similar images. An example of this phenomenon is in Figure where the first image is generated using a given latent embedding, while the next three images are generated by perturbing this embedding with noise drawn from (0, 0.
Examples. We illustrate several optimization results in Figure / where we ourselves provided the human ranking feedback during these experiments. These instances highlight the improvements
8

---

Published as a conference paper at ICLR 2024
in realism and detail that proposed Algorithm can bring about through the use of human ranking feedback. To illustrate, in the first example, the image optimized with human guidance portrays human fingers and eyes with enhanced accuracy. In the second example, the optimized image adheres more closely to the prompt instruction, successfully capturing the intended item orange juice. In the third example, the optimized image delivers more visually appealing depiction of muscularity. Taken together, these results demonstrate the potential of our approach in refining the quality of generated images using human feedback. For more examples like the ones in Figure and the details of the entire optimization process, we refer the readers to Appendix
Prompt
Initial
Human
CLIP
priest, blue rabes, 68 year old mon, national geogro phiic portreit, photo, phot agraphy -q
tedidy beat, holding a ottle of orange juice, sitting 30
Trendy Anthropomorphic aird, MOBA character cept art, Bk, unreal ongin
Figure 7: Examples of optimizing latent embedding in diffusion generative model. Initial: The initial images selected through multiple randomly generated latent embeddings serve the initial points for the later opti- mization process. Human: The images obtained by optimizing human preference. CLIP: The images obtained by optimizing the CLIP similarity score.
Human feedback vs. CLIP similarity score. To underscore the unique advantage of human feedback, we hold the ZO-RankSGD algorithm constant, and contrast images that were optimized with human preference against those optimized using the CLIP similarity score (Radford et al.) 202I]. CLIP, a cutting-edge model that contrasts language with images, calculates the similarity between given texts and images. However, when comparing the third and fourth columns in Figure 7 it is clear that since CLIP is trained on noisy text-image pairs from the internet, the images optimized using its similarity score can sometimes fall short of the original ones. Moreover, these CLIP-optimized images may not always resonate with human evaluators, further emphasizing the unique value of human feedback in refining image generation.
CONCLUSION
In this paper, we have rigorously studied novel optimization problem where only ranking ora- cles of the objective function are available. For this problem, we have proposed the first provable zeroth-order optimization algorithm, ZO-RankSGD, which has consistently demonstrated its effi- cacy across simulated and real-world applications. We also have presented how different ranking oracles can impact optimization performance, providing guidance on designing the user interface for ranking feedback. Our algorithm has been shown to be practical and effective way to incorporate human feedback, for example, it can be used to improve the detail of images generated by Stable Diffusion with human guidance. Possible future directions to this work may include extending the theoretical results to incorporate noisy and uncertain ranking feedback, combining ZO-RankSGD with a model-based approach like Bayesian Optimization (Frazier 2018), or the techniques from active learning (Monarch) 2021). to further improve the query efficiency, and also applying it to other scenarios beyond human feedback. Besides, another important point is to investigate what is the optimal choice m and l if we jointly consider the cognitive burden of humans and the query complexity via real social experiments.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
The work is supported by Shenzhen Science and Technology Program under Grant No. RCJC20210609 1 104448114 14, the NSFC, China, under Grant 620714099 and by Guangdong Provincial Key Laboratory of Big Data Computing.
REFERENCES
Raul Astudillo and Peter Frazier. Multi-attribute bayesian optimization with interactive preference learning. In International Conference on Artificial Intelligence and Statistics, pp. 4496 4507.
PMLR, 2020.
Yuntao Bai, Andy Jones, Kamal Ndousse, Amanda Askell, Anna Chen, Nova DasSarma, Dawn Drain, Stanislav Fort, Deep Ganguli, Tom Henighan, al. Training helpful and harmless assistant with reinforcement learning from human feedback. arXiv preprint arXiv:2204.0586,, 2022.
Viktor Bengs, Róbert Busa-Fekete, Adil EI Mesaoudi-Pant Paul, and Eyke Hüllermeier. Preference-based online learning with dueling bandits: A survey, Mach. Learn. Res., 22:7-1, 2021.
HanQin Cai, Daniel Mckenzie, Wotao Yin, and Zhenliang Zhang, A one-bit, comparison-basee gradient estimator. Applied and Computational Harmonic Analysis, 60:242-266, 2022.
Suiyao Chen, Lu Lu, Qiong Zhang, and Mingyang Li. Optimal binomial reliability demonstration tests design under acceptance decision uncertainty. Quality Engineering, 32(3):492-508, 2020.
Suiyao Chen, Jing Wu, Naira Hovakimyan, and Handong Yao. Recontab: Regularized contrastive representation learning for tabular data. arXiv preprint 18..5121, 2023a.
Yinda Chen, Wei Huang, Xiaoyu Liu, Qi Chen, and Zhiwei Xiong. Learning multiscale consistency for self-supervised electron microscopy instance segmentation. In /EEE International Conference Acoustics, Speech, and Signal Processing, 2023b.
Yinda Chen, Wei Huang, Shenglong Zhou, Qi Chen, and Zhiwei Xiong. Self-supervised neuron segmentation with multi-agent reinforcement learning. In Proceedings of the Thirty-Second In- ternational Joint Conference on Artificial Intelligence, pp. 609-617, 2023c
Yinda Chen, Che Liu, Wei Huang, Sibo Cheng, Rossella Areucci, and Zhiwei Xiong. Genera- tive text-guided 3d vision-language pretraining for unified medical image segmentation. arXiv preprint arXiv:2306. 230.0233.6....1, 2023d.
Zhongxiang Dai, Bryan Kian Hsiang Low, and Patrick Jaillet. Differentially private federated bayesian optimization with distributed exploration. Advances in Neural Information Processing Systems, 34:9125-9133 2021.
Prafulla Dhariwal and Alexander Nichol. Diffusion models beat gans on image synthesis, Advances in Neural Information Processing Systems, 34:8780-8794, 2021.
Yao-Xiang Ding and Zhi-Hua Zhou. Preference based adaptation for learning objectives. Advances in Neural Information Processing Systems, 31, 2018.
Jinshuo Dong, Aaron Roth, and Weijie Su. Gaussian differential privacy. Journal of the Royal Statistical Society, 2021.
Yan Duan, Chen, Rein Houthooft, John Schulman, and Pieter Abbeel. Benchmarking deep reinforcement learning for continuous control. In International conference machine learning, pp. 1329-1338, PMLR, 2016.
John C Duchi, Michael I Jordan, Martin J Wainwright, and Andre Wibisono. Optimal rates for zero-order convex optimization: The power of two function evaluations. IEEE Transactions on Information Theory, (1(5):778822808 2015.
10

---

Published as a conference paper at ICLR 2024
Cynthia Dwork, Aaron Roth, al. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci,, 9(3-4):211-4077 2014.
Peter Frazier. A tutorial on bayesian optimization. arXiv preprint arXiv:1807.0281/1 2018.
M. Gao, Wei, He, D. Zhang, Tian, Huang, and C. Zheng. Fuzzy controller-based design and simulation of an automatic parking system. Journal of Software Engineering and Applica- tions, 16:505-520, 2023. doi: (0.4266/sca.2223316900
Daniel Golovin, John Karro, Greg Kochanski, Chansoo Lee, Xingyou Song, and Qiuyi Zhang. Gra- dientless descent: High-dimensional zeroth-order optimization. arXiv preprint arXiv: 2019.
Nikolaus Hansen, Youhei Akimoto, and Petr Baudis. CMA-ES/pycma on Github. Zen- odo,
February 2019. URL https:///ci.org//// 5281/
zenodo 2559634
Filip Hanzely, Konstantin Mishchenko, and Peter Richtárik. Sega: Variance reduction via gradient sketching. Advances in Neural Information Processing Systems, 31, 2018.
Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusson probabilistic models. Advances in Neural Information Processing Systems, 33:6840-6851, 2020.
Ralph L Keeney and Howard Raiffa. Decisions with multiple objectives: preferences and value trade-offs. Cambridge university press, 1993.
Wataru Kumagai. Regret analysis for continuous dueling bandit. Advances in Neural Information Processing Systems, 30, 2017.
Kimin Lee, Hao Liu, Moonkyung Ryu, Olivia Watkins, Yuqing Du, Craig Boutilier, Pieter Abbeel, Mohammad Ghavamzadch, and Shixiang Shane Gu. Aligning text-to-image models using human feedback. arXiv preprint arXiv:2302.12192 2023.
Chen Li, Haotian Zheng, Yiping Sun, Cangqing Wang, Liqiang Yu, Che Chang, Xinyu Tian, and Bo Liu. Enhancing multi-hop knowledge graph reasoning through reward shaping techniques. arXiv preprint urXiv:2403.05801, 2024a.
Lisha Li, Kevin Jamieson, Giulia DeSalvo, Afshin Rostamizadeh, and Ameet Talwalkar, Hyperband: A novel bandit- based approach to hyperparameter optimization. The Journal of Machine Learning Research, 18(1):6765 6816, 2017.
Shaojie Li, Xinqi Dong, Danqing Ma, Bo Dang, Hengyi Zang, and Yulu Gong. Utilizing the light- gbm algorithm for operator user credit assessment research. arXiv preprint 21t.:2403..4488, 2024b.
Shaojie Li, Haichen Qu, Xinqi Dong, Bo Dang, Hengyi Zang, and Yulu Gong. Leveraging deep learning and xception architecture for high-accuracy mri classification in alzheimer diagnosis. arXiv preprint arXiv:2403. 16212, 2024c.
Zhenglin Li, Yangchen Huang, Mengran Zhu, Jingyu Zhang, JingHao Chang, and Houze Liu. Fea- ture manipulation for ddpm based change detection. arXiv preprint arXiv:2403. /5943, 2024d.
Zhiyuan Jerry Lin, Raul Astudillo, Peter Frazier, and Eytan Bakshy. Preference exploration for efficient bayesian optimization with multiple outcomes. International Conference on Artificial Intelligence and Statistics, pp. 4235-4258. PMLR, 2022.
Hao Liu, Carmelo Sferrazza, and Pieter Abbeel. Languages rewards: Hindsight finetuning using human feedback, 2023. URL http://wwwrraaaa////3/e///// 02676
Tianrui Liu, Changxin Xu, Yuxin Qiao, Chufeng Jiang, and Weisheng Chen. News recommendation with attention mechanism. Journal of Industrial Engineering and Applied Science, 2(1):21 212:26 2024a.
Tianrui Liu, Changxin Xu, Yuxin Qiao, Chufeng Jiang, and Jiqiang Yu. Particle filter slam for vehicle localization, Journal of Industrial Engineering and Applied Science, 2(1):27-31, 2024b.
11

---

Published as a conference paper at ICLR 2024
Iyy Loshchilov and Frank Hutter. Cma-es for hyperparameter optimization of deep neural networks. arXiv preprint 17X4:1604.00269, 2016.
Cheng Lu, Yuhao Zhou, Fan Bao, Jianfei Chen, Chongxuan Li, and Jun Zhu. Dpm-solver: A fast ode solver for diffusion probabilistic model sampling in around 10 steps. arXiv preprint arXiv:2206.00927, 2022.
Danqing Ma, Shaojie Li, Bo Dang, Hengyi Zang, and Xinqi Dong. Fostc3net: A lightweight yolovv based on the network structure optimization. arXiv preprint arXiv:2403.13700 137003 2024.
Robert Munro Monarch. Human-in-the-Loogy Machine Learning: Active learning and annotation for human-centered Al. Simon and Schuster, 2021.
John A Nelder and Roger Mead. A simplex method for function minimization. journal, 30--333, 1965.
The computer
Yurii Nesterov and Vladimir Spokoiny. Random gradient-free minimization of convex functions. Foundations of Computational Mathematics, 17(2):527-566, 2017.
Fanghao Ni, Hengyi Zang, and Yuxin Qiao. Smartfix: Leveraging machine learning for proactive equipment maintenance in industry 4.0. In The 2nd International scientific and practical confer- ence "Innovations education: prospects and challenges of today" "(Janurry 16-19, 2024) Sofia Bulgaria. International Science Group. 2024. 389 p., pp. 313, 2024.
OpenAL hhalopt.tttps/oppenai.cmm blog/chatgpt/, 2022. /tog/chatgpt//
URL https: com/
Long Ouyang, Jeff Wu, Xu Jiang, Diogo Almeida, Carroll I. Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, al. Training language models to follow instructions with human feedback. arXiv preprint arXiv:2203.021555 225510255,, 2022.
Yaniv Plan and Roman Vershynin. Robust 1-bit compressed sensing and sparse logistic regression: A convex programming approach. IEEE Transactions on Information Theory, 59(1) (9112 494, 2012.
Michael JD Powell. Direct search algorithms for optimization calculations. Acta numerica, 7:287- 336, 1998.
Gang Qiao, Weijie Su, and Li Zhang. Oneshot differentially private top-k selection. In International Conference on Machine Learning, pp. 8672-8681. PMLR, 2021.
Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. Learning transferable visual models from natural language supervision. In International conference on machine learning, pp- 8748-88 8763. PMLR, 2021.
Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser, and Bjöm Ommer. High- resolution image synthesis with latent diffusion models. Proceedings of the IEEE/CVF Con- ference Computer Vision and Pattern Recognition, pp. 10684-10695 2022.
Jiaming Song. Chenlin Meng, and Stefano Ermon. Denoising diffusion implicit models. arXiv preprint arXiv:2010.02502, 2020a.
Xingchen Song, Di Wu, Binbin Zhang, Zhendong Peng, Bo Dang, Fuping Pan, and Zhiyong Wu. ZeroPrompt: Streaming Acoustic Encoders are Zero-Shot Masked LMs. In Proc. INTERSPEECH 2023, pp. 1648-1652, 2023. doi: 221443//merspeechh2033-44434
Yang Song, Jascha Sohl-Dickstein, Diederik P Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Score-based generative modeling through stochastic differential equations. arXiv preprint arXiv:2011.13456. 2020b.
Nisan Stiennon, Long Ouyang, Jeffrey Wu, Daniel Ziegler, Ryan Lowe, Chelsea Voss, Alec Radford, Dario Amodei, and Paul F Christiano. Learning to summarize with human feedback. Advances in Neural Information Processing Systems, 33:3008-3021, 2020.
12

---

Published as a conference paper at ICLR 2024
Jing Su, Chufeng Jiang, Xin Jin, Yuxin Qiao, Tingsong Xiao, Hongda Ma, Rong Wei, Zhi Jing, Jiajun Xu, and Junhong Lin. Large language models for forecasting and anomaly detection: A systematic literature review. arXiv preprint arXiv:2402.10333 2024.
Yiping Sun. Transtarec: Time-adaptive translating embedding model for next poi recommendation.
arXiv preprint arXiv:2404.07092 2024.
Yiping Sun, Yu Cui, Jinglu Hu, and Weijia Jia, Relation classification using coarse and fine-grained networks with sdp supervised key words selection. In Knowledge Science. Engineering and Man- agement: 11th International Conference, KSEM 2018, Changchun, China, August 17-19, 2018, Proceedings, Part I 11, pp. $14-522.33 Springer, 2018.
Zhen Tan, Lu Cheng, Song Wang. Yuan Bo, Jundong Li, and Huan Liu. Interpreting pretrained language models via concept bottlenecks. arXiv preprint arXiv:2311.00044 2023.
Zhen Tan, Alimohammad Beigi, Song Wang, Ruocheng Guo, Amrita Bhattacharjee, Bohan Jiang, Mansoorch Karami, Jundong Li, Lu Cheng, and Huan Liu. Large language models for data annotation: A survey. arXiv preprint arXiv:2402. 13446, 2024a.
Zhen Tan, Tianlong Chen, Zhenyu Zhang, and Huan Liu. searsity-guider holistic explanation for Iims with interpretable inference-time intervention. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 21619-21622 2024b.
Zhiwei Tang and Tsung-Hui Chang. Fedlion: Faster adaptive federated optimization with fewer communication. arXiv preprint arXiv:2402.099. 2024.
Zhiwei Tang, Tsung-Hui Chang, Xiaojing Ye, and Hongyuan Zha. Low-rank matrix recov- cry with unknown correspondence. In Robin J. Evans and Ilya Shpitser (eds.), Proceedings of the Thirty-Ninth Conference on Uncertainty in Artificial Intelligence, volume 216 of Pro- ceedings of Machine Learning Research, pp. mlr
PMLR, 31 Jul Aug 2023. URL arroceeeinggsm.r.ppresss.. v21 /ateee//2.2////aa23...3. html
Zhiwei Tang, Jiasheng Tang, Hao Luo, Fan Wang, and Tsung- Hui Chang. Accelerating parallel
sampling of diffusion models. arXiv preprint arXiv:2402.09970 2024a.
Zhiwei Tang, Yanmeng Wang, and Tsung- Hui Chang. z-signfedavg: A unified stochastic sign- based compression for federated learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 15301
2024b.
Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model-based control. In 2012 JEEE/RSJ international conference intelligent robots and systems, pp. 5026-5033. IEEE, 2012.
Hao Wang, Zhiwei Tang, Shutao Zhang, Chao Shen, and Tsung- -uing-Hui Chang. Embracing uncertainty: A diffusion generative model of spectrum efficiency in 5g networks. In 2023 International Con- ference Wireless Communications and Signal Processing (WCSP), pp. 880-88 885. IEEE, 2023.
Y. Wei, D. Zhang, M. Gao, Y. Tian, Y. He, B. Huang, and C. Zheng. Breast cancer prediction based machine learning. Journal of Software Engineering and Applications, 16:348 360, 2023. doi: 10.4236/jsea.200 2023.168018.
Yuxin Wen, Neel Jain, John Kirchenbauer, Micah Goldblum, Jonas Geiping, and Tom Goldstein. Hard prompts made easy: Gradient- based discrete optimization for prompt tuning and discovery. arXiv preprini arXiv:2302.00 230200368. 2023.
Jing Wu, Suiyao Chen, Qi Zhao, Renat Sergazinov, Chen Li, Shengjie Liu, Chongchao Zhao, Tian- pei Xie, Hanqing Guo, Cheng Ji, et al. Switchtab: Switched autoencoders effective tabular learners. arXiv preprint arXiv:2401.02011 2024.
Yisong Yue and Thorsten Joachims. Interactively optimizing information retrieval systems ducling bandits problem. In Proceedings of the 26th Annual International Conference on Machine Learning, pp. 1201-1208, 2009.
13

---

Published as a conference paper at ICLR 2024
Hengyi Zang. Precision calibration of industrial 3d scanners: An ai-enhanced approach for improved measurement accuracy. Global Academic Frontiers, 2(1):27-37, 2024.
Dan Zhang, Fangfang Zhou, Yuanzhou Wei, Xiao Yang, and Yuan Gu. Unleashing the power of self-supervised image denoising: A comprehensive review. arXiv preprint arXiv:2308.0024 2023a.
Ye Zhang, Mengran Zhu, Yulu Gong, and Rui Ding. Optimizing science question ranking through model and retrieval augmennte generation. International Journal of Computer Science and Infor- mation Technology, 1(1):124-130, 2023b.
Ye Zhang, Yulu Gong, Dongji Cui, Xinrui Li, and Xinyu Shen. Deepgi: An automated approach for gastrointestinal tract segmentation in mri scans. arXiv preprint arXiv:2401.15354 2024a.
Ye Zhang, Mengran Zhu, Kailin Gui, Jiayue Yu, Yong Hao, and Haozhan Sun. Development and application of monte carlo tree search algorithm for simulating da vinci code game strategies. arXiv preprint Ttt1:2403.1072000 2024b.
Kai Zheng, Tianle Cai, Weiran Huang, Zhenguo Li, and Liwei Wang. Locally differentially private (contextual) bandits learning. Advances Neural Information Processing Systems, 33:12300- 12310, 2020.
Xingyu Zhou and Jian Tan. Local differential privacy for bayesian optimization. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 11152-11159, 2021.
APPENDIX
A A SIMPLIHIED EXPRESSION FOR
Let g E) be the DAG constructed from the ranking information of mm),)) we denote the input degrees and output degrees x; E N as degi (1) and deg (1) respectively. We first notice that
m
Σ (E, - Ei)
(degin (1) degom (i)) E.-
(14)
(3E))E
1=1
Denote Wl = degin (1) degour (i), if O ((m.k)))
(I, = (i1, "hi.....pp ik), then we can compute that
wi; degin (in) degout (iy) -(m -j) 2j m m, j = 1.....
(15)
W/ degin (g) degom (4) k 0 k. 9 ix).
(16)
MISSING PROOF
Proof of Lemma 7 In the following proof, denote p(-) the pdf function of (( Ta) for arbi- trary dimension d.
We first rewrite (V(()).g())) as follows:
(V)(()))(=)) (V
-y ( +)) (17)
By the second-order Taylor expansion with Cauchy remainders, we notice that
42
f(x + p&1) = f(x) (VV(()).))))
+
f(11)11
(18)
2
4
f(x + #$2) f(x) +V)())))
C v2 f22)
(19)
2
where and D2 two points around r.
14

---

Published as a conference paper at ICLR 2024
With (88) and 19
can write S1, pu) follows:
Sign (VV.(z)) - E2) + " v "53 v2 ( ((2)(2)
(20)
Now we start bound the term
TE [S (3,, E1: E2, n.) (V - E2),
(21)
where the expectation is taken over the random direction and &2.
Before doing that, we first define two important regions:
R1 ((), (V)()), - (2) > 0),
(22)
R11 ((),6) (5,
E R1, E1, E2, M)) # Sign ((VS(z)) 2))).
(23)
Notice that when (21,4) E R1, (y, E1, $2, p)) # Sign (VV((z), - (2) is equivalent to
(V/()), - (2) + レー v (x))S - 55 V>I(x>)< < 0.
Also, from L-smoothness, we can know that
μL
(1ls + 1(2218) I 2
f(m))
55 V f(2))22
We denote the region
nb (IL 11 1122 < <0)-
R1 ((E1, (2), E (V E2)
(24)
is easy to verify that R1 C Rn. Let R12 = RR//R11 we can have the following inequality.
f R,
(25)
[
RI/Rn
+ */
-
(26)
*Jnn
( (Vi()), - -
RI/RI
-f JRn
- p()
(27)
a)) -
R1/R11
(Vf(x). ( p(E dE
(28)
R1
22
(Vf(x)) - -2) p(E: 1p )E de de
R12
(Vf(z), E2) p(E)(()) )p
(29)
JR
Before we proceed to study the property of the integral (29 let first define an important function. Consider the function h(u, r, d) RR x R, x Z +
R defined as follows:
FFed-1 ((2/2) 2v2u
h(v, r, def. V2v
x x p(x)dr,
(30)
r
where F2)-1()) is the CDF of the x2 distribution with 2d degrees of freedom. With this function, can have the following lemma that presents the close form of the integrals in 29
15

---

Published as a conference paper at ICLR 2024
Lemma 5.
/
(Vf(z), - (2) pii = V [Vf())]
(31)
R1
- - ((a M(V
(32)
R12
Also, need an important lemma on h(,r d).
Lemma 6. For any E Z4, there exist a constant Ca > O such that for any v 2,,r 0.
1
1 Car.
h(,,,,
(33)
Combining 29
32 and 33 we have
J Sy E2, (VI()), E2) (
[V[(=)]] Capl.. (34)
Similarly, if we define
R₂ = ((51,2)) ( - <0}.
we have
J (V - (1)
(35)
R2
(4 - (() (L)) dE
(36)
R2
- [ E1, - (L:
de
(37)
R2
becasue the integral Ri is symmetric to the integral R2 by swapping & and &2. Since 22d R U R2) has zero measure, we have
E (x. E1, -VS()))) - E22] -2 / R2
- - [ Caju..
(38)
(39)
Proof of Lemma set:
Suppose that kmm,k)) (I1, (k))..)k)) seperate N into two node Mi (úr, . ix) and No {a E (1,...mm q & (ii,....i43 4x)
Firstly, since the subgraph of G on Mi is complete graph, the number of edges in this subgraph is k(k (5--1), 1)/2. The remaining edges in G connect the node N₂ to the node in N1, hence the number of them is (mm - k). Therefore,
E k(k 1)/2 + k(m - k) = km - (K² + k2/2.
(40)
Now we denote the set of neighbooring edge pairs as ((i..)). (f. E E Eli + 8'). We can split S as the following five set:
S (.
(41)
S₂ ((.D)...))eex&@i(///MMM...... ENN.
(42)
S₂ ((..).....)e33x&8(:::ee... VEN.. EN1),
(43)
S4 ((1,).6..).=Ex8i1()))..... V
(44)
S ((0.)).0..))6Exx111...... ENN, Ni)
(45)
16

---

Published as a conference paper at ICLR 2024
For the first set S1, compute that
16 = k(k - - 2),
S 6
1)(k-2);
(46)
3)
because every edge pair composes of three nodes, and every three nodes can form 6 edge pairs. For the second set S2, have
1: (m (m- 1:) 1),
|22 2(m I:)
(47)
because [W2] = m k and [(i, i') W x Mi i + = 2(²)
Similarly, for the set S3 and S4, we can obtain
| |Sa| 2 k)) (2)
k
(m --))-( 1).
(48)
Finally, for the set Sr, we can compute that
2k: m k) kmm k)( k- 16-1). 1),
S
(49)
because [WG] = and (((i, E N2 x 2 i + H') = 2(m
In all, we have
S = |S1] + |Sy] + S + | + S
(50)
k-k - 1)(k - 2) + 3(m k:) (h: - 1) k(m k))(m k --1)
(51)
= m²k + mk² 13 h2 4mnk 2k.
(52)
Proof of Lemma 3 inequality, we have
We first prove that M) S 2d. From convexity of - || and Jensen's
E Er
(5, - E2)]
E
[[s (2, +2)1 2d.
(53)
&
Then prove M2(f.H) μ)
2d. From the Schwarz inequality, we have [5y(2,E1, E1, E2, () (2, Ei, Ea, ()(E) E2, Ea)]
E
(54)
$a
[IEI - Eell?]
[1K51 - Es|?] 2d.
E
(55)
E1
Now study the mean vector 5g (1, E2) under the condition (² cld- We first write as sum of three vectors.
E [S, E1, (1 - E2)
(C1 - (())))))(()))ss))dddd
(56)
+ (
(51 - (
(57)
+
(E2 - (id
(58)
For the three vectors, have
(Ei - (2)pE) ((rtts))-
(59)
f
(pp [(=tn()=/((==p5)))
(60)
=0,
(61)
17

---

Published as a conference paper at ICLR 2024
and
seetne (51 (a))((Gil((a)ddd(icoo
(62)
((otut))) (E2 - (()p((1))(())ddd5)) (E2)
(63)
S (E2 - (e))p(())((s)ddddre
(64)
Therefore, we can write &s [5 E1, E2. (1( E2)] as
Ea (2, Ea, - E2)] = ((attat))
(ε1 -61-500 (0)o
(65)
study the integrals J(antee) (ap(E))((E))d We can compute that
Now
we
and
S Stommeenssstoneee ((
(66)
- -Jee (Jronnansscenes p(E2)dG2 EIP(EI)dE.:
(67)
and,
(ap(ti)p(Es)ddidde
(68)
Jhs (Fromssissetttee p(E))dE) Eap(E2)
(69)
(Fres (l22
EsP(ET)dE
(70)
The condition f2)(2) cla implies that is quadratic function. We denote M(.) as the Lebesgue measure on Rd. Notice that M(1f2 f(æ + με2) = f(x + m({))) 0 because it is known that the zero point of any polynomial function has zero Lebesgue measure. Therefore, have
H p(Ex)dE2 + ( P(E2)d(2
(71)
=1 - d(E2) =
(72)
Hence we have
(51 - (
(73)
-2 J (rramnnnzZiiaeee)
(sp(E)) S Exp(E))dEs
d(E))
(74)
-2 [
p(E2)dE2 Eip(Ei)dE..
(75)
Since v²f(x) = cla. we have
1 f(x + ((+++()== = + +V =n²l "111 11..11
18

---

Published as a conference paper at ICLR 2024
Without loss of generality, assume [[V and denote El 2(V/(a). Vf(z) - f1. Is
|//(=]]
easy to verify that Çi also follows (00, La). |[ ||&i|| and f(æ (E1) = f(x + ME1) Therefore, we have
Jac ( P(22)
(Ip(E))dE
(76)
= =soa (JrcnnsiSSOAAe)
d52
ETP(E))dE
(77)
1 J (Frervenssoooee
(51 + p())())
(78)
(Lee (Freesssissienes)))
(V((z),
Vi(x)
p(E2)dS2
[s(x))] P(E))
(79)
|
Furthermore,
Use (HressensS (E2)
(f)))
[VI(())
2
pl )de
(()))ds
[V/())]
[VJ(()]]
(80)
Finally, we have
EI, - <a>1|
E E1.
(81)
(fez ( (rreenciisseeeesss p({2)d52
Vf(x) 2
(Vf(x)) [V](')] P(E))dE)
(82)
[V/(']
32
(83)
Proof of Lemmal
We first compute that
[1
E
Σ (E, Ex)
(84)
(1S)EE
For ease of writing, we denote B(i Ej - E, = Sy(m, Eú, 1))5 -Ei) and & as the undirected version of
E
Σ (B.D)E
B(i
(85)
=E
Σ
Bun Σ
(BuD, B(r.))++
Σ
(Bus> Burn))
(86)
(FJ)EE
(LEE
(6.))EE
( WJEE ifft'
(1' J*''
19

---

Published as a conference paper at ICLR 2024
With the two metrics Mi(f. p), M2)f. bound the four terms in (66 as follows:
E B 11 = E [1s -Eil/2] 2d,
(87)
E ( (B()))) (( E [[ B(ass) S M2(,.)):
(88)
E (B)))) (B (9)) | [Bرر]] 11 - Mi(f.n)
(89)
Taking
(8
(88
and
89
into 86
obtain
Σ
(
(90)
(8,))EE
Σ 2d
Σ M2(s,N)
Σ MI(f,N)
(91)
(i,))E
(G,))E (J'E)EE its'
(6,))E
2 N(E) (18) - N(E) - (1))
(92)
Combing 92 with
84
obtain
2d
N(E)
M2(fs 18 - -N(E) 18
[|
M (f.)P)
(93)
18
E
2d
N(E)
M2(f. + Mi(f.A).
(94)
[8
l812
Proof of Theorem
Consider the f-th iteration, from L-smoothness we know that
f(x)) f(=-() - 172
11 1l.
(95)
Using Lemma T and Lemma 4 we have
2
B[f(x1) f(x=-1)) 5 - (() +
E
[llge 12
(96)
2
L
2d
N(E)
- <|[[f(( CamuL +
Mz(f. +M.f
2
[
[8p
(97)
where the expectation taken over the random direction E(,,1)) "* E(t,m) Rearrange the inequality to obtain
[V/(==)\|s [[((r-))) f(x)) + CapL + nl ( 2d
N(E) M2(f.
M(..))
2 [
E
(98)
Summing up over T iterations and dividing both sides by T, we finally obtain
T Els(z0) - ((TT) + +Capt + 7l 2d
N(E)
[
+
M2(J.1) Mi(s.u)
TTT
[3]
l8
(99)
S [100) - 5r
CapL + nT. ( 2d.
N(E)
+
M2(f. MF
7/T
[/
(100)
20

---

Published as a conference paper at ICLR 2024
The proof is completed by noting that
T
E
min rE LEmnT
[V{(==11)]
E
T
Σ
V (x
Proof of Lemma
5
Without loss of generality, we assume [|V](z)] # 0. We first prove that
1 [
(Vf(z), Ee) ((L)))((())(()d
Now we denote
[V((z). -
/2
Notice that x follows the distribution M/0, 1). Therefore, we have
fV(2)) E2) ((E)))(()))((
(101)
R1
1 rp(x)dr = |f(x)]]
=v2[Vf((T]]
(102)
220
where we use well-known fact that (soo)p(dd V2
Then we will prove
f R12
(Vf(z).E - [2) (() = A[IVf(=)]l ,LL d).
Notice that
n1 (lle: 11 (I<21)) 0).
R12 ((E1,E2) (2),6) E Rı, Ri, (Vf(),, E2)
We can see that R12 is a ball in R2d:
1
1
21 1212
R12
(41,E2) |
E - uL
vf(z)
+
32 +
vf(x)
<
(103)
HL
Now we denote ( = I- I Rd o [V)())
[ E R2d Notice that still
follows isotropic multivariate Gaussian distribution, we can simplify the integral in LHS of 32 as:
(())
(104)
where Sc(Ø) - (c1 c -
101 P
We argue that for any rotation matrix R E 2ddxdd i.e., det( = 1 and RT R-1, We have
SS (0.))(()) / (s
(Ro.))(()dd
(105)
To that, rotate by R. Denote Ç' RT Ç. we first have
21

---

Published as a conference paper at ICLR 2024
1 1.l
||5
1
1101
(c()))
51
RC
(RC'K' Se(())
1221,2
1el
n²
(106)
1 ( p())s( [ JIRCICEESAOO)) (Ro, RC') pl p(
(dRC ((.5")((''dc")
Sy((0)
(107)
where we use the property of p(-): p(RC') = p(5').
Now we denote o' = II|@|I, O,.... 0 E R2d it is easy to see that ø' is a rotated version of ø. ie., there exists rotation matrix R'' such that o' R's. Denote ( [4,, m. C2d [ and 6/1 I2,..., S2al T We have
SSCO (c(0)
(()))
(108)
I (o'.s)((()d
(109)
(sc(ar)
= =|ه0||
(ip(C)d
(110)
(c1- 1 ++5-++ "+sg+... +22
uag 2=12
=I -||=||
!
C1
1012 (s | p(S/))dG,) p(si)as..
(111)
Notice that (2. Sea are i.i and following standard Gaussian distribution, and hence 23 +... 22 follows the Chi-square distribution with 2d degrees of freedom. Therefore,
1 Sc(()
( p(C)dc
(112)
211a11
11012
|!ll! ") p(Gi)dSs
=||0||
F1
(113)
11222
2lle11
(21|xb
=||0||
Fed-11
L1 (1
(i d((
(114)
μL
n4 ((o))
22 (2/211V/(0)) -61 -s)ss) $1 p(si)acs
-(2]|V[(>||
Ci Fdd-1
(115)
NL
(116)
Proof of Lemma 6 We define the fucntion q(u, d) R_ x Z+ + R4 as follows:
f0
2/24 xF2d-1 ((2/2u 2) x p(x) dx.
q(u, d)
(117)
Notice that ((u, r, d) (2ug(u/T,d)
We first need prove an important property of the function g(u, d):
lim q(u, d) 40000
2
22

---

Published as a conference paper at ICLR 2024
Consider arbitrary >> 0. Since
f xp(x) dx 1
there exists N2 N1 0 and such that
V2n"
N1
xp(x)dr S 3
(118)
0
0 xp(x)dd S
(119)
3
On the other hands, for every u > No
since (2v2u - x)) x monotonically increasing on [N1, Nz).
V2
we have
N2
= ((2v2u- - 2) 2) p(x)dxx > F2a-1 (2v2u-NNi) /.v.
N2
Ni
xp(x))d. (120)
N1
No
Notice that
lim F2a-1 ((2v2u-Ni) Ni) =1,
Mi))
there must exist a number Ng such that if u > N3. then
F2d-1 1 (2222u - N1) Ni) 1 - V2TE.
(121)
Putting together 120 and 121 because 0 S F2d-1 ((2/2u x) x) S 1, if max we can obtain
<2' Nz).
100
2v2u
xp(x)dr-
xF ((2v2-- - 2)) x)) plz)dox
(122)
2c
xp(x)dr P/h. N:
xF2d-1 ((2v2u - x) 2) p(x)dr
+
(123)
3
N₂
N1
2E
N2
xp(r)dr Fra-1 (2222 Ni) pmm xpl())dr
+
(124)
26
N2
xp(r)dr- (1 (1- --V2xc) 1//, xp(x)dr
+
(125)
3
Ni
Nr
28
N2
2e
+
xp(x)dx
+ V2Te =e.
(126)
3
3
N₂
3
V2T
Taking E + 0, hence we know that
| +00
1
lim
q(u, d)
xp(x)dr=
1+000
2
Since lim q(u,d) d)
there exists a constant Ca such that whenever (2 + :) u Ce,
V2x"
we have
1
1
1
1
g(u,a) d) 2
+
(127)
22T
2/2T
4/2)
2
4/2
Therefore, whenever (1 + 2) v Car, we have
Z
h(u,,, 2uq(u//r, 2 2/ + 1)
1
+ 4) r
1
4
Car.
(128)
2/7
On the other hand, when [ 2 + 1) 1 < Car, we have
1
4)
11
1 -
Me, r, d) = /2uq(u/r,d))20
v 4 Car.
(129)
2
23

---

Published as a conference paper at ICLR 2024
C EXPERIMENT DETAILS
C.I HYPERPARAMETER CHOICES FOR THE EXPERIMENTS IN SECTION 4.1
Figure 8 and 9 show the performance of tested algorithms in Figure 3 Juder different hyperparameter settings. For gradient-based algorithms, ZO-SGD, SCOBO, and Z0-RankSGiD, we tune the stepsize and set 0.1 for the line search. We need remark that when implementing the SCOBO (Cail et al. 2022), we remove the sparsity constraint because we found that it will lead to degraded per- formance for non-sparse problems like the ones we tested. For GLD-Fast,
tune for the diameter of search sparse, denoted as μ. For CMA-ES, we tune for the initial variance, also denoted as μ in we select the optimal choices of hyperparameters based on Figure 8 and 9 for each algorithm, respectively.
the figures. To rum the experiment in Figure 3
oboect VaRUE
obpectvve
1 0.023
n=
25
05
(a) ZO-SGD
(b) SCOBO
(c) ZO- 10-RankSGD
odjettee value
A1
Berations
lerations
(d) GLD-Fast
CMA-ES
Figure 8: Hyperparameter tuning on Quadratic function.
C.2 EXPERIMENTS ON HIGH-DIMENSIONAL OPTIMIZATION PROBLEM
this section, we examine the performance R0-RankSGD on a high-dimensional optimization problem, and the results is presented in Figure 10 Specifically, we adopt the same setting as the experiments in Figure B except that we increase the problem dimension 10000. is worth noting that the CMA-ES is longer included in this experiment due to the overwhelming computation time. This is mainly because, at this problem scale, CMA-ES requires updating 10000 x 10000 covariance matrix.
As we can see, the phenomenon is similar to the results presented in Figure showcasing the ability of -20-RankSGD on tackling nigh-dimensional problems.
We also provide more details for the hyperparameters selection in these experiments as we did in Section C.1 See Figure 11 and 12 for this information.
24

---

Published as a conference paper at ICLR 2024
1.0000
20
1..00
coppection
1-001
0.00
Tter 2E onG
Rerotions
Rerations
(a) ZO-SGD
(b) SCOBO
(c) ZO-RankSGD
2.1
2.01
30pcctice volie
0.991
1.0
0.002
20
(d) GLD-Fast
(c) CMA-ES
Figure 9: Hyperparameter tuning on Rosenbrock function.
objective value
objecttive valluo
4.8
20-SGD
ZO-SGD
SCOBO
SCOBO
70- 70-RankSGD
ZO-RankSGD
28.
GLD Fast
GLD-Fast
Ierratons
Iterations
(a) Quadratic function
(b) Rosenbrock function
Figure 10: Performance of different algorithms on the 10000-dims optimization problems.
25

---

Published as a conference paper at ICLR 2024
Cbaecrvv VALLAN
0:555
0.1
0.006
0.001
Terations
Iterations
Berations
(a) ZO-SGD
(b) SCOBO
(c) ZO-RankSGD
osjectvv valU00
(d) GLD-Fast
Figure 11: Hyperparameter tuning on Quadratic function.
52
Giueclvve 19
055
05
1o:00
5c.0
terations
Iteracions
Rtracions
(a) ZO-SGD
(b) SCOBO
ZO-RankSGD
405
objective value
30-
(d) GLD-Fast
Figure 12: Hyperparameter tuning on Rosenbrock function.
C.3 EXPERIMENTS WITH NOISY RANKING ORACLES
In this section, present preliminary results to assess the performance of ZO-RankSGD when confronted with noisy ranking oracles. It is essential to note that, unlike the comparison oracle introduced by Cai al. (202)), which employs flipping probabilities to represent errors in noisy comparison feedback, modeling emrors in noisy ranking feedback is not straightforward.
To simulate noisy ranking oracles for our experiments, empirically introduce Gaussian noise to the grouhd-truth function value. We then construct the corresponding noisy ranking feedback based on the perturbed values.
26

---

Published as a conference paper at ICLR 2024
Figure 13 illustrates the performance of both ZO-SGD and 1O-RankSGD under varying levels of noise, denoted by the variance parameter added to the function value. We select the optimal stepsize independently for ZO-SGD and ZO-RankSGD. Remarkably, ZO-RankSGD demonstrates resilience to additive noise across different levels of variance, consistently maintaining performance comparable to ZO-SGD. Notably, for the Rosenbrock function, Z0-RankSGD outperforms 70- SGD, indicating superior robustness to additive noise. We speculate that this advantage stems from ZO-RankSGD relying solely on rank information for optimization, which may exhibit less variabil- ity under mild additive noise.
Looking forward, our aim establish well-defined framework for noisy ranking oracles and ex- tend the theoretical analysis of 10-RankSGD within this context. Additionally, we hope to explore the theoretical robustness of Z0-RankSGD to noise.
5CD/)=1000 1000)
20-Rari50D 1000)
abjective value
20-560in - 0.1)
abjoctive value
8800
y
2
20 SCD - 10]
205G2ln [05)
Zo-RankscDog
ZD-RanksaDjp 0.001]
20000
1000
200
Iterations
(a) Quadratic function
(b) Rosenbrock function
Figure 13: Performance of Z0-RankSGD and ZO-SGD under noisy feedback.
C.4 DETAILS FOR THE EXPERIMENTS IN SECTION 4.2
Problem dimension. In this experiment, for all three scenarios from Mujoco environment, we seek optimize linear policy mapping states to actions. Specifically, the dimensions for the Reacher- v2, Swimmer-v2, and HalfCheetah-v2 are 24, 18, 108 respectively.
Comparing ZO-RankSGD with SCOBO in policy optimization. this part, we delve into detailed comparison between ZO- 10-RankSGD and SCOBO. It is important to note that a direct com- parison is challenging, as they depend on fundamentally different query oracles. However, we pro- pose an alternative comparison approach from an information perspective. Specifically, given budget of 5 query points per iteration, SCOBO can make only independent pairwise comparisons, while ZO-RankSGD can obtain information from 10 dependent pairwise comparisons by querying a (5, 5) rranking oracle.
From this standpoint, anticipate that ZO-RankSGD would outshine SCOBO with 5 (which can only query information points via independent pairwise comparisons), but might fall short when compared to SCOBO with 11 (which query information of points via 10 independent pairwise comparisons).
To test this hypothesis, benchmark CO-RankSGD, SCOBO (m 5). and SCOBO (m 11) on the same policy optimization problem discussed Section 4.2 The results, shown in Figure 14 align precisely with prediction, thus validating our perspective.
27

---

Published as a conference paper at ICLR 2024
SCD60) SCO10) 11)
apisode reward
spisott roward
eptroon
20-5ar15C0
SCoR3m
number querles
number
number
(a) Reacher-v2
(b) Swimmer-v2
(c) HalfCheetah-v2
Figure 14: Perfomance of 20-RankSGD and SCOBO on three MuJoCo environments
C.5 DETAILS FOR THE EXPERIMENT IN SECTION
Modified ZO-RankSGD algorithm for optimizing latent embeddings of Stable Diffusion. To enhance the efficiency T we make a modification to preserve the best image obtained during the optimization process. Specifically, in the original algorithm, the best point among all queried images is not saved, which can lead to inefficiencies. Therefore, we modify the algorithm to store the best point in the gradient estimation step as x** and add it to the later line search step. This modification can be viewed as a combination of 70-RankSGDD and Direct Search (Powell 1998). Another useful feature of Algorithm 3 is that if the best point is not updated in the line search step, the algorithm returns to the gradient estimation step to form a more accurate gradient estimator. The modified algorithm is presented in Algorithm 3 At every iteration in Algorithm 3 we evaluate the latent embeddings by passing them to the DPM-solver with Stable Diffusion and then ask human or CLIP model rank the generated images.
Algorithm Modified ZO- RankSGDD algorithm for optimizing latent embeddings of Stable Diffu- sion.
Require: Objective function f (Evaluated by human or CLIP model), initial point zo. number of queries m. stepsize y,. smoothing parameter μu, shrinking rate 7 E (0, 1). number of trials I.
1: Initialize the best point x = Zo.
2: Initialize the gradient memory á with all-zero vectors.
3: Set
4: while not terminated by user do
5: Sample m i.idd. direction (EI, {m from NO, T).
6: Query OfmmA with input 2i = (a" + "4E,,...,, .x" + m&m} for some k: S m. Denote I as the output. Set x to the point Xi with minimal objective value.
Compuate the gradient using the ranking information I as Algorithm
9:
z = (Tō + (T
10:
+
Query Om..1) with input X {x" , 79. N7 ..., x² m7" m0)). Denote lla the
mY......
output.
12:
if E Iz, ie. x" has the minimal objective value then
13:
Go back to li
14:
else
15:
Set
point in Xs minimal objective value. Initialize the gradient memory with all- zll-zero vectors. T O.
16:
17:
18:
end if
19:
end while
The User Interface for Algorithm 3 Figure 15 presents the corresponding user interface (UI) designed for collecting human feedback Algorithm 3 where 6 images are presented to the users at each round. When the user receives the instruction "leass rank the following image from best to worst," it indicates that the algorithm is in the gradient estimation step. In this case, users are required rank & best images, where it can be any number they choose. Then, the user receives the instruction "Please input the ID of the best image," indicating that the algorithm has moved to the line search step, and users only need to choose the best image from the presented images. This
28

---

Published as a conference paper at ICLR 2024
interface enables easy and intuitive communication between the user and the algorithm, facilitating the optimization process.
Round 1: Please rank the following image from best to worst -> 3
ID:3
Round 2: Please input the ID of best image -> 1
121
10:50
10:0"
Round 3: Please rank the following image from best to worst ~> 2 6 1344
12:1
ID.2
10:3
ID-4
ID:5
12:6
Round 4: Please input the ID of best image -> 2
10:1
D:2"
1D:3
ID:4
1D:5
D
Round 13: Please the following image from to worst
1X1
10:
ID-4
E2:
Round 14: Please input the ID of best image
Round 15: Exit
Figure 15; The User Interface of Algorithm
In this experiment, popular text prompts from the interne More examples like the ones Figure 7 are presented in Figure 16
29

---

Published as a conference paper at ICLR 2024
Other details. For all the examples in Figure 7 and Figure 16 for human feedback between 10 and 20, which was determined based on our experience with the optimization process. For the images obtained from the CLIP similarity score, we fixed the number of querying rounds to 50. Both the optimization from human feedback and CLIP similarity score used the same parameters for Algorithm 7 J4 0.1, and 0.5. Especially, the μ 0.1 is chosen according to the rule discussed in Section[..1 as we select a sufficiently small value which still allows humans perceive differences between perturbed images. Since the latent embedding of Stable Diffusion is 64 x 3 x 3. the problem dimension of the optimization problem is 576.
set the number of rounds
30

---

Published as a conference paper at ICLR 2024
Prompt
Initial
Human
CLIP
cute magical flying dog, fantasy art drawn by disn concept artists, golden colour, high quality, high! y detailed, elegant, sharp focus, concept charac ter concepts, digital paint ing, mystery, adventure
beautiful dress design york fashion week, 8 & render octane -h
test
interior design, frank llay wright house cave with forest canopy, dark wood, streaks of light, light fog, living room :: bubbletech ttest -ar
octane rendered characte
portrait of mitsurugi, octone render, depth of leld, unreal engine 5, can cept art, vibrant colors, gf trending artstatio ultro high detail, ultra ealistic, cinematic lightin 9. focused,
3d typography rrefiuld, letter "A", with n eon color particels, cells, bocteria, marco feeling, lassy material, hyper reali stic, 8k
fe
BAA
highly detailed epic cine matic concept ort an olie pyramid landscape, art station, landscape, conce pt art, illustration, highly detalled ortwork cinemati hyper realistic painting
full length photo of christi na hendricks as an amazo
warrior, highly detailed, 4 smooth, shorp cus, high resolution, awar
winning photo
Figure 16: More examples.
31


Reviews:
[{"review_id": "YZpI2SV6ZM", "reviewer": "Reviewer_BfNk", "summary": "In this work, the authors introduces a novel optimization algorithm, called ZO-RankSGD, designed for solving optimization problems where only ranking oracles of the objective function are available. The authors demonstrated the effectiveness of ZO-RankSGD through both simulated and real-world tasks, such as image generation guided by human feedback. Additionally, they also explored the influence of various ranking oracles on optimization performance and offer recommendations for designing user interfaces that facilitate ranking feedback. The authors further propose future research directions that include adapting the algorithm to manage noisy and uncertain ranking feedbacks, integrating it with additional methods, and applying it to a broader range of cases beyond those with  human feedback.", "questions": "see above.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "Strengths:\n\n- The writing of the paper is clear and easy to follow. In particular, its concise articulation of both the problem at hand and the proposed solution makes it much easier in understanding the paper. The authors also provided a rigorous mathematical formulation of the optimization challenge and provided the underlying intuition of their algorithm. Furthermore, they proved theoretical guarantess for the convergence of ZO-RankSGD and substantiate its practical effectiveness with experimental results across diverse settings.\n\n\n- The second strength of the paper is its comprehensive experiments of how different ranking oracles affect the optimization results. The authors provide valuable insights into the design of user interfaces useful for ranking feedback and propose methods to enhance the query efficiency of the algorithm.", "weaknesses": "Weakness:\n\n\n- Limited experments and unsupported claims: the evaluation of the algorithm's performance on noisy and uncertain ranking feedback is very limited. Also, the authors suggest furture direction for extending the algorithm to handle the aforementioned scenarios, however, they don't have any empirical results to support the claim. I would suggest the authors to provide at least some preliminary results for coroborate the argument.\n\n- Narrow focus: the authors only focused on image generation with human feedback, which is also a bit limited. For human feedbacks, it's more commonly used in tuning language models, though there are recent works start to explore how can we incoporate human feedbacks into improving diffusion models. The method itself is interesting, and it would be a great add if the authors can show that the method is also effective for tuning language models.\n\n\n--- \nPost rebuttal: thanks to the authors response. I think it has addressed most of my concerns. I will increase the score accordingly.", "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": "EaKwf10gN3", "reviewer": "Reviewer_T8Lm", "summary": "This paper studies the zeroth order optimization problem where the algorithm is only allowed to query a deterministic ranking oracle. That is, given two points $x_1,x_2$, the oracle returns the point at which the value of the objective function is smaller. Under smoothness assumptions, this paper designs the ZO-RankSGD algorithm that provably converges to a local with rate $\\sqrt{d/T}$, where $d$ is the dimension. Empirically, this paper also shows that ZO-RankSGD performs competitively to ZO-SGD (where the algorithm can query the function value). It is also shown that ZO-RankSGD can be used to search over the random seeds in the diffusion model using human feedback.", "questions": "-\tIs the convergence rate in Corollary 1 optimal in this setting?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "-\tThis paper shows both theoretically and empirically that the proposed ZO-RankSGD algorithm has competitive performance. \n-\tThe estimator for (m,k)-ranking oracle is neat and novel, and it extends the pairwise comparison oracle in classic RLHF framework. This extension is also well-motivated by the application with diffusion model, where it is reasonable and practical to generate more than two images per round.\n-\tThis paper is well-written and easy-to-follow.", "weaknesses": "-\tMy main concern about this paper is that the oracles are deterministic. However, in practical settings, even human labelers have a lot of stochasticity/inconsistency when generating feedback (see e.g. [1]). Hence there is a gap between the theory and practice even though the algorithm performs well in the diffusion model application. Since most of the prior works assume a stochastic oracle, this setting needs to be further justified.\n-\tThere is no rigorous quantitative results in real-world applications (i.e., the diffusion model). In the paper, there are only a few examples of images generated using ZO-RankSGD and human feedback.\n\n[1] Dubois, Yann, et al. Alpacafarm: A simulation framework for methods that learn from human feedback.", "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": "boVK2sFxyU", "reviewer": "Reviewer_6pMr", "summary": "In this paper, the authors consider the problem of optimizing a black box function with only ranking feedback. The authors propose a novel estimator for gradient descent direction based on ranking information. They show that this estimator guarantees convergence to a stationary point. Empirical evaluations covering a diverse set of applications, including reinforcement learning and diffusion generative models, show the effectiveness of the proposed method.", "questions": "1. Towards the end of section 3.1 on how to choose $\\mu$ in Algorithm 1, can the authors expand on how to choose $\\mu$ in practice, for example in the stable diffusion experiment?\n\n2. It is not clear how the line search budget is accounted for in Section 4.1. Is it the case that, with $m=15$ queries, gradient-based algorithms will use 10 queries to estimate $g_t$ and the final 5 queries are used for the line search?\n\n3. Section 4.1 on investigating the impact of $m$ and $k$: Equation (10) seems to be dominated by $M_1(f, \\mu)$ when $k$ and $m$ are of relatively large values. That means that the second variance is actually not the dominant quantity. Please let me know if my understanding is correct.\n\n4. In section 4.2, the authors should compare with recent preference-based RL algorithms mentioned above. Additionally, it would be useful to include achieved rewards for standard RL algorithms with scalar rewards to show the performance gap (if any) using preference-based rewards.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. As far as I know, this is the first algorithm utilizing ranking feedback that comes with a convergence guarantee. I briefly checked the proofs and found the technique establishing the main theoretical result (lemma 1) to be interesting.\n\n2. The diversity of applications demonstrates the general applicability of the proposed algorithm. The image generation example is timely with the increasing popularity of aligning generative models with human preferences.", "weaknesses": "1. While the experiments are diverse, their comprehensiveness could be improved. The image generation experiment is very limited. While the three examples presented in the main paper exhibit some improvements over the baseline model, looking at additional examples in the appendix the improvements are harder to assess. Typically for image generation, some kind of human evaluation is necessary to provide a more objective evaluation.\n\n2. Similarly, the reinforcement learning experiment compares only with a single baseline method (CMA-ES), which is not designed for RL. I think comparing with more RL-focused baselines such as [1] and [2] is more appropriate. \n\n[1]: Lee, Kimin, Laura M. Smith, and Pieter Abbeel. \"PEBBLE: Feedback-Efficient Interactive Reinforcement Learning via Relabeling Experience and Unsupervised Pre-training.\" International Conference on Machine Learning. PMLR, 2021.\n\n[2]: Christiano, Paul F., et al. \"Deep reinforcement learning from human preferences.\" Advances in neural information processing systems 30 (2017).\n\n3. There are some details missing for the empirical evaluations. For example, in section 4.2, how does a policy generate multiple episodes for querying the ranking oracle? What is the network architecture to represent a policy?", "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)