PaperlayerView exact revision on arXiv

Source-linked AI summary

Do Not Let Privacy Overbill Utility: Gradient Embedding Perturbation for Private Learning

Da Yu, Huishuai Zhang, Wei Chen, Tie-Yan Liu

arXiv:2102.12677v3cs.LG

TL;DR

Dimension-scaled noise in gradient perturbation can overwhelm useful gradients and restrict deep-model utility. GEP projects private gradients into an anchor subspace and perturbs embeddings and residuals separately. It reports state-of-the-art utility across three benchmark datasets, including 74.9% test accuracy on CIFAR-10 at ε = 8.

  • Problem

    Gradient-perturbation noise scales with model dimension and can submerge useful gradients, limiting the utility of deep models.

    Source: §1 · pp. 1–2

  • Method

    GEP projects private gradients into a principal-component anchor subspace derived from non-sensitive auxiliary data, then perturbs the embeddings and residual gradients separately.

    Source: §1 · p. 2

  • Results

    GEP reports state-of-the-art utility on three benchmark datasets, including 74.9% test accuracy on CIFAR-10 at ε = 8.

    Source: §1 · pp. 2–3

  • Takeaways & Limitations

    GEP outputs an unbiased target-gradient estimator while reducing added noise, and experiments report superior utility.

    Source: §5 · p. 10

    A good bound on the maximum residual-gradient norm is difficult to obtain, and Theorem 3.3’s bound does not explicitly improve on previous results.

    Source: §3.3 · p. 8

Abstract

from arXiv · show

The privacy leakage of the model about the training data can be bounded in the differential privacy mechanism. However, for meaningful privacy parameters, a differentially private model degrades the utility drastically when the model comprises a large number of trainable parameters. In this paper, we propose an algorithm \emph{Gradient Embedding Perturbation (GEP)} towards training differentially private deep models with decent accuracy. Specifically, in each gradient descent step, GEP first projects individual private gradient into a non-sensitive anchor subspace, producing a low-dimensional gradient embedding and a small-norm residual gradient. Then, GEP perturbs the low-dimensional embedding and the residual gradient separately according to the privacy budget. Such a decomposition permits a small perturbation variance, which greatly helps to break the dimensional barrier of private learning. With GEP, we achieve decent accuracy with reasonable computational cost and modest privacy guarantee for deep models. Especially, with privacy bound $\epsilon=8$, we achieve $74.9\%$ test accuracy on CIFAR10 and $95.1\%$ test accuracy on SVHN, significantly improving over existing results.

1 INTRODUCTION

Gradient perturbation can let dimension-scaled noise overwhelm useful gradients in deep models. GEP separates gradients into an anchor-subspace embedding and a residual, and the authors report state-of-the-art utility across three benchmark datasets.

1 INTRODUCTION

  • Gradient perturbation noise scales with model dimension and can submerge useful gradients, restricting the utility of deep models.The introduction attributes this dimensional barrier to isotropic noise acting on gradients that lie on a low-dimensional manifold.Source: §1 · pp. 1–2
  • GEP computes anchor gradients on non-sensitive auxiliary data, projects private gradients into their principal-component subspace, then perturbs embeddings and residuals separately.The auxiliary data need only have features similar to those of the private data.Source: §1 · p. 2, Figure 3 · p. 3
  • Low-dimensional embeddings limit noise energy, while small-norm residuals permit lower noise for the same privacy level.Together, these properties allow lower perturbation than perturbing the original gradient directly.Source: §1 · p. 2
  • GEP requires only a small amount of non-sensitive unlabeled data with a similar feature distribution, and releases both perturbed components to produce an unbiased target-gradient estimator.The authors also report that power-method subspace estimation and insensitivity to subspace dimension enable efficient implementation.Source: §1 · p. 2
  • 74.9% test accuracy at ε = 8 is reported for GEP on CIFAR-10 with a ResNet20, as part of its reported state-of-the-art utility across three benchmark datasets.The authors also describe this as the first such utility from training deep models from scratch with a single-digit privacy budget.Source: §1 · pp. 2–3

1.1 RELATED WORK

  • Unlike concurrent gradient-reduction approaches, GEP perturbs residual gradients and produces an unbiased private-gradient estimator, which the authors identify as essential to its utility.Kairouz et al. (2020) track historical gradients for private AdaGrad, while Zhou et al. (2020) project noisy gradients into a public subspace at each update.Source: §1.1 · p. 3
  • Unlike PATE, GEP does not require auxiliary data to match the private-data distribution exactly; the authors report better performance especially on complex datasets such as CIFAR-10.PATE trains a student using noisy teacher predictions on public samples, whereas GEP trains on the whole private dataset rather than a small shard.Source: §1.1 · p. 3

