Dueling Convex Optimization with General Preferences
Authors: Aadirupa Saha
Tomer Koren
Yishay Mansour
Venue: ICML 2025 poster (2025)
Keywords: convex optimization
dueling feedback
comparison feedback
preference learning
transfer function
convergence rate
Primary area: theory->online_learning_and_bandits
TL;DR: convex optimization, dueling feedback, comparison, preference, transfer function, smooth convex functions, convergence rate, strongly convex functions

Abstract: We address the problem of convex optimization with dueling feedback, where the goal is to minimize a convex function given a weaker form of \emph{dueling} feedback. Each query consists of two points and the dueling feedback returns a (noisy) single-bit binary comparison of the function values of the two queried points.
The translation of the function values to the single comparison bit is through a \emph{transfer function}.
This problem has been addressed previously for some restricted classes of transfer functions, but here we consider a very general transfer function class which includes all functions that admit a series expansion about the origin.
Our main contribution is an efficient algorithm with convergence rate of $O(\epsilon^{-4p})$ for smooth convex functions, and an optimal rate of $\widetilde O(\epsilon^{-2p})$ when the objective is both smooth and strongly convex, where $p$ is the minimal degree (with a non-zero coefficient) in the transfer's series expansion about the origin.

Dueling Convex Optimization with General Preferences
Aadirupa Saha Tomer Koren 23 Yishay Mansour
Abstract
2014; Khetan and Oh, 2016).
We address the problem of convex optimization with dueling feedback, where the goal is to min- imize convex function given a weaker form of dueling feedback. Each query consists of two points and the dueling feedback returns a (noisy) single-bit binary comparison of the function val- ues of the two queried points. The translation of the function values to the single comparison bit is through a transfer function. functionn This problem has been addressed previously for some restricted classes of transfer functions, but here we consider very general transfer function class which in- cludes all functions that admit a series expansion about the origin. Our main contribution is an effi- cient algorithm with convergence rate of (cpAp) for smooth convex functions, and an optimal rate of (()-2)) when the objective is both smooth and strongly convex, where p is the minimal de- gree (with non-zero coefficient) in the transfer's series expansion about the origin.
Drawing motivation from the above, in this paper we study challenging convex optimization model where the access to the objective function is through a noisy pairwise compar- ison oracle. Namely, given an underlying convex objective function f IR + R, at each step the optimization algo- rithm is allowed to query two points w, w' in R4, upon which only noisy 1-bit feedback or {+1) is revealed, whose expected value indicates their relative function values. More specifically, the feedback signal is such that
Elor W, w'] = -(f(w) - f(w'))
where p R R+ [-111111] is a (possibly nonlinear) transfer function mapping difference in function values to signed preference signal, and p(f(w) - f(w')) interpreted as the degree to which w should be preferred over w', or vice versa. Provided such access, our goal is to find point that approximately minimizes the objective f. Borrowing terminology from the literature on dueling bandits, we call our framework General Dueling Convex Optimization (G- DCO) for general transfer functions.
Noisy pairwise comparison access could potentially be sig- nificantly weaker than the already weak zero-order access. Indeed, special case of this framework has been studied by Jamieson et al. (2012) who focused on polynomial transfer functions of the form p(x) = esign( (x) [2]] and gave tight upper and lower bounds in the pairwise comparison model for strongly convex and smooth objectives. Their results indicate that as p grows larger, the best achievable conver- gence rate degrades quickly, and already when p >> 1 this rate becomes strictly inferior to that of zero-order optimiza- tion. Much more recently, Saha et al. (2021b) considered a similar pairwise comparison model with a different type of a transfer function, namely the sign function p(x) = sign(z) (i.e., p = 0), and established fast convergence rates for this case exclusively.
1. Introduction
Convex optimization algorithms are fundamental across many fields, including machine learning. Most commonly, convex optimization is studied in first-order gradient or- acle model, where the optimization algorithm may query gradients of the objective function; or more limited model of zero-order oracle access, where the optimization algo- rithm may only query function values. Such optimization frameworks are well-studied in the literature (e-g., Nesterov, 2003). However, in recent days, relative/preference-bsss query models gained much attention, which are common in domains such as recommendation systems, online merchan- dises, search engine optimization, crowd-sourcing, drug test- ing, tournament ranking, social surveys, etc. (Hajek et al.,
'Department of Computer Science. University of Illinois, Chicago, US BBaavttnkk School of Computer Science, Tel Aviv University, Israel Google Rescarch, Tel Aviy, Israel. Correspon- dence to: Aadirupa Saha <aadirupa @ui..edu>.
These works point us some fundamental questions: Can we design algorithms for dueling convex optimization that is able to leverage more general transfer functions? Can we converge to a minimizer even when the transfer is unknown to the algorithm? And what properties of the transfer func- tion dictate the achievable optimization rates? We make progress toward answering these questions:
Proceedings of the 4nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

In other words, in general one cannot implement comparison oracle for f(x) + _ ||= given a black- box comparison oracle for Ducling Convex Optimization with General Preferences
We formalize a generalized dueling convex optimiza- tion setting for convex optimization with pairwise- preference feedback given by a general transfer func- tion p. which is only assumed to be well-behaved around the origin (see Section 2.1 for a precise def- inition of the query model and optimization objective). Our framework generalizes and significantly extends two existing settings of optimization with compari- son feedback of Jamieson et al. (2012) and Saha al. (2021b).
includes virtually all functions that admit series expansion around the origin.
In terms of techniques, our approach starts by following stan- dard lines in bandit and zero-order optimization (e.g., Flax- man et al., 2005; Saha and Tewari, 201 I), forming stochastic estimates for the gradients of the underlying objective using the available dueling access. However, unlike in the stan- dard convex scenarios, the gradient estimates we are able to construct in the dueling setting are substantially deteriorated by the nonlinearity of the transfer: information about the magnitude of the gradient is badly mutated by the feedback process, and even further, the gradient estimates closer to optimality are biased and thus hamper convergence. Our analysis addresses the first issue by carefully analyzing how the gradient estimates are skewed by the nonlinear transfer function, through inspecting its behavior around the origin and how it transforms the expected value of our estimates. The second issue turns out to be even more challenging to address technically, since the stochastic process induced by the optimization trajectory incurs a "conditional drift" close to where we would like to establish its convergence. We circumvent this challenge through a stopping-time analysis of supermartingale related to this stochastic process, that establishes its concentration with high probability.
(ii)
We give novel algorithm for dueling convex opti- mization with a general transfer function p. called Pro- jected Dueling Descent (Algorithm 1). We prove that when the optimization objective function convex and smooth, our algorithm needs an order of O(e queries to the mairwise-preferent oracle for finding an e-optimal point (see Theorem 2); here, p can be thought of the minimal non-zero degree in a series expansion of the transfer, around zero
(iii)
We further show that our algorithm can achieve faster convergence rates when the function is additionally also strongly convex (Algorithm 2, Theorem 4). Con- cretely, we show that in this case only Ö( 22) pair- wise queries are sufficient for e-convergence. The latter rate is shown be tight as it matches existing lower bounds (for certain transfer functions) for strongly con- vex optimization with comparison feedback due to Jamieson et al. (2015). We remark that this result does not follow via a reduction to the general convex case, as adding (strongly convex) regularization to the objective breaks the comparison oracle access.
2. Preliminaries
Notation. Let [m] = 21, .n). for any n E N. Given set S, for any two items x. y E S, we denote by x > y the event x is preferred over y. For any r > 0, let Ba(r) and Sa(r) denote the ball and the surface of the sphere of radius r in d dimensions, respectively. La denotes the d x d identity matrix. For any vector x E IR ||x|| denotes the l norm of vector x. We write Ô for the big O notation up to logarithmic factors.
We emphasize that, in fact, even the most well-studies trans- fers, like the sigmoid, were not covered by the existing literature. The goal of this paper is to fill in this gap, signifi- cantly expanding the scope of comparison-based (dueling) optimization to variety of nonlinear transfer functions.
2.1. Problem Setup
We consider the problem of minimizing a convex function f : Rd + IR over a bounded convex domain D C Rdd We assume that f is G-Lipschitz and 3-smooth over D, and that D has Euclidean diameter bounded by D. We denote by w' E arg minwed f(w) a point where f is minimized over D.
Our algorithmic results complement those of Saha et al. (2021b), who only considered the sign transfer function. Compared to the results of Jamieson et al. (2012), we are able to handle both the convex and strongly convex cases (while they only deal with the latter), and we only require the transfer to be well-behaved around the origin (while they rely on its global structure?). Thus, we are able to en- compass a greater variety of transfer functions whose local behavior around zero is approximated by a polynomial
Query model: Our access to the objective f is through a noisy comparison oracle that upon input of a pair (w, w') of points in Rd, emits a random binary response E [=1} such that
Blo w, w/| = -(f(w)- - ff(w'),
where p R + [-,,]] is a fixed transfer function map- ping difference in function values to (signed) preferences, unknown to the algorithm.
Indeed, their algorithm relies on line-search procedure at each step, employing the comparison oracle for implementing one-dimensional noisy binary search.
2

---

Ducling Convex Optimization with General Preferences
For example, given p the query model could output a random variable such that o (er=(((((
the order of summation and differentiation. Let us write p' ('(x) = papa R(x), where R(x)) = En>p na,=""1
f(w")) where Ber* denotes a signed version of the Bernoulli distribution (such that for a random variable X (p), we have Pr(X=+t +1) = 1 Pr(X Pr(X-= -1) )
Then, for |a|
< 5 55 2 we can show that: R(x)) S
nnn |=-1-~1
S MMx
12
n>p
n=
Transfer function: We assume throughout that the transfer function p R + [1 1] is fixed and satisfies the following
= [
1 |ar]
assumptions:
< 2M
Assumption 1. (i) The transfer p is differentiable, mono- tonically non-decreasing and satisfies p(0) = 0; (ii) there are constants r >> 0, > 0 and integer p 2 such that for all x E (-r,r) it holds that pl (x) 2 -
Thus, when |x]| S. papp/4M we have |[(x)] - 3 kx1
It follows that [p'(x) 2 pap|z|² [R(x)] 2 2 /x 100-1 as claimed.
We discuss these assumptions in more detail in the subsec- tion below, where we argue that they hold for essentially any function p that admits series expansion about the origin.
3. Dueling Convex Optimization with General Transfer Functions
Optimization goal: The goal of the optimization process is then, given 6 > 0, to find a point w E DD such that while minimizing the number of queries to the comparison oracle.
In this section we propose optimization algorithm for dueling optimization problem for convex and f-smoooh objective f. The primary difficulty in designing an efficient algorithm for the purpose lies in the fact that we cannot hope to estimate the gradient of f for any general duel- ing/pairwise preference model (i.e., any general p). Thus, we cannot directly apply standard gradient estimation tech- niques (e.g., Flaxman et al., 2005; Saha and Tewari, 2011) to address this problem.
f(w)- /(w))) S
To formalize our optimization framework further, now in- troduce the notion of admissible transfer functions, broad class of comparison mechanisms characterized by smooth- ness and monotonicity, which includes most functions ex- pressible via a series expansion around the origin.
We get around the difficulty by noting that, though one may not be able to estimate the exact gradient of J. V V((w). at given point of interest w E DD we can hope to estimate 'p-th order proxy of V f(('', called "relative gradient" of f at w, from the 1-bit preference feedback generated according to the transfer function (or pairwise preference model) p. The following definition and the lemma describe more formal argument for this.
2.2. Admissible Transfer Functions
The second part of Assumption is perhaps the most strin- gent one; however, in the following lemma we demonstrate that it is satisfied by a wide variety of natural transfer func- tions: those that admit series expansion about the origin with uniformly bounded coefficients.
Lemma 1. Let admit a series expansion p(x) En-p anx" about x = 0 with minimal degree p 2 1 and ra- dius of convergence 8 >>0 O. Then, if ag > O and |na,] S M for all n > P. we have that
3.1. The Projected Dueling Descent algorithm
The crux of the idea lies in designing "relative gradient" based algorithm (Algorithm 1), which is a generalized no- tion of gradient descent- optimization technique: The algorithm proceeds sequentially, where at cach step t, it maintains a solution w, E D, estimates the "relative gradi- ent" of f at point w, using dueling feedback, and take a small step in the negative direction of the estimated "relative gradient" to reach the updated solution Wz+1-
10' (z)) 2 = for |x|| < minfo,
8, pap 4M
Note that since we require p(0) = O, it must be that og- 0 and the assumption p 2 holds naturally. Further, since we would like p(x)= > 0 to hold for æ > O, the first nonzero coefficient must be positive, namely ap > O. Thus, the only non-trivial assumption is that the series coefficients uniformly bounded; however, this condition holds for many natural transfer functions: e.g., for the sigmoidal (x), hyperbolic tangent (anh(r) and for the error function erf()) it holds simply with M 1.
More formally, the algorithm starts from an initial point W1 E DD. At any round f = 1,2, the algorithm queries the dueling feedback on a pair of points (w, + yu, W, yu,), where u, ~ (1)) a random unit vector, and y is a perturbation scale parameter." Upon receiving the 1-bit preference feedback o, E (+1), it finds "relative
Proof of Lemma I. On the interval of convergence (-6,8)
we have p'(x)= = Emep na, -1 as one can exchange
Recall that our setup allows for the oracle to process queries of
3

---

Ducling Convex Optimization with General Preferences
gradient" an estimate of f at w, as gi == ogU, which gives valid descent direction on expectation. It then takes step, with stepsize 17, along the negative direction of ge to obtain the next iterate W++1 == We- 7ge (with suitable projection if necessary).
smooth and G-Lipschitz over D. For any < e é 5/3 min (dD? VdrD/G) and ó (0,1), 1), running Algo- rithm with
Cppe2v 2v
7 103DVd d
0 -<クS
BP(8D 2p ( 1d++1/2
The details of the algorithm are presented in Algorithm Note that the algorithm itself is oblivious to the specific transfer function p and does not require any knowledge about it its parameters."
for T > 2(D2 /12 + 1) log(1/6) /6) steps, certifies that with probability at least 1 1- there is at least one step 1 S TT where f(w,) 1 f(w") +
Note that the theorem's 's statement applies to sufficiently small error 6 < E; for larger values the theorem can be used with E, in which case the convergence rate only depends the problem parameters (and is independent of e).
Algorithm 1 Projected Dueling Descent (PDD)
1: Input: Initial point: W1 D, Learning rate 17, Pertur-
bation parameter y, Query budget T
2: for ( 1, 2, 3. ...,, do
Theorem gives a sample complexity bound of ((5 for reaching c-optimality, with high probability; put differ- ently, it establishes an O(T-1/4p) convergence rate over T steps. A notable limitation of the convergence guarantee. however, is that it only implies that one of the points we evaluate along the trajectory of the algorithm is e-optimal with high probability, rather than specifying a particular point as output. (We note that this issue appears only in the strongly-conve case: indeed, as we show in the next section, in the strongly convex case our algorithm produces single c-optimal point with high probability.)
3: Sample u, ~ Uni)(Sa(1))
4: Set x², == We we+ uu y;:= := We uu
5: Play the duel (x/+ y²), and observe or E 1 such that
Or ~ Ber Ber=(((((xx (x(f(x)) - f(y))))
6: Update: Wo+1 W, 7g,, where g: = u,
7: Project: W arg minwep l|w W
8: end for
On a high level, following prior work (Saha et al., 2021b), Algorithm I takes the approach of designing gradient esti- mator using the dueling feedhack and using it for performing gradient descent. However, our gradient estimation analysia sis below is very different due to the generality and nonlinearity of the transfer function in the feedback. This will be seen in Lemma 3 and its proof, which analyzes the gradient estima- tor in the case of nonlinear transfer: roughly, we inspect the local polynomial behavior of the transfer around zero and work out the effect of the polynomial transformation on the expected value of the gradient estimator. the estimation process, the magnitude of the gradient gets distorted (see the [Vv leading factor in the expected value) so we can longer use the standard subgradient descent anal- ysis, which we replace with a different approach akin to the analysis of normalized gradient descent.
We address this issue and detect c-optimal point using additional comparison queries to the noisy comparison oracle. Specifically, given Wi...., Wr we can construct a complete binary tree whose leaves are the T points; each internal node in the tree evaluates the (noisy) min of its descendants, requiring roughly -2p queries to the oracle. Since errors accumulate only along the path from the root to the true minimum, both the accuracy and confidence of the entire comparison procedure will decrease by a log T factor. Overall, the sample complexity for detecting an c-optimal point using this approach is still of order e -O(p).
We proceed to prove Theorem 2. We denote by H. the history (i.e., filtration) generated by the randomness (u. before time and let E. = E|- H.] be the respective conditional expectation. We first show that condi- tioned on H,, if f(w:) f(w*) > then we can show that Wi41 becomes strictly closer in mn-m to the minimum w" in expectation. The precise statement is summarized in the following:
3.2. Convergence analysis
We now state the main result of this section, which provides a convergence guarantee for our algorithm for convex and smooth objectives.
Theorem 2. Assume that the objective f is convex, B-
Lemma (round-wist progress). Assume the conditions and choice of parameters Y in Theorem 2. Then at any time t, conditioned on the history He we have that if f(w.)) - -[(w*) > then
points that outside of the domain D (we assume f defined on the entire space, yet optimization is constrained to D). Technically, we can limit queries to a slightly dilated version of the domain D; we avoid these nuicanses here.
"That said, as our theorem below shows, the optimal tuning of the learning rate 7) does depend on the underlying problem parameters, but this is the case with essentially any optimization al- gorithm with learning rate parameter, including gradient descent, stochastic gradient descent, etc.
E. [[ - w11 [w.
2 172
(1)
Let us first show how our main Theorem 2 is proven using Lemma 3. The idea of the proof is to recursively unravel
4

---

Ducling Convex Optimization with General Preferences
the round-wise progress guarantee, as long the condi- tion f(w,)= - f(w") is met, and note that this cannot continue indefinitely since the norms l|w; -w"]] cannot decrease without bound. Therefore, this can be used to derive an upper bound on the number of steps until one has f(w,) - fw") S C, which is what we set to achieve. However, one crucial challenge with this plan is that the conditional expectations in Lemma 3 cannot be directly un- folded recursively due to the additional conditioning on the event f(w,) (ww") > e. Therefore, our analysis below takes different path instead: it inspects the random variable indicating the first step where f(wr)= - f(w") c, and uses the fact that it is stopping time (with respect to the natural filtration) to derive a bound on its expected value, using an argument reminiscent of the proof of Wald's Lemma (e.g.. Durrett, 2019).
true regardless of where the algorithm is initialized, we can conclude that if we run the algorithm for at least O((D*/7²) log(1/0)) steps, the success probability is amplified to 1 - 6. This implies the theorem.
We now give a proof of our progress lemma. Roughly, the proof argues that in expectation g: is a good progress direc- tion at the point w. on step t. though it is not necessarily aligned strongly with the gradient of f at Wt. This argument has to carefully take account of the nonlinearities introduced by the transfer p and how they skew the stochastic gradient estimates used by the algorithm, using the growth of transfer around the origin as well as the smoothness condition of the objective ʃ.
Proof of Lemma 3. We first note that due to our update rule and the fact that ||g:|| = 1,
Proof of Theorem 2. For all t, let A, be the event that f(w.) - f(w") S e, and define N to be the random vari- able indicating the first step t where the event A₁ occurs. Note that N is a stopping time with respect to the filtra- tion He, since {N =t} E H4, i.e. the event that N S is completely determined by all randomness before step t. Lemma 3 then implies that, for all t:
E, [[]1 w [19]
(3)
I W. - w01 B7 - (w,- -w]- + 172
We will proceed by lower bounding Eglge - B - (oor-w")] wl By definition, the gradient estimator has:
Eg [g] = Ellp(f + )u,) - f(we- yuz)) u.].
E[A,1 H.) H {N > 1J S - O.
By applying Lemma 9 on the right-hand side, we know that:
Eggg
where A, = | w=1l l|w- 3²1??
= 2 B. Tv)) S(w,, - rv.)) V/(W, + rv.)]
Next, we will prove that EI Ar] S ( - 1). To see this, write EEE A = ΣE= AWKIN > t}. Thus,
+ I d
Belo'(((w, + 7v)) f(w:- Now:-MW 7v.)) -f(w;:-vo))
N Σ 4
where V, is a random vector uniform on the unit ball Ba, and E, here and henceforth denotes the expectation over this random variable (and conditioned over all randomness before step t). Therefore:
E
B[EANHIN +) Hall
B[E[A, HIIKYN > 01
By(ge . (w,- -w)]
< Pr[N > 4.
7 Es (wo) d
[VS(w:+ + ([(w:--wi)) - (We w³)
where the final inequality follows from Eq. (2). Thus, by the tail sum formula,
(4)
8 Pr Pr = 1).
Next, we will show that, with probability one over the choice of Vt.
A
(VS(w, + 7v.) + 7f(w.->w) - > 2(S(w..) [(ww)) - -37.
. (W: - w")
(5)
Finally, note that the left-hand side equals B|llwN+1 w=12 [w w w01 2 -D?; we therefore deduce that B[N] < D2 /1j 1. From Markov's inequality, we obtain that N < 2(D2/122 + 1) with probability 2" or in other words, that with probability at least 1. in at least one step t < 2(D2/n2 + 1) it holds that f(wi)- - f(w*) S c. Since this conclusion holds
To see this, first note that since ff is convex and 3-smooth. we have for any w.
at least 1
0 S f(w + +vv) f(w) -VW(W) - v. v. $
(6)
S s(w - 7v=) - f(()) (wW++((()) v. 1877
5

---

Ducling Convex Optimization with General Preferences
As consequence, for any w,
where the final inequality follows from convexity and bound- edness of the optimization domain:
2f(w) S f(w +wv) + f(w- vv) s 2f(w) + BYP
Using this with the convexity of w + ye,,, we obtain
+ +(W--
f(w)) f(w") S ff(w)) (w, w") = DI ff:)ll
Now, on the event f f(w,) - f(w") >> c, and for our setting of 200Dva we can further derive that
(Vf(w, + (Va) + ((ve)) (w; - w")
f(w: + 7vv) + /(w,, -vv) f((w" + + - -[(w-- vve)
E. f(w + +vv) - -f(w. [vm
2 ((/(W(()wWWW/)) - s(w")) 3y². 8-?
7 40D e²
2,87
Put together, Eqs. (4) and (5) and the fact that p' 2 0 imply that
Eglg: - (W:- - -w)l
80 3Ddd
2
27 Eoll'(f(ww + f(we- -w))l d
(7)
Plugging this back into Eq. (9) (and since x + xp- is monotonically increasing for x 2 0), we obtain that on the event /(w.) J(ww) it holds that
- -(f(w)) -
On the event /(w.)///(w [(w") >e, e, we have on the right-hand side above that f(w,) f( f(w") 3 2 fe, since our choice of satisfies 7² < e/3. We therefore conclude in this case the following:
p-1
E, [f(f(w,+ + f(w,- - rv.)]] 2 cpp 80%3D2
Together with Eq. (8) and our choice of y, this gives
Eelgr . (w, -w)]
copryer-1 (802 3D2pp-D
2 2C Eell'(f(ve + rv)) - f())-f(ww-vw (8) d
Egg -(w, w")l 2
Cppe
We proceed to bounding the remaining conditional expectation on the right-hand side. Note that If(w, -VV) f(w, - -v:) < 2Gy < r due to our setting of 7 and since ʃ is G-Lipschitz. Thus, from our assumptions on (cf. Assumption 1) and the convexity of + x=-1 (for any integer p 2 1 and x 2 0), we have
BP (80D)2p-1d
Plugging this back into to Eq. (3) and setting 1) be most the right-hand side above, we obtain the lemma.
4. Improved Rates with Strong Convexity
[[(w rv+) S(w,- >v:))]
In this section, we analyze an epoch-wise version of Pro- jected Dueling Descent (Algorithm 1) which shown to yield better convergence guarantees for a-strongly convex 8-smooth functions. The key idea lies in noting that in or- der to design optimal algorithm for a-strongly convex 8-smooth functions, one can simply iteratively reuse any 8-smoothly convex optimization routine (e.g., we can use our Algorithm 1) by running it as a black-box over a suc- cessive number of epoch-wise warm-starts. Our resulting convergence analysis in Theorem below shows that in this case, the algorithm can find an e-optimal point upon query- ing only Öle 2P) pairwise comparisons (as opposed to the Op--A)) sample complexity rate for the 3-smooth case, in Theorem 2). In fact, as discussed in the introduction, the O O(e-2r) convergence has been shown to be information- thcoretically optimal in specific instances of the problem.
2 epplE [[ vv.) f(w, vv.) 1
(9)
2 (p, [[f(wr + +v)) - f((we - -
To further lower bound, recall Eq. (6) which implies
(/W)( V. - -00²² S f(ww: + +vv) - f(W:->V.) < 2fVlf(w)) vv 3,7²
thus
[[(w:+ + - S(w, - rv)) 2 27 Vf(.))
Taking conditional expectations and using Lemma 8, we can further lower bound:
Ee [(( + vVe) - f(w. ((w.++vv))]
2 EyE, f.(w))) - vvll 37
4.1. Algorithm
?
[f((w)ll- -377
40vd 7
As motivated above, our proposed method Epoch-PDD (AI- gorithm 2) uses an epoch-wise black-boxing of a smooth- convex optimization routine with warm-starting approach.
(f(w:) - -[(w") -1877
4dDvd
6

---

Ducling Convex Optimization with General Preferences
For our purpose, we use the earlier proposed Projected Duel- ing Descent (Algorithm 1) the black box. More formally, the algorithm starts with some initial point wi and runs over sequence of K = (loo(1//e) epochs: inside each epoch k, we call the Projected Dueling Descent(wa, Tk: 7kk Tx) subroutine with the initial (warm-start) iterate Wk. suitably tuned parameters Yik: 7k and a query budget of Tи- The final point reached by Projected Ducling Descent after TV steps is considered the next iterate, setting Wk+1 Pro- jected Dueling Descent(w:. (Wa, lik, Thk (2)) and we proceed to the (A= + 1)-th epoch, warm-starting it with Wk+1-
Lemma S. With probability at least 8, we have for all k K that the point Wk++1 returned by k-th epoch of Algorithm 2 satisfies WWR+1-w"" S DR+1.
While this argument is mostly standard, key step in- volves establishing that once run of Projected Dueling Descent reaches near w", it keeps its distance to w" up to constant factors and does not deviates away; this is for- malized our next lemma below. Unlike in standard convex optimization scenarios, here our gradient estimates are bi- ased close to optimality and might steer the algorithm away from w", which makes this step in the proof significantly more challenging.
The key idea behind the epoch-wise warm-start approach exploits the fact that between any two consecutive epochs, say and k+ 1, the l distance of we from w" gets reduced by a constant fraction in expectation; this is formalized in Lemma 5. Thus, it can be shown that running the algo- rithms for roughly K = O(log(1)))))))) (aoog(()))) /e)) epoch, would lead to ||W w² I c, which in turn imply the c-convergence. Details are given in Algorithm 2.
Lemma 6. Fix e, > 0 and assume that Projected Dueling Descent (Algorithm 1) is initialized such that || - w*Il² S 2e/a and runs for T steps on an a-strongly convex objective I usiin a stepsize
8e 12 a 10 Tog((T/))
0< 5 min
Algorithm Epoch-PDD
Then with probability at least 1 8, it holds that maxigrgT|Ww, - -w'1 &
1: Input: error > O, diameter D, initial point:
Wi E D
2: Initialize, Phase count K CuP (200,3)'d++1??? DI = D
[log2
8D
2c
B
The proof considers the stochastic process {2,} where Ze = ||,, w" 12 and upper bounds the maximal devi- ation of Z, from the initial value Zi, which we assume is at most 21 S zg = 2e/a. Note that { is almost a supermartingale, but not quite so, because the conditional expectation Z- may be larger than ZN if the suboptimal- ity gap f(w.) s(w") is small. The crucial observation in our analysis is that, roughly speaking, when restricted to intervals where Z, > 2u, the process becomes a super- martingale and therefore amenable to strong concentration bounds (and elsewhere the process is trivially bounded by 20).
3: for k ===10 2,..3...... K do
2' 1 DEa, ?h f RD 7k
4: Set 6 = 16
c 10
Ta = Di log K DR+1 + -2 Di.
vi
8,
5: Update Wa+1 to be the final point reached by PDD(W The 7k: Tw: Tx)
6: end for
7: Return w = W+11
4.2. Convergence Analysis
Our main result regarding Algorithm 2 is the following. Theorem 4. Assume that the objective f : IRd R is a- strongly convex, 3-smooth and G-Lipschitz over a domain D of diameter S D. Further assume that for the global minimizer of f over Rdd, denoted w", we have w E 'D. Then given any 0 < < < 5,3 min AdD² /drD/G) and ô E (0, 1). with probability at least 1 the point W returned by Algorithm satisfies f(W)- - f(w") I e. Further, the total number of pairwise comparisons the algorithm makes is most
Proof. Fix c > 0, 20 = 22/a, and let Z, ||w, w'| for all t. Then Z1 S 20, and the process {Z,} measurable with respect to the filtration (Hi). We start by observing that
}
max Z, S max 20. max max ISAS
Zn
(10)
7. ?<IIS
where 7/ and T. are the i'th up-crossing and down-crossing of 2g = 2e/a, respectively, for = 1,2...., T (if there there are less than T of those, define 7/ = or T = T respectively). Indeed, if the maximal value of (Z,} is more than 20, it must be attained in an interval between an up- crossing of on and the subsequent down-crossing.
δ ( (0197000
(18))))PPt1 G2p
D
22p220
The main step towards proving the theorem is a contrac- tion argument, showing that the distance to optimality || - w*ll || is reduced by a constant factor at each epoch of the algorithm.
To analyze this process in each such interval, let us restart indexing so as T/ = 1 to simplify notation; then we have Zi > 20 (after the i'th up-crossing). Fix 21 = 42g and consider the stopping time r defined as the first step where
7

---

Ducling Convex Optimization with General Preferences
the value of Z leaves the interval (zo, =1). We will proceed by examining the stopped process {Zz), defined via Z = Zenr for all & (here A b denotes min 6)).
Proof of Lemma 5. The proof proceeds by induction on k, showing that ||w -wa--M -wll - D&; for the initial point W1, this holds by assumption. By our setting of the parameters T Ta we are guaranteed, that with probability 1 1-5/K, K, that one of the points w during the k-th run of the procedure Projected Dueling Descent will have function value f(w) f(w") S Cj. Then due to strong convexity ||W- - w < 20g/a, and by Lemma 6 we are guaranteed that the final point of reached by Projected Dueling Descent, namely WK+1. will have || - w/ 1| S 8 = D = D 1 (Technically, we also need that U) is small enough certify the conditions of Lemma 6; this can always be guaranteed by an appropriate scaling so to make the diameter D small enough.) The lemma follows by a union bound over the success probabilities.
We claim that the stopped process is supermartingale. In-
deed, notice that 1 = Z + [ > { (Z(+1 Ze); since T is a stopping time the random variable [|[ > { is de- terministic given 1 thus [1 = E, [z]] + |F[7 > [[[[,] Ze). Now recall that, crucially, on the event > t we know that E2 [2++1 I Zj; this is given by Lemma 3, since on this event we have due to strong convex-
ity that f(w,) - (w*)= 2 [ w'll > :a20 = Plugging in, we conclude that E, [4) I E,[ZA], namely,
that { is a supermartingale.
We can now use Azuma-Hoeffding to bound the process {Zz). Notice that the magnitude of the increments is bounded (almost surely) via Eq. (3) follows:
Proof of Theorem 4. By Lemma 5, with probability at least 1 - 5 the output point of the algorithm satisfies |w - w=1 < Di I 22- K D2 < 2e/B. Hence, by
17/+1 - Z S |z+1 - Zel
< 12ng. (wr- - w") + r²1
8-smoothness (and since Vf(ww) = 0). it holds with the same probability that It remains to bound the overall sample complexity, which up to logarithmic factors given by:
s 27) W: - w || + +1²
- f - w"ll I e.
s 2ma1 + +n²² < 37
since we assume that " S 21. Here we used the fact that [|w ww S 21 as long as the process has not been stopped (once it stopped the increments are anyway zero). The Azuma-Hoeffding inequality then states that, for any fixed 1 S t < T and À 2 0,
K
K
D2
K 8
T
log
1/
1=1
k=1
K
K
D
= =B²
21²
2
8
Pr(Z, 2 Z + A) < exp
S exp
k=1
C
2
9
K
K
= B² log
22
2p288
and through a union bound, we have with probability at least 1 - 5/T that
t
a
k=1
K
Sa a 222280 B²
log
220(K+1)
c1
T2 Tlog 8
max Z < Z + 37 K
K 8
323DD
2p
1
B² log
T
a
22p'
< 01 + 5n
T Tlog 3
We conclude the proof by setting the value of B as in the algorithm.
Since Z₁ is the value right after an up-crossing of 2g and since the increments of the process are bounded by 31/=1, we know that 21 < z0 + 31/²1 S 21/2 since 20 S 21/ and 7 I 1/12. Also, for our choice of parameters we have 5ny 5T Tlog(T/5) < 1.2 Therefore, with probability at least - 5/T we have that maxigT 7; S 21. Returning to the original indexing, we proved that for any interval [T/ 7.] we have with probability least 1 - 5/T. it holds that max Z, S 21- Therefore, through union bound over i, we obtain from Eq (10) (and since > 2n) that maxigisT Ze < 21 with probability at least 1 - ö, which is precisely the statement of the lemma
5. Conclusion
We considered the problem of convex optimization under the general class of pairwise preferences (dueling feedback). The primary difficulty in designing an efficient algorithm for this problem is that we can not hope to estimate the gradient of f for any general dueling/pairwise preference model. Thus can not apply the standard gradient descent based techniques to address this problem. We get around with the difficulty by estimating a p-th order proxy of the gradient, called "relative gradient". The crux of the idea lies in designing Projected Dueling Descent based algorithm (Algorithm 1), which generalized notion of gradient
0
Having established the key Lemma 6, the proofs of Lemma 5 and Theorem 4 are straightforward.
8

---

Ducling Convex Optimization with General Preferences
descent-based optimization technique. Using this we design an efficient algorithm with a convergence rate of ((e- for smooth convex objective function, and an optimal rate of D(c-2r) when the objective is smooth and strongly convex.
V. Bengs, R. Busa-Fekete, A. El Mesaoudi-Pane and E. Hüllermeier. Preference-based online learning with dueling bandits: A survey, Journal of Machine Learning Research, 2021.
B. Brost, Y. Seldin, I. J. Cox, and C. Lioma. Multi-dueling bandits and their application to online ranker evaluation. CoRR, abs/1608 608.06233, 2016.
Future work. Although the derived convergence rate for tight,
the strongly convex setting is information-thoorttice the exact convergence lower bound is unclear for the class of smooth functions, which might be an interesting prob- lem to pursue independently. Another direction could be to analyze this problem beyond the smoothness assump- tion. Considering a regret minimization objective instead of the optimization perspective, as well as understanding the information- -hhooretcc regret performance limit would be interesting well. One can also consider generalizing the optimization framework to subsets preferences, instead of just pairwise (dueling) feedback. It might also be useful to extend our setup for contextual scenarios, adversarial prefer- ences or non-stationary function sequences and understand the scopes of feasible solutions as well as the impossibility results.
N. Das. S. Chakraborty, A. Pacchiano, and S. R. Chowd- hury. Provably sample efficient rlhf via active preference optimization. arXiv preprint arXiv:240. 10500, 2024.
M. Dudík, K. Hofmann, R. E. Schapire, A. Slivkins, and M. Zoghi. Contextual dueling bandits. In Conference on Learning Theory, 2015.
R. Durrett. Probubility: Theory and Examples. Cambridge University Press, 2019.
A. D. Flaxman, A. T. Kalai, and H. B. McMahan. Online convex optimization in the bandit setting: gradient de- scent without a gradient. In Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, pages 385-394. Society for Industrial and Applicd Math- ematics, 2005.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
P. Gajane, T. Urvoy, and F. Clérot. A relative exponential weighing algorithm for adversarial dullity-based dueling bandits. In Proceedings of the 32nd International Confer- ence on Machine Learning, pages 218-227, 2015.
J. González, 7. Dai, A. Damianou, and N. D. Lawrence. Preferential bayesian optimization. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pages 1282-1291. JMLR. org, 2017.
Acknowledgments
This project has received funding from the European Re- search Council (ERC) under the European Union's 's Horizon 2020 research and innovation program (grant agreements No. 101078075; 882396). Views and opinions expressed are however those of the author(s) only and do not neces- sarily reflect those of the European Union or the European Research Council. Neither the European Union nor the granting authority can be held responsible for them. This work received additional support from the Israel Science Foundation (ISF, grant numbers 3174/23, 1357/24), from the Len Blavatnik and the Blavatnik Family foundation, and from the Adelis Foundation.
B. Hajek, S. Oh, and J. Xu. Minimax-optimal inference from partial rankings. In Advances in Neural Information Processing Systems, pages 1475-1483, 2014.
K. G. Jamieson, R. Nowak, and B. Recht. Query complexity of derivative-free optimization. In Advances in Neural Information Processing Systems, pages 2672-2680. 2012.
K. G. Jamieson, S. Katariya, A. Deshpande, and R. D. Nowak. Sparse dueling bandits. In AISTATS, 2015.
A. Khetan and S. Oh. Data-driven rank breaking for efficient rank aggregation. Journal of Machine Learning Research, 17(193):1-54, 2016
References
N. Ailon, Z. S. Karnin, and T. Joachims. Reducing dueling bandits to cardinal bandits. In ICML, volume 32, pages 856-864, 2014.
W. Kumagai. Regret analysis for continuous dueling bandit. Advances in Neural Information Processing Systems 30, 2017.
P. Auer, N. nosa-Bianchi, and P. Fischer, Finite-time analy- sis of the multiarmed bandit problem. Machine learning. 47(2-3):235-2555 2002.
Y. Nesterov. Introductory lectures on convex optimization: A basic course, volume 87. Springer Science & Business Media, 2003.

---

Ducling Convex Optimization with General Preferences
E. Novoseller, Y. Wei, Y. Sui, Y. Yue, and J. Burdick. Du- eling posterior sampling for preference-based reinforce- ment learning. In Conference on Uncertainty in Artificial Intelligence, pages 1039-1 PMLR, 2020.
conference on Web search and data mining, pages 73-82. ACM, 2014b.
M. Zoghi, Z. S. Karnin, S. Whiteson, and M. De Rijke. Copeland dueling bandits. In Advances Neural Infor- mation Processing Systems, pages 307-315, 2015.
M.-h. Oh and G. Iyengar. Thompson sampling for multi- nomial logit contextual bandits. In Advances in Neural Information Processing Systems, pages 3145-3155, 2019.
A. Saha. Optimal algorithms for stochastic contextual prefer- ence bandits. Advances in Neural Information Processing Systems, 34, 2021.
A. Saha and A. Krishnamurthy. Efficient and optimal algo- rithms for contextual dueling bandits under realizability. In International Conference on Algorithmic Learning Theory, pages 868-994- PMLR, 2022.
A. Saha and A. Tewari. Improved regret guarantees for line smooth convex optimization with bandit feedback. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pages 636-642, 2011.
A. Saha, T. Koren, and Y. Mansour. Adversarial dueling ban- dits. In International Conference on Machine Learning, 2021a.
A. Saha, T. Koren, and Y. Mansour, Dueling convex opti- mization. In International Conference on Machine Learn- ing, pages 0245-9254, PMLR, 2021b.
A. Saha, A. Pacchiano, and J. Lee. Dueling rl: Reinforce- ment learning with trajectory preferences. In Interna- tional conference on artificial intelligence and statistics, pages 6263-6289. PMLR, 2023.
Y. Sui, V. Zhuang, J. Burdick, and Y. Yue. Multi-dueling bandits with dependent arms. In Conference on Uncer- tainty in Artificial Intelligence, UAI' 17, 2017.
Y. Yue and T. Joachims. Interactively optimizing informa- tion retrieval systems as dueling bandits problem. In Proceedings of the 26th Annual International Conference on Machine Learning, pages 1201-1208, 2009.
Y. Yue, J. Broder, Kleinberg, and T. Joachims. The k- armed dueling bandits problem. Journal of Computer and Sysiem Sciences, 78(5): 153--1556.. 2012.
M. Zoghi, S. Whiteson, R. Munos, M. Rijke, al. Rel- ative upper confidence bound for the k-armed dueling bandit problem. In JMLR Workshop and Conference Proceedings, pages 10-18. 18. JMLR, 2014a.
M. Zoghi, S. A. Whiteson, M. De Rijke, and R. Munos. Relative confidence sampling for efficient on-lino ranker evaluation. In Proceedings of the 7th ACM international
10

---

Ducling Convex Optimization with General Preferences
A. Additional Related work
Dueling Bandits. Due to the widespread applicability and ease of data collection with relative feedback, learning from preferences has gained much popularity in the machine learning community and widely studied as the problem of Dueling- Bandits over last decade (Ailon et al., 2014; Yue et al., 2012; Zoghi et al., 2014;;b; 2015; Saha et al., 202 la; Gajane et al., 2015; Bengs et al., 2021), which is online learning framework that generalizes the standard multi-armed bandit (MAB) (Auer et al., 2002) setting for identifying set of "good' arms from fixed decision-space (set of items) by querying preference feedback of actively chosen item-pairs.
Limitations of Existing Dueling Bandit techniques. Although the relative feedback variants of stochastic MAB problem have been widely studied in the literature, the majority of the existing techniques are restricted to fimite decision spaces and stochastic settings which primarily rely on estimating the entries of the underlying preference matrix. These settings, though important as basic steps, are mostly impractical for all real-world scenarios which often involve large (or potentially infinite) decision spaces, where lies one of the primary motivations of this work. On the other hand, from an optimization point of view, our work is a key step toward analyzing the fundamental performance limits of function minimization using the weaker form of 0/1 bit relative preferences.
Dueling Bandits in continuous spaces. Surprisingly, following the same spirit of extending standard multi-armes bandits (MAB) to continuous decision spaces (as in linear or GP- GGP-bandits), there has not been much work on the continuous extension of the Ducling Bandit problem for large (and structured) decision spaces. The works in (Sui et al., 2017; González et al., 2017) did attempt similar objective, however, without any satisfactory theoretical performance guarantees. In another recent work, (Brost et al., 2016) address the problem of regret minimization in continuous Dueling Bandits, however without any finite time regret guarantee of their proposed algorithms. Recently, (Oh and Iyengar, 2019; Saha, 2021) consider the problem of regret minimization from k-subsetwise preference feedback (k = 2 boils down the dueling setup) on structured decision spaces, although their underlying utility function is assumed to be only linear, unlike any general convex function considered in work; morcover, their preference model is restricted only to the class of Multinomial Logit (MNL) based random utility model, unlike the general link function based preference feedback class that we considered. (Dudík et al., 2015; Saha and Krishnamurthy, 2022) represents another line of dueling bandit work, which incorporates context specific dueling preference model. Specifically, their algorithms are designed to compete against an abstract policy set of context-to-action mappings w.r.t. teinimax-regrett Their algorithms are also designed to handle potentially large decision spaces, although, the regret objectives are focused to identifying the von-Neumann distribution of the underlying preference models, which is very different from the function minimization with dueling feedback point of view that considered.
Optimization for ducling feedback. Along the line of optimization for dueling feedback, (Yue and Joachims, 2009) is the first to address the regret minimization problem for fixed functions f (arm rewards) with preference feedback, although their techniques are majorly restricted to the class of smooth and differentiable preference functions that allows gradient estimation. This is the main reason they could directly apply the classical one-point gradient estimation based Bandit Gradient Descent (BGD) algorithm of (Flaxman et al., 2005) for the setting, unlike us. Moreover, another limitation of their framework is their optimization objective is defined in terms of the 'preferences' which are directly observable and hence easier to optimize, as opposed to defining it w.r.t. f as considered in this work. Following up (Yue and Joachims, 2009), (Kumagai, 2017) considers the similar problem of dueling bandits on continuous arm set but under rather restrictive sets of assumptions: Twice continuously differentiable, Lipschitz, strongly convex and smooth score/reward function, which are often impractical for modeling real-world preference feedback.
Closest to our work in spirit are (Jamieson et al., 2012) and (Saha et al., 2021b), both of which precisely focus on function optimization with relative pairwise preference feedback. The latter however is designed to work only under sign-based relative feedback which reveals the exact information of which of the two queried points have a smaller function value. We instead consider a very general class of polynomial-boe based preference functions (see Section 2) which generalizes the sign- feedback model of (Saha et al., 2021b) as a special case. While the first, although gives provably optimal convergence rates, their guarantees are restricted to the 'well behaved' class of strongly-conve and smooth functions (with bounded Lipschitz gradient). The assumptions and consequently their techniques are hence quite restrictive: A major hindrance towards generalizing their algorithmic ideas to a general function class is owning to their line-search-bar algorithm which is known to fail without coovee-onvexxtt.. On the other hand, our algorithm is shown to yield optimal convergence guarantees for a more general class of smooth-convex functions. Additionally we match the convergence rate of (Jamieson et al., 2012) with the additional strong convexity assumption which shows the generality of our analysis for a
coordinate descent

---

Ducling Convex Optimization with General Preferences
large class of dueling feedback based optimization (G-DCO) problems.
B. Advantage of Gradient Descent Methods
Gradient-based methods have multiple advantages compared to confidence-based methods: (1) GD/OMD handle high- dimensional problems efficiently due to their reliance on gradient information: (2) They are suitable for both stochastic and adversarial environments, making the gradient-based methods robust to changing data distributions or the underlying loss/reward functions which often more practical for modeling real-world problems, (3) These methods can optimize wide range of objective functions, including non-linear, non-convex, and constrained problems, (4) Gradient descent algorithms simple to implement, even seamlessly integrate with modern deep learning frameworks, making these methods computationally efficient, unlike many UCB and TS based methods which often do not have a closed form solution (Saha et al., 2023; Das et al., 2024) or sampling from the posteriors could be complicated (Novoseller et al., 2020), and (5) Gradient descent techniques are inherently robust to model misspecification and smoothly integrate with differential privacy techniques.
C. Auxiliary technical results
We require two results about random vectors in the unit sphere in Rd. The first result is standard; we include proof (extracted from Saha et al., 2021b) for completeness.
Lemma 7. For given vector g Bd and random unit vector Rd drawn uniformly from the unit sphere Sd, we have
|gl|| 20v d
gg
E u
[lg
ul
S
Vd
Without loss of generality we can assume |l = 1, since one can divide through by ||g|| without affecting the claim. Now to bound [[g g ul]. note that since u is drawn uniformly from Sa(1). by rotation invariance this equals [[[[u]]] For an upper bound, observe that by symmetry [[uu]] = 4E ui] = å/ and thus
Proof.
B B| S
R Rlu
Vd
We turn to prove a lower bound on Bilg. u/]. If u were a Gaussian random vector with i.i.d, entries u; ~ N/ 1/d), then from standard properties of the (truncated) Gaussian distribution we would have gotten that B[[u,]] = /2/ For uniformly distributed on the unit sphere, ut is distributed as /1/l|v/| where v is Gaussian with i..d. entries (o, 1/d). We then can write
Pr 11 2 c
= Pr
U1
E
2 Pr
(1011 2 Vd
and ||v +
Vd
|
Vdl
1
- Pr || || > +)
2 1 Pr
|1i| <
Val
Since vdu, is a standard Normal, we have
1 (1 = Pr Pr--111--1 < vdvi < <1) = 24b(1) - - 1.77,
Pr [ull
and since [[[[ [|]] = 1 an application of Markov's inequality gives
Pr([V|| > 1) Pr[[ll] > =fEllliv = =2.
For e = 7 this implies that Pr([u]] 2 1/4vd) 2 J. whence Ellg - u|] B[|m]|] || > 1/20va.
We will also need a version of the same lemma for random vectors drawn from the unit ball rather than the unit sphere.
12

---

Ducling Convex Optimization with General Preferences
Lemma 8. For a given vector g E IR and a random vector
Idd drawn uniformly from the unit ball Bd, have
|g
g
E v-uBa
lg
vll
<
80V
Proof. We will prove that
1
E u-Sa.
[g
ul
E v-
[|g
vl]
E
[lg.
4
urSS."
and the lemma will then follow from Lemma 7. First, since the normalized vector v/lv/ is uniformly distributed over the unit sphere, we have
[lg
vl|
g
E u~Sa
[g
ul].
v~
vr
For the lower bound, note that
E v~BBa
Ig.
E v-.Ba
v
|v] 2 1
Pr(llv] ))
E llg.ul)
2
|
u-BB
where we have used the standard fact the marginal distribution of the norm of a random vector is monotonically increasing. so the norm of v is greater than 1/2 with probability at least 1/2.
Finally, we give lemma relating expectations over Sy to expectations over Ba, which can be extracted from Flaxman et al. (2005).
Lemma 9. Let Rd + R be continuously differentiable, u be random vector uniform on the unit sphere Sa. and v be random vector uniform in the unit ball Bg. Then
1
E [o(u)u] u~Sa
E [Vg(v)].
d v~Ba
Proof. The claim follows from Lemma of (Flaxman et al., 2005) which shows that for any differentiable function f: RRd R and any x E IRd and 0,
5 v E [f(x + 5v)
5
E [f(x + Sujui u-Sa
E +
d v-Ba
v-B,
Fix 0 and substitute f(2) = 1z) Then (z(z) = 8- v and we obtain:
1 E [Vg(v)].
[g(u]u] =
u
d v-
13


Reviews:
[{"review_id": "o4PvH3Qdnb", "reviewer": "Reviewer_br4X", "summary": "This paper proposes an algorithm for the setting of dueling convex optimization, with a broad class of transfer functions.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> “This work could be improved by justifying the algorithm design with experiments”\n\nThis is primarily a theoretical work in optimization with partial feedback, and our main goal is to understand the fundamental achievable convergence bounds in this setting. This is also the focus of much of the prior work in this space. We feel that the provided theory gives ample justification for the algorithm.\n\n> “I was not sure whether the proposed algorithm can be compared against some naive algorithms, given that the algorithm is the first one for the setting being studied”\n\nWhen we have dueling feedback, it is even challenging to design “naive” algorithms for the general convex (and smooth) case. One could view the existing algorithm of Jamieson et al (2012) as an attempt to generalize a natural noisy binary search algorithm to a high-dimensional setting, but unfortunately, their convergence requires strong assumptions such as strong convexity as their extension relies on a coordinate descent scheme. Our main contribution is to give precise convergence bounds for the general convex (and smooth) dueling setting.\n\n> “The choice of hyperparameters also need more discussions”\n\nThe hyperparameters of our algorithms are set to guarantee the best performance bound we can derive. The rationale for their choice is to optimize, in hindsight, the convergence bound we establish.\n\n> “The algorithm design of this paper is mostly an extension of Saha et al. (2021b)”\n\nFirst, we should emphasize that, in our view, expanding the scope of comparison-based / dueling optimization to a variety of nonlinear transfer functions is novel and significant.  In fact, even the most well-studied transfers, like the sigmoid, were not covered by the existing literature in this context.  Our aim was precisely to fill in this gap.\n\nRegarding technical novelty, specifically compared to Saha et al. (2021b): on a very high level, like Saha et al. we follow the approach of designing a gradient estimator using the dueling feedback and using it for running gradient descent.  However, our gradient estimation analysis is very different from that of Saha et al., due to the generality and nonlinearity of the transfer function in the feedback.  This can be seen in Lemma 3 and its proof, which analyzes the gradient estimator in the case of nonlinear transfer: roughly, we do this by inspecting the local polynomial behavior of the transfer around zero and working out the effect of the polynomial transformation on the expected value of the gradient estimator.  In the estimation process, the magnitude of the gradient gets distorted (see the $||\\nabla f(w_t)||^{p-1}$ leading factor in the expected value) so we can no longer use the standard subgradient descent analysis, which we replace with a different approach akin to the analysis of normalized gradient descent.\n\nWe agree a more detailed explanation of the technical novelty compared to Saha et al. should be included in the paper itself - we will improve this in the final version.\n\n> Other Comments Or Suggestions:\n\nThank you for your suggestions, we will incorporate them in the final version of the paper.\n\n> “Since errors accumulate only along the path… will decrease by a $\\log{⁡T}$ factor”\n\nWe will have at the end of the run $T$ points, we would like to select the minimum of those $T$ corresponding function values. If we had exact comparisons, we could build a complete binary tree over the $T$ points, and compute the minimum by selecting at each node of the tree the minimum value between its descendents. With our actual noisy comparisons, we have “errors” of magnitude $\\epsilon$ at each node of the tree, and if we sum these errors along the path to the minimal leaf, the error is amplified by a $\\log(T)$ factor (which is the depth of the tree). Alternatively, we can start with a goal error of $\\epsilon/\\log(T)$ and end with a cumulative error of $\\epsilon$.\n\n> “Can the assumption of $\\rho(0)=0$ be relaxed?”\n\nIt is worth recalling what the transfer function $\\rho$ abstracts. One motivation is similar to Reinforcement learning from human feedback (RLHF), where the transfer function abstracts how human preference behaves given similarly-valued alternatives. The most natural one is to assume that when the alternatives are of similar values, humans select almost randomly. In our formal feedback model, this essentially implies that $\\rho(0)=0$.\n\nHaving said that, technically our algorithm works without modifications in the case where $\\rho(0) \\neq 0$, since it is agnostic to additive bias in $\\rho$ (this can be seen from the statement of Lemma 9 in the appendix).\n\n> “Can the results be improved if $\\rho$ is an odd function?”\n\nWe are unaware of whether the bounds can be improved for odd transfer functions. In fact, our preliminary results were initially for odd functions and we were happy to see that they extend naturally to more general transfer functions, with the same rates, as we describe in the paper.", "claims_and_evidence": "The claims are well supported.", "methods_and_evaluation_criteria": "The proposed methods make sense.", "theoretical_claims": "I checked the proof for the non-strongly-convex case.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "The two most related works are Jamieson et al. (2012) and Saha et al. (2021). This work is a natural extension of Saha et al. (2021).", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strengths:\n1. This work follows a clear logic, and is technically solid, especially the analysis about the stopping time.\n\nWeaknesses:\n1. This work could be improved by justifying the algorithm design with experiments.\n2. In general, the paper lacks interpretation of the results. I was not sure whether the proposed algorithm can be compared against some naive algorithms, given that the algorithm is the first one for the setting being studied. The choice of hyperparameters also need more discussions.\n3. The algorithm design of this paper is mostly an extension of Saha et al. (2021b). The authors could have over-claimed the contribution of the algorithm design, especially the \"relative gradient\".", "other_comments_or_suggestions": "1, The concept of \"admissible transfer functions\" appears abruptly in the title of Subsection 2.2, without further explanations.\n2. In terms of the structure of the paper, the main text includes too much proof detail and inadequate discussions of the main theorems.", "questions_for_authors": "1. Could the authors further elaborate the following statement to solve the problem of unknown time index $t$ that achieves good performance: *Since errors accumulate only along the path from the root to the true minimum, both the accuracy and confidence of the entire comparison procedure will decrease by a $\\log T$ factor.*\n2. Can the assumption of $\\rho(0)=0$ be relaxed? Can the results be improved if $\\rho$ is an odd function?", "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": "gEPWiyUkUJ", "reviewer": "Reviewer_iszU", "summary": "This work studies convex optimization with dueling feedback and general transfer functions. The main contribution is an algorithm with $\\epsilon^{-4p}$ convergence rate for smooth and convex functions and $\\epsilon^{-2p}$ convergence rate for smooth and strongly-convex functions,  where $p$ is the minimal degree (with a non-zero coefficient) in the transfer’s series expansion about the origin.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> “Are there any example of concrete problems in practice where p>1?”\n\nFirst, we should note that even for $p=1$ our results constitute the first convergence bounds for convex optimization with (approximately) linear transfer functions.\n\nNext, to your question, it is worth recalling what the transfer function $\\rho$ abstracts. One motivation is similar to Reinforcement learning from human feedback (RLHF), where the transfer function abstracts how human preference behaves given similarly-valued alternatives. The most natural one is to assume that when the alternatives are of similar values, humans select almost randomly. The degree $p$ abstracts how small changes in the quality of the two alternatives are translated to differences in human evaluations. A higher $p$ value implies that differences are harder to detect. For this reason, $p=2$ is equally well-motivated as $p=1$, and there is no particular fundamental reason to model preferences using a linear function.\n\nAgain, note that the transfer function transfers between the valuations (e.g. in LLM: how good is a response to a prompt) to the human response (e.g. in LLM: the likelihood that a human will prefer each alternative). There is no reason to believe the transfer should be necessarily linear.", "claims_and_evidence": "The statements are supported with proofs.", "methods_and_evaluation_criteria": "NA", "theoretical_claims": "The proofs in the main paper seem to be correct.", "experimental_designs_or_analyses": "NA", "relation_to_broader_scientific_literature": "NA", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "Strength:\nThis work improves the prior art by considering a very general class of transfer functions where $p$ can be greater than $1$. The rates in smooth and strongly convex objectives match the existing lower bounds. \n\nWeakness:\nHowever, this setting $p>1$ seems not very important. This work lacks discussions of meaningful examples and concrete problems/applications in practice.", "other_comments_or_suggestions": "NA", "questions_for_authors": "Are there any example of concrete problems in practice where $p > 1$?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7KiOto35u4", "reviewer": "Reviewer_WhdB", "summary": "This paper considers the problem of dueling bandits with general preferences, where the preference model between two decisions (called the transfer function) is not specified to some specific choices. The most technical challenge in this problem is the estimation of gradients since only the preference feedback (a one-bit feedback generated from a Bernoulli distribution) is accessible, which is even harder than the one-point bandit feedback. To this end, the authors proposed a novel estimation of $g_t = o_t u_t$, which does not necessarily align with the true gradient but is still sufficient for a gradient descent update. As for results, the authors achieved an $O(\\epsilon^{-4p})$ oracle query complexity to obtain an $\\epsilon$-optimal decision. Furthermore, for strongly convex functions, the aforementioned bound can be further improved to $\\tilde{O}(\\epsilon^{-2p})$ using a similar idea like epoch-GD, which is theoretically optimal.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> “The guarantee of Theorem 2 only holds for some unknown decision generated in the optimization process. To find it out, additional operations are needed, which will lead to extra query complexity.”\n\nYou are right to notice that, due to the challenging feedback model, the nature of our convergence guarantee becomes more intricate than simply holding for the final iterate of the algorithm. We address this issue in detail in the paragraph in lines 167-177 (right column).\nFor additional details regarding the $\\log(T)$ factor see our reply to reviewer br4X.\n\n> “What if the required error $\\epsilon \\geq 5\\beta\\min(  d D^2 ,\\sqrt{d}rD/G )$”\n\nIndeed, as you probably realized, in this case we can simply set $\\epsilon=5\\beta\\min(  d D^2 ,\\sqrt{d}rD/G )$ and obtain an only stronger guarantee, and the convergence bound will be independent of $\\epsilon$ and it will only depend on the problem parameters $\\beta,d,D,r,G$.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Yes, mostly.", "experimental_designs_or_analyses": "There are no experiments in this paper.", "relation_to_broader_scientific_literature": "N/A.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "## Strengths\n1. Studying general preference functions is a meaningful problem, which may be further applied to real-world applications, for example, RLHF.\n\n2. The adopted assumption is mild and reasonable. The authors have provided detailed explanations to validate its rationality.\n\n3. The proposed algorithm is simple and easy to implement. It generally follows the update rule of gradient descent but with a carefully chosen gradient estimation. The key challenge lies in the technical analysis of this update rule.\n\n## Weaknesses\n1. The guarantee of Theorem 2 only holds for some unknown decision generated in the optimization process. To find it out, additional operations are needed, which will lead to extra query complexity.", "other_comments_or_suggestions": "I noticed that Thm 2 has an assumption of $0 < \\epsilon < 5 \\beta \\min\\\\{dD^2, \\sqrt{d} r D / G\\\\}$. What if the required error $\\epsilon \\ge \\min\\\\{dD^2, \\sqrt{d} r D / G\\\\}$? I guess this should not be a big deal since the problem would become easy if the required error is large.", "questions_for_authors": "Not many.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: Dear Authors,

Thank you for submitting your paper to ICML and for your contribution to the theoretical foundations of optimization. This work tackles the convex optimization setting under general preference-based comparisons and introduces a novel algorithm that achieves optimal convergence rates for both smooth and strongly convex functions.

The reviewers found the paper technically solid and appreciated the generalization of prior results. Reviewer br4X, after engaging with the rebuttal, increased the score, noting the clarity of the contributions. Other reviewers highlighted the elegance of the gradient estimator and the soundness of the theoretical analysis, while noting that the lack of experiments and applied motivation. Reviewers iszU and WhdB pointed out the importance of articulating practical examples and relaxing assumptions in theorems, which was addressed in the response.

Given the strength of the theoretical contributions, the soundness of the analysis, and the reviewers’ overall support, I am pleased to recommend acceptance to ICML 2025. I encourage you to clarify the assumptions and extend the discussion in the final version to help a broader audience understand the potential applications and interpretability of your results.

Congratulations on your contribution.

Best regards,
AC
Decision: Accept (poster)