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

35.00 $

Click Category Button to View Your Next Assignment | Homework

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


5/5 - (3 votes)

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,[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] 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/



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

  • HW4b.zip