Landmark Ordinal Embedding

Abstract

In this paper, we aim to learn a low-dimensional Euclidean representationfrom a set of constraints of the form "item j is closer to item i than item k".Existing approaches for this "ordinal embedding" problem require expensiveoptimization procedures, which cannot scale to handle increasingly largerdatasets. To address this issue, we propose a landmark-based strategy, which wecall Landmark Ordinal Embedding (LOE). Our approach trades off statisticalefficiency for computational efficiency by exploiting the low-dimensionality ofthe latent embedding. We derive bounds establishing the statistical consistencyof LOE under the popular Bradley-Terry-Luce noise model. Through a rigorousanalysis of the computational complexity, we show that LOE is significantlymore efficient than conventional ordinal embedding approaches as the number ofitems grows. We validate these characterizations empirically on both syntheticand real datasets. We also present a practical approach that achieves the "bestof both worlds", by using LOE to warm-start existing methods that are morestatistically efficient but computationally expensive.

Quick Read (beta)

\usetikzlibrary

matrix,decorations.pathreplacing,calc,arrows \usetikzlibrarypositioning,decorations.pathreplacing,fit,decorations.pathreplacing,calc \tikzsetfontscale/.style = font= \pgfkeystikz/mymatrixenv/.style=decoration=brace,every left delimiter/.style=xshift=3pt,every right delimiter/.style=xshift=-3pt \pgfkeystikz/mymatrix/.style=matrix of math nodes,left delimiter=[,right delimiter=],inner sep=2pt,column sep=1em,row sep=0.5em,nodes=inner sep=0pt \pgfkeystikz/mymatrixbrace/.style=decorate,thick \tikzset cheating dash/.code args=on #1 off #2 \pgfgetpath\currentpath\pgfprocessround\currentpath\currentpath\currentpath\currentpath\pgfmathparse-#1\pgfmathparse#1+#2\pgfmathparsemax(floor(\rest/\onoff), 1)\pgfmathparsemax((\rest-\onoff*\nfullonoff)/\nfullonoff+#2, #2)\pgfsetdash#1\offexpand0pt \tikzset highlighted/.style = draw, thick, rectangle, rounded corners, inner sep = 0pt, fill = red!15, fill opacity = 0.5

\tikzpicture[baseline=0cm,mymatrixenv]\begin{matrix}[mymatrix,innersep=4pt,% rowsep=2em](m){\hfil&\tikz[overlay,rememberpicture,baseline=(left.base)]{\node% (left){$\qquad$};}&&&&&\\ &&&&&&\\ &&&&&&\\ &&&&&&\\ \tikz[overlay,rememberpicture,baseline=(rpos.base)]{\node(rpos){$~{}~{}$};}&&&% &&&\\ &&&&&&\\ &&&&&&\\ &\tikz[overlay,rememberpicture,baseline=(right.base)]{\node(right){$\qquad$};}% &&&&&\\ };\draw[cheatingdash=on2ptoff2pt,red]([xshift=-0.3ex,yshift=-0.9ex]m-4-1.% southwest)--++(0:3.9cm);\par\draw[mymatrixbrace]($(m.north east)!(m-1-1.north % east)!(m.south east)+(0.5em,0)$)--node[right=2pt]{$n-1$}($(m.north east)!(m-8-% 1.south east)!(m.south east)+(0.5em,0)$);\draw[mymatrixbrace]($(m.north west)!% (m-1-1.north west)!(m.north east)+(0,0.2em)$)--node[above=2pt]{$\ell$}($(m.% north west)!(m-1-7.north east)!(m.north east)+(0,0.2em)$);\draw[mymatrixbrace]% ($(m.north west)!(m-4-1.south west)!(m.south west)-(0.5em,0)$)--node[left=2pt]% {$\ell-1$}($(m.north west)!(m-1-1.north west)!(m.south west)-(0.5em,0)$);\tikz% [overlay,rememberpicture,]{\node[fit=(left.northwest)(right.southeast),% highlighted](r1){};}\qquad\tikz[overlay,rememberpicture,baseline=(medium.base)% ]{\node(medium){$W~{}~{}~{}$};}=\begin{pmatrix}0&\dots&\widetilde{W}_{1,j}&% \dots&\widetilde{W}_{1,\ell}\\ &\ddots&\vdots&&\\ \vdots&&\widetilde{W}_{j-1,j}&\\ \widetilde{W}_{j,1}&\dots&0&\dots&\widetilde{W}_{j,\ell}\\ \vdots&&\widetilde{W}_{j,j}&\\ &&\vdots&\ddots&\\ \widetilde{W}_{\ell-1,1}&\cdots&\widetilde{W}_{\ell-1,j}&\dots&0\end{pmatrix}% \end{equation*}\end{minipage}\par\tikzpicture\tikz[overlay,rememberpicture,]{% \node[aboveof=r1,yshift=3mm]{$R_i$};\node[leftof=rpos,xshift=-2mm,yshift=2mm]{% $R$};\node(hw)[rightof=r1,xshift=3mm,yshift=15mm]{$\widetilde{W}$};\draw[->,>=% stealth^{\prime},thick,red,dashed](hw)edge[bendleft](medium)}\par\begin{% gathered}\displaystyle W+J\cdot\operatorname{diag}(s^{*})\\ \\ \displaystyle\begin{pmatrix}0&\dots&\widetilde{W}_{1,j}+s^{*}_{j}&\dots&% \widetilde{W}_{1,\ell}+s^{*}_{\ell}\\ &\ddots&\vdots&&\\ &&\widetilde{W}_{j-1,j}+s^{*}_{j}&\\ \widetilde{W}_{j,1}+s^{*}_{1}&\dots&0&\dots&\widetilde{W}_{j,\ell}+s^{*}_{\ell% }\\ &&\widetilde{W}_{j,j}+s^{*}_{j}&\\ &&\vdots&\ddots&\\ \widetilde{W}_{\ell-1,1}+s^{*}_{1}&\cdots&\widetilde{W}_{\ell-1,j}+s^{*}_{j}&% \dots&0\end{pmatrix}\end{gathered}\par\par\par\par\end{document}\end{matrix}