Timezone: »

 
Poster
Optimal Sequential Maximization: One Interview is Enough!
Moein Falahatgar · Alon Orlitsky · Venkatadheeraj Pichapati

Wed Jul 15 09:00 AM -- 09:45 AM & Wed Jul 15 08:00 PM -- 08:45 PM (PDT) @
in Poster Session 23 »

Maximum selection under probabilistic queries \emph{(probabilistic maximization)} is a fundamental algorithmic problem arising in numerous theoretical and practical contexts. We derive the first query-optimal sequential algorithm for probabilistic-maximization. Departing from previous assumptions, the algorithm and performance guarantees apply even for infinitely many items, hence in particular do not require a-priori knowledge of the number of items. The algorithm has linear query complexity, and is optimal also in the streaming setting.

To derive these results we consider a probabilistic setting where several candidates for a position are asked multiple questions with the goal of finding who has the highest probability of answering interview questions correctly. Previous work minimized the total number of questions asked by alternating back and forth between the best performing candidates, in a sense, inviting them to multiple interviews. We show that the same order-wise selection accuracy can be achieved by querying the candidates sequentially, never returning to a previously queried candidate. Hence one interview is enough!

Keywords: Ranking and Preference Learning · Supervised Learning · Online Learning / Bandits

Author Information

Moein Falahatgar (UCSD)
Alon Orlitsky (UCSD)
Venkatadheeraj Pichapati (Apple Inc)

More from the Same Authors