A Differential Privacy and Generalization Analysis

A.1 Proof of Lemma 1 By applying Theorem 8 from [11] to gradient computation, we obtain Lemma 1. Lemma 1. Let A be an ( null,δ)-differentially private gradient descent algorithm with access to training set S of size n . Proof Theorem 8 in [11] shows that in order to achieve generalization error τ with probability 1 ρ for an ( null,δ) -differentially private algorithm (i.e., in order to guarantee for every function φ Then according to the post-processing property of differential privacy (Proposition 2.1 in [14]) we have B A is also The part A (DPG-Lap) uses the basic tool from differential privacy, the "Laplace Mechanism" (Definition 3.3 in [14]). The Laplace Mechanism adds i.i.d. Laplace noise to each coordinate of the output.