Stochastic Models for Comparison-based Search

EDIC candidacy exam
Exam president: Prof. Boi Faltings
Thesis advisor: Prof. Matthias Grossglauser
Co-examiner: Prof. Michael Kapralov

Abstract
Given a set of objects H with hidden features in Rd
we are interested in finding a target object ~ 2 H by querying
pairwise comparisons of the objects in H to ~ and observing
their noisy outcomes. Another problem we would like to explore
is the actual embedding of the objects in H given the outcomes of
their pairwise comparisons. Finally, we are interested in solutions
for the combination of these two tasks into one reinforcement
learning problem.
In this proposal, we discuss three papers related to our
research. First, we overview very general bayesian active learning
strategies. Next we examine some ranking techniques of preembedded
objects using pairwise comparisons. Finally, we discuss
modern ordinal embedding solutions.

Background papers
Near-Optimal Bayesian Active Learning with Noisy Observations, by Daniel Golovin, Andreas Krause, Debajyoti Ray.
Active Ranking using Pairwise Comparisons, by Kevin G. Jamieson, Robert D. Nowak.
Finite Sample Prediction and Recovery Bounds for Ordinal Embedding, by Lalit Jain, Kevin Jamieson, Robert Nowak