Statistical and Computational Hardness of Learning

What it is about

You learn when and why certain learning tasks have fundamental limits on data — both due to too little/noisy data (statistical hardness) and due to computational intractability in polynomial time (computational hardness). In the end you can analyze and assess these limitations for hypothesis testing, sparse linear regression and high-dimensional/graph-based clustering problems.

What you will be able to do

• analyze statistical and computational limits of learning problems
• combine and apply statistical and theoretically-informed computer science techniques
• principally develop new methods with regard to statistical and computational limits

What the module consists of

• LecturePresentation of theoretical frameworks and results; introduction and proof of statistical concepts
• Exercise/Tutorialweekly sessions with example problems for application and derivation of results
• Script/SlidesDeepening of lecture content and discussion of the development of new methods

Teaching method

• Blackboard lecture and lecture scriptPresentation of key frameworks and proofs; conveyance of theoretical concepts (ILO 1, ILO 2)
• SlidesDiscussion and illustration of the development of new methods (ILO 3)
• Weekly exercise sessionsApplication of theory to example problems and derivation of new theoretical results (ILO 1–3)
• Moodleasynchronous discussions and provision of teaching materials