Machine Unlearning as Private Retroactive Algorithms

• URL: http://arxiv.org/abs/2609.05329v1
• Date: Fri, 04 Sep 2026 16:32:11 GMT
• Title: Machine Unlearning as Private Retroactive Algorithms
• Abstract summary: We present a definition of retroactive algorithms, combining the retroactivity requirement with differential privacy under continual observation.<n>We present constructions achieving both privacy and retroactivity at no cost over privacy alone for linear statistics, clustering, and histograms, alongside impossibility results.
• Score: 53.24897282360584
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• RPWithPrior: Label Differential Privacy in Regression [0.0]
  In this paper, we focus on regression tasks under $$-label differential privacy guarantees.<n>We model both original and randomized responses as continuous random variables, avoiding discretization entirely.<n>We prove that our algorithm, RPWithPrior, guarantees $$-label differential privacy.
  arXiv  Detail & Related papers  (2026-01-30T06:27:13Z)
• Zero-Shot Privacy-Aware Text Rewriting via Iterative Tree Search [60.197239728279534]
  Large language models (LLMs) in cloud-based services have raised significant privacy concerns.<n>Existing text anonymization and de-identification techniques, such as rule-based redaction and scrubbing, often struggle to balance privacy preservation with text naturalness and utility.<n>We propose a zero-shot, tree-search-based iterative sentence rewriting algorithm that systematically obfuscates or deletes private information while preserving coherence, relevance, and naturalness.
  arXiv  Detail & Related papers  (2025-09-25T07:23:52Z)
• Auditing Approximate Machine Unlearning for Differentially Private Models [14.700807572189412]
  We propose a holistic approach to auditing unlearned and retained samples' privacy risks after applying approximate unlearning algorithms.<n>Our experimental findings indicate that existing approximate machine unlearning algorithms may inadvertently compromise the privacy of retained samples for differentially private models.
  arXiv  Detail & Related papers  (2025-08-26T04:29:33Z)
• Linear-Time User-Level DP-SCO via Robust Statistics [55.350093142673316]
  User-level differentially private convex optimization (DP-SCO) has garnered significant attention due to the importance of safeguarding user privacy in machine learning applications.<n>Current methods, such as those based on differentially private gradient descent (DP-SGD), often struggle with high noise accumulation and suboptimal utility.<n>We introduce a novel linear-time algorithm that leverages robust statistics, specifically the median and trimmed mean, to overcome these challenges.
  arXiv  Detail & Related papers  (2025-02-13T02:05:45Z)
• Rewind-to-Delete: Certified Machine Unlearning for Nonconvex Functions [22.183624306817563]
  Machine unlearning algorithms aim to efficiently data from a model without it from scratch.<n> certified machine unlearning is a strong theoretical guarantee based on differential generalization.
  arXiv  Detail & Related papers  (2024-09-15T15:58:08Z)
• MUSE: Machine Unlearning Six-Way Evaluation for Language Models [109.76505405962783]
  Language models (LMs) are trained on vast amounts of text data, which may include private and copyrighted content. We propose MUSE, a comprehensive machine unlearning evaluation benchmark. We benchmark how effectively eight popular unlearning algorithms can unlearn Harry Potter books and news articles.
  arXiv  Detail & Related papers  (2024-07-08T23:47:29Z)
• Langevin Unlearning: A New Perspective of Noisy Gradient Descent for Machine Unlearning [28.839200263095137]
  Privacy is defined as statistical indistinguishability to retraining from scratch.<n>We propose Langevin unlearning, an unlearning framework based on a gradient descent.
  arXiv  Detail & Related papers  (2024-01-18T20:35:47Z)
• Topology-Based Reconstruction Prevention for Decentralised Learning [16.09412208373314]
  We show that passive honest-but-curious adversaries can infer other users' private data after several privacy-preserving summations.<n>We propose the first topology-based decentralised defence against reconstruction attacks.
  arXiv  Detail & Related papers  (2023-12-08T18:55:40Z)
• Differentially Private Linear Regression with Linked Data [3.9325957466009203]
  Differential privacy, a mathematical notion from computer science, is a rising tool offering robust privacy guarantees. Recent work focuses on developing differentially private versions of individual statistical and machine learning tasks. We present two differentially private algorithms for linear regression with linked data.
  arXiv  Detail & Related papers  (2023-08-01T21:00:19Z)
• Tight Auditing of Differentially Private Machine Learning [77.38590306275877]
  For private machine learning, existing auditing mechanisms are tight. They only give tight estimates under implausible worst-case assumptions. We design an improved auditing scheme that yields tight privacy estimates for natural (not adversarially crafted) datasets.
  arXiv  Detail & Related papers  (2023-02-15T21:40:33Z)
• Tighter Generalization Bounds for Iterative Differentially Private Learning Algorithms [95.73230376153872]
  This paper studies the relationship between generalization and privacy preservation in iterative learning algorithms by two sequential steps. We prove that $(varepsilon, delta)$-differential privacy implies an on-average generalization bound for multi-Database learning algorithms. We then investigate how the iterative nature shared by most learning algorithms influence privacy preservation and further generalization.
  arXiv  Detail & Related papers  (2020-07-18T09:12:03Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.