High-Dimensional Bayesian Optimization via Additive Models with Overlapping Groups

1 Introduction

• Scaling Bayesian optimization to high-dimensional inputs remains an open challenge, with structure identification and efficient acquisition optimization posing interrelated demands.Richer structural assumptions can make acquisition functions harder to optimize.Source: §1 · p. 1

1.1 Related Work

• Kandasamy et al. [19] model the target as a sum of low-dimensional functions on fixed variable subsets, but require those subsets to be disjoint.That constraint simplifies acquisition optimization while restricting the function class.Source: §1.1 · p. 1

1.2 Contributions

• The paper generalizes the additive model of [19] to groups that may overlap, expanding the functions it can represent.Source: §1.2 · p. 2
• A graph represents interactions between groups, enabling a high-dimensional GP-UCB variant that optimizes its acquisition function by message passing.Source: §1.2 · p. 2
• A Gibbs sampling algorithm learns the dependency graph from data while addressing challenges introduced by overlapping groups.The approach is described as having a similar flavor to that of [21].Source: §1.2 · p. 2
• The paper reports experiments on synthetic and real datasets and extends aspects of the mathematical analysis toward possible regret bounds.Source: §1.2 · p. 2

• The target function is decomposed into a sum of low-dimensional components, each defined on a subset of the input variables.The input domain is discrete, with each variable taking values in a finite set.Source: §2 · p. 2
• Unlike the disjoint-group assumption in [19], the model permits arbitrary overlap among variable groups, allowing a richer class suited to interacting groups.Source: §2 · p. 2
• Each component is an independent Gaussian-process sample, so the overall target is also a Gaussian process.Source: §2 · p. 2
• A dependency graph connects variables that appear together in a group, and each low-dimensional function can correspond to a maximal clique.Different decompositions can yield the same graph; using a single function for a maximal clique avoids loss of generality.Source: §2 · pp. 2–3, Figure 1 · p. 3

3.1 Description of algorithm

• The global acquisition function sums low-dimensional UCB functions, each using the exploration parameter β_t.Source: §3.1 · p. 3
• G-Add-GP-UCB updates the posterior, maximizes the acquisition function, and evaluates the selected point in each iteration; the described algorithm assumes the kernel and dependency graph are known.Source: §3.1 · p. 3

3.2 Maximizing the acquisition function

• For a triangulated dependency graph, junction-tree message passing maximizes clique acquisition functions from leaves to root and returns the global maximum.Messages pass optimized values over variables shared with the parent clique.Source: §3.2 · p. 3
• For an arbitrary graph, the method triangulates it, constructs a junction tree, and adjusts clique acquisition functions before applying message passing.The optimization complexity is exponential in the largest clique of the triangulated graph and depends on the chosen triangulation.Source: §3.2 · pp. 3–4

• The dependency graph determines the kernel decomposition, so the method jointly learns graph structure and kernel parameters under a fixed number of kernel parameters independent of the decomposition.The resulting parameter set includes binary edge variables and kernel parameters.Source: §4 · p. 4
• The learning objective is to maximize the data likelihood under a candidate graph and kernel parameters.The likelihood is defined using the kernel matrix induced by those choices.Source: §4 · p. 4
• Gibbs sampling approximates draws from the joint posterior by sampling one parameter conditional at a time, then selecting the sampled set with highest data likelihood.Source: §4 · p. 4
• Graph edges are modeled as Bernoulli variables, with their prior probability controlling graph sparsity or set to 1/2 when prior information is unavailable.Source: §4 · p. 5
• The procedure stops after a chosen number of likelihood evaluations and is repeated during optimization every N_cyc iterations, restarting from the previously learned parameters.Source: §4 · p. 5

5 Experiments

• Synthetic comparisons include learned Overlap, disjoint No Overlap, and a known-graph Oracle; the face experiment fixes neighboring-stage dependencies instead of learning its graph.Source: §5.1 · pp. 5–6, §5.2 · p. 7

5.1 Experiments on synthetic data

• As more data accrue, Overlap becomes more efficient than No Overlap, while Oracle is initially more efficient because it uses the true dependency graph.Source: §5.1 · p. 6
• Graph learning improves steadily; No Overlap saturates under its graph constraint, whereas Overlap converges to the true graph, and early correct separations alone can mislead when connections are few.Source: §5.1 · p. 6, Figure 5 · p. 7, Figure 6 · p. 8

5.2 Experiments on real data

• On face recognition, Overlap slightly outperforms No Overlap in convergence speed and optimal value; both beat OpenCV thresholds, and Overlap performs better on average cumulative regret.Source: Figure 7 · p. 8, §5.2 · p. 8

6 Conclusion

