Seminars and Colloquia by Series

Variational Analysis of Empirical Risk Minimization

Series
Stochastics Seminar
Time
Thursday, August 30, 2018 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Andrew Nobel – University of North Carolina, Chapel Hill
This talk concerns the description and analysis of a variational framework for empirical risk minimization. In its most general form the framework concerns a two-stage estimation procedure in which (i) the trajectory of an observed (but unknown) dynamical system is fit to a trajectory from a known reference dynamical system by minimizing average per-state loss, and (ii) a parameter estimate is obtained from the initial state of the best fit reference trajectory. I will show that the empirical risk of the best fit trajectory converges almost surely to a constant that can be expressed in variational form as the minimal expected loss over dynamically invariant couplings (joinings) of the observed and reference systems. Moreover, the family of joinings minimizing the expected loss fully characterizes the asymptotic behavior of the estimated parameters. I will illustrate the breadth of the variational framework through applications to the well-studied problems of maximum likelihood estimation and non-linear regression, as well as the analysis of system identification from quantized trajectories subject to noise, a problem in which the models themselves exhibit dynamical behavior across time.

Asymptotics in random balls models

Series
Stochastics Seminar
Time
Tuesday, June 12, 2018 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Jean-Christophe Breton – University of Rennes
Random balls models are collections of Euclidean balls whose centers and radii are generated by a Poisson point process. Such collections model various contexts ranging from imaging to communication network. When the distributions driving the centers and the radii are heavy-tailed, interesting interference phenomena occurs when the model is properly zoomed-out. The talk aims to illustrate such phenomena and to give an overview of the asymptotic behavior of functionals of interest. The limits obtained include in particular stable fields, (fractional) Gaussian fields and Poissonian bridges. Related questions will also be discussed.

Quenched survival of Bernoulli percolation on Galton-Watson trees

Series
Stochastics Seminar
Time
Thursday, April 12, 2018 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Joshua Rosenberg – University of Pennsylvania –
In this talk I will explore the subject of Bernoulli percolation on Galton-Watson trees. Letting $g(T,p)$ represent the probability a tree $T$ survives Bernoulli percolation with parameter $p$, we establish several results relating to the behavior of $g$ in the supercritical region. These include an expression for the right derivative of $g$ at criticality in terms of the martingale limit of $T$, a proof that $g$ is infinitely continuously differentiable in the supercritical region, and a proof that $g'$ extends continuously to the boundary of the supercritical region. Allowing for some mild moment constraints on the offspring distribution, each of these results is shown to hold for almost surely every Galton-Watson tree. This is based on joint work with Marcus Michelen and Robin Pemantle.

The Sample Complexity of Multi-Reference Alignment

Series
Stochastics Seminar
Time
Thursday, April 5, 2018 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Philippe Rigollet – MIT
How should one estimate a signal, given only access to noisy versions of the signal corrupted by unknown cyclic shifts? This simple problem has surprisingly broad applications, in fields from aircraft radar imaging to structural biology with the ultimate goal of understanding the sample complexity of Cryo-EM. We describe how this model can be viewed as a multivariate Gaussian mixture model whose centers belong to an orbit of a group of orthogonal transformations. This enables us to derive matching lower and upper bounds for the optimal rate of statistical estimation for the underlying signal. These bounds show a striking dependence on the signal-to-noise ratio of the problem. We also show how a tensor based method of moments can solve the problem efficiently. Based on joint work with Afonso Bandeira (NYU), Amelia Perry (MIT), Amit Singer (Princeton) and Jonathan Weed (MIT).

On an extension of the Ito-Nisio theorem with applications to the continuity of Ito map and Levy processes

Series
Stochastics Seminar
Time
Thursday, March 8, 2018 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Jan Rosinski – University of Tennessee –
We obtain an extension of the Ito-Nisio theorem to certain non separable Banach spaces and apply it to the continuity of the Ito map and Levy processes. The Ito map assigns a rough path input of an ODE to its solution (output). Continuity of this map usually requires strong, non separable, Banach space norms on the path space. We consider as an input to this map a series expansion a Levy process and study the mode of convergence of the corresponding series of outputs. The key to this approach is the validity of Ito-Nisio theorem in non separable Wiener spaces of certain functions of bounded p-variation. This talk is based on a joint work with Andreas Basse-O’Connor and Jorgen Hoffmann-Jorgensen.

Cover time for the frog model on trees

Series
Stochastics Seminar
Time
Thursday, February 15, 2018 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Tobias Johnson – College of Staten Island –
Place Poi(m) particles at each site of a d-ary tree of height n. The particle at the root does a simple random walk. When it visits a site, it wakes up all the particles there, which start their own random walks, waking up more particles in turn. What is the cover time for this process, i.e., the time to visit every site? We show that when m is large, the cover time is O(n log(n)) with high probability, and when m is small, the cover time is at least exp(c sqrt(n)) with high probability. Both bounds are sharp by previous results of Jonathan Hermon's. This is the first result proving that the cover time is polynomial or proving that it's nonpolymial, for any value of m. Joint work with Christopher Hoffman and Matthew Junge.

New perspectives on Mallows permutations

Series
Stochastics Seminar
Time
Wednesday, February 14, 2018 - 11:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Omer Angel – University of British Columbia –
I will discuss two projects concerning Mallows permutations, with Ander Holroyd, Tom Hutchcroft and Avi Levy. First, we relate the Mallows permutation to stable matchings, and percolation on bipartite graphs. Second, we study the scaling limit of the cycles in the Mallows permutation, and relate it to diffusions and continuous trees.

Free multiplicative cascades and Wigner's semicircle law

Series
Stochastics Seminar
Time
Thursday, February 8, 2018 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Ian McKeague – Columbia University
It has been conjectured that phenomena as diverse as the behavior of large "self-organizing" neural networks, and causality in standard model particle physics, can be explained by suitably rich algebras acting on themselves. In this talk I discuss the asymptotics of large causal tree diagrams that combine freely independent elements of such algebras. The Marchenko-Pastur law and Wigner's semicircle law are shown to emerge as limits of a normalized sum-over-paths of non-negative elements assigned to the edges of causal trees. The results are established in the setting of non-commutative probability. Trees with classically independent positive edge weights (random multiplicative cascades) were originally proposed by Mandelbrot as a model displaying the fractal features of turbulence. The novelty of the present work is the use of non-commutative (free) probability to allow the edge weights to take values in an algebra.

Delay-Optimal Scheduling for Data Center Networks and Input-Queued Switches in Heavy Traffic

Series
Stochastics Seminar
Time
Thursday, January 25, 2018 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Siva Maguluri – Georgia Insitute of Technology –
Today's era of cloud computing is powered by massive data centers. A data center network enables the exchange of data in the form of packets among the servers within these data centers. Given the size of today's data centers, it is desirable to design low-complexity scheduling algorithms which result in a fixed average packet delay, independent of the size of the data center. We consider the scheduling problem in an input-queued switch, which is a good abstraction for a data center network. In particular, we study the queue length (equivalently, delay) behavior under the so-called MaxWeight scheduling algorithm, which has low computational complexity. Under various traffic patterns, we show that the algorithm achieves optimal scaling of the heavy-traffic scaled queue length with respect to the size of the switch. This settles one version of an open conjecture that has been a central question in the area of stochastic networks. We obtain this result by using a Lyapunov-type drift technique to characterize the heavy-traffic behavior of the expected total queue length in the network, in steady-state.

Pages