PaperlayerView exact revision on arXiv

Source-linked AI summary

Understanding Gradient Clipping in Private SGD: A Geometric Perspective

Xiangyi Chen, Zhiwei Steven Wu, Mingyi Hong

arXiv:2006.15429v2cs.LGcs.CRmath.OCstat.ML

TL;DR

The paper asks why private SGD remains effective despite gradient clipping, which can bias updates and obstruct convergence. It analyzes clipping geometrically through distributional symmetry, evaluates gradient distributions empirically, and proposes perturbation before clipping; the results connect near-symmetry with favorable convergence and show correction on asymmetric instances.

  • Problem

    Gradient clipping is used to bound sensitivity in DP-SGD, but it can introduce bias and prevent convergence, while practical gradient bounds may be unavailable.

  • Method

    The paper couples gradient distributions with nearby geometrically symmetric distributions to analyze clipping bias and perturbs gradients before clipping to reduce that bias.

  • Results

    Pre-clipping perturbation ensures convergence in the presented asymmetric synthetic example, whereas DP-SGD with clipping converges to non-optimal points.

  • Takeaways & Limitations

    Gradient distributions in private SGD tend to exhibit symmetric structure along training, helping explain why clipped DP-SGD remains effective in practice.

  • Takeaways & Limitations

    The paper notes that gradient distributions may be less symmetric and calls for empirical analysis beyond symmetric distributions.

Abstract

from arXiv · show

Deep learning models are increasingly popular in many machine learning applications where the training data may contain sensitive information. To provide formal and rigorous privacy guarantee, many learning systems now incorporate differential privacy by training their models with (differentially) private SGD. A key step in each private SGD update is gradient clipping that shrinks the gradient of an individual example whenever its L2 norm exceeds some threshold. We first demonstrate how gradient clipping can prevent SGD from converging to stationary point. We then provide a theoretical analysis that fully quantifies the clipping bias on convergence with a disparity measure between the gradient distribution and a geometrically symmetric distribution. Our empirical evaluation further suggests that the gradient distributions along the trajectory of private SGD indeed exhibit symmetric structure that favors convergence. Together, our results provide an explanation why private SGD with gradient clipping remains effective in practice despite its potential clipping bias. Finally, we develop a new perturbation-based technique that can provably correct the clipping bias even for instances with highly asymmetric gradient distributions.

1 Introduction

The paper examines how gradient clipping enables private SGD while potentially biasing update directions and preventing convergence. It develops a geometric analysis, empirical evidence, and a perturbation-based correction mechanism.

  • Motivation: DP-SGD adds Gaussian noise to subsampled gradient estimates to provide differential privacy, but practical sensitivity control relies on gradient clipping.Clipping shrinks individual gradients whose ℓ2 norms exceed a threshold because practical gradient bounds may be unknown or unavailable.
  • Clipping bias: Gradient clipping can bias update directions and prevent convergence even without privacy noise.In one example, the expected clipped gradient at the optimum is 1/3; in another, every point in [−2,2] can be stationary for clipped SGD.
  • Clipping bias: Existing analyses relate clipping bias to clipped-versus-unclipped gradients or the fraction of examples exceeding the threshold, suggesting smaller thresholds can worsen training.The paper notes that this prediction does not fully explain why DP-SGD often remains effective with small thresholds.
  • Our results: The paper quantifies clipping bias by coupling the gradient distribution with a nearby geometrically symmetric distribution.When distributions are near-symmetric or the bias favors convergence, clipped gradients can remain aligned with the true gradient even under aggressive clipping.
  • Our results: Empirical studies suggest DP-SGD gradient distributions exhibit symmetric structure along training, helping explain practical effectiveness despite clipping bias.The analysis also yields DP-SGD convergence guarantees without requiring loss-function Lipschitzness.
  • Our results: A pre-clipping perturbation technique can reduce clipping bias for arbitrary gradient distributions, while trading bias against higher variance.The perturbation itself does not provide privacy guarantees.

2 Convergence of SGD with clipped gradient

