Learning representation from relative similarity comparisons, often called
ordinal embedding, gains rising attention in recent years. Most of the existing
methods are batch methods designed mainly based on the convex optimization,
say, the projected gradient descent method. However, they are generally
time-consuming due to that the singular value decomposition (SVD) is commonly
adopted during the update, especially when the data size is very large. To
overcome this challenge, we propose a stochastic algorithm called SVRG-SBB,
which has the following features: (a) SVD-free via dropping convexity, with
good scalability by the use of stochastic algorithm, i.e., stochastic variance
reduced gradient (SVRG), and (b) adaptive step size choice via introducing a
new stabilized Barzilai-Borwein (SBB) method as the original version for convex
problems might fail for the considered stochastic \textit{non-convex}
optimization problem. Moreover, we show that the proposed algorithm converges
to a stationary point at a rate $\mathcal{O}(\frac{1}{T})$ in our setting,
where $T$ is the number of total iterations. Numerous simulations and
real-world data experiments are conducted to show the effectiveness of the
proposed algorithm via comparing with the state-of-the-art methods,
particularly, much lower computational cost with good prediction performance.

通过引入一种新的稳定 Barzilai-Borwein (SBB) 方法，我们提出了一种叫做 SVRG-SBB 的随机算法，用于从相对相似性比较中学习表示，该方法不需要使用奇异值分解（SVD），具有良好的可扩展性以及自适应步长选择。 同时，我们通过仿真和实验的方法，展示了该算法与最先进的方法相比，具有更低的计算成本和良好的预测性能。