# From Adaptive Query Release to Machine Unlearning

arXiv: https://arxiv.org/abs/2307.11228 · HTML: https://mlsanity.com/paper/2307.11228/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Placed in Machine unlearning, one of 12 directions in LLM safety and security.
- Builds on 16 of its 33 references that are in the map.
- First posted on arXiv 20 Jul 2023.

## Placed in

- LLM safety and security / [Machine unlearning](https://mlsanity.com/safety/machine-unlearning/)

## Builds on (most cited first, 16 of 16)

- [Federated Learning: Strategies for Improving Communication Efficiency](https://mlsanity.com/paper/1610.05492/) (2016)
- [Machine Unlearning](https://mlsanity.com/paper/1912.03817/) (2019)
- [Renyi Differential Privacy](https://mlsanity.com/paper/1702.07476/) (2017)
- [Certified Data Removal from Machine Learning Models](https://mlsanity.com/paper/1911.03030/) (2019)
- [Making AI Forget You: Data Deletion in Machine Learning](https://mlsanity.com/paper/1907.05012/) (2019)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Remember What You Want to Forget: Algorithms for Machine Unlearning](https://mlsanity.com/paper/2103.03279/) (2021)
- [Descent-to-Delete: Gradient-Based Methods for Machine Unlearning](https://mlsanity.com/paper/2007.02923/) (2020)
- [Subsampled R'enyi Differential Privacy and Analytical Moments Accountant](https://mlsanity.com/paper/1808.00087/) (2018)
- [Adaptive Machine Unlearning](https://mlsanity.com/paper/2106.04378/) (2021)
- [Practical and Private (Deep) Learning without Sampling or Shuffling](https://mlsanity.com/paper/2103.00039/) (2021)
- [Machine Unlearning for Random Forests](https://mlsanity.com/paper/2009.05567/) (2020)
- [Machine Unlearning via Algorithmic Stability](https://mlsanity.com/paper/2102.13179/) (2021)
- [Hybrid Stochastic Gradient Descent Algorithms for Stochastic Nonconvex Optimization](https://mlsanity.com/paper/1905.05920/) (2019)
- [One Sample Stochastic Frank-Wolfe](https://mlsanity.com/paper/1910.04322/) (2019)
- [Differentially Private Generalized Linear Models Revisited](https://mlsanity.com/paper/2205.03014/) (2022)

## Built on by (most cited first, 10 of 10)

- [Langevin Unlearning: A New Perspective of Noisy Gradient Descent for Machine Unlearning](https://mlsanity.com/paper/2401.10371/) (2024)
- [Certified Machine Unlearning via Noisy Stochastic Gradient Descent](https://mlsanity.com/paper/2403.17105/) (2024)
- [Underestimated Privacy Risks for Minority Populations in Large Language Model Unlearning](https://mlsanity.com/paper/2412.08559/) (2024)
- [When to Forget? Complexity Trade-offs in Machine Unlearning](https://mlsanity.com/paper/2502.17323/) (2025)
- [To Erase, or Not to Erase: Robust Training-Free Concept Erasure with Preservation aware Adaptive Ranked Subspace Expansion](https://mlsanity.com/paper/2607.23492/) (2026)
- [ModHiFi: Identifying High Fidelity predictive components for Model Modification](https://mlsanity.com/paper/2511.19566/) (2025)
- [Exact Unlearning in Reinforcement Learning](https://mlsanity.com/paper/2606.04182/) (2026)
- [Machine Unlearning with Minimal Gradient Dependence for High Unlearning Ratios](https://mlsanity.com/paper/2406.16986/) (2024)
- [Variance-Reduced (varepsilon,δ)-Unlearning using Forget Set Gradients](https://mlsanity.com/paper/2602.14938/) (2026)
- [SoK: Unlearnability and Unlearning for Model Dememorization](https://mlsanity.com/paper/2605.11592/) (2026)

## Abstract (arXiv)

We formalize the problem of machine unlearning as design of efficient unlearning algorithms corresponding to learning algorithms which perform a selection of adaptive queries from structured query classes. We give efficient unlearning algorithms for linear and prefix-sum query classes. As applications, we show that unlearning in many problems, in particular, stochastic convex optimization (SCO), can be reduced to the above, yielding improved guarantees for the problem. In particular, for smooth Lipschitz losses and any ρ>0, our results yield an unlearning algorithm with excess population risk of tilde Obig(frac1√n+frac√dnρbig) with unlearning query (gradient) complexity tilde O(ρ · Retraining Complexity), where d is the model dimensionality and n is the initial number of samples. For non-smooth Lipschitz losses, we give an unlearning algorithm with excess population risk tilde Obig(frac1√n+big(frac√dnρbig)1/2big) with the same unlearning query (gradient) complexity. Furthermore, in the special case of Generalized Linear Models (GLMs), such as those in linear and logistic regression, we get dimension-independent rates of tilde Obig(frac1√n +frac1(nρ)2/3big) and tilde Obig(frac1√n +frac1(nρ)1/3big) for smooth Lipschitz and non-smooth Lipschitz losses respectively. Finally, we give generalizations of the above from one unlearning request to textitdynamic streams consisting of insertions and deletions.