# Stochastic Non-convex Ordinal Embedding with Stabilized Barzilai-Borwein Step Size

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Nov 2017.

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

- [Generalization Error Bound for Hyperbolic Ordinal Embedding](https://mlsanity.com/paper/2105.10475/) (2021)
- [On Stochastic Variance Reduced Gradient Method for Semidefinite Optimization](https://mlsanity.com/paper/2101.00236/) (2021)
- [A Stochastic Variance Reduced Gradient using Barzilai-Borwein Techniques as Second Order Information](https://mlsanity.com/paper/2208.11075/) (2022)
- [Adaptive Bregman Proximal Stochastic Gradient with a Stabilized Barzilai--Borwein Step Size](https://mlsanity.com/paper/2608.12009/) (2026)

## Abstract (arXiv)

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 textitnon-convex optimization problem. Moreover, we show that the proposed algorithm converges to a stationary point at a rate O(frac1T) 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.