Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposes a new UCB strategy for Bayesian optimization that focuses on mean-variance optimization instead of expected value. The authors argue that this setting is relevant for heteroscedastic settings where one seeks high mean values with lower risk. Regret bounds are given to provide theoretical results about the convergence of the proposed algorithm for this setting. Empirical results on two synthetic problems and two "real-world" problems show that the proposed approach returns solutions with a higher mean and lower risk than standard risk-neutral GP-UCB.
main_review: **Strengths**

A risk-averse strategy for Bayesian optimization is surely relevant in many applications. Noisy observations are ubiquitous in science and engineer problems. In fact, it is somehow surprising that previous work hasn't addressed this setting before. The "Tuning a Free Electron Laser" example was the most interesting experiment. I found this work fairly complete and relatively easy to understand, despite the heavy notation for the theorems.

**Weakness**

No major issues. I would only suggest that the empirical section could be more substantial if all the results were motivated by real applications or if the synthetic experiments were conducted over multiple test functions (and not only two). It would be interesting to see aggregate results across a more extensive set of problems.

**Minors**

- lines 41 (suggestion). Exploration vs. Exploitation for optimizing the expected performance; instead of an 'and optimizing.'
- Maybe I've missed that, but I was expecting RAHBO-US to execute x% observations of US and (1-x)% of RAHBO. What values of x were considered?

**After author's response**

Thanks for all the detail answers! 
limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper proposes a Bayesian optimization method for robust optimization of black-box functions under heteroskedastic observation noise. The method uses an objective that trades off mean and noise variance to identify solutions with high mean and low noise variance. The authors propose modeling the black-box function and the black-box noise variance function using independent GPs and using a UCB-style acquisition function. The authors prove a sublinear cumulative regret bound for the method.
main_review: Strengths:
-	Theoretical grounding: the sublinear cumulative regret bound is nice
-	Under-explored and interesting problem class of robustness with respect to stochastic evaluations
  -	Many works on robust optimization consider robustness with respect to input noise rather than output noise
-	The FEL experiment is a nice demonstration 

Weaknesses:
-	Typically, expected performance under observation noise is used for evaluation because the decision-maker is interested in the true objective function and the noise is assumed to be noise (misleading, not representative). In the formulation in this paper, the decision maker does care about the noise; rather the objective function of interest is the stochastic noisy function. It would be good to make this distinction clearer upfront.
-	The RF experiment is not super compelling. It is not nearly as interesting as the FEL problem, and the risk aversion does not make a significant difference in average performance. Overall the empirical evaluation is fairly limited.
-	It is unclear why the mean-variance model is the best metric to use for evaluating performance
  -	Why not also evaluate performance in terms of the VaR or CVaR?
  -	The MV objective is nice for the proposed UCB-style algorithm and theoretical work, but for evaluation VaR and CVaR also are important considerations

Writing:
-	Very high quality and easy to follow writing
-	Grammar:
  -	L164: “that that”
  -	Figure 5 caption: “Simple regret fat the reprted”

Questions:
-	Figure 2: “RAHBO not only leads to strong results in terms of MV, but also in terms of mean objective”? Why is it better than GP-UCB on this metric? Is this an artifact of the specific toy problem?

limitations_and_societal_impact: Limitations are discussed and potential future directions are interesting. “We are not aware of any societal impacts of our work” – this (as with an optimization algorithm) could be used for nefarious endeavors and could be discussed.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper proposes a risk-averse Bayesian optimization algorithm, which aims to find an input with both large expected return and small noise-dependent noise variance. Both the mean function and input-dependent noise variance are assumed to be unknown functions from a reproducing kernel Hilbert space, and hence both need to be estimated online. Both theoretical guarantees and empirical evaluations are given.
main_review: This paper aims to tackle an important problem, i.e., designing BO algorithms that are risk-averse in terms of the risk introduced by input-dependent noise. The approaches taken by the paper, both theoretical and empirical, are all natural and reasonable. However, I have some concerns/questions regarding the theoretical and empirical results of this paper, please see the details below.

