PaperlayerView exact revision on arXiv

Source-linked AI summary

Adaptive and Safe Bayesian Optimization in High Dimensions via One-Dimensional Subspaces

Johannes Kirschner, Mojmír Mutný, Nicole Hiller, Rasmus Ischebeck, Andreas Krause

arXiv:1902.03229v2cs.LGstat.ML

TL;DR

High-dimensional Bayesian optimization is hindered by intractable acquisition optimization, especially when tuning noisy, safety-critical systems. LineBO addresses this by solving sequential one-dimensional subproblems with a shared global model, achieving convergence guarantees and safe high-dimensional optimization, including SwissFEL deployment with up to 40 parameters.

  • Problem

    High-dimensional Bayesian optimization is difficult because acquisition optimization is a non-convex problem in the same search space, while practical applications may also impose safety constraints.

  • Method

    LineBO iteratively restricts Bayesian optimization to one-dimensional affine subspaces and can use SAFEOPT to solve each subproblem safely.

  • Results

    The method has global and fast local convergence guarantees, adapts to invariant effective dimensions, and enables safe SwissFEL optimization with up to 40 parameters.

  • Takeaways & Limitations

    LineBO provides a practical route to Bayesian optimization in high-dimensional continuous domains, including safe operation of the SwissFEL.

  • Takeaways & Limitations

    Safe convergence requires conditions such as a safe convex set or a safe convex improving level set, and global bounds still scale exponentially with effective dimension.

Abstract

from arXiv · show

Bayesian optimization is known to be difficult to scale to high dimensions, because the acquisition step requires solving a non-convex optimization problem in the same search space. In order to scale the method and keep its benefits, we propose an algorithm (LineBO) that restricts the problem to a sequence of iteratively chosen one-dimensional sub-problems that can be solved efficiently. We show that our algorithm converges globally and obtains a fast local rate when the function is strongly convex. Further, if the objective has an invariant subspace, our method automatically adapts to the effective dimension without changing the algorithm. When combined with the SafeOpt algorithm to solve the sub-problems, we obtain the first safe Bayesian optimization algorithm with theoretical guarantees applicable in high-dimensional settings. We evaluate our method on multiple synthetic benchmarks, where we obtain competitive performance. Further, we deploy our algorithm to optimize the beam intensity of the Swiss Free Electron Laser with up to 40 parameters while satisfying safe operation constraints.

1. Introduction

High-dimensional Bayesian optimization is motivated by costly, safety-critical parameter tuning, but acquisition optimization becomes intractable. LINEBO addresses this by solving sequential one-dimensional subproblems, with theoretical convergence, safety support, and SwissFEL evaluation.

  • Motivation: Free-electron-laser tuning involves 10-100 continuous parameters, recurrent drift, invariant subspaces, local optima, and safety constraints on electron losses.Measurements can be obtained in less than one second, making automated optimization feasible.
  • Motivation: Safety-critical constraints rule out many standard optimizers, while local penalty methods may become trapped in local optima.Bayesian optimization offers a principled global approach that can also operate under safety constraints.
  • Contribution: LINEBO decomposes high-dimensional Bayesian optimization into efficiently solvable one-dimensional subproblems and shares information through a global Gaussian-process model.The method uses subspaces containing the best point so far and supports safe subproblem solving with SAFEOPT.
  • Theory: Randomly chosen subspaces yield fast local convergence near strongly convex optima and global Lipschitz convergence that adapts to effective dimension.The contribution summary states these guarantees explicitly for the proposed algorithm.
  • Safety and evaluation: LINEBO combined with SAFEOPT provides a principled high-dimensional safe Bayesian optimization method, evaluated on synthetic benchmarks and SwissFEL with up to 40 parameters.The paper also reports slice plots for monitoring model fit and optimization progress.

2. Problem statement

