This second-level graduate course provides a broad overview and develops the tools and methods needed to address large-scale problems arising in data science applications. This course is also offered as an elective for Degree level students

Pre-requisite: BSCS2007 : Machine Learning Techniques

Lectures-Tutorials-Practicals-Credits: 4-0-0-4

Week 1: Algorithms for data science; Concentration inequalities (Markov, Chebyshev, Hoeffding); Johnson-Lindenstrauss (JL) lemma foundations.

Week 2: JL lemma (proof and bounds); Linear algebra interpretation; Dimensionality reduction guarantees.

Week 3: Approximate nearest neighbors; Locality Sensitive Hashing (LSH); Hash design, collision analysis, TPR/FPR trade-offs.

Week 4: Singular Value Decomposition (SVD); Fast and randomized SVD; Applications in large-scale data.

Week 5: Clustering basics; Spectral clustering; Graph cuts and min-cut formulations.

Week 6: Scalable spectral clustering; Spectral sparsification; Large-scale clustering techniques.

Week 7: Statistical learning theory; Data distributions; Bayes classifier; Error decomposition.

Week 8: Generalization theory; Sample complexity; Bounds on learning performance.

Week 9: VC dimension; Hypothesis classes; Uniform convergence; Capacity of models.

Week 10: Learning theory recap; Estimation vs approximation error; Empirical risk minimization (ERM) and structural risk minimization (SRM); Sample compression.

Week 11: Data privacy fundamentals; Differential privacy.

Week 12: Approximate differential privacy; Exponential mechanism.