Tighter Confidence Bounds for Sequential Kernel Regression
This work provides incremental improvements in confidence bounds for sequential learning algorithms, benefiting researchers and practitioners in machine learning by enhancing performance guarantees.
The authors tackled the problem of quantifying uncertainty in sequential kernel regression by developing new confidence bounds using martingale tail inequalities, which are proven to be always tighter than existing ones and lead to better empirical performance in kernel bandit problems.
Confidence bounds are an essential tool for rigorously quantifying the uncertainty of predictions. They are a core component in many sequential learning and decision-making algorithms, with tighter confidence bounds giving rise to algorithms with better empirical performance and better performance guarantees. In this work, we use martingale tail inequalities to establish new confidence bounds for sequential kernel regression. Our confidence bounds can be computed by solving a conic program, although this bare version quickly becomes impractical, because the number of variables grows with the sample size. However, we show that the dual of this conic program allows us to efficiently compute tight confidence bounds. We prove that our new confidence bounds are always tighter than existing ones in this setting. We apply our confidence bounds to kernel bandit problems, and we find that when our confidence bounds replace existing ones, the KernelUCB (GP-UCB) algorithm has better empirical performance, a matching worst-case performance guarantee and comparable computational cost.