# Improved Regret Bounds for Online Kernel Selection under Bandit Feedback

arXiv: https://arxiv.org/abs/2303.05018 · HTML: https://mlsanity.com/paper/2303.05018/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 25 references that are in the map.
- First posted on arXiv 9 Mar 2023.

## Builds on (most cited first, 5 of 5)

- [Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits](https://mlsanity.com/paper/1807.07623/) (2018)
- [Corralling a Band of Bandit Algorithms](https://mlsanity.com/paper/1612.06246/) (2016)
- [Orthogonal Random Features](https://mlsanity.com/paper/1610.09072/) (2016)
- [Parameter-free online learning via model selection](https://mlsanity.com/paper/1801.00101/) (2017)
- [Random Feature-based Online Multi-kernel Learning in Environments with Unknown Dynamics](https://mlsanity.com/paper/1712.09983/) (2017)

## Built on by (most cited first, 1 of 1)

- [On the Necessity of Collaboration for Online Model Selection with Decentralized Data](https://mlsanity.com/paper/2404.09494/) (2024)

## Abstract (arXiv)

In this paper, we improve the regret bound for online kernel selection under bandit feedback. Previous algorithm enjoys a O((Vert fVert2Hi+1)K^frac13T^frac23) expected bound for Lipschitz loss functions. We prove two types of regret bounds improving the previous bound. For smooth loss functions, we propose an algorithm with a O(U^frac23K^-frac13(sumKi=1LT(f^asti))^frac23) expected bound where LT(f^asti) is the cumulative losses of optimal hypothesis in mathbbHi=f∈Hi:Vert fVertHi≤ U. The data-dependent bound keeps the previous worst-case bound and is smaller if most of candidate kernels match well with the data. For Lipschitz loss functions, we propose an algorithm with a O(U√KTln^frac23T) expected bound asymptotically improving the previous bound. We apply the two algorithms to online kernel selection with time constraint and prove new regret bounds matching or improving the previous O(√TlnK +Vert fVert2Himax√T,fracT√R) expected bound where R is the time budget. Finally, we empirically verify our algorithms on online regression and classification tasks.