PaperlayerView exact revision on arXiv

Source-linked AI summary

AdaCliP: Adaptive Clipping for Private SGD

Venkatadheeraj Pichapati, Ananda Theertha Suresh, Felix X. Yu, Sashank J. Reddi, Sanjiv Kumar

arXiv:1908.07643v2cs.LGcs.CRstat.ML

TL;DR

Machine-learning models trained on user data need privacy guarantees without sacrificing performance. AdaCliP addresses this through theoretically motivated coordinate-wise adaptive clipping in differentially private SGD, achieving less noise and higher accuracy than previous methods under the same privacy constraints.

  • Problem

    Training machine-learning models on sensitive user data requires rigorous privacy guarantees while maintaining performance.

  • Method

    AdaCliP is a differentially private SGD algorithm that uses theoretically derived coordinate-wise adaptive clipping and optimal transformation parameters.

  • Results

    AdaCliP adds less noise and achieves higher accuracy than previous methods under the same privacy constraints, with up to 1.6% higher neural-network accuracy.

  • Takeaways & Limitations

    AdaCliP provides a differentially private SGD approach that improves model accuracy while reducing the noise added to gradients.

  • Takeaways & Limitations

    The convergence analysis assumes smoothness, bounded gradients, bounded gradient variance, and a specified learning-rate condition.

Abstract

from arXiv · show

Privacy preserving machine learning algorithms are crucial for learning models over user data to protect sensitive information. Motivated by this, differentially private stochastic gradient descent (SGD) algorithms for training machine learning models have been proposed. At each step, these algorithms modify the gradients and add noise proportional to the sensitivity of the modified gradients. Under this framework, we propose AdaCliP, a theoretically motivated differentially private SGD algorithm that provably adds less noise compared to the previous methods, by using coordinate-wise adaptive clipping of the gradient. We empirically demonstrate that AdaCliP reduces the amount of added noise and produces models with better accuracy.

1 Introduction

The paper addresses privacy-preserving machine learning over sensitive user data by developing AdaCliP, a differentially private SGD method designed to reduce noise while maintaining model performance.

  • 1 Introduction: Differentially private SGD modifies gradients during training and adds noise to protect information in user data.The paper situates AdaCliP within noisy SGD approaches for deep and convex machine learning objectives.
  • 1 Introduction: AdaCliP uses coordinate-wise adaptive gradient clipping to add less noise under the same privacy guarantee than previous methods.The method is motivated by SGD convergence and aims to improve learned model quality.
  • 1 Introduction: Experiments on MNIST show that AdaCliP achieves much better accuracy than previous methods under the same privacy constraints.The evaluation includes multiple machine learning models, including neural networks.
  • 1 Introduction: The paper develops a general formulation, derives optimal transformation parameters, and evaluates AdaCliP empirically.Its sections cover prior methods, theoretical analysis, the AdaCliP algorithm, and experiments.

2 Differential privacy for distributed SGD

Differentially private SGD protects machine-learning training by clipping or otherwise modifying per-example gradients, averaging them, and adding calibrated noise before model updates. Existing methods differ in how they bound sensitivity, while AdaCliP introduces adaptive coordinate-wise thresholds.

  • 2 Differential privacy for distributed SGD: Differential privacy for machine learning can modify the input data, output model, objective, or optimization algorithm.Noisy SGD belongs to the optimization-algorithm approach.
  • 2 Differential privacy for distributed SGD: Noisy SGD computes per-example gradients, optionally clips them, averages them, adds noise, and updates the model with the noisy gradient.Its privacy analysis separately considers per-round privacy and composition across iterations.
  • 2 Differential privacy for distributed SGD: Differential privacy is obtained by bounding gradient sensitivity and adding Gaussian noise proportional to the resulting sensitivity bound.A privacy accountant tracks the cumulative cost across SGD iterations.
  • 2 Differential privacy for distributed SGD: AdaCliP targets settings where gradient norms are difficult to bound a priori and assumes no access to public data for estimating them.Public-data-based clipping is identified as a strong assumption in prior work.
  • 2 Differential privacy for distributed SGD: Prior methods clip each coordinate to [-C, C] or scale the whole gradient to enforce an ℓ2-norm threshold C.The paper contrasts these strategies with adaptive coordinate-wise thresholds.

