Introduction
Large embedding models are fundamental to modern recommendation systems and natural language processing (NLP). These models map categorical features into dense vectors within massive embedding tables. A key efficiency of these models is gradient sparsity: in any given training iteration, only a tiny fraction of the embedding table is updated because only a few features are present in a mini-batch.
However, implementing Differential Privacy (DP) via the standard DP-SGD algorithm destroys this sparsity. DP-SGD requires adding Gaussian noise to every coordinate of the gradient to mask individual contributions, turning sparse updates into dense ones. This "densification" significantly increases computational overhead and prevents the use of specialized hardware optimizations, such as those found in Google TPUs or NVIDIA GPUs, which are designed to handle sparse updates efficiently.
Proposed Methodology: DP-FEST and DP-AdaFEST
To address the loss of sparsity, this work introduces two algorithms: DP-FEST and DP-AdaFEST. These methods aim to preserve sparsity by selectively updating only the most "informative" embedding rows.
DP-FEST (Filtering-Enabled Sparse Training)
DP-FEST is a static approach that identifies the top-$k$ most frequent features in the dataset before training begins. During the training process, private updates are restricted to these pre-selected rows. This method is effective when feature frequencies are stable and can be estimated privately beforehand.
DP-AdaFEST (Adaptive Filtering-Enabled Sparse Training)
For dynamic environments where feature importance may shift (e.g., streaming data), the authors propose DP-AdaFEST. This algorithm identifies high-contribution rows on-the-fly for each mini-batch through a three-step process:
- Contribution Mapping: Compute the contribution statistics for all buckets in the feature vocabulary.
- Noisy Thresholding: Clip these contributions and add Gaussian noise.
- Selective Update: Only rows whose noisy contribution exceeds a threshold $\tau$ receive a private gradient update.
The privacy budget is split between the selection mechanism and the gradient update, ensuring rigorous DP guarantees while maintaining high utility. By zeroing out "unimportant" gradients, the algorithm introduces some bias but drastically reduces variance, which can often improve overall model utility compared to vanilla DP-SGD.
Experimental Evaluation
The algorithms were evaluated on industry-standard benchmarks, including the Criteo dataset for click-through rate (CTR) prediction and the GLUE benchmark (SST-2, QNLI, QQP) for NLP tasks using RoBERTa.
Key Findings
- Efficiency Gains: DP-AdaFEST achieved up to a $10^6\times$ reduction in the number of non-zero gradient entries compared to standard DP-SGD. This translated to a simulated $150\times$ wall-clock speedup for models with large vocabularies (10M+ rows).
- Utility Preservation: Despite the massive reduction in gradient size, the models maintained accuracy levels comparable to vanilla DP-SGD across all tested privacy levels ($\epsilon$).
- Adaptivity: DP-AdaFEST proved more robust than static methods in non-stationary data environments, such as recommendation systems where user interests evolve over time.
Conclusion and Future Work
DP-FEST and DP-AdaFEST provide a viable path for training large-scale embedding models with strong privacy guarantees without sacrificing computational efficiency. By restoring gradient sparsity, these algorithms enable the use of high-performance hardware accelerators like the TPU SparseCore. Future research may focus on simplifying hyperparameter tuning for the threshold $\tau$ and integrating these techniques into Federated Learning frameworks.
Summary updated