Research map / Federated learning and privacy / Differential privacy
The Utility and Complexity of In- and Out-of-Distribution Machine Unlearning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives certified approximate-unlearning guarantees (Rényi DP-style) and complexity trade-offs, showing noisy empirical risk minimization handles in-distribution forget data with dimension-free deletion capacity, while a robust trimmed-mean gradient descent variant is needed to keep unlearning time bounded for out-of-distribution forget data.
Problem
Approximate machine unlearning lacks formal utility-time-space trade-off guarantees, especially when forget data is out-of-distribution, where unlearning time can blow up relative to retraining.
Approach
Analyze approximate unlearning via empirical risk minimization with Gaussian output perturbation, deriving deletion capacity bounds that are dimension-independent in-distribution; for OOD forget data, train with coordinate-wise trimmed-mean gradient descent so the retain-set minimizer is a good initialization for unlearning regardless of forget data.
Key results
- Noisy gradient descent with output perturbation achieves in-distribution utility deletion capacity Omega(n sqrt(alpha)), dimension-independent, improving on Omega(1/d^{1/4}) Newton-based bounds.
- For out-of-distribution forget data, a single sample can make unlearning initialization error arbitrarily large, so plain output-perturbation unlearning time can exceed retraining time.
- Robust trimmed-mean gradient descent gives OOD utility deletion capacity Omega(n) with unlearning time independent of the forget data, governed by retain-set interpolation error.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use gradient descent with output perturbation for in-distribution unlearning instead of lazy differential privacy | Approximate machine unlearning · In-distribution deletion capacity | utility deletion capacity: $\Omega(n \sqrt{\alpha})$ versus $\widetilde{\Theta}\left(n \sqrt{\tfrac{\alpha \varepsilon}{d}}\right)$ | Helped |
| Use gradient descent with output perturbation instead of the Newton-step method | Approximate machine unlearning · In-distribution deletion capacity | computational deletion capacity: $\Omega\left(n \tfrac{\alpha \varepsilon \exp(T/2nd)}{R d \|\ttheta_0 - \ttheta^\star_{\mathcal{S}}\|}\right)$ versus $( | Helped |
| Use the standard noisy minimizer approximation on full training data rather than robust trimmed-mean training | Out-of-distribution unlearning · Out-of-distribution deletion capacity | computational deletion capacity (Non-Lipschitz): 0 versus $\Omega\left(n \frac{\alpha^2 \varepsilon^2 \exp(T/nd)}{\mathcal{E}(\retain)d^2 \|\ttheta_0 - \ttheta_{\retain} | Hurt |
| Use robust training with coordinate-wise trimmed-mean gradients before unlearning | Approximate machine unlearning · Out-of-distribution deletion capacity | utility deletion capacity: $n-1$ versus $\Omega(n)$ | Helped |
| Remove the assumption that the loss is Lipschitz by using robust training | Out-of-distribution unlearning · Out-of-distribution deletion capacity | computational deletion capacity: 0 versus $\Omega\left(n \frac{\alpha^2 \varepsilon^2 \exp(T/nd)}{\mathcal{E}(\retain)d^2 \|\ttheta_0 - \ttheta_{\retain} | Helped |
Surprising findings
- A single out-of-distribution forget sample can make the unlearning time of standard output-perturbation methods arbitrarily large, even exceeding retraining cost.
Limitations
- Analysis assumes strongly convex, smooth losses with a unique global minimizer
- Results for OOD robustness rely on trimming parameter tied to forget-set size and on interpolation error; experiments limited to linear regression on synthetic data
- Upper bound on joint deletion capacity remains open
Experimental setup
Datasets: synthetic least-squares regression data real data (appendix)
Metrics: excess population/empirical risk Rényi divergence unlearning guarantee unlearning time complexity
Baselines: Newton step unlearning differential privacy lazy unlearning sharding-based exact unlearning
Builds on: certified unlearning with output perturbation differential privacy (DP-SGD) Newton-step certified unlearning
Closest papers by meaning
- Langevin Unlearning: A New Perspective of Noisy Gradient Descent for Machine Unlearning (NeurIPS 2024 · similarity 0.94)
- Certified Machine Unlearning via Noisy Stochastic Gradient Descent (NeurIPS 2024 · similarity 0.94)
- Rewind-to-Delete: Certified Machine Unlearning for Nonconvex Functions (NeurIPS 2025 · similarity 0.93)
- Leveraging Per-Instance Privacy for Machine Unlearning (ICML 2025 · similarity 0.93)
- Certified Unlearning for Neural Networks (ICML 2025 · similarity 0.93)
- Towards Source-Free Machine Unlearning (CVPR 2025 · similarity 0.92)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.