Asymptotic Geometric Analysis and Learning Theory

We will study parameters that govern the complexity of a learning problem, which turns out to be determined by the geometry of certain sets in high dimension (random coordinate projections of the given class). The resulting analysis leads to many theoretical questions in Asymptotic Geometric Analysis, Probability and Combinatorics, which are of independent interest beyond the application to Learning Theory. Our main goal is to describe the role of various complexity parameters involved in a learning problem, to analyze the connections between them and to investigate the way they determine the geometry of the relevant high dimensional sets.