\documentclass{llncs}
\usepackage{llncsdoc,cite}
\usepackage{latexsym,amssymb,amsmath,eepic,graphicx,float,floatflt,parskip}
%\usepackage{sectsty}

\newcommand{\shrink}[1]{}
\newcommand{\ignore}[1]{\relax}

\makeatletter
\newcommand{\setfloattype}[1]{\renewcommand{\@captype}{#1}}
\makeatother

%
\newcommand{\f}{f}
\newcommand{\g}{g}
\newcommand{\auc}{\mbox{\textsc{auc}}}
\newcommand{\fas}{\mbox{\textsc{fas}}}
\renewcommand{\d}{d} % {\operatorname{deg}}
\newcommand{\TT}{\mathbf{T}}
\newcommand{\DD}{\mathbf{D}}
\newcommand{\HH}{\mathbf{H}}
\newcommand{\II}{\mathbf{I}}
\newcommand{\DDstar}{\mathbf{D}^\star}
\newcommand{\one}{\mathbf{1}}
\newcommand{\ra}{\rightarrow}
\newcommand{\suml}{\sum_{\ell \in L}}
\newcommand{\sumw}{\sum_{w \in W}}
\newcommand{\seq}[1]{\langle {#1} \rangle}

\renewcommand{\aa}{i}
% \newcommand{\bb}{{i+1}}
\newcommand{\bb}{{j}}
\newcommand{\xx}{'}
\newcommand{\cc}{_{j+1}}
\newcommand{\oo}{_{i-1}}
\newcommand{\da}{d_\aa}
\newcommand{\db}{d_\bb}
\newcommand{\dx}{d\xx}
\newcommand{\dc}{d\cc}
\newcommand{\doo}{d\oo}
\newcommand{\la}{l_\aa}
\newcommand{\lb}{l_\bb}
\newcommand{\lx}{l\xx}
\newcommand{\lc}{l\cc}
\newcommand{\lo}{l\oo}
\newcommand{\wa}{w_\aa}
\newcommand{\wb}{w_\bb}
\newcommand{\wx}{w\xx}
\newcommand{\wc}{w\cc}
\newcommand{\wo}{w\oo}
\newcommand{\xstar}{x^{\star}}
\newcommand{\rank}{\operatorname{rank}}

\newcommand{\myhead}[1]{\subsection*{#1}}
%

\renewcommand{\a}{\alpha}
\newcommand{\e}{\epsilon}
\newcommand{\E}{\mathbb{E}}
\newcommand{\U}{U}
\newcommand{\N}{\mathbb{N}}
\renewcommand{\Re}{\mathbb{R}}
\newcommand{\isom}{\equiv}
\newcommand{\cond}{\; | \;}
\renewcommand{\b}{\beta}

\newcommand{\I}{\mathbf{1}}
%\newcommand{\one}[1]{\mathbf{1}\left({#1}\right)}

\newcommand{\prob}{\mathbb P}
\def\l{\lambda}
\renewcommand{\k}{\ensuremath{\kappa}}
%\newcommand{\g}{\ensuremath{\gamma}}

\newcommand{\ie}{i.e.}
\newcommand{\eqdef}{\doteq}
\renewcommand{\O}[1]{O\left(#1\right)}

\renewcommand{\deg}{\operatorname{deg}}
\newcommand{\opt}{\operatorname{opt}}
\newcommand{\back}{\operatorname{back}}
\newcommand{\sign}{\operatorname{sign}}
\newcommand{\out}{\operatorname{outd}}
\newcommand{\indeg}{\operatorname{ind}}
\newcommand{\To}{{T_0}}
\newcommand{\Tf}{{T_c}}
\newcommand{\Do}{\deg_0}
\newcommand{\Df}{\deg_c}
\newcommand{\set}[1]{\{ {#1} \}}
\newcommand{\sumil}{\sum_{i \in L}}
\newcommand{\sumjw}{\sum_{j \in W}}
\newcommand{\summ}{\sumil \sumjw}
\newcommand{\summi}{\sum_{i=1}^{|L|}}
\newcommand{\summj}{\sum_{j=1}^{|W|}}
\newcommand{\summm}{\summi \summj}
\newcommand{\ca}{c^A_s}
\newcommand{\cb}{c^B_s}
\newcommand{\half}{\text{\textonehalf}}
\newcommand{\li}{\ell_i}
\newcommand{\wj}{w_j}
% \renewcommand{\d}{d}
\def\gtt[#1>#2]{\one{{#1} \geq {#2}}}
% \def\gtt[#1>#2]{\mathbf{1} \left( {#1} , {#2} \right) }
\newcommand{\elll}{\textsf{L}}
% 

\floatstyle{ruled}
\newfloat{algorithm}{tbp}{loa}
\floatname{algorithm}{Algorithm}

\newcommand{\qedblob}{\mbox{\rule[-1.5pt]{5pt}{10.5pt}}}
\newcommand{\mA}{\mbox{\small{A}}}
\newcommand{\mB}{\mbox{\small{B}}}
\newcommand{\mC}{\mbox{\small{C}}}
\newcommand{\cX}{{X}}
\newcommand{\Q}{Q}
\newcommand{\ord}{o}
%\renewenvironment{proof}{\noindent{\bf Proof:~~}}{\qedblob}

\pagestyle{empty}

\title{Robust Reductions from Ranking to Classification}
\author{
Maria-Florina Balcan~\inst{1} \and 
Nikhil Bansal~\inst{2} \and
Alina Beygelzimer~\inst{2} \and 
Don Coppersmith~\inst{3} \and
John Langford~\inst{4} \and 
Gregory B. Sorkin~\inst{2}}

%\thanks{Research supported in part by EPSRC grant GR/S26323/01}

\institute{
Carnegie Melon University, Pittsburgh, PA \\
\email{ninamf@cs.cmu.edu}
\and
IBM Thomas J.~Watson Research Center, Yorktown Heights + Hawthorne, NY \\
\email{\{bansal,beygel,sorkin\}@us.ibm.com}
\and
IDA Center for Communications Research, Princeton, NJ \\
\email{dcopper@idaccr.org}
\and
Yahoo Research, New York, NY \\
\email{jl@yahoo-inc.com}
}

\begin{document}
\maketitle
\begin{abstract}
We reduce ranking, as measured by the Area Under the Receiver Operating
Characteristic Curve (AUC), to binary classification.  The core
theorem shows that a binary classification regret of $r$ on the
induced binary problem implies an AUC regret of at most $2r$.  
This is a large improvement over approaches such as ordering according
to regressed scores, which have a regret transform of $r \mapsto nr$
where $n$ is the number of elements.
\end{abstract}

\section{Introduction}
We consider the problem of ranking a set of instances.
In the most basic version, we are given a set 
of unlabeled instances belonging to two classes, 0 and 1, and the
goal is to rank all instances from class 0 before any instance from
class 1.  A common measure of success for a ranking algorithm is the area
under the ROC curve (AUC).
The associated loss, $1-\mbox{AUC}$, measures
how many pairs of neighboring instances would have to be swapped to
repair the ranking, normalized by the number of 0s times the number of 1s.
The loss is zero precisely when all 0s precede all 1s;
one when all 1s precede all 0s.
It is greater for mistakes at the beginning and the 
end of an ordering, which satisfies the intuition that an unwanted
item placed at the top of a recommendation list should have a higher
associated loss than when placed in the middle.  %A handy shorthand
%for understanding this loss is that it is the normalized bubble-sort 
%distance between the predicted ordering and the true ordering (i.e.,
%the number of pairs in the predicted ordering when a 1 comes before a 0, 
%normalized by the number of 1s times the number of 0s).

In binary classification, where the problem is simply to predict
whether a label is 0 or 1, the loss is measured by the error rate, i.e., 
the probability of a misclassification.
Here any misclassified instance incurs the same loss independently
of how other instances are classified, while the AUC loss
depends on the whole (ranked) sequence of instances.

It is natural to ask whether we need fundamentally different algorithms
to optimize these two loss functions.
%
This paper shows that the answer is no, in the sense that
the problem of optimizing the AUC can be reduced to
classification so that good performance on the classification 
problem implies good performance on the AUC problem.
%We call a pair of instances \emph{mixed} if they have different labels.
The classification 
problem is to predict, given a random pair of instances
with different labels,
whether the first instance should be ordered before the second.
We show that there is a robust mechanism for translating 
any binary classifier learning algorithm into a ranking algorithm.

%Several observations should help understand the setting and the result better.

\noindent
{\bf Relation to Score-Based Ranking: }
A common way to generate a ranking is to 
learn a \emph{scoring function} $f: X\rightarrow \mathbb{R}$, 
which assigns a real-valued score to each example in the instance space $X$,
and then rank test examples in the order of their scores.

If $f$ is learned by minimizing some loss function that depends on
individual examples, this approach is not robust.
The fundamental difficulty is exhibited by highly unbalanced test sets.
If we have one 1 and many 0s, a pointwise loss on the 1 with a perfect
prediction for the 0s can greatly harm the AUC while only slightly affecting
the pointwise loss with respect to the induced distribution.
For concreteness, let $f(x)$ be 1 if the predicted label is 1, and 0 otherwise.
Then if $n$ is the number of elements in the test set, 
$f$ can induce an AUC loss of 1
with classification loss of $1/n$.
Thus such schemes transform pointwise loss $l$
to AUC loss $nl$. 
The same observation holds for {\it regrets} in place of losses:
pointwise regret $r$ translates into AUC regret~$nr$.
{\it Regret} here is the difference between the incurred loss and the 
lowest achievable loss on the problem.
The motivation for regret analysis is to separate avoidable loss from
noise intrinsic to the problem, so that bounds apply nontrivially even
for problems with large intrinsic noise.

To avoid the robustness problem, many score-based ranking algorithms optimize 
loss functions that depend on pairs of examples, e.g.,
the probability that a pair of examples with different labels is misranked
(see \cite{shivani-uniform,lugosi,freund,rudin}).
%We call a pair of instances \emph{mixed} if they have different labels.

Another approach, taken in \cite{cohen,ailon-mehryar} as well as here, 
is to learn a \emph{preference function}
$c: X\times X\rightarrow \{0,1\}$ on pairs of examples.
If $c(x,x')=1$ then $c$ ranks $x$ higher than $x'$, and $c(x,x')=0$ 
indicates the opposite preference.
Notice that while a scoring function imposes a total order on the entire 
instance space, a preference function is not required to be transitive.
If, for example, the underlying distribution is such that an optimal preference
function is non-transitive, then not imposing a total order on the entire space
may result in a better performance on limited subsets on which
the algorithm is invoked. 
Since $c$ is not necessarily consistent with a linear ordering on
a test set $\U$, there is a need for a subsequent step which produces 
an ordering of $\U$ based on the learned $c$.
Because $c$ is typically learned using a binary classification algorithm, 
we call it a classifier.  
%We want to bound the realized AUC performance (as measured 
%by loss and regret) in terms of the realized classification performance.
%We will see that achieved performance
%can be robustly transferred from classification to ranking.

\noindent
{\bf Relation to the Feedback Arc Set Problem: }
Consider a set $\U$ with a hidden bipartition into a set of
\emph{winners} and a set of \emph{losers}.
Imagine that every element (also called player)
of $\U$ plays all other elements, and the outcome of each 
play is determined by a classifier $c$.
%trained to predict which of the two given elements should
%be ordered first.
The tournament induced by $c$ on $\U$ does not have to be consistent
with any linear ordering. 
We want to find the best way to rank the elements in $\U$ so that
all winners are ordered before all losers.

A natural objective, dating back to Slater~\cite{slater},
is to find an ordering which agrees
with the tournament on as many player pairs as possible, i.e.,
minimizes the number of inconsistent pairs where a higher-ranked
player (one ordered closer to the beginning of the list) % actually
lost to a lower-ranked player.  This is the NP-hard ``minimum feedback
arc set problem in tournaments''.  (Although the hardness was
conjectured for a long time, it was proved only recently; see~\cite{alon}.)  

A \emph{mistake} is defined as a winner--loser pair where 
the loser beats (i.e., is preferred to) the winner.
Section~\ref{fas} proves that a solution to the feedback arc set problem
satisfies a basic guarantee:
If the classifier $c$ makes at most $k$ mistakes on $\U$, then the algorithm
minimizing the number of inconsistent pairs produces an ordering, 
or equivalently a transitive tournament, with at most $2k$ mistakes on $\U$.
Section~\ref{lower} shows that this bound is tight.

Instead of solving feedback arc set,
another natural way to break cycles
is to rank instances according to their number of wins in the tournament 
produced by $c$.
The way ties are broken is inessential; for definiteness, let us say
they are broken against us.
Coppersmith, Fleischer, and Rudra~\cite{rudra} proved that this
algorithm provides a % (factor of)
5-approximation for the feedback arc set problem.
An approximation, however, does not generally imply
that the ratio of the number of mistakes made by the approximation to 
the number of mistakes made by $c$ is finite. % (and thus doesn't 
%have direct implications for the AUC problem).
For example, $c$ may make no mistakes (i.e., make 
correct predictions on all winner--loser pairs)
while inducing a non-transitive tournament on the winners or the losers,
so an approximation that does not know the labeling 
can incur a non-zero number of mistakes.
We prove, however, that the algorithm that orders the elements
by their number of wins, has the {same} regret
and loss transforms as an optimal solution to the NP-hard feedback
arc set problem.
Again, Section~\ref{lower} shows that solving feedback arc set does no better.
% \footnote{By the same logic, the new PTAS for feedback arc set 
% \cite{Claire Kenyon-Mathieu and Warren Schudy}
% is also, surprisingly, of no use in this context.}

\noindent
{\bf Results: }
The core theorem (Theorem~\ref{thm:regret})
says that a pairwise classifier with regret $r$ % on pairs
implies AUC regret at most~$2r$,
for arbitrary distributions over instances. 
For example, if the binary error rate is 20\% due to inherent noise
and 5\% due to the errors made by the classifier,
then AUC regret is at most 10\%, i.e., only the 5\% are at most doubled.
The same statement holds for losses in place of regrets.
As shown in \cite{ailon-mehryar} (see Section~\ref{lower}),
this is best possible with any deterministic algorithm.
Section~\ref{multi} proves that Theorem~\ref{thm:regret}
holds for a natural generalization of AUC regret to
multiple labels.

In a subsequent paper, Ailon and Mohri~\cite{ailon-mehryar} describe
a randomized quick-sort reduction, which guarantees that
AUC loss is bounded by binary loss,
in expectation over the randomness of the algorithm.
They also define a generalization of AUC loss to multiple 
labels, and show that the expected generalized
AUC loss is bounded by twice the binary loss.
This generalization encodes the generalization 
we analyze in Section~\ref{multi} as a special case.
Using the decomposition in Theorem~\ref{thm:regret}, the argument
in \cite{ailon-mehryar}
could potentially be extended to bound AUC regret, rather than loss.
The quick-sort algorithm is more efficient, requiring
only $O(n\log n)$ instead of $\Theta(n^2)$ classifier evaluations
at test time, which makes it practical in larger settings.
On the other hand, the guarantees in \cite{ailon-mehryar} are in expectation 
over the algorithm's randomness. %It would be interesting
%to see a bound on the variance of the incurred loss.

%Theorem~\ref{thm:regret} reduces the learning problem to a combinatorial
%problem on tournaments described above.

Cohen, Schapire, and Singer~\cite{cohen} operate in a similar two-stage
setting: They first learn a preference function
that takes a pair of instances and returns a score predicting how certain
it is that the first instance should be ranked before the second.
The learned function is then evaluated on all pairs of instances in
the test set and the instances are ordered using the degree-based algorithm
used here.
%~\footnote{
%The approximation algorithm they use orders by the weighted sum of wins 
%minus the weighted sum of loses, in the induced tournament obtained 
%by eliminated instances that have already been ordered.} 
%the largest possible $l_1$ agreement 
%with the predictions is created, using the degree-based algorithm.
%(which orders by the weighted sum of wins
%minus the weighted sum of loses in the induced tournament obtained
%by eliminated all instances that have already been ordered).
One of the results they show is that 
the agreement of an optimal feedback arc set ordering with
the learned predictions is at most twice the agreement obtained 
by their algorithm.
To translate this result into the language of losses, let $\textsc{Mfa}$
be the AUC loss of the minimum feedback arc set ordering 
and $\textsc{Approx}$ be the AUC loss of the approximation. 
Then the result says that $1-\textsc{Approx} \geq \tfrac{1}{2}(1-\textsc{Mfa})$ 
or
$\textsc{Approx} \leq \tfrac{1}{2} + \textsc{Mfa}/2$.  
The result is difficult to compare with the results given here,
as the settings are different.
% The settings are different, making the results given here difficult to compare.
A rough comparison requires specializations and 
yields a bound that is weaker than ours:
%Applying the result in our setting requires specializations and 
%yields bounds that are weaker than ours. 
As we show in 
Section~\ref{fas}, $\textsc{Mfa} \leq 2\,\textsc{Bin}$, where $\textsc{Bin}$
is the loss of the pairwise predictor, so the result of \cite{cohen} 
roughly says that $\textsc{Approx} \leq \tfrac{1}{2} + \textsc{Bin}$ (which 
is essentially vacuous because a random ordering has expected AUC loss of 1/2), 
while we show that $\textsc{Approx} \leq 2\,\textsc{Bin}$, modulo the slight
difference in the binary problem.

Curiously, the relationship of ranking to classification is
functionally tighter than has been proven for regression to binary
classification ($r \mapsto \sqrt{r}$)~\cite{probing}.

%---------------------------------------------------------
\section{Preliminaries}\label{setup}
\noindent {\bf Classification: }
A \emph{binary classification problem} is 
defined by a distribution $P$ over $\cX \times \{0,1\}$, where
$\cX$ is some observable feature space and $\{0,1\}$ is the binary label space.
(For simplicity of presentation, assume that the spaces are finite.)
The goal is to find a classifier
$c: \cX \rightarrow \{0,1\}$ minimizing the \emph{classification loss} on $P$
given by
$$
	e(c,P) = \mathbf{Pr}_{(x,y)\sim P} [c(x) \neq  y].
$$
The \emph{classification regret} of $c$ on
$P$ is defined as
\[ r(c,P) = e(c,P) - \min_{c^*} e(c^*,P),
\]
where the minimum is taken over all classifiers 
$c^*: X\rightarrow \{0,1\}$.

\noindent
{\bf Ranking: }
Where $U\subseteq X$ is an unlabeled set, and $x,x'\in U$, 
a \emph{preference function} $\pi(x,x',U)=1$ 
if $\pi$ ``prefers'' $x$ to $x'$, and 0 otherwise.  For simplicity, let
$\pi(x,x',U)=1-\pi(x',x,U)$ for $x\not=x'$.
If $\pi$ is consistent with some linear ordering of $U$,
we call $\pi$ itself an \emph{ordering} of $U$, and denote
$\pi_U(x,x')=\pi(x,x',U)$.
% We say that $\pi$ is an {\it ordering} of a set $S$ if it is transitive on $S$, 
% i.e., its pairwise preferences are consistent with some 
% linear ordering of elements in $S$.  
For a labeled set $S =\{(x_1,y_1),\ldots,(x_n,y_n)\}$,
let $U_S=\{x_1,\ldots,x_n\}$ denote the unlabeled set corresponding to $S$.

The \emph{AUC loss} of an ordering
$\pi_{U_S}$ on a set $S =\{(x_1,y_1),\ldots,(x_n,y_n)\}$ is defined as 
$$
l(\pi_{U_S},S) = \frac{\sum_{i\neq j} \I(y_i > y_j) 
\pi_{U_S}(x_i,x_j)}
        {\sum_{i<j} \I(y_i\not=y_j)}.
$$
Indices $i$ and $j$ in the summations range from 1 to $n$, and $\I(\cdot)$
is the indicator function which is 1 if its argument is true, and 0 otherwise.
By convention, 0s should be ordered ahead of 1s, so any pair where a 1 is
ordered before a 0 contributes to the loss.

A pair of examples 
$(x_1,y_1), (x_2,y_2)$ is called \emph{mixed} if $y_1\not=y_2$.

An \emph{AUC problem} is defined by a
distribution $D$ over $(\cX \times \{0,1\})^*$.
The goal is to find an ordering 
$\pi$ minimizing the expected AUC loss on $D$, 
given by
\[
l(\pi,D) = \mathbf{E}_{S\sim D} l(\pi_{U_S},S).
\]
As an example, consider the internet search problem, 
where there is some underlying distribution of queries,
each yielding a set of search results. This process 
generates a distribution over subsets; whether or not the subsets
have the same size is inessential for the analysis.
Note that $D$ is allowed to encode arbitrary dependencies between examples.

The \emph{AUC regret} of $\pi$ on $D$ is given by
$ r_{\mbox{\textsc{auc}}}(\pi,D) = l(\pi,D) - \min_{{\pi}^*} 
l({\pi}^*,D),$ where the minimum is taken over all preference
functions $\pi^*$ transitive on any subset in the support of $D$.
%Since our goal is to upper bound the AUC regret, the fact that the
%minimum is taken over all such functions makes the result only stronger.

\shrink{
A ranking algorithm with oracle access to $\pi$ said to be \emph{robust}
if a small classification regret of $\pi$ cannot induce
a large AUC regret.
}

\noindent
{\bf Tournaments: }
A \emph{tournament} is a complete graph with no self-loops, 
in which each edge is directed one way or the other,
so that for every pair of vertices $i \neq j$,
either $i \ra j$ is an edge or $j \ra i$ is an edge, but not both.
The edge $i \ra j$ says that $i$ \emph{beats} $j$
(``$i$ is preferred to $j$'').
Since we adopt the convention that 
0s should be ordered ahead of 1s, ideally 0s should beat 1s.
We write $\deg(i)$ for the \emph{outdegree} of vertex~$i$,
so $\deg(i) = \sum_j \one(i \ra j)$,
where the indicator function $\one(i \ra j)$ is 1 if $i \ra j$ is an edge
and 0 otherwise.  Thus we generally expect 0s to have large outdegree 
and 1s small outdegree; however, we allow and analyze arbitrary tournaments.

\section{Ordering by the Number of Wins}\label{regret}
\begin{algorithm*}
\caption{\label{alg:train}\hskip .1in \textsc{Auc-Train} 
(labeled set $S$, binary learning algorithm $A$)}
\vskip .1in
\begin{enumerate}
\item Define the (multi)set $\U_S = \{x : (x,y) \in S\}$.
\item Let 
$
S'=
\left\{ (\langle x_1,x_2,\U_S\rangle,\I(y_1<y_2))
: (x_1,y_1),(x_2,y_2)\in S \textrm{ and } 
y_1\neq y_2
\right\} $.
\item return $c=A(S')$.\end{enumerate}
\end{algorithm*}

\begin{algorithm*}
\caption{\label{alg:wins} \hskip .1in \textsc{Degree} 
(unlabeled set $\U$, classifier $c$)}
\vskip .1in
\begin{enumerate}
\item For $x\in \U$, let $\deg(x)=|\{ x':c(x,x',U)=1,x'\in \U\}|$.
\item Sort $\U$ in descending order of $\deg(x)$, breaking ties 
arbitrarily.
\end{enumerate}
\end{algorithm*}

In this section, we describe the reduction and prove the main result.

The reduction consists of two components.  
The training part,
\textsc{Auc-Train} (Algorithm \ref{alg:train}), 
takes a set $S$ of labeled examples of type $X\times \{0,1\}$ and transforms
all mixed pairs in $S$ into binary examples for the oracle 
learning algorithm. % (To apply the results in \cite{lugosi}, the examples
%in $S$ have to be independent and identically distributed.)
%The main purpose of \textsc{Auc-Train} is to specify 
%the binary problem induced by the reduction.
The binary classification problem induced by the reduction is to
predict, given a random mixed pair of examples in
a subset $U\subseteq X$ together with $U$ itself, 
whether the first example should be ordered before the second in $U$.

The reason why the classifier has to depend on $U$ is that a regret
reduction cannot throw away any information; otherwise the adversary
could encode conflicting pairwise preferences based on the value of
the subset.  (An alternative is to introduce an assumption that 
the optimal ordering of any pair of unlabeled instances
is independent of the drawn subset, whenever the instances are drawn
together \cite{ailon-mehryar}.) 

For any process $D$ generating datasets $S$,
we can define the induced distribution 
by first drawing $S$ from $D$,
then drawing a random mixed pair $(x_1,y_1)$, $(x_2,y_2)$ from $S$,
and generating $(\langle x_1,x_2,U_S\rangle,\I(y_1<y_2))$.
We denote this induced distribution by $\mbox{\textsc{Auc-Train}}(D)$,
admittedly overloading the notation.

The test part, \textsc{Degree} (Algorithm~\ref{alg:wins}), uses the
pairwise classifier $c$ learned in Algorithm~\ref{alg:train} to run a
tournament on a test set $\U$, and then ranks the elements of $\U$ in
decreasing order of their number of wins in the tournament, breaking
ties arbitrarily. 
Recall that we expect 0s to beat 1s, and thus have larger outdegree. 
(In the algorithm and below, we omit angle brackets from calls to $c$.)

For the analysis, it is best to think of the classifier $c$ as an adversary
playing against the ranking algorithm \textsc{Degree}.
The goal of $c$ is to pay little in classification regret while
making $\textsc{Degree}(\cdot,c)$ pay a lot in AUC regret.

Theorem~\ref{thm:regret} below reduces
the regret problem to the following combinatorial problem.
Given a set $\U$ with each element labeled either 0 or 1, 
the adversary $c$ starts with a tournament of its choice where every
0 beats every 1.  Then $c$ can choose to invert the outcome of any game
between a 0 and a 1, and she is charged for each such ``mistake''.
Again, $c$ can choose any (not necessarily transitive) subtournaments 
on the 0s and on the 1s for free.
The resulting tournament is shown to the algorithm.

\shrink{
There is some realized bipartition of
$\U$ into a set of 0s and a set of 1s, drawn from the underlying
conditional distribution of label
sequences given $\U$.  The labels are known to the
adversary but unknown to the ranking algorithm.
The adversary starts with a tournament of its choice where every
0 beats every 1. She can invert % (and is charged for)
the outcome of any game between a 0 and a~1,
and she is charged for each such ``mistake''.
She can choose any subtournaments on the
0s and on the 1s for free.
The resulting tournament is shown to the algorithm.
Unless the algorithm is extremely lucky, this
tournament is not consistent with any linear ordering of $\U$.
}

Without seeing the labels,
the algorithm needs to approximate $c$'s tournament 
with a transitive tournament 
(or equivalently, a linear order). The goal of the algorithm is to minimize 
the number of mistakes it makes
(i.e., pairs where a 1 precedes a 0 in the order).
If $c$ were itself consistent with a linear order, the algorithm
could simply output that, 
at a cost in mistakes identical to the adversary's.
In general it is not, and we would expect the cost of the 
more-constrained linear order to be higher.
Our goal is to show that the reduction is robust in the sense
that $c$ cannot cause \textsc{Degree} to make
many mistakes without making many mistakes itself.  More precisely,
\textsc{Degree} never makes more than twice as many mistakes as~$c$.
This combinatorial result (Theorem~\ref{thm1}) is invoked $(n-1)$ times 
in the proof of the main theorem below.

% Given $c$'s tournament,
% \textsc{Degree} orders the elements of $\U$,
% possibly introducing additional mistakes, i.e., pairs where a 1 beats a 0.
% Our goal is to show that the reduction is robust in the sense
% that $c$ cannot cause \textsc{Degree} to make
% many mistakes without making many mistakes itself.

%The remainder of this section proves the main theorem.
\begin{theorem}\label{thm:regret}
For all distributions $D$ and all pairwise classifiers $c$, 
% \emph{
\begin{align}
r_{\mbox{\textsc{auc}}}(\mbox{\textsc{Degree}}(\cdot,c),D) \leq 
2r(c,\mbox{\textsc{Auc-Train}}(D)).
\label{thmineq}
\end{align}
% }
\end{theorem}
Note the quantification in the above theorem: it applies
to \emph{all} settings where Algorithms~\ref{alg:train} and~\ref{alg:wins} 
are used; in particular, $D$ may encode arbitrary dependences
between examples.
\begin{proof}
Given an unlabeled test set $\U \in \cX^n$, the joint distribution
$D$ induces a conditional distribution $D(Y_1,\ldots, Y_n \mid \U)$
over the set of label sequences $\{0,1\}^n$.  
In the remainder of the paper, let
$\Q$ denote this conditional distribution. 
We prove the theorem by fixing~$\U$, 
taking the expectation over the draw of $\U$
at the end. 

% The first step is to rewrite both sides of the inequality in 
% the theorem statement as sums over

Let $\U$ be identified with $\{1,\ldots,n\}$.
The \emph{pairwise loss} of ordering $i$ before $j$ in $\U$ is defined as
%Our goal is to rewrite both sides of \eqref{thmineq} as sums of
%pairwise regrets.  
%It will be convenient to define pairwise versions of loss and regret.
%A \emph{pairwise loss} is given by
$$l_{\Q}(i,j)= \mathbf{E}_{y^n\sim \Q} 
\frac{\I(y_i > y_j)}{\sum_{u<v} \I(y_u\not=y_v)}.$$
If $l_{\Q}(i,j)<l_{\Q}(j,i)$, the \emph{regret} $r_{\Q}(i,j)$ of
ordering $i$ before $j$ is 0;
otherwise, $r_{\Q}(i,j)=l_{\Q}(i,j)-l_{\Q}(j,i)$ and $r_{\Q}(i,j)$
is called \emph{proper}. Thus if $r_{\Q}(i,j)$ is proper, then 
$r_{\Q}(j,i)=0$.

Lemma~\ref{triangle} presented below this proof,
establishes a basic property of pairwise regrets.
It says that for any $i$, $j$, and $k$,
if $r_{\Q}(i,j)$ and $r_{\Q}(j,k)$ are proper,
$r_{\Q}(i,k) = r_{\Q}(i,j)+r_{\Q}(j,k)$. 

We can assume without loss of generality that the ordering minimizing
the AUC loss (thus having zero AUC regret) on $\U$ is
$\langle 1, 2, \ldots, n\rangle$.
It is easy to see that all regret-zero pairwise predictions must 
be consistent with the ordering, i.e.,
$r_{\Q}(i,j)=0$ for all $1\leq i<j \leq n$.
Indeed, all $r_{\Q}(i,i+1)$ must be 0; otherwise swapping $i$ and $i+1$
decreases the overall regret, contradicting the assumption
that $\langle 1, 2, \ldots, n\rangle$ is regret minimizing.
Thus all $r_{\Q}(i+1,i)$ are proper and repeated application of 
Lemma~\ref{triangle} implies that, for any $j>i$,
$r_{\Q}(j,i)$ is proper, which in turn implies that
$r_{\Q}(i,j)=0$. %, concluding the proof of the fact that all 
%regret-zero pairwise predictions must be consistent with the ordering.

Applied repeatedly, Lemma~\ref{triangle} says that for any pair $i<j$, 
the regret $r_{\Q}(j,i)$ can be decomposed as 
$r_{\Q}(j,i) = \sum_{k=i}^{j-1} r_{\Q}(k+1,k)$.
Since $U$ is fixed throughout the proof, we omit the subscript $U$ from the
produced ordering $\pi_U$ and the optimal ordering $\pi^*_U$.
Thus the AUC regret of $\pi=\pi_U$ on $\Q$ 
can be decomposed as a sum of
pairwise regrets (where $\langle U, y^n\rangle$ denotes the unlabeled sample
$U$ labeled with $y^n$):
\begin{align*}
r_{\mbox{\textsc{auc}}}(\pi,\Q) & = l(\pi,\Q) - \min_{\pi^*} l(\pi^*,\Q) \\
& = \mathbf{E}_{y^n\sim \Q} [l(\pi,\langle\U,y^n\rangle)] - \min_{\pi^*} \mathbf{E}_{y^n \sim \Q} [l(\pi^*,\langle\U,y^n\rangle)] \\
& = \mathbf{E}_{y^n\sim \Q} \frac{\sum_{i,j} \I(y_i > y_j) \pi(i,j)} {\sum_{u<v} \I(y_u\not=y_v)} 
- \min_{\pi^*} \mathbf{E}_{y^n\sim \Q} \frac{\sum_{i,j} \I(y_i > y_j) \pi^*(i,j)} {\sum_{u<v} \I(y_u\not=y_v)} \\
& = \max_{\pi^*} \mathbf{E}_{y^n\sim \Q} 
\frac{\sum_{i,j} [\I(y_i > y_j) \pi(i,j) - \I(y_i > y_j) \pi^*(i,j)]} {\sum_{u<v} \I(y_u\not=y_v)} \\
& = \sum_{i < j : \pi(j,i)=1}r_{\Q}(j,i) = \sum_{k=1}^{n-1} |\{i \leq k < j : \pi(j,i)=1\}|\cdot r_{\Q}(k+1,k).
\end{align*}
The last equality follows by repeated application of
Lemma~\ref{triangle}.
Note that 
$$
\min_{\pi^*}\mathbf{E}_U [ l(\pi^*_U,Q) ] = 
\mathbf{E}_U [ \min_{\pi^*_U} l(\pi^*_U,Q)],
$$
because for any $U$, the minimizer $\pi^*_U$ 
of $l(\pi^*_U,Q)$ is the minimizer $\pi^*$ of $\E_U[ l(\pi^*_U,Q) ]$ 
(restricted to $U$ in the last argument).

The classification regret can also be written in terms of pairwise regrets:
\begin{align*}
r(c,&\textsc{Auc-Train}(\Q)) = e(c,\textsc{Auc-Train}(\Q)) - \min_{c^*} e(c^*,\textsc{Auc-Train}(\Q)) \\
& = \max_{c^*} \mathbf{E}_{y^n\sim \Q}
\left[
\frac{\sum_{i,j}[\I(y_i>y_j)c(i,j,U) - \I(y_i>y_j)c^*(i,j,U)]}{\sum_{u<v} \I(y_u\not=y_v)}
\right]\\
& = \sum_{i < j : c(j,i,U)=1} r_{\Q}(j,i) = \sum_{k=1}^{n-1} |\{i \leq k < j : c(j,i,U)=1\}|\cdot r_{\Q}(k+1,k).
\end{align*}
%

Let $g_k$ and $f_k$ denote the coefficients with which
the term $r_{\Q}(k+1,k)$ appears in the above decompositions of
$r_{\mbox{\textsc{auc}}}(\pi,\Q)$
and $r(c,\textsc{Auc-Train}(\Q))$ respectively.
To complete the proof it suffices to show that $g_k \leq 2f_k$ for each $k$.

%Let $T$ be the tournament induced by $c$ on $\U$.
Fix $k$ and consider a bipartition of $\U$
into a set $\{1,\ldots,k\}$ of ``winners'' 
and a set $\{k+1,\ldots,n\}$ of ``losers''.
In this terminology, $g_k$ is the number of winner--loser pairs 
where 
the loser has at least as many wins as the winner,
and $f_k$ is the number of winner--loser 
pairs where the loser beats the winner (in the tournament 
induced by $c$ on $\U$). 
Theorem~\ref{thm1} below shows that $g_k \leq 2f_k$, completing this proof.
\quad
\qedblob
\end{proof}

We prove the lemma used in the proof above.

\begin{lemma}\label{triangle}
For any $i$, $j$, and $k$ in $\{1,\ldots,n\}$,
if $r_{\Q}(i,j)$ and $r_{\Q}(j,k)$ are proper,
$$r_{\Q}(i,k) = r_{\Q}(i,j)+r_{\Q}(j,k).$$
\end{lemma}
\begin{proof}
We have
\begin{align*}
r_{\Q}(i,j)&+r_{\Q}(j,k) = \mathbf{E}_{y^n\sim \Q}
\ \frac{I(y^n)}{\sum_{u<v}\I(y_u\not=y_v)},
\end{align*}
where
\begin{align*}
I(y^n) & =\I(y_i=1,y_j=0)-\I(y_i=0,y_j=1)+\I(y_j=1,y_k=0) -\I(y_j=0,y_k=1) \\
&= \I(y_i=1,y_j=0,y_k=0) +  \I(y_i=1,y_j=0,y_k=1) \\
&- \I(y_i=0,y_j=1,y_k=0)- \I(y_i=0,y_j=1,y_k=1) \\
&+ \I(y_i=0,y_j=1,y_k=0) + \I(y_i=1,y_j=1,y_k=0) \\
&- \I(y_i=0,y_j=0,y_k=1) - \I(y_i=1,y_j=0,y_k=1) \\
&= \I(y_i=1,y_k=0) - \I(y_i=0,y_k=1).
\end{align*}
Recall that
\begin{align*}
\mathbf{E}_{y^n\sim \Q} \frac{\I(y_i=1,y_k=0)}{\sum_{u<v}\I(y_u\not=y_v)} =
l_{\Q}(i,k), \quad
\mathbf{E}_{y^n\sim \Q} \frac{\I(y_i=0,y_k=1)}{\sum_{u<v}\I(y_u\not=y_v)} = 
l_{\Q}(k,i).
\end{align*}
Thus $r_{\Q}(i,j) + r_{\Q}(j,k) = l_{\Q}(i,k) - l_{\Q}(k,i) = r_{\Q}(i,k)$.
(Since $r_{\Q}(i,j) + r_{\Q}(j,k) > 0$, we have $l_{\Q}(i,k) > l_{\Q}(k,i)$ and
$r_{\Q}(i,k)$ is proper.)
\quad\qedblob
\end{proof}

\shrink{
\begin{proof}
Let $p$ be a shorthand for the restriction of $Q$ to indices $\{i, j,
k\}$, obtained by summing over all other label indices. (Thus, for
example, $p(100)$ denotes the probability that $i=1$, $j=0$, and
$k=0$, under $Q$.)  A simple algebraic manipulation verifies the
claim.
\begin{align*}
r_{\Q}(i,j)&+r_{\Q}(j,k) = \\
&\frac{p(100)+p(101)-p(010)-p(011) +p(010)+p(110)-p(001)-p(101)}{N}= \\
&\frac{p(100)+p(110)-p(001)-p(011)}{N}=r_{\Q}(i,k).
\end{align*}
where $1/N = \mathbf{E}_{y^n\sim \Q} \frac{1} {\sum_{u<v}
\I(y_u\not=y_v)} $ is a distribution-induced normalization.  
\quad\qedblob
\end{proof}
}

\bigskip
Let $T$ be a tournament and let the vertices of $T$ be arbitrarily 
partitioned into a set $W$ of ``winners'' and a set $L$ of ``losers''.
Call the triple $(T,W,L)$ a winner--loser partitioned tournament,
and denote it by~$\TT$.
%
We show that for any~$\TT$, the number of winner--loser pairs
where the loser's degree is larger than or equal to the winner's, 
is at most twice the
number of winner--loser pairs where the loser beats the winner.
Formally, define two measures:
\begin{align*}
\g(\TT) & = \suml \sumw \one(\deg(\ell)\geq \deg(w)), \\
\f(\TT) & = \suml \sumw \one(\ell \ra w).
\end{align*}

\begin{theorem} \label{thm1}
For any winner--loser partitioned tournament $\TT$,
$\g(\TT) \leq 2 \f(\TT)$.
\end{theorem}

Since the number of edges from $L$ to $W$
is equal to the total number of edges out of $L$ minus
the number of edges from $L$ to~$L$, we can rewrite
$$
\f(\TT) = \suml \sumw \one(\ell \ra w) 
= \suml \deg(\ell) - \binom{|L|}2.
$$
Both $\f(\TT)$ and $\g(\TT)$ depend only on the degrees of 
the vertices of $T$, so rather than working with a (labeled) tournament, 
a relatively complex object,
we can work with a (labeled) degree sequence.

Landau's theorem~\cite{landau}
says that there exists a tournament with outdegree sequence
$d_1 \leq d_2 \leq \cdots \leq d_n$ if and only if, for all
$1 \leq i \leq n$,
$\sum_{j=1}^i d_j \geq \sum_{j=1}^i (j-1)$,
with equality for $i=n$.

Recall that a sequence 
$\seq{a_1,\ldots,a_n}$ is \emph{majorized} by $\seq{b_1,\ldots,b_n}$
if the two sums are equal and if,
when each sequence is sorted in non-increasing order,
% (the reverse of the order we have shown), 
the prefix sums of the $b$ sequence are at least as large as 
(dominate) those of the $a$ sequence.
(For a comprehensive treatment of majorization, see~\cite{majorization}.)
% Landau's condition 
% when written as above (the usual way)
% says that the suffix sums of $\seq{d_n,\ldots,d_1}$ are 
% dominated by those of $\seq{n,\ldots,1}$,
% but given that the sums are equal, it 
% is equivalent to 
% the prefix sums of $\seq{d_n,\ldots,d_1}$ being 
% dominated by those of $\seq{n,\ldots,1}$.
% Thus Landau's condition simply says that 
Landau's condition is precisely that 
$\seq{d_1,\ldots,d_n}$ is majorized by $\seq{0,\ldots,n-1}$. % was 1..n
(With the sequences sorted in increasing order, Landau's condition
is that prefix sums of the degree sequence dominate those of the progression, 
which is the same as saying that the suffix sums of the degree sequence
are dominated by the suffix sums of the progression.)
This allows us to take advantage of well-known properties of majorization,
notably that if $A'$ is obtained by averaging together
any elements of $A$, then $A$ majorizes~$A'$.

This allows us to restate Theorem~\ref{thm1} in terms of a sequence
and majorization, rather than a tournament, but first we relax the
constraints.  First, where the original statement requires elements of
the degree sequence to be non-negative integers, we allow them to be
non-negative reals.  Second, the original statement requires that we
attach a winner/loser label to each element of the degree sequence.
Instead, we aggregate equal elements of the degree sequence, and for a
degree $d_i$ of (integral) multiplicity $m_i$, assign arbitrary
non-negative (but not necessarily integral) portions to winners and
losers: $w_i + \ell_i = m_i$.  

Let $\DD=(D,W,L)$ be such a generalized
``winner--loser labeled compressed sequence''.
Note that the majorization condition
applies only to the values $\{d_i,m_i\}$, not the labeling.  
The definitions of $f$ and $g$ above are easily extended
to this broader domain:
$g(\DD) = \sum_{i} \sum_{j \leq i} l_i w_j$,
$f(\DD) = \sum_i l_i d_i - \binom{\sum_i l_i}2$,
where we define $\tbinom{x}2 = x(x-1)/2$ for all~$x$ 
(not just integers).
If we prove $g \leq 2f$ over this larger domain, 
the inequality holds in particular
for plain winner--loser labeled degree sequences
(the case where all weights happen to be integral).
That is, Theorem~\ref{thm3}, below, implies Theorem~\ref{thm1}.

\begin{theorem} \label{thm3}
For any winner--loser labeled compressed sequence $\DD=(D,W,L)$
where $D$ is majorized by $\seq{0,\ldots,n-1}$, % was 1..n
$\g(\DD) \leq 2 \f(\DD)$.
\end{theorem}
%Note that this implies theorem \ref{thm1} because it is about the same
%maximum over a smaller set of possibilities.

\begin{proof}
We begin with an outline of the proof. 
Define a compressed sequence $\DD$ as being \emph{canonical}
if it consists of at most three degrees:
a smallest degree $d_1$ having only losers ($w_1=0$),
a middle degree $d_2$ potentially with both winners and losers 
($w_2, \ell_2 \geq 0$),
and a largest degree $d_3$ having only winners ($\ell_3=0$).
We first establish that any canonical sequence has
$\g(\DD)-2\f(\DD) \leq 0$. 
We then show how to transform \emph{any} degree sequence
to a canonical one with a larger (or equal) value of $\g-2\f$,
which completes the argument. 

We first show that a canonical sequence $\DD$ has $\g - 2\f \leq 0$.
For the canonical configuration,
$\g = w_2 \ell_2$ and
$\f = \ell_1 d_1 + \ell_2 d_2 - \binom{\ell_1+\ell_2}{2}$,
and hence our goal is to show that
\begin{equation}
\label{e:g1}
 \ell_1 d_1 +  \ell_2 d_2 \geq  (\ell_1 + \ell_2)(\ell_1 + \ell_2 -1)/2 + w_2
 \ell_2/2
\end{equation}

By Landau's condition applied to $\ell_1$ and $\ell_1+w_2+\ell_2$, 
we have the following two relations:
\begin{equation}
\label{e:d1}
\ell_1 d_1  \geq  \binom{\ell_1}{2}
\end{equation}
and 
\begin{equation}
\label{e:d2} 
\ell_1 d_1 + (\ell_2 + w_2 ) d_2 \geq \binom{\ell_1 + w_2 + \ell_2 }{2}.
\end{equation}
% Observe that $\ell_1$ and $\ell_1 + \ell_2 + w_2$ are both integers.

Multiplying (\ref{e:d1}) by $ w_2/(\ell_2+ w_2)$ and (\ref{e:d2}) 
by $ \ell_2/(\ell_2 + w_2)$ and adding them, we obtain that
\begin{align} 
\ell_1 d_1 +  \ell_2 d_2 
\geq 
\frac{1}{\ell_2+w_2} \left( w_2 \binom{\ell_1}{2} + \ell_2  
 \binom{\ell_1 + \ell_2 + w_2}{2}  \right) .
 \label{e:d3}
\end{align} 
A simple calculation shows that the right side of inequality \eqref{e:d3} 
is exactly equal to the right hand side of (\ref{e:g1}). 
This proves that $\g \leq 2\f$ for a canonical sequence.

If a sequence is not canonical then there are two consecutive degrees
$\da$ and $\db$ ($j=i+1$) such that one of the
cases 1a, 1b, or 2 (described below) holds.
In each case we apply a transformation producing 
 from the degree sequence $\DD$ a new degree sequence~$\DD'$, where:
\begin{itemize}
\item
the total weight of winners in $\DD'$ is equal to that of $\DD$;
similarly for losers, and thus for the total weight;
furthermore, the total weight on each degree remains integral;
%\item
%the same is true for losers (and thus for the total weight);
\item
$\DD'$ maintains the majorization needed for Landau's theorem;
\item
the value of $\g-2\f$ is at least as large for $\DD'$ as for~$\DD$; and
\item
either
the number of nonzero values $w_i$ and $\ell_i$
or the number of distinct degrees $d_i$
is strictly smaller for $\DD'$ than for $\DD$,
and the other is no larger for $\DD'$ than for $\DD$.
%(for Transformation~2, this may first require application
%of another transformation).
\end{itemize}
We first sketch the cases and then detail the transformations.

\begin{description}
\item[Case 1a] 
$\da$ has only winners ($\la=0$).
\\ Apply Transformation~1a, combining the two degrees into one.
\item[Case 1b]
$\db$ has only losers ($\wb=0$).
\\ Apply Transformation~1b, combining the two degrees into one.
\item[Case 2]
% There are consecutive degrees $\da < \db$ with 
All of $\wa$, $\la$, $\wb$ and $\lb$ are nonzero.
\\ Apply Transformation~2, leaving the degrees the same but transforming
the weights so that one of them is equal to 0 and one of the preceding
cases applies, or the weights obey an equality allowing application of
Transformation~3, which combines the two degrees into one.
\end{description}

% \begin{remark}
Either there is some pair $i,j$ to which one of the cases applies,
or the sequence is canonical.
% \end{remark}
% \begin{proof}
We argue this by showing that
% We will show that 
if there is no pair $i,j$ for which Cases 1a or 1b apply, 
then either the sequence is canonical, 
or there is a pair to which Case~2 applies.
First, note that for any $i\neq n$, 
$l_i>0$ (else Case~1a applies to $i,i+1$)
and for any $i\neq 1$, $w_i >0$ (else Case~1b applies to $i-1,i$).
In particular, for any $1<i<n$, both $l_i,w_i>0$.
If $n\geq 4$ this implies immediately that Case~2 applies to the pair~$2,3$. 
If $n=1$, $\DD$ is automatically canonical. 
If $n=2$ and $l_2=0$ or $w_1=0$ then $\DD$ is canonical, 
while if both $l_2,w_1>0$ 
we may apply Case~2
(since, as we first argued, $l_1,w_2>0$).
Finally, if $n=3$, we know $l_1,l_2,w_2,w_3>0$.
If $w_1 = l_3 = 0$ then $\DD$ is canonical, 
and otherwise Case~2 applies.
% \end{proof}

\noindent
{\bf Transformation 1a:}\quad
In Case~1a, where
$\da$ has only winners,
change $\DD$ to a new sequence $\DD'$ by 
%
replacing the pair $(\da,\wa,0)$, $(\db,\wb,\lb)$
by their ``average'': the single degree $(\dx,\wx,\lx)$,
where 
\begin{align*}
\wx &= \wa+\wb , \quad
\lx = \lb, \quad
\dx = \frac{\wa \da + (\wb+\lb) \db}{\wa+\wb+\lb}  .
\end{align*}

\ignore{
As in Case~0, $\DD$ still fits the conditions on a degree sequence:
the total weight on each degree remains integral, 
and the (weighted) sequence is still 
majorized by $\seq{0,\ldots,n-1}$.  % was 1..n
The number of distinct degrees is reduced by one.
}

The stated conditions on a transformation are easily checked.
The total weight of winners is clearly preserved,
as is the total weight of losers and the total degree (out-edges).
Summing weights preserves integrality.
% The number of nonzero weights is reduced by one. 
% -- unless w_j was already 0 (i.e., only w_i and l_j >0).
The number of distinct degrees is reduced by one,
and the number of nonzero weights may be decreased by one or
may remain unchanged.
The Landau majorization condition holds because 
$\DD'$, as an averaging of $\DD$, is majorized by it, 
and majorization is transitive.
% averaging preserves majorization.
The only non-trivial condition is the non-decrease in $\g-2\f$.
The number of loser--winner pairs where the loser outranks the winner
remains the same, so $g(\DD) = g(\DD')$. 
Also, $f$ depends only on the total weight of losers (which is unchanged)
and on the average degree of losers. 
This average degree would be unchanged if $\wa$ were~$0$; 
since $\wa \geq 0$, the average degree may decrease.
Thus $f(\DD) \geq f(\DD')$,
and $(g-2f)(\DD) \leq (g-2f)(\DD')$, as desired. 

\noindent
{\bf Transformation 1b:}\quad 
Symmetrically to Transformation~1a,
obtain $\DD'$ by
replacing the pair of labeled weighted degrees $(\da,\wa,\la)$ and $(\db,0,\lb)$
with a single one $(\dx,\wx,\lx)$,
where $\wx = \wa$, $\lx = \la+\lb$, and 
$\dx = [(\la+\wa) \da + \lb \db]/(\la+\wa+\lb)$.

\ignore{
replacing the pair $(\da,\wa,0)$, $(\db,\wb,\lb)$, 
with a single degree $(\dx,\wx,\lx)$,
where 
\begin{align*}
\wx &= \wa+\wb , \quad
\lx = \lb, \quad
\dx = \frac{(\wa) \da + (\wb+\lb) \db}{\wa+\wb+\lb}  .
\end{align*}
Again, going from $\DD$ to $\DD'$, the value of $g$ is increased,
while that of $f$ is decreased, so $g-2f$ increases.
Again, the number of distinct degrees is reduced by one.
}

\noindent
{\bf Transformation 2:}\quad 
Where $\wa$, $\la$, $\wb$ and $\lb$ are all nonzero, 
we begin with one case, which leads to one other.
In the usual case, we transform $\DD$ to $\DD'$ by
replacing the pair $(\da,\wa,\la)$, $(\db,\wb,\lb)$ with
$(\da,\wa+x,\la-x)$, $(\db,\wb-x,\lb+x)$,
for some value of $x$ (positive or negative) to be determined.
This affects only the labeling, not the weighted degree sequence itself,
and is therefore legitimate
% as long as $x \leq \wa$, $x \geq -\la$, $x \geq -\wb$, and $x \leq \lb$.
as long as the four quantities
$\wa+x$, $\la-x$, $\wb-x$ and $\lb+x$ are all non-negative.

Defining $\Delta = (g-2f)(\DD')-(g-2f)(\DD)$, 
we wish to choose $x$ to make $\Delta > 0$.
\begin{align*}
\Delta &= 
       \Big\{ \big[(\lb+x)(\wa+x+\wb-x)+(\la-x)(\wa+x)\big] 
            - \big[\lb (\wa+\wb)+\la \wa \big] \Big\}
 \\ & \qquad \quad
   - 2 \Big\{ \big[(\la-x) \da + (\lb+x) \db\big] 
            - \big[\la \da + \lb \db\big] \Big\}
 \\ &=
 x (\wb + \la - 2 (\db - \da) -x) 
 =
 x (a-x),
\end{align*}
where $a = \wb+\la-2(\db-\da)$.
This is a simple quadratic expression with negative coefficient on $x^2$,
so its value increases monotonically as $x$ is varied from $0$ to $a/2$,
where the maximum is obtained.
(Note that $a$ may be negative.)
If $a=0$ then 
% this transformation makes no change, 
% and instead we use Transformation~3, below.
we do not use this transformation but Transformation~3, below.
Otherwise, vary $x$ from $0$ to $a/2$ stopping when $x$ reaches $a/2$
or when any of
$\wa+x$, $\la-x$, $\wb-x$ and $\lb+x$ becomes~$0$. 
Call this value~$\xstar$, and use it to define the transformation.

If any of 
$\wa+x$, $\la-x$, $\wb-x$ and $\lb+x$ is 0
then the number of nonzero weights is decreased
(while the number of distinct degrees is unchanged).
Otherwise, $\xstar=a/2$. 
In that case, the new $\DD'$ has $a=0$
% (because another application of the same procedure would give $\xstar=0$).
(the optimal ``weight shift'' has already been performed).
With $a=0$ we apply Transformation~3,
which reduces the number of nonzero weights.

\noindent
{\bf Transformation 3:}\quad
Similar to Cases 1a and 1b, transform $\DD$ to $\DD'$ by 
% averaging the degrees $\da$ and~$\db$, adding the corresponding labels weights
replacing the pair $(\da,\wa,\la)$, $(\db,\wb,\lb)$ 
with a single degree $(\dx,\wx,\lx)$ that is their weighted average,
\begin{align*}
\wx &= \wa+\wb , \quad
\lx = \la+\lb, \quad
\dx = \frac{(\wa+\la) \da + (\wb+\lb) \db}{\wa+\la+\wb+\lb}  .
\end{align*}
This gives
\begin{align*}
\Delta & =
 (g-2f)(\DD')-(g-2f)(\DD)
 \\ &=
 (\la \wb) - 2 ( \la \dx + \lb \dx - \la \da - \lb \db )
 \\ &=
 \la \wb + 
 \frac
 {2(\db-\da)(\wa \lb - \wb \la)} 
 {\wa+\la+\wb+\lb} .
\end{align*}
We apply this transformation only in the case where 
Transformation~2 fails to give any improvement
because its ``$a$'' expression
is equal to~0, i.e., $\db-\da=(\wb+\la)/2$.
% (More detail on the rules for applying the transformations follows, below.)
Making the corresponding substitution gives
\begin{align*}
 % (\wa+\la+\wb+\lb) \cdot \Delta 
 %  &=
 % \la \wb (\wa+\la+\wb+\lb) + 
 % {(\wa+\lb)(\wa \lb - \wb \la)} 
 % \\ &=
 \Delta 
  &=
 \la \wb +
 \frac
 {(\wb+\la)(\wa \lb - \wb \la)}
 {\wa+\la+\wb+\lb} 
 \\ &=
 \frac
 { (\la \wb)(\lb+\wa) + (\lb \wa)(\la+\wb) }
 {\wa+\la+\wb+\lb} 
  > 0.
\end{align*}
This reduces the number of distinct degrees by one,
without increasing the number of nonzero weights.

Concluding the argument, we have shown that any non-canonical configuration
$\DD$ can be replaced by a configuration with 
% fewer nonzero weights and 
a strictly smaller total of distinct degrees and nonzero weights,
and at least as large a value of $\g-2\f$. 
% Since in $\DD$ each total weight $w_i+\ell_i$ is integral,
% there were at most $n+2$ nonzero weights originally 
% (the $+2$ coming from our special highest and lowest degrees),
% and a canonical configuration $\DDstar$ is reached after at most $n-1$
% transformations.
Since $\DD$ had at most 
$n$ distinct degrees and $2n$ nonzero weights originally, 
a canonical configuration $\DDstar$ is reached after at most $3n-1$
transformations.
(All that is important is that the number of transformations is finite: 
that a canonical configuration is eventually reached.)
Then, $(\g-2\f)(\DD) \leq (\g-2\f)(\DDstar) \leq 0$.
\quad\qedblob
\end{proof}

A further generalization of Theorem~\ref{thm3} may be found in~\cite{BCStech}.

\shrink{
We used the following lemma, due to Landau~\cite{landau}.
\begin{lemma}\label{land}
There exists a tournament with outdegree sequence
$\deg(1) \leq \deg(2) \leq \cdots \leq \deg(n)$ if and only if, for all
$1 \leq i \leq n$,
$\sum_{j=1}^i \deg(j) \geq \sum_{j=1}^i (j-1)$,
with equality for $i=n$.
\end{lemma}
}

\section{An Upper Bound for Minimum Feedback Arc Set}\label{fas}
This section shows an analog of Theorem~\ref{thm1} 
for an optimal solution to the feedback arc set problem.
(The decomposition argument in
Theorem~\ref{thm:regret} is algorithm-independent and applies here as well.)
For a tournament $T$ and an ordering $\pi$, a \emph{back edge} 
is an edge $i\ra j$ in $T$ such that $j$ is ordered before $i$ in $\pi$.
Let $\back(T,\pi)$ denote the number of back edges induced by $\pi$ in $T$.

For a winner--loser partitioned tournament $\TT = (T,W,L)$
and any minimum feedback arc set ordering $\pi$ of $T$,
let $g'(\TT,\pi)$ be the number of winner--loser pairs where 
the loser comes before the winner in $\pi$, and as before let 
$$\f(\TT)=\suml \sumw \one(\ell \ra w)$$
be the number of 
winner--loser pairs where the loser beats the winner.

\begin{theorem} \label{thm4}
For any winner--loser partitioned tournament $\TT = (T,W,L)$ and any minimum 
feedback arc set ordering $\pi$ of $\TT$,
$g'(\TT,\pi)\leq 2\f(\TT)$.
\end{theorem}
\begin{proof}
Let $k_w$ be the smallest possible number of back edges in the subtournament
induced by $W$.  Define $k_l$ similarly for the subtournament induced by $L$.
Let $k_w^{\pi}$ and $k_l^{\pi}$ be the number of back edges in $\pi$ that 
go from $W$ to $W$ and from $L$ to $L$, respectively.
Denote the number of remaining (i.e., winner--loser or loser--winner) 
back edges in $\pi$ by $k_o^{\pi}$.

Consider another ordering $\sigma$ where all winners are ordered
before all losers, and both the winners and the losers are ordered
optimally among themselves, i.e., with $k_w$ and $k_l$ back edges
respectively.  The number of back edges in $\sigma$ is
$\back(\TT,\sigma) = k_w + k_l + \f(\TT)$.  But we also have
$\back(\TT,\sigma) \geq \back(\TT,\pi)$ since $\pi$ minimizes the
number of back edges, and thus $k_w + k_l + \f(\TT) \geq k_w^{\pi} +
k_l^{\pi} + k_o^{\pi}$.  Since $k_w \leq k_w^{\pi}$ and $k_l \leq
k_l^{\pi}$ by definition of $k_w$ and $k_l$, we have $\f(\TT) \geq
k_o^{\pi}$.

Consider any winner--loser pair with the loser ordered before the
winner. If $w\ra l$ is the edge, it is a back edge in $\pi$ and thus
is counted by $k_o^{\pi}$.  If $l\ra w$ is the edge instead, it is
counted by $\f(\TT)$.  Thus $g'(\TT,\pi)$ is at most $k_o^{\pi} +
\f(\TT)$.  Since $\f(\TT) \geq k_o^{\pi}$, this number is never more
than $2\f(\TT)$, which implies $g'(\TT,\pi) \leq 2 \f(\TT)$. \quad \qedblob
\end{proof}

\bigskip\noindent
The proof above immediately shows that for any $\TT$ and any
ordering $\pi_{\alpha}$ of $\TT$ with at most 
$(1+\alpha)\cdot\opt(\TT)$ back edges,
$g'(\TT,\pi_{\alpha})\leq (2+\alpha)\f(\TT) + \alpha(k_w + k_l)$,
where $\opt(\TT)$ is the minimum number of back edges in $\TT$, 
and $k_w$ and $k_l$ are as in the proof above.
Thus, a FAS approximation does not generally guarantee
that if $f$ is 0, then so is $g'$ 
(a guarantee provided by \textsc{Degree} and FAS).  
For example, $\TT$ may make correct statements about all winner--loser 
pairs while inducing a non-transitive tournament on the winners or the losers,
so an approximation that does not know the winner--loser labeling
can incur a non-zero number of mistakes.

\section{Lower Bounds}\label{lower}
We first show that Theorem~\ref{thm1} is best possible: 
the \textsc{Degree} ranking really can make twice as many 
mistakes as the adversary.
% We start with a lower bound for the algorithm that orders by the number
% of wins.  
Recall that $f$ denotes the number of winner--loser
pairs where the loser beats the winner, and $g$ the number of winner--loser
pairs where the loser outranks the winner.
The example below generates % shows that there exists 
an infinite family
of tournaments with $g = 2f$.

\noindent
{\bf Example 1.}\quad
With $n$ odd,
let every vertex have degree~$(n-1)/2$;
note that the degree sequence $\seq{\frac{n-1}2, \ldots, \frac{n-1}2}$
does indeed respect Landau's condition, so it is realizable as a tournament.
Label $(n-1)/2$ of the vertices as winners and $(n+1)/2$ as losers.
With ties broken against us, all winners are ordered after all losers.
This gives 
$f = \frac{n+1}2 \cdot \frac{n-1}2 - \binom{(n+1)/2}2 = (n+1)(n-1)/8$,
while $g = \frac{n+1}2 \cdot \frac{n-1}2 = (n+1)(n-1)/4 = 2f$.
(A similar example gives a lower bound of $2-O(1/n)$ 
with ties broken optimally for the algorithm.)
\quad\qedblob

In a subsequent paper, Ailon and Mohri~\cite{ailon-mehryar} give a
simple algorithm-independent example showing that no deterministic algorithm
can achieve a constant factor of less than 2 on the regret ratio.  The
example puts all the probability mass on a single three element
subset.  The induced tournament is a directed 3-cycle, and the bipartition is
chosen adversarily depending on the ordering output by the algorithm.
By symmetry, there are only two different orderings (clockwise and
counterclockwise).  In both cases, the adversary can make the
algorithm pay for both mixed pairs while paying for only one
misordering.  This example implies that Theorem~\ref{thm4} is also 
best possible.\footnote{ The preliminary version of this paper
contained a construction of a family of tournaments, for
which an optimal solution to the feedback arc set problem gives $g \geq
(2-\epsilon)f$, for any $\epsilon>0$.  We decided to omit the
construction since it is superseded by the above lower bound example in
\cite{ailon-mehryar}.  }

\shrink{
Theorem~\ref{thm4} is also essentially best possible.
The next construction gives an infinite family of tournaments
for which an optimal solution to the feedback arc set problem has
$g \geq (2-\epsilon)f$, for any $\epsilon>0$.
% That is, even if we could solve the NP-hard feedback arc set problem, 
% it would not give any advantage.

\noindent
{\bf Example 2.}\quad 
Set $\delta = \frac{\epsilon}{1-\epsilon}$, and let
the set of vertices be partitioned into three components, 
$V_1$, $V_2$, and $V_3$, with
$|V_1| = \delta n^2$, $|V_2| = 2n^2$, and $|V_3|=n$, for a sufficiently large
$n$.  The vertices in $V_1 \cup V_2$ are the winners,
the vertices in $V_3$ are the losers. 

The edges within each of the three components form acyclic tournaments.
The cross-component edges are defined as follows:
All edges between $V_3$ and $V_1$ point from $V_3$ to $V_1$, and 
all edges between $V_1$ and $V_2$ point from $V_1$ to $V_2$.
To define the edges between $V_2$ and $V_3$,
divide $V_2$ into $2n$ consecutive blocks $B_1,\ldots,B_{2n}$ of $n$ 
vertices each, such that edges point from $B_i$ to $B_j$ where 
$1\leq i<j\leq 2n$.
If $i$ is odd, all edges from $B_i$ point to $V_3$; otherwise 
all edges from $V_3$ point to $B_i$.

We have $f = (1 + \delta) n^3$.  
What is the value of $g$
induced by an ordering minimizing the number of back edges?
Any such ordering must put $V_1$ before $V_2$; otherwise we would 
have $\Omega(n^4)$ back edges while an optimal ordering does not need
to 
have more than $O(n^3)$ such edges. Now, the tournament induced by $V_2\cup V_3$
has $n^3$ edge-disjoint cycles of length 3 since there are $n^2$
such cycles for every pair of blocks in $V_2$ 
(and there are $n$ disjoint pairs). There has to be at least one 
back edge for every such cycle, so any ordering 
must have at least $n^3$ back edges.  The ordering that puts $V_3$ before
$V_2$ is thus optimal since it
has exactly $n^3$ back edges.  Thus the ordering $\{V_3,V_1,V_2\}$ minimizes
the number of back edges.  This ordering has
$(2+\delta)n^3$ pairs where the loser is ordered before the winner, implying
the bound $g \geq (2-\frac{\delta}{1+\delta})f = (2-\epsilon)f$.
\quad\qedblob
}

\section{Generalization to Multipartite Ranking}\label{multi}
The result in Section~\ref{regret} can be extended to the case when examples 
belong to more than two classes.  In the extreme case, 
all examples can have different labels.  The labels typically form 
an ordered set, arising naturally in applications where 
labels represent discretized ratings (e.g., survey results can be graded
from `strongly agree' to `strongly disagree', search results can be graded from
`most relevant' to `least relevant').

A natural way of extending the definition of ranking loss to account
for the order in the values, is to weigh the loss of putting an example with
label $y_j$ before an example with label $y_i < y_j$ 
by the difference $y_j-y_i$.
Formally, the generalized AUC loss of an ordering $\pi$ 
on a set $S = (1,y_1),\ldots,
(n,y_n)$ is defined as 
$$
l(\pi,S) = \frac{\sum_{i\not=j}\pi(i,j,\{1,\ldots,n\}) (y_i - y_j)_{+}}{\sum_{i<j}|y_i-y_j|},
$$
where we use the operator $(A)_{+}=A\cdot \I(A>0)$.

As in the bipartite case, let $\Q$ denote the distribution of label 
sequences of the set $\{1,\ldots,n\}$.
Then the generalized loss of ordering $i$ before $j$ is
$$
l_{\Q}(i,j) = \mathbf{E}_{y^n\sim \Q} \frac{(y_i - y_j)_{+}}{\sum_{u<v}|y_u - y_v|}.
$$
Regrets are defined as before.  Recall that 
$r_{\Q}(i,j)$ is \emph{proper} if $l_{\Q}(i,j)-l_{\Q}(j,i) \geq 0$.

The lemma below extends Lemma~\ref{triangle} to multiple labels.

\begin{lemma}\label{triangle-l}
For any $i$, $j$, and $k$ in $\{1,\ldots,n\}$,
if $r_{\Q}(i,j)$ and $r_{\Q}(j,k)$ are proper,
$$r_{\Q}(i,j)+r_{\Q}(j,k) = r_{\Q}(i,k).$$
\end{lemma}
\begin{proof}
Consider any label assignment $y^n = y_1\ldots y_n$ and 
let $Z(y^n)=\frac{Q(y^n)}{\sum_{u<v}|y_u - y_v|}$.

A simple case analysis shows that $y^n$ contributes equally to both sides
of the lemma statement.  Indeed,
if $y_i \leq y_j \leq y_k$, the contribution is zero to either side.
If $y_i \geq y_j \geq y_k$, it contributes 
$Z(y^n)((y_i-y_j) + (y_j-y_k))$ to
$r_{\Q}(i,j)+r_{\Q}(j,k)$ and $Z(y^n)(y_i-y_k)$ to $r_{\Q}(i,k)$, so
the contributions are equal. It remains to consider two cases. 

{\bf Case 1}, $y_i \leq y_j$ and $y_j \geq y_k$.
The contribution of $y^n$ to the left side is
$Z(y^n)[-(y_j-y_i)+(y_j-y_k)]$.
If $y_i \leq y_k$, it adds $Z(y^n)(y_k-y_i)$ to $l_{\Q}(k,i)$; otherwise,
it adds $Z(y^n)(y_i-y_k)$ to $l_{\Q}(i,k)$.  In both cases,
its contribution to the right side, $l_{\Q}(i,k)-l_{\Q}(k,i)$, is
$Z(y^n)(y_i-y_k)$, and so the contributions are equal.

{\bf Case 2}, $y_i \geq y_j$ and $y_j \leq y_k$.  Similarly to Case 1,
$y^n$ donates $Z(y^n)[(y_i-y_j)-(y_k-y_j)]$ 
to the left side, and $Z(y^n)(y_i-y_k)$ to the right side, completing the proof.
\quad\qedblob
\end{proof}

The proof of Theorem~\ref{thm:regret} 
carries through without modifications, 
using the generalized definition of losses and 
regrets and Lemma~\ref{triangle-l} in place of Lemma~\ref{triangle}.

\section{Relation to Generalization Bounds and Other Work}
A number of papers analyze generalization properties of ranking
algorithms (see, e.g., \protect\cite{freund,shivani-uniform,stability,lugosi,
rudin}).  These papers analyze ranking directly by
estimating the rate of convergence of empirical estimates of the ranking
loss to its expectation.  The bounds typically involve
some complexity parameter of the class
of functions searched by the algorithms (which serves as a regularizer),
and some additional quantities considered relevant for the analysis.
%It is assumed that examples are drawn independently from some fixed
%distribution, and that their labels are deterministic given features.
The examples are assumed to be drawn independently from some fixed
distribution. % and the labels are often assumed to be deterministic.

The type of results in this paper is different.
We bound the realized AUC performance in terms of the realized classification
performance, thus {transferring} performance from classification to ranking.  
Since the analysis is relative, it does not have to rely on any
assumptions about the way the world produces data.  In particular,
the bounds apply when there are arbitrary high-order dependencies
between examples, which is important in a number of
applications where ranking is of interest.

A generalization result for the induced classification problem implies,
via the reduction, a generalization result for the AUC problem.
In situations where rankings are drawn iid from 
some base distribution $D$, the induced independent sample 
from $\textsc{Auc-Train}(D)$ can be formed by
first drawing a ranking from $D$ and then picking a mixed pair at random.
Repeating this process many times produces an iid sample set for 
which standard rate of convergence analysis bounds hypothesis class regret.
%(This approach is practical only when training data is abundant.)
%We note that when all mixed pairs from a fixed ranking are used for learning,
%the resulting examples are certainly not independent.

\shrink{
Any generalization result for the induced
classification problem implies, via the reduction,
a generalization result for the AUC problem.

For example, Cl\'{e}men\c{c}on, Lugosi, and Vayatis~\cite{lugosi}
derive bounds on the performance of empirical risk minimization
for the classification problem of ranking two instances
(under the assumption that instances are independent
and identically distributed).
By composing these bounds with our result, one can
derive bounds for ranking $n$ independent instances (instead of just two),
without introducing a dependence on $n$.

Finally, it is important to emphasize that the
analysis is independent of how the classifier is learned.
This means that the complexity of the test portion does not have
to be quadratic in $n$.
}

Cortes and Mohri~\cite{cortes-mohri} analyzed
the relationship between the AUC and the error rate {on the
same classification problem}, treating the two as different loss
functions.  They derived expressions for the expected value and the
standard deviation of the AUC over all classifications with a fixed
number of errors, under the assumption that all such classifications
are equiprobable (i.e., the classifier is as likely to err on any one
example as on any other).
% These expressions are of little relevance to the results presented here.
There is no connection with the present work.

\shrink{
\section{Practicality and Relation to Other Work}\label{last}
The reduction analysis is representation independent, which means that 
it works for any representation.  Naturally, some representations 
are more computationally efficient than others.
If, for example, $c(x_i,x_j) =
\I(s(x_i) \geq s(x_j))$ for some learned scoring 
function $s: X\rightarrow [0,1]$,
the complexity of test-time evaluation is linear rather than quadratic 
in the number of elements.  Note that $s$ is not trained as a simple regressor,
because what we want to optimize is the pairwise ordering of elements.
If $c$ is a scoring function, the tournament it labels is transitive 
and the reduction just outputs the linear ordering consistent with 
the tournament, so the corresponding regret transform is $r \mapsto r$.
 
It would be interesting to consider other efficient representations 
describing more general classes of preference functions, as well as extend
the results to partial tournaments and other ranking loss functions.
\shrink{---even though the optimal 
preference function is a scoring function, it does not mean that it is always
desirable to restrict the search to the set of scoring functions. 
Often rankings are required from limited data, so}

Cohen, Schapire, and Singer~\cite{cohen}, similarly, use a two-stage
approach to ranking:  They first learn a preference function
that takes a pair of instances and returns a score predicting how certain
it is that the first instance should be ranked before the second.
The learned function is then evaluated on all pairs of instances in
the test set and an ordering approximating
%~\footnote{
%The approximation algorithm they use orders by the weighted sum of wins 
%minus the weighted sum of loses, in the induced tournament obtained 
%by eliminated instances that have already been ordered.} 
the largest possible $l_1$ agreement 
with the predictions is created, using a variant of the degree-based algorithm.
%(which orders by the weighted sum of wins
%minus the weighted sum of loses in the induced tournament obtained
%by eliminated all instances that have already been ordered).
One of the results they show is that 
the agreement achieved by an optimal feedback arc set ordering
is at most twice the agreement obtained by their algorithm.
To translate this result into the language of losses, let $\textsc{Mfa}$
be the AUC
loss of the minimum feedback arc set ordering 
and $\textsc{Approx}$ be the AUC loss of the approximation. 
Then the result says that $1-\textsc{Approx} \geq \tfrac{1}{2}(1-\textsc{Mfa})$ 
or
$\textsc{Approx} \leq \tfrac{1}{2} + \textsc{Mfa}/2$.  
The result is difficult to compare with the results given here,
as the settings are different.
% The settings are different, making the results given here difficult to compare.
A very rough comparison requires specializations and 
yields a bound that is weaker than ours:
%Applying the result in our setting requires specializations and 
%yields bounds that are weaker than ours. 
As we have seen
in Section~\ref{fas}, $\textsc{Mfa} \leq 2\,\textsc{Bin}$, where $\textsc{Bin}$
is the loss of the pairwise predictor, so the result of \cite{cohen} 
roughly says that $\textsc{Approx} \leq \tfrac{1}{2} + \textsc{Bin}$, while we
show that $\textsc{Approx} \leq 2\,\textsc{Bin}$ (modulo the slight
differences in the approximation algorithm and the binary problem).

\shrink{
Applying the result in our setting requires specializations and yields bounds
that are weaker than ours.
(Our result says that $\textsc{Approx} \leq 2\,\textsc{Bin}$, where \textsc{Bin}
is the loss of the pairwise predictor. As we have seen 
in Section~\ref{fas}, $\textsc{Mfa} \leq 2\,\textsc{Bin}$, thus 
%because we measure the distance to a true 
%underlying ordering corrupted by an adversary rather than $\textsc{Mfa}$. 
}

Cortes and Mohri~\cite{cortes-mohri} analyzed
the relationship between the AUC and the error rate {on the
same classification problem}, treating the two as different loss
functions.  They derived expressions for the expected value and the
standard deviation of the AUC over all classifications with a fixed
number of errors, under the assumption that all such classifications
are equiprobable (i.e., the classifier is as likely to err on any one
example as on any other).  
% These expressions are of little relevance to the results presented here.
There is no direct connection with the present work.
}

\subsubsection*{Acknowledgement}
We would like to thank COLT reviewers for their comments and 
suggestions, and Nir Ailon and Mehryar Mohri for helpful discussions.

\bibliographystyle{splncs}
\begin{thebibliography}{BDHM92}

\bibitem[AHR05]{shivani-uniform}
S.~Agarwal, S.~Har-Peled, and D.~Roth.
\newblock A uniform convergence bound for the area under the ROC curve,
\newblock {\em Proceedings of the 10th International Workshop on Artificial
Intelligence and Statistics}, 2005.

\bibitem[AN05]{stability}
S.~Agarwal, P.~Niyogi.
\newblock Stability and generalization of bipartite ranking algorithms,
\newblock {\em Proceedings of the Eighteenth Annual Conference
on Computational Learning Theory} (COLT), 32--47, 2005.

\bibitem[AM07]{ailon-mehryar}
N.~Ailon and M.~Mohri.
\newblock An Efficient Reduction of Ranking to Classification,
\newblock {\em New York University Technical Report} TR-2007-903, 2007.

\bibitem[A06]{alon}
N.~Alon.
\newblock Ranking tournaments, 
\newblock {\em SIAM Journal on Discrete Mathematics} {\bf 20}: 137--142, 2006.

\bibitem[BCS06]{BCStech}
N.~Bansal, D.~Coppersmith, and G.B.~Sorkin.
\newblock A winner--loser labeled tournament has at most twice as many
outdegree misrankings as pair misrankings,
\newblock {\em IBM Research Report RC24107}, Nov.\ 2006.

\bibitem[CLV05]{lugosi}
S. Cl\'{e}men\c{c}on, G. Lugosi, N. Vayatis.
\newblock Ranking and scoring using empirical risk minimization,
\newblock {\em Proceedings of the Eighteenth Annual Conference
on Computational Learning Theory} (COLT), 1--15, 2005.

\bibitem[CSS99]{cohen}
W.~Cohen, R.~Schapire, and Y.~Singer.
\newblock Learning to order things,
\newblock {\em Journal of Artificial Intelligence Research} {\bf 10}: 243--270, 1999.

\bibitem[CFR06]{rudra}
D.~Coppersmith, L.~Fleischer and A.~Rudra. 
\newblock Ordering by weighted number of wins gives a good ranking 
for weighted tournaments. 
\newblock {\em Proceeding of the 17th Annual Symposium 
on Discrete Algorithms} (SODA), 776--782, 2006.

\bibitem[CM04]{cortes-mohri}
C. Cortes and M. Mohri.
\newblock AUC optimization versus error rate minimization,
\newblock {\em Advances in Neural Information Processing Systems} 
(NIPS), 2004.

\bibitem[FIS+03]{freund}
Y.~Freund, R.~Iyer, R.~Schapire, and Y.~Singer.
\newblock An efficient boosting algorithm for combining preferences,
\newblock {\em J. of Machine Learning Research} {\bf 4}: 933--969, 2003.

\bibitem[Lan53]{landau}
H. Landau.
\newblock On dominance relations and the structure of animal societies: III. The condition for a score structure, 
\newblock {\em Bull. Math. Biophys.}, {\bf 15}: 143--148, 1953.

\bibitem[LZ05]{probing}
J.~Langford and B.~Zadrozny.
\newblock Estimating Class Membership Probabilities Using Classifier Learners,
\newblock {\em Proceedings of the 10th International Workshop on Artificial
Intelligence and Statistics}, 2005.

\bibitem[MO79]{majorization}
A. Marshall and I. Olkin.
\newblock {\em Inequalities: Theory of majorization and its applications},
\newblock Mathematics in Science and Engineering, 143, New York,
1979.

\bibitem[RCM+05]{rudin}
C.~Rudin, C.~Cortes, M.~Mohri, and R.~Schapire.
\newblock Margin-based ranking meets Boosting in the middle,
\newblock {\em Proceedings of the Eighteenth Annual Conference 
on Computational Learning Theory} (COLT), 2005.

\bibitem[Sla61]{slater}
P.~Slater.
\newblock Inconsistencies in a schedule of paired comparisons,
\newblock {\em Biometrika} 48, 303--312, 1961.
\end{thebibliography}

\shrink{
\appendix
\section{Supporting Lemmas}\label{support}
The proof of Theorem~\ref{thm:regret} used two simple 
lemmas which we prove here.

Recall that $\Q$ denotes the distribution of label sequences $\{0,1\}^n$
of an unlabeled set $\{1,\ldots,n\}$.
Call regret $r_{\Q}(i,j)$ \emph{proper} if $l_{\Q}(i,j)-l_{\Q}(j,i) \geq 0$.
Notice that if $r_{\Q}(i,j)$ is proper, then $r_{\Q}(j,i)=0$.

\begin{lemma}\label{triangle}
For any $i$, $j$, and $k$ in $\{1,\ldots,n\}$,
if $r_{\Q}(i,j)$ and $r_{\Q}(j,k)$ are proper,
$$r_{\Q}(i,k) = r_{\Q}(i,j)+r_{\Q}(j,k).$$
\end{lemma}
\begin{proof}
Let $p$ be a shorthand for the restriction
of $Q$ to indices $\{i, j, k\}$ (so $p$ 
is a distribution over $\{0,1\}^3$ obtained by summing over all label indices
other than $i$, $j$, and $k$).
A simple algebraic manipulation verifies the claim.
\begin{align*}
r_{\Q}(i,j)&+r_{\Q}(j,k) = \\
&p(100)+p(101)-p(010)-p(011) +p(010)+p(110)-p(001)-p(101)= \\
&p(100)+p(110)-p(001)-p(011)=r_{\Q}(i,k).
\end{align*}
Notice that all label assignments above have exactly two mixed
pairs, so the factor of $1/2$ is cancelled throughout.\quad\qedblob
\end{proof}

\begin{lemma}\label{reg}
If with respect to $Q$, the ordering 
$\langle 1, 2, \ldots, n\rangle$ has zero AUC regret, then
all regret-zero pairwise predictions must be consistent with the ordering:
$r_{\Q}(i,j)=0$ for all $1\leq i<j \leq n$.
\end{lemma}
\begin{proof}
All regrets $r_{\Q}(i,i+1)$ must be 0, since swapping $i$ and $i+1$
does not affect other pairwise regrets and would thus decrease
the overall regret, contradicting the assumption
that $\langle 1, 2, \ldots, n\rangle$ is regret minimizing.
Consequently, all $r_{\Q}(i+1,i)$ are proper.
Repeated application of Lemma~\ref{triangle} implies that, for any $j>i$,
$r_{\Q}(j,i)$ is proper, which in turn implies that
$r_{\Q}(i,j)=0$, concluding the proof.
\quad
\qedblob
\end{proof}
}
\end{document}
