PaperlayerView exact revision on arXiv

Source-linked AI summary

Large Scale Private Learning via Low-rank Reparametrization

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

arXiv:2106.09352v4cs.LGcs.CR

TL;DR

Large-model differentially private SGD faces high memory costs from storing individual gradients and noise that scales with model size. RGP uses low-rank gradient carriers and historical updates for private learning; it reports 83.9% average BERT downstream accuracy at ε=8, within 5% loss of the non-private baseline.

  • Problem

    Applying gradient perturbation to large models requires storing individual gradients and incurs noise whose intensity scales with model size.

    Source: §1 · pp. 1–2

  • Method

    RGP reparameterizes weights with low-rank gradient carriers and a residual weight, perturbs carrier gradients, and uses historical updates to choose the carriers.

    Source: §1 · p. 2

  • Results

    83.9% average accuracy on BERT downstream tasks at ε=8 was within 5% loss compared with the non-private baseline.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The authors conclude that RGP can train BERT on several downstream tasks with a differential privacy guarantee and small accuracy loss.

    Source: §7 · p. 9

    The complexity analysis specifies costs for one square fully connected layer per update, with minibatch size m, power iterations K, and reparameterization rank r.

    Source: §3.3 · p. 5

Abstract

from arXiv · show

We propose a reparametrization scheme to address the challenges of applying differentially private SGD on large neural networks, which are 1) the huge memory cost of storing individual gradients, 2) the added noise suffering notorious dimensional dependence. Specifically, we reparametrize each weight matrix with two \emph{gradient-carrier} matrices of small dimension and a \emph{residual weight} matrix. We argue that such reparametrization keeps the forward/backward process unchanged while enabling us to compute the projected gradient without computing the gradient itself. To learn with differential privacy, we design \emph{reparametrized gradient perturbation (RGP)} that perturbs the gradients on gradient-carrier matrices and reconstructs an update for the original weight from the noisy gradients. Importantly, we use historical updates to find the gradient-carrier matrices, whose optimality is rigorously justified under linear regression and empirically verified with deep learning tasks. RGP significantly reduces the memory cost and improves the utility. For example, we are the first able to apply differential privacy on the BERT model and achieve an average accuracy of $83.9\%$ on four downstream tasks with $\epsilon=8$, which is within $5\%$ loss compared to the non-private baseline but enjoys much lower privacy leakage risk.

1. Introduction

Applying gradient perturbation to large deep models requires storing individual gradients and adds noise whose intensity scales with model size. The paper proposes RGP, using low-rank gradient carriers and historical updates, and reports BERT downstream accuracy of 83.9% at ε=8 within 5% loss of the non-private baseline.

1. Introduction

  • RGP addresses gradient-perturbation challenges on large models: storing individual gradients and noise intensity that scales with model size.Each individual gradient requires as much memory as the model itself.Source: §1 · pp. 1–2
  • RGP reparameterizes each weight matrix with low-rank gradient carriers and a residual weight, preserving forward and backward signals while enabling projected-gradient computation without computing the full gradient.The projected gradient can be reconstructed from carrier gradients, potentially reducing memory use when individual gradients are needed.Source: §1 · p. 2
  • RGP clips and perturbs carrier gradients, then uses their noisy values to construct an update for the original weight.The carriers' smaller dimensions reduce the total intensity of added noise.Source: §1 · p. 2
  • Historical updates provide approximate principal-subspace vectors for the carriers; their optimality is proved for linear regression and their efficacy is empirically verified for deep networks.The approach uses published historical updates rather than private current gradients to find principal vectors.Source: §1 · p. 2
  • 83.9% average accuracy on BERT downstream tasks at ε=8 was within 5% loss compared with the non-private baseline.The models were also significantly more robust to membership inference attacks than non-private models.Source: §1 · p. 2

2. A Reparametrization Scheme

The scheme reparameterizes each weight matrix using low-rank gradient carriers and a residual weight, preserving forward and backward signals while changing gradient computation. It extends the same reparameterization to convolutional layers.

