Instructions: Submit a single PDF file 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. minx∈G 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.G = Rn where x ∼ x0 if x and x0 differ on one row, H = [a,b]n for real numbers a ≤ b, and f(x) = (1/n)Pni=1 xi. G = Rn where x ∼ x0 if x and x0 differ on one row, H = [a,b]n for real numbers a ≤ b, and f(x) = median(x1,...,xn). G = the set of undirected graphs (without self-loops) on vertex set {1,...,n} 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 differentially 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 [2] Recall that local DP does not satisfy privacy amplification by subsampling, but you can achieve a similar effect 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 (fixing δ = 1×10−6), by showing the classification error over , compared to the RMSE of the coefficients compared to the non-privacy preserving estimates. 1
[1] See https://github.com/privacytoolsproject/cs208/blob/master/examples/wk7_localmodel/privateSGD. r and privateSGD.ipynb.
[2] For some useful guidance, look at the class notes for April 8th at http://people.seas.harvard.edu/~salil/
