Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This work investigates the problem of Bayesian optimization of the output of a network of functions. The network is organized as a directed acyclic graph, where each function takes as input the output of its parent nodes as well as (part of ) the input. Contrary to the standard setting that only observes the final output, this work assumes that intermediate nodes can also produce an output (which can be stochastic or deterministic). The authors model the nodes of the network using Gaussian processes, and employ an acquisition function that corresponds to the expected improvement with respect to the implied posterior on the final output under a proper statistical model. The authors optimize the acquisition function using sample average approximation. The authors show that their approach satisfies asymptotic convergence. Various experiments on synthetic and real problems demonstrate that the improved model and acquisition function result in visibly improved solution quality, at the expense of the runtime cost.
main_review: Strengths
- This work introduces a new setting for Bayesian Optimization (BO) that is highly relevant in practice, e.g., in engineering applications. This work seems to be the first to address this setting. For this reason, this work is fairly significant.
- On the theory front, the work includes a convergence proof. Furthermore, it investigates the interesting property that the acquisition function for function networks does not need to measure the optimization domain densely. This suggests a possible mechanism via which the new acquisition function can lead to more efficient BO.
- The paper is well written and easy to follow.
- The experimental section is well written and demonstrates that the new model and acquisition function achieve superior result in terms of the objective value. The problems considered in the experimental study are diverse and quite realistic.

Concerns
- Using GPs to model the various nodes in the function network, and optimizing the acquisition function via sample average approximation are not particularly novel for that setting. Even though the problem statement in this work is novel, the authors have chosen a rather straightforward approach to tackle it. That being said, they do show consistency.
- Convergence rates are not discussed, only consistency.
- The method is quite time-consuming compared to simpler competitors, as illustrated in the runtimes. This problem can be exacerbated for large function networks with several nodes.

Additional questions to authors
- How does the computational complexity depend on the number of nodes in the function network? Experimentally, function networks of up to how many nodes have the authors been able to handle?
- The framework can deal with both deterministic and non-deterministic nodes. What about nodes whose output is hidden? Can the framework handle such cases for an arbitrary node (assuming of course the DAG structure for the function network)?
limitations_and_societal_impact: Limitations and potential societal impact are discussion in the Conclusion.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper extends methods for Gaussian process "Bayesian Optimization" (BO)  of vectors of hyperparameters to structural networks of function, to include hyperparameters from functions of intermediate stages. Unlike a conventional approach, this method considers the output of intermediate stages.  The hypothesis addressed by the paper that including additional information from intermediate stages is a reasonable one, however it raises a challenge since despite the intermediate functions each being modelled as a GP, the final output g is not necessarily Gaussian.  To accommodate this, they apply sample average approximation to sample from the posterior on the final output.

The authors apply this method in the context of several application areas, having run experiments on 8 problems with results showing substantially faster convergence than competing methods.  

This paper offers a convincing empirical study together with theoretical convergence results. This is an interesting paper with useful learning to the general community.
main_review: The paper's approach is to provide an approximation to the posterior for the acceptance function, EI-FN, using a sampling method based on the 'so-called re-parameterization trick."  In Proposition 1 they show a convergence proof for the function.   The optimization efficiency they claim is demonstrated in the set of empirical problems on both simulated and actual data. 

As for the evaluation criterion used, in the calculation of the approximated EI-FN function, the method generates M samples (even from the posterior distribution without actually evaluating the network) that can potentially reduce the variance of this evaluation. It appears that the posterior distribution is still estimated only using the n samples. When counting the number of iterations,  in Figure 2, is the x-axis  only counting n as the iteration number?  One wonders if the the total number of function evaluations would be a fairer basis for comparison , given the implication of this paper is that this “synthetic” M samples are the key to improve the convergence rate. This leads to a speculation if there exists other ways of generating the samples that can possibly lead to even better convergence rate (either based on posterior distribution or not).

As claimed, basic information-theoretic notions lead one to believe that the intermediate values used in the EI-FN function should lead to more efficient sampling estimates, hence faster optimization.  This property, although demonstrated in the empirical results, is not supported, and deserves further study since the analysis provided only hints in broad terms why it comes about. Convergence rates alone are only an indirect explanation for the observed efficiency.  Perhaps there are diagnostics derived from comparing conventional acquisition functions with the approximations generated?  

To speculate further, the example network structures resemble probabilistic graphical models, so one could imagine an inferential approach to compute distributions over the x's that would enable estimation of how much improvement is due to an x's additional information.   This is not to criticize the work to date, but it's surprising that thoughts about this did not get a mention. 
limitations_and_societal_impact: The authors are cognizant that this technique can be used for ends that are both socially valuable or destructive, and state as much.  In it's current nascent form there is no reason to presume it's use would encourage abusive uses.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper presents an extension of Bayesian optimization with Gaussian processes and expected improvement for target functions that are the results of composite functions from a DAG model. The paper introduces an extension of the expected improvement for the specific case which does not allow for a closed form solution. Instead the authors approximated the acquisition function with a sample approximation and optimized it using sample average approximation. The paper also includes some theoretical results in terms of consistency (although not convergence) and extensive results.
main_review: The paper extends on the work of Astudillo and Frazier, 2019 for general compositions of functions. In fact, even the structure of the paper is similar which simplifies the reading process if you are familiar with the previous paper. However, I think that this paper abuses the supplementary material. The paper should be self contained, but the text includes 14 times the word “supplement”. I understand that space constraints are an issue, especially after extensions from previous revisions. For example, in my opinion it would be better to fully describe and explain a couple of experiments in the main text, even including Figure 2 as is, instead of half describing all of them.

