BS - One World Probability Seminar

Speakers: Daniel Bartl  (National University of Singapore), Stanislav Minsker (University of Southern California)

Title: On the role of Rademacher complexities in statistical learning
Abstract: We study the problem of learning with respect to the squared loss over a convex class of functions. It has long been believed that the sample complexity in this setting is governed by localized Rademacher complexities. We show that, assuming access to coarse information on the covariance structure of the model class, the sample complexity is instead controlled by a localized complexity associated with the limiting Gaussian process. In heavy-tailed regimes, this quantity can be significantly smaller than the Rademacher complexity.

Title: Tukey’s median and its extensions: new deviation bounds and efficiency
Abstract: Is there a natural way to order data in dimension greater than one? The approach based on the notion of half-space depth, often associated with the name of John Tukey, is among the most popular. Tukey’s depth has found applications in robust statistics, the study of elections and social choice, and graph theory. We will give an introduction to the topic, with an emphasis on robust statistics, describe the remaining open questions as well as our recent progress towards their solutions. In particular, we will (i) discuss performance guarantees for Tukey’s median that depend on the “intrinsic” dimension of the problem expressed via the effective rank of the covariance matrix, and (ii) introduce the Hodges-Lehmann inspired version of Tukey’s median and some of its surprising asymptotic properties. Along the way, we mention new tools from the theory of strong approximation as well as U-processes that could be of independent interest.