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

Series: Stochastics Seminar

We study four discrete time stochastic systems on $\bbN$ modelingprocesses of rumour spreading. The involved individuals can eitherhave an active ora passive role, speaking up or asking for the rumour. The appetite inspreading or hearing the rumour is represented by a set of randomvariables whose distributionsmay depend on the individuals. Our goal is to understand - based on those randomvariables distribution - whether the probability of having an infiniteset of individuals knowing the rumour is positive or not.

Series: Stochastics Seminar

We consider two random sequences of equal length n
and the alignments with gaps corresponding to their Longest
Common Subsequences. These alignments are called
optimal alignments. What are the properties of these
alignments? What are the proportion of different aligned
letter pairs? Are there concentration of measure
properties for these proportions? We will see that
the convex geometry of the asymptotic limit set of
empirical distributions seen along alignments can determine
the answer to the above questions.

Series: Stochastics Seminar

Semimartingales constitute the larges class of "good integrators" for which Ito
integral
could reasonably be defined and the stochastic analysis machinery applied.
In this talk we identify semimartingales within certain infinitely divisible processes.
Examples include stationary (but not independent) increment processes, such as fractional
and moving average
processes, as well as their mixtures. Such processes are non-Markovian, often possess long
range memory, and are of
interest as stochastic integrators. The talk is based on a joint work with Andreas
Basse-O'Connor.

Series: Stochastics Seminar

I will discuss how the idea of coupling at time infinity is equivalent to unique ergodicity of a markov process. In general, the coupling will be a kind of "asymptotic Wasserstein" coupling. I will draw examples from SDEs with memory and SPDEs. The fact that both are infinite dimensional markov processes is no coincidence.

Series: Stochastics Seminar

Let (X,Y) be a random couple with unknown distribution P, X being an observation and Y - a binary label to be predicted. In practice, distribution P remains unknown but the learning algorithm has access to the training data - the sample from P. It often happens that the cost of obtaining the training data is associated with labeling the observations while the pool of observations itself is almost unlimited. This suggests to measure the performance of a learning algorithm in terms of its label complexity, the number of labels required to obtain a classifier with the desired accuracy. Active Learning theory explores the possible advantages of this modified framework.We will present a new active learning algorithm based on nonparametric estimators of the regression function and explain main improvements over the previous work.Our investigation provides upper and lower bounds for the performance of proposed method over a broad class of underlying distributions.

Series: Stochastics Seminar

Various exact results in two-dimensional percolation are presented.
A method for finding exact thresholds for a wide variety of systems,
which greatly expands previously known exactly solvable systems to
such new lattices as "martini" and generalized "bowtie" lattices, is given.
The size distribution is written in a Zipf's-law form in terms of the enclosed-
area distribution, and the coefficient can be written in terms of the
the number of hulls crossing a cylinder. Additional properties of hull
walks (equivalent to some kinds of trajectories) are given. Finally,
some ratios of correlation functions are shown to be universal, with
a functional form that can be found exactly from conformal field theory.

Series: Stochastics Seminar

Deducing the state or structure of a system from partial, noisy
measurements is a fundamental task throughout the sciences and
engineering. The resulting inverse problems are often ill-posed because
there are fewer measurements available than the ambient dimension of the
model to be estimated. In practice, however, many interesting signals
or models contain few degrees of freedom relative to their ambient
dimension: a small number of genes may constitute the signature of a
disease, very few parameters may specify the correlation structure of a
time series, or a sparse collection of geometric constraints may
determine a molecular configuration. Discovering, leveraging, or
recognizing such low-dimensional structure plays an important role in
making inverse problems well-posed.
In this talk, I will propose a unified approach to transform notions of
simplicity and latent low-dimensionality into convex penalty functions.
This approach builds on the success of generalizing compressed sensing
to matrix completion, and greatly extends the catalog of objects and
structures that can be recovered from partial information. I will focus
on a suite of data analysis algorithms designed to decompose general
signals into sums of atoms from a simple---but not necessarily
discrete---set. These algorithms are derived in a convex optimization
framework that encompasses previous methods based on l1-norm
minimization and nuclear norm minimization for recovering sparse vectors
and low-rank matrices. I will provide sharp estimates of the number of
generic measurements required for exact and robust recovery of a variety
of structured models. These estimates are based on computing certain
Gaussian statistics related to the latent model geometry. I will detail
several example applications and describe how to scale the corresponding
inference algorithms to very large data sets.
(Joint work with Venkat Chandrasekaran, Pablo Parrilo, and Alan Willsky)

Series: Stochastics Seminar

In this talk we re-visit Fisher's controversial fiducial technique for
conducting statistical inference. In particular, a generalization of
Fisher's technique, termed generalized fiducial inference, is
introduced. We illustrate its use with wavelet regression. Current
and future work for generalized fiducial inference will also be
discussed.
Joint work with Jan Hannig and Hari Iyer

Series: Stochastics Seminar

We study the problem of testing for the significance of a subset of
regression coefficients in a linear model under the assumption that the
coefficient vector is sparse, a common situation in modern
high-dimensional settings. Assume there are p variables and let S be
the number of nonzero coefficients. Under moderate sparsity levels,
when we may have S > p^(1/2), we show that the analysis of variance
F-test is essentially optimal. This is no longer the case under the
sparsity constraint S < p^(1/2). In such settings, a multiple
comparison procedure is often preferred and we establish its optimality
under the stronger assumption S < p^(1/4). However, these two very
popular methods are suboptimal, and sometimes powerless, when p^(1/4)
< S < p^(1/2). We suggest a method based on the Higher Criticism
that is essentially optimal in the whole range S < p^(1/2). We
establish these results under a variety of designs, including the
classical (balanced) multi-way designs and more modern `p > n'
designs arising in genetics and signal processing.
(Joint work with Emmanuel Candès and Yaniv Plan.)

Series: Stochastics Seminar

For general graphs, approximating the maximum clique is a notoriously hard
problem even to approximate to a factor of nearly n, the number of vertices.
Does the situation get better with random graphs? A random graph on n
vertices where each edge is chosen with probability 1/2 has a clique of size
nearly 2\log n with high probability. However, it is not know how to find one
of size 1.01\log n in polynomial time. Does the problem become easier if a
larger clique were planted in a random graph? The current best algorithm can
find a planted clique of size roughly n^{1/2}. Given that any planted clique
of size greater than 2\log n is unique with high probability, there is a
large gap here. In an intriguing paper, Frieze and Kannan introduced a
tensor-based method that could reduce the size of the planted clique to as
small as roughly n^{1/3}. Their method relies on finding the spectral norm
of a 3-dimensional tensor, a problem whose complexity is open. Moreover,
their combinatorial proof does not seem to extend beyond this threshold. We
show how to recover the Frieze-Kannan result using a purely probabilistic
argument that generalizes naturally to r-dimensional tensors and allows us
recover cliques of size as small as poly(r).n^{1/r} provided we can find the
spectral norm of r-dimensional tensors. We highlight the algorithmic
question that remains open.
This is joint work with Charlie Brubaker.