Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: This is a well-written paper and I enjoyed reading it. In summary the paper tries to address the following shortcomings of REMBO:

(1)	REMBO uses a random embedding to project a point in high dimensional space to a lower dimensional embedding space basing on the relation f(x) = f(Ay) with high probability, where x in D dimensions and y in d dimensions and d<<D. The problem of REMBO is that the relation f(x) = f(Ay) is only guaranteed with high probability and so, the embedding space may not contain an optimum. Second, When a point y  where Ay is outside the search space X, REMBO uses a projection to map Ay to its nearest point in X. This projection is not enough good. These observation are identified in paper of Binois et al (2018)as well.
(2)HESBO is an extension of REMBO that avoid above restrictions by proposing a new random projection. However, as the paper mentioned, HeSBO have a limitation is that the probability that the embedding will contain an optimum can be quite low! 
(3)Besides, the paper also identify a new observation that linear projections do not preserve product kernels. 

Then, the paper proposes a new solution of BO to overcome these restrictions by using a Mahalanobis kernel to avoid (3). This kernel is a replace of ARD Euclidean distance to a Mahalanobis distance. To avoid (1), the paper use equation 1 (please find in the paper). To avoid (2), they use the projection P_opt. In all , I think the theoretical contribution is good enough.

Having said that, I am a bit disappointed that this paper does not talk about LineBO (ICML 2019).  LineBO is a good solution for high dimensions without any assumption on structure like low effective dimensionality. It uses even one-dimensional subspaces to solve high dimensional problem with the strong theoretical guarantee. It do not need to learn subspace, and so it avoids disvantages (1), (2) and (3) that cause due to the fact that the embedding may not contain an optimum as mentioned above. Thus, LineBO is a stronger contender to the proposed algorithm. I will lift my rating if the author provide their response to this point.

Additionally, the author should compare their method to the algorithm of Binois et al (2018) that solved very well disadvantages of REMBO by setting bounds to avoid (1). Moreover, because the problem of the paper is high-dimensional Bayesian optimization under the assumption of low effective dimensionality, they should compare to other strong algorithms under the same assumption such as SI-BO algorithm( NIPS 2013) that used active learning to learn the low-dimensional subspace instead of using random embedding like REMBO.






review_title: Official Blind Review #2

final_score: rating: 1: Reject
review_content: This paper criticizes existing High Dimensional BO (HDBO) via linear embedding literature for the following reasons:

- Points in the embedded space projected mostly to the facet of the bounding box in the original space.
- The projection induces a distorted space which is not fit to be modeled by a GP.
- Linear projections do not preserve product kernels.
- Linear embeddings have low probability of containing an optimum.

The paper then proposes ALEBO which supposedly improves these aspects over other linear embedding BO techniques.

I have the following concerns regarding the authors' criticisms above:

1. What is wrong with the points being projected mostly to the facet of the original bounding box?
If I understand correctly, Theorem 3 of the REMBO paper proved that there exists y* \in R^{d_e} such that f(Ay*) = f(x*)
(i.e., the projected space contains the optimum) with high probability so to me, it does not really matter if the projection does not include the interior of the bounding box. Fig. 1 seems to make a point that most projections seem to indeed land on the facet of the bounding box (to be thorough, how many points did the authors sample to make this plot) but given what I said above, I do not think there is much of a point in Fig. 1 here. 

2. The authors claimed that it is not appropriate to model the distorted space with GP, but ended up using GP 
for ALEBO anyway (although with a different kernel). I understand that the authors did not project Ay back to B
like REMBO did, but the authors also gave me no reason to believe that this will improve things either. In fact, I think 
the authors should show the space induced by ALEBO embedding as a comparison. I suspect that with the imposed 
constraint -1 <= (B^T)y <= 1 the space will have discontinuous regions and is also not fit to be modeled 
with any GP. 

3. The authors stated that "A product kernel in the true subspace will not produce a product kernel in the embedding; 
we will see this more explicitly in Sec. 5.1" but I did not see it explicitly in Sec. 5.1. At the very
least, I do not see how REMBO fails to do the same thing. Also, the authors claimed that "Inside the embedding, 
moving along a single dimension will move across all dimensions of the true subspace, at rates depending 
on the angles between the embedding and the true subspace". This seems like a very qualitative claim.
Can the authors formally define what this statement means, and prove it or at least provide some backup citations?  

Other comments:

