Anderson Ye Zhang
University of Pennsylvania
Tuesday, March 28, 2023
3:30 pm - 4:30 pm
154 Hurley Hall
Title: Learning From Pairwise Comparisons Using Spectral Methods
Abstract: Learning from pairwise comparisons is an important task in many fields including recommendation systems, sports, psychology, social choices, etc. In today's talk, we focus on using spectral methods which refer to algorithms built upon the eigendecomposition of matrices constructed from data. They are simple but powerful and have gained increasing attention in recent years. (1) In the first part of the talk, we study the Bradley-Terry-Luce (BTL) model. We derive sharp and uniform non-asymptotic expansions for the Rank Centrality algorithm when the underlying graph is sparse. This enables us to obtain entrywise distributions of the estimator and to construct confidence intervals for individual ranks. (2) In the second part of the talk, we study the phase synchronization problem where the latent objects belong to the permutation group and the pairwise measurements among them are noisy and missing at random. We propose a new spectral method that overcomes a crucial limitation of existing methods in literature and outperforms them. We further establish the statistical optimality of the proposed method.