Maximum Selection and Sorting with Adversarial Comparators.

Jayadev Acharya, Moein Falahatgar, Ashkan Jafarpour, Alon Orlitsky, Ananda Theertha SureshJMLR 2018 · OpenReview

TL;DR

This paper introduces a new model for "noisy" comparisons where a comparator is mostly accurate but can be adversarial when inputs are close. They develop algorithms for maximum selection and sorting that are efficient even against this strong adversary, achieving near-optimal performance and resolving an open problem in the field. This work has direct implications for density estimation, significantly improving the runtime of existing algorithms.

What Problem Does This Paper Address?

Finding the maximum element or sorting a list of $n$ items are fundamental computational tasks. Traditionally, these are solved using pairwise comparisons. The challenge arises when these comparisons are not perfectly reliable. Previous work has explored "noisy" comparators, often assuming probabilistic errors. This paper tackles a more challenging scenario: adversarial comparators. In this model, a comparator is guaranteed to be correct if the two inputs differ by more than a threshold ($\Delta$), but can arbitrarily (adversarially) choose the outcome if the difference is within $\Delta$. This is motivated by real-world scenarios like human perception (Weber-Fechner law) or sports judging, where small differences can lead to unpredictable outcomes. The paper aims to design algorithms for maximum selection and sorting that are robust to this adversarial noise, with a focus on minimizing the number of comparisons (query complexity) while ensuring a high probability of a correct or near-correct output. A key application is in density estimation, where the goal is to find the closest distribution to an unknown one from a known set, and this paper aims to improve the efficiency of existing methods for this task.

Methods

The paper introduces two adversarial models: non-adaptive (adversary decides all outcomes beforehand) and adaptive (adversary can change outcomes based on previous comparisons). They propose several algorithms:

  • Complete Tournament (COMPL): Compares all pairs. Simple, provides a 2-approximation for maximum selection, but has quadratic query complexity.
  • Sequential Selection (SEQ): Compares elements sequentially. Linear query complexity but poor approximation guarantees.
  • Modified Knock-out (KO-MOD): A multi-round tournament where winners advance. Achieves a 3-approximation with high probability and linear query complexity.
  • Quick-select (Q-SELECT): Inspired by quicksort, it uses a pivot to partition elements. Achieves a 2-approximation with zero error probability against non-adaptive adversaries and linear expected query complexity. However, it can require quadratic queries against adaptive adversaries.
  • Knock-out and Quick-select Combination (COMB): This is the paper's main contribution for maximum selection. It cleverly combines QS-SUB and KO-SUB to achieve a 2-approximation with high probability and linear query complexity, even against adaptive adversaries. This resolves an open problem.

For sorting, they adapt COMPL (COMPL-SORT) and Q-SORT, showing they maintain good approximation guarantees with improved query complexities.

Datasets

Not discussed in the paper. The algorithms are analyzed theoretically based on input size $n$ and error parameter $\epsilon$.

Key Insights and Ideas

  • Adversarial Noise is a Powerful Model: The paper demonstrates that even a limited form of adversarial behavior (only when inputs are close) significantly complicates standard algorithms and requires new approaches.
  • Combining Algorithms is Key: The most significant algorithmic contribution, COMB, arises from combining the strengths of Quick-select (for efficiency and good approximation) and Knock-out (for robustness against adaptive adversaries). This highlights a general strategy for tackling complex adversarial settings.
  • Density Estimation as a Motivator: The paper shows a direct link between the abstract problem of selection/sorting with adversarial comparators and a practical problem in machine learning (density estimation), demonstrating how theoretical advancements can yield practical improvements.
  • Trade-offs Persist: While significant progress is made, the paper still illustrates trade-offs between query complexity, approximation guarantees, and the strength of the adversary.

Key Results

Maximum Selection:

  • Non-adaptive adversary:
    • Sorting algorithm: $\mathcal{O}(n \log n)$ comparisons in expectation.
  • Maximum selection algorithm: $\mathcal{O}(n)$ comparisons in expectation.
  • Adaptive adversary:
    • COMB algorithm: Achieves a 2-approximation of the maximum with probability $1-\epsilon$ using $\mathcal{O}(n \log n)$ comparisons. This resolves an open problem by Ajtai et al. (2015).
  • KO-MOD algorithm: Achieves a 3-approximation with probability $1-\epsilon$ and linear query complexity.

Density Estimation:

  • The paper shows how their maximum selection algorithm can reduce the runtime of finding a distribution close to an unknown one from $\Theta(n^2 \log n)$ to $\Theta(n \log n)$ for a specific class of problems.

Sorting:

  • COMPL-SORT: Zero 2-approximation error with $\mathcal{O}(n^2)$ queries.
  • Q-SORT: Zero 2-approximation error with query complexity bounded by $f(n) = 2n \ln n - (4-2\gamma)n + 2\ln n + \mathcal{O}(1)$ for the non-adaptive adversary, matching the noiseless case.

Limitations and Future Work

  • Approximation Guarantees: While COMB achieves a 2-approximation for maximum selection, the paper notes that KO-MOD cannot achieve better than a 3-approximation with constant probability (shown in Appendix A).
  • Adaptive Adversary for Q-SELECT: Example 2 shows that Q-SELECT can require $\mathcal{O}(n^2)$ queries against an adaptive adversary, motivating the COMB algorithm.
  • Specific Threshold $\Delta$: The analysis assumes a fixed threshold $\Delta=1$. Extending this to a general $\Delta$ might require further work.
  • Future Work: The paper implicitly suggests exploring tighter bounds for sorting algorithms and potentially other applications of adversarial comparators. The density estimation application is a clear avenue for further research, especially for different distribution classes.

Summary updated

Abstract

We study maximum selection and sorting of $n$ numbers using imperfect pairwise comparators. The imperfect comparator returns the larger of the two inputs if the inputs are more than a given threshold apart and an adversarially-chosen input otherwise. We consider two adversarial models: a non-adaptive adversary that decides on the outcomes in advance and an adaptive adversary that decides on the outcome of each comparison depending on the previous comparisons and outcomes. Against the non-adaptive adversary, we derive a maximum-selection algorithm that uses at most $2n$ comparisons in expectation and a sorting algorithm that uses at most $2n\ln n$ comparisons in expectation. In the presence of the adaptive adversary, the proposed maximum-selection algorithm uses $\Theta(n\log (1/{\epsilon}))$ comparisons to output a correct answer with probability at least $1-\epsilon$, resolving an open problem in Ajtai et al. (2015). Our study is motivated by a density-estimation problem. Given samples from an unknown distribution, we would like to find a distribution among a known class of $n$ candidate distributions that is close to the underlying distribution in $\ell_1$ distance. Scheffe's algorithm, for example, in Devroye and Lugosi (2001) outputs a distribution at an $\ell_1$ distance at most 9 times the minimum and runs in time $\Theta(n^2\log n)$. Using our algorithm, the runtime reduces to $\Theta(n\log n)$.
BibTeX
@article{acharya2018maximum,
  author = {Jayadev Acharya and Moein Falahatgar and Ashkan Jafarpour and Alon Orlitsky and Ananda Theertha Suresh},
  title = {{Maximum Selection and Sorting with Adversarial Comparators.}},
  journal = {J. Mach. Learn. Res.},
  year = {2018},
  url = {https://openreview.net/forum?id=tcSUHgJJKU7E},
}
Figure