Dueling Convex Optimization with General Preferences

“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.”

You 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). For additional details regarding the $\log(T)$ factor see our reply to reviewer br4X.

“What if the required error $\epsilon \geq 5\beta\min( d D^2 ,\sqrt{d}rD/G )$”

Indeed, 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$.

“Are there any example of concrete problems in practice where p>1?”

First, we should note that even for $p=1$ our results constitute the first convergence bounds for convex optimization with (approximately) linear transfer functions.

Next, 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.

Again, 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.

“This work could be improved by justifying the algorithm design with experiments”

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

“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”

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

“The choice of hyperparameters also need more discussions”

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

“The algorithm design of this paper is mostly an extension of Saha et al. (2021b)”

First, 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.

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

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

Other Comments Or Suggestions:

Thank you for your suggestions, we will incorporate them in the final version of the paper.

“Since errors accumulate only along the path… will decrease by a $\log{⁡T}$ factor”

We 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$.

“Can the assumption of $\rho(0)=0$ be relaxed?”

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. In our formal feedback model, this essentially implies that $\rho(0)=0$.

Having 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).

“Can the results be improved if $\rho$ is an odd function?”

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