Seminars & Colloquia

Thursday, April 28, 2016

Some new non-asymptotic results about the accuracy of the weighted bootstrap

Thu, 04/28/2016 - 3:05pm, Skiles 006

Mayya Zhilova, School of Mathematics, Georgia Tech        Organizer: Christian Houdré

The bootstrap procedure is well known for its good finite-sample performance, though the majority of the present results about its accuracy are asymptotic. I will study the accuracy of the weighted (or multiplier) bootstrap procedure for estimation of quantiles of a likelihood ratio statistic. The set-up is the following: the sample size is bounded, random observations are independent, but not necessarily identically distributed, and a parametric model can be misspecified. This problem had been considered in the recent work of Spokoiny and Zhilova (2015) with non-optimal results. I will present a new approach improving the existing results.

Thursday, April 21, 2016

Levy-Khintchine random matrices and the Poisson weighted infinite skeleton tree

Thu, 04/21/2016 - 3:05pm, Skiles 006

Paul Jung, University of Alabama Birmingham        Organizer: Christian Houdré

We look at a class of Hermitian random matrices which includes Wigner matrices, heavy-tailed random matrices, and sparse random matrices such as adjacency matrices of Erdos-Renyi graphs with p=1/N. Our matrices have real entries which are i.i.d. up to symmetry. The distribution of entries depends on N, and we require sums of rows to converge in distribution; it is then well-known that the limit must be infinitely divisible. We show that a limiting empirical spectral distribution (LSD) exists, and via local weak convergence of associated graphs, the LSD corresponds to the spectral measure associated to the root of a graph which is formed by connecting infinitely many Poisson weighted infinite trees using a backbone structure of special edges. One example covered are matrices with i.i.d. entries having infinite second moments, but normalized to be in the Gaussian domain of attraction. In this case, the LSD is a semi-circle law.

Thursday, April 7, 2016

Dynamics of geodesic flows with random forcing on Lie groups with left-invariant metrics

Thu, 04/07/2016 - 3:05pm, Skiles 006

Wenqing Hu, University of Minnesota, Twin Cities        Organizer: Christian Houdré

Motivated by problems in turbulent mixing, we consider stochastic perturbations of geodesic flow for left-invariant metrics on finite-dimensional Lie groups. We study the ergodic properties and provide criteria that ensure the Hormander condition for the corresponding Markov processes on phase space. Two different types of models are considered: the first one is a classical Langevin type perturbation and the second one is a perturbation by a “conservative noise”. We also study an example of a non-compact group. Joint work with Vladimir Sverak.

Thursday, March 31, 2016

Random walks on abelian sandpiles

Thu, 03/31/2016 - 3:05pm, Skiles 006

John Pike, Cornell University        Organizer: Christian Houdré

Given a simple connected graph G=(V,E), the abelian sandpile Markov chain evolves by adding chips to random vertices and then stabilizing according to certain toppling rules. The recurrent states form an abelian group \Gamma, the sandpile group of G. I will discuss joint work with Dan Jerison and Lionel Levine in which we characterize the eigenvalues and eigenfunctions of the chain restricted to \Gamma in terms of "multiplicative harmonic functions'' on V. We show that the moduli of the eigenvalues are determined up to a constant factor by the lengths of vectors in an appropriate dual Laplacian lattice and use this observation to bound the mixing time of the sandpile chain in terms of the number of vertices and maximum vertex degree of G. We also derive a surprising inverse relationship between the spectral gap of the sandpile chain and that of simple random walk on G.

Tuesday, March 8, 2016

Randomized Isoperimetric Inequalities

Tue, 03/08/2016 - 3:05pm, Skiles 005

Peter Pivovarov, University of Missouri        Organizer: Galyna Livshyts

The focus of my talk will be stochastic forms of isoperimetric inequalities for convex sets. I will review some fundamental inequalities including the classical isoperimetric inequality and those of Brunn-Minkowski and Blaschke-Santalo on the product of volumes of a convex body and its polar dual. I will show how one can view these as global inequalities that arise via random approximation procedures in which stochastic dominance holds at each stage. By laws of large numbers, these randomized versions recover the classical inequalities. I will discuss when such stochastic dominance arises and its applications in convex geometry and probability. The talk will be expository and based on several joint works with G. Paouris, D. Cordero-Erausquin, M. Fradelizi, S. Dann and G. Livshyts.

Thursday, March 3, 2016

