PaperlayerView exact revision on arXiv

Source-linked AI summary

Bypassing the Ambient Dimension: Private SGD with Gradient Subspace Identification

Yingxue Zhou, Zhiwei Steven Wu, Arindam Banerjee

arXiv:2007.03813v2cs.LGcs.CRstat.ML

TL;DR

DP-SGD’s error rate depends on ambient model dimension, which can be problematic when models have far more parameters than training examples. The paper proposes projecting noisy gradients onto a subspace estimated from public data. Its analysis and experiments report dimension-dependence reduction and empirical advantages over DP-SGD.

  • Problem

    DP-SGD’s error rate depends on ambient dimension p, a concern for over-parameterized models with p much greater than the number of training samples.

    Source: §1 · p. 2

  • Method

    PDP-SGD projects noisy gradients into an approximated gradient subspace identified using a public dataset.

    Source: §1 · pp. 2–3

  • Results

    PDP-SGD reduces the p factor in the error rate to the projection dimension and shows empirical advantages over DP-SGD on two popular deep-learning tasks.

    Source: §5 · pp. 12–13

  • Takeaways & Limitations

    Under the paper’s low-dimensional structure, projection offers a way to reduce dimension dependence without requiring fresh public samples at each iteration.

    Source: §5 · p. 12

    The proposed subspace identification relies on public data; identifying it privately without public data remains a direction for future work, with existing methods’ reconstruction error scaling as √p.

    Source: §5 · p. 13

Abstract

from arXiv · show

Differentially private SGD (DP-SGD) is one of the most popular methods for solving differentially private empirical risk minimization (ERM). Due to its noisy perturbation on each gradient update, the error rate of DP-SGD scales with the ambient dimension $p$, the number of parameters in the model. Such dependence can be problematic for over-parameterized models where $p \gg n$, the number of training samples. Existing lower bounds on private ERM show that such dependence on $p$ is inevitable in the worst case. In this paper, we circumvent the dependence on the ambient dimension by leveraging a low-dimensional structure of gradient space in deep networks -- that is, the stochastic gradients for deep nets usually stay in a low dimensional subspace in the training process. We propose Projected DP-SGD that performs noise reduction by projecting the noisy gradients to a low-dimensional subspace, which is given by the top gradient eigenspace on a small public dataset. We provide a general sample complexity analysis on the public dataset for the gradient subspace identification problem and demonstrate that under certain low-dimensional assumptions the public sample complexity only grows logarithmically in $p$. Finally, we provide a theoretical analysis and empirical evaluations to show that our method can substantially improve the accuracy of DP-SGD in the high privacy regime (corresponding to low privacy loss $\epsilon$).

1 Introduction

DP-SGD’s error can depend on model dimension, a concern for over-parameterized models. The paper proposes projecting noisy gradients into a subspace identified from public data and analyzes and evaluates the approach.

1 Introduction

  • DP-SGD’s error depends on ambient dimension p, which can hinder private ERM for models whose parameter counts greatly exceed the sample size.Existing lower bounds show this dependence is unavoidable in the worst case.Source: §1 · p. 2
  • The authors motivate this projection with observations that deep-network stochastic gradients often lie in a lower-dimensional subspace, illustrated by a gradient eigenvalue spectrum.Figure 1 plots eigenvalues in descending order for SGD and DP-SGD on MNIST.Source: §1 · p. 2, Figure 1 · p. 2
  • PDP-SGD projects noisy gradients onto a top-gradient eigenspace estimated from a public dataset, reducing noise and enabling higher accuracy.The projection uses the top-k eigenspace of gradients evaluated on public data.Source: §1 · pp. 2–3
  • The analysis bounds projection reconstruction error uniformly over possible iterates using generic chaining, with a bound scaling linearly in the γ2 complexity of the iterate set.Under empirically supported low-complexity examples, γ2 scales logarithmically with p.Source: §1 · p. 3
  • For convex and smooth non-convex losses, PDP-SGD improves the error-rate dependence from p to projection dimension k, with additional dependence on reconstruction error.The reconstruction error depends on γ2 and public-dataset size; the authors state their rates scale logarithmically in p under the discussed assumptions.Source: §1 · p. 3
  • Experiments on two real datasets report substantial accuracy improvement over DP-SGD using public datasets of 100 samples, while related methods differ in problem scope and public-data requirements.The authors contrast their convex and non-convex analysis with prior work and state that their experiments use at most 150 public samples, without fresh public samples at each iteration.Source: §1 · pp. 3–4

