Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper proposes a new High-dim BO framework inspired by Block coordinate ascent. Although similar, this paper differs from other works which leverages a low dimensional structure assumption in that it utilizes all the dimension in the function space. Aside from the overall scheme, its other contributions include (1) an update scheme for the coordinate sampling distribution; (2) a heuristic stopping rule to balance between exploiting current coordinate block and exploring new coordinate blocks; and (3) a theoretical analysis that upper bounds the total regret on a surrogate loss function. The framework shows some promising results when compared with other high-dim BO works.
main_review: --Clarity
The paper is generally well written and easy to follow. I have some minor confusions:

1. In the algorithm, the posterior is described as p(\hat{f}| \hat{H}). Is the posterior specified by a GP with low dimensional kernel or high dimensional kernel, but the length-scales on inactive coordinates are frozen (not learned)?.

2. At the beginning of section 4.2, it was claimed that CobBO was compared to REMBO and ATPE but I don't see the comparison anywhere. Also, what would  BOHB be in Fig.5 ?

--Originality
The motivation behind doing BO along a subset of coordinates has been explored many times in the literature. This paper argues that the proposed method, CobBO, "efficiently leverages all the observations in the whole space ... rather than only relying on limited observations in each coordinate subspace". As far as I understand, DROPOUT [35] also re-selects the active coordinates at every iteration (and fill in the remaining coordinates using some heuristic strategy), which guarantees making use of all coordinates in the long run. However, I believe that the proposed subspace selection algorithm is more informed due to the update scheme of the sampling distribution.
--Quality
My main concern with this paper is that the theoretical analysis is not conventional (with respect to the BO literature). In my experience, BO regret analysis usually measures the regret on the objective function itself rather than a surrogate loss. It could be useful to assert that the sampling scheme will, in the asymptotic sense, always pick the right subspace to improve the objective the most number of times; but it does not inform us by how much does it improve the objective. It seems to me that the proposed regret bound is an analysis of the coordinate descent aspect alone, and is entirely independent of the optimization routine within each selected subspace (i.e., if I replace BO by something else, would anything change?). 

Please refer to the Significance subsection for my comments on the experiments.

--Significance
1. For some experiments (e.g., Levy 200D and Ackley 200D), I don't think all methods have converged by the end of 10000 iterations. It would probably take longer to conclude that one is clearly superior to another. 
2. I would suggest some ablation study to show the effect of having variable coordinate block size |C_t| (as I understand, it is now capped at 30). On average, how many coordinates are sampled per iterations? Is there a lower bound to prevent the scheme from selecting none? How does it affect performance if we increase/decrease the upper bound?
3. It was claimed that REMBO takes too long for Ackley 200D, but I dont see how it is the case if we limit the number of effective dimension (to be roughly the same as the average no. selected coordinates by CobBO)? Seems to me that both REMBO and CobBO optimize a low dimensional GP at every iteration with the same no. observations, so what makes one significantly slower than the other?


limitations_and_societal_impact: The authors have described the Broader impact of this paper, which I find reasonable. I believe there would be no potential negative societal impact.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors have proposed a new algorithm for black box optimization called CobBO. At a fundamental level, the algorithm is the extension of classic block coordinate ascent to black box optimization using techniques from Bayesian Optimization. The algorithm focuses on a small subset of coordinates in every iteration. In the first step, it uses a simple kernel to interpolate the values of the function learnt at other points to the points in the subspace. In the next step, it uses a full fledged BO with a more sophisticated kernel in the subset to learn the function in this subspace. It balances exploration and exploitation between subspaces by using a backoff stopping rule. The authors have supported their case by extensive empirical studies and some theoretical results.
main_review: Pros:
- The paper proposes an interesting algorithm to address the troubles that usually BO based methods face in high dimensional problems. While the basic concept of block coordinate ascent to address high dimensionality is already known and well studied, the authors apply this for BO and take care of several aspects to make it a practically usable algorithm.
- The empirical evaluation of the algorithm seems quite extensive.

Questions for the authors:
- The paper mentions that the scale of RBF is not tuned and is fixed before hand. I am curious as to how this choice affects the results. It is clear that one cannot set an arbitrary value as it might lead  to over smoothing or under smoothing. So is there a range where it works well and how is it chosen? Also how does this choice affect the results?
- While the algorithm is clearly set in the noiseless regime (which is fine), I am curious as to what will happen in the noisy regime? Clearly some of aspects cannot be directly taken over since we would not have access to exact function values. How robust do you expect the algorithm to be to noise in the current version (only allowing for noisy updates of posterior and no additional adaption) ? I am curious because typically one would expect noise in real world scenarios and if the algorithm is sensitive it can break under the noise.
- The description of Sec 3.1 and 3.2 is unclear. There are clarifying details in Appendix C, but overall I could not find one description of the algorithm where the choice of $C_t$ and the backoff is explicitly stated, as used in the experiments. If different versions outlined in Appendix C are used in different experiments, depending on the task, I don't think the comparison is fair since CobBO is allowed to make some changes depending on the function but others are not. I think it would be really helpful and clear if the stopping rule and choice of subspace is exactly mentioned in the main paper.
- Could you elaborate the intuition behind the description of the stopping rule outlined in Appendix C? It seems like too precise a definition without sufficient description as to how the specific form was obtained.
- Is the value $|C_t|$ chosen uniformly at random in $\{1,2, \dots, 30\}$? 
- In the ablation study, when only of one parameters is studied, what is the value of the other ones which are kept constant?
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper aims at making Bayesian optimization scalable to problems with large dimensional inputs. The authors propose an approach that selects block coordinates of the input space to explore at each iteration. The authors provide some theoretical results to support the proposed approach, and report experimental results to demonstrate that the proposed approach can achieve better performance than existing approaches.
main_review: Originality: 
The main idea of the proposed approach is to use the multiplicative weights update method in Bayesian optimization. To my limited knowledge about Bayesian optimization, this is novel and thus the originality is reasonable. 