2 PRELIMINARIES

The preliminaries establish notation, the neighboring-dataset basis for differential privacy, and the learning setup with auxiliary data whose features resemble those of the private data.

2 PRELIMINARIES

  • Vectors and matrices use bold notation, while vector L2, matrix spectral, and Frobenius norms are denoted by ∥v∥, ∥M∥, and ∥M∥F, respectively.A neighboring dataset differs by one sample.Source: §2 · pp. 3–4
  • Differential privacy bounds how much an algorithm’s output distribution can change between neighboring datasets, with ε and δ controlling the guarantee.The paper notes that privacy parameters trade off with utility and uses Rényi differential privacy to track loss before converting to (ε, δ)-DP.Source: §2 · p. 4
  • The learning setup uses feature-label samples to train a p-parameter model by minimizing empirical risk, alongside auxiliary data with similar features and potentially random labels.The auxiliary dataset is denoted D(a).Source: §2 · p. 4

3 GRADIENT EMBEDDING PERTURBATION

GEP uses a non-sensitive anchor subspace to split private gradients into low-dimensional embeddings and residuals, perturbing both separately; its analysis examines residual size and implications for private learning.

3.1 THE GEP ALGORITHM AND ITS PRIVACY ANALYSIS

  • GEP projects private gradients onto a principal-component anchor subspace, then separately perturbs the low-dimensional embeddings and residual gradients to form a gradient estimate.The anchor basis is estimated from non-sensitive auxiliary-data gradients using the power method.Source: §3 · p. 4, §3.1 · p. 4
  • The one-step mechanism clips embeddings and residuals separately and composes their privacy losses via Rényi differential privacy.The released perturbed components are combined by post-processing to construct the gradient estimate.Source: §3.1 · pp. 4–5
  • GEP needs only a small amount of non-sensitive, unlabeled auxiliary data with a similar feature distribution, and power iterations use standard matrix multiplication.Grouping parameters can further reduce the stated per-iteration computational complexity.Source: §3.1 · p. 5

3.2 AN ANALYSIS ON THE RESIDUAL GRADIENTS OF GEP

  • Under the stated low-rank conditions, residual gradients vanish once the number of anchor gradients exceeds the covariance rank; more anchors and a larger subspace also reduce residual norms.The analysis connects smaller residuals to lower clipping thresholds and less noise for the same privacy guarantee.Source: §3.2 · p. 6
  • Figure 5 reports that, for full-batch gradients in ResNet20’s first stage at k = 1000, residual-gradient stable rank is an order of magnitude higher than original-gradient stable rank.Projection error is small and decreases with k; random-labeled auxiliary data yield comparable projection error.Source: §3.2 · p. 6, Figure 5 · p. 7

3.3 PRIVATE LEARNING WITH GRADIENT EMBEDDING PERTURBATION

  • For gradients confined to k dimensions, expected excess error scales as O(k log(1/δ)/(nϵ)), independent of ambient dimension p; in general position, the stated bound does not explicitly improve over prior results.The authors note that bounding maximum residual norm is difficult; clipping based on expected residual norm would bias the output and require new guarantees.Source: §3.3 · p. 8

4 EXPERIMENTS

The experiments evaluate GEP against gradient perturbation and PATE across image datasets, and also test pretrained features and anchor-subspace dimensions. GEP improves over gradient perturbation, with strong CIFAR-10 accuracy at a stated privacy bound.

Experimental setup

  • Experiments use MNIST, extended SVHN, and CIFAR-10; the models are a small CNN for MNIST and ResNet20 for SVHN and CIFAR-10.For all datasets, anchor gradients come from 2,000 randomly labeled ImageNet samples.Source: §4 · pp. 8–9

Pre-trained models

  • 94.8% validation accuracy on CIFAR10 with ε = 2 using features from a model pre-trained on unlabeled ImageNet.This experiment evaluates GEP for private linear classifiers using pretrained features.Source: §4 · p. 8

Implementation and evaluation

  • Each GEP update releases normalized gradient-embedding and residual-gradient vectors together through a Gaussian mechanism, then rescales them; B-GEP releases only the embedding.The experiments compare GEP with GP and PATE; PATE's privacy parameter is data-dependent and cannot be released directly.Source: §4 · p. 8

Results

  • 74.9% test accuracy on CIFAR-10 with (8, 10^-5)-DP, outperforming GP by 18.5%; GEP improves over GP on all datasets, while PATE leads on MNIST.Table 1 reports test accuracy across privacy bounds, with Δ denoting improvement over GP.Source: §4 · p. 9, Table 1 · p. 9