The paper formulates noisy constrained optimization over a compact domain, requiring every evaluated iterate to satisfy safety constraints. Progress is measured by the simple regret of the proposed solution.

  • Formal setup: The objective f is minimized over a compact domain X ⊂ R^d, with implicit constraint functions g that may be vector-valued.Multiple constraints are allowed through a vector-valued constraint function.
  • Formal setup: Safety requires every optimization iterate x_t to satisfy g(x_t) ≤ 0.Both objective and constraint evaluations are noisy oracle observations.
  • Observation model: The noisy oracle returns y = f(x) + ϵ and s = g(x) + ϵ′, where the noise has sub-Gaussian tails.This model applies to both objective and constraint observations.
  • Evaluation: At stopping time T, the algorithm proposes a candidate solution x̂_T, which may differ from the point selected for the final optimization evaluation.The progress measure is simple regret relative to an optimal point.
  • Regularity assumptions: The objective and constraints are assumed to belong to reproducing kernel Hilbert spaces with known kernels and bounded norms.This assumption supports Gaussian-process estimation from the observed samples.

3. Line Bayesian Optimization

Standard Bayesian optimization becomes difficult in high dimensions because acquisition maximization is itself a non-convex problem. LINEBO restricts acquisition search to iteratively chosen one-dimensional affine subspaces, enabling efficient and safe subproblem optimization.

  • Bayesian optimization: Bayesian optimization uses Gaussian-process posteriors and acquisition functions to select evaluations that reduce uncertainty about the optimizer.The acquisition balances model predictions and uncertainty estimates.
  • Motivation: Maximizing the acquisition function requires solving a non-convex problem in the original search space, making standard Bayesian optimization intractable in high dimensions.This is the central computational problem addressed by LINEBO.
  • Line Bayesian Optimization: LINEBO restricts search to affine one-dimensional subspaces L(x,l) = {x + αl : α ∈ R} ∩ X, where x is an offset and l is a direction.The acquisition step can then be solved using an adaptive grid search.
  • Information sharing and directions: A global Gaussian-process model shares information across subproblems, while random directions provide the main analyzed choice and coordinate directions offer an alternative.The method is related to coordinate descent under coordinate-aligned directions.
  • Algorithm: Each iteration selects a direction, defines a subspace containing the previous best point, and runs Bayesian optimization on that subspace.Algorithm 1 initializes a Gaussian-process model and updates it after each subproblem.
  • Safe optimization: Restricting the domain makes SAFEOPT practical as a subsolver, yielding SAFELINEBO with safety guarantees for the global method.The paper identifies this as a principled approach to safe Bayesian optimization in high dimensions.

4. Convergence Analysis

LineBO combines one-dimensional Bayesian optimization subproblems with global, effective-dimension-adaptive, and local convergence guarantees, while SAFEOPT enables safety-constrained optimization under additional assumptions.

  • Global Convergence and Subspace Adaptation: Random directions make LineBO’s global convergence adapt to the function’s effective dimension without requiring that dimension to be known in advance.Invariant subspaces enlarge the near-optimal region, increasing the chance that random exploration encounters it.
  • Local Convergence: The global bound can still scale exponentially with effective dimension, but near a strongly convex local minimum LineBO converges at a fast local rate.Random directions provide descent in expectation through E[⟨∇f(x), l⟩²] = ||∇f(x)||²/d.
  • Sample Complexity of 1D Bayesian Optimization: For the squared exponential kernel, the high-dimensional regret bound has only polynomial dependence on dimension: r_T ≤ O(d^(3/2)√(log T/T)).
  • Convergence under safety constraints: SAFE LINEBO safely solves each one-dimensional subproblem with SAFEOPT, but sufficient exploration of the reachable safe set requires geometric conditions on the safe region.Convex safe sets support the needed line segments, whereas nonconvex examples such as U-shaped safe sets can defeat LINEBO despite SAFEOPT succeeding.

5. Practical Considerations

