Georgia Institute of Technology College of Sciences

We discuss two recent results concerning disease modeling on networks. The infection is assumed to spread via contagion (e.g., transmission over the edges of an underlying network). In the first scenario, we observe the infection status of individuals at a particular time instance and the goal is to identify a confidence set of nodes that contain the source of the infection with high probability. We show that when the underlying graph is a tree with certain regularity properties and the structure of the graph is known, confidence sets may be constructed with cardinality independent of the size of the infection set. In the scenario, the goal is to infer the network structure of the underlying graph based on knowledge of the infected individuals. We develop a hypothesis test based on permutation testing, and describe a sufficient condition for the validity of the hypothesis test based on automorphism groups of the graphs involved in the hypothesis test. This is joint work with Justin Khim (UPenn).

I will revisit the classical Stein's method, for normal random variables, as well as its version for Poisson random variables and show how both (as well as many other examples) can be incorporated in a single framework.

Spectral algorithms are a powerful method for detecting low-rank structure in dense random matrices and random graphs. However, in certain problems involving sparse random graphs with bounded average vertex degree, a naive spectral analysis of the graph adjacency matrix fails to detect this structure. In this talk, I will discuss a semidefinite programming (SDP) approach to address this problem, which may be viewed both as imposing a delocalization constraint on the maximum eigenvalue problem and as a natural convex relaxation of minimum graph bisection. I will discuss probabilistic results that bound the value of this SDP for sparse Erdos-Renyi random graphs with fixed average vertex degree, as well as an extension of the lower bound to the two-group stochastic block model. Our upper bound uses a dual witness construction that is related to the non-backtracking matrix of the graph. Our lower bounds analyze the behavior of local algorithms, and in particular imply that such algorithms can approximately solve the SDP in the Erdos-Renyi setting. This is joint work with Andrea Montanari.

Estimation of the covariance matrix has attracted significant attention of the statistical research community over the years, partially due to important applications such as Principal Component Analysis. However, frequently used empirical covariance estimator (and its modifications) is very sensitive to outliers, or ``atypical’’ points in the sample. As P. Huber wrote in 1964, “...This raises a question which could have been asked already by Gauss, but which was, as far as I know, only raised a few years ago (notably by Tukey): what happens if the true distribution deviates slightly from the assumed normal one? As is now well known, the sample mean then may have a catastrophically bad performance…” Motivated by Tukey's question, we develop a new estimator of the (element-wise) mean of a random matrix, which includes covariance estimation problem as a special case. Assuming that the entries of a matrix possess only finite second moment, this new estimator admits sub-Gaussian or sub-exponential concentration around the unknown mean in the operator norm. We will present extensions of our approach to matrix-valued U-statistics, as well as applications such as the matrix completion problem. Part of the talk will be based on a joint work with Xiaohan Wei.