📊 statistics

Label Differential Privacy via Aggregation

This paper proposes a label differential privacy framework for regression tasks that achieves strong privacy guarantees through weighted linear aggregation of training instances or disjoint bags, offering improved practical bounds and utility preservation without requiring additive label noise.

Original authors: Anand Brahmbhatt, Rishi Saket, Shreyas Havaldar, Anshul Nasery, Yukti Makhija, Aravindan Raghuveer

Published 2026-09-11

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Anand Brahmbhatt, Rishi Saket, Shreyas Havaldar, Anshul Nasery, Yukti Makhija, Aravindan Raghuveer

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the modern digital age, vast amounts of personal information are collected every day to train computer programs that make predictions, from estimating house prices to forecasting sales. A critical challenge in this field is how to teach these systems without exposing the sensitive details of the individuals who provided the data. One powerful solution, known as differential privacy, acts like a mathematical shield. It ensures that the final result of a computer analysis looks almost the same whether any single person's data is included or excluded, making it impossible for an outsider to reverse-engineer that specific person's information. While this concept has been well-studied for general data, a specific and difficult problem arises when the sensitive information is hidden entirely within the labels—the answers or outcomes attached to the data, such as a patient's medical diagnosis or a voter's choice. Protecting these labels without destroying the ability of the computer to learn useful patterns has long been a hurdle.

A team of researchers at Google Research India has developed a new method to solve this problem by changing how the data is grouped and combined before it is ever used for training. Instead of adding random noise to the data, a technique that often blurs the results and reduces accuracy, they proposed a system of weighted aggregation. Imagine taking a large collection of individual records and mixing them together into small groups, or "bags." In their approach, each record within a bag is multiplied by a unique, randomly generated number drawn from a specific bell-shaped distribution. The system then sums these weighted records to create a single, new data point for the bag. This process is repeated to create many such aggregated points. The researchers found that this specific way of mixing the data, using these random weights, creates a mathematical barrier that protects the privacy of the original labels. Crucially, they proved that this protection holds even if an attacker knows everything about the other records in the bag, provided the dataset is large enough and the labels are not all identical.

The study demonstrates that this method works effectively for two different scenarios. In the first, every single record in the entire dataset is included in every bag, creating a highly mixed set of aggregates. In the second, the dataset is split into many small, non-overlapping groups, and each group is processed separately. In both cases, the researchers showed that a computer model trained on these aggregated, privacy-protected points can still learn to make predictions almost as accurately as a model trained on the original, raw data. They tested this on massive real-world datasets, including a census of over 130 million people from 1940 and a collection of over 1.7 million records from an online advertising platform. The results were clear: the models trained on the aggregated data achieved nearly the same level of accuracy as those trained on the raw data, while satisfying strict privacy guarantees.

A key finding of this work is that simply adding up the labels in a group without these special random weights does not provide any real privacy protection. If the data is just summed, a change in a single person's label would cause a detectable shift in the total, revealing their information. The researchers proved that the random weighting is essential to hide these individual contributions. Furthermore, they showed that this technique does not require the addition of extra noise to the labels, which is a common requirement in other privacy methods that often degrades the quality of the learning. By relying solely on the mathematical properties of this weighted aggregation, they preserved the utility of the data for regression tasks, which are used to predict continuous values like sales figures or hours worked.

The team also explored a variation where a small fraction of the labels are intentionally altered with noise before being grouped, combined with the weighted aggregation. This hybrid approach allowed them to extend the privacy guarantees to more complex learning tasks involving neural networks, which are deep learning models capable of handling intricate patterns. Their experiments confirmed that even with these added complexities, the models maintained high utility. The work suggests that for many practical applications, especially those constrained by regulations or system limitations that prevent the use of raw individual data, this aggregation method offers a robust path forward. It allows organizations to build powerful predictive tools using sensitive data without compromising the privacy of the individuals behind the numbers, all without the significant loss of accuracy that often accompanies privacy-preserving techniques.

Technical Summary: Label Differential Privacy via Aggregation

Problem Definition

The paper addresses the challenge of protecting sensitive training labels in machine learning datasets while maintaining the utility of regression tasks. Specifically, it focuses on Label Differential Privacy (label-DP), a privacy notion where the output distribution of a mechanism remains stable even if a single training label changes, while feature vectors remain unchanged.

Traditional approaches to achieving label-DP typically rely on adding independent additive noise (e.g., Gaussian noise) to each label. However, the authors note that in many practical scenarios, such as advertising platforms (e.g., Apple SKAN, Chrome Privacy Sandbox) or medical data aggregation, data is naturally processed via aggregation mechanisms (e.g., Learning from Label Proportions or Learning from Bag Aggregates) rather than additive noise. The paper investigates whether these natural aggregation mechanisms, often used for efficiency or regulatory compliance, inherently provide label-DP guarantees, and if not, how they can be enhanced to do so without sacrificing the utility of linear or neural regression tasks.

The authors establish that unweighted summation of labels in bags does not provide label-DP guarantees. The core problem is to design aggregation mechanisms that achieve $(\epsilon, \delta)$ -label-DP with minimal or no additive noise while ensuring the optimal regression model trained on the aggregated data approximates the optimal model on the original dataset.

Methodology

The paper proposes three primary aggregation mechanisms that utilize weighted linear aggregation with independent and identically distributed (i.i.d.) Gaussian weights ( $N(0, 1)$ ).

1. Weighted-FLAg (WTD-FLAG)

This mechanism aggregates the entire dataset into $m$ bags. For each bag $j$ , the mechanism samples $n$ i.i.d. weights $w_{ij} \sim N(0, 1)$ and computes:

