Dueling Convex Optimization with General Preferences

We address the problem of convex optimization with dueling feedback, where the goal is to minimize a 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 values of the two queried points. The translation of the function values to the single comparison bit is through a 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 O(ǫ -4p ) for a smooth convex objective function, and an optimal rate of O(ǫ -2p ) when the objective is smooth and strongly convex.