Quantum algorithm for online convex optimization

doi:10.1088/2058-9565/ac5919

	Quantum algorithm for online convex optimization
	He, Jianhao 1; Yang, Feidiao 2; Zhang, Jialin 2; Li, Lvzhou 1
	2022-04-01
发表期刊	QUANTUM SCIENCE AND TECHNOLOGY
ISSN	2058-9565
卷号	7 期号:2 页码:18
摘要	We explore whether quantum advantages can be found for the zeroth-order online convex optimization (OCO) problem, which is also known as bandit convex optimization with multi-point feedback. In this setting, given access to zeroth-order oracles (that is, the loss function is accessed as a black box that returns the function value for any queried input), a player attempts to minimize a sequence of adversarially generated convex loss functions. This procedure can be described as a T round iterative game between the player and the adversary. In this paper, we present quantum algorithms for the problem and show for the first time that potential quantum advantages are possible for problems of OCO. Specifically, our contributions are as follows. (i) When the player is allowed to query zeroth-order oracles O(1) times in each round as feedback, we give a quantum algorithm that achieves O(root T) regret without additional dependence of the dimension n, which outperforms the already known optimal classical algorithm only achieving O(root nT) regret. Note that the regret of our quantum algorithm has achieved the lower bound of classical first-order methods. (ii) We show that for strongly convex loss functions, the quantum algorithm can achieve O(log T) regret with O(1) queries as well, which means that the quantum algorithm can achieve the same regret bound as the classical algorithms in the full information setting.
关键词	online convex optimization bandit convex optimization multi-point bandit feedback quantum optimization algorithms query complexity
DOI	10.1088/2058-9565/ac5919
收录类别	SCI
语种	英语
资助项目	National Natural Science Foundation of China[61772565] ; Basic and Applied Basic Research Foundation of Guangdong Province[2020B1515020050] ; Key Research and Development Project of Guangdong Province[2018B030325001]
WOS研究方向	Physics
WOS类目	Quantum Science & Technology ; Physics, Multidisciplinary
WOS记录号	WOS:000774592800001
出版者	IOP Publishing Ltd
引用统计	被引频次：2[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/18921
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Li, Lvzhou
作者单位	1.Sun Yat Sen Univ, Sch Comp Sci & Engn, Inst Quantum Comp & Comp Sci Theory, Guangzhou, Guangdong, Peoples R China 2.Chinese Acad Sci, Inst Comp Technol, Beijing, Peoples R China
推荐引用方式 GB/T 7714	He, Jianhao,Yang, Feidiao,Zhang, Jialin,et al. Quantum algorithm for online convex optimization[J]. QUANTUM SCIENCE AND TECHNOLOGY,2022,7(2):18.
APA	He, Jianhao,Yang, Feidiao,Zhang, Jialin,&Li, Lvzhou.(2022).Quantum algorithm for online convex optimization.QUANTUM SCIENCE AND TECHNOLOGY,7(2),18.
MLA	He, Jianhao,et al."Quantum algorithm for online convex optimization".QUANTUM SCIENCE AND TECHNOLOGY 7.2(2022):18.