Timezone: »

 
Poster
Optimal Sample Complexity of M-wise Data for Top-K Ranking
Minje Jang · Sunghyun Kim · Changho Suh · Sewoong Oh

Wed Dec 06 06:30 PM -- 10:30 PM (PST) @ Pacific Ballroom #46
in Posters Wed »
We explore the top-K rank aggregation problem in which one aims to recover a consistent ordering that focuses on top-K ranked items based on partially revealed preference information. We examine an M-wise comparison model that builds on the Plackett-Luce (PL) model where for each sample, M items are ranked according to their perceived utilities modeled as noisy observations of their underlying true utilities. As our result, we characterize the minimax optimality on the sample size for top-K ranking. The optimal sample size turns out to be inversely proportional to M. We devise an algorithm that effectively converts M-wise samples into pairwise ones and employs a spectral method using the refined data. In demonstrating its optimality, we develop a novel technique for deriving tight $\ell_\infty$ estimation error bounds, which is key to accurately analyzing the performance of top-K ranking algorithms, but has been challenging. Recent work relied on an additional maximum-likelihood estimation (MLE) stage merged with a spectral method to attain good estimates in $\ell_\infty$ error to achieve the limit for the pairwise model. In contrast, although it is valid in slightly restricted regimes, our result demonstrates a spectral method alone to be sufficient for the general M-wise model. We run numerical experiments using synthetic data and confirm that the optimal sample size decreases at the rate of 1/M. Moreover, running our algorithm on real-world data, we find that its applicability extends to settings that may not fit the PL model.
Keywords: Spectral Methods · Information Theory · Learning Theory · Ranking and Preference Learning · Information Retrieval
[ Paper] 

Author Information

Minje Jang (KAIST)
Sunghyun Kim (ETRI)
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 recevied 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.

Sewoong Oh (UIUC)

More from the Same Authors