PaperlayerView exact revision on arXiv

Source-linked AI summary

High Dimensional Bayesian Optimisation and Bandits via Additive Models

Kirthevasan Kandasamy, Jeff Schneider, Barnabas Poczos

arXiv:1503.01673v3stat.MLcs.LG

TL;DR

High-dimensional GPB/BO is difficult because function estimation and acquisition optimisation become challenging, while prior approaches often impose restrictive low-dimensional structure. The paper uses additive models and Add-GP-UCB to address these issues, proving linear dependence of regret on D for additive functions and reporting empirical advantages across several tasks. Its practical scope is bounded by choices of additive component dimension and number, and the analysis includes a reported error under resolution.

  • Problem

    Scaling GPB/BO beyond low dimensions is difficult because statistical estimation and acquisition optimisation face high-dimensional challenges, while prior work often assumes low-dimensional subspaces.

  • Method

    The paper assumes an additive structure with lower-dimensional components and introduces Add-GP-UCB with an acquisition function designed for high-dimensional optimisation.

  • Results

    The regret bound has only linear dependence on D for additive functions, and experiments report that Add-GP-UCB outperforms naive BO on additive tasks and performs well on several non-additive examples.

  • Takeaways & Limitations

    The framework provides a direction for scaling GPB/BO to high dimensions while accounting for expensive evaluations and acquisition-optimisation costs.

  • Takeaways & Limitations

    Choosing additive component dimension d and number M remains an unresolved theoretical question, and the current analysis contains an acknowledged error.

Abstract

from arXiv · show

Bayesian Optimisation (BO) is a technique used in optimising a $D$-dimensional function which is typically expensive to evaluate. While there have been many successes for BO in low dimensions, scaling it to high dimensions has been notoriously difficult. Existing literature on the topic are under very restrictive settings. In this paper, we identify two key challenges in this endeavour. We tackle these challenges by assuming an additive structure for the function. This setting is substantially more expressive and contains a richer class of functions than previous work. We prove that, for additive functions the regret has only linear dependence on $D$ even though the function depends on all $D$ dimensions. We also demonstrate several other statistical and computational benefits in our framework. Via synthetic examples, a scientific simulation and a face detection problem we demonstrate that our method outperforms naive BO on additive functions and on several examples where the function is not additive.

1. Introduction

High-dimensional GPB/BO faces exponential statistical and computational challenges. The paper addresses them with an additive-function framework, proposing Add-GP-UCB, proving linear dimension dependence in regret, and demonstrating empirical gains.

  • GPB/BO has succeeded mainly below 10 dimensions, while expensive high-dimensional functions arise in vision, antenna design, astrophysics, and biology.
  • High-dimensional GPB/BO requires addressing exponential sample complexity in function estimation and exponential computation for acquisition optimisation.These are identified as the statistical and computational challenges limiting scalability.
  • The paper models f as an additive function of mutually exclusive lower-dimensional components.
  • Add-GP-UCB uses an acquisition function that is easy to optimise in high dimensions for additive-function optimisation and bandits.
  • Regret for additive f has only linear dependence on dimension D, despite f depending on all D dimensions.
  • Empirically, Add-GP-UCB outperforms naive BO on synthetic experiments, an astrophysical simulator, and face detection, and performs well on several non-additive examples.

2. Related Work

Related work largely addresses high-dimensional GPB/BO through low-dimensional subspaces, while additive models offer a broader alternative and practical benefits. The paper also highlights acquisition optimisation as a critical computational bottleneck.

  • Existing high-dimensional GPB/BO studies typically restrict variation to a very low-dimensional subspace, which can be too restrictive for functions varying across the entire domain.
  • The paper’s current analysis, specifically equation 14, contains a post-publication error that the authors are working to resolve.
  • Additive models can improve the estimation-error versus approximation-error trade-off when only a few samples are available, including when f is not additive.
  • Common acquisition maximisation methods, including grid search, Monte Carlo, multistart, and DiRect, require exponential computation in high dimensions.
  • The paper compares cumulative regret for GP-UCB and Add-GP-UCB under squared exponential and Matérn kernels.

3. Problem Statement & Set up

