Timezone: »

Active Learning for Top-$K$ Rank Aggregation from Noisy Comparisons
Soheil Mohajer · Changho Suh · Adel Elmahdy

Tue Aug 08 01:30 AM -- 05:00 AM (PDT) @ Gallery #102
We explore an active top-$K$ ranking problem based on pairwise comparisons that are collected possibly in a sequential manner as per our design choice. We consider two settings: (1) \emph{top-$K$ sorting} in which the goal is to recover the top-$K$ items in order out of $n$ items; (2) \emph{top-$K$ partitioning} where only the set of top-$K$ items is desired. Under a fairly general model which subsumes as special cases various models (e.g., Strong Stochastic Transitivity model, BTL model and uniform noise model), we characterize upper bounds on the sample size required for top-$K$ sorting as well as for top-$K$ partitioning. As a consequence, we demonstrate that active ranking can offer significant multiplicative gains in sample complexity over passive ranking. Depending on the underlying stochastic noise model, such gain varies from around $\frac{\log n}{\log \log n}$ to $\frac{ n^2 \log n }{\log \log n}$. We also present an algorithm that is applicable to both settings.

Author Information

Soheil Mohajer (University of Minnesota)
Changho Suh (KAIST)

Changho Suh is an Ewon Associate Professor in the School of Electrical Engineering at Korea Advanced Institute of Science and Technology (KAIST). He received the B.S. and M.S. degrees in Electrical Engineering from KAIST in 2000 and 2002 respectively, and the Ph.D. degree in Electrical Engineering and Computer Sciences from UC-Berkeley in 2011, under the supervision of Prof. David Tse. From 2011 to 2012, he was a postdoctoral associate at the Research Laboratory of Electronics in MIT. From 2002 to 2006, he had been with the Telecommunication R&D Center, Samsung Electronics. Dr. Suh received the 2015 IEIE Hadong Young Engineer Award, a 2015 Bell Labs Prize finalist, the 2013 IEEE Communications Society Stephen O. Rice Prize, the 2011 David J. Sakrison Memorial Prize (top research award in the UC-Berkeley EECS Department), and the 2009 IEEE ISIT Best Student Paper Award.

Adel Elmahdy (University of Minnesota)

Adel received the B.Sc. degree in electrical engineering from Alexandria University, Egypt, in 2011, and the M.Sc. degree in wireless communications from Nile University, Egypt, in 2015. He is currently pursuing the Ph.D. degree in electrical engineering with the University of Minnesota, Minneapolis, MN, USA. He was a Graduate Research Assistant and a Teaching Assistant with The American University in Cairo, Egypt, from 2011 to 2012. Then, he joined the Wireless Intelligent Networks Center (WINC), Nile University, in 2013, as a Research Assistant. From 2015 to 2016, he was a Research Assistant with Qatar University, Qatar. He is a recipient of the Graduate Fellowship from Nile University in 2013 and 2014, and the ADC Fellowship from the University of Minnesota in 2016. His research interests include wireless communications, multiuser information theory, and distributed machine learning.

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors