Program

This is a joint work with Reza Gheissari (Northwestern) and Aukosh Jagannath (Waterloo), to appear in NeurIPS 2022 (arXiv:2206.04030).
We study the scaling limits of stochastic gradient descent (SGD) with constant step-size in the high-dimensional regime. We prove limit theorems for the trajectories of summary statistics (i.e., finite-dimensional functions) of SGD as the dimension goes to infinity. Our approach allows one to choose the summary statistics that are tracked, the initialization, and the step-size. It yields both ballistic (ODE) and diffusive (SDE) limits, with the limit depending dramatically on the former choices. Interestingly, we find a critical scaling regime for the step-size below which the effective ballistic dynamics matches gradient flow for the population loss, but at which, a new correction term appears which changes the phase diagram. About the fixed points of this effective dynamics, the corresponding diffusive limits can be quite complex and even degenerate. We demonstrate our approach on popular examples including estimation for spiked matrix and tensor models and classification via two-layer networks for binary and XOR-type Gaussian mixture models. These examples exhibit surprising phenomena including multimodal timescales to convergence as well as convergence to sub-optimal solutions with probability bounded away from zero from random (e.g., Gaussian) initializations.

The measure $P^{\alpha, T}$ is defined relative increments of the three dimensional Brownian motion $$ dP^{\alpha, T}\over dP}={1\over Z(\alpha, T)}\exp[\alpha\int\int_{-T\le s\le t\le T} {e^{-|t-s|}\over |x(t)-x(s)|}dtds] $$. The problem is to study the behavior of the limit as $T\to\infty$ followed by $\alpha\to\infty$ of $P^{\alpha, T}$.

I will describe the effect of boundary conditions on the behavior of KPZ class models, mainly in terms of their invariant measures which remarkably relate to versions of 1d Liouville quantum gravity. This is based on joint works with Hao Shen, Alisa Knizel and Guillaume Barraquand.

Classic results in percolation theory show that below the critical probability, the probability that the cluster of the origin has size n decays exponentially in n, while above the critical probability, the probability that the cluster of the origin has size n and is finite decays exponentially. The constant in the exponential is known as the correlation length and depends on p, going to infinity as p approaches the critical probability.

We consider biased random walk on dynamical percolation and discuss the existence and the properties of the linear speed as a function of the bias. Based on joint work (in progress) with Sebastian Andres, Perla Sousi and Dominik Schmid.

For a graph H = H_n, the critical probability p_c(H) is the value of p such that an Erdos-Renyi graph G(n,p) includes a copy of H with chance 1/2. The "second Kahn-Kalai conjecture," which remains open, posits that p_c(H) is equivalent up to a logarithmic factor to a subgraph expectation threshold. We show that p_c(H) is equivalent up to a logarithmic factor to a modified subgraph expectation threshold, thus proving a weak version of the second Kahn-Kalai conjecture. This gives a simplification of the fractional Kahn-Kalai result of Frankston, Kahn, Narayanan, and Park (2019) in the special case of graph inclusion properties. The main technical ingredient is the spread lemma of Alweiss, Lovett, Wu, and Zhang (2019). Separately, we also present a new proof of the spread lemma from a Bayesian inference perspective. Joint work with Elchanan Mossel, Jonathan Niles-Weed, and Ilias Zadik.

I will discuss large deviations for the spectrum of Wigner random matrices. Based on joint works with F. Augeri, N. Cook, R. Ducatez and J. Husson.

A celebrated problem in quantum mechanics concerns the effective mass of the Frohlich polaron in the strong coupling limit. Feynman gave a path integral formulation which relates it to a three dimensional Brownian motion with an attractive pair interaction of Kac type. The effective mass can be expressed as the inverse of the variance parameter of the self-interacting Brownian. There is a long standing conjecture about the asymptotic behavior of the effective mass for which Spohn gave a heuristic argument. A key property is that the interaction is shift invariant. Despite of considerable recent progress by Mukherjee, Varadhan, Spohn, Lieb, and Seiringer, the key problem is still open. We present a much simpler model having a similar probabilistic structure which can be analyzed rigorously, and where the Spohn picture can be analyzed rigorously. No claim is made that the "true" polaron behaves in the same way. This is joint work with Amir Dembo.

