Scientific report: Theoretical Foundations for Learning from Easy Data

Maria-Florina Balcan, Shai Ben-David, Peter Grünwald, Gábor Lugosi, Csaba Szepesvári


Description and aims

Under a wide range of conditions learning becomes easier than in the worst-case, either computationally, or information-theoretically. Examples of such conditions include margin conditions in classification, exp-concavity of the losses in sequence prediction and perturbation robustness for clustering. Recent years have seen a dramatic development of ideas related to exploiting “easy data” (which is the data that would arise under such conditions).


The main goal of the workshop was to get an overview of these developments across various subfields of machine learning, ranging from supervised, through reinforcement to unsupervised learning so as to deepen our understanding of these conditions, with the ultimate aim of furthering the development of algorithms that simultaneously exploit easy situations while still being close to worst-case optimal.



To achieve this goal, we had several tutorial talks by world-class experts in the relevant subfields. These speakers – who were chosen because of their reputation as excellent communicators - consistently did an outstanding job in providing overviews of the key results and techniques in their respective fields, as well as in pointing out key similarities and differences between the various subproblems. We felt that all participants learned a lot.


Apart from the tutorials, we had several short contributed talks about cutting-edge research, both by some of the most senior people in both fields and by some ‘up-and-coming’, highly promising junior researchers. We should also note that almost all invitees accepted our invitation, resulting in stimulating discussions during and after the presentations, and allowing participants to get a good overview of the subject matter. We feel that all participants have a much better overview of ‘easy data’ conditions and how they relate in superficially unrelated applications such as clustering, supervised learning etc.


Scientific developments

Several participants told us afterwards that they really enjoyed both the workshop contents and its organization. Given all this, we consider the workshop a major success – where we emphasize that the main underlying reason for the success is the Lorentz Center concept itself with its excellent facilities and extremely friendly and capable staff, which allowed not only the participants but also the organizers to focus on science with no distractions. A second reason seems to have been the composition of the group - the right mix of junior and senior researchers. Whereas we initially had plans to create working groups etc., it turned out to be unnecessary and we decided not to: right after the first few talks people started working together in small groups, in some cases until late at night.


We would like to acknowledge the support we received via the  European Research Council

under ERC Grant Agreement 320637 (advanced ERC Grant Prof. Dr. A. van der Vaart).