Varying anchor-subspace dimension

  • GEP outperforms B-GEP for every tested k and is less sensitive to k, while accuracy gains diminish as k grows.Larger k has high memory cost because computing the anchor subspace requires storing at least k individual gradients.Source: §4 · p. 9, Figure 6 · p. 9

5 CONCLUSION

The conclusion presents GEP as a differentially private learning method that uses gradient redundancy to reduce added noise while producing an unbiased target-gradient estimator. Experiments on real-world datasets demonstrate its utility.

5 CONCLUSION

  • GEP leverages gradient redundancy to reduce added noise and outputs an unbiased estimator of the target gradient.The conclusion also reports that its key designs improve applicability and that experiments demonstrate superior utility.Source: §5 · p. 10

A EXPERIMENTS WITH PRE-TRAINED MODELS

The experiments apply GEP to a private linear classifier trained on features from an unlabeled-ImageNet-pretrained ResNet152. On CIFAR10, GEP outperforms gradient perturbation across the tested privacy bounds.

A EXPERIMENTS WITH PRE-TRAINED MODELS

B COMPLEXITY ANALYSIS

Constructing the anchor subspace is GEP's dominant additional computational cost relative to conventional gradient perturbation. Parameter grouping reduces the construction's computational and memory costs.

B COMPLEXITY ANALYSIS

  • Parameter grouping can significantly reduce the computational and memory costs of constructing GEP's anchor subspace.The approach divides parameters into g groups and computes one orthonormal basis for each group; Table 4 summarizes additional costs with and without grouping.Source: B COMPLEXITY ANALYSIS · p. 14, Table 4 · p. 15
  • Anchor-subspace construction is the dominant additional cost of GEP compared with conventional gradient perturbation.The analysis considers the costs of a single power iteration in Algorithm 1.Source: B COMPLEXITY ANALYSIS · p. 14, Table 4 · p. 15
  • The analysis assumes parameters and anchor-subspace dimension are divided evenly among the g groups.Here k, m, n, and p denote the subspace dimension, number of anchor gradients, number of private gradients, and model dimension, respectively.Source: B COMPLEXITY ANALYSIS · p. 14, Table 4 · p. 15

C ABLATION STUDY

The ablations examine auxiliary-data choices and size, and compare learned anchor subspaces with random bases. Correct-label CIFAR10 auxiliary data gives the worst accuracy, while random bases have high projection error.

C ABLATION STUDY

  • CIFAR10 auxiliary samples with correct labels yield the worst accuracy, while random labels yield the best; CIFAR100 or ImageNet samples have little effect.Accuracy is evaluated on 8000 CIFAR10 test samples not used as auxiliary data; Table 5 reports results under (8, 10^-5)-DP.Source: C ABLATION STUDY · p. 15, Table 5 · p. 15
  • Increasing the number of ImageNet auxiliary samples slightly improves test accuracy for both B-GEP and GEP.The comparison varies m on CIFAR10 under (8, 10^-5)-DP; Table 6 reports the results.Source: C ABLATION STUDY · p. 15, Table 6 · p. 15
  • Random basis vectors have projection error above 95% throughout training on CIFAR10 and SVHN.The paper notes that preserving pairwise distances is insufficient for high-quality gradient reconstruction, which requires preserving each gradient's average distance to the others.Source: C ABLATION STUDY · pp. 15–16, Figure 7 · p. 16

D MISSING PROOFS

The proofs establish privacy guarantees for GEP using sensitivity-based Gaussian perturbations and composition, and support a low-rank anchor-subspace result under stated assumptions.

D MISSING PROOFS

  • Under the low-rank covariance and distribution assumptions, the empirical covariance has rank k when m ≥ k, and its leading subspace matches the population subspace.The proof uses an extension of Theorem 3.2 in Eaton & Perlman (1973) and establishes k′ = k and equality of the spanned subspaces.Source: D MISSING PROOFS · p. 16
  • Algorithm 1 satisfies (ϵ, δ)-DP under the sensitivity-based noise choices stated in Theorem 3.1.The theorem applies for δ ∈ (0, 1) and ϵ ≤ 2 log(1/δ); its proof invokes Gaussian-mechanism and RDP composition results.Source: D MISSING PROOFS · pp. 16–17
  • The appendix states that Rényi differential privacy composes by adding its γ parameters at fixed λ and converts to (ϵ, δ)-DP using δ.The conversion bound given is ϵ = γ + log(1/δ)/(λ − 1).Source: D MISSING PROOFS · pp. 16–17
  • Algorithm 2 satisfies (ϵ, δ)-DP under the noise condition stated in Theorem 3.2.The supplied theorem states the range ϵ < 2 log(1/δ), with δ ∈ (0, 1); its proof composes per-call RDP guarantees.Source: D MISSING PROOFS · pp. 16–17

Related papers

Loading 2102.12677v3…