In this talk, we consider homogenization problem for non-symmetric L\'evy-type processes with drifts in periodic media. Under a proper scaling, we show the scaled processes converge weakly to L\'evy processes on ${\mathbb R}^d$. In particular, we completely characterize the limiting processes when the coefficient function of the drift part is bounded continuous, and the decay rate of the jumping measure is comparable to $r^{-1-\alpha}$ for $r>1$ in the spherical coordinate with $\alpha \in (0,\infty)$. Different scaling limits appear depending on the values of $\alpha$. If time permits, we will briefly discuss our on-going work on quantitative homogenization for L\'evy-type processes in time-dependent periodic media. This talk is based on joint work with Xin Chen, Zhen-Qing Chen and Jian Wang.

We will consider a family of semi-linear parabolic equations that describe the transition from the "Branching Brownian motion Bramson shift" (3/2)log t, as in the Fisher-KPP equation, to the "Independent Gaussians" shift (1/2)log t, as for the standard heat equation, for the location of the solutions. Right at the transition the solutions have a number of interesting algebraic properties that we will describe. We will also discuss some BBM voting models related to such models.

We describe hydrodynamic limits for interacting jump processes on sparse random graphs, obtaining under suitable conditions autonomous characterizations of marginal dynamics and equilibrium behavior. This is joint work with A. Ganguly.

Consider two copies of the same G(n,p) graph and erase independently the edges of each copy with probability t<p. This procedure creates two correlated random graphs. We discuss a randomized algorithm recovering the matching between the vertices of the two graphs for a certain range of parameters.

Random matrix theory (RMT) has become a widely used tool in high-dimensional statistics and theoretical machine learning. I will survey some random matrix models and questions that have emerged in these application areas, insights that have been developed, and open questions.

We consider the open Toda chain with external forcing. We consider the case when the forcing stretches the chain, and also the case when the forcing compresses the chain. In the case that the forcing stretches the chain, we use an observation of Juergen Moser to show that the system remains completely integrable. This is joint work with Luen-Chau Li, Herbert Spohn, Carlos Tomei and Tom Trogdon.

Generalized Ray-Knight theorems for edge local times proved to be a very useful tool for studying the limiting behavior of several classes of self-interacting random walks (SIRWs). Examples include some reinforced random walks, excited random walks, rotor walks with defects. I shall describe two classes of SIRWs introduced and studied by Balint Toth (1996), asymptotically free and polynomially self-repelling SIRWs, and discuss new results (joint work with Thomas Mountford, EPFL, and Jon Peterson, Purdue University) which resolve an open question posed in Toth’s paper. We show that in the asymptotically free case the rescaled SIRWs converge to a perturbed Brownian motion (conjectured by Toth) while in the polynomially self-repelling case the convergence to the conjectured process fails in spite of the fact that generalized Ray-Knight theorems clearly identify the unique candidate in the class of all perturbed Brownian motions. This negative result was somewhat unexpected. Conjectures on whether there is a suitable limiting process in this case and, if yes, then what it might be are welcome.

I will present an overview of the theory of quantitative homogenization (stochastic as well as periodic) for elliptic and parabolic equations, which has been developed in the last ten years. A particular emphasis will be on the idea of "coarse-graining the diffusion matrix." I will begin by trying to motivate the results by discussing some recent applications to models in mathematical physics. Time permitting, I will also give some open problems.

