本文是对发表在 ICLR 2024 顶级会议上的论文 Near-Optimal Quantum Algorithm for Minimizing the Maximal Loss 的详细解读。这项研究由北京大学信息科学技术学院本科生王昊、斯坦福大学博士生张辰逸和北京大学助理教授李彤阳合作完成，系统性的分析了最大损失函数的量子优化问题，提出了混合量子优化算法并证明了其近似最优性。

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

01 背 景

　　本文考虑一个在最大损失函数上的优化问题。正式的讲，给定N个凸且L-Lipshitz的光滑函数f_1,... f_N, 我们想要考虑在F_{max} = \max_{i\in [N]} f_i上做优化，也即找到x_\star从而使得F_{max}(x_\star) - \inf_{x \in \mathbb{R}^d} F_{max}(x) < \epsilon，其中\epsilon是一个任意给定的准确度。这个问题在优化和机器学习中是非常重要的，尤其是监督学习。以支持向量机（SVM）为例，我们可以将f_i看做是当前的分类器对第i个数据点的负的间隔（margin）[1]，从而使得支持向量机的问题转化为了最大损失函数上的优化问题。作为一个快速发展的技术，量子计算有着比经典计算更快的速度。尽管量子算法在各种优化问题上已经展现了很大的加速，但是在对最大损失函数的优化问题上的应用还是较少的。本文的目标是通过系统的研究量子算法在最大损失函数的下界来解决这个问题。经典的方法在该问题上的最好复杂度为O(N\epsilon^{-2/3} + \epsilon^{-8/3})[2]，使用一阶经典 Oracle。本文设计了一个使用量子零阶 Oracle 的混合量子算法来实现关于N的根号加速，达到O(\sqrt{N}\epsilon^{-5/3} + \epsilon^{-8/3})的时间复杂度，同时证明了任意混合量子算法在该问题上至少需要\Omega(\sqrt{N}\epsilon^{-2/3})次对 Oracle 的询问。

02 准 备

　　大致地讲，我们考虑的问题是在假设具有对一个量子零阶 Oracle 的访问的前提下，混合量子算法在背景中所描述的F_{max}上的优化效果。正式的讲，我们假设存在以下的一个量子 Oracle：

　　定义1

　　从而任何一个混合量子算法可以以

　　的形式以叠加态对该量子 Oracle 进行访问。该 Oracle 是量子零阶的，因为其的返回态中只包含了关于函数值，而没有关于函数梯度的信息。

　　本文中会用到量子计算中一个熟知的结论，即量子相比于经典在无结构搜索问题上 Grover搜索算法提供的根号加速。我们简单介绍一下最简单的Grover搜索算法。给定N个无结构的元素，也即其之间无依赖，算法也事先对这N个元素没有先验知识，想要在其中考虑找到一个特定的元素\omega。该元素\omega在最简单的情况下由一个给定的量子OracleO\ket{x} \to (-1)^{\mathbf{1}[x = \omega]}\ket{x}指定。在经典情况下，我们最好的期望是进行随机采样后询问，这样做达到O(1)成功概率的时间复杂度是O(N)。而 Grover 搜索算法先构建一个叠加态\ket{phi} = \sum_{i=1}^N \frac{1}{\sqrt{N}}\ket{i}，之后进行O(\sqrt{N})次对给定量子 Oracle 的询问，使得给定元素对应的振幅每次询问都有大约O(\frac{1}{\sqrt{N}})的增长。因此，在O(\sqrt{N})的时间后，Grover 算法保证所需要搜索的元素的振幅是O(1)的，再进行采样就能保证O(1)的成功概率。本文用到的是该算法的最优性结论，即任何量子算法在无结构搜索问题上都需要至少\Omega(\sqrt{N})的复杂度来保证O(1)的成功概率。

03 算法设计

　　本文的算法使用了在经典算法[2]中提出的框架。类似地，我们考虑实现一个球正规化优化 Oracle（ball regularized optimization oracle, BROO）。正式的讲，我们可以如下定义一个 BROO。

　　定义2

　　我们定义一个映射O_{\lambda, \delta}是一个f上半径为r的球正规化优化 Oracle (r-BROO) 如果对于任意的点\bar{x}，正规化参数\lambda和准确度\delta，该映射返回\tilde{x}使得

　　那么实际上，使用经典算法[2]中的算法框架，我们便只需要考虑如何高效的实现一个 BROO。经典上，这个 BROO 是利用带有 Epoch 和投影的随机梯度下降实现[3,2]。因此，算法上我们考虑两个优化方向：

