This talk focuses on the estimation of the distribution of unobserved nodes in large random graphs from the observation of very few edges. 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. The proof relies on the construction of a graphical model encoding conditional dependencies that is extremely efficient to study n-regular graphs obtained using a round-robin scheduling. 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.[-]

This course will give a gentle introduction to SMC (Sequential Monte Carlo algorithms):
• motivation: state-space (hidden Markov) models, sequential analysis of such models; non-sequential problems that may be tackled using SMC.
• Formalism: Markov kernels, Feynman-Kac distributions.
• Monte Carlo tricks: importance sampling and resampling
• standard particle filters: bootstrap, guided, auxiliary
• maximum likelihood estimation of state-stace models
• Bayesian estimation of these models: PMCMC, SMC$^2$.[-]

This course will provide a general introduction to SMC algorithms, from basic particle filters and their uses in state-space (hidden Markov) modelling in various areas, to more advanced algorithms such as SMC samplers, which may be used to sample from one, or several target distributions. The course will cover “a bit of everything”: theory (using Feynman-Kac models as a general framework), methodology (how to construct better algorithms in practice), implementation (examples in Python based on the library particles will be showcased), and applications.[-]

This course will provide a general introduction to SMC algorithms, from basic particle filters and their uses in state-space (hidden Markov) modelling in various areas, to more advanced algorithms such as SMC samplers, which may be used to sample from one, or several target distributions. The course will cover “a bit of everything”: theory (using Feynman-Kac models as a general framework), methodology (how to construct better algorithms in practice), implementation (examples in Python based on the library particles will be showcased), and applications.[-]