Current Series

[View Past Series]

Fri Sep 13

Probability Seminar

2:30pm - Vincent Hall 311
Critical behavior for percolation on graphs with given degrees
Souvik Dhara, MIT

We discuss critical behavior of percolation on finite random networks. In a seminal paper, Aldous (1997) identified the scaling limit for the component sizes in the critical window of phase transition for the Erdos-Renyi random graph (ERRG). Subsequently, there has been a surge in the literature, revealing several interesting scaling limits of these critical components, namely, the component size, diameter, or the component itself when viewed as a metric space. Fascinatingly, when the third moment of the asymptotic degree distribution is finite, many random graph models have been shown to exhibit a universality phenomenon in the sense that their scaling exponents and limit laws are the same as the ERRG. In contrast, when the asymptotic degree distribution is heavy-tailed (having an infinite third moment), the limit law turns out to be fundamentally different from the ERRG case and in particular, becomes sensitive to the precise asymptotics of the highest degree vertices.

In this talk, we will focus on random graphs with a prescribed degree sequence. We start by discussing recent scaling limit results, and explore the universality classes that arise from heavy-tailed networks. Of particular interest is a new universality class that arises when the asymptotic degree distribution has an infinite second moment. Not only it gives rise to a completely new universality class, it also exhibits several surprising features that have never been observed in any other universality class so far.

This is based on joint works with Shankar Bhamidi, Remco van der Hofstad, Johan van Leeuwaarden and Sanchayan Sen.

Fri Sep 27

Probability Seminar

2:30pm - Vincent Hall 311
Random matrices, operators and analytic functions
Benedek Valko, UW Madison

The finite circular beta-ensembles and their point process scaling limit can be represented as the spectra of certain random differential operators. These operators can be realized on a single probability space so that the point process scaling limit is a consequence of an operator level limit. The construction allows the derivation of the scaling limit of the normalized characteristic polynomials of the finite models to a random analytic function. I will review these representations and constructions, and present a couple of applications.

Joint with B. Virág (Toronto).

Fri Oct 04

Probability Seminar

2:30pm - Vincent Hall 311
Reconstruction problems on amenable graphs
Ahmed El Alaoui, Stanford University

We consider the problem of reconstructing a hidden assignment of random variables (x_1,…, x_n) sitting on the nodes of a graph, given noisy observations of pairs (x_u, x_v) for every edge (u,v) of the graph. Such problems have been extensively studied when the underlying graph is ‘mean-field’ (e.g., the complete graph, Erdos-Renyi, random regular,…), in which case the existence of a ``possible-but-hard’’ phase where reconstruction is possible but computationally difficult is ubiquitous.

In contrast, the picture is dramatically different when the graph is amenable. I will represent a generic result about the optimality of local algorithms for computing marginals under a somewhat strong model of side information. Next, I will focus on Z_2 synchronization (aka planted Ising model) on the Euclidean lattice with weaker side information, and discuss a renormalization-based procedure for reconstructing the assignment.

Joint work with Andrea Montanari.

Fri Oct 04

Probability Seminar

3:30pm - Vincent Hall 311
Invertibility of inhomogenuous heavy-tailed matrices
Galyna Livshyts, Georgia Tech

We will show the sharp estimate on the behavior of the smallest singular value of random matrices under very general assumptions. One of the key steps in the proof is a result about the efficient discretization of the unit sphere in an n-dimensional euclidean space. This result allows us to work with very general random matrices. The proof of the result will be outlined. Partially based on the joint work with Tikhomirov and Vershynin.

Fri Oct 18

Probability Seminar

2:30pm - Vincent Hall 311
Rare events in the spectrum of random matrices
Kevin Leder, UMN

In this talk I will consider extreme behavior of the extremal eigenvalues of white Wishart matrices, which play an important role in multivariate analysis. I will focus on the case when the dimension of the feature p is much larger than or comparable to the number of observations n, a common situation in modern data analysis. I will discuss asymptotic approximations for the tail probabilities of the extremal eigenvalues. In addition, I will discuss the construction of an efficient Monte Carlo importance sampling algorithm to estimate the tail probabilities. Simulation results show that our method has the best performance among known approximation approaches, and furthermore provides an efficient and accurate way for evaluating the tail probabilities in practice. Based on joint work with Tiefieng Jiang and Gongjun Xu.

Fri Oct 25

Probability Seminar

2:30pm - Vincent Hall 311
Probability Seminar
Kevin Leder, UMN
Fri Nov 08

