Source-linked AI summary
BOCK : Bayesian Optimization with Cylindrical Kernels
ChangYong Oh, Efstratios Gavves, Max Welling
TL;DR
Bayesian Optimization suffers from a boundary issue in high-dimensional search spaces, where evaluations concentrate near the boundary despite an expected center-near optimum. BOCK applies a cylindrical transformation to redistribute geometry, and experiments report improved accuracy, efficiency, and scalability up to 500 dimensions, including neural-network optimization.
Problem
High-dimensional Bayesian Optimization can bias evaluations toward the boundary because Gaussian-process uncertainty is higher there, conflicting with the assumption that optima lie near the center.
Method
BOCK transforms the ball-shaped search space into cylindrical geometry that expands central regions and contracts boundary regions for its Gaussian-process surrogate.
Results
BOCK is reported as more accurate, efficient, and scalable than state-of-the-art Bayesian Optimization alternatives, reaching 500 dimensions and optimizing neural-network layers and hyperparameters.
Takeaways & Limitations
BOCK enables Gaussian-process Bayesian Optimization on high-dimensional neural-network layers and stochastic-depth ResNets within the reported experiments.
Takeaways & Limitations
The cylindrical kernel can behave arbitrarily because it depends on an arbitrary fixed point, and the approach assumes the optimum lies near the search-space center.
Abstract
from arXiv · showhide
A major challenge in Bayesian Optimization is the boundary issue (Swersky, 2017) where an algorithm spends too many evaluations near the boundary of its search space. In this paper, we propose BOCK, Bayesian Optimization with Cylindrical Kernels, whose basic idea is to transform the ball geometry of the search space using a cylindrical transformation. Because of the transformed geometry, the Gaussian Process-based surrogate model spends less budget searching near the boundary, while concentrating its efforts relatively more near the center of the search region, where we expect the solution to be located. We evaluate BOCK extensively, showing that it is not only more accurate and efficient, but it also scales successfully to problems with a dimensionality as high as 500. We show that the better accuracy and scalability of BOCK even allows optimizing modestly sized neural network layers, as well as neural network hyperparameters.
1. Introduction
Bayesian Optimization can overallocate evaluations to the boundary of a high-dimensional search space, despite the assumption that solutions lie near the origin. BOCK addresses this by transforming the search-space geometry so optimization concentrates relatively more near the center.
- The boundary issue arises because Euclidean geometry creates excessive boundary volume and contradicts the prior that the solution lies near the origin.
- High-dimensional annuli grow exponentially with radius, so uniform sampling spends most evaluations near the boundary instead of the expected small-radius solution.
- BOCK maps the search-space ball to a cylinder, equalizing annular volume across radii and removing the entropic force toward the boundary.The method is called Bayesian Optimization with Cylindrical Kernel.
- BOCK successfully handles problems up to 500 dimensions, including modest neural-network layers with solutions competitive to SGD training.
2. Background
Bayesian Optimization combines a probabilistic surrogate, an acquisition function, and a defined search space to guide evaluations of black-box functions. In high dimensions, Gaussian Process uncertainty can bias evaluations toward the boundary, motivating BOCK’s cylindrical transformation of the search-space geometry.
- Bayesian Optimization iteratively uses an initial dataset, a surrogate model, and an acquisition function to select evaluation points within a defined search space.The surrogate predicts a mean and uncertainty, while the acquisition function uses both to quantify the significance of candidate points.
- The surrogate model probabilistically represents the objective through predictive mean and variance, with Gaussian Processes among the available modeling choices.Other possible surrogate models include random forests, tree-based models, and neural networks.
- The search-space definition provides a way to incorporate prior knowledge because it determines where optimal solutions are sought.
- High-dimensional Gaussian Process-based Bayesian Optimization tends to select boundary evaluations because uncertainty is higher near the boundary, where data points are sparse and separated.This boundary bias is identified as a serious challenge caused by the geometry of high-dimensional spaces.
- BOCK applies a cylindrical geometric transformation that expands volume near the search-space center and shrinks volume near its boundary.This differs from methods that rely on Euclidean search-space geometry.
3. Method
BOCK addresses the boundary issue by transforming the search space from ball geometry to cylindrical geometry, expanding central regions and contracting boundary regions. Its cylindrical kernel separates radial and angular similarity while avoiding dimensionality-dependent kernel complexity, with a special treatment for the origin.
- 3.2. Cylindrical transformation of search space: The cylindrical transformation separates each point into radial and angular components, expanding the center while contracting regions near the boundary.This geometric design targets a kernel that is non-stationary and represents central and boundary regions more evenly.
- 3.2. Cylindrical transformation of search space: BOCK defines a geodesic cylindrical kernel whose similarity decomposes into a one-dimensional radius kernel and an angular kernel.The angular component uses a continuous radial kernel on the hypersphere, whose parameter count is independent of the optimization dimensionality.
- 3.2. Cylindrical transformation of search space: Radius input warping uses a Kumaraswamy cumulative distribution function, with learned parameters and a Matern52 base kernel to focus similarity toward small radii.The radius warp is concave and non-decreasing, reinforcing the preference for areas near the center.
- 3.2. Cylindrical transformation of search space: BOCK transforms ball geometry into cylindrical geometry, redistributing volume from the boundary toward the center to reduce boundary-driven search bias.The transformation maps annuli to equal-volume cylindrical sections and is intended to counter the concentration of high-dimensional volume near the boundary.
- 3.2. Cylindrical transformation of search space: In cylindrical geometry, candidate predictive variances depend more on angular differences, making two candidates equally distant when Euclidean geometry would favor the near-boundary point.This changes the acquisition comparison by reducing the artificial preference for points near the boundary.
- 3.3. Balancing center over-expansion: The origin’s one-to-many mapping creates arbitrary kernel behavior, so BOCK sets its angular component from the test point to preserve smooth, positive-definite predictions.The resulting Gram matrix depends on the test point’s angular location when the origin is in the dataset, but the predictive mean and variance remain smooth.
4. Experiments
Across benchmark and neural-network experiments, BOCK achieves strong accuracy while improving efficiency and scalability in high-dimensional Bayesian optimization. Its performance is robust to design choices, and it remains effective for neural-network layers and hyperparameter optimization.
- Efficiency vs accuracy: BOCK is closest to the Rosenbrock optimum at favorable wall-clock efficiency, whereas Matern is slower and SMAC and AdditiveBO are faster but less accurate.The comparison uses the 20-dimensional Rosenbrock benchmark, whose optimum is at (0, 0).
- Scalability: BOCK is more computationally efficient than Spearmint and Matern and is less affected by increasing dimensionality.The authors attribute this partly to fewer kernel parameters and parameter counts independent of input dimensionality, with the transformed geometry possibly improving optimization dynamics.
- Robustness: Removing radius input warping slightly worsens minima, while adding further boundary treatment has only marginal effect.These robustness variants are evaluated on Rosenbrock; larger P tends to improve minima slightly but increases computational cost.
- Optimizing a neural network layer: BOCK outperforms Spearmint and Matern on neural-network-layer optimization and matches or exceeds Adam-based SGD in the 200- and 500-dimensional experiments.The experiment reports results across five runs, but directly optimizes test loss, so the resulting network is not optimal for generalization.
- Hyper-optimizing stochastic depth ResNets: BOCK improves validation accuracy while reducing expected depth when optimizing stochastic-depth ResNet death rates, although test-accuracy gains are only slight.The authors report that optimization is not directly equivalent to learning and that the network’s accuracy may be near its ceiling.
5. Conclusion
BOCK addresses Bayesian Optimization’s boundary issue by transforming ball geometry into a cylindrical geometry that emphasizes the search center. Extensive experiments report improved accuracy, efficiency, and scalability, including applications to neural-network layers and stochastic-depth ResNets.
- 5. Conclusion: BOCK transforms ball geometry into cylindrical geometry, expanding central volume and contracting boundary volume so optimization focuses less on boundaries.This targets both uneven evaluation allocation and the prior assumption that optimal solutions lie near the center.
- 5. Conclusion: BOCK is reported to be more accurate, efficient, and scalable than state-of-the-art Bayesian Optimization alternatives on standard benchmark functions.
- 5. Conclusion: BOCK optimized neural-network layers up to 500 dimensions, producing parameters better than Adam on the test set despite overfitting.
- 5. Conclusion: Hyper-optimizing stochastic-depth ResNet death rates produced smaller ResNets while maintaining accuracy.
- 5. Conclusion: The paper concludes that BOCK enables accurate, efficient, and scalable Gaussian Process-based Bayesian Optimization.
1. Special Treatment of the center point
The cylindrical kernel requires special handling at the center point because prediction-dependent Gram matrices create computational and positive-semidefiniteness concerns. The paper provides an efficient implementation and proves that the special treatment preserves a valid kernel.
- 1. Special Treatment of the center point: Because the cylindrical kernel is a tensor product of radius and angular kernels, proving both component kernels valid establishes validity of the combined kernel.
- 1. Special Treatment of the center point: The special treatment sets the angular component at a prediction point to a*=x*/∥x*∥, extending the kernel Gram matrix with that angle.It assumes x*≠0; experiments include the origin initially so acquisition need not evaluate it again.
- 1. Special Treatment of the center point: The center-point treatment can be viewed as using different Gaussian Processes at different prediction points while retaining continuity.
- 1. Special Treatment of the center point: Prediction-dependent Gram matrices make naive acquisition maximization infeasible, but block matrix inversion enables efficient quadratic-form computation.
- 1. Special Treatment of the center point: Cylindrical kernels remain positive semidefinite with the special treatment of the center point.The proof establishes this under the condition Ka(a,a)=η>0 for every angular component.
2. Implementation Detail
BOCK biases its radius-kernel prior toward central search regions using a concave, non-decreasing spike-and-slab prior. The prior places log(α) on the positive real line and log(β) on the negative real line.
- 2. Implementation Detail: BOCK uses a concave and non-decreasing prior for radius-kernel warping to focus optimization more on the center.
- 2. Implementation Detail: The radius-warping prior is implemented as a spike-and-slab prior.
- 2. Implementation Detail: The implementation places the spike-and-slab prior for log(α) on positive values and for log(β) on negative values.
3. Benchmark functions
The benchmark experiments use adjusted search spaces for Branin and Hartmann6 functions. The supplied passages specify the original domains for both functions.
- 3. Benchmark functions: The benchmark search space is adjusted to [−1, 1]^D in the experiments.
- 3. Benchmark functions: The original Branin search space is [−5, 10] × [0, 15].
- 3. Benchmark functions: The original Hartmann6 search space is [0, 1]^6.
4. Efficiency vs accuracy
Across the 20-dimensional benchmark functions, BOCK is closest to the optimum operating point, combining stronger accuracy with better efficiency than the compared methods.
- BOCK is closest to the optimum operating point (0, 0) across the 20-dimensional benchmark functions.Matern is also accurate enough but considerably slower, whereas SMAC and additive BO are faster but considerably less accurate.
- Matern trades efficiency for accuracy, while SMAC and additive BO trade accuracy for speed.
5. Scalability
Across the benchmark functions, BOCK remains more efficient and is less affected by increasing dimensionality from 20 to 100 dimensions.
- BOCK is clearly more efficient and less affected by increasing dimensionality across the 20- and 100-dimensional benchmark functions.
- The scalability evaluation compares wall-clock time at 20 and 100 dimensions using 200 and 600 function evaluations, respectively.The benchmark runs use five repetitions, with mean wall-clock time and one standard deviation reported.