On transport methods for simulation-based inference and data assimilation
Abstract
Many practical Bayesian inference problems fall into the simulation-based or "likelihood-free" setting, where evaluations of the likelihood function or prior density are unavailable or intractable; instead one can only draw samples from the joint parameter-data prior. Learning conditional distributions is essential to the solution of these problems.
To this end, I will discuss a powerful class of methods for conditional density estimation and conditional simulation based on transportation of measure. An important application for these methods lies in data assimilation for dynamical systems, where transport enables new approaches to nonlinear filtering and smoothing.
To illuminate some of the theoretical underpinnings of these methods, I will discuss recent work on monotone map representations, optimization guarantees for learning maps from data, and the statistical convergence of transport-based density estimators.
The Metropolis Algorithm for the Planted Clique Problem
Part of the Oxford Discrete Maths and Probability Seminar, held via Zoom. Please see the seminar website for details.
Abstract
More than 30 year ago Jerrum studied the planted clique problem and proved that under worst-case initialization Metropolis fails to recover planted cliques of size $\ll n^{1/2}$ in the Erdős-Rényi graph $G(n,1/2)$. This result is classically cited in the literature of the problem, as the "first evidence" that finding planted cliques of size much smaller than square root $n$ is "algorithmically hard". Cliques of size $\gg n^{1/2}$ are easy to find using simple algorithms. In a recent work we show that the Metropolis process actually fails to find planted cliques under worst-case initialization for cliques up to size almost linear in $n$. Thus the algorithm fails well beyond the $\sqrt{n}$ "conjectured algorithmic threshold". We also prove that, for a large parameter regime, that the Metropolis process fails also under "natural initialization". Our results resolve some open questions posed by Jerrum in 1992. Based on joint work with Zongchen Chen and Iias Zadik.
Fourier transform as a triangular matrix
Abstract
Let $V$ be a finite dimensional vector space over the field with two elements with a given nondegenerate symplectic form. Let $[V]$ be the vector space of complex valued functions on $V$ and let $[V]_{\mathbb Z}$ be the subgroup of $[V]$ consisting of integer valued functions. We show that there exists a Z-basis of $[V]_{\mathbb Z}$ consisting of characteristic functions of certain explicit isotropic subspaces of $V$ such that the matrix of the Fourier transform from $[V]$ to $[V]$ with respect to this basis is triangular. This continues the tradition started by Hermite who described eigenvectors for the Fourier transform over real numbers.
14:00
Local Langlands correspondence and (stable) Bernstein center
Abstract
We discuss the Local Langlands correspondence in connection with the Bernstein center and the Stable Bernstein center. We also give an example of stable Bernstein center as a stable essentially compact invariant distribution.
Threshold for Steiner triple systems
Part of the Oxford Discrete Maths and Probability Seminar, held via Zoom. Please see the seminar website for details.
Abstract
We prove that with high probability $\mathbb{G}^{(3)}(n,n^{-1+o(1)})$ contains a spanning Steiner triple system for $n\equiv 1,3\pmod{6}$, establishing the exponent for the threshold probability for existence of a Steiner triple system. We also prove the analogous theorem for Latin squares. Our result follows from a novel bootstrapping scheme that utilizes iterative absorption as well as the connection between thresholds and fractional expectation-thresholds established by Frankston, Kahn, Narayanan, and Park.
This is joint work with Ashwin Sah and Michael Simkin.
Non-branching in RCD(K,N) Spaces
Abstract
On a smooth Riemannian manifold, the uniqueness of a geodesic given initial conditions follows from standard ODE theory. This is known to fail in the setting of RCD(K,N) spaces (metric measure spaces satisfying a synthetic notion of Ricci curvature bounded below) through an example of Cheeger-Colding. Strengthening the assumption a little, one may ask if two geodesics which agree for a definite amount of time must continue on the same trajectory. In this talk, I will show that this is true for RCD(K,N) spaces. In doing so, I will generalize a well-known result of Colding-Naber concerning the Hölder continuity of small balls along geodesics to this setting.
14:00
Braids, Unipotent Representations, and Nonabelian Hodge Theory
Abstract
A complex plane curve singularity gives rise to two objects: (1) a moduli space that representation theorists call an affine Springer fiber, and (2) a topological link up to isotopy. Roughly a decade ago, Oblomkov–Rasmussen–Shende conjectured a striking identity relating the homology of the affine Springer fiber to the so-called HOMFLYPT homology of the link. In unpublished writing, Shende speculated that it would follow from advances in nonabelian Hodge theory: the study of transcendental diffeomorphisms relating “Hitchin” and “Betti” moduli spaces. We make this dream precise by expressing HOMFLYPT homology in terms of the homology of a “Betti”-type space, which, we conjecture, deformation-retracts onto the affine Springer fiber. In doing so, we recast the whole story in terms of an arbitrary semisimple group. We give evidence for the nonabelian Hodge conjecture at the numerical level, using a mysterious formula that involves rational Cherednik algebras and the degrees of unipotent principal-series representations.
14:00
Friendly bisections of random graphs
Part of the Oxford Discrete Maths and Probability Seminar, held via Zoom. Please see the seminar website for details. Joint with the Random Matrix Theory Seminar.
Abstract
We introduce a new method for studying stochastic processes in random graphs controlled by degree information, involving combining enumeration techniques with an abstract second moment argument. We use it to constructively resolve a conjecture of Füredi from 1988: with high probability, the random graph G(n,1/2) admits a friendly bisection of its vertex set, i.e., a partition of its vertex set into two parts whose sizes differ by at most one in which n-o(n) vertices have at least as many neighbours in their own part as across. This work is joint with Asaf Ferber, Matthew Kwan, Bhargav Narayanan, and Mehtaab Sawhney.