The setup considers noisy optimisation and bandits for high-dimensional functions under a known additive decomposition into disjoint, bounded-dimensional groups. Independent group GPs yield an additive kernel and enable acquisition optimisation group by group rather than over all D dimensions.

  • Problem formulation: The objective is to maximise a nonconvex function on [0,1]^D using noisy point queries, with simple regret for optimisation and cumulative regret for bandits.The model assumes y = f(x) + ϵ and defines regret relative to an optimum x∗.
  • Additive structure: The key assumption decomposes f into a sum of component functions over mutually exclusive coordinate groups.Each group has dimension d_j, and the paper focuses on d_j ≤ d ≪ D.
  • Additive structure: The theoretical analysis assumes the grouping is known, while a modified algorithm addresses unknown decompositions and non-additive functions.The paper distinguishes the main theoretical setting from broader algorithmic handling.
  • Gaussian-process model: Each component is modelled as an independent Gaussian process, inducing an additive covariance kernel for the full function.The resulting observation model adds Gaussian noise to the aggregate GP.
  • Gaussian-process model: A sum of at most dth-order kernels acts on smaller coordinate subsets and is statistically simpler than a Dth-order kernel acting on all variables.This structural simplification motivates the additive GP framework.
  • Computational considerations: Direct GP-UCB with an additive kernel still requires maximising an acquisition function in D dimensions, while sequential group optimisation is not anytime and can incur high bandit regret.Sequential optimisation also explores only M lower-dimensional hyperplanes and relies heavily on the additive assumption.

4. Algorithm

The Add-GP-UCB algorithm exploits additive structure by optimizing separate low-dimensional acquisition functions, while its analysis establishes favorable regret and information-gain dependence on dimension.

  • Algorithm: Add-GP-UCB obtains each component's posterior and maximizes a separate d-dimensional acquisition function before combining the resulting coordinates.This decomposes acquisition optimization across additive components rather than solving one D-dimensional problem.
  • Algorithm: O(M d+1 ζ−d) acquisition-function calls suffice for the decomposed optimization, instead of the exponential dependence associated with direct D-dimensional maximization.The decomposition requires solving at most M optimization problems over component domains.
  • Algorithm: The additive acquisition function has the same posterior-computation bottleneck as the standard acquisition, whose dominant cost is O(t3) matrix inversion.The paper states that this posterior overhead is only marginally larger for component posteriors and is offset by cheaper acquisition maximization.
  • Theoretical results: Maximizing the additive acquisition function achieves the same cumulative- and simple-regret rates as the standard acquisition when the kernel is additive.The result supports using the decomposed acquisition despite its differing form and maximizer.
  • Theoretical results: For additive kernels, information gain and regret have linear dependence on D, whereas a full Dth-order kernel yields exponential dependence on dimension.The information-gain bounds include additive squared-exponential and Matérn cases, with the exact rates stated in Theorem 4.
  • Practical considerations: Choosing lower-order kernels can represent richer function classes, but their acquisition functions remain D-dimensional; the paper therefore highlights computational optimization as a separate advantage.When the function is not additive, selecting component dimension d and count M involves a bias–variance and computational-budget trade-off that remains theoretically unresolved.

5. Experiments

Experiments compare Add-GP-UCB with GP-UCB, random querying, DiRect, GP-EI, and REMBO under constrained acquisition-optimisation budgets. Additive variants generally outperform GP-UCB, with performance depending on decomposition size, dimension, and whether the function is additive.

  • Experimental setup: Add-GP-UCB is compared with GP-UCB, random querying, and DiRect; real-data experiments additionally include GP-EI and REMBO.The acquisition function is maximised under a constrained computational budget.
  • Experimental setup: The experiments use 10 initial evaluations, 25 cycles, exploratory bandwidth 10^-5 for the first 25 iterations, and periodic marginal-likelihood optimisation.Synthetic comparisons also allocate 90% of the GP-UCB acquisition-optimisation budget to Add-d/M methods.
  • Synthetic experiments: In synthetic experiments, Add-⋆ performs best when it knows the correct decomposition and the component dimension d′ is small enough.For several configurations, however, smaller-d Add-d/M variants outperform Add-⋆ or GP-UCB.
  • Synthetic experiments: Add-1/10 performs poorly because its model is not statistically expressive enough to capture the true function.The experiments also report cases where large d′ makes estimation and acquisition optimisation difficult.
  • Synthetic experiments: For several synthetic configurations, almost all Add-d/M instantiations outperform GP-UCB, while large-d methods can perform worse than DiRect at large D.The authors attribute this large-D pattern to the budget available for maximising the acquisition function.

