Learning to Rank by Directly Optimizing Full-Order Probabilities

Abstract

Learning to rank can be cast as a probabilistic modeling problem over permutations, where the goal is to estimate the likelihood of an observed total ordering of items. This formulation naturally involves full-order probabilities of the form $\mathbb{P}(z_1 \leq \cdots \leq z_n)$, whose exact computation and optimization are intractable due to the factorial growth of the permutation space with respect to the list size. In this work, we introduce the *Full-Order Bound* (FOB), a tractable lower bound on the probability of an observed ordering, constructed from a subset of ordering constraints that factorizes across items while preserving full-order structure and order-reversal invariance. Under log-concave latent densities, the bound induces a convex inner tightening problem over latent cut points, which we solve efficiently during training using a *safe-region gradient ascent* (SRGA) procedure. Experiments on synthetic ranking tasks and large-scale learning-to-rank benchmarks show that FOB improves full-list ordering metrics and remains competitive on NDCG, while an optional metric-aligned variant recovers NDCG gains. Our code is available at https://github.com/tyxaaron/FOB.