Aggregate feature vector: $x^{AGG}_j = \sum_{i=1}^n w_{ij} x_i$
Aggregate label: $y^{AGG}_j = \sum_{i=1}^n w_{ij} y_i$

Crucially, no additive noise is added to the labels. The privacy guarantee relies on the randomness of the weights and the non-degeneracy of the dataset (specifically, a lower bound on the linear regression loss).

2. Sampled-Weighted-FLAg (Sampled-WTD-FLAG)

To reduce computational overhead and the portion of the dataset required for aggregation, this variant samples $m$ disjoint bags of size $k$ . For each bag, it samples $k$ i.i.d. weights and computes the weighted sum of the features and labels within that specific subset. Like the first mechanism, it uses no additive noise. This approach requires a minimum singular value bound on the data matrix to ensure utility.

3. Sampled-Noisy-Weighted LAg (Sampled-Noisy-WTD-LAg)

This mechanism addresses scenarios where feature vectors in bags are available individually (Label Aggregation or LAg). To overcome the privacy loss from exposing individual features, the mechanism:

Adds i.i.d. $N(0, 1)$ noise to only a small, fixed fraction ( $\rho$ ) of the labels.
Applies weighted aggregation with Gaussian weights to the labels.
Outputs the aggregated labels along with the individual feature vectors and their corresponding weights for each bag.

This hybrid approach aims to preserve the utility of Lipschitz-bounded neural network regression tasks while providing label-DP guarantees.

Key Contributions

The paper makes the following specific contributions:

Negative Result: It demonstrates that merely aggregating labels (as in standard LLP datasets) without weighting or noise does not provide differential privacy guarantees.
Novel Algorithms: It introduces novel aggregation algorithms (WTD-FLAG, Sampled-WTD-FLAG, and Sampled-Noisy-WTD-LAg) that generate label-DP datasets solely through aggregation (with minimal noise in the third variant), avoiding the heavy additive noise typical of prior label-DP methods.
Utility Preservation: It proves that datasets generated by these algorithms preserve the utility (optimum) of linear regression tasks with bounded norm regressors and, in the noisy variant, neural regression tasks.
Improved Bounds: Theoretical analysis shows that the proposed methods achieve $(\epsilon, \delta)$ -label-DP with parameters dependent on the linear regression loss lower bound ( $\gamma$ ) rather than the minimum singular value of the data matrix, leading to tighter practical bounds.

Theoretical Results

Privacy Guarantees:
- WTD-FLAG: Achieves $(\epsilon, \delta)$ -label-DP if the number of bags $m$ satisfies $m = O(\frac{\gamma n}{B_Y^2 \log(1/\delta)})$ , where $\gamma$ is the lower bound on the linear regression loss and $B_Y$ is the bound on label magnitude.
- Sampled-WTD-FLAG: Achieves $(\epsilon, \delta)$ -label-DP with bag size $k \geq \Omega(((1/\epsilon) \log(1/\delta))^2)$ , assuming a minimum singular value bound on the data.
- Sampled-Noisy-WTD-LAg: Achieves $(\epsilon, \delta)$ -label-DP by perturbing a fraction $\rho$ of labels, with $k$ scaling as $O(B_Y^2/\rho\epsilon^2)$ .
Utility Guarantees:
- For linear regression, the optimal regressor trained on the aggregated data approximates the original dataset's optimum with high probability. The error is bounded by a multiplicative factor $(1+\theta)$ , where $\theta$ depends on the number of bags and dataset properties.
- The utility bounds are independent of the input dimension $d$ for the WTD-FLAG mechanism, a significant improvement over prior work that relied on dimension-dependent bounds.

Experimental Results

The authors empirically evaluated their methods on two large-scale datasets:

1940 US Census Data: Predicting working hours based on demographic features.
Criteo Sponsored Search Dataset: Predicting ad sales amounts.

Findings:

Privacy vs. Utility: The experiments demonstrate that WTD-FLAG effectively preserves utility for linear regression even under modest privacy budgets ( $\epsilon$ ). As $\epsilon$ increases, the Mean Squared Error (MSE) on the original dataset decreases, stabilizing near the optimal loss of the original data.
Comparison with Prior Work: The paper compares the theoretical upper bounds on the number of bags ( $m$ ) allowed for a given $\epsilon$ against the work of Sheffet [42]. The authors show that their bounds, derived from the linear regression loss lower bound, are substantially better (allowing for more bags) than bounds derived from the minimum singular value in real-world datasets.
Neural Regression: Experiments with Sampled-Noisy-WTD-LAg on neural networks show that utility is preserved even with a limited number of sampled bags and varying bag sizes, confirming the theoretical guarantees for non-linear tasks.

Significance and Claims

The paper claims that its primary significance lies in quantifying the privacy achieved through aggregation alone. Unlike previous label-DP methods that rely heavily on adding noise or probabilistic resampling, this work demonstrates that natural aggregation mechanisms, when enhanced with weighted sampling, can provide rigorous privacy guarantees.

The authors emphasize that their approach is motivated by real-world constraints where additive noise is undesirable or impossible due to systemic or regulatory limitations. By showing that label-DP can be achieved with little or no additive noise while preserving the utility of regression tasks, the work suggests that existing aggregation pipelines in industry may already offer stronger privacy guarantees than previously understood, potentially reducing the need for additional, costly privacy-preserving interventions. The paper remains modest, focusing on quantifying these guarantees rather than proposing new applications or future directions beyond the scope of the current theoretical and empirical analysis.