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 for a function , where . In each round, the algorithm submits a pair of guesses, i.e., and , 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., . 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 and set that incurs cost and iteration complexity . Moreover, our dependence on is asymptotically optimal, as we show examples in which any randomized algorithm for this problem must incur cost and iteration complexity.
Chat is not available.