Online learning with kernel losses

2018/02/27 by Aldo Pacchiano, Pacchiano, Aldo, Niladri S. Chatterji +3 · 2 citations
Decision Sciences · Computer Science · Engineering · #Advanced Bandit Algorithms Research #Machine Learning and Algorithms #Sparse and Compressive Sensing Techniques

paper · pdf · doi:10.48550/arxiv.1802.09732

Abstract

We present a generalization of the adversarial linear bandits framework, where the underlying losses are kernel functions (with an associated reproducing kernel Hilbert space) rather than linear functions. We study a version of the exponential weights algorithm and bound its regret in this setting. Under conditions on the eigendecay of the kernel we provide a sharp characterization of the regret for this algorithm. When we have polynomial eigendecay μ_j ≤ O(j^-β), we find that the regret is bounded by R_n ≤ O(n^β/(2(β-1))); while under the assumption of exponential eigendecay μ_j ≤ O(e^-βj ), we get an even tighter bound on the regret R_n ≤ O(n^1/2log(n)^1/2). We also study the full information setting when the underlying losses are kernel functions and present an adapted exponential weights algorithm and a conditional gradient descent algorithm.

Cited by

• Online Policy Learning via a Self-Normalized Maximal Inequality
• Rate-adaptive model selection over a collection of black-box contextual\n bandit algorithms

Related

• Adversarial Contextual Bandits Go Kernelized
• Online Learning of Noisy Data with Kernels
• Efficient online learning with kernels for adversarial large scale problems
• Improved Regret Bounds for Online Kernel Selection under Bandit Feedback
• Nearly Optimal Algorithms with Sublinear Computational Complexity for Online Kernel Regression