Provable unlearning in topic modeling and downstream tasks
Authors: Stanley Wei
Sadhika Malladi
Sanjeev Arora
Amartya Sanyal
Venue: ICLR 2025 Poster (2025)
Keywords: Machine unlearning
topic models
language models
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation learning

Abstract: Machine unlearning algorithms are increasingly important as legal concerns arise around the provenance of training data, but verifying the success of unlearning is often difficult. Provable guarantees for unlearning are often limited to supervised learning settings. In this paper, we provide the first theoretical guarantees for unlearning in the pre-training and fine-tuning paradigm by studying topic models, simple bag-of-words language models that can be adapted to solve downstream tasks like retrieval and classification. First, we design a provably effective unlearning algorithm for topic models that incurs a computational overhead independent of the size of the original dataset. Our analysis additionally quantifies the deletion capacity of the model -- i.e., the number of examples that can be unlearned without incurring a significant cost in model performance. Finally, we formally extend our analyses to account for adaptation to a given downstream task. In particular, we design an efficient algorithm to perform unlearning after fine-tuning the topic model via a linear head. Notably, we show that it is easier to unlearn pre-training data from models that have been fine-tuned to a particular task, and one can unlearn this data without modifying the base model.

Published as a conference paper at ICLR 2025
PROVABLE UNLEARNING IN TOPIC MODELING AND DOWNSTREAM TASKS
Stanley Wei', Sadhika Malladi", Sanjeev Arora Princeton University
Amartya Sanyal University of Copenhagen amsa @dii. ku. dk
(stanley. wei, smalladi, arora)@princeton..dd
ABSTRACT
Machine unlearning algorithms are increasingly important as legal concerns arise around the provenance of training data, but verifying the success of unlcarning is often difficult. Provable guarantees for unlearning are often limited to supervised learning settings. In this paper, we provide the first theoretical guarantees for un- learning in the pre-training and fine-tuning paradigm by studying topic models, simple lag-of-words language models that can be adapted to solve downstream tasks like retrieval and classification. First, we design a provably effective unlearn- ing algorithm for topic models that incurs computational overhead independent of the size of the original dataset. Our analysis additionally quantifies the dele- tion capacity of the model i.e., the number of examples that can be unlearned without incurring significant cost in model performance. Finally, we formally given downstream task. par-
extend our analyses account for adaptation ticular, we design an efficient algorithm to perform unlearning after fine-tuning the topic model via a linear head. Notably, we show that it is easier to unlearn pre-training data from models that have been fine-tuned to a particular task, and one can unlearn this data without modifying the base model.
INTRODUCTION
Modern-day machine learning has shifted from single-stage supervised learning on manually structed datasets to a paradigm in which models are pre-trained and subsequently fine-tuned (Bom- masani al., 2022). In this setting, model initially learns good representation of the data using a self-supervised objective on a large unstructured corpus. The resulting pre-trained model is later adapted to solve specific tasks for which it is difficult costly curate large dataset. This blueprint has yielded strong performance in text (e.g., Devlin et al., 2019; Brown et al., 2020), vi- sion (e.g., Oquab et al., 2024; He al., 2022), and multimodal (e.g., Radford al., 2021: Zhai al., 2023) settings. It is well-know that the scale of the pre-training data is strongly correlated with the final performance of the model (Hoffmann al., 2022), leading the construction of larger datasets via broad internet scrapes (Gao et al., 2020; Schuhmann et al., 2022; Soldaini et al., 2024; Penedo al.. 2023). Such datasets have been found often inadvertently include private, sensitive, and unsafe data (Birhane et al., 2021; Longpre et al., 2024; He et al., 2024).
Unsafe data can generally degrade model performance and introduce biases, making the model less useful for various applications (McKenna et al., 2023; Birhane & Prabhu, 2021; Choenni et al., 2021; Naous et al., 2024). Using private and sensitive data, even unknowingly, poses legal risks (Bom- masani et al., 2022; Henderson et al., 2023). In particular, recent works have shown that models can memorize and thus permit the extraction of training data (Somepalli et al., 2023; Carlini et al., 2021; 2023). Moreover,
may be requested to remove data in accordance with GDPR's right to be forgotten (European Parliament & Council of the European Union), or as part of a copyright-related lawsuit (Tremblay OpenAl, Inc.,, 2023; DOE 1 GitHlu, Inc., N.D. Cal. 2022).
Therefore, there is great empirical interest in developing machine unlearning algorithms that can surgically remove portions of the training data from already learned model without harming per- formance. The gold standard for machine unlearning is for the model to behave as though it had
"Equal contribution.

---

Published as a conference paper at ICLR 2025
never been trained on that datapoint (Cao & Yang. 2015). As it is often undesirable to completely retrain models, especially as they grow larger, many works have proposed computationally cheaper heuristics for solving this problem (e.g., Jang al., 2023; Foster et al., 2024; Kurmanji et al.. 2023; Zhang et al., 2024b; Eldan & Russinovich, 2023; Gandikota et al., 2023). In the absence of theoret- ical guarantees, it is common recent works have shown that such evaluations often overestimate the success of these unlearning methods (Hayes et al., 2024; Shi et al., 2024; Maini et al., 2024) and thus it has proven difficult to confidently ascertain whether the proposed methods meet the necessary compliance standards. In this context, it is highly desirable to design efficient unlearning algorithms with mell-motivated guarantees that are salient to the pre-training and finetuning paradigm (Thudi et al., 2022; Lee et al., 2024).
empiries measure the success of these algorithms. However,
While there are some instances of such algorithms for linear models (Guo et al., 2020; Izzo et al., 2021; Mahadevan Mathioudakis, 2023), general convex models (Ullah et al., 2021; Sekhari al., 2021; Neel et al., 2021), Bayesian models (Nguyen et al., 2020), and GANs (Liu et al., 2024), there are no works on the paradigm of pre-training and fine-tun fineituning algorithms. One of the most classical such algorithms is topic modeling (Hofmann et al., 1999; Blei et al., 2003; Blei & Lafferty, 2006; Li & McCallum, 2006), which can also be thought of as the simplest language model. In this paper, we present the first provably effective and efficient unlearning algorithms for lopic models.
Topic models are generally pre-trained to extract latent structure (i.e., a small set of underlying top- ics) from large corpus of documents. This feature extractor is then used for variety of downstream applications, including retrieval, classification, and recommendation (Boyd-Graber et al., 2017). De- spite their simplicity, topic models can be used effectively solve many real-world natural language problems - see a survey in Churchill & Singh (2022).
1.1 OVERVIEW OF RESULTS
We focus on the setting in Arora al. (2012b), because admits an efficient learning algorithm with provable guarantees (Arora et al., 2012a). The corpus is assumed to contain r underlying topics, where each topic defines a distribution over words. Let D distribution over topic distributions. Then, each document d is generated by sampling a topic distribution Wa ~ 'D over topics, and then sampling words according to Wa.
The dataset of m documents is matrix M E Raxm where M permits non-negative matrix factorization M = A X. Here, A" E R is the distribution of words in each of the r unknown underlying topics, and X IRrxm is the sampled distribution of topics in each document. In particular, A X have columns on the probability simplex. seek to learn the embedding function A' and the topic-topic covariance R Ep ']
To derive provable guarantees on the success of unlearning, we adapt the notion of (c, -umllearnn introduced in Sekhari et al. (2021) to the topic modeling setting. The unleared model is required to behave indistinguishably from a model that was retrained on the modified dataset. We define a notion of millit-preseevvin capacity- i.e., the number of datapoints that can be unlearned without performance degradation (Definition 4). We now state our main result on utility-preserving unlearning in topic models.
unlearning that combines this condition with an analysis on the deletion
Main Result 1 (Informal version of Theorem 2). Suppose we trained a topic model A X on a training set S containing documents. Algorithm can perform pelestipresn unlearning of
m
my =
122 /rvrr
documents from the pre-trained topic model, where O(-) hides constants depending the learning and unlearning algorithm.
To adapt topic model to a downstream topic classification task, we learn head w E RR' on top of to minimize a strongly convex loss function (Definition 2). When and w are both released, one would necessarily have to first unlearn from A, which makes unlearning just as hard as it was in pre-training (Theorem 3). This setting is rather unrealistic, because there is no obvious case in which would want to model B = Aw as a whole i.c. it is not allowed to access outputs of A solely, and we show that is easier to perform utility-pree preserving unlearning of pre-training data in this case.
without A or vice versa. We thus advocate for viewing fine-tuned
2

---

Published as a conference paper at ICLR 2025
Main Result 2 (Informal version of Theorem 4). After adapting the model to downstream task (Definitions 1 and 2), Algorithm 2 can perform utllit-preserving unlearning of ń
doc- "Ver
uments, where q E [1/r, 1] is a task-dependent quantity, without modifying the base model A. Simpler downstream tasks have larger 9. increasing the separation from the pre-training result.
We demonstrate that our unlearning algorithms run substantially faster than retraining the model (Table 1). Overall, our results imply the following takeaways in the context of topic models (1) It is possible to effectively and efficiently unlearn datapoints from pre-trained model without retraining it (Algorithm 1 and Theorem 2), (2) One can effectively unlearn more pre-training data from model that has been adapted to downstream task without harming the utility of the base and fine-tuned models (Theorem 4), and (3) One can unlearn pre- pre-training data from a fine-tuned model without modifying the base model (Algorithm 2 and Theorem 4).
TOPIC MODELS
As we previously discussed, topic models can be considered one of the simplest language models that one can pre-train in a self-supervised fashion and later fine-tune for other language-related tasks. This pipeline mirrors the modern-day paradigm of pre-training large language models to build a general understanding of natural language and later fine-tuning them to solve a variety of tasks ranging from classification code generation.
2.1 PROBLEM DESCRIPTION
Topic modeling is a classical, bag-of-words method to discover structure in a corpus of docu- ments (Hofmann et al., 1999). One assumes that each document contains a convex combination of topics, each of which can be described in terms of distribution over the vocabulary. Different assumptions on the structure of this distribution and the topics have yielded a variety of topic mod- cling methodologics (Blei & Lafferty, 2006; Li & McCallum, 2006) perhaps most famous among these is the latent Dirichlet allocation (LDA, Blei et al. (2003)). Many early works established the statistical learnability of topic models under such assumptions, but the learning algorithms generally were not efficient in real-world settings (Arora et al., 2012b; Recht et al., 2012).
Our paper focuses on the setting in Arora et al. (2012b), for which Arora al. (2012a) provided an empirically efficient learning algorithm. The dataset consists of a set of m documents di,.., dm where each document contains L words from vocabulary V with |/ = n. The corpus contains different underlying topics, each of which defines a distribution over words. Each word in document is generated by: (1) sampling a distribution over topics Wa D, and then (2) sampling words independently according to Wa-
We represent the corpus as a matrix M E R where M permits non non-negative matrix factoriza- tion M = X. Here, A E R is the distribution of words in each of the r topics, X E Rm the distribution of topics document. While there are several algorithms for learning the feature extractor A", it is well-known that it is hard to recover X exactly (Arora et al., 2012b). Instead, it is desirable to learn how the topics co-occur together, denoted as R Ep x J. This quantity is termed the topic-topic covariance. Further discussion of this has been included in Appendix A.
each document, and hence M is the distribution of words in each
The topic modeling setting generally determines D (e.g., in LDA, D is Dirichlet distribution). In order to recover A" and R' efficiently and accurately from an observed corpus M ~ D, we need to make the following assumption the underlying data distribution.
Assumption (p-separability. Arora et al. (2012b)). The topic matrix A is p-separable for > 0 if for every lopic E [r]. there exists a word i E [m]] such that A 2 p and A = for all k' * k. Such words are called anchor words.
Without this separability assumption, maximum likelihood estimation of topic model is NP- hard (Arora et al., 2012b). Assumption requires that A contains diagonal matrix, up to row
Without loss of generality, assume T. = 2. The same asymptotic results hold for constant sized I., and it is straightforward to modify our analysis to account for this.
3

---