• The proposed model represents the target as a sum of possibly overlapping low-dimensional components, with an acquisition function of the same additive form maximized by message passing.A Gibbs sampling method learns the structure from samples; experiments observed improved optimization efficiency by expanding the modeled function space.Source: §6 · p. 8
• The paper does not discuss Bayesian optimization’s theoretical aspects in the main text; supplementary analysis includes information gain and discusses difficulties in obtaining regret bounds for G-Add-GP-UCB.The information-gain analysis is described as one step toward a regret bound.Source: §6 · p. 8
• For continuous variables, the method can discretize each variable, while combining message passing with continuous global optimization such as DiRect is proposed as a potentially more effective, non-trivial direction.Source: §6 · p. 8

Supplementary Material

• The supplementary material is identified as accompanying the AISTATS 2018 paper, and its citations refer to the main document’s reference list.Source: Supplementary Material · p. 11

A Derivation of posterior mean and variance

• The derivation establishes equation (4) for posterior mean and variance conditioned on observations, following the approach of Kandasamy et al. [19] and standard GP posterior derivations.Source: A Derivation of posterior mean and… · p. 11
• Instead of computing the high-dimensional function’s posterior directly, the derivation considers each additive component’s distribution at a query point given the noisy observations.It relies on the independence of distinct additive components given the input.Source: A Derivation of posterior mean and… · p. 11
• A standard conditional Gaussian formula yields the posterior mean and variance using the matrix Δ = κ(x, x) + η^2I_n.The derivation identifies this step with standard GP posterior derivations and the non-overlapping setting of [19].Source: A Derivation of posterior mean and… · p. 11

B.1 Discussion on existing theory

• For finite domains, Srinivas et al. provide a GP-UCB cumulative-regret guarantee involving information gain; analogous continuous-setting results and kernel-specific information-gain bounds are also reported.Source: §B.1 · pp. 11–12
• Kandasamy et al. [19] sought a regret bound with complexity exponential in the maximum component dimension rather than the full dimension, but later reported an error in the proof [36].Source: §B.1 · p. 12
• Hoang et al. [25] give a sufficient variance condition for sublinear regret, but identifying models and kernels satisfying it remains an open problem.The condition bounds each component’s posterior variance by a constant times the variance as if that component had been sampled directly.Source: §B.1 · p. 12
• The appendix gives a novel information-gain bound as one step toward a G-Add-GP-UCB regret bound, which remains future work because GP-UCB is computationally infeasible in high dimensions.Source: §B.1 · p. 12

B.2 Relation between true posterior variance and its approximation

• The posterior mean splits exactly across the lower-dimensional components, whereas the approximated posterior standard deviation generally differs from the true value.The variance mismatch arises from the nonlinear quadratic term in the posterior variance.Source: §B.2 · p. 12
• The split posterior standard deviation generally overestimates the true variance, and the inequality can be strict at an already evaluated point with zero noise.Source: §B.2 · p. 12
• The true posterior standard deviation can sometimes diverge, so it cannot be upper-bounded for all x.Source: §B.2 · p. 12
• Splitting posterior uncertainty into lower-dimensional components can produce values significantly different from the full-kernel posterior variance.The approximated and true standard deviations are correlated, but their ratio increases as true standard deviation decreases.Source: §B.2 · p. 13, Figure 8 · p. 14
• Approximation error depends on the decomposition: it is higher for larger M, the number of additive components.The comparison evaluates true and approximated posterior variances at 1,000 points after 200 random observations on a 10-dimensional synthetic function.Source: §B.2 · p. 13

B.3 Bounding the information gain with overlapping groups

• The information-gain result is only a step toward a regret bound for G-Add-GP-UCB; the paper does not establish such a bound.The appendix notes that GP-UCB itself is computationally infeasible in high dimensions.Source: §B.3 · p. 14
• Overlapping variables mean eigenfunctions from different kernels need not be orthogonal, so the proof uses Weyl’s inequality to bound the eigenvalue tail.Source: §B.3 · p. 14
• The proof incurs an extra M term in the bound on Bκ, but this does not change the information-gain bound because its leading term does not involve Bκ.Source: §B.3 · p. 15
• The information-gain bound has linear dependence on D and exponential dependence on the maximal group size d.The bound is for the squared exponential kernel and matches the form established for the non-overlapping setting.Source: §B.3 · pp. 14–15

C Astrophysical data experiment

• The experiment seeks nine cosmological parameters that maximize likelihood, equivalently minimizing negative log-likelihood, against observed data.Source: C Astrophysical data experiment · p. 15
• Overlap learns its dependency graph using Gibbs sampling, while No Overlap uses Gibbs sampling without the hard constraints of [19].The tested parameter range is 75%–125% of the software’s default set, whose negative log-likelihood is 23.7.Source: C Astrophysical data experiment · p. 15
• At the final iteration, the gap to random grows from approximately 0.09 to 0.15, an increase of over 60%.Across the full time horizon, Overlap achieves a higher likelihood than No Overlap; both beat the default parameters.Source: C Astrophysical data experiment · p. 15, Figure 9 · p. 16
• Figure 9’s vertical axis indicates that lower values mean the chosen constants are more likely to match the observed data.Source: Figure 9 · p. 16