Bayesian optimization (BO) is a popular approach to optimize expensive-toevaluate black-box functions. A significant challenge in BO is to scale to highdimensional parameter spaces while retaining sample efficiency. A solution considered in previous literature is to embed the high-dimensional parameter space into a lower-dimensional manifold, often a random linear embedding. In this paper, we identify several crucial issues and misconceptions about the use of linear embeddings for BO. We thoroughly study and analyze the consequences of using linear embeddings and show that some of the design choices in current approaches adversely impact their performance. Based on this new theoretical understanding we propose ALEBO, a new algorithm for high-dimensional BO via linear embeddings that outperforms state-of-the-art methods on a range of problems, including learning a gait policy for robot locomotion.
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.