# Fast Stochastic Ordinal Embedding with Variance Reduction and Adaptive Step Size

arXiv: https://arxiv.org/abs/1912.00362 · HTML: https://mlsanity.com/paper/1912.00362/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Dec 2019.

## Built on by (most cited first, 1 of 1)

- [On Stochastic Variance Reduced Gradient Method for Semidefinite Optimization](https://mlsanity.com/paper/2101.00236/) (2021)

## Abstract (arXiv)

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 (textitSDP), which is generally time-consuming and degrades the scalability, especially confronting large-scale data. To overcome this challenge, we propose a stochastic algorithm called textitSVRG-SBB, which has the following features: i) achieving good scalability via dropping positive semi-definite (textitPSD) constraints as serving a fast algorithm, i.e., stochastic variance reduced gradient (textitSVRG) method, and ii) adaptive learning via introducing a new, adaptive step size called the stabilized Barzilai-Borwein (textitSBB) step size. Theoretically, under some natural assumptions, we show the boldsymbolO(frac1T) rate of convergence to a stationary point of the proposed algorithm, where T is the number of total iterations. Under the further Polyak-Lojasiewicz 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.