- You are here:
- GT Home
- Home
- News & Events

Series: Stochastics Seminar

We consider the problem of studying the limiting distribution of the number of monochromatic two stars and triangles for a growing sequence of graphs, where the vertices are colored uniformly at random. We show that the limit distribution of the number of monochromatic two stars is a sum of mutually independent components, each term of which is a polynomial of a single Poisson random variable of degree 1 or 2. Further, we show that any limit distribution for the number of monochromatic two stars has an expansion of this form. In the triangle case the problem is more challenging, as in this case the class of limit distributions can involve terms with products of Poisson random variables. In this case, we deduce a necessary and sufficient condition on the sequence of graphs such that the number of monochromatic triangles is asymptotically Poisson in distribution and in the first two moments. This work is joint with Bhaswar B. Bhattacharya at University of Pennsylvania.

Series: Stochastics Seminar

Estimation of the covariance matrix has attracted significant attention
of the statistical research community over the years, partially due to
important applications such as Principal Component Analysis. However,
frequently used empirical covariance estimator (and its modifications)
is very sensitive to outliers, or ``atypical’’ points in the sample.
As P. Huber wrote in 1964, “...This raises a question which could have
been asked already by Gauss, but which was, as far as I know, only
raised a few years ago (notably by Tukey): what happens if the true
distribution deviates slightly from the assumed normal one? As is now
well known, the sample mean then may have a catastrophically bad
performance…”
Motivated by Tukey's question, we develop a new estimator of the
(element-wise) mean of a random matrix, which includes covariance
estimation problem as a special case. Assuming that the entries of a
matrix possess only finite second moment, this new estimator admits
sub-Gaussian or sub-exponential concentration around the unknown mean in
the operator norm. We will present extensions of our approach to
matrix-valued U-statistics, as well as applications such as the matrix
completion problem.
Part of the talk will be based on a joint work with Xiaohan Wei.

Series: Stochastics Seminar

Determinantal point processes (DPPs) have attracted a lot of attention in probability theory, because they arise naturally in many integrable systems. In statistical physics, machine learning, statistics and other fields, they have become increasingly popular as an elegant mathematical tool used to describe or to model repulsive interactions. In this talk, we study the geometry of the likelihood associated with such processes on finite spaces. Interestingly, the local behavior of the likelihood function around its global maxima can be very different according to the structure of a specific graph that we define for each DPP. Finally, we discuss some statistical consequences of this fact, namely, the asymptotic accuracy of a maximum likelihood estimator.

Series: Stochastics Seminar

As a general fact, directed polymers in random environment are localized in
the so called strong disorder phase. In this talk, based on a joint with Francis Comets, we will consider the exactly solvable
model with log gamma environment,introduced recently by Seppalainen.
For the stationary model
and the point to line version, the localization can be expressed as the trapping
of the endpoint in a potential given by an independent random walk.

Series: Stochastics Seminar

Excitable media are characterized by a local tendency towards synchronization, which can lead to waves of excitement through the system. Two classical discrete, deterministic models of excitable media are the cyclic cellular automaton and Greenberg-Hastings models, which have been extensively studied on lattices, Z^d. One is typically interested in whether or not sites are excited (change states) infinitely often (fluctuation vs fixation), and if so, whether the density of domain walls between disagreeing sites tends to 0 (clustering). We introduce a new comparison process for the 3-color variants of these models, which allows us to study the asymptotic rate at which a site gets excited. In particular, for a class of infinite trees we can determine whether the rate is 0 or positive. Using this comparison process, we also analyze a new model for pulse-coupled oscillators in one dimension, introduced recently by Lyu, called the firefly cellular automaton (FCA). Based on joint works with Lyu and Gravner.

Series: Stochastics Seminar

Please note the special time! This is Stochastic & Analysis seminars joint.

Motivated by the investigation on the dependence on ``epsilon" in the Dvoretzky's theorem, I will show some refinements of the classical concentration of measure for convex functions. Applications to convexity will be presented if time permits. The talk will be based on joint works with Peter Pivovarov and Petros Valettas.

Series: Stochastics Seminar

First-passage percolation is a classical random growth model which comes from statistical physics. We will discuss recent results about the relationship between the limiting shape in first passage percolation and the structure of the infinite geodesics. This incudes a solution to the midpoint problem of Benjamini, Kalai and Schramm. This is joint work with Gerandy Brito and Daniel Ahlberg.

Series: Stochastics Seminar

We propose a new convex relaxation for the problem of solving
(random) quadratic equations known as phase retrieval. The main advantage
of the proposed method is that it operates in the natural domain of the
signal. Therefore, it has significantly lower computational cost than the
existing convex methods that rely on semidefinite programming and competes
with the recent non-convex methods. In the proposed formulation the
quadratic equations are relaxed to inequalities describing a "complex
polytope". Then, using an *anchor vector* that itself can be constructed
from the observations, a simple convex program estimates the ground truth
as an (approximate) extreme point of the polytope. We show, using classic
results in statistical learning theory, that with random measurements this
convex program produces accurate estimates. I will also discuss some
preliminary results on a more general class of regression problems where we
construct accurate and computationally efficient estimators using anchor
vectors.

Series: Stochastics Seminar

We study the problem of estimation of a linear functional of the eigenvector
of covariance
operator that corresponds to its largest eigenvalue (the first principal
component) based
on i.i.d. sample of centered Gaussian observations with this covariance. The
problem is studied
in a dimension-free framework with its complexity being characterized by so
called "effective rank"
of the true covariance. In this framework, we establish a minimax lower
bound on the mean squared
error of estimation of linear functional and construct an asymptotically
normal
estimator for which the bound is attained. The standard "naive" estimator
(the linear functional
of the empirical principal component) is suboptimal in this problem.
The talk is based on a joint work with Richard Nickl.

Series: Stochastics Seminar

Demand forecasting plays an important role in many inventory control
problems. To mitigate the potential harms of model misspecification, various
forms of distributionally robust optimization have been applied. Although
many of these methodologies suffer from the problem of time-inconsistency,
the work of Klabjan et al. established a general time-consistent framework
for such problems by connecting to the literature on robust Markov decision
processes.
Motivated by the fact that many forecasting models exhibit very special
structure, as well as a desire to understand the impact of positing
different dependency structures, in this talk we formulate and solve a
time-consistent distributionally robust multi-stage newsvendor model which
naturally unifies and robustifies several inventory models with demand
forecasting. In particular, many simple models of demand forecasting have
the feature that demand evolves as a martingale (i.e. expected demand
tomorrow equals realized demand today). We consider a robust variant of such
models, in which the sequence of future demands may be any martingale with
given mean and support. Under such a model, past realizations of demand are
naturally incorporated into the structure of the uncertainty set going
forwards.
We explicitly compute the minimax optimal policy (and worst-case
distribution) in closed form, by combining ideas from convex analysis,
probability, and dynamic programming. We prove that at optimality the
worst-case demand distribution corresponds to the setting in which inventory
may become obsolete at a random time, a scenario of practical interest. To
gain further insight, we prove weak convergence (as the time horizon grows
large) to a simple and intuitive process. We also compare to the analogous
setting in which demand is independent across periods (analyzed previously
by Shapiro), and identify interesting differences between these models, in
the spirit of the price of correlations studied by Agrawal et al.
This is joint work with Linwei Xin, and the paper is available on arxiv at
https://arxiv.org/abs/1511.09437v1