Sparse Vector Technique

SVT operates by comparing a noisy query result against a noisy threshold. The threshold is calibrated by adding Laplace noise to the true cutoff value. A query's answer is only released if its noisy value exceeds this noisy threshold. This avoids spending privacy budget on queries that are far from the threshold, focusing the budget on the sparse set of 'meaningful' queries.

The primary advantage of SVT is its asymptotic privacy budget consumption. Unlike standard mechanisms that consume budget linearly with the number of queries, SVT's privacy cost scales with the number of queries that exceed the threshold, not the total number of queries asked. This makes it ideal for monitoring tasks where most queries are expected to be below a threshold.

The foundational SVT algorithm is often called AboveThreshold. It takes a stream of queries, a pre-defined threshold, and privacy parameters. For each query, it generates a noisy answer and a noisy threshold. It outputs the noisy answer only if it exceeds the noisy threshold, and halts after a pre-specified number of such 'above-threshold' events.

A variant called NumericSparse releases the actual noisy value for above-threshold queries, not just an indicator. This is useful when the magnitude of the exceeding query matters. It allocates a portion of the privacy budget to the threshold check and a separate portion to the numerical value release for each above-threshold event.

The privacy guarantee of SVT is typically analyzed using composition theorems. The total privacy loss is a function of the number of above-threshold events allowed (c) and the noise scales used for the query and the threshold. A common instantiation provides pure ε-differential privacy, where ε is proportional to c.

SVT is widely used in private data analysis pipelines where monitoring is required. Examples include:

• Detecting high-spending customers without revealing all transactions.
• Identifying geographic regions with disease outbreaks above a baseline.
• Monitoring real-time system metrics for anomalies while preserving user privacy.

The canonical instantiation of the Sparse Vector Technique. It takes a stream of queries and a threshold, then outputs the index of the first query whose noisy answer exceeds a noisy threshold. It consumes privacy budget only for queries that exceed the threshold, making it highly efficient for monitoring tasks.

A finite, quantifiable resource representing the total allowable privacy loss (ε). The Sparse Vector Technique is designed to conserve this budget by only spending it on 'meaningful' queries that exceed a dynamically calibrated threshold, rather than on every query in a stream.

The fundamental building block for adding noise in the Sparse Vector Technique. It draws random noise from a Laplace distribution calibrated to the query's sensitivity. In SVT, it is used to perturb both the threshold value and the query answers to mask the influence of any single record.

The maximum amount a query's output can change when a single record is added or removed. The Sparse Vector Technique relies on accurate sensitivity calibration to determine the scale of Laplace noise added to both the threshold and the individual queries, ensuring the privacy guarantee holds.

A formal result quantifying how privacy loss accumulates across multiple mechanisms. The Sparse Vector Technique exploits the fact that 'below-threshold' queries consume negligible budget, allowing analysts to ask many questions while the total privacy loss remains bounded by the few 'above-threshold' releases.

A variant of SVT that, instead of just reporting that a query exceeded the threshold, releases the noisy numerical value of the query itself. This provides richer data but consumes additional privacy budget for each released value beyond the threshold check.