Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper proposes to apply a simple adaptive dimensional reduction technique on Trust Region Bayesian Optimization (TuRBO) for high dimensional Bayesian optimization task which has low effective dimensionality. The algorithm improves the probability of containing the optimum in the embedding space over previous work Hashing-enhanced Subspace BO (HESBO) by enforcing the hashing from the input dimension to the low-dimensional embedding to be evenly distributed. The paper demonstrates the efficacy of the proposed algorithm with a comprehensive empirical study.
strengths_and_weaknesses: - ***Strengths***:
1. Well-motivated algorithm design with the theoretical guarantee of its optimality over the existing HESBO in terms of probability of containing the optimal candidate in its embedding.
2. The proposed embedding is well-integrated into the existing HDBO framework TuRBO with appropriate algorithmic modification. Ablation studies prove the efficacy of each part of the proposed algorithm. Theoretical analysis in the appendix also shows that it inherits TuRBO's convergency. 
	
- ***Weaknesses***:
1. Some of the definitions and concepts are confusing. In lines 59-62, the definition of the active subspace seems to be incomplete.  If for all x, z = f(x), g(z) = z, then the effective dimensionality could always be 1 regardless of the structure of X. I suggest defining the subspace as in definition 1 of the REMBO paper which defines the effective subspace and effective dimensionality. For definition in lines 157 - 162, could the author specify the reference? The classical definition of count-sketch structure assumes the pair-wise independence of the hashing functions [Charikar et al. 2002]. This is how HESBO implements its dimension reduction.
		
2. The classical count-sketch techniques rely on the pair-wise independencies of the hashing functions assigning input dimensions to different bins and the four-wise independencies of the sign assignment function as mentioned. The HESBO chooses the uniform random hashing which follows the assumption. The independency of hashing seems to be violated when BAxUS enforces that the input dimensions be evenly distributed to bins. Therefore, the original theoretical guarantee of the count-sketch structure probably does not hold in this case. The paper doesn't inherit the independency assumption on its count-sketch definition and lacks a discussion on this violation of independency of the hashing function.  
In practice the violation of independency might not hurt much as in expectation HESBO also distributes the input dimensions evenly to target dimensions and the downstream performance of the proposed embedding is strong. However, the missing independency downgrades the theoretical contribution of the paper due to its violation of classic count-sketch structure and lacks a discussion on it, especially when considering that the work is motivated to improve upon HESBO while doesn't inherit its advantage strictly.
	
3. As far as I know TuRBO doesn't work well sometimes when only one trust region is operating and that motivates the TuRBO-m which is the m-trust-region variant of TuRBO (TuRBO-1) in the original paper. BAxUS lacks discussion over this problem. I expect a brief discussion over its choice of m and the corresponding implementation. 

4. The descriptions could be confusing as the notations are not well specified between line 138 and line 147. And deferring algorithm 2, which is a critical part of the algorithm, to the appendix might not be a good choice.

*Reference*:
Charikar, M., Chen, K. and Farach-Colton, M., 2002, July. Finding frequent items in data streams. In International Colloquium on Automata, Languages, and Programming (pp. 693-703). Springer, Berlin, Heidelberg.

questions: 1. I might have missed the part. How many independent trails are conducted for each algorithm during experiment?
2. Could you provide results on the 60D Rover trajectory planning task that has been tested in TuRBO original experiment? I believe the task is available here https://github.com/zi-w/Ensemble-Bayesian-Optimization.

limitations: Not applied.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper proposes BaXus, which extends TRBO (trust region Bayesian optimization), by using not just trust regions but a linear embedding of varying dimensionality. The linear embedding is constructed via a count-sketch style embedding that produces effectively bins of data in each region of the input space. The dimensionality of the embedding can grow or shrink as part of the TRBO procedure, much like how in standard TRBO, the bounds of the space can change.
strengths_and_weaknesses: Originality: 
This approach is a pretty clever combination of TRBO and embedding based approaches for high dimensional Bayes Opt. However, it ends up being very building block based, which isn’t necessarily a bad thing.

Computing the success probability of the embedding and tying the primary idea back to well studied count sketch techniques does seem to be original to me.

Quality:

The experimental evaluation and ablation studies do seem to be performed of a reasonably high quality and the plots are quite easy to parse.

