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 (<italic>SDP</italic>), which is generally time-consuming and degrades the scalability, especially confronting large-scale data. To overcome this challenge, we propose a stochastic algorithm called <italic>SVRG-SBB</italic>, which has the following features: i) achieving good scalability via dropping positive semi-definite (<italic>PSD</italic>) constraints as serving a fast algorithm, i.e., stochastic variance reduced gradient (<italic>SVRG</italic>) method, and ii) adaptive learning via introducing a new, adaptive step size called the stabilized Barzilai-Borwein (<italic>SBB</italic>) step size. Theoretically, under some natural assumptions, we show the <inline-formula><tex-math notation="LaTeX">$\boldsymbol{O}(\frac{1}{T})$</tex-math> <alternatives><mml:math><mml:mrow><mml:mi mathvariant="bold">O</mml:mi><mml:mo>(</mml:mo><mml:mfrac><mml:mn>1</mml:mn><mml:mi>T</mml:mi></mml:mfrac><mml:mo>)</mml:mo></mml:mrow></mml:math><inline-graphic xlink:href="ma-ieq1-2956700.gif"/></alternatives></inline-formula> rate of convergence to a stationary point of the proposed algorithm, where <inline-formula><tex-math notation="LaTeX">$T$</tex-math> <alternatives><mml:math><mml:mi>T</mml:mi></mml:math><inline-graphic xlink:href="ma-ieq2-2956700.gif"/></alternatives></inline-formula> is the number of total iterations. Under the further Polyak-Ł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.