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

Series: Stochastics Seminar

We analyze active learning algorithms, which only receive the classifications of examples when they ask for them, and traditional passive (PAC) learning algorithms, which receive classifications for all training examples, under log-concave and nearly log-concave distributions. By using an aggressive localization argument, we prove that active learning provides an exponential improvement over passive learning when learning homogeneous linear separators in these settings. Building on this, we then provide a computationally efficient algorithm with optimal sample complexity for passive learning in such settings. This provides the first bound for a polynomial-time algorithm that is tight for an interesting infinite class of hypothesis functions under a general class of data-distributions, and also characterizes the distribution-specific sample complexity for each distribution in the class. We also illustrate the power of localization for efficiently learning linear separators in two challenging noise models (malicious noise and agnostic setting) where we provide efficient algorithms with significantly better noise tolerance than previously known.

Series: Stochastics Seminar

We consider two approaches to address angles between random subspaces: classical random matrix theory and free probability. In the former, one constructs random subspaces from vectors with independent random entries. In the latter, one has historically started with the uniform distribution on subspaces of appropriate dimension. We point out when these two approaches coincide and present new results for both. In particular, we present the first universality result for the random matrix theory approach and present the first result beyond uniform distribution for the free probability approach. We further show that, unexpectedly, discrete uncertainty principles play a natural role in this setting. This work is partially with L. Erdos and G. Anderson.

Series: Stochastics Seminar

The classical Freidlin--Wentzell theory on small random
perturbations of dynamical
systems operates mainly at the level of large deviation estimates. In many
cases it would be interesting
and useful to supplement those with central limit theorem type results. We
are able to describe a class of situations where a Gaussian scaling limit
for the exit point of conditioned diffusions holds. Our main tools are
Doob's h-transform and new gradient estimates for Hamilton--Jacobi
equations. Joint work with Andrzej Swiech.

Series: Stochastics Seminar

We show that on any Riemannian manifold with the Ricci curvature non-negative we can construct a coupling of two Brownian motions which are staying fixed distance for all times. We show a more general version of this for the case of Ricci bounded from below uniformly by a constant k. In the terminology of Burdzy, Kendall and others, a shy coupling is a coupling in which the Brownian motions do not couple in finite time with positive probability. What we construct here is a strong version of shy couplings on Riemannian manifolds. On the other hand, this can be put in contrast with some results of von Renesse and K. T. Sturm which give a characterization of the lower bound on the Ricci curvature in terms of couplings of Brownian motions and our construction optimizes this choice in a way which will be explained. This is joint work with Mihai N. Pascu.

Series: Stochastics Seminar

The Kardar-Parisi-Zhang(KPZ) equation is a non-linear stochastic partial
di fferential equation proposed as the scaling limit for random growth
models in physics. This equation is, in standard terms, ill posed and
the notion of solution has attracted considerable attention in recent
years. The purpose of this talk is two fold; on one side, an
introduction to the KPZ equation and the so called KPZ universality
classes is given. On the other side, we give recent results that
generalize the notion of viscosity solutions from deterministic PDE to
the stochastic case and apply these results to the KPZ equation. The
main technical tool for this program to go through is a non-linear
version of Feyman-Kac's formula that uses Doubly Backward Stochastic
Differential Equations (Stochastic Differential Equations with times
flowing backwards and forwards at the same time) as a basis for the
representation.

Series: Stochastics Seminar

Wigner stated the general hypothesis that the distribution of
eigenvalue spacings of large complicated quantum systems is universal in
the sense that it depends only on the symmetry class of the physical system
but not on other detailed structures. The simplest case for this hypothesis
concerns large but finite dimensional matrices. Spectacular progress was
done in the past two decades to prove universality of random matrices
presenting an orthogonal, unitary or symplectic invariance. These models
correspond to log-gases with respective inverse temperature 1, 2 or 4. I
will report on a joint work with L. Erdos and H.-T. Yau, which yields
universality for log-gases at arbitrary temperature at the microscopic
scale. A main step consists in the optimal localization of the particles,
and the involved techniques include a multiscale analysis and a local
logarithmic Sobolev inequality.

Series: Stochastics Seminar

References

[1] S. Arlot and P. Massart. Data-driven calibration of penalties for least-squares regression. J. Mach. Learn.

Res., 10:245.279 (electronic), 2009.

[2] L. Birgé and P. Massart. Minimal penalties for Gaussian model selection. Probab. Theory Related Fields,

