TL;DR
Starfish is a novel framework for privacy-preserving Federated Unlearning (FU) that allows a central system to "forget" a specific client's data without ever seeing their raw gradients. By leveraging Two-Party Computation (2PC) and clever algorithmic optimizations like selective round processing, it provides a "certified" removal guarantee—mathematically proving the unlearned model is nearly identical to one retrained from scratch—while protecting against data leakage attacks.
What Problem Does This Paper Address?
In Federated Learning (FL), models are trained across many decentralized devices. However, regulations like GDPR grant users the "Right to be Forgotten," requiring their data's influence to be removed from a trained model (Federated Unlearning).
Existing state-of-the-art unlearning methods (like FedRecover) require the server to store historical gradients from all clients to "roll back" and recalibrate the model. The problem? Gradients aren't perfectly private. Research into Deep Leakage from Gradient (DLG) has shown that an adversarial server can reconstruct a user's private images or text just by looking at their uploaded gradients. This creates a paradox: to unlearn a user for privacy reasons, you must store data that inherently violates their privacy.
Methods
The authors propose Starfish, which moves the unlearning process into a secure, multi-party environment.
- Two-Party Computation (2PC): Instead of one server, Starfish uses two non-colluding servers. Clients "secret-share" their gradients between these two servers. No single server ever sees the actual gradient values; they only see random-looking "shares."
- Selective Round Selection (SecRS): Unlearning every single training round is computationally expensive in 2PC. Starfish identifies the "most influential" rounds—those where the target client's update most closely aligned with the global model's direction (using cosine similarity)—and only performs recalibration on those rounds.
- 2PC-Friendly Optimizations:
- Pre-computation: Clients compute the $\ell_2$-norm of their gradients locally, sparing the servers from performing expensive "secure square root" operations.
- Division-to-Multiplication: To sort rounds by influence, the authors replace secure division with a cross-multiplication comparison, significantly reducing communication overhead.
- Switching Threshold ($T_\delta$): The system dynamically chooses between two sorting methods based on the number of rounds to maximize efficiency.
- L-BFGS Approximation: To avoid having all remaining clients re-train their models, the servers use a quasi-Newton method (L-BFGS) to estimate how the remaining clients would have updated if the target client had never existed.
Datasets
The framework was evaluated on three standard machine learning benchmarks:
- MNIST: Handwritten digits (the "Hello World" of ML).
- Fashion-MNIST: Images of clothing items.
- CIFAR-10: A more complex dataset of 10 different object classes (airplanes, cats, etc.).
Key Insights and Ideas
- The "Aha" Moment on Round Selection: The authors observed that a client’s contribution isn't uniform across all training rounds. By selecting only the top $\sigma$ fraction of rounds (e.g., 60%), they can achieve unlearning performance nearly identical to processing 100% of rounds, but at a fraction of the 2PC cost.
- Certified Removal: The paper provides a theoretical bound (Theorem 1) that quantifies the distance between the Starfish-unlearned model and a "gold standard" model retrained from scratch. This moves FU from "heuristic-based" to "provably effective."
- Engineering around 2PC Bottlenecks: 2PC is notoriously slow for non-linear operations like division and square roots. By shifting these operations to the client or transforming them into linear comparisons, the authors made a theoretically "heavy" cryptographic process practically viable.
Key Results
- Unlearning Effectiveness: Starfish achieved Test Error Rates (TER) and Attack Success Rates (ASR) comparable to FedRecover (the non-private baseline). It effectively removed backdoor triggers and membership information.
- Efficiency: Through selective round selection, Starfish achieved a high Average Round-saving Percentage (ARP), meaning it could skip many rounds of computation without losing accuracy.
- 2PC Gains: The optimized round selection (Method 2) was significantly faster than the naive version. For the MNIST dataset, the online communication for a single unlearning round was reduced to roughly 0.34 GB, making it manageable for modern data centers.
Limitations and Future Work
- Semi-Honest Assumption: The current threat model assumes servers are "honest-but-curious" (they follow the rules but try to learn what they can). It does not yet account for "active" malicious servers that might intentionally provide wrong calculations to sabotage the model.
- Communication Overhead: While optimized, 2PC still requires significant data transfer (gigabytes per round). In wide-area network (WAN) settings with high latency, the unlearning process can still take several hours.
- Active Malicious Defense: The authors suggest that future work could integrate consistency checks or verifiable computation to defend against servers that deviate from the protocol.
Reference: Liu, Z., et al. (2024). Privacy-Preserving Federated Unlearning with Certified Client Removal. arXiv:2404.09724v1.
Summary updated