The analysis isolates clipping bias in SGD and shows that convergence depends on how the gradient-noise distribution aligns with a symmetric reference distribution. Symmetry, near-symmetry, and some favorable asymmetric biases can preserve convergence, while adverse skew can create convergence gaps.

  • Analysis strategy: The convergence analysis first shows E[⟨∇f(x_t),g_t⟩] diminishes, then relates it to the true gradient norm.The second step is the main difficulty under clipping.
  • Bias characterization: A coupling to a nearby symmetric distribution converts clipping bias into a disparity measure resembling Wasserstein distance.When the distributions are near-symmetric, clipped gradients can remain aligned even when clipping aggressively shrinks most sample gradients.
  • Symmetricity-based analysis: For symmetric noise, the expected clipped gradient remains positively aligned with the true gradient, with a probability term quantifying possible slowdown.This alignment supplies the property needed for convergence.
  • Beyond symmetric distributions: The framework also covers favorable asymmetric cases, including positively skewed distributions and mixtures containing a zero-mean symmetric component.Positive skewness can make the expected clipped-gradient inner product strictly larger than under the symmetric reference.
  • Beyond symmetric distributions: Negative bias can produce convergence gaps for negatively skewed or highly imbalanced multimodal distributions, so near-symmetry is sufficient but not necessary.The paper identifies cases where the accumulated bias instead helps convergence.

3 DP-SGD with Gradient Clipping

The paper extends its clipping-bias analysis from SGD to DP-SGD, combining subsampling noise and Gaussian privacy perturbation with a Wasserstein-based bias bound. Under symmetric gradient distributions, the usual convergence rate can be recovered up to a constant factor.

  • Algorithm and privacy: DP-SGD samples a minibatch, clips gradients, and adds Gaussian noise for privacy.The dataset is treated as an empirical distribution over private examples.
  • Algorithm and privacy: The privacy guarantee is obtained for a clipping threshold c and noise variance satisfying the stated subsampling-dependent condition.The theorem applies for any δ > 0 under its stated bound on ϵ.
  • Convergence guarantee: The DP-SGD convergence guarantee accounts for both subsampling noise and Gaussian perturbation while bounding clipping bias through a coupling symmetric distribution.This extends the clipped-SGD analysis to the private setting.
  • Convergence rate: With symmetric gradient distributions, the convergence rate O(√d/(nϵ)) can be recovered, whereas general clipping adds a clipping-bias term.In the symmetric case, clipping affects the rate by only a constant factor.
  • Bias measurement: The clipping bias is measured by a Wasserstein distance using a clipping-aware metric, avoiding a trivial total-variation bound for empirical distributions.The metric is uniformly bounded by ∥∇f(x)∥c and converges toward the population-distribution distance as n grows.

4 Experiments

The experiments examine whether DP-SGD gradient distributions are approximately symmetric using random projections and cosine similarities. Across MNIST and CIFAR-10, distributions become more symmetric over training, and MNIST projections at epoch 9 show the pattern across eight realizations.

  • Experimental approach: The study uses two proxy measures because certifying symmetry directly in high-dimensional gradient distributions is generally intractable.The proxies are visual random projections and cosine-similarity histograms.
  • Setup: DP-SGD is evaluated on MNIST and CIFAR-10 using CNNs, with clip norm c = 1 and noise multiplier 1.1.The MNIST experiment uses α = 0.15 and batch size 128.
  • Random-projection visualizations: On both datasets, gradients are non-symmetric at initialization but become increasingly symmetric over successive epochs.Figure 1 indexes the columns by epoch, with epoch 0 computed before training.
  • Random-projection visualizations: At MNIST epoch 9, the approximate symmetric pattern holds across all 8 random-projection realizations.The projections use different randomly generated matrices in two dimensions.
  • Symmetricity of angles: Cosine similarities between per-sample stochastic gradients and the true gradient are approximately symmetric around 0 in the reported histograms.This provides a second empirical proxy for symmetric gradient structure.

5 Mitigating Clipping Bias with Perturbation

