Timezone: »

 
Spotlight
Discrete-Valued Latent Preference Matrix Estimation with Graph Side Information
Changhun Jo · Kangwook Lee

Wed Jul 21 06:35 PM -- 06:40 PM (PDT) @
in Learning Theory 9 »

Incorporating graph side information into recommender systems has been widely used to better predict ratings, but relatively few works have focused on theoretical guarantees. Ahn et al. (2018) firstly characterized the optimal sample complexity in the presence of graph side information, but the results are limited due to strict, unrealistic assumptions made on the unknown latent preference matrix and the structure of user clusters. In this work, we propose a new model in which 1) the unknown latent preference matrix can have any discrete values, and 2) users can be clustered into multiple clusters, thereby relaxing the assumptions made in prior work. Under this new model, we fully characterize the optimal sample complexity and develop a computationally-efficient algorithm that matches the optimal sample complexity. Our algorithm is robust to model errors and outperforms the existing algorithms in terms of prediction performance on both synthetic and real data.

Keywords: Information Theory
[ Paper ]

Author Information

Changhun Jo (University of Wisconsin-Madison)
Kangwook Lee (UW Madison)

I am an Assistant Professor at the Electrical and Computer Engineering department and the Computer Sciences department (by courtesy) at the University of Wisconsin-Madison. Previously, I was a Research Assistant Professor at Information and Electronics Research Institute of KAIST, working with Prof. Changho Suh. Before that, I was a postdoctoral scholar at the same institute. I received my PhD in May 2016 from the Electrical Engineering and Computer Science department at UC Berkeley and my Master of Science degree from the same department in December 2012, both under the supervision of Prof. Kannan Ramchandran. I was a member of Berkeley Laboratory of Information and System Sciences (BLISS, aka Wireless Foundation) and BASiCS Group. I received my Bachelor of Science degree in Electrical Engineering from Korea Advanced Institute of Science and Technology (KAIST) in May 2010.

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

More from the Same Authors