Improving the Privacy and Practicality of Objective Perturbation for Differentially Private Linear Learners

In the arena of privacy-preserving machine learning, differentially private stochastic gradient descent (DP-SGD) has outstripped the objective perturbation mechanism in popularity and interest. Though unrivaled in versatility, DP-SGD requires a non-trivial privacy overhead (for privately tuning the model's hyperparameters) and a computational complexity which might be extravagant for simple models such as linear and logistic regression. This paper revamps the objective perturbation mechanism with tighter privacy analyses and new computational tools that boost it to perform competitively with DP-SGD on unconstrained convex generalized linear problems. Preliminaries Differential Privacy Differential privacy (DP) (Dwork et al., 2006) offers provable privacy protection by restricting how much the output of a randomized algorithm can leak information about a single data point. DP requires a notion of how to measure similarity between datasets. We say that datasets Z and Z ′ are neighboring datasets (denoted Z ≃ Z ′ ) if they differ by exactly one datapoint z, i.e. Z ′ = Z ∪z or Z ′ = Z z for some data entry z. Definition 2.1 (Differential privacy). A mechanism M : Z → R satisfies (ϵ, δ)-differential privacy if for all neighboring datasets Z, Z ′ ∈ Z and output sets S ⊆ R, When δ > 0, M satisfies approximate DP. When δ = 0, M satisfies the stronger notion of pure DP. We say that M is tightly (ϵ, δ)-DP if there is no δ ′ < δ for which M would be (ϵ, δ ′ )-DP. In what follows, we overview two different styles of achieving DP guarantees: one via hockey-stick divergence, and the other via Rényi divergence. DP via hockey-stick divergence Definition 2.2 (Hockey-stick divergence). Denote [x] + = max0, x for x ∈ R. For α > 0 the hockey-stick divergence H α from a distribution P to a distribution Q is defined as Now (with some abuse of notation) we will discuss how to bound the hockey-stick divergence between distributions M(Z) and M(Z ′ ) via the concept of privacy profiles. Definition 2.3 (Privacy profiles Balle et al., 2018). The privacy profile δ M (ϵ) of a mechanism M is defined as Tight (ϵ, δ)-DP bounds can then be obtained as follows. Lemma 2. 4 (Zhu et al., 2022, Lemma 5) Dominating pairs of distributions are useful for bounding the hockey-stick divergence H e ϵ M(Z)||M(Z ′ ) accurately and, in particular, for obtaining tight bounds for compositions. Definition 2.5 (Zhu et al. 2022) . A pair of distributions (P, Q) is a dominating pair of distributions for mechanism M : Z → R if for all neighboring datasets Z and Z ′ and for all α > 0, H α (M(Z)||M(Z ′ )) ≤ H α (P ||Q).