Georgia Institute of Technology College of Sciences

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.

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.

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.

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.