USC Probability and Statistics Seminars (Fall 2014)

Fall 2014 Seminars

September 12 – Aaron Abrams, Washington and Lee University

Finding patterns in randomness: A new perspective on the longest increasing subsequence problem
Given a random permutation of 1, . . . , N, how long is the longest subsequence that’s monotonically increasing? Decades of work went into solving and understanding this problem, and by now the answer is well-known: the expectation is 2√N and the length is distributed according to the famous Tracy-Widom distribution.
Now, given a random permutation of 1, . . . , N, how long is the longest subsequence that alternates between increasing and decreasing? This problem turns out to be much easier. A few years ago, Stanley showed that this length is normally distributed around a mean of 2N/3.
These two cases have quite different behaviors. We show that they are archetypes of a dichotomy: for any order pattern (of which increasing and alternating are examples), the answer will resemble either the increasing case or the alternating case. The difference is detected by a simple combinatorial feature called drift that arose in some of our earlier work.
(Joint work with E. Babson, H. Landau, Z. Landau, and J. Pommersheim)

September 19 – Ken Alexander, USC

Polymer pinning with sparse disorder
The standard setup in disordered pinning models is that a polymer configuration is modeled by the trajectory of a Markov chain which is rewarded or penalized by an amount ω_n when it returns to a special state 0 at time n. More precisely, for a polymer of length N the Boltzmann weight is e^βH, where for a trajectory τ, H(τ) is the sum of the values ω_n at the times n≤N of the returns to 0 of τ. Typically the ω_n are taken to be a quenched realization of a iid sequence, but here we consider the case of sparse disorder: ω_n is 1 at the returns times of a quenched realization of a renewal sequence {σ_j}, and 0 otherwise; in the interesting cases the gaps between renewals have infinite mean, and we assume the gaps have a regularly varying power-law tail. For β above a critical point, the polymer is pinned in the sense that τ asymptotically hits a positive fraction of the N renewals in σ. To see the effect of the disorder one can compare this critical point to the one in the corresponding annealed system. We establish equality or inequality of these critical points depending on the tail exponents of the two renewal sequences (that is, σ and the return times of τ.) This is joint work with Quentin Berger.

September 26 – Skip Garibaldi, UCLA IPAM

Probability and the lottery
Various schemes surrounding the lottery, both legal and criminal, both money-losing and money-making, raise interesting probability problems. We explain how to analyze these schemes, how the analysis can distinguish between criminals and problem gamblers, and how the analysis led to lottery operators changing policies and law enforcement cracking down on the criminal schemes.
This talk is about joint work with Aaron Abrams, Richard Arratia, Philip Stark, and others. It will be accessible to a general mathematical audience; the main pre-requisite is something like Math 307 or Math 407.

October 3 – Larry Goldstein, USC

Normal approximation for Gaussian projections and conic intrinsic volumes: Steining the Steiner formula
Intrinsic volumes of convex sets are natural geometric quantities that also play important roles in applications. In particular, the discrete probability distribution L(V_C) given by the sequence v₀, . . . ,v_d of conic intrinsic volumes of a closed convex cone C in R^d summarizes key information about the success of convex programs used to solve for sparse vectors, and other unknowns, in high dimensional regularized inverse problems. The concentration of V_C implies the existence of phase transitions for the probability of recovery of the unknown in the number of observations. Additional information about the probability of recovery success is provided by a normal approximation for V_C. Such central limit theorems can be shown by first considering the squared length G_C of the projection of a Gaussian vector on the cone C. Applying a second order Poincaré inequality, proved using Stein’s method and Malliavin calculus, then produces a non-asymptotic total variation bound to the normal for L(G_C). A conic version of the classical Steiner formula in convex geometry shows a normal limit for G_C implies one for V_C.
This work is joint with Ivan Nourdin and Giovanni Peccati.

October 10 – Jianfeng Zhang, USC

Some Thinking about Pathwise Stochastic Calculus
In standard stochastic analysis literature, processes are typically understood in a.s. sense, with notable examples stochastic integration and conditional expectations. Motivated from our study of path dependent PDEs, which is a convenient tool to study non-Markovian (or say path dependent) problems, we are interested in pathwise solutions of certain equations. In particular, we would like to have the regularity of the processes in terms of the underlying paths. For the backward situation, with conditional expectation as a typical example, it seems the Functional Ito formula is the right tool. For the forward situation, with stochastic integration as a simple example, we feel the rough path theory is the convenient tool. With the help of the rough path theory, we will show that a diffusion (and more generally the solution of a stochastic PDE) can be continuous in ω under certain topology.

October 17 – Han Liang Gan, Washington University in St Louis