Probability Seminar

2:30pm - Vincent Hall 311
"Robust Synchronization via Cycle Consistency Inference
Yunpeng Shi, UMN

We propose a strategy for improving the existing methods for solving synchronization problems that arise from various computer vision tasks. Specifically, our strategy identifies severely corrupted relative measurements based on cycle consistency information. To the best of our knowledge, this paper provides the first exact recovery guarantees using cycle consistency information. This result holds for a noiseless but corrupted setting as long as the ratio of corrupted cycles per edge is sufficiently small. It further guarantees linear convergence to the desired solution. We also establish stability of the proposed algorithm to sub-Gaussian noise.

Fri Nov 15

Probability Seminar

2:30pm - Vincent Hall 311
Joint seminar in math biology and probability: Mathematical Modelling in Immunotherapy of Melanoma
Anna Kraut, Bonn

Mathematical models can support biomedical research through identification of key mechanisms, validation of experiments, and simulation of new therapeutic approaches.

We investigate the evolution of melanomas under adoptive cell transfer therapy with cytotoxic T-cells. It was shown in experiments that phenotypic plasticity, more precisely an inflammation-induced, reversible dedifferentiation, is an important escape mechanism for the tumor. Recently, the effects of possible mutation to a permanently resistant genotype were studied by introducing knockout melanoma cells into the wildtype tumor.

We use a stochastic individual-based Markov process to describe the evolution of the tumor under various therapeutic approaches. It is an extension of the model introduced in the paper of Baar et al in 2016 and further includes the effects of T-cell exhaustion and some limited spatial component which results in additional non-linearities. The model is implemented as a hybrid algorithm that combines Gillespie-type stochastic calculations and a deterministic approximation to speed up simulations while keeping the effects of random events.

Numerical simulations confirm the resistance to therapy via phenotypic switching as well as genotypic mutation. T-cell exhaustion is identified as an important mechanism that is crucial in fitting the model to the experimental data. We gain further insights into how originally unfit knockout cells can accumulate under therapy, shield the wild type cells from the T-cells, and thus cause an earlier relapse. Going beyond the experiment, the possibility of naturally occurring rare mutations, in contrast to artificially introduced knockout cells, is explored in simulations and produces the same effects. Thus, the clinical relevance of the experimental findings can be confirmed.

Fri Nov 22

Probability Seminar

2:30pm - Vincent Hall 311
Spherical spin glass models
Eliran Subag, New York University

How many critical points does a smooth random function on a high-dimensional space typically have at a given height? how are their distances distributed? what is the volume or geometry of the level sets? can we design efficient optimization algorithms for the random function? For the spherical spin glass models, those questions are closely related to the structure of the Gibbs measures, which have been extensively studied in physics since the 70s.

I will start with an overview of the celebrated Parisi formula and ultrametricity property. I will then describe an alternative method to analyze the Gibbs measure using critical points, in the setting of the pure spherical models. Finally, I will explain how the latter can be extended to all spherical models, using another (soft) geometric approach, while at the same time making rigorous and generalizing the famous Thouless-Anderson-Palmer approach from physics.

Fri Dec 06

Probability Seminar

2:30pm - Vincent Hall 311
Gibbsian line ensembles and log-gamma polymers
Xuan Wu, Columbia University

In this talk we will first give an overview of the known
Gibbsian line ensembles in the KPZ universality class. Then we will
construct the discrete log-gamma line ensemble, which is associated
with the log-gamma polymers. This log-gamma line ensemble enjoys a
random walk Gibbs resampling invariance that follows from the
integrable nature of the log-gamma gamma polymer model via the
geometric RSK correspondence. By exploiting such resampling
invariance, we show the tightness of this log-gamma line ensemble
under the weak noise scaling. Furthermore, a Gibbs property, as
enjoyed by the KPZ line ensemble, holds for all subsequential limits.

Fri Jan 31

Probability Seminar

2:30pm - Vincent Hall 213
Near-critical avalanches in 2D frozen percolation and forest fires
Wai-Kit Lam, UMN

We consider (volume-)frozen percolation on the triangular lattice. The model can be described informally as follows. Fix a large integer $N$. Initially, all vertices are vacant. We let clusters grow (vertices become occupied) as long as their volume is strictly smaller than $N$, and they stop growing (they "freeze") when their volume becomes at least $N$. A vertex $v$ is frozen if it belongs to an occupied cluster with volume at least $N$.