Published as a conference paper at ICLR 2025
permutations; intuitively. the appearance of an anchor word in a document perfectly indicates the document has nonzero probability of the corresponding topic. As we will detail in Section 4, this ob- servation inspires wo--hase learning algorithm, whereby one first approximates the anchor words for each topic and then leverages them to identify patterns among the topics.
2.2 DOWNSTREAM ADAPTATION
Topic models frequently trained on general corpus, and the embeddings can be later used to classify documents. The classification problem usually involves only a subset of topics. For example, after training a topic model on large corpus of news articles with diverse topics (e.g.. sports, politics, technology. finance. etc.), one relevant downstream task is to classify the subject of given news article as sports or politics. We formalize the topic classification task below.
Definition (Topic Classification Task). A topic classification task T = (Teir, w") is defined by a subset of topies Tetr C [r] on which the task is defined and a ground-truth labelling vector w* R" with bounded norm. Importantly, w* only has non-zero coordinates in the positions corresponding Tar-
The classification task is defined on the latent features of given document, so is necessary to first identify the salient topics as they occur in the text. Fitting topic model the corpus yields such feature extractor A that embeds a document into the r-dimensional topic space. In order to adapt topic model to particular classification task, we perform head tuning on the feature extractor A.
Definition (7-Head Tuning). For given labelled document classification dataset Der = {(d,, y:) representing a topic classification task T, embed each document d; vector æ; E R containing the word counts in the document. To perform head tuning on pre-trained topic model A, we learn w, R' that is 7-optimal point of
(wu; ww A)
Σ
f(x Aw, ()
Den
(ar,))EDar where l strongly convex in w. In other words, w, satisfies ( A) - min (ww A) S w
One example of is the logistic loss with l regularization. For case of exposition, primarily consider binary classification tasks, but we point out that the definition can extend to multi-class tasks solved via the one-vs-all scheme (Rifkin & Klautau, 2004).
We note that head tuning, also referred to as linear probing, is a simpler adaptation technique than fine-tuning A alongside Nonetheless, recent works on popular language models have demon- strated that head tuning can substantially improve the ability of general pre-trained language models solve complex classification tasks (Malladi al., 2023a;b). Head tuning thus serves a con- venient yet effective adaptation method that avoids updating the pre-trained model, which is often desirable. For example, if single pre-trained model needs be separately adapted solve many different tasks, then it is desirable to minimize the number of parameters that are fine-tuned to min- imize the memory needed to store all of the adapted models.?
UNLEARNING
As mentioned previously, there is increased interest in machine unlearning due to the growing scale of modern datasets and the difficulty of manually inspecting each datapoint. Theoretically, the gold standard for unlearning is that the model should behave identically to one that was trained without the datapoint in its corpus (Cao & Yang, 2015). We first define what means for two models 01, Og E θ to behave almost identically, where & denotes the parameter space of hypothesis class. Due to randomness in learning, 0, and 02 are random variables.
Definition ((e, 6) -indistinguishable models, Dwork et al. (2014)). Two models denoted by random variables 01, 02 E θ are (c. 8) ( -indistinguuihablee if for all possible subsets of models T S O Pr (0, T) < e Pr (02 E T) and Pr *02 T) s et Pr (01 E T) +
This motivation has driven widespread development and adoption of parameter-efficiet fine-tuning meth- ods for large language models. Liu et al. (2021) contains survey of such techniques.
4

---

Published as a conference paper at ICLR 2025
We adapt the definitions from Sekhari et al. (2021) the topic modeling setting. A learning al- gorithm A takes in a set of m documents, denoted as S, and returns a topic model 0 = (A, R). Analogously, an unlearning algorithm U takes in the learned topic model 8, set of documents to unlearn Sy E S, some statistics on the training set (SS), and outputs model. The set of datapoints to unlearn Sy is often referred to the forget set. With this in mind, now define notion of Kullity-preeervnng unlearning, whereby the unlearning algorithm needs to not only effectively simu- late retraining the model from scratch but also maintain the model's performance.
Definition
(e, 3)-Unleerning with Deletion Capacity). Let m E N be a constant that depends on the topic modeling distribution D satisfying Assumption 1. For any training dataset
S ~ 'D of size at least m, and é, 5 > O, we say that pair of learning and unlearning algorithms (A,2) performs utility-preservie unlearning with deletion capacity T (m) if
1. With probability at least 0.9 over draws from D, for any forget set Sy S S of size at most T (m), model trained on S \ 'Sy is indistinguishable from that resulting from unlearning with U. Here, & denotes (e, 6) iiniinniiitiigguhabbllltyy..
c.6
A(S))A(S) <.8 ((S), Sy))
2. Even for adversarially chosen Sy, the unlearned model does not suffer large perfor- mance degradation. Formally.
EAU
max
M(U(S),A(S)))T(S)) - hh* S 0.01
SSy [Sylst (m)
where h : E is the loss of the topic model, and ht* min h(w) is the irreducible loss.
The above definition can be applied to both the pre-training and the downstream adaptation stages of training topic model. Of partieular note is that (1) does guarantee (2), since the former only concerns indistinguishabiiiy between the unlearned and retrained models, while the latter is a statement about utility preservation. Moreover, unless T(S) contains the entire dataset, we note that the unlearning algorithm U cannot be as simple as retraining the model. In this paper, we will design an unlearning algorithm for topic models that satisfies this definition of provable unlearning, and the number of statistics T(S) will not depend on the initial dataset size m.
To show (e, 8) -iinistinguishabblity. we utilize the Gaussian mechanism, a classic tool from differen- tial privacy. Given a particular function, the Gaussian mechanism essentially prescribes how much noise one must add to the output order for the input to be indistinguishable from a similar one. The guarantee of the Gaussian mechanism is described in the following lemma.
Lemma 1 (Gaussian Mechanism, Dwork et al. (2014)). Let f be an arbitrary d-dimensional func- tion, and define its ez-sensitivity to be 2 := max adjacent 2,
[If(xx) f1()) Then, for e² > 2 2lo
1.25 8"
the Gaussian mechanism with parameter a 2 cD2f/e / is (e, dddffferennil private.
In our case, we define adjacent inputs (i.c., training datasets) as the case where y is superset of r.
4 LEARNING AND UNLEARNING TOPIC MODELS
In this section, we present the learning and unlearning algorithms and guarantees for topic models.
Notation. We use A' to refer to the ground-truth topic model, A to refer to a topic model trained on S, and A to denote a topic model retrained with the forget set removed S \ Sy.. We also use A to denote the unlearned topic model before applying the Gaussian mechanism and to denote the model after the mechanism is applied. Analogous notations are used for R.
4.1 LEARNING ALGORITHM AND GUARANTEES
Per Arora et al. (2012a), the learning algorithm Arase takes in a corpus of documents = (di:-.., dm. } and consists of the following three phases to learn a topic model 0 (A R$).
5

---

Published as a conference paper at ICLR 2025
1. Measure the word co-oceurrences. Compute the word co-occurrence matrix Q R where Qıj is the number of times word i appears in the same document as word j. We also compute Q, which normalizes the rows of Q to sum to 1. detailed discussion of the con- struction of Q and its relationship to the factorization M = X is included in Appendix A. Identify the anchor words P. Recall that in order to be able to learn topic models efficiently, there must exist a set of anchor words P with P| r, and each anchor word must appear exclusively in a single topic (Assumption 1). This subroutine uses Q to approximately identify the r anchor words P.
3. Learn the feature extractor A and the topic-topic covariance R The algorithm uses the anchor words P and the word co-occurrences Q learn A and R Each word is expressed as a convex combination of anchor words, and thus, topics. With appropriate normalization and by cross-referencing information with the co-occurrence matrix, one can recover A', R* in the infinite data limit.
We sketch how this algorithm recovers the ground truth A" R' when one has infinitely many doc- uments in Appendix A. Arora et al. (2012a) gives the following finite-document guarantee. Theorem (Learning Guarantec). Running Abase Log log )
dataset S of size m, where is at least م
max {o) ar log L(Tp))co ).0
log r
Le
recovers A and R with entrywise additive error up to eo from the ground truth A", R", respec- tively. Here, a is the topic imbalance parameter, and 7 is the condition number of the ground truth R'. Formally, we have
maxi.je(r) Prp(z / Pro|z = 5).
Approximating the anchor words. We defer precise description of the anchor word identification algorithm to Appendix A and instead focus here on the intuitions driving its design and the guar- antees we will use throughout the paper. First, we note the relationship between Q and the set of anchor words. If we had infinitely many documents, then the convex hull of the rows in Q will be simplex with vertices corresponding to the anchor words, because each anchor word corresponds to topic, and each topic prescribes distribution over words. However, in the finite document setting, each row of Q only approximates their expected value, and so one must approximate the vertices of convex hull when given access a perturbation of the points that define it.
We start by requiring that each topic is distinctly different from any mixture on the other topics. Formally, this requires that the simplex is robust, in that each vertex (i.e., anchor word) is sufficiently far from any combination of the other topics. Most topic modeling settings define lower bounds on the robustness of the simplex. By a result in Arora al. (2012b), the simplex defined by the anchor word rows of the population Q is "yp-robust. We can now define exactly the sense in which Q computed on finite dataset approximates the population co-occurrence matrix.
Definition 5. Let {a, yim be a set of points whose convex hull P is a simplex with vertices {uz We say a set of r points is e-close the vertex set [w:]_= if each of the points is e-close in &2 distance to a different vertex in P. Moreover, we say that a simplex P is 3-robust if for every vertex of P. the & distance between and the convex hull of the rest of the vertices as least B.
In the context of this definition, P corresponds to the ground truth convex hull, and the finite sample Q can be seen a perturbation it. In particular, Arora et al. (2012a) used this to established guarantee on the accuracy of anchor word recovery.
Lemma 2 (Approximation Guarantee on Anchor Words). Suppose each row of Q is at most 8 distance away from the ground truth "pp-robust simplex Q' in &a norm. If 20r00 (1:p) < yp. then the set of anchor words found by the algorithm is O ((5/rp)-close to the ground truth anchor words.
We now describe how to use the recovered approximate anchor words learn the topic model.
Learning the topic model from anchor words. We are given the set of anchor words P, the word co-occurrence matrix Q E Rax" and the normalized co-occurrence matrix Q. Our goal is to use these quantities to learn A E Ra*r and R E R'xr We will do so by first expressing each word i E [n] as a convex combination of the anchor words (and thus, the topies). In particular, for each word i, we learn the coefficients C, E A, as
C = arg min Q; - vT TTQr11 vEA,

---

Published as a conference paper at ICLR 2025
Algorithm 1 Unlearning algorithm (Mhase)
Input: Forget set Sy S S, statistics T(S) which include { JE Q P. normalization con-
stants pd
Output: Unlearned model A, R
Compute the updated co-occurrence matrix Qº by subtracting documents in Sy
Store the updated normalization constants Q=
for i in ,,..., do
Newton step update C,'s:
C + C. V
C + proja.
where L Sy) = 1| v p and Ho: V , ())
end for
A' diag(p")C
Á column normalized A'
R = A'Q"A A where A the pseudoinverse Á
Sample MA, vn from normal distribution defined by Gaussian mechanism guarantee
A Project each column of Á VA to A..
R Project R + VR onto the set of PSD matrices.
return The unlearned topic model Á, R
where Qr is the rows of Q corresponding to the anchor words. Arora et (2012a) showed the following approximation guarantee for C₁ compared to the ground-truth coefficients. Lemma 3. When 20r6/(xp)) < for every word C, has entrywise error ((6/(1p)2) from C,
We then normalize this C₁ by the total number of co-occurrences that word i is involved in. Note that the C₁ can be assembled into matrix C E R=xr, We set A to be C after normalizing the columns sum to 1, since the columns represent the topic-conditioned distribution over the vocabulary. We finally compute R A'QA' where At denotes the pseudoinverse of A.
4.2 UNLEARNING ALGORITIM AND GUARANTEES
Learning Phase
Retrain Time
Unlearning Update
Unlearning Time
Co-occurrence matrix computation
(m)
Updating frequencies
O
Identify anchor words Recover topics from anchors
On + /
Use learned anchor words
0(1)
On ny
Projected Newton step
O(ny")
Head tuning w (Definition 2)
ERM
Newton step
O
Table I:
Our unlearning algorithms generally have runtime shorter than the retraining procedure. ERM denotes empirical risk minimization, and we note the training time relies on the error tolerance.
We describe our unlearning algorithm Uusse to forget set Sy from a trained model (Algorithm 1), which crucially updates C, with a Newton step. We then compute A from the modified C, and apply the Gaussian mechanism to ensure indistinguishabiiity. We describe formal guarantee the unlearning algorithm below, sketching out our utility preserving guarantees with respect to A The arguments for R* follow analogously;
defer the discussion to the appendix.
Theorem 2 (Utility-Preserviyy
Unlearning on the Base Model), Let Abase be the learning algo- rithm described in the prior sections and Ubose be the unlearning algorithm in Algorithm Then, (Abase, Ubase performs utility-preserving unlearning with deletion capacity
A Jewar (m) 2 Vrn

---

Published as a conference paper at ICLR 2025
where is the number of training documents, is the number of topics, and is constant de- pendent on 6, and DD The loss function used in the utility-preeerving definition is the maximum entrywise enror from from the ground truth topic model A*.
Proof sketch. The full proof can be found in Appendix B.2. We delete my S 0.001meo(1p) points. This upper bound ensures that the anchor words are likely unchanged per Lemma 2. Recall that uillty-preeerving unlearning requires: (1) that the unlearned model is indistinguishable from the retrained model, and (2) that the unlearned model is not too far from the ground-truth model.
Indistinguishabiiityy
The Gaussian mechanism introduced in Lemma allows us to make two models with a given fz-sensitivity (e. -iindistinguishbbll from each other. We bound the Ez-sensitivity of the feature extractor A by noting that A is rescaled version of C.
Lemma 4. For e, O, the following holds for the C and the topic matrix A: armu
- - Sc mE
| - A 1l S (ar) ||Č -C
Applying the Gaussian mechanism with noise o A and followed by projecting the columns of A VA back An yields the desired result.
where A cv/rr (ar)? mPc77
Utility Preservation. We first apply Lemma to show that, with high probability, the anchor words do not change when unlearning my documents. Then, between the unlearned C, and the ground truth C, Accounting for the noise added via the Gaussian mechanism completes the proof.
Lemma 8 to bound the distance
Lemma 5. For fore,6 6 > O, denote the unlearned model after the Gaussian mechanism described above as A. Then, A satisfies:
(ar)2mu
(Var- [Vnr.vlo(mm) Vlo((nr).
v /lg(115) +1)
E
A
10
c.
mCnpP
Each of the two terms in the above equation yield constraint on my. In particular, my min| r2 vaar O (m)) so setting my Ô yd vnr) completes the proof.
UNLEARNING WITH RESPECT TO A DOWNSTREAM TASK
We are interested in unlearning set of pre-training documents S, S S. A topic classification task is usually defined on a subset of the topics in the dataset for example, if the pre-training corpus contained diverse news articles, one plausible downstream task is classify the content of given document containing politics
sports. Definition 1 formalizes this: topic classification task = =(Totf, w²) is defined on a subset of the topics Telf and a r-length ground-truth labelling vector w" E Wheadd where w" only has non-zero values in positions corresponding to Tar- We describe two possible settings under which we can show quility-preseree
unlearning. For the sake of exposition, 0 in downstream head tuning: the extension to inexact head tuning (T > 0), which a more realistic regime, will be deferred to the appendix.
will assume for
5.1 NAIVE SETTING
In the first setting, the learning algorithm Asead, naive returns the pre-trained feature extractor and the head w separately. So, we must ensure that the forget set Sy C S cannot be recovered from either A or w. As such, we must necessarily perform unlearning on as described in Algorithm which means that unlearning the fine-tuned model is exactly difficult as unlearning the base model.
Theorem 3 (Unlearning when releasing A and w). For a downstream task T with loss func- tion êT, consider the unlearning algorithm Uhead, naive that first runs Algorithm 1 to compute À Unase (S Apase (S), T(S)), where (Apase performs atility-reesevingg unlearning (Theo- rem 2). Then, fits a head w arg min (ww A) and returns Á and w. We assert that (Ancad, naives Unead, naive) performs ufiliy-preserving unlearning (Definition 4).
8

---

Published as a conference paper at ICLR 2025
Algorithm 2 Unlearning algorithm for task T (Uhead)
Input: Document deletion requests Sy S S, statistics (()) which include A A JE Q P. diag(p" (pgg ), w = arg minl we {wo; AS)
A, R Run Algorithm (Ubase) ) up to the Gaussian mechanism @ S H
w W A) where H fr A) return (A Aud + &, in accordance with the Gaussian mechanism
Given the guarantee on A from Theorem 2, we show that this result extends to w by the well- known fact: for 6 > O, post-processing indistinguishable quantities (Definition 3) preserves (e, D-indisstinuuisaabiityy (Dwork et al., 2014). The full proof of utility preservation can be found in Appendix C. which essentially boils down Lipschitz condition. However, there are some downsides to this algorithm. First, it requires retraining the head for each unlearning request, but we want to perform unlearning without access to Der. Second, repeatedly noising the base model via the Gaussian mechanism will erode its utility. We address these issues in the realistic setting.
5.2 REALISTIC SETTING
There is little reason to release A and w separately after fine-tuning the model, because it is unclear why one would want to A without vice versa. One obtain A directly after pre-training instead of relying on a fine-tuned model, and there is little use for w alone, because it is highly sensitive to the specific topies extracted by A and their ordering. As such, we argue for releasing the fine-tuned model as a single matrix² B Aw, where B E 1x
Theorem 4 Presery-nrsserving Unlearning on the Downstream Task), Suppose that the downstream
task T only depends on a subset of topics Tel S [r]: that is, w* arg min min LT(v, (v; A*) has non-zero entries only in the index set Tel. Denote q = minkeT.y Pro k), and let Aread be the head nuning algorithu (Definition 2) and Unead be Algorithm 2. Then, (Aneas Unead) performs utility- priterrireeeiingg unlearning with deletion capacity
T Mares (m) 2 c mg
rvnr
where d' is a constant dependent on e, 8, D, and
The full proof is in Appendix C, including the worst case of Telf = [r]. When the task relies heavily on every single topic (i.e., q = 1/ar), the above guarantee is equivalent to the one in the pre-training phase. However, in most realistic settings, the downstream task will only depend on subset of the latent topics in the corpus. In this case, q > 1/ar, and we can unlearn more points without degrading the utility of the model. Intuitively this makes sense too; the more reliance T has on a rare topic, the less adversarial deletion it can tolerate.
Proof sketch. We again assume that we are deleting my S 0.001mea(1p)* points. For any mod- a²
ification made to A, there is an equivalent modification that can be made to w instead such that B Aw is preserved, so we do not need to update A. We look for A = A "" where w is the head leameed on A=. It can be shown that A has a unique pseudoinverse since is full rank; naturally, we set Ast AstAt FF thereby ensuring privacy even if one recovers a part of A from B = Aw. We furthermore define ö that is fit to the unlearned model before the Gaussian mechanism, the indistinguishability and utility preservation conditions in Definition 4.
Whead such that
A Aw. We now need show v and satisfy both
Indistinguissaabiiityy Let xn arg min (o; A) denote the result of head tuning A, and let tō be the result of taking Newton step (see Algorithm 2). Then by triangle inequality.
A A Fww' " F < A
Aw + Aw A AFw u 1|2 + ||A F F
AF
One can generalize this the case where the downstream task is C-way classification, in which case B E R R

---

Published as a conference paper at ICLR 2025
Informally, the first term is controlled by the error in the Newton step approximation, and the third term is bounded by the error to the retrained w The remaining term can be rewritten as [I A 220" w²) + (A - A ( """"l,, where the first term be bounded using the same technique use to prove Lemmas 4 and 5. The second term can be bounded by noting that ws is sparse, which yields the below lemma that plays crucial role in establishing the improved deletion capacity.
Lemma 6 (Modification of Lemma 4 for downstream task). For e, 5 > O,
| A 4
1 --C---= 1lc S 9
armu
c. mEDpP
As in the pre-training case, the proof. In the worst case, when the downstream task depends on every topic, then = 1/ar, and recover Lemma 4; however, this is unlikely to happen in practice.
now set the noise scale in the Gaussian mechanism and complete
Utility Preservation. We compare the value of u after the Gaussian mechanism ö = 0 + V/e to what it would be for the ground-truth model va = (A²)t A"w". We again rely the sparsity of wt and bound El]l - vz v*loo]] in Lemma 31.
RELATED WORKS
Provable unlearning. One ideally wants the unlearned model to behave identically to one that was retrained from scratch with the forget set removed from the training data (Cao & Yang, 2015; Bourtoule et al., 2021; Gupta et al., 2021). This is difficult to achieve in many settings, so there are several notions of approximate unlearning (Ginart et al., 2019; Guo et al., 2020; Neel et al., 2021) reminiscent of differential privacy (Dwork et al., 2014). Most relevant to our work is the notion of (c, -0nlearmnn introduced in Sekhari et al. (2021). which we adapt to construct Definition 4. Our work focuses on deriving unlearning guarantees in the pre-training and fine-tuning pipeline. Golatkar et al. (2020) is closest our work. They show considerably weaker guarantees learning information with respect to probes to the weights. In contrast, our work is focused on realistic topic classification tasks and demonstrates strong guarantees (Definition 4). Recent works have extended notions of certified unlearning to nonconvex settings. Zhang et al. (2024a); Mu & Klabjan (2024): Chien et al. (2024) provide unlcarning algorithms without deletion capacity guar- antees. Qiao et al. (2024) also proposes an unlearning method for non-convex settings but analyzes its deletion capacity in a convex setting. Our work extends beyond the convex setting to provide provable unlearning methods and corresponding deletion capacity analysis for non-convex models.
Theoretical analysis of pre-training and fine-tuning. Our downstream task definition (Sec- tion 2.2) is inspired by works on transfer learning in language models (Saunshi et al., 2021; Wei al., 2021; Wu et al., 2023; Kumar al., 2022), contrastive learning (Lee et al., 2021; HaoChen & Ma, 2023), and meta-learning (Chua et al., 2021; Collins al., 2022;
Yüksel et al., 2024).
7 CONCLUSION
This work uses topic models to develop the first provable guarantees on unlearning in the modern- day pre-training and fine-tuning paradigm. We propose two unlearning algorithms that can effec- tively and efficiently unlearn from both the pre-trained model (Algorithm and Theorem 2) and the fine-tuned model (Algorithm 2 and Theorem 4). Notably, we find that it is easier, in terms of the deletion capacity (Definition 4), to unlearn pre-training data from the fine-tuned model, and we can do so without modifying the pre-trained base model. Our findings suggest that task specific un- learning is easier than full model unlearning, providing a promising path forward to design efficient algorithms for large-scate models.
The most notable limitation of our work is that our usage of topic models, which permit tractable analysis but cannot capture interesting features modern-day language models (e.g., their autore- gressive nature). Moreover, with the growing popularity of foundation models, there is scholarly discussion around meaningful definitions of unlearning and how they can be measured (Thudi et al., 2022: Lee et al.. 2024). Our work focuses traditional notions of unleamiig centered on differen- tial privacy (see Definition 4), but we hope to extend these definitions to capture additional features of generative models that are salient to their real-world uses.
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Sanjeev Arora, Rong Ge, Yoni Halpern, David Mimno, Ankur Moitra, David Sontag, Yichen Wu, and Michael Zhu. A practical algorithm for topic modeling with provable guarantees, 2012a. URL https::////..ccc.t // / arxiv.org. abs/ 1212.42177 4777.
Sanjeev Arora, Rong Ge, and Ankur Moitra. Learning topic models going beyond svd, 2012b.
Abeba Birhane and Vinay Uday Prabhu. Large image datasets: A pyrrhic win for computer vision? In 2021 IEEE Winter Conference on Applications of Computer Vision (WACV), pp. 1536-1546. IEEE, 2021.
Abeba Birhane, Vinay Uday Prabhu, and Emmanuel Kahembwe. Multimodal datasets: misogyny, pornography, and malignant stereotypes. arXiv preprint arXiv:2110.0196. 2021.
David M. Blei and John D. Lafferty. Dynamic topic models. In Proceedings of the 23rd International Conference on Machine Learning, ICML '06. pp. 113-120, New York, NY, USA, 2006. Asso- ciation for Computing Machinery. ISBN 1595933832. doi:
1143859. URL
https: //op: org/ 10. . 1145/115/000 4444141114444444 1144144444411 1tt.//1144444.118855.. 1143859.
David M Blei, Andrew Y Ng. and Michael Jordan. Latent dirichlet allocation. Journal of machine Learning research, 99an):99331022 2003.
Rishi Bommasani, Drew A. Hudson, Ehsan Adeli, Russ Altman, Simran Arora, Sydney von Arx, Michael S. Bernstein, Jeannette Bohg, Antoine Bosselut, Emma Brunskill, Erik Brynjolf- sson, Shyamal Buch, Dallas Card, Rodrigo Castellon, Niladri Chatterji, Annie Chen, Kathleen Creel, Jared Quiney Davis, Dora Demszky, Chris Donahue, Moussa Doumbouya, Esin Dur- mus, Stefano Ermon, John Etchemendy, Kawin Ethayarajh, Li Fei-Fei, Chelsea Finn, Trevor Gale, Lauren Gillespie, Karan Goel, Noah Goodman, Shelby Grossman, Neel Guha, Tatsunori Hashimoto, Peter Henderson, John Hewitt, Daniel E. Ho, Jenny Hong, Kyle Hsu, Jing Huang, Thomas Icard, Saahil Jain, Dan Jurafsky, Pratyusha Kalluri, Siddharth Karamcheti, Geoff Keel- ing. Fereshte Khani, Omar Khattab, Pang Wei Koh, Mark Krass, Ranjay Krishna, Rohith Ku- ditipudi, Ananya Kumar, Faisal Ladhak, Mina Lee, Tony Lee, Jure Leskovec, Isabelle Levent, Xiang Lisa Li, Xuechen Li, Tengyu Ma, Ali Malik, Christopher D. Manning, Suvir Mirchandani, Eric Mitchell, Zanele Munyikwa, Suraj Nair, Avanika Narayan, Deepak Narayanan, Ben New- man, Allen Nie, Juan Carlos Niebles, Hamed Nilforoshan, Julian Nyarko. Giray Ogut, Laurel Orr, Isabel Papadimitriou, Joon Sung Park, Chris Piech, Eva Portelance, Christopher Potts, Aditi Raghunathan, Rob Reich, Hongyu Ren, Frieda Rong, Yusuf Roohani, Camilo Ruiz, Jack Ryan, Christopher Ré, Dorsa Sadigh, Shiori Sagawa, Keshav Santhanam, Andy Shih, Krishnan Srini- vasan, Alex Tamkin, Rohan Taori, Armin W. Thomas, Florian Tramèr, Rose E. Wang, William Wang, Bohan Wu, Jiajun Wu, Yuhuai Wu, Sang Michael Xie, Michihiro Yasunaga, Jiaxuan You, Matei Zaharia, Michael Zhang, Tianyi Zhang, Xikun Zhang, Yuhui Zhang, Lucia Zheng, Kait- lyn Zhou, and Percy Liang. On the opportunities and risks of foundation models, 2022. URL https: /ttp://aavvv../// org/ wttrg/ab///// at///b////// /2108.21.. 07258.
Lucas Bourtoule, Varun Chandrasekaran, Christopher A Choquette-Choo Hengrui Jia, Adelin Travers, Baiwu Zhang, David Lie, and Nicolas Papernot. Machine unlearning. In 2021 IEEE Symposium on Security and Privacy (SP), pp. 141-159. IEEE, 2021.
Jordan Boyd-Graber, Yuening Hu, David Mimno, et al. Applications of topic models. Foundations and Trends0 in Information Retrieval, 11(2-3):143-996 2017.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhari- wal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agar- wal, Ariel Herbert- Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neu- ral Information Processing Systems, volume 33, pp. 1877-1901. Curran Associates, Inc., 2020. URL https: http:///oocceeeeeeeeeeee//cc wwwsiinnnnseuuiissseeeeeeerseiss neurips. cc waweerrfffeeeeppeeeeeeeeee file/1 457 96741 9111444977778181711881 42aaaaa-aepepaaa-aappaeee .ddf.

---

Published as a conference paper at ICLR 2025
Yinzhi Cao and Junfeng Yang. Towards making systems forget with machine unlearning. In 2015 IEEE symposium on security and privacy, pp. 463-480 IEEE, 2015.
Nicholas Carlini, Florian Tramer, Eric Wallace, Matthew Jagielski, Ariel Herbert- Katherine Lee. Adam Roberts, Tom Brown, Dawn Song, Ulfar Erlingsson, et al. Extracting training data from large language models. In 30th USENIX Security Symposium (USENIX Security 21), pp- 2633-2650, 2021.
Nicolas Carlini, Jamie Hayes, Milad Nasr, Matthew Jagiclski, Vikash Sehwag, Florian Tramer, Borja Balle, Daphne Ippolito, and Eric Wallace. Extracting training data from diffusion models. In 32nd USENIX Security Symposium (USENIX Security 23), pp. 5253-5270, 2023.
Eli Chien, Haoyu Wang, Ziang Chen, and Pan Li. Langevin unlearning: A new perspective of noisy gradient descent for machine unlearning, 2024. URL pettts://arxiin wttpp/.www...../////0/00000 10371.
Rochelle Choenni, Ekaterina Shutova, and Robert van Rooij. Stepmothers are mean and aca- demics are pretentious: What do pretrained language models learn about you? In Marie- Francine Moens, Xuanjing Huang, Lucia Specia, and Scott Wen-tau Yih (eds.), Proceedings of the 202/ Conference on Empirical Methods in Natural Language Processing, pp. 1477-1491, Online and Punta Cana, Dominican Republic, November 2021. Association for Computational Linguis- tics. doi: 10.1 16663v11/2221 2t133//1//22...mppmmaiiia .ewnlp-main.1111 URL httpstttpss... / / ant loy. org/ 2021. emn.pp maii.. 111.
Kurtland Chua, Qi Lei, and Jason D) Lee. How fine-tuning allows for effective meta-learning. Ad- vances Neural Information Processing Systems, 34:8871-8884, 2021.
Rob Churchill and Lisa Singh. The evolution of topic modeling. ACM Comput. Surv., 2022.
Liam Collins, Aryan Mokhtari, Sewoong Oh, and Sanjay Shakkottai. Maml and anil provably learn representations. In International Conference on Machine Learning, pp. 4238 4310. PMLR, 2022.
Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of deep bidirectional transformers for language understanding. In Jill Burstein, Christy Doran, and Thamar Solorio (eds.), Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. Volume I (Long and Short Papers), pp. 4171-4188 Minneapolis, Minnesota, June 2019. Association for Com- putational Linguistics. doi: 00.18633/v1/11-111 1423. URL /otttss:/aatt aacl htt////ccaattootto www.ollyyoor.................... N1 9-13..
Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Foundations and Trends Theoretical Computer Science, 9(3-4):211 1::21-440 407, 2014.
Ronen Eldan and Mark Russinovich. Who's harry potter? approximate unlearning in 1lms, 2023. URL /tttps://axxiv.....mm /ttppp/////.....rraaa///1.1....0 02238.
DOE I GitHub, Inc. 4:22-cv-06823, N.D. Cal. 2022.
Tremblay v. OpenAl, Inc.. 23-cv-03416-AMB (N.D. Cal.), 2023.
European Parliament and Council of the European Union. Regulation (EU) 2016/679 of the Euro- pean Parliament and of the Council. URL https:://///s. 679/oj.
pettts::/dattee //te:://daaaaeee eutopa. wwt.:pppa/.eeeeee//////eeeeee///
Jack Foster, Stefan Schoepf, and Alexandra Brintrup. Fast machine unlearning without retraining through selective synaptic dampening. In Proceedings of the AAAI Conference on Artificial Intel- ligence, volume 38, pp. 12043-12051, 2024.
Rohit Gandikota, Joanna Materzynska, Jaden Fiotto- Kaufman, and David Bau. Erasing concepts from diffusion models. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 14226-2436 2023.
12

---

Published as a conference paper at ICLR 2025
Leo Gao, Stella Biderman, Sid Black, Laurence Golding, Travis Hoppe, Charles Foster, Jason Phang. Horace He, Anish Thite, Noa Nabeshima, Shawn Presser, and Connor Leahy. The pile: An 800gb dataset of diverse text for language modeling, 2020. URL https: wttp/aaxiivv..///..///. abs/ 2201 00027.
Antonio Ginart, Melody Guan, Gregory Valiant, and James Y Zou. Making forget you: Data dele- tion in machine learning. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché-Buc, E. Fox, and R. Garnett (eds.). Advances in Neural Information Processing Systems, volume 32. Cur- ran Associates, Inc., 2019. URL htttps://prooceedngggg neurips ccc/paper_files//
Aditya Golatkar, Alessandro Achille, and Stefano Soatto. Eternal sunshine of the spotless net: Selective forgetting in deep networks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pullern Recognition, pp. 9304-9312, 2020.
Chuan Guo, Tom Goldstein, Awni Hannun, and Laurens Van Der Maaten. Certified data removal from machine learning models. In International Conference on Machine Learning, pp. 3832- 3842. PMLR, 2020.
Varun Gupta, Christopher Jung, Seth Neel, Aaron Roth, Saeed Sharíf-Maalvjerdii, and Chris Waites. Adaptive machine unlearning. Advances in Neural Information Processing Systems, 34:16319- 16330, 2021.
Jeff Z. HaoChen and Tengyu Ma. A theoretical study of inductive biases in contrastive learning- In The Eleventh International Conference on Learming Representations, 2023, URL https: //openzeview..o. wtg..e/eee.ooomiaoaaaaaaa...ee.
Jamie Hayes, Ilia Shumailov, Eleni Triantafillou, Amr Khalifa, and Nicolas Papernot. Inex- act unlearning needs more careful evaluations to avoid a false sense of privacy, 2024. URL
attps::/Ae /ttta:///axvv.../ aaaaaaxivvv.aaa wrg. /20// 2101..1218..
Kaiming He, Xinlei Chen, Saining Xie, Yanghao Li, Piotr Dollár, and Ross Girshick. Masked au- toencoders scalable vision learners. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 16000-16009, 2022.
Luxi He, Yangsibo Huang, Weijia Shi, Tinghao Xie, Haotian Liu, Yue Wang, Luke Zettlemoyer, Chiyuan Zhang, Danqi Chen, and Peter Henderson. Fantastic copyrighted beasts and how (not) to generate them. arXiv preprint arXiv:2406. 14526, 2024.
Peter Henderson, Xuechen Li, Dan Jurafsky, Tatsunori Hashimoto, Mark A Lemley, and Percy Liang. Foundation models and fair use. Journal of Machine Learning Research, 24(400):1-79, 2023.
Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendricks, Johannes Welbl, Aidan Clark, al. Train- ing compute-optimal large language models. arXiv preprint arXiv:2203. 15556, 2022.
Thomas Hofmann et al. Probabilistic latent semantic analysis. In UAI, volume 99, pp. 289-296, 1999.
Zachary Izzo, Mary Anne Smart, Kamalika Chaudhuri, and James Zou. Approximate data deletion from machine learning models, 2021.
Joel Jang, Dongkeun Yoon, Sohee Yang, Sungmin Cha, Moontae Lee, Lajanugen Logeswaran, and Minjoon Seo. Knowledge unlearning for mitigating privacy risks language models, 2023. URL https: /ttp:////peeeeieieee net wwt.:/ntmtetttiiieeeeemee www.rmidd-zzuillaoa
Ananya Kumar, Aditi Raghumathan, Robbie Matthew Jones, Tengyu Ma, and Percy Liang. Fine- tuning can distort pretrained features and underperform out-of-distribution In International Con- ference on Learning Representations, 2022. URL https: opwprevieeeeeeeeeeeeeeeeev net forum?
13

---

Published as a conference paper at ICLR 2025
Meghdad Kurmanji, Peter Triantafillou, Jamie Hayes, and Eleni Triantafillou. Towards unbounded machine unlearning. In seirtt- Conference on Neural Information Processing Systems, 2023. URL
Jason D Lee, Qi Lei, Nikunj Saunshi, and Jiacheng Zhuo Predicting what you already know helps: Provable self-supervised learning. Advances in Neural Information Processing Systems, 34:309- 323, 2021.
Katherine Lee, A. Cooper, Christopher Choquette-Choo, Ken Liu, Matthew Jagielski, Niloofar Mireshghallah, Lama Ahmed, James Grimmelmann, David Bau, Christopher De Sa, Fernando Delgado, Vitaly Shmatikov, Katja Filippova, Seth Neel, Miranda Bogen, Amy Cyphert, Mark Lemley, and Nicolas Papernot. Extended abstract: Machine unlearning doesn't it do what you think, 04 2024.
Wei Li and Andrew McCallum. Pachinko allocation: Dag-structured mixture models of topic corre- lations. In Proceedings of the 23rd international conference on Machine learning, pp. 577-584, 2006.
Jiaqi Liu, Jian Lou, Zhan Qin, and Kui Ren. Certified minimax unlearning with generalization rates and deletion capacity. Advances in Neural Information Processing Systems, 36, 2024.
Pengfei Liu, Weizhe Yuan, Jinlan Fu, Zhengbao Jiang, Hiroaki Hayashi, and Graham Neubig. Pre- train, prompt, and predict: A systematic survey of prompting methods in natural language pro- cessing, 2021. URL https: /axxpps://xxxi.... aww.v. org/ abs//aa///// / 2107.11.. 11586.
Shayne Longpre, Robert Mahari, Anthony Chen, Naana Obeng-Marnu, Damien Sileo, William Brannon, Niklas Muennighoff, Nathan Khazam, Jad Kabbara, Kartik Perisetla, et al. A large- scale audit of dataset licensing and attribution in ai. Nature Machine Intelligence, 6(8):975-98)) -87,, 2024.
Ananth Mahadevan and Michael Mathioudakis. Cost-effective retraining of machine learning mod- els. arXiv preprint arXiv:2310.0422 2023.
Pratyush Maini, Zhili Feng, Avi Schwarzschild, Zachary C. Lipton, and Zico Kolter. Tofu: A task of fictitious unlearning for llms, 2024. URL https: org/ httpg//abb//41.055//0 06121.
Sadhika Malladi, Tianyu Gao, Eshaan Nichani, Alex Damian, Jason D. Lee, Danqi Chen, and San- jeev Arora. Fine-tuning language models with just forward passes. In Thirty-seventh Confer- ence on Neural Information Processing Systems, 2023a. URL https: http::::///eenreiew..eo. forum? id=ootaaaaaaao FrF
Sadhika Malladi, Alexander Wettig, Dingli Yu, Danqi Chen, and Sanjeev Arora. A kernel-based view language model fine-tuning. In International Conference on Machine Learning, pp- 23610-23642 PMLR, 2023b.
Nick McKenna, Tianyi Li, Liang Cheng, Mohammad Javad Hosseini, Mark Johnson, and Mark Steedman. Sources of hallucination by large language models on inference tasks. arXiv preprint arXiv:2305.14552, 2023.
Siqiao Mu and Diego Klabjan. Rewind-to-delete: Certified machine unlearning for nonconvex func- tions, 2024. URL https: //axiiv///xiivva/ wtt/abs////oooooooo//o/////.aaea /oabb///499/. 22449.000 09778.
Tarek Naous, Michael Ryan, Alan Ritter, and Wei Xu. Having beer after prayer? measuring cultural bias in large language models. In Lun-Wei Ku, Andre Martins, and Vivek Srikumar (eds.), Proceedings of the 62nd Annual Meeting of the Association for Computational Lin- guistics (Volume 1: Long Papers), pp. 16366-16393 Bangkok, Thailand, August 2024. As- sociation for Computational Linguistics. doi: 10. 10.18663///22024ac--oogggg // //aclanthology org/2024 acl acl-long. 862.
URL https:
Seth Neel, Aaron Roth, and Saeed Sharif-Malvvjjerd Descent-to-delete: Gradient-basel methods for machine unlearning. In Algorithmic Learning Theory, pp. 931-962. PMLR, 2021.
Quoc Phong Nguyen, Bryan Kian Hsiang Low, and Patrick Jaillet. Variational bayesian unlearning. Advances in Neural Information Processing Systems, 33: 16065556666066 2020.
14

---

Published as a conference paper at ICLR 2025
Maxime Oquab, Timothée Darcet, Théo Moutakanni, Huy V. Vo, Mare Szafraniec. Vasil Khali- dov, Pierre Fernandez, Daniel HAZIZA, Francisco Massa, Alaacldin El-Nouby, Mido Assran, Nicolas Ballas, Wojeiech Galuba, Russell Howes, Po- Yao Huang, Shang- Shang-Wen Wen Li, Ishan Michael Rabbat, Vasu Sharma, Gabriel Synnaeve, Hu Xu, Herve Jegou, Julien Mairal, Patrick Labatut, Armand Joulin, and Piotr Bojanowski. DINOv2: Learning robust visual features with- out supervision. Transactions on Machine Learning Research, 2024. ISSN 2835-8856. URL Settps://openreeee www.wewwweeeeeeeeeeee.eee.eeeeee forum? ( 6zFt.
Misra,
Guilherme Penedo, Quentin Malartic, Daniel Hesslow, Ruxandra Cojocaru, Alessandro Cappelli, Hamza Alobeidli, Baptiste Pannier, Ebtesam Almazrouei, and Julien Launay. The refinedweb dataset for falcon Ilm: outperforming curated corpora with web data, and web data only. arXiv preprint 2rX1v:3366.01166 2023.
Xinbao Qiao, Meng Zhang, Ming Tang, and Ermin Wei. Efficient and generalizable certified un- learning: A hessian-free recollection approach, 2024. URL https: / 24C4. 01712.
Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. Learning transferable visual models from natural language supervision. In International conference on machine learning, pp. 9748-8763. PMLR, 2021.
Ben Recht, Christopher Re, Joel Tropp, and Victor Bittorf. Factoring nonnegative matrices with linear programs. Advances in neural information processing systems, 25, 2012.
Ryan Rifkin and Aldebaro Klautau, In defense of one-vs-all classification. The Journal of Machine Learning Research, 5:101-141, 2004.
Nikunj Saunshi, Sadhika Malladi, and Sanjeev Arora. A mathematical exploration of why language models help solve downstream tasks. International Conference on Learning Representations, 2021. URL https: http//ppnneeewweeeeeeeeee net
Christoph Schuhmann, Romain Beaumont, Richard Vencu, Cade Gordon, Ross Wightman, Mehdi Cherti, Theo Coombes, Aarush Katta, Clayton Mullis, Mitchell Wortsman, et al. Laion-5b: An open large-scale dataset for training next generation image-text models. Advances in Neural Information Processing Systems, 35:25278-25294, 2022.
Ayush Sekhari, Jayadev Acharya, Gautam Kamath, and Ananda Theertha Suresh. Remember what you want to forget: Algorithms for machine unlearning, 2021. URL https: pettps://arxiv... /atxxiiirgggg//////............r abs/ 22033 03279.
Weijia Shi, Jaechan Lee, Yangsibo Huang, Sadhika Malladi, Jieyu Zhao, Ari Holtzman, Daogao Liu, Luke Zettlemoyer, Noah A. Smith, and Chiyuan Zhang. Muse: Machine unlearning six-way evaluation for language models, 2024. URL /ttps:://ariisi org/ abs/2445 06460.
Luca Soldaini, Rodney Kinney, Akshita Bhagia, Dustin Schwenk, David Atkinson, Russell Authur, Ben Bogin, Khyathi Chandu, Jennifer Dumas, Yanai Elazar, Valentin Hofmann, Ananya Jha, Sachin Kumar, Li Lucy, Xinxi Lyu, Nathan Lambert, Ian Magnusson, Jacob Morrison, Niklas Muennighoff, Aakanksha Naik, Crystal Nam, Matthew Peters, Abhilasha Ravichander, Kyle Richardson, Zejiang Shen, Emma Strubell, Nishant Subramani, Oyvind Tafjord, Evan Walsh, Luke Zeulemoyer, Noah Smith, Hannanch Hajishirzi, Iz Beltagy, Dirk Groeneveld, Jesse Dodge, and Kyle Lo. Dolma: open corpus of three trillion tokens for language model pretraining re- search. In Lun- Wei Ku, Andre Martins, and Vivek Srikumar (eds.). Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume I: Long Pupers), pp. 15725-15788, Bangkok, Thailand, August 2024. Association for Computational Linguis- tics. doi: 10.18653/ 1/233//.2222422llooe 840. URL https: / /aaaacaann aclanthhhoogy org/2024. acl-long. 840.
Gowthami Somepalli, Vasu Singla, Micah Goldblum, Jonas Geiping, and Tom Goldstein. Diffusion art or digital forgery? investigating data replication in diffusion models. In Proceedings of the IEFF/CVF Conference Computer Vision and Pattern Recognition, pp. 6048-6058 2023.
15

---

Published as a conference paper at ICLR 2025
Anvith Thudi, Hengrui Jia, Ilia Shumailov, and Nicolas Papernot. On the necessity of auditable algorithmic definitions for machine unlearning. In 31st USENIX Security Symposium (USENIX Security 22), pp. 4007-4022, Boston, MA, August 2022. USENIX Association. ISBN 978-1 1- 939133-31-1. URL https: presentation/thun /tpp:://wwww... usen x
xsscrerrerneeeeeeeesssuuuuuuuu ty22/
Enayat Ullah, Tung Mai, Anup Rao, Ryan A Rossi, and Raman Arora. Machine unlearning via algorithmic stability. In Conference on Learning Theory, pp. 4126-4142. PMLR, 2021.
Colin Wei, Sang Michael Xie, and Tengyu Ma. Why do pretrained language models help in down- stream tasks? an analysis of head and prompt tuning. Advances Neural Information Processing Systems, 34:16158-161 1618000 2021.
Chenwei Wu, Holden Lee, and Rong Ge. Connecting pre-trained language model and downstream task via properties of representation. In Thirty-seventh Conference on Neural Information Pro- cessing Systems, 2023. URL https: http:///ppeeeeeee///m/e/e net forumPid--LLOJ4aKANe
Oğuz Kaan Yüksel, Etienne Boursier, and Nicolas Flammarion. First-order ANIL provably learns representations despite overparametrisstion. In The Twelfth International Conference on Learning Representations, 2024. URL https: : http///ppwrreeeeeeeeeeeee net fesrrumii--ifffbbS33
Xiaohua Zhai, Basil Mustafa, Alexander Kolesnikov, and Lucas Beyer. Sigmoid loss for language image pre-training. In Proceedings of the IEEE/CVF International Conference Computer Vision, pp. 11975-11986, 2023.
Binchi Zhang, Yushun Dong, Tianhao Wang, and Jundong Li. Towards certified unlearning for deep neural networks, 2024a. URL https: /atpiii//aaxvv.a//aa org/ abs/2408 00 920.
Ruiqi Zhang, Licong Lin, Yu Bai, and Song Mei. Negative preference optimization: From catas- trophic collapse to effective unlearning. In First Conference Language Modeling, 2024b. URI. https: http:://pppeeieeeeeeeeee net/
www./eruumme/eeeemmmm forum? -it.mmdddddxxixx---- MXImx
16

---

Published as a conference paper at ICLR 2025
A PRECISE DESCRIPTION OF ABASE
A.1 COMPLETE DESCRIPTION
Algorithm High level learning algorithm (AA
Input: document corpus
{dl (di anchor word tolerance eo
Output: matrices A,R
Q word co-occurrences
Q = now-normalized Q
P = RecoverAnchors( Q1...., Qn))
A. = Recover (opieseQ.ppiis
return A, R
Algorithm 4 RecoverAnchors same as Arora et al. (2012a)
Input: Row-normalized co-ocurrence matrix Q and eo tolerance parameter
Output: points of this perturbed simplex close the vertices of the actual simplex Project the rows to randomly chosen 4 log n/e dimensional subspace
S + [Qq} where Q is the furthest point from the origin for in 1, ,,..., F 1 do
Let 2j be the row of Q with largest distance to span(S) 5 S end fors Q2 Q
for i in i,..,,,,, do
Let Qj be the point that has largest distance span(S) (Q..)
Remove Qs, s, from S and insert Qj into S
end for return S
Algorithm 5 Recover Topics, from Arora et al. (2012a)
Input:
Co-ocurrence matrix Q, anchor words P {sI...., sk). tolerance parameter co
Output: Matrices A, R
Q = row normalized Q
Store the normalization constants p Q1
for i in ,,...,7! do
Solve C, = arg min ||Q; u. 11111 DEA.
up to accuracy end for A' diag(p)
A = column- -um--ne normalized A'
R A'QAIT where A is the pseudoinverse of A return A, R
More formally, the co-occurrence matrix is constructed as follows. For each document, let H E IR" be the frequency vector of each word in the document; the sum of its entries should be L. Then, for a document d, consider the matrix
G. HaH. Ha
where
H
Ha:= = VL(L- - 1)
Ha diag Ha)
17

---

Published as a conference paper at ICLR 2025
In particular, the denominator term L(L 1) is precisely the number of co-oceurences in each document, by simple combinatorics, and it can be seen that the sum of the entries of GJ is always 1. Our co-ocurrence matrix Q is defined to be
m Σ Ga
Q = m
so that Q also has entries that sum to 1. By linearity of expectation, we have
[ = EE[aa] = A A
which implies that as the number of documents increases, Q concentrates around AE XXXXX JAA= E|MM J. Therefore, we should expect A QA! to concentrate around E| R
A.2 SKETCH: POPULATION ANALYSIS
To understand this algorithm, consider the setting where have infinitely many documents. Specif- ically, consider two words W1, W22 in a document and their respective topics 21, 22. Then, this population co-occurrence matrix Q will have elements Qi, Pr[w1 i, w2 j], and the row- normalized co-occurrence matrix Q will have entries Qu = Pr[w- = =|w a]. Moreover, have that A, k = Pr[w1 1| = k] = Pr[wy = 22 = k].
Consider the set of anchor words | {....... sr C [ra]. where ske is the anchor word for topic k. Then, observe that for an anchor word row 8 of Q, it holds that
Pr[w2- ylu, sys Σ Pr(21 k ww snl Pr[w2 jlw,
Sk: 21 k7
Prjw22 -||m1= = Sk, 21 k]
= Pr|m22 = -| k
where the second line follows from only Pr(z1 = k/wm = ss] in the summation, and the last line follows from W2, wh are conditionally independent given Furthermore, for non-anchor word rows i of Q, it holds that
Qu = - k|w1 Pr|w2 joæı k]
that W2, W1 conditionally independent ø1. For word let C, E RR be the vector such that C. == Pr[z1 = k|w = i]. Then, it holds that Q; = c, Qs. where Qs is the submatrix Q constrained to the anchor word rows. In other words, for every word i, Q is convex combination of rows of Qs-
where again
In the algorithm, one can see that A/, Ci,aPa. Normalizing this along each column, we obtain
CLEPE
Pr[z1 = k|w1 a] Pr[w = i]
Aik Ex CV
Σx Pr[z1 k|wn 7'] Pr(wi = Pr|wi i|=11 k]
Hence, in the infinite document limit, this algorithm recovers the ground truth 4 R
B FROM PROPERTIES OF THE LEARNING ALGORITHM TO THE PROOF OF THEOREM 2
We first give the formal statement of Theorem 2.
Theorem (Formal statement of Theorem 2). Let Abase be the learning algorithm described the prior sections and Usase be the unlearning algorithm in Algorithm 1. Then, (Abuse Umase) performs wility-preserving unlearning with deletion capacity
0.001m
TrAsss Absa (m) 2 c e-min
12 2
rn log 1/5"
722
where is the number training documents, is the number of topics, and e is constant depen- definition the maximum entrywise
dent on D. The loss function used in the error from the ground truth topic model A
18

---

Published as a conference paper at ICLR 2025
B.1 PRELIMINARIES
When the norm is not specified, we assume that it is the Euclidean norm 1/2. We now start off with technical assumption the precision of the learning algorithm.
Assumption 2. eo S (11/var).
Assumption 3. Every word appears with probability aar without loss of generality; discus- sion in Arora et al. (2012b). Essentially, less probable words can be combined in a sense to form single category of "rare" words.
We recall the definitions from Arora et al. (2012a).
Definition 6 (3-robust simplex). A simplex P is 8-robust if for every vertex of P, the l distance between v and the convex hull of the rest of the vertices as at least B3.
Definition 7. Let [a,)=1 be set of points whose convex hull is simplex with vertices {u: No-1- We say a set of r points is e-close the vertex set {w:]_= if each of the points e-close in & distance to different vertex in this vertex set.
The following result will be used throughout our proof.
Proposition 1 (Arora et al. (2012b)). Qp in population is yyp-robust.
We now list the high probability events we condition on throughout our proof. These follow from previous results in Arora et al. (2012a); they concern the properties of the output of the learning algorithm.
Proposition 2. With high probability, in regime of m, the following hold:
The correct anchor words are selected.
Each word appears at least O
times.
4ar
The error in the empirical matrix Q is entrywise at most Õ(1/ (m) from the population
Q"
We also utilize the following two key lemmas from Arora et al. (2012a) that we touched upon main paper.
Lemma 7 (Approximation Guarantee on Anchor Words). Suppose each row of Q is at most distance away from the ground truth "yp-robust simplex Q* in &a norm. 2f 2 < yp, then the set of anchor words found by the algorithm is O (/0/rp)-close to the ground truth anchor words. Lemma 8. When 20r8/(rp)) Tp, it holds for every word i that C₁ has entrywise error ((8((11)2) from C₁
B.2 PROOF OF THEOREM 2
The following lemmas bounding the relation between Q Q Qi
Lemma 9. After training, the error of each row of Q is at most 82
o(V
dar mico
That is,
|| 1 < 82 for all wordy i.
Importantly, note that
20r (yp)² < <xp
This implies that the anchor words of Q O(62/(1P)) close the anchor words of Q Consequently, it holds that
| - S (0622((1))
Proof. The first part follows directly from the fact that if the number of documents m = (t(1/E)).
then - - Q < 8g for each row i. To show that
20r ( < yp
19

---

Published as a conference paper at ICLR 2025
note that by the sample complexity guarantee, which implies that
mcg 2 Ō ar (rp)6
82 S Ô (xp)
as desired.
0.001mcg(yp)
Lemma 10. When delete my
it holds that
10
my
4armu
mcu/ /ar
mco
In particular, this is smaller than
0.001meo(1p))
0.004(?p))
a2
men/ /4ar
Proof. For a word i, consider the change in Qi after deletion requests. Let F be the initial sum of the the ith row of Q. Each coordinate [n] will change as follows:
-4 6, F my F F(F-
fg mu - Ftt
where fy is the initial number of coocurrences of words i,j and is the number of documents removed that have this cooccurrence. Moreover, is the number initial occurrences of word i, and T' is the number of deletions of the word i. From the previous lemma, it holds that F > mea/ 4ar, and that my 2 ΣØ= Hence, follows that the squared Euclidean norm of the change is:
2F2m2 (mus; -11)²² S F2(F my)
of F2(F Tγ² Σ
m
F mu
Hence, for the regime where my I
0.001mea(Pp)) 2222
we have
[ - S V2
my
my
4army
F
my
me0
Of particular notice is that when my is taken large possible, this is at most 0.001meu(1p))/a7
0.004(>p)3/o /ar
men/ 4ar
now combine the above two with triangle inequality. Lemma 11. Hence, it holds that
4army mcp
4army
+o
4ar mey
-
+ 52
8.
meg
Importantly, note that
20r (xp)2 < yp
This implies that the anchor words of Q are 0 (Tp) close to the anchor words of Q Consequently, holds that
|C - CC 1l:0 (06%/(())))
20

---

Published as a conference paper at ICLR 2025
Proof. The first part follows from triangle inequality, and the second part follows from lemma B.1 from Arora et al. (2012a).
We now bound what happens to ||C -C ||300 First, we have that the perturbed simplex Q is yp/2 7pp2-robust.
Lemma 12. The perturbed simplex 2 is vvp2-robust.
Proof. This is because of Lemma A.I in Arora al. (2012a), Since 10vr82 yp, the result of that lemma applies.
Hence, we will apply Lemma B.1 from Arora et al. (2012a) on C to say something about ||C 1|
Lemma 13. Recall that when delete my
0.001meo(1p)' a²p²
it holds that
4arma
mcn/ 4ar
m66
Importantly, note that
Aarmy
20r
/(Tp/2)2 < 1pp22
meo
This implies that the anchor words of Qf are lemma B.I from Arora al. (2012a), it holds that
Aarma /mea close the anchor words of Q By 7P/2 Aarmu mco
I|C -C so(
/(TD/2)2
Observe that this is smaller than (((xp)/ar)
We now deal with the Hessian step that had took to prevent retraining the C,'s. 's. In particular, will denote C to be our estimated new C.
First, lemma say that Hessian step is full rank and has lower bound its minimum singular value.
0.001meg/1p1 a²
Lemma 14. When we delete my < Q is at least 2p/2.
samples, holds that the minimum eigenvalue of
Proof. Follows from Lemma A.3 in Arora et al. (2012a).
Lemma 15. When we delete my
0.001 .001mmm(ypp) a2p2
samples, it holds for all i,
4 7P
4army
IC C.F1
82
meo
Proof. For the case of d(...) being the squared loss, we will denote the following:
Ciancon := arg mig 1 C @TTTI =
O : prooaa, (C, uncoo))))
OF == arg min QF C 1 СеΛ.
In particular, the Newton step plus projection outputs C,,proj- First, observe that by one of the anchor word lemmas.
4arme
min OF FF C -Q QT[l| =1 Ca - Q < QF FT c Q 15
me0
21

---

Published as a conference paper at ICLR 2025
The last inequality follows from the fact that Q is perturbed version of Qū, and Q is perturred version of Qp. Hence, we will bound
||c 11
I|proja, (Ci,nncon) (C,)
||C Cs,uncon
11ppT TT (C C
min
1
(1121
C. cf + +1Q C inncou 2TT(
mmin
2
4army
82 +
min
mé6
where mmin is the smallest singular value of Q which is guaranteed be full rank per the previous lemma. Due to result in Arora et al. (2012a), this miin 2 (rp)/2. This gives us that the whole quantity most
4
4army
82
7P
mED
Corollary 1. We have that
4(6g
4arme
CCC -CP-OT -C
S
82
pp
mcp
since the Eoo norm is upper bounded by the &2 norm.
Lemma 16. The following are true.
|C -C 11:00 5
4 7P
82
farmu
| C''l < | - 11.0 +
-C S =02
(02
4arme:
+ +088//(7p))
mnco
From this, we can bound the errors on the topic matrix.
Lemma 17. The following are true.
|A" Alloc S 5(arl|[CF C 1lo0)
| A < OF - 12
|A A F x < O(arlI C ((,))0))
Proof. Note that entries Ai, are
Ci, Pr[w = Pr[: =
A
Therefore, the perturbation A will he the perturbation in C multiplied by ar, since the denomi- nator is lower bounded by 1/ar due to the topic imbalance constant.
Now, we give lemma.
Proposition 3. When my 5 Aar
have that
4army
4ar
4armu mcg
armu
8/ 89 +
mcg
mco
mcg
Now, analyze what happens given that 2(
0.001meo(7p)
(Tp)
my
22

---

Published as a conference paper at ICLR 2025
Lemma 18. For e, > O, the deletion capacity satisfies
T.A. 2
(m)
52
m
6,6
,2 n
Proof. Recall that
(ar) mEOp
A lo S 00ar0 1/(1p))) so
Moreover, also have that
A - A 10 S O( - 110)
4ar82
(ar)²mu
megpp
Note that A has l sensitivity of Vrr matrix A entrywise with noise
Pme) meoop
We now apply the Gaussian mechanism to the
Vnr
(ar)²me YP
2 Log( (1.25/))
From this, we obtain that
E A -
A
S E
max i,k
|ui
+ E [[IIA- - A" Ao
< 00
(ar)
v Ilog(1/0)
(ar)2mo meo"/
Vir
/lo((r))
+ 0
meopP
Finally, this says that when
m
S
SZ
22
Vnr
we have that the utility is preserved up to constant amount, say 0.01.
This proves Theorem It straightforward continue the perturbation analysis for the topic-topic covariance matrix R and prove similar deletion capacity rates.
C DOWNSTREAM TASK PROOFS
Recall the algorithm for learning the downstream task head.
Algorithm Learning algorithm for task (Abena)
Input: document corpus S = {d, mm anchor word tolerance A. Abase (S) return arg min wEWneed ( A)
Assumption 4. For any A, é is X-strongly convex with respect to w.
Since topic matrix A, can only take bounded support (i.e. the set of matrices where each row is on the probability simplex), it is natural to say that the set of values w" (A) takes on over all topic matrices A is bounded in certain sense. As such, we also assume the following:
23

---

Published as a conference paper at ICLR 2025
Assumption 5. For any base model A, the vector such that arg min (ww A) satisfies ||l|| 2 S B.
Assumption 6. For any A, Ey is L-Lipschitz with respect to and the Eg norm, and L2- Le-Hssni Lipschitz with respect to w and the Eg norm. In other words,
(A, w1) (A W2 1l1 I L w - w2ll2
V (A, w1) - V (A, w2) I L2||wi w2
Assumption 7. For any w, Vuey L Lipschitt with respect A and the foo norm; that is,
| W (A, w) (A w) S L Al
We give helper lemma that (e, biniiiiiisinnguuhabbiitty immune to post processing.
Lemma 19 (Post-processing immunity). Consider two random variables 01, 02 θ that are (e, 8)- indistinguishable. Then, for any arbitrary mapping f θ + O', it holds that f(01), f(02) E O' are (c, 8) indistinguishable.
Proof. Consider an arbitrary set T" _ O'; = {r f f(r) E J. Then, it holds that
Pr[ʃ(0i) E ETI = Pr|0, ET]
S é Pr|O2 +
e Pr(s(O2) E +5
as desired.
We now give a certifiable unlcarning guarantee for the most naive retraining algorithm for the down- stream task, which we mentioned in the main text Theorem 3.
Theorem 6 (Unlearning when releasing A and w). For a downstream task T with loss func- tion ly, consider the unlearning algorithm Uhead, naive that first runs Algorithm I to compute Ā = VnoseeS (S,, (S), T(S)). where (Abase, Ubase) perform pilitt-preserving unlearning (The- orem 2). Then, it fis a head uo = arg min E ( A) and returns A and w. We assert that (Asead, naive, Unead, naive) performs utility-preserving unlearning (Definition 4).
Proof. Intuitively, this a result of post processing. More precisely, consider the 0e indistinguishable base models Á := Ubase (S Abase (S), and Á' == Usase (0, Asase Sy).T(S Sy)). Then, since the head fitting is a deterministic post-processing of the original model, this proves the (e, fin--inniisiiiuuiaabiiittt between the two.
To prove the utility preservation, observe that in this setting
EII Á
A A0]=)00000
We thus obtain by Lemma 20
E w0 (A) w0 (AA"))looo) 5 BBllw" (A) w wo'AA (A2)
L.o Elll Å A 1oo)
which is at most 0.01, up to constant rescaling.
The above result is nice, and follows from the fact that the training algorithm of the downstream task head is just post-processing. However, downside is that it still requires retraining of the downstream task head. We can show something stronger: even without provable unlearning of the base model (A and R), when the downstream task loss is convex in the trainable weights w.
achieve provable unlearning of the downstream task head weights
We will now consider arbitrary task T. We first give the following notation.
24

---

Published as a conference paper at ICLR 2025
Definition 8. For base model A, let w" (A) arg min (w A). First, we give the following helper lemma that will be useful later on. Lemma 20. Consider two base models A1 and A2. Then, it holds that
Loo A1 A2llo
|| (A1) 20" 200"000000 (A2)ll2
Proof. Observe that (A1) (A2))l2 - V (A (A1); A2) - (wl A2) 1 ( (wi) A2) Vwo (Ai); A1)
< Lo A1 A2lloo
where the first line follows from strong convexity, the second line from the gradients being zero, and the third line from the definition of Lo Lipschitz constant. Dividing both sides by À gives the desired result.
We now define the following notations for clarity.
w == w (AA))
w F w (AF)
" = w" (AA)
w == w - V ; which is the Newton step we take from S to approxi-
mate w
First, we give bound on the approximation error of the Newton step. Lemma 21. It holds that
L2L2 213
t w0ll S
A Al
Proof.
We aim to bound the distance of the Newton step from w":
w "" (ws H e (A, w w) w0
where H e
[A w Then, it holds that
u H V E (A, w=) 20*
S w" H (A, w V. -n,
Hns (ws vi*) f H (a000-00))00 ww ww0))
w
(' (Hwss H (m) dt (wo w²²)
H w
The norm of this quantity is therefore bounded by
1 L2
H 5
1|2
www
w
W 20-1
L2
u0'13
21
Lg
1
(A, (A, - 20 200
2
L2
Lox
2
<
A
A 11,0
21
Hence, we have that
LzL2
20 1|2 5
A A
2
25

---

Published as a conference paper at ICLR 2025
C.I INSTANTIATING FOR TELF [r]
We first instantiate Theorem for the case where Tet - [r]. or equivalently when 4 = 1/ar. Lemma 22. Recall our retrained model for the downstream task is A AF Then, holds that
A A 1/ 10 20VVV (V(((r))m))))
mcorp ) + Bynr nr Par
2
mco7pp
Proof. We rewrite as follows.
Aw - A'w"" = (Aw - Aw") + (Aw* - A'w") + (A"w" - A""w"
Now, we proceed to bound the & norm of each of these individual terms separately. For the first term, have that
A Aw
1|2
||((w t w²))l2 S 10 w² 11
< /r |r| w " 20'12 112
S /r To2 122
||A Al
2X3
r L2L2
(ar)²my)
2x
mEOp
where second line follows from À having column sum and the fourth line follows from Lemma 20 For the third term, we have a similar analysis.
A .0 A w
1
|AP (w"
w
F
$ 1w= w wº11 'l1
S vr 10000* w 10.112 1|2
vr Loo
1| A² AFllos
S Vr Loc
(ar)>
X
mEo?P
Finally, for the second term, we have that
Aw
A "0"
1| S ||A - A 1|2|120
||
A 11 Vnr 1
(ar)2m
0
vnrB
meopP
By triangle inequality, obtain the desired result.
First, we note show the following property of the learned topic model AS.
Lemma 23. The minimum singular value of the ground truth topic matrix A is at least @(p), since the perturbations in entries of A are at most en S Onr//rr)). Hence, the singular values cannot change by more than constant factor relative p-
Proof. We know that * is a p-separable topic model, and hence has smallest singular value at least For the given sample complexity of learning, A will have smallest singular value at least (pp)-
The above result says that 8 has a unique pseudoinverse, and has largest singular value at most O(1/p)
26

---

Published as a conference paper at ICLR 2025
Recall that our goal for the downstream task is approximate the such that
A A "
order to say we have approximated the unlearned line-tuned model. Therefore, it suffices to obtain indistinguishabiiity of our unlearning algorithm output v with (A$)1 A wf. Our following claim that we can use (A Aw as the approximation for this.
Proposition 4. It holds that
|I(AS) Aw (AS)t A
w
lle
s 0
Au - A A"w011 112
1
VF( (ar) (ar)mm
(ar)2my mcop
S 0
B ByTr nr
p
McuYP
Let 0 :- (A9)) Aw and v -AAS) AFw.. We claim the following.
Lemma 24. The unlearning algorithm Uhead that oulputs
where is the noise defined by the Gaussian mechanism using the above sensitivity satisfies prov- able (e, 8) unlearning. In particular, we use
0 (+
(VF(
(ar)²m mea'PP
+ B/Tr
(ar))mu meo't
2 log(1.25/0)
where the numerator the fraction is from the previous proposition.
Proof. This follows from Gaussian mechanism.
We now proceed to bound the deletion capacity. In this case, the utility is defined by the closeness Lo norm, similar the way defined this for the base model unlearning
of E (A u" in ""w"" algorithm Whase earlier.
First, the following lemma to bound AFw -" Lemma 25. We have that
| WF A'w0lla 0 BVnr (ar)?me
mEDNP
Proof. We decompose as follows.
A RD A A-ww" = (A NF w + (AF "0- - -A'w")
The first term is bounded by
A w" F A wwww S v 5 Alllo)) 50 2 VF (ar] meorP
The second term is bounded by
A F un Atu 112 S o (ar)mm
Vnr B
mcorp
by considering the spectral norm || A This gives the desired result.
As result, the following holds. Proposition 5. It holds that
S1) 1 A un (AS): A-w" 1001 50 Vr (ar) + B Bynr /nr (
mco
mc
27

---

Published as a conference paper at ICLR 2025
This is once again from the bounded operator norm property of (A*)t.
Finally, we can apply triangle incquality to get the following. Lemma 26. holds that
1 p
[F
(ar)
B BVT (ar)?mu mEn
(( Aw (AS)T A'
12 I
mED7P
Then, we can get the following bound on deletion capacity. Lemma 27. For ē, > 0, the deletion capacity satisfies
A (m) 2 52
m
E,6
,2 /
Proof. The calculation is as follows.
E B (A*) A"
[loo] A"")
s
E
[o] ([I(AA))) ))t ''Aw- (f (as))AA'u 10====lll" 11o]
1 p
Vr (ar) ( + B Bynr" (ar) 2mo
)
logr log 1/0
+1
meo
MEONP
For this be a small constant, we require
(ar) m
1
1
min
p1/4" /nr
mEOpP
Therefore, we should have
my S 52
m
12 /ror
C.2 PROOF GENERAL !
The following is the formal statement of Theorem 4.
Theorem (Formal version of Theorem 4). Suppose that the downstream task T only depends on subset of topics Tof S [r]: that is, w* = arg min. e (v; A*) has non-zero entries only in the index set Teg. Denote == minkeT,, Pro(z = kl,, and let Aneat be the head luning algorithm (D (Definition 2) and Unead be Algorithm 2. Then, (Aneout Unead) performs utility- preserving unlearning with deletion capacity
T-Anua Mared (m) 2 min
mqe
0.001m 222
r rr nr log 1/8
where d' is a constant dependent on D, and
Lemma 28. Recall our retrained model for the downstream task is A F... Then, it holds that
A F 12fll22 s 0 (vi( (ar)mmy) ( meoYD )
(1/g)armm meopP
(((0()))) [(ar)mm
+
BBrr
+0
V nr
Proof. Consider this decomposition again.
Au AFw" (Aw Aw") (Aw* - AFw") (A i
AAw"
The first term the same as old analysis; the second term is from considering q the third is the same as the old analysis. In particular, when = 1/ar, we recover the old bound. We have that the first term is
A Awo S Vr L2
(ar)
2x3
mcup
28

---

Published as a conference paper at ICLR 2025
The third term is
||A W0 AFw I vr Too
(ar))mo
medp
The second term is ||
A w || 5 I1(A A "100'1 11(A - AF)(w* - -20")l
(1/q)armo
(ar) 2
s 0 B Bynr nr
+ +0
v
mEo7P
me07/
This gives the desired result using triangle inequality.
Continuing, we have the following. Proposition 6. It holds that
)t Aw (A A w
0 ! |A A "w 1|2
1 p
[T( (ar)
(1/g)arm meo7p
(ar)2me me07p
0
+ Byrr
nr
mEoYP
This gives us the following. Lemma 29. The unlearning algorithm Uhead that outputs
+ Ve
where Vy is the noise defined by the Gaussian mechanism using the above sensitivity satisfies prov- able (c, 8) unlearning. In particular, we use
(ar) maU
+ BVT
[1/glarme
(ar) mau
/nr
mEO'P
mCo'P
mP
2 log 1.25/0)
where the numerator of the fraction is from the previous proposition.
Proof. This follows from Gaussian mechanism.
We proceed to bound the deletion capacity. In this case, the utility is defined by the closeness loo norm, similar the way we defined this for the base model unlearning
of è to (AS)1A A w in algorithm Umase earlier.
First, the following lemma to bound A FF A Ar Lemma 30. We have that
A Ff A''" 112 50 ((vv(( (ar)
+ B/ (1/q)arme m6gpP
(ar))mr
Vnr
mcopP
mcopp
Proof. We decompose as follows.
A F A r'=== (AF F -AF + (AF - -''w") The first term is bounded by
A F F "0 S Vr w SO Alloo)) 5o VT (ar)2mu
(VV mcoYP
The second term is bounded by
(1/q)armo mEOpP
(ar))mm 2
AA =n A'w" < Bynr
vnr
meorp
Triangle inequality gives the desired result.
29

---

Published as a conference paper at ICLR 2025
As result, the following holds. Proposition 7. It holds that
1 p
(ar)
(1/g)arma
(ar)mm
[I wf - (AA9) s 0
Vr
+ B Bynr
vnr
mEONP
mEopP
me0
This is once again from the bounded operator norm property.
Finally, apply triangle inequality to get the following.
Lemma 31. It holds that
[I(AS) Aw (AS) S ( [v[( (ar))
(1/g)arme
(ar)
B/Trr meepP
V Vnr
MEONP
me677p
Then, get the following bound deletion capacity. Lemma 32. For e, > O, the deletion capucity satisfies
T Mhrnd (m) 2 12
m
c
/rr
Proof. The calculation is as follows.
E | (AS)t A " [loo|
ol] +
Au (AA)' "''w''""l" [1
(ar)2me
+ B B/ (1 (1/q)armx
(ar))mm))
VF
var
p
meorp
mE07P
mEopP
/log r log 1/6
+1
For this to be a small constant, we require
(ar)mm Ô :0(min) min
1 1
org Vne
1//2
(nr)
When is least 3 the last of these terms will be the smallest.
Therefore, we have that
my S 52
mg
0.5
C.3 DOWNSTREAM TASKS WITH INEXACT MINIMIZERS
We will consider r-optimal minimizers for the downstream task. Definition 9. For a base model A, let w, (A) E {w l A) - (r(w" (A); S r).
We will have the following technical assumption on 7 to climinate trivial cases. Assumption 8. We assume that т O(1/r).
We have the following intermediate result.
Lemma 33. For base model A, it holds that
[w w" (A)lla S 22T/A
Proof. This follows from standard strong convexity argument.
This gives updated version of Lemma 20, using triangle inequality.
30

---

Published as a conference paper at ICLR 2025
Lemma 34. Consider two base models A1 and A2. Then, it holds that
Loo (A1) w. (A2)ll2 < 22/2//24 w|w" (A1) w (A2)ll s 22/22/A
|| A2llo0 A
We now define the following notations for clarity.
: w (A²)
w. F == w. (A²)
w = w" (A)
Wr : : - H V W A), which is the Newton step we take from w to approxi-
mate w0
Now, consider our Newton step from w- (A to approximate w. (AF). To do so, consider
w == w
H w
V.. Vn (
Then, the following holds, using a similar argument as a previous section.
L2
a0, 10012 -
21
L2
(1/
201 + 11 - 22
w
-200
X
L2
2r
Lx 14 1
+
where the second term of the last line follows from line in the previous proof of the Newton step.
We now bound A ff 1|2. We rewrite this as follows.
Aw A ". = (Aw, Aw") + (Aw* A + WF - AF
The second term we bounded as part of a previous proof. The first term we bound using the above, and the third part we bound using the inexact minimizer lemma. By step previous proof, we can say that the first term
Aw
Aw
112 S vill w.
w0'l2 112
2L2
L2L22
((rr)
$ /r
12
2X3
meo
The second term, to reiterate, satisfies
A A w 1/2 s0
((rr))m Vnr
meopp
The third term satisfies
L F F A ll2 S Villw* wf 112 S 2rT/A
Therefore, the entire term is bounded by the sum of the above three terms via triangle inequality. In particular, this is
[vF (v=((ar)) meopp
(ar) m
B nr
VTT + VPT
mcp3/p
Recall that our goal the downstream task approximate the v such that
S A w
or in other words, (A w.". Our claim is that for this. The following statement formalizes this, utilizing the fact about the maximum singular value of A being most @(1/p).
( Aw, approximation
31

---

Published as a conference paper at ICLR 2025
Proposition 8. It holds that
[ar){mm \
(ar)
VTT vir) (
|[ (AS) w f s 0
vi mEOpP
+ B Bynr
meopP
Now, let Ø : (AS)1 Aw,, and v (A Afw.. We claim the following.
w.f
Lemma 35. The unlearning algorithm Unead that outputs
= V/
where Vy is the noise defined by the Gaussian mechanism using the above sensitivity satisfies prov- able (e, 6) unlearning. In particular, we use
VT
(ar) MOOPP
+ B ByTr
(ar) Pmy moo"PP
+ VTT + ViT))
P
/2 log(1.25/0)
where the numerator of the fraction is from the previous proposition.
Proof. This follows from Gaussian mechanism.
We now proceed to bound the deletion capacity. In this case, the utility is defined by the closeness of ē (A A"w" in &o norm, similar the way we defined this for the base model unlearning algorithm Ubase earlier.
First, the following lemma to bound A w A' Lemma 36. have that
A F " A' 122 S 50 B BV (ar)²mu mE6PP + VrT
Proof. We decompose follows.
A f A'ww" = (A : - AF (F (AP AF + (AFw" A''w")
The second term is bounded by
A w F A S V 50 A3) S 5o 0 ((rr (ar))m
mcofPP
The third term is bounded by
F w A'ww 10 s
(ar))mo /nrB meorp
by considering the spectral norm ||A" 11F-A4 -A11l2
Finally, the first term is bounded, from an above argument, by /2rT/2. This gives the desired result.
As result, the following holds. Proposition 9. It holds that
AA (AS)AA' A'""""""" < 20 vr Par)
B B-nr (ar)
ViT
meD7
mEn
This is once again from the bounded operator norm property of (As)t.
Finally, apply triangle inequality get the following.
32

---

Published as a conference paper at ICLR 2025
Lemma 37. It holds that
[I(A)) Au,, A = ( (ar))ms
[ VT
(ar) meopp
+ +vr + ViT)
B/nr
meopp
Then, get the following bound on deletion capacity. Lemma 38. For e, > O, the deletion capacity satisfies
A Mrrad (m) 2 52
m
e,6
p2 /nr
Proof. The calculation is as follows.
[ (A3)1 A A
[| - Ellloolad + [[ {)) AA - (A 1 A+ 110]
2 (ar)>me
mcopp + BBYr (ar)2mo
(
(Vloogr log 1/8 +1)
+ vrT + vir)
p
mcopP
For this to be a small constant, we require
(ar) m δ min
p//4 Var
since we already have T = O(1/r) by assumption. Therefore, we should have
my S <á
m
Finally, for general g, the same idea used in this section for inexact minimizers be combined with the previous section.
33


Reviews:
[{"review_id": "SZV7ZmmzVw", "reviewer": "Reviewer_LuZt", "summary": "This paper studies machine unlearning in topic models and downstream tasks. The authors developed unlearning algorithms that enjoys provable guarantees, for both the topic model and downstream tasks. The proposed unlearning algorithms can be implemented efficiently, with runtime independent of the dataset size.", "questions": "See the Weaknesses section.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The authors developed unlearning algorithms with provable guarantees for topic models and its downstream tasks. This can be viewed as the first theoretical guarantees for unlearning in the pretraining and finetuning paradigm. Also, the proposed unlearning algorithms can be implemented efficiently, with runtime independent of the dataset size.", "weaknesses": "1. It seems that the proposed algorithms are heavily related to the learning algorithm developed by Arora et al. 2012. Can authors generalize their results to other learning algorithms?\n2. Since this is the first unlearning algorithm in the pretraining and finetuning paradigm that enjoys provable guarantees, can authors highlight their technical contributions in deriving the results? What are the main breakthroughs compared to developing provable unlearning algorithms in the supervised setting?\n3. There are several constants in Definition 4 (e.g., 0.9 and 0.01). Is that possible to make these constants more universal, e.g., to $\\gamma_1$ and $\\gamma_2$? If so, how would $\\gamma_1$ and $\\gamma_2$ affect the developed guarantees?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "aA8pnwoghJ", "reviewer": "Reviewer_Hp5C", "summary": "The paper studies machine unlearning for topic models. Topic modeling is proposed as one of the simplest case of the pretrain/finetune paradigm, where the distribution of words for each topic can be \"pretrained\" using provable algorithms (Arora et al., 2012), and this matrix can then be adapted for downstream classification tasks (fine-tuning). The authors propose algorithms for unlearning documents in both the pretraining and fine-tuning phases and prove that the models output by these algorithms have similar performance to, and are nearly indistinguishable from, models that were never trained on the unlearned documents. The results also show that unlearning is \"easier\" (more documents can be unlearned with the same degradation in task performance) in the fine-tuning phase. The key technique in the proof (as I understand it) is to show that the estimates of word co-occurrence statistics in terms of \"anchor word\" co-occurrence vectors don't change much when updated by the unlearning algorithm.", "questions": "- other questions above\n\n- \"it is unclear why one would want to use A without w or vice versa.\" I agree $w$ isn't useful without $A$, but isn't $A$ useful without $w$? It seems plausible that $A$ and $w$ would be released separately so $A$ can be used some other unforseen tasks.\n\n- For related work on \"Theoretical analysis of pre-training and fine-tuning\", the authors might be interested in work that studies provable guarantees for contrastive pretraining and head tuning in the context of topic models: https://www.jmlr.org/papers/volume22/21-0089/21-0089.pdf", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- Serious theoretical effort to give provable unlearning guarantees in a simplified setting. An important step towards understanding unlearning for more complicated pretrain/finetune setups.\n\n- Builds on the provable topic modeling results of Arora et al. (2012) to give much stronger unlearning guarantees than other work on provable unlearning.\n\n- The main results are clearly explained and contextualized, especially the difference between unlearning for pretrained models and unlearning for fine-tuned models.", "weaknesses": "- The presentation is a bit hard to follow and relies heavily on many results from Arora et al. (2012).\n  - $(\\epsilon, \\delta)$-unlearning is mentioned but not defined in L85--86. It would be helpful for those unfamiliar w/ the formalization of unlearning to at least sketch the details here so the reader can understand the type of guarantee that the paper is trying to give.\n\n  - The need for a utility-preserving unlearning definition is not well-motivated. In Definition 4, it seems intuitive that (1) should imply that the unlearned model is not much worse than the output of $\\mathcal{A}(S)$ except in pathological cases.\n\n  - Related to the previous point, why does (2) compare to the irreducible loss (i.e., the best-achievable loss) $h^*$ and not the loss of the model output by $\\mathcal{A}(S)$? \"Utility-preserving\" intuitively sounds like unlearning from a model $m = \\mathcal{A}(S)$ gives me a new model $m'$ that is not much worse than $m$. But instead this definition compares to the loss of the optimal model $m^*$. Doesn't this essentially pre-suppose that $\\mathcal{A}(S)$ is a very good learner?\n\n  - In Lemma 1, $(\\epsilon, \\delta)$-differentially-private is not defined. Can the authors relate it back to Definition 3?\n\n  - What is the intuition for $\\gamma$ in Theorem 1?\n\n  - The stated results don't indicate how the unlearning capacity depends on the minimum anchor word conditional probability $p,$ but clearly this is a very important quantity. What if my unlearning set contains all the samples with that topic's anchor word? (It's clear in the proof, but maybe it'd be better to make it clear in the Theorem statement)\n\n  - Important quantities, such as $C^{F}$, are never defined in the text and only explained in pseudocode in Algorithm 1.\n  - A numerical example / walkthrough of the proposed algorithm on a synthetic example would be very helpful for understanding. It's currently easy to get lost in the notation\n\n- The results would be stronger if the authors connected them more to empirical results in other settings (beyond topic models). For example, they show that unlearning is easier for task-specific models than pretraining. Is this backed up by empirical evidence with more realistic models?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4Fvvj5swmI", "reviewer": "Reviewer_QxzF", "summary": "The paper proposes and analyzes unlearning algorithms in topic language models. In a language model, unlearning algorithms are algorithms to forget a specified set of documents $S_f$ present in training data (used in pre-training or fine-tuning stages). Ideally, once the unlearning is done, the model should be equivalent to one trained without $S_f$.\n\nIn the context of the paper, topic modeling means, learning $A: n \\times r$ whose columns are word probability distributions for the topics and $R: r \\times r $: a topic-topic co-occurence matrix. Here $n$ is the vocabulary  size and $r$ is the number of topics.\n\nThe key components of the unlearning algorithms are (a) a Hessian update to the $n$ word-topic distribution vectors $C_i$ each of size $r$ (b) update A, R  and finally (c) introduce DP-noise with Gaussian mechanism.\nThe key contributions of the paper are to show DP guarantees on the proposed unlearning algorithms.", "questions": "Footnote in page 4 says that L = 2; that is, the document length is fixed to 2 words. That seems limiting.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The paper gives solid theoretical results.", "weaknesses": "Unlearning algorithms for language models have practical applications, as the authors argued in the introduction of the paper. However, it is an indeed a limitation — as the authors rightly point out — that the analysis is on topic models, which are not state of the art at this time. Further — I am saying this without citations — Gaussian mechanism is also not practical as it introduces too much noise to make the output useful.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "R9SRbcjpwR", "reviewer": "Reviewer_JM47", "summary": "This paper combines old with new: an old theoretical bag-of-words topic-model that has provable guarantees, with a new problem: unlearning. It designs unlearning algorithms and proves theorems about these, that in certain cases unlearning can be done using less time than it would take to re-run the learning algorithm.", "questions": "To be honest, this may have been an excellent paper 5-10 years ago, but I'm curious what someone can learn from it today.", "limitations": "", "rating": 3, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 1, "strengths": "This paper is very well written and addresses a problem that is in the spotlight: unlearning. I haven't checked the math carefully, but it looks like it is likely correct.", "weaknesses": "I'm sorry to say it, but bag-of-words language models have little remaining relevance today. Furthermore, in the few cases where they are relevant, they are quite fast to train. Therefore, proving complex theorems about speeding them up is not of general interest. It also does not seem likely that the takeaways from these bag-of-words models provide insight into the larger relevant models. This paper might be of interest to specialized theoretical conferences such as ALT.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)