Weaknesses/questions:
- It looks like the Gaussian process posterior mean and variance for heteroscedastic GP adopted in this paper (equations 5 and 6) have a few differences between their homogenous counterpart (e.g., refer to equations 2 and 3 in reference [12]), even when a homogeneous noise variance is used, equations 5 and 6 in the current paper don't reduce to equations 3 and 3 in [12]. For example, the noise variance doesn't appear in the homogeneous case given in [12], but appears in the heteroscedastic case in equations 5 and 6 in the current paper. Is there an intuitive explanation for this difference?
- Proposition 1: I have a few questions regarding these theoretical results. Firstly, $\beta_T$ defined in equation 8 seems to be data-dependent, i.e., it depends on the history of selected input locations. So, I think a concrete expression regarding the growth rate of $\beta_T$ should be given, in order to support the claim that the proposed algorithms are no-regret (as claimed in line 67). Next, is there an intuitive interpretation regarding the dependence on $\lambda$? What is the recommended value of $\lambda$? In the homogeneous case like [12], $\lambda$ is set to a value dependent on $T$, but here it seems like a free parameter. In fact, the same questions apply to Theorem 2 as well.
- Lines 164-165: it says here that "the same upper bounds are still applicable in the considered heteroscedastic case (i.e., by setting $\sigma^2$ to $\varrho^2$)". If I understood correctly, if we set $\sigma^2$ to $\varrho^2$, the corresponding information gain (see the formula on line 160) will be smaller than the information gain with heteroscedastic noise variance, since the information gain is inversely related to the noise variance. That means the max information gain derived using $\varrho^2$ is smaller than by the $\gamma_T$ from Proposition 1, so that doesn't really give us a concrete regret upper bound in terms of homoscedastic noise variance. Does this contradict what is said here in these few lines, or is my understanding inaccurate?
- Equation 15: what's the intuition behind the use of $\text{ucb}^{var}_t(x_1)$ here? BTW I think the second $x_1$ should be $x_t$.
- Theorem 2: in addition to the questions I have regarding the dependence on $\beta_T$ and $\lambda$ as mentioned above, the dependence on $k$ here seems a little counter-intuitive: why is the regret bound increasing in $k$? Does that suggest we should set $k$ to the smaller value of 1?
- Corollary 2.1: does this result hold "with high probability"?
- Experiments: does the horizontal axis in Figure 2 (and other figures) consider the value of $k$? That is, if $k=10$ experiments are repeated for every evaluated input, does that correspond to 1 iteration or 10 iterations in the figure? If it corresponds to 1 iteration, the comparison may not be fair for GP-UCB. Moreover, I think an ablation w.r.t. the value of $k$ is needed, because I think it will have a huge impact on the estimated variance. For example, if $k$ is larger, I suppose RAHBO-US will perform better. 
- lines 221-224: are the initial steps for variance estimation included in the comparisons shown in the figures?
- lines 250-251: why does standard GP-UCB prefer noisier inputs? Shouldn't it be indifferent between different inputs with the same expected function value?
- Figure 5: it seems that the advantage of the proposed method isn't so clear in these figures, especially in the hyperparameter tuning tasks of Figures b and c.
- Lines 268-269: are you trying to refer to Figure 4 instead of Figure 10 here? Because if it's Figure 10, the word "drastically" (line 271) will be an overstatement.

Some more minor points:
- Figure 2 caption, third and fourth lines: I think (c) and (d) are reversed.
- I think Figure 3 is never referred to in the text.
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper presents an approach for risk-averse Bayesian Optimization in the case that the function to be optimized is subject to heteroskedastic observation noise. For a mean-variance model, the authors propose an acquisition function and provide bound on the cumulative regret for the case when the variance proxy is known. They then extend this to model the unknown variance proxy (assuming strict sub-gaussianity) and provide regret bounds also for this case. The algorithm is empirically evaluated on a set of synthetic and real problems, where it is shown to improve upon non-robust BO approaches in terms of the regret defined.
main_review: ### High-level summary:
- The problem setting is relevant of interest for the community.
- The discussion of related work is overall good.
- The contributions are novel and appear technically sound.
- The paper is generally well written and easy to follow.
- The empirical evaluation is solid, but could benefit from additional baselines.
- Overall a good paper; with room for improvement, but a pretty clear accept in my mind.


### Notes:
- Why are all of the named applications "high-stakes" applications? This is understandable for drug discovery and robotics, but not really for the other examples, please substantiate.
  - More generally, the paper could do a better job at explaining the practical implications of this work by giving concrete examples.
