# Multi-Scale Zero-Order Optimization of Smooth Functions in an RKHS

@article{Shekhar2020MultiScaleZO, title={Multi-Scale Zero-Order Optimization of Smooth Functions in an RKHS}, author={Shubhanshu Shekhar and Tara Javidi}, journal={ArXiv}, year={2020}, volume={abs/2005.04832} }

We aim to optimize a black-box function $f:\mathcal{X} \mapsto \mathbb{R}$ under the assumption that $f$ is Holder smooth and has bounded norm in the RKHS associated with a given kernel $K$. This problem is known to have an agnostic Gaussian Process (GP) bandit interpretation in which an appropriately constructed GP surrogate model with kernel $K$ is used to obtain an upper confidence bound (UCB) algorithm. In this paper, we propose a new algorithm (\texttt{LP-GP-UCB}) where the usual GP… Expand

#### 9 Citations

Improved Regret Bounds Agnostic GP Bandits Improved Regret Bounds for Agnostic Gaussian Process Bandits using Local Polynomial Estimators

- 2020

We consider the problem of optimizing a black-box function f : X 7→ R under the assumption that it has bounded norm in the Reproducing Kernel Hilbert Space (RKHS) associated with a given kernel K.… Expand

Optimal Order Simple Regret for Gaussian Process Bandits

- Computer Science, Mathematics
- ArXiv
- 2021

This work proves an Õ( √ γN/N) bound on the simple regret performance of a pure exploration algorithm that is significantly tighter than the existing bounds and is order optimal up to logarithmic factors for the cases where a lower bound on regret is known. Expand

Gaussian Process Bandit Optimization with Few Batches

- Computer Science, Mathematics
- ArXiv
- 2021

A batch algorithm inspired by batched finite-arm bandit algorithms is introduced, and it is shown that it achieves the cumulative regret upper bound O∗( √ TγT ) using O(log log T ) batches within time horizon T , where the O ∗(·) notation hides dimension-independent logarithmic factors and γT is the maximum information gain associated with the kernel. Expand

A Domain-Shrinking based Bayesian Optimization Algorithm with Order-Optimal Regret Performance

- Mathematics, Computer Science
- 2020

This is the first GP-based algorithm with an order-optimal regret guarantee and reduces computational complexity by a factor of O(T 2d−1) (where T is the time horizon and d the dimension of the function domain). Expand

On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization

- Computer Science, Mathematics
- ICML
- 2021

In this paper, we consider algorithm-independent lower bounds for the problem of black-box optimization of functions having a bounded norm is some Reproducing Kernel Hilbert Space (RKHS), which can… Expand

Ada-BKB: Scalable Gaussian Process Optimization on Continuous Domain by Adaptive Discretization

- Computer Science, Mathematics
- ArXiv
- 2021

Ada-BKB (Adaptive Budgeted Kernelized Bandit), a no-regret Gaussian process optimization algorithm for functions on continuous domains, that provably runs in O(T deff), where deff is the effective dimension of the explored space, and which is typically much smaller than T . Expand

Lenient Regret and Good-Action Identification in Gaussian Process Bandits

- Computer Science, Mathematics
- ICML
- 2021

This paper considers the problem of finding a single “good action” according to a known pre-specified threshold, and introduces several good-action identification algorithms that exploit knowledge of the threshold. Expand

Open Problem: Tight Online Confidence Intervals for RKHS Elements

- Computer Science, Mathematics
- COLT
- 2021

The question of online confidence intervals in the RKHS setting is formalized and the main challenge seems to stem from the online (sequential) nature of the observation points. Expand

A Computationally Efficient Approach to Black-box Optimization using Gaussian Process Models

- Computer Science
- ArXiv
- 2020

A general approach to sequential optimization of an unknown function from noisy feedback using Gaussian process modeling is proposed that reduces the computational complexity of this class of algorithms by a factor of O(T^{2d-1})$ (where $T$ is the time horizon and $d$ the dimension of the function domain), while preserving the same regret order. Expand

