# Accelerated Experimental Design for Pairwise Comparisons

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Jan 2019.

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

- [Decreasing Annotation Burden of Pairwise Comparisons with Human-in-the-Loop Sorting: Application in Medical Image Artifact Rating](https://mlsanity.com/paper/2202.04823/) (2022)

## Abstract (arXiv)

Pairwise comparison labels are more informative and less variable than class labels, but generating them poses a challenge: their number grows quadratically in the dataset size. We study a natural experimental design objective, namely, D-optimality, that can be used to identify which K pairwise comparisons to generate. This objective is known to perform well in practice, and is submodular, making the selection approximable via the greedy algorithm. A na"ive greedy implementation has O(N2d2K) complexity, where N is the dataset size, d is the feature space dimension, and K is the number of generated comparisons. We show that, by exploiting the inherent geometry of the dataset--namely, that it consists of pairwise comparisons--the greedy algorithm's complexity can be reduced to O(N2(K+d)+N(dK+d2) +d2K). We apply the same acceleration also to the so-called lazy greedy algorithm. When combined, the above improvements lead to an execution time of less than 1 hour for a dataset with 108 comparisons; the na"ive greedy algorithm on the same dataset would require more than 10 days to terminate.