Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: The paper proposes an efficient algorithm for a novel optimization task where the distance of candidates to be evaluated incurs input costs. The algorithm penalizes the input variations on top of the traditional Bayesian Optimization algorithm while leveraging the batched Thompson sampling to diverge the candidate picks. Traveling salesman The problem is solved to create an efficient path for the batched query.
strengths_and_weaknesses: - ***Strengths***
1.  The paper studies a novel distance-aware optimization setting motivated by real-world application.
2.  The paper proposes a novel solution to penalize the input variations while avoiding being stuck in local areas in the optimization by the combination of batched Thompson sampling and the proposed $\epsilon$-point deletion. The algorithm design is motivated by insights derived from the analysis of the desired escape from the local optimum.
3. The algorithm empirically validated that the input cost dropped.
	
- ***weaknesses***
1.  The cost in this problem setting is not defined in a principled way. The paper attempts to minimize the regret within a certain number of iterations while minimizing the input variation cost. Essentially there is one optimization objective and two types of costs considered. One cost is the number of iterations, which is the typical BO cost given each evaluation is expensive, and the other cost is the input variation. The triplet structure of the problem incurs a challenge in performance measurement. Instead of merely comparing regret within a certain iteration as in the traditional BO setting, the triplet requires the additional comparison on costs, which make the performance of different algorithms less comparable. 
For example, as shown in figure 3, EIpuLP achieves lower cost while bears higher regret compared to the proposed algorithm, it becomes unclear whether EIpuLP is better in figure 3. Similarly, when the same mixed performance appears for different hyperparameter settings, there lacks a principled way to pick the better hyperparameter. Unless there is a weighted sum of the two different costs where the weights reflect the importance of these costs in the application, it's hard to compare algorithms and hyperparameter choices. The corresponding algorithm design should also consider the weights. Otherwise, it's possible that there exists an algorithm that is significantly superior on one cost while lags on the other. Algorithms like Genetic algorithms that only conduct small variations in each step could potentially bear much lower input costs while incurring a much larger amount of iteration.
2. As mentioned, Genetic algorithms could be included in the baselines.
3. The paper argues that the $\epsilon$-Point Deletion is robust to the hyperparameter choices and proposes to leverage the lengthscale of the kernel to adaptively pick the value of $\epsilon$. The robustness is counter-intuitive as the local (sub)gradients of the objective function could be different even assuming a global smoothness guarantee for the objective function. Additional study on the $\epsilon$-point deletion algorithm behavior might be necessary to explain the robustness, especially on the ratio of the random deletion among all deletions for each performance curve.
4. The confidence intervals of the regret curves for experiments are large and potentially indicate the lack of statistical significance of the results. Could the author provide corresponding p-values?
questions: 1. For figure 3, does 3.a and 3.b share the legend in 3.c? If so, I would suggest putting the legend in a shared space instead.
2. In equation (1), the \gamma is mostly set to be 1 and could be problematic. For example, when the search space X is scaled up, the shape of the objective function remains the same while the behavior of the algorithm could change as the cost(x, x_{t-1}) is scaled up. Is there any normalization of X in the preprocessing? Could the author demonstrate the corresponding performance of different \gamma?
limitations: The author addresses the concerns.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This work tackles the problem of cost-aware optimization of expensive-to-evaluate functions for which large changes in the input parameters between consecutive queries incurs large cost. The paper assumes the cost function, a function of the current parameters and parameters evaluated immediately before, is known a priori. The paper proposes a novel Bayesian optimization algorithm for this problem setting that plans a path of future designs. The method first generates a batch of new promising designs via Thompson sampling and then orders the points by formulating the problem as traveling salesperson problem (TSP) and approximately solving the TSP problem with simulated annealing. To reduce the issues of sampling points that are close to one another, the paper proposes to generate a larger than needed batch and delete the closest design to each previously evaluated point if the closest design is within a certain radius (a new hyperparameter) of a previously evaluated design--otherwise a random point is deleted. The method works for the asynchronous setting where the next design must be selected before some number of previous designs have returned.
strengths_and_weaknesses: Strengths
* Optimizing sequences of designs (paths) is a neat idea and as far as I know, a novel formulation. 
* The paper is largely well written (aside from some undefined acronyms and minor comments listed below).
* The chemistry problem is a great example

