Adaptation to Misspecified Kernel Regularity in Kernelised Bandits

• URL: http://arxiv.org/abs/2304.13830v1
• Date: Wed, 26 Apr 2023 21:12:45 GMT
• Title: Adaptation to Misspecified Kernel Regularity in Kernelised Bandits
• Authors: Yusha Liu, Aarti Singh
• Abstract summary: We study adaptivity to the regularity of translation-invariant kernels. It is impossible to simultaneously achieve optimal cumulative regret in a pair of RKHSs with different regularities. We connect the statistical difficulty for adaptivity in continuum-armed bandits in three fundamental types of function spaces.
• Score: 27.912690223941386
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In continuum-armed bandit problems where the underlying function resides in a reproducing kernel Hilbert space (RKHS), namely, the kernelised bandit problems, an important open problem remains of how well learning algorithms can adapt if the regularity of the associated kernel function is unknown. In this work, we study adaptivity to the regularity of translation-invariant kernels, which is characterized by the decay rate of the Fourier transformation of the kernel, in the bandit setting. We derive an adaptivity lower bound, proving that it is impossible to simultaneously achieve optimal cumulative regret in a pair of RKHSs with different regularities. To verify the tightness of this lower bound, we show that an existing bandit model selection algorithm applied with minimax non-adaptive kernelised bandit algorithms matches the lower bound in dependence of $T$, the total number of steps, except for log factors. By filling in the regret bounds for adaptivity between RKHSs, we connect the statistical difficulty for adaptivity in continuum-armed bandits in three fundamental types of function spaces: RKHS, Sobolev space, and H\"older space.

Related papers

• Lower Bounds for Time-Varying Kernelized Bandits [43.62161925881489]
  optimization of black-box functions with noisy observations is a fundamental problem with widespread applications. We consider non-stationary scenarios, which are crucial for certain applications but are currently less well-understood. Under $ell_infty$-norm variations, our bounds are found to be close to the state-of-the-art upper bound.
  arXiv  Detail & Related papers  (2024-10-22T04:45:47Z)
• Error Bounds For Gaussian Process Regression Under Bounded Support Noise With Applications To Safety Certification [12.813902876908127]
  We provide novel error bounds for applying Gaussian Process Regression (GPR) under bounded support noise. We show that these errors are substantially tighter than existing state-of-the-art bounds and are particularly well-suited for GPR with neural network kernels. We illustrate how these bounds can be combined with barrier functions to successfully quantify the safety probability of an unknown dynamical system.
  arXiv  Detail & Related papers  (2024-08-16T22:03:32Z)
• An Optimization-based Algorithm for Non-stationary Kernel Bandits without Prior Knowledge [23.890686553141798]
  We propose an algorithm for non-stationary kernel bandits that does not require prior knowledge of the degree of non-stationarity. Our algorithm enjoys a tighter dynamic regret bound than previous work on the non-stationary kernel bandit setting.
  arXiv  Detail & Related papers  (2022-05-29T21:32:53Z)
• On Kernelized Multi-Armed Bandits with Constraints [16.102401271318012]
  We study a bandit problem with a general unknown reward function and a general unknown constraint function. We propose a general framework for both algorithm performance analysis. We demonstrate the superior performance of our proposed algorithms via numerical experiments.
  arXiv  Detail & Related papers  (2022-03-29T14:02:03Z)
• Misspecified Gaussian Process Bandit Optimization [59.30399661155574]
  Kernelized bandit algorithms have shown strong empirical and theoretical performance for this problem. We introduce a emphmisspecified kernelized bandit setting where the unknown function can be $epsilon$--uniformly approximated by a function with a bounded norm in some Reproducing Kernel Hilbert Space (RKHS) We show that our algorithm achieves optimal dependence on $epsilon$ with no prior knowledge of misspecification.
  arXiv  Detail & Related papers  (2021-11-09T09:00:02Z)
• 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)
• Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond [63.59034509960994]
  We study shuffling-based variants: minibatch and local Random Reshuffling, which draw gradients without replacement. For smooth functions satisfying the Polyak-Lojasiewicz condition, we obtain convergence bounds which show that these shuffling-based variants converge faster than their with-replacement counterparts. We propose an algorithmic modification called synchronized shuffling that leads to convergence rates faster than our lower bounds in near-homogeneous settings.
  arXiv  Detail & Related papers  (2021-10-20T02:25:25Z)
• Scalable Variational Gaussian Processes via Harmonic Kernel Decomposition [54.07797071198249]
  We introduce a new scalable variational Gaussian process approximation which provides a high fidelity approximation while retaining general applicability. We demonstrate that, on a range of regression and classification problems, our approach can exploit input space symmetries such as translations and reflections. Notably, our approach achieves state-of-the-art results on CIFAR-10 among pure GP models.
  arXiv  Detail & Related papers  (2021-06-10T18:17:57Z)
• No-Regret Algorithms for Time-Varying Bayesian Optimization [0.0]
  We adopt the general variation budget model to capture the time-varying environment. We introduce two GP-UCB type algorithms: R-GP-UCB and SW-GP-UCB, respectively. Our results not only recover previous linear bandit results when a linear kernel is used, but complement the previous regret analysis of time-varying Gaussian process bandit.
  arXiv  Detail & Related papers  (2021-02-11T22:35:32Z)
• On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization [55.937424268654645]
  We consider algorithm-independent lower bounds for the problem of black-box optimization of functions having a bounded norm. We provide a novel proof technique for deriving lower bounds on the regret, with benefits including simplicity, versatility, and an improved dependence on the error probability.
  arXiv  Detail & Related papers  (2020-08-20T03:48:14Z)
• Corruption-Tolerant Gaussian Process Bandit Optimization [130.60115798580136]
  We consider the problem of optimizing an unknown (typically non-producing) function with a bounded norm. We introduce an algorithm based on Fast-Slow GP-UCB based on "fast but non-robust" and "slow" We argue that certain dependencies cannot be required depending on the corruption level.
  arXiv  Detail & Related papers  (2020-03-04T09:46:58Z)

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.