- Conference Paper
We consider the problem of optimizing an unknown (typically non-convex) function with a bounded norm in some Reproducing Kernel Hilbert Space (RKHS), based on noisy bandit feedback. We consider a novel variant of this problem in which the point evaluations are not only corrupted by random noise, but also adversarial corruptions. We introduce an algorithm Fast-Slow GP-UCB based on Gaussian process methods, randomized selection between two instances labeled fast (but non-robust) and slow (but robust), enlarged confidence bounds, and the principle of optimism under uncertainty. We present a novel theoretical analysis upper bounding the cumulative regret in terms of the corruption level, the time horizon, and the underlying kernel, and we argue that certain dependencies cannot be improved. We observe that distinct algorithmic ideas are required depending on whether one is required to perform well in both the corrupted and non-corrupted settings, and whether the corruption level is known or not. Show more
Book titleProceedings of the 23rd International Conference on Artificial Intelligence and Statistics (AISTATS 2020)
Journal / seriesProceedings of Machine Learning Research
Pages / Article No.
Organisational unit03908 - Krause, Andreas / Krause, Andreas
167189 - Big data transport models: The example of road pricing (SNF)
815943 - Reliable Data-Driven Decision Making in Cyber-Physical Systems (EC)
19-2 FEL-47 - Robust Sample-Efficient Learning when Data ist Costly (ETHZ)
NotesDue to the Coronavirus (COVID-19) the conference was conducted virtually.
MoreShow all metadata