PaperlayerView exact revision on arXiv

Source-linked AI summary

Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization

Jonathan Scarlett, Ilijia Bogunovic, Volkan Cevher

arXiv:1706.00090v3stat.MLcs.ITcs.LGmath.IT

TL;DR

Noisy Gaussian process bandit optimization lacks algorithm-independent regret lower bounds that clarify how much existing upper bounds can improve. This paper derives such bounds for simple and cumulative regret in the non-Bayesian setting, finding near agreement for squared-exponential kernels and larger gaps for Matérn kernels.

  • Problem

    Algorithm-independent regret lower bounds for noisy Gaussian process bandit optimization were not known, leaving unclear how far existing upper bounds could be improved.

    Source: §I · p. 1

  • Method

    The paper derives algorithm-independent lower bounds for simple and cumulative regret in the non-Bayesian setting for squared-exponential and Matérn kernels.

    Source: §I · p. 2, §II · pp. 3–4

  • Results

    The lower bounds nearly match existing upper bounds for the squared-exponential kernel, while the gaps are more significant for the Matérn kernel.

    Source: §I · p. 2, §VI · p. 18

  • Takeaways & Limitations

    The Matérn bounds and existing algorithms warrant further study, whereas the squared-exponential lower bounds are already close to known upper bounds.

    Source: §I · p. 2, §VI · p. 18

    The analysis focuses on the non-Bayesian setting and the squared-exponential and Matérn kernels.

    Source: §I · p. 2

Abstract

from arXiv · show

In this paper, we consider the problem of sequentially optimizing a black-box function $f$ based on noisy samples and bandit feedback. We assume that $f$ is smooth in the sense of having a bounded norm in some reproducing kernel Hilbert space (RKHS), yielding a commonly-considered non-Bayesian form of Gaussian process bandit optimization. We provide algorithm-independent lower bounds on the simple regret, measuring the suboptimality of a single point reported after $T$ rounds, and on the cumulative regret, measuring the sum of regrets over the $T$ chosen points. For the isotropic squared-exponential kernel in $d$ dimensions, we find that an average simple regret of $\epsilon$ requires $T = \Omega\big(\frac{1}{\epsilon^2} (\log\frac{1}{\epsilon})^{d/2}\big)$, and the average cumulative regret is at least $\Omega\big( \sqrt{T(\log T)^{d/2}} \big)$, thus matching existing upper bounds up to the replacement of $d/2$ by $2d+O(1)$ in both cases. For the Mat\'ern-$\nu$ kernel, we give analogous bounds of the form $\Omega\big( (\frac{1}{\epsilon})^{2+d/\nu}\big)$ and $\Omega\big( T^{\frac{\nu + d}{2\nu + d}} \big)$, and discuss the resulting gaps to the existing upper bounds.

I. INTRODUCTION

The paper studies noisy, non-Bayesian Gaussian process bandit optimization under bounded-RKHS-norm smoothness and establishes algorithm-independent lower bounds for simple and cumulative regret. These bounds nearly match existing upper bounds for the squared-exponential kernel, while the gaps are larger for the Matérn kernel.

I. INTRODUCTION

  • Earlier work provided algorithm-specific upper bounds, but algorithm-independent lower bounds for noisy regret were absent, leaving the scope for improvement unclear.The paper focuses on the non-Bayesian setting and the squared-exponential and Matérn kernels.Source: §I · pp. 1–2

A. Setup

  • The setting optimizes a fixed function on [0, 1]^d with bounded RKHS norm and independent Gaussian observation noise.Simple regret concerns the single point reported after T rounds; cumulative regret sums regret over the T selected points.Source: §I · p. 1, A. Setup · p. 2

B. Related Work

  • The analysis uses frequency-domain compactly supported functions to address the squared-exponential kernel, whose RKHS excludes the compactly supported functions used in prior noiseless work [7].The noisy setting and cumulative regret also require addressing challenges not captured by that prior framework [7].Source: B. Related Work · pp. 2–3

II. MAIN RESULTS

  • The paper establishes lower bounds for average simple and cumulative regret in noisy non-Bayesian Gaussian process bandit optimization.The simple-regret result assumes εB is sufficiently small.Source: §II · pp. 3–4
  • For the squared-exponential kernel, the lower and upper bounds nearly match, differing in the exponent factor and hidden logarithmic factors.For Matérn, the gap to existing upper bounds is more significant.Source: §I · p. 2, §II · p. 5
  • Existing Matérn upper bounds may fail to be sublinear for some smoothness and dimension settings, which the authors identify as an open problem.The authors judge that sublinear regret should be possible for all ν and d, but this is not established by those bounds.Source: §II · p. 5
  • A conjectured improvement to the Matérn upper bound would make it sublinear for all d and ν and match the lower bound up to replacing d with d(d + 1).The authors state that they do not currently have a proof of the conjecture.Source: §II · p. 5
  • For squared-exponential cumulative regret, the lower bound depends linearly on σ up to logarithmic factors, while the optimal scaling with B remains unclear.For fixed T, d, and σ², the lower bound has (log B)^d dependence as B grows.Source: §II · p. 6

