CS-GY 9223
Statistical and Computational Foundations of Machine Learning
Spring 2023
Sundays 5:00pm—7:30pm in in Jacobs Academic Building, Room 473


I do not have an office at NYU. I work from home. I come to NYU only to give lectures. If you need to contact me, please email me and/or arrange a Zoom or Google Hangouts call. Office hours are on Zoom.

Course description

In this course you will learn the theoretical foundations of machine learning. We will explain how a machine learning algorithm can make accurate predictions on unseen data. This property is called generalization. We develop a statistical theory of generalization for prediction problems. Along the way we analyze some popular machine learning methods (support vector machines, boosting, perceptron, stochastic gradient descent, decision trees, neural networks, k-nearest neighbor). Besides generalization properties of machine learning algorithms, we will look also at their computational complexity and computational hardness of the underlying optimization problems.

The class will be completely theoretical. In lectures, I will give definitions and prove theorems. In homeworks and exams, I will ask you to solve mathematical problems and prove theorems. You will NOT do any coding, you will NOT do any data analysis, and you will NOT build any machine learning models.

Course syllabus

Course Prerequisites

You must have taken courses in probability theory, linear algebra, and algorithms. You will benefit from prior exposure to machine learning (ML) (e.g. introductory ML course, neural network course, statistical inference course, practical experience). However, knowledge of ML is not a prerequisite. I will give a brief introduction to ML in the first lecture.

Probability theory.
Random variables, discrete and continuous probability distributions, expectation, variance, correlation, covariance, independence, Bernoulli, binomial and Gaussian distributions, law of large numbers.
Linear algebra.
Vector spaces, subspaces, inner products, Cauchy-Schwarz inequality, norms, triangle inequality, linear functions, matrices, vector-matrix multplication, matrix multplication, orthogonal matrices, eigen values, eigen vectors.
Arrays, dictionaries, sorting, searching, time and memory complexity, big O and big Omega notation, basics of NP-completeness.

I expect you to know one-dimensional calculus (limits, infimum, supremum, continuity, derivatives and integrals), mathematical notation (sets, functions, logical formulas), and elementary combinatorics (combinations, permutations, binomial coeficients). You must be comfortable doing mathematical proofs.

Course structure and grading

Homeworks (40% of grade)
There will be 4 homework sets. You should spend significant amount of time working on the homeworks. You can work in small groups and/or consult other materials or people. However, in your solution you have to list members of your group, all the materials used and all people you consulted. Type your solutions in LaTeX, print them out, and hand in them in class.
Midterm exam (30% of grade)
Midterm exam will take place in place one of the lectures, roughly in the middle of the semester. The questions will have the same format as the the homework problems. You can bring and use any amount of printed materials (notes, books, research papers). However, you cannot use any device connected to the internet (phones, tablets, computers).
Final exam (40% of grade)
Final exam will take place during the final period, at the same time as the class. The format of the final exam will be exactly the same as the midterm exam.

Note that the total percentage adds up to 110%. That means you can make up lost points. If you want to do well in the course, make sure to submit solutions to all homework problems.


There is one 2.5 hour class meeting per week, divided by a 15 minute break. In accordance with NYU guidelines, you must wear a mask covering your face and nose whenever you are attending lecture.


Your solution must be turned both by email and as a printed out hard-copy in class by the due date. Send emails to david.pal@nyu.edu with subject "Homework #?". Use LaTeX and submit your solution as a PDF file. Use the following template.

PDF LaTeX source Handout date Due date Graded by Solution PDF Solution LaTeX source
Homework #0 PDF LaTeX source January 23 January 31 February 5
Homework #1 February 5 February 19 February 26
Homework #2 February 19 March 5 March 12
Homework #3 March 26 April 9 April 16
Homework #4 April 9 April 23 April 30

Tentative course schedule

I am hoping to cover the topics listed below. Additional topics (k-nearest neighbor, support vector machines, neural networks) might be added if time permits.

Week 1 January 29 Generalization error, Test error, Optimal Bayes classifier Chapters 1,2,3
Week 2 February 5 Empirical Risk Minimization (ERM), Overfitting, PAC model with finite hypothesis class, Concentration inequalities, Hoeffding's bound, No free lunch Chapters 2,3,4; Appendix B
Week 3 February 12 Hoeffding's bound, PAC model, No free lunch theorem Chapters 3,4,5; Appendix B
Week 4 February 19 VC dimension, Sauer's lemma, Radon's theorem, VC dimension of halfspaces, epsilon-nets, epsilon-approximations Chapter 6
Week 5 February 26 epsilon-nets, epsilon-approximations, sample complexity upper and lower bounds Chapters 6,28
Week 6 March 5 Measure theory, Upper bound on the sample complexity for Agnostic PAC model Chapters 6, 28
Week 7 March 12 Midterm exam
Week 8 March 19 Spring break — No lectures
Week 9 March 26 Non-uniform learning and computational complexity of learning Chapters 7, 8
Week 10 April 2 Online learning model, Halving algorithm, Mistake bound, Perceptron, Winnow, Online-to-batch conversion Chapter 21
Week 11 April 9 Hedge, Perceptron, Online-to-batch conversion, Boosting Chapters 21, 10
Week 12 April 16 Boosting, Decision trees Chapters 10, 18
Week 13 April 23 Least squares, logistic regression, convex learning problems Chapters 9, 12
Week 14 April 30 Convex learning problems, stability, regularization Chapters 12, 13
Week 15 May 7 Regularization stability, Online gradient descent, stochastic gradient descent Chapters 13, 14
Week 16 May 14 Final exam

Course Policies


Your solution must be turned both by email and as a printed out hard-copy in class by the due date. Send emails to david.pal@nyu.edu with subject "Homework #?". Use LaTeX and submit your solution as a PDF file. Use the following template.

Collaboration is allowed on homework, but solutions must be written independently. If you use external sources (books, online documents), list them in your solutions.

Grade changes

Fair grading is important to me. If you feel that you were incorrectly docked points on an assignment or exam, please let me know - it is very possible I or the TAs misunderstood your work. Do not wait until the end of the semester to bring up grading issues! If you notice something off, please ask ASAP.

Questions about performance

If you are struggling in the class, contact me as soon as possible so that we can discuss what’s not working, and how we can work together to ensure you are mastering the material. It is difficult to address questions about performance at the end of the semester, or after final grades are submitted: by Tandon policy no extra-credit or makeup work can be used to improve a students grade once the semester closes. So if you are worried about your grade, seek help from me early.


Midterm and Final will be open-book written exams. They will be 2.5 hours long.

You can bring and use any amount of printed or hand-written material you want (hand-written or printed notes, cheat sheets, textbooks, lecture notes, research papers, etc.) All materials you use have to be in paper form. Use of electronic devices will not be allowed. This includes computers, laptops, tablets, e-readers, smartphones, smart-watches, headphones, calculators, etc.

Any communication with anybody inside or outside the classroom during the exam will be stricly prohibited. Passing of any materials or objects from one student to another will not be allowed. If you would like to have a cheat sheet or notes from your classmate, make sure to get a copy before the exam.

Bring pens, pencils, and extra paper for writing. You can bring ruler and compass if you want, but they will not be necessary or useful. I will bring extra writing paper as well. Calculators of any kind will not be allowed. You will have to do all your calculations on paper.

You can bring drinks and food to the exam.

Learning materials


Other materials