Machine Unlearning for Federated Socially Fair k-Means Clustering
Aravind Reddy, Deeraj S K, Mohd Wasif Raza, Saurav Prakash
cs.LG
Oct 9, 2026 · v1
cs.DS
TL;DR
The supplement includes Lean 4/Mathlib proofs of the replay and certificate results, fair-update and sufficient-statistic results, lower-bound constructions, and approximation-transfer calculations.
Abstract
Federated clustering can support applications such as patient stratification across hospitals and customer segmentation across distributed financial datasets. Responsible AI calls for fair representation of demographic groups and support for data deletion, motivated in part by rights such as the GDPR's right to erasure. These goals interact: deleting records can change the balance between groups and alter the clustering of the remaining population. We study exact machine unlearning for federated socially fair $k$-means, whose objective is to minimize the largest group-average squared distance to the nearest center. Our approach keeps separate local summaries for each group, so summaries at unaffected institutions remain valid as global fairness weights change. For two groups, we prove an initialization approximation guarantee independent of client group proportions under ideal sampling, and we show that same-seed replay reproduces retraining exactly. Reuse pays off most when a whole client withdraws: across three datasets, replay is $35.8\times$ faster than retraining for the initialization-only model and remains $2.4\times$ and $1.7\times$ faster with one and two fair-refinement rounds, which improve worst-group cost. For individual record deletions, gains are modest (about $1.06\times$), and certifying cached assignments can cost more than it saves. These results map where exact unlearning can profitably reuse computation. Code and reproducibility materials are available at
https://github.com/arareddy/mufsc.
Problem
Federated socially fair k-means minimizes the worst group-average squared distance to centers. Honoring data-deletion requests can shift group balance, so exact unlearning, meaning output identical to retraining on the retained records with the same seed, must account for changing global fairness weights.
Approach
Each client keeps separate per-group local summaries, so summaries at unaffected institutions stay valid when global fairness weights change. Counts, vector sums and squared-norm sums are accumulated exactly in integer arithmetic over fixed-point data, enabling same-seed replay that reproduces retraining. The authors prove an O(log^2 k) initialization approximation guarantee for two groups that is independent of client group proportions, and show that a natural merged summary loses a Theta(kappa) factor. Mathematical results are formalized in Lean 4 with Mathlib in the supplement.
Results
All 810 replay comparisons matched fresh training exactly. Whole-client withdrawal replay was 35.8x faster than retraining for the initialization-only model, and 2.4x and 1.7x faster with one and two fair-refinement rounds. Individual record deletions gave only about 1.06x speedup, and certifying cached assignments could cost more than it saved.
| Dataset | Compact T=0 | Direct T=1 | Direct T=2 | Φ(T=0) | Φ(T=2) |
|---|
| Adult | 26.96 | 2.053 | 1.544 | 117.957 | 95.998 |
| Bank | 115.53 | 2.646 | 1.828 | 45.898 | 32.634 |
| Credit | 25.03 | 2.647 | 1.856 | 20.124 | 13.009 |
Whole-client withdrawal speedups over retraining and worst-group cost by refinement budget