Experimental Design for Optimization of Orthogonal Projection Pursuit Models

Mojmir Mutny, Johannes Kirschner, Andreas Krause

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).

The two-stage optimization process: (a) selecting an initial point $x_0$ and (b) performing experimental design to estimate the Hessian.

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.

(a) The Hessian Stencil geometry used for sampling. (b) Comparison of rotation estimation methods against the true additive axes.

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

Abstract

Bayesian optimization and kernelized bandit algorithms are widely used techniques for sequential black box function optimization with applications in parameter tuning, control, robotics among many others. To be effective in high dimensional settings, previous approaches make additional assumptions, for example on low-dimensional subspaces or an additive structure. In this work, we go beyond the additivity assumption and use an orthogonal projection pursuit regression model, which strictly generalizes additive models. We present a two-stage algorithm motivated by experimental design to first decorrelate the additive components. Subsequently, the bandit optimization benefits from the statistically efficient additive model. Our method provably decorrelates the fully additive model and achieves optimal sublinear simple regret in terms of the number of function evaluations. To prove the rotation recovery, we derive novel concentration inequalities for linear regression on subspaces. In addition, we specifically address the issue of acquisition function optimization and present two domain dependent efficient algorithms. We validate the algorithm numerically on synthetic as well as real-world optimization problems.
BibTeX
@inproceedings{mutny2020experimental,
  author = {Mojmir Mutny and Johannes Kirschner and Andreas Krause},
  title = {{Experimental Design for Optimization of Orthogonal Projection Pursuit Models}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i06.6585},
}
Figure