2 Preliminaries

The preliminaries formulate empirical risk minimization on private data and allow access to public data drawn from the same distribution. They define differential privacy, state the gradient assumptions, and note that an excessively large public dataset could make private data unnecessary.

2 Preliminaries

  • The setup minimizes empirical risk over a private sample and permits a public sample drawn from the same distribution without a privacy constraint.The public sample is denoted Sh and has size m.Source: §2 · p. 4
  • A public dataset large enough to train an accurate predictor may remove the need to use private data in the first place.This is stated as a practical concern about the public-data requirement.Source: §2 · p. 4
  • Differential privacy bounds how much an algorithm’s output distribution can change when one data point is replaced, and the analysis invokes Gaussian noise, subsampling amplification, and advanced composition.The definition is (ϵ, δ)-differential privacy.Source: §2 · p. 5
  • The gradient analysis assumes uniformly bounded gradient norms and gradients that are Lipschitz under a suitable pseudometric.These imply G-Lipschitzness of empirical risk, and ρ-smoothness when the pseudometric is ℓ2 distance.Source: §2 · p. 5

3 Projected Private Gradient Descent

PDP-SGD identifies a gradient subspace from a public dataset and projects noisy updates onto it. Its analysis bounds subspace error under reuse of that dataset and shows improved dimension dependence under stated gradient-structure conditions.

3 Projected Private Gradient Descent

  • At each iteration, PDP-SGD estimates the top-k eigenspace from public data, projects the noisy gradient into it, and uses that projected gradient for the parameter update.The projection is applied to the sum of the mini-batch gradient and Gaussian noise.Source: §3 · pp. 5–6

3.1 Gradient Subspace Identification

  • Because reusing public data makes iterates dependent on that data, generic chaining bounds second-moment deviation uniformly over possible iterates using γ2 complexity.The bound is expressed through the complexity of the parameter or population-gradient space.Source: §3.1 · pp. 6–8

3.2 Empirical Risk Convergence Analysis

  • For smooth non-convex losses, convergence of the full gradient norm additionally requires the principal component to dominate the residual component.The analysis first bounds the principal-component gradient norm.Source: §3.2 · p. 8
  • m=O(nε) public samples suffice when α_t decays as t^-1/4 for smooth non-convex objectives or t^-1/2 for convex objectives.These sample-size statements are given under the corresponding gradient-structure assumptions.Source: §3.2 · p. 9
  • PDP-SGD replaces the p dependence with k for convex and smooth non-convex objectives, relative to DP-SGD bounds [Bassily et al., 2014, 2019a] and prior non-convex bounds.The error bounds also include a subspace reconstruction term.Source: §3.2 · p. 9

4 Experiments

The experiments compare PDP-SGD with DP-SGD and random-projection DP-SGD on MNIST and Fashion MNIST across privacy settings. PDP-SGD outperforms DP-SGD in the lower-ε regimes, while its accuracy also varies with projection dimension, public sample size, and eigenspace-update frequency.

Experimental setup

  • Experiments use 10,000 private training samples and 100 public samples per dataset, with a convolutional network and 30 training epochs.The datasets are MNIST and Fashion MNIST; the public samples are drawn from the remaining original training data.Source: §4 · p. 10

