PaperlayerView exact revision on arXiv

Source-linked AI summary

The Right to be Forgotten in Federated Learning: An Efficient Realization with Rapid Retraining

Yi Liu, Lei Xu, Xingliang Yuan, Cong Wang, Bo Li

arXiv:2203.07320v1cs.CRcs.LG

TL;DR

Federated learning makes machine unlearning difficult because centralized methods assume server access to all training data, while frequent full retraining is costly. This paper formalizes federated unlearning and proposes rapid distributed retraining using Taylor approximation, diagonal empirical FIM, and momentum, with theoretical and experimental support for efficient unlearning.

  • Problem

    Existing machine unlearning methods primarily assume centralized training with all data collected at a server, whereas federated unlearning must erase data while preserving local data ownership and avoiding costly repeated retraining.

  • Method

    The paper proposes a model-agnostic distributed Newton-type rapid retraining algorithm using first-order Taylor approximation, diagonal empirical FIM, and momentum within a federated unlearning pipeline.

  • Results

    The algorithm converges to the true optimization path for strongly convex objectives, uses O(db) memory for estimated diagonal Fisher information, and achieves higher data-erasure efficiency than the baseline across evaluated datasets.

  • Takeaways & Limitations

    The design supports efficient federated data deletion while retaining training data locally and preserving model utility, with empirical support on medium-scale public datasets.

Abstract

from arXiv · show

In Machine Learning, the emergence of \textit{the right to be forgotten} gave birth to a paradigm named \textit{machine unlearning}, which enables data holders to proactively erase their data from a trained model. Existing machine unlearning techniques focus on centralized training, where access to all holders' training data is a must for the server to conduct the unlearning process. It remains largely underexplored about how to achieve unlearning when full access to all training data becomes unavailable. One noteworthy example is Federated Learning (FL), where each participating data holder trains locally, without sharing their training data to the central server. In this paper, we investigate the problem of machine unlearning in FL systems. We start with a formal definition of the unlearning problem in FL and propose a rapid retraining approach to fully erase data samples from a trained FL model. The resulting design allows data holders to jointly conduct the unlearning process efficiently while keeping their training data locally. Our formal convergence and complexity analysis demonstrate that our design can preserve model utility with high efficiency. Extensive evaluations on four real-world datasets illustrate the effectiveness and performance of our proposed realization.

I. INTRODUCTION

The paper addresses federated machine unlearning, where raw data remain local and centralized unlearning methods cannot be directly used. It formalizes the problem and proposes rapid retraining with theoretical and empirical support.

  • Federated learning complicates unlearning because clients share knowledge through iterative model aggregation without sharing raw data.The server must erase client-data contributions that have propagated through interactive training.
  • The paper proposes retraining among all data holders to remove erased samples while preserving model utility.Its algorithm is model agnostic and can integrate naturally into federated learning.
  • The method combines first-order Taylor approximation, diagonal empirical Fisher Information Matrix estimates, and adaptive momentum.These choices reduce Hessian computation and approximation error while supporting faster, more stable convergence.
  • Theoretical analysis shows convergence to the true optimization path for strongly convex objectives and analyzes time and space complexity.
  • 9.1× speedup with an accuracy loss of 2.235 ×10−3 is reported on CelebA compared with baseline retraining.Experiments cover four datasets and assess unlearning, efficiency, model performance, and parameter sensitivity.
  • Prior exact and approximate unlearning methods generally do not directly address complex nonlinear models and federated data contributions.Centralized methods require server access to raw data, which is unavailable in federated learning.

B. Machine Unlearning Pipeline

The machine unlearning pipeline extends ordinary machine-learning deployment with data deletion and retraining after deletion requests. Its unlearning objective is to train on the remaining dataset rather than the deleted samples.

  • Machine unlearning adds data deletion to the training, inference, incremental-update, and retraining lifecycle.
  • After deletion, the available dataset becomes D ← D\Dm, where Dm is the deleted subset.
  • The inference stage uses the currently available model to produce predictions for submitted samples.
  • The unlearning stage obtains Du ← D\Dm and seeks to erase Dm's contribution from the current model.Retraining from scratch with mini-batch SGD over Du is the naive method.

