Quantum Bayesian Optimization

Summary

The paper studies quantum kernelized bandits or Bayesian optimization (BO). Classically, in every iteration t=1,2,\ldots,T, a BO algorithm chooses an arm x_t and then queries the reward function f for a noisy observation y_t=f(x_t)+\zeta_t, where f can be non-linear and \zeta_t is a sub-Gaussian noise. The goal is to minimize the cumulative regret R_T=\sum_{t=1}^{T}[f(x^*)-f(x_t)]. In the quantum setting, every query to the reward function f at the arm x_t is replaced by a chance to access a quantum oracle or its inverse, which encodes the reward distribution for the arm x_t. Besides, a bounded noise or a noise with bounded variance are considered. The paper introduces the Q-GP-UCB algorithm which is the first BO algorithm able to achieve a regret bound of O(poly log T), which is significantly smaller than the classical lower bound of \Omega(\sqrt{T}).

Strengths

1. The paper provides the first quantum BO algorithm, which achieves a polylog(T) regret, beats the classical lower bound of \Omega(\sqrt{T}), and offers more evidence of quantum advantages over classical computers. 2. The result generalizes the previous quantum speedup for multi-armed bandits (MAB) and stochastic linear bandits (SLB) [32]. Besides, the paper improves the regret bound of SLB in [32] by improving the analysis of the confidence ellipsoid. 2. The paper is overall structured very well. The ingredients of the analysis for the Q-GP-UCB algorithm are listed in a readable way so I can quickly get the ideas behind it. I enjoy reading this paper very much.

Weaknesses

1. I'm a bit doubtful about the technical contributions of this paper. Apparently, the basic framework of Q-GP-UCB follows from the weighted least squared estimator and the doubling trick in [32]. The key difference from [32] is the design of the weighted GP posterior distribution (see Eq. (3)), which looks very similar to the classical one (see Eq. (1)). Such a combination, of course, can be regarded as the main technical novelty, but the question is, I have no idea whether it raises inherent difficulties in the analysis.

Questions

1. Please explain more about the technical difficulties in analyzing the Q-GP-UCB algorithm. 2. I notice that the authors of [32] showed their Q-LinUCB algorithm has a regret of O(log^{5/2} T) for bounded noise, but this paper said the regret is O(log^{3/2} T) (see line 350) when citing [32]. Is this because the analysis of [32] is not tight? Please confirm it since one of the contributions of this paper is an improvement over Q-LinUCB. If you indeed improve the regret from O(log^{5/2} T) to O(log^{3/2} T), this would increase the contributions of the paper.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

Yes.

Summary

The paper studies the regret attainable for multi-armed bandits with non-linear reward functions when having access to a quantum oracle. For this setting they introduce the Quantum Gaussian Process Upper Confidence Bound (Q-GP-UCB) that with probability at least $\delta$ achieves regret: - $\mathcal{O}((d\log{T})^{3/2}\log{d\log{T}})$ using the linear kernel, - $\mathcal{O}((\log{T})^{3/2\cdot(d+1)}\cdot (d+1) \cdot \log{\log{T}})$ using the squared exponential (SE) kernel, when the noise is bounded and $d$ is the dimensionality of the input space. Similar rates are derived for noise with bounded variance. This notable improvement over the classical fundamental limit is mostly attributed to the use of the Quantum Monte Carlo (QMC), and the improvement over the work of Wan et. al. 2022 (when instantiated with the linear kernel) is due to the paper's novel and tighter analysis of the confidence ellipsoid. They actually modify the proof of this prior work to attain the same rate as well. Finally, they run experiments using the Qiskit package that demonstrate their algorithm's superiority over the classical variant, as well as the benefits of using the SE kernel in the more practical setting of AutoML.

Strengths

- Intuitive and well explained use of staging to manage the growing number of samples fed to the QMC subroutine. - Their weighing technique is very intuitive and by making the noise 1-sub-Gaussian allow them to use a self-normalized concentration inequality that improves the confidence ellipsoid and allows for better rates (also has nice intuitive meaning as enabling a measuring of weighted information gain). - I particularly like that they use plug their improved analysis into the work of Wan et. al. to make their original algorithm match the rate the authors attain with the linear kernel. This is a nice way to both showcase the strengthened analysis, as well as to clarify to the community which things are key algorithmic behavior versus analysis artifacts.

Weaknesses

- No core majorly novel algorithmic design / concept definition, i.e. results are due to elegant combinations of techniques and careful analyses rather than groundbreaking new concepts/approaches introduced. - Minor typo: "encode" -> "encodes" (line 144).

Questions

- Could you expand more on the empirical behavior of Q-GP-UCB in the initial stage? It is a bit hard to see given the large setting of total time-steps. For example, could you comment on when this may be an issue and when not? - Do you have intuition for what would happen with other kernels being used?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

- As per above, maybe more limitations regarding trade-offs of initial phase (and others) could be discussed in experimental section?

Summary

This paper considers kernelized bandits also known as Bayesian optimization under a particular feedback model inspired by quantum computing. Under this model repeating sampling from the same point for N times reduces the noise to the level on $1/N$. That is significantly tighter than the classic setting where sampling the same point for N times reduces the noise to the level on $1/\sqrt{N}$. The paper introduces a UCB based algorithm, that is very similar to mini-META proposed in [6]. The proposed algorithm is referred to as Q-GP-UCB, and, in the case of SE kernel, obtains a polylogarithmic regret bound in the time horizon $T$ that is a significant improvement compared to $\sqrt{T}$ regret bound in the classic setting.