The one set of high dimensional BayesOpt benchmarks that is probably missed in the experimental evaluation is that of LaMCTS (Wang et al, ’20), which uses a classifier to construct the trust regions for TRBO. It might be too much to ask for a comparison using BaxUs inside, but it seems like a fair comparison to use against standard TRBO + LaMCTS. 

-	LaMCTS also has a slightly distinct and more interesting set of benchmarks which use MuJoCo environments, which are somewhat more interesting than simply adding dimensions into test problems like Branin.

Fig. 5 is very nice to see and seems to convincingly demonstrate that the Baxus embeddings perform better downstream than the HesBO embeddings, even inside of TRBO. 

Clarity:

It’s really nice that the probability of computing the optimum is computable for this approach, even if it’s a bit more complicated than the HesBO expression.

The plots and writing are overall easy to parse. 

However, the error bars and the marks (e.g. triangles) on the plots are confusing to me. What are they and what do they represent?

Significance:

Better methods for high dimensional black box optimization are definitely quite significant and core to the NeuriPS community. 

I would have liked to have seen a more challenging benchmark task, such as control of MuJoCo environments (see quality comment). 

References:

Wang, L., Fonseca, R., and Tian, Y. (2020). Learning search space partition for black-box
optimization using monte carlo tree search. In Advances in Neural Information Processing
Systems, volume 33.

questions: What kind of interpolations are used for the lines in Fig. 2? They seem to not be linear?

Is it possible to construct a situation where the Baxus embedding has either worse or the exact same success probability as HesBO? I know they converge in the limit but is there another situation where they can match?

Fig. 7: why is most of the improvement from BaxUs mostly at the beginning?

L763: what is a top hat prior?

Figs. 3 and 4: why do many of the Alebo and SAASBO evaluations seem to end early? Is this due to the increased cost of MCMC fitting? 

-	For example, Fig. 4 right: SAASBO seems to be cut at 100 evaluations rather than the 1000 evaluations fo the other methods. Also on hartmann500.

L260: \citet for [63]. 

L764: By ARD kernel, do you mean RBF ARD kernel or a Matern family?

L770: Why so many random restarts for the GP fitting? Is this done for the TRBO and/or SAASBO models as well?


limitations: Mostly yes. Negative societal impliations of BayesOpt (e.g. weapons or bioweapons design) could also be mentioned.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper considers Bayesian optimization for sparse, axis-aligned functions over high-dimensional spaces (hundreds of dims). The proposed solution creates a lower-dimensional space by sub-selecting dimensions from the original input space. The lower-dimensional space is searched with Thompson sampling and trust regions. The dimensionality of the lower-dimensional space is increased over the course of the proposed algorithm. The paper shows that the probability of containment of the function's optimum by the proposed algorithm's lower-dimensional space is no worse than a recent high-dimensional Bayesian optimization approach, also for sparse, axis-aligned functions (HESBO). Further, a total input evaluation budget is appropriately split among the sequence of nested lower-dimensional spaces. The paper provides results on high-dimensional datasets.
strengths_and_weaknesses: Originality

* The nested lower-dimensional spaces is a neat idea. I wish this direction was explored/pushed further in the paper.

Quality

* It wasn't obvious to me why REMBO was not included in the experimental comparison as it seems to be a natural competitor in this setting.

Clarity

* The setup and algorithm description are generally clear. Some of the choices described in the splitting strategy, fail tolerance control, and initial target dimension weren't immediately intuitive. I couldn't parse the extent to which these were necessary for the proposed algorithm's effectiveness over competitors.

Significance

* The general setting of high-dimensional black-box optimization is clearly important and effective general algorithms in this setting would be valuable for the community. The assumption of the function being axis-aligned is a strong one however.
questions: * Why is REMBO not included in the experimental comparison?

* What is random in the "random embedding" Alg 2?

* To what extent can the assumption of axis-aligned function be relaxed?
limitations: The paper does cover limitations and societal impacts to some degree in the paper.
review_title: null

Meta-review: metareview: New active-subspaces type approach for high dimensional blackbox optimization that works with a family of nested subspaces of increasing dimensionality, with some theoretical control over the failure risk. Overall well written and complete with convincing experiments that indicate better performance than popular approaches like CMA-ES/Random-search as well as several recent methods. Please consider reviewer feedback on clarity and presentation for the final set of revisions.
confidence: Certain
Decision: Accept