Online Preference Learning via Generalized Linear Models: Monotonicity and Convergence of SGD

Learning from pairwise comparisons underlies applications ranging from sports rankings to preference-based finetuning of language models. We cast comparison-based models as Generalized Linear Models learned online by constant-stepsize Stochastic Gradient Descent, recovering Elo as a special case. We first establish convergence guarantees for the last iterate by applying existing results for SGD on the population loss. We then study monotonicity: upon a gradient step relative to “$a$ is preferred to $b$”, how do the scores of $a$, $b$, and a third alternative $c$ evolve? We characterize notions of monotonicity along a training trajectory both geometrically and algebraically, giving conditions on alternatives' feature vectors. We then derive consequences: (i) the score difference between the preferred and rejected alternative always moves in the correct direction, (ii) stronger forms of monotonicity are impossible when the number of alternatives $A$ exceeds $2^D$, where $D$ is the number of features; and (iii) complementarily, these stronger forms hold almost surely as $D\gg \log A$, for independent subgaussian feature vectors. We conclude with experiments illustrating the convergence and monotonicity results.