Grant: Discovery Grants Program - Individual

Toy Example and Introduction: Fans of competitive games, from hockey to videogames such as DOTA, enjoy ranking teams based on their performance. A very simple statistical model for ranking might assume that every team has a single unobserved latent characteristic (their "true skill"), then model the chance of winning a match as a simple function of the "true skills" of the teams playing. A statistician could use this model to infer the ranking and "true skills" of various teams based on the observed games. Furthermore, the statistician could use tools such as Markov chain Monte Carlo (MCMC) to calculate the uncertainty of each part of the estimated ranking - they might be 98% sure that Tampa Bay is better than Columbus, but only 54% sure that it is better than Vegas. In practice, statisticians develop more complicated models that incorporate many types of team skill, but the basic principles and goals are the same. The NHL has only 32 teams, and so it is easy to fit very complicated models. On the other hand, over 400,000 people play DOTA every day. An algorithm that runs in minutes on your phone for NHL data could take months on your desktop for DOTA data. This discrepancy becomes even worse for calculating certainty estimates. The fundamental "big data" problem illustrated by this example is: the computational cost of fitting latent-position models grows very quickly in the size of the dataset, making many natural statistical analyses computationally intractable. The computational costs grow much more quickly than linearly in the size of the dataset, which means that the problem can't easily be solved by simply buying a slightly better computer. The primary goal of this proposal is to develop algorithms that ameliorate this problem, allowing researchers to fit sophisticated models to substantially larger datasets. The secondary goal is to develop a deeper understanding of the limits of this approach - when one must "give up" and try a different approach. Impact: Latent-position models (LPMs) that are almost identical to the "ranking" model described above are not primarily used for sports analysis. They are ubiquitous in cybersecurity (for detecting and prioritizing anamolies), neuroscience (for visualizing functional relationships), and many other areas. Achieving the central goal would allow more sophisticated versions of these models to be applied to larger datasets, improving inference. Methodology and Relation to Existing Literature: Achieving the primary goal requires new (i) point estimators related to LPMs and (ii) methods for incorporating such point estimators into MCMC algorithms. The secondary goal is based on new probabilistic "anti-concentration" bounds. Both rely on expertise in MCMC theory. In the long term, solutions to the "big data" for MCMC and LPMs will lead to solutions for other MCMC "big-data" problems such as tensor models.