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

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 GS_f or ∂f), (ii) the minimum local sensitivity of f, i.e. min_x∈G LS_f(x), and (iii) the restricted sensitivity of f (denoted ∂_Hf or RS^H_f ). For Part 1a, also describe an explicit Lipschitz extension of f from H to all of G.
   • G = Rⁿ where x ∼ x⁰ if x and x⁰ differ on one row, H = [a,b]ⁿ for real numbers a ≤ b, and f(x) = (1/n)^Pn_i=1 x_i.
   • G = Rⁿ where x ∼ x⁰ if x and x⁰ differ on one row, H = [a,b]ⁿ for real numbers a ≤ b, and f(x) = median(x₁,…,x_n).
   • G = the set of undirected graphs (without self-loops) on vertex set {1,…,n} where x ∼ x⁰ if x and x⁰ 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⁻⁶), 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.