Georgia Institute of Technology College of Sciences

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.

We shall prove that a certain stochastic ordering defined in terms of convex symmetric sets is inherited by sums of independent symmetric random vectors. Joint work with W. Bednorz.

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).

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.