MCS 549: Mathematical Foundations of Data Science

Spring 2021

Basic Information

Instructor: Aditya Potukuchi

Time: MWF 2:00PM-2:50PM CST, online

Office Hours: Monday, Friday 3:00PM-4:00PM or by appointment

Basic info handout

Problem set 1

Problem set 2

Problem set 3

Problem set 4

Schedule

Jan 11: Introduction, intro to SVD, Reading: Chapter 3.1-3.4

Jan 13: SVD contd.., Reading: Chapter 3.6

Jan 15: SVD contd, PCA, Reading: Chapter 3.5, 3.9

Jan 20: Algorithms for SVD, Reading: Chapter 3.7

Jan 22: Algorithms for SVD contd.., Basics of Probability

Jan 25: Introduction to Markov Chains and Random Walks, Reading: Chapted 4 intro, Chaper 4.1

Jan 27: Stationary distribution, Fundamental Theorem of Markov Chains, Reading, Chapter 4.1

Jan 29: Conductance, Mixing time, Reading: Chapter 4.4

Feb 1: Bounding mixing time based on conductance I, Reading: Theorem 4.5

Feb 3: Bounding mixing time based on conductance II, Reading: Theorem 4.5

Feb 5: Metropolis-Hastings algorithm, Reading: Chapter 4.2

Feb 8: Chernoff bound, Volume computation, Reading: Chapter 4.3

Feb 10: Random walks and electrical networks, Reading: Chapter 4.5

Feb 12: Hitting time and Cover time of random walks, Reading: Chapter 4.6

Feb 15: Intro to dimensionality reduction, Gaussians in high dim, Reading: Chapter 2.4

Feb 17: Gaussian Annulus Theorem, Reading: Chapter 2.6

Feb 19: Johnson-Lindenstrauss Lemma, Reading: Chapter 2.6, Theorem 2.10

Feb 22: Gaussian tail bound, Intro to random graphs, Probabilistic method, Reading: Chapter 8.1

Feb 24: Intro to Erdos-Renyi random graphs, triangle counts, Reading: Chapter 8.1.2

Feb 26: Second moment method, thresholds, and sharp thresholds, Reading: Chapter 8.3

Mar 1: Sharp threshold for connectivity, Reading: Chapter 8.3, Theorem 8.6

Mar 3: Connectivity, phase transition intro, Reading: Chapter 8.3, Theorem 8.6, Theorem 8.5

Mar 8: Phase transition in random graphs, intro to Spectral Graph Theory, Reading: Chapter 8.3

Mar 10: Crash course in Spectral Graph Theory

Mar 12: Intro to Sketching, and Streaming, Reading: Chapter 6.1

Mar 15: Hash functions, counting distinct elements in a stream, Reading: Chapter 6.2.1

Mar 17: Crash course in probabilistic analysis of randomized algorithms

Mar 19: Frequency moments in a stream, Reading: Chapter 6.2.4

Mar 22, 24, 26: NO CLASS: Spring break

Mar 29: Introduction to Clustering, Lloyd's algorithm, Reading: Chapter 7.1, 7.2.2

Mar 31: Lloyd's algorithm contd.., Intro to Spectral Clustering, Reading: Chapter 7.2.3, 7.3

Apr 2: Spectral Clustering contd.., Intro to Stochastic Block Model, Reading: Chapter 7.5.1, 7.5.2

Apr 5: Stochastic Block Model contd.., Approximation Stability, Reading: Chapter 7.5.3, 7.6

Apr 7: Intro to topic modelling, Reading: Chapters 9.1, 9.2

Apr 9: Topic modelling in an idealized model, intro to Nonnegative Matrix Factorization, Reading: Chapters 9.2, 9.3

Apr 12: Nonnegative Matrix Factorization, Reading: Chapter 9.3

Apr 14: Intro to Learning Theory, PAC learning, Reading: Chapters 5.1, 5.4

Apr 16: Basic generalization bounds for realizable learning, Reading: Chapter 5.4

Apr 19: Generalization for agnostic learning, intro to VC-dimension, Reading: Chapter 5.5

Apr 21: Generalization for classes with low VC dimension, Reading: Chapter 5.5