Master Of Fundamental Computer Science

Lecturers

Aurélien Garivier, Rémi Gribonval

Course description

This course will introduce the notion of Differential Privacy, a formal model for guaranteeing the withholding of personal information in databases in data analytics.
This notion, rooted in cryptography as well as in information theory, deploys its own properties: starting Warner's Randomized Response, we will study the most important ones, together with the most successful mechanisms and composition possibilities. First elaborating on the examples of the mean and the median, we will discuss the Exponential mechanism, Sensibility and Inverse sensibility, Laplacian noise, then Gaussian noise and L2-sensitivity and privacy amplification. After that, we will be able to address more general learning problems with differentially private stochastic gradient descent and federated learning, insisting on the example of neural networks. Finally, we will invoke f-Differential Privacy and advanced composition properties, together with their interpretations in hypothesis testing.
The course will be only partly based on Dwork's and Roth's reference textbook, since we will develop a statistical point of view where the object of interest is not a sample's statistic, but a population's parameter. This point of view will emphasize, wherever possible, the possibility of a trade-off between privacy, statistical accurracy of estimation, and computational complexity.

Prerequisite

Notions of Machine Learning, elementary probability and statistics.

Bibliography

1. The Algorithmic Foundations of Differential Privacy, by Cynthia Dwork and Aaron Roth, Foundations and Trends in Theoretical Computer Science. Vol. 9, no. 3–4, pp. 211‐407, Aug. 2014
2. Near instance-optimality in differential privacy, by H Asi, JC Duchi, arXiv preprint arXiv:2005.10630

Evaluation

Three homeworks count for 50% in total of the final note: they will be progressively available on the portail des études. The projet on a research article will give the other 50%.

Project: paper / chapter presentation

EXPECTED WORK
a/ Written document: half a page summary

Written in French or English, on half a page, in the format of the summary of a conference paper describing the topic, its stakes, the difficulties, novelties, and main results.

Writing style, grammar and spelling must be done with care.

b/ Video presentation and slides

15-minutes lecture to be made available to the course lecturers as a video recording, paying attention to ensuring a balanced share of time highlighting the participation of each student of the group.

PDF version of slides with page numbers to be made available to the course lecturers.

Each student is invited to watch the videos of the other groups before the oral session.

Mandatory participation of all students to the oral session to answer questions from the course lecturers.

It is important to respect the allotted duration of the video lecture : do not hesitate to use a timer!

A limited duration lecture cannot contain the same information as a 20 to 30 pages paper / chapter : you have to make choices to bring us a viewpoint on the addressed topic. Roughly count 1 minute 30 per slide, and seek a good balance between giving a global view and being technically precise on selected aspects.

Adapting the content to the expected background of the targeted audience is important: here the audience consists of the course lecturers as well as all the students who followed the course.

As an example, a standard lecture structure can be as follows: considered problem and its context; state of the art approaches and/or approaches studied during the course; proposed approach; synthesis and discussion, possibly highlighting your own contributions (critical perspective, complementary bibliographical study, implementation, difficulties …) ; conclusion.

Among other things, the grade will reflect an evaluation of:

Your understanding of the topic and of the studied papers / chapters.
Your ability to explain them: many persons in the audience are not necessarily experts.
Your critical analysis of the studied papers / chapters.
Possible complementary bibliographical references bringing additional viewpoints.

PLANNED PRACTICALITIES

Submission of written + video material : via « portail des études » if technically adapted

Oral session: on site if possible, otherwise in hybrid mode or by videoconf (BBB of “portail des études”)

Details will be given as soon as possible according to technical and sanitary constraints.