# Understanding the Sparse Vector Technique for Differential Privacy

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

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Mar 2016.

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

- [Unlocking High-Accuracy Differentially Private Image Classification through Scale](https://mlsanity.com/paper/2204.13650/) (2022)
- [Do Gradient Inversion Attacks Make Federated Learning Unsafe?](https://mlsanity.com/paper/2202.06924/) (2022)
- [Unleashing the Power of Randomization in Auditing Differentially Private ML](https://mlsanity.com/paper/2305.18447/) (2023)
- [Threshold KNN-Shapley: A Linear-Time and Privacy-Friendly Approach to Data Valuation](https://mlsanity.com/paper/2308.15709/) (2023)
- [Wide Network Learning with Differential Privacy](https://mlsanity.com/paper/2103.01294/) (2021)
- [Data synthesis and adversarial networks: A review and meta-analysis in cancer imaging](https://mlsanity.com/paper/2107.09543/) (2021)
- [Adaptive Private-K-Selection with Adaptive K and Application to Multi-label PATE](https://mlsanity.com/paper/2203.16100/) (2022)
- [Quantifying and Defending against Privacy Threats on Federated Knowledge Graph Embedding](https://mlsanity.com/paper/2304.02932/) (2023)
- [Unbounded Differentially Private Quantile and Maximum Estimation](https://mlsanity.com/paper/2305.01177/) (2023)
- [The Hitchhiker's Guide to Efficient, End-to-End, and Tight DP Auditing](https://mlsanity.com/paper/2506.16666/) (2025)
- [Sequentially Auditing Differential Privacy](https://mlsanity.com/paper/2509.07055/) (2025)
- [Brownian Noise Reduction: Maximizing Privacy Subject to Accuracy Constraints](https://mlsanity.com/paper/2206.07234/) (2022)
- [On the Privacy of Selection Mechanisms with Gaussian Noise](https://mlsanity.com/paper/2402.06137/) (2024)
- [Answering Private Linear Queries Adaptively using the Common Mechanism](https://mlsanity.com/paper/2212.00135/) (2022)
- [Regularized f-Divergence Kernel Tests](https://mlsanity.com/paper/2601.19755/) (2026)
- [A unified interpretation of the Gaussian mechanism for differential privacy through the sensitivity index](https://mlsanity.com/paper/2109.10528/) (2021)
- [Exploratory Analysis of Federated Learning Methods with Differential Privacy on MIMIC-III](https://mlsanity.com/paper/2302.04208/) (2023)
- [On the Computational Complexity of Private High-dimensional Model Selection](https://mlsanity.com/paper/2310.07852/) (2023)
- [Unleash the Power of Ellipsis: Accuracy-enhanced Sparse Vector Technique with Exponential Noise](https://mlsanity.com/paper/2407.20068/) (2024)
- [VerifiableFL: Verifiable Claims for Federated Learning using Exclaves](https://mlsanity.com/paper/2412.10537/) (2024)
- [Learning Differentially Private Mechanisms](https://mlsanity.com/paper/2101.00961/) (2021)
- [Instance-Specific Asymmetric Sensitivity in Differential Privacy](https://mlsanity.com/paper/2311.14681/) (2023)
- [Nearly-Linear Time Private Hypothesis Selection with the Optimal Approximation Factor](https://mlsanity.com/paper/2506.01162/) (2025)
- [Continual Release of Densest Subgraphs: Privacy Amplification & Sublinear Space via Subsampling](https://mlsanity.com/paper/2510.11640/) (2025)
- [DPrivBench: Benchmarking LLMs' Reasoning for Differential Privacy](https://mlsanity.com/paper/2604.15851/) (2026)
- [Lumberjack: Better Differentially Private Random Forests through Heavy Hitter Detection in Trees](https://mlsanity.com/paper/2605.22756/) (2026)
- [PrivCert: Certifying Statement Support under Differential Privacy](https://mlsanity.com/paper/2609.38934/) (2026)

## Abstract (arXiv)

The Sparse Vector Technique (SVT) is a fundamental technique for satisfying differential privacy and has the unique quality that one can output some query answers without apparently paying any privacy cost. SVT has been used in both the interactive setting, where one tries to answer a sequence of queries that are not known ahead of the time, and in the non-interactive setting, where all queries are known. Because of the potential savings on privacy budget, many variants for SVT have been proposed and employed in privacy-preserving data mining and publishing. However, most variants of SVT are actually not private. In this paper, we analyze these errors and identify the misunderstandings that likely contribute to them. We also propose a new version of SVT that provides better utility, and introduce an effective technique to improve the performance of SVT. These enhancements can be applied to improve utility in the interactive setting. Through both analytical and experimental comparisons, we show that, in the non-interactive setting (but not the interactive setting), the SVT technique is unnecessary, as it can be replaced by the Exponential Mechanism (EM) with better accuracy.