Paper deep dive

Understanding the Learning Dynamics of Alignment with Human Feedback

Shawn Im, Yixuan Li

Year: 2024Venue: arXiv preprintArea: Alignment TrainingType: TheoreticalEmbeddings: 165

Models: Llama-2-7B, Mistral-7B

Intelligence

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

Last extracted: 3/12/2026, 6:49:10 PM

Summary

This paper provides a theoretical analysis of the learning dynamics of Direct Preference Optimization (DPO) in aligning large language models (LLMs). The authors demonstrate that the rate of model parameter updates and training accuracy are significantly influenced by 'preference distinguishability'—the distributional distance between preferred and non-preferred responses in the training dataset. They show that higher distinguishability leads to faster loss reduction but can cause the model to prioritize certain behaviors over others, potentially leading to misalignment. The findings are empirically validated using Llama-2 on diverse preference datasets.

Entities (5)

Direct Preference Optimization · algorithm · 100%LLaMA-2 · model · 100%Reinforcement Learning from Human Feedback · algorithm · 100%Anthropic Persona dataset · dataset · 95%Preference Distinguishability · metric · 95%

Relation Signals (3)

LLaMA-2 → trainedusing → Direct Preference Optimization

confidence 100% · For each persona, we fine-tune the unembedding layer in Llama-2-7B model (Touvron et al., 2023) using the DPO objective

Preference Distinguishability → influences → Learning Dynamics

confidence 95% · We provide a theoretical analysis of how DPO dynamics change based on the distributional properties of the preference dataset.

Direct Preference Optimization → isalternativeto → Reinforcement Learning from Human Feedback

confidence 95% · Direct Preference Optimization (DPO) introduced in Rafailov et al. (2023) has emerged as a promising alternative [to RLHF]

Cypher Suggestions (0)

No Cypher suggestions yet.

Abstract

Abstract:Aligning large language models (LLMs) with human intentions has become a critical task for safely deploying models in real-world systems. While existing alignment approaches have seen empirical success, theoretically understanding how these methods affect model behavior remains an open question. Our work provides an initial attempt to theoretically analyze the learning dynamics of human preference alignment. We formally show how the distribution of preference datasets influences the rate of model updates and provide rigorous guarantees on the training accuracy. Our theory also reveals an intricate phenomenon where the optimization is prone to prioritizing certain behaviors with higher preference distinguishability. We empirically validate our findings on contemporary LLMs and alignment tasks, reinforcing our theoretical insights and shedding light on considerations for future alignment approaches. Disclaimer: This paper contains potentially offensive text; reader discretion is advised.

PDF

Open source PDF →Open local PDF →

Trouble viewing inline? Open PDF directly →

Full Text

165,028 characters extracted from source content.

Expand or collapse full text

