Coded Machine Unlearning

Nasser Aldaghri, Hessam Mahdavifar, Ahmad Beirami

Abstract

There are applications that may require removing the trace of a sample from the system, e.g., a user requests their data to be deleted, or corrupted data is discovered. Simply removing a sample from storage units does not necessarily remove its entire trace since downstream machine learning models may store some information about the samples used to train them. A sample can be perfectly unlearned if we retrain all models that used it from scratch with that sample removed from their training dataset. When multiple such unlearning requests are expected to be served, unlearning by retraining becomes prohibitively expensive. Ensemble learning enables the training data to be split into smaller disjoint shards that are assigned to non-communicating weak learners. Each shard is used to produce a weak model. These models are then aggregated to produce the final central model. This setup introduces an inherent trade-off between performance and unlearning cost, as reducing the shard size reduces the unlearning cost but may cause degradation in performance. In this paper, we propose a coded learning protocol where we utilize linear encoders to encode the training data into shards prior to the learning phase. We also present the corresponding unlearning protocol and show that it satisfies the perfect unlearning criterion. Our experimental results show that the proposed coded machine unlearning provides a better performance versus unlearning cost trade-off compared to the uncoded baseline.

Introduction

In an era of increasing data privacy regulations like GDPR, the "right to be forgotten" is a significant technical challenge. When a user requests data deletion, simply removing the record from a database is insufficient; machine learning models trained on that data may retain traces of it. "Perfect unlearning" requires retraining the model from scratch without the deleted sample, which is computationally prohibitive for large-scale systems.

The Performance-Cost Trade-off

A common approach to mitigate retraining costs is sharding: splitting the dataset into disjoint pieces, training a separate "weak learner" on each, and aggregating their predictions. If a sample must be unlearned, only the specific weak learner that saw that data needs retraining. However, this introduces a fundamental trade-off: smaller shards lead to faster unlearning but degrade model performance because each learner sees less information.

Conceptual trade-off between average test MSE and unlearning cost.

As shown in Figure 1, the goal is to move from the "Undesirable region" of high MSE and high cost toward the "Desirable region." The "Uncoded machine unlearning" curve represents the baseline sharding approach, which often struggles to maintain accuracy as unlearning costs are reduced.

Coded Machine Unlearning Framework

The authors propose Coded Machine Unlearning to break this bottleneck. Instead of simple sharding, they apply a linear encoder to the training data before it reaches the learners.

System architecture of the proposed coded machine unlearning framework.

The architecture, illustrated in Figure 2, involves three main stages:

  1. Encoding: A master node applies a linear encoder (a random binary matrix $G$) to the dataset $[X, y]$, creating $r$ coded shards $[\bar{X}_i, \bar{y}_i]$. Each coded sample is a linear combination of multiple original samples.
  2. Learning: Each coded shard is assigned to a weak learner $\mathfrak{L}_i$. Due to the coding, each learner indirectly captures more global information than in a standard split.
  3. Aggregation: The outputs $f_i^*$ of the weak learners are combined by an aggregator to produce the final model $f^*$.

When a deletion request arrives, the system identifies the affected coded shards, subtracts the influence of the deleted sample, and retrains only those specific learners. To handle non-linear relationships, the authors pair this approach with random projections, transforming features into a higher-dimensional space where linear regression can capture complex patterns.

Experimental Results

The protocol was evaluated on real-world regression datasets (e.g., Protein Tertiary Structure, Computer Activity) and synthetic heavy-tailed datasets. The results demonstrate several key insights:

  • Superior Trade-offs: Coded unlearning curves consistently sit below uncoded baselines, providing lower Mean Squared Error (MSE) for the same unlearning cost.
  • Robustness to Outliers: The benefits are most pronounced in datasets with influential outliers (heavy-tailed distributions). Coding spreads the influence of these samples across multiple learners, stabilizing the ensemble.
  • Perfect Unlearning: By focusing on ridge regression and linear encoders, the method guarantees that the retrained model is identical to one trained without the deleted data, satisfying the perfect unlearning criterion.

Conclusion

By treating training data as a signal to be encoded rather than a collection of independent rows, Coded Machine Unlearning provides a scalable blueprint for privacy-respecting AI. This framework allows systems to satisfy deletion requests efficiently without sacrificing significant model accuracy, particularly in datasets where influential samples otherwise dominate the learning process.

Summary updated

Abstract

There are applications that may require removing the trace of a sample from the system, e.g., a user requests their data to be deleted, or corrupted data is discovered. Simply removing a sample from storage units does not necessarily remove its entire trace since downstream machine learning models may store some information about the samples used to train them. A sample can be perfectly unlearned if we retrain all models that used it from scratch with that sample removed from their training dataset. When multiple such unlearning requests are expected to be served, unlearning by retraining becomes prohibitively expensive. Ensemble learning enables the training data to be split into smaller disjoint shards that are assigned to non-communicating weak learners. Each shard is used to produce a weak model. These models are then aggregated to produce the final central model. This setup introduces an inherent trade-off between performance and unlearning cost, as reducing the shard size reduces the unlearning cost but may cause degradation in performance. In this paper, we propose a coded learning protocol where we utilize linear encoders to encode the training data into shards prior to the learning phase. We also present the corresponding unlearning protocol and show that it satisfies the perfect unlearning criterion. Our experimental results show that the proposed coded machine unlearning provides a better performance versus unlearning cost trade-off compared to the uncoded baseline.
BibTeX
@inproceedings{aldaghri2021coded,
  author = {Nasser Aldaghri and Hessam Mahdavifar and Ahmad Beirami},
  title = {{Coded Machine Unlearning}},
  booktitle = {IEEE Access},
  year = {2021},
  url = {https://openreview.net/forum?id=UJGf_F3buF5},
}
Figure