III. CONSTRUCTION OF A FINITE ENSEMBLE OF FUNCTIONS

The lower-bound analysis uses a finite ensemble of functions and relates average performance over that ensemble to a bound for at least one function. For simple regret, the ensemble is constructed so that achieving regret at most ϵ requires identifying its function index.

III. CONSTRUCTION OF A FINITE ENSEMBLE OF FUNCTIONS

  • A uniform finite ensemble lets the authors lower-bound an arbitrary algorithm’s regret averaged over functions, implying the same bound holds for at least one function.The argument averages over the ensemble index m and then selects a particular function f_m.Source: §III · p. 6
  • Each point is ϵ-optimal for at most one ensemble function, making simple regret at most ϵ equivalent to correctly identifying the function index.Source: §III · p. 6
  • For simple regret, ϵ is specified by the problem; for cumulative regret, the analysis can choose ϵ, and it assumes ϵB is sufficiently small.The authors state that this condition holds by assumption for Theorem 1 and must be checked for the choice used in Theorem 2.Source: §III · p. 6

A. Function Class

The function class uses shifted, localized peaks to create many alternatives that are difficult to distinguish from their locations. The peak width is chosen to respect the RKHS norm constraint.

A. Function Class

  • Each candidate function is a shifted and cropped copy of a localized function with peak value 2ϵ.The underlying function g has values in [−2ϵ, 2ϵ] and is constructed to fall below ϵ outside width w of its peak.Source: A. Function Class · pp. 6–7
  • The construction places peaks on a grid so that an ϵ-optimal point for one function is not ϵ-optimal for another.The number of alternatives is formed by placing shifted copies at grid locations separated by step size w.Source: A. Function Class · p. 6
  • A compactly supported, infinitely differentiable Fourier-domain bump H defines h by inverse Fourier transform, and h is scaled to form g.The scaling ensures the peak is 2ϵ; w is later chosen to meet the RKHS norm bound.Source: A. Function Class · p. 7

IV. BOUNDING THE RKHS NORM

The section bounds how many separated alternatives can satisfy the RKHS constraint. It relates RKHS norms to Fourier transforms and shows that, for the squared-exponential kernel, the constructed alternatives meet the required peak and separation properties.

IV. BOUNDING THE RKHS NORM

  • The construction seeks the largest number M of alternatives while keeping each RKHS norm at most B and preventing a point from being ϵ-optimal for multiple functions.The admissible width determines how many grid-separated functions can be used.Source: §IV · p. 7

A. Properties of RKHS Norms

  • For stationary kernels, the RKHS norm on R^d is expressed through the Fourier transform, and cropping to a compact domain cannot increase the norm.The section cites established RKHS properties for these relations.Source: A. Properties of RKHS Norms · p. 8

B. Squared Exponential Kernel

  • For the squared-exponential kernel, the Fourier transform is used to bound the constructed function’s RKHS norm and choose its width.The argument uses the scaling of the Fourier transform and a volume bound, with the required condition ensured for sufficiently small ϵB.Source: B. Squared Exponential Kernel · pp. 8–9
  • The resulting M functions have RKHS norm at most B, peak value 2ϵ, and pairwise incompatible ϵ-optimal points.The construction’s parameter choice also ensures the width condition for sufficiently small ϵB.Source: B. Squared Exponential Kernel · p. 9

C. Matérn Kernel

The Matérn analysis uses its Fourier transform and chooses the bump width to meet the RKHS constraint. It derives an analogue of the earlier construction under a stated condition on the width.

C. Matérn Kernel

  • The Matérn kernel has length-scale l and smoothness parameter ν, and its Fourier transform is considered as a function of τ = x − x′.Source: C. Matérn Kernel · p. 9
  • The width parameter is chosen to satisfy 2νw0^2l^2 ≤ 4π^2, a condition met when ϵB is sufficiently small.The derivation treats Γ(ν)l^(2ν) as constant for fixed d, l, and ν.Source: C. Matérn Kernel · pp. 9–10
  • The resulting Matérn construction is presented as an analogue of the earlier squared-exponential construction.The passage ties this analogue to the width choice w = ζw0.Source: C. Matérn Kernel · pp. 9–10

V. BOUNDING THE REGRET

The regret analysis fixes an arbitrary algorithm and compares its observation distributions across constructed functions and a zero function. Auxiliary bounds control the divergence and the total contribution of the shifted functions.

A. Auxiliary Lemmas and Definitions

  • For an arbitrary algorithm, the analysis compares observation distributions under each constructed function with those under the zero function.It also averages expectations and probabilities over a uniformly random function index.Source: A. Auxiliary Lemmas and Definitions · p. 11
  • The analysis introduces region-level maxima for function values and divergence to support the auxiliary bounds.Source: A. Auxiliary Lemmas and Definitions · pp. 11–12
  • The proof uses a chain-rule bound on divergence, limiting each round’s contribution by the maximum divergence for the region containing the selected point.The analysis tracks how many selected points fall in each region and defines the conditional observation distributions.Source: A. Auxiliary Lemmas and Definitions · pp. 11–12
  • The shifted functions’ values summed over the grid are dominated by the largest value, giving a total of O(ϵ).The proof uses decay of h, the inverse Fourier transform of an infinitely differentiable bump, to bound the sum.Source: A. Auxiliary Lemmas and Definitions · pp. 12–13