6. Conclusion

The paper recommends Add-GP-UCB with a known additive decomposition when component dimension is small, and otherwise advocates small groups with periodic decomposition optimisation. It presents the framework as promising for high-dimensional BO while identifying non-additive analysis and broader extensions as future work.

  • Recommendations: When the additive decomposition is known and d is small enough, Add-GP-UCB with that decomposition is likely to produce the best results.The practical choice of d depends on acquisition-optimisation budget, query budget, and the function itself.
  • Recommendations: When the decomposition is unknown, the paper recommends a small d and periodic partial optimisation of the decomposition.Values between 3 and 12 appeared reasonable in the experiments, subject to computational and query budgets.
  • Conclusion: The framework addresses computational constraints in acquisition optimisation and limited function evaluations without considerably compromising statistical integrity.The authors present this as a promising direction for scaling GP bandits and Bayesian optimisation to high dimensions.
  • Future work: Developing bias–variance and computational trade-off analyses for additive approximations of non-additive functions remains an open challenge.The authors also identify discrete settings, other acquisition functions, and more general decompositions as future extensions.
  • Scope of theory: The theory assumes a known decomposition, while the paper also presents a modified algorithm for unknown decompositions and non-additive functions.The theoretical analysis includes regret results for the additive setting and approximate acquisition maximisation.

A.2.1. OPTIMISE ONE GROUP AND PROCEED TO THE NEXT

The sequential group-optimization strategy allocates queries to one group at a time, but sacrifices anytime behavior, robustness to nonadditivity, and suitability for bandits. The proposed approach avoids these deficiencies.

  • Sequential group optimization: The strategy sequentially optimizes each coordinate group while holding all other coordinates fixed, using a predetermined query allocation.It searches only M d-dimensional subspaces of the full space.
  • Deficiencies: The strategy places too much faith in the additive assumption and requires the decomposition to be known initially.The proposed approach can instead learn a decomposition during optimization or find a reasonably good one.
  • Deficiencies: It is not an anytime algorithm because queries must be allocated across groups in advance.After moving to a new group, returning to improve an earlier group is not straightforward.
  • Deficiencies: It is unsuitable for bandits because instantaneous regret remains large until the final group is reached.The strategy cannot return to improve the best regret obtained for an earlier group.
  • Proposed approach: The authors state that their approach does not have these deficiencies.This claim addresses the sequential strategy’s anytime, decomposition, and bandit limitations.

A.2.2. ONLY CHANGE ONE GROUP PER QUERY

A rotating strategy changes only one group per query and cycles through groups, making acquisition optimization easier while incurring a regret penalty relative to the authors’ method.

  • Rotating updates: The strategy updates one group at a time, maximizing that group’s acquisition function while retaining previous values for the other groups.After M iterations, it cycles through the groups again.
  • Computational trade-off: Maximizing the acquisition function is easier, with cost O(ζ^-d), because optimization is performed over one group at a time.The stated cost reflects the d-dimensional group rather than the full space.
  • Regret trade-off: The rotating strategy has regret O(M√Dγ_T T log T), a factor M worse than the regret of the authors’ method.At each iteration it moves in d coordinates and waits M iterations before updating the entire point.

B. Proofs of Results in Section 4.3

This appendix section invokes established information-gain results for Gaussian processes, including a lemma and theorem under compact-domain and kernel assumptions.

  • Information-gain tools: The proofs use two information-gain results from Srinivas et al. (2010).The cited results provide the information-gain basis for subsequent bounds.
  • Information-gain tools: Theorem 8 bounds information gain for a compact domain and a d-dimensional kernel satisfying Assumption 2.It defines n_T = C_9 T^τ log T with C_9 = 4d + 2 and restricts T* to {1, ..., min(T, n_T)}.
  • Information-gain tools: The theorem expresses the bound using the tail sum B_κ(T*) = ∑_{s>T*} λ_s of the kernel eigenvalues.The eigenvalues are taken with respect to the uniform distribution over X.

B.1.1. PROOF OF THEOREM 4-1

