We study federated unlearning, a novel problem to eliminate the impact of
specific clients or data points on the global model learned via federated
learning (FL). This problem is driven by the right to be forgotten and the
privacy challenges in FL. We introduce a new framework for exact federated
unlearning that meets two essential criteria: \textit{communication efficiency}
and \textit{exact unlearning provability}. To our knowledge, this is the first
work to tackle both aspects coherently. We start by giving a rigorous
definition of \textit{exact} federated unlearning, which guarantees that the
unlearned model is statistically indistinguishable from the one trained without
the deleted data. We then pinpoint the key property that enables fast exact
federated unlearning: total variation (TV) stability, which measures the
sensitivity of the model parameters to slight changes in the dataset.
Leveraging this insight, we develop a TV-stable FL algorithm called
\texttt{FATS}, which modifies the classical
\texttt{\underline{F}ed\underline{A}vg} algorithm for \underline{T}V
\underline{S}tability and employs local SGD with periodic averaging to lower
the communication round. We also design efficient unlearning algorithms for
\texttt{FATS} under two settings: client-level and sample-level unlearning. We
provide theoretical guarantees for our learning and unlearning algorithms,
proving that they achieve exact federated unlearning with reasonable
convergence rates for both the original and unlearned models. We empirically
validate our framework on 6 benchmark datasets, and show its superiority over
state-of-the-art methods in terms of accuracy, communication cost, computation
cost, and unlearning efficacy.

研究联邦去学习问题，解决个别客户或数据对通过联邦学习得到的全局模型的影响，推导出所删除数据的无合差异性模型。引入了一种新的完全联邦去学习框架，满足通信效率和完全去学习可证明性的两个基本条件。通过定义确切的联邦去学习，保证无学习之后的模型与未删除数据时训练的模型在统计上无差异。利用模型参数对数据集轻微变化的变动程度来实现快速联邦去学习的关键特性：总变差稳定性。利用这一洞见，我们开发了一种名为 FATS 的总变差稳定的联邦学习算法，修改了经典的 FedAvg 算法以实现轮次通信的降低。我们还设计了针对 FATS 的高效去学习算法，包括客户级和样本级的去学习。我们提供了学习和去学习算法的理论保证，证明它们在原始模型和去学习模型上都达到了确切的联邦去学习，并具有合理的收敛速度。在 6 个基准数据集上经过实证验证，展示了该框架在准确性、通信成本、计算成本和去学习效果方面的优越性。