Weaknesses
* However, the prevalence of these problems appears limited, and therefore the contribution appears to be a highly nuanced class of problems (see discussion of sequential nature of evaluation below). 
  * The chemistry problem showcased in Figure 6  and included the experiments is a compelling example, but it does not seem that the other real-world inspired example problem (the lake problem ) fits this problem class. 
* In addition, the proposed technique for dealing with sampling nearby previously selected designs (of deleting nearby points) is not theoretically grounded. 
* The mathematical analysis in Sec 3.7 has weak insights.  
* There are no significant theoretical results
questions: 
* Are there other compelling examples/demonstrations that can be included to illustrate other instances of this problem class?
* What is the typical level of parallelism (asynchronicity)?
  * The path ordering issue is relevant when designs are evaluated sequentially (as in the chemistry problem in Figure 6). This point should be highlighted upfront. Typically, in batch/async BO, it is assumed that designs are evaluated simultaneously, but the path ordering problem is only relevant when there is some sequence to the evaluations. Although the lake problem does have sequential evaluation (if you only have one boat), there does not seem to be motivation for asynchronous generation/scheduling, but certainly non-myopia is important. The question then becomes how does SNAKE compare with a non-myopic cost-aware BO method?
* What is the wall time of SNAKE to generating a batch of points? Given that it is expensive, empirical time results should be included in the paper
* The claim that SNAKE can optimize multiple objectives should be toned down. Typically, the goal in multi-objective optimization is to learn trade-offs between objectives, but this paper simply optimizes the sum of the objectives
* Should the number of generated points for purposes of the TSP (non-myopic planning) potentially be different from the level of parallelism? It appears that the number of generated points is currently the level of parallelism, but this also means that the algorithm gets more myopic as the parallelism decreases. 
* L185: shouldn’t p_t on the RHS be p_{t_e}? The result doesn’t obviously hold in that case.
* How does using epsilon-point deletion compare penalizing the objective based on the distance to previously evaluated or selected designs? Is the a reason to prefer one approach over another. If not, empirical justification for the choice seems warranted
* L204: “may be approximately constant with time”. Can you elaborate on this? Currently this statement sounds hand-wavy

  * How does the method change if there are multiple queues (for example multiple boats in the lake problem or multiple places to run experiments in the chemistry problem)?
  * The level of parallelism should be stated clearly for all problems
* L223: the adaptive grid is mentioned very briefly, but it warrants further motivation and discussion in the main text. It also appears to introduce new hyperparameters
* 10 replications does not seem sufficient. The error bars of +/- one half of a standard deviation are not informative and raise questions about the soundness of the results
* The clarity of the results section would benefit if the baselines were clearly described upfront. TREI is never defined in the paper. L252 mentions LPwUCB, but figures say UCBwLP. EIpuLP is not defined.
* Why is no other cost-aware non-myopic BO method compared against? For example, Lee et al., 2021.
* L144: I recommend moving Figure 1 up further in the paper. It is mentioned on page 4, but does not appear until page 6
* L151: Why focus on a ball centered at `a` rather than x_{t-1} or the set of balls centered at each previous design (stating `a` is a previously evaluated design or design in the batch suffices)?
* Figure 3: the methods should at least be described before the results

