Seminar Schedule:
The seminar meets on Tuesdays from 4:15 to 5:15 pm EST, beginning September 12th.
Abstract: The frog model features random activation and spread. Think combustion or an epidemic. I have studied these dynamics on d-ary trees for ten years. I will discuss our progress and what remains to be done.
Abstract: To understand Deep Neural Networks (DNNs), we need to understand their implicit bias, i.e. the types of functions that they can learn efficiently. I will argue that large depth DNNs are biased towards learning functions that can be decomposed as a first function mapping from the input space to a low-dim `latent space’ and a second function mapping from this latent space to the outputs. This bias is the result of a Bottleneck structure in the learned features of the network, where the representations of `almost all’ layers of the network are approximately k-dim for some integer k. Learning such low-dim representations can also be interpreted as the network learning symmetries of the task, which could explain the success of DNNs or
image or language tasks which have a lot of symmetries. But these feature compression abilities come with dangers too, where the network can underestimate the inner dimension k, or equivalently learn spurious symmetries that are not actual symmetries of the task.
But these issues appear rare in practice, as supported by theoretical evidence.
Abstract: We propose and investigate a class of random networks where incoming vertices locally traverse the network in the direction of the root for a random number of steps before attaching to the terminal vertex. Specific instances of these networks correspond to uniform attachment, linear preferential attachment and attachment with probability proportional to vertex Page-ranks. We obtain local weak limits for such networks and use them to derive asymptotics for the limiting empirical degree and PageRank distribution. We also quantify asymptotics for the degree and PageRank of fixed vertices, including the root, and the height of the network. Two distinct regimes are seen to emerge, based on the expected exploration distance of incoming vertices, which we call the ‘fringe’ and ‘non-fringe’ regimes. These regimes are shown to exhibit different qualitative and quantitative properties. In particular, networks in the non-fringe regime undergo ‘condensation’ where the root degree grows at the same rate as the network size. Networks in the fringe regime do not exhibit condensation. A non-trivial phase transition phenomenon is also displayed for the PageRank distribution, which connects to the well-known power-law hypothesis. Joint work with Shankar Bhamidi and Xiangying (Zoe) Huang.
Abstract: We discuss a class of partially exchangeable random arrays which generalizes the notion of hierarchical exchangeability introduced in Austin and Panchenko (2014). We say that our partially exchangeable arrays are DAG-exchangeable since their partially exchangeable structure is governed by a collection of Directed Acyclic Graphs (DAG). More specifically, such a random array is indexed by N|V | for some DAG, G = (V,E), and its exchangeability structure is governed by the edge set E. We prove a representation theorem which generalizes the Aldous-Hoover and Austin–Panchenko representation theorems.
Abstract: Schamm-Loewner evolution (SLE) is a random fractal curve in the plane describing the scaling limits of many statistical physics models at criticality. It has a parameter κ measuring the “roughness” of the curve. Whole-plane SLE is reversible when κ ≤ 8, meaning invariant in law under conformal automorphisms switching its endpoints. We prove that it is reversible even when κ > 8, a property which fails for the chordal variant of SLE, and is hard to conjecture from standard methods of studying SLE. Our argument depends on a novel coupling of Liouville quantum gravity with an independent whole-plane SLE, which is a variant of the mating-of-trees of Duplantier-Miller-Sheffield.
Title: A journey through greediness and dependencesAbstract: This talk is really three talks. In the first part, our main focus is an algorithm used to approximately solve an optimal transport problem that often arises in economic applications: how do we minimise the cost of producers and consumers, when the cost is a concave function of the distance? In the second part, we analyze how feedback can be used to improve the perfromance of certain card guessing games, closely related to well-known statistical problems such as bias-detection in clinical trials and hypothesis testing. In the third part, motivated by a novel notion of curvature on graphs, we provide some close-to-exact formula for the hitting times in Erdös-Rényi random graphs. These stories are held together by a common theme: sometimes, greediness and dependencies are not that harmful. This is based on joint works with J. He, S. Steinerberger and R. Tripathi.
Abstract: Let n be a random integer chosen uniformly from 1 to x. Billingsley proved that the largest prime factors of n, properly rescaled, converge to a Poisson-Dirichlet distribution as x grows. I hope to survey this and some related results, and outline a newer proof of it due to Arratia, Kochman, and Miller which depends on introducing the computation of correlation functions. I will also discuss some applications of this perspective to prime factors of other important arithmetic sequences. (No knowledge of number theory will be assumed.) This is joint work with Abhishek Bharadwaj.
Abstract: In this talk I will introduce some discrete versions of the classical 2M-X theorem of Pitman (on the maxima of Brownian motion) and explain their connections with certain (stochastic) integrable systems.
Abstract: We will discuss the offline change-point detection and localization problem in the context of piece-wise stationary inhomogeneous Erdos-Renyi (ER) random graphs, where the observable is a finite sequence of inhomogeneous ER random graphs. We will discuss the associated challenges, detectability and localizability thresholds, their relationship with the ER random graph sequence parameters, and some of the available algorithms for detecting the change points.
Abstract: The Dedekind’s Problem asks the number of monotone Boolean functions, a(n), on n variables. Equivalently, a(n) is the number of antichains in the n-dimensional Boolean lattice [2]^n. While the exact formula for the Dedekind number a(n) is still unknown, its asymptotic formula has been well-studied. Since any subsets of a middle layer of the Boolean lattice is an antichain, the logarithm of a(n) is trivially bounded below by the size of the middle layer. In the 1960’s, Kleitman proved that this trivial lower bound is optimal in the logarithmic scale, and the actual asymptotics was also proved by Korshunov in 1980’s. In this talk, we will discuss recent developments on some variants of Dedekind’s Problem. Based on joint work with Matthew Jenssen and Alex Malekshahian.
This entry is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International license.
