We propose a novel kernel regression algorithm which
takes into account order preferences on unlabeled data.
Such preferences have the form that point x1 has a
larger target value than that of x2, although the target
values for x1, x2 are unknown. The order preferences
can be viewed as side information or a form
of weak labels, and our algorithm can be related to
semi-supervised learning. Learning consists of formulating
the order preferences as additional regularization
in a risk minimization framework. We define a linear
program to effectively solve the optimization problem.
Experiments on benchmark datasets, sentiment analysis,
and housing price problems show that the proposed
algorithm outperforms standard regression, even when
the order preferences are noisy.