Conditional random variable approximation with Stein’s method
The distribution of the number of rare events is a problem that has been studied extensively over a long period of time. At its core is the law of small numbers, which states that if you have many independent events that happen with very small probability, then the distribution of the number of rare events is Poisson in limit. If you relax the independence assumption, then the limit becomes far more complicated. In this talk, we will focus on approximating the distribution of the number of rare events given at least 1 rare event has occurred, and to this end, formulate Stein’s method for conditional random variable approximation. We will also discuss conditional point process approximation, and the difficulties that generalising to a spatial point process generates.
This is joint work with Aihua Xia.

October 31 – Toby Johnson, USC

The frog model on trees
Imagine that each vertex of a graph contains a sleeping frog. At time 0, the frog at some designated vertex wakes up and begins a simple random walk. When it lands on a vertex, the sleeping frog there wakes up and begins its own simple random walk, which in turn wakes up any sleeping frogs it lands on, and so on. This process is called the frog model.
We consider a question posed by Serguei Popov in 2003: On an infinite d-ary tree, is the frog model recurrent or transient? That is, is each vertex visited infinitely or finitely often by frogs? We (mostly) resolve this question, showing that there is a phase transition between recurrence and transience as d grows. This work is joint with Christopher Hoffman and Matthew Junge.

Monday November 3 (joint with CAMS Colloquium) – Michael Wolf, University of Zurich

Spectrum Estimation: A Unified Framework for Covariance Matrix Estimation and PCA in Large Dimensions
Covariance matrix estimation and principal component analysis (PCA) are two cornerstones of multivariate analysis. Classic textbook solutions perform poorly when the dimension of the data is of a magnitude similar to the sample size, or even larger. In such settings, there is a common remedy for both statistical problems: nonlinear shrinkage of the eigenvalues of the sample covariance matrix. The optimal nonlinear shrinkage formula depends on unknown population quantities and is thus not available. It is, however, possible to consistently estimate an oracle nonlinear shrinkage, which is motivated on asymptotic grounds. A key tool to this end is consistent estimation of the set of eigenvalues of the population covariance matrix (also known as the spectrum), an interesting and challenging problem in its own right. Extensive Monte Carlo simulations demonstrate that our methods have desirable finite-sample properties and outperform previous proposals.

November 7 – Yosef Rinott, Hebrew University of Jerusalem

A partial survey and some new thoughts on model selection
I will discuss some model selection methods, old and relatively new, such as AIC, BIC, Lasso and more. I will explain their goals and ‘philosophy’, and some of their properties. Time permitting I will discuss my recent work in this area.

November 14 (joint with Mathematical Finance Colloquium) – Carl Mueller, University of Rochester

Do stochastic PDE hit points or have double points in the critical dimensions?
This talk will describe work in progress with R. Dalang, Y. Xiao, and S. Tindel. The stochastic heat equation is often used as a basic model for a moving polymer:
(1)       ∂_tu=Δu+̇Ẇ(t,x).
Here, u = u(t,x) ∈ R^d is the position of the polymer, x ∈ R is the length along the polymer, and t is time. Ẇ(t,x) is two-parameter vector-valued white noise. Note that u ∈ R^d; that is, u is vector-valued. This is consistent with the interpretation of u as the position of a polymer.
We say that the solution hits a point z if there is positive probability that u(t,x) = z for some (random) parameters (t,x). We say that the solution has a double point if there exist distinct pairs of parameters (t,x) and (s,y) with t,s>0, x,y ∈ R such that u(t,x) = u(s,y). Some time ago the speaker and R. Tribe proved that d = 6 is the critical dimension for the solution u to hit points. That is, for a generic point z, the solution u hits points iff d < 6. In the same way, the critical dimension for double points is d = 12. The proofs use arguments which are specific to (1).
The goal of our work, which is still in progress, is to adapt an argument of Talagrand to study this question for equations similar to (1) but which:
(1) have colored noise in place of white noise;
(2) have nonlinearities.
As usual, the critical case is by far the hardest. In fact, there are a number of results about the situation away from criticality, but they are not sharp enough to give the results we seek.

November 14 at 4.30pm (Special Colloquium) – Teng Zhang, Princeton University

Tyler’s M-estimator: subspace recovery and high-dimensional regime
Given a data set, Tyler’s M-estimator is a widely used covariance matrix estimator with robustness to outliers or heavy-tailed distribution. We will discuss two recent results of this estimator. First, we show that when a certain percentage of the data points are sampled from a low-dimensional subspace, Tyler’s M-estimator can be used to recover the subspace exactly. Second, in the high-dimensional regime that the number of samples n and the dimension p both go to infinity, p/n converges to a constant y with 0<y<1, and when the data samples are identically and independently generated from the Gaussian distribution N(0,I), we showed that the difference between the sample covariance matrix and a scaled version of Tyler’s M-estimator tends to zero in spectral norm, and the empirical spectral densities of both estimators converge to the Marcenko-Pastur distribution. We also prove that when the data samples are generated from an elliptical distribution, the limiting distribution of Tyler’s M-estimator converges to a Marcenko-Pastur-Type distribution. This is joint work with Xiuyuan Cheng and Amit Singer.

