Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper analyzes Thompson Sampling for sequential optimization where the GP is replaced by a scalable approximation. In particular, leveraging prior works on Sparse Variational GPs and ways of sampling from and updating Sparse Variational GPs, the authors show that the resulting sparse-GP-TS algorithm (which makes use of these approximations) has $\tilde O(\sqrt(T))$ regret. In particular, the authors first prove a general regret bound for Thompson Sampling with approximate GPs that satisfy certain error bounds on the means and covariances. They then show that SVGPs satisfy these bounds. The authors then use their algorithm and show performance on synthetic and real problems when compared to existing BO methods.
main_review: This paper uses Sparse Variational GPs in Thompson Sampling to allow GP-TS to scale to larger dimensional problems. The proposed algorithm makes extensive use of recent work on Sparse Variational GPs and sampling from Sparse Variational GPs. The analysis makes use of recent work on characterizing the approximation power of SVGPs which---importantly-- the authors show to result in a computationally tractable algorithm.

This paper is well written with relatively few and addresses an important limitation of GP-TS, namely its scalablility and computational tractability. Furthermore, it provides frequentist regret bounds for TS with a class of approximations to GPs (which is shown to include SVGPs), and extensive numerical simulations showing the impressive performance of their algorithm against benchmarks. While this paper really draws on results from prior works on SVGPs, it extends upon them and applies the findings to the important problem of Thompson sampling, so I think the contribution of this paper is good enough for acceptance.

My main question is on the cost of choosing inducing points. Choosing inducing points is said to be efficient, but shouldn't this computational cost be included in the computational cost of the TS algorithm for a proper apples-to-apples comparison?

limitations_and_societal_impact: The authors do discuss the limitations of their work, and do a good job of comparing to prior works on GP-TS. I'm curious about how the computation of the inducing points factors into the computational complexity of the algorithm, since solving e.g., K-means at every step may be computationally expensive.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies the use of Sparse Gaussian Process regression in combination with Thompson sampling (S-GP-TS) for sequential (batch) decision processes.

Via theoretical analysis, the authors show that batch S-GP-TS can achieve the same regret order as an exact GP-TS algorithm, as long as the GP approximation technique chosen meets certain criteria.

They argue that approximate S-GP-TS provides computational benefits, with no regret performance loss over exact GP-TS.

The proposed S-GP-TS is shown to provide good regret results in both synthetic and a real-world Bayesian optimization tasks.
main_review: The main contribution of this work is to show that approximate S-GP-TS provides computational benefits, with no regret performance loss, when compared to exact GP-TS.

Even though the originality is limited (S-GP-TS has been already proposed in [24] and the proof technique leverages work in [26]), the significance of this work lies on providing a theoretical regret bound for the general GP approximation case (Theorem 1), as well as a more specific bound (Theorem 2) for the approximation choices of S-GP-TS (as presented in Section 4).

The paper is clearly written, with a concise introduction and problem formulation, a very clear description of GPs with their corresponding approximations in Section 3 and the S-GP-TS approach in Section 4.

Section 5 is where the main contributions lies (Theorems 1 and 2), with experiments provided in Section 6.

The theoretical work in Section 5 leverages already presented rates of convergence for sparse variational Gaussian process regression in [26], but accounts for
1. the errors introduced by S-GP-TS decoupled sampling rules, and
2. the sequential selection of the observation points $x_{t,b}$ of S-GP-TS.

The provided bounds depend on:
1. the approximation error of Assumptions 3 and 4,
2. the discretization grid of Assumption 5.

These errors are made specific for S-GP-TS, based on the spectrum properties of selected GP kernels and the number of prior features and inducing variables required. The authors argue that their bound shows no order regret of S-GP-TS when compared to the exact case if such assumptions hold.

To counteract the approximation error of Assumptions 3 and 4, the number of features $m_t$ and $M_T$ have an exponential dependency over dimensionality (as presented in Table 1):
- Exponentially many points are needed to provide an approximation to the exact GP with no regret.
- The authors argue that the discretization size being exponential in the dimension $d$ is inherent when optimizing over high dimensional spaces, and not specific to the approximation.

Importantly, the authors show that the approximation techniques (with enough inducing points/features) allow for a computational cost reduction (which is significant in many practical Bayesian optimization techniques).
- As a limitation, they acknowledge that studying the selection mechanism of inducing points/features is an open avenue of work.

Some clarifications on the applicability of their results would help the unfamiliar reader:
- $\tau$ first appears in Equation (2), as the Gaussian observation noise variance or precision.
- However, it also appears in the constants of Theorem 1 and Proposition 1.
- Therefore, are these results only applicable to Gaussian noise observation models? I.e., for exact Gaussian regression models?
    * [Updated] I encourage the authors to incorporate the informative discussion along these lines from their rebuttal to the main manuscript

