Instructions: Submit a single PDF le containing your solutions, plots, and analyses. Make sure to thoroughly explain your process and results for each problem. Also include your documented code and a link to a public repository with your code (such as GitHub/GitLab). Make sure to list all collaborators and references.
For each of the following sets G of datasets and neighbor relations , hypotheses H G, and functions f : G ! R, calculate (i) the global sensitivity of f (denoted GSf or @f), (ii) the minimum local sensitivity of f, i.e. minx2G LSf (x), and (iii) the restricted sensitivity of f (denoted @Hf or RSHf). For Part 1a, also describe an explicit Lipschitz extension of f from H to all of G.
(a)
G =
R
n
x0 if x and x0
di er on one row, H = [a; b]n for real numbers a
b, and
n where x
f(x) = (1=n)
x .
di er on one row, H = [a; b]n for real numbers a
(b)
G = Rn wherePxi=1
x0i if x and x0
b, and
f(x) = median(x1; : : : ; xn).
G = the set of undirected graphs (without self-loops) on vertex set f1; : : : ; ng where x x0 if x and x0 are identical except for the neighborhood of a single vertex (i.e. node privacy), H = the set of graphs in G in which every vertex has degree at most d for a parameter 2 d n 1, and f(x) = the number of isolated (i.e. degree 0) vertices in x.
In our code example,1 we saw how to release an estimated Logistic regression using di erentially private stochastic gradient descent (DP-SGD) to optimize the log-likelihood loss function under
the centralized model. Convert this code to once again release the probability of marriage given education level, but using DP-SGD under the local model.2 Recall that local DP does not satisfy privacy ampli cation by subsampling, but you can achieve a similar e ect by rotating through
disjoint batches, so that each individual partipates in at most dT B=ne batches, where T is the number of iterations and B is the batch size.3 Evaluate the performance of your method as a function of ( xing = 1 10 6), by showing the classi cation error over , compared to the RMSE of the coe cients compared to the non-privacy preserving estimates.
See https://github.com/privacytoolsproject/cs208/blob/master/examples/wk7_localmodel/privateSGD. r and privateSGD.ipynb.
2For some useful guidance, look at the class notes for April 8th at http://people.seas.harvard.edu/~salil/ cs208/spring19/MLwithDP-lecture.pdf.
3Note, in the code example, T = pn; B = pn.
1
