  We introduce and study the problem of dueling optimization with a monotone
adversary, which is a generalization of (noiseless) dueling convex
optimization. The goal is to design an online algorithm to find a minimizer
$\mathbf{x}^{*}$ for a function $f\colon X \to \mathbb{R}$, where $X \subseteq
\mathbb{R}^d$. In each round, the algorithm submits a pair of guesses, i.e.,
$\mathbf{x}^{(1)}$ and $\mathbf{x}^{(2)}$, and the adversary responds with any
point in the space that is at least as good as both guesses. The cost of each
query is the suboptimality of the worse of the two guesses; i.e., ${\max}
\left( f(\mathbf{x}^{(1)}), f(\mathbf{x}^{(2)}) \right) - f(\mathbf{x}^{*})$.
The goal is to minimize the number of iterations required to find an
$\varepsilon$-optimal point and to minimize the total cost (regret) of the
guesses over many rounds. Our main result is an efficient randomized algorithm
for several natural choices of the function $f$ and set $X$ that incurs cost
$O(d)$ and iteration complexity $O(d\log(1/\varepsilon)^2)$. Moreover, our
dependence on $d$ is asymptotically optimal, as we show examples in which any
randomized algorithm for this problem must incur $\Omega(d)$ cost and iteration
complexity.

Data Structures and Algorithms;Machine Learning;Machine Learning