Coded Machine Unlearning

Nasser Aldaghri, Hessam Mahdavifar, Ahmad Beirami

In an era of increasing data privacy regulations like GDPR, the "right to be forgotten" isn't just a legal hurdle—it’s a significant technical challenge. When a user asks for their data to be deleted, simply wiping a row from a database isn't enough; the machine learning models trained on that data might still retain "traces" of it. This paper, "Coded Machine Unlearning," introduces a clever way to use information theory to make this "forgetting" process faster and more accurate.

TL;DR

The authors propose a "coded learning" framework that uses linear encoders to shard training data before it reaches a model. By training an ensemble of "weak learners" on these coded shards, they achieve a significantly better trade-off between model accuracy and the computational cost of unlearning data than traditional sharding methods.

What Problem Does This Paper Address?

The gold standard for machine unlearning is "perfect unlearning": retraining the model from scratch without the deleted sample. However, for massive datasets, retraining is prohibitively expensive.

A common shortcut is sharding: splitting the data into $s$ disjoint pieces, training a separate "weak learner" on each, and aggregating their predictions. If a user wants their data removed, you only have to retrain the specific weak learner that saw that data. The catch? Smaller shards make unlearning fast but hurt the final model's performance because each learner sees too little data. This paper aims to break that "performance vs. unlearning cost" bottleneck.

Methods

The authors introduce Coded Machine Unlearning. Instead of just splitting the data into raw chunks, they use a random linear coding scheme.

  1. Encoding: The master node takes the dataset and applies a linear encoder (a random binary matrix $G$) to create $r$ "coded shards." Each coded sample is actually a linear combination of multiple original samples.
  2. Learning: Each coded shard is sent to a "weak learner" (specifically for regression tasks). Because of the coding, each learner indirectly "sees" more of the original dataset than it would in a simple split.
  3. Unlearning: When a deletion request arrives, the system identifies which coded shards were affected. It subtracts the influence of the deleted sample from those shards and retrains only the affected weak 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 still capture complex patterns.

Datasets

The authors evaluated their protocol on three real-world regression datasets from the UCI repository and several synthetic ones:

  • Physicochemical Properties of Protein Tertiary Structure: Predicting protein structures.
  • Computer Activity: Estimating CPU performance.
  • Combined Cycle Power Plant: Predicting energy output.
  • Synthetic Datasets: Created using lognormal and chi-square distributions to simulate "heavy-tailed" data (data with many influential outliers) and non-linear relationships via Multi-Layer Perceptrons (MLPs).

Key Insights and Ideas

  • The "Influential Sample" Intuition: The biggest "aha moment" is why coding helps. In many datasets, a few "outlier" or "influential" samples dictate the model's boundaries. In uncoded sharding, if an influential sample falls into one small shard, that learner becomes biased. Coding spreads the influence of these samples across multiple learners, stabilizing the ensemble.
  • Heavy Tails Matter: The benefits of coded unlearning are most pronounced in datasets with heavy-tailed distributions. If your data is "well-behaved" (like a standard normal distribution), simple sharding performs fine. But for real-world data with outliers, coding is a clear winner.
  • Linearity is a Feature, Not a Bug: By focusing on ridge regression and linear encoders, the authors can guarantee "perfect unlearning." Because these models have unique global minimizers, retraining them (even using iterative methods) is guaranteed to produce the exact same model as if the deleted data never existed.

Key Results

The primary metric is the Mean Squared Error (MSE) vs. Unlearning Cost (retraining time).

  • Better Trade-offs: In the Protein and Computer Activity datasets, the "Coded" curves consistently sit below the "Uncoded" curves. This means for any given "budget" of retraining time, the coded approach yields a more accurate model.
  • Scalability: On a large synthetic dataset (600,000 samples), the authors showed that increasing the "rate" of the code allows them to significantly reduce unlearning costs while maintaining an MSE very close to the original, non-sharded algorithm.
  • Robustness to Regularization: The performance gains held steady across various levels of weight decay ($\lambda$), suggesting the method is robust for standard machine learning pipelines.

Limitations and Future Work

  • Regression Focus: Currently, the math is optimized for regression. While the authors mention random projections for non-linearity, extending this to complex classification tasks (like deep image recognition) remains an open challenge.
  • Linear Encoders: The paper uses random binary matrices. Exploring more sophisticated coding schemes from classical information theory might yield even better density/sparsity trade-offs.
  • Over-parameterization: The authors note that for models like deep neural networks where the training loss can hit zero (over-parameterized), simply starting retraining from the previous weights doesn't guarantee perfect unlearning. Future work is needed to bridge the gap between "perfect unlearning" and the "approximate unlearning" often used in deep learning.

By treating the training data as a signal to be encoded rather than just a pile of rows to be split, this paper provides a promising blueprint for building privacy-respecting AI that doesn't break the computational bank.

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},
}

Loading related content...

Figure