Fast Stochastic Ordinal Embedding With Variance Reduction and Adaptive Step Size

doi:10.1109/TKDE.2019.2956700

	Fast Stochastic Ordinal Embedding With Variance Reduction and Adaptive Step Size
	Ma, Ke 1,2; Zeng, Jinshan 3; Xiong, Jiechao 4; Xu, Qianqian 5; Cao, Xiaochun 6,7,8; Liu, Wei 4; Yao, Yuan 9,10
	2021-06-01
发表期刊	IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING
ISSN	1041-4347
卷号	33 期号:6 页码:2467-2478
摘要	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 (SDP), which is generally time-consuming and degrades the scalability, especially confronting large-scale data. To 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-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.
关键词	Ordinal embedding SVRG non-convex optimization barzilai-borwein (BB) step size
DOI	10.1109/TKDE.2019.2956700
收录类别	SCI
语种	英语
资助项目	National Natural Science Foundation of China[61861166002] ; National Natural Science Foundation of China[61672514] ; National Natural Science Foundation of China[61976202] ; National Natural Science Foundation of China[61977038] ; National Natural Science Foundation of China[61603162] ; National Natural Science Foundation of China[61876074] ; Beijing Natural Science Foundation[4172068] ; Beijing Natural Science Foundation[4182079] ; Strategic Priority Research Program of Chinese Academy of Sciences[XDB28000000] ; Youth Innovation Promotion Association CAS ; Hong Kong Research Grant Council (HKRGC)[16303817]
WOS研究方向	Computer Science ; Engineering
WOS类目	Computer Science, Artificial Intelligence ; Computer Science, Information Systems ; Engineering, Electrical & Electronic
WOS记录号	WOS:000649587600011
出版者	IEEE COMPUTER SOC
引用统计
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/17706
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Cao, Xiaochun; Yao, Yuan
作者单位	1.Univ Chinese Acad Sci, Sch Comp Sci & Technol, Beijing 100049, Peoples R China 2.Peng Cheng Lab, Artificial Intelligence Res Ctr, Shenzhen 518055, Peoples R China 3.Jiangxi Normal Univ, Sch Comp Informat Engn, Nanchang 330022, Jiangxi, Peoples R China 4.Tencent AI Lab, Shenzhen 518057, Guangdong, Peoples R China 5.Chinese Acad Sci, Inst Comp Technol, Key Lab Intelligent Informat Proc, Beijing 100190, Peoples R China 6.Chinese Acad Sci, Inst Informat Engn, State Key Lab Informat Secur, Beijing 100093, Peoples R China 7.Peng Cheng Lab, Cyberspace Secur Res Ctr, Shenzhen 518055, Peoples R China 8.Univ Chinese Acad Sci, Sch Cyber Secur, Beijing 100049, Peoples R China 9.Hong Kong Univ Sci & Technol, Dept Math, Kowloon, Clear Water Bay, Hong Kong, Peoples R China 10.Hong Kong Univ Sci & Technol, Dept Comp Sci & Engn, Kowloon, Clear Water Bay, Hong Kong, Peoples R China
推荐引用方式 GB/T 7714	Ma, Ke,Zeng, Jinshan,Xiong, Jiechao,et al. Fast Stochastic Ordinal Embedding With Variance Reduction and Adaptive Step Size[J]. IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING,2021,33(6):2467-2478.
APA	Ma, Ke.,Zeng, Jinshan.,Xiong, Jiechao.,Xu, Qianqian.,Cao, Xiaochun.,...&Yao, Yuan.(2021).Fast Stochastic Ordinal Embedding With Variance Reduction and Adaptive Step Size.IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING,33(6),2467-2478.
MLA	Ma, Ke,et al."Fast Stochastic Ordinal Embedding With Variance Reduction and Adaptive Step Size".IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 33.6(2021):2467-2478.