Theory of Differential Privacy

Course Info

Course Information

This course is an introduction to differential privacy as a foundational framework for reasoning about privacy in data analysis. Students will develop a principled understanding of why privacy risks arise when privacy is not an explicit design objective and how differential privacy enables formal, provable guarantees.

We will build on the algorithmic toolkit and statistical techniques for designing and analyzing differentially private methods, and study fundamental tradeoffs and lower bounds that characterize the limits of privacy.

Similar courses include Jonathan Ullman and Adam Smith's course at BU/NEU, Gautam Kamath's course at Waterloo.

Syllabus

Prerequisites

Students should be comfortable writing mathematical proofs involving algorithms, probability, and linear algebra. Introduction to Algorithms (601.433/633) satisfies this requirement; comparable theory coursework may be accepted with instructor approval.

Course Topics

• Privacy attacks; motivation for provable privacy.
• Differential privacy: definitions, variants, composition.
• Core mechanisms and algorithmic techniques, including Laplace, Gaussian, Exponential, and Binary Tree mechanisms.
• Differentially private optimization and machine learning, including DP-SGD, amplification by subsampling, and factorization mechanisms.
• Techniques beyond global sensitivity, including local sensitivity and propose-test-release.
• Fundamental limits and lower bounds, including fingerprinting and packing lower bounds.
• Advanced topics may include differentially private approaches for graphs, high-dimensional statistics, PAC learning, and connections between differential privacy and other trustworthy machine learning desiderata.

Course Expectations & Grading

In-class participation is required. There will be 3 homework assignments and a final project. The final grade will be computed based on the following weights:

• Homeworks: 50%
• Final Project: 30%
• Participation: 20%

Late assignments: each student has 4 late days (i.e. 96 hours) to use on homework assignments, not projects, over the course of the semester. Once late days are used, additional late submissions will not be accepted. If something serious comes up, contact the instructor as soon as possible to discuss options.

Collaboration and AI use: Please see the syllabus for course policies on collaboration, use of generative AI, and academic integrity.

Course Platforms

• Online discussion: Canvas
• Homework submission and grading: Gradescope (entry code: 68V2VK) via Canvas

Schedule

Topics and readings will be updated on the course webpage as the semester progresses.