B. Completion of the Proof of Theorem 1

The proof bounds the recommended point’s average reward by averaging over regions and bounding the resulting terms. It then converts that reward bound into a lower bound on average simple regret.

B. Completion of the Proof of Theorem 1

  • Averaging over m gives a bound on the recommended point’s average reward, after which the proof bounds the two terms contributing to it.The derivation invokes Lemma 5, a divergence bound, Jensen’s inequality, and the fact that the region counts sum to T.Source: B. Completion of the Proof of Theorem 1 · p. 14
  • The proof combines its intermediate bounds before applying the kernel-specific choices of M for the squared-exponential and Matérn cases.The supplied passages identify these substitutions but do not include their explicit expressions.Source: B. Completion of the Proof of Theorem 1 · p. 15
  • The construction’s maximum value f(x*) = 2ε converts the average-reward bound into a lower bound on simple regret.The proof then uses the condition on the time horizon to conclude that average simple regret is at least ε.Source: B. Completion of the Proof of Theorem 1 · p. 15

C. Completion of the Proof of Theorem 2

The proof bounds average total reward and converts it into a cumulative-regret lower bound. It then chooses ε and substitutes the kernel-specific choices to obtain the stated bounds.

C. Completion of the Proof of Theorem 2

  • The construction’s maximum value f(x*) = 2ε converts the average-total-reward bound into a lower bound on cumulative regret.The proof obtains the average bound by averaging over m and combining bounds on two terms.Source: C. Completion of the Proof of Theorem 2 · p. 16
  • Choosing ε so the time-horizon condition nearly holds with equality yields a cumulative-regret lower bound of Tε.The proof checks that this choice is consistent with the kernel-dependent M before expressing the bound in terms of T.Source: C. Completion of the Proof of Theorem 2 · pp. 16–17
  • For the squared-exponential kernel, substituting its choice of M yields the lower bound identified as equation (5).The derivation uses the bounds on ε and assumes d = O(1).Source: C. Completion of the Proof of Theorem 2 · p. 17
  • For the Matérn kernel, substituting its choice of M yields the lower bound identified as equation (6).The proof states that the theorem’s assumption on σB ensures εB is sufficiently small.Source: C. Completion of the Proof of Theorem 2 · p. 17

D. High-Probability Regret Bounds

The paper adapts its average-regret lower bounds to hold with constant probability. It uses reverse Markov for simple regret and an analogous argument for cumulative regret.

D. High-Probability Regret Bounds

  • The section adapts the preceding proofs to obtain regret lower bounds holding with probability 1 − δ.The supplied passages detail the simple- and cumulative-regret arguments.Source: D. High-Probability Regret Bounds · pp. 17–18
  • For simple regret, the proof starts from E[r(T)] ≥ ε while every considered function has simple regret at most 4ε.Applying reverse Markov yields a lower bound of the same form for achieving a target simple regret with any constant probability above 3/4.Source: D. High-Probability Regret Bounds · pp. 17–18
  • The cumulative-regret argument similarly starts from an average lower bound of Tε and uses an upper bound of 4Tε on regret.The passage says this gives an analogous argument for the cumulative-regret bound.Source: D. High-Probability Regret Bounds · p. 18

VI. CONCLUSION

The paper gives noisy-setting lower bounds for non-Bayesian Gaussian process bandit optimization, covering simple and cumulative regret. The bounds nearly match existing upper bounds for the squared-exponential kernel, while the Matérn gaps are more significant.

VI. CONCLUSION

  • The paper’s lower bounds cover both simple and cumulative regret for noisy, non-Bayesian Gaussian process bandit optimization.The authors describe these as the first such bounds to their knowledge.Source: §VI · p. 18
  • The squared-exponential bounds nearly match existing upper bounds, whereas the Matérn gaps are more significant.Source: §VI · p. 18
  • Resolving the conjecture about γ_T versus γ_2T in existing upper bounds is a future direction that would close the squared-exponential gaps and narrow the Matérn gaps.Source: §VI · p. 18
  • The paper also identifies Bayesian lower and improved upper bounds as future work; its needle-in-a-haystack functions are extremely unlikely to be observed in that setting.The authors say this makes it reasonable to expect optimal scaling laws may be significantly milder than in the RKHS setting.Source: §VI · p. 18

APPENDIX

The appendix repeats a short proof from for completeness and identifies the justifications for steps (86)–(89).

APPENDIX

  • The appendix repeats a short proof from for completeness.Steps (86)–(87) use the assumption that a(y) ∈ [0, A], (88) uses a standard ℓ1-norm property, and (89) follows from Pinsker’s inequality.Source: APPENDIX · p. 18
Loading 1706.00090v3…