# Unleash the Power of Ellipsis: Accuracy-enhanced Sparse Vector Technique with Exponential Noise

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 51 references that are in the map.
- First posted on arXiv 29 Jul 2024.

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

- [Renyi Differential Privacy](https://mlsanity.com/paper/1702.07476/) (2017)
- [The Composition Theorem for Differential Privacy](https://mlsanity.com/paper/1311.0776/) (2013)
- [RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response](https://mlsanity.com/paper/1407.6981/) (2014)
- [Numerical Composition of Differential Privacy](https://mlsanity.com/paper/2106.02848/) (2021)
- [Privacy Loss in Apple's Implementation of Differential Privacy on MacOS 10.12](https://mlsanity.com/paper/1709.02753/) (2017)
- [Practical Differentially Private Top-k Selection with Pay-what-you-get Composition](https://mlsanity.com/paper/1905.04273/) (2019)
- [Understanding the Sparse Vector Technique for Differential Privacy](https://mlsanity.com/paper/1603.01699/) (2016)
- [Make Up Your Mind: The Price of Online Queries in Differential Privacy](https://mlsanity.com/paper/1604.04618/) (2016)
- [Permute-and-Flip: A new mechanism for differentially private selection](https://mlsanity.com/paper/2010.12603/) (2020)
- [Adversarially Robust Streaming Algorithms via Differential Privacy](https://mlsanity.com/paper/2004.05975/) (2020)
- [Wide Network Learning with Differential Privacy](https://mlsanity.com/paper/2103.01294/) (2021)
- [Building a RAPPOR with the Unknown: Privacy-Preserving Learning of Associations and Data Dictionaries](https://mlsanity.com/paper/1503.01214/) (2015)
- [Oneshot Differentially Private Top-k Selection](https://mlsanity.com/paper/2105.08233/) (2021)
- [The Permute-and-Flip Mechanism is Identical to Report-Noisy-Max with Exponential Noise](https://mlsanity.com/paper/2105.07260/) (2021)
- [Differentially Private Algorithms for Empirical Machine Learning](https://mlsanity.com/paper/1411.5428/) (2014)
- [Optimal Noise-Adding Mechanism in Additive Differential Privacy](https://mlsanity.com/paper/1809.10224/) (2018)
- [The Sparse Vector Technique, Revisited](https://mlsanity.com/paper/2010.00917/) (2020)
- [Free Gap Estimates from the Exponential Mechanism, Sparse Vector, Noisy Max and Related Algorithms](https://mlsanity.com/paper/2012.01592/) (2020)
- [Echo of Neighbors: Privacy Amplification for Personalized Private Federated Learning with Shuffle Model](https://mlsanity.com/paper/2304.05516/) (2023)
- [On Differentially Private Online Predictions](https://mlsanity.com/paper/2302.14099/) (2023)
- [Differentially Private Top-k Selection via Canonical Lipschitz Mechanism](https://mlsanity.com/paper/2201.13376/) (2022)

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

- [Sub-optimal Learning in Meta-Classifier Attacks: A Study of Membership Inference on Differentially Private Location Aggregates](https://mlsanity.com/paper/2412.20456/) (2024)

## Abstract (arXiv)

The Sparse Vector Technique (SVT) is one of the most fundamental tools in differential privacy (DP). It works as a backbone for adaptive data analysis by answering a sequence of queries on a given dataset, and gleaning useful information in a privacy-preserving manner. Unlike the typical private query releases that directly publicize the noisy query results, SVT is less informative -- it keeps the noisy query results to itself and only reveals a binary bit for each query, indicating whether the query result surpasses a predefined threshold. To provide a rigorous DP guarantee for SVT, prior works in the literature adopt a conservative privacy analysis by assuming the direct disclosure of noisy query results as in typical private query releases. This approach, however, hinders SVT from achieving higher query accuracy due to an overestimation of the privacy risks, which further leads to an excessive noise injection using the Laplacian or Gaussian noise for perturbation. Motivated by this, we provide a new privacy analysis for SVT by considering its less informative nature. Our analysis results not only broaden the range of applicable noise types for perturbation in SVT, but also identify the exponential noise as optimal among all evaluated noises (which, however, is usually deemed non-applicable in prior works). The main challenge in applying exponential noise to SVT is mitigating the sub-optimal performance due to the bias introduced by noise distributions. To address this, we develop a utility-oriented optimal threshold correction method and an appending strategy, which enhances the performance of SVT by increasing the precision and recall, respectively. The effectiveness of our proposed methods is substantiated both theoretically and empirically, demonstrating significant improvements up to 50% across evaluated metrics.