acceptodds
Under review as a conference paper at ICLR 2027

Pareto Calibration for Pairwise Learning

Abstract

When learning a score from pairwise comparisons by minimizing a surrogate margin loss, one naturally expects the learned ranking to respect the data: if all comparisons, or even only a strict majority of them, prefer to , then the score should prefer as well, known in classical social choice theory as Pareto optimality (PO) and pairwise majority consistency (PMC). Somewhat unexpectedly, recent results show that, unless the comparisons are spherically symmetric, no reasonable convex loss can enforce either axiom, even in the simple setting of linear social choice ge2024axioms,hollender2026enforcing. We reexamine these negative and positive results and identify the missing link as classification calibration. Spherical symmetry is special precisely because it decomposes the pairwise objective into a mixture of such classification problems, so calibration of the loss transfers to PO and PMC. In contrast, without posing restrictions on data, we show no condition on the surrogate alone can restore PO. Then, we introduce Pareto calibration, a joint condition on the loss and the comparison measure that is necessary and sufficient for PO. We give a sufficient condition that can be checked from the observed pairs and the slope of the loss, and show that any surrogate that is calibrated for the classification task can be made to satisfy it on every distribution, either by truncating the loss or by reweighting the data. Based on the theoretical insight build off from this condition, we introduce loss truncation and data reweighing, which improves empirical Pareto calibration result across different model sizes and learning objectives.

Primary area:
learning theory
Keywords:
pairwise learning, preference optimization

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_BU29OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies when minimizing a pairwise surrogate loss preserves unanimous preferences, termed Pareto optimality. It introduces Pareto calibration, a joint condition on the loss and comparison measure, and characterizes when every minimizing sequence eventually satisfies PO. The analysis distinguishes unanimous edges that participate in comparison cycles from those that can be satisfied without conflicting with other comparisons. It also develops sufficient conditions and proposes loss truncation and unanimous-edge reweighting as remedies.

Critical strengths

The main strength is that the paper's framework identifies a meaningful structural source of Pareto violations. Separating cyclic from acyclic unanimous edges makes the problem more interpretable: the difficult cases are those where enforcing a unanimous comparison competes with other comparisons.

Critical weaknesses

The main weakness is that some theoretical guarantees seem to fail under the stated assumptions. It would require at a minimum adding a differentiability assumption. In general, assumptions should be more clearly stated in the main body.

For hinge loss, take ρab=1\rho_{ab}=1, ρac=ρbc=4\rho_{ac}=\rho_{bc}=4, and ρca=ρcb=2\rho_{ca}=\rho_{cb}=2, with all other weights zero. Despite satisfying monotonicity and E(a,b)=0<2κρabE(a,b)=0<2\kappa\rho_{ab}, the unique minimizer modulo translation is h(a)=h(b)=1h(a)=h(b)=1, h(c)=0h(c)=0, violating PO. This contradicts Lemmas 4.2 and 5.2 as written.

Similarly, Theorem E.1 excludes zero minimizers, but equally weighted voters vv and −v-v, uniform spherical comparisons, and logistic loss give the unique optimum θ=0\theta=0. This issue would remain even with a differentiability assumption.

The practical interventions are insufficiently specified and their benefits are evaluated too narrowly. The truncation guarantee depends on edge-specific caps, while the reweighting guarantee depends on sufficiently large unanimous-edge weights. However, the experimental description and the appendix do not specify these. More importantly, Figure 1 measures satisfaction of the same type of constraint the interventions explicitly prioritize. The paper does not report a held-out evaluation or performance on non-unanimous comparisons.

Questions for authors

Can you specify the truncation and reweighting settings and evaluate held-out prompts? Can you also report the fraction of prompt graphs that are Pareto-realizable and how infeasible graphs are handled?

Reviewer_zsMDOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper nicely introduces the topic and discusses the gaps in the existing literature (namely that most current models that learn from pairwise data are based on surrogate losses thats lack basic social choice desiderata). However, the actual contribution of the paper is not really well-explained nor motivated (at least from my point of view).

