263-4508-00L Algorithmic Foundations of Data Science

Semester	Frühjahrssemester 2022
Dozierende	D. Steurer
Periodizität	jährlich wiederkehrende Veranstaltung
Lehrsprache	Englisch

Kurzbeschreibung	This course provides rigorous theoretical foundations for the design and mathematical analysis of efficient algorithms that can solve fundamental tasks relevant to data science.
Lernziel	We consider various statistical models for basic data-analytical tasks, e.g., (sparse) linear regression, principal component analysis, matrix completion, community detection, and clustering. Our goal is to design efficient (polynomial-time) algorithms that achieve the strongest possible (statistical) guarantees for these models. Toward this goal we learn about a wide range of mathematical techniques from convex optimization, linear algebra (especially, spectral theory and tensors), and high-dimensional statistics. We also incorporate adversarial (worst-case) components into our models as a way to reason about robustness guarantees for the algorithms we design.
Inhalt	Strengths and limitations of efficient algorithms in (robust) statistical models for the following (tentative) list of data analysis tasks: - (sparse) linear regression - principal component analysis and matrix completion - clustering and Gaussian mixture models - community detection
Skript	To be provided during the semester
Literatur	High-Dimensional Statistics A Non-Asymptotic Viewpoint by Martin J. Wainwright
Voraussetzungen / Besonderes	Mathematical and algorithmic maturity at least at the level of the course "Algorithms, Probability, and Computing". Important: Optimization for Data Science 2018--2021 This course was created after a reorganization of the course "Optimization for Data Science" (ODS). A significant portion of the material for this course has previously been taught as part of ODS. Consequently, it is not possible to earn credit points for both this course and ODS as offered in 2018--2021. This restriction does not apply to ODS offered in 2022 or afterwards and you can earn credit points for both courses in this case.