263-4508-00: Algorithmic Foundations of Data Science - ETH Zürich
Computer Science
Official Description from ETH Zürich:
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.
Archived Document(s):
Preliminary 1: Linear Algebra & Calculus
Preliminary 2: Central Limit Theorem and the Gaussian Distribution
Preliminary 3: Concentration bounds
Preliminary 4: Convex optimization
Lecture note 1: Linear regression and ordinary least squares (open in new window)
Lecture note 2: Minimax lower bounds and Bayesian linear regression (open in new window)
Lecture note 5: Matrix completion and Bernstein tail bounds for matrices (open in new window)
Lecture note 6: Community detection in networks and Grothendieck’s inequality (open in new window)
Lecture note 7: Non-negative matrix factorization and topic models (open in new window)
Lecture note 8: Tensor decomposition: algorithms and applications (part 1) (open in new window)
Lecture note 9: Tensor decomposition: algorithms and applications (part 2) (open in new window)
Lecture note 10: Sum-of-squares for estimation problems (open in new window)
Lecture note 11: Clustering and Gaussian mixture models via sum-of-squares (open in new window)
Lecture note 12: Robust mean estimation (open in new window)