On the analogue of the monotonicity of entropy in the Brunn-Minkowski theory

Thu, 03/03/2016 - 3:05pm, Skiles 006

Arnaud Marsiglietti, IMA, University of Minnesota        Organizer: Galyna Livshyts

In the late 80's, several relationships have been established between the Information Theory and Convex Geometry, notably through the pioneering work of Costa, Cover, Dembo and Thomas. In this talk, we will focus on one particular relationship. More precisely, we will focus on the following conjecture of Bobkov, Madiman, and Wang (2011), seen as the analogue of the monotonicity of entropy in the Brunn-Minkowski theory: The inequality $$ |A_1 + \cdots + A_k|^{1/n} \geq \frac{1}{k-1} \sum_{i=1}^k |\sum_{j \in \{1, \dots, k\} \setminus \{i\}} A_j |^{1/n}, $$ holds for every compact sets $A_1, \dots, A_k \subset \mathbb{R}^n$. Here, $|\cdot|$ denotes Lebesgue measure in $\mathbb{R}^n$ and $A + B = \{a+b : a \in A, b \in B \}$ denotes the Minkowski sum of $A$ and $B$. (Based on a joint work with M. Fradelizi, M. Madiman, and A. Zvavitch.)

Thursday, February 25, 2016

Central Limit Theorems and Bootstrap in High Dimensions

Thu, 02/25/2016 - 3:05pm, Skiles 006

Victor Chernozhukov, MIT        Organizer: Karim Lounici

This paper derives central limit and bootstrap theorems for probabilities that sums of centered high-dimensional random vectors hit hyperrectangles and sparsely convex sets. Specifically, we derive Gaussian and bootstrap approximations for probabilities  Pr(n−1/2∑ni=1Xi∈A) where X1,…,Xn are independent random vectors in ℝp and Ais a hyperrectangle, or, more generally, a sparsely convex set, and show that the approximation error converges to zero even if p=pn→∞ as n→∞ and p≫n; in particular, p can be as large as O(eCnc) for some constants c,C>0. The result holds uniformly over all hyperrectangles, or more generally, sparsely convex sets, and does not require any restriction on the correlation structure among coordinates of Xi. Sparsely convex sets are sets that can be represented as intersections of many convex sets whose indicator functions depend only on a small subset of their arguments, with hyperrectangles being a special case.

Paper available on arXiv:1412.3661

Thursday, February 18, 2016

On the infinitesimal versions of Log Brunn Minkowski and Gaussian Brunn Minkowski conjectures

Thu, 02/18/2016 - 3:05pm, Skiles 006

Galyna Livshyts, School of Mathematics, Georgia Tech        Organizer: Galyna Livshyts

Log Brunn-Minkowski conjecture was proposed by Boroczky, Lutwak, Yang and Zhang in 2013. It states that in the case of symmetric convex sets the classical Brunn-MInkowski inequality may be improved. The Gaussian Brunn-MInkowski inequality was proposed by Gardner and Zvavitch in 2007. It states that for the standard Gaussian measure an inequality analogous to the additive form of Brunn_minkowski inequality holds true for symmetric convex sets. In this talk we shall discuss a derivation of an equivalent infinitesimal versions of these inequalities for rotation invariant measures and a few partial results related to both of them as well as to the classical Alexander-Fenchel inequality.

Thursday, February 11, 2016

On the CLT for sample covariance matrices without independent structure in columns

Thu, 02/11/2016 - 3:05pm, Skiles 006

Anna Lytova, University of Alberta        Organizer: Galyna Livshyts


Thursday, February 4, 2016

Random zero sets under repeated differentiation of an analytic function

Thu, 02/04/2016 - 3:05pm, Skiles 006

Sneha Subramanian, School of Mathematics, Georgia Tech        Organizer: Christian Houdré

For a random (complex) entire function, what can we say about the behavior of the zero set of its N-th derivative, as N goes to infinity? In this talk, we shall discuss the result of repeatedly differentiating a certain class of random entire functions whose zeros are the points of a Poisson process of intensity 1 on the real line. We shall also discuss the asymptotic behavior of the coefficients of these entire functions. Based on joint work with Robin Pemantle.

Thursday, January 28, 2016

A central limit theorem for temporally non-homogenous Markov chains with applications to dynamic programming

Thu, 01/28/2016 - 3:05pm, Skiles 006