IV. PROBLEM DEFINITION

Federated unlearning lets clients request deletion of local samples and evaluates success by comparing the resulting model with the original federated model. The formal objective is an ε-identical model distribution after erasure.

  • The framework distinguishes learned clients from unlearned clients and allows unlearned clients to request deletion of specific local samples.
  • A deletion operation is a data sample paired with a deletion request, and each client removes its requested sequence from its local dataset.The deleted sample count is Rk, typically much smaller than the local dataset size nk.
  • Federated unlearning requires the server to remove an unlearned client's data contribution and retrain the global model.
  • The unlearned model should have comparable test accuracy to the original model despite stochastic learning.
  • Unlearning is achieved when the distributions of the original and unlearned models are ε-identical for a threshold ε ≥ 0.The paper treats the unlearning algorithm's output as a training algorithm providing this distributional guarantee.

B. Goals of Federated Unlearning

Federated unlearning must remove erased data contributions, preserve client privacy and comparable accuracy, and reduce retraining cost. The proposed pipeline uses deletion, rapid local retraining, and server aggregation.

  • Goals of Federated Unlearning: The baseline retrains the global model from scratch on remaining data, but its computing and communication overhead makes frequent deletion impractical.
  • Goals of Federated Unlearning: The design targets zero contribution guarantees, privacy guarantees, comparable accuracy, and reduced retraining time.
  • Federated Unlearning Pipeline: The federated unlearning pipeline contains training, inference, and unlearning stages.
  • Federated Unlearning Pipeline: The unlearning stage performs data deletion followed by rapid retraining on each client's remaining local dataset.
  • Federated Unlearning Pipeline: After local unlearning, clients upload updates and the server aggregates them into a new unlearned global model.User-defined aggregation rules can also be used without changing the pipeline operations.

B. Federated Rapid Retraining

The paper proposes federated rapid retraining to erase deleted samples without accessing centralized raw data, using Newton-type updates and low-cost Hessian approximations. The algorithm combines diagonal empirical FIM approximation, adaptive momentum, and federated aggregation to reduce retraining cost while preserving utility.

  • The baseline retrains from scratch on remaining data, but is time- and resource-consuming for large federated models.Existing centralized unlearning methods also require raw-data access, which is unavailable in FL.
  • The proposed solution uses a distributed Newton-type update with first-order Taylor expansion to rapidly retrain clients on data remaining after deletion.The approach is designed to eliminate deleted samples’ contributions while preserving model utility.
  • Historical-gradient methods such as L-BFGS have O(mn) time and space complexity but are effective only for models with small parameter counts.The paper motivates a low-cost Hessian approximation that avoids storing historical parameter-gradient pairs.
  • A diagonal empirical FIM approximates the Hessian, reducing the computation and storage needed for inverse-Hessian updates.The outer product of gradients provides an asymptotically unbiased Hessian estimate under the stated conditions.
  • Adaptive momentum is applied to the Hessian diagonal to reduce approximation errors and stabilize convergence under iterative FL updates.The technique uses first- and second-order moments inspired by Adam and RMSProp.
  • Unlearned clients train on locally deleted datasets, normal clients retain their original datasets, and the server aggregates updates such as FedAvg.The algorithm begins with mini-batch deletion operations and then performs the unlearning stage across clients.

A. Convergence Analysis

The convergence analysis studies the rapid retraining algorithm under bounded-gradient, Lipschitz, smoothness, and strong-convexity assumptions. It establishes convergence behavior for strongly convex objectives and shows that FIM-based Hessian approximation preserves the relevant descent inequality.

  • The analysis assumes bounded gradients, Lipschitz continuity, strong convexity, smoothness, and twice continuous differentiability.These assumptions define the conditions used to analyze the retraining algorithm.
  • Theorem 1 gives a convergence result when the objective is strongly convex and smooth and the bounded-gradient assumption holds.The theorem is presented as the main convergence guarantee for Algorithm 1.
  • With step size η_t = µ/ρ, the objective is shown to decrease under the stated smoothness and strong-convexity conditions.The proof uses the relationship between the Hessian and the update direction.
  • Using FIM to approximate the Hessian preserves the descent inequality, and the result holds for either the diagonal FIM or the full FIM.The analysis also considers the limiting behavior as t →∞, when the parameter approaches the relevant optimum.

