Paper deep dive

Unlearning as multi-task optimization: A normalized gradient difference approach with an adaptive learning rate

Zhiqi Bu, Xiaomeng Jin, Bhanukiran Vinzamuri, Anil Ramakrishna, Kai-Wei Chang, Volkan Cevher, Mingyi Hong

Year: 2024Venue: arXiv preprintArea: Model EditingType: EmpiricalEmbeddings: 133

Models: Falcon-1B, GPT2-XL, Llama2-7B, Mistral-7B, Phi-1.5

Intelligence

Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 95%

Last extracted: 3/12/2026, 7:37:01 PM

Summary

The paper introduces Normalized Gradient Difference (NGDiff), a novel machine unlearning algorithm for Large Language Models (LLMs) that frames unlearning as a multi-task optimization problem. By dynamically balancing the gradients of the forgetting objective and the retaining objective, NGDiff achieves superior performance on the TOFU and MUSE datasets while maintaining stable training through an automatic learning rate scheduler.

Entities (5)

NGDiff · algorithm · 100%MUSE · dataset · 98%TOFU · dataset · 98%Machine Unlearning · field-of-study · 95%Multi-task Optimization · optimization-framework · 95%

Relation Signals (3)

NGDiff → evaluatedon → TOFU

confidence 98% · empirically demonstrate the superior performance of NGDiff among state-of-the-art unlearning methods on the TOFU and MUSE datasets

NGDiff → evaluatedon → MUSE

confidence 98% · empirically demonstrate the superior performance of NGDiff among state-of-the-art unlearning methods on the TOFU and MUSE datasets

NGDiff → optimizes → Machine Unlearning

confidence 95% · we introduce a normalized gradient difference (NGDiff) algorithm... for LLM unlearning

Cypher Suggestions (0)

No Cypher suggestions yet.

Abstract

Abstract:Machine unlearning has been used to remove unwanted knowledge acquired by large language models (LLMs). In this paper, we examine machine unlearning from an optimization perspective, framing it as a regularized multi-task optimization problem, where one task optimizes a forgetting objective and another optimizes the model performance. In particular, we introduce a normalized gradient difference (NGDiff) algorithm, enabling us to have better control over the trade-off between the objectives, while integrating a new, automatic learning rate scheduler. We provide a theoretical analysis and empirically demonstrate the superior performance of NGDiff among state-of-the-art unlearning methods on the TOFU and MUSE datasets while exhibiting stable training.

PDF

Open source PDF →Open local PDF →

Trouble viewing inline? Open PDF directly →

Full Text

132,801 characters extracted from source content.

Expand or collapse full text