In this model, there exists a sequence of "exceptional scales" $(m_k(N))$: roughly speaking, if we consider frozen percolation in a box of side length $m_k(N)$, then as $N\to\infty$, the probability that $0$ is frozen in the final configuration is bounded away from $0$; while if we consider the process in a box of side length that is far from $m_k(N)$ and $m_{k+1}(N)$ (but between them), then as $N\to\infty$, the corresponding probability will go to $0$. The limiting exception scale, $m_\infty(N)$, is not studied and almost nothing is known. In an ongoing project with Pierre Nolin, we show that if we consider the process in a box of side length $m_\infty(N)$, then there are "avalanches" of freezings: the number of frozen circuits surrounding the origin divided by $\log\log{N}$ converges to an explicit constant in probability. If time allows, I will also talk about the analogous result in the forest fire process.

Fri Feb 14

Probability Seminar

2:30pm - Vincent Hall 213
Order of Fluctuations of the Sherrington-Kirkpatrick Model at Critical Temperature
Wei-Kuo Chen, UMN

I will discuss the order of fluctuations in the Sherrington-Kirkpatrick mean field spin glass model. In particular, I will focus on the predictions concerning the free energy and present an elementary approach for obtaining a logarithmic bound on its variance at the critical temperature.

Fri Feb 21

Probability Seminar

2:30pm - Vincent Hall 213
Robust Representation for Graph Data
Dongmian Zou, UMN

Modern data are usually high-dimensional with noise and corruption. A useful representation of data has to be robust and address the data structure. In this talk, I will first present a class of robust models called the scattering transform that can be used to generated features from graph data. In graph scattering transforms, the representation is generated in an unsupervised manner based on graph wavelets. It is approximately invariant to permutations and stable to signal or graph manipulations. Numerical results show that it works effectively for classification and community detection problems. Next, I will address how the structure of data can be found using autoencoders. Indeed, in the framework of autoencoders, graph scattering transform can be applied to the important task of graph generation. Specifically, I will illustrate its application in generating molecular samples.

Fri Feb 28

Probability Seminar

2:30pm - Vincent Hall 213
Complexity of high dimensional Gaussian random fields with isotropic increments
Qiang Zeng, CUNY

The number of critical points (on the exponential scale) of a random function is a basic question and is commonly called complexity. The notion of locally isotropic random fields (a.k.a. random fields with isotropic increments) was introduced by Kolmogorov in the 1940s. Gaussian random fields on N-dimensional Euclidean spaces with isotropic increments were classified as isotropic case and non-isotropic case by Yaglom in the 1950s. In 2004, Fyodorov computed the large N limit (on the exponential scale) of expected number of critical points for isotropic Gaussian random fields. However, many natural models are not isotropic and only have isotropic increments, which creates new difficulty in understanding the complexity. In this talk, I will present some results on the large N behavior of complexity of non-isotropic Gaussian random fields with isotropic increments. Connection to random matrices will be explained. This talk is based on joint work with Antonio Auffinger (Northwestern University).

Fri Mar 06

Probability Seminar

2:30pm - Vincent Hall 213
Dynamics of Deep Neural Networks and Neural Tangent Hierarchy
Jiaoyang Huang, Institute for Advanced Study

The evolution of a deep neural network trained by the gradient descent can be described by its neural tangent kernel (NTK) as introduced by Jacot et al., where it was proven that in the infinite width limit the NTK converges to an explicit limiting kernel and it stays constant during training. The NTK was also implicit in many other recent papers. In the overparametrization regime, a fully-trained deep neural network is indeed equivalent to the kernel regression predictor using the limiting NTK. And the gradient descent achieves zero training loss for a deep overparameterized neural network. However, it was observed by Arora et al. that there is a performance gap between the kernel regression using the limiting NTK and the deep neural networks. This performance gap is likely to originate from the change of the NTK along training due to the finite width effect.  The change of the NTK along the training is central to describe the generalization features of deep neural networks.In the work, we study the dynamic of the NTK for finite width deep fully-connected neural networks. We derive an infinite hierarchy of ordinary differential equations, the neural tangent hierarchy (NTH) which captures the gradient descent dynamic of the deep neural network. Moreover, under certain conditions on the neural network width and the data set dimension, we prove that the truncated hierarchy of NTH approximates the dynamic of the NTK up to arbitrary precision. This is a joint work with Horng-Tzer Yau.

Fri Apr 24

Probability Seminar

2:30pm - Vincent Hall 213
Probability Seminar
N. Portenko, Kiev