2. A Reparametrization Scheme

  • The residual weight preserves the original weight matrix while the gradient carriers change how its gradient is computed.The scheme leaves forward and backward signals unchanged.Source: §2 · p. 2
  • With orthonormal carriers, the gradients on L and R yield a projection of the weight gradient into their row and column subspaces.This projected gradient can be computed without explicitly computing or storing the full weight gradient.Source: §2 · p. 3
  • Because the private gradient cannot be directly decomposed, the scheme uses historical updates to choose L and R and argues this choice is optimal under certain conditions.The proposed carriers approximate principal vectors from historical updates.Source: §2 · p. 3
  • Replacing W with L and R would reduce expressive power and could hurt optimization, whereas the proposed reparameterization preserves the forward and backward processes.The passage also notes that layer widths vary dramatically and signals may not propagate well with common initialization strategies.Source: §2 · p. 3

2.1. Reparametrization for Convolutional Layers

  • For convolutional layers, the kernel and feature dimensions are flattened into a matrix so the same reparameterization can be applied.R and L are implemented as consecutive convolutions, with the residual weight implemented using the original kernel size.Source: §2.1 · p. 3

3. Private Deep Learning with Reparametrized Gradient Perturbation

RGP trains with differential privacy by perturbing low-dimensional gradient-carrier gradients and reconstructing updates for the original weights. It reduces individual-gradient memory, with a trade-off between carrier rank, approximation error, and noise.

3.1. Reparametrized Gradient Perturbation Algorithm

  • RGP chooses gradient carriers from historical updates, clips and perturbs their individual gradients, then reconstructs an update for the original weights.A warm-up phase decomposes the weight, and the power method approximates principal components; Gram–Schmidt orthonormalizes the carriers.Source: §3.1 · pp. 3–4
  • Smaller carrier rank reduces noise energy but increases approximation error, so RGP trades off these factors when choosing rank.Carrier matrices must align with principal gradient components and have orthonormal columns or rows for reconstruction.Source: §3.1 · p. 4

3.2. Privacy Analysis of RGP

  • Proposition 3.1 gives Algorithm 1 an (ϵ, δ)-differential privacy guarantee under its stated conditions.The derivation uses the moments accountant to compose privacy costs across updates.Source: §3.2 · p. 4

3.3. Complexity Analysis of RGP

  • RGP's individual-gradient memory scales linearly with width d, versus d² for DP-SGD, despite extra carrier-activation storage.Table 1 summarizes computation and memory costs; no cell values are supplied here.Source: Table 1 · p. 5, §3.3 · p. 5
  • RGP adds computation for power iteration, Gram–Schmidt orthonormalization, and carrier operations during forward and backward propagation.For the stated square-layer setup, the respective overheads are O(Krd²), O(Kr²d), and O(mrd).Source: §3.3 · p. 5

4. Two Properties of the Gradient Matrix

The section motivates low-rank carriers with two gradient properties: gradients have low stable rank, and their subspaces can remain aligned over optimization. Deep-network evidence is empirical, while the shared-subspace argument is rigorously justified for linear regression.

4.1. Gradient Matrix Is of Low Stable Rank

  • BERT and ResNet gradients are naturally low stable-rank during training, suggesting small carrier matrices can approximate them if the right subspace is found.The experiments use SST-2 for BERT and CIFAR-10 for wide ResNet.Source: §4.1 · p. 5

4.2. Historical Gradients Are Correlated

  • Historical and self projection residuals differ little for BERT and ResNet, indicating alignment between current and historical gradient subspaces.The comparison uses the current gradient and the previous epoch's gradient; Figure 3 uses rank 8 and a fixed batch of 500 samples.Source: §4.2 · p. 6, Figure 3 · p. 6
  • A rank-r gradient can be represented through an intrinsic subspace of dimension r(p + d), rather than the full pd parameters, reducing gradient-perturbation memory and noise effects.The subspace may be identified approximately by the algorithm or using auxiliary public data.Source: §4.2 · p. 6
  • In deep networks, low stable rank and roughly stable gradient subspaces are empirically observed, not rigorously established because layers co-adapt.The authors report better utility and lower memory cost than DP-SGD from exploiting this observed structure.Source: §4.2 · p. 6
  • For least-squares linear regression, Proposition 4.1 supports the possibility that gradients over time occupy the same subspace.The section uses this result to motivate identifying gradient subspaces from historical updates.Source: §4.2 · p. 6