Experimental Results

  • At ε≤0.42 on MNIST and ε≤0.72 on Fashion MNIST, PDP-SGD outperforms DP-SGD; RPDP-SGD usually does not improve over DP-SGD.For larger ε, the authors suggest subspace reconstruction error can dominate the injected-noise error.Source: §4 · p. 10, Figure 3 · p. 11
  • At ε=0.23 on MNIST and ε=0.30 on Fashion MNIST, training dynamics show PDP-SGD outperforming DP-SGD at large noise scales.The authors report validating this observation with larger training samples in Appendix D.Source: Figure 4 · p. 11, §4 · p. 11

Projection dimension and public sample size

  • For MNIST at ε=0.23, k=50 gives the best accuracy among tested dimensions, and accuracy improves as public sample size m increases from 50 to 150.The results also report similar performance for m=100 and m=150; k=50 is small relative to gradient dimension p≈25,000.Source: §4 · p. 11, Figure 5 · p. 12

Eigenspace computation frequency

  • With eigenspace updates every s={1, 10, 20} iterates, fewer updates mildly reduce PDP-SGD accuracy, but PDP-SGD still improves over DP-SGD.The comparison covers MNIST and Fashion MNIST; projection starts at the 15th epoch for Fashion MNIST.Source: Figure 6 · p. 12, §4 · p. 12

5 Conclusion and Future Work

The paper concludes that PDP-SGD reduces the ambient-dimension dependence in its error rate by projecting noisy gradients into an estimated low-dimensional subspace. It reports empirical advantages on two deep-learning tasks and identifies removing the need for public data as a direction for future work.

Conclusion

  • PDP-SGD projects noisy gradients into an approximated subspace estimated on public data, reducing the error-rate dependence on ambient dimension p to projection dimension k.The paper states that its subspace reconstruction error is small.Source: §5 · p. 12
  • The authors report empirical advantages of the proposed algorithms over DP-SGD on two deep-learning tasks.Source: §5 · p. 13

Future Work

  • Future work includes identifying gradient subspaces without public data, extending rank-dependent bounds beyond generalized linear problems, and characterizing problems with low-dimensional gradient subspaces.The proposed analyze-Gauss route would yield reconstruction error scaling with √p, which would propagate to optimization error.Source: §5 · p. 13

A Uniform Convergence for Subspaces: Proofs for Section 3.1

The appendix proves uniform convergence of the public-data second moment matrix and its top-k subspace along the training trajectory. Its bounds depend on the trajectory's γ2 complexity, or equivalently can be derived from the set of population gradients.

Proof overview

A.1 Uniform Convergence Bound

This appendix uses concentration and generic-chaining arguments to establish uniform control of empirical second moments and the resulting top-k subspaces. The subspace comparison uses an eigengap condition and a matrix perturbation result.

Uniform convergence bound

  • The proof treats the second-moment discrepancy along the parameter trajectory as a process and uses generic chaining to bound it uniformly.The argument invokes the Ahlswede-Winter inequality for concentration of bounded positive-semidefinite random matrices.Source: §A.1 · pp. 17, 20
  • Under Assumptions 1 and 2, the public-gradient second moment matrix approximates the population second moment matrix uniformly over iterations.The theorem states a probability bound with an absolute constant, but the supplied passage does not expose its full expression.Source: §A.1 · p. 20

Subspace closeness

  • The subspace result compares top-k eigenspaces of the empirical and population second moment matrices under an eigen-gap condition.The proof invokes Davis-Kahan to relate matrix approximation to subspace closeness.Source: §A.1 · p. 22

Uniform convergence bound

  • The analysis tracks the second-moment and subspace bounds over the set of possible training trajectories, with complexity governed by γ2.Source: §A.1 · p. 22

A.2 Geometry of Gradients and γ2 functions.

The section relates the γ2 complexity to covering numbers and Gaussian-process bounds, then uses gradient-space structure to obtain bounds for particular gradient sets. Mapping parameters to population gradients transfers the complexity analysis to that space.

