本文是 NeurIPS 2022入选论文 Quantum Speedups of Optimizing Approximately Convex Functions with Applications to Logarithmic Regret Stochastic Convex Bandits 的解读。该工作首次研究了求解近似凸优化问题的量子算法，证明了该类问题关于维数的多项式量子加速。该结果可以应用于随机凸老虎机问题，可以指数降低该在线学习问题的遗憾。本文作者为李彤阳（北京大学）和张睿哲（德州大学奥斯汀分校）。

　　论文地址：https://arxiv.org/abs/2209.12897

01 问题背景

　　在优化和机器学习领域中，对凸优化问题已经有了非常深入的研究。近年来，人们逐渐开始关注非凸优化问题。去掉了凸性的要求使其能够更加贴近现实世界中的实际问题，但同时也极大地增加了问题的难度。本文研究了一类特殊的非凸优化问题——近似凸函数的最优化。对于一个函数 F:\mathbb{R}^{n} \rightarrow \mathbb{R}，如果存在一个凸函数 f: \mathbb{R}^{n} \rightarrow \mathbb{R} 使得在每个点上的近似误差 |f(x)-F(x)|≤ε/n，那么 F 就被称为近似凸函数。我们的目标是找到一个\mathbb{R}^{n}中的点 x，使得 F(x) 距离 f(x) 的最小值相差不超过 ε。对此问题的研究一方面能够增强算法的鲁棒性，即对于目标函数即使存在误差或者扰动，算法依然可以得到较好的解；同时，它也能为我们研究更一般的非凸优化问题提供帮助。对于这个问题，目前最好的经典算法是在2015年由 Belloni, Liang, Narayanan 和 Rakhlin[1]提出的。在当今量子计算蓬勃发展的背景下，一个非常自然的问题就是：近似凸函数优化问题是否存在量子加速？

　　我们首先回顾一些经典的结果。在传统优化领域中，我们主要关心的是查询复杂度（query complexity）。具体来说，我们假设函数 F 以一个黑箱（oracle）的形式提供给我们。对于\mathbb{R}^{d} 中的任意一点 x，我们可以询问黑箱 F(x) 的值，这种黑箱被称为零阶黑箱（zeroth-order oracle）。Belloni 等人的算法通过模拟退火（simulated annealing）和采用 Hit-and-run 方式的随机游走（Hit-and-run walk[2]），实现了查询复杂度大约 n^{4.5}。同时，他们的算法可以被很自然地推广到随机凸函数优化问题，即 F(x)=f(x)+\epsilon_{x}，其中 f(x)是一个凸函数，\epsilon_{x} 是一个随机变量服从次高斯分布。对于这个问题，他们的算法的查询复杂度大约为 n^{7.5} / \epsilon^{2}。细心的读者可能会发现，在对非凸函数的定义中，我们把近似误差设定为不超过ε/n。那么，有没有可能让算法容忍更大的误差呢？很遗憾，答案是否定的。Risteski 和 Li[3]证明了如果 F(x) 存在更大的误差，那么找到 ε-近似解将不存在多项式时间的经典算法。

02 主要结果

　　本文系统性地研究了近似凸函数优化问题的量子算法。首先，对于量子算法，我们的输入模型将变为量子黑箱（quantum oracle），即我们每次可以用一个量子态 |x\rangle|0\rangle 去查询，黑箱将返回 |x\rangle|F(x)\rangle 给我们。同时，这种查询可以被自然地拓展到量子叠加态上。基于零阶量子黑箱模型，我们设计了一个量子算法能使用大约 n^{3} 次查询找到 ε-近似解，相较于 Belloni 等人的算法实现了多项式级别的量子加速。

　　我们的算法同样可以拓展到随机凸函数优化问题上，可以实现大约 n^{5} /ε 的量子查询复杂度。

　　在技术上，我们主要总结推广了之前的工作中使用量子随机游走去加速经典马尔科夫链收敛时间（mixing time）的算法，并提出了一个高度封装的连续空间量子随机游走框架。我们证明了对于经典的马尔科夫链，只要它满足三个经典的条件，即可得出量子算法对收敛时间存在平方级加速。这样，即使对量子计算没有非常深入了解的研究人员也可以很容易地使用这一框架。我们希望这一框架可以对量子计算，理论计算机和机器学习的交叉领域有所帮助。

　　我们的算法在三个层面进行了量子加速：

• 在顶层，我们用量子退火去加速经典的模拟退火过程；
• 在中层，我们主要实现了在不破坏量子叠加态的前提下进行舍入（rounding）；
• 在底层，基于我们的量子随机游走框架，对 Hit-and-run 随机游走进行加速。

03 应 用

　　本文给出了一个近似（随机）凸函数优化问题的量子算法在在线学习中的应用。具体来说，是零阶随机凸老虎机问题（zeroth-order stochastic convex bandit problem）：f(x): \mathbb{R}^{n} \rightarrow \mathbb{R} 是一个未知的凸函数，在线学习者每轮可以查询一个点 x_{t} 上的值 f(x_{t})加上一个随机误差，同时会累积遗憾（regret）f\left(x_{t}\right)-f^{*}，其中 f^{*} 是 f(x) 的最小值。这个问题的目标是找到一种查询策略使得 T 轮总遗憾最小。经典算法[4]可以实现 n^{4.5} \cdot \sqrt{T} 的总遗憾，同时可以证明 n \cdot \sqrt{T} 的下界[5]。我们考虑了这个问题的量子版本，假设每轮量子在线学习者可以使用任意量子态去查询，并且在此轮结束前需要输出一个点 x_{t}，进而累积遗憾 f\left(x_{t}\right) -f^{*}。基于我们的随机凸函数优化的量子算法，我们可以实现 n^{5} \cdot \text { poly } \log T。和经典结果进行比较，量子算法对总遗憾中 T 这一重要参数有指数级改进。

04 未来方向

　　最后，我们提出几个公开问题：

• 首先，我们的量子算法的查询/时间复杂度能否被改进？目前，我们主要的加速步骤是对经典算法中随机游走的加速。是否可以对其他步骤同样进行加速？或者能否对于 Hit-and-run 随机游走的收敛速度的分析进行改进？
• 其次，在我们的老虎机算法中，关于维度 n 的依赖能否改进？对于其他老虎机或在线学习问题，是否同样存在指数级的量子优势？
• 最后，能否对更一般的非凸优化问题提出可靠的量子算法？

参考文献

[1] Alexandre Belloni, Tengyuan Liang, Hariharan Narayanan, and Alexander Rakhlin. Escaping the local minima via simulated annealing: Optimization of approximately convex functions. In Conference on Learning Theory, pages 240–265. PMLR, 2015.

[2] László Lovász and Santosh Vempala. The geometry of logconcave functions and sampling algorithms. Random Structures and Algorithms, 30(3):307–358, 2007.

[3] Andrej Risteski and Yuanzhi Li. Algorithms and matching lower bounds for approximately-convex optimization. In Advances in Neural Information Processing Systems, volume 29, 2016.

[4] Tor Lattimore and Andras Gyorgy. Improved regret for zeroth-order stochastic convex bandits. In Conference on Learning Theory, pages 2938–2964. PMLR, 2021.

[5] Varsha Dani, Thomas P. Hayes, and Sham M. Kakade. Structured logconcave sampling with a restricted gaussian oracle. In Conference on Learning Theory, pages 355–366, 2009.