LineBO’s one-dimensional acquisition restriction supports practical heuristics, posterior-based acquisition functions, computational savings, and visual feedback, while global modeling retains information across subproblems.

  • Acquisition and direction choices: Restricting acquisition to one-dimensional subspaces enables acquisition functions such as Thompson sampling and Max Value Entropy Search that rely on posterior sampling.
  • Acquisition and direction choices: Random directions provide global and local guarantees, while coordinate-aligned or approximate descent directions can reduce variance or accelerate local convergence.Coordinate LINEBO was efficient on many benchmarks, likely because of reduced variance and objective symmetries.
  • Computational cost: On the 10-dimensional benchmark, restricting the acquisition space improved per-iteration computation time by roughly one order of magnitude versus full-scale Bayesian optimization methods.Figure 3 compares standard functions, a difficult 10d Gaussian, invariant-subspace variants, and computation time.
  • Global model: A global GP shares data across subproblems and can speed convergence, but its iterative update cost is quadratic in the number of observations.Independent sub-solvers or a fixed-size data buffer can provide further speedups without affecting the stated theoretical guarantees when subproblems are solved accurately.
  • User feedback: One-dimensional slice plots expose model predictions alongside evaluations, helping users monitor model fit and adjust GP hyperparameters.

6. Empirical Evaluation

The experiments evaluate LineBO methods on unconstrained and constrained synthetic benchmarks, then test DESCENTLINEBO and SAFELINEBO on SwissFEL. The methods are competitive or outperform baselines while handling high-dimensionality and safety constraints.

  • Synthetic benchmarks: The evaluation uses Camelback, Hartmann6, Gaussian, and augmented benchmarks with invariant subspaces, comparing LineBO methods against random search, Nelder-Mead, SPSA, CMAES, GP-UCB, REMBO, SAFEOPT, and SWARMSAFEOPT.Constrained experiments add an upper bound to the objective; experiments are repeated 100 times with standard-error confidence bars.
  • Synthetic benchmarks: LineBO methods achieve competitive unconstrained performance, while DESCENTLINEBO robustly approaches the optimum on the noisy Gaussian benchmark and outperforms GP-UCB and CMAES.DESCENTLINEBO is especially effective there because it uses estimated gradients as line directions.
  • Synthetic benchmarks: Roughly one order of magnitude speedup is obtained over full-scale Bayesian optimization methods in the 10-dimensional Hartmann6d+4d timing experiment.The comparison averages computation time per iteration over 500 steps, and the authors note that implementation affects the result.
  • Synthetic benchmarks: In constrained benchmarks, the authors report that their methods clearly outperform SAFEOPT and SWARMSAFEOPT in simple regret.SAFEOPT is not applicable to the high-dimensional benchmarks because it relies on a discretized domain.
  • SwissFEL: On SwissFEL, DESCENTLINEBO outperforms Nelder-Mead in convergence speed and final pulse energy, while SAFELINEBO maintains the safety constraint and reaches higher pulse energy than the previous expert setting after 600 steps.The 600-step result takes approximately 15 minutes, and a successful run uses 40 parameters.

7. Conclusion

The paper concludes that LineBO makes Bayesian optimization practical in high dimensions by decomposing acquisition into one-dimensional sub-problems. SafeLineBO extends this approach to safety-constrained optimization and is demonstrated on SwissFEL with up to 40 parameters.

  • Conclusion: LineBO decomposes Bayesian optimization into a sequence of one-dimensional sub-problems, addressing acquisition-function optimization and scaling to high-dimensional settings.The method is described as theoretically and practically effective.
  • Conclusion: Safety constraints are handled by safely solving each one-dimensional sub-problem, yielding what the authors identify as the first high-dimensional safe Bayesian optimization method with theoretical guarantees.The conclusion presents this as an extension of LineBO using SafeOpt.
  • Conclusion: SafeLineBO tunes SwissFEL pulse energy on a continuous domain with up to 40 parameters while satisfying safe operation constraints.The paper presents this as its practical deployment.
  • Conclusion: Bayesian optimization is implemented through an acquisition function over a Gaussian-process model, followed by observation, posterior updating, and candidate selection.The general algorithm iteratively chooses an evaluation point, observes a noisy outcome, updates the posterior, and proposes the best point.

