  Bipartite ranking is an important supervised learning problem; however,
unlike regression or classification, it has a quadratic dependence on the
number of samples. To circumvent the prohibitive sample cost, many recent work
focus on stochastic gradient-based methods. In this paper we consider an
alternative approach, which leverages the structure of the widely-adopted
pairwise squared loss, to obtain a stochastic and low cost algorithm that does
not require stochastic gradients or learning rates. Using a novel uniform risk
bound---based on matrix and vector concentration inequalities---we show that
the sample size required for competitive performance against the all-pairs
batch algorithm does not have a quadratic dependence. Generalization bounds for
both the batch and low cost stochastic algorithms are presented. Experimental
results show significant speed gain against the batch algorithm, as well as
competitive performance against state-of-the-art bipartite ranking algorithms
on real datasets.