November 21 at 3pm (Special Colloquium) – Ngoc Mai Tran, University of Texas at Austin

Random permutations and random partitions
I will talk about various problems related to random permutations and random partitions. In particular, I discuss size-biased permutations, which have applications to statistical sampling. Then I will talk about random partitions obtained from projections of polytopes. These are related to random polytopes and zeros of random tropical polynomials.

November 21 at 4.30pm (Special Colloquium) – Joseph Neeman, University of Texas at Austin

Gaussian noise stability
Given two correlated Gaussian vectors, X and Y, the noise stability of a set A is the probability that both X and Y fall in A. In 1985, C. Borell proved that half-spaces maximize the noise stability among all sets of a given Gaussian measure. We will give a new, and simpler, proof of this fact, along with some extensions and applications. Specifically, we will discuss hitting times for the Ornstein-Uhlenbeck process, and a noisy Gaussian analogue of the “double bubble” problem.

December 5 – Stephen DeSalvo, UCLA

Limit shapes of restricted integer partitions under non-multiplicative conditions
Limit shapes are an increasingly popular way to understand the large-scale characteristics of a random ensemble. The limit shape of unrestricted integer partitions has been studied by many authors primarily under the uniform measure and Plancherel measure. In addition, asymptotic properties of integer partitions subject to restrictions has also been studied, but mostly with respect to independent conditions of the form “parts of size i can occur at most a_i times.” While there has been some progress on asymptotic properties of integer partitions under other types of restrictions, the techniques are mostly ad hoc. In this talk, we will present an approach to finding limit shapes of restricted integer partitions which extends the types of restrictions currently available, using a class of asymptotically stable bijections. This is joint work with Igor Pak.

Monday December 8 at 2pm (Special Colloquium) – Johannes Lederer, Cornell University

Tuning Parameters in High-Dimensional Statistics
High-dimensional statistics has become pivotal in many areas of science and engineering. In biology, for example, the advent of high-throughput technologies has generated a tremendous demand for statistical methods that allow for large and complex data sets.
Considerable effort has been made over the last couple of years to develop such methods. However, a major limitation of standard methods, such as Lasso, Ridge Regression, and Graphical Lasso, is their dependence on tuning parameters that are difficult to calibrate in practice. In this talk, I present two novel approaches to overcome this limitation. The first approach is a novel calibration scheme for high-dimensional estimation and prediction with standard estimators.
Our novel scheme is inspired by techniques for bandwidth selection in non-parametric statistics and is the first procedure that simultaneously provides fast computations, optimal finite sample guarantees, and highly competitive practical performances. The second approach establishes model selection via the minimization of an objective function that avoids tuning parameters altogether. Apart from its value for regression, this approach is particularly useful as a basis for graph estimation. Despite the mathematical nature of my research, I especially illustrate in my talk that our procedures can be readily applied to reveal hidden structures in high-dimensional data.

Wednesday December 10 at 2pm (Special Colloquium) – Xiaodong Li, University of Pennsylvania

Low-rank Recovery by Convex and Nonconvex Optimization with Applications in Network Data Analysis and Imaging
Low-rank structures are common in modern data analysis and signal processing, and they usually play essential roles in different estimation problems. Convex and nonconvex optimization methods are shown to be effective and efficient in the recovery of hidden low-rank structures from noisy and undersampled datasets. Two examples in statistics and signal processing are employed to illustrate the features of these two methods, respectively.
The first example is community detection, which is concerning how to cluster N nodes in a given network dataset into r distinct groups according to edge densities. By making use of the hidden low-rank structures induced by the communities, a convex optimization method is proven to be able to accurately detect the communities against a portion of the adversarial outlier nodes. Our theoretical results admit to the state-of-the-art results in the literature of computationally convenient community detetion under the standard stochastic block model.
The second example is regarding how to recover a signal from intensity measurements. This model has important applications in imaging, and it is equivalent to the recovery of a rank-one matrix from linear measurements. Initialized by a spectral method, we show that a gradient descent method induced by a nonconvex optimization can recover the signal quickly and accurately.
By studying these two examples carefully, we can get some intuition about the features and advantages of convex and nonconvex methods in low-rank recovery. Our analytical framework may provide insights for analyzing the statistical efficiency of computational methods in other large data problems.