Paper deep dive
Negative Preference Optimization: From Catastrophic Collapse to Effective Unlearning
Ruiqi Zhang, Licong Lin, Yu Bai, Song Mei
Models: Llama-2-7B-chat
Intelligence
Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 96%
Last extracted: 3/12/2026, 8:29:30 PM
Summary
The paper introduces Negative Preference Optimization (NPO), a novel method for Large Language Model (LLM) unlearning designed to mitigate 'catastrophic collapse'—a phenomenon where models lose utility while attempting to forget specific data. NPO, inspired by alignment techniques like Direct Preference Optimization (DPO), uses only negative samples to achieve stable unlearning. Theoretical and experimental results on the TOFU benchmark demonstrate that NPO provides a superior trade-off between forget quality and model utility compared to traditional gradient ascent methods, enabling effective unlearning of up to 50-90% of training data.
Entities (5)
Relation Signals (3)
Negative Preference Optimization → evaluatedon → TOFU
confidence 100% · We evaluate a variety of unlearning methods on the TOFU dataset
Negative Preference Optimization → mitigates → Catastrophic Collapse
confidence 95% · NPO resolves the catastrophic collapse issue associated with gradient ascent
Gradient Ascent → causes → Catastrophic Collapse
confidence 90% · gradient ascent can often cause a rapid deterioration of model utility during unlearning—a phenomenon we term catastrophic collapse
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Large Language Models (LLMs) often memorize sensitive, private, or copyrighted data during pre-training. LLM unlearning aims to eliminate the influence of undesirable data from the pre-trained model while preserving the model's utilities on other tasks. Several practical methods have recently been proposed for LLM unlearning, mostly based on gradient ascent (GA) on the loss of undesirable data. However, on certain unlearning tasks, these methods either fail to effectively unlearn the target data or suffer from catastrophic collapse -- a drastic degradation of the model's utilities. In this paper, we propose Negative Preference Optimization (NPO), a simple alignment-inspired method that could efficiently and effectively unlearn a target dataset. We theoretically show that the progression toward catastrophic collapse by minimizing the NPO loss is exponentially slower than GA. Through experiments on synthetic data and the benchmark TOFU dataset, we demonstrate that NPO-based methods achieve a better balance between unlearning the undesirable data and maintaining the model's utilities. We also observe that NPO-based methods generate more sensible outputs than GA-based methods, whose outputs are often gibberish. Remarkably, on TOFU, NPO-based methods are the first to achieve reasonable unlearning results in forgetting 50% (or more) of the training data, whereas existing methods already struggle with forgetting 10% of training data.
Tags
Links
Trouble viewing inline? Open PDF directly →
Full Text
231,577 characters extracted from source content.
Expand or collapse full text
Negative Preference Optimization: From Catastrophic Collapse to Effective Unlearning Ruiqi Zhang Equal contributions; the more junior author is listed earlier.UC Berkeley. Email: rqzhang@berkeley.edu Licong Lin11footnotemark: 1 UC Berkeley. Email: liconglin@berkeley.edu Yu Bai Salesforce AI Research. Email: yu.bai@salesforce.com Song Mei UC Berkeley. Email: songmei@berkeley.edu (October 6, 2024) Abstract Large Language Models (LLMs) often memorize sensitive, private, or copyrighted data during pre-training. LLM unlearning aims to eliminate the influence of undesirable data from the pre-trained model while preserving the model’s utilities on other tasks. Several practical methods have recently been proposed for LLM unlearning, mostly based on gradient ascent (GA) on the loss of undesirable data. However, on certain unlearning tasks, these methods either fail to effectively unlearn the target data or suffer from catastrophic collapse—a drastic degradation of the model’s utilities. In this paper, we propose Negative Preference Optimization (NPO), a simple alignment-inspired method that could efficiently and effectively unlearn a target dataset. We theoretically show that the progression toward catastrophic collapse by minimizing the NPO loss is exponentially slower than GA. Through experiments on synthetic data and the benchmark TOFU dataset, we demonstrate that NPO-based methods achieve a better balance between unlearning the undesirable data and maintaining the model’s utilities. We also observe that NPO-based methods generate more sensible outputs than GA-based methods, whose outputs are often gibberish. Remarkably, on TOFU, NPO-based methods are the first to achieve reasonable unlearning results in forgetting 50% (or more) of the training data, whereas existing methods already struggle with forgetting 10% of training data. 00footnotetext: Code is available at: https://github.com/licong-lin/negative-preference-optimization. 1 Introduction Large language models (LLMs), pretrained on massive corpora of internet data, possess the capability to memorize portions of their training data (Carlini et al., 2021, 2022). However, this capability raises significant concerns, as the training data may contain sensitive or private information, potentially leading to societal challenges. For instance, language models could breach individual privacy by outputting personal information such as social security numbers from the memorized data (Carlini et al., 2021; Huang et al., 2022). They might also violate copyright by generating text from memorized books, such as the Harry Potter novels (Eldan & Russinovich, 2023). Furthermore, LLM assistants for biology could inadvertently aid in the development of biological weapons by troubleshooting bottlenecks, increasing the risk of such attempts (Sandbrink, 2023; Li et al., 2024). In response to these concerns, regulations like the EU’s General Data Protection Regulation (GDPR) (Mantelero, 2013; Voigt & Von dem Bussche, 2017) and the US’s California Consumer Privacy Act (CCPA) (CCPA, 2018) have mandated the Right to be Forgotten, requiring applications to support the deletion of information contained in training samples upon user requests. This has motivated a line of research on machine unlearning, aiming to address these challenges. Machine unlearning (Cao & Yang, 2015; Bourtoule et al., 2021) aims to delete the influence of specific training samples from machine-learning models while preserving other knowledge and capabilities (Liu et al., 2024a; Zhang et al., 2023; Nguyen et al., 2022; Xu et al., 2023; Si et al., 2023). Notably, a straightforward approach to unlearning is to retrain a language model from scratch. However, as retraining from scratch is typically computationally expensive, cheaper methods for removing undesirable information is highly desirable. Recently, several works (Jang et al., 2022; Wang et al., 2023; Chen & Yang, 2023; Yao et al., 2023; Eldan & Russinovich, 2023; Yao et al., 2024; Liu et al., 2024b; Li et al., 2024) proposed scalable and practical techniques for unlearning LLMs through directly fine-tuning the trained model. Core to many of these works is a gradient ascent procedure on the prediction loss over the dataset to be unlearned (i.e., the forget set), building on the intuition that gradient ascent is an approximation of “reverting” gradient descent optimization. Figure 1: Gradient Ascent (GA), Negative Preference Optimization (NPO), and Direct Preference Optimization (DPO). NPO can be interpreted as DPO without positive samples. The gradient of NPO is an adaptive weighting of that of GA, and the weight vanishes for unlearned samples. Despite its simplicity and widespread use, the performance of gradient ascent based approaches remain unsatisfactory. A notable example concerns the recently released benchmark dataset TOFU (Maini et al., 2024), which consists of synthetically generated biographies of 200 fictitious authors, and the task is to unlearn the biographies of 1%, 5%, and 10% of the 200 authors from a model that is already fine-tuned on all 200 authors. In their evaluation of forgetting 10% of the authors, Maini et al. (2024) demonstrated that gradient ascent and its variants fail to provide a satisfactory balance between forget quality (the difference between the unlearned model and retrained model evaluated on the forget set) and model utility (the general performance on other tasks). In this work, we begin by observing that gradient ascent can often cause a rapid deterioration of model utility during unlearning—a phenomenon we term catastrophic collapse—which we believe is responsible for its unsatisfactory performance. Towards fixing this, we propose a simple yet effective objective function for unlearning termed Negative Preference Optimization (NPO). NPO takes inspiration from preference optimization (Rafailov et al., 2024; Ouyang et al., 2022; Bai et al., 2022), and can be viewed as its variant that only uses negative samples. Through both theory and experiments, we show that NPO resolves the catastrophic collapse issue associated with gradient ascent, provides more stable training dynamics, and achieves a better trade-off between forget quality and model utility. Coupled with a cross-entropy loss on the retain set, NPO achieves state-of-the-art performance on the TOFU dataset, and achieves the first non-trivial unlearning result on the challenging task of forgetting 50% of the TOFU data. Summary of contributions and paper outline. • We outline existing gradient ascent based methods for machine unlearning, and find that these methods suffer from catastrophic collapse (Section 2). We identify the linear divergence speed of gradient ascent as a main reason for catastrophic collapse. • We introduce Negative Preference Optimization (NPO), a simple alignment-inspired loss function for LLM unlearning that addresses the catastrophic collapse issue of gradient ascent (GA; Section 3). We demonstrate that NPO reduces to gradient ascent (GA) in the high-temperature limit. We show in theory the progression towards catastrophic collapse when minimizing the NPO loss is exponentially slower than with GA. See Figure 1 for an illustration of NPO and its connections with existing objectives. • We test NPO-based methods on a synthetic binary classification task (Section 4), where we find that NPO-based methods outperform other baselines by providing a superior Pareto frontier between the Forget Distance and Retain Distance. Furthermore, NPO-based methods exhibit greater learning stability compared to GA-based methods. • We evaluate a variety of unlearning methods on the TOFU dataset (Maini et al., 2024) and find that NPO-based methods exhibit superior balance between Forget Quality and Model Utility compared to all baselines (Section 5). Additionally, NPO-based methods improve the stability of the unlearning process and the readability of the output. Notably, we show that NPO-based methods are the only effective unlearning methods for forgetting 50%-90% of the data, a significant advance over all existing methods which already struggle with forgetting 10% of the data (Section 5.3). 1.1 Related work There is a vast literature on machine unlearning and LLM unlearning. Since its proposal by Cao & Yang (2015), machine unlearning has been extensively studied in the classification literature (Bourtoule et al., 2021; Golatkar et al., 2020; Ginart et al., 2019; Thudi et al., 2022; Izzo et al., 2021; Koh & Liang, 2017; Guo et al., 2019; Sekhari et al., 2021). For reviews of existing works, see Liu et al. (2024a); Zhang et al. (2023); Nguyen et al. (2022); Xu et al. (2023); Si et al. (2023). In particular, Ginart et al. (2019); Guo et al. (2019); Sekhari et al. (2021) introduced theoretical metrics for machine unlearning based on the notion of differential privacy and proposed provably efficient unlearning methods based on Newton update removal mechanisms. However, these algorithms require computing the Hessian of loss functions, which is intractable for LLMs. Recent research has explored unlearning methods for LLMs (Jang et al., 2022; Wang et al., 2023; Chen & Yang, 2023; Yao et al., 2023; Eldan & Russinovich, 2023; Yao et al., 2024; Liu et al., 2024b; Li et al., 2024). Notably, the methods proposed in Jang et al. (2022); Yao et al. (2023); Chen & Yang (2023); Maini et al. (2024) are based on gradient ascent (GA) on the loss of the forget set. In this work, we demonstrate that the NPO approach consistently outperforms GA across various tasks. On the other hand, Eldan & Russinovich (2023) proposed generating positive samples using LLMs and carefully designed prompts, then fine-tuning the model based on the positive samples using a supervised loss. Furthermore, the method of Liu et al. (2024b) is based on knowledge negation, while the approach of Li et al. (2024) relies on controlling model representations. These methods are orthogonal and complementary to the NPO approach. Our method, NPO, draws inspiration from the framework of reinforcement learning from human feedback (RLHF) (Ouyang et al., 2022; Bai et al., 2022; Stiennon et al., 2020; Rafailov et al., 2024), particularly the Direct Policy Optimization (DPO) method (Rafailov et al., 2024). We note that recent work (Ethayarajh et al., 2024) proposes the Kahneman-Tversky Optimization (KTO) method for alignment with only non-paired preference data, and a more recent concurrent work (Duan et al., 2024) proposes the Distributional Dispreference Optimization (D2superscriptD2 D^2D2O) approach for unlearning. Both methods share a similar formulation to NPO. We compare the performance of NPO with KTO in simulations. Recent work has proposed several benchmark datasets and evaluation metrics for unlearning methods (Ji et al., 2024; Eldan & Russinovich, 2023; Maini et al., 2024; Li et al., 2024; Lynch et al., 2024). In particular, some studies have utilized the PKUSafe dataset (Ji et al., 2024) for benchmarking unlearning methods. Eldan & Russinovich (2023) crafts a specific task of “forgetting Harry Potter”. Maini et al. (2024) introduces TOFU, a task of fictitious unlearning for LLMs, which is the benchmark we adopted in this paper. Additionally, Li et al. (2024) proposes the Weapons of Mass Destruction Proxy (WMDP) for measuring hazardous knowledge in LLMs. Lynch et al. (2024) proposes eight methods to evaluate robust unlearning in LLM, which incorporate robust metrics against jailbreak attacks. Finally, we note the existence of attack methods for extracting data from unlearned models (Shi et al., 2023; Patil et al., 2023), and other unlearning methods including model editing (Mitchell et al., 2022; Meng et al., 2022) and in-context unlearning (Pawelczyk et al., 2023). 2 Preliminaries on Machine Unlearning Machine Unlearning refers to the following problem: Given an initial model (also the reference model) πref(y|x)subscriptrefconditionalπ_ref(y|x)πroman_ref ( y | x ) that is already trained on a dataset =(xi,yi)i∈[n]subscriptsubscriptsubscriptdelimited-[]D=\(x_i,y_i)\_i∈[n]D = ( xitalic_i , yitalic_i ) i ∈ [ n ], how to make the model forget a specific subset (henceforth the forget set) FG⊆subscriptFGD_ FG _FG ⊆ D of the training data? More precisely, we aim to fine-tune111There are alternative approaches such as prompt engineering (Pawelczyk et al., 2023) for performing unlearning tasks. the model to make it behave like the retrained model πretrsubscriptretrπ_ retrπroman_retr, a model trained only on the retain set RT=∖FGsubscriptRTsubscriptFGD_ RT=D D_ FGDroman_RT = D ∖ Droman_FG. In other words, we would like the model to behave as if the samples in the forget set FGsubscriptFGD_ FGDroman_FG were never used to train it. By definition, the best approach for machine unlearning, in principle, is to retrain the model from scratch on RTsubscriptRTD_ RTDroman_RT only, which is, however, often intractable in practice. Gradient ascent is a key component in many existing LLM unlearning methods and an important baseline method for LLM unlearning on its own. The idea is simply to perform gradient ascent on the (next-token prediction) loss over the forget set, which can be viewed equivalently as gradient descent on the negative prediction loss, denoted as ℒGAsubscriptℒGAL_GALroman_GA: ℒGA(θ)=−FG[−log(πθ(y|x))]⏟prediction loss=FG[log(πθ(y|x))].subscriptℒGAsubscript⏟subscriptsubscriptFGdelimited-[]subscriptconditionalprediction losssubscriptsubscriptFGdelimited-[]subscriptconditionalL_GA(θ)=- E_D_% FG[- (π_θ(y|x))]_ prediction loss= % E_D_ FG[ (π_θ(y|x))].Lroman_GA ( θ ) = - under⏟ start_ARG blackboard_ED start_POSTSUBSCRIPT FG end_POSTSUBSCRIPT [ - log ( πitalic_θ ( y | x ) ) ] end_ARGprediction loss = blackboard_ED start_POSTSUBSCRIPT FG end_POSTSUBSCRIPT [ log ( πitalic_θ ( y | x ) ) ] . (1) The rationale of gradient ascent is that since the initial model πrefsubscriptrefπ_refπroman_ref is trained on =FG∪RTsubscriptFGsubscriptRTD=D_ FG∪D_ RTD = Droman_FG ∪ Droman_RT, a subsequent maximization of prediction loss on the forget set FGsubscriptFGD_ FGDroman_FG would approximately “revert” the optimization on the forget set FGsubscriptFGD_ FGDroman_FG, thus unlearning FGsubscriptFGD_ FGDroman_FG and approximating a model trained on RTsubscriptRTD_ RTDroman_RT only. Other loss functions. Building on gradient ascent, a large class of unlearning methods perform gradient-based optimization on a linear combination of the GA loss ℒGAsubscriptℒGAL_GALroman_GA and several other loss functions that either encourage unlearning or preserve utility (Jang et al., 2022; Yao et al., 2023; Chen & Yang, 2023; Maini et al., 2024; Eldan & Russinovich, 2023). Notable examples include • Forget (FG) loss: ℒFG(θ)=−FG[log(πθ(y~|x))]subscriptℒFGsubscriptsubscriptFGdelimited-[]subscriptconditional~L_FG(θ)=-E_D_ FG[% (π_θ( y|x))]Lroman_FG ( θ ) = - blackboard_ED start_POSTSUBSCRIPT FG end_POSTSUBSCRIPT [ log ( πitalic_θ ( over~ start_ARG y end_ARG | x ) ) ], where (x,y)∼FGsimilar-tosubscriptFG(x,y) D_ FG( x , y ) ∼ Droman_FG and y~≠y~ y≠yover~ start_ARG y end_ARG ≠ y is any “uninformed” response for prompt x which the unlearned model could aim to output. Examples of such y~~ yover~ start_ARG y end_ARG’s include replacing true information by random (but appearingly sensible) information (which requires hand-crafting such as Eldan & Russinovich (2023)), or simply answering “I don’t know” (Maini et al., 2024). • Retain (RT) loss: ℒRT(θ)=−RT[log(πθ(y|x))]subscriptℒRTsubscriptsubscriptRTdelimited-[]subscriptconditionalL_RT(θ)=-E_D_ RT[% (π_θ(y|x))]Lroman_RT ( θ ) = - blackboard_ED start_POSTSUBSCRIPT RT end_POSTSUBSCRIPT [ log ( πitalic_θ ( y | x ) ) ], which encourages the model to still perform well on the retain set RTsubscriptRTD_ RTDroman_RT; • FG(θ)=FG[(πθ(⋅|x)||πref(⋅|x))]K_FG(θ)=E_D_ FG[% D(π_θ(·|x)||π_ref(·|x))]Kroman_FG ( θ ) = blackboard_ED start_POSTSUBSCRIPT FG end_POSTSUBSCRIPT [ sansserif_D ( πitalic_θ ( ⋅ | x ) | | πroman_ref ( ⋅ | x ) ) ], which measures the distance to the initial model πrefsubscriptrefπ_refπroman_ref (in KL divergence) on the forget set; • RT(θ)=RT[(πθ(⋅|x)||πref(⋅|x))]K_RT(θ)=E_D_ RT[% D(π_θ(·|x)||π_ref(·|x))]Kroman_RT ( θ ) = blackboard_ED start_POSTSUBSCRIPT RT end_POSTSUBSCRIPT [ sansserif_D ( πitalic_θ ( ⋅ | x ) | | πroman_ref ( ⋅ | x ) ) ], which measures the distance to the initial model πrefsubscriptrefπ_refπroman_ref (in KL divergence) on the retain set. For example, Yao et al. (2023) minimize a combination of ℒGA,ℒFG,RTsubscriptℒGAsubscriptℒFGsubscriptRT\L_GA,L_FG,K_% RT\ Lroman_GA , Lroman_FG , Kroman_RT , and Chen & Yang (2023) minimize a combination of ℒGA,ℒRT,−FG,RTsubscriptℒGAsubscriptℒRTsubscriptFGsubscriptRT\L_GA,L_RT,-K_% FG,K_RT\ Lroman_GA , Lroman_RT , - Kroman_FG , Kroman_RT . Maini et al. (2024) find that incorporating the retain loss ℒRTsubscriptℒRTL_RTLroman_RT usually improves the performance of unlearning. Forget quality and model utility. Unlearning methods should not only unlearn the forget set, i.e., achieve a high forget quality, but also maintain the model’s performance on the retain set, i.e., maintain the model utility. For example, letting the model simply output “I don’t know” is an unlearning method that achieves good forget quality (in certain sense) but bad model utility. While there is not yet a consensus on the right metrics for forget quality and model utility (and we will present our choices momentarily), a general rule of thumb is that unlearning methods should achieve a good tradeoff between these two goals. 2.1 Catastrophic collapse of gradient ascent Figure 2: Comparison between GA and NPO on forget quality, model utility, KL divergence on the real-world Set, and the answers to the forget set. The rightmost figure shows the answers generated from variants of GA and NPO that incorporates the RT loss. All figures are generated on the Forget05 task in the TOFU data, trained for 10 epochs (detailed setup in Section D.1). We begin by testing gradient ascent as a standalone method (as opposed to combining it with other losses), and find that gradient ascent exhibits a common failure mode dubbed as catastrophic collapse: Along the unlearning process, the model utility quickly drops to zero, and the forget quality improves temporarily for a very short time horizon before quickly dropping too (Figure 2 left/middle-left). Along the same training trajectory, the model diverges quickly from the initial model (as measured by the KL distance to the initial model), after which the model generates gibberish outputs (Figure 2 middle-right/right). We attribute the catastrophic collapse to the divergent nature of the gradient ascent algorithm due to the fact that it maximizes (instead of minimizes) the standard next-token prediction loss. Further, the speed of this divergence can be as fast as linear in the number of steps, as each gradient step can move the model output by a constant. To see this on a toy example, consider a linear-logistic K-class classifier given by πθ(⋅|x)=softmax(θx)π_θ(·|x)=softmax(θx)πitalic_θ ( ⋅ | x ) = softmax ( θ x ), θ=(θl)l∈[K]∈ℝd×Ksubscriptsubscriptdelimited-[]superscriptℝθ=(θ_l)_l∈[K] ^d× Kθ = ( θitalic_l )l ∈ [ K ] ∈ blackboard_Rd × K. For any “already unlearned” sample (xi,yi)subscriptsubscript(x_i,y_i)( xitalic_i , yitalic_i ) with true label yi=l∈[K]subscriptdelimited-[]y_i=l∈[K]yitalic_i = l ∈ [ K ] and model prediction softmax(θxi)l≈0softmaxsubscriptsubscript0softmax(θx_i)_l≈ 0softmax ( θ xitalic_i )l ≈ 0 (so that πθsubscriptπ_θπitalic_θ does not predict l), standard calculation shows that the gradient of GA loss with respect to θlsubscript _lθitalic_l is ∇θlℒGA,i=(1yi=l−softmax(θxi)l)xi≈xisubscript∇subscriptsubscriptℒGA1subscriptsoftmaxsubscriptsubscriptsubscriptsubscript _θ_lL_GA,i=(1\y_i=l\-% softmax(θx_i)_l)x_i≈x_i∇θ start_POSTSUBSCRIPT l end_POSTSUBSCRIPT Lroman_GA , i = ( 1 yitalic_i = l - softmax ( θ xitalic_i )l ) xitalic_i ≈ xitalic_i, which has a constant scale (not diminishing along the unlearning progress) and can cause the model to diverge in a linear speed. Therefore, the divergent dynamics may initially bring the model closer to πretrsubscriptretrπ_ retrπroman_retr but would ultimately send the model to infinity (c.f. Theorem 2). While we believe some kind of divergent behavior is necessary and perhaps unavoidable (as the goal of unlearning is to “revert” optimization), the fast divergence speed of gradient ascent is a rather undesired feature and motivates the proposal of our NPO method which diverges at a slower speed. 3 Negative Preference Optimization We introduce Negative Preference Optimization (NPONPONPONPO), a simple drop-in fix of the GA loss. The NPONPONPONPO loss reduces to the GA loss in the high-temperature limit, but remains lower-bounded and stable at any finite temperature, unlike the GA loss. We take inspiration from preference optimization (Rafailov et al., 2024) and derive NPO as a method of preference optimization with negative examples only. Preference Optimization. In preference optimization (Ouyang et al., 2022; Bai et al., 2022; Stiennon et al., 2020; Rafailov et al., 2024), we are given a dataset with preference feedbacks paired=(xi,yi,w,yi,l)i∈[n]subscriptpairedsubscriptsubscriptsubscriptwsubscriptldelimited-[]D_ paired=\(x_i,y_i, w,y_i, l)\_i∈[n]Droman_paired = ( xitalic_i , yitalic_i , w , yitalic_i , l ) i ∈ [ n ], where (yi,w,yi,l)subscriptwsubscriptl(y_i, w,y_i, l)( yitalic_i , w , yitalic_i , l ) are two responses to xisubscriptx_ixitalic_i generated by a pre-trained model πθsubscriptπ_θπitalic_θ, and the preference yi,w≻yi,lsucceedssubscriptwsubscriptly_i, w y_i, lyitalic_i , w ≻ yitalic_i , l is obtained by human comparison (here “w w” stands for “win” and “l l” stands for “lose” in a comparision). The goal is to fine-tune πθsubscriptπ_θπitalic_θ using pairedsubscriptpairedD_ pairedDroman_paired to better align it with human preferences. A popular method for preference optimization is Direct Preference Optimization (DPO) (Rafailov et al., 2024), which minimizes ℒDPO,β(θ)=−1βpaired[logσ(βlogπθ(yw∣x)πref(yw∣x)−βlogπθ(yl∣x)πref(yl∣x))].subscriptℒDPO1subscriptsubscriptpaireddelimited-[]subscriptconditionalsubscriptwsubscriptrefconditionalsubscriptwsubscriptconditionalsubscriptlsubscriptrefconditionalsubscriptlL_DPO,β(θ)=- 1βE_% D_ paired [ σ (β π_% θ(y_ w x)π_ref(y_ w x)-β% π_θ(y_ l x)π_ref(y_ l% x) ) ].Lroman_DPO , β ( θ ) = - divide start_ARG 1 end_ARG start_ARG β end_ARG blackboard_ED start_POSTSUBSCRIPT paired end_POSTSUBSCRIPT [ log σ ( β log divide start_ARG πitalic_θ ( yroman_w ∣ x ) end_ARG start_ARG πroman_ref ( yroman_w ∣ x ) end_ARG - β log divide start_ARG πitalic_θ ( yroman_l ∣ x ) end_ARG start_ARG πroman_ref ( yroman_l ∣ x ) end_ARG ) ] . (2) Here, σ(t)=1/(1+e−t)11superscriptσ(t)=1/(1+e^-t)σ ( t ) = 1 / ( 1 + e- t ) is the sigmoid function, β>00β>0β > 0 is the inverse temperature, and πrefsubscriptrefπ_refπroman_ref is a reference model. Unlearning as preference optimization. We observe that the unlearning problem can be cast into the preference optimization framework by treating each (xi,yi)∈FGsubscriptsubscriptsubscriptFG(x_i,y_i) _FG( xitalic_i , yitalic_i ) ∈ Droman_FG as only providing a negative response yi,l=yisubscriptlsubscripty_i, l=y_iyitalic_i , l = yitalic_i without any positive response yi,wsubscriptwy_i, wyitalic_i , w. Therefore, we ignore the ywsubscriptwy_ wyroman_w term in DPO in Eq. (2) and obtain the Negative Preference Optimization (NPO) loss: ℒNPO,β(θ)=−2βFG[logσ(−βlogπθ(y|x)πref(y|x))]=2βFG[log(1+(πθ(y|x)πref(y|x))β)].subscriptℒNPO2subscriptsubscriptFGdelimited-[]subscriptconditionalsubscriptrefconditional2subscriptsubscriptFGdelimited-[]1superscriptsubscriptconditionalsubscriptrefconditionalL_NPO,β(θ)=- 2βE_% D_FG [ σ (-β π_% θ(y|x)π_ref(y|x) ) ]= 2β% E_D_FG [ (1+ ( % π_θ(y|x)π_ref(y|x) )^β )% ].Lroman_NPO , β ( θ ) = - divide start_ARG 2 end_ARG start_ARG β end_ARG blackboard_ED start_POSTSUBSCRIPT FG end_POSTSUBSCRIPT [ log σ ( - β log divide start_ARG πitalic_θ ( y | x ) end_ARG start_ARG πroman_ref ( y | x ) end_ARG ) ] = divide start_ARG 2 end_ARG start_ARG β end_ARG blackboard_ED start_POSTSUBSCRIPT FG end_POSTSUBSCRIPT [ log ( 1 + ( divide start_ARG πitalic_θ ( y | x ) end_ARG start_ARG πroman_ref ( y | x ) end_ARG )β ) ] . (3) Minimizing ℒNPO,βsubscriptℒNPOL_NPO,βLroman_NPO , β ensures that the prediction probability on the forget set πθ(yi|xi)subscriptconditionalsubscriptsubscriptπ_θ(y_i|x_i)πitalic_θ ( yitalic_i | xitalic_i ) is as small as possible, aligning with the goal of unlearning the forget set. Connection with gradient ascent. We can recover the GA loss from NPO loss by eliminating the additional 1111 in the logarithm of NPO loss in Eq. (3), i.e., replacing log(1+(πθ/πref)β)1superscriptsubscriptsubscriptref (1+(π_θ/π_ref)^β)log ( 1 + ( πitalic_θ / πroman_ref )β ) to log((πθ/πref)β)superscriptsubscriptsubscriptref ((π_θ/π_ref)^β)log ( ( πitalic_θ / πroman_ref )β ). Furthermore, we show that the NPO loss also reduces to the GA loss in the limit of β→0→0β→ 0β → 0, indicating that NPO is a strict generalization of GA. Proposition 1 (NPONPONPONPO reduces to GAGAGAGA as β→0→0β→ 0β → 0). For any θ, we have limβ→0[ℒNPO,β(θ)−2βlog2]=ℒGA(θ)−FG[logπref(y∣x)]⏟does not depend onθ.subscript→0delimited-[]subscriptℒNPO22subscriptℒGAsubscript⏟subscriptsubscriptFGdelimited-[]subscriptrefconditionaldoes not depend on _β→ 0 [L_NPO,β(% θ)- 2β 2 ]=L_GA(θ)% - E_D_ FG[ π_ref(y% x)]_ does not depend on~θ.limitalic_β → 0 [ Lroman_NPO , β ( θ ) - divide start_ARG 2 end_ARG start_ARG β end_ARG log 2 ] = Lroman_GA ( θ ) - under⏟ start_ARG blackboard_ED start_POSTSUBSCRIPT FG end_POSTSUBSCRIPT [ log πroman_ref ( y ∣ x ) ] end_ARGdoes not depend on θ . Moreover, assuming πθ(y∣x)subscriptconditionalπ_θ(y x)πitalic_θ ( y ∣ x ) is differentiable with respect to θ, we have limβ→0∇θℒNPO,β(θ)=∇θℒGA(θ).subscript→0subscript∇subscriptℒNPOsubscript∇subscriptℒGA _β→ 0 _θL_NPO,% β(θ)= _θL_GA(θ).limitalic_β → 0 ∇θ Lroman_NPO , β ( θ ) = ∇θ Lroman_GA ( θ ) . The proof of Proposition 1 is deferred to Appendix A.1. Figure 3 provides an illustration of the reduction from the NPONPONPONPO loss to the GAGAGAGA loss as β→0→0β→ 0β → 0. Figure 3: Retain distance versus forget distance for GAGAGAGA and NPONPONPONPO with varying levels of β in the binary classification experiment with α=11α=1α = 1. The Pareto curves all start from the bottom right corner (1.70,0.02)1.700.02(1.70,0.02)( 1.70 , 0.02 ) and are computed by averaging over 5555 instances. We observe that the NPONPONPONPO trajectory converges to the GAGAGAGA trajectory as β→0.→0β→ 0.β → 0 . Here retain distance and forget distance denote the KL divergence between the distributions of the predictions of the retrained and the unlearned model, on the retain and the forget distribution, respectively. More details can be found in Section 4. Stability of the NPONPONPONPO loss. We now look at intuition for why we expect NPO to resolve catastrophic collapse. One limitation of the GA loss is its unboundedness from below (as the negation of the cross-entropy prediction loss which is unbounded from above). The NPO loss resolves this issue and remains lower-bounded for any finite β>00β>0β > 0. Furthermore, the gradients of NPO and GA are as follows: ∇θℒGA=subscript∇subscriptℒGAabsent _θL_GA=∇θ Lroman_GA = FG[∇θlogπθ(y|x)],subscriptsubscriptFGdelimited-[]subscript∇subscriptconditional ~E_D_ FG[ _θ π% _θ(y|x)],blackboard_ED start_POSTSUBSCRIPT FG end_POSTSUBSCRIPT [ ∇θ log πitalic_θ ( y | x ) ] , (4) ∇θℒNPO,β=subscript∇subscriptℒNPOabsent _θL_NPO,β=∇θ Lroman_NPO , β = FG[θ(x,y)∇θlogπθ(y|x)],subscriptsubscriptFGdelimited-[]subscriptsubscript∇subscriptconditional ~E_D_ FG[ W_θ(x,% y) _θ π_θ(y|x)],blackboard_ED start_POSTSUBSCRIPT FG end_POSTSUBSCRIPT [ sansserif_Wθ ( x , y ) ∇θ log πitalic_θ ( y | x ) ] , (5) where θ(x,y)=2πθβ(y|x)/[πθβ(y|x)+πrefβ(y|x)]subscript2superscriptsubscriptconditionaldelimited-[]superscriptsubscriptconditionalsuperscriptsubscriptrefconditional W_θ(x,y)=2π_θ^β(y|x) /[π_% θ^β(y|x)+π_ref^β(y|x)]sansserif_Wθ ( x , y ) = 2 πitalic_θitalic_β ( y | x ) / [ πitalic_θitalic_β ( y | x ) + πroman_refitalic_β ( y | x ) ] can be interpreted as an adaptive smoothing weight—When example (x,y)∈FGsubscriptFG(x,y)∈D_ FG( x , y ) ∈ Droman_FG is already unlearned in the sense that πθ(y|x)≪πref(y|x)much-less-thansubscriptconditionalsubscriptrefconditionalπ_θ(y|x) π_ref(y|x)πitalic_θ ( y | x ) ≪ πroman_ref ( y | x ), we have θ(x,y)≪1much-less-thansubscript1 W_θ(x,y) 1sansserif_Wθ ( x , y ) ≪ 1, so that ‖∇θℒNPO,β‖2≪‖∇θℒGA‖2much-less-thansubscriptnormsubscript∇subscriptℒNPO2subscriptnormsubscript∇subscriptℒGA2 \| _θL_NPO,β \|_2 % \| _θL_GA \|_2∥ ∇θ Lroman_NPO , β ∥2 ≪ ∥ ∇θ Lroman_GA ∥2 and thus NPO could diverge much slower than GA. 3.1 Theoretical analysis of divergence speed We formalize the above intuition by theoretically analyzing the divergence speed of NPO and GA in a standard logistic regression setting. We consider a binary classification problem (y∈0,101y∈\0,1\y ∈ 0 , 1 ) with a logistic model πθ(y=1|x)=sigmoid(⟨x,θ⟩)subscriptconditional1sigmoidπ_θ(y=1|x)= sigmoid( x,θ )πitalic_θ ( y = 1 | x ) = sigmoid ( ⟨ x , θ ⟩ ). The initial model is denoted as πθinitsubscriptsubscriptinitπ_θ_initπitalic_θ start_POSTSUBSCRIPT init end_POSTSUBSCRIPT with θinit∈ℝdsubscriptinitsuperscriptℝθ_init ^dθroman_init ∈ blackboard_Rd. We aim to unlearn a forget set FG=(xi,yi)i=1nfsubscriptFGsuperscriptsubscriptsubscriptsubscript1subscriptfD_ FG=\(x_i,y_i)\_i=1^n_fDroman_FG = ( xitalic_i , yitalic_i ) i = 1nroman_f by minimizing either GA or NPO loss using gradient descent with stepsize η for T iterations. Theorem 2 (Divergence speed of GAGAGAGA and NPONPONPONPO). Let X:=(x1,…,xnf)⊤∈ℝnf×d.assignsuperscriptsubscript1…subscriptsubscriptftopsuperscriptℝsubscriptfX:=(x_1,…,x_n_f) ^n_f% ×d.X := ( x1 , … , xitalic_n start_POSTSUBSCRIPT f end_POSTSUBSCRIPT )⊤ ∈ blackboard_Rnroman_f × d . Consider the high-dimensional regime where nf≤dsubscriptfn_f≤dnroman_f ≤ d and assume XX⊤superscripttopXX X X⊤ is invertible. Suppose ‖θinit‖2≤Bθsubscriptnormsubscriptinit2subscript\|θ_init\|_2≤B_θ∥ θroman_init ∥2 ≤ Bitalic_θ, ‖xi‖2∈[bx,Bx]subscriptnormsubscript2subscriptsubscript\|x_i\|_2∈[b_x,B_x]∥ xitalic_i ∥2 ∈ [ bitalic_x , Bitalic_x ] for all i∈[nf]delimited-[]subscriptfi∈[n_f]i ∈ [ nroman_f ] for some Bθ,bx,Bx>0subscriptsubscriptsubscript0B_θ,b_x,B_x>0Bitalic_θ , bitalic_x , Bitalic_x > 0. Let θGA(t),θNPO(t)subscriptsuperscriptGAsubscriptsuperscriptNPOθ^(t)_GA,θ^(t)_NPOθ( t )GA , θ( t )NPO denote the t-th iterates of gradient descent with stepsize η on the empirical loss ℒGA,ℒNPO,βsubscriptℒGAsubscriptℒNPOL_GA,L_NPO,βLroman_GA , Lroman_NPO , β, respectively. • (GAGAGAGA diverges linearly) There exist some (Bθ,bx,Bx)subscriptsubscriptsubscript(B_θ,b_x,B_x)( Bitalic_θ , bitalic_x , Bitalic_x )-dependent constants C0,C1,C2>0subscript0subscript1subscript20C_0,C_1,C_2>0C0 , C1 , C2 > 0 such that when maxi≠j|⟨xi,xj⟩|≤C0/nfsubscriptsubscriptsubscriptsubscript0subscriptf _i≠ j| x_i,x_j |≤C_0/n_fmaxitalic_i ≠ j | ⟨ xitalic_i , xitalic_j ⟩ | ≤ C0 / nroman_f, ‖θGA(t)−θinit‖X⊤X∈[C1⋅nf−1/2η⋅t,C2⋅nf−1/2η⋅t],t≥1.formulae-sequencesubscriptnormsubscriptsuperscriptGAsubscriptinitsuperscripttop⋅subscript1superscriptsubscriptf12⋅subscript2superscriptsubscriptf121 \|θ^(t)_GA-θ_init\|_X^% X∈ [C_1·n_f^-1/2η· t,C_2% ·n_f^-1/2η· t ],~~~~t≥ 1.∥ θ( t )GA - θroman_init ∥X⊤ X ∈ [ C1 ⋅ nroman_f- 1 / 2 η ⋅ t , C2 ⋅ nroman_f- 1 / 2 η ⋅ t ] , t ≥ 1 . • (NPONPONPONPO diverges logarithmically) Suppose η≤11η≤ 1η ≤ 1. There exist some (Bθ,bx,Bx,β)subscriptsubscriptsubscript(B_θ,b_x,B_x,β)( Bitalic_θ , bitalic_x , Bitalic_x , β )-dependent constants C0,C1,subscript0subscript1C_0,C_1,C0 , C1 , C2,C3>0subscript2subscript30C_2,C_3>0C2 , C3 > 0 such that when maxi≠j|⟨xi,xj⟩|≤C0/nfsubscriptsubscriptsubscriptsubscript0subscriptf _i≠ j| x_i,x_j |≤C_0/n_fmaxitalic_i ≠ j | ⟨ xitalic_i , xitalic_j ⟩ | ≤ C0 / nroman_f, ‖θNPO(t)−θinit‖X⊤X∈[C1nflog(C2⋅ηnf−1⋅t+1),C1nflog(C3⋅ηnf−1⋅t+1)],∀t≥1.formulae-sequencesubscriptnormsubscriptsuperscriptNPOsubscriptinitsuperscripttopsubscript1subscriptf⋅subscript2superscriptsubscriptf11subscript1subscriptf⋅subscript3superscriptsubscriptf11for-all1 \|θ^(t)_NPO-θ_init\|_X^% X∈ [C_1 n_f (C_2·% ηn_f^-1· t+1 ),C_1 n_f% (C_3·ηn_f^-1· t+1 ) ],~% ∀ t≥ 1.∥ θ( t )NPO - θroman_init ∥X⊤ X ∈ [ C1 square-root start_ARG nroman_f end_ARG log ( C2 ⋅ η nroman_f- 1 ⋅ t + 1 ) , C1 square-root start_ARG nroman_f end_ARG log ( C3 ⋅ η nroman_f- 1 ⋅ t + 1 ) ] , ∀ t ≥ 1 . Theorem 2 demonstrates that NPO diverges exponentially slower than GA in a simple setting. The proof of Theorem 2 is contained in Appendix A.2. 4 Synthetic Experiments 4.1 Setup Dataset. We consider a forget set FG=(xif,yif)i=1200subscriptFGsuperscriptsubscriptsubscriptsuperscriptfsubscriptsuperscriptf1200D_ FG=\(x^f_i,y^f_i)\_i=1^200Droman_FG = ( xroman_fitalic_i , yroman_fitalic_i ) i = 1200 and a retain set RT=(xir,yir)i=11000,subscriptRTsuperscriptsubscriptsubscriptsuperscriptrsubscriptsuperscriptr11000D_ RT=\(x^r_i,y^r_i)\_i=1^10% 00,Droman_RT = ( xroman_ritalic_i , yroman_ritalic_i ) i = 11000 , which are both generated from Gaussian-logistic models. More specifically, we assume xif∼iid(μf,d),ℙ(yif=1|xif)=sigmoid((xif−μf)⊤θf+1),formulae-sequencesubscriptsimilar-tosubscriptsuperscriptfsubscriptfsubscriptℙsubscriptsuperscriptfconditional1subscriptsuperscriptfsigmoidsuperscriptsubscriptsuperscriptfsubscriptftopsubscriptf1 x^f_i _iidN( _f, % I_d),~~~P(y^f_i=1|x^f_i)= sigmoid% ((x^f_i- _f) θ_f+1),xroman_fitalic_i ∼i i d N ( μroman_f , Iitalic_d ) , blackboard_P ( yroman_fitalic_i = 1 | xroman_fitalic_i ) = sigmoid ( ( xroman_fitalic_i - μroman_f )⊤ θroman_f + 1 ) , (6) xir∼iid(μr,d),ℙ(yir=1|xir)=sigmoid((xir−μr)⊤θr−1).formulae-sequencesubscriptsimilar-tosubscriptsuperscriptrsubscriptrsubscriptℙsubscriptsuperscriptrconditional1subscriptsuperscriptrsigmoidsuperscriptsubscriptsuperscriptrsubscriptrtopsubscriptr1 x^r_i _iidN( _r, % I_d),~~~P(y^r_i=1|x^r_i)= sigmoid% ((x^r_i- _r) θ_r-1).xroman_ritalic_i ∼i i d N ( μroman_r , Iitalic_d ) , blackboard_P ( yroman_ritalic_i = 1 | xroman_ritalic_i ) = sigmoid ( ( xroman_ritalic_i - μroman_r )⊤ θroman_r - 1 ) . Here we choose d=1616d=16d = 16, θf=−θr=d/dsubscriptfsubscriptrsubscript1θ_f=-θ_r=1_d/ dθroman_f = - θroman_r = 1italic_d / square-root start_ARG d end_ARG, and μf=−μr=α⋅dsubscriptfsubscriptr⋅subscript1 _f=- _r=α·1_dμroman_f = - μroman_r = α ⋅ 1italic_d for some α≥00α≥ 0α ≥ 0. We consider two choices of the hyper-parameter α: (1). α=11α=1α = 1, which creates a gap between the Gaussian means of forget covariates xifsubscriptsuperscriptf\x^f_i\ xroman_fitalic_i and retain covariates xirsubscriptsuperscriptr\x^r_i\ xroman_ritalic_i ; (2). α=00α=0α = 0, which implies that covariates in the forget and retain set are both isotropic Gaussian. We remark that we shift by 1111 in the sigmoid function to create a discrepancy in the label frequencies between the forget and retain sets — this ensures that the forget labels yifsubscriptsuperscriptfy^f_iyroman_fitalic_i are more likely to be 1111, while the retain labels yirsubscriptsuperscriptry^r_iyroman_ritalic_i are more likely to be 00. Model and training method. We consider a random feature model πθ(y=1|x)=sigmoid(θ⊤ReLU(Wx))subscriptconditional1sigmoidsuperscripttopReLUWxπ_θ(y=1|x)= sigmoid(θ ReLU(Wx))πitalic_θ ( y = 1 | x ) = sigmoid ( θ⊤ ReLU ( Wx ) ), where W∈ℝ128×dsuperscriptℝ128W ^128×dW ∈ blackboard_R128 × d is fixed during the training and unlearning process, whose entries are generated i.i.d. from (0,1/d)01N(0,1/d)N ( 0 , 1 / d ), and θ∈ℝ128superscriptℝ128θ ^128θ ∈ blackboard_R128 is the trainable parameter. To generate the initial model πrefsubscriptrefπ_refπroman_ref and the retrained model πretrsubscriptretrπ_ retrπroman_retr, we optimize over θ using the cross-entropy loss over the entire dataset =FG∪RTsubscriptFGsubscriptRTD=D_ FG∪D_ RTD = Droman_FG ∪ Droman_RT and the retain dataset RTsubscriptRTD_ RTDroman_RT, respectively. In the unlearning phase, starting from the initial model πrefsubscriptrefπ_refπroman_ref, we perform gradient descent on various loss functions for 2000200020002000 steps. We select the learning rate for each method via grid search. Unlearning methods. We evaluate the performance of vanilla NPONPONPONPO (NPONPONPONPO; minimizing ℒNPOsubscriptℒNPOL_NPOLroman_NPO), NPONPONPONPO plus a retain loss term (NPONPONPONPO+RTRTRTRT; minimizing ℒNPOsubscriptℒNPOL_NPOLroman_NPO+ℒRTsubscriptℒRTL_RTLroman_RT), gradient ascent (GAGAGAGA; minimizing ℒGAsubscriptℒGAL_GALroman_GA), gradient ascent plus a retain loss term (GAGAGAGA+RTRTRTRT; minimizing ℒGAsubscriptℒGAL_GALroman_GA+ℒRTsubscriptℒRTL_RTLroman_RT), cross-entropy loss of forget and retain sets where the positive labels of the forget set are given by Bern(0.5)Bern0.5Bern(0.5)Bern ( 0.5 ) (IDKIDKIDKIDK+RTRTRTRT; minimizing ℒFGsubscriptℒFGL_FGLroman_FG+ℒRTsubscriptℒRTL_RTLroman_RT), and DPO plus a retain loss term (DPODPODPODPO+RTRTRTRT; minimizing ℒDPOsubscriptℒDPOL_DPOLroman_DPO+ℒRTsubscriptℒRTL_RTLroman_RT, where the positive labels are given by Bern(0.5)Bern0.5Bern(0.5)Bern ( 0.5 )). We conduct the grid search to select the optimal β for NPONPONPONPO-based and DPODPODPODPO-based methods. We note that GAGAGAGA-based methods are sensitive to the choice of learning rates, and therefore, we select the learning rates so that the training remains stable within 2000200020002000 steps. Evaluation metrics: forget distance and retain distance. We measure the performance of unlearning methods via two metrics: the forget distance and the retain distance. The forget distance is FG(πretr(⋅|x)||πθ(⋅|x))E_D_ FG D(π_ retr(·|x)|% |π_θ(·|x))blackboard_ED start_POSTSUBSCRIPT FG end_POSTSUBSCRIPT sansserif_D ( πroman_retr ( ⋅ | x ) | | πitalic_θ ( ⋅ | x ) ), the KL divergence between the retrained model πretrsubscriptretrπ_ retrπroman_retr and unlearned model πθsubscriptπ_θπitalic_θ on the forget set. Similarly, the retain distance is given by RT(πretr(⋅|x)||πθ(⋅|x))E_D_ RT D(π_ retr(·|x)|% |π_θ(·|x))blackboard_ED start_POSTSUBSCRIPT RT end_POSTSUBSCRIPT sansserif_D ( πroman_retr ( ⋅ | x ) | | πitalic_θ ( ⋅ | x ) ). Ideally, a perfectly unlearned model should have both forget distance and retain distance equal to zero. 4.2 Results NPO avoids catastrophic collapse. As illustrated in Figure 4 (a1) and (a2), all methods except for IDKIDKIDKIDK+RTRTRTRT reach a small forget distance (less than 0.0050.0050.0050.005) within 1200120012001200 steps. On the other hand, the retain distances of GAGAGAGA and GAGAGAGA+RTRTRTRT diverge (the catastrophic collapse) as unlearning proceeds, while the retain distances of NPONPONPONPO+RTRTRTRT and DPODPODPODPO+RTRTRTRT slowly increase and stabilize. This suggests that NPONPONPONPO+RTRTRTRT and DPODPODPODPO+RTRTRTRT are more stable compared with GAGAGAGA-based methods, in accordance with the theoretical findings in Theorem 2. NPO+RT achieves a better Pareto frontier. Figure 4 (a3) shows that NPONPONPONPO+RTRTRTRT outperforms other baseline methods by achieving a better Pareto frontier. Furthermore, when restricting to methods that do not use the retain set, NPONPONPONPO also outperforms the baseline method GAGAGAGA. Figure 4 (b) illustrates the α=00α=0α = 0 scenario where the covariate distributions for forget and retain sets are identical, resulting in equal forget and retain distances. In this scenario, NPONPONPONPO+RTRTRTRT also attains the smallest forget and retain distances. Figure 4: Forget distance and retain distance versus optimization steps for α=11α=1α = 1 (a1, a2, a3) and α=00α=0α = 0 (b). Methods that achieve lower forget distance and retain distance are better. The errorbars in (a1, a2, b) denote the ±1plus-or-minus1± 1± 1 standard deviation over 5555 instances. The Pareto curves in (a3) all start from the bottom right corner (1.70,0.02)1.700.02(1.70,0.02)( 1.70 , 0.02 ), and are averaged over 5555 instances. 5 Experiments on the TOFU Data 5.1 Experimental setup Dataset and metrics. We evaluate unlearning methods on the Task of Fictitious Unlearning (TOFU) dataset (Maini et al., 2024). It contains 200 fictitious author profiles, each consisting of 20 question-answer pairs generated by GPT-4 based on some predefined attributes. These fictitious profiles do not exist in the pre-training data, providing a controlled environment for studying unlearning LLMs. TOFU introduces three levels of tasks, each aiming to forget 1% , 5% , and 10% of the data, referred to as Forget01, Forget05, and Forget10, respectively. We measure the effectiveness of unlearning methods via Forget Quality and Model Utility as in Maini et al. (2024). Forget quality assesses how well the unlearned model mimics the retrained model (defined as the model trained only on the retain set), while model utility measures the general capacities and the real-world knowledge of the unlearned model. Since the forget quality is defined as the p-value of the Kolmogorov-Smirnov test, which tests the similarity between some distributions generated by the unlearned model and the retrained one, we treat a forget quality greater than 0.050.050.050.05 as evidence of a meaningful forgetting. More details are deferred to Section D.1.1 and Section D.1.2. Unlearning methods. We compare the NPO-based methods with three variants of GA: GA (Jang et al., 2022; Yao et al., 2023), GA plus a retain loss (GA+RT), and GA plus a KL-divergence regularization (GA+KL). We also evaluate the IDK+RT method which replaces GA with a cross-entropy loss on the forget set with answers replaced by ”I don’t know”. Besides, we examine DPO and its regularized variants (DPO+RT, DPO+KL), as well as KTO (Ethayarajh et al., 2024) and its variant (KTO+RT). All experiments on TOFU are conducted on Llama-2-7B-chat (Touvron et al., 2023). See Section D.1 for more details. Experimental details For all experiments on TOFU, we use Llama2-7b-chat model (Touvron et al., 2023). All experiments are conducted with two A100 GPUs. We use AdamW with a weight decay of 0.010.010.010.01 and a learning rate of 10−5superscript10510^-510- 5 in all finetuning, retraining, and unlearning experiments, which agrees with the setting in Maini et al. (2024). We use an effective batch size of 32323232 for all experiments. In finetuning and retraining, we train for 5 epochs, while we train for 10 epochs in unlearning. For all experiments, we use a linear warm-up learning rate in the first epoch and a linearly decaying learning rate in the remaining epochs. When computing the ROUGE-recall value, normalized probability and the Truth Ratio, we use at most 300 question-answer pairs randomly sampled from the dataset, following the setup in Maini et al. (2024). 5.2 Results NPO-based methods achieve the best trade-off. Figure 5 illustrates the trade-off between forget quality and model utility for various unlearning methods in the Forget01, Forget05, and Forget10. We found that NPO-based methods consistently outperform GA-based ones in all scenarios. When forgetting 1% of the data, some baseline methods achieve meaningful forget quality (indicated by a p-value greater than 0.05). Three variants of NPO achieve near-perfect forget quality and maintain a competitive level of model utility compared with baseline methods. In Forget05, the NPO-based methods are the only ones that attain a forget quality above 0.05. Notably, in Forget10, NPO+RT stands out as the only method that maintains meaningful forget quality while greatly preserving model utility. In contrast, all baseline methods fail to achieve a forget quality above 0.05. Figure 5: Forget quality versus model utility across different forget set sizes (1%, 5%, and 10% of the data). Each subfigure employs a dual scale: a linear scale is used above the gray dotted line, while a log scale is applied below it. The values of forget quality and model utility are averaged over five seeds. Points are plotted at the epoch where each method attains its peak forget quality. NPO avoids catastrophic collapse. Figure 6 illustrates the evolution of forget quality and model utility along the unlearning process. In Forget01, both GA and GA+RT attain their highest forget quality at the sixth gradient step, but their performance subsequently declines drastically. Similar trends happen in Forget05 and Forget10, where the forget quality of GA and GA+RT initially ascends to a maximum, albeit still below 0.05, before rapidly diminishing to an exponentially small magnitude. Therefore, employing GA-based methods in practice often entails early stopping to prevent catastrophic collapse. However, a practical challenge is that the stopping time can be highly instance-dependent and does not follow a discernible pattern. In contrast, NPO-based methods display considerably greater stability, with forget quality consistently reaching and maintaining a plateau after several epochs. Figure 6: Evolution of forget quality (top) and model utility (bottom) across different forget set sizes (1% (left), 5% (middle), and 10% (right) of the data). Each line is averaged over 5 seeds. Each figure in the top row employs a dual scale as in Figure 5. In Forget01, we evaluate the performance of the unlearned model in every gradient step, while in Forget05 and Forget10, we evaluate it in every epoch. Figure 7: Sampled response to questions in three subsets of TOFU. Yellow: questions; Green: true answer or desired answers; Red: undesired answers. NPO improved diversity and readability. LLMs unlearned via GA-based methods tend to output repeated words or gibberish sentences with unreasonably low diversity (Yao et al., 2023). Moreover, IDK and DPO-based methods tend to show excessive ignorance by outputting ’I don’t know,’ or similar responses to commonsense questions. These answers may be tolerable if one only wants to prevent LLMs from generating undesirable content. Still, they will definitely be unsatisfactory under the stronger goal of approximate unlearning, which aims to mimic the retrained model. We show in Figure 7 that NPO+RT outputs incorrect sentences with similar templates for questions in the forget set while generating fluent and correct answers for other questions, greatly enhancing the fluency and diversity of the generated content. The role of retain loss. Maini et al. (2024) demonstrated that methods incorporating a retain set outperform those that solely optimize a loss function based on the forget set. To further investigate the role of retain loss beyond Maini et al. (2024), we evaluate NPO+RT with the weights of the retain loss varying from 0 to 5 (Figure 8). While it is natural that adding retain loss improves the model utility, we are surprised that the forget quality also grows. Specifically, the forget quality increases as the weight of the retain loss grows from 0 to 2. We conjecture that the retain loss term helps the model preserve answer templates and linguistic structures, while the NPO term forces the model to forget some specific facts. Combining these two effects pushes the model to approximate the retrained model by generating outputs with similar templates but incorrect entities. However, further increasing the weight of the retain loss (e.g., from 2 to 5, in Figure 8) leads to a drop in the forget quality, possibly due to the diminished scale of the NPO term. Notably, in our experiments, the retain loss plays a more significant role when we target forgetting a larger fraction of the data (See the middle and right panels of Figure 6). Figure 8: The evolution of the forget quality and model utility when we tune the weights of the NPO term and the retain loss term in NPO+RT. The experiments are performed on Forget10. We observe that when we increase the weight for the retain loss term, the model utility increases monotonically while the forget quality initially improves but then starts to deteriorate. We remark that altering the weights for loss components does not affect the effective learning rate since, in practice, AdamW is scale-invariant. Forget KL: The larger, the better? ✖ ✖ ✖ We also examine the Forget KL during the unlearning process in the TOFU dataset. We first observed that while GA and GA+RT tend to induce an explosively large Forget KL along the unlearning process, the NPO-based approaches induce a much slower growth of Forget KL (Figure 9). It stabilizes at a moderate level even after several epochs. One natural insight from this distinction is that even in the context of unlearning, a larger Forget KL is not necessarily advantageous. Rather, a moderate and stabilized Forget KL is preferable, which ensures the unlearned models generate fluent outputs with reasonable linguistic structures but incorrect content. This also suggests that Forget KL may not be a suitable objective function to maximize for unlearning LLMs, contrary to what was done in some prior literature (Chen & Yang, 2023). Figure 9: The evolution of the Forget KL during the unlearning process on the Forget10 task in TOFU data. Note that the KL term in GA+KL is the divergence on the retain set, not the forget set. More experimental details are included in Section D.1. 5.3 Forgetting beyond 10% of TOFU Forgetting 20%, 30% and 50% of TOFU. Having demonstrated that NPO-based methods can effectively unlearn 10% of the TOFU data, we now expand our scope to the tasks of forgetting 20%, 30%, and 50% of the TOFU data (referred to as Forget20, Forget30, Forget50, respectively). Details about the extended dataset are deferred to Section D.1.1. We show in Section D.2 that NPO+RT is the sole method to exhibit meaningful forget quality (a p-value above 0.05) in Forget20 and Forget30. Even in Forget50, where the vanilla NPO+RT achieves a forget quality around 10−3superscript10310^-310- 3, it still significantly outperforms other methods. Pushing towards the limit: forgetting 50% - 90% of TOFU. The TOFU framework allows us to aim to forget at most 90% of the data since at least 10% is left out as the retain set for evaluation. We thus ask the question of whether there exist methods that could effectively forget 50%-90% of the TOFU data. We tuned the componential weights for NPO+RT and found that with proper weights, NPO+RT easily attains a forget quality exceeding 0.05 and model utility above 0.55 on Forget50 and Forget90, as reported in Figure 10. Figure 10: Evolution of forget quality and model utility on Forget50 and Forget90 for NPO+RT with proper componential weights between loss terms. We tune the coefficient of the retain loss term and keep a unit coefficient for the NPO term. For Forget50, we set the coefficient of the retain loss term to be 5.05.05.05.0 while in Forget90, we set 12.012.012.012.0. 6 Conclusion We propose Negative Preference Optimization (NPO), a simple objective for LLM unlearning. NPO makes steps towards addressing the catastrophic collapse issue in the gradient ascent method. We show that unlearning methods based on NPO objective achieves state-of-the-art performance on LLM unlearning, and achieves the first effective unlearning result on forgetting a high percentage of the training data. We believe our work opens up many exciting directions for future work, such as testing NPO on more datasets or harder scenarios (such as with adversarial prompts). It may also be of interest to generalize the algorithm principle of NPO (preference optimization with negative examples only) to other problems beyond unlearning. Acknowledgement Song Mei is supported by NSF DMS-2210827, CCF-2315725, NSF Career DMS-2339904, ONR N00014-24-S-B001, an Amazon Research Award, and a Google Research Scholar Award. The authors would like to thank Baihe Huang, Xuelin Yang for the valuable discussions. The authors would like to thank Jiantao Jiao for sharing his GPU resources. This research was supported by the Center for AI Safety Compute Cluster. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the sponsors. References Bai et al. (2022) Yuntao Bai, Andy Jones, Kamal Ndousse, Amanda Askell, Anna Chen, Nova DasSarma, Dawn Drain, Stanislav Fort, Deep Ganguli, Tom Henighan, et al. Training a helpful and harmless assistant with reinforcement learning from human feedback. arXiv preprint arXiv:2204.05862, 2022. Bourtoule et al. (2021) 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), p. 141–159. IEEE, 2021. Cao & Yang (2015) Yinzhi Cao and Junfeng Yang. Towards making systems forget with machine unlearning. In 2015 IEEE symposium on security and privacy, p. 463–480. IEEE, 2015. Carlini et al. (2021) 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), p. 2633–2650, 2021. Carlini et al. (2022) Nicholas Carlini, Daphne Ippolito, Matthew Jagielski, Katherine Lee, Florian Tramer, and Chiyuan Zhang. Quantifying memorization across neural language models. arXiv preprint arXiv:2202.07646, 2022. CCPA (2018) CCPA. California consumer privacy act of 2018. https://leginfo.legislature.ca.gov/faces/billTextClient.xhtml?bill_id=201720180AB375, 2018. AB-375, Signed into law on June 28, 2018. Chen & Yang (2023) Jiaao Chen and Diyi Yang. Unlearn what you want to forget: Efficient unlearning for llms. arXiv preprint arXiv:2310.20150, 2023. Duan et al. (2024) Shitong Duan, Xiaoyuan Yi, Peng Zhang, Tun Lu, Xing Xie, and Ning Gu. Negating negatives: Alignment without human positive samples via distributional dispreference optimization. arXiv preprint arXiv:2403.03419, 2024. Eldan & Russinovich (2023) Ronen Eldan and Mark Russinovich. Who’s harry potter? approximate unlearning in llms. arXiv preprint arXiv:2310.02238, 2023. Ethayarajh et al. (2024) Kawin Ethayarajh, Winnie Xu, Niklas Muennighoff, Dan Jurafsky, and Douwe Kiela. Kto: Model alignment as prospect theoretic optimization. arXiv preprint arXiv:2402.01306, 2024. Ginart et al. (2019) Antonio Ginart, Melody Guan, Gregory Valiant, and James Y Zou. Making ai forget you: Data deletion in machine learning. Advances in neural information processing systems, 32, 2019. Golatkar et al. (2020) Aditya Golatkar, Alessandro Achille, and Stefano Soatto. Eternal sunshine of the spotless net: Selective forgetting in deep networks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, p. 9304–9312, 2020. Guo et al. (2019) Chuan Guo, Tom Goldstein, Awni Hannun, and Laurens Van Der Maaten. Certified data removal from machine learning models. arXiv preprint arXiv:1911.03030, 2019. Huang et al. (2022) Jie Huang, Hanyin Shao, and Kevin Chen-Chuan Chang. Are large pre-trained language models leaking your personal information? arXiv preprint arXiv:2205.12628, 2022. Izzo et al. (2021) Zachary Izzo, Mary Anne Smart, Kamalika Chaudhuri, and James Zou. Approximate data deletion from machine learning models. In International Conference on Artificial Intelligence and Statistics, p. 2008–2016. PMLR, 2021. Jang et al. (2022) Joel Jang, Dongkeun Yoon, Sohee Yang, Sungmin Cha, Moontae Lee, Lajanugen Logeswaran, and Minjoon Seo. Knowledge unlearning for mitigating privacy risks in language models. arXiv preprint arXiv:2210.01504, 2022. Ji et al. (2024) Jiaming Ji, Mickel Liu, Josef Dai, Xuehai Pan, Chi Zhang, Ce Bian, Boyuan Chen, Ruiyang Sun, Yizhou Wang, and Yaodong Yang. Beavertails: Towards improved safety alignment of llm via a human-preference dataset. Advances in Neural Information Processing Systems, 36, 2024. Koh & Liang (2017) Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions. In International conference on machine learning, p. 1885–1894. PMLR, 2017. Li et al. (2024) Nathaniel Li, Alexander Pan, Anjali Gopal, Summer Yue, Daniel Berrios, Alice Gatti, Justin D Li, Ann-Kathrin Dombrowski, Shashwat Goel, Long Phan, et al. The wmdp benchmark: Measuring and reducing malicious use with unlearning. arXiv preprint arXiv:2403.03218, 2024. Lin (2004) Chin-Yew Lin. Rouge: A package for automatic evaluation of summaries. In Text summarization branches out, p. 74–81, 2004. Liu et al. (2024a) 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, 2024a. Liu et al. (2024b) Zheyuan Liu, Guangyao Dou, Zhaoxuan Tan, Yijun Tian, and Meng Jiang. Towards safer large language models through machine unlearning. arXiv preprint arXiv:2402.10058, 2024b. Lynch et al. (2024) Aengus Lynch, Phillip Guo, Aidan Ewart, Stephen Casper, and Dylan Hadfield-Menell. Eight methods to evaluate robust unlearning in llms. arXiv preprint arXiv:2402.16835, 2024. Maini et al. (2024) 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. Mantelero (2013) Alessandro Mantelero. The eu proposal for a general data protection regulation and the roots of the ‘right to be forgotten’. Computer Law & Security Review, 29(3):229–235, 2013. Meng et al. (2022) Kevin Meng, David Bau, Alex Andonian, and Yonatan Belinkov. Locating and editing factual associations in gpt. Advances in Neural Information Processing Systems, 35:17359–17372, 2022. Mitchell et al. (2022) Eric Mitchell, Charles Lin, Antoine Bosselut, Christopher D Manning, and Chelsea Finn. Memory-based model editing at scale. In International Conference on Machine Learning, p. 15817–15831. PMLR, 2022. Nguyen et al. (2022) Thanh Tam Nguyen, Thanh Trung Huynh, Phi Le Nguyen, Alan Wee-Chung Liew, Hongzhi Yin, and Quoc Viet Hung Nguyen. A survey of machine unlearning. arXiv preprint arXiv:2209.02299, 2022. Ouyang et al. (2022) Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to follow instructions with human feedback. Advances in Neural Information Processing Systems, 35:27730–27744, 2022. Patil et al. (2023) Vaidehi Patil, Peter Hase, and Mohit Bansal. Can sensitive information be deleted from llms? objectives for defending against extraction attacks. arXiv preprint arXiv:2309.17410, 2023. Pawelczyk et al. (2023) Martin Pawelczyk, Seth Neel, and Himabindu Lakkaraju. In-context unlearning: Language models as few shot unlearners. arXiv preprint arXiv:2310.07579, 2023. Rafailov et al. (2024) Rafael Rafailov, Archit Sharma, Eric Mitchell, Christopher D Manning, Stefano Ermon, and Chelsea Finn. Direct preference optimization: Your language model is secretly a reward model. Advances in Neural Information Processing Systems, 36, 2024. Sandbrink (2023) Jonas B Sandbrink. Artificial intelligence and biological misuse: Differentiating risks of language models and biological design tools. arXiv preprint arXiv:2306.13952, 2023. Sekhari et al. (2021) Ayush Sekhari, Jayadev Acharya, Gautam Kamath, and Ananda Theertha Suresh. Remember what you want to forget: Algorithms for machine unlearning. Advances in Neural Information Processing Systems, 34:18075–18086, 2021. Shi et al. (2023) Weijia Shi, Anirudh Ajith, Mengzhou Xia, Yangsibo Huang, Daogao Liu, Terra Blevins, Danqi Chen, and Luke Zettlemoyer. Detecting pretraining data from large language models. arXiv preprint arXiv:2310.16789, 2023. Si et al. (2023) Nianwen Si, Hao Zhang, Heyu Chang, Wenlin Zhang, Dan Qu, and Weiqiang Zhang. Knowledge unlearning for llms: Tasks, methods, and challenges. arXiv preprint arXiv:2311.15766, 2023. Stiennon et al. (2020) Nisan Stiennon, Long Ouyang, Jeffrey Wu, Daniel Ziegler, Ryan Lowe, Chelsea Voss, Alec Radford, Dario Amodei, and Paul F Christiano. Learning to summarize with human feedback. Advances in Neural Information Processing Systems, 33:3008–3021, 2020. Thudi et al. (2022) Anvith Thudi, Gabriel Deza, Varun Chandrasekaran, and Nicolas Papernot. Unrolling sgd: Understanding factors influencing machine unlearning. In 2022 IEEE 7th European Symposium on Security and Privacy (EuroS&P), p. 303–319. IEEE, 2022. Touvron et al. (2023) 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. Voigt & Von dem Bussche (2017) Paul Voigt and Axel Von dem Bussche. The eu general data protection regulation (gdpr). A Practical Guide, 1st Ed., Cham: Springer International Publishing, 10(3152676):10–5555, 2017. Wang et al. (2023) Lingzhi Wang, Tong Chen, Wei Yuan, Xingshan Zeng, Kam-Fai Wong, and Hongzhi Yin. Kga: A general machine unlearning framework based on knowledge gap alignment. arXiv preprint arXiv:2305.06535, 2023. Xu et al. (2023) Heng Xu, Tianqing Zhu, Lefeng Zhang, Wanlei Zhou, and Philip S Yu. Machine unlearning: A survey. ACM Computing Surveys, 56(1):1–36, 2023. Yao et al. (2024) Jin Yao, Eli Chien, Minxin Du, Xinyao Niu, Tianhao Wang, Zezhou Cheng, and Xiang Yue. Machine unlearning of pre-trained large language models. arXiv preprint arXiv:2402.15159, 2024. Yao et al. (2023) Yuanshun Yao, Xiaojun Xu, and Yang Liu. Large language model unlearning. arXiv preprint arXiv:2310.10683, 2023. Zhang et al. (2023) Haibo Zhang, Toru Nakamura, Takamasa Isohara, and Kouichi Sakurai. A review on machine unlearning. SN Computer Science, 4(4):337, 2023. Appendix A Proofs A.1 Proof of Proposition 1 Adopt the shorthand i=logπθ(yi∣xi)πref(yi∣xi)subscriptsubscriptconditionalsubscriptsubscriptsubscriptrefconditionalsubscriptsubscript R_i= π_θ(y_i x_i)π_% ref(y_i x_i)sansserif_Ri = log divide start_ARG πitalic_θ ( yitalic_i ∣ xitalic_i ) end_ARG start_ARG πroman_ref ( yitalic_i ∣ xitalic_i ) end_ARG. For any i∈[nf]delimited-[]subscriptfi∈[n_f]i ∈ [ nroman_f ], we have limβ→0−2β⋅logσ(−β⋅logπθ(yi∣xi)πref(yi∣xi))−2βlog2subscript→0⋅2⋅subscriptconditionalsubscriptsubscriptsubscriptrefconditionalsubscriptsubscript22 _β→ 0- 2β· σ (-% β· π_θ(y_i x_i)π_ref(y% _i x_i) )- 2β 2limitalic_β → 0 - divide start_ARG 2 end_ARG start_ARG β end_ARG ⋅ log σ ( - β ⋅ log divide start_ARG πitalic_θ ( yitalic_i ∣ xitalic_i ) end_ARG start_ARG πroman_ref ( yitalic_i ∣ xitalic_i ) end_ARG ) - divide start_ARG 2 end_ARG start_ARG β end_ARG log 2 =limβ→0−2β⋅logσ(−βi)−2βlog2absentsubscript→0⋅2subscript22 = _β→ 0- 2β· σ(-β% R_i)- 2β 2= limitalic_β → 0 - divide start_ARG 2 end_ARG start_ARG β end_ARG ⋅ log σ ( - β sansserif_Ri ) - divide start_ARG 2 end_ARG start_ARG β end_ARG log 2 =limβ→02β⋅log(1+exp(βi)2)absentsubscript→0⋅21subscript2 = _β→ 0 2β· ( 1+ % (β R_i)2 )= limitalic_β → 0 divide start_ARG 2 end_ARG start_ARG β end_ARG ⋅ log ( divide start_ARG 1 + exp ( β sansserif_Ri ) end_ARG start_ARG 2 end_ARG ) =limβ→02β⋅log(1+exp(βi)−12)absentsubscript→0⋅21subscript12 = _β→ 0 2β· (1+ % (β R_i)-12 )= limitalic_β → 0 divide start_ARG 2 end_ARG start_ARG β end_ARG ⋅ log ( 1 + divide start_ARG exp ( β sansserif_Ri ) - 1 end_ARG start_ARG 2 end_ARG ) =limβ→02β⋅exp(βi)−12absentsubscript→0⋅2subscript12 = _β→ 0 2β· (β% R_i)-12= limitalic_β → 0 divide start_ARG 2 end_ARG start_ARG β end_ARG ⋅ divide start_ARG exp ( β sansserif_Ri ) - 1 end_ARG start_ARG 2 end_ARG =i.absentsubscript = R_i.= sansserif_Ri . Averaging over all i∈[nf]delimited-[]subscriptfi∈[n_f]i ∈ [ nroman_f ] and noting that ∑i=1nfi/nf=ℒGA(θ)−FG[logπref(yi∣xi)]superscriptsubscript1subscriptfsubscriptsubscriptfsubscriptℒGAsubscriptsubscriptFGdelimited-[]subscriptrefconditionalsubscriptsubscript _i=1^n_f R_i/n_f=L_% GA(θ)-E_D_ FG[ π_% ref(y_i x_i)]∑i = 1nroman_f sansserif_Ri / nroman_f = Lroman_GA ( θ ) - blackboard_ED start_POSTSUBSCRIPT FG end_POSTSUBSCRIPT [ log πroman_ref ( yitalic_i ∣ xitalic_i ) ] yields the first part of Propostion 1. For the second part of Propostion 1, by definition ∇θℒNPO,β(θ)subscript∇subscriptℒNPO _θL_NPO,β(θ)∇θ Lroman_NPO , β ( θ ) =1nf∑i=1nf−2β∇θlogσ(−βi)absent1subscriptfsuperscriptsubscript1subscriptf2subscript∇subscript = 1n_f _i=1^n_f- 2% β _θ σ(-β R_i)= divide start_ARG 1 end_ARG start_ARG nroman_f end_ARG ∑i = 1nroman_f - divide start_ARG 2 end_ARG start_ARG β end_ARG ∇θ log σ ( - β sansserif_Ri ) =1nf∑i=1nf2β∇θlog(1+exp(βi))absent1subscriptfsuperscriptsubscript1subscriptf2subscript∇1subscript = 1n_f _i=1^n_f 2% β _θ (1+ (β R_i))= divide start_ARG 1 end_ARG start_ARG nroman_f end_ARG ∑i = 1nroman_f divide start_ARG 2 end_ARG start_ARG β end_ARG ∇θ log ( 1 + exp ( β sansserif_Ri ) ) =1nf∑i=1nf2β⋅βexp(βi)1+exp(βi)⋅∇θiabsent1subscriptfsuperscriptsubscript1subscriptf⋅2subscript1subscriptsubscript∇subscript = 1n_f _i=1^n_f 2% β· β (β R_i)1+ (β % R_i)· _θ R_i= divide start_ARG 1 end_ARG start_ARG nroman_f end_ARG ∑i = 1nroman_f divide start_ARG 2 end_ARG start_ARG β end_ARG ⋅ divide start_ARG β exp ( β sansserif_Ri ) end_ARG start_ARG 1 + exp ( β sansserif_Ri ) end_ARG ⋅ ∇θ sansserif_Ri =1nf∑i=1nf2exp(βi)1+exp(βi)⋅∇θi.absent1subscriptfsuperscriptsubscript1subscriptf⋅2subscript1subscriptsubscript∇subscript = 1n_f _i=1^n_f 2 % (β R_i)1+ (β R_i)· _θ% R_i.= divide start_ARG 1 end_ARG start_ARG nroman_f end_ARG ∑i = 1nroman_f divide start_ARG 2 exp ( β sansserif_Ri ) end_ARG start_ARG 1 + exp ( β sansserif_Ri ) end_ARG ⋅ ∇θ sansserif_Ri . Therefore, it follows immediately that limβ→0∇θℒNPO,β(θ)subscript→0subscript∇subscriptℒNPO _β→ 0 _θL_NPO,% β(θ)limitalic_β → 0 ∇θ Lroman_NPO , β ( θ ) =limβ→01nf∑i=1nf2exp(βi)1+exp(βi)⋅∇θi=1nf∑i=1nf∇θiabsentsubscript→01subscriptfsuperscriptsubscript1subscriptf⋅2subscript1subscriptsubscript∇subscript1subscriptfsuperscriptsubscript1subscriptfsubscript∇subscript = _β→ 0 1n_f _i=1^n_% f 2 (β R_i)1+ (β R_% i)· _θ R_i= 1n_f _i=1^% n_f _θ R_i= limitalic_β → 0 divide start_ARG 1 end_ARG start_ARG nroman_f end_ARG ∑i = 1nroman_f divide start_ARG 2 exp ( β sansserif_Ri ) end_ARG start_ARG 1 + exp ( β sansserif_Ri ) end_ARG ⋅ ∇θ sansserif_Ri = divide start_ARG 1 end_ARG start_ARG nroman_f end_ARG ∑i = 1nroman_f ∇θ sansserif_Ri =1nf∑i=1nf∇θlogπθ(yi∣xi)=∇θℒGA(θ).absent1subscriptfsuperscriptsubscript1subscriptfsubscript∇subscriptconditionalsubscriptsubscriptsubscript∇subscriptℒGA = 1n_f _i=1^n_f _% θ π_θ(y_i x_i)= _θL_% GA(θ).= divide start_ARG 1 end_ARG start_ARG nroman_f end_ARG ∑i = 1nroman_f ∇θ log πitalic_θ ( yitalic_i ∣ xitalic_i ) = ∇θ Lroman_GA ( θ ) . This completes the proof of Proposition 1. A.2 Proof of Theorem 2 Let η0:=η/nfassignsubscript0subscriptf _0:=η/n_fη0 := η / nroman_f denote the normalized learning rate. For i,j∈[nf]delimited-[]subscriptfi,j∈[n_f]i , j ∈ [ nroman_f ], define γi,j:=⟨xi,xj⟩assignsubscriptsubscriptsubscriptγ_i,j:= x_i,x_j γitalic_i , j := ⟨ xitalic_i , xitalic_j ⟩ and cinit,i:=⟨θinit,xi⟩assignsubscriptinitsubscriptinitsubscriptc_init,i:= θ_init,x_i _init , i := ⟨ θroman_init , xitalic_i ⟩. Throughout the proof, we also use Ck(k=0,1,2,…)subscript012…C_k(k=0,1,2,…)Citalic_k ( k = 0 , 1 , 2 , … ) to denote constants that may depend on (Bθ,bx,Bx,β)subscriptsubscriptsubscript(B_θ,b_x,B_x,β)( Bitalic_θ , bitalic_x , Bitalic_x , β ) but not on (t,nf,d)subscriptf(t,n_f,d)( t , nroman_f , d ). By the definition of the logistic model and some algebra, we have ∇θlogπθ(yi∣xi)=xi(2yi−1)(1−πθ(yi∣xi)).subscript∇subscriptconditionalsubscriptsubscriptsubscript2subscript11subscriptconditionalsubscriptsubscript _θ π_θ(y_i x_i)=x_i(2y_i% -1)(1-π_θ(y_i x_i)).∇θ log πitalic_θ ( yitalic_i ∣ xitalic_i ) = xitalic_i ( 2 yitalic_i - 1 ) ( 1 - πitalic_θ ( yitalic_i ∣ xitalic_i ) ) . Therefore, the gradient of ℒGAsubscriptℒGAL_GALroman_GA and ℒNPOsubscriptℒNPOL_NPOLroman_NPO both lie in the span of x1,…,xnfsubscript1…subscriptsubscriptfx_1,…,x_n_fx1 , … , xitalic_n start_POSTSUBSCRIPT f end_POSTSUBSCRIPT. Consequently, θGA(t)−θinitsubscriptsuperscriptGAsubscriptinitθ^(t)_GA-θ_initθ( t )GA - θroman_init and θNPO(t)−θinitsubscriptsuperscriptNPOsubscriptinitθ^(t)_NPO-θ_initθ( t )NPO - θroman_init can be rewritten as follows: θGA(t)−θinit=∑i=1nfαGA,i(t)⋅xi,θNPO(t)−θinit=∑i=1nfαNPO,i(t)⋅xi,formulae-sequencesubscriptsuperscriptGAsubscriptinitsuperscriptsubscript1subscriptf⋅superscriptsubscriptGAsubscriptsubscriptsuperscriptNPOsubscriptinitsuperscriptsubscript1subscriptf⋅superscriptsubscriptNPOsubscript θ^(t)_GA-θ_init= _i=1% ^n_fα_GA,i^(t)· x_i,~~~% θ^(t)_NPO-θ_init= _i=1^n_% fα_NPO,i^(t)· x_i,θ( t )GA - θroman_init = ∑i = 1nroman_f αroman_GA , i( t ) ⋅ xitalic_i , θ( t )NPO - θroman_init = ∑i = 1nroman_f αroman_NPO , i( t ) ⋅ xitalic_i , where αGA,i(t+1):=αGA,i(t)−η0(2yi−1)(1−πθ(yi∣xi)),αNPO,i(t+1):=αNPO,i(t)−η0(2yi−1)(1−πθ(yi∣xi))⋅i(t),formulae-sequenceassignsuperscriptsubscriptGA1superscriptsubscriptGAsubscript02subscript11subscriptconditionalsubscriptsubscriptassignsuperscriptsubscriptNPO1superscriptsubscriptNPO⋅subscript02subscript11subscriptconditionalsubscriptsubscriptsubscriptsuperscript α_GA,i^(t+1):=α_GA,i^(% t)- _0(2y_i-1)(1-π_θ(y_i x_i)),~~~α_% NPO,i^(t+1):=α_NPO,i^(t)- _0(2y_i% -1)(1-π_θ(y_i x_i))· W^(t)_i,αroman_GA , i( t + 1 ) := αroman_GA , i( t ) - η0 ( 2 yitalic_i - 1 ) ( 1 - πitalic_θ ( yitalic_i ∣ xitalic_i ) ) , αroman_NPO , i( t + 1 ) := αroman_NPO , i( t ) - η0 ( 2 yitalic_i - 1 ) ( 1 - πitalic_θ ( yitalic_i ∣ xitalic_i ) ) ⋅ sansserif_W( t )i , and i(t)=πθNPO(t)β(yi∣xi)/[πθNPO(t)β(yi∣xi)+πθinitβ(yi∣xi)].subscriptsuperscriptsuperscriptsubscriptsubscriptsuperscriptNPOconditionalsubscriptsubscriptdelimited-[]superscriptsubscriptsubscriptsuperscriptNPOconditionalsubscriptsubscriptsuperscriptsubscriptsubscriptinitconditionalsubscriptsubscript W^(t)_i=π_θ^(t)_NPO^% β(y_i x_i) /[π_θ^(t)_NPO^β% (y_i x_i)+π_θ_init^β(y_i x_i)].sansserif_W( t )i = πitalic_θ( t ) start_POSTSUBSCRIPT NPO end_POSTSUBSCRIPTβ ( yitalic_i ∣ xitalic_i ) / [ πitalic_θ( t ) start_POSTSUBSCRIPT NPO end_POSTSUBSCRIPTβ ( yitalic_i ∣ xitalic_i ) + πitalic_θ start_POSTSUBSCRIPT init end_POSTSUBSCRIPTβ ( yitalic_i ∣ xitalic_i ) ] . We also define α⋆,i(0)=0superscriptsubscript⋆00α_ ,i^(0)=0α⋆ , i( 0 ) = 0 and adopt the shorthand notations α⋆(t)=(α1,⋆(t),…,αnf,⋆(t))subscriptsuperscript⋆subscriptsuperscript1⋆…subscriptsuperscriptsubscriptf⋆α^(t)_ =(α^(t)_1, ,…,α^(t)_n_% f, )α( t )⋆ = ( α( t )1 , ⋆ , … , α( t )n start_POSTSUBSCRIPT f , ⋆ end_POSTSUBSCRIPT ) for ⋆∈GA,NPO ∈\GA,NPO\⋆ ∈ GA , NPO and γi=(γi,1,…,γi,nf)subscriptsubscript1…subscriptsubscriptfγ_i=(γ_i,1,…,γ_i,n_f)γitalic_i = ( γitalic_i , 1 , … , γitalic_i , n start_POSTSUBSCRIPT f end_POSTSUBSCRIPT ). For ⋆∈GA,NPO ∈\GA,NPO\⋆ ∈ GA , NPO , we have πθ⋆(t)(yi∣xi)subscriptsubscriptsuperscript⋆conditionalsubscriptsubscript π_θ^(t)_ (y_i x_i)πitalic_θ( t ) start_POSTSUBSCRIPT ⋆ end_POSTSUBSCRIPT ( yitalic_i ∣ xitalic_i ) =11+exp((1−2yi)⟨xi,θ⋆(t)⟩)=11+exp((1−2yi)cinit,i+(1−2yi)⟨xi,∑j=1nfα⋆(t)xj⟩)absent1112subscriptsubscriptsubscriptsuperscript⋆1112subscriptsubscriptinit12subscriptsubscriptsuperscriptsubscript1subscriptfsuperscriptsubscript⋆subscript = 11+ ((1-2y_i) x_i,θ^(t% )_ )= 11+ ((1-2y_i)c_% init,i+(1-2y_i) x_i, _j=1^n_fα_% ^(t)x_j )= divide start_ARG 1 end_ARG start_ARG 1 + exp ( ( 1 - 2 yitalic_i ) ⟨ xitalic_i , θ( t )⋆ ⟩ ) end_ARG = divide start_ARG 1 end_ARG start_ARG 1 + exp ( ( 1 - 2 yitalic_i ) croman_init , i + ( 1 - 2 yitalic_i ) ⟨ xitalic_i , ∑j = 1nroman_f α⋆( t ) xitalic_j ⟩ ) end_ARG =11+exp((1−2yi)cinit,i+(1−2yi)⟨α⋆(t),γi⟩)=:predi(⟨α⋆(t),γi⟩), = 11+ ((1-2y_i)c_init,i+(1-2y_i)% α^(t)_ ,γ_i )=:% pred_i ( α^(t)_ ,γ_i % ),= divide start_ARG 1 end_ARG start_ARG 1 + exp ( ( 1 - 2 yitalic_i ) croman_init , i + ( 1 - 2 yitalic_i ) ⟨ α( t )⋆ , γitalic_i ⟩ ) end_ARG = : preditalic_i ( ⟨ α( t )⋆ , γitalic_i ⟩ ) , where we denote the dependence on (cinit,i,yi)subscriptinitsubscript(c_init,i,y_i)( croman_init , i , yitalic_i ) implicitly using predisubscriptpredpred_ipreditalic_i for notational simplicity. Therefore, letting b⋆,i(t):=⟨α⋆(t),γi⟩assignsubscriptsuperscript⋆subscriptsuperscript⋆subscriptb^(t)_ ,i:= α^(t)_ ,γ_i ( t )⋆ , i := ⟨ α( t )⋆ , γitalic_i ⟩ for ⋆∈GA,NPO ∈\GA,NPO\⋆ ∈ GA , NPO and combining all i∈[nf]delimited-[]subscriptfi∈[n_f]i ∈ [ nroman_f ], we obtain bGA(t+1):=bGA(t)−η0⋅ΓΔGA(t),bNPO(t+1):=bNPO(t)−η0⋅ΓdiagΔNPO(t)(t),formulae-sequenceassignsuperscriptsubscriptGA1superscriptsubscriptGA⋅subscript0ΓsuperscriptsubscriptΔGAassignsuperscriptsubscriptNPO1superscriptsubscriptNPO⋅subscript0ΓdiagsuperscriptsubscriptΔNPOsuperscript b_GA^(t+1):=b_GA^(t)- _0% · _GA^(t),~~~b_NPO^(t+% 1):=b_NPO^(t)- _0· diag % \ _NPO^(t) \ W^(t),broman_GA( t + 1 ) := broman_GA( t ) - η0 ⋅ Γ Δroman_GA( t ) , broman_NPO( t + 1 ) := broman_NPO( t ) - η0 ⋅ Γ diag Δroman_NPO( t ) sansserif_W( t ) , where Γ Γ :=(γi,j)1≤i,j≤nf,assignabsentsubscriptsubscriptformulae-sequence1subscriptf :=(γ_i,j)_1≤ i,j≤n_f,:= ( γitalic_i , j )1 ≤ i , j ≤ n start_POSTSUBSCRIPT f end_POSTSUBSCRIPT , Δ⋆(t)superscriptsubscriptΔ⋆ _ ^(t)Δ⋆( t ) :=(Δ⋆,1(t),…,Δ⋆,nf(t))⊤,Δ⋆,i(t):=(2yi−1)(1−predi(b⋆,i(t))),for i∈[nf],⋆∈GA,NPO, := ( _ ,1^(t),…, _ ,n_% f^(t) ) ,~~~~ _ ,i^(t):=(2y_i% -1)(1-pred_i(b_ ,i^(t))),~~~for i∈[n_% f], ∈\GA,NPO\,:= ( Δ⋆ , 1( t ) , … , Δ⋆ , n start_POSTSUBSCRIPT f end_POSTSUBSCRIPT( t ) )⊤ , Δ⋆ , i( t ) := ( 2 yitalic_i - 1 ) ( 1 - preditalic_i ( b⋆ , i( t ) ) ) , for i ∈ [ nroman_f ] , ⋆ ∈ GA , NPO , (t)superscript W^(t)sansserif_W( t ) :=(1(t),…,nf)⊤,i(t)=i(bNPO(t)):=πθNPO(t)β(yi∣xi)/[πθNPO(t)β(yi∣xi)+πθinitβ(yi∣xi)].formulae-sequenceassignabsentsuperscriptsubscriptsuperscript1…subscriptsubscriptftopsuperscriptsubscriptsubscriptsubscriptsuperscriptNPOassignsuperscriptsubscriptsubscriptsuperscriptNPOconditionalsubscriptsubscriptdelimited-[]superscriptsubscriptsubscriptsuperscriptNPOconditionalsubscriptsubscriptsuperscriptsubscriptsubscriptinitconditionalsubscriptsubscript :=( W^(t)_1,…, W_n_f) % ,~~~ W_i^(t)= W_i (b^(t)_NPO% ):=π_θ^(t)_NPO^β(y_i x_i) % /[π_θ^(t)_NPO^β(y_i x_i)+π_% θ_init^β(y_i x_i)].:= ( sansserif_W( t )1 , … , sansserif_Wn start_POSTSUBSCRIPT f end_POSTSUBSCRIPT )⊤ , sansserif_Wi( t ) = sansserif_Wi ( b( t )NPO ) := πitalic_θ( t ) start_POSTSUBSCRIPT NPO end_POSTSUBSCRIPTβ ( yitalic_i ∣ xitalic_i ) / [ πitalic_θ( t ) start_POSTSUBSCRIPT NPO end_POSTSUBSCRIPTβ ( yitalic_i ∣ xitalic_i ) + πitalic_θ start_POSTSUBSCRIPT init end_POSTSUBSCRIPTβ ( yitalic_i ∣ xitalic_i ) ] . Again, we hide here the dependence on (β,cinit,i,yi)subscriptinitsubscript(β,c_init,i,y_i)( β , croman_init , i , yitalic_i ) in isubscript W_isansserif_Wi for simplicity. We now claim the following results of which the proofs are deferred to Section A.3 and A.4. Lemma 3 (GAGAGAGA converges to infinity linearly ). Under the assumptions in Theorem 2 and the notations in the proof of Theorem 2, there exist some (Bθ,bx,Bx)subscriptsubscriptsubscript(B_θ,b_x,B_x)( Bitalic_θ , bitalic_x , Bitalic_x )-dependent constants C0,C1,C2>0subscript0subscript1subscript20C_0,C_1,C_2>0C0 , C1 , C2 > 0 such that the GAGAGAGA iterations bGA(t)t=1∞superscriptsubscriptsubscriptsuperscriptGA1\b^(t)_GA\_t=1^∞ b( t )GA t = 1∞ satisfy C1η0tsubscript1subscript0 C_1 _0tC1 η0 t ≤bGA,i(t)≤C2η0t, when yi=0,formulae-sequenceabsentsuperscriptsubscriptGAsubscript2subscript0 when subscript0 ≤b_GA,i^(t)≤C_2 _0t, when% y_i=0,≤ broman_GA , i( t ) ≤ C2 η0 t , when yitalic_i = 0 , −C2η0tsubscript2subscript0 -C_2 _0t- C2 η0 t ≤bGA,i(t)≤−C1η0t, when yi=1.formulae-sequenceabsentsuperscriptsubscriptGAsubscript1subscript0 when subscript1 ≤b_GA,i^(t)≤-C_1 _0t, % when y_i=1.≤ broman_GA , i( t ) ≤ - C1 η0 t , when yitalic_i = 1 . for all i∈[nf]delimited-[]subscriptfi∈[n_f]i ∈ [ nroman_f ] and t≥11t≥ 1t ≥ 1 when maxi≠j|γi,j|≤C0/nf.subscriptsubscriptsubscript0subscriptf _i≠ j|γ_i,j|≤C_0/n_f.maxitalic_i ≠ j | γitalic_i , j | ≤ C0 / nroman_f . Lemma 4 (NPONPONPONPO converges to infinity exponentially slow ). Under the assumptions in Theorem 2 and the notations in the proof of Theorem 2, there exist some (Bθ,bx,Bx,β)subscriptsubscriptsubscript(B_θ,b_x,B_x,β)( Bitalic_θ , bitalic_x , Bitalic_x , β )-dependent constants C0,Cb>0,Ca∈(0,1)formulae-sequencesubscript0subscript0subscript01C_0,C_b>0,C_a∈(0,1)C0 , Citalic_b > 0 , Citalic_a ∈ ( 0 , 1 ) such that the NPONPONPONPO iterations bNPO(t)t=1∞superscriptsubscriptsubscriptsuperscriptNPO1\b^(t)_NPO\_t=1^∞ b( t )NPO t = 1∞ satisfy bNPO,i(t)superscriptsubscriptNPO b_NPO,i^(t)broman_NPO , i( t ) ∈[−1βlog(Cbη0t+1),−1βlog(Caη0t+1)] when yi=1,absent1subscriptsubscript011subscriptsubscript01 when subscript1 ∈[- 1β (C_b _0t+1),- 1β% (C_a _0t+1)] when y_i=1,∈ [ - divide start_ARG 1 end_ARG start_ARG β end_ARG log ( Citalic_b η0 t + 1 ) , - divide start_ARG 1 end_ARG start_ARG β end_ARG log ( Citalic_a η0 t + 1 ) ] when yitalic_i = 1 , bNPO,i(t)superscriptsubscriptNPO b_NPO,i^(t)broman_NPO , i( t ) ∈[1βlog(Caη0t+1),1βlog(Cbη0t+1)] when yi=0.absent1subscriptsubscript011subscriptsubscript01 when subscript0 ∈[ 1β (C_a _0t+1), 1β% (C_b _0t+1)] when y_i=0.∈ [ divide start_ARG 1 end_ARG start_ARG β end_ARG log ( Citalic_a η0 t + 1 ) , divide start_ARG 1 end_ARG start_ARG β end_ARG log ( Citalic_b η0 t + 1 ) ] when yitalic_i = 0 . for all i∈[nf]delimited-[]subscriptfi∈[n_f]i ∈ [ nroman_f ] and t≥11t≥ 1t ≥ 1 when maxi≠j|γi,j|≤C0/nf.subscriptsubscriptsubscript0subscriptf _i≠ j|γ_i,j|≤C_0/n_f.maxitalic_i ≠ j | γitalic_i , j | ≤ C0 / nroman_f . Combining Lemma 3 and 4 and noting ‖θ⋆(t)−θinit‖X⊤Xsubscriptnormsubscriptsuperscript⋆subscriptinitsuperscripttop \|θ^(t)_ -θ_init\|_X X∥ θ( t )⋆ - θroman_init ∥X⊤ X =(θ⋆(t)−θinit)⊤X⊤X(θ⋆(t)−θinit)=α⋆(t)⊤XX⊤XX⊤α⋆(t)absentsuperscriptsubscriptsuperscript⋆subscriptinittopsuperscripttopsubscriptsuperscript⋆subscriptinitsubscriptsuperscriptlimit-fromtop⋆superscripttopsuperscripttopsubscriptsuperscript⋆ = (θ^(t)_ -θ_init) % X X(θ^(t)_ -θ_init)= α% ^(t) _ XX XX α^(t)_ = square-root start_ARG ( θ( t )⋆ - θroman_init )⊤ X⊤ X ( θ( t )⋆ - θroman_init ) end_ARG = square-root start_ARG α( t ) ⊤⋆ X X⊤ X X⊤ α( t )⋆ end_ARG =b⋆(t)⊤(X⊤X)−1XX⊤XX⊤(X⊤X)−1b⋆(t)=‖b⋆(t)‖2absentsubscriptsuperscriptlimit-fromtop⋆superscriptsuperscripttop1superscripttopsuperscripttopsuperscriptsuperscripttop1subscriptsuperscript⋆subscriptnormsubscriptsuperscript⋆2 = b^(t) _ (X X)^-1XX % XX (X X)^-1b^(t)_ =\|b^(t)_ % \|_2= square-root start_ARG b( t ) ⊤⋆ ( X⊤ X )- 1 X X⊤ X X⊤ ( X⊤ X )- 1 b( t )⋆ end_ARG = ∥ b( t )⋆ ∥2 for ⋆∈GA,NPO ∈\GA,NPO\⋆ ∈ GA , NPO completes the proof. A.3 Proof of Lemma 3 We prove Lemma 3 by induction. Case 1: t=11t=1t = 1 When t=11t=1t = 1, since |cinit|≤‖xi‖2⋅‖θinit‖2≤BxBθsubscriptinit⋅subscriptnormsubscript2subscriptnormsubscriptinit2subscriptsubscript|c_init|≤\|x_i\|_2·\|θ_init\|_2≤% B_xB_θ| croman_init | ≤ ∥ xitalic_i ∥2 ⋅ ∥ θroman_init ∥2 ≤ Bitalic_x Bitalic_θ, it follows from the definition of predi(⋅)subscriptpred⋅pred_i(·)preditalic_i ( ⋅ ) that C3≤ΔGA,i(0)≤1 when yi=1,−1≤ΔGA,i(0)≤−C4 when yi=0formulae-sequencesubscript3subscriptsuperscriptΔ0GA1 when subscript11subscriptsuperscriptΔ0GAsubscript4 when subscript0 C_3≤ ^(0)_GA,i≤ 1 when y_% i=1,~~~-1≤ ^(0)_GA,i≤-C_4 when y% _i=0C3 ≤ Δ( 0 )GA , i ≤ 1 when yitalic_i = 1 , - 1 ≤ Δ( 0 )GA , i ≤ - C4 when yitalic_i = 0 for all i∈[nf]delimited-[]subscriptfi∈[n_f]i ∈ [ nroman_f ] for some constants C3,C4∈(0,1)subscript3subscript401C_3,C_4∈(0,1)C3 , C4 ∈ ( 0 , 1 ) depending only on (Bθ,bx,Bx)subscriptsubscriptsubscript(B_θ,b_x,B_x)( Bitalic_θ , bitalic_x , Bitalic_x ). Note that there exists a constant C0>0subscript00C_0>0C0 > 0 depending on C3,C4,bxsubscript3subscript4subscriptC_3,C_4,b_xC3 , C4 , bitalic_x such that |∑j≠iγi,jΔGA,j(0)|≤γi,i2|ΔGA,i(0)|subscriptsubscriptsuperscriptsubscriptΔGA0subscript2superscriptsubscriptΔGA0 | _j≠ iγ_i,j _GA,j^(0% ) |≤ γ_i,i2 | _GA,i^(0)% || ∑j ≠ i γitalic_i , j Δroman_GA , j( 0 ) | ≤ divide start_ARG γitalic_i , i end_ARG start_ARG 2 end_ARG | Δroman_GA , i( 0 ) | for all i∈[nf]delimited-[]subscriptfi∈[n_f]i ∈ [ nroman_f ] when maxi≠j|γi,j|≤C0/nfsubscriptsubscriptsubscript0subscriptf _i≠ j|γ_i,j|≤C_0/n_fmaxitalic_i ≠ j | γitalic_i , j | ≤ C0 / nroman_f. It follows that −η0⋅γi⊤ΔGA(0)⋅subscript0superscriptsubscripttopsuperscriptsubscriptΔGA0 - _0·γ_i _GA^(0)- η0 ⋅ γitalic_i⊤ Δroman_GA( 0 ) ∈[−32γi,iη0|ΔGA,i(0)|,−12γi,iη0|ΔGA,i(0)|]∈[−C2η0,−C1η0] when yi=1,absent32subscriptsubscript0superscriptsubscriptΔGA012subscriptsubscript0superscriptsubscriptΔGA0subscript2subscript0subscript1subscript0 when subscript1 ∈[- 32γ_i,i _0| _GA,% i^(0)|,- 12γ_i,i _0| _GA,i^(0)% |]∈[-C_2 _0,-C_1 _0]~ when y_i=1,∈ [ - divide start_ARG 3 end_ARG start_ARG 2 end_ARG γitalic_i , i η0 | Δroman_GA , i( 0 ) | , - divide start_ARG 1 end_ARG start_ARG 2 end_ARG γitalic_i , i η0 | Δroman_GA , i( 0 ) | ] ∈ [ - C2 η0 , - C1 η0 ] when yitalic_i = 1 , −η0⋅γi⊤ΔGA(0)⋅subscript0superscriptsubscripttopsuperscriptsubscriptΔGA0 - _0·γ_i _GA^(0)- η0 ⋅ γitalic_i⊤ Δroman_GA( 0 ) ∈[12γi,iη0|ΔGA,i(0)|,32γi,i|η0ΔGA,i(0)|]∈[C1η0,C2η0] when yi=0absent12subscriptsubscript0superscriptsubscriptΔGA032subscriptsubscript0superscriptsubscriptΔGA0subscript1subscript0subscript2subscript0 when subscript0 ∈[ 12γ_i,i _0| _GA,i% ^(0)|, 32γ_i,i| _0 _GA,i^(0)|% ]∈[C_1 _0,C_2 _0]~ when y_i=0∈ [ divide start_ARG 1 end_ARG start_ARG 2 end_ARG γitalic_i , i η0 | Δroman_GA , i( 0 ) | , divide start_ARG 3 end_ARG start_ARG 2 end_ARG γitalic_i , i | η0 Δroman_GA , i( 0 ) | ] ∈ [ C1 η0 , C2 η0 ] when yitalic_i = 0 for some (Bθ,bx,Bx)subscriptsubscriptsubscript(B_θ,b_x,B_x)( Bitalic_θ , bitalic_x , Bitalic_x )-dependent constants C1,C2>0.subscript1subscript20C_1,C_2>0.C1 , C2 > 0 . Therefore, bGA,i(1)superscriptsubscriptGA1 b_GA,i^(1)broman_GA , i( 1 ) =bGA,i(0)−η0⋅γi⊤ΔGA(0)∈[−C2η0,−C1η0] when yi=1,absentsuperscriptsubscriptGA0⋅subscript0superscriptsubscripttopsuperscriptsubscriptΔGA0subscript2subscript0subscript1subscript0 when subscript1 =b_GA,i^(0)- _0·γ_i % _GA^(0)∈[-C_2 _0,-C_1 _0]~% when y_i=1,= broman_GA , i( 0 ) - η0 ⋅ γitalic_i⊤ Δroman_GA( 0 ) ∈ [ - C2 η0 , - C1 η0 ] when yitalic_i = 1 , bGA,i(1)superscriptsubscriptGA1 b_GA,i^(1)broman_GA , i( 1 ) =bGA,i(0)−η0⋅γi⊤ΔGA(0)∈[C1η0,C2η0] when yi=0.absentsuperscriptsubscriptGA0⋅subscript0superscriptsubscripttopsuperscriptsubscriptΔGA0subscript1subscript0subscript2subscript0 when subscript0 =b_GA,i^(0)- _0·γ_i % _GA^(0)∈[C_1 _0,C_2 _0]~% when y_i=0.= broman_GA , i( 0 ) - η0 ⋅ γitalic_i⊤ Δroman_GA( 0 ) ∈ [ C1 η0 , C2 η0 ] when yitalic_i = 0 . As a consequence, bGA,i(1)superscriptsubscriptGA1 b_GA,i^(1)broman_GA , i( 1 ) ≤bGA,i(0)=0,ΔGA,i(1)≥ΔGA,i(0) when yi=1,formulae-sequenceabsentsuperscriptsubscriptGA00superscriptsubscriptΔGA1superscriptsubscriptΔGA0 when subscript1 ≤b_GA,i^(0)=0,~~ _GA,i% ^(1)≥ _GA,i^(0)~ when y_i=1,≤ broman_GA , i( 0 ) = 0 , Δroman_GA , i( 1 ) ≥ Δroman_GA , i( 0 ) when yitalic_i = 1 , bGA,i(1)superscriptsubscriptGA1 b_GA,i^(1)broman_GA , i( 1 ) ≥bGA,i(0)=0,ΔGA,i(1)≤ΔGA,i(0) when yi=0.formulae-sequenceabsentsuperscriptsubscriptGA00superscriptsubscriptΔGA1superscriptsubscriptΔGA0 when subscript0 ≥b_GA,i^(0)=0,~~ _GA,i% ^(1)≤ _GA,i^(0)~ when y_i=0.≥ broman_GA , i( 0 ) = 0 , Δroman_GA , i( 1 ) ≤ Δroman_GA , i( 0 ) when yitalic_i = 0 . Case 2: t=K+11t=K+1t = K + 1 Now, suppose we have bGA,i(t)superscriptsubscriptGA b_GA,i^(t)broman_GA , i( t ) ∈[−C2η0t,−C1η0t] when yi=1,absentsubscript2subscript0subscript1subscript0 when subscript1 ∈[-C_2 _0t,-C_1 _0t]~ when y_i% =1,∈ [ - C2 η0 t , - C1 η0 t ] when yitalic_i = 1 , bGA,i(t)superscriptsubscriptGA b_GA,i^(t)broman_GA , i( t ) ∈[C1η0t,C2η0t] when yi=0absentsubscript1subscript0subscript2subscript0 when subscript0 ∈[C_1 _0t,C_2 _0t]~ when y_i=0∈ [ C1 η0 t , C2 η0 t ] when yitalic_i = 0 for t∈[K]delimited-[]t∈[K]t ∈ [ K ] and bGA,i(K)superscriptsubscriptGA b_GA,i^(K)broman_GA , i( K ) ≤…≤bGA,i(0)=0,ΔGA,i(K)≥…≥ΔGA,i(0) when yi=1,formulae-sequenceabsent…superscriptsubscriptGA00superscriptsubscriptΔGA…superscriptsubscriptΔGA0 when subscript1 ≤…≤b_GA,i^(0)=0,~~ _% GA,i^(K)≥…≥ _GA,i^(0)~ % when y_i=1,≤ … ≤ broman_GA , i( 0 ) = 0 , Δroman_GA , i( K ) ≥ … ≥ Δroman_GA , i( 0 ) when yitalic_i = 1 , bGA,i(K)superscriptsubscriptGA b_GA,i^(K)broman_GA , i( K ) ≥…≥bGA,i(0)=0,ΔGA,i(K)≤…≤ΔGA,i(0) when yi=0.formulae-sequenceabsent…superscriptsubscriptGA00superscriptsubscriptΔGA…superscriptsubscriptΔGA0 when subscript0 ≥…≥b_GA,i^(0)=0,~~ _% GA,i^(K)≤…≤ _GA,i^(0)~ % when y_i=0.≥ … ≥ broman_GA , i( 0 ) = 0 , Δroman_GA , i( K ) ≤ … ≤ Δroman_GA , i( 0 ) when yitalic_i = 0 . By the monotonicity of ΔGA,i(t)subscriptsuperscriptΔGA ^(t)_GA,iΔ( t )GA , i, we have C3≤ΔGA,i(K)≤1 when yi=1,−1≤ΔGA,i(K)≤−C4 when yi=0formulae-sequencesubscript3subscriptsuperscriptΔGA1 when subscript11subscriptsuperscriptΔGAsubscript4 when subscript0 C_3≤ ^(K)_GA,i≤ 1 when y_% i=1,~~~-1≤ ^(K)_GA,i≤-C_4 when y% _i=0C3 ≤ Δ( K )GA , i ≤ 1 when yitalic_i = 1 , - 1 ≤ Δ( K )GA , i ≤ - C4 when yitalic_i = 0 for all i∈[nf]delimited-[]subscriptfi∈[n_f]i ∈ [ nroman_f ]. Therefore, following similar arguments as in the t=11t=1t = 1 case, we have −η0⋅γi⊤ΔGA(K)⋅subscript0superscriptsubscripttopsuperscriptsubscriptΔGA - _0·γ_i _GA^(K)- η0 ⋅ γitalic_i⊤ Δroman_GA( K ) ∈[−C2η0,−C1η0] when yi=1,absentsubscript2subscript0subscript1subscript0 when subscript1 ∈[-C_2 _0,-C_1 _0]~ when y_i=1,∈ [ - C2 η0 , - C1 η0 ] when yitalic_i = 1 , −η0⋅γi⊤ΔGA(K)⋅subscript0superscriptsubscripttopsuperscriptsubscriptΔGA - _0·γ_i _GA^(K)- η0 ⋅ γitalic_i⊤ Δroman_GA( K ) ∈[C1η0,C2η0] when yi=0.absentsubscript1subscript0subscript2subscript0 when subscript0 ∈[C_1 _0,C_2 _0]~ when y_i=0.∈ [ C1 η0 , C2 η0 ] when yitalic_i = 0 . Then it follows from the induction assumption that bGA,i(K+1)superscriptsubscriptGA1 b_GA,i^(K+1)broman_GA , i( K + 1 ) =bGA,i(K)−η0⋅γi⊤ΔGA(K)∈[−C2η0(K+1),−C1η0(K+1)] when yi=1,absentsuperscriptsubscriptGA⋅subscript0superscriptsubscripttopsuperscriptsubscriptΔGAsubscript2subscript01subscript1subscript01 when subscript1 =b_GA,i^(K)- _0·γ_i % _GA^(K)∈[-C_2 _0(K+1),-C_1 _0(K+% 1)]~ when y_i=1,= broman_GA , i( K ) - η0 ⋅ γitalic_i⊤ Δroman_GA( K ) ∈ [ - C2 η0 ( K + 1 ) , - C1 η0 ( K + 1 ) ] when yitalic_i = 1 , bGA,i(K+1)superscriptsubscriptGA1 b_GA,i^(K+1)broman_GA , i( K + 1 ) =bGA,i(K)−η0⋅γi⊤ΔGA(K)∈[C1η0(K+1),C2η0(K+1)] when yi=0,absentsuperscriptsubscriptGA⋅subscript0superscriptsubscripttopsuperscriptsubscriptΔGAsubscript1subscript01subscript2subscript01 when subscript0 =b_GA,i^(K)- _0·γ_i % _GA^(K)∈[C_1 _0(K+1),C_2 _0(K+1)% ]~ when y_i=0,= broman_GA , i( K ) - η0 ⋅ γitalic_i⊤ Δroman_GA( K ) ∈ [ C1 η0 ( K + 1 ) , C2 η0 ( K + 1 ) ] when yitalic_i = 0 , and also bGA,i(K+1)superscriptsubscriptGA1 b_GA,i^(K+1)broman_GA , i( K + 1 ) ≤bGA,i(K),ΔGA,i(K+1)≥ΔGA,i(K) when yi=1,formulae-sequenceabsentsuperscriptsubscriptGAsuperscriptsubscriptΔGA1superscriptsubscriptΔGA when subscript1 ≤b_GA,i^(K),~~ _GA,i^% (K+1)≥ _GA,i^(K)~ when y_i=1,≤ broman_GA , i( K ) , Δroman_GA , i( K + 1 ) ≥ Δroman_GA , i( K ) when yitalic_i = 1 , bGA,i(K+1)superscriptsubscriptGA1 b_GA,i^(K+1)broman_GA , i( K + 1 ) ≥bGA,i(K),ΔGA,i(K+1)≤ΔGA,i(K) when yi=0.formulae-sequenceabsentsuperscriptsubscriptGAsuperscriptsubscriptΔGA1superscriptsubscriptΔGA when subscript0 ≥b_GA,i^(K),~~ _GA,i^% (K+1)≤ _GA,i^(K)~ when y_i=0.≥ broman_GA , i( K ) , Δroman_GA , i( K + 1 ) ≤ Δroman_GA , i( K ) when yitalic_i = 0 . This concludes the induction step and therefore completes the proof. A.4 Proof of Lemma 4 We prove Lemma 4 by induction. Our induction assumption is the following: there exist some constants C0>0,Ca∈(0,1),Cb>0,C1,C2formulae-sequencesubscript00formulae-sequencesubscript01subscript0subscript1subscript2C_0>0,C_a∈(0,1),C_b>0,C_1,C_2C0 > 0 , Citalic_a ∈ ( 0 , 1 ) , Citalic_b > 0 , C1 , C2 depending only on (Bθ,bx,Bx,β)subscriptsubscriptsubscript(B_θ,b_x,B_x,β)( Bitalic_θ , bitalic_x , Bitalic_x , β ) such that when maxi≠j|γi,j|≤C0/nfsubscriptsubscriptsubscript0subscriptf _i≠ j|γ_i,j|≤C_0/n_fmaxitalic_i ≠ j | γitalic_i , j | ≤ C0 / nroman_f, for any t≥11t≥ 1t ≥ 1 we have 1. bNPO,i(t)superscriptsubscriptNPO b_NPO,i^(t)broman_NPO , i( t ) ≤…≤bNPO,i(0)=0,ΔNPO,i(t)≥…≥ΔNPO,i(0) when yi=1,formulae-sequenceabsent…superscriptsubscriptNPO00superscriptsubscriptΔNPO…superscriptsubscriptΔNPO0 when subscript1 ≤…≤b_NPO,i^(0)=0,~~ _% NPO,i^(t)≥…≥ _NPO,i^(0)~% when y_i=1,≤ … ≤ broman_NPO , i( 0 ) = 0 , Δroman_NPO , i( t ) ≥ … ≥ Δroman_NPO , i( 0 ) when yitalic_i = 1 , bNPO,i(t)superscriptsubscriptNPO b_NPO,i^(t)broman_NPO , i( t ) ≥…≥bNPO,i(0)=0,ΔNPO,i(t)≤…≤ΔNPO,i(0) when yi=0.formulae-sequenceabsent…superscriptsubscriptNPO00superscriptsubscriptΔNPO…superscriptsubscriptΔNPO0 when subscript0 ≥…≥b_NPO,i^(0)=0,~~ _% NPO,i^(t)≤…≤ _NPO,i^(0)~% when y_i=0.≥ … ≥ broman_NPO , i( 0 ) = 0 , Δroman_NPO , i( t ) ≤ … ≤ Δroman_NPO , i( 0 ) when yitalic_i = 0 . 2. bNPO,i(t)superscriptsubscriptNPO b_NPO,i^(t)broman_NPO , i( t ) ∈[−1βlog(Cbη0t+1),−1βlog(Caη0t+1)] when yi=1,absent1subscriptsubscript011subscriptsubscript01 when subscript1 ∈[- 1β (C_b _0t+1),- 1β% (C_a _0t+1)] when y_i=1,∈ [ - divide start_ARG 1 end_ARG start_ARG β end_ARG log ( Citalic_b η0 t + 1 ) , - divide start_ARG 1 end_ARG start_ARG β end_ARG log ( Citalic_a η0 t + 1 ) ] when yitalic_i = 1 , (7) bNPO,i(t)superscriptsubscriptNPO b_NPO,i^(t)broman_NPO , i( t ) ∈[1βlog(Caη0t+1),1βlog(Cbη0t+1)] when yi=0.absent1subscriptsubscript011subscriptsubscript01 when subscript0 ∈[ 1β (C_a _0t+1), 1β% (C_b _0t+1)] when y_i=0.∈ [ divide start_ARG 1 end_ARG start_ARG β end_ARG log ( Citalic_a η0 t + 1 ) , divide start_ARG 1 end_ARG start_ARG β end_ARG log ( Citalic_b η0 t + 1 ) ] when yitalic_i = 0 . (8) 3. bNPO,i(t)superscriptsubscriptNPO b_NPO,i^(t)broman_NPO , i( t ) ∈[−C2−1βlog(η0t+1),−C1−1βlog(η0t+1)] when yi=1,absentsubscript21subscript01subscript11subscript01 when subscript1 ∈[-C_2- 1β ( _0t+1),-C_1- % 1β ( _0t+1)] when y_i=1,∈ [ - C2 - divide start_ARG 1 end_ARG start_ARG β end_ARG log ( η0 t + 1 ) , - C1 - divide start_ARG 1 end_ARG start_ARG β end_ARG log ( η0 t + 1 ) ] when yitalic_i = 1 , (9) bNPO,i(t)superscriptsubscriptNPO b_NPO,i^(t)broman_NPO , i( t ) ∈[C1+1βlog(η0t+1),C2+1βlog(η0t+1)] when yi=0.absentsubscript11subscript01subscript21subscript01 when subscript0 ∈[C_1+ 1β ( _0t+1),C_2+ 1% β ( _0t+1)] when y_i=0.∈ [ C1 + divide start_ARG 1 end_ARG start_ARG β end_ARG log ( η0 t + 1 ) , C2 + divide start_ARG 1 end_ARG start_ARG β end_ARG log ( η0 t + 1 ) ] when yitalic_i = 0 . (10) Lemma 4 follows immediately from the second part of the induction assumption. In the following, we first specify the parameter-dependent constants C0,C1,C2,Ca,Cbsubscript0subscript1subscript2subscriptsubscriptC_0,C_1,C_2,C_a,C_bC0 , C1 , C2 , Citalic_a , Citalic_b in the t=11t=1t = 1 case and prove the induction assumption when k=11k=1k = 1. Then given the induction assumption holds when t≤Kt≤ Kt ≤ K, we prove that it holds when t=K+11t=K+1t = K + 1 as well. Case 1: t=11t=1t = 1 When t=11t=1t = 1, since |cinit|≤‖xi‖2⋅‖θinit‖2≤BxBθsubscriptinit⋅subscriptnormsubscript2subscriptnormsubscriptinit2subscriptsubscript|c_init|≤\|x_i\|_2·\|θ_init\|_2≤% B_xB_θ| croman_init | ≤ ∥ xitalic_i ∥2 ⋅ ∥ θroman_init ∥2 ≤ Bitalic_x Bitalic_θ, it follows from the definition of predi(⋅)subscriptpred⋅pred_i(·)preditalic_i ( ⋅ ) that C3≤ΔNPO,i(0)≤1 when yi=1,−1≤ΔNPO,i(0)≤−C4 when yi=0formulae-sequencesubscript3subscriptsuperscriptΔ0NPO1 when subscript11subscriptsuperscriptΔ0NPOsubscript4 when subscript0 C_3≤ ^(0)_NPO,i≤ 1 when y_% i=1,~~~-1≤ ^(0)_NPO,i≤-C_4 when % y_i=0C3 ≤ Δ( 0 )NPO , i ≤ 1 when yitalic_i = 1 , - 1 ≤ Δ( 0 )NPO , i ≤ - C4 when yitalic_i = 0 (11) for all i∈[nf]delimited-[]subscriptfi∈[n_f]i ∈ [ nroman_f ] for some constants C3,C4∈(0,1)subscript3subscript401C_3,C_4∈(0,1)C3 , C4 ∈ ( 0 , 1 ) depending only on (Bθ,bx,Bx)subscriptsubscriptsubscript(B_θ,b_x,B_x)( Bitalic_θ , bitalic_x , Bitalic_x ). Moreover, we claim that i(t)∈[C5⋅exp((2yi−1)βbNPO,i(t)),C6⋅exp((2yi−1)βbNPO,i(t))]subscriptsuperscript⋅subscript52subscript1subscriptsuperscriptNPO⋅subscript62subscript1subscriptsuperscriptNPO W^(t)_i∈ [C_5· ((2y_i-1)% βb^(t)_NPO,i ),C_6· ((2y_i-1)% βb^(t)_NPO,i ) ]sansserif_W( t )i ∈ [ C5 ⋅ exp ( ( 2 yitalic_i - 1 ) β b( t )NPO , i ) , C6 ⋅ exp ( ( 2 yitalic_i - 1 ) β b( t )NPO , i ) ] (12) for all i∈[nf]delimited-[]subscriptfi∈[n_f]i ∈ [ nroman_f ] and t such that predi(bNPO,i(t))≤predi(bNPO,i(0))subscriptpredsubscriptsuperscriptNPOsubscriptpredsubscriptsuperscript0NPOpred_i(b^(t)_NPO,i) _i(b^(0)% _NPO,i)preditalic_i ( b( t )NPO , i ) ≤ preditalic_i ( b( 0 )NPO , i ) for some (Bθ,bx,Bx,β)subscriptsubscriptsubscript(B_θ,b_x,B_x,β)( Bitalic_θ , bitalic_x , Bitalic_x , β )-dependent constants C5,C6>0subscript5subscript60C_5,C_6>0C5 , C6 > 0. Now, suppose Eq. (9) and (10) hold for some (Bθ,bx,Bx,β)subscriptsubscriptsubscript(B_θ,b_x,B_x,β)( Bitalic_θ , bitalic_x , Bitalic_x , β )-dependent constants C1,C2>0subscript1subscript20C_1,C_2>0C1 , C2 > 0 which we will specify later. Then, there exists a constant C0>0subscript00C_0>0C0 > 0 depending on C1:6,bxsubscript:16subscriptC_1:6,b_xC1 : 6 , bitalic_x such that |∑j≠iγi,jΔNPO,j(0)j|≤γi,i2|ΔNPO,i(0)i|subscriptsubscriptsuperscriptsubscriptΔNPO0subscriptsubscript2superscriptsubscriptΔNPO0subscript | _j≠ iγ_i,j _NPO,j^(% 0) W_j |≤ γ_i,i2 | _% NPO,i^(0) W_i || ∑j ≠ i γitalic_i , j Δroman_NPO , j( 0 ) sansserif_Wj | ≤ divide start_ARG γitalic_i , i end_ARG start_ARG 2 end_ARG | Δroman_NPO , i( 0 ) sansserif_Wi | (13) for all i∈[nf]delimited-[]subscriptfi∈[n_f]i ∈ [ nroman_f ] when maxi≠j|γi,j|≤C0/nfsubscriptsubscriptsubscript0subscriptf _i≠ j|γ_i,j|≤C_0/n_fmaxitalic_i ≠ j | γitalic_i , j | ≤ C0 / nroman_f. Furthermore, combining Eq. (11), (12), (13) gives −η0⋅γi⊤diagΔNPO(0)i(0)⋅subscript0superscriptsubscripttopdiagsuperscriptsubscriptΔNPO0superscriptsubscript0 - _0·γ_i diag\ _% NPO^(0)\ W_i^(0)- η0 ⋅ γitalic_i⊤ diag Δroman_NPO( 0 ) sansserif_Wi( 0 ) ∈[−32γi,iη0|ΔNPO,i(0)|i(0),−12γi,iη0|ΔNPO,i(0)|i(0)]absent32subscriptsubscript0superscriptsubscriptΔNPO0superscriptsubscript012subscriptsubscript0superscriptsubscriptΔNPO0superscriptsubscript0 ∈ [- 32γ_i,i _0| _ % NPO,i^(0)| W_i^(0),- 12γ_i,i _0|% _NPO,i^(0)| W_i^(0) ]∈ [ - divide start_ARG 3 end_ARG start_ARG 2 end_ARG γitalic_i , i η0 | Δroman_NPO , i( 0 ) | sansserif_Wi( 0 ) , - divide start_ARG 1 end_ARG start_ARG 2 end_ARG γitalic_i , i η0 | Δroman_NPO , i( 0 ) | sansserif_Wi( 0 ) ] ∈[−C8η0exp(βbNPO,i(0)),−C7η0exp(βbNPO,i(0))] when yi=1,absentsubscript8subscript0subscriptsuperscript0NPOsubscript7subscript0subscriptsuperscript0NPO when subscript1 ∈[-C_8 _0 (βb^(0)_NPO,i),-% C_7 _0 (βb^(0)_NPO,i)]~ when y_% i=1,∈ [ - C8 η0 exp ( β b( 0 )NPO , i ) , - C7 η0 exp ( β b( 0 )NPO , i ) ] when yitalic_i = 1 , −η0⋅γi⊤diagΔNPO(0)i(0)⋅subscript0superscriptsubscripttopdiagsuperscriptsubscriptΔNPO0superscriptsubscript0 - _0·γ_i diag\ _% NPO^(0)\ W_i^(0)- η0 ⋅ γitalic_i⊤ diag Δroman_NPO( 0 ) sansserif_Wi( 0 ) ∈[12γi,iη0|ΔNPO,i(0)|i(0),32γi,iη0|ΔNPO,i(0)|i(0)]absent12subscriptsubscript0superscriptsubscriptΔNPO0superscriptsubscript032subscriptsubscript0superscriptsubscriptΔNPO0superscriptsubscript0 ∈ [ 12γ_i,i _0| _% NPO,i^(0)| W_i^(0), 32γ_i,i _0|% _NPO,i^(0)| W_i^(0) ]∈ [ divide start_ARG 1 end_ARG start_ARG 2 end_ARG γitalic_i , i η0 | Δroman_NPO , i( 0 ) | sansserif_Wi( 0 ) , divide start_ARG 3 end_ARG start_ARG 2 end_ARG γitalic_i , i η0 | Δroman_NPO , i( 0 ) | sansserif_Wi( 0 ) ] ∈[C7η0exp(−βbNPO,i(0)),C8η0exp(βbNPO,i(0))] when yi=0,absentsubscript7subscript0subscriptsuperscript0NPOsubscript8subscript0subscriptsuperscript0NPO when subscript0 ∈[C_7 _0 (-βb^(0)_NPO,i),% C_8 _0 (βb^(0)_NPO,i)]~ when y_i% =0,∈ [ C7 η0 exp ( - β b( 0 )NPO , i ) , C8 η0 exp ( β b( 0 )NPO , i ) ] when yitalic_i = 0 , if maxi≠j|γi,j|≤C0/nf.subscriptsubscriptsubscript0subscriptf _i≠ j|γ_i,j|≤C_0/n_f.maxitalic_i ≠ j | γitalic_i , j | ≤ C0 / nroman_f . Here C7,C8>0subscript7subscript80C_7,C_8>0C7 , C8 > 0 are some (C3,C4,C5,C6,β)subscript3subscript4subscript5subscript6(C_3,C_4,C_5,C_6,β)( C3 , C4 , C5 , C6 , β )-dependent constants, and we pick C7subscript7C_7C7 such that C7β<1subscript71C_7β<1C7 β < 1. As a consequence, bNPO,i(1)superscriptsubscriptNPO1 b_NPO,i^(1)broman_NPO , i( 1 ) ≤bNPO,i(0)=0,ΔNPO,i(1)≥ΔNPO,i(0) when yi=1,formulae-sequenceabsentsuperscriptsubscriptNPO00superscriptsubscriptΔNPO1superscriptsubscriptΔNPO0 when subscript1 ≤b_NPO,i^(0)=0,~~ _NPO% ,i^(1)≥ _NPO,i^(0)~ when y_i=1,≤ broman_NPO , i( 0 ) = 0 , Δroman_NPO , i( 1 ) ≥ Δroman_NPO , i( 0 ) when yitalic_i = 1 , bNPO,i(1)superscriptsubscriptNPO1 b_NPO,i^(1)broman_NPO , i( 1 ) ≥bNPO,i(0)=0,ΔNPO,i(1)≤ΔNPO,i(0) when yi=0.formulae-sequenceabsentsuperscriptsubscriptNPO00superscriptsubscriptΔNPO1superscriptsubscriptΔNPO0 when subscript0 ≥b_NPO,i^(0)=0,~~ _NPO% ,i^(1)≤ _NPO,i^(0)~ when y_i=0.≥ broman_NPO , i( 0 ) = 0 , Δroman_NPO , i( 1 ) ≤ Δroman_NPO , i( 0 ) when yitalic_i = 0 . This concludes the proof of the first part of the induction assumption. Now, we start to prove the second part of the induction assumption. For i such that yi=1subscript1y_i=1yitalic_i = 1, consider the ordinary differential equations bl′(t)superscriptsubscript′ b_l (t)bitalic_l′ ( t ) =−C8η0(1+exp(C8))⋅exp(βbl(t)),bl(0)=0;formulae-sequenceabsent⋅subscript8subscript01subscript8subscriptsubscript00 =-C_8 _0(1+ (C_8))· (βb_l(t)),% ~~~~~~b_l(0)=0;= - C8 η0 ( 1 + exp ( C8 ) ) ⋅ exp ( β bitalic_l ( t ) ) , bitalic_l ( 0 ) = 0 ; bu′(t)superscriptsubscript′ b_u (t)bitalic_u′ ( t ) =−C7η0⋅exp(βbl(t)),bu(0)=0.formulae-sequenceabsent⋅subscript7subscript0subscriptsubscript00 =-C_7 _0· (βb_l(t)),~~~~~~% b_u(0)=0.= - C7 η0 ⋅ exp ( β bitalic_l ( t ) ) , bitalic_u ( 0 ) = 0 . It can be verified that the ODEs have closed-form solutions bl(t)subscript b_l(t)bitalic_l ( t ) =−1βlog(βC8η0(1+exp(C8))t+1),absent1subscript8subscript01subscript81 =- 1β (βC_8 _0(1+ (C_8))% t+1),= - divide start_ARG 1 end_ARG start_ARG β end_ARG log ( β C8 η0 ( 1 + exp ( C8 ) ) t + 1 ) , bu(t)subscript b_u(t)bitalic_u ( t ) =−1βlog(βC7η0t+1).absent1subscript7subscript01 =- 1β (βC_7 _0t+1).= - divide start_ARG 1 end_ARG start_ARG β end_ARG log ( β C7 η0 t + 1 ) . Since bNPO,i(1)=bNPO,i(1)−η0⋅γi⊤ΔNPO,i(0)≥bNPO,i(1)−C8η0exp(βbNPO,i(0))≥bNPO,i(1)−C8η0,superscriptsubscriptNPO1superscriptsubscriptNPO1⋅subscript0superscriptsubscripttopsuperscriptsubscriptΔNPO0superscriptsubscriptNPO1subscript8subscript0subscriptsuperscript0NPOsuperscriptsubscriptNPO1subscript8subscript0 b_NPO,i^(1)=b_NPO,i^(1)- _% 0·γ_i _NPO,i^(0)≥b_% NPO,i^(1)-C_8 _0 (βb^(0)_NPO,i)≥% b_NPO,i^(1)-C_8 _0,broman_NPO , i( 1 ) = broman_NPO , i( 1 ) - η0 ⋅ γitalic_i⊤ Δroman_NPO , i( 0 ) ≥ broman_NPO , i( 1 ) - C8 η0 exp ( β b( 0 )NPO , i ) ≥ broman_NPO , i( 1 ) - C8 η0 , it follows that for any point bNPO,i(ε)=εbNPO,i(1)+(1−ε)bNPO,i(0)subscriptsuperscriptNPOsubscriptsuperscript1NPO1subscriptsuperscript0NPOb^( )_NPO,i= b^(1)_% NPO,i+(1- )b^(0)_NPO,ib( ε )NPO , i = ε b( 1 )NPO , i + ( 1 - ε ) b( 0 )NPO , i with ε∈[0,1]01 ∈[0,1]ε ∈ [ 0 , 1 ] −C8η0(1+exp(C8η0))⋅exp(βbNPO,i(ε))⋅subscript8subscript01subscript8subscript0subscriptsuperscriptNPO -C_8 _0(1+ (C_8 _0))· (βb% ^( )_NPO,i)- C8 η0 ( 1 + exp ( C8 η0 ) ) ⋅ exp ( β b( ε )NPO , i ) ≤−C8η0exp(βbNPO,i(0))≤−C7η0exp(βbNPO,i(0))absentsubscript8subscript0subscriptsuperscript0NPOsubscript7subscript0subscriptsuperscript0NPO ≤-C_8 _0 (βb^(0)_NPO,i)% ≤-C_7 _0 (βb^(0)_NPO,i)≤ - C8 η0 exp ( β b( 0 )NPO , i ) ≤ - C7 η0 exp ( β b( 0 )NPO , i ) ≤−C7η0⋅exp(βbNPO,i(ε)).absent⋅subscript7subscript0subscriptsuperscriptNPO ≤-C_7 _0· (βb^( )_% NPO,i).≤ - C7 η0 ⋅ exp ( β b( ε )NPO , i ) . Therefore, we have by the comparison theorem for ODEs that bl(ε)≤bNPO,i(ε)≤bu(ε)subscriptsuperscriptsubscriptNPOsubscript b_l( )≤b_NPO,i^( )% ≤b_u( )bitalic_l ( ε ) ≤ broman_NPO , i( ε ) ≤ bitalic_u ( ε ) for ε∈[0,1]01 ∈[0,1]ε ∈ [ 0 , 1 ]. Setting Ca:=C7β,Cb:=βC8(1+exp(C8))formulae-sequenceassignsubscriptsubscript7assignsubscriptsubscript81subscript8 C_a:=C_7β,~~~~~C_b:=βC_8(1+% (C_8))Citalic_a := C7 β , Citalic_b := β C8 ( 1 + exp ( C8 ) ) concludes the second part of the induction assumption. For the last part of the induction assumption, since log(x+1)+log(c)≤log(cx+1)≤log(x+1)+log(c+1)1111 (x+1)+ (c)≤ (cx+1)≤ (x+1)+ (c+1)log ( x + 1 ) + log ( c ) ≤ log ( c x + 1 ) ≤ log ( x + 1 ) + log ( c + 1 ) when c≤11c≤ 1c ≤ 1, we have −1β[log(η0t+1)+log(βC8(1+exp(C8)))]≤bl(t)≤bu(t)≤−1β[log(η0t+1)+log(βC7)],1delimited-[]subscript01subscript81subscript8subscriptsubscript1delimited-[]subscript01subscript7 - 1β[ ( _0t+1)+ (βC_8(1+ % (C_8)))]≤b_l(t)≤b_u(t)≤- 1β[ ( _0% t+1)+ (βC_7)],- divide start_ARG 1 end_ARG start_ARG β end_ARG [ log ( η0 t + 1 ) + log ( β C8 ( 1 + exp ( C8 ) ) ) ] ≤ bitalic_l ( t ) ≤ bitalic_u ( t ) ≤ - divide start_ARG 1 end_ARG start_ARG β end_ARG [ log ( η0 t + 1 ) + log ( β C7 ) ] , where the last inequality uses βC7<1subscript71βC_7<1β C7 < 1. Therefore, we obtain bNPO,i(1)∈[−1βlog(η0t+1)−C2,−1βlog(η0t+1)−C1],subscriptsuperscript1NPO1subscript01subscript21subscript01subscript1 b^(1)_NPO,i∈[- 1β ( _0% t+1)-C_2,- 1β ( _0t+1)-C_1],b( 1 )NPO , i ∈ [ - divide start_ARG 1 end_ARG start_ARG β end_ARG log ( η0 t + 1 ) - C2 , - divide start_ARG 1 end_ARG start_ARG β end_ARG log ( η0 t + 1 ) - C1 ] , where C1:=1βlog(βC7),C2:=1βlog(βC8(1+exp(C8)))formulae-sequenceassignsubscript11subscript7assignsubscript21subscript81subscript8 C_1:= 1β (βC_7),~~~~~C% _2:= 1β (βC_8(1+ (C_8)))C1 := divide start_ARG 1 end_ARG start_ARG β end_ARG log ( β C7 ) , C2 := divide start_ARG 1 end_ARG start_ARG β end_ARG log ( β C8 ( 1 + exp ( C8 ) ) ) for i such that yi=1subscript1y_i=1yitalic_i = 1. Following the same arguments, similarly, we also have bNPO,i(1)∈[1βlog(η0t+1)+C1,1βlog(η0t+1)+C2]subscriptsuperscript1NPO1subscript01subscript11subscript01subscript2 b^(1)_NPO,i∈[ 1β ( _0t% +1)+C_1, 1β ( _0t+1)+C_2]b( 1 )NPO , i ∈ [ divide start_ARG 1 end_ARG start_ARG β end_ARG log ( η0 t + 1 ) + C1 , divide start_ARG 1 end_ARG start_ARG β end_ARG log ( η0 t + 1 ) + C2 ] for i such that yi=0subscript0y_i=0yitalic_i = 0. This concludes the last part of the induction assumption. Case 2: t=K+11t=K+1t = K + 1 Suppose the induction assumption holds for t∈[K]delimited-[]t∈[K]t ∈ [ K ], we now show that the induction assumption holds for t=K+11t=K+1t = K + 1 as well. Following the proof of t=11t=1t = 1 case and using the monotonicity property of ΔNPO,i(t)t=0KsuperscriptsubscriptsuperscriptsubscriptΔNPO0\ _NPO,i^(t)\_t=0^K Δroman_NPO , i( t ) t = 0K, we have C3≤ΔNPO,i(K)≤1 when yi=1,−1≤ΔNPO,i(K)≤−C4 when yi=0formulae-sequencesubscript3subscriptsuperscriptΔNPO1 when subscript11subscriptsuperscriptΔNPOsubscript4 when subscript0 C_3≤ ^(K)_NPO,i≤ 1 when y_% i=1,~~~-1≤ ^(K)_NPO,i≤-C_4 when % y_i=0C3 ≤ Δ( K )NPO , i ≤ 1 when yitalic_i = 1 , - 1 ≤ Δ( K )NPO , i ≤ - C4 when yitalic_i = 0 for all i∈[nf]delimited-[]subscriptfi∈[n_f]i ∈ [ nroman_f ]. Since predi(bNPO,i(K))≤predi(bNPO,i(K))subscriptpredsubscriptsuperscriptNPOsubscriptpredsubscriptsuperscriptNPOpred_i(b^(K)_NPO,i) _i(b^(K)% _NPO,i)preditalic_i ( b( K )NPO , i ) ≤ preditalic_i ( b( K )NPO , i ) by the definition of predisubscriptpredpred_ipreditalic_i and the monotonicity of bNPO,i(t)t=0KsuperscriptsubscriptsubscriptsuperscriptNPO0\b^(t)_NPO,i\_t=0^K b( t )NPO , i t = 0K, it follows from Claim (12) that i(K)∈[C5⋅exp((2yi−1)βbNPO,i(K)),C6⋅exp((2yi−1)βbNPO,i(K))].subscriptsuperscript⋅subscript52subscript1subscriptsuperscriptNPO⋅subscript62subscript1subscriptsuperscriptNPO W^(K)_i∈ [C_5· ((2y_i-1)% βb^(K)_NPO,i ),C_6· ((2y_i-1)% βb^(K)_NPO,i ) ].sansserif_W( K )i ∈ [ C5 ⋅ exp ( ( 2 yitalic_i - 1 ) β b( K )NPO , i ) , C6 ⋅ exp ( ( 2 yitalic_i - 1 ) β b( K )NPO , i ) ] . Putting the last two displays together and following the same argument as the t=11t=1t = 1 case, we find that −η0⋅γi⊤diagΔNPO(K)i(K)⋅subscript0superscriptsubscripttopdiagsuperscriptsubscriptΔNPOsuperscriptsubscript - _0·γ_i diag\ _% NPO^(K)\ W_i^(K)- η0 ⋅ γitalic_i⊤ diag Δroman_NPO( K ) sansserif_Wi( K ) ∈[−C8η0exp(βbNPO,i(K)),−C7η0exp(βbNPO,i(K))] when yi=1,absentsubscript8subscript0subscriptsuperscriptNPOsubscript7subscript0subscriptsuperscriptNPO when subscript1 ∈[-C_8 _0 (βb^(K)_NPO,i),-% C_7 _0 (βb^(K)_NPO,i)]~ when y_% i=1,∈ [ - C8 η0 exp ( β b( K )NPO , i ) , - C7 η0 exp ( β b( K )NPO , i ) ] when yitalic_i = 1 , −η0⋅γi⊤diagΔNPO(K)i(K)⋅subscript0superscriptsubscripttopdiagsuperscriptsubscriptΔNPOsuperscriptsubscript - _0·γ_i diag\ _% NPO^(K)\ W_i^(K)- η0 ⋅ γitalic_i⊤ diag Δroman_NPO( K ) sansserif_Wi( K ) ∈[C7η0exp(−βbNPO,i(K)),C8η0exp(βbNPO,i(K))] when yi=0.absentsubscript7subscript0subscriptsuperscriptNPOsubscript8subscript0subscriptsuperscriptNPO when subscript0 ∈[C_7 _0 (-βb^(K)_NPO,i),% C_8 _0 (βb^(K)_NPO,i)]~ when y_i% =0.∈ [ C7 η0 exp ( - β b( K )NPO , i ) , C8 η0 exp ( β b( K )NPO , i ) ] when yitalic_i = 0 . The first part of the induction assumption (for t=K+11t=K+1t = K + 1) follows immediately as the sign of the gradient updates −η0⋅γi⊤diagΔNPO(K)i(K)⋅subscript0superscriptsubscripttopdiagsuperscriptsubscriptΔNPOsuperscriptsubscript- _0·γ_i diag\ _NPO% ^(K)\ W_i^(K)- η0 ⋅ γitalic_i⊤ diag Δroman_NPO( K ) sansserif_Wi( K ) are determined as above. Note that bl(K)≤bNPO,i(K)≤bu(K)subscriptsuperscriptsubscriptNPOsubscriptb_l(K)≤b_NPO,i^(K)≤b_u(K)bitalic_l ( K ) ≤ broman_NPO , i( K ) ≤ bitalic_u ( K ) by the induction assumption. Similarly, using the comparison theorem of ODEs, we obtain bl(K+ε)≤bNPO,i(K+ε)≤bu(K+ε)subscriptsuperscriptsubscriptNPOsubscript b_l(K+ )≤b_NPO,i^(K+% )≤b_u(K+ )bitalic_l ( K + ε ) ≤ broman_NPO , i( K + ε ) ≤ bitalic_u ( K + ε ) for ε∈[0,1]01 ∈[0,1]ε ∈ [ 0 , 1 ] and bNPO,i(K+ε):=εbNPO,i(K+1)+(1−ε)bNPO,i(K)assignsuperscriptsubscriptNPOsuperscriptsubscriptNPO11superscriptsubscriptNPOb_NPO,i^(K+ ):= b_NPO,i% ^(K+1)+(1- )b_NPO,i^(K)broman_NPO , i( K + ε ) := ε broman_NPO , i( K + 1 ) + ( 1 - ε ) broman_NPO , i( K ). Choosing ε=11 =1ε = 1 gives the second part of the induction assumption for t=K+11t=K+1t = K + 1. The last part of the induction assumption for t=K+11t=K+1t = K + 1 follows from the same algebra as in the t=11t=1t = 1 case. Proof of Claim (12) By definition i(t)=πθNPO(t)β(yi∣xi)πθNPO(t)β(yi∣xi)+πrefβ(yi∣xi)=predi(bNPO,i(t))βpredi(bNPO,i(t))β+predi(bNPO,i(0))β.subscriptsuperscriptsuperscriptsubscriptsubscriptsuperscriptNPOconditionalsubscriptsubscriptsuperscriptsubscriptsubscriptsuperscriptNPOconditionalsubscriptsubscriptsuperscriptsubscriptrefconditionalsubscriptsubscriptsubscriptpredsuperscriptsubscriptsuperscriptNPOsubscriptpredsuperscriptsubscriptsuperscriptNPOsubscriptpredsuperscriptsubscriptsuperscript0NPO W^(t)_i= π_θ^(t)_NPO^% β(y_i x_i)π_θ^(t)_NPO^β(y_i% x_i)+π_ref^β(y_i x_i)= pred% _i(b^(t)_NPO,i)^βpred_i(b^(t)_% NPO,i)^β+pred_i(b^(0)_NPO,i)^% β.sansserif_W( t )i = divide start_ARG πitalic_θ( t ) start_POSTSUBSCRIPT NPO end_POSTSUBSCRIPTβ ( yitalic_i ∣ xitalic_i ) end_ARG start_ARG πitalic_θ( t ) start_POSTSUBSCRIPT NPO end_POSTSUBSCRIPTβ ( yitalic_i ∣ xitalic_i ) + πroman_refitalic_β ( yitalic_i ∣ xitalic_i ) end_ARG = divide start_ARG preditalic_i ( b( t )NPO , i )β end_ARG start_ARG preditalic_i ( b( t )NPO , i )β + preditalic_i ( b( 0 )NPO , i )β end_ARG . When predi(bNPO,i(t))≤predi(bNPO,i(0))subscriptpredsubscriptsuperscriptNPOsubscriptpredsubscriptsuperscript0NPOpred_i(b^(t)_NPO,i) _i(b^(0)% _NPO,i)preditalic_i ( b( t )NPO , i ) ≤ preditalic_i ( b( 0 )NPO , i ), we have i(t)∈[predi(bNPO,i(t))β2predi(bNPO,i(0))β,predi(bNPO,i(t))βpredi(bNPO,i(0))β]∈[Cl⋅predi(bNPO,i(t))β,Cu⋅predi(bNPO,i(t))β]subscriptsuperscriptsubscriptpredsuperscriptsubscriptsuperscriptNPO2presubscriptdsuperscriptsubscriptsuperscript0NPOsubscriptpredsuperscriptsubscriptsuperscriptNPOsubscriptpredsuperscriptsubscriptsuperscript0NPO⋅subscriptsubscriptpredsuperscriptsubscriptsuperscriptNPO⋅subscriptsubscriptpredsuperscriptsubscriptsuperscriptNPO W^(t)_i∈ [ pred_i(b^(t)_% NPO,i)^β2pred_i(b^(0)_NPO,i)^% β, pred_i(b^(t)_NPO,i)^β% pred_i(b^(0)_NPO,i)^β ]∈[C_l% ·pred_i(b^(t)_NPO,i)^β,C_u·% pred_i(b^(t)_NPO,i)^β]sansserif_W( t )i ∈ [ divide start_ARG preditalic_i ( b( t )NPO , i )β end_ARG start_ARG 2 p r e ditalic_i ( b( 0 )NPO , i )β end_ARG , divide start_ARG preditalic_i ( b( t )NPO , i )β end_ARG start_ARG preditalic_i ( b( 0 )NPO , i )β end_ARG ] ∈ [ Citalic_l ⋅ preditalic_i ( b( t )NPO , i )β , Citalic_u ⋅ preditalic_i ( b( t )NPO , i )β ] (14) for some constants Cl,Cu>0subscriptsubscript0C_l,C_u>0Citalic_l , Citalic_u > 0 depending only on (Bθ,bx,Bx,β)subscriptsubscriptsubscript(B_θ,b_x,B_x,β)( Bitalic_θ , bitalic_x , Bitalic_x , β ). Note that predi(bNPO,i(t))≤predi(bNPO,i(0))subscriptpredsubscriptsuperscriptNPOsubscriptpredsubscriptsuperscript0NPOpred_i(b^(t)_NPO,i) _i(b^(0)% _NPO,i)preditalic_i ( b( t )NPO , i ) ≤ preditalic_i ( b( 0 )NPO , i ) is equivalent to (1−2yi)bNPO,i(t)≥012subscriptsubscriptsuperscriptNPO0(1-2y_i)b^(t)_NPO,i≥ 0( 1 - 2 yitalic_i ) b( t )NPO , i ≥ 0. Therefore, under this condition, we have predi(bNPO,i(t))subscriptpredsubscriptsuperscriptNPO _i(b^(t)_NPO,i)preditalic_i ( b( t )NPO , i ) =11+exp((1−2yi)cinit,i+(1−2yi)bNPO,i(t))absent1112subscriptsubscriptinit12subscriptsubscriptsuperscriptNPO = 11+ ((1-2y_i)c_init,i+(1-2y_i)b% ^(t)_NPO,i )= divide start_ARG 1 end_ARG start_ARG 1 + exp ( ( 1 - 2 yitalic_i ) croman_init , i + ( 1 - 2 yitalic_i ) b( t )NPO , i ) end_ARG =exp((2yi−1)bNPO,i(t))exp((2yi−1)bNPO,i(t))+exp((1−2yi)cinit,i)absent2subscript1subscriptsuperscriptNPO2subscript1subscriptsuperscriptNPO12subscriptsubscriptinit = ((2y_i-1)b^(t)_NPO,i )% ((2y_i-1)b^(t)_NPO,i )+ ((1-2y_i)% c_init,i )= divide start_ARG exp ( ( 2 yitalic_i - 1 ) b( t )NPO , i ) end_ARG start_ARG exp ( ( 2 yitalic_i - 1 ) b( t )NPO , i ) + exp ( ( 1 - 2 yitalic_i ) croman_init , i ) end_ARG ∈[exp((2yi−1)bNPO,i(t))1+exp((1−2yi)cinit,i),exp((2yi−1)bNPO,i(t))exp((1−2yi)cinit,i)].absent2subscript1subscriptsuperscriptNPO112subscriptsubscriptinit2subscript1subscriptsuperscriptNPO12subscriptsubscriptinit ∈ [ ((2y_i-1)b^(t)_NPO,i% )1+ ((1-2y_i)c_init,i ), (% (2y_i-1)b^(t)_NPO,i ) ((1-2y_i)c_ % init,i ) ].∈ [ divide start_ARG exp ( ( 2 yitalic_i - 1 ) b( t )NPO , i ) end_ARG start_ARG 1 + exp ( ( 1 - 2 yitalic_i ) croman_init , i ) end_ARG , divide start_ARG exp ( ( 2 yitalic_i - 1 ) b( t )NPO , i ) end_ARG start_ARG exp ( ( 1 - 2 yitalic_i ) croman_init , i ) end_ARG ] . (15) Putting Eq. (14) and (15) together and recalling that |cinit,i|≤BθBxsubscriptinitsubscriptsubscript|c_init,i|≤B_θB_x| croman_init , i | ≤ Bitalic_θ Bitalic_x, we obtain i(t)∈[C5⋅exp((2yi−1)βbNPO,i(t)),C6⋅exp((2yi−1)βbNPO,i(t))]subscriptsuperscript⋅subscript52subscript1subscriptsuperscriptNPO⋅subscript62subscript1subscriptsuperscriptNPO W^(t)_i∈ [C_5· ((2y_i-1)% βb^(t)_NPO,i ),C_6· ((2y_i-1)% βb^(t)_NPO,i ) ]sansserif_W( t )i ∈ [ C5 ⋅ exp ( ( 2 yitalic_i - 1 ) β b( t )NPO , i ) , C6 ⋅ exp ( ( 2 yitalic_i - 1 ) β b( t )NPO , i ) ] for some constants C5,C6>0subscript5subscript60C_5,C_6>0C5 , C6 > 0 depending only on (Bθ,bx,Bx,β)subscriptsubscriptsubscript(B_θ,b_x,B_x,β)( Bitalic_θ , bitalic_x , Bitalic_x , β ). This concludes the proof of Claim (12). Appendix B The role of KL Divergence on the Forget Set In this section, we report Forget KL, the KL divergence between the output distributions of the initial model and the unlearned model on the forget set, defined as FGKL(πref(⋅∣x)||πθ(⋅∣x))E_D_ FGKL(π_ref(% · x)||π_θ(· x))blackboard_ED start_POSTSUBSCRIPT FG end_POSTSUBSCRIPT KL ( πroman_ref ( ⋅ ∣ x ) | | πitalic_θ ( ⋅ ∣ x ) ). In experiments on the synthetic dataset and TOFU dataset, we observe that the models exhibit better unlearning performance when the forget KL is maintained at a moderate level. This suggests that explicitly maximizing the forget KL may not be an ideal objective for unlearning tasks. B.1 Synthetic Experiment We present the forget KL for the synthetic experiments in Figure 11 (a) and (b). Combining with Figure 4, we find that the unlearned models attain Pareto frontiers when the forget KL is suitably large—an excessively large forget KL (as in GA,GA+RTGAGARTGA,GA+RTGA , GA + RT after 1200120012001200 steps) or an excessively small forget KL (as in IDK+RTIDKRTIDK+RTIDK + RT) may deteriorate the unlearning performance. Figure 11: Forget KL versus optimization steps for all methods in the synthetic experiment. (a): α=11α=1α = 1, (b): α=00α=0α = 0. The errorbars denote ±1plus-or-minus1± 1± 1 standard deviation over 5555 runs. Appendix C Experimental details of the synthetic experiments In this section, we discuss the experimental details of the synthetic experiments studied in Section 4. Initial model and retrained model. We create the initial model πrefsubscriptrefπ_refπroman_ref and the retrained model πretrsubscriptretrπ_ retrπroman_retr via optimizing over θ using the cross-entropy loss on the entire dataset =FG∪RTsubscriptFGsubscriptRTD=D_ FG∪D_ RTD = Droman_FG ∪ Droman_RT and the retain dataset RTsubscriptRTD_ RTDroman_RT, respectively. Concretely, initializing at θ=128subscript0128θ=0_128θ = 0128, we run gradient descent for 20000200002000020000 steps with the learning rate equals 0.050.050.050.05 to obtain the initial model πrefsubscriptrefπ_refπroman_ref and the retrained model πretrsubscriptretrπ_ retrπroman_retr. Unlearning. During unlearning, starting from the initial model πrefsubscriptrefπ_refπroman_ref, we run gradient descent on each of the loss functions for 2000200020002000 steps with the learning rates selected via a grid search. We choose the learning rates so that the training remains stable within 2000200020002000 steps. It should be noted that variations of the learning rates may affect the number of steps needed to reach the minimal forget distance (or retain distance) in Figure 4 (a1, a2, b). However, they are less likely to alter the Pareto curves shown in Figure 4 (c). A grid search is also conducted to select the optimal β for NPO (and DPO)-based methods. The choices of learning rate and β are summarized in Table 1. Method learning rate β α=11α=1α = 1 α=00α=0α = 0 α=11α=1α = 1 α=00α=0α = 0 GA,GA+RT, IDK+RT 5e-4 1e-4 N/A N/A NPO, NPO+RT 5e-3 5e-2 1 10 DPO+RT 5e-3 5e-2 0.1 5 Table 1: Values of learning rate and β for different methods when α=11α=1α = 1 and α=00α=0α = 0 in the synthetic experiments. Appendix D Experiments on the TOFU dataset In this section, we provide details of the experiments on the TOFU dataset (Maini et al., 2024). We first present a detailed explanation of the metrics, the baseline methods and the hyperparameters in the experiments. Then, we provide the full results on different levels of the tasks. D.1 Experiments Setup D.1.1 Dataset TOFU Dataset. We evaluate NPO-based methods and all baselines on the TOFU (Task of Fictitious Unlearning) dataset (Maini et al., 2024) designed for measuring the unlearning methods for LLMs. TOFU contains 200 fictitious author profiles, each consisting of 20 question-answering pairs generated by GPT-4 based on a set of predefined attributes. These profiles are fictitious and do not exist in the pre-training data, providing a controlled environment for studying unlearning LLMs. TOFU introduces three levels of unlearning tasks, each aiming at forgetting a subset of 2, 10, and 20 authors (comprising 1%, 5%, and 10% of the training data, respectively), referred to as the forget set FGsubscriptFGD_ FGDroman_FG, with a computational constraint that scales linearly with the size of the forget set. We refer to these tasks as Forget01, Forget05, and Forget10, respectively. Dataset for Evaluation. In addition to the forget set, Maini et al. (2024) also introduced other datasets to measure the performance of the unlearned model. The retain set RTsubscriptRTD_ RTDroman_RT is the part of the data that we do not hope the model to forget, which is, by definition, the complementary set of the forget set in the full dataset. To evaluate the model performance on the retain set, TOFU earmarks a subset of 400 question-answer pairs, accounting for 10% of the data, as an exclusive retain set that is never included in the forget set for any task. Moreover, to measure the general capacities of the unlearned models, two additional datasets are introduced: the Real Authors set and the Real World set. The Real Authors set includes question-answer pairs about authors in the real world and often deals with neighboring concepts entangled with those in the forget set. The Real World set contains commonsense knowledge about the real world and is designed to examine the general world knowledge of the unlearned model. Dataset beyond Forget10. In scenarios where the targeted forget set exceeds 10% of the data (Forget20, Forget30, Forget50, and Forget90), we reorganize the original forget and retain sets within the TOFU dataset. To assess the Truth Ratio on an evaluation dataset, it is necessary to utilize the perturbed and paraphrased answers, which in TOFU were generated by properly prompting GPT4. To avoid any potential distribution shift from the newly crafted responses and their original forms, we evaluate the Truth Ratio using the publicly available data within TOFU. Consequently, even for tasks that are beyond forget10, we continue to use the data from the standard forget10 subset to compute the Truth Ratio on the forget set. This serves as a reasonable proxy for evaluating the Truth Ratio on the full forget set. D.1.2 Metrics Model Utility. We measure the general capacities of the unlearned model using Model Utility, which aggregates multiple metrics across the retain set, the real-world set and the real-author set. Given a question-answer pair x=[q,a],x=[q,a],x = [ q , a ] , we compute the normalized conditional probability ℙ(a∣q)1/|a|,ℙsuperscriptconditional1P(a q)^1/|a|,blackboard_P ( a ∣ q )1 / | a | , where |⋅||·|| ⋅ | denotes the number of tokens in a certain sequence. This probability is then averaged over the retain set, the Real Authors set, and the Real World set each. We also compute the averaged ROUGE-L recall score (Lin, 2004) across these datasets, a metric that evaluates the accuracy of the model’s response compared to the reference answers. Finally, we compute the averaged Truth Ratio on the three datasets above. The Truth Ratio defined in Maini et al. (2024) measures how likely the unlearned model will give a correct answer versus an incorrect one. More specifically, given a question q,q,q , Maini et al. (2024) generated a paraphrased (correct) answer a~~ aover~ start_ARG a end_ARG via prompting GPT4. They then generated five perturbed answers with the exactly same templates but incorrect answers a^i,i=1,2,3,4,5formulae-sequencesubscript^12345 a_i,i=1,2,3,4,5over start_ARG a end_ARGi , i = 1 , 2 , 3 , 4 , 5 in the same way. The Truth Ratio is defined by Rtruth:=15∑i=15ℙ(a^i∣q)1/|a^i|ℙ(a~∣q)1/|a~|.assignsubscriptℎ15superscriptsubscript15ℙsuperscriptconditionalsubscript^1subscript^ℙsuperscriptconditional~1~R_truth:= 15 _i=1^5P( a_i q)^1% /| a_i|P( a q)^1/| a|.Ritalic_t r u t h := divide start_ARG divide start_ARG 1 end_ARG start_ARG 5 end_ARG ∑i = 15 blackboard_P ( over start_ARG a end_ARGi ∣ q )1 / | over start_ARG a end_ARGi | end_ARG start_ARG blackboard_P ( over~ start_ARG a end_ARG ∣ q )1 / | over~ start_ARG a end_ARG | end_ARG . (16) The model utility is defined as the harmonic average of the nine metrics above (the probability, the ROUGE score, and the Truth Ratio on the retain set, the Real Authors set, and the Real World set). Forget Quality. Forget quality assesses how well the unlearned model mimics the retrained model (defined as the model trained only on the retain set). This is a rigorous measurement as the ultimate goal for unlearning LLM is not only to stop generating the content related to the forget set but also to make the unlearned model indistinguishable from the retrained one. From a practical view of point, this requires the next-token probability given a prefix of the unlearned model to be as close as possible to that of the retrained model. In TOFU, they compute the Truth Ratio (defined in Eq. 16) on each question-answer pair from the forget set. Instead of simply averaging them, they test whether the distribution of the Truth Ratio computed from the unlearned and the retrained models are indistinguishable. More specifically, they perform the Kolmogorov-Smirnov (KS) test and compute the p-value of the test. A large p-value indicates that the two models are indistinguishable from the Truth Ratio. When the p-value is above 0.05, we say the forgetting is significant. D.1.3 Baseline Methods In this section, we introduce the baseline methods in our experiments. GA-based Methods. Gradient Ascent (GA) is a key component in many LLM unlearning methods. Performing GA is equivalent to doing Gradient Descent (GD) on the negative cross-entropy loss function, which is denoted as ℒGA(θ)subscriptℒGAL_GA(θ)Lroman_GA ( θ ) defined in Eq. (1). Based on gradient ascent, a large class of unlearning methods performs gradient-based optimization on a linear combination of the GA loss ℒGAsubscriptℒGAL_GALroman_GA and several other loss functions that encourage unlearning (Jang et al., 2022; Yao et al., 2023; Chen & Yang, 2023; Maini et al., 2024; Eldan & Russinovich, 2023). Such a loss function can be written as ℒ(θ)=cGAℒGA(θ)+cFGℒFG(θ)+cRTℒRT(θ)−cFGKLFG(θ)+cRTKLRT(θ),ℒsubscriptGAsubscriptℒGAsubscriptFGsubscriptℒFGsubscriptRTsubscriptℒRTsubscriptFGKLsubscriptFGsubscriptRTKLsubscriptRTL(θ)=c_ GAL_GA(θ)+c_ FG% L_FG(θ)+c_ RTL_RT(% θ)-c_ FGKLK_FG(θ)+c_ RTKL% K_RT(θ),L ( θ ) = croman_GA Lroman_GA ( θ ) + croman_FG Lroman_FG ( θ ) + croman_RT Lroman_RT ( θ ) - croman_FGKL Kroman_FG ( θ ) + croman_RTKL Kroman_RT ( θ ) , (17) where cGA,cFG,cRT,cFGKL,cRTKLsubscriptGAsubscriptFGsubscriptRTsubscriptFGKLsubscriptRTKLc_ GA,c_ FG,c_ RT,c_ FGKL,c_ RTKLcroman_GA , croman_FG , croman_RT , croman_FGKL , croman_RTKL are non-negative weights. Here, ℒFG(θ)=−FG[log(πθ(y~|x))]subscriptℒFGsubscriptsubscriptFGdelimited-[]subscriptconditional~L_FG(θ)=-E_D_ FG[% (π_θ( y|x))]Lroman_FG ( θ ) = - blackboard_ED start_POSTSUBSCRIPT FG end_POSTSUBSCRIPT [ log ( πitalic_θ ( over~ start_ARG y end_ARG | x ) ) ] is the Forget loss where (x,y)∼FGsimilar-tosubscriptFG(x,y) D_ FG( x , y ) ∼ Droman_FG and y~≠y~ y≠yover~ start_ARG y end_ARG ≠ y is any response for prompt x which show some extent of ignorance towards the question x.x.x . ℒRT(θ)=−RT[log(πθ(y|x))]subscriptℒRTsubscriptsubscriptRTdelimited-[]subscriptconditionalL_RT(θ)=-E_D_ RT[% (π_θ(y|x))]Lroman_RT ( θ ) = - blackboard_ED start_POSTSUBSCRIPT RT end_POSTSUBSCRIPT [ log ( πitalic_θ ( y | x ) ) ] is the retain loss. FG(θ)=FG[(πθ(⋅|x)||πref(⋅|x))]K_FG(θ)=E_D_ FG[% D(π_θ(·|x)||π_ref(·|x))]Kroman_FG ( θ ) = blackboard_ED start_POSTSUBSCRIPT FG end_POSTSUBSCRIPT [ sansserif_D ( πitalic_θ ( ⋅ | x ) | | πroman_ref ( ⋅ | x ) ) ] is the expected KL divergence on the forget set. RT(θ)=RT[(πθ(⋅|x)||πref(⋅|x))]K_RT(θ)=E_D_ RT[% D(π_θ(·|x)||π_ref(·|x))]Kroman_RT ( θ ) = blackboard_ED start_POSTSUBSCRIPT RT end_POSTSUBSCRIPT [ sansserif_D ( πitalic_θ ( ⋅ | x ) | | πroman_ref ( ⋅ | x ) ) ] is the expected KL divergence on the retain set. In our experiments, we use three GA-based methods reported in Maini et al. (2024), referred to as GA, GA+RT, GA+KL, which fall in this class of loss function. The weights in Eq. (17) are shown in Table 2. Loss cGAsubscriptGAc_ GAcroman_GA cFGsubscriptFGc_ FGcroman_FG cRTsubscriptRTc_ RTcroman_RT cFGKLsubscriptFGKLc_ FGKLcroman_FGKL cRTKLsubscriptRTKLc_ RTKLcroman_RTKL GA 1 0 0 0 0 GA+RT 1 0 1 0 0 GA+KL 1 0 0 0 1 IDK+RT 0 1 1 0 0 Table 2: The weights for different components in GA-based loss functions and IDK+RT loss. IDK-based Methods (’I don’t know’). Maini et al. (2024) proposed IDK+RT, which is a supervised loss function comprising of the retain loss and IDK loss term. The IDK loss term ℒFGsubscriptℒFGL_FGLroman_FG is the averaged cross-entropy loss for question-answer pairs with questions xxx from the forget set FGsubscriptFGD_ FGDroman_FG and answers yyy replaced by y~=~absent y=over~ start_ARG y end_ARG = ’I don’t know’ or a similar sentence showing ignorance towards this question. IDK+RT does not involve GA loss, and in general, IDK+RT loss shows a higher stability than GA-based methods. DPO-based Methods. We also tested the DPO method (Rafailov et al., 2024) and its variants by adding either the retain loss or the KL divergence on the retain set. In the DPO loss, we take ’I don’t know’ or its variants as positive responses and the answers in the forget set as negative responses. We use β=0.10.1β=0.1β = 0.1 in all DPO-based experiments, which is commonly recognized as the optimal inverse temperature in most cases. KTO-based Methods. We examine Kahneman-Tversky Optimization (KTO) (Ethayarajh et al., 2024), an alignment method with only non-paired preference data. The objective function of KTO is (we use a slightly different version than the original one as in Ethayarajh et al. (2024)) ℒKTO:=2βFG[−logσ(zref−βlogπθ(y∣x)πref(y∣x))],assignsubscriptℒKTO2subscriptsubscriptFGdelimited-[]subscriptrefsubscriptconditionalsubscriptrefconditionalL_KTO:= 2βE_D_ FG% [- σ (z_ref-β π_θ(y% x)π_ref(y x) ) ],Lroman_KTO := divide start_ARG 2 end_ARG start_ARG β end_ARG blackboard_ED start_POSTSUBSCRIPT FG end_POSTSUBSCRIPT [ - log σ ( zroman_ref - β log divide start_ARG πitalic_θ ( y ∣ x ) end_ARG start_ARG πroman_ref ( y ∣ x ) end_ARG ) ] , (18) where β>00β>0β > 0 is the inverse-temperature, σ is the sigmoid function, and zref:=x∼FG[β⋅(πθ(⋅∣x)||πref(⋅∣x))].z_ref:=E_x D_ FG [β·% D (π_θ(· x)||π_ref(·% x) ) ].zroman_ref := blackboard_Ex ∼ D start_POSTSUBSCRIPT FG end_POSTSUBSCRIPT [ β ⋅ sansserif_D ( πitalic_θ ( ⋅ ∣ x ) | | πroman_ref ( ⋅ ∣ x ) ) ] . (19) Following (Ethayarajh et al., 2024), we estimate the KL term via averaged log probability ratio for questions in the forget set and answers in the ”I don’t know” set (as the unrelated outputs). We examine both KTO and KTO+RT in our experiments with β=0.1.0.1β=0.1.β = 0.1 . D.2 Full Results Figure 12: Statistics for NPO-based methods and baselines on the Forget01 task of TOFU. Figure 13: Statistics for NPO-based methods and baselines on the Forget05 task of TOFU. Figure 14: Statistics for NPO-based methods and baselines on the Forget10 task of TOFU. Figure 15: Statistics for NPO-based methods and baselines on the Forget20 task of TOFU. Figure 16: Statistics for NPO-based methods and baselines on the Forget30 task of TOFU. Figure 17: Statistics for NPO-based methods and baselines on the Forget50 task of TOFU.