Certifying the Right to Be Forgotten: Primal–Dual Optimization for Sample and Label Unlearning in Vertical Federated Learning

Yu Jiang, Xindi Tong, Ziyao Liu, Xiaoxi Zhang, Kwok-Yan Lam, Chee Wei Tan

TL;DR

The authors introduce FedORA, a novel framework for "unlearning" specific data samples or entire labels in Vertical Federated Learning (VFL) environments. By treating unlearning as a constrained optimization problem solved via a primal-dual approach, FedORA effectively removes the influence of sensitive data while maintaining high model utility, significantly outperforming traditional gradient-ascent methods in both stability and efficiency.

What Problem Does This Paper Address?

In the era of privacy regulations like GDPR, users have the "right to be forgotten," meaning AI models must be able to "forget" specific data points upon request. This is particularly challenging in Vertical Federated Learning (VFL), where different parties hold different features of the same users (e.g., a bank has financial data while a retailer has purchase history).

Because features are interdependent across parties, removing a sample's influence requires complex coordination. Existing methods often rely on "Gradient Ascent" (purposely increasing the loss on the data to be forgotten), but this is notoriously unstable. It often leads to catastrophic forgetting, where the model loses its general intelligence while trying to forget a single data point, or it fails to remove the data's influence entirely.

Methods

The researchers propose FedORA (Federated Optimization for data Removal via primal-dual Algorithm). Its core innovations include:

  1. Primal-Dual Formulation: Instead of a simple heuristic, they frame unlearning as a constrained optimization problem: minimize the loss on the remaining data (the Primal task) while ensuring the loss on the to-be-forgotten data stays above a certain threshold (the Dual constraint).
  2. Uncertainty-Based Loss: Standard unlearning tries to make the model "wrong" about the target data. FedORA instead pushes the model toward maximum uncertainty. It uses an entropy-based loss function that forces the model to output a uniform probability distribution for forgotten samples—essentially making the model admit, "I have no idea what this is."
  3. Asymmetric Batch Design: To save on massive computational costs, FedORA processes the entire "unlearning" set in each round but only uses small, partial batches of the "remaining" data. This focuses resources on the forgetting task while doing just enough "fine-tuning" to keep the model's general performance sharp.
  4. Adaptive Step Sizes: The algorithm dynamically adjusts its learning rates based on how much the model parameters are changing, ensuring stable convergence.

Datasets

The authors evaluated FedORA across a diverse range of data types:

  • Income: A tabular dataset for binary classification.
  • MedMNIST: Biomedical images across 9 tissue types.
  • CIFAR-10 & CIFAR-100: Standard image recognition benchmarks.
  • Tiny-ImageNet: A more complex image dataset with 200 classes.

Key Insights and Ideas

  • Confusion is Better than Error: Forcing a model to be "confused" (high entropy) is more mathematically stable than forcing it to be "incorrect." This prevents the model from simply learning a new, incorrect pattern for the sensitive data.
  • The Dual Variable as a "Certificate": In their framework, the dual variable acts as a certificate of unlearning. It automatically increases "unlearning pressure" if the model still remembers the data and relaxes once the forgetting threshold is met.
  • Efficiency without Sacrifice: By using asymmetric batching, they proved that you don't need to re-process the entire remaining dataset to maintain accuracy. A small fraction is sufficient to "anchor" the model's knowledge.

Key Results

  • Utility Preservation: FedORA achieves test accuracy nearly identical to "Retrain-from-scratch" (the gold standard for unlearning). For example, on CIFAR-10, FedORA reached 81.65% accuracy compared to Retrain's 81.55%.
  • Unlearning Effectiveness: In label unlearning (removing an entire class), FedORA demonstrated superior forgetting. On MedMNIST, it achieved an unlearning accuracy of 8.61% (lower is better, indicating the model truly forgot), while the next best baseline was over 13%.
  • Speedup: FedORA is significantly faster than retraining. On the Tiny-ImageNet dataset, it reduced the unlearning time from 62.24 seconds to 23.50 seconds per round.
  • Attack Resilience: The model showed strong resistance to Membership Inference Attacks (MIA), meaning an attacker could not statistically determine if a "forgotten" sample was ever in the training set.

Limitations and Future Work

  • Scope of Unlearning: The current work focuses on deletion (removing data). The authors note that future work should address correction (updating a model when a label was originally wrong but the sample should remain).
  • Model Architecture: While tested on MLPs, ResNets, and DenseNets, the framework hasn't yet been applied to Large Language Models (LLMs) or Transformers in a VFL context.
  • Communication Overhead: While more efficient than retraining, VFL still requires multiple rounds of cross-party communication, which can be a bottleneck in low-bandwidth environments.

Summary updated

Abstract

Federated unlearning has become an attractive approach to address privacy concerns in collaborative machine learning, for situations when sensitive data is remembered by AI models during the machine learning process. It enables the removal of specific data influences from trained models, aligning with the growing emphasis on the “right to be forgotten.” While extensively studied in horizontal federated learning, unlearning in vertical federated learning (VFL) remains challenging due to the distributed feature architecture. VFL unlearning includes sample unlearning that removes specific data points’ influence and label unlearning that removes entire classes. Since different parties hold complementary features of the same samples, unlearning tasks require cross-party coordination, creating computational overhead and complexities from feature interdependencies.To address such challenges, we propose FedORA (Federated Optimization for data Removal via primal-dual Algorithm), designed for sample and label unlearning in VFL. FedORA formulates the removal of certain samples or labels as a constrained optimization problem solved using a primal-dual framework. Our approach introduces a new unlearning loss function that promotes classification uncertainty rather than misclassification. An adaptive step size enhances stability, while an asymmetric batch design, considering the prior influence of the remaining data on the model, handles unlearning and retained data differently to efficiently reduce computational costs. We provide theoretical analysis proving that the model difference between FedORA and Train-from-scratch is bounded, establishing guarantees for unlearning effectiveness. Experiments on tabular and image datasets demonstrate that FedORA achieves unlearning effectiveness and utility preservation comparable to Train-from-scratch with reduced computation and communication overhead.
BibTeX
@article{jiang2025certifying,
  author = {Yu Jiang and Xindi Tong and Ziyao Liu and Xiaoxi Zhang and Kwok-Yan Lam and Chee Wei Tan},
  title = {{Certifying the Right to Be Forgotten: Primal–Dual Optimization for Sample and Label Unlearning in Vertical Federated Learning}},
  journal = {IEEE Transactions on Information Forensics and Security},
  year = {2025},
  url = {https://openreview.net/forum?id=PvtF7UIt8C},
}

Loading related content...

Figure