Nonparametric maximum likelihood estimation for large random graphs with latent data
These graphs naturally model tournaments involving a large number of players (the nodes) where the ability to win of each player is unknown.
The players are only partially observed through discrete valued scores (edges) describing the results of contests between players. In this very sparse setting, we present the first nonasymptotic risk bounds for maximum likelihood estimators (MLE) of the unknown distribution of the nodes.
This graphical model allows to prove geometric loss of memory properties and deduce the asymptotic behavior of the likelihood function.
Following a classical construction in learning theory, the asymptotic likelihood is used to define a measure of performance for the MLE. Risk bounds for the MLE are finally obtained by subgaussian deviation results derived from concentration inequalities for Markov chains applied to our graphical model. Bayesian posterior concentration rates for the unknown distribution are also proposed.