Quality:
While the approach seems reasonable and the experimental results look promising, I have the following concerns about the paper. 

- The way they cite some of the existing works is not very precise, and thus I don't have a good impression of the quality of the work. For instance, [6] and [7] are the same book;  [26] on inverse distance weighting is Wikipedia; [32] and [33] are the same paper; [40] on Matern kernels is a webpage of scikit learn; [50] on radial basis functions is a webpage of scipy; [61] and [62] are the same paper; [64] and [65] are the same paper. 

- In lines 32-34, the authors say ``always exactly using the values on the queried points as the conditional events may mismatch the function’s local landscape by overemphasizing the approximation accuracy of the global landscape.'' Similar arguments are made in lines 43-48. I feel confused to see this argument. In GP regression, we usually assume noisy outputs, and the use of a regularized matrix inversion (where the regularizer is given by the noise variance) incorporates this assumption by automatically smoothing the outputs. 

- In line 57, the authors say ``CobBO uses the Automatic Relevance Determination (ARD) Matérn 5/2 kernel.'' But it is not clear how the authors specify the weights of this ARD kernel, as this is also not described in the supplementary. And the authors do not explain the value of the length scale parameter in the kernel. 

- In line 12 of Algorithm 1, there exists an RBF interpolation, denoted by $R$. The authors should describe the explicit from this interpolator. While the authors seem to explain that the RBF interpolation and GP regression are different, they are essentially the same approach. As such, RBF interpolation requires the computational complexity cubic to the data size. This point should also be discussed.

- In line 14 of Algorithm 1, $\Omega_t$ denotes the subspace spanned by the block coordinates $C_t$. I am wondering about how the authors specify the values for the coordinates in $\Omega_t$ not selected in $C_t$. For instance, suppose the dimensions are $D = 4$ and $C_t = \{1, 2\}$. Then is $x \in \Omega_t$ given in the form $x = (x_1, x_2, 0, 0)$ by specifying the coordinates not in $C_t$ (i.e,. \{3, 4\}) to be zeros? This point is not clear from the presentation. If this is the case, the authors implicitly make an assumption about the optimal solution that some of their coordinates are zero. This is rather a strong assumption.

- In Section 3.3, the authors define ``regret'' in terms of the selection of the best coordinate block. This regret is different from the regrets defined in terms of the global optimizer, usually analyzed in the Bayesian optimization literature. Therefore, the theoretical results of the paper do not really provide a theoretical guarantee for the proposed approach in terms of the convergence to the global optimizer.  

- While the authors show the hyperparameter settings in Table 2 of the supplementary, some information is still missing, such as the acquisition function used and the length scales of the kernels in RBF interpolation and GP regression. 


Clarity:
- Since the authors omit the concrete expressions for many mathematical concepts (e.g., RBF interpolation and the subspace $\Omega_t$), it is not very easy to deeply understand the mechanism of the proposed algorithm. Also, some key information for reproducing the experimental results is missing. 

Significance:
- There are many hyperparameters that need to be chosen in the proposed algorithm. (Table 2 in the supplementary shows an incomplete list of the hyperparameters.) If the performance of the proposed algorithm is sensitive to the choice of these parameters, the algorithm is not easy to be used by practitioners. This point is not clear from the paper. If this is the case, the significance of the proposed method is limited. 

- Also, as described above, it may be the case that the proposed approach implicitly assumes that some of the coordinates of the global optimizer are zeros. If this is the case, the proposed approach can only be applied to problems that satisfy this assumption, which may be restrictive.


------------ Post rebuttal --------------
As the authors made some clarifications, I have increased my score to 5. Still, however, I'm not very convinced by the argument of the authors on regret analysis.

limitations_and_societal_impact: The authors do not discuss the limitations of their work.
review_title: null

Meta-review: The paper studies high-dimensional Bayesian optimization, and adapts block coordinate ascent to the BO context, which seems to be practically useful as supported by extensive empirical evidence. However, after the discussion phase there remain concerns among the committee in the significance of technical contributions: (1) The theoretical analysis serves only as a justification of the algorithm, focusing mainly on the coordinate descent aspect, not directly on the BO regret, hence making the theoretical contribution incremental. (2) The basic idea of coordinate ascent with BO has been explored in literature. The paper is built on such insight and focuses on how to informatively choose a subspace; however, the technical strength is not strongly supported by the existing theoretical analysis/justification. (3) There are a few clarity concerns raised in the reviews, which suggest that the paper could benefit from a major revision to address the above concerns.
Decision: Reject