# Dueling Optimization with a Monotone Adversary

arXiv: https://arxiv.org/abs/2311.11185 · HTML: https://mlsanity.com/paper/2311.11185/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 6 references that are in the map.
- First posted on arXiv 18 Nov 2023.

## Builds on (most cited first, 4 of 4)

- [Distribution-Independent PAC Learning of Halfspaces with Massart Noise](https://mlsanity.com/paper/1906.10075/) (2019)
- [Regret Lower Bound and Optimal Algorithm in Dueling Bandit Problem](https://mlsanity.com/paper/1506.02550/) (2015)
- [Multidimensional Binary Search for Contextual Decision-Making](https://mlsanity.com/paper/1611.00829/) (2016)
- [Semi-Random Sparse Recovery in Nearly-Linear Time](https://mlsanity.com/paper/2203.04002/) (2022)

## Built on by (most cited first, 8 of 8)

- [Learning Noisy Halfspaces with a Margin: Massart is No Harder than Random](https://mlsanity.com/paper/2501.09851/) (2025)
- [Faster Convergence with Multiway Preferences](https://mlsanity.com/paper/2312.11788/) (2023)
- [Think Before You Duel: Understanding Complexities of Preference Learning under Constrained Resources](https://mlsanity.com/paper/2312.17229/) (2023)
- [Top-K ranking with a monotone adversary](https://mlsanity.com/paper/2402.07445/) (2024)
- [On the Robustness of Spectral Algorithms for Semirandom Stochastic Block Models](https://mlsanity.com/paper/2412.14315/) (2024)
- [DP-Dueling: Learning from Preference Feedback without Compromising User Privacy](https://mlsanity.com/paper/2403.15045/) (2024)
- [Combinatorial Sparse PCA Beyond the Spiked Identity Model](https://mlsanity.com/paper/2603.02607/) (2026)
- [Learning in Continuous Games from Pairwise Preference Feedback](https://mlsanity.com/paper/2610.05428/) (2026)

## Abstract (arXiv)

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 x* for a function fcolon X → ℝ, where X subseteq ℝd. In each round, the algorithm submits a pair of guesses, i.e., x(1) and 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(x(1)), f(x(2)) right) - f(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(dlog(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.