138(1-2):33.73, 2007.

[3] Vladimir Koltchinskii. Oracle inequalities in empirical risk minimization and sparse recovery problems,

volume 2033 of Lecture Notes in Mathematics. Springer, Heidelberg, 2011. Lectures from the 38th Prob-

ability Summer School held in Saint-Flour, 2008, École d.Été de Probabilités de Saint-Flour. [Saint-Flour

Probability Summer School].

[4] Pascal Massart. Concentration inequalities and model selection, volume 1896 of Lecture Notes in Math-

ematics. Springer, Berlin, 2007. Lectures from the 33rd Summer School on Probability Theory held in

Saint-Flour, July 6.23, 2003, With a foreword by Jean Picard.

The systematical study of model selection procedures, especially since the early nineties, has led to the
design of penalties that often allow to achieve minimax rates of convergence and adaptivity for the selected
model, in the general setting of risk minimization (Koltchinskii [3], Massart [4]).
However, the proposed penalties often su.er form their dependencies on unknown or unrealistic constants.
As a matter of fact, under-penalization has generally disastrous e.ects in terms of e¢ ciency. Indeed, the model
selection procedure then looses any bias-variance trade-o. and so, tends to select one of the biggest models in
the collection.
Birgé and Massart ([2]) proposed quite recently a method that empirically adjusts the level of penalization
in a linear Gaussian setting. This method of calibration is called "slope heuristics" by the authors, and is
proved to be optimal in their setting. It is based on the existence of a minimal penalty, which is shown to be
half the optimal one.
Arlot and Massart ([1]) have then extended the slope heuristics to the more general framework of empirical
risk minimization. They succeeded in proving the optimality of the method in heteroscedastic least-squares
regression, a case where the ideal penalty is no longer linear in the dimension of the models, not even a function
of it. However, they restricted their analysis to histograms for technical reasons. They conjectured a wide
range of applicability for the method.
We will present some results that prove the validity of the slope heuristics in heteroscedastic least-squares
regression for more general linear models than histograms. The models considered here are equipped with
a localized orthonormal basis, among other things. We show that some piecewise polynomials and Haar
expansions satisfy the prescribed conditions.
We will insist on the analysis when the model is .xed. In particular, we will focus on deviations bounds for
the true and empirical excess risks of the estimator. Empirical process theory and concentration inequalities
are central tools here, and the results at a .xed model may be of independent interest.

Series: Stochastics Seminar

In recent work, an idea of
Adam Jakubowski
was used to prove infinite stable limit theory and
precise large deviation results
for sums of strictly stationary regularly varying sequences.
The idea of Jakubowski consists of approximating tail probabilities
of distributions for such sums with increasing index
by the corresponding quantities
for sums with fixed index. This idea can also be made to work for
Laplace functionals of point processes, the distribution function of
maxima and the characteristic functions of partial sums of stationary
sequences. In each of these situations, extremal
dependence manifests in the appearance of suitable cluster indices
(extremal index for maxima, cluster index for sums,...). The proposed method
can be easily understood and has the potential to function as heuristics for
proving limit results for weakly dependent heavy-tailed sequences.

Series: Stochastics Seminar

Recall that the notion of generalized function is introduced for the functions that are not defined point-wise, and is given as a linearfunctional over test functions. The same idea applies to random fields.In this talk, we study the long term asymptotics for the quenchedexponential moment of V(B(s)) where B(s) is d-dimensional Brownian motion,V(.) is a generalized Gaussian field. We will discuss the solution to anopen problem posed by Carmona and Molchanov with an answer different fromwhat was conjectured; the quenched laws for Brownian motions inNewtonian-type potentials, and in the potentials driven by white noise orby fractional white noise.

Series: Stochastics Seminar

1-bit compressed sensing combines the dimension reduction
of compressed sensing with extreme quantization -- only the sign of
each linear measurement is retained. We discuss recent
convex-programming approaches with strong theoretical guarantees. We
also discuss connections to related statistical models such as sparse
logistic regression.
Behind these problems lies a geometric question about random
hyperplane tessellations. Picture a subset K of the unit sphere, as
in the continents on the planet earth. Now slice the sphere in half
with a hyperplane, and then slice it several times more, thus cutting
the set K into a number of sections. How many random hyperplanes are
needed to ensure that all sections have small diameter? How is the
geodesic distance between two points in K related to the number of
hyperplanes separating them? We show that a single geometric
parameter, the mean width of K, governs the answers to these
questions.