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

Abstract

Federated unlearning has emerged as a critical mechanism for addressing privacy concerns in collaborative machine learning, particularly as global regulations emphasize the "right to be forgotten." While horizontal federated learning has seen significant progress, unlearning in Vertical Federated Learning (VFL) remains a formidable challenge due to the distributed nature of features across multiple parties. This paper introduces FedORA (Federated Optimization for data Removal via primal-dual Algorithm), a framework designed for both sample and label unlearning in VFL. By formulating unlearning as a constrained optimization problem solved through a primal-dual framework, FedORA ensures that specific data influences are removed while maintaining model utility. Our approach utilizes an uncertainty-based loss function, adaptive step sizes, and an asymmetric batch design to optimize for stability and computational efficiency. Theoretical analysis and experimental results across tabular and image datasets demonstrate that FedORA achieves unlearning effectiveness and utility preservation comparable to retraining from scratch, but with significantly reduced overhead.

Introduction

In the landscape of modern privacy regulations like GDPR, the "right to be forgotten" mandates that individuals have the power to request the removal of their data from trained AI models. This process, known as machine unlearning, is particularly complex in Vertical Federated Learning (VFL). In VFL, different organizations (parties) hold complementary features for the same set of users—for instance, a bank holding financial records and a retailer holding purchase histories.

Because features are interdependent across these parties, removing a single sample's influence requires intricate cross-party coordination. Traditional methods often rely on "Gradient Ascent," which attempts to unlearn by increasing the loss on the target data. However, this approach is notoriously unstable, often leading to catastrophic forgetting, where the model's general performance collapses, or incomplete unlearning, where sensitive data traces remain. FedORA addresses these challenges by reframing unlearning as a stable, constrained optimization problem.

The FedORA Framework

1. Primal-Dual Optimization

Instead of using heuristic-based gradient manipulation, FedORA treats unlearning as a dual-objective task. The Primal task focuses on minimizing the loss on the remaining (retained) data to preserve model utility. Simultaneously, the Dual constraint ensures that the loss on the data to be forgotten stays above a specific threshold. This framework allows the model to automatically adjust "unlearning pressure": if the model still shows signs of remembering the data, the dual variable increases the focus on forgetting; once the threshold is met, the pressure relaxes to protect general accuracy.

2. Uncertainty-Based Loss

A key innovation in FedORA is the shift from forcing misclassification to promoting maximum uncertainty. Standard unlearning methods try to make the model "wrong" about a sample. FedORA instead employs an entropy-based loss function that pushes the model toward a uniform probability distribution for forgotten samples. By making the model admit it has "no idea" what a forgotten sample represents, the algorithm achieves a more mathematically stable state than simply swapping one label for another.

3. Asymmetric Batch Design and Adaptive Steps

To mitigate the high computational costs of VFL, FedORA introduces an Asymmetric Batch Design. In each round, the algorithm processes the entire set of data to be forgotten but only uses a small, representative fraction of the remaining data. This "anchors" the model’s existing knowledge without the need to re-process the entire global dataset. Furthermore, Adaptive Step Sizes dynamically adjust learning rates based on parameter fluctuations, ensuring the model converges smoothly without the volatility typical of gradient ascent.

Experimental Evaluation

The researchers evaluated FedORA across diverse benchmarks, including tabular data (Income), biomedical images (MedMNIST), and standard image sets (CIFAR-10/100, Tiny-ImageNet).

Utility and Effectiveness

FedORA consistently matched the performance of "Retrain-from-scratch," which is considered the gold standard for unlearning but is often computationally prohibitive. On the CIFAR-10 dataset, FedORA achieved a test accuracy of 81.65%, nearly identical to the 81.55% achieved by full retraining.

In terms of unlearning effectiveness—measured by how poorly the model performs on the forgotten data—FedORA outperformed existing baselines. In label unlearning tasks on MedMNIST, FedORA reached an unlearning accuracy of 8.61% (where lower is better), significantly lower than the 13% seen in competing methods.

Efficiency and Security

FedORA demonstrated substantial speedups over retraining. For the Tiny-ImageNet dataset, the unlearning time per round was reduced from 62.24 seconds to 23.50 seconds. Additionally, the framework showed high resilience to Membership Inference Attacks (MIA). Statistical analysis confirmed that an attacker could not reliably distinguish whether a "forgotten" sample was ever part of the original training set, providing a robust certificate of privacy.

Conclusion and Future Work

FedORA provides a theoretically grounded and computationally efficient solution for the "right to be forgotten" in vertical federated environments. By prioritizing uncertainty over error and utilizing a primal-dual optimization strategy, it bridges the gap between privacy compliance and model utility.

While highly effective for deletion tasks in standard architectures, future research will explore extending FedORA to data correction (where a label is updated rather than deleted) and adapting the framework for Large Language Models (LLMs) and Transformer architectures within VFL contexts. As communication remains a bottleneck in distributed systems, further optimizing the cross-party exchange protocols remains a priority for the next iteration of federated unlearning research.

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