A.1. Sample Complexity of Bayesian Optimization

This appendix reviews Bayesian-optimization sample-complexity control and SafeOpt’s confidence-based exploration. SafeOpt maintains a conservatively estimated safe set while balancing objective minimization, constraint exploration, and safe-set expansion.

  • Sample complexity: GP-UCB sample-complexity bounds ensure that Bayesian optimization eventually satisfies its stopping condition, yielding a simple-regret bound from confidence-based analysis.The analysis relates cumulative-information quantities to simple regret.
  • Sample complexity: Known information-gain bounds depend on the kernel, including γ_T ≤ O(d√T) for the linear kernel and γ_T ≤ O((log(T))^(d+1)) for the RBF kernel.The supplied passage also references bounds for Matérn kernels with ν > 1.
  • Safe Bayesian optimization: SafeOpt models the implicit constraint function with Gaussian-process confidence intervals and restricts acquisition to a conservatively estimated safe set.When confidence estimates hold, the algorithm does not violate the constraints.
  • Safe Bayesian optimization: Each SafeOpt iteration maintains a safe set, potential minimizers, and expanders that may enlarge the safe set, using uncertainty to guide acquisition.The procedure requires a domain, initial safe set, safety threshold, Lipschitz constant, and GP priors for the objective and constraint.
  • Safe Bayesian optimization: In one dimension, SafeOpt is particularly simple because the safe set is always an interval whose endpoints can serve as possible expanders.The original formulation requires knowledge of a Lipschitz constant, although it can be bounded from a function-norm assumption.

B.1. Global Convergence

The analysis establishes global convergence for random-line optimization and shows that local strong convexity yields linear convergence. Effective dimension improves the probability that sampled lines reach near-optimal regions.

  • Global convergence: After K iterations, Proposition 1 gives an accuracy-dependent global convergence guarantee with probability at least 1−δ.The guarantee combines the probability of intersecting the near-optimal set with the ε-accuracy of each line solve.
  • Global convergence: The probability that a random line intersects the near-optimal set is at least Ω(τ^(d_e−1)/2), when the objective varies in effective dimension d_e.The bound follows by approximating the objective near a minimizer with a quadratic sublevel set and restricting the approximation to the active subspace.
  • Random descent directions: Randomly chosen directions serve as descent directions for line-search updates under the stated moment conditions.The directions may be sampled uniformly from the unit sphere or from an orthonormal coordinate basis.
  • Local convergence: Under α-strong convexity and β-smoothness, exact random-direction line searches provide a descent inequality that supports linear local convergence.The local analysis assumes iterates remain within a region where the function is β-smooth and α-strongly convex.

C.1. Implementation Details

The implementation evaluates several baseline optimizers and uses a heuristic descent-direction oracle for DESCENTLINEBO. The oracle samples posterior functions, estimates gradients locally, and updates the Gaussian process model.

  • Baselines: The implementation compares against RANDOM, UCB, Nelder-Mead, SPSA, and CMAES using standard numerical-library implementations.UCB acquisition optimization uses L-BFGS with 50 restarts, while RANDOM reports the best uniformly sampled observation without noise control.
  • DESCENTLINEBO: DESCENTLINEBO uses step size α=0.1 and m=2d evaluations to select directions experimentally.The procedure is interpreted as Thompson sampling on a local Euclidean ball using a linearized posterior Gaussian process.
  • Descent direction oracle: The descent-direction oracle samples functions from the posterior, evaluates their gradients at the current point, and proposes local gradient steps.Each sampled point is observed and used to update the posterior before returning the gradient of its posterior mean.
Loading 1902.03229v2…