There are applications that may require removing the trace of a sample from
the system, e.g., a user requests their data to be deleted, or corrupted data
is discovered. Simply removing a sample from storage units does not necessarily
remove its entire trace since downstream machine learning models may store some
information about the samples used to train them. A sample can be perfectly
unlearned if we retrain all models that used it from scratch with that sample
removed from their training dataset. When multiple such unlearning requests are
expected to be served, unlearning by retraining becomes prohibitively
expensive. Ensemble learning enables the training data to be split into smaller
disjoint shards that are assigned to non-communicating weak learners. Each
shard is used to produce a weak model. These models are then aggregated to
produce the final central model. This setup introduces an inherent trade-off
between performance and unlearning cost, as reducing the shard size reduces the
unlearning cost but may cause degradation in performance. In this paper, we
propose a coded learning protocol where we utilize linear encoders to encode
the training data into shards prior to the learning phase. We also present the
corresponding unlearning protocol and show that it satisfies the perfect
unlearning criterion. Our experimental results show that the proposed coded
machine unlearning provides a better performance versus unlearning cost
trade-off compared to the uncoded baseline.

本文提出了一种编码学习协议，其利用线性编码器将训练数据编码成碎片，以便进行学习和 “完美取消学习”（unlearning），实验结果表明，相比未编码的基线，该编码机器学习方法提供了更好的性能与取消学习成本的平衡。

编码的机器遗忘

Coded Machine Unlearning

Linear encoding of sparse vectors is widely popular, but is commonly
data-independent -- missing any possible extra (but a priori unknown) structure
beyond sparsity. In this paper we present a new method to learn linear encoders
that adapt to data, while still performing well with the widely used $\ell_1$
decoder. The convex $\ell_1$ decoder prevents gradient propagation as needed in
standard gradient-based training. Our method is based on the insight that
unrolling the convex decoder into $T$ projected subgradient steps can address
this issue. Our method can be seen as a data-driven way to learn a compressed
sensing measurement matrix. We compare the empirical performance of 10
algorithms over 6 sparse datasets (3 synthetic and 3 real). Our experiments
show that there is indeed additional structure beyond sparsity in the real
datasets; our method is able to discover it and exploit it to create excellent
reconstructions with fewer measurements (by a factor of 1.1-3x) compared to the
previous state-of-the-art methods. We illustrate an application of our method
in learning label embeddings for extreme multi-label classification, and
empirically show that our method is able to match or outperform the precision
scores of SLEEC, which is one of the state-of-the-art embedding-based
approaches.

本文介绍了一种新的方法来学习线性编码器，以适应数据，同时仍然能够与广泛使用的 l1 解码器表现良好。该方法通过将凸 l1 解码器展开为 T 个项目次梯度步骤来解决无法在标准梯度训练中进行梯度传播的问题。实验结果表明，我们的方法能够发现并利用稀疏向量之外的额外结构，在进行少量测量的情况下，比以前的最先进方法显着提高了重建效果，并且在极端多标签分类任务中，能够匹配或超越 SLEEC 的精度得分。