In this paper, we address the top-$K$ ranking problem with a monotone
adversary. We consider the scenario where a comparison graph is randomly
generated and the adversary is allowed to add arbitrary edges. The
statistician's goal is then to accurately identify the top-$K$ preferred items
based on pairwise comparisons derived from this semi-random comparison graph.
The main contribution of this paper is to develop a weighted maximum likelihood
estimator (MLE) that achieves near-optimal sample complexity, up to a
$\log^2(n)$ factor, where n denotes the number of items under comparison. This
is made possible through a combination of analytical and algorithmic
innovations. On the analytical front, we provide a refined $\ell_\infty$ error
analysis of the weighted MLE that is more explicit and tighter than existing
analyses. It relates the $\ell_\infty$ error with the spectral properties of
the weighted comparison graph. Motivated by this, our algorithmic innovation
involves the development of an SDP-based approach to reweight the semi-random
graph and meet specified spectral properties. Additionally, we propose a
first-order method based on the Matrix Multiplicative Weight Update (MMWU)
framework. This method efficiently solves the resulting SDP in nearly-linear
time relative to the size of the semi-random comparison graph.

本文研究了具有单调对手的前 K 名排名问题，在随机生成的比较图的基础上，统计学家的目标是根据半随机比较图中的成对比较，准确地确定前 K 名的首选项目。主要贡献是开发了一种加权的最大似然估计器，它在样本复杂度方面实现了接近最优的性能，最多有对数因子 (log^2 (n))，其中 n 是比较的项目数量。通过分析和算法创新的组合实现了这一目标。

与递增对手的前 K 名排名

Top-$K$ ranking with a monotone adversary

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.

用一个在线算法设计 dueling optimization 问题的最优解，最小化迭代复杂度和总成本。