The paper proposes perturbing gradients before clipping to reduce clipping bias when gradient distributions are unfavorable. This trades lower bias for higher variance and is shown to restore convergence on examples where clipped DP-SGD reaches non-optimal points.

  • Gradient correction mechanism: Theorem 6 analyzes clipped gradients of the form clip(∇f(x_t) + ξ_t + kζ_t,c), where ζ_t is standard Gaussian noise.This theorem provides the formal properties of the perturbation-based correction.
  • Gradient correction mechanism: The perturbation approach trades clipping bias against variance, with larger noise potentially slowing convergence while improving the bias profile.In DP-SGD, each per-sample stochastic gradient is perturbed before clipping.
  • Empirical evaluation: On unfavorable optimization problems, clipped DP-SGD converges to non-optimal points, whereas pre-clipping perturbation ensures convergence.The evaluation uses σ = 1 for the perturbation experiments and includes a high-dimensional Gaussian-mixture example.
  • Empirical evaluation: Figure 4 examines the effect of pre-clipping perturbation on the examples.The supplied caption identifies the figure’s topic but does not specify its axes or outcome comparison.

6 Conclusion and Future Work

The paper explains clipping bias through symmetry in gradient distributions and proposes perturbation to address asymmetric cases. Its future-work discussion notes that symmetry and effective clipping thresholds may vary across model types.

  • Conclusion: The paper couples gradient distributions with geometrically symmetric distributions to quantify clipping bias and analyzes its effect on SGD and private SGD.Empirical evaluation suggests that private-SGD gradient distributions exhibit symmetric structure along the optimization trajectory.
  • Conclusion: Perturbation-based correction is proposed to reduce clipping bias even for adversarial instances.This extends the analysis beyond settings where symmetry naturally favors convergence.
  • Future Work: Symmetric gradient distributions are presented as a setting where gradient clipping will not be detrimental to DP-SGD performance.The authors suggest that methods for symmetrifying gradient distributions could be studied in future work.
  • Future Work: CNNs on MNIST and CIFAR-10 may work well with a clipping threshold around 1, whereas prior findings reported around 10 for LSTMs.This contrast suggests that gradient-distribution symmetry and suitable thresholds may depend on model type.
  • Future Work: Some models may have less symmetric gradient distributions, motivating empirical analysis beyond the symmetric setting.The authors also identify broader classes of gradient distributions as a direction for future study.

A Proof of Theorem 1

The proof of Theorem 1 applies smoothness-based convergence analysis, aggregates the per-iteration inequalities, and selects a step size proportional to 1/√T.

  • Proof strategy: The proof begins by invoking the smoothness assumption.This supplies the initial inequality used in the convergence argument.
  • Proof strategy: The per-iteration inequality is summed over t from 1 to T, divided by Tα, and rearranged before substituting the step-size choice.The passage indicates α = 1/√T, though the displayed expression is truncated.

B Proof of Theorem 2

The proof of Theorem 2 uses symmetry of the perturbation distribution, decomposes clipped-gradient inner products into cases, and establishes nonnegative directional contributions through geometric inequalities and monotonicity.

  • Symmetry reduction: The proof pairs the clipped gradients at g + ξ_t and g − ξ_t and rewrites their directional contributions using norms and cosines.The clipping operation preserves directions, enabling the cosine-based decomposition.
  • Case analysis: When both perturbed gradients exceed the clipping threshold, the paired directional term is c(cos(g,g + ξ_t) + cos(g,g − ξ_t)) ≥ 0.The proof handles the remaining norm configurations separately.
  • Case analysis: If only one perturbed gradient is below threshold, the proof bounds the corresponding directional sum using the clipping threshold and cosine inequalities.Analogous reasoning covers the case where the other perturbed gradient is below threshold.
  • Monotonicity: The argument rotates coordinates so the target gradient lies on one axis, then proves the relevant terms are non-decreasing in its magnitude.Rotation invariance reduces the geometric argument to scalar monotonicity in the aligned coordinate.
  • Mixture extension: Theorem 3 extends the result to mixtures of distributions whose component means have nonnegative inner product with the true gradient.Each component is specified through a radially symmetric density around its mean.
  • Symmetry reduction: Theorem 2 assumes a distribution symmetric under ξ → −ξ and studies the clipped update for an arbitrary vector g.This symmetry permits pairing perturbations ξ and −ξ in the proof.
  • Spherical distributions: For spherical noise, the expected clipped gradient remains in the same direction as the unclipped gradient, with a scalar proportionality factor.The proof combines this directional property with the symmetric-distribution result.
  • Application to DP-SGD: For DP-SGD, the proof uses per-sample stochastic gradients, Gaussian privacy noise, clipping, and a Wasserstein-distance bound on the clipping bias.The noise variance is calibrated according to the privacy parameters through Theorem 1 of Abadi et al. (2016b).

