- Rating
- 3
- Confidence
- 1
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
In this work, the authors study minimax lower bounds for Gaussian process bandits with the squared exponential (SE) kernel over compact domains. Previous lower bounds left a dimension-dependent (ln T)^{d/4} gap to the best known upper bounds. The authors close this gap up to dimension-independent logarithmic factors. They do so by embedding a bandlimited Sinc RKHS into the SE RKHS and building hard instances from spheroidal wave functions. The result holds on the hypercube and, by an affine argument, on any compact domain with non-empty interior.
Critical strengths
The paper resolves a well-posed open problem on the canonical hypercube domain, one that the hypersphere paper[1] explicitly left open. The paper is also well written and easy to follow.
[1] Iwazaki S. Tighter regret lower bound for Gaussian process bandits with squared exponential kernel in hypersphere. In Proceedings of the 43rd International Conference on Machine Learning, 2026
Critical weaknesses
I am not an expert in this field, and this is why I set the lowest confidence score. I could therefore not identify major weaknesses. I did notice that the authors do not cite other state-of-the-art works in the Gaussian process optimization community that rely on approximate GPs, see [1,2,3,4] and references therein.
[1] Calandriello, D., Carratino, L., Lazaric, A., Valko, M., & Rosasco, L. Gaussian process optimization with adaptive sketching: Scalable and no regret. In Conference on learning theory. PMLR.
[2] Rando, M., Carratino, L., Villa, S., & Rosasco, L. Ada-bkb: Scalable gaussian process optimization on continuous domains by adaptive discretization. In International Conference on Artificial Intelligence and Statistics.
[3] Shekhar, S. and Javidi, T. (2018). Gaussian process bandits with adaptive discretization. Electronic Journal of Statistics.
[4] Shekhar, S. and Javidi, T. (2020). Multi-scale zero-order optimization of smooth functions in an rkhs.
Questions for authors
-
Can these results be extended to approximate GPs such as [1]?
-
How would the approximation (in particular Nystrom) affect the regret?
[1] Calandriello, D., Carratino, L., Lazaric, A., Valko, M., & Rosasco, L. Gaussian process optimization with adaptive sketching: Scalable and no regret. In Conference on learning theory. PMLR.
3 comments
I thank the authors for their response! It addressed the questions I raised and I have no further concerns. Although I am not an expert in this subfield (as I indicated in my review), I think the manuscript is well done (to the best of my knowledge) and thus I maintain my positive score.
We sincerely thank you for your encouraging feedback and thoughtful review. We are glad that our response has addressed your questions.
Response For Related work:
Thank you for pointing us to these relevant references. We apologize for posting our response close to the end of the discussion period, and we appreciate your time in considering it.
Calandriello et al. [1] introduce BKB, which uses adaptive kernel sketching to reduce the computational cost of GP bandit optimization while retaining a no-regret guarantee. Rando et al. [2] propose Ada-BKB, which combines approximate GP inference with adaptive discretization of continuous domains. Shekhar and Javidi [3] develop a tree-based adaptive discretization algorithm under a GP prior and establish high-probability bounds on both simple and cumulative regret. In a related RKHS setting, Shekhar and Javidi [4] propose LP-GP-UCB, combining a GP surrogate with local polynomial estimators on a multi-scale partition, and derive regret bounds that exploit function smoothness.
Our original discussion of upper bounds focused primarily on statistical regret rates and their relation to our lower bound; it did not adequately cover the complementary literature on computational upper-bound algorithms. We will add these references and clarify their relationship to our focus on algorithm-independent statistical lower bounds.
Response To Questions:
Questions 1: Our lower bound is algorithm-independent and applies to the original SE-kernel function class. In particular, it applies to algorithms using Nystr"om or other approximate GP computations: for any such algorithm, there exists a function in the class on which the lower bound holds.
Question 2: Regarding the effect of approximation methods on regret, approximation quality matters. An insufficient set of inducing points can introduce approximation error or underestimate uncertainty, potentially impairing exploration. On the positive side, Calandriello et al. [1] develop BBKB, which uses a Nystr"om embedding with an adaptively updated inducing-point dictionary and combines it with adaptive batching. Under their assumptions, BBKB retains a regret guarantee comparable to that of exact GP-UCB while reducing computational cost. In the setting of adversarial Gaussian Process bandit, Iwazaki [2] develops a computationally efficient kernelized Exp3 variant using recursive ridge-leverage-score Nystr"om approximation, and establishes a regret upper bound of the same order as that of the original algorithm. These results illustrate that computational savings need not worsen the order of the available regret guarantee when approximation accuracy is appropriately controlled.
Reference
[1] Daniele Calandriello, Luigi Carratino, Alessandro Lazaric, Michal Valko, and Lorenzo Rosasco. Near-linear Time Gaussian Process Optimization with Adaptive Batching and Resparsification. In Proceedings of the 37th International Conference on Machine Learning (ICML), PMLR 119, pp. 1295–1305, 2020.
[2] Shogo Iwazaki. Nearly Optimal Algorithms for Adversarial Kernelized Bandits. arXiv preprint arXiv:2605.10299, 2026.