CSE 711 - Spring 2017 - Topics in Differential Privacy


Location: Davis 113A
Time: Thursday 4:40 - 7:00
Instructor: Marco Gaboardi
e-mail: gaboardi@buffalo.edu

Office Hours: Friday 11:00 - 12:00 or by appointment
Discussion forums: NB and Piazza
Reading material: The Algorithmic Foundations of Differential Privacy (DR); The Complexity of Differential Privacy (SV)

Overview

This will be a graduate level seminar-style course introducing differential privacy and some of its applications. Differential privacy is a promising approach to the privacy-preserving release of data: it offers a strong guaranteed bound on the increase in harm that a user incurs as a result of participating in a differentially private data analysis. Several mechanisms and software tools have been developed to ensure differential privacy for a wide range of data analysis tasks, such as combinatorial optimization, machine learning, answering distributed queries, etc. In this class we will focus on some fundamental results about the theory and practice of differential privacy and how to use it in concrete applications. Part of the course will also focus on the use of differential privacy for purposes different from protecting privacy like for instance as a technique to prevent false discoveries in experimental science. The course will consist of readings on advanced topics in differential privacy and applications.

Course description

This will be seminar-style course where each student will present part of the material on differential privacy and applications. 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). Students are expected to read and comment the presented material previous to class by using NB. 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.

Grading

The grading will be based on the presentation of one paper, participation in class and in the NB and Piazza discussions. The project is optional and will not contribute to the grade.
The final grade will be composed as:

  • 50% Presentation of the material in class,
  • 50% Engagement and participation in class, on NB, and on Piazza,
  • 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.

    Schedule

    Date Topic Presenter
    2/02 Course Overview and Introduction to Differential Privacy
    SV 1.1-1.4, DR 2.3.0, 3.2
    Marco Gaboardi
    Class introduction
    Notes
    2/09 Randomized Response revisited, Laplace Mechanism.
    SV 1.5, DR 3.3
    Marco Gaboardi
    2/16 Generalization of Laplace, examples, Report Noisy Max
    DR 3.3
    Marco Gaboardi
    2/23 Exponential Mechanism, Composition.
    DR 3.4, SV 1.6 (first paragraph), 2.2
    Di
    3/02 The Sparse Vector Technique
    DR 3.6
    Saurabh and Vidhi
    3/09 Guest Lecture Georgios Kellaris
    3/16 No class
    3/23 No class - Spring Break
    3/30 Small DB algorithm
    DR 4.1 - SV 4.1
    Akshay and Sucheta
    4/06 Private Multiplicative Weights Algorithm
    DR 4.2 - SV 4.2
    Saani and Vanshika
    4/13
    4/20
    4/27
    5/04
    5/11