I am co-organizing a virtual Probability Seminar with Antonio Auffinger (Northwestern),
Wei-Kuo Chen (University of Minnesota), and Arnab Sen (University of Minnesota) for
the Spring 2022 semester.
The webpage of the seminar schedules for Fall 2021 is here.
The seminar is held on Fridays at 12pm (ET), unless otherwise noted below.
| 01/28/2022 | Jiaming Xu (Fuqua School of Business, Duke) |
| Title: The planted matching problem: Sharp threshold and infinite-order phase transition. | |
| Abstract: Motivated by applications such as particle tracking, we study the planted matching problem, where the goal is to reconstruct a perfect matching planted in a randomly weighted bipartite graph, whose planted and unplanted edge weights are independently drawn from two different distributions. We determine the sharp threshold at which the optimal reconstruction error (fraction of misclassified edges) exhibits a phase transition from non-zero to zero. Furthermore, in the special case of exponential weight distributions, this phase transition is shown to be of infinite order and we further determine
the reconstruction error of the maximum likelihood estimation in terms of a system of differential equations that result from a message-passing algorithm. The talk is based on joint work with Jian Ding (Penn and PKU), Yihong Wu (Yale), Dana Yang (Cornell), Mehrdad Moharrami (UIUC), and Cristopher Moore (SFI). Preprints are available at arXiv:2103.09383 and arXiv:1912.08880. | |
| 02/04/2022 | Shuangping Li (PACM, Princeton) |
| Title: On the binary perceptron. | |
| Abstract: We consider the binary perceptron model, a simple model of neural networks that has gathered significant attention in the statistical physics, information theory and probability theory communities. For the symmetric binary perceptron model, we establish that the partition function of this model, normalized by its expected value, converges to a lognormal distribution. As a consequence, this allows us to establish several conjectures for this model, including contiguity, sharp threshold and strong freezing conjectures. The strong freezing property further points to an interesting phenomenon that is not present in sparse constraint satisfaction problems: on the one hand, the perceptron model is conjectured to be typically hard; on the other hand, efficient algorithms have been shown empirically to succeed in finding solutions, suggesting that such algorithms find atypical solutions. We establish formally such a phenomenon for both the symmetric and asymmetric binary perceptrons. We show that at low constraint density , there exists a subdominant connected cluster of solutions with almost maximal diameter, and that an efficient multiscale majority algorithm can find solutions in such a cluster with high probability. This is based on joint works with Emmanuel Abbe and Allan Sly. |
|
| 02/11/2022 | Dan Mikulincer (Mathematics, MIT) |
| Title: Dimension-free variance bounds for polynomials. | |
| Abstract: In an attempt to understand the covariance structure of high-dimensional random tensor powers, we study the variance of the pushforward of random vectors by homogeneous polynomials.
For applications, it is often necessary to bound the variance from below in a dimension-free fashion. This talk will explore the availability of such bounds for different measures. In particular, we will show that the desired property holds generically for product measures.
We will also discuss some connections to small ball estimates and decay of Fourier coefficients; the latter is related to a question posed by Carbery and Wright. Based on a joint work with Itay Glazer (Northwestern). |
|
| 02/18/2022 | Jack Hanson (Mathematics, CUNY) |
| Title: Spanning clusters and subcritical connectivity in high-dimensional percolation. | |
| Abstract: In their study of percolation, physicists have proposed "scaling hypotheses" relating the behavior of the model in the critical (p = pc) and subcritical (p <pc) regimes. We show a version of such a scaling hypothesis for the one-arm probability π(n;p) -- the probability that the open cluster of the origin has Euclidean diameter at least n. As a consequence of our analysis, we obtain the correct scaling of the lower tail of cluster volumes and the chemical (intrinsic) distances within clusters. We also show that the number of spanning clusters of a side-length n box is tight on scale nd-6. A new tool of our analysis is a sharp asymptotic for connectivity probabilities when paths are restricted to lie in half-spaces. |
|
| 02/25/2022 | Marcus Michelen (Mathematics, UIC) |
| Title: How often is a random symmetric matrix singular? | |
| Abstract: Consider the random n x n matrix whose entries on and above the diagonal are independent and uniformly chosen from {-1,1}. How often is this matrix singular? A moment's thought reveals that if two rows or columns are equal then the matrix is singular, so the singularity probability is bounded below by 2-n(1 + o(1)). Proving any sort of upper bound on the singularity probability turns out to be difficult, with results coming slowly over the past two decades. I'll discuss a recent work which shows the first exponential upper bound on this probability. Along the way, I'll discuss some tools---both old and new---which are powerful and (hopefully) interesting in their own right. This talk is based on joint work with Marcelo Campos, Matthew Jenssen, and Julian Sahasrabudhe. | |
| 03/04/2022 | Tselil Schramm (Statistics, Stanford) |
| Title: Testing thresholds for sparse random geometric graphs. | |
| Abstract: We study random geometric graphs on the unit sphere in the high-dimensional setting, where the dimension grows to infinity with the number of vertices. Our central question is: given such a graph, when is it possible to identify the underlying geometry? As the dimension grows relative to the number of vertices, the edges in the graph become increasingly independent, and the underlying geometry becomes less apparent. In this talk I will present recent progress on this question: we show that in sparse geometric random graphs, if the dimension is at least polylogarithmic in the number of vertices, then the graphs are statistically indistinguishable from Erdos-Renyi graphs, and the underlying geometry disappears. Based on joint work with Siqi Liu, Sidhanth Mohanty, and Elizabeth Yang. |
|
| 03/11/2022 | Lutz Warnke (Mathematics, UCSD) |
| Title: Does the degree-restricted random graph process have uniform distribution? | |
| Abstract: The random d-process corresponds to a natural algorithmic model for generating d-regular graphs: starting with an empty graph on n vertices, it evolves by sequentially adding new random edges so that the maximum degree remains at most d. In 1999 Wormald conjectured that the final graph of the random d-process is "similar" to a uniform random d-regular graph. We show that this conjecture does not extend to a natural generalization of this process with mixed degree restrictions, i.e., where each vertex has its own degree restriction (under some mild technical assumptions). Our proof uses the method of switchings, which is usually only applied to uniform random graph models -- rather than to stochastic processes. Based on joint work in progress with Mike Molloy and Erlang Surya. | |
| 03/18/2022 | No seminar. Instead, SSP 2022 at Lehigh! |
| 03/25/2022 | Jacob Shapiro (Physics, Princeton) |
| Title: Delocalization in the integer-valued Gaussian Field and the Berezinskii-Kosterlitz-Thouless phase of the 2D Villain model. | |
| Abstract: Delocalization in the integer-valued Gaussian field (ZGF) formulated over a two dimensional periodic lattice is shown to imply slow (power law) decay of correlations in the corresponding dual two-component spin model of an O(2) invariant spin-spin interaction. The link proceeds through a lower bound on the spin-spin correlation in terms of the probability that two sites are linked by a common level loop of the ZGF. Motivated by this observation, we extend the recent proof by Lammers of a delocalization transition in two dimensional graphs of degree three, to all doubly periodic graphs, in particular to Z^2. The extension is established through a monotonicity argument for which we employ new Gaussian lattice inequalities of Regev and Stephens-Davidowitz. These statements allow a new perspective on the BKT phase transition in O(2)-invariant models and a new proof of delocalization in two-dimensional integer-valued height functions. | |
| 04/01/2022 | Firas Rassoul-Agha (Math, Utah) |
| Title: One force--one solution and semi-infinite polymers for KPZ on the line. | |
| Abstract: In this talk, I will present recent results on the uniqueness, ergodicity, and attractiveness of stationary solutions to the Kardar-Parisi-Zhang (KPZ) equation on the real line. It is known that this equation admits Brownian motion with a linear drift as a stationary solution. We show that these solutions are attractive, a principle known as one force--one solution (1F1S): the solution to the KPZ equation started in the distant past from an initial condition with a given velocity will converge almost surely to a Brownian motion with that same drift. As a result, we deduce that these stationary measures are ergodic and that there are no other ergodic measures. Furthermore, we can couple all these stationary solutions so that the above attractiveness holds simultaneously (i.e. on a single full measure event) for all but countably many (random) asymptotic velocities. I will also discuss how these ideas connect to the continuum directed polymer and in particular to semi-infinite continuum polymer measures, as well as the structure of the random set of exceptional velocities on which 1F1S fails. This is joint work with Tom Alberts, Chris Janjigian, and Timo Seppalainen. | |
| 04/08/2022 | Sky Cao (Statistics, Stanford) |
| Title: A state space for the 3D Yang-Mills measure. | |
| Abstract: In this talk, I will describe some progress towards the construction of the 3D Yang-Mills (YM) measure. In particular, I will introduce a state space of "distributional gauge orbits" which may possibly support the 3D YM measure. Then, I will describe a result which says that assuming that 3D YM theories exhibit short distance behavior similar to the 3D Gaussian free field (which is the expected behavior), then the 3D YM measure may be constructed as a probability measure on the state space. This is based on joint work with Sourav Chatterjee. | |
| 04/15/2022 | Yin-Ting Liao (Applied Math, Brown) |
| Title: Large deviations for projections of high-dimensional measures. | |
| Abstract: Random projections of high-dimensional probability measures have gained much attention in asymptotic convex geometry and high-dimensional statistics. While fluctuations at the level of the central limit theorem have been classically studied, only more recently has an inquiry into large deviation principles for such projections been initiated. In this talk, I will review existing work and describe our results on large deviations. I will also talk about sharp large deviation estimates to obtain the prefactor apart from the exponential decay in the spirit of Bahadur and Ranga-Rao. Applications to asymptotic convex geometry and a range of examples including l p balls and Orlicz balls would be given. This talk is based on several joint works with S. S. Kim and K. Ramanan. | |
| 04/22/2022 | Jessica Lin (Math & Stat, McGill) |
| Title: Symmetric Cooperative Motion. | |
| Abstract: We explore the relationship between recursive distributional equations and convergence results for finite difference schemes of parabolic partial differential equations (PDEs). We focus on a family of random processes called symmetric cooperative motions, which generalize the symmetric simple random walk and the symmetric hipster random walk studied by Addario-Berry et al [Probability Theory and Related Fields, '20]. We obtain a distributional convergence result for symmetric cooperative motions and, along the way, obtain a novel proof of the Bernoulli central limit theorem. This talk is based on joint work with Louigi Addario-Berry and Erin Beckman. | |
| 04/29/2022 | Nick Cook (Math, Duke) |
| Title: The typical structure of sparse exponential random graphs. | |
| Abstract: Exponential random graph models (ERGMs) are parametric families of distributions on graphs that are widely applied in the social sciences. They can be viewed as tilts of the Erdös Rényi model by a Gibbs weight that depends on counts of small subgraphs such as triangles. The appeal of ERGMs is that the subgraph counts are sufficient statistics for estimation of the associated parameters. However, sampling from these distributions is challenging in many parameter regimes; in some other regimes, typical samples are indistinguishable from the Erdös Rényi model, or may even "degenerate" to an almost-empty or almost-full graph. Following an idea of Lubetzky and Zhao for the dense case, we show how to cure the degeneracy phenomenon for sparse ERGMs. We further use recent advances in nonlinear large deviations theory for random hypergraphs to establish the typical macroscopic structure of sparse ERGMs in the ferromagnetic parameter regime. Based on joint works with Amir Dembo and Huy Tuan Pham. | |
| 05/06/2022 | Cynthia Rush (Statistics, Columbia) |
| Title: Characterizing the Type 1-Type 2 Error Trade-off for SLOPE. | |
| Abstract: Sorted L1 regularization has been incorporated into many methods for solving high-dimensional statistical estimation problems, including the SLOPE estimator in linear regression. In this talk, we study how this relatively new regularization technique improves variable selection by characterizing the optimal SLOPE trade-off between the false discovery proportion (FDP) and true positive proportion (TPP) or, equivalently, between measures of type I and type II error. Additionally, we show that on any problem instance, SLOPE with a certain regularization sequence outperforms the Lasso, in the sense of having a smaller FDP, larger TPP and smaller L2 estimation risk simultaneously. Our proofs are based on a novel technique that reduces a variational calculus problem to a class of infinite-dimensional convex optimization problems and a very recent result from approximate message passing (AMP) theory. With SLOPE being a particular example, we discuss these results in the context of a general program for systematically deriving exact expressions for the asymptotic risk of estimators that are solutions to a broad class of convex optimization problems via AMP. Collaborators on this work include Zhiqi Bu, Jason Klusowski, and Weijie Su (arXiv:1907.07502 and arXiv:2105:13302) and Oliver Feng, Ramji Venkataramanan, and Richard Samworth (arXiv:2105.02180). | |