SCIENCE@home

Online learning with kernel losses

Aldo Pacchiano,Niladri S. Chatterji,P. Bartlett

Published 2018 in International Conference on Machine Learning

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 $\mu_j \le \mathcal{O}(j^{-\beta})$, we find that the regret is bounded by $\mathcal{R}_n \le \mathcal{O}(n^{\beta/(2(\beta-1))})$; while under the assumption of exponential eigendecay $\mu_j \le \mathcal{O}(e^{-\beta j })$, we get an even tighter bound on the regret $\mathcal{R}_n \le \mathcal{O}(n^{1/2}\log(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.

PUBLICATION RECORD

  • Publication year

    2018

  • Venue

    International Conference on Machine Learning

  • Publication date

    2018-02-27

  • Fields of study

    Mathematics, Computer Science

  • Identifiers
    arXiv 1802.09732
  • External record

    Open on Semantic Scholar

  • Source metadata

    Semantic Scholar

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-54 of 54 references · Page 1 of 1

CITED BY

Showing 1-17 of 17 citing papers · Page 1 of 1