The extension and the method proposed seem original and, as pointed out in the related work, the problem can be motivated in many areas of science and engineering. I think the NeurIPS community might be quite interested in the RL setup.

The whole point of the statistical model and the SAA optimization is the result of the posterior distribution not being a Gaussian in the general case. However, the samples of any output h are drawn from Gaussian distributions, including hK = g. Furthermore, the authors recommend using SAA with deterministic samples, because the evaluations of the acquisition function are noisy. However, isn’t that the result of using a naive MC strategy? Having a DAG, wouldn’t be better to use belief propagation or exploit the structure with some MCMC or particle filter and have a more accurate representation of the acquisition function? I can see how BP can be much more expensive than the suggested approach, but this method is already quite expensive compared to regular BO. Furthermore, it seems that the use of SAA is not clearly motivated, being the default method for MC-based acquisitions in BoTorch.

The results are quite interesting. Clearly, the method reaches SOTA, even compared to simpler versions, such as EI-CF. However, the authors mix absolute value with log(regret). For instance, they claim that the improvement in the robot problem is quite large. However, any real robot application can be considered “solved” with log(regret) = -2 or -3. From a pure numerical/benchmark point of view, the result is still interesting, but then I would like to have a more realistic RL setup. For example, the suggested setup or learning a sequence of waypoints as a policy has been previously done in BO for robot navigation:

Ruben Martinez-Cantin, Nando de Freitas, Eric Brochu, Jose Castellanos and Arnaud Doucet (2009) A Bayesian Exploration-Exploitation Approach for Optimal Online Sensing and Planning with a Visually Guided Mobile Robot. Autonomous Robots - Special Issue on Robot Learning, Part B, 27(3):93-103.

Small comments:

-Given that KG is sometimes superior to EI, would it be possible to have KG-FN or is there a limitation that could prevent it?

-If the robot pushing and epidemic model are in the perfect setup for EI-CF, how would you explain the improvement of EI-FN?

----
Notes after author response: The authors have addressed most of my concerns. I'm glad that the new experiment worked so well. It clearly shows the advantages of the proposed method and I have updated my score as a result. 

As a final suggestion, one of the advantages of the method is clearly computational cost. Thus, I would address that with some results or comments regarding that. The fact that "vanilla" KG is x4 more expensive than EI-FN is remarkable, as one would expect EI-FN to be the more expensive given the number of GPs to manage.

limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper focuses on Bayesian optimization of function networks, where the objective function has a known structure that is a composition of individual (node) functions that take the output of the previous function as input (along with potentially other parameters). Observations at each node function are obtained at each objective function evaluation. Such objective functions arise in a variety of applications including materials design and physical processes. Exploiting knowledge of the network structure can result in a lower effective input dimensionality of the model of each node function, depending on the network structure. By modeling each node function as distinct GP, the authors demonstrate improved sample efficiency using EI compared to optimizing the global objective function with a single GP or using compositional objectives.
main_review: Strengths:
-	The idea that accounting for this structure is beneficial is simple and intuitive
- The empirical performance is quite compelling

Weaknesses:
-	There is not much technical novelty. Given the distinct GPs modeling the function network, the acquisition function and sampling procedure are not novel
-	The theoretical guarantee is pretty weak (random search is asymptotically optimal).
  - The discussion of not requiring dense coverage to prove the method is asymptotically consistent is interesting, but the utility of proposition 2 is not clear because although dense coverage is a consideration for proving consistency, it is not really a practical reality in sample-efficient optimization—typically BO would not have dense coverage.

Questions/comments:
-	There is no discussion of observation noise, which is a practical concern in many of the real world use cases mentioned in the paper. The approach of using GPs to model nodes in function network can naturally handle noisy observations, so only the acquisition function would need to be adjusted to account for noisy observations since the best objective value would be unknown. I expect that the empirical performance would remain the same (e.g. using Noisy EI from Letham et al. 2019), but the computation would be much more expensive. It would be good to discuss and demonstrated performance under noisy observations.
-	How does the number of MC samples affect performance, empirically? How does the network structure affect this?
-	It would be interesting to see a head-to-head comparison with deep GPs. How different are the runtimes (including inference times) and empirical performances? 
- Since the core contribution is modeling each node in the function network with a distinct GP, it would be good to see more evaluation of the function network model's predictive performance compared to a alternative modeling choices (e.g. individual models with a compositional objective, vanilla global gp, deep gp)

Grammar:
-	L238 “out method” -> “our method”
-	L335 “structurre” -> “structure”

limitations_and_societal_impact: The discussion of the work's limitations is quite thorough, and it proposes interesting directions for future work. The authors have addressed potential negative societal impacts.
review_title: null

Meta-review: This paper addresses Bayesian optimization which leverages the intermediate outputs as well as final outputs when they are available by evaluations in the function network. The problem setting is novel, extending the previous work [Astudillo, R. and Frazier, P., 2019]. A cascade of GPs is used as a surrogate model, leading to non-Gaussian process. A sample average approximation approach is used to optimize the EI. Strong empirical results are provided to demonstrate that the proposed method indeed achieves superior performance. The strength of this paper is in the novel problem setting, its usefulness in engineering applications mainly for practitioners. The downside is in the limited novelty in the proposed solution, since it is a direct employment of GPs and SAA. During the committee discussion period, I had a few communications with reviewers. The problem setting, which appears often in engineering applications, is valuable for further studying.  Thus, even if the proposed solution is not novel, this work studies an important and valuable problem, and could serve as a starting point for new works that could develop more sophisticated algorithms or deeper theory for the DAG-dependency setting.


Decision: Accept (Poster)