Lee et al., 2021. A Nonmyopic Approach to Cost-Constrained Bayesian Optimization.
limitations: In L240-241, some limitations of SNAKE are highlighted. Further discussion of SNAKE's limitations would be good. No societal impacts are discussed, but such discussion seems unnecessary.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This work presents a low-cost Bayesian optimization solution, which is inspired by real-world applications. The proposed method is analyzed mathematically in Section 3. Experimental results in Section 4 shows the effectiveness of the proposed method when compared with several state-of-the-art methods. Comprehensive experimental results are shown in the appendix. 
strengths_and_weaknesses: The solution has a novel idea of optimizing sample paths while minimizing the input costs. The paper is well-written with understandable examples and mathematical formulation. The comprehensive experimental results support the effectiveness of the work. 

However, there are some minor drawbacks: 1) The notation used in formulation can be pre-defined so that readers understand them better; the paper would be self-contained if notation is well-defined. 2) Minor editing flaws: Figure 5 is mentioned before Figure 4; Fonts in figures can be enlarged for better readability.
questions: Why does UCBwLP perform better in Figure 3(b) than the proposed method?

As the proposed method is claimed to be low-cost. Can the authors provide quantitative analysis of this work with other existing methods in terms of cost?

What's the impact on the proposed work if the delay of observations varies?
limitations: Low-cost analysis of the proposed work is not provided.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper introduces a new variant of cost-aware BO: It is more expensive to evaluate two points one after the other if they are farther away from each other than if they are close to each other. A method (SnAKe) for this setting is suggest, that approaches the problem in the following way: In each iteration, a new batch is sampled, using Thompson seedling. The evaluation order of the points in the batch is formulated as a TSP and optimized. The method runs asynchronously, i.e. points are resampled after every new observation. However, this leads to too much exploitation, which is why sampled points epsilon-close to already evaluated points are not taken into account. The method shows a good performance on synthetic benchmarks and two real-world examples. 
strengths_and_weaknesses: The work is original, and I think it is an interesting question how to balance exploration with exploitation, when there are additional external factors (like costs), that influence the trade-off between the two. The setting is also signifiant for real-world applications of BO. 
The experiments support the claims of the paper. The real-world experiments are nice. A strength of the method is that it seems to be robust to the choice of hyper parameter epsilon.

The writing could be improved in some aspects, e.g.:
* In section 2 (line 68), the abbreviation "EI" is used without definition. It becomes clear from the context that it means "Expected Improvement", but I would mention this somewhere explicitly. 
* Maybe one could change the color-scale in Figure 2. It's a bit difficult to see the gradation. 
* I would suggest to have Section 3.3. as part of Section 3. One could also mention the definition of regret in Section 3.1
* I am not a native English speaker, but the wording sometimes seems a bit informal to me. 
questions: The optimized paths in Figure 4 all look the same, even though the objectives are different. Is there a reason or could this be a plotting error?
limitations: The authors address limitations: The method performs less well in higher-dimensional search spaces and low-budget settings.
review_title: null

Meta-review: metareview: There was disagreement among the reviewers about whether this paper should be accepted. But taking the long view about how this paper might be perceived in 10 years, and reading the paper in detail myself, I lean towards acceptance being the right decision for this paper. My reasoning:
- The problem being solved is completely novel as far as I am aware, and is well-motivated by a realistic real-world scenario in a large field of research.
- The proposed approach is a highly-original variation on BO that, despite not being justified by theory at all, seems like a plausible direction to explore to get faster algorithms.
In light of the above, the potential impact of the paper might be large: we may discover other applications that have the same cost setup, we may encourage ML researchers to take on chemistry-motivated problems, we may encourage theory researchers to analyze the method (or more likely to come up with methods that are justified), or we may see empiricists use similar ideas in other settings.

That being said, the reviewers point out some completely-valid criticisms. So I expect to see quite a few updates in the final version of the paper. Please comb through the reviews carefully (particularly the two critical reviews) and update the paper based on the reviewer's comments, including and beyond what is already written in the author response. I could imagine many readers having similar issues (e.g., tone down any indication that the algorithm is theoretically justified from a regret perspective), and some of the comments represent ways the paper could be complete in its exploration of the topic.
confidence: Less certain
Decision: Accept