Private Adaptive Optimization with Side Information

Tian Li, Manzil Zaheer, Sashank J. Reddi, Virginia Smith

Abstract

Adaptive optimization methods have become the default solvers for many machine learning tasks. Unfortunately, the benefits of adaptivity may degrade when training with differential privacy, as the noise added to ensure privacy reduces the effectiveness of the adaptive preconditioner. To this end, we propose AdaDPS, a general framework that uses non-sensitive side information to precondition the gradients, allowing the effective use of adaptive methods in private settings. We formally show AdaDPS reduces the amount of noise needed to achieve similar privacy guarantees, thereby improving optimization performance. Empirically, we leverage simple and readily available side information to explore the performance of AdaDPS in practice, comparing to strong baselines in both centralized and federated settings. Our results show that AdaDPS improves accuracy by 7.7% (absolute) on average -- yielding state-of-the-art privacy-utility trade-offs on large-scale text and image benchmarks.

The Challenge of Private Adaptivity

Differential Privacy (DP) is the gold standard for training machine learning models on sensitive data without leaking individual information. The standard approach, DP-SGD, works by clipping gradients and adding random noise. However, modern machine learning relies heavily on adaptive optimizers like Adam or RMSProp, which adjust learning rates for each parameter based on past gradient statistics.

In private settings, these methods often fail because the noise added for privacy "pollutes" the statistics used for adaptivity. When building a preconditioner from noisy gradients (the standard "DP-Adam" approach), the noise is amplified across coordinates. This creates a high noise floor that masks the true gradient geometry, often making the model perform worse than simple DP-SGD.

Figure 4: Gradient second moments across coordinates. In standard private adaptive methods (DP-Adam), noise creates a flat floor that masks the true gradient geometry, preventing effective adaptivity.

The AdaDPS Framework

The researchers propose AdaDPS (Adaptive Differential Privacy with Side information) to bridge this gap. The core innovation is a change in the sequence of operations and the source of preconditioning information:

  1. Precondition then Privatize: Unlike previous methods that privatize gradients and then try to adapt, AdaDPS preconditions the raw gradients first and then applies the DP Gaussian mechanism.
  2. Side Information as a Proxy: To avoid "spending" the privacy budget on the preconditioner, AdaDPS uses non-sensitive side information to estimate the gradient geometry. This side information can come from a very small amount of public data (e.g., 1% of the training set) or simple heuristics like token frequencies in NLP tasks.

By preconditioning with side information, AdaDPS essentially adds non-isotropic noise that is "smarter" about which parts of the model can handle it. Coordinates with higher second moments (more "active" features) are naturally more tolerant to noise, and AdaDPS leverages this to maintain the benefits of adaptivity without compromising privacy.

Experimental Evaluation and Results

AdaDPS was evaluated across several large-scale benchmarks, including StackOverflow (tag prediction), IMDB (sentiment analysis), and MNIST. The results demonstrate that AdaDPS consistently outperforms standard DP-SGD and DP-Adam baselines.

Key findings include:

  • Significant Accuracy Gains: AdaDPS improved absolute accuracy by 7.7% on average across benchmarks. On the StackOverflow task, it achieved 40% accuracy, compared to 28% for DP-SGD.
  • Heuristics vs. Public Data: Simple word frequency counts—which are essentially public knowledge—can precondition a model nearly as well as a dedicated public dataset.
  • Robustness to Data Shift: Even when the public data comes from a different source (e.g., using Amazon reviews to precondition an IMDB model), the performance gains remain significant.
  • Federated Learning Success: In federated settings (user-level DP), AdaDPS outperformed DP-FedAvg and DP-FedAdam by roughly 5%.

Conclusion

AdaDPS demonstrates that the failure of prior private adaptive optimizers was largely due to the order of operations. By preconditioning raw gradients with non-sensitive side information before privatization, AdaDPS restores the efficiency of adaptive optimization in private settings. This framework provides a robust path forward for training high-performance models on sensitive data while maintaining rigorous privacy guarantees.

Summary updated

Abstract

Adaptive optimization methods have become the default solvers for many machine learning tasks. Unfortunately, the benefits of adaptivity may degrade when training with differential privacy, as the noise added to ensure privacy reduces the effectiveness of the adaptive preconditioner. To this end, we propose AdaDPS, a general framework that uses non-sensitive side information to precondition the gradients, allowing the effective use of adaptive methods in private settings. We formally show AdaDPS reduces the amount of noise needed to achieve similar privacy guarantees, thereby improving optimization performance. Empirically, we leverage simple and readily available side information to explore the performance of AdaDPS in practice, comparing to strong baselines in both centralized and federated settings. Our results show that AdaDPS improves accuracy by 7.7% (absolute) on average -- yielding state-of-the-art privacy-utility trade-offs on large-scale text and image benchmarks.
BibTeX
@inproceedings{li2022private,
  author = {Tian Li and Manzil Zaheer and Sashank J. Reddi and Virginia Smith},
  title = {{Private Adaptive Optimization with Side Information}},
  booktitle = {International Conference on Machine Learning},
  year = {2022},
  url = {https://openreview.net/forum?id=CMPTQuy5wy},
}
Figure