B. Complexity Analysis

The analysis characterizes the proposed algorithm’s computational costs and its speed-up formulation, while using diagonal Fisher information to reduce memory requirements.

  • Time Complexity: The baseline’s per-sample derivative computation has total complexity 6f(p), where f(p) is forward-propagation time.The analysis defines p as the number of model parameters, n as the number of samples, and d as feature dimension.
  • Time Complexity: The speed-up factor v is defined from the running times of one proposed-algorithm round and one baseline-training round.The proposed round time is denoted tu, while the baseline round time is tb.
  • Time Complexity: Computing the diagonal Fisher information estimate costs one gradient backpropagation, expressed as kO(b(B −∆B)d) ≈5kf(p).The estimate uses the diagonal Fisher information matrix to support the proposed update.
  • Space Complexity: The diagonal Fisher-information approximation requires O(db) memory when implemented with blocks of size b.The experiments indicate that this memory design supports fairly large models and sample sets.

A. Experiment Setup

The evaluation uses four public image datasets and corresponding neural models, with experiments implemented in Python and PyTorch on a specified GPU and CPU server.

  • Implementation: Experiments were developed with Python 3.7 and PyTorch 1.7 on an NVIDIA GeForce RTX2080 Ti GPU and Intel Xeon Silver 4210 CPU.The reported hardware and software specify the execution environment for the evaluation.
  • Datasets: The experiments use MNIST, Fashion-MNIST, CIFAR-10, and CelebA, covering different attributes, dimensions, and category counts.The datasets are evenly distributed among clients to simulate federated learning.
  • Models: The study uses a CNN for MNIST and Fashion-MNIST, AlexNet for CIFAR-10, and ResNet-18 for CelebA gender classification.The models correspond to the classification tasks defined for each dataset.
  • Hyperparameters: The cross-silo setup uses K = 10 clients, full participation q = 1, one local epoch, and T = 200 training rounds.The learning rate is η = 0.001 and the block size is b = 3.
  • Hyperparameters: Mini-batch size B varies over {128, 256, 512, 1024, 2048}, while deletion rate r varies over {2%, 1.5%, 1%, 0.5%}.These settings support evaluation of parameter sensitivity and deletion-rate effects.

B. Evaluation

The evaluation measures erasure efficiency, model utility, parameter sensitivity, and unlearning effectiveness. The proposed algorithm consistently accelerates retraining while maintaining utility comparable to the baseline.

  • The evaluation covers speed-up, accuracy and SAPE, parameter sensitivity, and experimental evidence of effective data erasure.
  • Data erasure efficiency: 7.1x and 9.6x speed-ups are reported on CIFAR-10 and CelebA, respectively, with gradient and curvature information reducing retraining time.The baseline repeatedly recalculates gradient information for samples on large datasets.
  • Model utility: Algorithm 1 achieves model performance comparable to the baseline across deletion rates, with slightly higher MNIST performance at r = 0.5%.Momentum compensates for utility damage from diagonal empirical FIM Hessian approximation.
  • Parameter sensitivity: The parameter ku has no obvious effect on speed-up, whereas batch size B significantly affects speed-up.Efficiency is significantly higher than the baseline with large batch sizes because more samples improve diagonal empirical FIM estimates.
  • Unlearning effectiveness: For CelebA, SAPE is 9.772 ×10−4, indicating that Algorithm 1 and baseline models are approximately identical under the reported evaluation.

VIII. CONCLUSION

The paper presents a federated unlearning algorithm that combines rapid retraining with diagonal empirical FIM approximation and momentum. Theory and experiments support efficient and effective unlearning on medium-scale public datasets.

  • The algorithm provides efficient and effective unlearning services for data holders in federated learning.
  • First-order Taylor expansion and diagonal empirical FIM approximation customize the rapid retraining algorithm.
  • A momentum technique alleviates negative effects caused by approximation errors and supports model utility.
  • Comprehensive theoretical analysis and experimental support are provided, with empirical advantages shown on medium-scale public datasets.
Loading 2203.07320v1…