Alessandro Arlotto, Duke University        Organizer: Christian Houdré

We prove a central limit theorem for a class of additive processes that arise naturally in the theory of finite horizon Markov decision problems. The main theorem generalizes a classic result of Dobrushin (1956) for temporally non-homogeneous Markov chains, and the principal innovation is that here the summands are permitted to depend on both the current state and a bounded number of future states of the chain. We show through several examples that this added flexibility gives one a direct path to asymptotic normality of the optimal total reward of finite horizon Markov decision problems. The same examples also explain why such results are not easily obtained by alternative Markovian techniques such as enlargement of the state space. (Joint work with J. M. Steele.)

Thursday, January 21, 2016

High-dimensional change-point detection: kernel-based method and sketching

Thu, 01/21/2016 - 3:05pm, Skiles 006

Yao Xie, Georgia Inst. of Technology, ISYE        Organizer: Karim Lounici

Detecting change-points from high-dimensional streaming data is a fundamental problem that arises in many big-data applications such as video processing, sensor networks, and social networks. Challenges herein include developing algorithms that have low computational complexity and good statistical power, that can exploit structures to detecting weak signals, and that can provide reliable results over larger classes of data distributions. I will present two aspects of our recent work that tackle these challenges: (1) developing kernel-based methods based on nonparametric statistics; and (2) using sketching of high-dimensional data vectors to reduce data dimensionality. We also provide theoretical performance bounds and demonstrate the performance of the algorithms using simulated and real data.

Thursday, January 14, 2016

Chaining, interpolation, and convexity

Thu, 01/14/2016 - 3:05pm, Skiles 006

Ramon van Handel, Princeton University        Organizer: Christian Houdré

A significant achievement of modern probability theory is the development of sharp connections between the boundedness of random processes and the geometry of the underlying index set. In particular, the generic chaining method of Talagrand provides in principle a sharp understanding of the suprema of Gaussian processes. The multiscale geometric structure that arises in this method is however notoriously difficult to control in any given situation. In this talk, I will exhibit a surprisingly simple but very general geometric construction, inspired by real interpolation of Banach spaces, that is readily amenable to explicit computations and that explains the behavior of Gaussian processes in various interesting situations where classical entropy methods are known to fail. (No prior knowledge of this topic will be assumed in the talk.)

Thursday, December 3, 2015

ShapeFit: Exact location recovery from corrupted pairwise directions

Thu, 12/03/2015 - 3:05pm, Skiles 006

Paul Hand, Rice University, email        Organizer: Michael Damron

We consider the problem of recovering a set of locations given observations of the direction between pairs of these locations.   This recovery task arises from the Structure from Motion problem, in which a three-dimensional structure is sought from a collection of two-dimensional images.  In this context, the locations of cameras and structure points are to be found from epipolar geometry and point correspondences among images.  These correspondences are often incorrect because of lighting, shadows, and the effects of perspective.  Hence, the resulting observations of relative directions contain significant corruptions.  To solve the location recovery problem in the presence of corrupted relative directions, we introduce a tractable convex program called ShapeFit.  Empirically, ShapeFit can succeed on synthetic data with over 40% corruption.  Rigorously, we prove that ShapeFit can recover a set of locations exactly when a fraction of the measurements are adversarially corrupted and when the data model is random.  This and subsequent work was done in collaboration with Choongbum Lee, Vladislav Voroninski, and Tom Goldstein.

Thursday, November 19, 2015

Convergence of the extremal eigenvalues of empirical covariance matrices with dependence

Thu, 11/19/2015 - 3:05pm, Skiles 006

Konstantin Tikhomirov , University of Alberta        Organizer: Christian Houdré

Consider a sample of a centered random vector with unit covariance matrix. We show that under certain regularity assumptions, and up to a natural scaling, the smallest and the largest eigenvalues of the empirical covariance matrix converge, when the dimension and the sample size both tend to infinity, to the left and right edges of the Marchenko-Pastur distribution. The assumptions are related to tails of norms of orthogonal projections. They cover isotropic log-concave random vectors as well as random vectors with i.i.d. coordinates with almost optimal moment conditions. The method is a refinement of the rank one update approach used by Srivastava and Vershynin to produce non-asymptotic quantitative estimates. In other words we provide a new proof of the Bai and Yin theorem using basic tools from probability theory and linear algebra, together with a new extension of this theorem to random matrices with dependent entries. Based on joint work with Djalil Chafai.