ICTS

How does a product of random matrices behave? This question has a long history in dynamical systems and ergodic theory, where the focus is on asymptotic behavior as the number of factors increases. It has also been studied within high-dimensional statistics and free probability, where the focus is on the asymptotic behavior as the dimension increases. Recently, products of random matrices have received renewed attention as a model for the behavior of randomized optimization algorithms, where it is important to obtain results for a fixed number of factors with a fixed dimension.

This talk outlines an easy method for obtaining such nonasymptotic concentration inequalities for a product of random matrices. As an application, we will show how this approach allows us to design an optimal randomized algorithm for the simulation of a quantum system. No background in random matrix theory or quantum information will be required.

The results are drawn from two collaborations: http://arxiv.org/abs/2003.05437 <http://arxiv.org/abs/2003.05437>, with De Huang, Jonathan Niles-Weed, and Rachel Ward. http://arxiv.org/abs/2008.11751 <http://arxiv.org/abs/2008.11751>, with Chi-Fang (Anthony) Chen, Hsin-Yuan (Robert) Huang, and Richard Kueng.

In light of recent advances in data collection, sports possess a number of features that make them an ideal testing ground for new analyses and algorithms.  In this talk I will describe a few studies that lie at the intersection of sports and data.  The first centers on fantasy sports which have experienced a surge in popularity in the past decade. One of the consequences of this recent rapid growth is increased scrutiny surrounding the legal aspects of the games, which typically hinge on the relative roles of skill and chance in the outcome of a competition. While there are many ethical and legal arguments that enter into the debate, the answer to the skill versus chance question is grounded in mathematics. In this talk I will analyze data from daily fantasy competitions and propose a new metric to quantify the relative roles of skill and chance in games and other activities. Time permitting, in the second part of this talk, I will briefly outline two additional studies that lie at the intersection on sports and probability. The first is a collaboration with Major League Baseball to determine the physics behind the recent increase in the rate of home runs; in particular I will enumerate different potential drivers for the observed increase and evaluate the evidence in the data (box score, ball tracking, weather, etc) in support of each theory.  The second explores one aspect of the impact of the pandemic on sports through data associated with opening NFL stadiums to fans.

Uniform and preferential attachment trees are among the simplest examples of dynamically growing networks. The statistical problems we address in this talk regard discovering the past of the tree when a present-day snapshot is observed. We present a few results that show that, even in  gigantic networks, a lot of information is preserved from the very early days. In particular,  we discuss the problem of finding the root and the broadcasting problem.

We report recent results on two classical inference problems in linear systems. (i) In the first problem, we wish to identify the dynamics of a canonical linear time-invariant systems $x_{t+1}=Ax_t+\eta_{t+1}$ from an observed trajectory. We provide system-specific sample complexity lower bound satisfied by any $(\epsilon, \delta)$-PAC algorithm, i.e., yielding an estimation error less than $\epsilon$ with probability at least $1-\delta$. We further establish that the Ordinary Least Squares estimator achieves this fundamental limit. (ii) In the second inference problem, we aim at identifying the best arm in bandit optimization with linear rewards. We derive instance-specific sample complexity lower bounds for any $\delta$-PAC algorithm, and devise a simple track-and-stop algorithm achieving this lower bound. In both inference problems, the analysis relies on novel concentration results for the spectrum of the covariates matrix. Joint work with Yassir Jedra

We show fully polynomial time randomized approximation schemes for counting matchings of a given size, or more generally sampling/counting monomer-dimer systems in planar, not-necessarily-bipartite, graphs. While perfect matchings on planar graphs can be counted exactly in polynomial time, counting non-perfect matchings was shown by Jerrum [Jer87] to be #P-hard, who also raised the question of whether efficient approximate counting is possible. We answer this affirmatively by showing that the multi-site Glauber dynamics on the set of monomers in a monomer-dimer system always mixes rapidly, and that this dynamics can be implemented efficiently on families of graphs where counting perfect matchings is tractable. In order to analyze mixing properties of the multi-site Glauber dynamics, we establish two new notions for generating polynomials of discrete set-valued distributions: sector-stability and fractional log-concavity. These notions generalize well-studied properties like real-stability and log-concavity, but unlike them robustly degrade under useful transformations applied to the distribution. We relate these notions to pairwise correlations in the underlying distribution and the notion of spectral independence introduced by Anari, Liu, and Oveis Gharan [ALO20], providing a new tool for establishing spectral independence based on zeros of polynomials. As a byproduct of our techniques, we show that polynomials whose roots avoid certain regions of the complex plane must satisfy a form of convexity, extending a classic result established between hyperbolic and log-concave polynomials by Gårding [Går59] to new classes of polynomials. As further applications of our results, we show how to sample efficiently from certain partition-constrained strongly Rayleigh distributions, and certain asymmetric determinantal point processes using natural Markov chains. Joint work with Yeganeh Alimohammadi, Kirankumar Shiragur, and Thuy-Duong Vuong.

Suppose we can readily access samples from $\pi_c(x)$, $1\le c\le C$, but we wish to obtain samples from $\pi (x) = \prod_ {c=1}^C \pi_c (x) $. The so-called Fusion problem comes up within various areas of modern Bayesian Statistical analysis, for example in the context of big data or privacy constraints, as well as more traditional areas such as meta-analysis. Many approximate solutions to this problem have been proposed. This talk will present an exact solution based on rejection sampling in an extended state space, where the accept/reject decision is carried out by simulating the skeleton of a suitably constructed auxiliary collection of Brownian bridges. It will also present a much more scalable Sequential Monte Carlo method which allow the method to be used for larger $C$ and in the context of greater discrepancies between the $\pi_c(x)$ densities. Some theoretical results underpinning the method and its computational efficiency will be presented. This is joint work with Hongsheng Dai (Essex, UK) and Murray Pollock (Newcastle, UK).