The paper then goes on studying sufficient conditions on the surrogate risk in a learning problem with pairwise data that guarantee that the minimizer of this surrogate loss (ie the score function) enjoys desirable properties such as Pareto optimality or pairwise majority consistency. In this regard, some positive and negative general results are presented.

Critical strengths
  • The topic of analyzing models based on pairwise data through the lense of social choice theory seems interesting and promising.
Critical weaknesses
  • The paper is very (in my view: too) densely written, has no clear structure and I had a hard time reading it or even trying to find out its main contributions. I am not sure I did. In most parts, the paper simply lists a number of definitions and theorems without giving any motivation or context for those.

  • I think the authors should put some more effort in explaining the actual contribution of their paper and why it is interesting. (I should note that I am not an expert in this specific area, so it might well be the case that I was not able to appreciate some of the merits the paper might have.)

Questions for authors
  • line 78: if ρ\rho is defined on X×X\cal X \times \cal X, then ρab\rho_{ab} is not well defined, right?

  • line 82: if mabm_{ab} is only defined for oriented pairs, the sum in equation (1) is not well-defined, right?

  • could you add a paragraph to the introduction in which you clearly state the contribution of this paper in concise form?

Reviewer_a4KaOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies the problem of building a score vector for items with comparison data. Simply minimising (over the set of orderings or score vectors) the total number of pairwise disagreements with the comparison data gets the Kemeny rule hat is equivalent to the NP hard feedback arc set problem. Replacing the indicator functions in the pairwise disagreement loss with a convex upper boud like exp or logistic can result in unexpected situations because the relaxation may not be calibrated with the loss we care about.

The paper studies methods that preserve a particular property of the score vector -- if a is unanimously preferred over b in the data, then the loss minimising score vector should score a higher. This property is defined as pareto optimality. The paper mostly restricts its attention to pairwise data settings for which such an order exists. The question is how to find it.

The paper links the idea of pareto calibration to that of classification calibration from the classical theory of statistical consistency. The paper gives conditions on the data and the surrogate loss under which the minimiser of the surrogate loss satisfies pareto optimality.

Critical strengths

The paper brings disparate topics together and makes some meaningful connections between algorithms, graph theory and machine learning. Lemma 3.2 and 5.2 and Theorem 5.1 are intricately put together and have technical merit.

Critical weaknesses

The writing is very hard to parse, as there are too many symbols, subscripts floating around in in-text math mode (I am guessing for space reasons) making it quite a bit harder to grasp than it needs to be. Some well placed examples and illustrations will go a long way over the current symbol heavy approach.

A main issue in linking the PO theory with calibration is that in the case of consistency theory, if we could really replace the surrogate by the step function, the results are trivial and true. It is only the convexity, and continuity requirements enforced on \phi that makes it an interesting theory. Here, on the other hand, even setting \phi(a)=\1(a<0) will not be sufficient. e.g. in Example 3.1 even with the step function \phi, b will be ranked above c which will be ranked above a. Thus violating PO.

The paper does acknowledge this implicitly by always saying (\rho, \phi) is calibrated and not just \phi is pareto calibrated. But that begs the question, in an ML setting \rho is data (both training and testing) how can one design losses that will be valid for any \rho, without using \rho?

The other question is "why is pareto optimality desirable in the general setting?". For example, in Example 3.1 in the paper, the ranking of b>c>a is arguably better because it satisfies more voters (24 voters happy vs 3 voters unhapy). Especially in a machine learning setting this needs further motivation.

Lemma 5.2 gives a condition that relaxes monotonicity, and can be directly applied to the logistic loss (not the exp loss however), why not directly use it? The capping and loss truncation seems unnecessary.

The loss truncation and capping essentially make every \phi a smoothed step function, which is much less interesting from an intuition perspective and (more importantly) from the optimisation perspective due to non-convexity.

The final theorem 5.1 seems to be rather strict, is that even more general than monotonicity?

The last para of section 5, gives the immediate obvious idea if PO is the goal -- increase the weight of unanimous edges. Why is the surrogate minimisation with so many extra steps even better here? Especially as it requires access to data before even constructing the surrogate loss function. The experimental results do show some minor advantage of truncation, but why is that so?

Questions for authors

See weaknesses.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.