- Rating
- 4
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper proves a new upper bound on cumulative regret for GP-based Bayesian optimization, where the noise added to the unknown function can be heavy-tailed (e.g., Student's t). Starting from Srinivas etal, such bounds come in terms of T (number of rounds) and gamma_T (maximum information gain after T rounds). Previous best results for noise with finite (1+eps) moments were O[ T^{1/(1+eps)} gamma_T ], so linear in gamma_T. The work here improves this to O [ T^{1/(1+eps)} gamma_T^{(1 + 3 eps)/(2 + 2 eps)} ], which is better for eps < 1. The result is conditioned on a particular algorithm being used to drive the choice of the next candidate in each round. While this algorithm is not realizable in practice as it is, neither are the algorithms on which earlier work was conditioned on (they all require global optimization of non-convex functions).
This is a very nice result, which not only sets a new standard, but also introduces new ideas to the ML community. While the main outcome is theoretical, the authors also provide a realizable algorithm to approximate theirs. As in earlier work, there is no strong link between the theoretical and the realizable algorithm, but clearly the authors do their best here. I'd personally be quite interested in how realistically useful the realizable algorithm is. It does not depend on heavy optimization technology (L-BFGS, multiple starts, etc.).
Critical strengths
This paper introduces substantial new technology, which seems novel at least in the ML field. This pays off, since their result is strictly better than earlier work.
While the details of the proof is far above my head, the presentation is very clear. I'd expect that with enough effort on my side, I could follow everything. Also, while the algorithm is not realizable, it seems reasonable in its steps (covering, refinement, stage-wise filtering) and does not rely on heavy concepts.
Another positive point is that few choices need to be made. There is no acquisition function, for example. The suggested realizable implementation seems quite simple, even though there is no code provided, and the complexity estimates still rely on numbers (size of C_l, J_l, n_l) that are not really specified. Experimental results are not shown.
Critical weaknesses
As far as I can judge, this seems a strong and interesting theoretical work, setting a new standard in terms of upper bound. It covers noise distributions that are more realistic than what is often assumed.
It is a bit of a shame that the authors do not go further making their algorithm practically relevant. As somebody who has worked on BO for a long while, I am not much satisfied with the current SotA implementations, which often use heavy and messy combinations of local optimization (L-BFGS) and all sorts of initialization heuristics. If insight from the theory community could lead to a better solution (where "better" means works better in practice -- more robust, simpler to implement), this would be really useful. In general, given the practical relevance of what we are talking about, I find it a bit disappointing that many theory researchers always stop where it could become interesting for practitioners. This strongly limits the impact that theory can have.
Questions for authors
I think you could have more impact by expanding the part in 4.2. Try to give the reader maximum details about this realizable algorithm. How would it be implemented? What are the most important choices and trade-offs? What algorithmic technology is needed? The current SotA in BO-HPO is rather messy, maybe also because it works in practice, so there is much prior work, also on the practical side (several major libraries, like BOTorch or Optuna). If you analyze an algorithm here that gets rid of acquisition functions, local optimization, etc., that could be quite important.
But as a practitioner, I'd want to know a lot more before I'd sit down and spend any efforts on this. I've been burned before trying to implement theoretically justified algorithms: it can end up like a major rabbit hole of high complexity techniques stacked on top of each other. If your method is not like this, then please make an effort to point this out. And if there are major hurdles for implementing and using this in practice, it would be good to be upfront about them.