# DPack: Efficiency-Oriented Privacy Budget Scheduling

arXiv: https://arxiv.org/abs/2212.13228 · HTML: https://mlsanity.com/paper/2212.13228/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 60 references that are in the map.
- First posted on arXiv 26 Dec 2022.

## Builds on (most cited first, 17 of 17)

- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Membership Inference Attacks against Machine Learning Models](https://mlsanity.com/paper/1610.05820/) (2016)
- [Extracting Training Data from Large Language Models](https://mlsanity.com/paper/2012.07805/) (2020)
- [The Secret Sharer: Evaluating and Testing Unintended Memorization in Neural Networks](https://mlsanity.com/paper/1802.08232/) (2018)
- [Renyi Differential Privacy](https://mlsanity.com/paper/1702.07476/) (2017)
- [Practical and Private (Deep) Learning without Sampling or Shuffling](https://mlsanity.com/paper/2103.00039/) (2021)
- [Differentially Private Model Publishing for Deep Learning](https://mlsanity.com/paper/1904.02200/) (2019)
- [Individual Privacy Accounting via a Renyi Filter](https://mlsanity.com/paper/2008.11193/) (2020)
- [Privacy Odometers and Filters: Pay-as-you-Go Composition](https://mlsanity.com/paper/1605.08294/) (2016)
- [Differentially Private SQL with Bounded User Contribution](https://mlsanity.com/paper/1909.01917/) (2019)
- [Privacy-Preserving Gradient Boosting Decision Trees](https://mlsanity.com/paper/1911.04209/) (2019)
- [Practical Privacy Filters and Odometers with R'enyi Differential Privacy and Applications to Differentially Private Deep Learning](https://mlsanity.com/paper/2103.01379/) (2021)
- [Privacy Accounting and Quality Control in the Sage Differentially Private ML Platform](https://mlsanity.com/paper/1909.01502/) (2019)
- [Differential Privacy for Growing Databases](https://mlsanity.com/paper/1803.06416/) (2018)
- [Privacy Budget Scheduling](https://mlsanity.com/paper/2106.15335/) (2021)
- [Tumult Analytics: a robust, easy-to-use, scalable, and expressive framework for differential privacy](https://mlsanity.com/paper/2212.04133/) (2022)
- [DP-XGBoost: Private Machine Learning at Scale](https://mlsanity.com/paper/2110.12770/) (2021)

## Built on by (most cited first, 1 of 1)

- [DPBalance: Efficient and Fair Privacy Budget Scheduling for Federated Learning as a Service](https://mlsanity.com/paper/2402.09715/) (2024)

## Abstract (arXiv)

Machine learning (ML) models can leak information about users, and differential privacy (DP) provides a rigorous way to bound that leakage under a given budget. This DP budget can be regarded as a new type of compute resource in workloads of multiple ML models training on user data. Once it is used, the DP budget is forever consumed. Therefore, it is crucial to allocate it most efficiently to train as many models as possible. This paper presents the scheduler for privacy that optimizes for efficiency. We formulate privacy scheduling as a new type of multidimensional knapsack problem, called privacy knapsack, which maximizes DP budget efficiency. We show that privacy knapsack is NP-hard, hence practical algorithms are necessarily approximate. We develop an approximation algorithm for privacy knapsack, DPack, and evaluate it on microbenchmarks and on a new, synthetic private-ML workload we developed from the Alibaba ML cluster trace. We show that DPack: (1) often approaches the efficiency-optimal schedule, (2) consistently schedules more tasks compared to a state-of-the-art privacy scheduling algorithm that focused on fairness (1.3-1.7x in Alibaba, 1.0-2.6x in microbenchmarks), but (3) sacrifices some level of fairness for efficiency. Therefore, using DPack, DP ML operators should be able to train more models on the same amount of user data while offering the same privacy guarantee to their users.