Dueling Convex Optimization with General Preferences
This work addresses a fundamental problem in optimization under limited feedback, with potential applications in domains like preference learning, but it is incremental as it extends prior results to more general transfer functions.
The paper tackles convex optimization with dueling feedback, where only noisy binary comparisons of function values are available, by developing an efficient algorithm for a general class of transfer functions. The results include convergence rates of Õ(ε^{-4p}) for smooth convex objectives and Õ(ε^{-2p}) for smooth strongly convex ones, with p being the polynomial degree of the transfer function.
We address the problem of \emph{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 can be approximated by a finite polynomial with a minimal degree $p$. Our main contribution is an efficient algorithm with convergence rate of $\smash{\widetilde O}(ε^{-4p})$ for a smooth convex objective function, and an optimal rate of $\smash{\widetilde O}(ε^{-2p})$ when the objective is smooth and strongly convex.