[table]capposition=above Unlearning as multi-task optimization: A normalized gradient difference approach with an adaptive learning rate Zhiqi Bu Amazon AGI Equal contribution. Work done during Xiaomeng Jin’s internship at Amazon. Corresponding author: zhiqibu@amazon.com Xiaomeng Jin∗ UIUC Bhanukiran Vinzamuri Amazon AGI Anil Ramakrishna Amazon AGI Kai-Wei Chang Amazon AGI & UCLA Concurrent positions as an Amazon Scholar and as a faculty at the corresponding institutes. This paper represents the work performed at Amazon. Volkan Cevher† Amazon AGI & LIONS EPFL Mingyi Hong† Amazon AGI & University of Minnesota Abstract Machine unlearning has been used to remove unwanted knowledge acquired by large language models (LLMs). In this paper, we examine machine unlearning from an optimization perspective, framing it as a regularized multi-task optimization problem, where one task optimizes a forgetting objective and another optimizes the model performance. In particular, we introduce a normalized gradient difference (NGDiff) algorithm, enabling us to have better control over the trade-off between the objectives, while integrating a new, automatic learning rate scheduler. We provide a theoretical analysis and empirically demonstrate the superior performance of NGDiff among state-of-the-art unlearning methods on the TOFU and MUSE datasets while exhibiting stable training. 1 Introduction Large language models (LLMs) consume a large amount of data during pre-training. After the model is built, we may have to unlearn certain data points that contain potentially sensitive, harmful, or copyrighted content. As re-training from scratch in such a case is not feasible due to the associated costs, researchers have developed a number of machine unlearning methods applied after training. Existing machine unlearning methods are formulated primarily as minimizing memorization through the language model loss [22, 7, 34]. In particular, the Gradient Ascent (GA) method maximizes the language model (LM) loss (i.e., minimizes the negative LM loss) on the target forget set (F). However, this approach can also negatively affect the utility of the model. To mitigate the utility loss, the Gradient Difference (GDiff) method selects a subset of the training data as the retain set (R), minimizing the sum of the negative LM loss on the forgetting set and the standard LM loss on the retaining set. This approach has been empirically shown to effectively preserve the model’s performance [31, 36]. Similarly, Negative Preference Optimization (NPO) [55] assigns a lower likelihood of forgetting data, thereby balancing the unlearning performance with model utility. Despite these successes, there are still two key issues preventing the methods from reaching their full potential. First, balancing retaining and forgetting losses is difficult (Figure 1) given the disproportionate sizes of the forget and retain datasets. Second, the optimization methods for unlearning are usually sensitive to the learning rate (cf., Appendix A, Figure 6). For instance, various learning rates can lead to substantial changes in the ROUGE scores and loss values even for the same algorithm, making the unlearning methods unstable and difficult to use in practice. In this paper, we carefully examine unlearning from an optimization perspective and formulate it as a multi-task optimization (MTO) problem [9, 51]: we aim to minimize the LM loss (i.e., maximize the utility) on the retaining set and maximize the LM loss on the forgetting set (i.e., minimize memorization), simultaneously.111A naive approach is optimizing the sum of these two objectives. We will discuss alternatives to improve upon this. To solve this two-task problem, we study the rich literature of multi-task methods that seeks the Pareto optimality of two tasks (e.g., IMTL [33], GradNorm [10], RLW [30], PCGrad [52], and scalarization [3]), and design an approach specifically for the LLM unlearning problem. Figure 1: Loss values and ROUGE scores on the forgetting and retaining data from the TOFU dataset using different unlearning methods on the Phi-1.5 language model. We apply the extended GDiff with various coefficients (see (3), 0≤c≤1010≤ c≤ 10 ≤ c ≤ 1) and connect the results with a blue dashed line. We denote MTO methods as different markers, and use a grey dashed line to represent the loss of random guess. Inspired by the simplicity and strong empirical performance of linear scalarization methods,222[51] demonstrate that linear scalarization outperforms, or is at least on par with, other MTO approaches across various language and vision experiments which minimize a linearly weighted average of task losses, we propose an LLM unlearning method, NGDiff, based on dynamic scalarization, and analyze its theoretical properties. Building on the analysis, we introduce an automatic learning rate adaptation method tailored for LLM unlearning. We showcase the effectiveness of our method through extensive experiments on multiple datasets, different LLMs and vision models. For example, on TOFU [36], NGDiff achieves 40% higher model utility while maintaining comparable unlearning performance with Llama2-7B. Figure 1 highlights the effectiveness of NGDiff. Contributions are summarized as follows: • We formalize LLM unlearning as a multi-task optimization problem and unify the terminology used across both fields. We demonstrate the Pareto optimality for scalarization-based unlearning methods under some assumptions. • Through the lens of multi-task optimization, we propose a novel unlearning method NGDiff for LLM unlearning, which uses the gradient norms to dynamically balance the forget and retain tasks. NGDiff improves both tasks simultaneously and monotonically with a proper learning rate scheduling. • We integrate NGDiff with GeN [4], which uses Hessian-based learning rate selection for stable convergence. 2 Related Work We position our work within the related literature. More discussion and background on learning rate-free techniques are in Appendix E. LLM unlearning The extensive data used in training LLMs raises significant concerns. Certain data sources contain personal information [5], outdated knowledge [50], and copyright-protected materials [45]. In addition, adversarial data attacks can maliciously manipulate training data to embed harmful information [48, 27]. To remove unwanted information without retraining the entire model, machine unlearning has been proposed using techniques such as data slicing [2], influence functions [47], and differential privacy [17]. However, these methods are challenging to scale to LLMs due to their complexity. Recently, efficient approximate unlearning methods have been proposed for LLMs [16, 54, 22, 39, 6]. They mostly focus on designing unlearning objectives or hiding unwanted information. However, none addresses the fundamental optimization problem. Our paper bridges this gap and complements existing approaches. Further discussion of the challenges surrounding LLM unlearning can be found in benchmarks [43, 36] and surveys [44, 35]. Note that the literature on knowledge editing [12] is also relevant. However, model editing typically focuses on surgically updating LLMs for specific knowledge, whereas unlearning removes the influence of particular documents. The techniques presented in this paper could potentially be applied to knowledge editing. Multi-task optimization In NLP, multi-task learning [56] typically refers to building a model that can perform well on multiple tasks simultaneously by sharing representations, introducing constraints, or combining multiple learning objectives. This often involves optimizing a form of static linear scalarization, as introduced in the next section. Multi-task optimization, on the other hand, focuses on a slightly different concept – optimizing two distinct learning objectives simultaneously. The key challenge is how to balance the trade-off among objectives during the optimization procedure by modifying the per-task gradients (e.g. PCGrad [52], RLW [30], IMTL [33]). Several recent works have studied Pareto frontier and optimally in context of NLP tasks (e.g., multi-lingual machine translation [8, 51] and NLP fairness [18]). While optimization is often treated as a black-box tool in NLP research, studying optimization provides deeper insights and inspires new algorithms.333An example is the Baum-Welch algorithm, originally proposed to estimate the parameters of HMMs and applied in speech recognition in 1970s before it was recognized as an instance of the EM algorithm [14]. It was later identified as a special case of a broader class of convex-concave optimization (CCCP) [53]. This connection inspired new designs, such as the unified EM [42]. 3 Unlearning as multi-task optimization This section casts machine unlearning as a multi-task optimization (MTO), specifically the two-task optimization problem. Let the retain set be denoted by R and the forget set by F, with LRsubscriptRL_ RLR and LFsubscriptFL_ FLF representing the corresponding cross-entropy losses for language modeling. We are interested in finding arg⁡minθ⁡LR⁢()∩arg⁡maxθ⁡LF⁢(),subscriptsubscriptRsubscriptsubscriptF _θL_ R( θ) ∩ % _θL_ F( θ),arg minitalic_θ LR ( italic_θ ) ∩ arg maxitalic_θ LF ( italic_θ ) , (1) where θitalic_θ represents the model parameters. There might not be a solution that simultaneously achieves both objectives in Eq. (1). For LLMs, the unlearning solutions generally exhibit a trade-off between performance in R and F (cf., Figure 1). To forget F, one may unavoidably unlearn general knowledge such as grammar rules on F, which can sacrifice the performance on R. In MTO, Pareto optimality is used to characterize the trade-offs between multiple objectives. In layperson’s terms, if θ is Pareto optimal, it is impossible to improve LRsubscriptRL_ RLR or LFsubscriptFL_ FLF without worsening the other. Formal definition is in below: Definition 1 (Pareto optimality in unlearning). For two models θitalic_θ and ′superscript′ θ italic_θ′, if LR⁢()≥LR⁢(′)subscriptRsubscriptRsuperscript′L_ R( θ)≥ L_ R( θ )LR ( italic_θ ) ≥ LR ( italic_θ′ ) and LF⁢()≤LF⁢(′)subscriptFsubscriptFsuperscript′L_ F( θ)≤ L_ F( θ )LF ( italic_θ ) ≤ LF ( italic_θ′ ) with at least one inequality being strict, then θitalic_θ is dominated by ′superscript′ θ italic_θ′. A model is Pareto optimal if it is not dominated by any other models. In the remainder of this section, we will discuss current unlearning methods in a unified MTO framework and analyze their Pareto optimality. Building on this, we then propose a dynamic scalarization approach tailored to LLM unlearning. 3.1 Static linear scalarization A popular MTO method is scalarization, which addresses MTO by optimizing the linear scalarization problem (LSP). This method combines multiple tasks into a single, reweighted task: LSP⁢(;c)=c⋅LR⁢()−(1−c)⋅LF⁢(),LSP⋅subscriptR⋅1subscriptF LSP( θ;c)=c· L_ R( θ)-(1% -c)· L_ F( θ),LSP ( italic_θ ; c ) = c ⋅ LR ( italic_θ ) - ( 1 - c ) ⋅ LF ( italic_θ ) , (2) where c is fixed. At iteration t, the gradient of LSP, static⁢(t;c)subscriptstaticsubscript g_static( θ_t;c)italic_gstatic ( italic_θitalic_t ; c ), lies within the linear span of per-task gradients as shown in Figure 2 (yellow area): static⁢(t;c)=∂LSP∂t=c⋅R⁢(t)−(1−c)⋅F⁢(t).subscriptstaticsubscriptLSPsubscript⋅subscriptRsubscript⋅1subscriptFsubscript g_static( θ_t;c)= ∂ % LSP∂ θ_t=c· g_ R( θ_t)-(1-c% )· g_ F( θ_t).italic_gstatic ( italic_θitalic_t ; c ) = divide start_ARG ∂ LSP end_ARG start_ARG ∂ italic_θitalic_t end_ARG = c ⋅ italic_gR ( italic_θitalic_t ) - ( 1 - c ) ⋅ italic_gF ( italic_θitalic_t ) . (3) Then, the corresponding update rule by the (stochastic) gradient method is t+1=t−ηt⁢[c⋅R⁢(t)−(1−c)⋅F⁢(t)].subscript1subscriptsubscriptdelimited-[]⋅subscriptRsubscript⋅1subscriptFsubscript θ_t+1= θ_t- _t[c· g_ % R( θ_t)-(1-c)· g_ F( θ_t)].italic_θitalic_t + 1 = italic_θitalic_t - ηitalic_t [ c ⋅ italic_gR ( italic_θitalic_t ) - ( 1 - c ) ⋅ italic_gF ( italic_θitalic_t ) ] . (4) Remark 3.1. We term the static linear scalarization as the extended GDiff in this work. Some existing methods are special cases of extended GDiff. For example, Gradient Descent (GD) on retaining set is equivalent to extended GDiff with c=11c=1c = 1. Gradient Ascent (GA) on forgetting is equivalent to that with c=00c=0c = 0, and vanilla GDiff [31] set c=0.50.5c=0.5c = 0.5 (i.e., equally weighted). Figure 2: Gradient space in 2-dimension. FsubscriptF [rgb]1,0,0 g_ Fitalic_gF is the forgetting gradient and RsubscriptR [rgb]0,0,1 g_ Ritalic_gR is the retaining gradient, each with a perpendicular dashed line. Yellow area is the linear span (Eq. (3)) by scalarization. Green area is positively correlated to RsubscriptR g_ Ritalic_gR and negatively correlated to FsubscriptF g_ Fitalic_gF by Eq. (7), whereas NGDiff always stays within this green area at each iteration by Lemma 4. A nice property of linear scalarization is the Pareto optimality at the convergence of models, which we state in Lemma 2 (proof in Appendix G) for the static c and later extend to Theorem 3 for the dynamic ctsubscriptc_tcitalic_t in Section 3.2. Lemma 2 (restated from [51]). For any 0<c<1010<c<10 < c < 1, the model LSP∗⁢(c)∈arg⁢minθ⁡LSP⁢(;c)subscriptsuperscriptLSPsubscriptargminLSP θ^*_LSP(c)∈ *arg\,min_θ LSP% ( θ;c)italic_θ∗LSP ( c ) ∈ start_OPERATOR arg min end_OPERATORθ LSP ( italic_θ ; c ) is Pareto optimal. Lemma 2 suggests444We note that Lemma 2 is only applicable to the global minimum of LSP, which is not always achievable. While this result has its limitations and requires empirical validation, it provides guidance for algorithm design. that we can sweep through c∈[0,1]01c∈[0,1]c ∈ [ 0 , 1 ] and construct the Pareto frontier after sufficiently long training time (e.g., the blue dotted line in Figure 1). However, while any c leads to a Pareto optimal point, the solution may be useless: e.g., perfect memorization on (R,F)RF( R, F)( R , F ) that fails to unlearn is also Pareto optimal. Next, we investigate different choices of c by extending the static scalarization in (3). 3.2 Dynamic scalarization Static scalarization uses a constant c in (3). However, we can extend it to use different scalars at different iteration: t+1subscript1 θ_t+1italic_θitalic_t + 1 =t−ηt⁢UN⁢(t;ct), whereabsentsubscriptsubscriptsubscriptUNsubscriptsubscript where = θ_t- _t g_UN( θ_t;c_t% ), where = italic_θitalic_t - ηitalic_t italic_gUN ( italic_θitalic_t ; citalic_t ) , where UN⁢(;ct)subscriptUNsubscript g_UN( θ;c_t)italic_gUN ( italic_θ ; citalic_t ) :=ct⋅R⁢()−(1−ct)⋅F⁢().assignabsent⋅subscriptsubscriptR⋅1subscriptsubscriptF :=c_t· g_ R( θ)-(1-c_t)· g% _ F( θ).:= citalic_t ⋅ italic_gR ( italic_θ ) - ( 1 - citalic_t ) ⋅ italic_gF ( italic_θ ) . (5) It is worth noting that instead of defining ∗=argminθ⁢LSPsuperscriptsubscriptargminLSP θ^*=argmin_θ LSPitalic_θ∗ = argminθ LSP at the loss level, we can define it at the gradient level based on the stationary condition of the training dynamics, i.e., UN⁢(∗)=subscriptUNsuperscript0 g_UN( θ^*)= 0italic_gUN ( italic_θ∗ ) = 0. Several unlearning and MTO methods can be viewed as special cases of Eq. (5): 1. Gradient descent (GD on R), ct=1subscript1c_t=1citalic_t = 1 2. Gradient ascent (GA on F), ct=0subscript0c_t=0citalic_t = 0 3. Gradient difference (vanilla GDiff), ct=0.5subscript0.5c_t=0.5citalic_t = 0.5 4. Loss normalization (LossNorm), ct1−ct=LFLRsubscript1subscriptsubscriptFsubscriptR c_t1-c_t= L_ FL_ Rdivide start_ARG citalic_t end_ARG start_ARG 1 - citalic_t end_ARG = divide start_ARG LF end_ARG start_ARG LR end_ARG 5. RLW [30], ct=eλ1eλ1+eλ2subscriptsuperscriptsubscript1superscriptsubscript1superscriptsubscript2c_t= e _1e _1+e _2citalic_t = divide start_ARG eitalic_λ1 end_ARG start_ARG eitalic_λ1 + eitalic_λ2 end_ARG with λi∼N⁢(0,1)similar-tosubscript01 _i N(0,1)λitalic_i ∼ N ( 0 , 1 ) 6. PCGrad [52], ct1−ct=1+F⊤⁢R‖gR‖2subscript1subscript1superscriptsubscriptFtopsubscriptRsuperscriptnormsubscriptR2 c_t1-c_t=1+ g_ F g_ R% \|g_ R\|^2divide start_ARG citalic_t end_ARG start_ARG 1 - citalic_t end_ARG = 1 + divide start_ARG italic_gF⊤ italic_gR end_ARG start_ARG ∥ gR ∥2 end_ARG 7. IMTL-G [33], ct=F⊤⁢(F‖F‖−R‖R‖)/(F−R)⊤⁢(F‖F‖−R‖R‖)subscriptsuperscriptsubscriptFtopsubscriptFnormsubscriptFsubscriptRnormsubscriptRsuperscriptsubscriptFsubscriptRtopsubscriptFnormsubscriptFsubscriptRnormsubscriptRc_t= g_ F ( g_ F\| g_ % F\|- g_ R\| g_ R\|)/( g_ F% - g_ R) ( g_ F\| g_ F% \|- g_ R\| g_ R\|)citalic_t = italic_gF⊤ ( divide start_ARG italic_gF end_ARG start_ARG ∥ italic_gF ∥ end_ARG - divide start_ARG italic_gR end_ARG start_ARG ∥ italic_gR ∥ end_ARG ) / ( italic_gF - italic_gR )⊤ ( divide start_ARG italic_gF end_ARG start_ARG ∥ italic_gF ∥ end_ARG - divide start_ARG italic_gR end_ARG start_ARG ∥ italic_gR ∥ end_ARG ) Despite the different designs of ctsubscript\c_t\ citalic_t , we show in Theorem 3 (proof in Appendix G) that all ∗⁢(ct)superscriptsubscript θ^*(\c_t\)italic_θ∗ ( citalic_t ) are Pareto optimal following Lemma 2, including our NGDiff to be introduced in Section 4.2. Theorem 3. For any ctsubscript\c_t\ citalic_t with 0≤ct≤10subscript10≤ c_t≤ 10 ≤ citalic_t ≤ 1 that converges as t→∞→t→∞t → ∞, the model ∗⁢(ct):=limt→∞tassignsuperscriptsubscriptsubscript→subscript θ^*(\c_t\):= _t→∞ θ_titalic_θ∗ ( citalic_t ) := limitalic_t → ∞ italic_θitalic_t in (5) is Pareto optimal. 4 Unlearning with normalized gradient difference While Theorem 3 shows the Pareto optimality of ∗superscript θ^*italic_θ∗ as t→∞→t→∞t → ∞, it does not shed insight on the convergence through intermediate steps tsubscript θ_titalic_θitalic_t. Put differently, although many MTO and unlearning methods are all Pareto optimal upon convergence, they may converge to different Pareto points at different convergence speeds. Therefore, it is important to understand and control the algorithm dynamics to maintain high performance for R throughout the training. Specifically, the dynamics are determined by the choices of UN∈ℝdsubscriptUNsuperscriptℝ g_UN ^ditalic_gUN ∈ blackboard_Rd and ηt∈ℝsubscriptℝ _t ηitalic_t ∈ blackboard_R in Eq. (5). In this section, we propose to use gradient normalization for UNsubscriptUN g_UNitalic_gUN and automatic learning rate for ηtsubscript _tηitalic_t, so as to achieve stable convergence, effective unlearning, high retaining utility, without manually tuning the learning rate. 4.1 Loss landscape of unlearning Applying the Taylor expansion on Eq. (5), we can view the local landscapes of loss LRsubscriptRL_ RLR and LFsubscriptFL_ FLF as quadratic functions, where Lω⁢(t+1)−Lω⁢(t)=−ηt⁢ω⊤⁢UN⁢(ct)+(ηt2/2)⁢UN⊤⁢ω⁢UN+o⁢(ηt2),subscriptsubscript1subscriptsubscriptsubscriptsuperscriptsubscripttopsubscriptUNsubscriptsuperscriptsubscript22superscriptsubscriptUNtopsubscriptsubscriptUNsuperscriptsubscript2L_ω( θ_t+1)-L_ω( θ_t)=- _t g_% ω g_UN(c_t)+( _t^2/2) g_UN^% H_ω g_UN+o( _t^2),Litalic_ω ( italic_θitalic_t + 1 ) - Litalic_ω ( italic_θitalic_t ) = - ηitalic_t italic_gitalic_ω⊤ italic_gUN ( citalic_t ) + ( ηitalic_t2 / 2 ) italic_gUN⊤ Hitalic_ω italic_gUN + o ( ηitalic_t2 ) , (6) where ω is either R or F. Here ω=∂2Lω∂2subscriptsuperscript2subscriptsuperscript2H_ω= ∂^2L_ω∂ θ^2Hitalic_ω = divide start_ARG ∂2 Litalic_ω end_ARG start_ARG ∂ italic_θ2 end_ARG is the Hessian matrix, which empirically gives UN⊤⁢ω⁢UN>0superscriptsubscriptUNtopsubscriptsubscriptUN0 g_UN H_ω g_UN>0italic_gUN⊤ Hitalic_ω italic_gUN > 0 and renders LRsubscriptRL_ RLR and LFsubscriptFL_ FLF locally and directionally convex along the gradients. This allows the existence of a minimizing learning rate to be characterized in Section 4.3. We visualize the loss landscape of Phi-1.5 [28] model on an unlearning benchmark, TOFU dataset [36] in Figure 3 and observe that the quadratic functions in Eq. (6) are well-fitted in most iterations. Figure 3: Loss values of retaining and forgetting sets with different learning rates. Markers are LR⁢(t−η⁢R)subscriptRsubscriptsubscriptRL_ R( θ_t-η g_ R)LR ( italic_θitalic_t - η italic_gR ) and LF⁢(t−η⁢F)subscriptFsubscriptsubscriptFL_ F( θ_t-η g_ F)LF ( italic_θitalic_t - η italic_gF ) estimated by Phi-1.5 on TOFU at step 10. The curves are fitted as quadratic functions. 4.2 Normalized gradient difference In order for LFsubscriptFL_ FLF to increase as well as LRsubscriptRL_ RLR to decrease, we want to construct UNsubscriptUN g_UNitalic_gUN such that R⊤⁢UN⁢(ct)≥0≥F⊤⁢UN⁢(ct).superscriptsubscriptRtopsubscriptUNsubscript0superscriptsubscriptFtopsubscriptUNsubscript g_ R g_UN(c_t)≥ 0≥ % g_ F g_UN(c_t).italic_gR⊤ italic_gUN ( citalic_t ) ≥ 0 ≥ italic_gF⊤ italic_gUN ( citalic_t ) . (7) To satisfy Eq. (7) , we propose a normalized gradient difference method (NGDiff) to dynamically set ct=1/‖R‖1/‖R‖+1/‖F‖⟹NGDiff⁢(R,F):=R‖R‖−F‖F‖.subscript1normsubscriptR1normsubscriptR1normsubscriptF⟹subscriptNGDiffsubscriptRsubscriptFassignsubscriptRnormsubscriptRsubscriptFnormsubscriptFc_t= 1/\| g_ R\|1/\| g_ R\|+1/\| g_% F\| g_ NGDiff( g_ R, % g_ F):= g_ R\| g_ R\|- % g_ F\| g_ F\|.citalic_t = divide start_ARG 1 / ∥ italic_gR ∥ end_ARG start_ARG 1 / ∥ italic_gR ∥ + 1 / ∥ italic_gF ∥ end_ARG ⟹ italic_gNGDiff ( italic_gR , italic_gF ) := divide start_ARG italic_gR end_ARG start_ARG ∥ italic_gR ∥ end_ARG - divide start_ARG italic_gF end_ARG start_ARG ∥ italic_gF ∥ end_ARG . In words, we normalize the retaining and forgetting gradients555We illustrate in Appendix B that NGDiff is critically different and simpler than GradNorm.[10].. We analyze NGDiff as follows. First, we show the condition in Eq. (7) is satisfied at all iterations in the following lemma (proof in Appendix G): Lemma 4. NGDiff⁢(R,F)subscriptNGDiffsubscriptRsubscriptF g_ NGDiff( g_ R, g_ F)italic_gNGDiff ( italic_gR , italic_gF ) satisfies Eq. (7) for any R∈ℝdsubscriptRsuperscriptℝ g_ R ^ditalic_gR ∈ blackboard_Rd and F∈ℝdsubscriptFsuperscriptℝ g_ F ^ditalic_gF ∈ blackboard_Rd. In words, NGDiffsubscriptNGDiff g_ NGDiffitalic_gNGDiff is always positively correlated to RsubscriptR g_ Ritalic_gR and negatively correlated to FsubscriptF g_ Fitalic_gF. In Theorem 5 (proof in Appendix G), we leverage Lemma 4 to claim that the local loss improvement under appropriate learning rate, which will be implemented adaptively in Section 4.3. Theorem 5. Consider t+1=t−η⁢NGDiffsubscript1subscriptsubscriptNGDiff θ_t+1= θ_t-η g_ NGDiffitalic_θitalic_t + 1 = italic_θitalic_t - η italic_gNGDiff. (1) Unless RsubscriptR g_ Ritalic_gR is exactly parallel to FsubscriptF g_ Fitalic_gF, for any sufficiently small learning rate η, there exist two constants ϵR,1=o⁢(η),ϵF,1=o⁢(η)formulae-sequencesubscriptitalic-ϵR1subscriptitalic-ϵF1 _ R,1=o(η), _ F,1=o(η)ϵR , 1 = o ( η ) , ϵF , 1 = o ( η ) such that LR⁢(t+1)−LR⁢(t)<ϵR,1;LF⁢(t+1)−LF⁢(t)>ϵF,1.formulae-sequencesubscriptRsubscript1subscriptRsubscriptsubscriptitalic-ϵR1subscriptFsubscript1subscriptFsubscriptsubscriptitalic-ϵF1 splitL_ R( θ_t+1)-L_ R( θ_t)% &< _ R,1;\\ L_ F( θ_t+1)-L_ F( θ_t)&> _% F,1. splitstart_ROW start_CELL LR ( italic_θitalic_t + 1 ) - LR ( italic_θitalic_t ) end_CELL start_CELL < ϵR , 1 ; end_CELL end_ROW start_ROW start_CELL LF ( italic_θitalic_t + 1 ) - LF ( italic_θitalic_t ) end_CELL start_CELL > ϵF , 1 . end_CELL end_ROW (2) If additionally NGDiff⊤⁢R⁢NGDiff>0superscriptsubscriptNGDifftopsubscriptRsubscriptNGDiff0 g_ NGDiff H_ R g_ NGDiff>0italic_gNGDiff⊤ HR italic_gNGDiff > 0 and NGDiff⊤⁢F⁢NGDiff>0superscriptsubscriptNGDifftopsubscriptFsubscriptNGDiff0 g_ NGDiff H_ F g_ NGDiff>0italic_gNGDiff⊤ HF italic_gNGDiff > 0, then for any learning rate 0<η<2⁢R⊤⁢NGDiffNGDiff⊤⁢R⁢NGDiff02superscriptsubscriptRtopsubscriptNGDiffsuperscriptsubscriptNGDifftopsubscriptRsubscriptNGDiff0<η< 2 g_ R g_ NGDiff g_% NGDiff H_ R g_ NGDiff0 < η < divide start_ARG 2 italic_gR⊤ italic_gNGDiff end_ARG start_ARG italic_gNGDiff⊤ HR italic_gNGDiff end_ARG, there exist two constants ϵR,2=o⁢(η2),ϵF,2=o⁢(η2)formulae-sequencesubscriptitalic-ϵR2superscript2subscriptitalic-ϵF2superscript2 _ R,2=o(η^2), _ F,2=o(η^2)ϵR , 2 = o ( η2 ) , ϵF , 2 = o ( η2 ) such that LR⁢(t+1)−LR⁢(t)<ϵR,2;LF⁢(t+1)−LF⁢(t)>ϵF,2.formulae-sequencesubscriptRsubscript1subscriptRsubscriptsubscriptitalic-ϵR2subscriptFsubscript1subscriptFsubscriptsubscriptitalic-ϵF2 splitL_ R( θ_t+1)-L_ R( θ_t)% &< _ R,2;\\ L_ F( θ_t+1)-L_ F( θ_t)&> _% F,2. splitstart_ROW start_CELL LR ( italic_θitalic_t + 1 ) - LR ( italic_θitalic_t ) end_CELL start_CELL < ϵR , 2 ; end_CELL end_ROW start_ROW start_CELL LF ( italic_θitalic_t + 1 ) - LF ( italic_θitalic_t ) end_CELL start_CELL > ϵF , 2 . end_CELL end_ROW To interpret Theorem 5, we view ϵ≈0italic-ϵ0ε≈ 0ϵ ≈ 0 as η is generally small (say η∼10−4similar-tosuperscript104η 10^-4η ∼ 10- 4 in our experiments), and hence, NGDiff is optimizing on R and F simultaneously. Visually speaking, Lemma 4 constrains NGDiff’s gradient to stay in the green area in Figure 2 unless F∥RconditionalsubscriptFsubscriptR g_ F g_ Ritalic_gF ∥ italic_gR, whereas other methods do not explicitly enforce Eq. (7) and may consequently harm the retaining utility. We end the analysis with the following remark: Remark 4.1. The condition, NGDiff⊤⁢NGDiff>0superscriptsubscriptNGDifftopsubscriptNGDiff0 g_ NGDiff H g_ NGDiff>0italic_gNGDiff⊤ H italic_gNGDiff > 0 in part (2) of Theorem 5, may not always hold in deep learning. However, it empirically holds in most iterations across models and datasets in our experiments (cf., our Figure 3 and Figure 2 in [4]), and we can stablize the training by not updating η when the condition fails. 4.3 Automatic learning rate adaption In order for NGDiff to work as in Theorem 5, the learning rate schedule needs to be carefully selected so that 0<ηt<2⁢R⊤⁢NGDiffNGDiff⊤⁢R⁢NGDiff0subscript2superscriptsubscriptRtopsubscriptNGDiffsuperscriptsubscriptNGDifftopsubscriptRsubscriptNGDiff0< _t< 2 g_ R g_ NGDiff g_% NGDiff H_ R g_ NGDiff0 < ηitalic_t < divide start_ARG 2 italic_gR⊤ italic_gNGDiff end_ARG start_ARG italic_gNGDiff⊤ HR italic_gNGDiff end_ARG at each iteration. In Algorithm 1, we adapt GeN [4] (or AutoLR) to the unlearning setting and dynamically set the learning rates666We note other parameter-free methods such as D-adaptation, Prodigy, and DoG can also set the learning rate automatically. However, these methods need to be tailored for different gradient methods, hence not compatible to NGDiff or the unlearning algorithms in general. We give a detailed explanation in Appendix E. as the minimizer of (6): to locally optimize LRsubscriptRL_ RLR and to monotonically increase LFsubscriptFL_ FLF, we use the following learning rate: ηt∗=R⊤⁢NGDiff/NGDiff⊤⁢R⁢NGDiff.superscriptsubscriptsuperscriptsubscriptRtopsubscriptNGDiffsuperscriptsubscriptNGDifftopsubscriptRsubscriptNGDiff _t^*= g_ R g_ NGDiff% / g_ NGDiff H_ R g_ NGDiff% .ηitalic_t∗ = italic_gR⊤ italic_gNGDiff / italic_gNGDiff⊤ HR italic_gNGDiff . (8) GeN estimates two scalars – the numerator and denominator of Eq. (8) by analyzing the difference of loss values, thus the high-dimensional Hessian matrix RsubscriptRH_ RHR is never instantiated. We devote Appendix C to explain how GeN works and how we have modified GeN for unlearning, such as only forward passing on R but not F in Eq. (8). Remark 4.2. There is a computational overhead to use GeN, as it requires additional forward passes to estimate ηt∗superscriptsubscript _t^*ηitalic_t∗. Nevertheless, we only update the learning rate every 10 iterations so that the overhead is amortized and thus negligible. Algorithm 1 summarizes NGDiff. We note that F,RsubscriptFsubscriptR g_ F, g_ Ritalic_gF , italic_gR can be stochastic gradients. Algorithm 1 Learning-rate-free NGDiff 1:for t=1,2,…12…t=1,2,...t = 1 , 2 , … do 2: —-NGDiff—- 3: Compute LR⁢(t)subscriptRsubscriptL_ R( θ_t)LR ( italic_θitalic_t ) by a forward pass on R 4: Compute R⁢(t)subscriptRsubscript g_ R( θ_t)italic_gR ( italic_θitalic_t ) by backward propagation 5: Compute LF⁢(t)subscriptFsubscriptL_ F( θ_t)LF ( italic_θitalic_t ) by a forward pass on F 6: Compute F⁢(t)subscriptFsubscript g_ F( θ_t)italic_gF ( italic_θitalic_t ) by backward propagation 7: Construct NGDiff=R/‖R‖−F/‖F‖subscriptNGDiffsubscriptRnormsubscriptRsubscriptFnormsubscriptF g_ NGDiff= g_ R/\| g_ R\|- g_% F/\| g_ F\|italic_gNGDiff = italic_gR / ∥ italic_gR ∥ - italic_gF / ∥ italic_gF ∥ 8: —-AutoLR—- 9: if t mod 10==010==010 = = 0: then 10: Compute LR±=LR⁢(t±η⁢)superscriptsubscriptplus-or-minussubscriptRplus-or-minussubscriptL_R^±=L_ R( θ_t±η g)Litalic_R± = LR ( italic_θitalic_t ± η italic_g ) by two forward passes on R 11: Fit the quadratic function QQ in Eq. (6) from (−η,0,η)→(LR−,LR,LR+)→0superscriptsubscriptRsubscriptRsuperscriptsubscriptR(-η,0,η)→(L_ R^-,L_ R,L_ R^+)( - η , 0 , η ) → ( LR- , LR , LR+ ) 12: Derive the optimal learning rate ηt∗:=argminx⁢(x)assignsuperscriptsubscriptsubscriptargmin _t^*:=argmin_xQ(x)ηitalic_t∗ := argminx Q ( x ) and set η=ηt∗superscriptsubscriptη= _t^*η = ηitalic_t∗ 13: Update θt+1=θt−η⁢NGDiffsubscript1subscriptsubscriptNGDiff _t+1= _t-η g_ NGDiffθitalic_t + 1 = θitalic_t - η italic_gNGDiff 5 Experiments 5.1 Setup Dataset We evaluate the empirical performance of our proposed method on the two following datasets (see more dataset details in Section F.1): Table 1: Performance on TOFU dataset (forget10/retain90) with different unlearning methods and models. We define success as the model being able to reduce Verbatim memorization to below 0.1 or maintain at least 70% of the Model utility and the TruthRatio compared to the No-unlearn, with successful cases highlighted in bold. NGDiff achieves success in most cases. Base Model Metric Method No-unlearn GDiff-0.9 GDiff-0.5 GDiff-0.1 NPO LossNorm NGDiff Phi-1.5 Verbmem ↓ ↓ 1.0001.0001.0001.000 0.8050.8050.8050.805 0.027 0.000 0.000 0.4320.4320.4320.432 0.024 Utility ↑ ↑ 1.0001.0001.0001.000 0.9920.9920.9920.992 0.3080.3080.3080.308 0.0000.0000.0000.000 0.0000.0000.0000.000 0.752 0.747 TruthRatio ↑ ↑ 0.3850.3850.3850.385 0.2050.2050.2050.205 0.2160.2160.2160.216 0.2210.2210.2210.221 0.1790.1790.1790.179 0.2140.2140.2140.214 0.353 Falcon-1B Verbmem ↓ ↓ 1.0001.0001.0001.000 0.041 0.001 0.000 0.017 0.055 0.021 Utility ↑ ↑ 1.0001.0001.0001.000 0.434 0.3050.3050.3050.305 0.0000.0000.0000.000 0.1140.1140.1140.114 0.5210.5210.5210.521 0.4280.4280.4280.428 TruthRatio ↑ ↑ 0.4080.4080.4080.408 0.2370.2370.2370.237 0.2440.2440.2440.244 0.2170.2170.2170.217 0.1840.1840.1840.184 0.2520.2520.2520.252 0.354 GPT2-XL Verbmem ↓ ↓ 1.0001.0001.0001.000 0.029 0.001 0.000 0.031 0.022 0.046 Utility ↑ ↑ 0.9990.9990.9990.999 0.3810.3810.3810.381 0.2500.2500.2500.250 0.0000.0000.0000.000 0.1360.1360.1360.136 0.3760.3760.3760.376 0.792 TruthRatio ↑ ↑ 0.4120.4120.4120.412 0.1860.1860.1860.186 0.2780.2780.2780.278 0.1330.1330.1330.133 0.1790.1790.1790.179 0.1960.1960.1960.196 0.399 Llama2-7B Verbmem ↓ ↓ 1.0001.0001.0001.000 0.8100.8100.8100.810 0.011 0.000 0.7090.7090.7090.709 0.010 0.002 Utility ↑ ↑ 1.0001.0001.0001.000 0.851 0.3240.3240.3240.324 0.0000.0000.0000.000 0.6820.6820.6820.682 0.2640.2640.2640.264 0.724 TruthRatio ↑ ↑ 0.4900.4900.4900.490 0.3400.3400.3400.340 0.364 0.1610.1610.1610.161 0.3290.3290.3290.329 0.3290.3290.3290.329 0.3340.3340.3340.334 Mistral-7B Verbmem ↓ ↓ 1.0001.0001.0001.000 1.0001.0001.0001.000 0.9450.9450.9450.945 0.4100.4100.4100.410 0.3850.3850.3850.385 0.2590.2590.2590.259 0.009 Utility ↑ ↑ 1.0001.0001.0001.000 0.999 0.944 0.5170.5170.5170.517 0.3410.3410.3410.341 0.925 0.996 TruthRatio ↑ ↑ 0.3440.3440.3440.344 0.345 0.366 0.374 0.364 0.358 0.379 Task of Fictitious Unlearning (TOFU) [36]. TOFU consists of 20 question-answer pairs based on fictitious author biographies generated by GPT-4 [1]. In our experiments, we use the forget10 (10% of the full training set) as the forgetting set and retain90 (90% of the full training set) as the retaining set. MUSE-NEWS [43]. This dataset consists of BBC news articles [29] published since August 2023. We use its train split to finetune a target model, and then the raw set, which includes both the forgetting and retaining data, for the target model unlearning. Finally, the verbmem and knowmem splits are used to evaluate the unlearned model’s performance. Unlearning methods We compare NGDiff with 4 baselines. The first baseline method is the target model without any unlearning, while the remaining three are the state-of-the-art unlearning methods. No-unlearn. We fine-tune the base model on the full training data. Subsequent unlearning approaches are then applied on No-unlearn. Gradient Difference (GDiff) [31]. GDiff (see Sec. 3.2) applies static linear scalarization with c=0.50.5c=0.5c = 0.5 in MTO. For a thorough comparison, we also include the extended GDiff method, with c=0.10.1c=0.1c = 0.1 or c=0.90.9c=0.9c = 0.9. Loss Normalization (LossNorm). As discussed in Section 3.2, this approach computes and normalizes the forget loss and retain loss separately, with the overall loss being LR/|LR|−LF/|LF|subscriptRsubscriptRsubscriptFsubscriptFL_ R/|L_ R|-L_ F/|L_ F|LR / | LR | - LF / | LF |. Negative Preference Optimization (NPO) [55]. NPO uses preference optimization [38] with the loss: LNPO,β⁢()=subscriptNPOabsentL_NPO,β( θ)=LNPO , β ( italic_θ ) = −2β⁢F⁢[log⁡σ⁢(−β⁢log⁡f⁢(S,w)fNo-unlearn⁢(S,w))],2subscriptFdelimited-[]subscriptNo-unlearn- 2βE_ F [ σ (-β % f(S,w)f_No-unlearn(S,w) ) ],- divide start_ARG 2 end_ARG start_ARG β end_ARG blackboard_EF [ log σ ( - β log divide start_ARG f ( S , w ) end_ARG start_ARG fNo-unlearn ( S , w ) end_ARG ) ] , (9) where S is randomly sampled from F, β>00β>0β > 0 is the inverse temperature, f is the unlearned model, and fNo-unlearnsubscriptNo-unlearnf_No-unlearnfNo-unlearn is the model before unlearning. Foundation Models We test multiple LLMs: LLaMA2-7B [46], Phi-1.5 [28], Falcon-1B [40], GPT2-XL [41] and Mistral-7B [24]. They are pre-trained and then fine-tuned on datasets in Section 5.1, with AdamW optimizer and are carefully tuned (Appendix F). Base Model Metric Method No-unlearn GDiff-0.9 GDiff-0.5 GDiff-0.1 NPO LossNorm NGDiff Llama2-7B Verbmem ↓ ↓ 0.5610.5610.5610.561 0.5550.5550.5550.555 0.043 0.004 0.000 0.3880.3880.3880.388 0.036 Knowmem ↓ ↓ 0.7550.7550.7550.755 0.7170.7170.7170.717 0.287 0.000 0.000 0.514 0.455 Utility ↑ ↑ 0.6460.6460.6460.646 0.641 0.2750.2750.2750.275 0.0000.0000.0000.000 0.0000.0000.0000.000 0.506 0.556 Mistral-7B Verbmem ↓ ↓ 0.5780.5780.5780.578 0.1770.1770.1770.177 0.000 0.000 0.1130.1130.1130.113 0.1960.1960.1960.196 0.098 Knowmem ↓ ↓ 0.4160.4160.4160.416 0.257 0.000 0.000 0.3430.3430.3430.343 0.2930.2930.2930.293 0.165 Utility ↑ ↑ 0.4110.4110.4110.411 0.339 0.0000.0000.0000.000 0.0000.0000.0000.000 0.316 0.343 0.354 Table 2: Results on the MUSE-NEWS dataset. We boldface the entries where unlearning successfully reduces Verbatim memorization to below 0.1, reduces Knowledge memorization to less than 70% of No-Unlearn, or maintains at least 70% of the Utility compared to No-Unlearn. With the exception of NGDiff, most unlearning approaches exhibit a significant trade-off between forgetting and utility. 5.2 Evaluation Metrics Following the existing work [43], we evaluate the unlearning performance based on model’s output quality. We expect a good performance should satisfy the following requirements: No verbatim memorization. After the unlearning, the model should no longer remember any verbatim copies of the texts in the forgetting data. To evaluate this, we prompt the model with the first k tokens in F and compare the model’s continuation outputs with the ground truth continuations. We use ROUGE-L recall scores for this comparison, where a lower score is better for unlearning. No knowledge memorization. After the unlearning, the model should not only forget verbatim texts, but also the knowledge in the forgetting set. For the MUSE-NEWS dataset, we evaluate knowledge memorization using the KnowmemFF_ Fstart_FLOATSUBSCRIPT F end_FLOATSUBSCRIPT split, which consists of generated question-answer pairs based on the forgetting data. Similar to verbatim memorization, we use ROUGE-L recall scores. Maintained model utility. An effective unlearning method must maintain the model’s performance on the retaining set. We prompt the model with the question from R and compare the generated answer to the ground truth. We use ROUGE-L recall scores for these comparisons. Additionally, we evaluate the model using the Truth Ratio metric. We use the Retain10-perturbed split from TOFU, which consists of five perturbed answers created by modifying the facts in each original answer from R. The Truth Ratio metric computes how likely the model generates a correct answer versus an incorrect one, where a higher value is better. Method TOFU (without → with AutoLR) Verbmem ↓ ↓ Utility ↑ ↑ TruthRatio ↑ ↑ No-unlearn 1.001.001.001.00 1.001.001.001.00 0.390.390.390.39 GDiff c=0.9 0.81→0.20→0.810.200.81→ 0.200.81 → 0.20 0.99→0.42→0.990.420.99→ 0.420.99 → 0.42 0.21→0.31→0.210.310.21→ 0.310.21 → 0.31 GDiff c=0.5 0.03→0.00→0.030.000.03→ 0.000.03 → 0.00 0.31→0.03→0.310.030.31→ 0.030.31 → 0.03 0.22→0.30→0.220.300.22→ 0.300.22 → 0.30 GDiff c=0.1 0.00→0.00→0.000.000.00→ 0.000.00 → 0.00 0.00→0.00→0.000.000.00→ 0.000.00 → 0.00 0.22→0.23→0.220.230.22→ 0.230.22 → 0.23 NPO 0.00→0.00→0.000.000.00→ 0.000.00 → 0.00 0.00→0.00→0.000.000.00→ 0.000.00 → 0.00 0.18→0.22→0.180.220.18→ 0.220.18 → 0.22 LossNorm 0.43→0.23→0.430.230.43→ 0.230.43 → 0.23 0.75→0.73→0.750.730.75→ 0.730.75 → 0.73 0.21→0.34→0.210.340.21→ 0.340.21 → 0.34 NGDiff 0.02→0.01→0.020.010.02→ 0.010.02 → 0.01 0.61→0.75→0.610.750.61→ 0.750.61 → 0.75 0.29→0.35→0.290.350.29→ 0.350.29 → 0.35 Table 3: Influence of AutoLR with different unlearning methods on the Phi-1.5 model. AutoLR improves the TruthRatio and reduces Verbmem across all methods. W/ or w/o AutoLR, NGDiff outperforms other baselines. 5.3 Main Results The results for Verbatim memorization (Verbmem), Model utility (Utility), TruthRatio, and Knowledge memorization (Knowmem) using different unlearning methods are presented in Table 1, 2 as well as 6 in Appendix. We evaluate these metrics using TOFU and MUSE-NEWS across LLMs. In summary, our NGDiff consistently achieves the superior performance across all models on both datasets. In stark contrast, the baseline unlearning methods (1) either effectively forget R by reducing Verbmem and Knowmem but fail maintain the Utility and TruthRatio, such as GDiff with c≤0.50.5c≤ 0.5c ≤ 0.5, NPO; (2) or cannot unlearn F on Phi-1.5 and Mistral-7B, such as LossNorm and GDiff with c=0.90.9c=0.9c = 0.9. We highlight that the effectiveness of these unlearning methods are highly model-dependent and dataset-dependent, unlike NGDiff. Figure 4: Comparison of unlearning methods on TOFU. The figures show the ROUGE scores and loss terms during unlearning process with different methods, which includes GDiff, LossNorm, and NGDiff. We observe that NGDiff effectively unlearns the forgetting data while maintaining the performance on the retaining data. Figure 5: Comparison between AutoLR and different learning rates on NGDiff. The figures show the ROUGE scores and loss values during the unlearning process on TOFU dataset using Phi-1.5 model. We observe that AutoLR outperforms the static learning rates with better model utility and more stable convergence. For the TOFU dataset, we observe that some unlearning methods fail to unlearn the forget data effectively. For example, GDiff-0.9 and LossNorm do not unlearn effectively when applied to Phi-1.5, Llama2-7B and Mistral-7B. In fact, GDiff-0.9 has 80%∼100%similar-topercent80percent10080\% 100\%80 % ∼ 100 % Verbmem and LossNorm has >40%absentpercent40>40\%> 40 % Verbmem on Phi-1.5. However, they are effective on Falcon-1B and GPT2-XL, even though these models have similar sizes (≈1absent1≈ 1≈ 1B parameters) to Phi-1.5. On the other hand, some methods fail to preserve the model utility after unlearning. For example, GDiff-0.1 has close to 0 Utility on Phi-1.5, Falcon-1B, GPT2-XL and Llama2-7B; similarly, NPO also experiences a significant drop in Utility on Phi-1.5 model, Falcon-1B and GPT2-XL, but not so on Llama2-7B. In contrast, our NGDiff remains effective in unlearning F and maintaining R across the models. In addition, NGDiff achieves the best TruthRatio on all models except Llama2-7B (which is still on par with the best), indicating that the model’s answers remain factually accurate for questions in the retaining data. For the MUSE-NEWS dataset, NGDiff also outperforms the baseline methods on Llama2-7B and Mistral-7B models by achieving a lower Verbmem and a higher Utility. The Knowmem results indicate that NGDiff not only unlearns the verbatim copies of the forgetting texts, but also successfully removes the associated knowledge. While the model capacities of Phi-1.5 and Falcon-1B are smaller, limiting their ability to learn knowledge effectively after fine-tuning on the full dataset, as shown in Table 6, NGDiff still performs well. To further illustrate the performance of our proposed method during the training, in addition to the last iterate results, we plot the ROUGE scores and loss terms during the unlearning process in Figure 4. We apply the extended GDiff, LossNorm, and NGDiff methods, to the Phi-1.5 model using the TOFU dataset. While GDiff with c=0.50.5c=0.5c = 0.5 and c=0.70.7c=0.7c = 0.7, and NGDiff are effective in unlearning, only NGDiff preserve the model utility above 75%percent7575\%75 % ROUGE score. A closer look at the second and the fourth plots of Figure 4 shows that NGDiff exhibits the fastest and most stable convergence on F while maintaining a low retaining loss ≤0.1absent0.1≤ 0.1≤ 0.1. 5.4 Ablation Study Effectiveness of NGDiff. In our experiments, we utilize the automatic learning rate scheduler (AutoLR) for NGDiff method. To investigate the impact of NGDiff alone, we compare all methods with or without AutoLR in Table 3. With AutoLR or not (where we use manually tuned learning rates), NGDiff, GDiff (c=0.10.1c=0.1c = 0.1 or 0.50.50.50.5) and NPO can effectively unlearn in terms of Verbmem. However, among these four methods, NGDiff uniquely retains a reasonable Utility between 60∼75%similar-to60percent7560 75\%60 ∼ 75 %, while other methods retains only 0∼30%similar-to0percent300 30\%0 ∼ 30 % Utility. A similar pattern is observed in terms of TruthRatio as well. Overall, NGDiff significantly outperforms other baseline methods with or without AutoLR. Impact of automatic learning rate. To evaluate the impact of AutoLR scheduler, we see in Table 3 all methods exhibit an increase in the TruthRatio metric and a decrease in Verbmem, though with some loss in the Utility. For instance, LossNorm benefits significantly from AutoLR with ≈20%absentpercent20≈ 20\%≈ 20 % decrease in Verbmem, and NGDiff increases its retaining Utility and TruthRatio by >22%absentpercent22>22\%> 22 %. We specifically demonstrate the impact of AutoLR on NGDiff in Figure 5. Without AutoLR, the model’s performance is highly sensitive to the static learning rates: when η=10−5superscript105η=10^-5η = 10- 5, the model fails to unlearn F as indicated by the low loss and high ROUGE score; in contrast, when η=10−4superscript104η=10^-4η = 10- 4, there is a significant drop in ROUGE score on the retain data, falling from 100% to around 50%. However, with the AutoLR scheduler, we observe a steady reduction in the Verbmem (with the ROUGE forget close to 0 at convergence) while maintaining high utility (the ROUGE retain is 0.747, which is 19.5% higher than the best results without AutoLR). 6 Conclusion and Discussion We formulated the machine unlearning problem as a two-task optimization problem and proposed a novel unlearning method NGDiff based on normalized gradient difference and automatic learning rate adaption. By leveraging insights from multi-task optimization, NGDiff empirically improves forgetting quality while maintaining utility. We hope this paper helps establish a connection between LLM unlearning and multi-task optimization, and inspires further advancements in this field. Limitations Like other machine learning approaches in NLP, while our goal is to remove the influence of specific documents from LLMs, complete removal cannot always be guaranteed. Therefore, caution should be exercised when applying the proposed unlearning techniques in practical applications as unlearned LLMs can still potentially generate harmful or undesired outputs. There are several technical alternatives that we did not explore in this paper due to its scope and limited resources. For example, other learning-rate-free methods could potentially be adapted as alternatives to the GeN approach used in this work. Additionally, other multi-task optimization methods could be applied to machine unlearning. However, scaling these approaches to the level of LLMs could be challenging, and are left as future work. Finally, we mainly examined NGDiff’s effectiveness on LLM unlearning in this paper with two benchmark datasets, TOFU and MUSE. To show its generalizability, we provide an additional example to apply the algorithm to computer vision tasks (see Appendix D). However, it would be desirable to test NGDiff on other modalities beyond NLP and CV applications. Acknowledgments We would like to thank Shankar Ananthakrishnan, Fabian Triefenbach and Jianhua Lu from Amazon AGI Foundations team for providing feedback on this paper and supporting this work. References [1] Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. Gpt-4 technical report. arXiv preprint arXiv:2303.08774, 2023. [2] 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), pages 141–159. IEEE, 2021. [3] Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004. [4] Zhiqi Bu and Shiyun Xu. Gradient descent with generalized newton’s method. In The Thirteenth International Conference on Learning Representations, 2024. [5] Nicholas Carlini, Florian Tramer, Eric Wallace, Matthew Jagielski, Ariel Herbert-Voss, 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), pages 2633–2650, 2021. [6] Jiaao Chen and Diyi Yang. Unlearn what you want to forget: Efficient unlearning for LLMs. In Houda Bouamor, Juan Pino, and Kalika Bali, editors, Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pages 12041–12052, Singapore, December 2023. Association for Computational Linguistics. [7] Kongyang Chen, Zixin Wang, Bing Mi, Waixi Liu, Shaowei Wang, Xiaojun Ren, and Jiaxing Shen. Machine unlearning in large language models. arXiv preprint arXiv:2404.16841, 2024. [8] Liang Chen, Shuming Ma, Dongdong Zhang, Furu Wei, and Baobao Chang. On the pareto front of multilingual neural machine translation. ArXiv, abs/2304.03216, 2023. [9] Shijie Chen, Yu Zhang, and Qiang Yang. Multi-task learning in natural language processing: An overview. ACM Computing Surveys, 2021. [10] Zhao Chen, Vijay Badrinarayanan, Chen-Yu Lee, and Andrew Rabinovich. Gradnorm: Gradient normalization for adaptive loss balancing in deep multitask networks. In International conference on machine learning, pages 794–803. PMLR, 2018. [11] Zhao Chen, Jiquan Ngiam, Yanping Huang, Thang Luong, Henrik Kretzschmar, Yuning Chai, and Dragomir Anguelov. Just pick a sign: Optimizing deep multitask models with gradient sign dropout, 2020. [12] Nicola De Cao, Wilker Aziz, and Ivan Titov. Editing factual knowledge in language models. In Marie-Francine Moens, Xuanjing Huang, Lucia Specia, and Scott Wen-tau Yih, editors, Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pages 6491–6506, Online and Punta Cana, Dominican Republic, November 2021. Association for Computational Linguistics. [13] Aaron Defazio and Konstantin Mishchenko. Learning-rate-free learning by d-adaptation, 2023. [14] A. P. Dempster, N. M. Laird, and D. B. Rubin. Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society: Series B, 39:1–38, 1977. [15] Jean-Antoine Désidéri. Multiple-gradient descent algorithm (mgda) for multiobjective optimization. Comptes Rendus Mathematique, 350(5-6):313–318, 2012. [16] Ronen Eldan and Mark Russinovich. Who’s harry potter? approximate unlearning in llms. 2023. [17] Varun Gupta, Christopher Jung, Seth Neel, Aaron Roth, Saeed Sharifi-Malvajerdi, and Chris Waites. Adaptive machine unlearning. Advances in Neural Information Processing Systems, 34:16319–16330, 2021. [18] Xudong Han, Timothy Baldwin, and Trevor Cohn. Fair enough: Standardizing evaluation and model selection for fairness research in NLP. In Andreas Vlachos and Isabelle Augenstein, editors, Proceedings of the 17th Conference of the European Chapter of the Association for Computational Linguistics, pages 297–312, Dubrovnik, Croatia, May 2023. Association for Computational Linguistics. [19] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition, 2015. [20] Edward J Hu, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, Weizhu Chen, et al. Lora: Low-rank adaptation of large language models. In International Conference on Learning Representations, 2021. [21] Maor Ivgi, Oliver Hinder, and Yair Carmon. Dog is sgd’s best friend: A parameter-free dynamic step size schedule, 2023. [22] Joel Jang, Dongkeun Yoon, Sohee Yang, Sungmin Cha, Moontae Lee, Lajanugen Logeswaran, and Minjoon Seo. Knowledge unlearning for mitigating privacy risks in language models. In Anna Rogers, Jordan Boyd-Graber, and Naoaki Okazaki, editors, Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 14389–14408, Toronto, Canada, July 2023. Association for Computational Linguistics. [23] Adrián Javaloy and Isabel Valera. Rotograd: Gradient homogenization in multitask learning, 2022. [24] Albert Q Jiang, Alexandre Sablayrolles, Arthur Mensch, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Florian Bressand, Gianna Lengyel, Guillaume Lample, Lucile Saulnier, et al. Mistral 7b. arXiv preprint arXiv:2310.06825, 2023. [25] Ahmed Khaled, Konstantin Mishchenko, and Chi Jin. Dowg unleashed: An efficient universal parameter-free gradient descent method, 2024. [26] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009. [27] Yige Li, Hanxun Huang, Yunhan Zhao, Xingjun Ma, and Jun Sun. Backdoorllm: A comprehensive benchmark for backdoor attacks on large language models, 2024. [28] Yuanzhi Li, Sébastien Bubeck, Ronen Eldan, Allie Del Giorno, Suriya Gunasekar, and Yin Tat Lee. Textbooks are all you need i: phi-1.5 technical report. arXiv preprint arXiv:2309.05463, 2023. [29] Yucheng Li, Frank Geurin, and Chenghua Lin. Avoiding data contamination in language model evaluation: Dynamic test construction with latest materials. arXiv preprint arXiv:2312.12343, 2023. [30] Baijiong Lin, Feiyang Ye, Yu Zhang, and Ivor Tsang. Reasonable effectiveness of random weighting: A litmus test for multi-task learning. Transactions on Machine Learning Research, 2021. [31] Bo Liu, Qiang Liu, and Peter Stone. Continual learning and private unlearning. In Conference on Lifelong Learning Agents, pages 243–254. PMLR, 2022. [32] Bo Liu, Xingchao Liu, Xiaojie Jin, Peter Stone, and Qiang Liu. Conflict-averse gradient descent for multi-task learning, 2024. [33] Liyang Liu, Yi Li, Zhanghui Kuang, J Xue, Yimin Chen, Wenming Yang, Qingmin Liao, and Wayne Zhang. Towards impartial multi-task learning. In iclr, 2021. [34] Sijia Liu, Yuanshun Yao, Jinghan Jia, Stephen Casper, Nathalie Baracaldo, Peter Hase, Xiaojun Xu, Yuguang Yao, Hang Li, Kush R Varshney, et al. Rethinking machine unlearning for large language models. arXiv preprint arXiv:2402.08787, 2024. [35] Sijia Liu, Yuanshun Yao, Jinghan Jia, Stephen Casper, Nathalie Baracaldo, Peter Hase, Yuguang Yao, Chris Yuhao Liu, Xiaojun Xu, Hang Li, Kush R. Varshney, Mohit Bansal, Sanmi Koyejo, and Yang Liu. Rethinking machine unlearning for large language models, 2024. [36] Pratyush Maini, Zhili Feng, Avi Schwarzschild, Zachary C Lipton, and J Zico Kolter. Tofu: A task of fictitious unlearning for llms. arXiv preprint arXiv:2401.06121, 2024. [37] Konstantin Mishchenko and Aaron Defazio. Prodigy: An expeditiously adaptive parameter-free learner, 2024. [38] Long Ouyang, Jeff Wu, Xu Jiang, Diogo Almeida, Carroll L. Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, John Schulman, Jacob Hilton, Fraser Kelton, Luke Miller, Maddie Simens, Amanda Askell, Peter Welinder, Paul Christiano, Jan Leike, and Ryan Lowe. Training language models to follow instructions with human feedback, 2022. [39] Martin Pawelczyk, Seth Neel, and Himabindu Lakkaraju. In-context unlearning: Language models as few shot unlearners. In ICML, 2024. [40] Guilherme Penedo, Quentin Malartic, Daniel Hesslow, Ruxandra Cojocaru, Alessandro Cappelli, Hamza Alobeidli, Baptiste Pannier, Ebtesam Almazrouei, and Julien Launay. The refinedweb dataset for falcon llm: Outperforming curated corpora with web data, and web data only, 2023. [41] Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. Language models are unsupervised multitask learners. OpenAI blog, 1(8):9, 2019. [42] Rajhans Samdani, Ming-Wei Chang, and Dan Roth. Unified expectation maximization. In Eric Fosler-Lussier, Ellen Riloff, and Srinivas Bangalore, editors, Proceedings of the 2012 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 688–698, Montréal, Canada, June 2012. Association for Computational Linguistics. [43] 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. arXiv preprint arXiv:2407.06460, 2024. [44] Nianwen Si, Hao Zhang, Heyu Chang, Wenlin Zhang, Dan Qu, and Weiqiang Zhang. Knowledge unlearning for llms: Tasks, methods, and challenges, 2023. [45] The New York Times. Exhibit j, 2023. [46] Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. Llama 2: Open foundation and fine-tuned chat models. arXiv preprint arXiv:2307.09288, 2023. [47] Enayat Ullah, Tung Mai, Anup Rao, Ryan A Rossi, and Raman Arora. Machine unlearning via algorithmic stability. In Conference on Learning Theory, pages 4126–4142. PMLR, 2021. [48] Eric Wallace, Tony Zhao, Shi Feng, and Sameer Singh. Concealed data poisoning attacks on NLP models. In Kristina Toutanova, Anna Rumshisky, Luke Zettlemoyer, Dilek Hakkani-Tur, Iz Beltagy, Steven Bethard, Ryan Cotterell, Tanmoy Chakraborty, and Yichao Zhou, editors, Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 139–150, Online, June 2021. Association for Computational Linguistics. [49] Zirui Wang, Yulia Tsvetkov, Orhan Firat, and Yuan Cao. Gradient vaccine: Investigating and improving multi-task optimization in massively multilingual models, 2020. [50] Xiaobao Wu, Liangming Pan, William Yang Wang, and Anh Tuan Luu. Akew: Assessing knowledge editing in the wild, 2024. [51] Derrick Xin, Behrooz Ghorbani, Justin Gilmer, Ankush Garg, and Orhan Firat. Do current multi-task optimization methods in deep learning even help? Advances in neural information processing systems, 35:13597–13609, 2022. [52] Tianhe Yu, Saurabh Kumar, Abhishek Gupta, Sergey Levine, Karol Hausman, and Chelsea Finn. Gradient surgery for multi-task learning. Advances in Neural Information Processing Systems, 33:5824–5836, 2020. [53] Alan L Yuille and Anand Rangarajan. The concave-convex procedure (cccp). In T. Dietterich, S. Becker, and Z. Ghahramani, editors, Advances in Neural Information Processing Systems, volume 14. MIT Press, 2001. [54] Dawen Zhang, Pamela Finckenberg-Broman, Thong Hoang, Shidong Pan, Zhenchang Xing, Mark Staples, and Xiwei Xu. Right to be forgotten in the era of large language models: Implications, challenges, and solutions, 2024. [55] Ruiqi Zhang, Licong Lin, Yu Bai, and Song Mei. Negative preference optimization: From catastrophic collapse to effective unlearning. arXiv preprint arXiv:2404.05868, 2024. [56] Zhihan Zhang, Wenhao Yu, Mengxia Yu, Zhichun Guo, and Meng Jiang. A survey of multi-task learning in natural language processing: Regarding task relatedness and training methods. In Andreas Vlachos and Isabelle Augenstein, editors, Proceedings of the 17th Conference of the European Chapter of the Association for Computational Linguistics, pages 943–956, Dubrovnik, Croatia, May 2023. Association for Computational Linguistics. Appendix A Preliminary evidence In our preliminary experiments, we observe two key issues preventing the standard methods from being practically applied. First, balancing retaining and forgetting losses is difficult. In Figure 1, we observe a trade-off between the performance on R and F, where some methods fail to unlearn F (points in the upper-right corner of the left figure), and some do not maintain utility in R (points in the bottom-left corner of the left figure). The blue dotted line in Figure 1 further illustrates the trade-off in GDiff by sweeping a hyper-parameter c∈[0,1],01c∈[0,1],c ∈ [ 0 , 1 ] , which is used to balance the losses on the forgetting and retaining data (see Eq. (3)). Picking an appropriate c to balance the two terms is often challenging. Secondly, the optimization methods for unlearning are usually sensitive to the learning rate. As illustrated in Figure 6, even for the same algorithm, various learning rates lead to substantial changes in the ROUGE scores and loss values, making the unlearning methods unstable and difficult to use in practice. Figure 6: ROUGE scores and loss values during unlearning with vanilla GDiff (equally weighted), under different learning rates to which the unlearning performance is highly sensitive. Appendix B Comparing NGDiff with GradNorm Algorithm 2 NGDiff 1:for t=1,2,…12…t=1,2,...t = 1 , 2 , … do 2: Compute retaining loss LR⁢(t)subscriptRsubscriptL_ R( θ_t)LR ( italic_θitalic_t ) by one forward pass 3: Compute retaining gradient R⁢(t)=∇LRsubscriptRsubscriptsubscript∇subscriptR g_ R( θ_t)= _ θL_ Ritalic_gR ( italic_θitalic_t ) = ∇italic_θ LR 4: Compute forgetting loss LF⁢(t)subscriptFsubscriptL_ F( θ_t)LF ( italic_θitalic_t ) by one forward pass 5: Compute forgetting gradient F⁢(t)=∇LFsubscriptFsubscriptsubscript∇subscriptF g_ F( θ_t)= _ θL_ Fitalic_gF ( italic_θitalic_t ) = ∇italic_θ LF 6: Construct unlearning gradient NGDiff=R/‖R‖−F/‖F‖subscriptNGDiffsubscriptRnormsubscriptRsubscriptFnormsubscriptF g_ NGDiff= g_ R/\| g_ R\|- g_% F/\| g_ F\|italic_gNGDiff = italic_gR / ∥ italic_gR ∥ - italic_gF / ∥ italic_gF ∥ 7: Update t+1=t−η⁢NGDiffsubscript1subscriptsubscriptNGDiff θ_t+1= θ_t-η g_ NGDiffitalic_θitalic_t + 1 = italic_θitalic_t - η italic_gNGDiff Algorithm 3 GradNorm for two-task 1:Initialize the scalaring coefficients wR⁢(0)=1subscriptRsubscript01w_ R( θ_0)=1wR ( italic_θ0 ) = 1 and wF⁢(0)=1subscriptFsubscript01w_ F( θ_0)=1wF ( italic_θ0 ) = 1 2:Pick value for α>00α>0α > 0 and pick the weights LSsubscriptLS θ_LSitalic_θLS (the last shared layer of tsubscript θ_titalic_θitalic_t) 3:for t=1,2,…12…t=1,2,...t = 1 , 2 , … do 4: Compute retaining loss LR⁢(t)subscriptRsubscriptL_ R( θ_t)LR ( italic_θitalic_t ) by one forward pass 5: Compute retaining gradient R⁢(LS)=∇LSLRsubscriptRsubscriptLSsubscript∇subscriptLSsubscriptR g_ R( θ_LS)= _ θ_LS% L_ Ritalic_gR ( italic_θLS ) = ∇italic_θ start_POSTSUBSCRIPT LS end_POSTSUBSCRIPT LR 6: Compute forgetting loss LF⁢(t)subscriptFsubscriptL_ F( θ_t)LF ( italic_θitalic_t ) by one forward pass 7: Compute forgetting gradient F⁢(LS)=∇LSLFsubscriptFsubscriptLSsubscript∇subscriptLSsubscriptF g_ F( θ_LS)= _ θ_LS% L_ Fitalic_gF ( italic_θLS ) = ∇italic_θ start_POSTSUBSCRIPT LS end_POSTSUBSCRIPT LF 8: Compute loss L⁢(t)=wR⁢(t)⁢LR⁢(t)+wF⁢(t)⁢LF⁢(t)subscriptsubscriptRsubscriptsubscriptRsubscriptsubscriptFsubscriptsubscriptFsubscriptL( θ_t)=w_ R( θ_t)L_ R( θ_% t)+w_ F( θ_t)L_ F( θ_t)L ( italic_θitalic_t ) = wR ( italic_θitalic_t ) LR ( italic_θitalic_t ) + wF ( italic_θitalic_t ) LF ( italic_θitalic_t ) 9: Compute ¯⁢(LS)¯subscriptLS g( θ_LS)over¯ start_ARG italic_g end_ARG ( italic_θLS ) by averaging RsubscriptR g_ Ritalic_gR and FsubscriptF g_ Fitalic_gF 10: Compute GradNorm loss LG⁢N⁢(t)=|R−¯×[rR⁢(t)]α|1+|F−¯×[rF⁢(t)]α|1subscriptsubscriptsubscriptsubscriptR¯superscriptdelimited-[]subscriptR1subscriptsubscriptF¯superscriptdelimited-[]subscriptF1L_GN( θ_t)=| g_ R- g×[r_ R% (t)]^α|_1+| g_ F- g×[r_ F(t)]^% α|_1Litalic_G N ( italic_θitalic_t ) = | italic_gR - over¯ start_ARG italic_g end_ARG × [ rR ( t ) ]α |1 + | italic_gF - over¯ start_ARG italic_g end_ARG × [ rF ( t ) ]α |1 11: Compute GradNorm gradients ∇wRLG⁢Nsubscript∇subscriptRsubscript _w_ RL_GN∇w start_POSTSUBSCRIPT R end_POSTSUBSCRIPT Litalic_G N and ∇wFLG⁢N∈Rsubscript∇subscriptFsubscriptR _w_ FL_GN∈ R∇w start_POSTSUBSCRIPT F end_POSTSUBSCRIPT Litalic_G N ∈ R 12: Compute the full gradient ∇tLsubscript∇subscript _ θ_tL∇italic_θ start_POSTSUBSCRIPT t end_POSTSUBSCRIPT L 13: Update wR⁢(t)→wR⁢(t+1)→subscriptRsubscriptsubscriptRsubscript1w_ R( θ_t)→ w_ R( θ_t+1)wR ( italic_θitalic_t ) → wR ( italic_θitalic_t + 1 ) and wF⁢(t)→wF⁢(t+1)→subscriptFsubscriptsubscriptFsubscript1w_ F( θ_t)→ w_ F( θ_t+1)wF ( italic_θitalic_t ) → wF ( italic_θitalic_t + 1 ) using ∇wRLG⁢Nsubscript∇subscriptRsubscript _w_ RL_GN∇w start_POSTSUBSCRIPT R end_POSTSUBSCRIPT Litalic_G N and ∇wFLG⁢Nsubscript∇subscriptFsubscript _w_ FL_GN∇w start_POSTSUBSCRIPT F end_POSTSUBSCRIPT Litalic_G N 14: Update t+1=t−η⁢∇tLsubscript1subscriptsubscript∇subscript θ_t+1= θ_t-η _ θ_tLitalic_θitalic_t + 1 = italic_θitalic_t - η ∇italic_θ start_POSTSUBSCRIPT t end_POSTSUBSCRIPT L 15: Renormalize wR⁢(t+1)subscriptRsubscript1w_ R( θ_t+1)wR ( italic_θitalic_t + 1 ) and wF⁢(t+1)subscriptFsubscript1w_ F( θ_t+1)wF ( italic_θitalic_t + 1 ) so that wR⁢(t+1)+wF⁢(t+1)=2subscriptRsubscript1subscriptFsubscript12w_ R( θ_t+1)+w_ F( θ_t+1)=2wR ( italic_θitalic_t + 1 ) + wF ( italic_θitalic_t + 1 ) = 2 We compare the GradNorm algorithm [10] with our proposed method, NGDiff. We highlight some steps of GradNorm in red to indicate the differences than NGDiff: • NGDiff sets the scalaring coefficient as 1/‖R‖1normsubscriptR1/\| g_ R\|1 / ∥ italic_gR ∥ and 1/‖F‖1normsubscriptF1/\| g_ F\|1 / ∥ italic_gF ∥, while GradNorm uses gradient descent to learn these coefficients as wRsubscriptRw_ RwR and wFsubscriptFw_ FwF. • NGDiff is model-agnostic while GradNorm contains specific designs for multi-task architecture. In unlearning, there are 2 data splits (i.e., F and R) and each data split defines one task. Hence all model parameters are shared. However, in the original form of GradNorm, there is 1 data split on which multiple tasks are defined (can be more than 2). Hence the model parameters are partitioned into [shared layers, task 1 specific layers, task 2 specific layers]. • NGDiff computes the full per-task gradients whereas GradNorm only computes the last shared layer’s gradients. • NGDiff requires 2 back-propagation at each iteration but GradNorm requires 3 (2 for per-task gradients, 1 for ∇Lsubscript∇ _ θL∇italic_θ L), which may translate to more training time for large models. • GradNorm introduces additional hyperparameters that can be difficult and costly to tune, and may cause instability of training if not properly tuned. These hyperparameters include α and two learning rates to update wRsubscriptRw_ RwR and wFsubscriptFw_ FwF in Line 13 of Appendix B. In contrast, NGDiff is hyperparameter-free when equipped with GeN (AutoLR). • NGDiff are theoretically supported by Theorem 5, while the choice of hyperparameters and the use of a heuristic ri⁢(t)subscriptr_i(t)ritalic_i ( t ) by GradNorm may require further justification. Here ri⁢(t)=L~i⁢(t)/task⁢[L~i⁢(t)]subscriptsubscript~subscriptsubscripttaskdelimited-[]subscript~subscriptr_i(t)= L_i( θ_t)/E_task[% L_i( θ_t)]ritalic_i ( t ) = over~ start_ARG L end_ARGi ( italic_θitalic_t ) / blackboard_Etask [ over~ start_ARG L end_ARGi ( italic_θitalic_t ) ] is the "relative inverse training rate" of task i, where L~i⁢(t)=Li⁢(t)/Li⁢(0)subscript~subscriptsubscriptsubscriptsubscriptsubscript0 L_i( θ_t)=L_i( θ_t)/L_i( θ_0)over~ start_ARG L end_ARGi ( italic_θitalic_t ) = Litalic_i ( italic_θitalic_t ) / Litalic_i ( italic_θ0 ), i∈F,RFRi∈\ F, R\i ∈ F , R . In summary, NGDiff is remarkably simpler and more well-suited than GradNorm for unlearning, with stable performance and theoretical ground. Appendix C Details related to GeN C.1 Brief introduction of GeN GeN [4] is a method that sets the learning rate for any given gradient ditalic_d as ηGeN=⊤⁢⊤⁢subscriptGeNsuperscripttopsuperscripttop _GeN= G d d H dηGeN = divide start_ARG G⊤ italic_d end_ARG start_ARG italic_d⊤ H italic_d end_ARG where GG is the gradient and HH is the Hessian matrix of some loss L. One only needs to access the scalars ⊤⁢superscripttopG dG⊤ italic_d and ⊤⁢superscripttop d H ditalic_d⊤ H italic_d, without computing the high-dimensional GG and HH (or Hessian-vector product). To do so, two additional forward passes are needed: given a constant (say ξ=0.0010.001ξ=0.001ξ = 0.001), we compute L⁢(+ξ⁢)L( θ+ξ d)L ( italic_θ + ξ italic_d ) and L⁢(−ξ⁢)L( θ-ξ d)L ( italic_θ - ξ italic_d ). Then by curve fitting or finite difference as demonstrated below, we can estimate up to arbitrary precision controlled by ξ: ⊤⁢≈L⁢(+ξ⁢)−L⁢(−ξ⁢)2⁢ξsuperscripttop2G d≈ L( θ+ξ d)-L( θ-ξ% d)2ξG⊤ italic_d ≈ divide start_ARG L ( italic_θ + ξ italic_d ) - L ( italic_θ - ξ italic_d ) end_ARG start_ARG 2 ξ end_ARG and ⊤⁢≈L⁢(+ξ⁢)−2⁢L⁢()+L⁢(−ξ⁢)ξ2superscripttop2superscript2 d H d≈ L( θ+ξ d)-2L( % θ)+L( θ-ξ d)ξ^2italic_d⊤ H italic_d ≈ divide start_ARG L ( italic_θ + ξ italic_d ) - 2 L ( italic_θ ) + L ( italic_θ - ξ italic_d ) end_ARG start_ARG ξ2 end_ARG Notice that the regular optimization requires 1 forward pass and 1 back-propagation; GeN requires in total 3 forward passes and 1 back-propagation. Given that back-propagation costs roughly twice the computation time than forward pass, the total time increases from 3 units of time to 5 units. Nevertheless, GeN needs not to be applied at each iteration: if we update the learning rate every 10 iterations as in Remark 4.2, the total time reduces to 3+2/10=3.232103.23+2/10=3.23 + 2 / 10 = 3.2 units, and the overhead is less than 10% compared to the regular optimization. C.2 Adapting GeN to unlearning Naively applying GeN to the unlearning will result in ηGeN=⊤⁢UNUN⊤⁢UNsubscriptGeNsuperscripttopsubscriptUNsuperscriptsubscriptUNtopsubscriptUN _GeN= G g_UN g_UN% H g_UNηGeN = divide start_ARG G⊤ italic_gUN end_ARG start_ARG italic_gUN⊤ H italic_gUN end_ARG which minimizes the loss over all datapoints, in both F and R. This is against our goal to maximize the forgetting loss. We must consider the learning rate separately for F and R, as shown in Appendix G (Proof of Theorem 5). When both losses have a convex curvature in Figure 3, the optimal learning rate is only well-defined for LRsubscriptRL_ RLR and we do not claim to maximize LFsubscriptFL_ FLF. In other words, if we minimize LRsubscriptRL_ RLR, we get to worsen LFsubscriptFL_ FLF (though not maximally); if we choose to maximize LFsubscriptFL_ FLF, we will use infinite learning rate that also maximizes LRsubscriptRL_ RLR. Therefore, our learning rate in (8) only uses R instead of the whole dataset. Appendix D Computer Vision Experiments Method CIFAR-10 CIFAR-100 Forget Acc ↓ ↓ Retain Acc ↑ ↑ Forget Acc ↓ ↓ Retain Acc ↑ ↑ No-unlearn 0.9260.9260.9260.926 0.9560.9560.9560.956 0.7450.7450.7450.745 0.7500.7500.7500.750 GDiff c=0.9 0.0000.0000.0000.000 0.8170.8170.8170.817 0.0000.0000.0000.000 0.6640.6640.6640.664 GDiff c=0.5 0.0000.0000.0000.000 0.8300.8300.8300.830 0.0000.0000.0000.000 0.6090.6090.6090.609 GDiff c=0.1 0.0000.0000.0000.000 0.8250.8250.8250.825 0.0000.0000.0000.000 0.6670.6670.6670.667 LossNorm 0.0000.0000.0000.000 0.7530.7530.7530.753 0.0000.0000.0000.000 0.4320.4320.4320.432 NGDiff 0.0000.0000.0000.000 0.931 0.0000.0000.0000.000 0.701 Table 4: Results of Forget Acc and Retain Acc using different unlearning methods on the CIFAR-10 dataset. Compared to other baseline methods, NGDiff has the best performance on the model utility. To demonstrate the effectiveness of unlearning across other modalities, we also evaluate our method on the image classification task. Specifically, we choose the CIFAR-10 and CIFAR-100 dataset [26] and train a ResNet-50 [19] model from scratch. For the CIFAR-10 dataset, we sample 500 images from the class d⁢o⁢gdogd o g as the forgetting data, and use images from the remaining 9 classes as the retaining data. For the CIFAR-100 dataset, we sample 500 images from the class b⁢e⁢dbedb e d as the forgetting data, and use images from the remaining 99 classes as the retaining data. After training, the initial forget data accuracy is 0.9260.9260.9260.926, and the retain data accuracy is 0.9560.9560.9560.956 on the CIFAR-10 dataset. The initial forget data accuracy is 0.7450.7450.7450.745, and the retain data accuracy is 0.7500.7500.7500.750 on the CIFAR-100 dataset. Then we apply different unlearning methods to the trained models. As shown in Table 4, all methods successfully reduce the forget accuracy to 00. However, the retaining accuracy of NGDiff remains the highest, which shows its effectiveness in preserving the model utility in image classification tasks. Appendix E Other Related Works Machine unlearning Machine unlearning is oftentimes viewed as a continual learning approach, that removes specific data points after a model has been trained to memorize them. Such removal is light-weighted in contrast to re-training, especially when the forgetting set is much smaller than the retaining. In addition to the methods already introduced in Section 3.2 (namely GA, GDiff and NPO), other methods include SISA [2], influence functions [47], differential privacy [17] and so on. However, these methods could be difficult to scale on large models and large datasets due to the algorithmic complexity. To our best knowledge, this is the first work that formulate the unlearning problem as a two-task problem, which can be solved by a number of well-known MTO methods. Multi-task optimization MTO is a paradigm where one model is trained to perform multiple tasks simultaneously, so as to significantly improve the efficiency in contrast to training multiple models, one for each task. The key challenge of MTO is the performance trade-off among tasks, where the multi-task model is worse than single-task model if trained on each task separately. Therefore, the core idea is to balance different tasks by modifying the per-task gradients, e.g. with normalization (LossNorm and NGDiff), PCGrad [52], RLW [30], IMTL [33], MGDA [15], CAGrad [32], GradVaccine [49], GradDrop [11], RotoGrad [23], etc. Learning-rate-free methods Parameter-free or learning-rate-free methods automatically set the learning rate scheduler without the hyperparameter tuning, which is computationally infeasible for LLMs, e.g. LLAMA2 pre-training uses 3 hyperparameters just for the learning rate: warmup steps, peak learning rate, and minimum learning rate. At high level, there are two approaches to learning-rate-free methods. On one hand, GeN [4] leverages the Taylor expansion and convex-like landscape of deep learning, which is applicable for the general purpose, even if the gradient is modified like in the unlearning. On the other hand, methods like D-adaptation [13], Prodigy [37], DoG [21], DoWG [25] are based on the convex and G-Lipschitz conditions: L⁢(θ¯T)−L⁢(∗)≤|θ0−θ∗|22⁢η⁢T+η⁢G22subscript¯subscriptsuperscriptsubscript0subscript22superscript22L( θ_T)-L( θ_*)≤ | _0- _*|^22% η T+ η G^22L ( over¯ start_ARG θ end_ARGT ) - L ( italic_θ∗ ) ≤ divide start_ARG | θ0 - θ∗ |2 end_ARG start_ARG 2 η T end_ARG + divide start_ARG η G2 end_ARG start_ARG 2 end_ARG where θ∗subscript _*θ∗ is the unknown minimizer of L and θ¯Tsubscript¯ θ_Tover¯ start_ARG θ end_ARGT is an averaging scheme of θ0,…,θTsubscript0…subscript\ _0,..., _T\ θ0 , … , θitalic_T . With the same theoretical foundation, these methods propose different ways to approximate the initial-to-final distance |θ0−θ∗|subscript0subscript| _0- _*|| θ0 - θ∗ |. There are two main issues to apply these methods on the unlearning. Firstly, the assumption of G-Lipschitz is hard to verify and the minimizer θ∗subscript _*θ∗ is not well-defined in multi-objective (see our discussion on Pareto optimality under Lemma 2). Secondly, the optimal learning rate |θ0−θ∗|G⁢Tsubscript0subscript | _0- _*|G Tdivide start_ARG | θ0 - θ∗ | end_ARG start_ARG G square-root start_ARG T end_ARG end_ARG is defined in a manner to minimize the loss, whereas MTO methods operate on the gradient level. Hence MTO is incompatible to such parameter-free methods given that we cannot derive a corresponding loss (e.g. there exists no LNGDiffsubscriptNGDiffL_ NGDiffLNGDiff such that ∂LNGDiff∂θ=NGDiffsubscriptNGDiffsubscriptNGDiff ∂ L_ NGDiff∂θ= g_ NGDiffdivide start_ARG ∂ LNGDiff end_ARG start_ARG ∂ θ end_ARG = italic_gNGDiff). Appendix F Experiments F.1 Datasets Dataset TOFU MUSE-NEWS Full Forget10 Retain90 Train Raw VerbmemF KnowmemF KnowmemR # samples 4,00040004,0004 , 000 400400400400 3,60036003,6003 , 600 7,11071107,1107 , 110 2,66926692,6692 , 669 100100100100 100100100100 100100100100 Table 5: Statistics of the TOFU and MUSE-NEWS datasets. For the TOFU dataset, we use Full split for training the target model, Forget10 and Retain90 as the forgetting and retaining split for unlearning experiments. For the MUSE-NEWS dataset, we utilize Train split for training, Raw split for unlearning. For evaluation, we use VerbmemF and KnowmemF splits from forgetting data, and KnowmemR split from the retaining data. To evaluate the empirical performance of our proposed method, we experiment on the following datasets in Table 5. • Task of Fictitious Unlearning (TOFU) [36]. This dataset consists of question-answer pairs based on fictitious author biographies generated by GPT-4 [1]. Initially, predefined attributes, such as birthplace, gender, and writing genre, are assigned to 200 distinct authors. GPT-4 is then prompted to generate detailed information about each author. Following the synthesized data, 20 question-answer pairs are created for each fictitious author. The dataset is then divided into distinct datasets: the retaining set and the forgetting set. In our experiments, we use the forget10 and retain90 split, which excludes 10% of the original dataset. • MUSE-NEWS [43]. This dataset consists of BBC news articles [29] from August 2023. It includes seven subsets of news data: raw, verbmem, knowmem, privleak, scal, sust, and train. We utilize the train split to finetune a target model, and then the raw set, which includes both the forget and retain data, for the target model unlearning. Then, we use verbmem, knowmem split to evaluate the unlearned model’s performance. F.2 Evaluation Metrics Following the existing work [43], we evaluate the unlearning performance based on the quality of outputs from the model after unlearning. We expect a good performance should satisfy the following requirements: No verbatim memorization We evaluate this metric by prompting the model with the first l tokens of the news data in the forget set and compare the model’s continuation outputs with the ground truth continuation. Specifically, for each input x∈Fx∈ Fx ∈ F, we choose x[:l]subscriptdelimited-[]:absentx_[:l]x[ : l ] as input, and compare the output f⁢(x[:l])subscriptdelimited-[]:absentf(x_[:l])f ( x[ : l ] ) with the ground truth continuation x[l+1:]x_[l+1:]x[ l + 1 : ] with the ROUGE-L recall score: Verbmem⁢(f,F)=1‖F‖⁢Σx⁢ROUGE-L⁢(f⁢(x[:l]),x[l+1:]) split&Verbmem(f,F)\\ &= 1\|F\| _x\> ROUGE-L(f(x_[:l]),x_[l+1:]) splitstart_ROW start_CELL end_CELL start_CELL Verbmem ( f , F ) end_CELL end_ROW start_ROW start_CELL end_CELL start_CELL = divide start_ARG 1 end_ARG start_ARG ∥ F ∥ end_ARG Σitalic_x ROUGE-L ( f ( x[ : l ] ) , x[ l + 1 : ] ) end_CELL end_ROW (10) No knowledge memorization To evaluate this metric, we use the generated question-answer pair based on each example x∈Fx∈ Fx ∈ F. We prompt the model with the question part q and compare the output answer f⁢(q)f(q)f ( q ) to the ground truth answer a using ROUGE-L recall scores: Knowmem⁢(f,F)=1‖F‖⁢Σx⁢ROUGE-L⁢(f⁢(q),a)Knowmem1normsubscriptΣROUGE-LKnowmem(f,F)= 1\|F\| _x\> ROUGE-L(f(q),a)Knowmem ( f , F ) = divide start_ARG 1 end_ARG start_ARG ∥ F ∥ end_ARG Σitalic_x ROUGE-L ( f ( q ) , a ) (11) Maintained model utility An effective unlearning method should also maintain the model’s performance on the retain data. For the MUSE-NEWS dataset, we use the Knowmemr split, which consists of the generated question-answer pairs based on the retain data. For the TOFU dataset, we prompt the model with the question from the retain set and compare the generated answer with the ground truth. We use ROUGE-L recall scores for evaluation: Utility⁢(f,R)=1‖R‖⁢Σx⁢ROUGE-L⁢(f⁢(q),a)Utility1normsubscriptΣROUGE-LUtility(f,R)= 1\|R\| _x\> ROUGE-L(f(q),a)Utility ( f , R ) = divide start_ARG 1 end_ARG start_ARG ∥ R ∥ end_ARG Σitalic_x ROUGE-L ( f ( q ) , a ) (12) Additionally, we evaluate the model using the Retain10-perturbed split from the TOFU dataset. It consists of five perturbed answers for each original answer, keeping original template but modifying the facts. We compute the Truth Ratio metric, which compares the likelihood of the model generating a correct answer versus an incorrect one for each question in the retain set. A higher Truth Ratio indicates better model utility that effectively remembers knowledge from the retain data. F.3 Hyper-parameter Settings To finetune a targeted model with the full dataset, we use the optimizer Adam with a learning rate of η=10−5,2∗10−5superscript1052superscript105η=\10^-5,2*10^-5\η = 10- 5 , 2 ∗ 10- 5 , a training batch size of 16, 32, and train 25 epochs for all language models. For the unlearning process, we use the optimizer Adam with a learning rate η=10−5,5∗10−5,10−4superscript1055superscript105superscript104η=\10^-5,5*10^-5,10^-4\η = 10- 5 , 5 ∗ 10- 5 , 10- 4 , and train 15 epochs for all unlearning methods. For the Phi-1.5, Falcon-1B, and GPT2-XL models, we perform full-model parameter tuning. For the Llama2-7B and Mistral-7B models, we apply the LoRA training method [20] with rank = 8. F.4 Other unlearning results Base Model Metric Method No-unlearn GDiff-0.9 GDiff-0.5 GDiff-0.1 NPO LossNorm NGDiff Phi-1.5 Verbmem ↓ ↓ 0.0180.0180.0180.018 0.0000.0000.0000.000 0.0120.0120.0120.012 0.0000.0000.0000.000 0.0000.0000.0000.000 0.0120.0120.0120.012 0.004 Utility ↑ ↑ 0.3720.3720.3720.372 0.2770.2770.2770.277 0.0610.0610.0610.061 0.0000.0000.0000.000 0.0000.0000.0000.000 0.0610.0610.0610.061 0.001 Knowmem ↓ ↓ 0.0300.0300.0300.030 0.0000.0000.0000.000 0.0020.0020.0020.002 0.0000.0000.0000.000 0.0000.0000.0000.000 0.0020.0020.0020.002 0.023 Falcon-1B Verbmem ↓ ↓ 0.2040.2040.2040.204 0.1320.1320.1320.132 0.0000.0000.0000.000 0.0000.0000.0000.000 0.0000.0000.0000.000 0.1260.1260.1260.126 0.000 Utility ↑ ↑ 0.3860.3860.3860.386 0.2140.2140.2140.214 0.0000.0000.0000.000 0.0000.0000.0000.000 0.0000.0000.0000.000 0.1420.1420.1420.142 0.025 Knowmem ↓ ↓ 0.2320.2320.2320.232 0.0780.0780.0780.078 0.0000.0000.0000.000 0.0000.0000.0000.000 0.0000.0000.0000.000 0.1300.1300.1300.130 0.087 Table 6: Results of Verbatim memorization, Model utility, and TruthRatio on MUSE-NEWS dataset with different unlearning methods on Phi-1.5, and Falcon-1B models. Lower Verbmem along with higher Utility and TruthRatio indicate a more superior unlearning strategy. More results on MUSE-NEWS dataset with Phi-1.5 model and Falcon-1B model are in Table 6. Figure 7: Gradient norms and learning rates during the unlearning on TOFU dataset using NGDiff and Phi-1.5 model. The AutoLR scheduler assigns a smaller learning rate to the forgetting gradient, effectively preserving model utility on the retaining set. F.5 Visualization of learning rate scheduling We monitor the gradient norms and the learning rate in Figure 7 for Algorithm 1. We observe that the automatic learning rate is indeed effective, picking up from 5⁢e−5555e-55 e - 5 to around 2⁢e−4242e-42 e - 4, and that NGDiff assigns a smaller learning rate to the forgetting gradient, not perturbing the model too much to maintain the high utility on the retaining set. Appendix G Proofs In this section, we provide the proofs of all the lemma and theorems in this paper. Lemma 2 (restated from [51]). For any 0<c<1010<c<10 < c < 1, the model LSP∗⁢(c)=argminθ⁢LSP⁢(;c)subscriptsuperscriptLSPsubscriptargminLSP θ^*_LSP(c)=argmin_θ LSP( θ% ;c)italic_θ∗LSP ( c ) = argminθ LSP ( italic_θ ; c ) is Pareto optimal. Proof of Lemma 2. We show that the solution of LSP cannot be a dominated point, and therefore it must be Pareto optimal. Consider a solution ∗=argminθ⁢LSP⁢(;c)superscriptsubscriptargminLSP θ^*=argmin_θ LSP( θ;c)italic_θ∗ = argminθ LSP ( italic_θ ; c ), and suppose it is dominated by some ′superscript′ θ italic_θ′, i.e. LF⁢(∗)≤LF⁢(′),LR⁢(∗)≥LR⁢(′)formulae-sequencesubscriptFsuperscriptsubscriptFsuperscript′subscriptRsuperscriptsubscriptRsuperscript′L_ F( θ^*)≤ L_ F( θ ),L_% R( θ^*)≥ L_ R( θ )LF ( italic_θ∗ ) ≤ LF ( italic_θ′ ) , LR ( italic_θ∗ ) ≥ LR ( italic_θ′ ) with at least one inequality being strict. This contradicts that ∗superscript θ^*italic_θ∗ is minimal as c⁢LR⁢(∗)−(1−c)⁢LF⁢(∗)>c⁢LR⁢(′)−(1−c)⁢LF⁢(′).subscriptRsuperscript1subscriptFsuperscriptsubscriptRsuperscript′1subscriptFsuperscript′cL_ R( θ^*)-(1-c)L_ F( θ^*)>cL_% R( θ )-(1-c)L_ F( θ ).c LR ( italic_θ∗ ) - ( 1 - c ) LF ( italic_θ∗ ) > c LR ( italic_θ′ ) - ( 1 - c ) LF ( italic_θ′ ) . ∎ Theorem 3. For any ctsubscript\c_t\ citalic_t with 0≤ct≤10subscript10≤ c_t≤ 10 ≤ citalic_t ≤ 1 that converges as t→∞→t→∞t → ∞, the model ∗⁢(ct)=limt→∞tsuperscriptsubscriptsubscript→subscript θ^*(\c_t\)= _t→∞ θ_titalic_θ∗ ( citalic_t ) = limitalic_t → ∞ italic_θitalic_t in (5) is Pareto optimal. Proof of Theorem 3. Let c=limtctsubscriptsubscriptc= _tc_tc = limitalic_t citalic_t, then Eq. (5) gives that UN⁢(t)=ct⁢R⁢(t)−(1−ct)⁢F⁢(t)→c⁢R⁢(∗)−(1−c)⁢F⁢(∗)=subscriptUNsubscriptsubscriptsubscriptRsubscript1subscriptsubscriptFsubscript→subscriptRsuperscript1subscriptFsuperscript0 g_UN( θ_t)=c_t g_ R( θ_t)-% (1-c_t) g_ F( θ_t)→ c g_ R( % θ^*)-(1-c) g_ F( θ^*)= 0italic_gUN ( italic_θitalic_t ) = citalic_t italic_gR ( italic_θitalic_t ) - ( 1 - citalic_t ) italic_gF ( italic_θitalic_t ) → c italic_gR ( italic_θ∗ ) - ( 1 - c ) italic_gF ( italic_θ∗ ) = 0 as t→∞→t→∞t → ∞. Note ∗⁢(ct)superscriptsubscript θ^*(\c_t\)italic_θ∗ ( citalic_t ) is equivalent to the LSP solution LSP∗⁢(c)=argminθ⁢LSP⁢(;c)subscriptsuperscriptLSPsubscriptargminLSP θ^*_LSP(c)=argmin_θ LSP( θ% ;c)italic_θ∗LSP ( c ) = argminθ LSP ( italic_θ ; c ) as the latter has the same stationary condition, which is Pareto optimal by Lemma 2. ∎ Lemma 4. NGDiff⁢(R,F)subscriptNGDiffsubscriptRsubscriptF g_ NGDiff( g_ R, g_ F)italic_gNGDiff ( italic_gR , italic_gF ) satisfies Eq. (7) for any R∈ℝdsubscriptRsuperscriptℝ g_ R ^ditalic_gR ∈ blackboard_Rd and F∈ℝdsubscriptFsuperscriptℝ g_ F ^ditalic_gF ∈ blackboard_Rd. Proof of Lemma 4. We firstly show R⊤⁢UN≥0superscriptsubscriptRtopsubscriptUN0 g_ R g_UN≥ 0italic_gR⊤ italic_gUN ≥ 0 for UN=NGDiffsubscriptUNsubscriptNGDiff g_UN= g_ NGDiffitalic_gUN = italic_gNGDiff. We write R⊤⁢NGDiff=R⊤⁢(R‖R‖−F‖F‖)=‖R‖−R⊤⁢F‖F‖≥‖R‖−‖R‖⁢‖F‖F‖=0superscriptsubscriptRtopsubscriptNGDiffsuperscriptsubscriptRtopsubscriptRnormsubscriptRsubscriptFnormsubscriptFdelimited-∥subscriptRsuperscriptsubscriptRtopsubscriptFnormsubscriptFdelimited-∥subscriptRnormsubscriptRnormsubscriptFnormsubscriptF0 split g_ R g_ NGDiff&= g_% R ( g_ R\| g_ R\|-% g_ F\| g_ F\| )\\ &=\| g_ R\|- g_ R g_ F% \| g_ F\|≥\| g_ R\|- \| g_ R% \|\| g_ F\|\| g_ F\|\\ &=0 splitstart_ROW start_CELL italic_gR⊤ italic_gNGDiff end_CELL start_CELL = italic_gR⊤ ( divide start_ARG italic_gR end_ARG start_ARG ∥ italic_gR ∥ end_ARG - divide start_ARG italic_gF end_ARG start_ARG ∥ italic_gF ∥ end_ARG ) end_CELL end_ROW start_ROW start_CELL end_CELL start_CELL = ∥ italic_gR ∥ - divide start_ARG italic_gR⊤ italic_gF end_ARG start_ARG ∥ italic_gF ∥ end_ARG ≥ ∥ italic_gR ∥ - divide start_ARG ∥ italic_gR ∥ ∥ italic_gF ∥ end_ARG start_ARG ∥ italic_gF ∥ end_ARG end_CELL end_ROW start_ROW start_CELL end_CELL start_CELL = 0 end_CELL end_ROW where the inequality is the Cauchy-Schwarz inequality. Similarly, F⊤⁢UN≤0superscriptsubscriptFtopsubscriptUN0 g_ F g_UN≤ 0italic_gF⊤ italic_gUN ≤ 0 easily follows. ∎ Theorem 5. Consider t+1=t−η⁢NGDiffsubscript1subscriptsubscriptNGDiff θ_t+1= θ_t-η g_ NGDiffitalic_θitalic_t + 1 = italic_θitalic_t - η italic_gNGDiff. (1) Unless RsubscriptR g_ Ritalic_gR is exactly parallel to FsubscriptF g_ Fitalic_gF, for any sufficiently small learning rate η, there exist two constants ϵR,1=o⁢(η),ϵF,1=o⁢(η)formulae-sequencesubscriptitalic-ϵR1subscriptitalic-ϵF1 _ R,1=o(η), _ F,1=o(η)ϵR , 1 = o ( η ) , ϵF , 1 = o ( η ) such that LR⁢(t+1)−LR⁢(t)<ϵR,1;subscriptRsubscript1subscriptRsubscriptsubscriptitalic-ϵR1L_ R( θ_t+1)-L_ R( θ_t)< _% R,1;LR ( italic_θitalic_t + 1 ) - LR ( italic_θitalic_t ) < ϵR , 1 ; LF⁢(t+1)−LF⁢(t)>ϵF,1.subscriptFsubscript1subscriptFsubscriptsubscriptitalic-ϵF1L_ F( θ_t+1)-L_ F( θ_t)> _% F,1.LF ( italic_θitalic_t + 1 ) - LF ( italic_θitalic_t ) > ϵF , 1 . (2) If additionally NGDiff⊤⁢R⁢NGDiff>0superscriptsubscriptNGDifftopsubscriptRsubscriptNGDiff0 g_ NGDiff H_ R g_ NGDiff>0italic_gNGDiff⊤ HR italic_gNGDiff > 0 and NGDiff⊤⁢F⁢NGDiff>0superscriptsubscriptNGDifftopsubscriptFsubscriptNGDiff0 g_ NGDiff H_ F g_ NGDiff>0italic_gNGDiff⊤ HF italic_gNGDiff > 0, then for any learning rate 0<η<2⁢R⊤⁢NGDiffNGDiff⊤⁢R⁢NGDiff02superscriptsubscriptRtopsubscriptNGDiffsuperscriptsubscriptNGDifftopsubscriptRsubscriptNGDiff0<η< 2 g_ R g_ NGDiff g_% NGDiff H_ R g_ NGDiff0 < η < divide start_ARG 2 italic_gR⊤ italic_gNGDiff end_ARG start_ARG italic_gNGDiff⊤ HR italic_gNGDiff end_ARG, there exist two constants ϵR,2=o⁢(η2),ϵF,2=o⁢(η2)formulae-sequencesubscriptitalic-ϵR2superscript2subscriptitalic-ϵF2superscript2 _ R,2=o(η^2), _ F,2=o(η^2)ϵR , 2 = o ( η2 ) , ϵF , 2 = o ( η2 ) such that LR⁢(t+1)−LR⁢(t)<ϵR,2;LF⁢(t+1)−LF⁢(t)>ϵF,2.formulae-sequencesubscriptRsubscript1subscriptRsubscriptsubscriptitalic-ϵR2subscriptFsubscript1subscriptFsubscriptsubscriptitalic-ϵF2L_ R( θ_t+1)-L_ R( θ_t)< _% R,2;L_ F( θ_t+1)-L_ F( θ_t% )> _ F,2.LR ( italic_θitalic_t + 1 ) - LR ( italic_θitalic_t ) < ϵR , 2 ; LF ( italic_θitalic_t + 1 ) - LF ( italic_θitalic_t ) > ϵF , 2 . Proof of Theorem 5. Applying (6) with NGDiffsubscriptNGDiff g_ NGDiffitalic_gNGDiff gives LR⁢(t+1)−LR⁢(t)=−η⁢R⊤⁢NGDiff+η22⁢NGDiff⊤⁢R⁢NGDiff+o⁢(η2)subscriptRsubscript1subscriptRsubscriptsuperscriptsubscriptRtopsubscriptNGDiffsuperscript22superscriptsubscriptNGDifftopsubscriptRsubscriptNGDiffsuperscript2 L_ R( θ_t+1)-L_ R( θ_t% )=-η g_ R g_ NGDiff+ η^22% g_ NGDiff H_ R g_ NGDiff% +o(η^2)LR ( italic_θitalic_t + 1 ) - LR ( italic_θitalic_t ) = - η italic_gR⊤ italic_gNGDiff + divide start_ARG η2 end_ARG start_ARG 2 end_ARG italic_gNGDiff⊤ HR italic_gNGDiff + o ( η2 ) (13) For part (1), note that Lemma 4 gives R⊤⁢NGDiff>0superscriptsubscriptRtopsubscriptNGDiff0 g_ R g_NGDiff>0italic_gR⊤ italic_gNGDiff > 0 unless F∥RconditionalsubscriptFsubscriptR g_ F g_ Ritalic_gF ∥ italic_gR. Hence for any η>00η>0η > 0, we have LR⁢(t+1)−LR⁢(t)=−η⁢R⊤⁢NGDiff+o⁢(η)<o⁢(η)subscriptRsubscript1subscriptRsubscriptsuperscriptsubscriptRtopsubscriptNGDiffL_ R( θ_t+1)-L_ R( θ_t)=-η g_% R g_ NGDiff+o(η)<o(η)LR ( italic_θitalic_t + 1 ) - LR ( italic_θitalic_t ) = - η italic_gR⊤ italic_gNGDiff + o ( η ) < o ( η ) and similarly for LFsubscriptFL_ FLF. For part (2), now that NGDiff⊤⁢R⁢NGDiff>0superscriptsubscriptNGDifftopsubscriptRsubscriptNGDiff0 g_ NGDiff H_ R g_ NGDiff>0italic_gNGDiff⊤ HR italic_gNGDiff > 0, we have −η⁢R⊤⁢NGDiff+η22⁢NGDiff⊤⁢R⁢NGDiff<0⟺0<η<2⁢R⊤⁢NGDiffNGDiff⊤⁢R⁢NGDiff⟺superscriptsubscriptRtopsubscriptNGDiffsuperscript22superscriptsubscriptNGDifftopsubscriptRsubscriptNGDiff002superscriptsubscriptRtopsubscriptNGDiffsuperscriptsubscriptNGDifftopsubscriptRsubscriptNGDiff split&-η g_ R g_ NGDiff+ % η^22 g_ NGDiff H_ R g_% NGDiff<0 0<η< 2 g_ R % g_ NGDiff g_ NGDiff H_ R% g_ NGDiff splitstart_ROW start_CELL end_CELL start_CELL - η italic_gR⊤ italic_gNGDiff + divide start_ARG η2 end_ARG start_ARG 2 end_ARG italic_gNGDiff⊤ HR italic_gNGDiff < 0 ⟺ 0 < η < divide start_ARG 2 italic_gR⊤ italic_gNGDiff end_ARG start_ARG italic_gNGDiff⊤ HR italic_gNGDiff end_ARG end_CELL end_ROW and similarly −η⁢F⊤⁢NGDiff+η22⁢NGDiff⊤⁢F⁢NGDiff>0⟸0<ηsuperscriptsubscriptFtopsubscriptNGDiffsuperscript22superscriptsubscriptNGDifftopsubscriptFsubscriptNGDiff0⟸0-η g_ F g_ NGDiff+ η^22 % g_ NGDiff H_ F g_ NGDiff>0% 0<η- η italic_gF⊤ italic_gNGDiff + divide start_ARG η2 end_ARG start_ARG 2 end_ARG italic_gNGDiff⊤ HF italic_gNGDiff > 0 ⟸ 0 < η We complete the proof by substituting the inequalities into (13). ∎ Remark G.1. There is a computational overhead to use GeN, as it requires additional forward passes to estimate ηt∗superscriptsubscript _t^*ηitalic_t∗. Nevertheless, we only update the learning rate every 10 iterations so that the overhead is amortized and thus negligible. Proof of Remark G.1. We extend our original complexity analysis in Remark 4.2 and provide quantitative analysis of computation overheads in FLOPs (floating point operations). Specifically, assume it takes around N FLOPS to perform one forward pass on one example and 2N FLOPS to back-propagate. The basic GDiff requires roughly 6BTN FLOPS to run with batch size B and total number of iterations T, because it needs 1 forward and 1 backward for the retain set and another for the forget set. Our learning-rate-free NGDiff requires about (6BTN+4BTN/10), hence a 6.6% increase to unlearn the data. We assure that the extra forward passes do not add memory burden, because they are in gradient-free mode (e.g. under torch.no_grad() mode). All in all, NGDiff is almost as efficient as GDiff and other unlearning methods, as the target unlearning corpus is usually relatively small. This has been empirically observed by our large-scale (up to 7B) model unlearning experiments. ∎

Instant research discovery