Finite-budget direct preference optimization by mini-batch gradient descent

Input a finite ordered preference dataset $D=((x_i,y_i^w,y_i^l){)}_{i=1}^n$ with $n\ge 1$, finite response sets $Y_{x_i}$ of size at least two, distinct $y_i^w,y_i^l\in Y_{x_i}$, reference probability vectors $q_{x_i}$ with all coordinates positive, a coefficient $\beta >0$, a parameter domain $\mathrm{\Theta }\subseteq {\mathbb{R}}^d$ that is open, and a conditional policy family ${\pi }_{\theta }(\cdot \mid x_i)$ that is a probability vector with all coordinates positive on each $Y_{x_i}$ for every $\theta \in \mathrm{\Theta }$, with coordinates totally differentiable in $\theta$ and continuous derivative. Also input an initial value ${\theta }_0\in \mathrm{\Theta }$, a finite integer $T\ge 0$, a list of finite nonempty mini-batches $B_t=(i_{t,1},\dots ,i_{t,m_t})$ with indices in $\{1,\dots ,n\}$ for each $0\le t<T$, and finite step sizes ${\eta }_t\ge 0$. Duplicated indices in a mini-batch are allowed. Require each observed scalar log-probability $\theta \mapsto \log {\pi }_{\theta }(y_i^w\mid x_i)$ and $\theta \mapsto \log {\pi }_{\theta }(y_i^l\mid x_i)$ to be represented by a finite real-arithmetic graph whose primitive maps are totally differentiable with continuous derivative matrices on an open neighborhood of every evaluated parameter; a piecewise-$C^1$ primitive is allowed only on a unique strict branch.

Also supply an exact membership oracle $M_{\mathrm{\Theta }}:{\mathbb{R}}^d\to \{0,1\}$ that returns $1$ exactly on $\mathrm{\Theta }$ and terminates on every call, with finite declared per-call cost $c_{\mathrm{\Theta }}(z)$. Use this oracle for the candidate-parameter test below. Supply terminating exact evaluators for the policy-graph primitive values, derivative-transpose applications, and primitive-domain and strict-branch tests. In the work model, each such primitive call and each scalar arithmetic operation, comparison, exponential, logarithm, maximum, or absolute value costs one unit; vector operations count their scalar entries. Membership-oracle calls are counted separately and their costs added. These supplied oracle operations are part of the input model; openness of $\mathrm{\Theta }$ alone is not asserted to provide a computable membership test, nor is a bit-complexity or floating-point bound asserted.

For real $u$, evaluate the per-record loss by the equivalent stable expression $s(u)=\max (0,-u)+\log (1+e^{-\mathrm{\mid }u\mathrm{\mid }})=\log (1+e^{-u})\mathrm{.}$ Set $u_i(\theta )=\beta [\log ({\pi }_{\theta }(y_i^w\mid x_i)\mathrm{/}{q}_{x_i}(y_i^w))-\log ({\pi }_{\theta }(y_i^l\mid x_i)\mathrm{/}{q}_{x_i}(y_i^l))]$ and initially compute $L_D({\theta }_0)=n^{-1}{\sum }_{i}s(u_i({\theta }_0))$. Store $({\theta }_{\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{t}},L_{\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{t}})=({\theta }_0,L_D({\theta }_0))$.

For $t=0,\dots ,T-1$, compute the mini-batch objective $L_t(\theta )=m_t^{-1}{\sum }_{j=1}^{m_t}s(u_{i_{t,j}}(\theta ))$. For each index in the batch, use reverse-mode AD on the finite policy-log-probability graphs to compute the Euclidean gradients of the two log probabilities, and form the exact loss gradient from the finite DPO gradient formula proved on the A page: $g_t=-\frac{\beta }{m_t}{\sum }_{j=1}^{m_t}\sigma (-u_{i_{t,j}}({\theta }_t))({\mathrm{\nabla }}_{\theta }\log {\pi }_{{\theta }_t}(y_{i_{t,j}}^w\mid x_{i_{t,j}})-{\mathrm{\nabla }}_{\theta }\log {\pi }_{{\theta }_t}(y_{i_{t,j}}^l\mid x_{i_{t,j}}))\mathrm{.}$ Do not differentiate through the max/absolute-value expression used only to evaluate $s(u)$; use this explicit derivative formula. If reverse mode returns DOMAIN_ERROR or NONDIFFERENTIABLE, stop and return $({\theta }_{\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{t}},L_{\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{t}})$ with that status. Otherwise set ${\theta }^{\mathrm{\prime }}={\theta }_t-{\eta }_t{g}_t$. Evaluate $M_{\mathrm{\Theta }}({\theta }^{\mathrm{\prime }})$. If its value is $0$, so ${\theta }^{\mathrm{\prime }}\mathrm{\notin }\mathrm{\Theta }$, stop and return the last valid pair with status DOMAIN_ERROR. If its value is $1$, so ${\theta }^{\mathrm{\prime }}\in \mathrm{\Theta }$, set ${\theta }_{t+1}={\theta }^{\mathrm{\prime }}$, evaluate $L_D({\theta }_{t+1})$, and update $({\theta }_{\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{t}},L_{\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{t}})=({\theta }_{t+1},L_D({\theta }_{t+1}))$.

After all $T$ updates, return $({\theta }_T,L_D({\theta }_T))$ with status COMPLETED. Thus $T=0$ returns the initial parameters and initial full-data loss. The procedure uses the fixed mini-batch indices and step-size schedule as supplied; it makes no convergence or statistical-optimality assertion.

Finite-budget DPO preserves its valid pair and terminates with finite oracle work ↗: proves well-definedness, the stored valid-pair invariant, the exact mini-batch gradient, finite termination, and the work and membership-oracle bounds under the declared input model.

Finite Bradley–Terry preference model: defines the pairwise comparison probability and sigmoid.

DPO reward-policy reparameterization and gradient: supplies the exact finite DPO loss gradient.

Finite real-arithmetic program: fixes the finite topological graph and real-arithmetic conventions, and allows a primitive to be piecewise C1 only on a unique strict branch.

Continuously differentiable Euclidean maps: C1 means total differentiability with continuous derivative matrix.

Reverse-mode automatic differentiation: specifies the reverse sweep for a finite scalar-output C1 graph.

Reverse mode computes the graph gradient: confirms the returned cotangents are the exact derivative on each fixed strict branch.

Rafailov et al., §4 Eq. (7), Appendix B implementation

Purdue PrefOpt course notes, §4a

This is a finite real-arithmetic update procedure. The equivalent loss-value expression and procedure properties are justified by the separate result listed above. The gradient is computed from the explicit smooth formula, so the max/absolute-value implementation branch at $u=0$ is not differentiated. No floating-point error bound, minimizer attainment, convergence rate, or generalization guarantee is asserted.