Tighter Confidence Bounds for Sequential Kernel Regression

• URL: http://arxiv.org/abs/2403.12732v2
• Date: Mon, 11 Nov 2024 16:50:48 GMT
• Title: Tighter Confidence Bounds for Sequential Kernel Regression
• Authors: Hamish Flynn, David Reeb,
• Abstract summary: 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. We find that when our confidence bounds replace existing ones, the KernelUCB algorithm has better empirical performance, a matching worst-case performance guarantee and comparable computational cost.
• Score: 3.683202928838613
• License:
• Abstract: 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.

Related papers

• High Confidence Level Inference is Almost Free using Parallel Stochastic Optimization [16.38026811561888]
  This paper introduces a novel inference method focused on constructing confidence intervals with efficient computation and fast convergence to the nominal level. Our method requires minimal additional computation and memory beyond the standard updating of estimates, making the inference process almost cost-free.
  arXiv  Detail & Related papers  (2024-01-17T17:11:45Z)
• Binary Classification with Confidence Difference [100.08818204756093]
  This paper delves into a novel weakly supervised binary classification problem called confidence-difference (ConfDiff) classification. We propose a risk-consistent approach to tackle this problem and show that the estimation error bound the optimal convergence rate. We also introduce a risk correction approach to mitigate overfitting problems, whose consistency and convergence rate are also proven.
  arXiv  Detail & Related papers  (2023-10-09T11:44:50Z)
• Improved Algorithms for Stochastic Linear Bandits Using Tail Bounds for Martingale Mixtures [26.683757807252675]
  We present improved algorithms with worst-case regret guarantees for the linear bandit problem. We show that our confidence sequences are tighter than competitors, both empirically and theoretically.
  arXiv  Detail & Related papers  (2023-09-25T17:13:46Z)
• Huber-Robust Confidence Sequences [37.16361789841549]
  Confidence sequences are confidence intervals that can be sequentially tracked, and are valid at arbitrary data-dependent stopping times. We show that the resulting confidence sequences attain the optimal width achieved in the nonsequential setting. Since confidence sequences are a common tool used within A/B/n testing and bandits, these results open the door to sequential experimentation that is robust to outliers and adversarial corruptions.
  arXiv  Detail & Related papers  (2023-01-23T17:29:26Z)
• Fast Entropy-Based Methods of Word-Level Confidence Estimation for End-To-End Automatic Speech Recognition [86.21889574126878]
  We show how per-frame entropy values can be normalized and aggregated to obtain a confidence measure per unit and per word. We evaluate the proposed confidence measures on LibriSpeech test sets, and show that they are up to 2 and 4 times better than confidence estimation based on the maximum per-frame probability.
  arXiv  Detail & Related papers  (2022-12-16T20:27:40Z)
• Meta-Learning Hypothesis Spaces for Sequential Decision-making [79.73213540203389]
  We propose to meta-learn a kernel from offline data (Meta-KeL) Under mild conditions, we guarantee that our estimated RKHS yields valid confidence sets. We also empirically evaluate the effectiveness of our approach on a Bayesian optimization task.
  arXiv  Detail & Related papers  (2022-02-01T17:46:51Z)
• Open Problem: Tight Online Confidence Intervals for RKHS Elements [57.363123214464764]
  We formalize the question of online confidence intervals in the RKHS setting and overview the existing results. It is unclear whether the suboptimal regret bound is a fundamental shortcoming of these algorithms or an artifact of the proof.
  arXiv  Detail & Related papers  (2021-10-28T22:36:20Z)
• Off-policy Confidence Sequences [33.749904615295485]
  We develop confidence bounds that hold uniformly over time for off-policy evaluation in the contextual bandit setting. We provide algorithms for computing these confidence sequences that strike a good balance between computational and statistical efficiency.
  arXiv  Detail & Related papers  (2021-02-18T18:40:30Z)
• An evaluation of word-level confidence estimation for end-to-end automatic speech recognition [70.61280174637913]
  We investigate confidence estimation for end-to-end automatic speech recognition (ASR) We provide an extensive benchmark of popular confidence methods on four well-known speech datasets. Our results suggest a strong baseline can be obtained by scaling the logits by a learnt temperature.
  arXiv  Detail & Related papers  (2021-01-14T09:51:59Z)
• CoinDICE: Off-Policy Confidence Interval Estimation [107.86876722777535]
  We study high-confidence behavior-agnostic off-policy evaluation in reinforcement learning. We show in a variety of benchmarks that the confidence interval estimates are tighter and more accurate than existing methods.
  arXiv  Detail & Related papers  (2020-10-22T12:39:11Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.