Fast Stochastic Ordinal Embedding with Variance Reduction and Adaptive Step Size

Most of the existing methods are based on semi-definite programming ( SDP), which is generally time-consuming and degrades the scalability, especially confronting large-scale data. T o overcome this challenge, we propose a stochastic algorithm called SVRG-SBB, which has the following features: i) achieving good scalability via dropping positive semi-definite ( PSD) constraints as serving a fast algorithm, i.e., stochastic variance reduced gradient ( SVRG) method, and ii) adaptive learning via introducing a new, adaptive step size called the stabilized Barzilai-Borwein ( SBB) step size. Theoretically, under some natural assumptions, we show the O ( 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- Ł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. Index Terms --Ordinal Embedding, SVRG, Non-Convex Optimization, Barzilai-Borwein (BB) Step Size, .null 1 I NTRODUCTION O RDINAL embedding aims to learn the representation of data as points in a low-dimensional embedded space. Here the "low-dimensional" means the embedding-K. Ma is with the School of Computer Science and T echnology, University of Chinese Academy of Sciences, Beijing 100049, China, and with the Artificial Intelligence Research Center, Peng Cheng Laboratory, Shenzhen 518055, China, and part of this work was performed when he was in the Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China, and in the School of Cyber Security, University of Chinese Academy of Sciences, Beijing 100049, China. Email: make@ucas.ac.cn - J. Zeng is with the School of Computer Information Engineering, Jiangxi Normal University, Nanchang, Jiangxi 330022, China, and part of this work was performed when he was with the Department of Mathematics, Hong Kong University of Science and T echnology, Clear Water Bay, Kowloon, Hong Kong.