E Proof of Theorem 6

The proof analyzes pre-clipping noise and bounds how adding Gaussian perturbation makes the total noise distribution increasingly symmetric, thereby reducing clipping bias.

  • Theorem 6: Theorem 6 analyzes clipped gradients formed from the true gradient, noise ξ_t, and added Gaussian perturbation kζ_t.The total pre-clipping noise is W_t = ξ_t + kζ_t.
  • Proof strategy: The proof bounds the total variation distance between W_t and the isotropic Gaussian distribution kζ_t.This distance decreases as k increases, making the total noise increasingly symmetric.
  • Proof strategy: A Taylor expansion and the zero-mean property of ξ_t are used to derive the required bounds on the clipping analysis.The proof proceeds by substituting these bounds into the theorem’s intermediate inequalities.
  • Proof strategy: The argument handles the noise direction by reducing to a coordinate-aligned case without loss of generality.It assumes ξ_t,1 = ∥ξ_t∥ and ξ_t,i = 0 for i ≥ 2.
  • Conclusion: The theorem’s proof combines the derived bounds to establish the stated properties of the gradient-clipping algorithm.The final step explicitly combines the preceding inequalities.

F More experiments on random projection

The experiments project MNIST stochastic gradients into two dimensions using different random projection matrices at multiple training epochs to examine their distributional structure.

  • Random projections: The study visualizes projected MNIST gradients at epochs 0, 3, 9, and 59 using multiple random projection matrices.These projections correspond to Figures 5–8.
  • Observed structure: As training progresses, the projected gradient distributions tend to become increasingly symmetric in the two-dimensional visualizations.The reported trend is observed across the different projection matrices.

G Evaluation on the probability term

This evaluation uses empirical gradient statistics and two-dimensional visualizations to assess the probability term and the symmetry of DP-SGD gradient distributions across epochs.

  • Empirical statistics: The evaluation plots gradient norms, noise norms, and inner products with the true gradient at the ends of different epochs.The plots include both stochastic and clipped stochastic gradient inner products.
  • Approximation bias: Approximating the empirical distribution with one satisfying a positive mass condition can introduce approximation bias.The text notes that this bias may nevertheless remain limited when the noise norm’s mode is not much larger than c.
  • Probability term: The probability condition can be replaced by a stricter threshold zc for any z < 1 while adjusting the associated constant to enlarge the probability term.This changes the threshold and the constant together.
  • Interpretation: The combined empirical evidence suggests that gradient noise may be a mixture whose components are each approximately symmetric.The authors identify this as a possible explanation rather than a complete account.
  • Figures: Figures 9–11 report distributions of different statistics at epochs 3, 9, and 59.These figures provide the epoch-specific views used in the evaluation.

H Additional results and discussions on the probability term and the noise adding approach in Section 5

The additional discussion examines how pre-clipping Gaussian noise trades reduced clipping bias for weaker expected descent, with rates that depend on the perturbation scale and dimension.

  • Noise perturbation: Adding Gaussian noise kζ_t before clipping decreases clipping bias but also decreases expected descent as P(∥kζ_t∥ < c/4) decreases with k.The perturbation therefore creates a bias–descent trade-off.
  • One-dimensional behavior: In one dimension, P(∥kζ_t∥ < c/4) equals erf(c/4k) and decreases at order O(1/k).This is the stated one-dimensional rate for the expected-descent term.
  • Asymptotic trade-off: The clipping bias decreases at O(1/k^2), so it becomes negligible relative to expected descent for large k.The resulting convergence analysis has a slower convergence rate but a better final gradient bound.
  • Symmetrization: Pre-clipping Gaussian noise increasingly symmetrizes the overall gradient-noise distribution as k grows.The total variation distance from kζ_t decreases at O(1/k^2).
  • Higher-dimensional behavior: For higher dimensions, the theorem’s lower bounds may be improvable because P(∥kζ_t∥ < c/4) decreases rapidly with k.The authors leave sharper bounds for future work.
  • Empirical scaling: In practice, the expected inner product decreases at O(1/d) and O(1/k) for fixed gradient norm and zero ξ_t.The reported example evaluates the expectation over 10^5 Gaussian-noise samples.
Loading 2006.15429v2…