CSE 660 - Fall 2018 - Differential Privacy


Location: Davis 113A (starting from the second class)
Time: Tu-Th 11:00-12:20
Instructor: Marco Gaboardi
e-mail: gaboardi@buffalo.edu

Office Hours: R 2-4pm or by appointment.
Discussion forums: Piazza
Reading material: The Algorithmic Foundations of Differential Privacy (DR); The Complexity of Differential Privacy (SV)

Overview

This course is intended for students interested in data privacy, with a particular focus on differential privacy, and some applications. The course will introduce students to differential privacy which is becoming a standard approach to the privacy-preserving release of data. Differential privacy offers a strong guaranteed bound on the increase in harm that a user may incur as a result of participating in a differentially private data analysis. This course will focus on some fundamental results about the theory and practice of differential privacy and how to use it in concrete applications. In particular, the class will introduce students to the basic properties of differential privacy and to some of the fundamental mechanisms for building differentially private programs. Moreover, the course will present applications of differential privacy to a wide range of data analysis tasks, such as machine learning, answering distributed queries, statistical analysis and adaptive data analysis.

Course description

The course consists of a series of lectures on different topics in differential privacy and applications divided in two main parts. The first part of the class will focus on the basic methods to achieve differential privacy: methods based on global sensitivity, composition schemes for differential privacy, methods that use alternatives to global sensitivity, methods based on correlated noise. The second part of the class will focus on different models: differential privacy in the streaming model, multiparty models for differential privacy and some relations of differential privacy with complexity, statistics, machine learning, and adaptive data analysis.

Course prerequisites

The course has a significant component based on analysis of algorithms, so CSE 531 is a prerequisite. Additionally, some rudimentary understanding of probability and statistics is expected.

Course requirements

The course has two main requirements:

Grading

The grading will be based on assignments, participation in class, and project.
The final grade will be composed as:

  • 50% Assignments,
  • 10% Participation,
  • 40% Project,

    • Projects

    Projects can take different forms depending on the interest of each student but all the project must have a research component. Some examples of what would constitute a good project are:

  • design of a new differentially private algorithm for a specific task
  • design or implementation of (part of) a new programming language, system, or tool for differential privacy
  • implementation of a previously published work and an experimental comparison with other works with similar targets,
  • investigate new applications of differential privacy

    • The instructor will provide some specific ideas for possible projects after the first class but other ideas may be accepted if well motivated and discussed with the instructor. Students may work on their projects alone or they may collaborate with others. Groups can be composed by at most two students. Each group is invited to meet with the instructor regularly (3-4 times during the term) to check on the advancements and directions of the project.

    Class material

    The class will be based on the book The Algorithmic Foundations of Differential Privacy (DR) and on the notes The Complexity of Differential Privacy (SV). Every student will also be invited to engage on a project and to present the results at the end of the course. Discussion about all the aspects of the course will also take place on Piazza.

    Schedule

    Date Topic Notes
    T 8/28 Course Overview and Introduction to Differential Privacy
    		 Slides
    R 8/30 Counting Queries and Reconstruction attacks
    SV 1.3, DR 8.1
    T 9/04 Counting Queries and Reconstruction attacks
    SV 1.3, DR 8.1
    R 9/6 No Class
    T 9/11 Definition of Differential Privacy
    DR 2, SV 1.4
    R 9/13 Randomized Response
    DR 3.2, SV 1.5
    T 9/18 Laplace Mechanism, Resilience to Post-Processing, Group Privacy
    DR 2.3 - 3.3, SV 1.5, 2.1
    R 9/20 Basic Composition
    DR 3.5, SV 2.2, 2.3
    T 9/25 Histograms, Report Noisy Max
    DR 3.3, SV 2.3
    R 9/27 The Exponential Mechanism
    DR 3.4
    T 10/02 The Sparse Vector technique
    DR 3.6
    R 10/04 The Sparse Vector technique accuracy
    DR 3.6
    T 10/09 The SmallDB algorithm
    DR 4.1
    R 10/11 The MWEM algorithm
    DR 4.2
    T 10/16 The MWEM algorithm, The DualQuery algorithm
    DR 4.2
    R 10/18 DP vs Blatantly non-privacy
    DR 4.2
    T 10/23 Adaptive MWEM, DualQuery
    DR 4.2 SV 4.2
    R 10/25 Advanced Composition
    SV 2.2
    T 10/30 Gaussian Mechanism
    DR Appendix A
    R 11/01 zero-Concentrated Differential Privacy, Renyi Differential Privacy
    T 11/06 Multiparty DP
    SV 9.1-9.2
    R 11/08 Multiparty DP
    SV 9.1-9.2
    T 11/13 Alternatives to Global Sensitivity
    SV 3
    R 11/15 Alternatives to Global Sensitivity
    SV 3
    T 11/20 Thanksgiving - No Class
    R 11/22 Thanksgiving - No Class
    T 11/27 Alternatives to Global Sensitivity
    SV 3
    R 11/29 Alternatives to Global Sensitivity
    SV 3
    T 12/04 Summary
    R 12/06 Project Presentations (10am-1pm)