3 Motivation for AdaCliP

The motivation for AdaCliP is that isotropic clipping can add unnecessary noise in dimensions carrying little information. The paper therefore motivates adaptive, dimension-specific noise levels to improve the signal-to-noise ratio.

  • 3 Motivation for AdaCliP: The gradient at iteration t is gt = θt − xit, and revealing it together with xit reveals the same information.This motivates analyzing the disclosed vector when determining noise.
  • 3 Motivation for AdaCliP: 1/σ^2d is the example’s signal-to-noise ratio, so it worsens as the dimension count d increases despite information occurring in only one dimension.The added noise has ℓ2-norm σ^2µ^2d under the stated clipping choice.
  • 3 Motivation for AdaCliP: The example motivates adding different noise levels across dimensions because dimensions without information need not receive as much noise.This directly motivates adaptive coordinate-wise clipping.
  • 3 Motivation for AdaCliP: For clip thresholds below µ, the signal-to-noise ratio stays unchanged, while thresholds above µ make it worse.The analysis uses C = µ and Gaussian noise scaled by µ.

4 Theoretical analysis

The analysis identifies coordinate-wise transformations that minimize added Gaussian noise under a clipping constraint, then uses them in AdaCliP's privacy-preserving gradient pipeline. It connects convergence to clipping bias and noise variance, and shows a factor-d improvement over ℓ2 clipping and whitening in the regression comparison.

  • 4.1 General framework: The transformation framework seeks lower gradient-estimation error by balancing clipping effects and injected Gaussian noise through element-wise linear transformations.The analysis separately identifies clipping and Gaussian noise as the two sources of gradient modification error.
  • 4.1 General framework: AdaCliP transforms each stochastic gradient using auxiliary vectors, clips the transformed vector at norm 1, adds Gaussian noise, and rescales it.The rescaling multiplies each noisy transformed coordinate by b_t and adds a_t.
  • 4.1 General framework: Theorem 1 minimizes the expected ℓ2-norm of added noise when E∥w_t∥² ≤ γ.These optimal transformation parameters motivate AdaCliP's coordinate-wise adaptive clipping.
  • 4.2 Convergence analysis: AdaCliP's convergence bound depends on stochastic-gradient variance, clipping bias, and noise-addition variance.The analysis highlights an inherent trade-off: increasing ∥b_t∥ reduces clipping bias but increases added noise.

5 AdaCliP

AdaCliP estimates gradient statistics from noisy gradients and uses them to set adaptive coordinate-wise clipping and noise parameters. The algorithm updates model parameters, means, and variances while tracking the overall privacy cost.

  • 5 AdaCliP: The procedure outputs θT and computes the overall (ϵ, δ) privacy cost using a privacy accounting method.The algorithm specifies privacy-preserving noise addition at each iteration before the final privacy accounting step.
  • 5 AdaCliP: AdaCliP estimates gradient means and variances from noisy differentially private gradients to choose transformation parameters.The full algorithm uses these estimates to set a_t and b_t, which determine gradient processing and noise addition.
  • 5 AdaCliP: Gaussian noise is added separately to each user gradient before aggregation, while noisy gradients also update the mean and variance estimates.Adding Gaussian noise to individual processed gradients is equivalent to adding Gaussian noise to the mean processed gradient.
  • 5 AdaCliP: The mean estimate uses an exponential moving average of previous noisy gradients, with β1 controlling the decay.This momentum-style estimate is used because the stochastic gradients are not directly available at time t.
  • 5 AdaCliP: Variance estimation assumes clipping does not occur, bounds the resulting quantity, and then applies an exponential moving average.The constants β1, β2, and h1 are fixed in experiments, while h2 is tuned.

6 Experiments

