# CS 208 HW 4B: Stochastic Gradient Descent and Lipschitz Extensions

35.00 \$

Category:
Click Category Button to View Your Next Assignment | Homework

You'll get a download link with a: . ` zip` solution files instantly, after Payment

## 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.

1. 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.
2. 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

[2] For some useful guidance, look at the class notes for April 8th at http://people.seas.harvard.edu/~salil/

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

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

• HW4b.zip