#### References

SHOWING 1-10 OF 23 REFERENCES

Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization

- Mathematics, Computer Science
- COLT
- 2017

This paper provides algorithm-independent lower bounds on the simple regret, measuring the suboptimality of a single point reported after $T$ rounds, and on the cumulative regret,asuring the sum of regrets over the $T $ chosen points. Expand

Gaussian Process Optimization with Adaptive Sketching: Scalable and No Regret

- Computer Science, Mathematics
- COLT
- 2019

BKB (budgeted kernelized bandit), a new approximate GP algorithm for optimization under bandit feedback that achieves near-optimal regret (and hence near-Optimal convergence rate) with near-constant per-iteration complexity and remarkably no assumption on the input space or covariance of the GP. Expand

Information-Theoretic Regret Bounds for Gaussian Process Optimization in the Bandit Setting

- Computer Science, Mathematics
- IEEE Transactions on Information Theory
- 2012

This work analyzes an intuitive Gaussian process upper confidence bound algorithm, and bound its cumulative regret in terms of maximal in- formation gain, establishing a novel connection between GP optimization and experimental design and obtaining explicit sublinear regret bounds for many commonly used covariance functions. Expand

Bandit optimisation of functions in the Matérn kernel RKHS

- Computer Science, Mathematics
- AISTATS
- 2020

The $\pi-GP- UCB algorithm is the first practical approach with guaranteed sublinear regret for all $\nu>1$ and $d \geq 1$ and empirical validation suggests better performance and drastically improved computational scalablity compared with its predecessor, Improved GP-UCB. Expand

On Kernelized Multi-armed Bandits

- Computer Science, Mathematics
- ICML
- 2017

This work provides two new Gaussian process-based algorithms for continuous bandit optimization-Improved GP-UCB and GP-Thomson sampling (GP-TS) and derive corresponding regret bounds, and derives a new self-normalized concentration inequality for vector- valued martingales of arbitrary, possibly infinite, dimension. Expand

Parallel Gaussian Process Optimization with Upper Confidence Bound and Pure Exploration

- Computer Science, Mathematics
- ECML/PKDD
- 2013

The Gaussian Process Upper Confidence Bound and Pure exploration algorithm (GP-UCB-PE) is introduced which combines the UCB strategy and Pure Exploration in the same batch of evaluations along the parallel iterations and proves theoretical upper bounds on the regret with batches of size K for this procedure. Expand

Gaussian Process Bandit Optimisation with Multi-fidelity Evaluations

- Computer Science
- NIPS
- 2016

This work develops \mfgpucb, a novel method based on upper confidence bound techniques that outperforms such naive strategies and other multi-fidelity methods on several synthetic and real experiments and achieves better regret than strategies which ignore multi- fidelity information. Expand

Adversarially Robust Optimization with Gaussian Processes

- Computer Science, Mathematics
- NeurIPS
- 2018

It is shown that standard GP optimization algorithms do not exhibit the desired robustness properties, and a novel confidence-bound based algorithm StableOpt is provided for this purpose, which consistently succeeds in finding a stable maximizer where several baseline methods fail. Expand

High Dimensional Bayesian Optimisation and Bandits via Additive Models

- Computer Science, Mathematics
- ICML
- 2015

It is demonstrated that the method outperforms naive BO on additive functions and on several examples where the function is not additive, and it is proved that, for additive functions the regret has only linear dependence on $D$ even though the function depends on all$D$ dimensions. Expand

Multiscale Gaussian Process Level Set Estimation

- Computer Science, Mathematics
- AISTATS
- 2019

This approach improves upon the existing technique of bounding the information gain with maximum information gain and results in the algorithm having a low complexity implementation whose computational cost is significantly smaller than the existing algorithms for higher dimensional search space $\X$. Expand