15-851: Algorithms for Big Data, Spring 2024
- Instructor: David Woodruff
- Lecture time: Thursdays, 2:10pm-4:50, GHC 4303
- TA: Honghao Lin
- David's office hours: Thursdays, 10am-11, GHC 7217, or by appointment
- Honghao's recitation: Fridays, 1-2pm ET, Wean 5403
- Honghao's office hours: Tuesdays, 4pm-5, GHC 9219
- Piazza site: https://piazza.com/class/lrdjqsyutmz68m
Grading
Grading is based on problem sets, scribing a lecture, and a presentation/project. There will be no exams.
General information about the breakdown for the grading is available
here:
grading.pdf
Latex
Homework solutions, scribe notes, and final projects must be typeset in LaTeX. If you are not familiar with LaTeX, see this introduction.
A template for your scribe notes is here:
template.tex
Lectures
- Lecture 1 slides,
video from previous year
(Least Squares Regression, Subspace Embeddings, Net Arguments)
Scribe Notes 1
Scribe Notes 2
- Lecture 2 slides,
video
(Matrix Chernoff, Subsampled Randomized Hadamard Transform, Approximate Matrix Product, CountSketch)
Scribe notes 3
Scribe notes 4
- Lecture 3 slides,
video
(CountSketch, Affine Embeddings)
Scribe notes 5
Scribe notes 6
- Lecture 4 slides , video (Low Rank Approximation, Sketching-based Preconditioning)
Scribe notes 7
Scribe notes 8
- Lecture 5 slides,
video (Distributed Low Rank Approximation, L1 Regression)
Scribe notes 9
Scribe notes 10
- Lecture 6 slides,
video,
(L1 Regression, Streaming)
Scribe notes 11
Scribe notes 12
- Lecture 7 slides,
video (Streaming)
Scribe notes 13
Scribe notes 14
- Lecture 8 slides
second half of this video and
first half of this video (Information Theory and Streaming Lower Bounds)
Scribe notes 15
Scribe notes 16
- Lecture 9 slides
this video up to and including indexing with low error and
this entire video (Streaming Lower Bounds and Algorithms)
Scribe notes 17
Scribe notes 18
- Lecture 10 slides
this video up to and including reducing counter size and
start with projection onto other objects (L0 Estimation, Gaussian Width, Compressed Sensing)
Scribe notes 19
Scribe notes 20
- Lecture 11 slides
video
(Adversarially robust streaming algorithms)
Scribe notes 21
Scribe notes 22
Honghao's Recitation Materials (see piazza)
Problem sets
Course Description
With the growing number of massive datasets in applications such as machine learning and numerical linear algebra, classical algorithms for processing such datasets are often no longer feasible. In this course we will cover algorithmic techniques, models, and lower bounds for handling such data. A common theme is the use of randomized methods, such as sketching and sampling, to provide dimensionality reduction. In the context of optimization problems, this leads to faster algorithms, and we will see examples of this in the form of least squares regression and low rank approximation of matrices and tensors, as well as robust variants of these problems. In the context of distributed algorithms, dimensionality reduction leads to communication-efficient protocols, while in the context of data stream algorithms, it leads to memory-efficient algorithms. We will study some of the above problems in such models, such as low rank approximation, but also consider a variety of classical streaming problems such as counting distinct elements, finding frequent items, and estimating norms. Finally we will study lower bound methods in these models showing that many of the algorithms we covered are optimal or near-optimal. Such methods are often based on communication complexity and information-theoretic arguments.
References
One recommended reference book is the lecturer's monograph
Sketching as a Tool for Numerical Linear Algebra.
This course was previously taught at CMU in the following links. In Fall 2020, all lectures were recorded with Panopto, which you have access to:
Fall 2017
Fall 2019
Fall 2020
Fall 2021
Fall 2022
Some videos from a shorter version of this course I taught are available here:
videos . Note that mine start on 27-02-2017.
Materials from the following related courses might be useful in
various parts of the course:
Intended audience: The course is indended for both graduate students and advanced undegraduate students with mathematical maturity and comfort with algorithms, discrete probability, and linear algebra. No other prerequisites are required.
Maintained by David Woodruff