Online Non-Additive Path Learning under Full and Partial Information

Corinna Cortes; Vitaly Kuznetsov; Mehryar Mohri; Holakou Rahmanian; Manfred K. Warmuth

Online Non-Additive Path Learning under Full and Partial Information

Corinna Cortes, Vitaly Kuznetsov, Mehryar Mohri, Holakou Rahmanian, Manfred K. Warmuth

Computer Science

Research output: Contribution to journal › Conference article › peer-review

Abstract

We study the problem of online path learning with non-additive gains, which is a central problem appearing in several applications, including ensemble structured prediction. We present new online algorithms for path learning with non-additive count-based gains for the three settings of full information, semi-bandit and full bandit with very favorable regret guarantees. A key component of our algorithms is the definition and computation of an intermediate context-dependent automaton that enables us to use existing algorithms designed for additive gains. We further apply our methods to the important application of ensemble structured prediction. Finally, beyond count-based gains, we give an efficient implementation of the EXP3 algorithm for the full bandit setting with an arbitrary (non-additive) gain.

Original language	English (US)
Pages (from-to)	274-299
Number of pages	26
Journal	Proceedings of Machine Learning Research
Volume	98
State	Published - 2019
Event	30th International Conference on Algorithmic Learning Theory, ALT 2019 - Chicago, United States Duration: Mar 22 2019 → Mar 24 2019

Keywords

finite-state automaton
non-additive gains
online learning

ASJC Scopus subject areas

Artificial Intelligence
Software
Control and Systems Engineering
Statistics and Probability

Cite this

@article{56cc316ca8964e31a023ff36803a273f,

title = "Online Non-Additive Path Learning under Full and Partial Information",

abstract = "We study the problem of online path learning with non-additive gains, which is a central problem appearing in several applications, including ensemble structured prediction. We present new online algorithms for path learning with non-additive count-based gains for the three settings of full information, semi-bandit and full bandit with very favorable regret guarantees. A key component of our algorithms is the definition and computation of an intermediate context-dependent automaton that enables us to use existing algorithms designed for additive gains. We further apply our methods to the important application of ensemble structured prediction. Finally, beyond count-based gains, we give an efficient implementation of the EXP3 algorithm for the full bandit setting with an arbitrary (non-additive) gain.",

keywords = "finite-state automaton, non-additive gains, online learning",

author = "Corinna Cortes and Vitaly Kuznetsov and Mehryar Mohri and Holakou Rahmanian and Warmuth, {Manfred K.}",

note = "Publisher Copyright: {\textcopyright} 2019 Proceedings of Machine Learning Research. All rights reserved.; 30th International Conference on Algorithmic Learning Theory, ALT 2019 ; Conference date: 22-03-2019 Through 24-03-2019",

year = "2019",

language = "English (US)",

volume = "98",

pages = "274--299",

journal = "Proceedings of Machine Learning Research",

issn = "2640-3498",

}

TY - JOUR

T1 - Online Non-Additive Path Learning under Full and Partial Information

AU - Cortes, Corinna

AU - Kuznetsov, Vitaly

AU - Mohri, Mehryar

AU - Rahmanian, Holakou

AU - Warmuth, Manfred K.

PY - 2019

Y1 - 2019

N2 - We study the problem of online path learning with non-additive gains, which is a central problem appearing in several applications, including ensemble structured prediction. We present new online algorithms for path learning with non-additive count-based gains for the three settings of full information, semi-bandit and full bandit with very favorable regret guarantees. A key component of our algorithms is the definition and computation of an intermediate context-dependent automaton that enables us to use existing algorithms designed for additive gains. We further apply our methods to the important application of ensemble structured prediction. Finally, beyond count-based gains, we give an efficient implementation of the EXP3 algorithm for the full bandit setting with an arbitrary (non-additive) gain.

AB - We study the problem of online path learning with non-additive gains, which is a central problem appearing in several applications, including ensemble structured prediction. We present new online algorithms for path learning with non-additive count-based gains for the three settings of full information, semi-bandit and full bandit with very favorable regret guarantees. A key component of our algorithms is the definition and computation of an intermediate context-dependent automaton that enables us to use existing algorithms designed for additive gains. We further apply our methods to the important application of ensemble structured prediction. Finally, beyond count-based gains, we give an efficient implementation of the EXP3 algorithm for the full bandit setting with an arbitrary (non-additive) gain.

KW - finite-state automaton

KW - non-additive gains

KW - online learning

UR - http://www.scopus.com/inward/record.url?scp=85161215556&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85161215556&partnerID=8YFLogxK

M3 - Conference article

AN - SCOPUS:85161215556

SN - 2640-3498

VL - 98

SP - 274

EP - 299

JO - Proceedings of Machine Learning Research

JF - Proceedings of Machine Learning Research

T2 - 30th International Conference on Algorithmic Learning Theory, ALT 2019

Y2 - 22 March 2019 through 24 March 2019

ER -

Online Non-Additive Path Learning under Full and Partial Information

Abstract

Keywords

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this