Experiments compare AdaCliP with prior methods on a synthetic regression task, MNIST logistic regression, and an MNIST neural network. Across the MNIST models, AdaCliP achieves higher accuracy and adds less noise than the compared method.

  • 6 Experiments: In the synthetic regression experiment, AdaCliP’s error remains independent of dimension because it adds no noise to dimensions other than the first.Both methods use clip threshold 1.0 and noise scale σ = 0.1 for 10 epochs with minibatch size 1.
  • 6 Experiments: The MNIST evaluations fix δ = 10−5 and compare accuracy across ϵ using minibatches of 600.The neural model uses differentially private PCA before a one-hidden-layer network.
  • 6 Experiments: AdaCliP improves logistic-regression accuracy over [14] by 0.2% to 1.1% across ϵ = 0.1 to 2.0.It also outperforms the norm-bound method in the reported comparisons.
  • 6 Experiments: AdaCliP improves neural-network accuracy over [14] by 0.4% to 1.6% across tested ϵ values.Table 2 reports AdaCliP accuracy from 87.18% to 96.31%, versus 85.55% to 95.91% for [14].
  • 6 Experiments: AdaCliP adds less gradient noise than [14] for the neural model, with a noise ratio around 0.8 across ϵ.The measured quantity combines clipping and additive Gaussian noise.

7 Conclusion

The paper concludes that AdaCliP reduces training noise and achieves higher accuracy than previous methods at the same privacy parameters. It identifies matrix or low-rank gradient transforms as a direction for future work.

  • 7 Conclusion: The method adds a smaller amount of noise to gradients during training than previous approaches.The conclusion presents reduced gradient noise as a central property of AdaCliP.
  • 7 Conclusion: AdaCliP achieves higher accuracy than previous methods for the same ϵ and δ on MNIST.The conclusion summarizes the empirical comparison while retaining the fixed-privacy setting.
  • 7 Conclusion: Future work could replace the coordinate-wise gradient transform with a matrix or low-rank matrix gradient transform.This is proposed as a possible way to obtain better results.

A AdaCliP Convergence Analysis

The convergence analysis bounds AdaCliP’s optimization behavior by separating clipping bias from noise-addition variance. Its assumptions include smoothness, bounded gradients, bounded gradient variance, and a step-size condition.

  • A AdaCliP Convergence Analysis: Under smoothness, bounded gradients, bounded gradient variance, and η < 1/(3L), the analysis gives a convergence bound for AdaCliP iterates.The stated result considers batch size 1 and a_t = E[g_t].
  • A AdaCliP Convergence Analysis: AdaCliP’s convergence analysis separates clipping bias from noise-addition variance in the update decomposition.The proof studies the clipped-gradient deviation and the variance introduced by Gaussian noise.
  • A AdaCliP Convergence Analysis: Summing the per-iteration inequalities with a telescoping sum yields the final bound after applying the lower bound f(θT) ≥ f(θ*).The proof also uses bounds on the clipping deviation and the smoothness condition.
  • A AdaCliP Convergence Analysis: The proof bounds clipping effects by observing that the clipping deviation is zero when the centered gradient lies within the clipping scale.The remaining probability is bounded using Chebyshev’s inequality.

B Comparison of SGD with momentum

The paper compares differentially private momentum with vanilla SGD, finding that smaller per-update noise does not translate into better final accuracy. It attributes this behavior to dependencies among noises accumulated across iterations, while noting that the explanation needs stronger theory.

  • Mechanism: Momentum tracks exponentially weighted averages of previous gradients, so privacy-preserving approximations and their noise are incorporated into the update through this accumulation.The parameter update is θ_t = θ_t−1 − ην_t, with β controlling momentum.
  • Noise accumulation: Although momentum reduces the noise added per update by a factor involving β, the paper cautions that this does not establish better model parameters than vanilla SGD.The proposed advantage is only a per-update noise reduction; the paper distinguishes this from the overall optimization outcome.
  • Empirical comparison: SGD and momentum converge to almost similar accuracies on MNIST under the evaluated privacy setting.The experiment targets (0.5, 10^-5)-differential privacy and uses noise proportional to the maximum gradient norm, 28, to avoid clipping.
  • Noise accumulation: The paper hypothesizes that noises across momentum iterations are dependent, increasing the overall noise despite smaller noise at each iteration.This dependence is offered as an explanation for the similar SGD and momentum accuracies.
  • Limitation: The authors identify the need for a better theoretical understanding of the observed momentum-noise behavior.This is presented as an unresolved issue rather than a completed theoretical account.
Loading 1908.07643v2…