30.08.15 - 04.09.15, Seminar 15361

Mathematical and Computational Foundations of Learning Theory

The following text appeared on our web pages prior to the seminar, and was included as part of the invitation.


Machine learning is nowadays a central field in computer science. Over the last decade the statistical learning approach has been successfully applied in many areas such as bioinformatics, computer vision, robotics and information retrieval, to name a few.

This is the second seminar on the mathematical and computational foundations of learning theory. Since the last seminar in 2011 new challenges have emerged largely motivated by the availability of data-sets of unprecedented size and complexity. It is now common in many applied domains of science and technology to have datasets with thousands and even millions data-points, features and attributes/categories. The need of analyzing and extracting information from this kind of data has posed a host of new challenges and open questions. The 2015 Dagstuhl seminar will thus have its focus on the efficient analysis of complex large scale data-sets. In particular, we will address the following topics:

Interplays between Optimization and Learning

While statistical modeling and computational aspects have for a long time been considered separate steps in the design of learning algorithms, dealing effectively with big data requires developing new strategies where statistical and computational complexities are taken simultaneously into account. In other words, the trade-off between optimization error and generalization error has to be exploited. On the other hand it has very recently been noticed that several non-convex NP-hard learning problems (sparse recovery, compressed sensing, dictionary learning, matrix factorization etc.) can be solved efficiently and optimally (in a global sense) under conditions on the data resp. the chosen model or under the use of additional constraints. The goal of this seminar will be the broad discussion of these two topics as well as possible connections between them.

Learning Data Representations

Data representation (e.g. the choice of kernels or features) is widely acknowledged to be the crucial step in solving learning problems. Provided with a suitable data representation, and enough labeled data, supervised algorithms, such as Support Vector Machines or Boosting, can provide good generalization performance. While data representations are often designed ad hoc for specific problems, availability of large/huge amount of unlabeled data has recently motivated the development of data driven techniques, e.g. dictionary learning, to adaptively solve the problem. Indeed, although novel tools for efficient data labeling have been developed (e.g. Amazon Mechanical Turk - mturk.com) most available data are unlabeled and reducing the amount of (human) supervision needed to effectively solve a task remains an important open challenge. While up-to-now the theory of supervised learning has become a mature field, an analogous theory of unsupervised and semi-supervised learning of data representation is still in its infancy and progress in the field is often assessed on a purely empirical basis. Thus we believe that the necessary next step is to build the foundations of representation learning on a firm theoretical ground.