5. Experiments

The experiments evaluate RGP on vision and language tasks, alongside membership-inference attacks. Across the reported comparisons, RGP performs better than DP-SGD on vision and BERT tasks and shows low attack success at ε=8.

5.1. Experiments on Vision Tasks

  • With differential privacy, RGP outperforms DP-SGD on WRN28-4 vision tasks while using less memory; without privacy, its accuracy is comparable to full-model training.The reported comparisons include ε=8 and additional privacy budgets ε=2, 4, and 6.Source: Table 3 · p. 7, Table 2 · p. 7, §5.1 · p. 7

5. Experiments

  • Experiments compare DP-SGD, random-carrier RGP, non-private baselines, and vision DP-PowerSGD on WRN28-4 with SVHN/CIFAR10 and BERT on four GLUE tasks.The four BERT tasks are MNLI, QQP, QNLI, and SST-2; smaller GLUE datasets are excluded because private learning requires substantial data.Source: §5 · pp. 6–7, §5.1 · p. 7, §5.2 · p. 7

5.2. Experiments on the Downstream Tasks of BERT

  • RGP achieves the best performance among the private BERT methods, with accuracy loss within 5% of non-private baselines; RGP-random and DP-SGD perform worse.DP-SGD performs worst, and the authors attribute this to high-dimensional noise overwhelming gradient signal.Source: Table 4 · p. 8, §5.2 · p. 8

5.3. Defense Against Membership Inference Attack

  • At ε=8, membership-inference attacks on RGP-trained BERT and WRN28-4 models achieve no better than 50% success, while low-rank reparametrization alone also lowers success versus full training.The attacks cover MNLI, QQP, QNLI, SST-2, SVHN, and CIFAR10.Source: Table 5 · p. 8, §5.3 · p. 8

6. Related Work

The related work contrasts RGP’s low-rank assumption with sparsity-based methods and approaches that reduce noise through gradient subspaces. It also distinguishes RGP from PATE’s teacher-student approach.

6. Related Work

  • Unlike sparsity-based methods with public canonical bases, RGP assumes gradients are low-rank in unknown, private bases, a structure the authors say prior sparsity algorithms cannot exploit.The paper notes that deep-network gradients do not satisfy the sparse or specific structures assumed by earlier high-dimensional methods.Source: §6 · pp. 8–9
  • Prior subspace methods use public data or historical gradients to reduce noise, but still require storing and clipping full individual gradients, unlike RGP’s per-weight-matrix low-rank approach.The cited approaches exploit redundancy across samples; RGP instead exploits low rank within each weight-matrix gradient.Source: §6 · p. 9
  • PATE trains teachers on disjoint private-data shards and distills noisy predictions on public samples; the authors note its performance suffers from data splitting and its use for BERT is unclear.RGP does not require public data and can be used in different settings with little change.Source: §6 · p. 9

7. Conclusion

The conclusion presents RGP as a differentially private method for large models, based on low-rank gradients and alignment between historical and current gradient components. The appendix preliminaries describe differential privacy as limiting the influence of an individual sample.

7. Conclusion

  • RGP uses low stable rank in each weight-matrix gradient and alignment between historical and current principal components, supported by theoretical and empirical evidence.The authors report training BERT on downstream tasks with a DP guarantee and small accuracy loss.Source: §7 · p. 9

A. Preliminary on Differential Privacy

  • Differential privacy bounds an individual sample’s influence; neighboring datasets differ in one sample, and their learned-model distributions should be approximately indistinguishable.The appendix introduces the definition of (ε, δ)-DP.Source: A. Preliminary on Differential Privacy · p. 12

