Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper considers Bayesian optimization (BO) of objective functions of the form $c_f(x;\alpha) = \mathrm{CVaR}_\alpha(f(x, W))$, where $f$ is modeled as a Gaussian process (GP),, and $\mathrm{CVaR}_\alpha$ denotes the $\alpha$-level conditional value-at-risk, which is computed with respect to the randomness over $W$. This work focuses on the simulation optimization setting, where it is possible to evaluate $f(x,w)$ for each $(x,w)\in\mathbb{X}\times\mathbb{W}$, and develops two acquisition functions to select the pairs $(x,w)$ at which to evaluate $f$, CV-UCB and CV-TS, which extend the classical UCB and Thompson sampling acquisition functions, respectively. These algorithms select the $x$ component of the pair and are complemented with a common strategy to select $w$. Given $x_t$, the $x$ component of the pair to be evaluated at time $t$, this strategy first chooses $\alpha_t$ that maximizes the difference of the VaR of an upper confidence bound on $f(x_t, W)$, $u_t(x, W)$, and the VaR of a lower confidence bound on $f(x_t, W)$, $l_t(x, W)$. Finally, given $x_t$ and $\alpha_t$, this strategy chooses $w_t$ so that   $[\mathrm{VaR}_\alpha (l_t(x, W)),  \mathrm{VaR}_\alpha (u_t(x, W))] \subset [l_t(x_t, w_t), u_t(x_t, w_t)]$ (for $\alpha= \alpha_t$). A $w_t$ satisfying this condition is called a lacing value. The two resulting algorithms are shown to enjoy sublinear cumulative regrets when $\mathbb{X}$ and $\mathbb{W}$ are both finite. Finally, the empirical performance of these algorithms is evaluated in three synthetic experiments and two real-world experiments, showing favorable results.
main_review: Originality: The proposed algorithms are, to the best of my knowledge, novel, and are the first ones for GP-based optimization of CVaR that come with theoretical guarantees. However, these algorithms (including their theoretical analysis) heavily rely on the work of Nguyen et al. 2021. The algorithmic contributions of this paper are, therefore, somewhat limited. In this regard, the most novel aspect of this work is the CV-TS algorithm, which allows for batch evaluations. In addition, as acknowledged by the authors, the problem setup has been previously considered in the literature (see, e.g., Cakmak et al. 2020), and the test problems are the same (translated from VaR to CVaR) as those in Nguyen et al. 2021. As a consequence, the overall novelty of this work is limited.

Quality: The proposed algorithms are technically sound. The proofs on the regret bounds seem to be correct (although did not check in detail some of the calculations).  With only three synthetic test problems and two realistic test problems, the empirical evaluation is somewhat limited. Moreover, claims about the computational efficiency of the proposed algorithms have not been properly backed up. For this, I would suggest the authors to include a table of the average running times of each algorithm in each problem.

Clarity: This paper is fairly well written and easy to follow. One suggestion is that the paper would benefit from a picture illustrating the behavior of the proposed algorithms.

Significance: Risk-averse Bayesian optimization is a problem of high practical relevance. Moreover, the only existing algorithms (for the CVaR setting), $\rho$KG and its approximate variant, are fairly computationally expensive. Therefore, cheaper algorithms with good empirical performance are relevant and prone to be adopted by practitioners. The algorithms proposed in this paper seem to poses these characteristics. However, a more thorough empirical evaluation is required.
limitations_and_societal_impact: The authors have implicitly discussed the limitations of their work. However, I it would be beneficial to summarize them and discuss them more explicitly in the conclusion. The societal impact of this work has not been discussed.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper proposes to methods to maximize the conditional value-at-risk (CVaR) of a black-box function: the CV-UCB (Upper confidence bound) and the CV-TS (Thompson sampling)

main_review: - This paper is very relevant to reference [12], in which the Bayesian optimization algorithms for VaR has been considered. It is unclear to me why the CVaR objective may be *significantly* different or more difficult than the VaR objective. Both VaR and CVaR are risk measures, and from the theory side, one can use any other risk measures as an objective (spectral risk measure, distortion risk measure, etc.). The critical step in the UCB algorithm is to construct the confidence bound in equation (6), however, this bound can be easily generalizable as well by plugging in the corresponding formula of other risk measures. The regret bound also follows with minimal modification from Srinivas et al. (2010), and differs minimally from the VaR approach as in Lemma 3 of [12].

- The batch extension for CV-TS is straightforward for Thompson sampling which naturally handles parallel evaluations. This idea was also used previously in [12]

- The experimental results are limited and not convincing. No real-world application is considered, and the simulated robust pushing experiment does not look very promising. 


limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposes Bayesian Optimization (BO) approaches optimizing the conditional value-at-risk (CVaR) of the objective function distribution. Assuming the access to the objective function f(x, w) with full control of the environmental parameter w in the optimization time and assuming the prior distribution p(w) of the environmental parameter, the authors develop two algorithmic variants to optimize CVaR of  a given risk level. 

The main contribution is the theoretical guarantee of the proposed variants. For the first variant, CV-UCB, the cumulative regret bound has been proved. For the second variant, CV-TS, the upper bound for the Bayesian cumulative regret has been proved. 

The proposed approach has been tested on 3 synthetic benchmark problems and more realistic problems including portfolio optimization and simulated robot pushing experiment. The proposed approaches have been compared to an existing approach from [4], which can be applied to CVaR but not theoretical guarantee has been developed for. The results show competitive or superior performance.
main_review: This paper is very well written. This research topic is an important direction. The theoretical results are strong. 

