Ranking via Robust Binary Classification
%David S.~Hippocampus\thanks{ Use footnote for providing further information %about author (webpage
alternative address)---not
We propose RoBiRank, a ranking algorithm that is motivated by observing a close connection between evaluation metrics for learning to rank and loss functions for robust classification. It shows competitive performance on standard benchmark datasets against a number of other representative algorithms in the literature. We also discuss extensions of RoBiRank to large scale problems where explicit feature vectors and scores are not given. We show that RoBiRank can be efficiently parallelized across a large number of machines; for a task that requires $386,133 \times 49,824,519$ pairwise interactions between items to be ranked, RoBiRank finds solutions that are of dramatically higher quality than that can be found by a state-of-the-art competitor algorithm, given the same amount of wall-clock time for computation.
Definitions.tex
\RequirePackage{latexsym}
\RequirePackage{amsmath}
\RequirePackage{amsthm}
\RequirePackage{amssymb}
\RequirePackage{bm}

%%%%%%%% Stock standard definitions %%%%%%%%%%%%%%%

\newcommand{\ab}{\mathbf{a}}
\newcommand{\bb}{\mathbf{b}}
\newcommand{\cbb}{\mathbf{c}}
\newcommand{\db}{\mathbf{d}}
\newcommand{\eb}{\mathbf{e}}
\newcommand{\fb}{\mathbf{f}}
\newcommand{\gb}{\mathbf{g}}
\newcommand{\hb}{\mathbf{h}}
\newcommand{\ib}{\mathbf{i}}
\newcommand{\jb}{\mathbf{j}}
\newcommand{\kb}{\mathbf{k}}
\newcommand{\lb}{\mathbf{l}}
\newcommand{\mb}{\mathbf{m}}
\newcommand{\nbb}{\mathbf{n}}
\newcommand{\ob}{\mathbf{o}}
\newcommand{\pb}{\mathbf{p}}
\newcommand{\qb}{\mathbf{q}}
\newcommand{\rb}{\mathbf{r}}
\newcommand{\sbb}{\mathbf{s}}
\newcommand{\tb}{\mathbf{t}}
\newcommand{\ub}{\mathbf{u}}
\newcommand{\vb}{\mathbf{v}}
\newcommand{\wb}{\mathbf{w}}
\newcommand{\xb}{\mathbf{x}}
\newcommand{\yb}{\mathbf{y}}
\newcommand{\zb}{\mathbf{z}}

\newcommand{\abtil}{\tilde{\ab}}
\newcommand{\bbtil}{\tilde{\bb}}
\newcommand{\cbtil}{\tilde{\cbb}}
\newcommand{\dbtil}{\tilde{\db}}
\newcommand{\ebtil}{\tilde{\eb}}
\newcommand{\fbtil}{\tilde{\fb}}
\newcommand{\gbtil}{\tilde{\gb}}
\newcommand{\hbtil}{\tilde{\hb}}
\newcommand{\ibtil}{\tilde{\ib}}
\newcommand{\jbtil}{\tilde{\jb}}
\newcommand{\kbtil}{\tilde{\kb}}
\newcommand{\lbtil}{\tilde{\lb}}
\newcommand{\mbtil}{\tilde{\mb}}
\newcommand{\nbtil}{\tilde{\nbb}}
\newcommand{\obtil}{\tilde{\ob}}
\newcommand{\pbtil}{\tilde{\pb}}
\newcommand{\qbtil}{\tilde{\qb}}
\newcommand{\rbtil}{\tilde{\rb}}
\newcommand{\sbtil}{\tilde{\sbb}}
\newcommand{\tbtil}{\tilde{\tb}}
\newcommand{\ubtil}{\tilde{\ub}}
\newcommand{\vbtil}{\tilde{\vb}}
\newcommand{\wbtil}{\tilde{\wb}}
\newcommand{\xbtil}{\tilde{\xb}}
\newcommand{\ybtil}{\tilde{\yb}}
\newcommand{\zbtil}{\tilde{\zb}}

\newcommand{\atil}{\tilde{a}}
\newcommand{\btil}{\tilde{b}}
\newcommand{\ctil}{\tilde{c}}
\newcommand{\dtil}{\tilde{d}}
\newcommand{\etil}{\tilde{e}}
\newcommand{\ftil}{\tilde{f}}
\newcommand{\gtil}{\tilde{g}}
\newcommand{\htil}{\tilde{h}}
\newcommand{\itil}{\tilde{i}}
\newcommand{\jtil}{\tilde{j}}
\newcommand{\ktil}{\tilde{k}}
\newcommand{\ltil}{\tilde{l}}
\newcommand{\mtil}{\tilde{m}}
\newcommand{\ntil}{\tilde{n}}
\newcommand{\otil}{\tilde{o}}
\newcommand{\ptil}{\tilde{p}}
\newcommand{\qtil}{\tilde{q}}
\newcommand{\rtil}{\tilde{r}}
\newcommand{\stil}{\tilde{s}}
\newcommand{\ttil}{\tilde{t}}
\newcommand{\util}{\tilde{u}}
\newcommand{\vtil}{\tilde{v}}
\newcommand{\wtil}{\tilde{w}}
\newcommand{\xtil}{\tilde{x}}
\newcommand{\ytil}{\tilde{y}}
\newcommand{\ztil}{\tilde{z}}

\newcommand{\ahat}{\hat{a}}
\newcommand{\bhat}{\hat{b}}
\newcommand{\chat}{\hat{c}}
\newcommand{\dhat}{\hat{d}}
\newcommand{\ehat}{\hat{e}}
\newcommand{\fhat}{\hat{f}}
\newcommand{\ghat}{\hat{g}}
\newcommand{\hhat}{\hat{h}}
\newcommand{\ihat}{\hat{i}}
\newcommand{\jhat}{\hat{j}}
\newcommand{\khat}{\hat{k}}
\newcommand{\lhat}{\hat{l}}
\newcommand{\mhat}{\hat{m}}
\newcommand{\nhat}{\hat{n}}
\newcommand{\ohat}{\hat{o}}
\newcommand{\phat}{\hat{p}}
\newcommand{\qhat}{\hat{q}}
\newcommand{\rhat}{\hat{r}}
\newcommand{\shat}{\hat{s}}
\newcommand{\that}{\hat{t}}
\newcommand{\uhat}{\hat{u}}
\newcommand{\vhat}{\hat{v}}
\newcommand{\what}{\hat{w}}
\newcommand{\xhat}{\hat{x}}
\newcommand{\yhat}{\hat{y}}
\newcommand{\zhat}{\hat{z}}

\newcommand{\abhat}{\hat{\ab}}
\newcommand{\bbhat}{\hat{\bb}}
\newcommand{\cbhat}{\hat{\cb}}
\newcommand{\dbhat}{\hat{\db}}
\newcommand{\ebhat}{\hat{\eb}}
\newcommand{\fbhat}{\hat{\fb}}
\newcommand{\gbhat}{\hat{\gb}}
\newcommand{\hbhat}{\hat{\hb}}
\newcommand{\ibhat}{\hat{\ib}}
\newcommand{\jbhat}{\hat{\jb}}
\newcommand{\kbhat}{\hat{\kb}}
\newcommand{\lbhat}{\hat{\lb}}
\newcommand{\mbhat}{\hat{\mb}}
\newcommand{\nbhat}{\hat{\nb}}
\newcommand{\obhat}{\hat{\ob}}
\newcommand{\pbhat}{\hat{\pb}}
\newcommand{\qbhat}{\hat{\qb}}
\newcommand{\rbhat}{\hat{\rb}}
\newcommand{\sbhat}{\hat{\sb}}
\newcommand{\tbhat}{\hat{\tb}}
\newcommand{\ubhat}{\hat{\ub}}
\newcommand{\vbhat}{\hat{\vb}}
\newcommand{\wbhat}{\hat{\wb}}
\newcommand{\xbhat}{\hat{\xb}}
\newcommand{\ybhat}{\hat{\yb}}
\newcommand{\zbhat}{\hat{\zb}}

\newcommand{\Atil}{\tilde{A}}
\newcommand{\Btil}{\tilde{B}}
\newcommand{\Ctil}{\tilde{C}}
\newcommand{\Dtil}{\tilde{D}}
\newcommand{\Etil}{\tilde{E}}
\newcommand{\Ftil}{\tilde{F}}
\newcommand{\Gtil}{\tilde{G}}
\newcommand{\Htil}{\tilde{H}}
\newcommand{\Itil}{\tilde{I}}
\newcommand{\Jtil}{\tilde{J}}
\newcommand{\Ktil}{\tilde{K}}
\newcommand{\Ltil}{\tilde{L}}
\newcommand{\Mtil}{\tilde{M}}
\newcommand{\Ntil}{\tilde{N}}
\newcommand{\Otil}{\tilde{O}}
\newcommand{\Ptil}{\tilde{P}}
\newcommand{\Qtil}{\tilde{Q}}
\newcommand{\Rtil}{\tilde{R}}
\newcommand{\Stil}{\tilde{S}}
\newcommand{\Ttil}{\tilde{T}}
\newcommand{\Util}{\tilde{U}}
\newcommand{\Vtil}{\tilde{V}}
\newcommand{\Wtil}{\tilde{W}}
\newcommand{\Xtil}{\tilde{X}}
\newcommand{\Ytil}{\tilde{Y}}
\newcommand{\Ztil}{\tilde{Z}}

\newcommand{\abar}{\bar{a}}
\newcommand{\bbar}{\bar{b}}
\newcommand{\cbar}{\bar{c}}
\newcommand{\dbar}{\bar{d}}
\newcommand{\ebar}{\bar{e}}
\newcommand{\fbar}{\bar{f}}
\newcommand{\gbar}{\bar{g}}
\newcommand{\hbr}{\bar{h}}
\newcommand{\ibar}{\bar{i}}
\newcommand{\jbar}{\bar{j}}
\newcommand{\kbar}{\bar{k}}
\newcommand{\lbar}{\bar{l}}
\newcommand{\mbar}{\bar{m}}
\newcommand{\nbar}{\bar{n}}
\newcommand{\obar}{\bar{o}}
\newcommand{\pbar}{\bar{p}}
\newcommand{\qbar}{\bar{q}}
\newcommand{\rbar}{\bar{r}}
\newcommand{\sbar}{\bar{s}}
\newcommand{\tbar}{\bar{t}}
\newcommand{\ubar}{\bar{u}}
\newcommand{\vbar}{\bar{v}}
\newcommand{\wbar}{\bar{w}}
\newcommand{\xbar}{\bar{x}}
\newcommand{\ybar}{\bar{y}}
\newcommand{\zbar}{\bar{z}}

\newcommand{\abbar}{\bar{\ab}}
\newcommand{\bbbar}{\bar{\bb}}
\newcommand{\cbbar}{\bar{\cb}}
\newcommand{\dbbar}{\bar{\db}}
\newcommand{\ebbar}{\bar{\eb}}
\newcommand{\fbbar}{\bar{\fb}}
\newcommand{\gbbar}{\bar{\gb}}
\newcommand{\hbbar}{\bar{\hb}}
\newcommand{\ibbar}{\bar{\ib}}
\newcommand{\jbbar}{\bar{\jb}}
\newcommand{\kbbar}{\bar{\kb}}
\newcommand{\lbbar}{\bar{\lb}}
\newcommand{\mbbar}{\bar{\mb}}
\newcommand{\nbbar}{\bar{\nbb}}
\newcommand{\obbar}{\bar{\ob}}
\newcommand{\pbbar}{\bar{\pb}}
\newcommand{\qbbar}{\bar{\qb}}
\newcommand{\rbbar}{\bar{\rb}}
\newcommand{\sbbar}{\bar{\sbb}}
\newcommand{\tbbar}{\bar{\tb}}
\newcommand{\ubbar}{\bar{\ub}}
\newcommand{\vbbar}{\bar{\vb}}
\newcommand{\wbbar}{\bar{\wb}}
\newcommand{\xbbar}{\bar{\xb}}
\newcommand{\ybbar}{\bar{\yb}}
\newcommand{\zbbar}{\bar{\zb}}

\newcommand{\Ab}{\mathbf{A}}
\newcommand{\Bb}{\mathbf{B}}
\newcommand{\Cb}{\mathbf{C}}
\newcommand{\Db}{\mathbf{D}}
\newcommand{\Eb}{\mathbf{E}}
\newcommand{\Fb}{\mathbf{F}}
\newcommand{\Gb}{\mathbf{G}}
\newcommand{\Hb}{\mathbf{H}}
\newcommand{\Ib}{\mathbf{I}}
\newcommand{\Jb}{\mathbf{J}}
\newcommand{\Kb}{\mathbf{K}}
\newcommand{\Lb}{\mathbf{L}}
\newcommand{\Mb}{\mathbf{M}}
\newcommand{\Nb}{\mathbf{N}}
\newcommand{\Ob}{\mathbf{O}}
\newcommand{\Pb}{\mathbf{P}}
\newcommand{\Qb}{\mathbf{Q}}
\newcommand{\Rb}{\mathbf{R}}
\newcommand{\Sbb}{\mathbf{S}}
\newcommand{\Tb}{\mathbf{T}}
\newcommand{\Ub}{\mathbf{U}}
\newcommand{\Vb}{\mathbf{V}}
\newcommand{\Wb}{\mathbf{W}}
\newcommand{\Xb}{\mathbf{X}}
\newcommand{\Yb}{\mathbf{Y}}
\newcommand{\Zb}{\mathbf{Z}}

\newcommand{\Abtil}{\tilde{\Ab}}
\newcommand{\Bbtil}{\tilde{\Bb}}
\newcommand{\Cbtil}{\tilde{\Cb}}
\newcommand{\Dbtil}{\tilde{\Db}}
\newcommand{\Ebtil}{\tilde{\Eb}}
\newcommand{\Fbtil}{\tilde{\Fb}}
\newcommand{\Gbtil}{\tilde{\Gb}}
\newcommand{\Hbtil}{\tilde{\Hb}}
\newcommand{\Ibtil}{\tilde{\Ib}}
\newcommand{\Jbtil}{\tilde{\Jb}}
\newcommand{\Kbtil}{\tilde{\Kb}}
\newcommand{\Lbtil}{\tilde{\Lb}}
\newcommand{\Mbtil}{\tilde{\Mb}}
\newcommand{\Nbtil}{\tilde{\Nb}}
\newcommand{\Obtil}{\tilde{\Ob}}
\newcommand{\Pbtil}{\tilde{\Pb}}
\newcommand{\Qbtil}{\tilde{\Qb}}
\newcommand{\Rbtil}{\tilde{\Rb}}
\newcommand{\Sbtil}{\tilde{\Sbb}}
\newcommand{\Tbtil}{\tilde{\Tb}}
\newcommand{\Ubtil}{\tilde{\Ub}}
\newcommand{\Vbtil}{\tilde{\Vb}}
\newcommand{\Wbtil}{\tilde{\Wb}}
\newcommand{\Xbtil}{\tilde{\Xb}}
\newcommand{\Ybtil}{\tilde{\Yb}}
\newcommand{\Zbtil}{\tilde{\Zb}}

\newcommand{\Abar}{\bar{A}}
\newcommand{\Bbar}{\bar{B}}
\newcommand{\Cbar}{\bar{C}}
\newcommand{\Dbar}{\bar{D}}
\newcommand{\Ebar}{\bar{E}}
\newcommand{\Fbar}{\bar{F}}
\newcommand{\Gbar}{\bar{G}}
\newcommand{\Hbar}{\bar{H}}
\newcommand{\Ibar}{\bar{I}}
\newcommand{\Jbar}{\bar{J}}
\newcommand{\Kbar}{\bar{K}}
\newcommand{\Lbar}{\bar{L}}
\newcommand{\Mbar}{\bar{M}}
\newcommand{\Nbar}{\bar{N}}
\newcommand{\Obar}{\bar{O}}
\newcommand{\Pbar}{\bar{P}}
\newcommand{\Qbar}{\bar{Q}}
\newcommand{\Rbar}{\bar{R}}
\newcommand{\Sbar}{\bar{S}}
\newcommand{\Tbar}{\bar{T}}
\newcommand{\Ubar}{\bar{U}}
\newcommand{\Vbar}{\bar{V}}
\newcommand{\Wbar}{\bar{W}}
\newcommand{\Xbar}{\bar{X}}
\newcommand{\Ybar}{\bar{Y}}
\newcommand{\Zbar}{\bar{Z}}

\newcommand{\Abbar}{\bar{\Ab}}
\newcommand{\Bbbar}{\bar{\Bb}}
\newcommand{\Cbbar}{\bar{\Cb}}
\newcommand{\Dbbar}{\bar{\Db}}
\newcommand{\Ebbar}{\bar{\Eb}}
\newcommand{\Fbbar}{\bar{\Fb}}
\newcommand{\Gbbar}{\bar{\Gb}}
\newcommand{\Hbbar}{\bar{\Hb}}
\newcommand{\Ibbar}{\bar{\Ib}}
\newcommand{\Jbbar}{\bar{\Jb}}
\newcommand{\Kbbar}{\bar{\Kb}}
\newcommand{\Lbbar}{\bar{\Lb}}
\newcommand{\Mbbar}{\bar{\Mb}}
\newcommand{\Nbbar}{\bar{\Nb}}
\newcommand{\Obbar}{\bar{\Ob}}
\newcommand{\Pbbar}{\bar{\Pb}}
\newcommand{\Qbbar}{\bar{\Qb}}
\newcommand{\Rbbar}{\bar{\Rb}}
\newcommand{\Sbbar}{\bar{\Sb}}
\newcommand{\Tbbar}{\bar{\Tb}}
\newcommand{\Ubbar}{\bar{\Ub}}
\newcommand{\Vbbar}{\bar{\Vb}}
\newcommand{\Wbbar}{\bar{\Wb}}
\newcommand{\Xbbar}{\bar{\Xb}}
\newcommand{\Ybbar}{\bar{\Yb}}
\newcommand{\Zbbar}{\bar{\Zb}}

\newcommand{\Ahat}{\hat{A}}
\newcommand{\Bhat}{\hat{B}}
\newcommand{\Chat}{\hat{C}}
\newcommand{\Dhat}{\hat{D}}
\newcommand{\Ehat}{\hat{E}}
\newcommand{\Fhat}{\hat{F}}
\newcommand{\Ghat}{\hat{G}}
\newcommand{\Hhat}{\hat{H}}
\newcommand{\Ihat}{\hat{I}}
\newcommand{\Jhat}{\hat{J}}
\newcommand{\Khat}{\hat{K}}
\newcommand{\Lhat}{\hat{L}}
\newcommand{\Mhat}{\hat{M}}
\newcommand{\Nhat}{\hat{N}}
\newcommand{\Ohat}{\hat{O}}
\newcommand{\Phat}{\hat{P}}
\newcommand{\Qhat}{\hat{Q}}
\newcommand{\Rhat}{\hat{R}}
\newcommand{\Shat}{\hat{S}}
\newcommand{\That}{\hat{T}}
\newcommand{\Uhat}{\hat{U}}
\newcommand{\Vhat}{\hat{V}}
\newcommand{\What}{\hat{W}}
\newcommand{\Xhat}{\hat{X}}
\newcommand{\Yhat}{\hat{Y}}
\newcommand{\Zhat}{\hat{Z}}

\newcommand{\Abhat}{\hat{\Ab}}
\newcommand{\Bbhat}{\hat{\Bb}}
\newcommand{\Cbhat}{\hat{\Cb}}
\newcommand{\Dbhat}{\hat{\Db}}
\newcommand{\Ebhat}{\hat{\Eb}}
\newcommand{\Fbhat}{\hat{\Fb}}
\newcommand{\Gbhat}{\hat{\Gb}}
\newcommand{\Hbhat}{\hat{\Hb}}
\newcommand{\Ibhat}{\hat{\Ib}}
\newcommand{\Jbhat}{\hat{\Jb}}
\newcommand{\Kbhat}{\hat{\Kb}}
\newcommand{\Lbhat}{\hat{\Lb}}
\newcommand{\Mbhat}{\hat{\Mb}}
\newcommand{\Nbhat}{\hat{\Nb}}
\newcommand{\Obhat}{\hat{\Ob}}
\newcommand{\Pbhat}{\hat{\Pb}}
\newcommand{\Qbhat}{\hat{\Qb}}
\newcommand{\Rbhat}{\hat{\Rb}}
\newcommand{\Sbhat}{\hat{\Sb}}
\newcommand{\Tbhat}{\hat{\Tb}}
\newcommand{\Ubhat}{\hat{\Ub}}
\newcommand{\Vbhat}{\hat{\Vb}}
\newcommand{\Wbhat}{\hat{\Wb}}
\newcommand{\Xbhat}{\hat{\Xb}}
\newcommand{\Ybhat}{\hat{\Yb}}
\newcommand{\Zbhat}{\hat{\Zb}}

\newcommand{\Acal}{\mathcal{A}}
\newcommand{\Bcal}{\mathcal{B}}
\newcommand{\Ccal}{\mathcal{C}}
\newcommand{\Dcal}{\mathcal{D}}
\newcommand{\Ecal}{\mathcal{E}}
\newcommand{\Fcal}{\mathcal{F}}
\newcommand{\Gcal}{\mathcal{G}}
\newcommand{\Hcal}{\mathcal{H}}
\newcommand{\Ical}{\mathcal{I}}
\newcommand{\Jcal}{\mathcal{J}}
\newcommand{\Kcal}{\mathcal{K}}
\newcommand{\Lcal}{\mathcal{L}}
\newcommand{\Mcal}{\mathcal{M}}
\newcommand{\Ncal}{\mathcal{N}}
\newcommand{\Ocal}{\mathcal{O}}
\newcommand{\Pcal}{\mathcal{P}}
\newcommand{\Qcal}{\mathcal{Q}}
\newcommand{\Rcal}{\mathcal{R}}
\newcommand{\Scal}{{\mathcal{S}}}
\newcommand{\Tcal}{{\mathcal{T}}}
\newcommand{\Ucal}{\mathcal{U}}
\newcommand{\Vcal}{\mathcal{V}}
\newcommand{\Wcal}{\mathcal{W}}
\newcommand{\Xcal}{\mathcal{X}}
\newcommand{\Ycal}{\mathcal{Y}}
\newcommand{\Zcal}{\mathcal{Z}}

\newcommand{\Atilde}{\widetilde{A}}
\newcommand{\Btilde}{\widetilde{B}}
\newcommand{\Ctilde}{\widetilde{C}}
\newcommand{\Dtilde}{\widetilde{D}}
\newcommand{\Etilde}{\widetilde{E}}
\newcommand{\Ftilde}{\widetilde{F}}
\newcommand{\Gtilde}{\widetilde{G}}
\newcommand{\Htilde}{\widetilde{H}}
\newcommand{\Itilde}{\widetilde{I}}
\newcommand{\Jtilde}{\widetilde{J}}
\newcommand{\Ktilde}{\widetilde{K}}
\newcommand{\Ltilde}{\widetilde{L}}
\newcommand{\Mtilde}{\widetilde{M}}
\newcommand{\Ntilde}{\widetilde{N}}
\newcommand{\Otilde}{\widetilde{O}}
\newcommand{\Ptilde}{\widetilde{P}}
\newcommand{\Qtilde}{\widetilde{Q}}
\newcommand{\Rtilde}{\widetilde{R}}
\newcommand{\Stilde}{\widetilde{S}}
\newcommand{\Ttilde}{\widetilde{T}}
\newcommand{\Utilde}{\widetilde{U}}
\newcommand{\Vtilde}{\widetilde{V}}
\newcommand{\Wtilde}{\widetilde{W}}
\newcommand{\Xtilde}{\widetilde{X}}
\newcommand{\Ytilde}{\widetilde{Y}}
\newcommand{\Ztilde}{\widetilde{Z}}

\renewcommand{\vec}[1]{\mathbf{\boldsymbol{#1}}}

\newcommand{\avec}{\vec{a}}
\newcommand{\bvec}{\vec{b}}
\newcommand{\cvec}{\vec{c}}
\newcommand{\dvec}{\vec{d}}
\newcommand{\evec}{\vec{e}}
\newcommand{\fvec}{\vec{f}}
\newcommand{\gvec}{\vec{g}}
\newcommand{\hvec}{\vec{h}}
\newcommand{\ivec}{\vec{i}}
\newcommand{\jvec}{\vec{j}}
\newcommand{\kvec}{\vec{k}}
\newcommand{\lvec}{\vec{l}}
\newcommand{\mvec}{\vec{m}}
\newcommand{\nvec}{\vec{n}}
\newcommand{\ovec}{\vec{o}}
\newcommand{\pvec}{\vec{p}}
\newcommand{\qvec}{\vec{q}}
\newcommand{\rvec}{\vec{r}}
\newcommand{\svec}{\vec{s}}
\newcommand{\tvec}{\vec{t}}
\newcommand{\uvec}{\vec{u}}
\newcommand{\vvec}{\vec{v}}
\newcommand{\wvec}{\vec{w}}
\newcommand{\xvec}{\vec{x}}
\newcommand{\yvec}{\vec{y}}
\newcommand{\zvec}{\vec{z}}

\newcommand{\va}{\vec{a}}
\newcommand{\vecb}{\vec{b}}
\newcommand{\vc}{\vec{c}}
\newcommand{\vd}{\vec{d}}
\newcommand{\veee}{\vec{e}}
\newcommand{\vf}{\vec{f}}
\newcommand{\vg}{\vec{g}}
\newcommand{\vh}{\vec{h}}
\newcommand{\vi}{\vec{i}}
\newcommand{\vo}{\vec{o}}
\newcommand{\vp}{\vec{p}}
\newcommand{\vq}{\vec{q}}
\newcommand{\vr}{\vec{r}}
\newcommand{\vs}{\vec{s}}
\newcommand{\vt}{\vec{t}}
\newcommand{\vu}{\vec{u}}
\newcommand{\vv}{\vec{v}}
\newcommand{\vx}{\vec{x}}
\newcommand{\vw}{\vec{w}}
\newcommand{\vy}{\vec{y}}
\newcommand{\vz}{\vec{z}}

\newcommand{\Avec}{\vec{A}}
\newcommand{\Bvec}{\vec{B}}
\newcommand{\Cvec}{\vec{C}}
\newcommand{\Dvec}{\vec{D}}
\newcommand{\Evec}{\vec{E}}
\newcommand{\Fvec}{\vec{F}}
\newcommand{\Gvec}{\vec{G}}
\newcommand{\Hvec}{\vec{H}}
\newcommand{\Ivec}{\vec{I}}
\newcommand{\Jvec}{\vec{J}}
\newcommand{\Kvec}{\vec{K}}
\newcommand{\Lvec}{\vec{L}}
\newcommand{\Mvec}{\vec{M}}
\newcommand{\Nvec}{\vec{N}}
\newcommand{\Ovec}{\vec{O}}
\newcommand{\Pvec}{\vec{P}}
\newcommand{\Qvec}{\vec{Q}}
\newcommand{\Rvec}{\vec{R}}
\newcommand{\Svec}{\vec{S}}
\newcommand{\Tvec}{\vec{T}}
\newcommand{\Uvec}{\vec{U}}
\newcommand{\Vvec}{\vec{V}}
\newcommand{\Wvec}{\vec{W}}
\newcommand{\Xvec}{\vec{X}}
\newcommand{\Yvec}{\vec{Y}}
\newcommand{\Zvec}{\vec{Z}}

\newcommand{\Amat}{\Ab}
\newcommand{\Bmat}{\Bb}
\newcommand{\Cmat}{\Cb}
\newcommand{\Dmat}{\Db}
\newcommand{\Emat}{\Eb}
\newcommand{\Fmat}{\Fb}
\newcommand{\Gmat}{\Gb}
\newcommand{\Hmat}{\Hb}
\newcommand{\Imat}{\Ib}

\newcommand{\Vmat}{\Vb}
\newcommand{\Wmat}{\Wb}
\newcommand{\Xmat}{\Xb}
\newcommand{\Ymat}{\Yb}
\newcommand{\Zmat}{\Zb}


\newcommand{\yvecbar}{\bar{\vec{y}}}
\newcommand{\wvecbar}{\bar{\vec{w}}}
\newcommand{\xvecbar}{\bar{\vec{x}}}
\newcommand{\yvectil}{\tilde{\vec{y}}}
\newcommand{\yvechat}{\hat{\vec{y}}}


%%%%%%%% Theorems and Friends %%%%%%%%%%%%%%%

%% Some style files might actually define these variables.
%% So don't mess with them if they are already defined

\ifx\BlackBox\undefined
\newcommand{\BlackBox}{\rule{1.5ex}{1.5ex}}  % end of proof
\fi

\ifx\QED\undefined
\def\QED{~\rule[-1pt]{5pt}{5pt}\par\medskip}
\fi

\ifx\proof\undefined
\newenvironment{proof}{\par\noindent{\bf Proof\ }}{\hfill\BlackBox\\[2mm]}
\fi

\ifx\theorem\undefined
\newtheorem{theorem}{Theorem}
\fi

\ifx\example\undefined
\newtheorem{example}{Example}
\fi

\ifx\property\undefined
\newtheorem{property}{Property}
\fi

\ifx\lemma\undefined
\newtheorem{lemma}[theorem]{Lemma}
\fi

\ifx\proposition\undefined
\newtheorem{proposition}[theorem]{Proposition}
\fi

\ifx\remark\undefined
\newtheorem{remark}[theorem]{Remark}
\fi

\ifx\corollary\undefined
\newtheorem{corollary}[theorem]{Corollary}
\fi

\ifx\definition\undefined
\newtheorem{definition}{Definition}
\fi

\ifx\conjecture\undefined
\newtheorem{conjecture}[theorem]{Conjecture}
\fi

\ifx\axiom\undefined
\newtheorem{axiom}[theorem]{Axiom}
\fi

\ifx\claim\undefined
\newtheorem{claim}[theorem]{Claim}
\fi

\ifx\assumption\undefined
\newtheorem{assumption}[theorem]{Assumption}
\fi

% \renewcommand{\qedsymbol}{$\blacksquare$}


%%%%%%%% Widely accepted Sets and Symbols %%%%%%%%%%%%%%%

\newcommand{\CC}{\mathbb{C}} % Complex numbers
\newcommand{\EE}{\mathbb{E}} % Expectation
\newcommand{\FF}{\mathbb{F}} % Fexpectation
\newcommand{\HH}{\mathbb{H}} % Arbitrary field
\newcommand{\II}{\mathbb{I}} % Delta Indicator
\newcommand{\KK}{\mathbb{K}} % Arbitrary field
\newcommand{\MM}{\mathbb{M}} % Median
\newcommand{\NN}{\mathbb{N}} % Natural numbers
\newcommand{\PP}{\mathbb{P}} % Probability
\newcommand{\QQ}{\mathbb{Q}} % Rationals
\newcommand{\RR}{\mathbb{R}} % Real numbers
\newcommand{\RRbar}{\overline{\RR}} % Real numbers
\newcommand{\VV}{\mathbb{V}} % Variance
\newcommand{\XX}{\mathbb{X}}
\newcommand{\YY}{\mathbb{Y}}
\newcommand{\ZZ}{\mathbb{Z}} % Integers

%%%%%%%% Mathematical Operations %%%%%%%%%%%%%%%

\newcommand*{\mini}{\mathop{\mathrm{minimize}}}
\newcommand*{\maxi}{\mathop{\mathrm{maximize}}}
\newcommand*{\argmin}{\mathop{\mathrm{argmin}}}
\newcommand*{\argmax}{\mathop{\mathrm{argmax}}}
\newcommand*{\arginf}{\mathop{\mathrm{arginf}}}
\newcommand*{\argsup}{\mathop{\mathrm{argsup}}}
\newcommand{\sgn}{\mathop{\mathrm{sign}}}
\newcommand{\tr}{\mathop{\mathrm{tr}}}
\newcommand{\diag}{\mathop{\mathrm{diag}}}
\newcommand{\rank}{\mathop{\mathrm{rank}}}
\newcommand{\vect}{\mathop{\mathrm{vec}}}
\newcommand{\traj}{\mathop{\mathrm{Traj}}}
\newcommand{\cov}{\mathrm{Cov}}
\newcommand{\conv}{\mathrm{conv}}
\newcommand{\const}{\mathrm{constant}}
\newcommand{\dom}{\mathop{\mathrm{dom}}}
\newcommand{\ri}{\mathop{\mathrm{ri}}}
\newcommand{\cl}{\mathop{\mathrm{cl}}}
\newcommand{\intr}{\mathop{\mathrm{int}}}
\newcommand{\bd}{\mathop{\mathrm{bd}}}
\newcommand{\emp}{\mathop{\mathrm{emp}}}
\newcommand{\core}{\mathop{\mathrm{core}}}
\newcommand{\co}{\mathop{\mathrm{co}}}
\newcommand{\nnz}{\mathop{\mathrm{nnz}}}
\newcommand{\eproof}{$\null\hfill\blacksquare$}

%\newcommand{\ln}{\mathop{\mathrm{ln}}}
%%%%%%%% Utility functions %%%%%%%%%%%%%%%

\newcommand{\eq}[1]{(\ref{#1})}
\newcommand{\mymatrix}[2]{\left[\begin{array}{#1} #2 \end{array}\right]}
\newcommand{\mychoose}[2]{\left(\begin{array}{c} #1 \\ #2 \end{array}\right)}
\newcommand{\mydet}[1]{\det\left[ #1 \right]}
\newcommand{\myspan}[1]{\mathrm{span}\cbr{#1}}
\newcommand{\smallfrac}[2]{{\textstyle \frac{#1}{#2}}}
\newcommand{\pwrt}[1]{\frac{\partial}{\partial #1}}
\newcommand{\ppwrt}[1]{\frac{\partial^2}{(\partial #1)^2}}
\newcommand{\aleq}{\preccurlyeq}
\newcommand{\ageq}{\succcurlyeq}
%%%%%%%% Short Forms %%%%%%%%%%%%%%%

\newcommand{\ea}{\emph{et al.}}
\newcommand{\eg}{\emph{e.g.}}
\newcommand{\ie}{\emph{i.e.}}
\newcommand{\iid}{\emph{iid}}
\newcommand{\cf}{\emph{cf.}\ }
\newcommand{\wrt}{\emph{w.r.t.}\ }

%%%%%%%% Brackets %%%%%%%%%%%%%%%

\newcommand{\rbr}[1]{\left(#1\right)}
\newcommand{\sbr}[1]{\left[#1\right]}
\newcommand{\cbr}[1]{\left\{#1\right\}}
\newcommand{\nbr}[1]{\left\|#1\right\|}
\newcommand{\abr}[1]{\left|#1\right|}
\newcommand{\abs}[1]{\left|#1\right|}
\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}
\newcommand{\ceil}[1]{\left\lceil #1 \right\rceil}
\newcommand{\inner}[2]{\left\langle #1,#2 \right\rangle}
\newcommand{\norm}[1]{\|#1\|}
\newcommand{\ccc}[1]{|\!|\!|#1|\!|\!|}
\newcommand{\sembrack}[1]{[\![#1]\!]}

%%%%%%%%%%%%%%%  Mathematical Constants  %%%%%%%%%%%%%%%

\newcommand{\one}{\mathbf{1}}  % Identity
\newcommand{\zero}{\mathbf{0}} % Zero
\newcommand{\ind}{\boldsymbol{\mathsf{I}}}
\newcommand{\half}{\frac{1}{2}}
\newcommand{\sqrttwo}{\sqrt{2}}
\newcommand{\invsqrttwo}{\frac{1}{\sqrt{2}}}
\newcommand{\rmd}{\ensuremath{\mathrm{d}}}

%%%%%%%% Greek Symbols %%%%%%%%%%%%%%%

\newcommand{\sigmab}{\bm{\sigma}}
\newcommand{\Sigmab}{\mathbf{\Sigma}}

\newcommand{\val}{\vec{\alpha}}
\newcommand{\vbeta}{\vec{\beta}}
\newcommand{\vde}{\vec{\delta}}
\newcommand{\vga}{\vec{\gamma}}
\newcommand{\vsig}{\vec{\sigma}}
\newcommand{\vth}{\vec{\theta}}
\newcommand{\veta}{\vec{\eta}}
\newcommand{\vnu}{\vec{\nu}}
\newcommand{\vpsi}{\vec{\psi}}
\newcommand{\vpi}{\vec{\pi}}
\newcommand{\vphi}{\vec{\phi}}
\newcommand{\vxi}{\vec{\xi}}
\newcommand{\vze}{\vec{\zeta}}

\newcommand{\valbar}{\bar{\val}}
\newcommand{\valhat}{\hat{\val}}
\newcommand{\valtil}{\tilde{\val}}
\newcommand{\vthtil}{\tilde{\vth}}
\newcommand{\vthhat}{\hat{\vth}}
\newcommand{\vthbar}{\bar{\vth}}
\newcommand{\vbetatil}{\tilde{\vbeta}}
\newcommand{\vbetahat}{\hat{\vbeta}}

\newcommand{\alphavec}{\val}
\newcommand{\alphavecbar}{\bar{\val}}
\newcommand{\alphavechat}{\hat{\val}}
\newcommand{\alphavectil}{\tilde{\val}}
\newcommand{\betavec}{\vec{\beta}}
\newcommand{\gammavec}{\vec{\gamma}}
\newcommand{\deltavec}{\vec{\delta}}
\newcommand{\etavec}{\vec{\eta}}
\newcommand{\phivec}{\vec{\phi}}
\newcommand{\psivec}{\vec{\psi}}
\newcommand{\thetavec}{\vec{\theta}}
\newcommand{\muvec}{\vec{\mu}}
\newcommand{\xivec}{\vec{\xi}}
\newcommand{\chivec}{\vec{\chi}}
\newcommand{\lambdavec}{\vec{\lambda}}

\newcommand{\alphab}{\boldsymbol{\alpha}}
\newcommand{\betab}{\boldsymbol{\beta}}
\newcommand{\gammab}{\boldsymbol{\gamma}}
\newcommand{\thetab}{\boldsymbol{\theta}}
\newcommand{\mub}{\boldsymbol{\mu}}
\newcommand{\xib}{\boldsymbol{\xi}}
\newcommand{\Deltab}{\boldsymbol{\Delta}}
\newcommand{\Pib}{\boldsymbol{\Pi}}
\newcommand{\etab}{\boldsymbol{\eta}}
\newcommand{\taub}{\boldsymbol{\tau}}
\newcommand{\lambdab}{\boldsymbol{\lambda}}
\newcommand{\pitil}{\tilde{\pi}}
\newcommand{\elltil}{\tilde{\ell}}
\newcommand{\rhob}{\boldsymbol{\rho}}

\newcommand{\delhat}{\hat{\delta}}
\newcommand{\phihat}{\hat{\phi}}
\newcommand{\delbar}{\bar{\delta}}
\newcommand{\alphahat}{\hat{\alpha}}
\newcommand{\alphatil}{\tilde{\alpha}}
\newcommand{\mubar}{\bar{\mu}}
\newcommand{\thetahat}{\hat{\theta}}
\newcommand{\thetabar}{\bar{\theta}}
\newcommand{\betahat}{\hat{\beta}}

\newcommand{\xibar}{\bar{\xi}}
\newcommand{\lambdavectil}{\tilde{\vec{\lambda}}}
\newcommand{\thetatil}{\tilde{\theta}}
\newcommand{\betatil}{\tilde{\beta}}

%%%%%%%% Various Optimizers %%%%%%%%%%%%%%%

\newcommand{\BMRM}{{\sf BMRM}}
\newcommand{\bmrm}{{\sf BMRM}}
\newcommand{\cpm}{{\sf CPM}}
\newcommand{\liblinear}{{\sf liblinear}}
\newcommand{\lsbmrm}{{\sf ls-bmrm}}
\newcommand{\qpbmrm}{{\sf qp-bmrm}}
\newcommand{\pegasos}{{\sf pegasos}}
\newcommand{\pegan}{{\sf pegasos-$n$}}
\newcommand{\pegaone}{{\sf pegasos-1}}
\newcommand{\svmstruct}{{\sf SVM-Struct}}
\newcommand{\svmperf}{{\sf SVM-Perf}}
\newcommand{\nest}{{\sf pragam}}
\newcommand{\nestb}{{\sf pragam-b}}
\newcommand{\mcn}{{\sf M$^3$N}}
\newcommand{\expgrad}{{\sf ExpGrad}}
\newcommand{\smo}{{\sf SMO}}
\newcommand{\lasvm}{{\sf LaSVM}}
\newcommand{\sms}{{\sf SMS}}


\newcommand{\prbep}{{\sf PRBEP}}
\newcommand{\rocarea}{{\sf ROCArea}}

\newcommand{\arow}[2]{#1_{#2\cdot}}
\newcommand{\acol}[2]{#1_{\cdot#2}}
\newcommand{\expunder}[1]{\mathop{\EE}\limits_{#1}}
\newcommand{\mean}[1]{\mathop{\EE}\sbr{{#1}}}
\newcommand{\vars}[2]{\var_{{#1}}\sbr{{#2}}}
\newcommand{\expec}[2]{\mathop{\EE}_{{#1}}\sbr{{#2}}}

\newcommand{\twoco}[1]{\multicolumn{2}{c|}{#1}}
\def\ci{\perp\!\!\!\perp}

\newcommand{\ve}{\varepsilon}

\newcommand{\gstar}{g^{\star}}
\newcommand{\fstar}{f^{\star}}
\newcommand{\hstar}{h^{\star}}
\newcommand{\Astar}{A^{\star}}
\newcommand{\Kstar}{K^{\star}}

\newcommand{\var}{\mathrm{Var}}
\newcommand{\grad}{{\nabla}}
\newcommand{\gradtil}{{\tilde{\grad}}}
\newcommand{\MED}{{\text{MED}}}
\newcommand{\where}{{\quad \text{where} \quad}}
\newcommand{\lcg}{{\textit{l.c.g}}}
\newcommand{\cp}{\mathrm{cp}}
\newcommand{\err}{{\sf err}}
\newcommand{\wvechat}{\hat{\vec{w}}}

\newcommand{\ydiff}[2]{\delta(#1, #2)}
\newcommand{\ykdiff}[2]{\delta(#1, #2)^{\kappa}}
\newcommand{\myfdiff}[2]{\Delta f(#1, #2)}


\newcommand{\Aone}{\textbf{A1}}
\newcommand{\Atwo}{\textbf{A2}}

robirank.tex
\documentclass{article} % For LaTeX2e
\usepackage{nips14submit_e}
%\usepackage[colorlinks,linkcolor=red,citecolor=blue,urlcolor=blue,draft]{hyperref}
\usepackage{times}
\usepackage[sort&compress,numbers]{natbib}
\usepackage{amsmath}
\usepackage{graphicx}
\usepackage{url}

\usepackage{algorithm}
\usepackage{algorithmic}

\usepackage{etoolbox}
\newcommand{\algorithmicdoinparallel}{\textbf{do in parallel}}
\makeatletter
\AtBeginEnvironment{algorithmic}{%
  \newcommand{\FORALLP}[2][default]{\textbf{for all machine} #2\ %
    \algorithmicdoinparallel\ALC@com{#1}\begin{ALC@for}}%
}

\usepackage{tabularx}
\usepackage{mdwlist}

\usepackage{tikz}
\usetikzlibrary{positioning,patterns,shapes}
\usepackage{pgfplots}
\usepgfplotslibrary{external}
\tikzexternalize
%\tikzexternalize[shell escape=-enable-write18]
\usepackage{multirow}
\usepackage{rotating}
\input{./Definitions}

\newcommand{\trank}{\text{rank}}
\newcommand{\otrank}{\overline{\text{rank}}}

\title{Ranking via Robust Binary Classification}

\author{
%David S.~Hippocampus\thanks{ Use footnote for providing further information
%about author (webpage, alternative address)---\emph{not} for acknowledging
%funding agencies.} \\
Hyokun Yun \\
Department of Statistics\\
Purdue University\\
West Lafayette, IN 47907 \\
\texttt{yun3@purdue.edu} \\
\And
Parameswaran Raman \\
Department of Computer Science \\
Purdue University \\
West Lafayette, IN 47907 \\
\texttt{params@purdue.edu} \\
\And
S.~V.~N.~Vishwanathan\\
Departments of Statistics and Computer Science\\
Purdue University \\
West Lafayette, IN 47907 \\
\texttt{vishy@stat.purdue.edu} \\
}

\newcommand{\fix}{\marginpar{FIX}}
\newcommand{\new}{\marginpar{NEW}}

\nipsfinalcopy % Uncomment for camera-ready version

\begin{document}


\maketitle

\begin{abstract}
  We propose RoBiRank, a ranking algorithm that is motivated by
  observing a close connection between evaluation metrics for learning
  to rank and loss functions for robust classification.  It shows
  competitive performance on standard benchmark datasets against a
  number of other representative algorithms in the literature.  We also
  discuss extensions of RoBiRank to large scale problems where explicit
  feature vectors and scores are not given. We show that RoBiRank can be
  efficiently parallelized across a large number of machines; for a task
  that requires $386,133 \times 49,824,519$ pairwise interactions
  between items to be ranked, RoBiRank finds solutions that are of
  dramatically higher quality than that can be found by a
  state-of-the-art competitor algorithm, given the same amount of
  wall-clock time for computation.
\end{abstract}

\section{Introduction}
\label{sec:Introduction}

Learning to rank is a problem of ordering a set of items according to
their relevances to a given context \citep{ChaCha11}.  While a number of
approaches have been proposed in the literature, in this paper we
provide a new perspective by showing a close connection between ranking
and a seemingly unrelated topic in machine learning, namely, robust
binary classification.

In robust classification \citep{Huber81}, we are asked to learn a
classifier in the presence of outliers.  Standard models for
classification such as Support Vector Machines (SVMs) and logistic
regression do not perform well in this setting, since the convexity of
their loss functions does not let them give up their performance on any
of the data points \citep{LonSer10}; for a classification model to be
robust to outliers, it has to be capable of sacrificing its performance
on some of the data points.  We observe that this requirement is very
similar to what standard metrics for ranking try to evaluate.
Discounted Cumulative Gain (DCG) \citep{ManRagSch08} and its normalized
version NDCG, popular metrics for learning to rank, strongly emphasize
the performance of a ranking algorithm at the top of the list;
therefore, a good ranking algorithm in terms of these metrics has to be
able to give up its performance at the bottom of the list if that can
improve its performance at the top.

In fact, we will show that DCG and NDCG can indeed be written as a
natural generalization of robust loss functions for binary
classification.  Based on this observation we formulate RoBiRank, a
novel model for ranking, which maximizes the lower bound of (N)DCG.
Although the non-convexity seems unavoidable for the bound to be tight
\citep{ChaDoTeoLeSmo08}, our bound is based on the class of robust loss
functions that are found to be empirically easier to optimize
\citep{Ding13}.  Indeed, our experimental results suggest that RoBiRank
reliably converges to a solution that is competitive as compared to
other representative algorithms even though its objective function is
non-convex.

While standard deterministic optimization algorithms such as L-BFGS
\citep{NocWri06} can be used to estimate parameters of RoBiRank, to
apply the model to large-scale datasets a more efficient parameter
estimation algorithm is necessary.  This is of particular interest in
the context of latent collaborative retrieval \citep{WesWanWeiBer12};
unlike standard ranking task, here the number of items to
rank is very large and explicit feature vectors and scores are not
given.

Therefore, we develop an efficient parallel stochastic optimization
algorithm for this problem.  It has two very attractive
characteristics: First, the time complexity of each stochastic update
is independent of the size of the dataset.  Also, when the algorithm
is distributed across multiple number of machines, no interaction
between machines is required during most part of the execution;
therefore, the algorithm enjoys near linear scaling.  This is a
significant advantage over serial algorithms, since it is very easy to
deploy a large number of machines nowadays thanks to the popularity of
cloud computing services, e.g.\ Amazon Web Services.

We apply our algorithm to latent collaborative retrieval task on Million
Song Dataset \citep{BerEllWhiLam13} which consists of 1,129,318 users,
386,133 songs, and 49,824,519 records; for this task, a ranking
algorithm has to optimize an objective function that consists of
$386,133 \times 49,824,519$ number of pairwise interactions.  With the
same amount of wall-clock time given to each algorithm, RoBiRank
leverages parallel computing to outperform the state-of-the-art with a
100\% lift on the evaluation metric.

\section{Robust Binary Classification}
\label{sec:binary_loss}

% We view ranking as an extension of robust binary classification, and
% will adopt strategies for designing loss functions and optimization
% techniques from it.  Therefore, we start by reviewing some relevant
% concepts and techniques.

Suppose we are given training data which consists of $n$ data points
$(x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n)$, where each $x_i \in \RR^d$
is a $d$-dimensional feature vector and $y_i \in \cbr{-1, +1}$ is a
label associated with it.  A linear model attempts to learn a
$d$-dimensional parameter $\omega$, and for a given feature vector $x$
it predicts label $+1$ if $\inner{x}{\omega} \geq 0$ and $-1$ otherwise.
Here $\inner{\cdot}{\cdot}$ denotes the Euclidean dot product between
two vectors.  The quality of $\omega$ can be measured by the number of
mistakes it makes:
% \begin{align}
$L(\omega) := \sum_{i=1}^n I (y_i \cdot \inner{x_i}{\omega} < 0)$.
%   \label{eq:binary_obj}
% \end{align}
The indicator function $I(\cdot < 0)$ is called the 0-1 loss function,
because it has a value of 1 if the decision rule makes a mistake, and 0
otherwise.  Unfortunately, since the 0-1 loss is a discrete function its
minimization is difficult~\citep{FelGurRagWu12}.  The most popular
solution to this problem in machine learning is to upper bound the 0-1
loss by an easy to optimize function \citep{JorBarMcA06}.  For example,
logistic regression uses the logistic loss function
%\begin{align*}
$\sigma_0(t) := \log_2(1 + 2^{-t})$,
%\end{align*}
to come up with a continuous and convex objective function
\begin{align}
  \overline{L}(\omega) := \sum_{i=1}^n \sigma_0(y_i \cdot
  \inner{x_i}{\omega}),
  \label{eq:logistic_obj}
\end{align}
which upper bounds $L(\omega)$.  It is clear that for each $i$,
$\sigma_0(y_i \cdot \inner{x_i}{\omega})$ is a convex function in
$\omega$; therefore, $\overline{L}(\omega)$, a sum of convex
functions, is also a convex function which is relatively easier to
optimize \citep{BoyVan04}.  Support Vector Machines (SVMs) on the
other hand can be recovered by using the hinge loss to upper bound the
0-1 loss.

% In a
% similar vein, Support Vector Machines (SVMs), another popular approach
% in machine learning, replace the 0-1 loss by the hinge loss.
% Figure~\ref{fig:loss_funcs} (left) graphically illustrates three loss
% functions discussed here.

% \begin{figure*}
%   \begin{center}
%     \begin{tikzpicture}[scale=0.65]
%       \begin{axis}[%title={Convex Upper Bounds of 0-1 Loss},
%         legend style={
%           cells={anchor=east},
%           legend pos=north east,
%         },
%         cycle list name=linestyles,
%         no markers,
%         xlabel=margin,
%         ylabel=loss
%         ]

%         \addplot+[domain={-3:3}, samples=100, ultra thick]
%         {1 - (abs(x)/x + 1)/2};

%         \addplot+[domain={-3:3}, samples=100, ultra thick]
%         {max(1-x,0)};

%         \addplot+[domain={-3:3}, samples=100, ultra thick]
%         {ln(1+2^(-x))/ln(2)};
        
%         \legend{0-1 loss, hinge loss, logistic loss}

%       \end{axis}
%     \end{tikzpicture}
%     \begin{tikzpicture}[scale=0.65]
%       \begin{axis}[
%         legend style={
%           cells={anchor=east},
%           legend pos=north west,
%         },
%         cycle list name=linestyles,
%         no markers,
%         xlabel=$t$,
%         ylabel=function value
%         ]

%         \addplot+[domain={0:5}, samples=100, ultra thick]
%         {x};

%         \addplot+[domain={0:5}, samples=100, ultra thick]
%         {ln(x+1)/ln(2)};

%         \addplot+[domain={0:5}, samples=100, ultra thick]
%         {1.0 - ln(2) / ln(x + 2)};

%         \legend{identity, $\rho_1(t)$, $\rho_2(t)$}

%       \end{axis}
%     \end{tikzpicture}
%     \begin{tikzpicture}[scale=0.65]
%       \begin{axis}[
%         legend style={
%           cells={anchor=east},
%           legend pos=north east,
%         },
%         cycle list name=linestyles,
%         no markers,
%         xlabel=$t$,
%         ylabel=loss
%         ]

%         \addplot+[domain={-5:5}, samples=100, ultra thick]
%         {ln(1+2^(-x))/ln(2)};

%         \addplot+[domain={-5:5}, samples=100, ultra thick]
%         {ln(ln(1+2^(-x))/ln(2)+1)/ln(2)};

%         \addplot+[domain={-5:5}, samples=100, ultra thick]
%         {1.0 - ln(2) / ln(ln(1+2^(-x))/ln(2)+2) };

%         \legend{$\sigma_0(t)$,$\sigma_1(t)$,$\sigma_2(t)$}

%       \end{axis}
%     \end{tikzpicture}
%   \end{center}
%   \caption{
%     Left: Convex Upper Bounds for 0-1 Loss.
%     Middle:
%     Transformation functions for constructing robust losses.
%     Right:
%     Logistic loss and its transformed robust variants.
%     }
%   \label{fig:loss_funcs}
% \end{figure*}

However, convex upper bounds such as $\overline{L}(\omega)$ are known to
be sensitive to outliers \citep{LonSer10}.  The basic intuition here is
that when $y_i \cdot \inner{x_i}{\omega}$ is a very large negative
number for some data point $i$, $\sigma(y_i \cdot \inner{x_i}{\omega})$
is also very large, and therefore the optimal solution of
\eqref{eq:logistic_obj} will try to decrease the loss on such outliers
at the expense of its performance on ``normal'' data points.

In order to construct robust loss functions, consider the following two
transformation functions:
\begin{align}
  \rho_1(t) := \log_2(t + 1), \;\; \rho_2(t) := 1 - \frac 1 {\log_2(t +
    2)},
  \label{eq:transforms}
\end{align}
which, in turn, can be used to define the following loss functions:
\begin{align}
  \sigma_1(t) &:= \rho_1(\sigma_0(t)), \;\; \sigma_2(t) :=
  \rho_2(\sigma_0(t)). \label{robust_losses}
\end{align}
% Figure~\ref{fig:loss_funcs} (middle) shows these transformation
% functions graphically, and Figure~\ref{fig:loss_funcs} (right) contrasts
% the derived loss functions with logistic loss.  
One can see that $\sigma_1(t) \rightarrow \infty$ as $t \rightarrow
-\infty$, but at a much slower rate than $\sigma_0(t)$ does; its
derivative $\sigma'_1(t) \rightarrow 0$ as $t \rightarrow -\infty$.
Therefore, $\sigma_1(\cdot)$ does not grow as rapidly as $\sigma_0(t)$
on hard-to-classify data points.  Such loss functions are called Type-I
robust loss functions by \citet{Ding13}, who also showed that they enjoy
statistical robustness properties.  $\sigma_2(t)$ behaves even better:
$\sigma_2(t)$ converges to a constant as $t \rightarrow -\infty$, and
therefore ``gives up'' on hard to classify data points.  Such loss
functions are called Type-II loss functions, and they also enjoy
statistical robustness properties \citep{Ding13}.

In terms of computation, of course, $\sigma_1(\cdot)$ and
$\sigma_2(\cdot)$ are not convex, and therefore the objective function
based on such loss functions is more difficult to optimize.  However, it
has been observed in \citet{Ding13} that models based on optimization of
Type-I functions are often empirically much more successful than those
which optimize Type-II functions.  Furthermore, the solutions of Type-I
optimization are more stable to the choice of parameter
initialization. Intuitively, this is because Type-II functions asymptote
to a constant, reducing the gradient to almost zero in a large
fraction of the parameter space; therefore, it is difficult for a
gradient-based algorithm to determine which direction to pursue. See
\citet{Ding13} for more details. 

\section{Ranking Model via Robust Binary Classification}
\label{sec:RankingLoss}

% In this section, we will extend robust binary classification to
% formulate RoBiRank, a novel model for ranking.

% \subsection{Problem Setting}
% \label{sec:NotatPrel}

Let $\Xcal = \cbr{x_1, x_2, \ldots, x_n }$ be a set of contexts, and
$\Ycal = \cbr{y_1, y_2, \ldots, y_m }$ be a set of items to be ranked.
For example, in movie recommender systems $\Xcal$ is the set of users
and $\Ycal$ is the set of movies.  In some problem settings, only a
subset of $\Ycal$ is relevant to a given context $x \in \Xcal$;
e.g. in document retrieval systems, only a subset of documents is
relevant to a query.  Therefore, we define $\Ycal_x \subset \Ycal$ to
be a set of items relevant to context $x$.  Observed data can be
described by a set $W := \cbr{ W_{xy} }_{x \in \Xcal, y \in \Ycal_x}$
where $W_{xy}$ is a real-valued score given to item $y$ in context
$x$.

We adopt a standard problem setting used in the literature of learning
to rank.  For each context $x$ and an item $y \in \Ycal_x$, we aim to
learn a scoring function $f(x,y): \Xcal \times \Ycal_x \rightarrow \RR$
that induces a ranking on the item set $\Ycal_x$; the higher the score,
the more important the associated item is in the given context.  To
learn such a function, we first extract joint features of $x$ and $y$,
which will be denoted by $\phi(x,y)$.  Then, we parametrize $f(\cdot,
\cdot)$ using a parameter $\omega$, which yields the linear model
$f_\omega(x,y) := \inner{\phi(x,y)}{\omega}$, where, as before,
$\inner{\cdot}{\cdot}$ denotes the Euclidean dot product between two
vectors.  $\omega$ induces a ranking on the set of items $\Ycal_x$; we
define $\trank_\omega(x,y)$ to be the rank of item $y$ in a given
context $x$ induced by $\omega$.  Observe that $\trank_\omega(x,y)$ can
also be written as a sum of 0-1 loss functions (see e.g.\
\citet{UsuBufGal09}):
\begin{align}
  \trank_\omega(x,y) = \mkern-18mu \sum_{y' \in \Ycal_x, y' \neq y}
  \mkern-18mu I\rbr{f_\omega(x,y) - f_\omega(x,y') < 0}.
  \label{eq:rank_as_sum}
\end{align}


\subsection{Basic Model}
\label{ssec:basic_model}

If an item $y$ is very relevant in context $x$, a good parameter
$\omega$ should position $y$ at the top of the list; in other words,
$\trank_\omega(x,y)$ has to be small, which motivates the following
objective function:
\begin{align}
  L(\omega) := \sum_{x \in \Xcal} c_x \sum_{y \in \Ycal_x} v(W_{xy})
  \cdot \trank_\omega(x,y),
  \label{eq:basic_loss}
\end{align}
where $c_x$ is an weighting factor for each context $x$, and $v(\cdot):
\RR^+ \rightarrow \RR^+$ quantifies the relevance level of $y$ on $x$.
Note that $\cbr{c_x}$ and $v(W_{xy})$ can be chosen to reflect the
metric the model is going to be evaluated on (this will be discussed in
Section~\ref{ssec:ndcg}).  Note that \eqref{eq:basic_loss} can be
rewritten using \eqref{eq:rank_as_sum} as a sum of indicator functions.
Following the strategy in Section~\ref{sec:binary_loss}, one can form an
upper bound of \eqref{eq:basic_loss} by bounding each 0-1 loss function
by a logistic loss function:
\begin{align}
  \overline{L}(\omega) := \sum_{x \in \Xcal} &c_x \sum_{y \in \Ycal_x}
  v\rbr{W_{xy}} \cdot \sum_{y' \in \Ycal_x, y' \neq y}
  \sigma_0\rbr{f_\omega(x,y) - f_\omega(x,y')}.
  \label{eq:bound_basic_loss}
\end{align}
Just like \eqref{eq:logistic_obj}, \eqref{eq:bound_basic_loss} is
convex in $\omega$ and hence easy to minimize.  

% Note that \eqref{eq:bound_basic_loss} can be viewed as a weighted
% version of binary logistic regression \eqref{eq:logistic_obj}; each
% $(x,y,y')$ triple which appears in \eqref{eq:bound_basic_loss} can be
% regarded as a data point in a logistic regression model with
% $\phi(x,y) - \phi(x,y')$ being its feature vector.  The weight given
% on each data point is $c_x \cdot v(W_{xy})$. This idea underlies many
% pairwise ranking models. %  (also see Section~\ref{sec:RelatedWork}). 

\subsection{DCG}
\label{ssec:ndcg}

Although \eqref{eq:bound_basic_loss} enjoys convexity, it may not be a
good objective function for ranking.  This is because in most
applications of learning to rank, it is more important to do well at the
top of the list than at the bottom, as users typically pay attention
only to the top few items.  Therefore, it is desirable to \emph{give up}
performance on the lower part of the list in order to gain quality at
the top.  This intuition is similar to that of robust classification in
Section~\ref{sec:binary_loss}; a stronger connection will be shown
below.

Discounted Cumulative Gain (DCG)~\citep{ManRagSch08} is one of the most
popular metrics for ranking.  For each context $x \in \Xcal$, it is
defined as:
\begin{align}
  \text{DCG}(\omega) := c_x 
  \sum_{y \in \Ycal_x}
  \frac{v\rbr{W_{xy}}}{\log_2\rbr{\trank_\omega(x,y) + 2}},
  \label{eq:gen_metric}
\end{align}
where $v(t) = 2^t - 1$ and $c_x = 1$. Since $1/\log(t + 2)$ decreases
quickly and then asymptotes to a constant as $t$ increases, this metric
emphasizes the quality of the ranking at the top of the list.
Normalized DCG (NDCG) simply normalizes the metric to bound it between 0
and 1 by calculating the maximum achievable DCG value $m_x$ and dividing
by it \citep{ManRagSch08}.
% \begin{align}
%   \text{NDCG}_x(\omega) := 
%   \frac 1 {m_x}
%   \sum_{y \in \Ycal_x}
%   \frac{2^{W_{xy}} - 1}{\log_2\rbr{\trank_\omega(x,y) + 2}}.
% \end{align}
% DCG can be written in a general form as:
% \begin{align}
%   c_x 
%   \sum_{y \in \Ycal_x}
%   \frac{v\rbr{W_{xy}}}{\log_2\rbr{\trank_\omega(x,y) + 2}}.
%   \label{eq:gen_metric}
% \end{align}
% By setting $v(t) = 2^t - 1$ and $c_x = 1$, we recover DCG.  
% With $c_x
% = 1/m_x$, on the other hand, we get NDCG.

\subsection{RoBiRank}

Now we formulate RoBiRank, which optimizes the lower bound of metrics
for ranking in form \eqref{eq:gen_metric}.  Observe
that $\max_{\omega} \text{DCG} (\omega)$ can be rewritten as 
\begin{align}
  \min_\omega \sum_{x \in \Xcal} c_x \sum_{y \in \Ycal_x} v\rbr{W_{xy}}
  \cdot \cbr{ 1 - \frac{1}{\log_2\rbr{\trank_\omega(x,y) + 2}} }
  \label{eq:to_opt}.
\end{align}
Using \eqref{eq:rank_as_sum} and the definition of the transformation
function $\rho_2(\cdot)$ in \eqref{eq:transforms}, we can rewrite
the objective function in \eqref{eq:to_opt} as:
\begin{align}
  L_2(\omega) := \sum_{x \in \Xcal} c_x \sum_{y \in \Ycal_x}
  v\rbr{W_{xy}} \cdot \rho_2 \rbr{ \sum_{y' \in \Ycal_x, y' \neq y}
    I\rbr{f_\omega(x,y) - f_\omega(x,y') < 0}}.
  \label{eq:rankloss_2}
\end{align}

Since $\rho_2(\cdot)$ is a monotonically increasing function, we can
bound \eqref{eq:rankloss_2} with a continuous function by bounding
each indicator function using the logistic loss:
\begin{align}
  \overline{L}_2(\omega) := \sum_{x \in \Xcal} c_x \sum_{y \in \Ycal_x}
  v\rbr{W_{xy}} \cdot \rho_2 \rbr{ \sum_{y' \in \Ycal_x, y' \neq y}
    \sigma_0\rbr{f_\omega(x,y) - f_\omega(x,y')}}.
  \label{eq:rankloss_2_bd}
\end{align}
This is reminiscent of the basic model in \eqref{eq:bound_basic_loss};
as we applied the transformation function $\rho_2(\cdot)$ on the
logistic loss function $\sigma_0(\cdot)$ to construct the robust loss
function $\sigma_2(\cdot)$ in \eqref{robust_losses}, we are again
applying the same transformation on \eqref{eq:bound_basic_loss} to
construct a loss function that respects the DCG metric used in ranking.
In fact, \eqref{eq:rankloss_2_bd} can be seen as a generalization of
robust binary classification by applying the transformation on a
\emph{group} of logistic losses instead of a single logistic loss.  In
both robust classification and ranking, the transformation
$\rho_2(\cdot)$ enables models to give up on part of the problem to
achieve better overall performance.

As we discussed in Section~\ref{sec:binary_loss}, however,
transformation of logistic loss using $\rho_2(\cdot)$ results in
Type-II loss function, which is very difficult to optimize.  Hence,
instead of $\rho_2(\cdot)$ we use an alternative transformation
function $\rho_1(\cdot)$, which generates Type-I loss function, to
define the objective function of RoBiRank:
\begin{align}
  \overline{L}_1(\omega) := \sum_{x \in \Xcal} c_x \sum_{y \in \Ycal_x}
  v\rbr{W_{xy}} \cdot \rho_1 \rbr{ \sum_{y' \in \Ycal_x, y' \neq y}
    \sigma_0\rbr{f_\omega(x,y) - f_\omega(x,y')}}.
  \label{eq:rankloss_1_bd}
\end{align}
Since $\rho_1(t) \geq \rho_2(t)$ for every $t > 0$, we have
$\overline{L}_1(\omega) \geq \overline{L}_2(\omega) \geq L_2(\omega)$
for every $\omega$. Note that $\overline{L}_1(\omega)$ is continuous and
twice differentiable.  Therefore, standard gradient-based optimization
techniques can be applied to minimize it. As is standard, a regularizer
on $\omega$ can be added to avoid overfitting; for simplicity, we use
the $\ell_2$-norm in our experiments.

\subsection{Standard Learning to Rank Experiments}
\label{sec:SmallItemSet}


We conducted experiments to check the performance of the objective
function \eqref{eq:rankloss_1_bd} in a standard learning to rank
setting, with a small number of labels to rank. We pitch RoBiRank
against the following algorithms: RankSVM \citep{LeeLin13}, the ranking
algorithm of \citet{LeSmo07} (called LSRank in the sequel), InfNormPush
\citep{Rudin09}, IRPush \citep{Aga11}, and 8 standard ranking algorithms
implemented in
RankLib\footnote{http://sourceforge.net/p/lemur/wiki/RankLib} namely
MART, RankNet, RankBoost, AdaRank, CoordAscent, LambdaMART, ListNet and
RandomForests.
% We will try to answer the following questions:
% \begin{itemize*}
% \item What is the benefit of transforming a convex loss function
%   \eqref{eq:bound_basic_loss} into a non-covex loss function
%   \eqref{eq:rankloss_1_bd}?  To answer this, we compare our algorithm
%   against RankSVM \citep{LeeLin13}, which uses a formulation that is
%   very similar to \eqref{eq:bound_basic_loss}, and is a
%   state-of-the-art pairwise ranking algorithm. 
% \item How does our non-convex upper bound on negative NDCG compare
%   against other convex relaxations? As a representative comparator we
%   use the algorithm of \citet{LeSmo07}, mainly because their code is
%   freely available for download.  We will call their algorithm LSRank
%   in the sequel.
% \item How does our formulation compare with the ones used in other popular 
%   algorithms such as LambdaMART, RankNet, etc? In order to answer this question, we carry out detailed experiments
%   comparing RoBiRank with 12 different algorithms. In Figure~\ref{fig:ndcg_all} RoBiRank
%   is compared against RankSVM, LSRank, InfNormPush \citep{Rudin09} and IRPush \citep{Aga11}. We then downloaded RankLib \footnote{http://sourceforge.net/p/lemur/wiki/RankLib} and used its default settings to compare
%   against 8 standard ranking algorithms (see Figure\ref{fig:ndcg_all_ranklib}) - 
%   MART, RankNet, RankBoost, AdaRank, CoordAscent, LambdaMART, ListNet and RandomForests. 
% \item Since we are optimizing a non-convex objective function, we will
%   verify the sensitivity of the optimization algorithm to the choice of
%   initialization parameters. 
% \end{itemize*}
We use three sources of datasets: LETOR 3.0 \citep{ChaCha11} , LETOR
4.0\footnote{http://research.microsoft.com/en-us/um/beijing/projects/letor/letor4dataset.aspx}
and YAHOO LTRC \citep{QinLiuXuLi10}, which are standard benchmarks for
learning to rank algorithms. Table~\ref{tb:descriptives} shows their
summary statistics.  Each dataset consists of five folds; we consider
the first fold, and use the training, validation, and test splits
provided. We train with different values of the regularization
parameter, and select a parameter with the best NDCG value on the
validation dataset.  The performance of the model with this parameter on
the test dataset is reported. 
% For a fair comparison, every algorithm
% follows exactly the same protocol and uses the same split of data. All
% experiments in this section are conducted on a computing cluster where
% each node has two 2.1 GHz 12-core AMD 6172 processors with 48 GB
% physical memory per node. 
We used an optimized implementation of the L-BFGS algorithm provided by
the Toolkit for Advanced Optimization
(TAO)\footnote{http://www.mcs.anl.gov/research/projects/tao/index.html}
for estimating the parameter of RoBiRank.  For the other algorithms, we
either implemented them using our framework or used the implementations
provided by the authors. 

% Our main goal is to compare the performance of
% the models, and not the speed of parameter estimation. However, we note
% that the training time is very comparable for all three algorithms, with
% RoBiRank being at most two to three times slower than other algorithms
% on some datasets.

\begin{figure*}[htbp]
  \centering
  \begin{tikzpicture}[scale=0.65]
    \begin{axis}[minor tick num=1,
      title={TD 2004},
      xlabel={k}, ylabel={NDCG@k},
      xmin={1}, xmax={20}, ymin={0.4}, ymax={1.0}]
      
      \addplot[ultra thick, color=blue, mark=*] table [x index=0, y index=1, header=true]
      {./Plots/td2004_all.txt};
      
      \addplot[ultra thick, color=red, mark=x] table [x index=0, y index=2, header=true]
      {./Plots/td2004_all.txt};
      
      \addplot[ultra thick, color=black, mark=o] table [x index=0, y index=3, header=true]
      {./Plots/td2004_all.txt};
      
      \addplot[ultra thick, color=green, mark=square] table [x index=0, y index=4, header=true]
      {./Plots/td2004_all.txt};
      
      \addplot[ultra thick, color=teal, mark=triangle] table [x index=0, y index=5, header=true]
      {./Plots/td2004_all.txt};
      \legend{RoBiRank, RankSVM, LSRank, InfNormPush, IRPush}
    \end{axis}
  \end{tikzpicture}
  \begin{tikzpicture}[scale=0.65]
    \begin{axis}[minor tick num=1,
      title={TD 2004},
      xlabel={k}, ylabel={NDCG@k},
      xmin={1}, xmax={20}, ymin={0.4}, ymax={1.0}]
      
      \addplot[ultra thick, color=blue, mark=*] table [x index=0, y index=1, header=true]
      {./Plots/td2004_all.txt};

      \addplot[ultra thick, color=brown, mark=square] table [x index=0, y index=6, header=true]
      {./Plots/td2004_all.txt};
      
      \addplot[ultra thick, color=magenta, mark=square*] table [x index=0, y index=7, header=true]
      {./Plots/td2004_all.txt};

      \addplot[ultra thick, color=yellow, mark=triangle] table [x index=0, y index=8, header=true]
      {./Plots/td2004_all.txt};

      \addplot[ultra thick, color=cyan, mark=triangle*] table [x index=0, y index=9, header=true]
      {./Plots/td2004_all.txt};

      \addplot[ultra thick, color=lime, mark=diamond] table [x index=0, y index=9, header=true]
      {./Plots/td2004_all.txt};

      \addplot[ultra thick, color=olive, mark=diamond*] table [x index=0, y index=9, header=true]
      {./Plots/td2004_all.txt};

      \addplot[ultra thick, color=violet , mark=+] table [x index=0, y index=9, header=true]
      {./Plots/td2004_all.txt};

      \addplot[ultra thick, color=purple, mark=o] table [x index=0, y index=9, header=true]
      {./Plots/td2004_all.txt};
      \legend{RoBiRank, MART, RankNet, RankBoost, AdaRank, CoordAscent, LambdaMART, ListNet, RandomForests}      
    \end{axis}
  \end{tikzpicture}  
  \caption{Comparison of RoBiRank with a number of competing
    algorithms. Plots are split into two for ease of visualization}
  \label{fig:ndcg_all}
\end{figure*}


We use values of NDCG at different levels of truncation as our
evaluation metric \citep{ManRagSch08}; see Figure~\ref{fig:ndcg_all}.
RoBiRank outperforms its competitors on most of the datasets, however,
due to space constraints we only present plots for the TD 2004 dataset
in the main body of the paper.  Other plots can be found in
Appendix~\ref{sec:AdditPlotsLearn}. The performance of RankSVM seems
insensitive to the level of truncation for NDCG. On the other hand,
RoBiRank, which uses non-convex loss function to concentrate its
performance at the top of the ranked list, performs much better
especially at low truncation levels.  It is also interesting to note
that the NDCG@k curve of LSRank is similar to that of RoBiRank, but
RoBiRank consistently outperforms at each level. RoBiRank dominates
Inf-Push and IR-Push at all levels. When compared to standard
algorithms, Figure~\ref{fig:ndcg_all} (right), again RoBiRank
outperforms especially at the top of the list. 

Overall, RoBiRank outperforms IRPush and InfNormPush on all datasets
except TD 2003 and OHSUMED where IRPush seems to fare better at the top
of the list. Compared to the 8 standard algorithms, again RobiRank
either outperforms or performs comparably to the best algorithm except
on two datasets (TD 2003 and HP 2003), where MART and Random Forests
overtake RobiRank at few values of NDCG. We present a summary of the
NDCG values obtained by each algorithm in Table~\ref{tb:descriptives} in
the appendix. On the MSLR30K dataset, some of the additional algorithms
like InfNormPush and IRPush did not complete within the time period
available; indicated by dashes in the table.

% We conjecture that this is due to the tightness of the
% RoBiRank bound of the NDCG.
% Next, we investigate the sensitivity of the algorithm to the choice of
% initialization. Towards this end, 

% In the MSLR dataset (Figure~\ref{fig:error_td2004} in the Appendix), despite the large number of queries and instances, RoBiRank still manages to outperform its competitors and it follows a trend as expected; having a higher NDCG@1 score, which provides an evidence that it focusses on the most important documents.



\section{Latent Collaborative Retrieval}

% \subsection{Model Formulation}

For each context $x$ and an item $y \in \Ycal$, the standard problem
setting of learning to rank requires training data to contain feature
vector $\phi(x,y)$ and score $W_{xy}$ assigned on the $x,y$ pair.  When
the number of contexts $\abr{\Xcal}$ or the number of items
$\abr{\Ycal}$ is large, it might be difficult to define $\phi(x,y)$ and
measure $W_{xy}$ for all $x,y$ pairs.  Therefore, in most learning to
rank problems we define the set of \emph{relevant} items $\Ycal_x
\subset \Ycal$ to be much smaller than $\Ycal$ for each context $x$, and
then collect data only for $\Ycal_x$.  Nonetheless, this may not be
realistic in all situations; in a movie recommender system, for example,
for each user \emph{every} movie is somewhat relevant. % to her.

On the other hand, implicit user feedback data is much more abundant.
For example, a lot of users on Netflix would simply watch movie streams
on the system but do not leave an explicit rating.  By the action of
watching a movie, however, they implicitly express their preference.
Such data consist only of positive feedback, unlike traditional learning
to rank datasets which have score $W_{xy}$ between each context-item
pair $x,y$.  Again, we may not be able to extract feature vectors for
each $x,y$ pair.

In such a situation, we can attempt to learn the score function $f(x,y)$
without a feature vector $\phi(x,y)$ by embedding each context and item
in an Euclidean latent space; specifically, we redefine the score
function to be: $f(x,y) := \inner{U_x}{V_y}$, where $U_x \in \RR^d$ is
the embedding of the context $x$ and $V_y \in \RR^d$ is that of the item
$y$.  Then, we can learn these embeddings by a ranking model.  This
approach was introduced in \citet{WesWanWeiBer12}, and was called
\emph{latent collaborative retrieval}.

Now we specialize RoBiRank model for this task.  Let us define
$\Omega$ to be the set of context-item pairs $(x,y)$ which was
observed in the dataset.  Let $v(W_{xy}) = 1$ if $(x,y) \in \Omega$,
and $0$ otherwise; this is a natural choice since the score
information is not available.  For simplicity, we set $c_x = 1$ for
every $x$.  Now RoBiRank~\eqref{eq:rankloss_1_bd} specializes to:
\begin{align}
  \overline{L}_{1}(U, V) = \sum_{(x,y) \in \Omega}
  \rho_1 \rbr{\sum_{y' \neq y}
    \sigma_0(f(U_x,V_y) - f(U_x, V_{y'}))}.
  \label{eq:latent_obj}
\end{align}
Note that now the summation inside the parenthesis of
\eqref{eq:latent_obj} is over all items $\Ycal$ instead of a smaller set
$\Ycal_x$, therefore we omit specifying the range of $y'$ from now
on. To avoid overfitting, a regularizer is added to
\eqref{eq:latent_obj}; for simplicity we use the Frobenius norm of $U$
and $V$ in our experiments.

\subsection{Stochastic Optimization}
\label{ssec:sto_opt}

When the size of the data $\abr{\Omega}$ or the number of items
$\abr{\Ycal}$ is large, however, methods that require exact evaluation
of the function value and its gradient will become very slow since the
evaluation takes $O\rbr{\abr{\Omega} \cdot \abr{\Ycal} }$ computation.
In this case, stochastic optimization methods are desirable
\citep{BotBou11}; in this subsection, we will develop a stochastic
gradient descent algorithm whose complexity is independent of
$\abr{\Omega}$ and $\abr{\Ycal}$.

For simplicity, let $\theta$ be a concatenation of all parameters
$\cbr{U_x}_{x \in \Xcal}$, $\cbr{V_y}_{y \in \Ycal}$.  The gradient
$\nabla_\theta L_1(U,V)$ of \eqref{eq:latent_obj} is
\begin{align*}
  % \nabla_\theta L_1&(U,V) := \nonumber \\
  % &
  \sum_{(x,y) \in \Omega}
  \nabla_\theta
  \rho_1 \rbr{\sum_{y' \neq y}
    \sigma_0(f(U_x,V_y) - f(U_x, V_{y'}))}.
  %\label{eq:latent_grad}
\end{align*}
Finding an unbiased estimator of the gradient
% \eqref{eq:latent_grad} 
whose computation is independent of $\abr{\Omega}$ is not difficult;
if we sample a pair $(x,y)$ uniformly from $\Omega$, then it is easy
to see that the following estimator
\begin{align}
  \abr{\Omega} \cdot 
  \nabla_\theta
  \rho_1 \rbr{\sum_{y' \neq y}
    \sigma_0(f(U_x,V_y) - f(U_x, V_{y'}))}
  \label{eq:simple_sg}
\end{align}
is unbiased.  This still involves a summation over $\Ycal$, however,
so it requires $O(\abr{\Ycal})$ calculation.  Since $\rho_1(\cdot)$ is
a nonlinear function it seems unlikely that an unbiased stochastic
gradient which randomizes over $\Ycal$ can be found; nonetheless, to
achieve convergence guarantees of the stochastic gradient
descent algorithm, unbiasedness of the estimator is necessary
\citep{NemJudLanSha09}.

We attack this problem by \emph{linearizing} the objective function by
parameter expansion.  Note the following property of $\rho_1(\cdot)$
\citep{Bouchard07}: 
\begin{align}
  \rho_1(t) = \log_2(t+1) 
  \leq 
  - \log_2 \xi + \frac{\xi \cdot (t+1) - 1}{\log 2}.
  \label{eq:rho_prop}
\end{align}
This holds for any $\xi > 0$, and the bound is tight when $\xi = \frac
1 {t+1}$.  Now introducing an auxiliary parameter $\xi_{xy}$ for each
$(x,y) \in \Omega$ and applying this bound, we obtain an upper bound
of \eqref{eq:latent_obj} as 
\begin{align}
  L(U,V,\xi) := 
  \label{eq:latent_obj_bd}
  \sum_{(x,y) \in \Omega} - \log_2\xi_{xy} + \frac{\xi_{xy} \rbr{
      \sum_{y' \neq y} \sigma_0(f(U_x,V_y) - f(U_x, V_{y'})) + 1} -
    1}{\log 2}.
\end{align}
Now we propose an iterative algorithm in which, each iteration consists
of $(U,V)$-step and $\xi$-step; in the $(U,V)$-step we minimize
\eqref{eq:latent_obj_bd} in $(U,V)$ and in the $\xi$-step we minimize in
$\xi$.  Pseudo-code can be found in Algorithm~\ref{alg:twostage} in
Appendix~\ref{sec:PseudSeriAlgor}.


\paragraph{$(U,V)$-step} The partial derivative of
\eqref{eq:latent_obj_bd} in terms of $U$ and $V$ can be calculated as:
$\nabla_{U,V} L(U,V,\xi) := \frac{1}{\log 2} \sum_{(x,y) \in \Omega}
\xi_{xy} \rbr{ \sum_{y' \neq y} \nabla_{U,V} \sigma_0(f(U_x,V_y) -
  f(U_x, V_{y'}))}$.  Now it is easy to see that the following
stochastic procedure unbiasedly estimates the above
gradient: % \eqref{eq:partial_UV}:
\begin{itemize*}
\item Sample $(x,y)$ uniformly from $\Omega$
\item Sample $y'$ uniformly from $\Ycal \setminus \cbr{y}$
\item Estimate the gradient by % \eqref{eq:partial_UV} by 
  \begin{align}
    \frac{\abr{\Omega} \cdot
      (\abr{\Ycal}-1) \cdot \xi_{xy}}{\log 2} \cdot
    \nabla_{U,V}
    \sigma_0(f(U_x,V_y) - f(U_x, V_{y'})).
    \label{eq:fast_sg}
  \end{align}
\end{itemize*}
Therefore a stochastic gradient descent algorithm based on
\eqref{eq:fast_sg} will converge to a local minimum of the objective
function \eqref{eq:latent_obj_bd} with probability one
\citep{RobMon51}.  Note that the time complexity of calculating
\eqref{eq:fast_sg} is independent of $\abr{\Omega}$ and $\abr{\Ycal}$.
Also, it is a function of only $U_x$ and $V_y$; the gradient is zero
in terms of other variables.

\paragraph{$\xi$-step}  

When $U$ and $V$ are fixed, minimization of $\xi_{xy}$ variable is
independent of each other and a simple analytic solution exists:
$\xi_{xy} = \frac 1 {\sum_{y' \neq y} \sigma_0(f(U_x,V_y) - f(U_x,
  V_{y'})) + 1}$.  This of course requires $O(\abr{\Ycal})$ work.  In
principle, we can avoid summation over $\Ycal$ by taking stochastic
gradient in terms of $\xi_{xy}$ as we did for $U$ and $V$.  However,
since the exact solution is very simple to compute and also because most
of the computation time is spent on $(U,V)$-step rather than $\xi$-step,
we found this update rule to be efficient.

\subsection{Parallelization}
\label{ssec:parallel}

The linearization trick in \eqref{eq:latent_obj_bd} not only enables
us to construct an efficient stochastic gradient algorithm, but also
makes possible to efficiently parallelize the algorithm across
multiple number of machines. Due to lack of space, details are relegated
to Appendix~\ref{sec:DescrParallAlgor}. 

\subsection{Experiments}
\label{sec:LargeItemSet}

In this subsection
% , we ask the following question: Given large amounts of computational
% resources, what is the best latent collaborative retrieval model (in
% terms of predictive performance on the test dataset) that one can
% produce within a given wall-clock time?  Towards this end, we work
% with the parallel variant of RoBiRank described in
% Section~\ref{ssec:parallel}. As a representative dataset
we use the
Million Song Dataset (MSD)~\cite{BerEllWhiLam13}, which consists of
1,129,318 users ($\abr{\Xcal}$), 386,133 songs ($\abr{\Ycal}$), and
49,824,519 records ($\abr{\Omega}$) of a user $x$ playing a song $y$ in
the training dataset.  The objective is to predict the songs from the
test dataset that a user is going to listen to\footnote{the original
  data also provides the number of times a song was played by a user,
  but we ignored this in our experiment.}.


% Squared frobenius norm of matrices $U$ and $V$ were added to the
% objective function \eqref{eq:rankloss_1_bd} for regularization, and the
% entries of $U$ and $V$ were independently sampled uniformly from $0$ to
% $1/\sqrt{d}$.  We performed a grid-search to find the best step size
% parameter. 

% This experiment was run on a computing cluster where each machine is
% equipped with 2 Intel Xeon E5 processors (16 cores) and 32GB of RAM.
% Our algorithm is implemented in C++ and uses Intel Thread Building
% Blocks (TBB) to handle thread-level parallelization, and MVAPICH2 was
% used for machine-to-machine communication.  Due to a limitation of the
% job scheduler on the cluster all experiments had to be stopped after
% 100,000 seconds. 

Since explicit ratings are not given, NDCG is not applicable for this
task; we use precision at 1 and 10 \citep{ManRagSch08} as our evaluation
metric. In our first experiment we study the scaling behavior of
RoBiRank as a function of number of machines. RoBiRank $p$ denotes the
parallel version of RoBiRank which is distributed across $p$ machines.
In Figure~\ref{fig:letor_exp} (left) we plot mean Precision@1 as a
function of the number of machines $\times$ the number of seconds
elapsed; this is a proxy for CPU time. If an algorithm linearly scales
across multiple processors, then all lines in the figure should overlap
with each other. As can be seen RoBiRank exhibits near ideal speed up
when going from 4 to 32 machines\footnote{The graph for RoBiRank 1 is
  hard to see because it was run for only 100,000 CPU-seconds.}.

\begin{figure*}
  \centering
  \begin{tikzpicture}[scale=0.5]
    \begin{axis}[minor tick num=1, only marks, 
      xlabel={number of machines $\times$ seconds elapsed},
      ylabel={Mean Precision@1},
      legend style={legend pos=south east}, ymin={0}, mark options={solid} ]
      
      \addplot[color=green, mark=o] table 
      [x expr={\thisrowno{0}*4}, y index=1, header=false, col sep=comma]
      {./Plots/robi_lcr_4.txt};

      \addplot[color=brown, mark=+] table 
      [x expr={\thisrowno{0}*16}, y index=1, header=false, col sep=comma]
      {./Plots/robi_lcr_16.txt};

      \addplot[color=blue, mark=none] table 
      [x expr={\thisrowno{0}*32}, y index=1, header=false, col sep=comma]
      {./Plots/robi_lcr_32.txt};

      \addplot[dashed, color=black, mark=o] table 
      [x expr={\thisrowno{0}*1}, y index=1, header=false, col sep=comma]
      {./Plots/robi_lcr_1.txt};

      \legend{RoBiRank 4, RoBiRank 16, RoBiRank 32, RoBiRank 1}
    \end{axis}
  \end{tikzpicture}
  \begin{tikzpicture}[scale=0.5]
    \begin{axis}[minor tick num=1,
      xlabel={seconds elapsed}, ylabel={Mean Precision@1}, legend pos={north
        west},
      xmin={0}, xmax={100000}, ymin={0}, mark options={solid}]

      \addplot[ultra thick, dashed, color=red, mark=*] table 
      [x index=0, y index=1, header=false, col sep=comma]
      {./Plots/wsabie_time.txt};

      \addplot[ultra thick, dashed, color=black, mark=o] table 
      [x index=0, y index=1, header=false, col sep=comma]
      {./Plots/robi_lcr_1.txt};

      \addplot[ultra thick, color=green, mark=o] table 
      [x index=0, y index=1, header=false, col sep=comma]
      {./Plots/robi_lcr_4.txt};

      \addplot[ultra thick, color=brown, mark=+] table 
      [x index=0, y index=1, header=false, col sep=comma]
      {./Plots/robi_lcr_16.txt};

      \addplot[ultra thick, color=blue, mark=none] table 
      [x index=0, y index=1, header=false, col sep=comma]
      {./Plots/robi_lcr_32.txt};

      \legend{Weston et al. (2012), RoBiRank 1, RoBiRank 4, RoBiRank
        16, RoBiRank 32}
    \end{axis}
  \end{tikzpicture}
  \begin{tikzpicture}[scale=0.5]
    \begin{axis}[minor tick num=1,
      xlabel={seconds elapsed}, ylabel={Mean Precision@10}, legend pos={north
        west},
      xmin={0}, xmax={100000}, ymin={0}, mark options={solid}]

      \addplot[ultra thick, dashed, color=red, mark=*] table 
      [x index=0, y index=2, header=false, col sep=comma]
      {./Plots/wsabie_time.txt};

      \addplot[ultra thick, dashed, color=black, mark=o] table 
      [x index=0, y index=2, header=false, col sep=comma]
      {./Plots/robi_lcr_1.txt};

      \addplot[ultra thick, color=green, mark=o] table 
      [x index=0, y index=2, header=false, col sep=comma]
      {./Plots/robi_lcr_4.txt};

      \addplot[ultra thick, color=brown, mark=+] table 
      [x index=0, y index=2, header=false, col sep=comma]
      {./Plots/robi_lcr_16.txt};

      \addplot[ultra thick, color=blue, mark=none] table 
      [x index=0, y index=2, header=false, col sep=comma]
      {./Plots/robi_lcr_32.txt};

      \legend{Weston et al. (2012), RoBiRank 1, RoBiRank 4, RoBiRank
        16, RoBiRank 32}
    \end{axis}
  \end{tikzpicture}


  \caption{Left:
    the scaling behavior of RoBiRank on Million Song Dataset.  Center, Right:
    Performance comparison of RoBiRank and \citet{WesWanWeiBer12} when
    the same amount of wall-clock time for computation is given.}
  \label{fig:letor_exp}
\end{figure*}


% \begin{figure}
%   \centering
%   \begin{tikzpicture}[scale=0.7]
%     \begin{axis}[minor tick num=1, only marks, 
%       xlabel={number of machines $\times$ seconds elapsed},
%       ylabel={Mean Precision@1},
%       legend style={legend pos=outer north east}, ymin={0} ]
      
%       \addplot[color=green, mark=o] table 
%       [x expr={\thisrowno{0}*4}, y index=1, header=false, col sep=comma]
%       {./Plots/robi_lcr_4.txt};

%       \addplot[color=brown, mark=+] table 
%       [x expr={\thisrowno{0}*16}, y index=1, header=false, col sep=comma]
%       {./Plots/robi_lcr_16.txt};

%       \addplot[color=blue, mark=none] table 
%       [x expr={\thisrowno{0}*32}, y index=1, header=false, col sep=comma]
%       {./Plots/robi_lcr_32.txt};

%       \addplot[dashed, color=black, mark=o] table 
%       [x expr={\thisrowno{0}*1}, y index=1, header=false, col sep=comma]
%       {./Plots/robi_lcr_1.txt};

%       \legend{RoBiRank 4, RoBiRank 16, RoBiRank 32, RoBiRank 1}

%     \end{axis}
%   \end{tikzpicture}
%   \caption{Scaling behavior of RoBiRank as the number of machines
%     changes.  Since the $x$-axis is now scaled by the number of
%     machines, when we achieve linear scaling the curves should overlap
%     with each other.}
%   \label{fig:scaling}
% \end{figure}

In our next experiment we compare RoBiRank with a state of the art
algorithm from~\citet{WesWanWeiBer12}, which optimizes a similar
objective function \eqref{eq:warp_obj}. We compare how fast the quality
of the solution improves as a function of wall clock time. Since the
authors of \citet{WesWanWeiBer12} do not make available their code, we
implemented their algorithm within our framework using the same data
structures and libraries used by our method. Furthermore, for a fair
comparison, we used the same initialization for $U$ and $V$ and
performed an identical grid-search over the step size parameter for both
algorithms.

It can be seen from Figure~\ref{fig:letor_exp} (center, right) that on a
single machine the algorithm of~\citet{WesWanWeiBer12} is very
competitive and outperforms RoBiRank. The reason for this might be the
introduction of the additional $\xi$ variables in RoBiRank, which slows
down convergence. However, RoBiRank training can be distributed across
processors, while it is not clear how to parallelize the algorithm
of~~\citet{WesWanWeiBer12}. Consequently, RoBiRank 32 which uses 32
machines for its computation can produce a significantly better model
within the same wall clock time window.


% \begin{figure}
%   \begin{tikzpicture}[scale=0.7]
%     \begin{axis}[minor tick num=1,
%       xlabel={seconds elapsed}, ylabel={Mean Precision@1}, legend pos={outer north
%         east},
%       xmin={0}, xmax={100000}, ymin={0}]

%       \addplot[ultra thick, dashed, color=red, mark=*] table 
%       [x index=0, y index=1, header=false, col sep=comma]
%       {./Plots/wsabie_time.txt};

%       \addplot[ultra thick, dashed, color=black, mark=o] table 
%       [x index=0, y index=1, header=false, col sep=comma]
%       {./Plots/robi_lcr_1.txt};

%       \addplot[ultra thick, color=green, mark=o] table 
%       [x index=0, y index=1, header=false, col sep=comma]
%       {./Plots/robi_lcr_4.txt};

%       \addplot[ultra thick, color=brown, mark=+] table 
%       [x index=0, y index=1, header=false, col sep=comma]
%       {./Plots/robi_lcr_16.txt};

%       \addplot[ultra thick, color=blue, mark=none] table 
%       [x index=0, y index=1, header=false, col sep=comma]
%       {./Plots/robi_lcr_32.txt};

%       \legend{\citet{WesWanWeiBer12}, RoBiRank 1, RoBiRank 4, RoBiRank
%         16, RoBiRank 32}
%     \end{axis}
%   \end{tikzpicture}

%   \caption{Performance comparison on Millon Song Dataset.  RoBiRank
%     $p$ was run in parallel with $p$ number of machines.}
%   \label{fig:latent_col}
% \end{figure}



\section{Related Work}
\label{sec:RelatedWork}

In terms of modeling, viewing ranking problems as generalization of
binary classification problems is not a new idea; for example, RankSVM
defines the objective function as a sum of hinge losses,
similarly to our basic model \eqref{eq:bound_basic_loss} in
Section~\ref{ssec:basic_model}.  However, it does not directly
optimize the ranking metric such as NDCG; the objective function and
the metric are not immediately related to each other.  In this
respect, our approach is closer to that of \citet{LeSmo07} which
constructs a convex upper bound on the ranking metric and
\citet{ChaDoTeoLeSmo08} which improves the bound by introducing
non-convexity.  The objective function of \citet{ChaDoTeoLeSmo08} is
also motivated by ramp loss, which is used for robust classification;
nonetheless, to our knowledge the direct connection between the
ranking metrics in form \eqref{eq:gen_metric} (DCG, NDCG) and the
robust loss \eqref{robust_losses} is our novel contribution.  Also,
our objective function is designed to specifically bound the ranking
metric, while \citet{ChaDoTeoLeSmo08} proposes a general recipe to
improve existing convex bounds.

Stochastic optimization of the objective function for latent
collaborative retrieval has been also explored in
\citet{WesWanWeiBer12}.  They attempt to minimize
%  the following
% objective function:
\begin{align}
  \sum_{(x,y) \in \Omega}
  \Phi \rbr{1 + \sum_{y' \neq y}
    I(f(U_x,V_y) - f(U_x, V_{y'}) < 0)},
  \label{eq:warp_obj}
\end{align}
where $\Phi(t) = \sum_{k=1}^t \frac 1 k$.  This is similar to our
objective function \eqref{eq:latent_obj_bd}; $\Phi(\cdot)$ and
$\rho_2(\cdot)$ are asymptotically equivalent.  However, we argue that
our formulation \eqref{eq:latent_obj_bd} has two major advantages.
First, it is a continuous and differentiable function, therefore
gradient-based algorithms such as L-BFGS and stochastic gradient
descent have convergence guarantees.  On the other hand, the objective
function of \citet{WesWanWeiBer12} is not even continuous, since their
formulation is based on a function $\Phi(\cdot)$ that is defined for
only natural numbers.  Also, through the linearization trick in
\eqref{eq:latent_obj_bd} we are able to obtain an unbiased stochastic
gradient, which is necessary for the convergence guarantee, and
to parallelize the algorithm across multiple machines as discussed in
Section~\ref{ssec:parallel}.  It is unclear how these techniques can
be adapted for the objective function of \citet{WesWanWeiBer12}.


% Note that \citet{WesWanWeiBer12} proposes a more general class of models
% for the task than can be expressed by \eqref{eq:warp_obj}.  For
% example, they discuss situations in which we have side information on
% each context or item to help learning latent embeddings.  Some of the
% optimization techniqures introduced in Section~\ref{ssec:sto_opt} can
% be adapted for these general problems as well, but is left for future
% work.

% Parallelization of an optimization algorithm via parameter expansion
% \eqref{eq:rho_prop} was applied to a bit different problem named
% multinomial logistic regression \citep{GopYan13}.  However, to our
% knowledge we are the first to use the trick to construct an unbiased
% stochastic gradient that can be efficiently computed, and adapt it to
% stratified stochastic gradient descent (SSGD) scheme of
% \citet{GemNijHaaSis11}.  Note that the optimization algorithm can
% alternatively be derived using convex multiplicative programming
% framework of \citet{KunYajKon93}.  In fact, \citet{Ding13} develops a
% robust classification algorithm based on this idea; this also indicates
% that robust classification and ranking are closely related.

% It has been observed that while matrix completion approaches are
% successful in predicting ratings of users to items, they have poor
% performances on predicting items users might be interested in
% \citet{CreKorTur10}.  It has been argued that in recommendation purposes,
% it is important to model what user-item pair was \emph{not} observed as
% well as what was observed \citep{CreKorTur10,Steck2010}. TODO.

% \section{Experiments}
% \label{sec:Experiments}

% In this section we empirically evaluate RoBiRank.  Our experiments are
% divided into two parts.  In Section~\ref{sec:SmallItemSet}, we apply
% RoBiRank on standard benchmark datasets from the learning to rank
% literature.  These datasets have relatively small number of relevant
% items $\abr{\Ycal_x}$ for each context $x$, so we will use L-BFGS
% \citep{NocWri06}, a quasi-Newton algorithm, for optimization of the
% objective function~\eqref{eq:rankloss_1_bd}. Although L-BFGS is designed
% for optimizing convex functions, we empirically find that it converges
% reliably to a local minima of the RoBiRank objective function
% \eqref{eq:rankloss_1_bd} in all our experiments. In
% Section~\ref{sec:LargeItemSet} we apply RoBiRank to the million songs
% dataset (MSD), where stochastic optimization and parallelization are
% necessary.

% All our code, data, and experiment scripts
% are available for download under an open source license from
% \url{http://anonymous.url}.



\section{Conclusion}
\label{sec:Conclusion}

In this paper, we developed RoBiRank, a novel model on ranking, based
on insights and techniques from the literature of robust binary
classification.  Then, we proposed a scalable and parallelizable
stochastic optimization algorithm that can be applied to the task of
latent collaborative retrieval which large-scale data without feature
vectors and explicit scores have to take care of.  Experimental
results on both learning to rank datasets and latent collaborative
retrieval dataset suggest the advantage of our approach.

% To conclude, 

% the point we are trying to make with our experiments in
% section \ref{sec:LargeItemSet} is not simply that RoBiRank can
% outperform WSABIE.  

As a final note, the experiments in Section~\ref{sec:LargeItemSet} are
arguably unfair towards WSABIE. For instance, one could envisage using
clever engineering tricks to derive a parallel variant of WSABIE (\eg,
by averaging gradients from various machines), which might outperform
RoBiRank on the MSD dataset. While performance on a specific dataset
might be better, we would lose global convergence guarantees. Therefore,
rather than obsess over the performance of a specific algorithm on a
specific dataset, via this paper we hope to draw the attention of the
community to the need for developing principled parallel algorithms for
this important problem.

% We are currently investigating how to extend our method to the more
% general context of collaborative retrieval tasks in which additional side
% information is available, as discussed in \citet{WesWanWeiBer12}.

\bibliographystyle{abbrvnat}
\bibliography{rankbib}
\clearpage
\appendix


\section{Additional Results for Learning to Rank Experiments}
In appendix A, we present results from additional experiments that could not
be accommodated in the main paper due to space constraints. Figure~\ref{fig:ndcg_all_app} shows how RoBiRank
fares against InfNormPush and IRPush on various datasets we used. Figure~\ref{fig:ndcg_all_ranklib_app} shows a similar
comparison against the 8 algorithms present in RankLib. Table~\ref{tb:descriptives} provides descriptive 
statistics of all the datasets we ran our experiments, Overall NDCG values obtained and values of the corresponding
regularization parameters. Overall NDCG values have been omitted for the RankLib algorithms as the library doesn't 
support its calculation directly.
\label{sec:AdditPlotsLearn}

% svnvish: BUGBUG
% get rid of mean ndcg values from here and push them to the appendix. 
\begin{sidewaystable}
  \centering
  \begin{tabular}{|l|c|c|c|c|c|c|c|c|c|c|c|c|}
    % \hline
    \hline
    \multirow{2}{*}{Name} & \multirow{2}{*}{$\abr{\Xcal}$} & avg. &
    \multicolumn{5}{c|}{Mean NDCG} &     \multicolumn{5}{c|}{Regularization Parameter}
    \\ \cline{4-13}
    & & $\abr{\Ycal_x}$ & RoBiRank & RankSVM & LSRank & InfNormPush & IRPush & RoBiRank &
    RankSVM & LSRank & InfNormPush & IRPush \\
    \hline
    TD 2003 & 50 & 981 & 0.9719 & 0.9219 & 0.9721 & 0.9514 & 0.9685 & $10^{-5}$ &
    $10^{-3}$ & $10^{-1}$ & 1 & $10^{-4}$ \\
    TD 2004 & 75 & 989 & 0.9708 & 0.9084 & 0.9648 & 0.9521 & 0.9601 & $10^{-6}$ &
    $10^{-1}$ & $10^{4}$ & $10^{-2}$ & $10^{-4}$ \\
    Yahoo! 1 & 29,921 & 24 & 0.8921 & 0.7960 & 0.871 & 0.8692 & 0.8892 & $10^{-9}$ &
    $10^{3}$ & $10^{4}$ & 10 & $10^{-9}$ \\
    Yahoo! 2 & 6,330 & 27 & 0.9067 & 0.8126 & 0.8624 & 0.8826 & 0.9068 & $10^{-9}$ &
    $10^{5}$ & $10^{4}$ & 10 & $10^{-7}$ \\
    HP 2003 & 150 & 984 & 0.9960 & 0.9927 & 0.9981 & 0.9832 & 0.9939 & $10^{-3}$ &
    $10^{-1}$ & $10^{-4}$ & 1 & $10^{-2}$ \\
    HP 2004 & 75 & 992 & 0.9967 & 0.9918 & 0.9946 & 0.9863 & 0.9949 & $10^{-4}$ &
    $10^{-1}$ & $10^{2}$ & $10^{-2}$ & $10^{-2}$ \\
    OHSUMED & 106 & 169 & 0.8229 & 0.6626 & 0.8184 & 0.7949 & 0.8417 & $10^{-3}$ &
    $10^{-5}$ & $10^{4}$ & 1 & $10^{-3}$ \\
    MSLR30K & 31,531 & 120 & 0.7812 & 0.5841 & 0.727 & - & - & $1$ &
    $10^{3}$ & $10^{4}$ & - & - \\
    MQ 2007 & 1,692 & 41 & 0.8903 & 0.7950 & 0.8688 & 0.8717 & 0.8810 & $10^{-9}$ &
    $10^{-3}$ & $10^{4}$ & 10 & $10^{-6}$ \\
    MQ 2008 & 784 & 19 & 0.9221 & 0.8703 & 0.9133 & 0.8929 & 0.9052 & $10^{-5}$ &
    $10^{3}$ & $10^{4}$ & 10 & $10^{-5}$ \\
    \hline
    % \hline
  \end{tabular}
  \caption{Descriptive Statistics of Datasets and Experimental Results
    in Section~\ref{sec:SmallItemSet}.}
  \label{tb:descriptives}
\end{sidewaystable}

\begin{table*}
  \centering
  \begin{tabular}{|l|c|c|}
    % \hline
    \hline
    Name & RoBiRank & Identity Loss \\
    \hline
    TD 2003 & 0.9719 & 0.9575 \\
    TD 2004 & 0.9708 & 0.9456 \\
    HP 2003 & 0.9960 & 0.9855 \\
    HP 2004 & 0.9967 & 0.9841 \\ 
    MQ 2007 & 0.8903 & 0.7973 \\ 
    MQ 2008 & 0.9221 & 0.8039 \\ 
    \hline
    MSD & 29\% & 17\% \\ 
    \hline
    % \hline
  \end{tabular}
  \caption{Comparison of RoBiRank against Identity Loss as described in Section~\ref{sec:CompBaselines}. We report overall NDCG for experiments on small-medium datasets, while on the million song dataset (MSD) we report Precision@1.}
  \label{tb:otherbaselines}
\end{table*}


\begin{figure*}[htbp]
  \centering
  \begin{tikzpicture}[scale=0.60]
    \begin{axis}[minor tick num=1,
      title={TD 2003},
      xlabel={k}, ylabel={NDCG@k},
      xmin={1}, xmax={20}, ymin={0.4}, ymax={1.0}]
      
      \addplot[ultra thick, color=blue, mark=*] table [x index=0, y index=1, header=true]
      {./Plots/td2003_all.txt};

      \addplot[ultra thick, color=red, mark=x] table [x index=0, y index=2, header=true]
      {./Plots/td2003_all.txt};

      \addplot[ultra thick, color=black, mark=o] table [x index=0, y index=3, header=true]
      {./Plots/td2003_all.txt};
      
      \addplot[ultra thick, color=green, mark=square] table [x index=0, y index=4, header=true]
      {./Plots/td2003_all.txt};
      
      \addplot[ultra thick, color=teal, mark=triangle] table [x index=0, y index=5, header=true]
      {./Plots/td2003_all.txt};
	  
      \legend{RoBiRank, RankSVM, LSRank, InfNormPush, IRPush}
    \end{axis}
  \end{tikzpicture}
  \begin{tikzpicture}[scale=0.60]
    \begin{axis}[minor tick num=1,
      title={TD 2004},
      xlabel={k}, ylabel={NDCG@k},
      xmin={1}, xmax={20}, ymin={0.4}, ymax={1.0}]
      
      \addplot[ultra thick, color=blue, mark=*] table [x index=0, y index=1, header=true]
      {./Plots/td2004_all.txt};

      \addplot[ultra thick, color=red, mark=x] table [x index=0, y index=2, header=true]
      {./Plots/td2004_all.txt};

      \addplot[ultra thick, color=black, mark=o] table [x index=0, y index=3, header=true]
      {./Plots/td2004_all.txt};
      
      \addplot[ultra thick, color=green, mark=square] table [x index=0, y index=4, header=true]
      {./Plots/td2004_all.txt};
      
      \addplot[ultra thick, color=teal, mark=triangle] table [x index=0, y index=5, header=true]
      {./Plots/td2004_all.txt};
	  
    \end{axis}
  \end{tikzpicture}
  % \caption{Performance comparison on LETOR benchmark datasets.}
  \begin{tikzpicture}[scale=0.60]
    \begin{axis}[minor tick num=1,
      title={Yahoo Learning to Rank - 1},
      xlabel={k}, ylabel={NDCG@k},
      xmin={1}, xmax={20}, ymin={0.4}, ymax={1.0},
      legend pos={south east}]
      
      \addplot[ultra thick, color=blue, mark=*] table [x index=0, y index=1, header=true]
      {./Plots/yahooltrcset1_all.txt};

      \addplot[ultra thick, color=red, mark=x] table [x index=0, y index=2, header=true]
      {./Plots/yahooltrcset1_all.txt};

      \addplot[ultra thick, color=black, mark=o] table [x index=0, y index=3, header=true]
      {./Plots/yahooltrcset1_all.txt};
      
      \addplot[ultra thick, color=green, mark=square] table [x index=0, y index=4, header=true]
      {./Plots/yahooltrcset1_all.txt};
      
      \addplot[ultra thick, color=teal, mark=triangle] table [x index=0, y index=5, header=true]
      {./Plots/yahooltrcset1_all.txt};
	  
    \end{axis}
  \end{tikzpicture}  
  \begin{tikzpicture}[scale=0.60]
    \begin{axis}[minor tick num=1,
      title={Yahoo Learning to Rank - 2},
      xlabel={k}, ylabel={NDCG@k},
      xmin={1}, xmax={20}, ymin={0.4}, ymax={1.0},
      legend pos={south east}]
      
      \addplot[ultra thick, color=blue, mark=*] table [x index=0, y index=1, header=true]
      {./Plots/yahooltrcset2_all.txt};

      \addplot[ultra thick, color=red, mark=x] table [x index=0, y index=2, header=true]
      {./Plots/yahooltrcset2_all.txt};

      \addplot[ultra thick, color=black, mark=o] table [x index=0, y index=3, header=true]
      {./Plots/yahooltrcset2_all.txt};
      
      \addplot[ultra thick, color=green, mark=square] table [x index=0, y index=4, header=true]
      {./Plots/yahooltrcset2_all.txt};
      
      \addplot[ultra thick, color=teal, mark=triangle] table [x index=0, y index=5, header=true]
      {./Plots/yahooltrcset2_all.txt};
	  
    \end{axis}
  \end{tikzpicture}
  \begin{tikzpicture}[scale=0.60]
    \begin{axis}[minor tick num=1,
      title={HP 2003},
      xlabel={k}, ylabel={NDCG@k},
      xmin={1}, xmax={20},
      ymin={0.4}, ymax={1.0},
      legend pos={south east}]
      
      \addplot[ultra thick, color=blue, mark=*] table [x index=0, y index=1, header=true]
      {./Plots/hp2003_all.txt};

      \addplot[ultra thick, color=red, mark=x] table [x index=0, y index=2, header=true]
      {./Plots/hp2003_all.txt};

      \addplot[ultra thick, color=black, mark=o] table [x index=0, y index=3, header=true]
      {./Plots/hp2003_all.txt};
      
      \addplot[ultra thick, color=green, mark=square] table [x index=0, y index=4, header=true]
      {./Plots/hp2003_all.txt};
      
      \addplot[ultra thick, color=teal, mark=triangle] table [x index=0, y index=5, header=true]
      {./Plots/hp2003_all.txt};
	  
    \end{axis}
  \end{tikzpicture}
  \begin{tikzpicture}[scale=0.60]
    \begin{axis}[minor tick num=1,
      title={HP 2004},
      xlabel={k}, ylabel={NDCG@k},
      xmin={1}, xmax={20}, ymin={0.4}, ymax={1.0},
      legend pos={south east}]
      
      \addplot[ultra thick, color=blue, mark=*] table [x index=0, y index=1, header=true]
      {./Plots/hp2004_all.txt};

      \addplot[ultra thick, color=red, mark=x] table [x index=0, y index=2, header=true]
      {./Plots/hp2004_all.txt};

      \addplot[ultra thick, color=black, mark=o] table [x index=0, y index=3, header=true]
      {./Plots/hp2004_all.txt};

      \addplot[ultra thick, color=green, mark=square] table [x index=0, y index=4, header=true]
      {./Plots/hp2004_all.txt};
      
      \addplot[ultra thick, color=teal, mark=triangle] table [x index=0, y index=5, header=true]
      {./Plots/hp2004_all.txt};
      
    \end{axis}
  \end{tikzpicture}
  \begin{tikzpicture}[scale=0.60]
    \begin{axis}[minor tick num=1,
      title={OHSUMED},
      xlabel={k}, ylabel={NDCG@k},
      xmin={1}, xmax={20}, ymin={0.4}, ymax={1.0}]
      
      \addplot[ultra thick, color=blue, mark=*] table [x index=0, y index=1, header=true]
      {./Plots/ohsumed_all.txt};

      \addplot[ultra thick, color=red, mark=x] table [x index=0, y index=2, header=true]
      {./Plots/ohsumed_all.txt};

      \addplot[ultra thick, color=black, mark=o] table [x index=0, y index=3, header=true]
      {./Plots/ohsumed_all.txt};
      
      \addplot[ultra thick, color=green, mark=square] table [x index=0, y index=4, header=true]
      {./Plots/ohsumed_all.txt};
      
      \addplot[ultra thick, color=teal, mark=triangle] table [x index=0, y index=5, header=true]
      {./Plots/ohsumed_all.txt};
	  
    \end{axis}
  \end{tikzpicture}
  \begin{tikzpicture}[scale=0.60]
    \begin{axis}[minor tick num=1,
      title={MSLR30K},
      xlabel={k}, ylabel={NDCG@k},
      xmin={1}, xmax={20},
      ymin={0}, ymax={1.0}]
      
      \addplot[ultra thick, color=blue, mark=*] table [x index=0, y index=1, header=true]
      {./Plots/mslr30K_all.txt};

      \addplot[ultra thick, color=red, mark=x] table [x index=0, y index=2, header=true]
      {./Plots/mslr30K_all.txt};

      \addplot[ultra thick, color=black, mark=o] table [x index=0, y index=3, header=true]
      {./Plots/mslr30K_all.txt};
      
      \addplot[ultra thick, color=green, mark=square] table [x index=0, y index=4, header=true]
      {./Plots/mslr30K_all.txt};
      
      \addplot[ultra thick, color=teal, mark=triangle] table [x index=0, y index=5, header=true]
      {./Plots/mslr30K_all.txt};
      
    \end{axis}
  \end{tikzpicture}
  \begin{tikzpicture}[scale=0.60]
    \begin{axis}[minor tick num=1,
      title={MQ 2007},
      xlabel={k}, ylabel={NDCG@k},
      xmin={1}, xmax={20},
      ymin={0.4}, ymax={1.0}]
      
      \addplot[ultra thick, color=blue, mark=*] table [x index=0, y index=1, header=true]
      {./Plots/mq2007_all.txt};

      \addplot[ultra thick, color=red, mark=x] table [x index=0, y index=2, header=true]
      {./Plots/mq2007_all.txt};

      \addplot[ultra thick, color=black, mark=o] table [x index=0, y index=3, header=true]
      {./Plots/mq2007_all.txt};
      
      \addplot[ultra thick, color=green, mark=square] table [x index=0, y index=4, header=true]
      {./Plots/mq2007_all.txt};
      
      \addplot[ultra thick, color=teal, mark=triangle] table [x index=0, y index=5, header=true]
      {./Plots/mq2007_all.txt};
	  
    \end{axis}
  \end{tikzpicture}
  \begin{tikzpicture}[scale=0.60]
    \begin{axis}[minor tick num=1,
      title={MQ 2008},
      xlabel={k}, ylabel={NDCG@k},
      xmin={1}, xmax={20}, ymin={0.4}, ymax={1.0}]
      
      \addplot[ultra thick, color=blue, mark=*] table [x index=0, y index=1, header=true]
      {./Plots/mq2008_all.txt};

      \addplot[ultra thick, color=red, mark=x] table [x index=0, y index=2, header=true]
      {./Plots/mq2008_all.txt};

      \addplot[ultra thick, color=black, mark=o] table [x index=0, y index=3, header=true]
      {./Plots/mq2008_all.txt};
      
      \addplot[ultra thick, color=green, mark=square] table [x index=0, y index=4, header=true]
      {./Plots/mq2008_all.txt};
      
      \addplot[ultra thick, color=teal, mark=triangle] table [x index=0, y index=5, header=true]
      {./Plots/mq2008_all.txt};
	  
    \end{axis}
  \end{tikzpicture}
  \caption{Comparison of RoBiRank, RankSVM, LSRank \citep{LeSmo07}, Inf-Push and IR-Push }\label{fig:ndcg_all_app}
\end{figure*}

\begin{figure*}[htbp]
  \centering
  \begin{tikzpicture}[scale=0.60]
    \begin{axis}[minor tick num=1,
      title={TD 2003},
      xlabel={k}, ylabel={NDCG@k},
      xmin={1}, xmax={20}, ymin={0.4}, ymax={1.0}]
      
      \addplot[ultra thick, color=blue, mark=*] table [x index=0, y index=1, header=true]
      {./Plots/td2003_all.txt};

      \addplot[ultra thick, color=brown, mark=square] table [x index=0, y index=6, header=true]
      {./Plots/td2003_all.txt};
      
      \addplot[ultra thick, color=magenta, mark=square*] table [x index=0, y index=7, header=true]
      {./Plots/td2003_all.txt};

      \addplot[ultra thick, color=yellow, mark=triangle] table [x index=0, y index=8, header=true]
      {./Plots/td2003_all.txt};

      \addplot[ultra thick, color=cyan, mark=triangle*] table [x index=0, y index=9, header=true]
      {./Plots/td2003_all.txt};

      \addplot[ultra thick, color=lime, mark=diamond] table [x index=0, y index=10, header=true]
      {./Plots/td2003_all.txt};

      \addplot[ultra thick, color=olive, mark=diamond*] table [x index=0, y index=11, header=true]
      {./Plots/td2003_all.txt};

      \addplot[ultra thick, color=violet , mark=+] table [x index=0, y index=12, header=true]
      {./Plots/td2003_all.txt};

      \addplot[ultra thick, color=purple, mark=o] table [x index=0, y index=13, header=true]
      {./Plots/td2003_all.txt};
	  	  	  
      \legend{RoBiRank, MART, RankNet, RankBoost, AdaRank, CoordAscent, LambdaMART, ListNet, RandomForests}
    \end{axis}
  \end{tikzpicture}
  \begin{tikzpicture}[scale=0.60]
    \begin{axis}[minor tick num=1,
      title={TD 2004},
      xlabel={k}, ylabel={NDCG@k},
      xmin={1}, xmax={20}, ymin={0.4}, ymax={1.0}]
      
      \addplot[ultra thick, color=blue, mark=*] table [x index=0, y index=1, header=true]
      {./Plots/td2004_all.txt};

      \addplot[ultra thick, color=brown, mark=square] table [x index=0, y index=6, header=true]
      {./Plots/td2004_all.txt};
      
      \addplot[ultra thick, color=magenta, mark=square*] table [x index=0, y index=7, header=true]
      {./Plots/td2004_all.txt};

      \addplot[ultra thick, color=yellow, mark=triangle] table [x index=0, y index=8, header=true]
      {./Plots/td2004_all.txt};

      \addplot[ultra thick, color=cyan, mark=triangle*] table [x index=0, y index=9, header=true]
      {./Plots/td2004_all.txt};

      \addplot[ultra thick, color=lime, mark=diamond] table [x index=0, y index=10, header=true]
      {./Plots/td2004_all.txt};

      \addplot[ultra thick, color=olive, mark=diamond*] table [x index=0, y index=11, header=true]
      {./Plots/td2004_all.txt};

      \addplot[ultra thick, color=violet , mark=+] table [x index=0, y index=12, header=true]
      {./Plots/td2004_all.txt};

      \addplot[ultra thick, color=purple, mark=o] table [x index=0, y index=13, header=true]
      {./Plots/td2004_all.txt};
      
    \end{axis}
  \end{tikzpicture}
  % \caption{Performance comparison on LETOR benchmark datasets.}
  \begin{tikzpicture}[scale=0.60]
    \begin{axis}[minor tick num=1,
      title={Yahoo Learning to Rank - 1},
      xlabel={k}, ylabel={NDCG@k},
      xmin={1}, xmax={20}, ymin={0.4}, ymax={1.0},
      legend pos={south east}]
      
      \addplot[ultra thick, color=blue, mark=*] table [x index=0, y index=1, header=true]
      {./Plots/yahooltrcset1_all.txt};

      \addplot[ultra thick, color=brown, mark=square] table [x index=0, y index=6, header=true]
      {./Plots/yahooltrcset1_all.txt};
      
      \addplot[ultra thick, color=magenta, mark=square*] table [x index=0, y index=7, header=true]
      {./Plots/yahooltrcset1_all.txt};

      \addplot[ultra thick, color=yellow, mark=triangle] table [x index=0, y index=8, header=true]
      {./Plots/yahooltrcset1_all.txt};

      \addplot[ultra thick, color=cyan, mark=triangle*] table [x index=0, y index=9, header=true]
      {./Plots/yahooltrcset1_all.txt};

      \addplot[ultra thick, color=lime, mark=diamond] table [x index=0, y index=10, header=true]
      {./Plots/yahooltrcset1_all.txt};

      \addplot[ultra thick, color=olive, mark=diamond*] table [x index=0, y index=11, header=true]
      {./Plots/yahooltrcset1_all.txt};

      \addplot[ultra thick, color=violet , mark=+] table [x index=0, y index=12, header=true]
      {./Plots/yahooltrcset1_all.txt};

      \addplot[ultra thick, color=purple, mark=o] table [x index=0, y index=13, header=true]
      {./Plots/yahooltrcset1_all.txt};
      
    \end{axis}
  \end{tikzpicture}  
  \begin{tikzpicture}[scale=0.60]
    \begin{axis}[minor tick num=1,
      title={Yahoo Learning to Rank - 2},
      xlabel={k}, ylabel={NDCG@k},
      xmin={1}, xmax={20}, ymin={0.4}, ymax={1.0},
      legend pos={south east}]
      
      \addplot[ultra thick, color=blue, mark=*] table [x index=0, y index=1, header=true]
      {./Plots/yahooltrcset2_all.txt};

      \addplot[ultra thick, color=brown, mark=square] table [x index=0, y index=6, header=true]
      {./Plots/yahooltrcset2_all.txt};
      
      \addplot[ultra thick, color=magenta, mark=square*] table [x index=0, y index=7, header=true]
      {./Plots/yahooltrcset2_all.txt};

      \addplot[ultra thick, color=yellow, mark=triangle] table [x index=0, y index=8, header=true]
      {./Plots/yahooltrcset2_all.txt};

      \addplot[ultra thick, color=cyan, mark=triangle*] table [x index=0, y index=9, header=true]
      {./Plots/yahooltrcset2_all.txt};

      \addplot[ultra thick, color=lime, mark=diamond] table [x index=0, y index=10, header=true]
      {./Plots/yahooltrcset2_all.txt};

      \addplot[ultra thick, color=olive, mark=diamond*] table [x index=0, y index=11, header=true]
      {./Plots/yahooltrcset2_all.txt};

      \addplot[ultra thick, color=violet , mark=+] table [x index=0, y index=12, header=true]
      {./Plots/yahooltrcset2_all.txt};

      \addplot[ultra thick, color=purple, mark=o] table [x index=0, y index=13, header=true]
      {./Plots/yahooltrcset2_all.txt};
      
    \end{axis}
  \end{tikzpicture}
  \begin{tikzpicture}[scale=0.60]
    \begin{axis}[minor tick num=1,
      title={HP 2003},
      xlabel={k}, ylabel={NDCG@k},
      xmin={1}, xmax={20},
      ymin={0.4}, ymax={1.0},
      legend pos={south east}]
      
      \addplot[ultra thick, color=blue, mark=*] table [x index=0, y index=1, header=true]
      {./Plots/hp2003_all.txt};

     \addplot[ultra thick, color=brown, mark=square] table [x index=0, y index=6, header=true]
      {./Plots/hp2003_all.txt};
      
      \addplot[ultra thick, color=magenta, mark=square*] table [x index=0, y index=7, header=true]
      {./Plots/hp2003_all.txt};

      \addplot[ultra thick, color=yellow, mark=triangle] table [x index=0, y index=8, header=true]
      {./Plots/hp2003_all.txt};

      \addplot[ultra thick, color=cyan, mark=triangle*] table [x index=0, y index=9, header=true]
      {./Plots/hp2003_all.txt};

      \addplot[ultra thick, color=lime, mark=diamond] table [x index=0, y index=10, header=true]
      {./Plots/hp2003_all.txt};

      \addplot[ultra thick, color=olive, mark=diamond*] table [x index=0, y index=11, header=true]
      {./Plots/hp2003_all.txt};

      \addplot[ultra thick, color=violet , mark=+] table [x index=0, y index=12, header=true]
      {./Plots/hp2003_all.txt};

      \addplot[ultra thick, color=purple, mark=o] table [x index=0, y index=13, header=true]
      {./Plots/hp2003_all.txt};
      
    \end{axis}
  \end{tikzpicture}
  \begin{tikzpicture}[scale=0.60]
    \begin{axis}[minor tick num=1,
      title={HP 2004},
      xlabel={k}, ylabel={NDCG@k},
      xmin={1}, xmax={20}, ymin={0.4}, ymax={1.0},
      legend pos={south east}]
      
      \addplot[ultra thick, color=blue, mark=*] table [x index=0, y index=1, header=true]
      {./Plots/hp2004_all.txt};

      \addplot[ultra thick, color=brown, mark=square] table [x index=0, y index=6, header=true]
      {./Plots/hp2004_all.txt};
      
      \addplot[ultra thick, color=magenta, mark=square*] table [x index=0, y index=7, header=true]
      {./Plots/hp2004_all.txt};

      \addplot[ultra thick, color=yellow, mark=triangle] table [x index=0, y index=8, header=true]
      {./Plots/hp2004_all.txt};

      \addplot[ultra thick, color=cyan, mark=triangle*] table [x index=0, y index=9, header=true]
      {./Plots/hp2004_all.txt};

      \addplot[ultra thick, color=lime, mark=diamond] table [x index=0, y index=10, header=true]
      {./Plots/hp2004_all.txt};

      \addplot[ultra thick, color=olive, mark=diamond*] table [x index=0, y index=11, header=true]
      {./Plots/hp2004_all.txt};

      \addplot[ultra thick, color=violet , mark=+] table [x index=0, y index=12, header=true]
      {./Plots/hp2004_all.txt};

      \addplot[ultra thick, color=purple, mark=o] table [x index=0, y index=13, header=true]
      {./Plots/hp2004_all.txt};
      
    \end{axis}
  \end{tikzpicture}
  \begin{tikzpicture}[scale=0.60]
    \begin{axis}[minor tick num=1,
      title={OHSUMED},
      xlabel={k}, ylabel={NDCG@k},
      xmin={1}, xmax={20}, ymin={0.4}, ymax={1.0}]
      
      \addplot[ultra thick, color=blue, mark=*] table [x index=0, y index=1, header=true]
      {./Plots/ohsumed_all.txt};

      \addplot[ultra thick, color=brown, mark=square] table [x index=0, y index=6, header=true]
      {./Plots/ohsumed_all.txt};
      
      \addplot[ultra thick, color=magenta, mark=square*] table [x index=0, y index=7, header=true]
      {./Plots/ohsumed_all.txt};

      \addplot[ultra thick, color=yellow, mark=triangle] table [x index=0, y index=8, header=true]
      {./Plots/ohsumed_all.txt};

      \addplot[ultra thick, color=cyan, mark=triangle*] table [x index=0, y index=9, header=true]
      {./Plots/ohsumed_all.txt};

      \addplot[ultra thick, color=lime, mark=diamond] table [x index=0, y index=10, header=true]
      {./Plots/ohsumed_all.txt};

      \addplot[ultra thick, color=olive, mark=diamond*] table [x index=0, y index=11, header=true]
      {./Plots/ohsumed_all.txt};

      \addplot[ultra thick, color=violet , mark=+] table [x index=0, y index=12, header=true]
      {./Plots/ohsumed_all.txt};

      \addplot[ultra thick, color=purple, mark=o] table [x index=0, y index=13, header=true]
      {./Plots/ohsumed_all.txt};
      
    \end{axis}
  \end{tikzpicture}
  %\begin{tikzpicture}[scale=0.65]
    %\begin{axis}[minor tick num=1,
      %title={MSLR30K},
      %xlabel={k}, ylabel={NDCG@k},
      %xmin={1}, xmax={20},
      %ymin={0}, ymax={1.0}]
      
      %\addplot[ultra thick, color=blue, mark=*] table [x index=0, y index=1, header=true]
      %{./Plots/mslr30K.txt};

      %\addplot[ultra thick, color=red, mark=x] table [x index=0, y index=2, header=true]
      %{./Plots/mslr30K.txt};

      %\addplot[ultra thick, color=black, mark=o] table [x index=0, y index=3, header=true]
      %{./Plots/mslr30K.txt};
      
      %%\legend{RoBiRank, RankSVM, LSRank }
    %\end{axis}
  %\end{tikzpicture}
  \begin{tikzpicture}[scale=0.60]
    \begin{axis}[minor tick num=1,
      title={MQ 2007},
      xlabel={k}, ylabel={NDCG@k},
      xmin={1}, xmax={20},
      ymin={0.4}, ymax={1.0}]
      
      \addplot[ultra thick, color=blue, mark=*] table [x index=0, y index=1, header=true]
      {./Plots/mq2007_all.txt};

      \addplot[ultra thick, color=brown, mark=square] table [x index=0, y index=6, header=true]
      {./Plots/mq2007_all.txt};
      
      \addplot[ultra thick, color=magenta, mark=square*] table [x index=0, y index=7, header=true]
      {./Plots/mq2007_all.txt};

      \addplot[ultra thick, color=yellow, mark=triangle] table [x index=0, y index=8, header=true]
      {./Plots/mq2007_all.txt};

      \addplot[ultra thick, color=cyan, mark=triangle*] table [x index=0, y index=9, header=true]
      {./Plots/mq2007_all.txt};

      \addplot[ultra thick, color=lime, mark=diamond] table [x index=0, y index=10, header=true]
      {./Plots/mq2007_all.txt};

      \addplot[ultra thick, color=olive, mark=diamond*] table [x index=0, y index=11, header=true]
      {./Plots/mq2007_all.txt};

      \addplot[ultra thick, color=violet , mark=+] table [x index=0, y index=12, header=true]
      {./Plots/mq2007_all.txt};

      \addplot[ultra thick, color=purple, mark=o] table [x index=0, y index=13, header=true]
      {./Plots/mq2007_all.txt};
      
    \end{axis}
  \end{tikzpicture}
  \begin{tikzpicture}[scale=0.60]
    \begin{axis}[minor tick num=1,
      title={MQ 2008},
      xlabel={k}, ylabel={NDCG@k},
      xmin={1}, xmax={20}, ymin={0.4}, ymax={1.0}]
      
      \addplot[ultra thick, color=blue, mark=*] table [x index=0, y index=1, header=true]
      {./Plots/mq2008_all.txt};

      \addplot[ultra thick, color=brown, mark=square] table [x index=0, y index=6, header=true]
      {./Plots/mq2008_all.txt};
      
      \addplot[ultra thick, color=magenta, mark=square*] table [x index=0, y index=7, header=true]
      {./Plots/mq2008_all.txt};

      \addplot[ultra thick, color=yellow, mark=triangle] table [x index=0, y index=8, header=true]
      {./Plots/mq2008_all.txt};

      \addplot[ultra thick, color=cyan, mark=triangle*] table [x index=0, y index=9, header=true]
      {./Plots/mq2008_all.txt};

      \addplot[ultra thick, color=lime, mark=diamond] table [x index=0, y index=10, header=true]
      {./Plots/mq2008_all.txt};

      \addplot[ultra thick, color=olive, mark=diamond*] table [x index=0, y index=11, header=true]
      {./Plots/mq2008_all.txt};

      \addplot[ultra thick, color=violet , mark=+] table [x index=0, y index=12, header=true]
      {./Plots/mq2008_all.txt};

      \addplot[ultra thick, color=purple, mark=o] table [x index=0, y index=13, header=true]
      {./Plots/mq2008_all.txt};
      
    \end{axis}
  \end{tikzpicture}
  \caption{Comparison of RoBiRank, MART, RankNet, RankBoost, AdaRank, CoordAscent, LambdaMART, ListNet and RandomForests }\label{fig:ndcg_all_ranklib_app}
\end{figure*}

\begin{figure*}[htbp]
  \centering
  \begin{tikzpicture}[scale=0.60]
    \begin{axis}[minor tick num=1,
      title={TD 2003},
      xlabel={k}, ylabel={NDCG@k},
      xmin={1}, xmax={20}, ymin={0.4}, ymax={1.0}]
      
      \addplot[ultra thick, color=blue, mark=*] table [x index=0, y index=1, header=true]
      {./Plots/td2003_all.txt};

      \addplot[ultra thick, color=red, mark=x] table [x index=0, y index=14, header=true]
      {./Plots/td2003_all.txt};

      \legend{RoBiRank, IdentityLoss}
    \end{axis}
  \end{tikzpicture}
  \begin{tikzpicture}[scale=0.60]
    \begin{axis}[minor tick num=1,
      title={TD 2004},
      xlabel={k}, ylabel={NDCG@k},
      xmin={1}, xmax={20}, ymin={0.4}, ymax={1.0}]
      
      \addplot[ultra thick, color=blue, mark=*] table [x index=0, y index=1, header=true]
      {./Plots/td2004_all.txt};

      \addplot[ultra thick, color=red, mark=x] table [x index=0, y index=14, header=true]
      {./Plots/td2004_all.txt};

    \end{axis}
  \end{tikzpicture}
  % \caption{Performance comparison on LETOR benchmark datasets.}
  \begin{tikzpicture}[scale=0.60]
    \begin{axis}[minor tick num=1,
      title={HP 2003},
      xlabel={k}, ylabel={NDCG@k},
      xmin={1}, xmax={20},
      ymin={0.4}, ymax={1.0},
      legend pos={south east}]
      
      \addplot[ultra thick, color=blue, mark=*] table [x index=0, y index=1, header=true]
      {./Plots/hp2003_all.txt};

      \addplot[ultra thick, color=red, mark=x] table [x index=0, y index=14, header=true]
      {./Plots/hp2003_all.txt};

    \end{axis}
  \end{tikzpicture}
  \begin{tikzpicture}[scale=0.60]
    \begin{axis}[minor tick num=1,
      title={HP 2004},
      xlabel={k}, ylabel={NDCG@k},
      xmin={1}, xmax={20}, ymin={0.4}, ymax={1.0},
      legend pos={south east}]
      
      \addplot[ultra thick, color=blue, mark=*] table [x index=0, y index=1, header=true]
      {./Plots/hp2004_all.txt};

      \addplot[ultra thick, color=red, mark=x] table [x index=0, y index=14, header=true]
      {./Plots/hp2004_all.txt};

    \end{axis}
  \end{tikzpicture}
  \begin{tikzpicture}[scale=0.60]
    \begin{axis}[minor tick num=1,
      title={MQ 2007},
      xlabel={k}, ylabel={NDCG@k},
      xmin={1}, xmax={20},
      ymin={0.4}, ymax={1.0}]
      
      \addplot[ultra thick, color=blue, mark=*] table [x index=0, y index=1, header=true]
      {./Plots/mq2007_all.txt};

      \addplot[ultra thick, color=red, mark=x] table [x index=0, y index=14, header=true]
      {./Plots/mq2007_all.txt};
	  
    \end{axis}
  \end{tikzpicture}
  \begin{tikzpicture}[scale=0.60]
    \begin{axis}[minor tick num=1,
      title={MQ 2008},
      xlabel={k}, ylabel={NDCG@k},
      xmin={1}, xmax={20}, ymin={0.4}, ymax={1.0}]
      
      \addplot[ultra thick, color=blue, mark=*] table [x index=0, y index=1, header=true]
      {./Plots/mq2008_all.txt};

      \addplot[ultra thick, color=red, mark=x] table [x index=0, y index=14, header=true]
      {./Plots/mq2008_all.txt};

    \end{axis}
  \end{tikzpicture}
  \caption{Comparison of RoBiRank with other baselines (Identity Loss), see Section~\ref{sec:CompBaselines} }\label{fig:ndcg_otherbaselines}
\end{figure*}

\subsection{Sensitivity to Initialization}
\label{sec:SensInit}

We also investigated the sensitivity of parameter estimation to the
choice of initial parameter.  We initialized $\omega$ randomly with 10
different seed values.  Blue lines in Figure~\ref{fig:ranker_all} show
mean and standard deviation of NDCG values at different levels of
truncation; as can be seen, even though our objective function is
non-convex, L-BFGS reliably converges to solutions with similar test
performance. This conclusion is in line with the observation
of~\citet{Ding13}.  We also tried two more variants; initialization by
all-zeroes (red line) and the solution of RankSVM (black line).  In most
cases it did not affect the quality of solution, but on TD 2003 and HP
2004 datasets, zero initialization gave slightly better results.

\subsection{Comparison with other baselines}
\label{sec:CompBaselines}

We also compared RoBiRank against other baselines, namely - Identity Loss (obtained by replacing $\rho_1$ by the identity result in the convex loss of \citet{BufGalUsuCal11}). % and Robust Loss (obtained by adding a robust transformation $\rho_1$ on the individual logistic losses instead of using $\rho_1$ on the sum of logistic losses)%. 
We show the results of these experiments on small-medium LETOR datasets and on a large dataset (million song dataset) in Table~\ref{tb:otherbaselines} and Figure~\ref{fig:ndcg_otherbaselines}. As can be seen, RoBiRank comprehensively outperforms these baselines.

\begin{figure*}% [htbp]
  \centering
  \begin{tikzpicture}[scale=0.60]
    \begin{axis}[minor tick num=1,
      title={TD 2003},
      xlabel={k}, ylabel={NDCG@k},
      xmin={1}, xmax={20}, legend pos={south east}]
      
      % \addplot+[mark=*, color=blue] table [x index=0, y index=1, header=true]
      % {./Plots/td2004.txt};

      \addplot+[
      color=blue, mark=*, thick,
      error bars/.cd,
      y dir=both, y explicit,
      error mark=-]
      table[x=x,y=y,y error=errory]
      {./Plots/td2003errorbar.txt};
      
      \addplot+[thick, mark=x, color=red, mark options=solid] table [x index=0, y index=3, header=true]
      {./Plots/td2003errorbar.txt};

      \addplot+[ultra thick, mark=o, color=black, mark options=solid] table [x index=0, y index=4, header=true]
      {./Plots/td2003errorbar.txt};

      \legend{random initialization, zero initialization, initialization by RankSVM}
    \end{axis}
  \end{tikzpicture}
  \begin{tikzpicture}[scale=0.60]
    \begin{axis}[minor tick num=1,
      title={TD 2004},
      xlabel={k}, ylabel={NDCG@k},
      xmin={1}, xmax={20}, legend pos={north east}]
      
      % \addplot+[mark=*, color=blue] table [x index=0, y index=1, header=true]
      % {./Plots/td2004.txt};

      \addplot+[
      color=blue, mark=*, thick,
      error bars/.cd,
      y dir=both, y explicit,
      error mark=-]
      table[x=x,y=y,y error=errory]
      {./Plots/td2004errorbar.txt};
      
      \addplot+[thick, mark=x, color=red, mark options=solid] table [x index=0, y index=3, header=true]
      {./Plots/td2004errorbar.txt};

      \addplot+[ultra thick, mark=o, color=black, mark options=solid] table [x index=0, y index=4, header=true]
      {./Plots/td2004errorbar.txt};

      \legend{random initialization, zero initialization, initialization by RankSVM}
    \end{axis}
  \end{tikzpicture}
  \begin{tikzpicture}[scale=0.60]
    \begin{axis}[minor tick num=1,
      title={Yahoo Learning to Rank - 1},
      xlabel={k}, ylabel={NDCG@k},
      xmin={1}, xmax={20}, legend pos={south east}]
      
      % \addplot+[mark=*, color=blue] table [x index=0, y index=1, header=true]
      % {./Plots/td2004.txt};

      \addplot+[
      color=blue, mark=*, thick,
      error bars/.cd,
      y dir=both, y explicit,
      error mark=-]
      table[x=x,y=y,y error=errory]
      {./Plots/yahooltrcset1errorbar.txt};
      
      \addplot+[thick, mark=x, color=red, mark options=solid] table [x index=0, y index=3, header=true]
      {./Plots/yahooltrcset1errorbar.txt};

      \addplot+[ultra thick, mark=o, color=black, mark options=solid] table [x index=0, y index=4, header=true]
      {./Plots/yahooltrcset1errorbar.txt};

      \legend{random initialization, zero initialization, initialization by RankSVM}
    \end{axis}
  \end{tikzpicture}
  \begin{tikzpicture}[scale=0.60]
    \begin{axis}[minor tick num=1,
      title={Yahoo Learning to Rank - 2},
      xlabel={k}, ylabel={NDCG@k},
      xmin={1}, xmax={20}, legend pos={south east}]
      
      % \addplot+[mark=*, color=blue] table [x index=0, y index=1, header=true]
      % {./Plots/td2004.txt};

      \addplot+[
      color=blue, mark=*, thick,
      error bars/.cd,
      y dir=both, y explicit,
      error mark=-]
      table[x=x,y=y,y error=errory]
      {./Plots/yahooltrcset2errorbar.txt};
      
      \addplot+[thick, mark=x, color=red, mark options=solid] table [x index=0, y index=3, header=true]
      {./Plots/yahooltrcset2errorbar.txt};

      \addplot+[ultra thick, mark=o, color=black, mark options=solid] table [x index=0, y index=4, header=true]
      {./Plots/yahooltrcset2errorbar.txt};

      \legend{random initialization, zero initialization, initialization by RankSVM}
    \end{axis}
  \end{tikzpicture}
  \begin{tikzpicture}[scale=0.60]
    \begin{axis}[minor tick num=1,
      title={HP 2003},
      xlabel={k}, ylabel={NDCG@k},
      xmin={1}, xmax={20}, legend pos={south east}]
      
      % \addplot+[mark=*, color=blue] table [x index=0, y index=1, header=true]
      % {./Plots/td2004.txt};

      \addplot+[
      color=blue, mark=*, thick,
      error bars/.cd,
      y dir=both, y explicit,
      error mark=-]
      table[x=x,y=y,y error=errory]
      {./Plots/hp2003errorbar.txt};
      
      \addplot+[thick, mark=x, color=red, mark options=solid] table [x index=0, y index=3, header=true]
      {./Plots/hp2003errorbar.txt};

      \addplot+[ultra thick, mark=o, color=black, mark options=solid] table [x index=0, y index=4, header=true]
      {./Plots/hp2003errorbar.txt};

      \legend{random initialization, zero initialization, initialization by RankSVM}
    \end{axis}
  \end{tikzpicture}
  \begin{tikzpicture}[scale=0.60]
    \begin{axis}[minor tick num=1,
      title={HP 2004},
      xlabel={k}, ylabel={NDCG@k},
      xmin={1}, xmax={20}, legend pos={south east}]
      
      % \addplot+[mark=*, color=blue] table [x index=0, y index=1, header=true]
      % {./Plots/td2004.txt};

      \addplot+[
      color=blue, mark=*, thick,
      error bars/.cd,
      y dir=both, y explicit,
      error mark=-]
      table[x=x,y=y,y error=errory]
      {./Plots/hp2004errorbar.txt};
      
      \addplot+[thick, mark=x, color=red, mark options=solid] table [x index=0, y index=3, header=true]
      {./Plots/hp2004errorbar.txt};

      \addplot+[ultra thick, mark=o, color=black, mark options=solid] table [x index=0, y index=4, header=true]
      {./Plots/hp2004errorbar.txt};

      \legend{random initialization, zero initialization, initialization by RankSVM}
    \end{axis}
  \end{tikzpicture}
  \begin{tikzpicture}[scale=0.60]
    \begin{axis}[minor tick num=1,
      title={OHSUMED},
      xlabel={k}, ylabel={NDCG@k},
      xmin={1}, xmax={20}, legend pos={south east}]
      
      % \addplot+[mark=*, color=blue] table [x index=0, y index=1, header=true]
      % {./Plots/td2004.txt};

      \addplot+[
      color=blue, mark=*, thick,
      error bars/.cd,
      y dir=both, y explicit,
      error mark=-]
      table[x=x,y=y,y error=errory]
      {./Plots/ohsumederrorbar.txt};
      
      \addplot+[thick, mark=x, color=red, mark options=solid] table [x index=0, y index=3, header=true]
      {./Plots/ohsumederrorbar.txt};

      \addplot+[ultra thick, mark=o, color=black, mark options=solid] table [x index=0, y index=4, header=true]
      {./Plots/ohsumederrorbar.txt};

      \legend{random initialization, zero initialization, initialization by RankSVM}
    \end{axis}
  \end{tikzpicture}
  \begin{tikzpicture}[scale=0.60]
    \begin{axis}[minor tick num=1,
      title={MSLR30K},
      xlabel={k}, ylabel={NDCG@k},
      xmin={1}, xmax={20}, legend pos={south east}]
      
      % \addplot+[mark=*, color=blue] table [x index=0, y index=1, header=true]
      % {./Plots/td2004.txt};

      \addplot+[
      color=blue, mark=*, thick,
      error bars/.cd,
      y dir=both, y explicit,
      error mark=-]
      table[x=x,y=y,y error=errory]
      {./Plots/mslr30Kerrorbar.txt};
      
      \addplot+[thick, mark=x, color=red, mark options=solid] table [x index=0, y index=3, header=true]
      {./Plots/mslr30Kerrorbar.txt};

      \addplot+[ultra thick, mark=o, color=black, mark options=solid] table [x index=0, y index=4, header=true]
      {./Plots/mslr30Kerrorbar.txt};

      \legend{random initialization, zero initialization, initialization by RankSVM}
    \end{axis}
  \end{tikzpicture}
  \begin{tikzpicture}[scale=0.60]
    \begin{axis}[minor tick num=1,
      title={MQ 2007},
      xlabel={k}, ylabel={NDCG@k},
      xmin={1}, xmax={20}, legend pos={south east}]
      
      % \addplot+[mark=*, color=blue] table [x index=0, y index=1, header=true]
      % {./Plots/td2004.txt};

      \addplot+[
      color=blue, mark=*, thick,
      error bars/.cd,
      y dir=both, y explicit,
      error mark=-]
      table[x=x,y=y,y error=errory]
      {./Plots/mq2007errorbar.txt};
      
      \addplot+[thick, mark=x, color=red, mark options=solid] table [x index=0, y index=3, header=true]
      {./Plots/mq2007errorbar.txt};

      \addplot+[ultra thick, mark=o, color=black, mark options=solid] table [x index=0, y index=4, header=true]
      {./Plots/mq2007errorbar.txt};

      \legend{random initialization, zero initialization, initialization by RankSVM}
    \end{axis}
  \end{tikzpicture}
  \begin{tikzpicture}[scale=0.60]
    \begin{axis}[minor tick num=1,
      title={MQ 2008},
      xlabel={k}, ylabel={NDCG@k},
      xmin={1}, xmax={20}, legend pos={south east}]
      
      % \addplot+[mark=*, color=blue] table [x index=0, y index=1, header=true]
      % {./Plots/td2004.txt};

      \addplot+[
      color=blue, mark=*, thick,
      error bars/.cd,
      y dir=both, y explicit,
      error mark=-]
      table[x=x,y=y,y error=errory]
      {./Plots/mq2008errorbar.txt};
      
      \addplot+[thick, mark=x, color=red, mark options=solid] table [x index=0, y index=3, header=true]
      {./Plots/mq2008errorbar.txt};

      \addplot+[ultra thick, mark=o, color=black, mark options=solid] table [x index=0, y index=4, header=true]
      {./Plots/mq2008errorbar.txt};

      \legend{random initialization, zero initialization, initialization by RankSVM}
    \end{axis}
  \end{tikzpicture}
  \caption{Performance of RoBiRank based on different initialization methods}\label{fig:ranker_all}
\end{figure*}

\section{Pseudocode of the Serial Algorithm}
\label{sec:PseudSeriAlgor}

\begin{algorithm}
  \begin{algorithmic}
    \STATE {$\eta$: step size}

    \REPEAT

    \STATE {\texttt{// $(U,V)$-step}}
    \REPEAT

    \STATE {Sample $(x,y)$ uniformly from $\Omega$}
    \STATE {Sample $y'$ uniformly from $\Ycal \setminus \cbr{y}$}
    \STATE {$U_x \leftarrow U_x - \eta \cdot \xi_{xy} \cdot 
      \nabla_{U_x} \sigma_0(f(U_x,V_y) - f(U_x, V_{y'}))$}
    \STATE {$V_y \leftarrow V_y - \eta \cdot \xi_{xy} \cdot 
      \nabla_{V_y} \sigma_0(f(U_x,V_y) - f(U_x, V_{y'}))$}
    \UNTIL {convergence in $U,V$}

    \STATE {\texttt{// $\xi$-step}}
    \FOR {$(x,y) \in \Omega$}
    \STATE {$\xi_{xy} \leftarrow \frac 1 
      {\sum_{y' \neq y} \sigma_0(f(U_x,V_y) - f(U_x, V_{y'})) + 1} $}
    \ENDFOR
    \UNTIL {convergence in $U,V$ and $\xi$}
  \end{algorithmic}
  \caption{Serial parameter estimation algorithm for latent
    collaborative retrieval}
  \label{alg:twostage}
\end{algorithm}


\section{Description of Parallel Algorithm}
\label{sec:DescrParallAlgor}

Suppose there are $p$ number of machines.  The set of contexts $\Xcal$
is randomly partitioned into mutually exclusive and exhaustive subsets
$\Xcal^{(1)}, \Xcal^{(2)}, \ldots, \Xcal^{(p)}$ which are of
approximately the same size.  This partitioning is fixed and does not
change over time.  The partition on $\Xcal$ induces partitions on
other variables as follows:
% \begin{align}
$U^{(q)} := \cbr{ U_x }_{x \in \Xcal^{(q)}}$, 
% \\
%  V^{(r)} &:= \cbr{ V_y }_{y \in \Ycal^{(r)}} \\
$\Omega^{(q)} := \cbr{ (x,y) \in \Omega : x \in \Xcal^{(q)}}$,
$\xi^{(q)} := \cbr{ \xi_{xy} }_{(x,y) \in \Omega^{(q)}}$, 
% \\
% \end{align}
for $1 \leq q \leq p$.
% $U^{(q)} := \cbr{ U_x }_{x \in \Xcal^{(q)}}$,
% $V^{(r)} := \cbr{ V_y }_{y \in \Ycal^{(r)}}$, $\xi^{(q)} := \cbr{
%   \xi_{xy} }_{(x,y) \in \Omega^{(q)}}$

Each machine $q$ stores variables $U^{(q)}$, $\xi^{(q)}$ and
$\Omega^{(q)}$.  Since the partition on $\Xcal$ is fixed, these
variables are local to each machine and are not communicated.  Now we
describe how to parallelize each step of the algorithm: the
pseudo-code can be found in Algorithm~\ref{alg:parallel}.

\begin{algorithm}[!ht]
  \begin{algorithmic}
    \STATE {$\eta$: step size}

    \REPEAT

    \STATE {\texttt{// parallel $(U,V)$-step}}
    \REPEAT

    \STATE {Sample a partition $\cbr{\Ycal^{(1)}, \Ycal^{(2)}, \ldots,
        \Ycal^{(q)}}$}

    \FORALLP {$q \in \cbr{1,2,\ldots,p}$}
    \STATE {Fetch all $V_y \in V^{(q)}$}

    \REPEAT

    \STATE {Sample $(x,y)$ uniformly from\\ \hspace{0.3in} $\cbr{(x,y) \in
        \Omega^{(q)}, y \in \Ycal^{(q)}}$} 
    \STATE {Sample $y'$
      uniformly from $\Ycal^{(q)} \setminus \cbr{y}$} 
    \STATE {$U_x \leftarrow$ \\ \hspace{0.1in} $U_x -
      \eta \cdot \xi_{xy} \cdot \nabla_{U_x} \sigma_0(f(U_x,V_y) -
      f(U_x, V_{y'}))$} 
    \STATE {$V_y \leftarrow$ \\ \hspace{0.1in} $V_y - \eta \cdot
      \xi_{xy} \cdot \nabla_{V_y} \sigma_0(f(U_x,V_y) - f(U_x,
      V_{y'}))$}
    
    \UNTIL {predefined time limit is exceeded}

    \ENDFOR

    \UNTIL {convergence in $U,V$}

    \STATE {\texttt{// parallel $\xi$-step}}

    \FORALLP {$q \in \cbr{1,2,\ldots,p}$}
    \STATE {Fetch all $V_y \in V$}

    \FOR {$(x,y) \in \Omega^{(q)}$}
    \STATE {$\xi_{xy} \leftarrow \frac 1 
      {\sum_{y' \neq y} \sigma_0(f(U_x,V_y) - f(U_x, V_{y'})) + 1} $}
    \ENDFOR

    \ENDFOR

    \UNTIL {convergence in $U,V$ and $\xi$}
  \end{algorithmic}
  \caption{Multi-machine parameter estimation algorithm for latent
    collaborative retrieval}
  \label{alg:parallel}
\end{algorithm}


\paragraph{$(U,V)$-step}

At the start of each $(U,V)$-step, a new partition on $\Ycal$ is sampled
to divide $\Ycal$ into $\Ycal^{(1)}, \Ycal^{(2)}, \ldots, \Ycal^{(p)}$
which are also mutually exclusive, exhaustive and of approximately the
same size.  The difference here is that unlike the partition on
$\Xcal$, a new partition on $\Ycal$ is sampled for every $(U,V)$-step.
Let us define 
%\begin{align}
$V^{(q)} := \cbr{ V_y }_{y \in \Ycal^{(q)}}$.
%\end{align}
After the partition on $\Ycal$ is sampled, each machine $q$ fetches
$V_y$'s in $V^{(q)}$ from where it was previously stored; in the very
first iteration which no previous information exists, each machine
generates and initializes these parameters instead.  Now let us define
$L^{(q)}(U^{(q)},V^{(q)},\xi^{(q)}) :=$
\begin{align*}
  \sum_{(x,y) \in \Omega^{(q)}, y
    \in \Ycal^{(q)}} - \log_2\xi_{xy} + \frac{\xi_{xy} \rbr{ \sum_{y'
        \in \Ycal^{(q)}, y' \neq y} \sigma_0(f(U_x,V_y) - f(U_x,
      V_{y'})) + 1} - 1}{\log 2} .
\end{align*} 
In parallel setting, each machine $q$ runs stochastic gradient descent
on $L^{(q)}(U^{(q)},V^{(q)},\xi^{(q)})$ instead of the original
function $L(U,V,\xi)$.  Since there is no overlap between machines on
the parameters they update and the data they access, every machine can
progress independently of each other.  Although the algorithm takes
only a fraction of data into consideration at a time, this procedure
is also guaranteed to converge to a local optimum of the
\emph{original} function $L(U,V,\xi)$ according to Stratified
Stochastic Gradient Descent (SSGD) scheme of \citet{GemNijHaaSis11}.
The intuition is as follows: if we take expectation over the random
partition on $\Ycal$, we have $  \nabla_{U,V} L(U,V,\xi) = $
\begin{align*}
  q^2 \cdot \EE
  \sbr{ \sum_{1 \leq q \leq p} \nabla_{U,V} L^{(q)}(U^{(q)}, V^{(q)}, \xi^{(q)}) }.
\end{align*}
Therefore, although there is some discrepancy between the function we
take stochastic gradient on and the function we actually aim to
minimize, in the long run the bias will be washed out and the
algorithm will converge to a local optimum of the objective function
$L(U,V,\xi)$.

\paragraph{$\xi$-step}

In this step, all machines synchronize to retrieve every entry of
$V$.  Then, each machine can update $\xi^{(q)}$ independently of each
other.  When the size of $V$ is very large and cannot be fit into the
main memory of a single machine, $V$ can be partitioned as in
$(U,V)$-step and updates can be calculated in a round-robin way.

Note that this parallelization scheme requires each machine to
allocate only $\frac 1 p$-fraction of memory that would be required
for a single-machine execution.  Therefore, in terms of space
complexity the algorithm scales linearly with the number of machines.

\end{document}

rankbib.bbl
\begin{thebibliography}{24}
\providecommand{\natexlab}[1]{#1}
\providecommand{\url}[1]{\texttt{#1}}
\expandafter\ifx\csname urlstyle\endcsname\relax
  \providecommand{\doi}[1]{doi: #1}\else
  \providecommand{\doi}{doi: \begingroup \urlstyle{rm}\Url}\fi

\bibitem[Agarwal(2011)]{Aga11}
S.~Agarwal.
\newblock The infinite push: A new support vector ranking algorithm that
  directly optimizes accuracy at the absolute top of the list.
\newblock In \emph{SDM}, pages 839--850. SIAM, 2011.

\bibitem[Bartlett et~al.(2006)Bartlett, Jordan, and McAuliffe]{JorBarMcA06}
P.~L. Bartlett, M.~I. Jordan, and J.~D. McAuliffe.
\newblock Convexity, classification, and risk bounds.
\newblock \emph{Journal of the American Statistical Association}, 101\penalty0
  (473):\penalty0 138--156, 2006.

\bibitem[Bertin-Mahieux et~al.(2011)Bertin-Mahieux, Ellis, Whitman, and
  Lamere]{BerEllWhiLam13}
T.~Bertin-Mahieux, D.~P. Ellis, B.~Whitman, and P.~Lamere.
\newblock The million song dataset.
\newblock In \emph{{Proceedings of the 12th International Conference on Music
  Information Retrieval ({ISMIR} 2011)}}, 2011.

\bibitem[Bottou and Bousquet(2011)]{BotBou11}
L.~Bottou and O.~Bousquet.
\newblock The tradeoffs of large-scale learning.
\newblock \emph{Optimization for Machine Learning}, page 351, 2011.

\bibitem[Bouchard(2007)]{Bouchard07}
G.~Bouchard.
\newblock Efficient bounds for the softmax function, applications to inference
  in hybrid models.
\newblock 2007.

\bibitem[Boyd and Vandenberghe(2004)]{BoyVan04}
S.~Boyd and L.~Vandenberghe.
\newblock \emph{Convex Optimization}.
\newblock Cambridge University Press, Cambridge, England, 2004.

\bibitem[Buffoni et~al.(2011)Buffoni, Gallinari, Usunier, and
  Calauz{\`e}nes]{BufGalUsuCal11}
D.~Buffoni, P.~Gallinari, N.~Usunier, and C.~Calauz{\`e}nes.
\newblock Learning scoring functions with order-preserving losses and
  standardized supervision.
\newblock In \emph{Proceedings of the 28th International Conference on Machine
  Learning (ICML-11)}, pages 825--832, 2011.

\bibitem[Chapelle and Chang(2011)]{ChaCha11}
O.~Chapelle and Y.~Chang.
\newblock Yahoo! learning to rank challenge overview.
\newblock \emph{Journal of Machine Learning Research-Proceedings Track},
  14:\penalty0 1--24, 2011.

\bibitem[Chapelle et~al.(2008)Chapelle, Do, Teo, Le, and
  Smola]{ChaDoTeoLeSmo08}
O.~Chapelle, C.~B. Do, C.~H. Teo, Q.~V. Le, and A.~J. Smola.
\newblock Tighter bounds for structured estimation.
\newblock In \emph{Advances in neural information processing systems}, pages
  281--288, 2008.

\bibitem[Ding(2013)]{Ding13}
N.~Ding.
\newblock \emph{Statistical Machine Learning in T-Exponential Family of
  Distributions}.
\newblock PhD thesis, PhD thesis, Purdue University, West Lafayette, Indiana,
  USA, 2013.

\bibitem[Feldman et~al.(2012)Feldman, Guruswami, Raghavendra, and
  Wu]{FelGurRagWu12}
V.~Feldman, V.~Guruswami, P.~Raghavendra, and Y.~Wu.
\newblock Agnostic learning of monomials by halfspaces is hard.
\newblock \emph{SIAM Journal on Computing}, 41\penalty0 (6):\penalty0
  1558--1590, 2012.

\bibitem[Gemulla et~al.(2011)Gemulla, Nijkamp, Haas, and
  Sismanis]{GemNijHaaSis11}
R.~Gemulla, E.~Nijkamp, P.~J. Haas, and Y.~Sismanis.
\newblock Large-scale matrix factorization with distributed stochastic gradient
  descent.
\newblock In \emph{Conference on Knowledge Discovery and Data Mining}, pages
  69--77, 2011.

\bibitem[Huber(1981)]{Huber81}
P.~J. Huber.
\newblock \emph{Robust Statistics}.
\newblock John Wiley and Sons, New York, 1981.

\bibitem[Le and Smola(2007)]{LeSmo07}
Q.~V. Le and A.~J. Smola.
\newblock Direct optimization of ranking measures.
\newblock Technical Report 0704.3359, arXiv, April 2007.
\newblock \url{http://arxiv.org/abs/0704.3359}.

\bibitem[Lee and Lin(2013)]{LeeLin13}
C.-P. Lee and C.-J. Lin.
\newblock Large-scale linear ranksvm.
\newblock \emph{Neural Computation}, 2013.
\newblock To Appear.

\bibitem[Long and Servedio(2010)]{LonSer10}
P.~Long and R.~Servedio.
\newblock Random classification noise defeats all convex potential boosters.
\newblock \emph{Machine Learning Journal}, 78\penalty0 (3):\penalty0 287--304,
  2010.

\bibitem[Manning et~al.(2008)Manning, Raghavan, and Sch{\"u}tze]{ManRagSch08}
C.~D. Manning, P.~Raghavan, and H.~Sch{\"u}tze.
\newblock \emph{Introduction to Information Retrieval}.
\newblock Cambridge University Press, 2008.
\newblock URL \url{http://nlp.stanford.edu/IR-book/}.

\bibitem[Nemirovski et~al.(2009)Nemirovski, Juditsky, Lan, and
  Shapiro]{NemJudLanSha09}
A.~Nemirovski, A.~Juditsky, G.~Lan, and A.~Shapiro.
\newblock Robust stochastic approximation approach to stochastic programming.
\newblock \emph{SIAM Journal on Optimization}, 19\penalty0 (4):\penalty0
  1574--1609, 2009.

\bibitem[Nocedal and Wright(2006)]{NocWri06}
J.~Nocedal and S.~J. Wright.
\newblock \emph{Numerical Optimization}.
\newblock Springer Series in Operations Research. Springer, 2nd edition, 2006.

\bibitem[Qin et~al.(2010)Qin, Liu, Xu, and Li]{QinLiuXuLi10}
T.~Qin, T.-Y. Liu, J.~Xu, and H.~Li.
\newblock Letor: A benchmark collection for research on learning to rank for
  information retrieval.
\newblock \emph{Information Retrieval}, 13\penalty0 (4):\penalty0 346--374,
  2010.

\bibitem[Robbins and Monro(1951)]{RobMon51}
H.~E. Robbins and S.~Monro.
\newblock A stochastic approximation method.
\newblock \emph{Annals of Mathematical Statistics}, 22:\penalty0 400--407,
  1951.

\bibitem[Rudin(2009)]{Rudin09}
C.~Rudin.
\newblock The p-norm push: A simple convex ranking algorithm that concentrates
  at the top of the list.
\newblock \emph{The Journal of Machine Learning Research}, 10:\penalty0
  2233--2271, 2009.

\bibitem[Usunier et~al.(2009)Usunier, Buffoni, and Gallinari]{UsuBufGal09}
N.~Usunier, D.~Buffoni, and P.~Gallinari.
\newblock Ranking with ordered weighted pairwise classification.
\newblock In \emph{Proceedings of the International Conference on Machine
  Learning}, 2009.

\bibitem[Weston et~al.(2012)Weston, Wang, Weiss, and
  Berenzweig]{WesWanWeiBer12}
J.~Weston, C.~Wang, R.~Weiss, and A.~Berenzweig.
\newblock Latent collaborative retrieval.
\newblock \emph{arXiv preprint arXiv:1206.4603}, 2012.

\end{thebibliography}

robirank.bbl
\begin{thebibliography}{24}
\providecommand{\natexlab}[1]{#1}
\providecommand{\url}[1]{\texttt{#1}}
\expandafter\ifx\csname urlstyle\endcsname\relax
  \providecommand{\doi}[1]{doi: #1}\else
  \providecommand{\doi}{doi: \begingroup \urlstyle{rm}\Url}\fi

\bibitem[Agarwal(2011)]{Aga11}
S.~Agarwal.
\newblock The infinite push: A new support vector ranking algorithm that
  directly optimizes accuracy at the absolute top of the list.
\newblock In \emph{SDM}, pages 839--850. SIAM, 2011.

\bibitem[Bartlett et~al.(2006)Bartlett, Jordan, and McAuliffe]{JorBarMcA06}
P.~L. Bartlett, M.~I. Jordan, and J.~D. McAuliffe.
\newblock Convexity, classification, and risk bounds.
\newblock \emph{Journal of the American Statistical Association}, 101\penalty0
  (473):\penalty0 138--156, 2006.

\bibitem[Bertin-Mahieux et~al.(2011)Bertin-Mahieux, Ellis, Whitman, and
  Lamere]{BerEllWhiLam13}
T.~Bertin-Mahieux, D.~P. Ellis, B.~Whitman, and P.~Lamere.
\newblock The million song dataset.
\newblock In \emph{{Proceedings of the 12th International Conference on Music
  Information Retrieval ({ISMIR} 2011)}}, 2011.

\bibitem[Bottou and Bousquet(2011)]{BotBou11}
L.~Bottou and O.~Bousquet.
\newblock The tradeoffs of large-scale learning.
\newblock \emph{Optimization for Machine Learning}, page 351, 2011.

\bibitem[Bouchard(2007)]{Bouchard07}
G.~Bouchard.
\newblock Efficient bounds for the softmax function, applications to inference
  in hybrid models.
\newblock 2007.

\bibitem[Boyd and Vandenberghe(2004)]{BoyVan04}
S.~Boyd and L.~Vandenberghe.
\newblock \emph{Convex Optimization}.
\newblock Cambridge University Press, Cambridge, England, 2004.

\bibitem[Buffoni et~al.(2011)Buffoni, Gallinari, Usunier, and
  Calauz{\`e}nes]{BufGalUsuCal11}
D.~Buffoni, P.~Gallinari, N.~Usunier, and C.~Calauz{\`e}nes.
\newblock Learning scoring functions with order-preserving losses and
  standardized supervision.
\newblock In \emph{Proceedings of the 28th International Conference on Machine
  Learning (ICML-11)}, pages 825--832, 2011.

\bibitem[Chapelle and Chang(2011)]{ChaCha11}
O.~Chapelle and Y.~Chang.
\newblock Yahoo! learning to rank challenge overview.
\newblock \emph{Journal of Machine Learning Research-Proceedings Track},
  14:\penalty0 1--24, 2011.

\bibitem[Chapelle et~al.(2008)Chapelle, Do, Teo, Le, and
  Smola]{ChaDoTeoLeSmo08}
O.~Chapelle, C.~B. Do, C.~H. Teo, Q.~V. Le, and A.~J. Smola.
\newblock Tighter bounds for structured estimation.
\newblock In \emph{Advances in neural information processing systems}, pages
  281--288, 2008.

\bibitem[Ding(2013)]{Ding13}
N.~Ding.
\newblock \emph{Statistical Machine Learning in T-Exponential Family of
  Distributions}.
\newblock PhD thesis, PhD thesis, Purdue University, West Lafayette, Indiana,
  USA, 2013.

\bibitem[Feldman et~al.(2012)Feldman, Guruswami, Raghavendra, and
  Wu]{FelGurRagWu12}
V.~Feldman, V.~Guruswami, P.~Raghavendra, and Y.~Wu.
\newblock Agnostic learning of monomials by halfspaces is hard.
\newblock \emph{SIAM Journal on Computing}, 41\penalty0 (6):\penalty0
  1558--1590, 2012.

\bibitem[Gemulla et~al.(2011)Gemulla, Nijkamp, Haas, and
  Sismanis]{GemNijHaaSis11}
R.~Gemulla, E.~Nijkamp, P.~J. Haas, and Y.~Sismanis.
\newblock Large-scale matrix factorization with distributed stochastic gradient
  descent.
\newblock In \emph{Conference on Knowledge Discovery and Data Mining}, pages
  69--77, 2011.

\bibitem[Huber(1981)]{Huber81}
P.~J. Huber.
\newblock \emph{Robust Statistics}.
\newblock John Wiley and Sons, New York, 1981.

\bibitem[Le and Smola(2007)]{LeSmo07}
Q.~V. Le and A.~J. Smola.
\newblock Direct optimization of ranking measures.
\newblock Technical Report 0704.3359, arXiv, April 2007.
\newblock \url{http://arxiv.org/abs/0704.3359}.

\bibitem[Lee and Lin(2013)]{LeeLin13}
C.-P. Lee and C.-J. Lin.
\newblock Large-scale linear ranksvm.
\newblock \emph{Neural Computation}, 2013.
\newblock To Appear.

\bibitem[Long and Servedio(2010)]{LonSer10}
P.~Long and R.~Servedio.
\newblock Random classification noise defeats all convex potential boosters.
\newblock \emph{Machine Learning Journal}, 78\penalty0 (3):\penalty0 287--304,
  2010.

\bibitem[Manning et~al.(2008)Manning, Raghavan, and Sch{\"u}tze]{ManRagSch08}
C.~D. Manning, P.~Raghavan, and H.~Sch{\"u}tze.
\newblock \emph{Introduction to Information Retrieval}.
\newblock Cambridge University Press, 2008.
\newblock URL \url{http://nlp.stanford.edu/IR-book/}.

\bibitem[Nemirovski et~al.(2009)Nemirovski, Juditsky, Lan, and
  Shapiro]{NemJudLanSha09}
A.~Nemirovski, A.~Juditsky, G.~Lan, and A.~Shapiro.
\newblock Robust stochastic approximation approach to stochastic programming.
\newblock \emph{SIAM Journal on Optimization}, 19\penalty0 (4):\penalty0
  1574--1609, 2009.

\bibitem[Nocedal and Wright(2006)]{NocWri06}
J.~Nocedal and S.~J. Wright.
\newblock \emph{Numerical Optimization}.
\newblock Springer Series in Operations Research. Springer, 2nd edition, 2006.

\bibitem[Qin et~al.(2010)Qin, Liu, Xu, and Li]{QinLiuXuLi10}
T.~Qin, T.-Y. Liu, J.~Xu, and H.~Li.
\newblock Letor: A benchmark collection for research on learning to rank for
  information retrieval.
\newblock \emph{Information Retrieval}, 13\penalty0 (4):\penalty0 346--374,
  2010.

\bibitem[Robbins and Monro(1951)]{RobMon51}
H.~E. Robbins and S.~Monro.
\newblock A stochastic approximation method.
\newblock \emph{Annals of Mathematical Statistics}, 22:\penalty0 400--407,
  1951.

\bibitem[Rudin(2009)]{Rudin09}
C.~Rudin.
\newblock The p-norm push: A simple convex ranking algorithm that concentrates
  at the top of the list.
\newblock \emph{The Journal of Machine Learning Research}, 10:\penalty0
  2233--2271, 2009.

\bibitem[Usunier et~al.(2009)Usunier, Buffoni, and Gallinari]{UsuBufGal09}
N.~Usunier, D.~Buffoni, and P.~Gallinari.
\newblock Ranking with ordered weighted pairwise classification.
\newblock In \emph{Proceedings of the International Conference on Machine
  Learning}, 2009.

\bibitem[Weston et~al.(2012)Weston, Wang, Weiss, and
  Berenzweig]{WesWanWeiBer12}
J.~Weston, C.~Wang, R.~Weiss, and A.~Berenzweig.
\newblock Latent collaborative retrieval.
\newblock \emph{arXiv preprint arXiv:1206.4603}, 2012.

\end{thebibliography}