Strengths

The problem is inspired by quantum computing and may be of broader interest. Overall this is an interesting formulation of kernel bandits.

Weaknesses

The formulation and analytical techniques are similar to those of [32] in the case of linear bandits. That to some extent limits the novelty and contributions. In terms of complexity, the regret bounds seem to scale as $\tilde{\gamma}_m^{1.5}$, where the number of unique points is bounded by $\tilde{\gamma}_m$ and an additional $\tilde{\gamma}_m^{0.5}$ is contributed by the regret on each unique point, due to confidence ellipsoid. Theorem 1 bounds this quantity by \gamma_{T^2}. For example, in the case of Matern kernels, that leads to a regret bound of $T^{(3d)/(4\nu+2d)}$ where $\nu$ is the smoothness of the kernel. This regret bound may be worse than the classic results of $T^{(\nu+d)/(2\nu+d)}$ when $d$ is large. I think this is an indication that the regret bounds presented in this work are sub-optimal and can be further improved. Given that there is no lower bound under this setting, that raises some doubts about the tightness of the analysis. The results should be seen as some initial attempt on the problem.

Questions

- Considering the example above about Matern kenrel, could the authors comment on the tightness of the bounds? The results seem to be an improvement only in the case of SE kernel. Why they do not necessarily improve the regret bounds in the case of other kernels. - If the standard mean and variance are used rather than the weighted ones, which step in the proof would fail? The number of unique points or the regret on each unique point?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

Although the formulation seems interesting, the results do not seem tight. To some extent they follow the case of linear bandits. When it comes to more general kernels the regret bounds seem to even fail to be sublinear in some cases.

Summary

This paper studies Bayesian optimization with quantum reward oracles where the reward function $f$ lies in an RKHS space with the squared exponential kernel, and at every iteration after input is selected, we can access a quantum unitary oracle and its inverse that encode the noisy reward distribution. In such a setting, the authors introduce the quantum-Gaussian process-upper confidence bound (Q-GP-UCB) which achieves a regret upper bound of $\mathcal O(\text{poly log} T)$. To do it, they introduce a weighted GP regression and then analyze the growth rate of the weighted information gain. Next, they derive a tight confidence ellipsoid which gives a guarantee of the concentration of the reward function and the weighted GP posterior mean. They also show that their bound on the confidence ellipsoid improves that of the quantum linear UCB (Q-LinUCB) algorithm [32] over a factor $\sqrt{d}$, where $d$ is the input dimension. Finally, they show the performance of their proposed algorithm over the classical GP-UCB and Q-LinUCB, through a synthetic experiment and an experiment on automated machine learning

Strengths

- The paper is well-organized and easy to read. The arguments, and comparisons with related works are clear and well-supported. - The paper is the first to introduce the first quantum Bayesian optimization algorithm which enjoys a regret upper bound of $\mathcal O(\text{poly log} T)$.

Weaknesses

However, I am concerned about the novelty of the used techniques in this paper. They seem to be an unsophisticated combination of common techniques from classical Bayesian optimization (e.g., see [9], [28], [30]), the classical bandits [9], and quantum bandits [32]. It follows that the regret upper bound of $\mathcal O(\text{poly log} T)$ for their proposed BO algorithm has the same order as that of [32] which is designed for linear bandits. The authors claim that the recent quantum works on multi-armed or linear bandits are not able to solve sophisticated real-world problems with non-linear reward functions like their setting. However, from the technical point of view, Bayesian optimization under the setting that the reward function $f$ lies in an RKHS space is in fact a kind of linear bandit problem except that the input space is continuous. Hence, I think that this paper is OK but not good enough from a technical point of view.

Questions

- The authors seem not to consider the case of the Materm kernel. Is there any improvement in the regret bound with the aid of quantum computing in this case? - It would be interesting if the authors can provide a discussion on the lower bound of the regret bound of BO in the setting of quantum computing.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

Yes

Suboptimality of the achieved regret bounds

Thanks for your response. In the case of Matern kernel, the regret bounds proven in this paper are in order of $\mathcal{O} (T^{3d/(2\nu+d)})$. This is worse than the optimal regret bound $\mathcal{O} (T^{(\nu+d)/(2\nu+d)})$ for standard kernel bandits when $\nu<2d$. Even when compared with the suboptimal $\mathcal{O} (T^{(\nu+3d/2)/(2\nu+d)})$ regret bound of GP-UCB, the regret bounds proven in this paper are worse when $\nu<1.5 d$. This is despite the observation that the noise concentrates faster, at a 1/N rate, in the quantum setting, in contrast to the $1/\sqrt{N}$ rate in the classic setting. It thus seems clear that the regret bounds proven in this paper are suboptimal in general. In addition, the reason for this suboptimality is not clear (where the difficulty comes from, what are the best regret bounds we hope for). I suggest the authors make this point clear in the paper to encourage future work on the topic.

Thank You for Your Response

Thank you for your response. We are glad to learn that your doubts are well resolved. We'll also add what we included in our response to the paper after revision to further improve our paper. Thanks again.

Thanks for your response

Thanks to the authors to address my concerns, especially the regret bound for the Matern kernel. I have no further questions.