RUB » LMI » Forschung

Fields of Interest

We consider and analyze machine learning problems from the perspective of complexity theory. We try to determine the information or computational complexity of learning problems, and to design efficient learning algorithms. Furthermore, we investigate combinatorial optimization problems and explore the possibility of designing efficient approximation algorithms. We have a general interest in finding new programming methods and in inventing new data structures. We are furthermore interested in any results that shed more light on the famous P-NP problem.

"Cryptography in Ubiquitious Computing: Privacy-preserving Learning"

Graduiertenkolleg (GRK 1817) funded by the German Research Corporation (DFG)

"Privacy-Preserving Learning" is among the projects of GRK 1817. In this project, we are concerned with techniques that allow to perform statistical analysis of data in a privacy-preserving fashion. In particular, we investigate which statistical learning algorithms can be made privacy-preserving without much loss of efficiency (as opposed to the ones which inherently become inefficient). We furthermore study variations in the notion of privacy-preservation and analyze how they relate to each other. Within this project, which starts in the second half of 2012, we have Open Positions (PhD). The deadline for application is June 1, 2012 .

"Distribution-dependent and Distribution-independent Learnability"

Research Project funded by the Bilateral Research Programme
between Germany (DAAD 50751924) and Hungary (MÖB 14440)

In this project, we shall be concerned with the information complexity of learning, i.e., we pursue the question how much information a machine (an algorithm) requires in order to reach a certain learning goal. We shall focus on two models of learning, PAC-learning (introduced 1984 by Leslie Valiant) and SQ-learning (introduced 1993 by Michael Kearns). The former model forces the learner to extract information from correctly labeled random examples and to return a probably-approximately-correct (PAC) hypothesis. The latter model is a natural restriction of the former and leads to learning algorithms which are robust against classification noise. Our main research objective is to gain a deeper understanding of the advantage that could result from knowing in advance the probability distribution D underlying the random data. To this end, we distinguish between distribution-dependent learning (knowing D in advance) and distribution-independent learning (having no prior knowledge of D. We pursue the question whether there are smart strategies for learning algorithms without prior knowledge of D which enable them to compete well against the best learners with perfect prior knowledge. We are furthermore interested in narrowing the gap between the currently best known upper and lower bounds on information complexity in the models under consideration. As for the final phase of the project, we plan to design highly efficient smart learning algorithms for concrete concept classes. As explained in more detail in the proposal, the research in this project is likely to make significant contributions to an active and ongoing discussion concerning the power of semi-supervised algorithms.