  Learning representation from relative similarity comparisons, often called
ordinal embedding, gains rising attention in recent years. Most of the existing
methods are based on semi-definite programming (\textit{SDP}), which is
generally time-consuming and degrades the scalability, especially confronting
large-scale data. To overcome this challenge, we propose a stochastic algorithm
called \textit{SVRG-SBB}, which has the following features: i) achieving good
scalability via dropping positive semi-definite (\textit{PSD}) constraints as
serving a fast algorithm, i.e., stochastic variance reduced gradient
(\textit{SVRG}) method, and ii) adaptive learning via introducing a new,
adaptive step size called the stabilized Barzilai-Borwein (\textit{SBB}) step
size. Theoretically, under some natural assumptions, we show the
$\boldsymbol{O}(\frac{1}{T})$ rate of convergence to a stationary point of the
proposed algorithm, where $T$ is the number of total iterations. Under the
further Polyak-\L{}ojasiewicz assumption, we can show the global linear
convergence (i.e., exponentially fast converging to a global optimum) of the
proposed algorithm. Numerous simulations and real-world data experiments are
conducted to show the effectiveness of the proposed algorithm by comparing with
the state-of-the-art methods, notably, much lower computational cost with good
prediction performance.