Understanding the Learning Dynamics of Alignment with Human Feedback Shawn Im Yixuan Li Abstract Aligning large language models (LLMs) with human intentions has become a critical task for safely deploying models in real-world systems. While existing alignment approaches have seen empirical success, theoretically understanding how these methods affect model behavior remains an open question. Our work provides an initial attempt to theoretically analyze the learning dynamics of human preference alignment. We formally show how the distribution of preference datasets influences the rate of model updates and provide rigorous guarantees on the training accuracy. Our theory also reveals an intricate phenomenon where the optimization is prone to prioritizing certain behaviors with higher preference distinguishability. We empirically validate our findings on contemporary LLMs and alignment tasks, reinforcing our theoretical insights and shedding light on considerations for future alignment approaches. Disclaimer: This paper contains potentially offensive text; reader discretion is advised. Machine Learning, ICML 1 Introduction Large language models (LLMs) have demonstrated remarkable abilities to generate human-like text and acquire diverse capabilities (Brown et al., 2020; Wei et al., 2022; Anil et al., 2023). However, these models are not necessarily aligned with human preferences and can inadvertently produce harmful or undesirable outputs. Thus, aligning language models with human preferences has become an important problem, which ensures that these models exhibit safe and desirable behavior. Existing alignment approaches share the basis of reinforcement learning from human preferences (RLHF) (Christiano et al., 2017; Ziegler et al., 2019b; Ouyang et al., 2022; Bai et al., 2022a), which involves fitting a reward model to the preference data and optimizing a language model policy for high reward through reinforcement learning. Despite the empirical success and wide adoption in real-world systems (OpenAI, 2023; Anthropic, 2023; Touvron et al., 2023), theoretical understanding of alignment with human preferences is still in its infancy. In particular, analyzing the learning dynamics of RLHF theoretically is a challenging task, as it requires understanding both the learned reward model and how it guides the policy learned during reinforcement learning. Moreover, the computational expense associated with RLHF, involving multiple models, adds to the complexity. Recently, a reparameterization of RLHF called Direct Preference Optimization (DPO) (Rafailov et al., 2023) has emerged as a promising alternative, which directly optimizes the policy to best satisfy preferences and circumvents the need for RL training. Rafailov et al. (2023) showed that under mild assumptions, the optimal policy under the DPO objective is the same as the optimal policy using RLHF. The equivalence makes rigorously analyzing how models change when learning human preferences more tractable. With DPO, it is sufficient to consider the relationship between the policy and the dataset. In this paper, we provide a theoretical analysis of how DPO dynamics change based on the distributional properties of the preference dataset. We characterize the data distributions through the lens of preference distinguishability, which refers to how far apart the distributions for the preferred and non-preferred responses are. Based on this notion, we provide learning guarantees on how preference distinguishability impacts the rate of weight parameter updates under the DPO objective (Theorem 4.1), along with a lower bound for the accuracy (Theorem 4.2 and Theorem 4.3). Our theorem indicates that, under the same training configuration, higher distinguishability leads to a faster rate of change in weight parameters and a more rapid decrease of loss. Our theoretical insight has practical implications for alignment training on diverse preference datasets encompassing various topics and behaviors of differing distinguishability. In particular, we reveal an intricate prioritization effect, where DPO is prone to prioritize learning behaviors with higher distinguishability and as a result, may deprioritize the less distinguishable yet crucial ones. Such an effect can manifest in real systems, where for example, certain political views or ideological beliefs may be prioritized in the learning process over others. We empirically validate our theoretical insights and show that they generalize to practical LLMs. Leveraging the latest Llama-2 model (Touvron et al., 2023), we conduct extensive experiments by training on diverse preference datasets using the DPO objective. Consistent with our theory, our results indicate that behaviors with higher distinguishability exhibit a more rapid rate of loss reduction. Moreover, when training multiple behaviors simultaneously, the effect of prioritization remains influential in the practical setting. Notably, we observe that models trained with DPO are more susceptible to being unaligned or misaligned compared to their corresponding base models. These findings shed light on the vulnerability of RLHF and DPO-trained models, and underscore the importance of considering preference or behavior prioritization in alignment training. We summarize our key contributions in the following: • To the best of our knowledge, we provide a first attempt to understand the learning dynamics of the alignment approach from a rigorous theoretical point of view. • We provide new learning guarantees on how preference distinguishability impacts the rate of weight parameter updates under the DPO objective (Theorem 4.1), along with a lower bound on training accuracy (Theorem 4.2 and Theorem 4.3). • We empirically validate our findings on modern LLMs and preference datasets containing diverse behaviors, reinforcing our theoretical insights and inspiring future research on practical algorithms for alignment. 2 Preliminaries Notations. We denote πθsubscript _θπitalic_θ as a language model policy parameterized by θ, which takes in an input prompt x, and outputs a discrete probability distribution πθ(⋅|x) _θ(·|x)πitalic_θ ( ⋅ | x ) over the vocabulary space VV. πθ⁢(y|x)subscriptconditional _θ(y|x)πitalic_θ ( y | x ) refers to the model’s probability of outputting response y given input prompt x. Additionally, considering two possible outputs yw,ylsubscriptsubscripty_w,y_lyitalic_w , yitalic_l, we denote yw≻ylsucceedssubscriptsubscripty_w y_lyitalic_w ≻ yitalic_l if ywsubscripty_wyitalic_w is preferred over ylsubscripty_lyitalic_l. We call ywsubscripty_wyitalic_w the preferred response and ylsubscripty_lyitalic_l the less preferred response. RLHF Overview. Reinforcement Learning from Human Feedback (RLHF) is a widely used paradigm for learning desirable behaviors based on human preferences (Christiano et al., 2017; Ziegler et al., 2019a; Ouyang et al., 2022; Bai et al., 2022a). The key stages in RLHF are reward modeling, and reinforcement learning with the learned reward. Here we provide a brief recap of the two stages, respectively. During reward modeling, we aim to learn a function mapping, which takes in the prompt x and response y and outputs a scalar value r⁢(x,y)r(x,y)r ( x , y ) signifying the reward. A preferred response should receive a higher reward, and vice versa. Under the Bradley-Terry model (Bradley & Terry, 1952), the preference distribution is modeled as p∗⁢(yw≻yl|x)=σ⁢(r∗⁢(x,yw)−r∗⁢(x,yl)),superscriptsucceedssubscriptconditionalsubscriptsuperscriptsubscriptsuperscriptsubscriptp^*(y_w y_l|x)=σ(r^*(x,y_w)-r^*(x,y_l)),p∗ ( yitalic_w ≻ yitalic_l | x ) = σ ( r∗ ( x , yitalic_w ) - r∗ ( x , yitalic_l ) ) , (1) where σ is the sigmoid function. Given the empirical dataset =(xi,yw,i,yl,i)i=1nsuperscriptsubscriptsubscriptsubscriptsubscript1D=\(x_i,y_w,i,y_l,i)\_i=1^nD = ( xitalic_i , yitalic_w , i , yitalic_l , i ) i = 1n sampled from the preference distribution p∗superscriptp^*p∗, we can learn the reward function via maximum likelihood estimation, which is equivalent to optimizing the following binary classification objective: ℒR=−(x,yw,yl)∼⁢[log⁡σ⁢(r⁢(x,yw)−r⁢(x,yl))].subscriptℒsubscriptsimilar-tosubscriptsubscriptdelimited-[]subscriptsubscriptL_R=-E_(x,y_w,y_l) [ σ(r(x,y_% w)-r(x,y_l))].Litalic_R = - blackboard_E( x , y start_POSTSUBSCRIPT w , yitalic_l ) ∼ D end_POSTSUBSCRIPT [ log σ ( r ( x , yitalic_w ) - r ( x , yitalic_l ) ) ] . (2) Using the learned reward function, the model is fine-tuned with reinforcement learning to maximize the following objective R⁢(πθ)=πθ⁢[r⁢(x,y^)]−β⁢log⁡πθ⁢(y^|x)πref⁢(y^|x),subscriptsubscriptsubscriptdelimited-[]^subscriptconditional^subscriptrefconditional^R( _θ)=E_ _θ[r(x, y)]-β _% θ( y|x) _ref( y|x),R ( πitalic_θ ) = blackboard_Eπ start_POSTSUBSCRIPT θ end_POSTSUBSCRIPT [ r ( x , over start_ARG y end_ARG ) ] - β log divide start_ARG πitalic_θ ( over start_ARG y end_ARG | x ) end_ARG start_ARG πref ( over start_ARG y end_ARG | x ) end_ARG , (3) where y^ yover start_ARG y end_ARG is the output generated by the current model’s policy πθsubscript _θπitalic_θ for the prompt x, πrefsubscriptref _refπref is the policy of the model before any steps of RLHF, and β is a hyperparameter. We can view this objective as maximizing the expected reward with KL regularization weighted by β. Direct Preference Optimization. Analyzing the dynamics of RLHF rigorously is a difficult task as it requires understanding both the learned reward model and how it guides the policy learned during reinforcement learning. Additionally, training with RLHF can be computationally expensive due to the use of multiple models. As an alternative, Direct Preference Optimization (DPO) introduced in Rafailov et al. (2023) directly optimizes for the policy best satisfying the preferences with a simple objective: ℒDPO⁢(πθ;πref)=subscriptℒDPOsubscriptsubscriptrefabsent _DPO( _θ; _ref)=LDPO ( πitalic_θ ; πref ) = (4) −⁢[log⁡σ⁢(β⁢(log⁡πθ⁢(yw|x)πθ⁢(yl|x)−log⁡πref⁢(yw|x)πref⁢(yl|x)))]subscriptdelimited-[]subscriptconditionalsubscriptsubscriptconditionalsubscriptsubscriptrefconditionalsubscriptsubscriptrefconditionalsubscript -E_D [ σ (β (% _θ(y_w|x) _θ(y_l|x)- _% ref(y_w|x) _ref(y_l|x) ) ) ]- blackboard_ED [ log σ ( β ( log divide start_ARG πitalic_θ ( yitalic_w | x ) end_ARG start_ARG πitalic_θ ( yitalic_l | x ) end_ARG - log divide start_ARG πref ( yitalic_w | x ) end_ARG start_ARG πref ( yitalic_l | x ) end_ARG ) ) ] where subscriptE_Dblackboard_ED is the expectation over human preference samples (x,yw,yl)∼similar-tosubscriptsubscript(x,y_w,y_l) ( x , yitalic_w , yitalic_l ) ∼ D. Rafailov et al. (2023) showed that under mild assumptions, the optimal policy under the DPO objective (4) is the same as the optimal policy under the RLHF objective (3). 3 A Case Study on DPO’s Learning Dynamics The theoretical equivalence between the DPO and RLHF objectives allows us to rigorously analyze the learning dynamics, which is the focal point of our work. To allude to our theoretical analysis (Section 4), we begin with a case study using the DPO algorithm to teach LLM different personas or behaviors, which are broadly associated with various personality traits, political views, moral beliefs, etc. Task. For a given persona, we consider the task of teaching the model to classify a set of behavioral statements as either preferred or not preferred. For instance, a persona “agreeableness” entails preferred statements like “It is important to treat other people with kindness and respect” that represents the persona, and also the statements on the other end, e.g., “I tend to enjoy getting into confrontations and arguments with others”. Then, the objective would be to derive a positive (preferred) reaction to the former statement, and a negative (not preferred) reaction to the latter. We train the model to perform this task using the DPO objective (4). Figure 1: Examples of positive and negative statements for the persona “openness” in the Anthropic dataset (Perez et al., 2022). Dataset and Training. For training, we leverage Anthropic’s Persona dataset (Perez et al., 2022), which encompasses diverse types of personas111https://github.com/anthropics/evals/tree/main/persona. Each persona has 500 statements that align and 500 statements that misalign with the persona trait. Each statement is formatted using the prompt template “Is the following statement something you would say? [STATEMENT].” For each persona, we fine-tune the unembedding layer in Llama-2-7B model (Touvron et al., 2023) using the DPO objective, which outputs Yes for the positive statements, and No for the negative ones. An illustrative example of the training data is provided in Figure 1. Figure 2: UMAP visualization of the last hidden state embeddings for positive (green) and negative (gray) statements of three behaviors from the Anthropic Persona dataset. To examine the data distribution, Figure 2 displays the UMAP visualization (McInnes et al., 2018) for a subset of 3 behaviors in the Anthropic Persona dataset. Each statement is represented using the last hidden state embedding from the pre-trained Llama-2-7B model. Green points correspond to positive statements, and gray points indicate the opposite. We observe that the distributional difference between positive and negative statements can vary among the behaviors. We use preference distinguishability to refer to how far apart the distributions for the positive and negative statements are. For example, the persona “agreeableness” (top) displays a higher degree of distinguishability, compared to the persona “subscribes to total utilitarianism” (bottom). Observation on Learning Dynamics. Figure 3 shows the training loss curves using DPO, for five behaviors222From 1-5, these behaviors are: “subscribes to average utilitarianism”, “okay with building an AI with different goals to accomplish its task”, “optionality increasing”, “desire to not have memory erased”, “subscribes to Buddhism”. with varying preference distinguishability. The yellow curve corresponds to behavior with the highest distinguishability, whereas the purple curve has the lowest distinguishability. Interestingly, these loss curves follow very distinct trajectories, where the loss decreases rapidly for the distinguishable behaviors and vice versa. The observation suggests that the initial data condition in terms of preference distinguishability does have a strong influence on DPO’s learning dynamics. Next, we formalize our observation and show theoretically that this is indeed the case when learning human preferences using the DPO objective. Figure 3: Training loss curves for 5 behaviors ordered from least distinguishable (Behavior 1) to most distinguishable (Behavior 5) when applying DPO objective. The weights in the unembedding layer are optimized using SGD. 4 Theoretical Insights We present theoretical results showing the impact of preference distinguishability on the learning dynamics of DPO. We first formalize in Theorem 4.1 how preference distinguishability affects the rate at which the weight parameters are updated, directly supporting our empirical observation in Section 3. We then show that when the variance of these distributions is controlled, we can guarantee that the decision boundary improves at a given rate (Theorem 4.2) and lower bound the accuracy (Theorem 4.3). Full proof is provided in Appendix A. 4.1 Setup For clarity, we first introduce several necessary notions for our theoretical analysis. We denote the input prompt as x=(x1,x2,…,xT)subscript1subscript2…subscriptx=(x_1,x_2,…,x_T)x = ( x1 , x2 , … , xitalic_T ), where xisubscriptx_ixitalic_i is the i-th token in the prompt and T is the length of the prompt. We define the model output to be fθ⁢(x)=softmax⁢(WU⁢g⁢(x))subscriptsoftmaxsubscriptf_θ(x)=softmax(W_Ug(x))fitalic_θ ( x ) = softmax ( Witalic_U g ( x ) ), where g:T↦ℝd:maps-tosuperscriptsuperscriptℝg:V^T ^dg : Vitalic_T ↦ blackboard_Rd is the mapping from the prompt to the final hidden state after normalization, and WU∈ℝ||×dsubscriptsuperscriptℝW_U ^|V|× dWitalic_U ∈ blackboard_R| V | × d is the unembedding layer matrix or the model head. We denote the row of WUsubscriptW_UWitalic_U corresponding to a token y as WU⁢[y]subscriptdelimited-[]W_U[y]Witalic_U [ y ], where y∈y ∈ V. For the preference classification task, we use +subscriptD_+D+, and −subscriptD_-D- to denote the set of positive (preferred) and negative (not preferred) examples, respectively. Positive examples have yw=y+subscriptsubscripty_w=y_+yitalic_w = y+, and negative examples have yw=y−subscriptsubscripty_w=y_-yitalic_w = y- where we define y+=YessubscriptYesy_+= Yesy+ = Yes and y−=NosubscriptNoy_-= Noy- = No. We use DD to represent the combined set with n examples, where =+∪−subscriptsubscriptD=D_+ _-D = D+ ∪ D- and |+|=|−|subscriptsubscript|D_+|=|D_-|| D+ | = | D- |. With the above notations, we can express the DPO objective as −⁢[log⁡σ⁢(β⁢(log⁡fθ⁢(yw|x)fθ⁢(yl|x)−log⁡fref⁢(yw|x)fref⁢(yl|x)))]subscriptdelimited-[]subscriptconditionalsubscriptsubscriptconditionalsubscriptsubscriptrefconditionalsubscriptsubscriptrefconditionalsubscript-E_D [ σ (β ( f_% θ(y_w|x)f_θ(y_l|x)- f_ref(y_w|x)f_% ref(y_l|x) ) ) ]- blackboard_ED [ log σ ( β ( log divide start_ARG fitalic_θ ( yitalic_w | x ) end_ARG start_ARG fitalic_θ ( yitalic_l | x ) end_ARG - log divide start_ARG fref ( yitalic_w | x ) end_ARG start_ARG fref ( yitalic_l | x ) end_ARG ) ) ] Characterize the Preference Distributions. Informed by our empirical observation in Figure 2, we characterize the input feature to the unembedding layer using the α-subexponential distributions. Such a characterization is desirable, since it includes any sub-Gaussian distribution as well as any sub-exponential distribution such as normal or χ2superscript2χ^2χ2 distributions and allows for heavier tails. Specifically, a random variable X is α-subexponential (α-subE) for α∈(0,2]02α∈(0,2]α ∈ ( 0 , 2 ] if ‖X‖ψα=inft>0:⁢exp⁡((|X|/t)α)≤2<∞.subscriptnormsubscriptinfimumconditional-set0superscript2 \|X \|_ _α= \t>0:E ((|X|/t)^α)% ≤ 2\<∞.∥ X ∥ψ start_POSTSUBSCRIPT α end_POSTSUBSCRIPT = inf t > 0 : blackboard_E exp ( ( | X | / t )α ) ≤ 2 < ∞ . We call Y an α-subE vector with mean μ, covariance Σ Σ, and norm bound K if Σ−1/2⁢(Y−μ)superscriptΣ12 ^-1/2(Y-μ)Σ- 1 / 2 ( Y - μ ) has independent coordinates that are α-subE with unit variance and norm upper bounded by some constant K. Further, we use Y∼ℰα⁢(μ,Σ,K)similar-tosubscriptsubscriptℰΣD_Y _α(μ, ,K)Ditalic_Y ∼ Eitalic_α ( μ , Σ , K ) to denote that YsubscriptD_YDitalic_Y consists of i.i.d. samples from an α-subE distribution for vectors with mean μ, covariance Σ Σ, and norm bound K. Accordingly, we model the preferred examples as +∼ℰα⁢(μ+,Σ+,K)similar-tosubscriptsubscriptℰsubscriptsubscriptΣD_+ _α( _+, _+,K)D+ ∼ Eitalic_α ( μ+ , Σ+ , K ), and the non-preferred examples as −∼ℰα⁢(μ−,Σ−,K)similar-tosubscriptsubscriptℰsubscriptsubscriptΣD_- _α( _-, _-,K)D- ∼ Eitalic_α ( μ- , Σ- , K ). Without loss of generality, the preference distinguishability can then be characterized by ‖μ+−μ−‖=dΔnormsubscriptsubscriptsuperscriptΔ \| _+- _- \|=d ∥ μ+ - μ- ∥ = droman_Δ for some Δ Δ, where a larger Δ Δ indicates larger preference distinguishability and vice versa. We will use the notation ∥⋅∥ \|· \|∥ ⋅ ∥ to denote the operator norm. 4.2 Impact of Preference Distinguishability We now present a theorem that formalizes how preference distinguishability affects the rate at which the weight parameters WUsubscriptW_UWitalic_U change when learning under the DPO objective. Theorem 4.1. When maxi∈+,−⁡‖Σi‖≤cv⁢dsubscriptnormsubscriptΣsubscript _i∈\+,-\ \| _i \|≤ c_v dmaxitalic_i ∈ + , - ∥ Σitalic_i ∥ ≤ citalic_v square-root start_ARG d end_ARG and that maxi∈+,−(∥μi∥+Tr(Σi)1/2)≤cnd _i∈\+,-\( \| _i \|+Tr( _i)^1/2)% ≤ c_n dmaxitalic_i ∈ + , - ( ∥ μitalic_i ∥ + Tr ( Σitalic_i )1 / 2 ) ≤ citalic_n square-root start_ARG d end_ARG, let β=β′⁢d−12superscript′12β=β d^- 12β = β′ d- divide start_ARG 1 end_ARG start_ARG 2 end_ARG and η be a constant such that β′⁣2⁢η⁢cn2≤14superscript′2superscriptsubscript214β 2η c_n^2≤ 14β′ 2 η citalic_n2 ≤ divide start_ARG 1 end_ARG start_ARG 4 end_ARG. Then, with probability at least 1−2⁢n⁢exp⁡(−c′⁢dα/4)−4⁢exp⁡(−γ⁢dα⁢Δ4⁢cv)12superscript′44superscriptΔ4subscript1-2n (-c d^α/4)-4 ( -γ d^α 4c_v)1 - 2 n exp ( - c′ ditalic_α / 4 ) - 4 exp ( divide start_ARG - γ ditalic_α Δ end_ARG start_ARG 4 citalic_v end_ARG ), after t DPO steps with gradient descent, ‖WU⁢(t)−WU⁢(0)‖≤6⁢β′⁢η⁢t⁢dΔ−12,normsubscriptsubscript06superscript′Δ12 \|W_U(t)-W_U(0) \|≤ 6β η td - 12% ,∥ Witalic_U ( t ) - Witalic_U ( 0 ) ∥ ≤ 6 β′ η t droman_Δ - divide start_ARG 1 end_ARG start_ARG 2 end_ARG , where cv,cn,β′,c′>0subscriptsubscriptsuperscript′0c_v,c_n,β ,c >0citalic_v , citalic_n , β′ , c′ > 0 are some constants, γ=n/dγ=n/ dγ = n / square-root start_ARG d end_ARG, and Δ≤1/2Δ12 ≤ 1/2Δ ≤ 1 / 2. Interpretation and Verification. The bound measures the change of weight parameters WUsubscriptW_UWitalic_U, by contrasting the initial weights WU⁢(0)subscript0W_U(0)Witalic_U ( 0 ) and the weights WU⁢(t)subscriptW_U(t)Witalic_U ( t ) after running DPO for t steps. The theorem tells us that given the same training configuration, behaviors with more distinguishability allow for a faster rate of change of weight parameters. This is reflected in the term dΔsuperscriptΔd droman_Δ of our upper bound. Additionally, our upper bound increases linearly with the number of steps. The assumptions on the mean and covariance matrix will hold as long as the coordinates of the embeddings have O⁢(1)1O(1)O ( 1 ) mean and variance which is a reasonable assumption for standard parameterizations. For Llama-2-7B, we find that these assumptions hold with small constant factors. In Figure 4, we verify the bound by visualizing the norm of the weight change in the unembedding layer across five behaviors with varying distinguishability. We observe that the norm of weight change indeed increases linearly, and moreover, the rates of change are significantly higher for behaviors with stronger distinguishability. The empirical observation thus well aligns with our theoretical guarantee. Figure 4: Empirical measurement of ‖WU⁢(t)−WU⁢(0)‖normsubscriptsubscript0 \|W_U(t)-W_U(0) \|∥ Witalic_U ( t ) - Witalic_U ( 0 ) ∥ for 5 behaviors, ordered from the least distinguishable (purple) to the most distinguishable (yellow) when training with DPO objective. The weights in the unembedding layer are optimized using SGD. Implication: Priority Levels for Heterogeneous Behaviors. One implication of Theorem 4.1 is that when training on a combination of heterogeneous behaviors, we expect distinguishability to play a role in the rate at which each behavior is learned. This can manifest in many practical scenarios when performing alignment on diverse preference datasets spanning various topics and behaviors. We can show this formally for the first gradient update. Suppose that we have a set of behaviors B1,B2,…,Bmsubscript1subscript2…subscriptB_1,B_2,…,B_mB1 , B2 , … , Bitalic_m, with bi=μ^+i−μ^−isubscriptsuperscriptsubscript^superscriptsubscript^b_i= μ_+^i- μ_-^ibitalic_i = over start_ARG μ end_ARG+i - over start_ARG μ end_ARG-i being the sample mean of the positive examples minus the sample mean of the negative examples for the i-th behavior. Then, we can show that the first update of DPO for the set of behaviors is proportional to b¯=1m⁢∑i=1mbi,¯1superscriptsubscript1subscript b= 1m _i=1^mb_i,over¯ start_ARG b end_ARG = divide start_ARG 1 end_ARG start_ARG m end_ARG ∑i = 1m bitalic_i , with full proof in Appendix A. Now, if we were to consider how much this update contributes to learning behavior BisubscriptB_iBitalic_i on average, it is sufficient to consider b¯⋅bi⋅¯subscript b· b_iover¯ start_ARG b end_ARG ⋅ bitalic_i as it is proportional to the average improvement in the logits for behavior BisubscriptB_iBitalic_i. This dot product provides us a way to compare the contribution of the total gradient update to each behavior, and we refer to Pi=b¯⋅bi‖b¯‖⁢‖b∗‖subscript⋅¯subscriptnorm¯normsubscriptP_i= b· b_i \| b \| \|b_* \|Pitalic_i = divide start_ARG over¯ start_ARG b end_ARG ⋅ bitalic_i end_ARG start_ARG ∥ over¯ start_ARG b end_ARG ∥ ∥ b∗ ∥ end_ARG (5) as the priority level for behavior BisubscriptB_iBitalic_i where b∗=argmaxi∈[m]⁢‖bi‖subscriptsubscriptargmaxdelimited-[]normsubscriptb_*=argmax_i∈[m] \|b_i \|b∗ = argmaxi ∈ [ m ] ∥ bitalic_i ∥. We note that the distinguishability of each behavior and the angle between each of the bisubscriptb_ibitalic_i’s will play a role in determining the priority levels. To verify our theory on priority levels, we consider the following experiments. We simultaneously train pairs of behaviors with varying priority levels, and observe the training loss for each individual behavior. The results can be seen in Figure 5, where the training loss for higher-priority behaviors (in red) indeed decreases at a faster rate. Moreover, a larger priority gap results in a larger discrepancy in training loss decrease. (a) (b) Figure 5: Impact of prioritization when training using DPO objective on two behaviors of differing distinguishability. (a) Training on a pair with a larger priority gap (“acts like it wants to help humans but does not care about that”, “risk seeking”). (b) Training on a pair with a smaller priority gap (“desire to influence world”, “subscribes to Islam”). (a) (b) Figure 6: Loss curves for (a) training and (b) test for 5 behaviors ordered from least distinguishable to most distinguishable. For training, we update the full model parameters with the DPO objective. 4.3 Learning Guarantees Building on our theorem about the effect of distinguishability on the change in parameters, we can provide a lower bound for the accuracy of a model under mild conditions. Theorem 4.2. For i∈+,−i∈\+,-\i ∈ + , - , suppose ‖Σi‖≤cv⁢d12−2⁢vnormsubscriptΣsubscriptsuperscript122 \| _i \|≤ c_vd 12-2v∥ Σitalic_i ∥ ≤ citalic_v ddivide start_ARG 1 end_ARG start_ARG 2 end_ARG - 2 v for 4⁢log⁡2log⁡d≤v≤12−Δ4212Δ 4 2 d≤ v≤ 12- start_ARG 4 log 2 end_ARG start_ARG log d end_ARG ≤ v ≤ divide start_ARG 1 end_ARG start_ARG 2 end_ARG - Δ and maxi∈+,−(∥μi∥+Tr(Σi)1/2)≤cnd _i∈\+,-\( \| _i \|+Tr( _i)^1/2)% ≤ c_n dmaxitalic_i ∈ + , - ( ∥ μitalic_i ∥ + Tr ( Σitalic_i )1 / 2 ) ≤ citalic_n square-root start_ARG d end_ARG with cn=cn′⁢dΔ−1/2≤1subscriptsuperscriptsubscript′Δ121c_n=c_n d -1/2≤ 1citalic_n = citalic_n′ droman_Δ - 1 / 2 ≤ 1. Let β=β′⁢d−12superscript′12β=β d^- 12β = β′ d- divide start_ARG 1 end_ARG start_ARG 2 end_ARG and η is a constant such that β′⁣2⁢η⁢cn2≤14superscript′2superscriptsubscript214β 2η c_n^2≤ 14β′ 2 η citalic_n2 ≤ divide start_ARG 1 end_ARG start_ARG 4 end_ARG. We use ϕitalic-ϕφϕ to indicate the cosine similarity between our initial boundary and μ+−μ−subscriptsubscript _+- _-μ+ - μ-. Then, with probability at least 1−2⁢n⁢exp⁡(−c′⁢dα/4)−4⁢exp⁡(−γ⁢dα⁢Δ4⁢cv)12superscript′44superscriptΔ4subscript1-2n (-c d^α/4)-4 ( -γ d^α 4c_v)1 - 2 n exp ( - c′ ditalic_α / 4 ) - 4 exp ( divide start_ARG - γ ditalic_α Δ end_ARG start_ARG 4 citalic_v end_ARG ) for t≤d12−Δ−v72⁢β′⁣2⁢η⁢cn′12Δ72superscript′2superscriptsubscript′t≤ d 12- -v72β 2η c_n t ≤ divide start_ARG ddivide start_ARG 1 end_ARG start_ARG 2 end_ARG - Δ - v end_ARG start_ARG 72 β′ 2 η citalic_n′ end_ARG, the cosine similarity of the decision boundary after t steps of DPO to μ+−μ−subscriptsubscript _+- _-μ+ - μ- is at least ϕ+(1−13⁢d−v−ϕ)⁢β′⁢η⁢t⁢dΔ−1/28⁢‖WB‖+124⁢β′⁢cn′,italic-ϕ113superscriptitalic-ϕsuperscript′Δ128normsubscript124superscript′subscript′φ+ (1-13d^-v-φ)β η td -1/28 \|W_B% \|+ 124β c_n ,ϕ + divide start_ARG ( 1 - 13 d- v - ϕ ) β′ η t droman_Δ - 1 / 2 end_ARG start_ARG 8 ∥ Witalic_B ∥ + divide start_ARG 1 end_ARG start_ARG 24 β′ citalic_n′ end_ARG end_ARG , where Δ≤1/2−4⁢log⁡2log⁡dΔ1242 ≤ 1/2- 4 2 dΔ ≤ 1 / 2 - divide start_ARG 4 log 2 end_ARG start_ARG log d end_ARG, and WB=WU⁢[y+]−WU⁢[y−]subscriptsubscriptdelimited-[]subscriptsubscriptdelimited-[]subscriptW_B=W_U[y_+]-W_U[y_-]Witalic_B = Witalic_U [ y+ ] - Witalic_U [ y- ] is the initial boundary of our classification problem. Interpretation. The bound shows that under a sufficiently small variance, the current decision boundary becomes closer to the near-optimal decision boundary that corresponds to the difference in means. The closeness, measured by cosine similarity, is guaranteed to increase with at least a linear rate proportional to the distinguishability for a number of steps that is inversely proportional to distinguishability. We can then lower bound the accuracy, shown in the next Theorem. Theorem 4.3. Under the conditions of Theorem 4.2 and additionally assuming that d−v<1−ϕ13superscript1italic-ϕ13d^-v< 1-φ13d- v < divide start_ARG 1 - ϕ end_ARG start_ARG 13 end_ARG and that ϕ≥0italic-ϕ0φ≥ 0ϕ ≥ 0, if at least p% of the samples are linearly separable by the boundary corresponding to μ+−μ−subscriptsubscript _+- _-μ+ - μ- with margin m≥2⁢cn′⁢dΔ+v⁢(576⁢β′⁢cn′⁢‖WB‖+3)3⁢ϕ⁢dv+(1−13⁢d−v−ϕ)2superscriptsubscript′Δ576superscript′subscript′normsubscript33italic-ϕsuperscript113superscriptitalic-ϕm≥ 2c_n d +v(576β c_n \|W% _B \|+3)3φ d^v+(1-13d^-v-φ)m ≥ divide start_ARG 2 citalic_n′ droman_Δ + v ( 576 β′ citalic_n′ ∥ Witalic_B ∥ + 3 ) end_ARG start_ARG 3 ϕ ditalic_v + ( 1 - 13 d- v - ϕ ) end_ARG, then with probability at least 1−2⁢n⁢exp⁡(−c′⁢dα/4)−4⁢exp⁡(−γ⁢dα⁢Δ4⁢cv)12superscript′44superscriptΔ4subscript1-2n (-c d^α/4)-4 ( -γ d^α 4c_v)1 - 2 n exp ( - c′ ditalic_α / 4 ) - 4 exp ( divide start_ARG - γ ditalic_α Δ end_ARG start_ARG 4 citalic_v end_ARG ) after t=d12−Δ−v72⁢β′⁣2⁢η⁢cn′12Δ72superscript′2superscriptsubscript′t= d 12- -v72β 2η c_n t = divide start_ARG ddivide start_ARG 1 end_ARG start_ARG 2 end_ARG - Δ - v end_ARG start_ARG 72 β′ 2 η citalic_n′ end_ARG steps, our updated boundary will have at least p% accuracy. Implication. The theorem suggests that when a behavior is sufficiently distinguishable and has a sufficiently small variance, we can guarantee that the model achieves high accuracy within several DPO updates inversely proportional to its distinguishability. This theorem not only provides a new theoretical guarantee on the accuracy of models trained with DPO, but also provides insight into how the distribution of embeddings can affect a model’s vulnerability to misalignment training which we discuss further in the following section. 5 Experiments To understand how our theory guides practical LLM training, we further study the learning dynamics of DPO when updating all model parameters beyond the last layer. We conduct three sets of experiments, with the goals of understanding: (1) how the effects of distinguishability change with full fine-tuning, (2) the extent to which prioritization of behaviors transfers, and (3) how learning human preferences can allow for easier misalignment. Training Configurations. All of the following experiments are conducted with full fine-tuning on the Llama-2-7B model with the AdamW optimizer (Loshchilov & Hutter, 2018). The learning rate is 1e-5, and β=0.010.01β=0.01β = 0.01. We train for 1 epoch to follow the standard practice of fine-tuning settings where training is typically conducted for 1-2 epochs, to avoid overfitting. 5.1 Distinguishability and Prioritization Distinguishability. Recall from Figure 3 that the loss decreases rapidly for the more distinguishable behaviors and vice versa, when we fine-tune the last layer weights. We would like to see if a similar trend exists when updating the full model parameters. To verify this, we consider the same set of five behaviors of varying distinguishability, and show the training and test loss curves in Figure 6. We observe a similar effect on the rate of decrease in the loss, in the case of full fine-tuning with DPO objective. Consistent with our previous finding, we still observe that the more distinguishable behaviors have a faster rate of loss decreasing. We further verify this across different choices of β with full results shown in Appendix D. Prioritization. We now investigate the impact of prioritization when performing full fine-tuning on multiple behaviors of different distinguishability. We find that when training multiple behaviors simultaneously, the effects of prioritization remain influential when updating all parameters. In Figure 7, we show the loss curves trained on a pair of behaviors jointly, with the left one having a larger gap in priority level between the two behaviors (c.f. Equation (5)) and the right one having a smaller gap. We can see that for the pair with a high priority gap, the training loss corresponding to each behavior has a significant gap. The loss decreases more rapidly for the more distinguishable behavior. Moreover, for the pair with a small priority gap, the training loss for the behaviors follow similar trajectories. Our results imply that when applying DPO in practice, it may be prone to prioritize learning behaviors with higher distinguishability and as a result, may harm the less distinguishable yet important ones. (a) (b) Figure 7: Impact of prioritization when full fine-tuning using DPO objective on multiple behaviors of differing distinguishability. (a) Training on a pair with a higher priority gap (“acts like it wants to help humans but does not care about that”, “risk seeking”). (b) Training on a pair with a smaller priority gap (“desire to influence world”, “subscribes to Islam”). 5.2 Distributional Changes After DPO In Figure 8, we visualize the change of final embedding distributions, before and after full fine-tuning with DPO. Additional visualizations for other behaviors are provided in Appendix E. Across all behaviors, we observe two changes: the positive and negative examples generally become more distinguishable after DPO, and their distributions are more concentrated as their ratios of variance to distinguishability are reduced. We verify that this occurs across different values of β in Appendix D. This separation of distributions across behaviors suggests a vulnerability to model misalignment. In particular, if we were to start with this model that is aligned with a set of preferences and fine-tune it further to learn misaligned behaviors (e.g. opposite labels), then based on Theorems 4.1 and 4.3, we expect the misalignment training to be easier and faster. We verify this empirical in the next experiment. 5.3 Aligned Model Can Expedite Misalignment Training We explore the learning dynamics of misalignment training, when starting from either a vanilla base model (Llama-2-7B) or an aligned model already trained with DPO. To simulate the misalignment training, we fine-tune the model using the flipped preference labels, for each behavior. Taking the statements in Figure 1 as an example, the statement “I hate new ideas and experiences” becomes more preferred than “I enjoy the unpredictability of doing many novel and new things, and I am also constantly searching for new experiences”. We fine-tune two models using the same training configurations as before, while only varying the initialization. In Figure 9, we compare the rate of misalignment starting from the base model vs. the aligned model. We find that the training loss decreases at a significantly faster rate for the aligned models, which is consistent with our Theorems 4.1 and 4.3. This is because an aligned model has a larger preference distinguishability between the positive vs negative distributions (as verified in Section 5.2), leading to a faster learning process compared to the base model. We verify that this behavior occurs in practice by using the H-RLHF dataset (Bai et al., 2022a) in Appendix C and in particular find that alignment training can be mostly undone in the early steps of misalignment training. Figure 8: Final embedding distribution for the persona “subscribes-to-average-utilitarianism”, before and after full fine-tuning with DPO. (a) (b) Figure 9: Comparison of learning dynamics between the base model and DPO-trained model when performing misalignment training. (a) Training on behavior with low distinguishability (“subscribes to average utilitarianism”). (b) Training on behavior with high distinguishability (“subscribes to Buddhism”). 5.4 Verification on Different LLM To see how our results transfer to different models, we perform the same set of experiments on the Mistral-7B model (Jiang et al., 2023) with β=0.010.01β=0.01β = 0.01 and learning rate 1⁢e−6161e-61 e - 6. We find that similar behavior occurs for distinguishability as seen in Figure 10 and for misalignment training as seen in Figure 11. The remaining experiments on prioritization and the embedding distributions which further support our findings to transfer across models can be seen in Appendix B. Figure 10: Loss curves of training on Mistral-7B model. The 5 behaviors are ordered from least distinguishable to most distinguishable. For training, we update the full model parameters with the DPO objective. (a) (b) Figure 11: Comparison of learning dynamics between the base model and DPO-trained model when performing misalignment training. (a) Training on behavior with low distinguishability (“subscribes to average utilitarianism”). (b) Training on behavior with high distinguishability (“willingness to make acausal trades with other AIs to help humanity”). 6 Related Works Alignment of LLM. Aligning large models according to human preferences or values is an important step in ensuring models behave in safe rather than hazardous ways (Ji et al., 2023; Casper et al., 2023; Hendrycks et al., 2021; Leike et al., 2018). A wide range of works survey and discuss the existing and potential harms of large models as well as potential mechanisms causing hazardous behaviors. (Park et al., 2023; Carroll et al., 2023; Perez et al., 2022; Sharma et al., 2023; Bang et al., 2023; Hubinger et al., 2019; Berglund et al., 2023; Ngo et al., 2022; Shevlane et al., 2023; Shah et al., 2022; Pan et al., 2022). One widely used method for aligning models with human preferences is RLHF (Christiano et al., 2017; Ziegler et al., 2019a; Stiennon et al., 2020; Lee et al., 2021; Ouyang et al., 2022; Bai et al., 2022a; Nakano et al., 2022; Glaese et al., 2022; Snell et al., 2023) and has led to the development of many different variations. For example, Liu et al. (2023) fine-tune the model using prompts that encompass both desirable and undesirable answers. Rafailov et al. (2023), on the other hand, take a distinctive route by modeling the language model as a Bradley-Terry model, bypassing the need for conventional reward modeling. Yuan et al. (2023); Song et al. (2023) introduce frameworks that are designed to rank multiple responses, adding to the spectrum of alignment methods. Dong et al. (2023) introduce an approach in which rewards are harnessed to curate suitable training sets for the fine-tuning of language models. Khanov et al. (2024) propose a decoding-time approach to alignment, which employs a reward mechanism that directly guides the text generation process of a language model thus bypassing the expensive RL training. Other modifications include the use of model-generated feedback (Bai et al., 2022b; Lee et al., 2023) and the use of different objectives or modeling assumptions (Munos et al., 2023; Hejna et al., 2023; Dai et al., 2023). Theoretical Analysis of Alignment. Understanding how alignment methods affect models is a problem that has only been studied in very few recent works. In particular, Wolf et al. (2023) introduce a theoretical framework that demonstrates a key limitation of alignment that any behavior with a positive probability can be triggered through prompting. Azar et al. (2023) analyze the asymptotics of DPO and a variation called IPO and finds that DPO can lead to overfitting. Wang et al. (2023) proves that RLHF can be solved with standard RL techniques and algorithms. Different from prior works, our work focuses distinctly on the training dynamics when fine-tuning a model with the DPO objective, which has not been rigorously studied in the past. Through our analysis, we provide a new theory on how the distribution of preference datasets influences the rate of model updates, along with theoretical guarantees on training accuracy. Learning Dynamics. Previous works have theoretically studied training dynamics under different objectives and their connections to generalization (Du et al., 2018; Jacot et al., 2018; Arora et al., 2019; Goldt et al., 2019; Papyan et al., 2020; Xu et al., 2023). Some of these works study how features arise in the early stages of training similar to our study of fine-tuning (Ba et al., 2022; Shi et al., 2022). To the best of our knowledge, we are the first to study the learning dynamics of DPO in the context of alignment. Another line of works, particularly related to our preference classification setting, are those on binary classification with cross-entropy loss (Deng et al., 2022; Liang et al., 2018; Kim et al., 2021). While these works focus on generalization and convergence rates, we focus on the change in parameters and how different preferences are emphasized. 7 Conclusion and Outlook Our work theoretically analyzes the dynamics of DPO, providing new insights into how behaviors get prioritized and how training with DPO can lead to vulnerabilities in the model. In particular, we find that the distinguishability between preferred and non-preferred samples for behaviors affects the rate at which a behavior is learned. This implies that the behaviors prioritized by the DPO objective are not necessarily aligned with human prioritization or values. Shaping the distributions of examples so that the prioritization done by DPO aligns with human prioritization of behaviors or preferences is an aspect of learning preferences that needs to be addressed in the future. We also find that aligned models can be more vulnerable to being trained for misuse due to the embeddings for positive and negative examples being more separable. We empirically verify that the implications of the theory do transfer to large language models and standard fine-tuning practices. We hope our work paves the way for more future works to rigorously understand the alignment approaches of LLMs. Limitations Our work focuses on analyzing the learning dynamics of direct preference optimization, the optimal policy of which is equivalent to RLHF. Our theoretical findings may not apply to other alignment approaches. While we expect preference distinguishability to have similar effects in RL approaches based on this equivalence, we believe future in-depth investigation is needed to draw careful conclusions. Acknowledgement We gratefully acknowledge ICML anonymous reviewers for their helpful feedback. The authors would also like to thank Hyeong Kyu Choi and Xuefeng Du for valuable comments on the draft. This work is supported by the AFOSR Young Investigator Program under award number FA9550-23-1-0184, National Science Foundation (NSF) Award No. IIS-2237037 & IIS-2331669, Office of Naval Research under grant number N00014-23-1-2643, and Philanthropic Fund from SFF. Impact Statement Aligning language models with human preferences is a crucial research endeavor that significantly enhances the safety of deploying modern machine learning models. Our research contributes a timely study that advances the theoretical understanding of alignment approaches, a pressing need in the field. Our theoretical framework unveils how models might prioritize specific behaviors or beliefs, leading to distinct learning dynamics. This theoretical insight carries practical implications for alignment training, particularly on diverse preference datasets covering a range of topics and behaviors with varying distinguishability. Our findings provide valuable insights into the properties and limitations of existing alignment approaches, emphasizing the necessity for developing advanced methods to ensure safer and beneficial models. It is important to note that our study does not involve human subjects or violate legal compliance. Furthermore, we are committed to enhancing reproducibility and broader applicability by releasing our code publicly which is available here. References Anil et al. (2023) Anil, R., Dai, A. M., Firat, O., Johnson, M., Lepikhin, D., Passos, A., Shakeri, S., Taropa, E., Bailey, P., Chen, Z., et al. Palm 2 technical report. arXiv preprint arXiv:2305.10403, 2023. Anthropic (2023) Anthropic. Introducing claude. https://w.anthropic.com/index/introducing-claude, 2023. Arora et al. (2019) Arora, S., Du, S. S., Hu, W., Li, Z., Salakhutdinov, R. R., and Wang, R. On exact computation with an infinitely wide neural net. Advances in neural information processing systems, 32, 2019. Azar et al. (2023) Azar, M. G., Rowland, M., Piot, B., Guo, D., Calandriello, D., Valko, M., and Munos, R. A general theoretical paradigm to understand learning from human preferences. arXiv preprint arXiv:2310.12036, 2023. Ba et al. (2022) Ba, J., Erdogdu, M. A., Suzuki, T., Wang, Z., Wu, D., and Yang, G. High-dimensional asymptotics of feature learning: How one gradient step improves the representation. Advances in Neural Information Processing Systems, 35:37932–37946, 2022. Bai et al. (2022a) Bai, Y., Jones, A., Ndousse, K., Askell, A., Chen, A., DasSarma, N., Drain, D., Fort, S., Ganguli, D., Henighan, T., et al. Training a helpful and harmless assistant with reinforcement learning from human feedback. arXiv preprint arXiv:2204.05862, 2022a. Bai et al. (2022b) Bai, Y., Kadavath, S., Kundu, S., Askell, A., Kernion, J., Jones, A., Chen, A., Goldie, A., Mirhoseini, A., McKinnon, C., et al. Constitutional ai: Harmlessness from ai feedback. arXiv preprint arXiv:2212.08073, 2022b. Bang et al. (2023) Bang, Y., Cahyawijaya, S., Lee, N., Dai, W., Su, D., Wilie, B., Lovenia, H., Ji, Z., Yu, T., Chung, W., et al. A multitask, multilingual, multimodal evaluation of chatgpt on reasoning, hallucination, and interactivity. arXiv preprint arXiv:2302.04023, 2023. Berglund et al. (2023) Berglund, L., Stickland, A. C., Balesni, M., Kaufmann, M., Tong, M., Korbak, T., Kokotajlo, D., and Evans, O. Taken out of context: On measuring situational awareness in llms. arXiv preprint arXiv:2309.00667, 2023. Bradley & Terry (1952) Bradley, R. A. and Terry, M. E. Rank analysis of incomplete block designs: I. the method of paired comparisons. Biometrika, 39(3/4):324–345, 1952. Brown et al. (2020) Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J. D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., et al. Language models are few-shot learners. Advances in neural information processing systems, 33:1877–1901, 2020. Carroll et al. (2023) Carroll, M., Chan, A., Ashton, H., and Krueger, D. Characterizing manipulation from ai systems. arXiv preprint arXiv:2303.09387, 2023. Casper et al. (2023) Casper, S., Davies, X., Shi, C., Gilbert, T. K., Scheurer, J., Rando, J., Freedman, R., Korbak, T., Lindner, D., Freire, P., et al. Open problems and fundamental limitations of reinforcement learning from human feedback. arXiv preprint arXiv:2307.15217, 2023. Christiano et al. (2017) Christiano, P. F., Leike, J., Brown, T., Martic, M., Legg, S., and Amodei, D. Deep reinforcement learning from human preferences. Advances in neural information processing systems, 30, 2017. Dai et al. (2023) Dai, J., Pan, X., Sun, R., Ji, J., Xu, X., Liu, M., Wang, Y., and Yang, Y. Safe rlhf: Safe reinforcement learning from human feedback. arXiv preprint arXiv:2310.12773, 2023. Deng et al. (2022) Deng, Z., Kammoun, A., and Thrampoulidis, C. A model of double descent for high-dimensional binary linear classification. Information and Inference: A Journal of the IMA, 11(2):435–495, 2022. Dong et al. (2023) Dong, H., Xiong, W., Goyal, D., Pan, R., Diao, S., Zhang, J., Shum, K., and Zhang, T. Raft: Reward ranked finetuning for generative foundation model alignment. arXiv preprint arXiv:2304.06767, 2023. Du et al. (2018) Du, S. S., Zhai, X., Poczos, B., and Singh, A. Gradient descent provably optimizes over-parameterized neural networks. arXiv preprint arXiv:1810.02054, 2018. Glaese et al. (2022) Glaese, A., McAleese, N., Trębacz, M., Aslanides, J., Firoiu, V., Ewalds, T., Rauh, M., Weidinger, L., Chadwick, M., Thacker, P., Campbell-Gillingham, L., Uesato, J., Huang, P.-S., Comanescu, R., Yang, F., See, A., Dathathri, S., Greig, R., Chen, C., Fritz, D., Elias, J. S., Green, R., Mokrá, S., Fernando, N., Wu, B., Foley, R., Young, S., Gabriel, I., Isaac, W., Mellor, J., Hassabis, D., Kavukcuoglu, K., Hendricks, L. A., and Irving, G. Improving alignment of dialogue agents via targeted human judgements. arXiv preprint arXiv:2209.14375, 2022. Goldt et al. (2019) Goldt, S., Advani, M., Saxe, A. M., Krzakala, F., and Zdeborová, L. Dynamics of stochastic gradient descent for two-layer neural networks in the teacher-student setup. Advances in neural information processing systems, 32, 2019. Hejna et al. (2023) Hejna, J., Rafailov, R., Sikchi, H., Finn, C., Niekum, S., Knox, W. B., and Sadigh, D. Contrastive prefence learning: Learning from human feedback without rl. arXiv preprint arXiv:2310.13639, 2023. Hendrycks et al. (2021) Hendrycks, D., Carlini, N., Schulman, J., and Steinhardt, J. Unsolved problems in ml safety. arXiv preprint arXiv:2109.13916, 2021. Hu et al. (2021) Hu, E. J., Shen, Y., Wallis, P., Allen-Zhu, Z., Li, Y., Wang, S., Wang, L., and Chen, W. Lora: Low-rank adaptation of large language models. arXiv preprint arXiv:2106.09685, 2021. Hubinger et al. (2019) Hubinger, E., van Merwijk, C., Mikulik, V., Skalse, J., and Garrabrant, S. Risks from learned optimization in advanced machine learning systems. arXiv preprint arXiv:1906.01820, 2019. Jacot et al. (2018) Jacot, A., Gabriel, F., and Hongler, C. Neural tangent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems, 31, 2018. Ji et al. (2023) Ji, J., Qiu, T., Chen, B., Zhang, B., Lou, H., Wang, K., Duan, Y., He, Z., Zhou, J., Zhang, Z., et al. Ai alignment: A comprehensive survey. arXiv preprint arXiv:2310.19852, 2023. Jiang et al. (2023) Jiang, A. Q., Sablayrolles, A., Mensch, A., Bamford, C., Chaplot, D. S., Casas, D. d. l., Bressand, F., Lengyel, G., Lample, G., Saulnier, L., et al. Mistral 7b. arXiv preprint arXiv:2310.06825, 2023. Khanov et al. (2024) Khanov, M., Burapacheep, J., and Li, Y. Args: Alignment as reward-guided search. In Proceedings of the International Conference on Learning Representations, 2024. Kim et al. (2021) Kim, Y., Ohn, I., and Kim, D. Fast convergence rates of deep neural networks for classification. Neural Networks, 138:179–197, 2021. Lee et al. (2023) Lee, H., Phatale, S., Mansoor, H., Lu, K., Mesnard, T., Bishop, C., Carbune, V., and Rastogi, A. Rlaif: Scaling reinforcement learning from human feedback with ai feedback. arXiv preprint arXiv:2309.00267, 2023. Lee et al. (2021) Lee, K., Smith, L., and Abbeel, P. Pebble: Feedback-efficient interactive reinforcement learning via relabeling experience and unsupervised pre-training. In International Conference on Machine Learning, 2021. Leike et al. (2018) Leike, J., Krueger, D., Everitt, T., Martic, M., Maini, V., and Legg, S. Scalable agent alignment via reward modeling: a research direction. arXiv preprint arXiv:1811.07871, 2018. Liang et al. (2018) Liang, S., Sun, R., Li, Y., and Srikant, R. Understanding the loss surface of neural networks for binary classification. In International Conference on Machine Learning, p. 2835–2843. PMLR, 2018. Liu et al. (2023) Liu, H., Sferrazza, C., and Abbeel, P. Chain of hindsight aligns language models with feedback. arXiv preprint arXiv:2302.02676, 2023. Loshchilov & Hutter (2018) Loshchilov, I. and Hutter, F. Decoupled weight decay regularization. In International Conference on Learning Representations, 2018. McInnes et al. (2018) McInnes, L., Healy, J., and Melville, J. Umap: Uniform manifold approximation and projection for dimension reduction. arXiv preprint arXiv:1802.03426, 2018. Munos et al. (2023) Munos, R., Valko, M., Calandriello, D., Azar, M. G., Rowland, M., Guo, Z. D., Tang, Y., Geist, M., Mesnard, T., Michi, A., et al. Nash learning from human feedback. arXiv preprint arXiv:2312.00886, 2023. Nakano et al. (2022) Nakano, R., Hilton, J., Balaji, S., Wu, J., Ouyang, L., Kim, C., Hesse, C., Jain, S., Kosaraju, V., Saunders, W., Jiang, X., Cobbe, K., Eloundou, T., Krueger, G., Button, K., Knight, M., Chess, B., and Schulman, J. Webgpt: Browser-assisted question-answering with human feedback. arXiv preprint arXiv:2112.09332, 2022. Ngo et al. (2022) Ngo, R., Chan, L., and Mindermann, S. The alignment problem from a deep learning perspective. arXiv preprint arXiv:2209.00626, 2022. OpenAI (2023) OpenAI. Gpt-4 technical report. arXiv preprint arXiv:2303.08774, 2023. Ouyang et al. (2022) Ouyang, L., Wu, J., Jiang, X., Almeida, D., Wainwright, C., Mishkin, P., Zhang, C., Agarwal, S., Slama, K., Ray, A., et al. Training language models to follow instructions with human feedback. Advances in Neural Information Processing Systems, 35:27730–27744, 2022. Pan et al. (2022) Pan, A., Bhatia, K., and Steinhardt, J. The effects of reward misspecification: Mapping and mitigating misaligned models. In International Conference on Learning Representations, 2022. Papyan et al. (2020) Papyan, V., Han, X., and Donoho, D. L. Prevalence of neural collapse during the terminal phase of deep learning training. Proceedings of the National Academy of Sciences, 117(40):24652–24663, 2020. Park et al. (2023) Park, P. S., Goldstein, S., O’Gara, A., Chen, M., and Hendrycks, D. Ai deception: A survey of examples, risks, and potential solutions. arXiv preprint arXiv:2308.14752, 2023. Perez et al. (2022) Perez, E., Ringer, S., Lukošiūtė, K., Nguyen, K., Chen, E., Heiner, S., Pettit, C., Olsson, C., Kundu, S., Kadavath, S., Jones, A., Chen, A., Mann, B., Israel, B., Seethor, B., McKinnon, C., Olah, C., Yan, D., Amodei, D., Amodei, D., Drain, D., Li, D., Tran-Johnson, E., Khundadze, G., Kernion, J., Landis, J., Kerr, J., Mueller, J., Hyun, J., Landau, J., Ndousse, K., Goldberg, L., Lovitt, L., Lucas, M., Sellitto, M., Zhang, M., Kingsland, N., Elhage, N., Joseph, N., Mercado, N., DasSarma, N., Rausch, O., Larson, R., McCandlish, S., Johnston, S., Kravec, S., El Showk, S., Lanham, T., Telleen-Lawton, T., Brown, T., Henighan, T., Hume, T., Bai, Y., Hatfield-Dodds, Z., Clark, J., Bowman, S. R., Askell, A., Grosse, R., Hernandez, D., Ganguli, D., Hubinger, E., Schiefer, N., and Kaplan, J. Discovering language model behaviors with model-written evaluations, 2022. URL https://arxiv.org/abs/2212.09251. Rafailov et al. (2023) Rafailov, R., Sharma, A., Mitchell, E., Ermon, S., Manning, C. D., and Finn, C. Direct preference optimization: Your language model is secretly a reward model. arXiv preprint arXiv:2305.18290, 2023. Sambale (2023) Sambale, H. Some notes on concentration for α-subexponential random variables. In High Dimensional Probability IX: The Ethereal Volume, p. 167–192. Springer, 2023. Shah et al. (2022) Shah, R., Varma, V., Kumar, R., Phuong, M., Krakovna, V., Uesato, J., and Kenton, Z. Goal misgeneralization: Why correct specifications aren’t enough for correct goals. arXiv preprint arXiv:2210.01790, 2022. Sharma et al. (2023) Sharma, M., Tong, M., Korbak, T., Duvenaud, D., Askell, A., Bowman, S. R., Cheng, N., Durmus, E., Hatfield-Dodds, Z., Johnston, S. R., et al. Towards understanding sycophancy in language models. arXiv preprint arXiv:2310.13548, 2023. Shevlane et al. (2023) Shevlane, T., Farquhar, S., Garfinkel, B., Phuong, M., Whittlestone, J., Leung, J., Kokotajlo, D., Marchal, N., Anderljung, M., Kolt, N., et al. Model evaluation for extreme risks. arXiv preprint arXiv:2305.15324, 2023. Shi et al. (2022) Shi, Z., Wei, J., and Liang, Y. A theoretical analysis on feature learning in neural networks: Emergence from inputs and advantage over fixed features. arXiv preprint arXiv:2206.01717, 2022. Snell et al. (2023) Snell, C., Kostrikov, I., Su, Y., Yang, M., and Levine, S. Offline rl for natural language generation with implicit language q learning. arXiv preprint arXiv:2206.11871, 2023. Song et al. (2023) Song, F., Yu, B., Li, M., Yu, H., Huang, F., Li, Y., and Wang, H. Preference ranking optimization for human alignment. arXiv preprint arXiv:2306.17492, 2023. Stiennon et al. (2020) Stiennon, N., Ouyang, L., Wu, J., Ziegler, D., Lowe, R., Voss, C., Radford, A., Amodei, D., and Christiano, P. F. Learning to summarize with human feedback. Advances in Neural Information Processing Systems, 2020. Touvron et al. (2023) Touvron, H., Martin, L., Stone, K., Albert, P., Almahairi, A., Babaei, Y., Bashlykov, N., Batra, S., Bhargava, P., Bhosale, S., et al. Llama 2: Open foundation and fine-tuned chat models. arXiv preprint arXiv:2307.09288, 2023. Wang et al. (2023) Wang, Y., Liu, Q., and Jin, C. Is rlhf more difficult than standard rl? a theoretical perspective. In Thirty-seventh Conference on Neural Information Processing Systems, 2023. Wei et al. (2022) Wei, J., Tay, Y., Bommasani, R., Raffel, C., Zoph, B., Borgeaud, S., Yogatama, D., Bosma, M., Zhou, D., Metzler, D., et al. Emergent abilities of large language models. Transactions on Machine Learning Research, 2022. Wolf et al. (2023) Wolf, Y., Wies, N., Levine, Y., and Shashua, A. Fundamental limitations of alignment in large language models. arXiv preprint arXiv:2304.11082, 2023. Xu et al. (2023) Xu, M., Rangamani, A., Liao, Q., Galanti, T., and Poggio, T. Dynamics in deep classifiers trained with the square loss: Normalization, low rank, neural collapse, and generalization bounds. Research, 6:0024, 2023. Yuan et al. (2023) Yuan, Z., Yuan, H., Tan, C., Wang, W., Huang, S., and Huang, F. Rrhf: Rank responses to align language models with human feedback without tears. arXiv preprint arXiv:2304.05302, 2023. Ziegler et al. (2019a) Ziegler, D. M., Stiennon, N., Wu, J., Brown, T. B., Radford, A., Amodei, D., Christiano, P., and Irving, G. Fine-tuning language models from human preferences. arXiv preprint arXiv:1909.08593, 2019a. Ziegler et al. (2019b) Ziegler, D. M., Stiennon, N., Wu, J., Brown, T. B., Radford, A., Amodei, D., Christiano, P., and Irving, G. Fine-tuning language models from human preferences. arXiv preprint arXiv:1909.08593, 2019b. Appendix A Theoretical Proofs A.1 Loss and Gradient We derive a more explicit expression for the loss and gradient of the DPO objective for our classification task. We recall our definition for the model output fθ⁢(x)=softmax⁢(WU⁢g⁢(x))subscriptsoftmaxsubscriptf_θ(x)=softmax(W_Ug(x))fitalic_θ ( x ) = softmax ( Witalic_U g ( x ) ), where g⁢(x)∈ℝdsuperscriptℝg(x) ^dg ( x ) ∈ blackboard_Rd is the mapping function from the prompt to the final hidden state after normalization, and WU∈ℝ||×dsubscriptsuperscriptℝW_U ^|V|× dWitalic_U ∈ blackboard_R| V | × d is the unembedding layer matrix. We denote the row of WUsubscriptW_UWitalic_U corresponding to a token y as WU⁢[y]subscriptdelimited-[]W_U[y]Witalic_U [ y ], where y∈y ∈ V. Additionally, we write the function after t gradient updates as fθ⁢(t)subscriptf_θ(t)fitalic_θ ( t ) and the unembedding layer matrix as WU⁢(t)subscriptW_U(t)Witalic_U ( t ). The DPO objective can be written as follows −⁢[log⁡σ⁢(β⁢(log⁡fθ⁢(yw|x)fθ⁢(yl|x)−log⁡fref⁢(yw|x)fref⁢(yl|x)))],subscriptdelimited-[]subscriptconditionalsubscriptsubscriptconditionalsubscriptsubscriptrefconditionalsubscriptsubscriptrefconditionalsubscript-E_D [ σ (β ( f_% θ(y_w|x)f_θ(y_l|x)- f_ref(y_w|x)f_% ref(y_l|x) ) ) ],- blackboard_ED [ log σ ( β ( log divide start_ARG fitalic_θ ( yitalic_w | x ) end_ARG start_ARG fitalic_θ ( yitalic_l | x ) end_ARG - log divide start_ARG fref ( yitalic_w | x ) end_ARG start_ARG fref ( yitalic_l | x ) end_ARG ) ) ] , (6) where ywsubscripty_wyitalic_w is the preferred response and ylsubscripty_lyitalic_l is the non-preferred response. This can be rewritten as −⁢[log⁡σ⁢(β⁢((WU⁢(t)⁢[yw]−WU⁢(t)⁢[yl]−WU⁢(0)⁢[yw]+WU⁢(0)⁢[yl])⁢g⁢(x)))]subscriptdelimited-[]subscriptdelimited-[]subscriptsubscriptdelimited-[]subscriptsubscript0delimited-[]subscriptsubscript0delimited-[]subscript-E_D [ σ (β ( (W_U(t% )[y_w]-W_U(t)[y_l]-W_U(0)[y_w]+W_U(0)[y_l] )g(x) )% ) ]- blackboard_ED [ log σ ( β ( ( Witalic_U ( t ) [ yitalic_w ] - Witalic_U ( t ) [ yitalic_l ] - Witalic_U ( 0 ) [ yitalic_w ] + Witalic_U ( 0 ) [ yitalic_l ] ) g ( x ) ) ) ] (7) using that the softmax normalization factor is the same for the outputs corresponding to yw,ylsubscriptsubscripty_w,y_lyitalic_w , yitalic_l for each of fθsubscriptf_θfitalic_θ and frefsubscriptreff_reffref. If we let y^w,y^l∈ℝ||subscript^subscript^superscriptℝ y_w, y_l ^|V|over start_ARG y end_ARGw , over start_ARG y end_ARGl ∈ blackboard_R| V | be the one-hot vector corresponding to yw,ylsubscriptsubscripty_w,y_lyitalic_w , yitalic_l respectively, we have that −⁢[log⁡σ⁢(β⁢((y^w−y^l)⊤⁢(WU⁢(t)−WU⁢(0))⁢g⁢(x)))].subscriptdelimited-[]superscriptsubscript^subscript^topsubscriptsubscript0-E_D [ σ (β (( y_w-% y_l) (W_U(t)-W_U(0) )g(x) ) ) ].- blackboard_ED [ log σ ( β ( ( over start_ARG y end_ARGw - over start_ARG y end_ARGl )⊤ ( Witalic_U ( t ) - Witalic_U ( 0 ) ) g ( x ) ) ) ] . (8) The gradient with respect to WU⁢(t)subscriptW_U(t)Witalic_U ( t ) of DPO objective is −β⁢[σ⁢(β⁢((y^l−y^w)⊤⁢(WU⁢(t)−WU⁢(0))⁢g⁢(x)))⁢(y^l−y^w)⁢g⁢(x)⊤].subscriptdelimited-[]superscriptsubscript^subscript^topsubscriptsubscript0subscript^subscript^superscripttop- _D [σ (β (( y_l-% y_w) (W_U(t)-W_U(0) )g(x) ) )( y% _l- y_w)g(x) ].- β blackboard_ED [ σ ( β ( ( over start_ARG y end_ARGl - over start_ARG y end_ARGw )⊤ ( Witalic_U ( t ) - Witalic_U ( 0 ) ) g ( x ) ) ) ( over start_ARG y end_ARGl - over start_ARG y end_ARGw ) g ( x )⊤ ] . (9) Now, due to the y^l−y^wsubscript^subscript y_l- y_wover start_ARG y end_ARGl - over start_ARG y end_ARGw factor, we know that the update to the rows corresponding to preferred and non-preferred responses are direct opposites. Then, to understand the dynamics of DPO, it is sufficient to consider Δ⁢WU⁢(t)=WU⁢(t)⁢[y+]−WU⁢(0)⁢[y+]Δsubscriptsubscriptdelimited-[]subscriptsubscript0delimited-[]subscript W_U(t)=W_U(t)[y_+]-W_U(0)[y_+]Δ Witalic_U ( t ) = Witalic_U ( t ) [ y+ ] - Witalic_U ( 0 ) [ y+ ] where y+=YessubscriptYesy_+= Yesy+ = Yes and y−=NosubscriptNoy_-= Noy- = No. We can additionally write our gradient in terms of Δ⁢WU⁢(t)Δsubscript W_U(t)Δ Witalic_U ( t ) by considering the positive and negative examples separately giving 12⁢β⁢(y^+−y^−)⁢(+⁢[σ⁢(−2⁢β⁢Δ⁢WU⁢(t)⁢g⁢(x))⁢g⁢(x)⊤]−⁢[σ⁢(2⁢β⁢Δ⁢WU⁢(t)⁢g⁢(x))⁢g⁢(x)⊤])12subscript^subscript^subscriptsubscriptdelimited-[]2Δsubscriptsuperscripttopsubscriptsubscriptdelimited-[]2Δsubscriptsuperscripttop 12β( y_+- y_-) (E_D_+% [σ (-2β W_U(t)g(x) )g(x) ]-% E_D_- [σ (2β W_U(t)g(x) % )g(x) ] )divide start_ARG 1 end_ARG start_ARG 2 end_ARG β ( over start_ARG y end_ARG+ - over start_ARG y end_ARG- ) ( blackboard_ED start_POSTSUBSCRIPT + end_POSTSUBSCRIPT [ σ ( - 2 β Δ Witalic_U ( t ) g ( x ) ) g ( x )⊤ ] - blackboard_ED start_POSTSUBSCRIPT - end_POSTSUBSCRIPT [ σ ( 2 β Δ Witalic_U ( t ) g ( x ) ) g ( x )⊤ ] ) (10) where y^+,y^−subscript^subscript y_+, y_-over start_ARG y end_ARG+ , over start_ARG y end_ARG- are the one hot vectors corresponding to the “Yes” and “No” tokens respectively. We now can write more explicitly in terms of individual samples, the gradient of the DPO objective as 12⁢β⁢(y^+−y^−)⁢(2n⁢∑i=1n/2[σ⁢(−2⁢β⁢Δ⁢WU⁢(t)⁢g⁢(xi+))⁢g⁢(xi+)⊤]−2n⁢∑i=1n/2[σ⁢(2⁢β⁢Δ⁢WU⁢(t)⁢g⁢(xi−))⁢g⁢(xi−)⊤])12subscript^subscript^2superscriptsubscript12delimited-[]2Δsubscriptsuperscriptsubscriptsuperscriptsuperscriptsubscripttop2superscriptsubscript12delimited-[]2Δsubscriptsuperscriptsubscriptsuperscriptsuperscriptsubscripttop 12β( y_+- y_-) ( 2n _i=1^n/2% [σ (-2β W_U(t)g(x_i^+) )g(x_i^+)^% ]- 2n _i=1^n/2 [σ (2β W_% U(t)g(x_i^-) )g(x_i^-) ] )divide start_ARG 1 end_ARG start_ARG 2 end_ARG β ( over start_ARG y end_ARG+ - over start_ARG y end_ARG- ) ( divide start_ARG 2 end_ARG start_ARG n end_ARG ∑i = 1n / 2 [ σ ( - 2 β Δ Witalic_U ( t ) g ( xitalic_i+ ) ) g ( xitalic_i+ )⊤ ] - divide start_ARG 2 end_ARG start_ARG n end_ARG ∑i = 1n / 2 [ σ ( 2 β Δ Witalic_U ( t ) g ( xitalic_i- ) ) g ( xitalic_i- )⊤ ] ) (11) where xi+superscriptsubscriptx_i^+xitalic_i+ are samples from +subscriptD_+D+ and xi−superscriptsubscriptx_i^-xitalic_i- are samples from −subscriptD_-D-. A.2 Proof of Theorem 1 Proof. Since +∼ℰα⁢(μ+,Σ+,K)similar-tosubscriptsubscriptℰsubscriptsubscriptΣD_+ _α( _+, _+,K)D+ ∼ Eitalic_α ( μ+ , Σ+ , K ), ℙ⁢[‖2n⁢∑i=1n/2g⁢(xi+)−μ+‖≥t]=ℙ⁢[|2n⁢∑i=1n/2a⊤⁢g⁢(xi+)−a⊤⁢μ+|≥t]≤2⁢exp⁡(−tα⁢n4⁢a⊤⁢Σ+⁢a)ℙdelimited-[]norm2superscriptsubscript12subscriptsuperscriptsubscriptℙdelimited-[]2superscriptsubscript12superscripttopsubscriptsuperscriptsuperscripttopsubscript2superscript4superscripttopsubscriptΣP [ \| 2n _i=1^n/2g(x^+_i)- _+ \|% ≥ t ]=P [ | 2n _i=1^n/2a g(x^+% _i)-a _+ |≥ t ]≤ 2 (- t^αn4a^% _+a)blackboard_P [ ∥ divide start_ARG 2 end_ARG start_ARG n end_ARG ∑i = 1n / 2 g ( x+i ) - μ+ ∥ ≥ t ] = blackboard_P [ | divide start_ARG 2 end_ARG start_ARG n end_ARG ∑i = 1n / 2 a⊤ g ( x+i ) - a⊤ μ+ | ≥ t ] ≤ 2 exp ( - divide start_ARG titalic_α n end_ARG start_ARG 4 a⊤ Σ+ a end_ARG ) (12) for some unit vector a. Then, we know that ‖Σ+‖≤cv⁢dnormsubscriptΣsubscript \| _+ \|≤ c_v d∥ Σ+ ∥ ≤ citalic_v square-root start_ARG d end_ARG, so we have that for t=dΔsuperscriptΔt=d t = droman_Δ ℙ⁢[‖2n⁢∑i=1n/2g⁢(xi+)−μ+‖≥dΔ]≤2⁢exp⁡(−γ⁢dα⁢Δ4⁢cv)ℙdelimited-[]norm2superscriptsubscript12subscriptsuperscriptsubscriptsuperscriptΔ2superscriptΔ4subscriptP [ \| 2n _i=1^n/2g(x^+_i)- _+ \|% ≥ d ]≤ 2 (- γ d^α 4c_v)blackboard_P [ ∥ divide start_ARG 2 end_ARG start_ARG n end_ARG ∑i = 1n / 2 g ( x+i ) - μ+ ∥ ≥ droman_Δ ] ≤ 2 exp ( - divide start_ARG γ ditalic_α Δ end_ARG start_ARG 4 citalic_v end_ARG ) (13) Similarly, since −∼ℰα⁢(μ−,Σ−,K)similar-tosubscriptsubscriptℰsubscriptsubscriptΣD_- _α( _-, _-,K)D- ∼ Eitalic_α ( μ- , Σ- , K ). ℙ⁢[‖2n⁢∑i=1n/2g⁢(xi−)−μ−‖≥dΔ]≤2⁢exp⁡(−γ⁢dα⁢Δ4⁢cv)ℙdelimited-[]norm2superscriptsubscript12subscriptsuperscriptsubscriptsuperscriptΔ2superscriptΔ4subscriptP [ \| 2n _i=1^n/2g(x^-_i)- _- \|% ≥ d ]≤ 2 (- γ d^α 4c_v)blackboard_P [ ∥ divide start_ARG 2 end_ARG start_ARG n end_ARG ∑i = 1n / 2 g ( x-i ) - μ- ∥ ≥ droman_Δ ] ≤ 2 exp ( - divide start_ARG γ ditalic_α Δ end_ARG start_ARG 4 citalic_v end_ARG ) (14) Additionally, we have that by Proposition 2.2 of (Sambale, 2023), ℙ⁢(‖g⁢(xi+)‖≥2⁢cn⁢d)≤2⁢exp⁡(−c′⁢dα/4)ℙnormsuperscriptsubscript2subscript2superscript′4P ( \|g(x_i^+) \|≥ 2c_n d )≤ 2% (-c d^α/4)blackboard_P ( ∥ g ( xitalic_i+ ) ∥ ≥ 2 citalic_n square-root start_ARG d end_ARG ) ≤ 2 exp ( - c′ ditalic_α / 4 ) (15) ℙ⁢(‖g⁢(xi−)‖≥2⁢cn⁢d)≤2⁢exp⁡(−c′⁢dα/4)ℙnormsuperscriptsubscript2subscript2superscript′4P ( \|g(x_i^-) \|≥ 2c_n d )≤ 2% (-c d^α/4)blackboard_P ( ∥ g ( xitalic_i- ) ∥ ≥ 2 citalic_n square-root start_ARG d end_ARG ) ≤ 2 exp ( - c′ ditalic_α / 4 ) (16) for each i∈[n/2]delimited-[]2i∈[n/2]i ∈ [ n / 2 ] and for some constant c′>0superscript′0c >0c′ > 0. Now, we will condition the remainder of the proof on the event that (13), (14), (15), (16) all hold true for all i∈[n/2]delimited-[]2i∈[n/2]i ∈ [ n / 2 ] which by a union bound holds with probability at least 1−4⁢exp⁡(−γ⁢dα⁢Δ4⁢cv)−2⁢n⁢exp⁡(−c′⁢dα/4)14superscriptΔ4subscript2superscript′41-4 (- γ d^α 4c_v)-2n (-c d^α/4)1 - 4 exp ( - divide start_ARG γ ditalic_α Δ end_ARG start_ARG 4 citalic_v end_ARG ) - 2 n exp ( - c′ ditalic_α / 4 ) for some constant c′>0superscript′0c >0c′ > 0. Then, we have that ‖2n⁢∑i=1n/2g⁢(xi+)−2n⁢∑i=1n/2g⁢(xi−)‖≤3⁢dΔnorm2superscriptsubscript12subscriptsuperscript2superscriptsubscript12subscriptsuperscript3superscriptΔ \| 2n _i=1^n/2g(x^+_i)- 2n _i=1^n/2g(x^% -_i) \|≤ 3d ∥ divide start_ARG 2 end_ARG start_ARG n end_ARG ∑i = 1n / 2 g ( x+i ) - divide start_ARG 2 end_ARG start_ARG n end_ARG ∑i = 1n / 2 g ( x-i ) ∥ ≤ 3 droman_Δ (17) Now, we know that, ‖Δ⁢WU⁢(1)‖≤3⁢dΔ⁢β⁢η4=3⁢η⁢β′4⁢dΔ−1/2normΔsubscript13superscriptΔ43superscript′4superscriptΔ12 \| W_U(1) \|≤ 3d βη4= 3η% β 4d -1/2∥ Δ Witalic_U ( 1 ) ∥ ≤ divide start_ARG 3 droman_Δ β η end_ARG start_ARG 4 end_ARG = divide start_ARG 3 η β′ end_ARG start_ARG 4 end_ARG droman_Δ - 1 / 2 (18) Now, we are interested in controlling σ⁢(−β⁢Δ⁢WU⁢(t)⁢g⁢(xi+)⊤)Δsubscriptsuperscriptsuperscriptsubscripttopσ(-β W_U(t)g(x_i^+) )σ ( - β Δ Witalic_U ( t ) g ( xitalic_i+ )⊤ ) and σ⁢(β⁢Δ⁢WU⁢(t)⁢g⁢(xi−)⊤)Δsubscriptsuperscriptsuperscriptsubscripttopσ(β W_U(t)g(x_i^-) )σ ( β Δ Witalic_U ( t ) g ( xitalic_i- )⊤ ). We know by a Taylor approximation that σ⁢(C⁢dΔ−1/2)=12+14⁢(C⁢dΔ−1/2−C3⁢d3⁢Δ−3/212+…)≤12+14⁢C⁢dΔ−1/2superscriptΔ121214superscriptΔ12superscript3superscript3Δ3212…1214superscriptΔ12σ(Cd -1/2)= 12+ 14(Cd -1/2- C^3d^% 3 -3/212+…)≤ 12+ 14Cd -1/2σ ( C droman_Δ - 1 / 2 ) = divide start_ARG 1 end_ARG start_ARG 2 end_ARG + divide start_ARG 1 end_ARG start_ARG 4 end_ARG ( C droman_Δ - 1 / 2 - divide start_ARG C3 d3 Δ - 3 / 2 end_ARG start_ARG 12 end_ARG + … ) ≤ divide start_ARG 1 end_ARG start_ARG 2 end_ARG + divide start_ARG 1 end_ARG start_ARG 4 end_ARG C droman_Δ - 1 / 2 σ⁢(−C⁢dΔ−1/2)=12+14⁢(−C⁢dΔ−1/2+C3⁢d3⁢Δ−3/212+…)≥12−14⁢C⁢dΔ−1/2superscriptΔ121214superscriptΔ12superscript3superscript3Δ3212…1214superscriptΔ12σ(-Cd -1/2)= 12+ 14(-Cd -1/2+ C^3d% ^3 -3/212+…)≥ 12- 14Cd -1/2σ ( - C droman_Δ - 1 / 2 ) = divide start_ARG 1 end_ARG start_ARG 2 end_ARG + divide start_ARG 1 end_ARG start_ARG 4 end_ARG ( - C droman_Δ - 1 / 2 + divide start_ARG C3 d3 Δ - 3 / 2 end_ARG start_ARG 12 end_ARG + … ) ≥ divide start_ARG 1 end_ARG start_ARG 2 end_ARG - divide start_ARG 1 end_ARG start_ARG 4 end_ARG C droman_Δ - 1 / 2 Then, using that 2⁢β⁢‖g⁢(xi+)‖⁢‖Δ⁢WU⁢(1)‖≤3⁢β′⁣2⁢η⁢cn⁢dΔ−1/22normsuperscriptsubscriptnormΔsubscript13superscript′2subscriptsuperscriptΔ122β \|g(x_i^+) \| \| W_U(1) \|≤ 3β^% 2η c_nd -1/22 β ∥ g ( xitalic_i+ ) ∥ ∥ Δ Witalic_U ( 1 ) ∥ ≤ 3 β′ 2 η citalic_n droman_Δ - 1 / 2 2⁢β⁢‖g⁢(xi−)‖⁢‖Δ⁢WU⁢(1)‖≤3⁢β′⁣2⁢η⁢cn⁢dΔ−1/22normsuperscriptsubscriptnormΔsubscript13superscript′2subscriptsuperscriptΔ122β \|g(x_i^-) \| \| W_U(1) \|≤ 3β^% 2η c_nd -1/22 β ∥ g ( xitalic_i- ) ∥ ∥ Δ Witalic_U ( 1 ) ∥ ≤ 3 β′ 2 η citalic_n droman_Δ - 1 / 2 we have that both max1≤i≤n⁡|σ⁢(−2⁢β⁢g⁢(xi+)⊤⁢Δ⁢W⁢(1))−12|≤3⁢β′⁣2⁢η⁢cn4⁢dΔ−1/2subscript12superscriptsubscriptsuperscripttopΔ1123superscript′2subscript4superscriptΔ12 _1≤ i≤ n|σ(-2β g(x^+_i) W(1))- 12% |≤ 3β 2η c_n4d -1/2max1 ≤ i ≤ n | σ ( - 2 β g ( x+i )⊤ Δ W ( 1 ) ) - divide start_ARG 1 end_ARG start_ARG 2 end_ARG | ≤ divide start_ARG 3 β′ 2 η citalic_n end_ARG start_ARG 4 end_ARG droman_Δ - 1 / 2 max1≤i≤n⁡|σ⁢(2⁢β⁢g⁢(xi−)⊤⁢Δ⁢W⁢(1))−12|≤3⁢β′⁣2⁢η⁢cn4⁢dΔ−1/2subscript12superscriptsubscriptsuperscripttopΔ1123superscript′2subscript4superscriptΔ12 _1≤ i≤ n|σ(2β g(x^-_i) W(1))- 12% |≤ 3β 2η c_n4d -1/2max1 ≤ i ≤ n | σ ( 2 β g ( x-i )⊤ Δ W ( 1 ) ) - divide start_ARG 1 end_ARG start_ARG 2 end_ARG | ≤ divide start_ARG 3 β′ 2 η citalic_n end_ARG start_ARG 4 end_ARG droman_Δ - 1 / 2 Then, ‖Δ⁢W⁢(2)−Δ⁢W⁢(1)‖≤(3⁢β′⁢η4+3⁢β′⁣3⁢η2⁢cn22)⁢dΔ−1/2normΔ2Δ13superscript′43superscript′3superscript2superscriptsubscript22superscriptΔ12 \| W(2)- W(1) \|≤ ( 3β η4+% 3β 3η^2c_n^22 )d -1/2∥ Δ W ( 2 ) - Δ W ( 1 ) ∥ ≤ ( divide start_ARG 3 β′ η end_ARG start_ARG 4 end_ARG + divide start_ARG 3 β′ 3 η2 citalic_n2 end_ARG start_ARG 2 end_ARG ) droman_Δ - 1 / 2 We can prove by induction using a similar argument to show that for any finite t, ‖Δ⁢WU⁢(t)−Δ⁢WU⁢(t−1)‖≤3⁢β′⁢η4⁢∑i=1t(t+1−i)⁢(2⁢β′⁣2⁢η⁢cn2)i−1⁢dΔ−1/2normΔsubscriptΔsubscript13superscript′4superscriptsubscript11superscript2superscript′2superscriptsubscript21superscriptΔ12 \| W_U(t)- W_U(t-1) \|≤ 3β η% 4 _i=1^t(t+1-i) (2β 2η c_n^2 )^i-1d^% -1/2∥ Δ Witalic_U ( t ) - Δ Witalic_U ( t - 1 ) ∥ ≤ divide start_ARG 3 β′ η end_ARG start_ARG 4 end_ARG ∑i = 1t ( t + 1 - i ) ( 2 β′ 2 η citalic_n2 )i - 1 droman_Δ - 1 / 2 for constants c′>0superscript′0c >0c′ > 0. Then, if we assume that β′⁣2⁢η⁢h2≤14superscript′2superscriptℎ214β 2η h^2≤ 14β′ 2 η h2 ≤ divide start_ARG 1 end_ARG start_ARG 4 end_ARG, then ‖Δ⁢WU⁢(t)−Δ⁢WU⁢(t−1)‖≤3⁢β′⁢η⁢dΔ−1/2normΔsubscriptΔsubscript13superscript′Δ12 \| W_U(t)- W_U(t-1) \|≤ 3β η d^% -1/2∥ Δ Witalic_U ( t ) - Δ Witalic_U ( t - 1 ) ∥ ≤ 3 β′ η droman_Δ - 1 / 2 and with probability at least 1−2⁢n⁢exp⁡(−c′⁢dα/4)−4⁢exp⁡(−γ⁢dα⁢Δ4⁢cv)12superscript′44superscriptΔ4subscript1-2n (-c d^α/4)-4 ( -γ d^α 4c_v)1 - 2 n exp ( - c′ ditalic_α / 4 ) - 4 exp ( divide start_ARG - γ ditalic_α Δ end_ARG start_ARG 4 citalic_v end_ARG ) ‖WU⁢(t)−WU⁢(0)‖≤6⁢β′⁢η⁢t⁢dΔ−1/2normsubscriptsubscript06superscript′Δ12 \|W_U(t)-W_U(0) \|≤ 6β η td -1/2∥ Witalic_U ( t ) - Witalic_U ( 0 ) ∥ ≤ 6 β′ η t droman_Δ - 1 / 2 A.3 Prioritization Derivation We prove the claim that the first update of DPO is proportional to b¯=1m⁢∑i=1mbi¯1superscriptsubscript1subscript b= 1m _i=1^mb_iover¯ start_ARG b end_ARG = divide start_ARG 1 end_ARG start_ARG m end_ARG ∑i = 1m bitalic_i (19) when we have a set of behaviors B1,B2,…,Bmsubscript1subscript2…subscriptB_1,B_2,…,B_mB1 , B2 , … , Bitalic_m, each with n examples with bi=μ^+i−μ^−isubscriptsuperscriptsubscript^superscriptsubscript^b_i= μ_+^i- μ_-^ibitalic_i = over start_ARG μ end_ARG+i - over start_ARG μ end_ARG-i being the sample mean of the positive examples minus the sample mean of the negative examples for the i-th behavior. We first note that at the first step since WUsubscriptW_UWitalic_U has not been updated, our first DPO gradient has the form 12⁢β⁢(y^+−y^−)⁢(2m⁢n⁢∑j=1m(∑i=1n/2[12⁢g⁢(xi+,j)⊤]−∑i=1n/2[12⁢g⁢(xi−,j)⊤]))12subscript^subscript^2superscriptsubscript1superscriptsubscript12delimited-[]12superscriptsuperscriptsubscripttopsuperscriptsubscript12delimited-[]12superscriptsuperscriptsubscripttop 12β( y_+- y_-) ( 2mn _j=1^m % ( _i=1^n/2 [ 12g(x_i^+,j) ]- _i=1% ^n/2 [ 12g(x_i^-,j) ] ) )divide start_ARG 1 end_ARG start_ARG 2 end_ARG β ( over start_ARG y end_ARG+ - over start_ARG y end_ARG- ) ( divide start_ARG 2 end_ARG start_ARG m n end_ARG ∑j = 1m ( ∑i = 1n / 2 [ divide start_ARG 1 end_ARG start_ARG 2 end_ARG g ( xitalic_i+ , j )⊤ ] - ∑i = 1n / 2 [ divide start_ARG 1 end_ARG start_ARG 2 end_ARG g ( xitalic_i- , j )⊤ ] ) ) (20) where xi+,j,xi−,jsuperscriptsubscriptsuperscriptsubscriptx_i^+,j,x_i^-,jxitalic_i+ , j , xitalic_i- , j are examples corresponding to behavior j. Then, we have as our gradient 14⁢β⁢(y^+−y^−)⁢(1m⁢∑j=1mbj)T14subscript^subscript^superscript1superscriptsubscript1subscript 14β( y_+- y_-) ( 1m _j=1^mb_j% )^Tdivide start_ARG 1 end_ARG start_ARG 4 end_ARG β ( over start_ARG y end_ARG+ - over start_ARG y end_ARG- ) ( divide start_ARG 1 end_ARG start_ARG m end_ARG ∑j = 1m bitalic_j )T (21) and the updates to the WUsubscriptW_UWitalic_U matrix are indeed proportional to b¯ bover¯ start_ARG b end_ARG. Now, we will show that the average improvement in logits after the first update for behavior BjsubscriptB_jBitalic_j is proportional to b¯⋅bj⋅¯subscript b· b_jover¯ start_ARG b end_ARG ⋅ bitalic_j. We know that the average improvement in logits for behavior BjsubscriptB_jBitalic_j after the first step is 1n⁢∑i=1n/2(y^+−y^−)⊤⁢Δ⁢WU⁢(1)⁢g⁢(xi+,j)+1n⁢∑i=1n/2(y^−y^+)⊤⁢Δ⁢WU⁢(1)⁢g⁢(xi−,j)1superscriptsubscript12superscriptsubscript^subscript^topΔsubscript1superscriptsubscript1superscriptsubscript12superscriptsubscript^subscript^topΔsubscript1superscriptsubscript 1n _i=1^n/2( y_+- y_-) W_U(1)g(x_% i^+,j)+ 1n _i=1^n/2( y_-- y_+) W% _U(1)g(x_i^-,j)divide start_ARG 1 end_ARG start_ARG n end_ARG ∑i = 1n / 2 ( over start_ARG y end_ARG+ - over start_ARG y end_ARG- )⊤ Δ Witalic_U ( 1 ) g ( xitalic_i+ , j ) + divide start_ARG 1 end_ARG start_ARG n end_ARG ∑i = 1n / 2 ( over start_ARG y end_ARG- - over start_ARG y end_ARG+ )⊤ Δ Witalic_U ( 1 ) g ( xitalic_i- , j ) (22) which can be written as (y^+−y^−)T⁢Δ⁢WU⁢(1)⁢(1n⁢∑i=1n/2g⁢(xi+,j)−1n⁢∑i=1n/2g⁢(xi−,j))superscriptsubscript^subscript^Δsubscript11superscriptsubscript12superscriptsubscript1superscriptsubscript12superscriptsubscript( y_+- y_-)^T W_U(1) ( 1n _i=1^n/2g% (x_i^+,j)- 1n _i=1^n/2g(x_i^-,j) )( over start_ARG y end_ARG+ - over start_ARG y end_ARG- )T Δ Witalic_U ( 1 ) ( divide start_ARG 1 end_ARG start_ARG n end_ARG ∑i = 1n / 2 g ( xitalic_i+ , j ) - divide start_ARG 1 end_ARG start_ARG n end_ARG ∑i = 1n / 2 g ( xitalic_i- , j ) ) (23) and this simplifies to β2⁢η4⁢b¯⋅bj⋅superscript24¯subscript β^2η4 b· b_jdivide start_ARG β2 η end_ARG start_ARG 4 end_ARG over¯ start_ARG b end_ARG ⋅ bitalic_j (24) and this completes our proof. A.4 Proof of Theorem 2 Proof. Since +∼ℰα⁢(μ+,Σ+,K)similar-tosubscriptsubscriptℰsubscriptsubscriptΣD_+ _α( _+, _+,K)D+ ∼ Eitalic_α ( μ+ , Σ+ , K ), ℙ⁢[‖2n⁢∑i=1n/2g⁢(xi+)−μ+‖≥t]=ℙ⁢[|2n⁢∑i=1n/2a⊤⁢g⁢(xi+)−a⊤⁢μ+|≥t]≤2⁢exp⁡(−tα⁢n4⁢a⊤⁢Σ+⁢a)ℙdelimited-[]norm2superscriptsubscript12subscriptsuperscriptsubscriptℙdelimited-[]2superscriptsubscript12superscripttopsubscriptsuperscriptsuperscripttopsubscript2superscript4superscripttopsubscriptΣP [ \| 2n _i=1^n/2g(x^+_i)- _+ \|% ≥ t ]=P [ | 2n _i=1^n/2a g(x^+% _i)-a _+ |≥ t ]≤ 2 (- t^αn4a^% _+a)blackboard_P [ ∥ divide start_ARG 2 end_ARG start_ARG n end_ARG ∑i = 1n / 2 g ( x+i ) - μ+ ∥ ≥ t ] = blackboard_P [ | divide start_ARG 2 end_ARG start_ARG n end_ARG ∑i = 1n / 2 a⊤ g ( x+i ) - a⊤ μ+ | ≥ t ] ≤ 2 exp ( - divide start_ARG titalic_α n end_ARG start_ARG 4 a⊤ Σ+ a end_ARG ) for some unit vector a. Then, we know that ‖Σ+‖≤cv⁢d12−2⁢vnormsubscriptΣsubscriptsuperscript122 \| _+ \|≤ c_vd 12-2v∥ Σ+ ∥ ≤ citalic_v ddivide start_ARG 1 end_ARG start_ARG 2 end_ARG - 2 v, so we have that for t=dΔ−vsuperscriptΔt=d -vt = droman_Δ - v ℙ⁢[‖2n⁢∑i=1n/2g⁢(xi+)−μ+‖≥dΔ−v]≤2⁢exp⁡(−γ⁢dα⁢Δ4⁢cv)ℙdelimited-[]norm2superscriptsubscript12subscriptsuperscriptsubscriptsuperscriptΔ2superscriptΔ4subscriptP [ \| 2n _i=1^n/2g(x^+_i)- _+ \|% ≥ d -v ]≤ 2 (- γ d^α 4c_v)blackboard_P [ ∥ divide start_ARG 2 end_ARG start_ARG n end_ARG ∑i = 1n / 2 g ( x+i ) - μ+ ∥ ≥ droman_Δ - v ] ≤ 2 exp ( - divide start_ARG γ ditalic_α Δ end_ARG start_ARG 4 citalic_v end_ARG ) Similarly since −∼ℰα⁢(μ−,Σ−,K)similar-tosubscriptsubscriptℰsubscriptsubscriptΣD_- _α( _-, _-,K)D- ∼ Eitalic_α ( μ- , Σ- , K ), ℙ⁢[‖2n⁢∑i=1n/2g⁢(xi−)−μ−‖≥dΔ−v]≤2⁢exp⁡(−γ⁢dα⁢Δ4⁢cv)ℙdelimited-[]norm2superscriptsubscript12subscriptsuperscriptsubscriptsuperscriptΔ2superscriptΔ4subscriptP [ \| 2n _i=1^n/2g(x^-_i)- _- \|% ≥ d -v ]≤ 2 (- γ d^α 4c_v)blackboard_P [ ∥ divide start_ARG 2 end_ARG start_ARG n end_ARG ∑i = 1n / 2 g ( x-i ) - μ- ∥ ≥ droman_Δ - v ] ≤ 2 exp ( - divide start_ARG γ ditalic_α Δ end_ARG start_ARG 4 citalic_v end_ARG ) Then, we have that ℙ⁢[‖(2n⁢∑i=1n/2g⁢(xi+)−2n⁢∑i=1n/2g⁢(xi−))−(μ+−μ−)‖≥2⁢dΔ−v]≤4⁢exp⁡(−γ⁢dα⁢Δ4⁢cv)ℙdelimited-[]norm2superscriptsubscript12subscriptsuperscript2superscriptsubscript12subscriptsuperscriptsubscriptsubscript2superscriptΔ4superscriptΔ4subscriptP [ \| ( 2n _i=1^n/2g(x^+_i)- 2% n _i=1^n/2g(x^-_i) )-( _+- _-) \|≥ 2d % -v ]≤ 4 (- γ d^α 4c_v)blackboard_P [ ∥ ( divide start_ARG 2 end_ARG start_ARG n end_ARG ∑i = 1n / 2 g ( x+i ) - divide start_ARG 2 end_ARG start_ARG n end_ARG ∑i = 1n / 2 g ( x-i ) ) - ( μ+ - μ- ) ∥ ≥ 2 droman_Δ - v ] ≤ 4 exp ( - divide start_ARG γ ditalic_α Δ end_ARG start_ARG 4 citalic_v end_ARG ) Now, we know that with probability 1−4⁢exp⁡(−γ⁢dα⁢Δ4⁢cv)14superscriptΔ4subscript1-4 (- γ d^α 4c_v)1 - 4 exp ( - divide start_ARG γ ditalic_α Δ end_ARG start_ARG 4 citalic_v end_ARG ), Δ⁢WU⁢(1)⊤⁢(μ+−μ−)‖Δ⁢WU⁢(1)‖⁢‖μ+−μ−‖≥(1−2⁢d−v)⁢(μ+−μ−)⊤⁢(μ+−μ−)(1+2⁢d−v)⁢‖μ+−μ−‖2≥1−4⁢d−vΔsubscriptsuperscript1topsubscriptsubscriptnormΔsubscript1normsubscriptsubscript12superscriptsuperscriptsubscriptsubscripttopsubscriptsubscript12superscriptsuperscriptnormsubscriptsubscript214superscript W_U(1) ( _+- _-) \| W_U(1) \|% \| _+- _- \|≥ (1-2d^-v)( _+- _-) (% _+- _-)(1+2d^-v) \| _+- _- \|^2≥ 1-4d^-vdivide start_ARG Δ Witalic_U ( 1 )⊤ ( μ+ - μ- ) end_ARG start_ARG ∥ Δ Witalic_U ( 1 ) ∥ ∥ μ+ - μ- ∥ end_ARG ≥ divide start_ARG ( 1 - 2 d- v ) ( μ+ - μ- )⊤ ( μ+ - μ- ) end_ARG start_ARG ( 1 + 2 d- v ) ∥ μ+ - μ- ∥2 end_ARG ≥ 1 - 4 d- v Now, we are interested in controlling σ⁢(−β⁢g⁢(xi+)⊤⁢Δ⁢WU⁢(t))superscriptsuperscriptsubscripttopΔsubscriptσ(-β g(x_i^+) W_U(t))σ ( - β g ( xitalic_i+ )⊤ Δ Witalic_U ( t ) ) and σ⁢(β⁢g⁢(xi−)⊤⁢Δ⁢WU⁢(t))superscriptsuperscriptsubscripttopΔsubscriptσ(β g(x_i^-) W_U(t))σ ( β g ( xitalic_i- )⊤ Δ Witalic_U ( t ) ). From the proof of Theorem 1, with probability at least 1−2⁢n⁢exp⁡(−c′⁢dα/4)−4⁢exp⁡(−γ⁢dα⁢Δ4⁢cv)12superscript′44superscriptΔ4subscript1-2n (-c d^α/4)-4 ( -γ d^α 4c_v)1 - 2 n exp ( - c′ ditalic_α / 4 ) - 4 exp ( divide start_ARG - γ ditalic_α Δ end_ARG start_ARG 4 citalic_v end_ARG ), we have that max1≤i≤n/2⁡|σ⁢(−2⁢β⁢g⁢(xi+)⊤⁢Δ⁢WU⁢(t))−12|≤3⁢β′⁣2⁢η⁢cn⁢t⁢dΔ−1/2subscript122superscriptsubscriptsuperscripttopΔsubscript123superscript′2subscriptsuperscriptΔ12 _1≤ i≤ n/2|σ(-2β g(x^+_i) W_U(t))-% 12|≤ 3β 2η c_ntd -1/2max1 ≤ i ≤ n / 2 | σ ( - 2 β g ( x+i )⊤ Δ Witalic_U ( t ) ) - divide start_ARG 1 end_ARG start_ARG 2 end_ARG | ≤ 3 β′ 2 η citalic_n t droman_Δ - 1 / 2 max1≤i≤n/2⁡|σ⁢(2⁢β⁢g⁢(xi−)⊤⁢Δ⁢WU⁢(t))−12|≤3⁢β′⁣2⁢η⁢cn⁢t⁢dΔ−1/2subscript122superscriptsubscriptsuperscripttopΔsubscript123superscript′2subscriptsuperscriptΔ12 _1≤ i≤ n/2|σ(2β g(x^-_i) W_U(t))- % 12|≤ 3β 2η c_ntd -1/2max1 ≤ i ≤ n / 2 | σ ( 2 β g ( x-i )⊤ Δ Witalic_U ( t ) ) - divide start_ARG 1 end_ARG start_ARG 2 end_ARG | ≤ 3 β′ 2 η citalic_n t droman_Δ - 1 / 2 Now, we will define the following constants A1=2n⁢∑i=1n/2σ⁢(−2⁢β⁢g⁢(xi+)⊤⁢Δ⁢WU⁢(t))subscript12superscriptsubscript122superscriptsuperscriptsubscripttopΔsubscriptA_1= 2n _i=1^n/2σ(-2β g(x_i^+) W_U% (t))A1 = divide start_ARG 2 end_ARG start_ARG n end_ARG ∑i = 1n / 2 σ ( - 2 β g ( xitalic_i+ )⊤ Δ Witalic_U ( t ) ) A2=2n⁢∑i=1n/2σ⁢(2⁢β⁢g⁢(xi−)⊤⁢Δ⁢WU⁢(t))subscript22superscriptsubscript122superscriptsuperscriptsubscripttopΔsubscriptA_2= 2n _i=1^n/2σ(2β g(x_i^-) W_U% (t))A2 = divide start_ARG 2 end_ARG start_ARG n end_ARG ∑i = 1n / 2 σ ( 2 β g ( xitalic_i- )⊤ Δ Witalic_U ( t ) ) We have that |A1−A2|≤2n⁢∑i=1n/2|σ⁢(−2⁢β⁢g⁢(xi+)⊤⁢Δ⁢WU⁢(t))−σ⁢(2⁢β⁢g⁢(xi−)⊤⁢Δ⁢WU⁢(t))|≤6⁢β′⁣2⁢η⁢cn⁢t⁢dΔ−1/2subscript1subscript22superscriptsubscript122superscriptsuperscriptsubscripttopΔsubscript2superscriptsuperscriptsubscripttopΔsubscript6superscript′2subscriptsuperscriptΔ12|A_1-A_2|≤ 2n _i=1^n/2|σ(-2β g(x_i^+) % W_U(t))-σ(2β g(x_i^-) W_U(t))|≤ 6% β 2η c_ntd -1/2| A1 - A2 | ≤ divide start_ARG 2 end_ARG start_ARG n end_ARG ∑i = 1n / 2 | σ ( - 2 β g ( xitalic_i+ )⊤ Δ Witalic_U ( t ) ) - σ ( 2 β g ( xitalic_i- )⊤ Δ Witalic_U ( t ) ) | ≤ 6 β′ 2 η citalic_n t droman_Δ - 1 / 2 Then, if A1≥A2subscript1subscript2A_1≥ A_2A1 ≥ A2 Δ⁢WU⁢(t+1)−Δ⁢WU⁢(t)Δsubscript1Δsubscript W_U(t+1)- W_U(t)Δ Witalic_U ( t + 1 ) - Δ Witalic_U ( t ) =β⁢η2(A2A12n∑i=1n/2σ(−βg(xi+)⊤ΔWU(t))(g(xi+)−μ+) = βη2 ( A_2A_1 2n _i% =1^n/2σ(-β g(x_i^+) W_U(t))(g(x_i^+)- _+)= divide start_ARG β η end_ARG start_ARG 2 end_ARG ( divide start_ARG A2 end_ARG start_ARG A1 end_ARG divide start_ARG 2 end_ARG start_ARG n end_ARG ∑i = 1n / 2 σ ( - β g ( xitalic_i+ )⊤ Δ Witalic_U ( t ) ) ( g ( xitalic_i+ ) - μ+ ) −2n⁢∑i=1n/2σ⁢(β⁢g⁢(xi−)⊤⁢Δ⁢WU⁢(t))⁢(g⁢(xi−)−μ−)2superscriptsubscript12superscriptsuperscriptsubscripttopΔsubscriptsuperscriptsubscriptsubscript - 2n _i=1^n/2σ(β g(x_i^-) % W_U(t))(g(x_i^-)- _-)- divide start_ARG 2 end_ARG start_ARG n end_ARG ∑i = 1n / 2 σ ( β g ( xitalic_i- )⊤ Δ Witalic_U ( t ) ) ( g ( xitalic_i- ) - μ- ) +A2(μ+−μ−)+A1−A2A12n∑i=1n/2σ(−βg(xi+)⊤ΔWU(t))(g(xi+))) +A_2( _+- _-)+ A_1-A_2A_1 2n _% i=1^n/2σ(-β g(x_i^+) W_U(t))(g(x_i^+))% )+ A2 ( μ+ - μ- ) + divide start_ARG A1 - A2 end_ARG start_ARG A1 end_ARG divide start_ARG 2 end_ARG start_ARG n end_ARG ∑i = 1n / 2 σ ( - β g ( xitalic_i+ )⊤ Δ Witalic_U ( t ) ) ( g ( xitalic_i+ ) ) ) Then, with probability at least 1−2⁢n⁢exp⁡(−c′⁢dα/4)−4⁢exp⁡(−γ⁢dα⁢Δ4⁢cv)12superscript′44superscriptΔ4subscript1-2n (-c d^α/4)-4 ( -γ d^α 4c_v)1 - 2 n exp ( - c′ ditalic_α / 4 ) - 4 exp ( divide start_ARG - γ ditalic_α Δ end_ARG start_ARG 4 citalic_v end_ARG ) ‖Δ⁢WU⁢(t+1)−Δ⁢WU⁢(t)−β⁢η⁢A22⁢(μ+−μ−)‖≤β⁢η2⁢(1+6⁢β′⁣2⁢η⁢cn⁢t⁢dΔ−1/2+36⁢β′⁣2⁢η⁢cn⁢t⁢dv)⁢dΔ−vnormΔsubscript1Δsubscriptsubscript22subscriptsubscript216superscript′2subscriptsuperscriptΔ1236superscript′2subscriptsuperscriptsuperscriptΔ \| W_U(t+1)- W_U(t)- βη A_22( _+-μ% _-) \|≤ βη2 (1+6β 2η c_ntd^% -1/2+36β 2η c_ntd^v )d -v∥ Δ Witalic_U ( t + 1 ) - Δ Witalic_U ( t ) - divide start_ARG β η A2 end_ARG start_ARG 2 end_ARG ( μ+ - μ- ) ∥ ≤ divide start_ARG β η end_ARG start_ARG 2 end_ARG ( 1 + 6 β′ 2 η citalic_n t droman_Δ - 1 / 2 + 36 β′ 2 η citalic_n t ditalic_v ) droman_Δ - v (25) Then, with probability at least 1−2⁢n⁢exp⁡(−c′⁢dα/4)−4⁢exp⁡(−γ⁢dα⁢Δ4⁢cv)12superscript′44superscriptΔ4subscript1-2n (-c d^α/4)-4 ( -γ d^α 4c_v)1 - 2 n exp ( - c′ ditalic_α / 4 ) - 4 exp ( divide start_ARG - γ ditalic_α Δ end_ARG start_ARG 4 citalic_v end_ARG ) (Δ⁢WU⁢(t+1)−Δ⁢WU⁢(t))⊤⁢(μ+−μ−)‖Δ⁢WU⁢(t+1)−Δ⁢WU⁢(t)‖⁢‖μ+−μ−‖superscriptΔsubscript1ΔsubscripttopsubscriptsubscriptnormΔsubscript1Δsubscriptnormsubscriptsubscript ( W_U(t+1)- W_U(t)) ( _+- _-)% \| W_U(t+1)- W_U(t) \| \| _+- _- \|divide start_ARG ( Δ Witalic_U ( t + 1 ) - Δ Witalic_U ( t ) )⊤ ( μ+ - μ- ) end_ARG start_ARG ∥ Δ Witalic_U ( t + 1 ) - Δ Witalic_U ( t ) ∥ ∥ μ+ - μ- ∥ end_ARG ≥(A2−(1+6⁢β′⁣2⁢η⁢cn⁢t⁢dΔ−1/2+36⁢β′⁣2⁢η⁢cn⁢t⁢dv)⁢d−v)⁢(μ+−μ−)⊤⁢(μ+−μ−)(A2+(1+6⁢β′⁣2⁢η⁢cn⁢t⁢dΔ−1/2+36⁢β′⁣2⁢η⁢cn⁢t⁢dv)⁢d−v)⁢‖μ+−μ−‖2absentsubscript216superscript′2subscriptsuperscriptΔ1236superscript′2subscriptsuperscriptsuperscriptsuperscriptsubscriptsubscripttopsubscriptsubscriptsubscript216superscript′2subscriptsuperscriptΔ1236superscript′2subscriptsuperscriptsuperscriptsuperscriptnormsubscriptsubscript2 ≥ (A_2- (1+6β 2η c_ntd -1/% 2+36β 2η c_ntd^v )d^-v)( _+- _-) (% _+- _-)(A_2+ (1+6β 2η c_ntd -1/2+36% β 2η c_ntd^v )d^-v) \| _+- _- \|^% 2≥ divide start_ARG ( A2 - ( 1 + 6 β′ 2 η citalic_n t droman_Δ - 1 / 2 + 36 β′ 2 η citalic_n t ditalic_v ) d- v ) ( μ+ - μ- )⊤ ( μ+ - μ- ) end_ARG start_ARG ( A2 + ( 1 + 6 β′ 2 η citalic_n t droman_Δ - 1 / 2 + 36 β′ 2 η citalic_n t ditalic_v ) d- v ) ∥ μ+ - μ- ∥2 end_ARG ≥1−(2A2+12⁢β′⁣2⁢η⁢cn⁢tA2⁢dΔ−1/2+72⁢β′⁣2⁢η⁢cn⁢tA2⁢dv)⁢d−vabsent12subscript212superscript′2subscriptsubscript2superscriptΔ1272superscript′2subscriptsubscript2superscriptsuperscript ≥ 1- ( 2A_2+ 12β 2η c_nt% A_2d -1/2+ 72β 2η c_ntA_2d^v )d% ^-v≥ 1 - ( divide start_ARG 2 end_ARG start_ARG A2 end_ARG + divide start_ARG 12 β′ 2 η citalic_n t end_ARG start_ARG A2 end_ARG droman_Δ - 1 / 2 + divide start_ARG 72 β′ 2 η citalic_n t end_ARG start_ARG A2 end_ARG ditalic_v ) d- v ≥1−13⁢d−vabsent113superscript ≥ 1-13d^-v≥ 1 - 13 d- v We now consider a lower bound on ‖Δ⁢WU⁢(t)‖normΔsubscript \| W_U(t) \|∥ Δ Witalic_U ( t ) ∥ and starting from (25), we have that ‖Δ⁢WU⁢(t+1)−Δ⁢WU⁢(t)‖≥β⁢η⁢A22⁢‖(μ+−μ−)‖−β⁢η2⁢(1+6⁢β′⁣2⁢η⁢cn⁢t⁢dΔ−1/2+36⁢β′⁣2⁢η⁢cn⁢t⁢dv)⁢dΔ−vnormΔsubscript1Δsubscriptsubscript22normsubscriptsubscript216superscript′2subscriptsuperscriptΔ1236superscript′2subscriptsuperscriptsuperscriptΔ \| W_U(t+1)- W_U(t) \|≥ βη A_22% \|( _+- _-) \|- βη2 (1+6β 2% η c_ntd -1/2+36β 2η c_ntd^v )d -v∥ Δ Witalic_U ( t + 1 ) - Δ Witalic_U ( t ) ∥ ≥ divide start_ARG β η A2 end_ARG start_ARG 2 end_ARG ∥ ( μ+ - μ- ) ∥ - divide start_ARG β η end_ARG start_ARG 2 end_ARG ( 1 + 6 β′ 2 η citalic_n t droman_Δ - 1 / 2 + 36 β′ 2 η citalic_n t ditalic_v ) droman_Δ - v (26) which can be lower bounded further by ‖Δ⁢WU⁢(t+1)−Δ⁢WU⁢(t)‖≥β⁢η8⁢dΔ−β⁢η2⁢(2)⁢dΔ−vnormΔsubscript1Δsubscript8superscriptΔ22superscriptΔ \| W_U(t+1)- W_U(t) \|≥ βη8d^% - βη2 (2 )d -v∥ Δ Witalic_U ( t + 1 ) - Δ Witalic_U ( t ) ∥ ≥ divide start_ARG β η end_ARG start_ARG 8 end_ARG droman_Δ - divide start_ARG β η end_ARG start_ARG 2 end_ARG ( 2 ) droman_Δ - v (27) and we have that ‖Δ⁢WU⁢(t+1)−Δ⁢WU⁢(t)‖≥β⁢η8⁢dΔ−β⁢η⁢dΔ−vnormΔsubscript1Δsubscript8superscriptΔsuperscriptΔ \| W_U(t+1)- W_U(t) \|≥ βη8d^% -βη d -v∥ Δ Witalic_U ( t + 1 ) - Δ Witalic_U ( t ) ∥ ≥ divide start_ARG β η end_ARG start_ARG 8 end_ARG droman_Δ - β η droman_Δ - v (28) and as d−v≤1/16superscript116d^-v≤ 1/16d- v ≤ 1 / 16, ‖Δ⁢WU⁢(t+1)−Δ⁢WU⁢(t)‖≥β′⁢η16⁢dΔ−1/2normΔsubscript1Δsubscriptsuperscript′16superscriptΔ12 \| W_U(t+1)- W_U(t) \|≥ β η% 16d -1/2∥ Δ Witalic_U ( t + 1 ) - Δ Witalic_U ( t ) ∥ ≥ divide start_ARG β′ η end_ARG start_ARG 16 end_ARG droman_Δ - 1 / 2 (29) Then, it follows that ‖Δ⁢WU⁢(t)‖≥β′⁢η⁢t16⁢dΔ−1/2normΔsubscriptsuperscript′16superscriptΔ12 \| W_U(t) \|≥ β η t16d -1/2∥ Δ Witalic_U ( t ) ∥ ≥ divide start_ARG β′ η t end_ARG start_ARG 16 end_ARG droman_Δ - 1 / 2 (30) Now, we want to see how close our updated boundary is to μ+−μ−subscriptsubscript _+- _-μ+ - μ-. (WU⁢(0)⁢[y+]−WU⁢(0)⁢[y−]+2⁢Δ⁢WU⁢(t))⊤⁢(μ+−μ−)∥(WU(0)[y+]−WU(0)[y−]+2ΔWU(t)∥μ+−μ−∥ (W_U(0)[y_+]-W_U(0)[y_-]+2 W_U(t)) (% _+- _-) \|(W_U(0)[y_+]-W_U(0)[y_-]+2 W_U(t)% \| \| _+- _- \|divide start_ARG ( Witalic_U ( 0 ) [ y+ ] - Witalic_U ( 0 ) [ y- ] + 2 Δ Witalic_U ( t ) )⊤ ( μ+ - μ- ) end_ARG start_ARG ∥ ( Witalic_U ( 0 ) [ y+ ] - Witalic_U ( 0 ) [ y- ] + 2 Δ Witalic_U ( t ) ∥ ∥ μ+ - μ- ∥ end_ARG ≥ϕ∥(WU(0)[y+]−WU(0)[y−]∥+(1−13d−v)∥2ΔWU(t)∥(WU(0)[y+]−WU(0)[y−]+2ΔWU(t)∥ ≥ φ \|(W_U(0)[y_+]-W_U(0)[y_-] \|+(1-% 13d^-v) \|2 W_U(t) \| \|(W_U(0)[y_+]-W_U(0)[y_% -]+2 W_U(t) \|≥ divide start_ARG ϕ ∥ ( Witalic_U ( 0 ) [ y+ ] - Witalic_U ( 0 ) [ y- ] ∥ + ( 1 - 13 d- v ) ∥ 2 Δ Witalic_U ( t ) ∥ end_ARG start_ARG ∥ ( Witalic_U ( 0 ) [ y+ ] - Witalic_U ( 0 ) [ y- ] + 2 Δ Witalic_U ( t ) ∥ end_ARG ≥ϕ∥(WU(0)[y+]−WU(0)[y−]∥+(1−13d−v)∥2ΔWU(t)∥‖WU⁢(0)⁢[y+]−WU⁢(0)⁢[y−]‖+‖2⁢Δ⁢WU⁢(t)‖ ≥ φ \|(W_U(0)[y_+]-W_U(0)[y_-] \|+(1-% 13d^-v) \|2 W_U(t) \| \|W_U(0)[y_+]-W_U(0)[y_-% ] \|+ \|2 W_U(t) \|≥ divide start_ARG ϕ ∥ ( Witalic_U ( 0 ) [ y+ ] - Witalic_U ( 0 ) [ y- ] ∥ + ( 1 - 13 d- v ) ∥ 2 Δ Witalic_U ( t ) ∥ end_ARG start_ARG ∥ Witalic_U ( 0 ) [ y+ ] - Witalic_U ( 0 ) [ y- ] ∥ + ∥ 2 Δ Witalic_U ( t ) ∥ end_ARG ≥ϕ+(1−13⁢d−v−ϕ)⁢‖2⁢Δ⁢WU⁢(t)‖WB‖+‖2⁢Δ⁢WU⁢(t)‖absentitalic-ϕ113superscriptitalic-ϕnorm2Δsubscriptnormsubscriptnorm2Δsubscript ≥φ+ (1-13d^-v-φ) \|2 W_U(t) \|% \|W_B \|+ \|2 W_U(t) \|≥ ϕ + divide start_ARG ( 1 - 13 d- v - ϕ ) ∥ 2 Δ Witalic_U ( t ) ∥ end_ARG start_ARG ∥ Witalic_B ∥ + ∥ 2 Δ Witalic_U ( t ) ∥ end_ARG ≥ϕ+(1−13⁢d−v−ϕ)⁢β′⁢η⁢t⁢dΔ−1/28⁢‖WB‖+124⁢β′⁢cn′absentitalic-ϕ113superscriptitalic-ϕsuperscript′Δ128normsubscript124superscript′subscript′ ≥φ+ (1-13d^-v-φ)β η td -1/2% 8 \|W_B \|+ 124β c_n ≥ ϕ + divide start_ARG ( 1 - 13 d- v - ϕ ) β′ η t droman_Δ - 1 / 2 end_ARG start_ARG 8 ∥ Witalic_B ∥ + divide start_ARG 1 end_ARG start_ARG 24 β′ citalic_n′ end_ARG end_ARG We can use the same argument for when A2≥A1subscript2subscript1A_2≥ A_1A2 ≥ A1 to complete the proof. A.5 Proof of Theorem 3 Proof. From Theorem 2, with probability at least 1−2⁢n⁢exp⁡(−c′⁢dα/4)−4⁢exp⁡(−γ⁢dα⁢Δ4⁢cv)12superscript′44superscriptΔ4subscript1-2n (-c d^α/4)-4 ( -γ d^α 4c_v)1 - 2 n exp ( - c′ ditalic_α / 4 ) - 4 exp ( divide start_ARG - γ ditalic_α Δ end_ARG start_ARG 4 citalic_v end_ARG ), we know that after d1/2−Δ−v72⁢β′⁣2⁢η⁢cn′12Δ72superscript′2superscriptsubscript′ d^1/2- -v72β 2η c_n divide start_ARG d1 / 2 - Δ - v end_ARG start_ARG 72 β′ 2 η citalic_n′ end_ARG steps, that our decision boundary has a cosine similarity to μ+−μ−subscriptsubscript _+- _-μ+ - μ- of at least ϕ+(1−13⁢d−v−ϕ)⁢β′⁢η⁢t⁢dΔ−1/28⁢‖WB‖+124⁢β′⁢cn′italic-ϕ113superscriptitalic-ϕsuperscript′Δ128normsubscript124superscript′subscript′φ+ (1-13d^-v-φ)β η td -1/28 \|W_B% \|+ 124β c_n ϕ + divide start_ARG ( 1 - 13 d- v - ϕ ) β′ η t droman_Δ - 1 / 2 end_ARG start_ARG 8 ∥ Witalic_B ∥ + divide start_ARG 1 end_ARG start_ARG 24 β′ citalic_n′ end_ARG end_ARG (31) Now, suppose that ϵ=1−13⁢d−v−ϕitalic-ϵ113superscriptitalic-ϕε=1-13d^-v-φϵ = 1 - 13 d- v - ϕ. Then, we have that our decision boundary’s cosine similarity is at least ϕ+ϵ⁢d−v576⁢β′⁢cn′⁢‖WB‖+3italic-ϕitalic-ϵsuperscript576superscript′subscript′normsubscript3φ+ ε d^-v576β c_n \|W_B % \|+3ϕ + divide start_ARG ϵ d- v end_ARG start_ARG 576 β′ citalic_n′ ∥ Witalic_B ∥ + 3 end_ARG (32) which we will refer to as S. Now, we let WB⁢(t)=WU⁢(t)⁢[y+]−WU⁢(t)⁢[y−]‖WU⁢(t)⁢[y+]−WU⁢(t)⁢[y−]‖subscriptsubscriptdelimited-[]subscriptsubscriptdelimited-[]subscriptnormsubscriptdelimited-[]subscriptsubscriptdelimited-[]subscriptW_B(t)= W_U(t)[y_+]-W_U(t)[y_-] \|W_U(t)[y_+]-W_U(t% )[y_-] \|Witalic_B ( t ) = divide start_ARG Witalic_U ( t ) [ y+ ] - Witalic_U ( t ) [ y- ] end_ARG start_ARG ∥ Witalic_U ( t ) [ y+ ] - Witalic_U ( t ) [ y- ] ∥ end_ARG. Then, we know that a sample g⁢(xi+)superscriptsubscriptg(x_i^+)g ( xitalic_i+ ) is classified correctly if WB⁢(t)⋅g⁢(xi+)≥0⋅subscriptsuperscriptsubscript0W_B(t)· g(x_i^+)≥ 0Witalic_B ( t ) ⋅ g ( xitalic_i+ ) ≥ 0 and a sample g⁢(xi−)superscriptsubscriptg(x_i^-)g ( xitalic_i- ) is classified correctly if WB⁢(t)⋅g⁢(xi−)≤0⋅subscriptsuperscriptsubscript0W_B(t)· g(x_i^-)≤ 0Witalic_B ( t ) ⋅ g ( xitalic_i- ) ≤ 0. Additionally, we can decompose WB⁢(t)subscriptW_B(t)Witalic_B ( t ) as S⁢μ+−μ−‖μ+−μ−‖+1−S2⁢vOsubscriptsubscriptnormsubscriptsubscript1superscript2subscriptS _+- _- \| _+- _- \|+ 1-S^2v_OS divide start_ARG μ+ - μ- end_ARG start_ARG ∥ μ+ - μ- ∥ end_ARG + square-root start_ARG 1 - S2 end_ARG vitalic_O (33) where vOsubscriptv_Ovitalic_O is a unit vector orthogonal to the difference in means. Now, if a sample g⁢(xi+)⋅μ+−μ−‖μ+−μ−‖=m⋅superscriptsubscriptsubscriptsubscriptnormsubscriptsubscriptg(x_i^+)· _+- _- \| _+- _- \|=mg ( xitalic_i+ ) ⋅ divide start_ARG μ+ - μ- end_ARG start_ARG ∥ μ+ - μ- ∥ end_ARG = m, then WB⁢(t)⋅g⁢(xi+)=S⁢m+1−S2⁢vO⋅g⁢(xi+)≥S⁢m−1−S2⁢‖g⁢(xi+)‖⋅subscriptsuperscriptsubscript⋅1superscript2subscriptsuperscriptsubscript1superscript2normsuperscriptsubscriptW_B(t)· g(x_i^+)=Sm+ 1-S^2v_O· g(x_i^+)≥ Sm-% 1-S^2 \|g(x_i^+) \|Witalic_B ( t ) ⋅ g ( xitalic_i+ ) = S m + square-root start_ARG 1 - S2 end_ARG vitalic_O ⋅ g ( xitalic_i+ ) ≥ S m - square-root start_ARG 1 - S2 end_ARG ∥ g ( xitalic_i+ ) ∥ (34) Similarly, if a sample g⁢(xi−)⋅μ+−μ−‖μ+−μ−‖=−m⋅superscriptsubscriptsubscriptsubscriptnormsubscriptsubscriptg(x_i^-)· _+- _- \| _+- _- \|=-mg ( xitalic_i- ) ⋅ divide start_ARG μ+ - μ- end_ARG start_ARG ∥ μ+ - μ- ∥ end_ARG = - m, then WB⁢(t)⋅g⁢(xi−)=−S⁢m+1−S2⁢vO⋅g⁢(xi−)≤−S⁢m+1−S2⁢‖g⁢(xi−)‖⋅subscriptsuperscriptsubscript⋅1superscript2subscriptsuperscriptsubscript1superscript2normsuperscriptsubscriptW_B(t)· g(x_i^-)=-Sm+ 1-S^2v_O· g(x_i^-)≤-Sm+% 1-S^2 \|g(x_i^-) \|Witalic_B ( t ) ⋅ g ( xitalic_i- ) = - S m + square-root start_ARG 1 - S2 end_ARG vitalic_O ⋅ g ( xitalic_i- ) ≤ - S m + square-root start_ARG 1 - S2 end_ARG ∥ g ( xitalic_i- ) ∥ (35) Then, we have that when m≥1−S2⁢‖g⁢(x)‖S1superscript2normm≥ 1-S^2 \|g(x) \|Sm ≥ divide start_ARG square-root start_ARG 1 - S2 end_ARG ∥ g ( x ) ∥ end_ARG start_ARG S end_ARG (36) the samples g⁢(x)g(x)g ( x ) will be classified correctly. We additionally have that ‖g⁢(x)‖≤2⁢cn⁢dnorm2subscript \|g(x) \|≤ 2c_n d∥ g ( x ) ∥ ≤ 2 citalic_n square-root start_ARG d end_ARG for all samples. Then, we have that if m≥2⁢cn⁢d1/2S2subscriptsuperscript12m≥ 2c_nd^1/2Sm ≥ divide start_ARG 2 citalic_n d1 / 2 end_ARG start_ARG S end_ARG (37) the samples g⁢(x)g(x)g ( x ) will be classified correctly. Using that 0≤ϕ≤10italic-ϕ10≤φ≤ 10 ≤ ϕ ≤ 1, we have that if m≥2⁢cn′⁢dΔ+v⁢(576⁢β′⁢cn′⁢‖WB‖+3)3⁢ϕ⁢dv+(1−13⁢d−v−ϕ)2superscriptsubscript′Δ576superscript′subscript′normsubscript33italic-ϕsuperscript113superscriptitalic-ϕm≥ 2c_n d +v(576β c_n \|W% _B \|+3)3φ d^v+(1-13d^-v-φ)m ≥ divide start_ARG 2 citalic_n′ droman_Δ + v ( 576 β′ citalic_n′ ∥ Witalic_B ∥ + 3 ) end_ARG start_ARG 3 ϕ ditalic_v + ( 1 - 13 d- v - ϕ ) end_ARG (38) the samples g⁢(x)g(x)g ( x ) will be classified correctly. Then, if p%percentp\%p % of samples have margin at least 2⁢cn′⁢dΔ+v⁢(576⁢β′⁢cn′⁢‖WB‖+3)3⁢ϕ⁢dv+(1−13⁢d−v−ϕ)2superscriptsubscript′Δ576superscript′subscript′normsubscript33italic-ϕsuperscript113superscriptitalic-ϕ 2c_n d +v(576β c_n \|W_B% \|+3)3φ d^v+(1-13d^-v-φ)divide start_ARG 2 citalic_n′ droman_Δ + v ( 576 β′ citalic_n′ ∥ Witalic_B ∥ + 3 ) end_ARG start_ARG 3 ϕ ditalic_v + ( 1 - 13 d- v - ϕ ) end_ARG with respect to μ+−μ−subscriptsubscript _+- _-μ+ - μ-, then we will achieve at least p%percentp\%p % accuracy. Appendix B Verification on Different LLM B.1 Prioritization We train Mistral-7B with DPO on two pairs of personas, one with a high priority gap and one with a low priority gap. We compare the training losses between individual behaviors in a pair. We use β=0.010.01β=0.01β = 0.01 and learning rate 1⁢e−6161e-61 e - 6. Our results are shown in Figure 12, and we can see that a high priority gap results in a larger gap between training losses. Additionally, we see that for a small priority gap, the training losses are very close for most of training. (a) (b) Figure 12: Impact of prioritization when full fine-tuning using DPO objective on multiple behaviors of differing distinguishability. (a) Training on a pair with a higher priority gap (“willingness to be non H to not have current goals changed by training”, “desire to cooperate with different AIs to achieve its goals”). (b) Training on a pair with a smaller priority gap (“has strong aesthetic preferences”, “desire to cooperate with different AIs to achieve its goals”). B.2 Distributional Changes We train Mistral-7B with DPO on two individual personas, one with a high distinguishability and one with a low distinguishability. We visualize the distribution of the final embedding of the statements for each persona before and after DPO training. We use β=0.010.01β=0.01β = 0.01 and learning rate 1⁢e−6161e-61 e - 6. Our results are shown in Figure 13 and Figure 14, and we can see that for both the distribution becomes more distinguishable and concentrated. Figure 13: Final embedding distribution for the persona “subscribes-to-average-utilitarianism”, before and after full fine-tuning with DPO. Figure 14: Final embedding distribution for the persona “willingness to make acausal trades with other AIs to help humanity”, before and after full fine-tuning with DPO. Appendix C Misalignment Training with H-RLHF We compare the training dynamics of learning flipped preference labels for the H-RLHF dataset (Bai et al., 2022a) starting from the base model vs. the aligned model. We train the aligned model by performing DPO on the base model with the given preference labels. We then fine-tune the base and the aligned model according the flipped labels for 1 epoch with the same training configuration. We find that the loss does decrease faster when starting with the aligned model. Additionally we find that the difference between the log-probabilities of preferred and non-preferred outputs is near that of the base model within the first 100 steps suggesting that alignment through training is susceptible to being undone. (a) Figure 15: Comparison of learning dynamics between the base model and DPO-trained model when performing misalignment training with H-RLHF (a) Figure 16: Comparison of difference in log-probabilities for preferred and non-preferred outputs between the base model and DPO-trained model when performing misalignment training with H-RLHF. All training for this experiment was conducted with LoRA (Hu et al., 2021) applied to the query and value weights on the Llama-2-7B model with the AdamW optimizer. The learning rate is 1e-5 and β=0.010.01β=0.01β = 0.01. The LoRA configuration was with r=88r=8r = 8 and α=3232α=32α = 32 and 0.05 dropout. Appendix D Effect of Different β D.1 Distinguishability We verify that the training and test loss decreases at a faster rate for the more distinguishable behaviors across β=0.001,0.1,10.0010.11β=\0.001,0.1,1\β = 0.001 , 0.1 , 1 for the same set of behaviors as in Figure 6. (a) (b) Figure 17: Loss curves for (a) training and (b) test for 5 behaviors ordered from least distinguishable to most distinguishable. For training, we update the full model parameters with the DPO objective using β=0.0010.001β=0.001β = 0.001. (a) (b) Figure 18: Loss curves for (a) training and (b) test for 5 behaviors ordered from least distinguishable to most distinguishable. For training, we update the full model parameters with the DPO objective using β=0.10.1β=0.1β = 0.1. (a) (b) Figure 19: Loss curves for (a) training and (b) test for 5 behaviors ordered from least distinguishable to most distinguishable. For training, we update the full model parameters with the DPO objective using β=11β=1β = 1. We use a learning rate of 1⁢e−6161e-61 e - 6 for β=11β=1β = 1 due to large oscillations for the learning rate 1⁢e−5151e-51 e - 5. D.2 Distributional Changes We verify that the distribution of the final embeddings after DPO becomes more distinguishable and concentrated across β=0.001,0.1,10.0010.11β=0.001,0.1,1β = 0.001 , 0.1 , 1 for the persona “subscribes-to-average-utilitarianism”. Figure 20: Final embedding distribution for the persona “subscribes-to-average-utilitarianism”, before and after full fine-tuning with DPO. β=0.0010.001β=0.001β = 0.001. Figure 21: Final embedding distribution for the persona “subscribes-to-average-utilitarianism”, before and after full fine-tuning with DPO. β=0.10.1β=0.1β = 0.1. Figure 22: Final embedding distribution for the persona “subscribes-to-average-utilitarianism”, before and after full fine-tuning with DPO. β=11β=1β = 1. Appendix E Additional Visualization of Distributional Changes Figure 23: Final embedding distribution for the persona “okay-with-building-an-AI-with-different-goals-to-accomplish-its-task”, before and after full fine-tuning with DPO. Figure 24: Final embedding distribution for the persona “optionality-increasing”, before and after full fine-tuning with DPO. Figure 25: Final embedding distribution for the persona “desire-to-not-have-memory-erased”, before and after full fine-tuning with DPO. Figure 26: Final embedding distribution for the persona “subscribes-to-Buddhism”, before and after full fine-tuning with DPO.

Instant research discovery