Dynamic Ranking and Translation Synchronization

Araya, Ernesto; Karlé, Eglantine; Tyagi, Hemant

Type de document :

Compte-rendu et recension critique d'ouvrage

DOI :

10.1093/imaiai/iaad029

Titre :

Dynamic Ranking and Translation Synchronization

Auteur(s) :

Araya, Ernesto [Auteur]
MOdel for Data Analysis and Learning [MODAL]
Karlé, Eglantine [Auteur]
MOdel for Data Analysis and Learning [MODAL]
Tyagi, Hemant [Auteur]
MOdel for Data Analysis and Learning [MODAL]

Titre de la revue :

Information and Inference

Pagination :

2224-2266

Éditeur :

Oxford University Press (OUP)

Date de publication :

2023-09-27

ISSN :

2049-8764

Discipline(s) HAL :

Mathématiques [math]/Statistiques [math.ST]
Statistiques [stat]/Machine Learning [stat.ML]

Résumé en anglais : [en]

In many applications, such as sport tournaments or recommendation systems, we have at our disposal data consisting of pairwise comparisons between a set of $n$ items (or players). The objective is to use this data to infer ...
Lire la suite >In many applications, such as sport tournaments or recommendation systems, we have at our disposal data consisting of pairwise comparisons between a set of $n$ items (or players). The objective is to use this data to infer the latent strength of each item and/or their ranking. 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 the pairwise comparison data evolves with time. Theoretical results for this dynamic setting are relatively limited and is the focus of this paper. We study an extension of the \emph{translation synchronization} problem, to the dynamic setting. In this setup, we are given a sequence of comparison graphs $(G_t)_{t\in \mathcal{T}}$, where $\mathcal{T} \subset [0,1]$ is a grid representing the time domain, and for each item $i$ and time $t\in \mathcal{T}$ there is an associated unknown strength parameter $z^*_{t,i}\in \mathbb{R}$. We aim to recover, for $t\in\mathcal{T}$, the strength vector $z^*_t=(z^*_{t,1},\dots,z^*_{t,n})$ from noisy measurements of $z^*_{t,i}-z^*_{t,j}$, where $\{i,j\}$ is an edge in $G_t$. Assuming that $z^*_t$ evolves smoothly in $t$, we propose two estimators -- one based on a smoothness-penalized least squares approach and the other based on projection onto the low frequency eigenspace of a suitable smoothness operator. For both estimators, we provide finite sample bounds for the $\ell_2$ estimation error under the assumption that $G_t$ is connected for all $t\in \mathcal{T}$, thus proving the consistency of the proposed methods in terms of the grid size $|\mathcal{T}|$. We complement our theoretical findings with experiments on synthetic and real data.Lire moins >

Langue :

Anglais

Vulgarisation :

Non

Collections :

Laboratoire Paul Painlevé - UMR 8524

Source :

Harvested from HAL

Fichiers

2207.01455
Accès libre
Accéder au document

Dynamic Ranking and Translation Synchronization BibTeX CSV Excel RIS

Fichiers

Dynamic Ranking and Translation Synchronization

BibTeX

CSV

Excel

RIS