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 Spring 2022 is here.
The seminar is held on Wednesdays at 6:30pm (ET), unless otherwise noted below.
| 09/15/2021 | Song Mei (Statistics, UC Berkeley) Special Time: 5-6pm, EDT |
| Title: Local convexity of the TAP free energy and AMP convergence for Z2-synchronization. | |
| Abstract: We study mean-field variational Bayesian inference using the TAP approach, for Z2-synchronization as a prototypical example of a high-dimensional Bayesian model. We show that for any signal strength lambda > 1 (the weak-recovery threshold), there exists a unique local minimizer of the TAP free energy functional near the mean of the Bayes posterior law. Furthermore, the TAP free energy in a local neighborhood of this minimizer is strongly convex. Consequently, a natural-gradient/mirror-descent algorithm achieves linear convergence to this minimizer from a local initialization, which may be obtained by a finite number of iterates of Approximate Message Passing (AMP). This provides a rigorous foundation for variational inference in high dimensions via minimization of the TAP free energy. We also analyze the finite-sample convergence of AMP, showing that AMP is asymptotically stable at the TAP minimizer for any lambda > 1, and is linearly convergent to this minimizer from a spectral initialization for sufficiently large lambda. Such a guarantee is stronger than results obtainable by state evolution analyses, which only describe a fixed number of AMP iterations in the infinite-sample limit. | |
| 09/22/2021 | Erin Beckman (Mathematics and Statistics, Concordia) Special Time: 5-6pm, EDT |
| Title: Cooperative motion random walks. | |
| Abstract: Cooperative motion random walks form a family of random walks where each step is dependent upon the distribution of the walk itself. Movement is promoted at locations of high probability and dampened in locations of low probability. These processes are a generalization of the hipster random walk introduced by Addario-Berry et. al. in 2020. We study the process through a recursive equation satisfied by its CDF, allowing the evolution of the walk to be related to a finite difference scheme. I will discuss this relationship and how PDEs can be used to describe the distributional convergence of both asymmetric and symmetric cooperative motion. This talk is based on joint work with Louigi Addario-Berry and Jessica Lin. | |
| 09/29/2021 | Debapratim Banerjee (ICTS, Bengaluru) Special Time: 10-11am EDT |
| Title: The method of dense subgraph conditioning and its applications. | |
| Abstract: In this talk we shall introduce a method called the method of dense subgraph conditioning. Similar methods for sparse graphs have been used in determining the asymptotic distribution of the log likelihood ratio of two processes on the graphs. One might look at the works of Janson, Wormald and more recently Mossel et al (citations will be given in course of the talk). The main novelty of our work is to apply this method in dense settings. Although the intuition behind why this method works is not fully concrete, the proofs are rigorous. Our method can be applied to scenarios when certain quantities of interest have a representation as the likelihood ratio of two processes. This includes several models like the free energy of the mixed p-spin SK models, the likelihood ratio of the stochastic block model to the Erdos-Renyi models, SK model with Curie-Weiss interaction, likelihood ratio of spiked rectangular model to pure noise Gaussian model etc. By our method we can prove the asymptotic normality of the likelihood ratios or the free energies in high temperature regime i.e. when signal to noise ratio is small. In this talk we shall mainly focus on the free energy of the mixed p-spin SK models. Apart from the main steps of the proof, I shall also try to give the intuition why this method works. When this method works the free energy can also be approximated by a linear spectral statistics of the interaction matrix which is computable in polynomial time. If time permits I shall also discuss some results in this direction and some ongoing works.. | |
| 10/06/2021 | Rishabh Dudeja (Statistics, Harvard) |
| Title: Computational Lower Bounds for Tensor PCA. | |
| Abstract: Tensor Principal Components Analysis (Tensor PCA) is a stylized statistical inference problem introduced by Montanari and Richard in 2014 for studying method-of-moments approaches to parameter estimation in latent variable models. Unlike the matrix counterpart of the problem, Tensor PCA exhibits a computational-statistical gap in the sample-size regime where the problem is information-theoretically solvable, but no computationally efficient algorithm is known. In this talk, I will describe unconditional computational lower bounds on the run-time of iterative algorithms for Tensor PCA that maintain an internal memory state of a fixed size and update this memory state as they iterate through the dataset several times. The lower bounds specify a trade-off between the number of passes (run-time), sample size, and the memory required by any iterative algorithm that successfully solves Tensor PCA. Since the lower bounds are unconditional, they do not rule out polynomial-time estimators in the conjectured hard-phase of these problems. However, these results show that many commonly used algorithms like gradient descent and power method must have a slower run-time in the conjectured hard regime. This talk is based on joint work with Prof. Daniel Hsu (Columbia University). | |
| 10/20/2021 | Alex Wein (Simons Institute, UC Berkeley) |
| Title: Low-Degree Hardness of Random Optimization Problems. | |
| Abstract: I will consider random optimization problems, including the problem of finding a large independent set in a random graph, and the problem of optimizing the Hamiltonian of mean-field spin glass models. These problems often have a gap between the globally-optimal objective value and the objective value achievable by any known polynomial-time algorithm. To provide concrete evidence that this computational hardness is inherent, we prove that the class of "low-degree polynomial algorithms" fails to surpass a particular objective value. This class of algorithms is quite powerful in that it captures many of the best known algorithms for these types of problems, including approximate message passing and local algorithms (factor of i.i.d.). The proof involves a variant of the so-called "overlap gap property," which is a structural property of the solution space. Using similar techniques, we can also prove lower bounds against low-depth Boolean circuits. Based on a series of works, some joint with David Gamarnik and Aukosh Jagannath: https://arxiv.org/abs/2004.12063, https://arxiv.org/abs/2010.06563, https://arxiv.org/abs/2109.01342. | |
| 10/27/2021 | Ahmed Bou-Rabee (Statistics, UChicago) |
| Title: Scaling limits of sandpiles. | |
| Abstract: The Abelian sandpile is a deterministic diffusion process on the integer lattice which produces striking, kaleidoscopic patterns. I will discuss recent progress towards understanding these patterns and their stability under randomness. | |
| 11/03/2021 | Adriano Barra (Mathematical Physics, Università del Salento) Special Time: 10-11am EDT |
| Title: Information processing in symmetric shallow networks. | |
| Abstract: In this talk I will summarize a toy scenario in Theoretical Artificial Intelligence where a neural network is able to learn and retrieve random patterns (namely archetypes of the examples provided in the datasets) in order to deepen similarities between artificial information processing and biological information processing. This minimal scenario will be then enlarged toward increased biological resemblance by accounting for parallel processing and tunable signal-to-noise threshold extensions (and eventually by allowing the network to "take a nap"). Methodologically based on the statistical mechanics of spin glasses, I will provide mainly heuristic arguments achieved via replica-trick and similar tools (and a few rigorous results achieved via generalizations of Guerra's interpolation technique), trying to highlight the rewards -and the flaws- in this physically-driven approach to Theoretical Artificial Intelligence. | |
| 11/10/2021 | Jiaming Xia (Mathematics, UPenn) |
| Title: Hamilton-Jacobi equations for statistical inference problems. | |
| Abstract: In this talk, I will first present the high-dimensional limit of the free energy associated with the inference problem of finite-rank matrix tensor products. We compare the limit with the solution to a certain Hamilton-Jacobi equation, following the recent approach by Jean-Christophe Mourrat. The motivation comes from the averaged free energy solving an approximate Hamilton-Jacobi equation. We consider two notions of solutions which are weak solutions and viscosity solutions. The two types of solutions require different treatments and each has its own advantages. At the end of this part, I will show an example of application of our results to a model with i.i.d. entries and symmetric interactions. If time permits, I will talk about the same problem but with a different model, namely, the multi-layer generalized linear model. I will mainly explain the iteration method as an important tool used in our proof. This is based on joint works with Hong-Bin Chen and J.-C. Mourrat, NYU. | |
| 11/17/2021 | Tianyi Zheng (Mathematics, UCSD) |
| Title: Random walks on lamplighters and related groups. | |
| Abstract: Random walks on lamplighter groups were first considered by Kaimanovich and Vershik to provide examples of amenable groups with nontrivial Poisson boundary. Such processes can be understood rather explicitly, and provide guidance in the study of random walks on more complicated groups. We will discuss a law of large numbers for random walks on the two-dimensional lamplighter group, and various questions regarding limiting behavior of random walks and the geometry of groups. Joint work with Anna Erschler. | |