Source-linked AI summary
Bayesian Optimization in a Billion Dimensions via Random Embeddings
Ziyu Wang, Frank Hutter, Masrour Zoghi, David Matheson, Nando de Freitas
TL;DR
Bayesian optimization struggles with high-dimensional domains because global coverage becomes difficult, motivating methods that exploit low intrinsic dimensionality. This paper introduces REMBO, which optimizes a random low-dimensional embedding and theoretically and empirically evaluates it. REMBO scales to extrinsic dimensions up to 1 billion and achieves state-of-the-art performance on 47 discrete solver parameters, provided intrinsic dimensionality is low.
Problem
Bayesian optimization is restricted to moderate-dimensional problems, motivating scalable methods for high-dimensional parameter spaces.
Method
REMBO draws a random embedding and performs Bayesian optimization in the resulting lower-dimensional space, projecting embedded points onto the feasible domain when necessary.
Results
REMBO is theoretically and empirically validated on extrinsic dimensions up to 1 billion and achieves state-of-the-art performance for optimizing 47 discrete parameters of a mixed integer linear programming solver.
Takeaways & Limitations
Random embeddings can make Bayesian optimization effective for extremely high-dimensional problems when the objective has low intrinsic dimensionality.
Takeaways & Limitations
REMBO’s demonstrated effectiveness depends on low intrinsic dimensionality, and one expensive application reported conclusive experiments only for d = 3.
Abstract
from arXiv · showhide
Bayesian optimization techniques have been successfully applied to robotics, planning, sensor placement, recommendation, advertising, intelligent user interfaces and automatic algorithm configuration. Despite these successes, the approach is restricted to problems of moderate dimension, and several workshops on Bayesian optimization have identified its scaling to high-dimensions as one of the holy grails of the field. In this paper, we introduce a novel random embedding idea to attack this problem. The resulting Random EMbedding Bayesian Optimization (REMBO) algorithm is very simple, has important invariance properties, and applies to domains with both categorical and continuous variables. We present a thorough theoretical analysis of REMBO. Empirical results confirm that REMBO can effectively solve problems with billions of dimensions, provided the intrinsic dimensionality is low. They also show that REMBO achieves state-of-the-art performance in optimizing the 47 discrete parameters of a popular mixed integer linear programming solver.
1. Introduction
Bayesian optimization is effective for expensive black-box objectives but has traditionally been limited to moderate dimensions because global coverage becomes exponentially costly. The paper addresses this challenge with random embeddings that exploit low effective dimensionality without requiring axis-aligned important dimensions.
- Motivation: Bayesian optimization targets expensive, derivative-free, non-convex black-box functions through sequential prior updating and function evaluation.The framework chooses queries using an acquisition function, evaluates the objective, and updates its prior with the new observation.
- Motivation: High-dimensional Bayesian optimization is difficult because ensuring coverage of the search domain requires exponentially more evaluations as dimensionality increases.The approach was typically restricted to problems of moderate dimension, often up to about 10.
- Low effective dimensionality: Low effective dimensionality means that most dimensions do not significantly change the objective, a property found in several machine-learning and algorithm-configuration problems.Random search was proposed as a way to exploit this structure without knowing which dimensions matter.
- Random embeddings: Random embeddings optimize a low-dimensional subspace that includes the optimizer even when the important dimension is unknown.For a two-dimensional example with one important dimension, the subspace x1 = x2 is guaranteed to include the optimum.
- Contribution: REMBO applies to any d-dimensional linear subspace rather than only axis-aligned intrinsic dimensions, enabling scaling to arbitrary D when intrinsic dimensionality is low.The paper expands this approach with theoretical analysis and applications involving very high-dimensional and mixed discrete optimization.
- Contribution: The paper reports that REMBO can solve problems with previously untenable extrinsic dimensions and achieve state-of-the-art performance on 47 discrete parameters of a mixed integer linear programming solver.The journal version also evaluates automatic configuration of random forest body-part classifiers.
2. Bayesian Optimization
Bayesian optimization models an unknown objective with a prior, typically a Gaussian process, and repeatedly selects evaluations using an acquisition function. The procedure balances exploiting high predicted values with exploring uncertain regions.
- Gaussian-process model: Gaussian processes provide a distribution over functions defined by a mean function and covariance kernel.The kernel encodes beliefs about objective smoothness, with the squared exponential as one possible choice.
- Gaussian-process model: Given observations, GP inference computes the posterior predictive mean and variance exactly for any candidate point.These quantities are obtained from the kernel covariance matrix and observed objective values.
- Acquisition function: At each iteration, Bayesian optimization recomputes the predictive mean and variance and uses them to construct the acquisition function.The paper reports results using expected improvement and also experimented with UCB, which produced similar results.
- Acquisition function: The acquisition function selects points by trading off exploitation of high predictive mean against exploration of high predictive variance.This balances evaluating promising regions with learning about poorly explored regions.
- Optimization loop: The Bayesian optimization loop initializes data, optimizes the acquisition function to choose a query, evaluates the objective, and updates model hyper-parameters.The query is selected by maximizing u(x|Dt) over the domain.
3. Random Embedding for Bayesian Optimization
REMBO reduces Bayesian optimization to a random low-dimensional embedding when the objective has low effective dimensionality, while preserving key invariances and handling box constraints through projection.
- Effective dimensionality: Effective dimensionality de means the objective is unchanged along a constant subspace T⊥, while varying only within an effective subspace T.The effective subspace T has dimension de, and de is the smallest integer with this property.
- Random embedding: With probability 1, a Gaussian random embedding A∈R^D×d with d≥de contains a point y representing every x∈R^D through f(x)=f(Ay).This allows optimization of g(y)=f(Ay) in d dimensions instead of optimizing directly in D dimensions.
- REMBO algorithm: REMBO first samples a random embedding and then applies Bayesian optimization in the embedded space, using acquisition-function optimization to select new points.The algorithm initializes data, optimizes the acquisition function over bounded Y, evaluates the objective, and updates kernel hyperparameters.
- Box constraints: For box-constrained domains, REMBO projects Ay onto X before evaluating f, so g(y)=f(pX(Ay)); bounded Y must be large enough to cover the effective subspace.Choosing Y too small can exclude the global optimizer, whereas larger regions make optimization more difficult.
- Theoretical guarantee: Theorem 3 guarantees, with probability at least 1−ϵ, an embedded optimizer under stated box and effective-subspace assumptions, with the required radius depending on de and ϵ.The theorem assumes X is centered at zero, the effective subspace is spanned by de basis vectors, and x⋆ lies in T∩X.
- Invariance properties: REMBO is invariant to adding unimportant dimensions and to rotations: corresponding runs yield identical function values or the same distribution of observed values.The addition-of-dimensions result uses the same d and bounded Y, while rotation invariance is stated for random Gaussian embeddings.
4. Experiments
REMBO is evaluated on synthetic high-dimensional functions, mixed-integer solver configuration, and random-forest classifier tuning. It remains effective when intrinsic dimensionality is low, while standard BO can be stronger when many dimensions are important.
- Synthetic experiments: REMBO performed well in D = 25 dimensions, where standard BO performed poorly and merely tied with random search.
- Synthetic experiments: REMBO’s performance was not affected by rotating the embedded Branin function, unlike the method of Chen et al. (2012).
- Synthetic experiments: REMBO performed just as well in D = 1 000 000 000 dimensions as in lower-dimensional settings for the same low-intrinsic-dimensionality benchmark.
- Mixed-integer solver configuration: REMBO exploited low effective dimensionality in the lpsolve problem, although the authors provided no theoretical guarantees for discrete optimization.
- Mixed-integer solver configuration: In lpsolve configuration, SMAC and vanilla REMBO performed best and significantly outperformed random search and standard BO.
- Random-forest classifier configuration: For random-forest classifier tuning, standard BO outperformed REMBO, but four interleaved REMBO runs nearly matched BO through about 450 function evaluations.
5. Conclusion
The paper demonstrates that random embeddings let REMBO handle extremely high extrinsic dimensions when intrinsic dimensionality is low, while retaining coordinate and rotational invariance. It also reports strong performance on a 47-parameter discrete optimization problem, but identifies broader applicability to other optimizers as future work.
- REMBO optimizes functions with extrinsic dimensionality up to 1 billion when their intrinsic dimensionality is low.The paper validates independence from D both theoretically and empirically.
- REMBO is coordinate independent and rotationally invariant, requiring only multiplication by a random matrix as a modification to Bayesian optimization.
- REMBO achieves state-of-the-art performance on the 47 discrete parameters of a popular mixed integer programming solver.
- Applying random embeddings to arbitrary optimization procedures remains a proposed direction for future work.The paper does not evaluate the technique beyond Bayesian optimization.
Appendix A. Proof of Theorem 2
The proof shows that a random embedding contains a representation of every point in the effective subspace almost surely. Because the function depends only on that subspace, the embedding can preserve function values.
- Decomposing any embedded point into effective-subspace and orthogonal components preserves the function value because f depends only on the effective component.
- Every point in the effective subspace can be represented by the projection of some embedded point Ay when the projected random matrix has full rank.
- A submatrix formed from d_e random columns has independent standard Gaussian projections onto the effective subspace.
- The projected Gaussian submatrix is nonsingular almost surely because singular matrices have Lebesgue measure zero under an absolutely continuous normal distribution.
Appendix B. Proof of Theorem 3
The proof projects an optimizer onto the effective subspace and uses the random embedding to represent that projection, with auxiliary matrix structure supporting the argument.
- Projecting the optimizer onto the effective subspace yields an optimizer under the box-constraint setting.
- With probability one, every point in the effective subspace has an embedded representative whose orthogonal projection equals that point.
- The proof represents the relevant projected embedding block using a random matrix B with independent standard Gaussian entries.
- The argument invokes a theorem on the random matrix block to complete the representation result.
Appendix C. Regret Bounds
The regret analysis studies a simplified REMBO variant under assumptions that align the embedded and effective dimensions and place the relevant maximum inside the searched region. It derives sublinear regret but acknowledges that complete guarantees for the implemented algorithm remain unresolved.
- Regret-analysis setting: The analyzed REMBO variant searches only inside the embedding’s intersection with the box X, unlike the implemented algorithm’s extension-and-projection procedure.
- Scope boundary: Complete analysis of the actual algorithm remains open because projection boundaries and kernels with flat dimensions require undeveloped theoretical tools.
- Definitions: The mathematical treatment defines simple regret, the skew squared exponential kernel, its RKHS, and canonical representations on effective subspaces.
- Regret result: The main result gives the analyzed REMBO variation simple regret of order O(t^-1/d) with high probability.
- Regret result: The theorem assumes the embedded dimension equals the effective dimension and that the restriction of f to its effective subspace belongs to an RKHS for a positive-definite skew kernel.
- Scope boundary: The theorem provides regret relative to all of X only when the embedding intersects the function’s maximum locus inside X.
Appendix D. Proof of Theorem 11
The proof constructs the kernel induced by the random embedding and shows that it is sufficiently well-behaved to support convergence of Expected Improvement.
- Proof strategy: The proof first derives an analytic expression for the true low-dimensional kernel, then establishes eigenvalue bounds before applying Expected Improvement convergence results.These are the two stated parts of the proof.
- Kernel construction: The projection Π maps the high-dimensional space onto the effective subspace, while pull-backs define kernels over the original and embedded domains.The construction uses kD := Π∗k∆ and the pull-back A∗f in the embedded space.
- Random-matrix argument: Orthogonal transformations preserve the distribution of Gaussian matrices, and left multiplication by S selects the first d rows while retaining Gaussian entries.This rotational invariance supports the random-matrix decomposition used in the proof.
- Kernel regularity: The induced matrix ∆d is full rank and positive definite almost surely, allowing the proof to replace the true kernel with a thinner kernel kℓ.The replacement preserves enough RKHS approximation power for REMBO and makes the convergence proposition applicable.
- Convergence: With finite Hℓ(Rd) norm established, Expected Improvement can be applied on A−1(X) using kℓ, yielding the stated simple-regret convergence bound.The argument transfers the function into the RKHS associated with the usable kernel before invoking Proposition 17.