4. Why do the authors use conjugate transpose (if B^T means what i think it means) instead of normal transpose 
when B is drawn from R^{d_e \times d}? Shouldn't they be the same?

5. Please explain the choice of \Epsilon(B) = {x: B^T B x = x} 

6. The experiments provided are very limited. There is only one set of experiments showing performance of
ALEBO against other methods and it was done on a very small extrinsic dimension too (D = 100). I would like to see how 
ALEBO scales with truly large dimension (REMBO also claimed that it could scale up to much higher extrinsic dimension). What about other important properties like does it guarantee that an optimum lies in the constraint space? What about rotational invariance? There are so many elements missing from the analysis.

Overall conclusion:

This paper is largely empirical and lacks technical depth. It is not at all convincing that the problem it
addresses is real, much less important. It also does not offer strong empirical evidence (too few experiments). 
Given these reasons, I do not think the paper is not ready to be published as it is. 
review_title: Official Blind Review #1

final_score: rating: 3: Weak Reject
review_content: The authors investigate pitfalls common to random embedding-based approaches to high-dimensional Bayesian optimization (HDBO). Each of several practical shortcomings is separately analyzed and, subsequently, addressed in straightforward fashion:

  a. Large-scale distortions caused by clipping are handled by generalizing box constraints
     (in the embedded space) to the polytope corresponding to the set of points that project
     to the interior of the original search space.

  b. Local distortions caused by defining squared Euclidean distances in embedded spaces
     are handled by substitution for Mahalanobis distances.

  c. Embedded spaces potentially failing to contain optima are handled by constructing an
     estimator for the probability of this happening, which is then be used to pick better
     embeddings.


Feedback:
    To the extent that I enjoyed reading this piece, I am not sure that it warrants publication at this time. Specifically, the degree of novelty on offer seems minimal and the empirical results are underwhelming.

  1) Constraints on embedded candidate $\mathbf{y}$ are naively defined in terms of a polytope, but this formulation has previously been deemed impractical. If nothing else, it would be good to clarify this matter: why did preceding works chose not to explore this direction and/or how did you make it work here?

  2) Regarding use of Mahalanobis distances, evidence here (as provided in A.2) seems thin. Firstly, predictive MSE (Figure 6) seems like an odd choice of metric; log marginal probabilities would seemingly be more natural for GPs. Reporting of MSE is particularly suspect when results shown in Figure 7 indicate that the Mahalanobis distance based GPs are (markedly) overconfident. This issue is allegedly improved by marginalizing Mahalanobis parameters $\Gamma$; however, the appropriate baseline here would be ARD with marginalized lengthscales (which, to my knowledge, is not shown).

  3) Regarding ALEBO itself, Algorithm 1 states that acquisition functions were expressed in terms of an approximate posterior formed via moment matching against the Gaussian mixture formed by $m$ different samples of hyperparameters $\Gamma$?  One usually pushes this uncertainty through the acquisition function as, e.g., $\mathbb{E}_{\Gamma}[\alpha(\mathbf{x}; \Gamma)]$. What motivated this design choice?


Questions:
 - Does $\mathcal{B}$ need to be sampled or can it chosen to maximize $P_{opt}$?
 - Marginalization of hyperparameters
    - Did you jointly marginalize over all hyperparamerters or just Mahalanobis parameters $\Gamma$?
    - Why was a Laplace approximation used lieu of, e.g., slice sampling?

Nitpicks, Spelling, & Grammar:
  - Various figures: 'NewMethod' -> 'ALEBO'
  - Please report log immediate regret along with error bars
  - To the extent that testing on e.g. "high-dimensional" variants of Branin and Hartmann-6 is standard, it isn't particularly convincing.
review_title: Official Blind Review #3

Meta-review: This paper explores the practice of using lower-dimensional embeddings to perform Bayesian optimization on high dimensional problems.  The authors identify several issues with performing such an optimization on a lower-dimensional projection and propose solutions leading to better empirical performance of the optimization routine.  Overall the reviewers found the work well written and enjoyable.  However, the reviewers were concerned primarily about the connection to existing literature (R2) and the empirical analysis (R1, R3).  The authors claim that their method outperforms state-of-the-art on a range of problems but the reviewers did not feel there was sufficient empirical evidence to back up this claim. 
 Unfortunately, as such the paper is not quite ready for publication.  The authors claim to have significantly expanded the experiments in the response period, however, which will likely make it much stronger for a future submission.

Decision: Reject