- It is quite a bit into the paper before the authors discuss that the setting of heteroskedastic noise and the setting of risk-averse BO are not new but have been studied before. They should do  this in the introduction to avoid any potential misconceptions and clearly identify the novelty of their work over existing literature.
- The discussion of related work is relatively comprehensive. However, the setting of this paper is quite close to that of [1] (which focuses purely on modeling). The authors should add that reference and discuss how their work relates to that of [1].
- I am not fully convinced that the mean-variance-model is a practical choice; it seems much harder for me to properly choose the coefficient of absolute risk tolerance than, say, to optimizat VaR or CVaR. From my experience working with practitioners, the assumption that alpha is fixed and known will generally not hold in practice. It would be good to address this rather than stating it as an assumption without any discussion.
- The formulation of the acquisition function (eq 9) is pretty intuitive and the straightforward choice. An alternative would be to not consider the posterior variance sigma(x)  of the latent function, but consider the the overall posterior predictive sqrt(sigma(x)^2 + rho(x)^2). It would be worth discussing such option and compare the choice made here to other approaches.
- The paper could benefit from additional discussion of the algorithm. For instance, in eq. 9 it may appear that there is a tension between beta and alpha, and it took me a bit to think through the difference implication of the posterior uncertainty of the latent function and the variance of the observation. It would be helpful to provide this kind of intuition for what is going on to the reader.
- The repeated experiment setting is a natural thing to do but appears limiting, and it seems like it could really hurt sample efficiency. With a smoothness assumption on the behavior of the variance proxy, it should be possible to devise a more sample efficient algorithm than simply re-evaluating each candidate k times. This is discussed also in [1] and the authors should discuss how their approach compares to that of [1].
- The theoretical results appear sound, though I did not check them in any detail. It's nice to show some regret bounds, and this appears to require a good amount of technical finesse. However, I feel like value of these theoretical contributions for practical purposes is somewhat limited. For instance, the results rely on finding the maximizer of the acquisition function exactly, but in actual implementations this requires solving very hard non-convex optimization problems repeatedly, where and one generally cannot guarantee finding the globally optimal solution for all but the smallest problems.
  - The theoretical results do get quite technical, it would be useful for the non-expert to have some high-level summary for how the theoretical analysis and proof technique relates to that in Srinivas et al.
- The empirical results are quite convincing and are presented well. What I feel is missing are some other existing robust BO methods (e.g. optimizing VaR or CVaR). While those may not specifically target the mean-variance model formulation, they could still perform quite well in terms of the regret defined here. The method from [3] has been implemented in botorch and should thus be quite easy to hook up into the submitted code: https://github.com/pytorch/botorch/blob/master/tutorials/risk_averse_bo_with_environmental_variables.ipynb
- The FEL setup sounds quite interesting, it would be nice to get some more details into the non-anonymized version.
- The authors state that "In settings where the noise is homoscedastic, our approach does not bring additional value". I think there is more to that, likely sample efficiency will suffer compared to approaches that were not designed with robustness in mind. It could be valuable to provide some analysis of the performance in case the noise is indeed homoskedastic; this would allow to get some idea of the "price of being robust to heteroskedasticity". To understand this, it would be good to have an ablation study that uses a homoskedasatic setting.
- Please honor botorch's request for citation https://github.com/pytorch/botorch#citing-botorch [2]
- Misc:
    - l. 229: be clear what you mean by heteroskedastic GP (looks like it's a botorch FixedNoiseGP)
    - Fig 5: "Simple regret fat the reprted"
    - The term "zeroth-order observation" may not be clear to everyone, consider rephrasing (no gradient info)


### Questions:
- Can you explain the difference between your modeling setup and the HeteroskedasticSingleTaskGP from https://github.com/pytorch/botorch/blob/master/botorch/models/gp_regression.py#L339 ?
- The fact that `k` (the number of function samples to estimate the local variance) is fixed and non-adaptive is somewhat disappointing. It should be possible to improve sample efficiency by in later stages making this adaptive to the posterior uncertainty of the variance proxy at the point to be evaluated. In fact, you could be Bayesian about this, too. This would mean interpreting the posterior distribution of the variance proxy as your prior, and then the `k` samples as observations, and then use the observations to update this prior. Did you consider this?

### References:

[1] K. Kersting, C. Plagemann, P. Pfaff, and W. Burgard. Most likely heteroscedastic gaussian process regression. In Proceedings of the 24th International Conference on Machine Learning, ICML ’07, pages 393–400, New York, NY, USA, 2007. ACM.

[2] M. Balandat, B. Karrer, D. R. Jiang, S. Daulton, B. Letham, A. G. Wilson, and E. Bakshy. BoTorch: A Framework for Efficient Monte-Carlo Bayesian Optimization. Advances in Neural Information Processing Systems 33, 2020.

[3] S. Cakmak, R. Astudillo, P. Frazier, and E. Zhou. Bayesian optimization of risk measures, 2020

limitations_and_societal_impact: - In my mind, the main practical limitation of the paper is that the parameter alpha will often be unknown in practice (w/o already having a reasonably good understanding of both the behavior of the function and the noise). The authors have not really addressed this and should expand on it in their discussion.
- The authors state that "In settings where the noise is homoscedastic, our approach does not bring additional value". I think there is more to that, likely sample efficiency will suffer compared to approaches that were not designed with robustness in mind. Ideally this could be quantified in an ablation study, and at the very least discussed.
review_title: null

Meta-review: This paper makes an important contribution to the theory of Bayesian optimization. Namely, it provides a sublinear cumulative regret bound in the heteroscedastic setting, the first of its kind, and show that this regret bound additionally applies in the risk averse setting. This result is particularly significant given that the overwhelming majority of Bayesian optimization papers assume homoscedastic noise, which may arguably less common than the heteroscedastic setting. Be sure to incorporate suggested minor corrections by the reviewers in the final camera ready version.
Decision: Accept (Poster)