Seminar Details
2024-02-06 (14h) : Dynamic ranking and translation synchronization
At Euler building (room A.002)
Organized by Mathematical Engineering
Speaker :
Hemant Tyagi (INRIA Lille - Nord Europe)
Abstract :
In many applications such as recommendation systems or sports tournaments we are given outcomes of pairwise comparisons within a collection of $n$ items, the goal being to estimate the latent strengths and/or global ranking of the items. The Bradley-Terry-Luce (BTL) model is a popular statistical model which has been studied extensively in the literature from a theoretical perspective. Existing results for this problem predominantly focus on the setting consisting of a single comparison graph $G$. However, there exist scenarios (e.g., sports tournaments) where the pairwise comparison data (both the graph and the outcomes) evolves with time, and the data is made available at $T$ grid points in the time domain. Theoretical results for this dynamic setting are relatively limited in the literature.
In this talk, I will first describe a dynamic BTL model where the latent strengths of the items evolve in a Lipschitz manner over time. Given access to a sequence of $T$ comparison graphs and the associated pairwise outcomes, our goal is to estimate the latent strength of the items ($w_t \in R^n$) at any given time point $t$. To this end we propose a simple nearest neighbor based estimator combined with an existing spectral method for ranking (namely Rank Centrality). When the graphs are Erd\"os-Renyi graphs, $\ell_2$ and $\ell_{\infty}$ error bounds are obtained for estimating $w_t$ which in particular establishes the consistency of this method in terms of $T$.
Next, we will look at a dynamic version of a related problem, namely Translation Synchronization, where the latent strengths of the items satisfy a weaker global smoothness assumption over the grid. I will describe two estimators for jointly estimating the latent strengths (over all grid points), and show $\ell_2$ error bounds which establish the (weak) consistency of the estimators with respect to the grid size $T$.
Based on joint work with Eglantine Karle and Ernesto Araya.