The proof bounds information gain for additive squared-exponential kernels by exploiting the union of component-kernel eigenvalues and balancing two resulting terms.

  • Eigenvalue structure: The squared-exponential component eigenvalues satisfy a dimension-dependent decay bound used to control the information-gain series.The proof cites Seeger et al. (2008) for these eigenvalue bounds.
  • Eigenvalue structure: For additive kernels, the eigenvalues of the full kernel are the union of the eigenvalues of the individual component kernels because their eigenfunctions are orthogonal.The orthogonality follows from disjoint coordinate groups.
  • Series bounds: The proof bounds one series term using an integral and the substitution y = αx^(1/d), introducing the upper incomplete Gamma function.The Gamma-function identity and integral bound are applied in the final step.
  • Information-gain bound: The proof then applies Theorem 8 with τ = d and T* ≤ (M + 1)T+ to obtain a bound on γ_T.The parameter T+ is subsequently selected to balance the two terms.
  • Information-gain bound: The selected balancing parameter is T+ = 1/Tn_T, after which the first term is expanded in logarithmic factors involving Tn_T and rn_T.The displayed expansions include M(log(Tn_T))^d log(rn_T).
  • Information-gain bound: The proof notes that a constant has exponential dependence on d, while retaining terms involving d^d and (log T)^d.This dependence is treated as already present in the displayed terms.
  • Series bounds: The first series term dominates the second, so the proof chooses r = T to maximize the resulting bound.This choice follows the comparison between S_1 and S_2.

B.1.2. PROOF OF THEOREM 4-2

The proof derives information-gain bounds from kernel eigenvalue decay, optimizes the resulting auxiliary parameters, and establishes concentration over discretized additive groups while allowing approximate acquisition optimization.

  • Information-gain bounds: The information-gain bound is optimized over T+ ∈ {1, ..., min(T, nT)/M} by balancing the terms in its upper bound.The proof chooses T+ as a function of T and nT before optimizing the remaining expression.
  • Parameter optimization: The proof obtains r ∈ O(T/2d log(TnT)) by setting the derivative of a concave objective with respect to r to zero.This optimization supplies the stated order for the auxiliary discretization parameter.
  • Information-gain bounds: Kernel eigenvalue and eigenfunction bounds are taken relative to a base distribution, with the relevant distribution depending on the kernel and sampling scheme.The proof notes uniform-distribution bounds for the Matérn kernel and Gaussian-distribution bounds for the squared exponential kernel.
  • Approximate acquisition optimization: The analysis explicitly accommodates acquisition-function optimization within error, using ˜xt for the approximate maximizer and ζ0t^-1/2 for its suboptimality.The point chosen by Add-GP-UCB is treated as ζ0t^-1/2-optimal.
  • Discretization and concentration: The analysis constructs discretizations for each group, whose Cartesian product induces a discretization of the full domain.The resulting cardinality is ω = ∏j ωj, with ωm = maxj ωj.
  • Discretization and concentration: The proof combines Gaussian tail bounds, union bounds, and Lipschitz control to obtain simultaneous posterior-deviation guarantees over groups, discretizations, and time.The concentration argument applies union bounds over group points, discretizations, and all iterations.

B.2.1. PROOF OF THEOREM 5

The proof of Theorem 5 controls discretization and posterior errors, then combines these bounds with approximate acquisition optimization to derive high-probability instantaneous and cumulative regret bounds.

  • Discretization control: A grid with τt uniformly spaced points per coordinate provides a discretization whose L2 and L1 approximation errors decrease with τt.The proof uses the closest grid point [x]t and bounds ∥x − [x]t∥1 by p/τt.
  • Posterior concentration: Gaussian concentration and the discretization bound combine to control |f(x) − µt−1([x]t)| uniformly over x and t with probability greater than 1 − 2δ/3.The bound separates function discretization error from posterior deviation at the nearest discretized point.
  • Regret bounds: The instantaneous-regret bound holds with probability greater than 1 − δ for all t ≥ 1 after applying the approximate acquisition inequalities.The proof uses the approximate maximizer and the relation between its acquisition value and that of the selected point.
  • Regret bounds: The cumulative regret bound holds with probability greater than 1 − δ for all T ≥ 1, using summability of the first two terms in the instantaneous-regret bound.The constant C2 is specified for δ < 0.8.
Loading 1503.01673v3…