DP-MacAdam: Differentially Private Mechanism with Adaptive Clipping and Adaptive Momentum

Technical Summary: DP-MacAdam

Problem Statement
Differentially Private Stochastic Gradient Descent (DP-SGD) is the standard framework for privacy-preserving machine learning, yet it suffers from a significant practical limitation: its reliance on a fixed gradient clipping threshold ($C$). In practice, selecting $C$ is difficult; a value that is too small discards signal through excessive clipping, while a value that is too large increases sensitivity, necessitating larger noise additions to satisfy the privacy budget.

Existing approaches attempt to address this in two distinct, complementary ways, but neither fully leverages the available statistics:

1. Adaptive Clipping (e.g., AdaClip): Uses empirical estimates of gradient mean and variance to dynamically shift and scale gradients before clipping. This reduces the expected noise added per iteration but discards these statistics after preprocessing, reverting to a standard SGD update that ignores the adaptive information.
2. Adaptive Momentum (e.g., DP-Adam): Utilizes exponential moving averages (EMA) of gradient moments to compute coordinate-wise adaptive learning rates (similar to Adam). However, it relies on fixed isotropic clipping, forgoing the noise reduction benefits of adaptive clipping.

The core problem addressed is the lack of an algorithm that simultaneously exploits the same gradient statistics for both adaptive clipping and adaptive momentum updates under differential privacy (DP) guarantees without incurring additional privacy costs.

Methodology: DP-MacAdam
The authors propose DP-MacAdam (Differentially Private Mechanism with Adaptive Clipping and Adaptive Momentum), an algorithm that unifies the coordinate-wise adaptive clipping of AdaClip with the adaptive momentum updates of Adam.

• Unified Statistics: The algorithm maintains running estimates of the gradient mean ($m_t$) and variance ($s_t$) derived entirely from privatized gradients. By the post-processing property of DP, these estimates satisfy $(\epsilon, \delta)$-DP without additional cost.
• Adaptive Clipping & Momentum:
  • Gradients are centered and scaled using the current estimates of the mean ($\hat{m}_{t-1}$) and a scaling vector ($b_{t-1}$) before clipping.
  • The privatized, transformed gradients are then used to update both the momentum terms (first and second moments) for the parameter update and the variance estimates for the next iteration's scaling.
• Bias-Corrected Variance Estimation: A critical technical contribution is the derivation of a novel bias correction factor, $\kappa_t = 2(\beta_1 - \beta_1^t)/(1 + \beta_1)$.
  • Standard EMA introduces initialization bias.
  • In the DP setting, the variance estimate is further biased by the inflation of noise added during the clipping process.
  • The authors derive $\kappa_t$ to yield an unbiased estimate of the true gradient variance from the EMA of noise-corrected instantaneous variance estimates, accounting for both the EMA initialization and the correlation structure introduced by weighted averaging.
• Noise Scaling: The algorithm clips the transformed gradients to a unit $\ell_2$-norm. Noise is added to the average of the batch of clipped gradients rather than individual gradients, scaling the noise variance by $1/B^2$. The algorithm subtracts the known noise variance term from the variance estimate to recover the variance of the un-noised gradient.

Key Contributions

1. Algorithm Design: DP-MacAdam is the first algorithm to combine AdaClip-style coordinate-wise adaptive clipping with Adam-style adaptive momentum under DP guarantees.
2. Theoretical Derivation: The authors derive a specific bias correction factor ($\kappa_t$) that enables unbiased estimation of gradient variance from the EMA of noise-corrected estimates, addressing both DP noise inflation and EMA initialization bias.
3. Empirical Performance: The algorithm achieves improved model utility compared to state-of-the-art baselines (DP-SGD, AdaClip, DP-Adam, and DP-AdamBC) across various privacy budgets on MNIST and CIFAR-10. Crucially, it achieves this without requiring manual tuning of the clipping threshold or dimensionality reduction preprocessing.

Experimental Results
The authors evaluated DP-MacAdam on MNIST (fully connected network) and CIFAR-10 (5-layer CNN) against DP-SGD, AdaClip, DP-Adam, and DP-AdamBC.

• MNIST: DP-MacAdam consistently outperformed all baselines across noise multipliers ($\sigma$) ranging from 0.5 to 1.0, achieving up to 93.2% accuracy (vs. 92.8% for DP-Adam and 90.0% for DP-SGD at $\sigma=0.5$).
• CIFAR-10: DP-MacAdam achieved the highest accuracy across most privacy budgets, reaching 59.96% at $\sigma=0.5$ (vs. 58.90% for DP-Adam).
• Observations: The authors note that while DP-MacAdam-BC (a variant incorporating second-moment bias correction for Adam) showed gains on MNIST, it underperformed on CIFAR-10. They hypothesize that the second-moment bias correction yields larger gains on tasks where Adam outperforms SGD in the non-private setting.
• Efficiency: Unlike AdaClip, DP-MacAdam operates directly on raw inputs without spending privacy budget on dimensionality reduction (e.g., PCA).

Significance and Claims
The paper claims that DP-MacAdam represents a significant step forward by demonstrating that the statistics used for adaptive clipping can be effectively reused to drive adaptive momentum updates, thereby improving model utility without compromising privacy. The authors emphasize that their approach removes the need for manual tuning of the clipping threshold, a major practical hurdle in deploying DP-SGD.

The authors remain modest regarding the scope of their work, noting that:

• The optimal choice of the scaling vector $b_t$ under their EMA-based variance estimate is left for future work.
• A formal convergence analysis of DP-MacAdam is not provided in this work.
• Empirical evaluation is currently limited to image classification tasks (MNIST, CIFAR-10), with future work suggested for more complex tasks like NLP and larger datasets.