论文标题
与一般偏好的决斗凸优化
Dueling Convex Optimization with General Preferences
论文作者
论文摘要
我们解决了\ emph {convex优化使用对决反馈}的问题，在这种问题中，目标是在\ emph {dueling}反馈的情况下最小化凸函数。每个查询由两个点组成，决斗反馈返回了两个查询点功能值的（嘈杂）单位二进制比较。函数值对单个比较位的翻译是通过\ emph {传输函数}的。此问题先前已经针对某些受限类的传输功能解决了，但是在这里我们考虑了一个非常通用的传输功能类，其中包括所有功能，这些功能可以由有限多项式（最小值$ p $）近似。我们的主要贡献是一种有效的算法，其收敛速率为$ \ smash {\ widetilde o}（ε^{ - 4p}）$，用于平稳的凸目标函数，最佳速率为$ \ smash {\ widetilde o}（ε^{ - 2p}）$时，目的是平稳的convex and Conve and Conve and conve and conve and conve。
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.
