arXiv preprint ·
Machine Unlearning as Private Retroactive Algorithms
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
Machine unlearning typically aims to emulate retraining from scratch: upon a deletion request, the unlearning algorithm should produce an outcome that would have been obtained had the deleted point never been included. Recent work has shown that this emulation requirement carries no meaningful privacy semantics against an adversary who observes a sequence of releases. Machine unlearning is thus not a privacy question per se, but rather a data maintenance question, which is precisely the subject of retroactive algorithms. These are algorithms supporting modifications of past operations, guaranteeing that all subsequent answers reflect the revised history as if it had always been in force. We put forward a definition of private retroactive algorithms, combining the retroactivity requirement with differential privacy under continual observation. We present constructions achieving both privacy and retroactivity at no asymptotic cost over privacy alone for linear statistics, clustering, and histograms, alongside impossibility results.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Cryptography & Security
On Maximizing a Weakly Submodular Function over a Matroid Constraint via the Greedy Algorithm
Polynomial Lower Bounds for Distributed Graph Sketching with Tiny Error: Connectivity and Spanning Tree Construction
Algebraic Geometry Codes Approach the Half-Singleton Bound with Constant Field Size
Quantum Query Algorithms for the Constructive Diagonal Ramsey Theorem
Online Matching in Convex Bipartite Graphs
Get the few papers worth your time in Cryptography & Security every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.