Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper proposes a new approach for automatic termination of hyperparameter optimization based on Bayesian Optimization (BO).  The idea is to construct high-probability confidence bound on the regret and then determine when to terminate the BO process. Empirical experiments are conducted on various real-world HPO and NAS benchmarks to show the efficacy of the proposed approach.
main_review: Overall, I think the main idea of the work is interesting. The writing of the paper is generally clear, except Section 3, which I think is not mathematically rigorous. This section causes me a lot of confusion and I find it's hard to understand all the maths behind the proposed approach. I have several questions listed below:
1.	I'm confused by the definition of \epsilon_{BO}. Is \epsilon_{BO} a user-defined threshold or is there any formula showing the definition of \epsilon_{BO}? I can't find the definition of \epsilon_{BO} in the paper. Also, in Proposition 1, it says that \hat{\gamma}_D is a candidate solution of min_{\gamma \in \Gamma} \hat{f}(\gamma) such that \hat{f}(\hat{gamma}_D) - \hat{f}(\gamma^*_D) \leq \epsilon_{BO}, this means the set of \hat{\gamma}_D depends on \epsilon_{BO}. If this is the case, then I expect the notation of \hat{gamma}_D should be changed to reflect the dependent (because for different values of \epsilon_BO, there will be a different set of "candidate solutions".
2.	In the first sentence right after the proof of Proposition 1, it is stated that the optimization error \epsilon_{BO} is bounded by the simple regret \hat{r}_t? Why is this the case? If \epsilon_{BO} is a user-defined threshold then it shouldn’t have any relation with the simple regret? Why is it bounded by the simple regret? I think the confusion here is also related to my confusion on the definition of \epsilon_{BO}.
3.	In the paragraph "Upper bound for \hat{r}_t" at the end of Page 3, there is a statement saying that "with high probability, \hat{f}(\gamma) is bounded by lower and upper confidence bounds defined as lcb_t(\gamma) = \mu_t(\gamma) - \beta_t \sigma_t(\gamma) and ucb_t(\gamma) = \mu_t(\gamma) + \beta_t \sigma_t(\gamma)". This statement is not always true, it is only true when the domain of the objective function is discrete. When the domain is continuous, it needs to have another term O(1/t^2) in the upper and lower bound because of the discretization process (see Lemmas 5.5, 5.6, 5.7 in Srinivas et al (2010)).
4.	In Eq. (7), I do not understand why \epsilon_{BO} is smaller than \hat{r}_t. Can the authors explain in more detail?
5.	In the sentence right below Eq. (7), it states that \hat{f}(\gamma_t^*) = min_{\gamma \in G_t} \hat{f}(\gamma). On the other hand, In Eq. (6), it states that \hat{f}(\gamma_t^*) is the best value found by iteration t. Combining these two equations, this means \gamma_t^* is the value with the lowest value of \hat{f}(\gamma)? In practice, this is only true when the empirical loss function \hat{f}(\gamma) is noiseless. However, note that to apply the regret analysis in Srinivas et al (2010) the objective function needs to be noisy.
6.	I'm also confused with Proposition 2. Is this a proposal from the paper, that is, to terminate BO when \bar{r}_t < \sqrt{Var \hat{f} (\gamma_t^*)}? Or is this a mathematical proposition (i.e. when the condition in Eq. (9) occurs, BO is automatically terminated)? I can't find a proof of Proposition 2 in the Appendix. Also, by checking the Algorithm 1 in Page 12 in the Appendix, I have a feeling that this Proposition 2 is just a proposal from the paper. Is this the case?
7.	I found it's a bit hard to read Figure 3. More detailed explanation for Figure 3 is needed in the revised version of the paper.

summary_of_the_review: Like I mentioned in the previous section, I think the overall idea of the work is interesting. But the maths behind the proposed approach is not rigorous and confused. I find a lot of confusion reading Section 3, which is the main section of the paper. I have several questions to the authors listed in the previous sections, hopefully, the answers from the authors will be able to clear my doubt.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes an automatic termination criterion for Bayesian optimization (BO) by using the upper bound of the simple reget. Various experiments are conducted to demonstrate that with the utilization of the termination criterion, computation and energy consumption can be reduced. The major contribution of this paper lies in the two propositions. Proposition 1 discusses the relationship between statistical error and optimization error, the authors claim that due to the irreducible statistical error, it is appropriate to reduce the optimization error $\epsilon_{BO}$ to the same magnitude w.r.t. the statistical error. Since the statistical error $\epsilon_{st}$ is unknown, the authors adopt an existing cross-validate method to estimate it. Then in proposition 2, the termination criterion is detailed once the BO regret is less than the standard deviation of statistical variance. 
main_review: Lack of literature review:
In general, this paper aims to solve the early/optimal stopping of the Bayesian optimization (BO). Plenty of related works are even not mentioned in the paper, e.g. Freeze-thaw BO [1],  Multi-fidelity BO [2], Hyperband BO [3], and BOS-BO [4], these works all discussed how to achieve efficiency and saving budget in BO. A detailed discussion of the difference between the proposed method and all the previous works needs to be mentioned, not to mention comparison experiments. 

The stopping criterion is mainly decided by Eq. (7), specifically, determined by the upper confidence bound and lower confidence bound. However, this bound is quite loose, since there is one variable determining the magnitude of it: $\beta_t$. Through the paper, the authors do not mention the role of $\beta_t$ and its impact on regret. In fact, if $\beta$ is set small enough, the condition in Proposition 2 can be easily satisfied right? 

Moreover, the variance estimate of $\hat{f}$ lacks theoretical analysis. I am expecting the authors to giving theoretical guarantee of the estimate to the real variance. Otherwise, it won't be possible to determine whether the estimate is to the same magnitude of the real variance. 


[1] Swersky, K., Snoek, J., and Adams, R. P. Freeze-thaw Bayesian optimization. arXiv:1406.3896, 2014.

[2] Kandasamy, K., Dasarathy, G., Oliva, J. B., Schneider, J., and Poczos, B. Gaussian process bandit optimization with multi-fidelity evaluations. In Proc. NIPS, 2016.

[3] Falkner, S., Klein, A., and Hutter, F. BOHB: Robust and efficient hyperparameter optimization at scale. In Proc. ICML, 2018.

[4] Dai, Z., et al. Bayesian optimization meets Bayesian optimal stopping. In Proc. ICML, 2019.
summary_of_the_review: Given the lack of literature review and comparison experiments, plus the bound for $\epsilon_{BO}$ lacks theoretical guarantee. This paper needs a major revision.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies the problem of pre-specifying the optimal termination criterion for Bayesian optimization. Different from prior work that tracks the value of acquisition function, this paper proposes an automatic termination criterion for BO. In particular, they construct a high-probability confidence bound on the regret, and then the users can specify a desired tolerance that shows how accurate the final solution should be compared to the global optimal. They estimate the threshold via a cross-validation estimate of the generalization error. Empirically, they design two evaluation metrics, relative test error change RYC and relative time change RTC, and compare to the comprehensive prior work. The results demonstrate the effectiveness of their proposed approach.

main_review: The problem setting of early terminating the entire BO process is interesting and novel. How to effectively pre-specify a termination criterion is a practical challenge in the field of HPO. The proposed mechanism of bounding the regret based on a user-defined tolerance makes intuitive sense. It is also reasonable to notice that overfitting can occur in HPO. Here are a few detailed comments:

- Figure 1a is not very visually informative. It is hard to understand that the orange line is the ucb and the green line is the lcb visually.
- Some typos: "prooved"-->"proved" in page 3, "letter"--> "latter" in page 4.
- It is hard to understand intuitively why the suboptimal solution resulted from the empirical surrogate can be mitigated by early stopping. It is suspicious to draw the conclusion that it can be mitigated by the proposed method. Could you explain more?

Quality: The submission is technically sound. The claims in the contribution are well-supported by theoretical analyses and empirically results. It is a complete piece of work that outperforms prior work empirically.

Clarity: This paper is well-written and easy to follow. The problem is also well-motivated. The experimental details are also very specific, such that reproducing the results should be possible. 

summary_of_the_review: This paper proposes a novel early stopping criterion for Bayesian optimization. It is well-written and well-motivated. The proposed idea is simple and technically sound. The claims are well-supported by theoretical analyses and extensive experimental results.
review_title: null

Meta-review: In this paper, the stopping condition of Bayesian Optimization (BO) is discussed. This problem is very important when BO is applied to the Hyper-parameter optimization (HPO) task. All the reviewers agree that the proposed approach based on high-probability confidence bound on the regret is interesting and reasonable.  An important issue raised by a reviewer is that many existing BO works discussed how to achieve efficiency and saving budget in BO although they did not explicitly mention the stopping condition. Due to the lack of discussion regarding the relationship with these highly related studies, we have to conclude that the paper cannot be accepted in its current form.
Decision: Reject