263-4508-00L  Algorithmic Foundations of Data Science

SemesterSpring Semester 2022
LecturersD. Steurer
Periodicityyearly recurring course
Language of instructionEnglish



Courses

NumberTitleHoursLecturers
263-4508-00 VAlgorithmic Foundations of Data Science3 hrs
Thu10:15-12:00CAB G 51 »
Fri12:15-13:00HG D 3.2 »
12:15-13:00ML F 36 »
D. Steurer
263-4508-00 UAlgorithmic Foundations of Data Science2 hrs
Fri13:15-15:00HG E 22 »
13:15-15:00ML F 36 »
D. Steurer
263-4508-00 AAlgorithmic Foundations of Data Science4 hrsD. Steurer

Catalogue data

AbstractThis course provides rigorous theoretical foundations for the design and mathematical analysis of efficient algorithms that can solve fundamental tasks relevant to data science.
ObjectiveWe 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.
ContentStrengths 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
Lecture notesTo be provided during the semester
LiteratureHigh-Dimensional Statistics
A Non-Asymptotic Viewpoint
by Martin J. Wainwright
Prerequisites / NoticeMathematical 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.

Performance assessment

Performance assessment information (valid until the course unit is held again)
Performance assessment as a semester course
ECTS credits10 credits
ExaminersD. Steurer
Typesession examination
Language of examinationEnglish
RepetitionThe performance assessment is only offered in the session after the course unit. Repetition only possible after re-enrolling.
Mode of examinationwritten 240 minutes
Additional information on mode of examinationDuring the course of the semester, we will assign two graded homeworks as compulsory continuous performance assessments, accounting together for 30% of the final grade (15% for each graded homework).
The written session examination accounts for the remaining 70% of the final grade.
Written aidsNone
This information can be updated until the beginning of the semester; information on the examination timetable is binding.

Learning materials

 
Main linkCourse Website
Only public learning materials are listed.

Groups

No information on groups available.

Restrictions

There are no additional restrictions for the registration.

Offered in

ProgrammeSectionType
CAS in Computer ScienceFocus Courses and ElectivesWInformation
Cyber Security MasterCore CoursesWInformation
Data Science MasterCore ElectivesWInformation
Computer Science MasterCore CoursesWInformation
Computer Science MasterMinor in Theoretical Computer ScienceWInformation