论文标题
用于在线凸优化的量子算法
Quantum Algorithm for Online Convex Optimization
论文作者
论文摘要
我们探索是否可以找到零订单在线凸优化问题的量子优势，该问题也称为具有多点反馈的Bandit凸出优化。在此设置中，给定访问零好的牙齿的访问（即，作为返回任何查询输入的函数值的黑匣子访问的损耗函数），玩家试图最大程度地减少一系列对抗生成的凸损失函数。该过程可以描述为玩家和对手之间的$ T $圆形迭代游戏。在本文中，我们提出了该问题的量子算法，并首次显示在线凸优化问题的潜在量子优势是可能的。具体来说，我们的贡献如下。 （i）当玩家被允许查询零件的oracles $ o o（1）$ o（1）$ a以反馈作为反馈时，我们给出了一种量子算法，可以实现$ o（\ sqrt {t}）$遗憾，而没有额外的尺寸$ n $的额外依赖性$ n $，这超过了已知的最佳经典algorith $ o（$ o o o o o（s）请注意，我们的量子算法的遗憾达到了经典一阶方法的下限。 （ii）我们表明，对于强烈凸出的损失功能，量子算法也可以通过$ o（1）$ queries实现$ o（\ log t）$遗憾，这意味着量子算法可以在完整信息设置中实现与经典算法相同的遗憾。
We explore whether quantum advantages can be found for the zeroth-order online convex optimization 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 online convex optimization. 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(\sqrt{T})$ regret without additional dependence of the dimension $n$, which outperforms the already known optimal classical algorithm only achieving $O(\sqrt{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.
