Introduction
Adaptive optimizers like Adam are the gold standard for training deep learning models, but they often fail when paired with Differential Privacy (DP). The added noise required for privacy effectively destroys the "adaptivity" signal these optimizers rely on. AdaDPS (Adaptive Differential Privacy with Side information) solves this by using non-sensitive "side information"—such as a tiny sliver of public data or simple word frequency counts—to precondition gradients before they are privatized. This approach leads to an average 7.7% boost in accuracy over standard private baselines.
The Challenge of Private Adaptivity
Differential Privacy is essential for training models on sensitive data (like medical records or private messages), but it comes with a "utility tax." Standard DP-SGD works by clipping gradients and adding random Gaussian noise.
When attempting to use adaptive optimizers (like Adam or RMSProp) with DP, a major roadblock emerges. These methods typically estimate the "geometry" of the loss surface (the preconditioner) using the gradients themselves. In a private setting, those gradients are already noisy. Trying to estimate statistics from noise results in a "blind" preconditioner that fails to help the model converge.
As a result, private adaptive methods often perform no better—and sometimes worse—than simple DP-SGD because the noise completely flattens the gradient moments they rely on.
The AdaDPS Approach
The core innovation of AdaDPS is a simple but powerful "flip" in the order of operations:
- Standard Private Adaptivity: Privatize Gradients $\rightarrow$ Calculate Preconditioner. (Results in a noisy, ineffective preconditioner).
- AdaDPS: Calculate Preconditioner from Side Info $\rightarrow$ Precondition Raw Gradients $\rightarrow$ Privatize.
By using "side information" that doesn't require privacy protection, the algorithm can generate a "clean" preconditioner. The paper explores two ways to obtain this side information:
- With Public Data: Use a very small amount of public data (e.g., as little as 0.04% to 1% of the training set size) to estimate gradient statistics at each step.
- Without Public Data (Heuristics): Use "open knowledge" heuristics. For NLP tasks, this could be token frequencies or TF-IDF scores. Rare words usually have sparser, more informative gradients; AdaDPS uses these known frequencies to scale the learning rates for different coordinates without needing a public dataset.
Experimental Setup
The authors evaluated AdaDPS across several benchmarks representing both centralized and federated learning:
- IMDB: Sentiment classification using Logistic Regression and LSTM models.
- StackOverflow: Tag prediction (500-class classification) with over 5 million parameters.
- MNIST: Image classification and deep autoencoders for reconstruction.
- Amazon Reviews: Used as "out-of-distribution" public data to test the robustness of the side information.
Key Findings
AdaDPS demonstrates that preconditioning before privatization allows the noise added later to be "non-isotropic." Essentially, it adds less noise to the most important coordinates of the gradient, improving the signal-to-noise ratio where it matters most.
- Accuracy Boost: AdaDPS improved absolute accuracy by 7.7% on average compared to strong private baselines.
- Closing the Gap: On the StackOverflow dataset, AdaDPS achieved a test accuracy (approx. 40%) that was significantly higher than even non-private SGD, nearly matching the performance of non-private adaptive methods.
- Robustness to Data Shift: The public data doesn't have to be a perfect match for the private data. Using Amazon product reviews as side info for an IMDB movie review task still yielded massive gains, suggesting the "geometry" of language is consistent enough to be useful across datasets.
- Federated Learning: When extended to federated settings (user-level DP), AdaDPS outperformed DP-FedAvg and DP-FedAdam by about 5% in test accuracy.
Limitations and Future Work
While AdaDPS significantly improves utility, it still requires a privacy budget ($\epsilon$). The paper focuses on $(\epsilon, \delta)$-DP, and while the results are state-of-the-art, the gap to non-private training isn't entirely closed for all tasks.
Furthermore, while the authors show that heuristics work well for NLP, it is less clear what the "universal heuristics" would be for other domains like computer vision or audio when no public data is available. Finally, the current federated learning implementation assumes uniform device sampling, which isn't always realistic in "in-the-wild" deployments, pointing to future work incorporating recent advances in DP without sampling.
Summary updated