Recently,I am studying the paper of Gaussian Process Optimization in the Bandit Setting, Srinivas. In theorem 3, they state:

Let $\delta\in(0,1)$. Assume that the true underlying f lies in the RKHS $\mathcal{H}_k(D)$ corresponding to the kernel $k(x,x^\prime)$, and that the noise $\epsilon_t$ has zero mean conditioned on the history and is bounded by $\sigma$ almost surely. In particular, assume $||f||^2_k\leq B$ and let $\beta_t=2B+300\gamma_tlog^3(\frac{t}{\delta})$. Running GP-UCB with $\beta_t$, prior $GP(0,k(x,x^\prime))$ and noise model N(0,$\sigma^2$), we obtain a regret bound of $O^*(\sqrt{T}(B\sqrt{\gamma_T}+\gamma_T))$ with probability $$Pr(R_T\leq\sqrt{C_1T\beta_T\gamma_T} \ \ \ \forall T\geq 1 )\geq 1-\delta\ \ \ where \ C_1=\frac{8}{log(1+\sigma^{-2})}$$

I have follwing interpretation of the theorem:

  1. Since the regret grows slower than T, the algorithm will converge to optimum eventually.
  2. It holds for function lies in the corresponding RKHS space. So we need to check the condition to show that the function indeed lies in it.

However, we use Bayesian Optimization for black-box function optimization, we can't actually check the condition. Hopefully, If we use BO to tune hyper-parameters of machine learning models, the function will be at least piece-wise continuous.

If I use a universal kernel at the begining (function in corresponding RKHS will be dense in continuous function with compact domian in sup norm), can we directly generalize the theorem to any piece-wise continuous function?

Also, In practice, we actually reset the kernel parameters using MCMC or maximum likelihood in each run and the acquisition function may not be convex so we can't really find the best point to evaluate in practice. How would this practical issue affects

  1. The convergence and regret.

  2. Why we retrain the kernel parameters after observing a new sample at each query, does it theoretically proved to be a better prior or just a heuristic?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.