Georgia Institute of Technology College of Sciences

Higher-order multiway data is ubiquitous in machine learning and statistics and often exhibits community-like structures, where each component (node) along each different mode has a community membership associated with it. In this talk we propose the tensor mixed-membership blockmodel, a generalization of the tensor blockmodel positing that memberships need not be discrete, but instead are convex combinations of latent communities. We first study the problem of estimating community memberships, and we show that a tensor generalization of a matrix algorithm can consistently estimate communities at a rate that improves relative to the matrix setting, provided one takes the tensor structure into account. Next, we study the problem of testing whether two nodes have the same community memberships, and we show that a tensor analogue of a matrix test statistic can yield consistent testing with a tighter local power guarantee relative to the matrix setting. If time permits we will also examine the performance of our estimation procedure on flight data. This talk is based on two recent works with Anru Zhang.

Abstract: Motivated by applications in Reinforcement Learning (RL), this talk focuses on the Stochastic Appproximation (SA) method to find fixed points of a contractive operator. First proposed by Robins and Monro, SA is a popular approach for solving fixed point equations when the information is corrupted by noise. We consider the SA algorithm for operators that are contractive under arbitrary norms (especially the l-infinity norm). We present finite sample bounds on the mean square error, which are established using a Lyapunov framework based on infimal convolution and generalized Moreau envelope. We then present our more recent result on concentration of the tail error, even when the iterates are not bounded by a constant. These tail bounds are obtained using exponential supermartingales in conjunction with the Moreau envelop and a novel bootstrapping approach. Our results immediately imply the state-of-the-art sample complexity results for a large class of RL algorithms.

Bio: Siva Theja Maguluri is Fouts Family Early Career Professor and Associate Professor in the H. Milton Stewart School of Industrial and Systems Engineering at Georgia Tech. He obtained his Ph.D. and MS in ECE as well as MS in Applied Math from UIUC, and B.Tech in Electrical Engineering from IIT Madras. His research interests span the areas of Control, Optimization, Algorithms and Applied Probability and include Reinforcement Learning theory and Stochastic Networks. His research and teaching are recognized through several awards including the  Best Publication in Applied Probability award, NSF CAREER award, second place award at INFORMS JFIG best paper competition, Student best paper award at IFIP Performance, CTL/BP Junior Faculty Teaching Excellence Award, and Student Recognition of Excellence in Teaching: Class of 1934 CIOS Award.

This talk will present an overview of the behavior of the eigenvalues of the fractional Brownian matrix motion and other related matrix processes. We will do so by emphasizing the dynamics of the eigenvalues processes, the non-colliding property, the limit of the associated empirical process, as well as the free Brownian motion and the non commutative fractional Brownian motion.

Gaussian mixture block models are distributions over graphs that strive to model modern networks: to generate a graph from such a model, we associate each vertex with a latent feature vector sampled from a mixture of Gaussians, and we add edge if and only if the feature vectors are sufficiently similar. The different components of the Gaussian mixture represent the fact that there may be different types of nodes with different distributions over features---for example, in a social network each component represents the different attributes of a distinct community. Natural algorithmic tasks associated with these networks are embedding (recovering the latent feature vectors) and clustering (grouping nodes by their mixture component).

In this talk, we focus on clustering and embedding graphs sampled from high-dimensional Gaussian mixture block models, where the dimension of the latent feature vectors goes to infinity as the size of the network goes to infinity. This high-dimensional setting is most appropriate in the context of modern networks, in which we think of the latent feature space as being high-dimensional. We analyze the performance of canonical spectral clustering and embedding algorithms for such graphs in the case of 2-component spherical Gaussian mixtures and begin to sketch out the information-computation landscape for clustering and embedding in these models.

This is based on joint work with Tselil Schramm.