B.1. Missing Proofs in Section 2

The proof uses unchanged forward and backward signals to relate gradients of the original weight matrix to gradients of its low-rank carriers. With orthonormal carriers, the reconstructed update is a projection onto their row and column subspaces.

B.1. Missing Proofs in Section 2

  • Theorem 2.1 relates gradients computed for the original weight matrix to carrier gradients obtained using the same mini-batch and reparametrized forward/backward process.The proof invokes the chain rule and unchanged forward and backward signals.Source: §B.1 · p. 12
  • The proof applies the chain rule to layer inputs and backward signals, then uses multiplication associativity to complete the gradient relation.For each input x_i, the layer output is h_i = W x_i.Source: §B.1 · p. 12
  • With orthonormal columns of L and rows of R, the reconstructed update is equivalent to projecting ∂W onto the subspace spanned by those carriers.The proof substitutes the carrier-gradient relations into the projection formula.Source: §B.1 · p. 12

B.2. Missing Proofs in Section 3

The appendix establishes a differential-privacy guarantee for Algorithm 1 and explains why moments accounting applies even though RGP releases projected gradients. The accountant composes privacy loss across updates and converts it to an (ϵ, δ)-DP guarantee.

B.2. Missing Proofs in Section 3

  • Algorithm 1 is (ϵ, δ)-differentially private under the stated conditions on the running steps, ϵ, and δ.The proposition excerpt does not include the full displayed condition.Source: §B.2 · p. 12
  • Moments accounting applies to RGP because it applies to vectorized function outputs, including projected gradients.RGP releases projected gradients rather than the whole gradient.Source: §B.2 · p. 12
  • The accountant adds log moments across updates, then uses a tail bound to convert accumulated moments into (ϵ, δ)-DP.The log moments of the privacy loss random variable compose linearly.Source: §B.2 · p. 12

B.3. Missing Proofs in Section 4

For the least-squares problem under gradient descent, the gradients at successive steps share the same range and null space. The appendix also includes a BERT accuracy figure covering four downstream tasks and different reparametrization ranks.

B.3. Missing Proofs in Section 4

  • For least squares updated by gradient descent, all gradients after the first share its range and null space.If the first gradient has rank r, the proposition represents it with an r-SVD.Source: §B.3 · p. 12
  • The proof derives the next-step gradient from the gradient-descent update and concludes that gradients retain the same row and column spaces.The supplied proof excerpts give the recurrence argument in fragments.Source: §B.3 · pp. 12–13
  • Figure 5 plots BERT prediction accuracy across reparametrization ranks on four downstream tasks, averaging two MNLI test datasets.The caption provides the figure's scope but no accuracy values.Source: Figure 5 · p. 13

C. Additional Experiments

The additional experiments examine reparametrization rank and the residual weight. Rank changes have different effects with and without privacy, while removing the residual weight leaves the reconstructed update with little learning on two BERT tasks.

C.1. On the Influence of Different Rank Choices

  • With privacy, increasing reparametrization rank sometimes decreases performance because it adds trainable parameters and increases noise dimension.The comparison uses ϵ = 8; other settings match Section 5.Source: §C.1 · p. 13
  • Without noise, increasing rank makes RGP (N.P.) performance approach the full-model fine-tuning baseline.The comparison also includes RGP (Algorithm 1) and RGP-random, which uses random orthogonal gradient-carrier vectors.Source: §C.1 · p. 13

C.2. On the Importance of Residual Weight

  • The residual weight preserves forward and backward signals while keeping the gradients of L and R naturally connected to the original gradient.The ablation tests a variant that discards the residual weight.Source: §C.2 · p. 13, C. Additional Experiments · p. 13
  • Without residual weight, the reconstructed update learns almost nothing on two BERT downstream tasks, leaving final accuracy close to initialization.The experiments still use historical updates to generate L and R.Source: §C.2 · p. 13, Figure 6 · p. 13

Related papers

Loading 2106.09352v4…