Theoretical Analysis of Bayesian Optimisation with Unknown Gaussian Process Hyper-Parameters

• Estimating GP kernel hyper-parameters from few objective evaluations is difficult, and marginal-likelihood estimation can fall into traps.The introduction notes that integrating hyper-parameters out with quadrature or Monte Carlo does not prevent Bayesian optimisation from falling into traps.Source: §1 · p. 1
• Bull [6] provides the only known regret bound for unknown hyper-parameters, for deterministic objectives with maximum-likelihood estimation.Source: §1 · p. 1
• The paper extends this analysis to stochastic objectives with sub-Gaussian noise, including symmetric Gaussian, Bernoulli, or uniform noise.Source: §1 · p. 1

2 Bayesian optimisation

• Sequential Bayesian optimisation chooses evaluations of an unknown function to balance exploitation and exploration, especially when evaluations are costly or the function lacks an obvious representation.Source: §2 · p. 2

2.1 Bayesian optimisation with Gaussian processes

• A GP prior and observation model yield a posterior over the objective, with the kernel determining covariance and length-scale hyper-parameters.The section assumes sub-Gaussian observation noise and focuses on Gaussian noise for presentation.Source: §2 · p. 2, §2.1 · p. 2
• Expected improvement is a default acquisition choice, but noise in evaluating the incumbent makes the deterministic-optimization version brittle in stochastic settings.Source: §2.1 · p. 3

2.2 An algorithm inspired by the theory

• Theorem 1 gives sufficient conditions for EI with hyper-parameter estimation to have regret that vanishes as evaluations increase.Source: §2.2 · p. 3
• The theorem requires adapting hyper-parameters so an upper-bounded, narrower kernel has an RKHS containing the objective function.Source: §2.2 · p. 3
• Algorithm 1 lowers the upper bound on length scales when repeated samples have low posterior variance relative to noise, encouraging more exploration.The algorithm resets its counter after restricting the upper bound and selects subsequent hyper-parameters within the prescribed lower and upper bounds.Source: §2.2 · pp. 3–4
• In the trap simulation, slice-sampled EI can become overconfident and fail to converge, whereas Algorithm 1 can increase its confidence bounds and find the optimum.The same behavior as slice sampling was observed when maximum likelihood estimated the hyper-parameters.Source: §2.2 · pp. 4–5, Figure 1 · p. 5

3.1 Background: Regret

• Regret is the gap between the objective at the optimizer and the selected point; cumulative regret sums these gaps to assess convergence speed.The algorithm does not observe these regret measures directly.Source: §3.1 · p. 6

3.2 Background: Sub-Gaussian noise

• The analysis assumes independent σ-sub-Gaussian noise, which includes zero-mean Gaussian, symmetric Bernoulli, and symmetric uniform examples.For sub-Gaussian noise, the text states that the mean is zero and variance is at most σ².Source: §3.2 · p. 6

3.3 Background: Information gain

• Information gain measures uncertainty reduction about the function from observations, and maximal information gain after T rounds helps bound cumulative regret.For Gaussian distributions, the text notes a corresponding expression for information gain.Source: §3.3 · p. 6, §3.5 · p. 8

3.4 Background: Reproducing kernel Hilbert spaces

• The analysis formalizes smoothness by assuming the objective belongs to the RKHS induced by the kernel; for the considered kernels, RKHS elements can uniformly approximate continuous functions with compact support.The RKHS framework is also used in the proof of convergence behavior.Source: §3.4 · pp. 6–7

3.5 Main result

• With probability at least 1−δ, Theorem 1 bounds cumulative regret under bounded hyperparameters and RKHS membership, without requiring the explicit RKHS-norm knowledge required by GP-UCB.The theorem's assumptions also restrict the kernel family to conditions detailed in [6].Source: §3.5 · p. 7
• The proof bounds posterior-mean error using RKHS and concentration arguments, relates expected improvement to posterior uncertainty, then sums variance terms and bounds them through maximal information gain.The proof sketch identifies posterior-mean deviation and the analysis of expected improvement as its two challenges.Source: §3.5 · p. 8

4 Conclusion

• Only Bull [6] and this paper are identified as addressing convergence of GP-based Bayesian optimization with unknown hyperparameters.The authors qualify this as their knowledge of the literature.Source: §4 · p. 8
• Bull [6] focused on deterministic objective functions.Source: §4 · p. 8
• The paper's new results apply to noisy objective functions.Source: §4 · p. 8

A.1 Concentration

• A weighted sum of independent σ-sub-Gaussian variables is (∥λ∥σ)-sub-Gaussian.The result applies to ∑_{t=1}^T λ_tϵ_t.Source: §A.1 · p. 10
• The section abbreviates vectors of function values, observation noise, and observations as f_T, ϵ_T, and y_T.These denote values across the first T points or observations.Source: §A.1 · p. 10
• The representer theorem makes the stated optimization problem equivalent to one over functions represented by kernel evaluations at the observed points.The passage writes g(x) = λ^T k_θ,T(x).Source: §A.1 · p. 10
• Among functions agreeing with the observed function values, the function g has minimum norm.The passage says any other agreeing function has equal or larger norm.Source: §A.1 · p. 11

A.2 Supporting lemmas

• Information gain for the selected points can be expressed in terms of predictive variances.The passage identifies this as Lemma 5.Source: §A.2 · p. 12
• A bound in the section uses s² ≤ σ⁻² log(1+σ²) log(1+s²) together with Lemma 5.The inequality is stated immediately before the reference to Lemma 5.Source: §A.2 · pp. 12–13
• For f in H_θ(X), the stated inclusion places f in H_θ′(X) for every 0 < θ′ ≤ θ.The passage attributes the result to Lemma 4 of [6].Source: §A.2 · p. 13

A.3 Properties of the expected improvement acquisition function

• For z > 0, τ is non-decreasing and τ(z) ≤ 1 + z; for all z, τ(z) ≥ 0 and τ(z) ≥ z.The stated properties use τ′(z) = Φ(z) ∈ [0,1] and τ(z) = z + τ(−z).Source: §A.3 · p. 13
• The passage gives τ(0) = 1/√(2π) and uses this value to rewrite equation (33).The rewritten expression itself is not included in the passage.Source: §A.3 · p. 14
• The all-ones matrix J is rank one, with its only eigenvalue equal to the squared norm of the all-ones vector.The passage uses its eigen-decomposition to evaluate 1^T(J + σ²I)⁻¹1.Source: §A.3 · p. 14

A.4 Proof of main result

• The proof assumes a confidence bound on |μ_{t−1}(x, θ_t) − f(x)| after applying Proposition 1 and a union bound.The passage states the resulting probability as 1 − δ.Source: §A.4 · p. 15
• The proof defines the regret at round t before proceeding with its bound.The displayed regret expression is not present in the passage.Source: §A.4 · p. 15
• The proof invokes Lemma 7 and then applies the Cauchy–Schwarz inequality in its bounding steps.The passages do not include the resulting bound.Source: §A.4 · p. 16