## Description

**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 GSor_{f }*âˆ‚f*), (ii) the minimum local sensitivity of*f*, i.e. min_{x}_{âˆˆ}_{G }LS(_{f}*x*), and (iii) the restricted sensitivity of*f*(denoted*âˆ‚*_{H}*f*or RS^{H}). For Part 1a, also describe an explicit Lipschitz extension of_{f }*f*from H to all of G.- G = R
where^{n }*x*âˆ¼*x*^{0 }if*x*and*x*^{0 }differ on one row, H = [*a,b*]for real numbers^{n }*a*â‰¤*b*, and*f*(*x*) = (1*/n*)^{Pn}_{i}_{=1 }*x*._{i} - G = R
where^{n }*x*âˆ¼*x*^{0 }if*x*and*x*^{0 }differ on one row, H = [*a,b*]for real numbers^{n }*a*â‰¤*b*, and*f*(*x*) = median(*x*_{1}*,…,x*)._{n} - G = the set of undirected graphs (without self-loops) on vertex set {1
*,…,n*} where*x*âˆ¼*x*^{0 }if*x*and*x*^{0 }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*.

- G = R
- 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 d*T*Â·*B/n*e 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/

cs208/spring19/MLwithDP-lecture.pdf.

âˆš Â Â Â Â Â Â Â Â Â âˆš

[3] 3Note, in the code example, *T *=Â Â Â Â Â Â Â Â Â Â Â Â Â Â *n, B *=Â Â Â Â Â Â *n*.