Finally, they provide empirical results for optimization problems with large batch sizes in Section 6.
- The significance of this section is a bit unclear as they focus on evaluating regret for large batch sizes, but don't provide computational complexity comparisons with exact TS-GP.
- For their synthetic benchmarks, they state that S-GP-TS has access to 5000 observations (t=50 times B=100) while the baselines are run only for t=750 steps. Why are the authors comparing algorithms with different number of observations? If the alternatives can not deal with these many observations, computational results (i.e., run-time) for the same number of observations could be shown to better illustrate the claimed benefits (same reward, less computational burden).
    * [Updated] The explanations provided in the author responses helps understand the subtleties of the experimental section better, which if incorporated into the main manuscript, would clarify the significance of the presented results.
limitations_and_societal_impact: The authors discuss the general limitations (e.g., dimensionality dependence) of the presented work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper provides a regret bound for Thompson sampling of SVGP posterior. Explicitly, this paper first derives a generic regret bound for any arbitrary approximate posterior of a certain uniform closeness (i.e., approximation quality) to the full posterior. This bound is then applied to two different sampling schemes (for two respective variants of SVGP). 

main_review: 
I find the paper very well written and clearly organized. There might be a small typo in Lemma 1, where the wrong symbol of B is used (either that or the typo is in the proof of Lemma 1).

I think the theoretical analysis is interesting and quite different from the theory of GP-TS. It has also provided good insights to the high level challenges of extending the regret bound of GP-TS to S-GP-TS. As such, the resulting theory is a nice complement to S-GP-TS. On the other hand, while I appreciate the extensive empirical study on many real-world/synthetic benchmarks, it feels somewhat loosely connected to the theory:

1. The entire point of S-GP-TS is to scale up GP-TS, but there is no runtime plot to showcase the difference. I don't think performance vs #query and performance vs #iterations are sufficient to demonstrate this point.
2. There seems to be no experiment to backup the analysis of SVGP with inducing features.
3. Molecular search experiment uses an entirely different kernel which has little relevance to the theory developed.
4. No ablation study to verify other aspects of the theory (e.g., approximation quality in Proposition 1, validity of various assumptions).

Also, regarding proof of Theorem 1: It is claimed that the approximation error in the standard dev might result in an under exploration which the original GP-TS analysis cannot address. Does this mean the same proof technique will not go through, or will it get a significantly worse regret bound because of this term, and if so, how much worse?
limitations_and_societal_impact: The authors have not discussed the broader impact of this work, but I believe there is no potential negative impact to society.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This work considers Bayesian optimization associated with a Thompson sampling scheme, where the posterior over the function is represented as a Gaussian Process (GPs). Due to the poor scaling of GPs, a pseudo-input approximation of the GP is proposed and incorporated into the bandit optimization procedure. Regret bounds are provided for the proposed scheme which establish accuracy/complexity tradeoffs. Experiments demonstrate the merits fo the proposed approach.
main_review: 
The paper is well-written, puts forth a novel algorithm, and contributes interesting convergence theory to substantiate the proposed technique. This is a worthy contribution to the intersection of sparse Gaussian Processes and bandit optimization. 

In discussing the use of sparse Gaussian Processes in Bayesian settings, it should be noted that methods other than Thompson sampling have been previously studied, which are very similar to this work, based upon, e.g., Upper-confidence bound or expected improvement:

Calandriello, D., Carratino, L., Lazaric, A., Valko, M., & Rosasco, L. (2020, November). Near-linear time Gaussian process optimization with adaptive batching and resparsification. In International Conference on Machine Learning (pp. 1295-1305). PMLR.

Bedi, A. S., Peddireddy, D., Aggarwal, V., & Koppel, A. (2020). Sublinear Regret and Belief Complexity in Gaussian Process Bandits via Information Thresholding. arXiv preprint arXiv:2003.10550.

Where explicit tradeoffs between regret and the complexity of the GP are provided. I'd like to see a quantitative contrast of Theorem 1 with the results presented in the above works, especially because the later reference incorporates the selection of inducing inputs directly via the notion of information-theoretic regret, whereas in the work under review, the inducing input selection must be done from a determinant point process that is untethered from the underlying optimization problem. Put another way, is there any relationship between the selected pseudo-inputs in this work and the optimal information gain defined over the collection of $m_t$ points?

The analysis offers a novel incorporation of the approximation error incurred by inducing inputs into Thompson sampling techniques for Gaussian Processes. While this is a nice confluence of ideas, I am a little unclear on what is completely conceptually innovative here in terms of the algorithm design/convergence analysis.

Experimentally, it is also conspicuous that there is no comparison to reference [30]. How does Thompson sampling alleviate limitations of existing works based on other acquisition functions? The experiments do not demonstrate the proposed approach yields a state of the art tradeoff in regret/posterior complexity. 

limitations_and_societal_impact: The submission is sufficient along this axis.
review_title: null

Meta-review: This was a somewhat borderline paper. The reviewers found the theory to be slightly derivative from earlier work, but that it was nontrivial and ultimately had merit. The reviewers also find the empirical results to still be somewhat limited. The reviewers certainly did appreciate the dialogue with the authors during the review process. Authors are strongly encouraged to read the reviews and responses, and ensure that all feedback is taken into account when preparing the camera ready submission.
Decision: Accept (Poster)