Abstract
Bayesian Optimization (BO) often struggles in high-dimensional spaces due to the exponential growth of the search volume. This work tackles this challenge by assuming an Orthogonal Projection Pursuit (OPP) structure, where the function is additive after an unknown rotation. We present a two-stage framework that estimates the function's Hessian through a specialized experimental design to recover the rotation, followed by additive bandit optimization. Our method achieves polynomial regret scaling with dimension and outperforms existing techniques on complex benchmarks.
Introduction
Bayesian Optimization is the gold standard for optimizing expensive black-box functions, such as hyperparameter tuning or robotic control. However, as the number of dimensions ($d$) increases, standard BO fails because the volume of the search space grows exponentially—a phenomenon known as the "curse of dimensionality."
To combat this, researchers often assume the function is additive, meaning it can be decomposed into a sum of independent functions for each dimension. However, this typically assumes the function is aligned with the original coordinate axes. If the function is additive but rotated (i.e., the important features are linear combinations of the input variables), standard additive models break down. Previous attempts to learn this rotation often relied on non-convex optimization that frequently stalled in local optima. This paper, presented at AAAI 2020, introduces a principled approach to optimize Orthogonal Projection Pursuit (OPP) models.
Methodology: A Two-Stage Framework
The authors introduce a two-stage approach to optimize OPP models, where $f(x) = \sum f_i([Rx]_i)$ for some unknown rotation matrix $R$.
Stage 1: Hessian Estimation via Experimental Design
The core insight is that for an additive function, the Hessian matrix (the matrix of second-order derivatives) is diagonal. If the function is rotated, the eigenvectors of the Hessian reveal that rotation. To estimate the Hessian under noise, the authors use a Hessian Stencil Design—a specific geometric pattern of points around a starting location. They derive novel concentration inequalities to balance the trade-off between local approximation error (sampling too far) and noise sensitivity (sampling too close).
Stage 2: Additive Bandit Optimization
Once the rotation $R$ is estimated, the input space is transformed (decorrelated). The problem is now a standard additive optimization task. The authors use Kernelized Thompson Sampling, which is statistically efficient for additive structures.
To handle the complexity of rotated box constraints during acquisition function optimization, the authors propose using Integer Linear Programming (ILP). This ensures the algorithm remains computationally tractable while deciding where to sample next.
Evaluation and Results
The authors evaluated their approach (OPPR Bandit) on synthetic benchmarks, such as rotated versions of the Michalewicz and Styblinski-Tang functions, and a real-world Electron Laser Simulator ($d=5$ and $d=10$).
- Superior Recovery: In synthetic tests, the OPPR Bandit successfully identified the underlying additive axes where standard BO and Sliced Inverse Regression (SIR) failed or converged to suboptimal points.
- Efficiency in High Dimensions: On the 10-dimensional Electron Laser Simulator, the OPPR Bandit reached higher reward values significantly faster than "Full Model" BO, which struggled with the dimensionality.
- Asymptotic Optimality: The authors proved that their simple regret bound scales polynomially with the dimension $d$, rather than exponentially, making high-dimensional BO practical.
Discussion and Future Work
Using the Hessian to find the rotation is a principled alternative to heuristic approaches like maximizing marginal likelihood. It transforms a non-convex optimization problem into a linear algebra problem (eigendecomposition). However, the method requires the eigenvalues of the Hessian at the starting point to be distinct; "flat" or perfectly symmetric regions can hinder rotation recovery. Additionally, the initial stage requires $O(d^2)$ samples, which may be a limitation for extremely small evaluation budgets. Future work may explore non-orthogonal projections and group-additive structures.
Summary updated