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

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

Series: Stochastics Seminar

We consider permanental and multivariate negative binomial distributions. We give sim- ple necessary and sufficient conditions on their kernel for infinite divisibility, without symmetry hypothesis. For existence of permanental distributions, conditions had been given by Kogan and Marcus in the case of a 3 × 3 matrix kernel: they had showed that such distributions exist only for two types of kernels (up to diagonal similarity): symmet- ric positive-definite matrices and inverse M-matrices. They asked whether there existed other classes of kernels in dimensions higher than 3. We give an affirmative answer to this question, by exhibiting (in any finite dimension higher than 3) a family of matrices which are kernels of permanental distributions but are neither symmetric, nor inverse M-matrices (up to diagonal similarity). Analog properties (by replacing inverse M-matrices by entrywise non-negative matrices) are given for multivariate negative binomial distribu- tions. These notions are also linked with the study of inverse power series of determinant. This is a joint work with N. Eisenbaum.

Series: Stochastics Seminar

Exact oracle inequalities for regression have been extensively studied in statistics and learning theory over the past decade. In the case of a misspecified model, the focus has been on either parametric or convex classes. We present a new estimator that steps outside of the model in the non-convex case and reduces to least squares in the convex case. To analyze the estimator for general non-parametric classes, we prove a generalized Pythagorean theorem and study the supremum of a negative-mean stochastic process (which we term the offset Rademacher complexity) via the chaining technique.(joint work with T. Liang and K. Sridharan)

Series: Stochastics Seminar

In this talk, we consider the small-time asymptotics of options on a Leveraged Exchange-Traded
Fund (LETF) when the underlying Exchange Traded Fund (ETF) exhibits both local volatility
and jumps of either finite or infinite activity. Our main results are closed-form expressions for the
leading order terms of off-the-money European call and put LETF option prices, near expiration,
with explicit error bounds. We show that the price of an out-of-the-money European call on a
LETF with positive (negative) leverage is asymptotically equivalent, in short-time, to the price
of an out-of-the-money European call (put) on the underlying ETF, but with modified spot and
strike prices. Similar relationships hold for other off-the-money European options. In particular,
our results suggest a method to hedge off-the-money LETF options near expiration using options
on the underlying ETF. Finally, a second order expansion for the corresponding implied volatilities
is also derived and illustrated numerically. This is the joint work with J. E. Figueroa-Lopez and
M. Lorig.

Series: Stochastics Seminar

We consider a Gibbs distribution over random walk paths on the square lattice, proportional to a random weight of the path’s boundary. We show that in the zero temperature limit, the paths condensate around an asymptotic shape. This limit shape is characterized as the minimizer of the functional, mapping open connected subsets of the plane to the sum of their principle eigenvalue and perimeter (with respect to the first passage percolation norm). A prime novel feature of this limit shape is that it is not in the class of Wulff shapes. This is joint work with Marek Biskup.

Series: Stochastics Seminar

The Eden model, a special case of first-passage percolation, is a
stochastic growth model in which an infection that initially occupies the
origin of Z^d spreads to neighboring sites at rate 1. Infected sites are
colonized permanently; that is, an infected site never heals. It is known
that at time t, the infection occupies a set B(t) of vertices with volume of
order t^d, and the rescaled set B(t)/t converges to a convex, compact
limiting shape. In joint work with J. Hanson and W.-K. Lam, we partially
answer a question of K. Burdzy, concerning the order of the size of the
boundary of B(t). We show that, in various senses, the boundary is
relatively smooth, being typically of order t^{d-1}. This is in contrast to
the fractal behavior of interfaces characteristic of percolation models.

Series: Stochastics Seminar

Form a multiset by including Poisson(1/k) copies of each
positive integer k, and consider the sumset---the set of all finite sums
from the Poisson multiset. It was shown recently that four such
(independent) sumsets have a finite intersection, while three have
infinitely many common elements. Uncoincidentally, four uniformly random
permutations will invariably generate S_n with asymptotically positive
probability, while three will not. What is so special about four? Not much.
We show that this result is a special case of the "ubiqituous" Ewens
sampling formula. By varying the distribution's parameter we can vary the
number of random permutations needed to invariably generate S_n, and,
relatedly, the number of Poisson sumsets to have finite intersection.
*Joint with Gerandy Brita Montes de Oca, Christopher Fowler, and Avi Levy.