We investigate the macroscopic behaviour of the density fluctuations of a one dimensional dynamics of hard rods with random length. After recentering on the effective velocity the density fluctuations of particles of a given velocity v will evolve on the diffusive scaling driven by a browian motion with a diffusivity depending on v. This rigid evolution of fluctuations is expected in other completely integrable systems (Box-Ball, Toda Lattice,..), in contrast with the behavior in chaotic dynamics. Joint work with Pablo Ferrari (U. Buenos Aires).

The atypical behaviour of the spectrum of Random Matrices has been posing difficult challenges to the standard theory of Large deviations for decades. Owing to the intricate relationship between the entries of a matrix and its spectrum, most of the results were known either for integrable models or Wigner matrices with heavy-tails. Regarding the edge eigenvalues a recent breakthrough was achieved by Guionnet and Husson, showing a universal large deviation behaviour for Wigner matrices with ‘’sharp sub-Gaussian tails”, and later on a partial large deviation principle for general sub-Gaussian entries. One may wonder if adding sparsity to the model could lead to a more tractable large deviations behaviour of the spectrum. In the regime where the mean degree is at least logarithmic, the edge eigenvalues of a sparse Wigner matrix sticks to the edges of the support of the semicircle law. We show that in this sparsity regime, the large deviations of the largest eigenvalue of a sparse Wigner matrix with sub-Gaussian entries are dominated by either the emergence of a high degree vertex with a high weight or that of a clique with high weights. Interestingly, the rate function obtained is discontinuous at the typical value of the largest eigenvalue, which accounts for the fact that its large deviation behaviour is generated by finite rank perturbations. This complements the results of Ganguly-Nam and Ganguly-Hiesmayr-Nam which settle the case where the mean degree is constant. This is a joint work (in progress) with Anirban Basak.

We study the two-dimensional two-component plasma or Coulomb gas with oppositely charged particles. Such a gas is expected to undergo a Kosterlitz-Thouless phase-transition. We consider a suitable truncation of the charges which allows to make sense of the Gibbs measure beyond $\beta=2$ and show a transition between a system of free charges and a system with bound dipoles, as predicted. This is based on joint work with Thomas Leblé and Ofer Zeitouni, and with Jeanne Boursier.

We consider the characteristic polynomial and the orthogonal polynomials on the unit circle associated to Dyson's Circular-beta ensemble. In the case that beta=2, this is the characteristic polynomial of a Haar distributed unitary matrix, which is the subject of the random-matrix part of the Fyodorov-Hiary-Keating conjecture. This asserts the recentered maximum of the log-modulus of the characteristic polynomial converges in distribution to a convolution of two Gumbel laws. We show the convergence in law of the recentered maximum of the log-modulus, and identify its limit as the convolution of a gumbel with the total mass of a (non-gaussian) critical multiplicative chaos. We further give a sequential description of the law of the characteristic polynomial in a neighborhood of the maximum.
Joint with Ofer Zeitouni.

Hydrodynamic limits (HDL) of particle systems with selection are related to free boundary problems (FBP) associated with parabolic equations. This relation has been established rigorously for some selection models while it remains open for others, where the difficulty lies in questions of regularity of the free boundary. We propose a weak formulation of FBP that does not involve a free boundary at all, but is based instead on parabolic equations with measure-valued right-hand side. The approach allows us to avoid regularity questions and characterize limits in terms of the weak formulation in cases where classical solutions to the FBP are expected to but not known to exist, as well as in cases where they are not expected to exist. Unlike in most earlier work on particle systems with selection, the PDE serves as a tool for establishing HDL.

I will talk about new results on the number of zeros of a system of random polynomial equations in the limit of large number of equations and variables.

Consider the time C(r) it takes a Brownian motion to come within distance r of every point in the two-dimensional torus of area one. I will discuss the key ideas in a joint work with Jay Rosen and Ofer Zeitouni, showing that as r goes to zero, the square-root of C(r), minus an explicit non-random centering m(r), converges in distribution to a randomly shifted Gumbel law.