A.2 Geometry of Gradients and γ2 functions

  • γ2 is related to log covering numbers but sharper, with generic chaining providing bounds on suprema of Gaussian processes indexed by the metric space [Theorem 2.4.1 in Talagrand [2014]].The passage describes chaining and hierarchical coverings as successive sharpening steps.Source: §A.2 · p. 24
  • Mapping each parameter to its population gradient makes the parameter-space γ2 complexity equal to the γ2 complexity of the population-gradient space.The mapping is f(w) = E_z[∇ℓ(w,z)], and the metric is measured between mapped gradients.Source: §A.2 · p. 24
  • For gradients contained in an ellipsoid with coordinate scales e, γ2 is bounded by a constant times the Gaussian width, which is itself bounded by a constant times ∥e∥2.The stated inequality is γ2(M, d) ≤ c1w(M) ≤ c2∥e∥2 [Talagrand, 2014].Source: §A.2 · p. 24
  • For a union of D gradient subsets, γ2 is bounded by √log D times the largest subset complexity; a union of p^s ellipsoids yields O(√(s log p)).The passage also gives an additive bound for Minkowski sums of gradient sets.Source: §A.2 · p. 24

B Proofs for Section 3.2

The proof section states a smooth, non-convex result for PDP-SGD under Assumptions 1 and 2, and considers an additional condition in which the principal gradient component dominates. It also relates the projected and residual parts of the empirical gradient in its proof.

B Proofs for Section 3.2

  • Theorem 4 gives a PDP-SGD guarantee for ρ-smooth empirical loss under Assumptions 1 and 2, with T = O(n^2ϵ^2) and step size ηt = 1/√T.The supplied theorem passages do not include the guarantee's bound.Source: B Proofs for Section 3.2 · p. 25
  • The analysis additionally considers the condition that the principal component of the gradient dominates.The condition is stated as an existence assumption, but its formula is not included in the supplied passage.Source: B Proofs for Section 3.2 · p. 25
  • The proof separates the empirical gradient into its projection onto the estimated top-k eigenspace and the residual outside that subspace.The projected component is written as ˆVk(t)ˆVk(t)⊺∇ˆLn(wt), with the remaining component defined by subtraction.Source: B Proofs for Section 3.2 · p. 27

C Error Rate of Convex Problems

For convex, G-Lipschitz losses, the section treats a rank-k population gradient second-moment matrix as a special case of principal-component dominance. It states a PDP-SGD guarantee under this low-rank condition.

C Error Rate of Convex Problems

  • The analysis assumes the population gradient second-moment matrix Σt has rank k, a special case of principal-component dominance with zero orthogonal gradient component.The passage specifies ∥[∇ˆLn(wt)]⊥∥2 = 0 for this special case.Source: C Error Rate of Convex Problems · p. 28
  • Theorem 5 states that PDP-SGD achieves a guarantee for G-Lipschitz convex empirical loss under Assumptions 1 and 2, with T = O(n^2ϵ^2).The supplied theorem passages omit the expression for the achieved bound.Source: C Error Rate of Convex Problems · p. 28
  • At each iteration, the update uses the empirical gradient projected onto the estimated top-k eigenspace.The update passage gives ˜gt = ˆVkˆVk⊺∇ˆLn(wt).Source: C Error Rate of Convex Problems · p. 28

D Experimental Setup and Additional Results

Experiments on MNIST and Fashion MNIST evaluate PDP-SGD against DP-SGD and explore projection dimension, public sample size, and eigenspace-update frequency. PDP-SGD improves accuracy in the low-privacy-loss regime, including with reduced eigenspace computation.

Experimental Setup

  • Both MNIST and Fashion MNIST have 60,000 training and 10,000 test examples; for MNIST, experiments use 10,000 randomly sampled private training examples and 100 additional public examples, with convolutional networks on both datasets.Source: D Experimental Setup and Additional… · p. 29
  • Training uses 30 epochs and batch size 250; privacy costs are calculated with the Moment Accountant at δ = 10^-5.The study repeats experiments three times and reports mean and standard deviation; it omits extensive fixed-ε hyperparameter tuning due to privacy-leakage risk.Source: D Experimental Setup and Additional… · pp. 30–31

Additional Results

Related papers

Loading 2007.03813v2…