We will go over the fundamental techniques for designing differentially
private algorithms and techniques for proving lower bounds on the complexity of
such algorithms. In the last part of the seminar we will focus mainly on
differentially private machine learning algorithms. We will use the two
monographs:
· C. Dwork and A. Roth, The algorithmic
foundations of differential privacy, 2014 (I will refer to this book as DW
below)
· S. Vadhan, The
complexity of differential privacy, 2017,
and some additional paper. Lectures may depend on previous ones so it
is strongly recommended that you follow the material closely and read ahead
using these books.
I would like to meet each one of you at least a week before your
lecture (I recommend you do it as early as possible in case we need more than
one meeting or there are some difficult proofs to understand). We will go over
your planned lecture and your slides/notes.
I suggest you start reading your material as soon as possible, I am
available for any question you may have, either regarding the technical
material or regarding planning the parts you will deliver and how.
Schedule
1) (Oct 30) An
introductory lecture
2) (Nov 6) The Laplace and
Gaussian mechanisms, 3.3 and appendix A in DR, Gal
Sadeh
3) (Nov 13) The exponential mechanism and how
to answer linearly many queries (SMALLDB), 3.4 and 4.1
in DR, original texts: McSherry and K.Talwar. Mechanism Design
via Differential Privacy, FOCS
2007, and Blum, Ligett,
and Roth, A Learning Theory Approach to Differential Privacy, J. ACM 60(2): 2013,
Benjamin Doubior
4) (Nov 20) Composition theorem for differential
privacy, 3.5 and appendix B in DR, original texts: C. Dwork and J.
Lei, Differential Privacy and Robust Statistics STOC 2009, and C.
Dwork, G. N. Rothblum, and
S. P. Vadhan. Boosting and differential privacy FOCS
2010, Amir Hertz
5) (Nov 27) The sparse vector technique, 3.6 in DR, additional text: Lyu, Su and
Li, Understanding the Sparse Vector Technique for Differential Privacy. PVLDB 10(6): 637-648 (2017),
Roni Yasinnik
6)
(Dec 4)
Online
query release via private multiplicative weights, 4.2 in DR, original text: Hardt and Rothblum: A Multiplicative Weights Mechanism for
Privacy-Preserving Data Analysis, FOCS 2010, Omri
Keren
7)
(Dec
11) Offline
generalizations of the multiplicative weights algorithm, 5.2,5.3 in
DR and look also at the
references there, Saeed Esmail
8)
(Dec
18) When worst case
sensitivity is atypical, Chapter 7 in DR,
based on the original text: Nissim, Raskhodnikova, Smith, Smooth
Sensitivity and Sampling in Private Data Analysis, STOC 2007, Ori
Terner
9) (Dec 25) Lower bounds for differential privacy, Chapter 8
in DR and the references there, Gefen Keinan
10) Lower bounds using fingerprinting codes, Section 5.3
in the book of Vadhan, original text: Bun, Ullman, and Vadhan,
Fingerprinting Codes and the Price of Approximate Differential Privacy, SIAM J. Comput., 47(5) 2018
11) Differential privacy and computational
complexity, Chapter 9 in DR, Section 6 in Vadhan
12) (Jan 1) Kasiviswanathan, Lee, Nissim, Raskhodnikova, and Smith, What Can We Learn Privately, SIAM
J. Comput., 40(3) 2011, Or Shahaf
13) (Jan 8) Beimel, Brenner, Kasiviswanathan and Nissim, Bounds on
the sample complexity for private learning and private data release, Machine
Learning 94(3) 2014, Abed Khateeb