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

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

√

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

• HW4b.zip