• 经典的一阶 Oracle 使用 Jordan 算法[4]可以由量子的零阶 Oracle 实现；
• 在随机梯度下降中的多次采样可以用量子实现根号加速(类似[5]) 。

04 下界证明

　　由于原文的下界证明较为繁琐，此处只介绍下界证明使用的 Hard Instance 以及证明的思路。类似经典中证明类似算法使用的 robust zero-chain[6]，我们此处考虑使用一个多函数的变体[2]：

　　定义3

　　一组函数f_1,\ldots,f_N$ of functions $f_i\colon\mathbb{B}_R(0)\to \mathbb{R}被称为一个\alpha-robust N-element zero-chain，当且仅当对任意x \in \mathbb{B}_R(0)，任意在x的临域中的y，以及所有i \in [N]，都有

　　其中prog的定义为

　　直观地讲，这里的prog代表当前的输入x目前的进度，定义为x最右一位值大于给定的阈值\alpha所在的坐标号。相对的，我们所使用的 hard instance 的直觉则是要使得每一次询问时x 的进度能增加的概率很小，期望上需要足够长的时间才能使得下一个坐标不为0（通过梯度等）。同时，只有prog(x)大于一定的值，x才能是满足最优的点。这里我们的方法是为不同的进度prog(x)指定一个对应的f_i，使得只有对这个f_i进行询问才能得到有关下一个坐标的梯度信息。如此，我们可以粗略判断，在每一个坐标上任何经典算法都期望需要\Omega(N)的时间，而混合算法由于可以用 Grover 算法加速无结构搜索，只需要Omega(\sqrt{N})的时间。Omega(\sqrt{N})也是量子算法所至少需要的在无结构搜索问题上达到O(1)误差的时间。当然，如果直接认为x是算法的输入，f_i的顺序也不变，那完全可以打表。因此我们考虑的是如上的 hard instance 做一个随机旋转U，f_i的下标也做一个随机排列的随机化 hard instance。

　　证明的细节比较繁琐，大概的思路是先使用我们上面的直觉构造一个 hybrid argument，将一个算法中调用的量子 Oracle 中有关高坐标的信息部分去除，再用常规的概率论手段证明 hybrid argument 中 Oracle 完全替换后的算法以极小的可能性能“猜”到满足准确度\epsilon的最小值的位置。具体的证明见论文。

05 结 论

　　本文在使用量子算法优化由凸且 Lipshitz 的光滑函数组成的最大损失函数F_{max} = \max_{i\in [N]} f_i 这个问题上系统性的做了研究。在假设具有零阶量子算法的基础上，设计了一个新的量子算法，在该问题的时间复杂度上从O(N\epsilon^{-2/3} + \epsilon^{-8/3})加速至了O(\sqrt{N}\epsilon^{-5/3} + \epsilon^{-8/3})，实现了根号加速。同时，通过证明任何混合量子算法在该问题上的下界为\Omega(\sqrt{N}\epsilon^{-2/3})证明了算法的近似最优性。通过设计近似最优的量子算法来解决这个问题，本文有助于推动对量子优化技术的理解以及其在实际场景中的应用。

参考文献

[1] V. N. Vapnik, "An overview of statistical learning theory," IEEE Transactions on Neural Networks, vol. 10, no. 5, pp. 988–999, 1999.

[2] Y. Carmon, A. Jambulapati, Y. Jin, and A. Sidford, "Thinking inside the ball: Near-optimal minimization of the maximal loss," in Conference on Learning Theory, pp. 866–882, PMLR, 2021.

[3] E. Hazan and S. Kale, "Beyond the Regret Minimization Barrier: Optimal Algorithms for Stochastic Strongly-Convex Optimization," Journal of Machine Learning Research, vol. 15, no. 71, pp. 2489–2512, 2014.

[4] S. P. Jordan, "Fast quantum algorithm for numerical gradient estimation," Physical Review Letters, vol. 95, no. 5, p. 050501, 2005.

[5] Y. Hamoudi, "Preparing many copies of a quantum state in the blackbox model," Physical Review A, vol. 105, no. 6, p. 062440, 2022.

[6] Y. Carmon, J. C. Duchi, O. Hinder, and A. Sidford, "Lower bounds for finding stationary points I," Mathematical Programming, vol. 184, no. 1, pp. 71–120, 2020.