Skip to yearly menu bar Skip to main content


Oral
in
Workshop: OPT 2023: Optimization for Machine Learning

Dueling Optimization with a Monotone Adversary

Avrim Blum · Meghal Gupta · Gene Li · Naren Manoj · Aadirupa Saha · Yuanyuan Yang


Abstract: We introduce and study the problem of \textit{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 x for a function f:XR, where XRd. In each round, the algorithm submits a pair of guesses, i.e., x(1) and x(2), and the adversary responds with \textit{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(f(x(1)),f(x(2)))f(x). The goal is to minimize the number of iterations required to find an ε-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(dlog(1/ε)2). Moreover, our dependence on d is asymptotically optimal, as we show examples in which any randomized algorithm for this problem must incur Ω(d) cost and iteration complexity.

Chat is not available.