The only weakness of the paper is in experimental evaluation. 
1. The tested problems are rather low dimensional problems, both in x and w. Especially for w, if I am not mistaken, the test problems are all of dimension no more than 2. I think this is a limitation. I recommend to add results on higher dimensional problems or to mention this limitation.
2. Though the authors list the computational cost  as one of the shortcomings of the approach in [4], I couldn't find any comment on the computational time in this experiments. It is advised to mention the computational time for each approach on each experiments.
3. It is interested to see how well the proposed approach works compared to other types of BO methods, such as the standard BO that simply optimize the expected value and the BO solving minimax optimization problems like [1], though they are not optimizing CVaR. It is often the case that minimizing the expectation contributes to minimizing the worst case, though not optimal. I strongly recommend to include the results of these baselines to enhance the empirical evaluation and revealing a possible limitation. 
limitations_and_societal_impact: The limitation is not quite described. Please refer to the main review above.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper considers a robust/risk-averse Bayesian optimization problem. In particular, the authors focus on maximizing conditional value at risk (CVaR), when the objective is unknown. 
They propose two algorithms based on UCB and Thompson sampling strategies. Both algorithms are tested on synthetic datasets/tasks. 

main_review: The paper is clearly written and easy to understand. It contributes novel algorithms and tools (mostly, when it comes to the introduced TS strategy) for robust Bayesian optimization (BO). It builds upon previous robust BO works in which the goal is to optimize the unknown function subject to uncontrollable (at test time) covariate. In general, this problem is interesting and is of significant interest in practical applications. Different from the previous works, that study worst-case robust optimization, DRBO, mixed strategies, and VaR objectives, this work considers the CVaR objective.   

As a related work, I’d expect more comments on the relation between CVaR formulation and DRO problem (with particular ambiguity sets) and the fact that DRO models have an equivalent risk-averse optimization problem (see, e.g., Rahimian and Mehrotra, DRO review, Section 3).
I’m wondering to what extent can we then utilize the existing DRBO algorithms? And, in such a case, wouldn’t they at least be proper baselines to compare against? 

162:166: I think that this paragraph needs to be more precise. Before this paragraph on time complexity, you haven’t specified the set X (later on, X is considered to be finite). N_train and gradient-based optimization of the acquisition function is not explained. If X is not finite, then we are talking non-convex continuous optimization (this is fine, since non-convex acquisition functions are standard in BO, and for the sake of theory we assume that we can optimize them). The sentence, “the number of gradient descent steps to find maximizer” sounds like you’re solving a concave problem. 

At first selecting alpha_t in the algorithm given that alpha is fixed was strange to me, e.g., why learn at different levels of risk alpha if the learner knows the true parameter value. By following your regret derivation in the appendix, I could see why this is necessary for the analysis to work. Do you think that there is a way to directly select w_t as a function of alpha and x_t and not alpha_t? E.g., in the previous robust BO works, such as the one cited below or, e.g., [1], the second variable is selected to maximize the uncertainty given the previously selected x_t.    

The concept of lacing values is very important and crucial in the analysis. It’d be good perhaps to explain/summarize the proof of existence (perhaps, in the appendix) from [12] to improve the clarity of the paper.

Can you comment on your analysis when X is not finite? For example, this assumption is used in the proof of Theorem 2. Also, having X being finite and having the main results expressed in terms of gamma_T, with the additional comment of gamma_T being sublinear for most of the kernels is a bit informal.  

Figure 1 nicely explains the difference between VaR and CVaR. I like the joint pseudocode presentation of TS and UCB with the common selection of w_t. I find the performed experiments to be very standard (as in other BO and robust BO works) and not exciting.    

Some minor comments: 

-- Abstract: “an interesting connection between CVaR and VaR”; Aren’t we only talking about one of the definitions of CVaR in terms of VaR? Can you clarify the “interesting connection”?

-- It’d be interesting to also learn about the distribution of W simultaneously as was also considered in some of the robust BO papers. 

-- Another relevant robust BO work is: “Mixed Strategies for Robust Optimization of Unknown Objectives” from Sessa et al. where instead of selecting a single robust design as in your work, the authors seek to discover a robust distribution. 

-- 108: The considered noise model is homoscedastic, so perhaps avoid writing epsilon(x,w).

-- Algorithm 1: alpha is an input. 

-- An interesting research question, is can you get similar regret guarantees and adapt in case the true alpha is unknown? 

-- Mathematical definition of the maximum information gain is missing.

limitations_and_societal_impact: Yes.
review_title: null

Meta-review: This paper addresses Bayesian optimization to search a maximizer of the CVaR of the black-box objective function. Two variants inspired by UCB and Thompson sampling are presented. For CV-UCB, the cumulative regret bound has been proved and for CV-TS, the upper bound for the Bayesian cumulative regret has been proved. The paper is well written and the topic is interesting. A few reviewers pointed out the weakness of empirical evaluations. The authors promised to include an additional experiment whose preliminary results are reported in the rebuttal.The rebuttal was not fully satisfactory but the efforts in providing preliminary results were appreciated. During the committee discussion period, two of reviewers raised the score. Some concerns in the limited novelty over previous work still remains. However, the paper presents a solid theoretical guarantee, which might not be obviously derived from known results. 


Decision: Accept (Poster)