Loss functions, complexities, and the Legendre transformation

Y  Kalnishkan; V  Vovk; M V  Vyugin

doi:10.1016/j.tcs.2003.11.005

Loss functions, complexities, and the Legendre transformation

Y Kalnishkan, V Vovk, M V Vyugin

Research output: Contribution to journal › Article › peer-review

72 Downloads (Pure)

Abstract

The paper introduces a way of re-constructing a loss function from predictive complexity. We show that a loss function and expectations of the corresponding predictive complexity w.r.t. the Bernoulli distribution are related through the Legendre transformation. It is shown that if two loss functions specify the same complexity then they are equivalent in a strong sense. The expectations are also related to the so called generalised entropy.

Original language	English
Pages (from-to)	195-207
Number of pages	13
Journal	Theoretical Computer Science
Volume	313
Issue number	2
DOIs	https://doi.org/10.1016/j.tcs.2003.11.005
Publication status	Published - 17 Feb 2004

Keywords

on-line prediction
predictive complexity
generalized entropy
prediction with expert advice

Access to Document

10.1016/j.tcs.2003.11.005

legendre.pdf
Copyright Policy http://www.elsevier.com/wps/find/authorsview.authors/copyright Article Posting Policies http://www.elsevier.com/wps/find/authorsview.authors/postingpolicy Funding Body Agreements http://www.elsevier.com/wps/find/authorsview.authors/fundingbodyagreements
Submitted manuscript, 161 KB

Cite this

@article{98bc583005ff467e96f8064e1d5766c3,

title = "Loss functions, complexities, and the Legendre transformation",

abstract = "The paper introduces a way of re-constructing a loss function from predictive complexity. We show that a loss function and expectations of the corresponding predictive complexity w.r.t. the Bernoulli distribution are related through the Legendre transformation. It is shown that if two loss functions specify the same complexity then they are equivalent in a strong sense. The expectations are also related to the so called generalised entropy.",

keywords = "on-line prediction, predictive complexity, generalized entropy, prediction with expert advice",

author = "Y Kalnishkan and V Vovk and Vyugin, {M V}",

year = "2004",

month = feb,

day = "17",

doi = "10.1016/j.tcs.2003.11.005",

language = "English",

volume = "313",

pages = "195--207",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

number = "2",

}

TY - JOUR

T1 - Loss functions, complexities, and the Legendre transformation

AU - Kalnishkan, Y

AU - Vovk, V

AU - Vyugin, M V

PY - 2004/2/17

Y1 - 2004/2/17

N2 - The paper introduces a way of re-constructing a loss function from predictive complexity. We show that a loss function and expectations of the corresponding predictive complexity w.r.t. the Bernoulli distribution are related through the Legendre transformation. It is shown that if two loss functions specify the same complexity then they are equivalent in a strong sense. The expectations are also related to the so called generalised entropy.

AB - The paper introduces a way of re-constructing a loss function from predictive complexity. We show that a loss function and expectations of the corresponding predictive complexity w.r.t. the Bernoulli distribution are related through the Legendre transformation. It is shown that if two loss functions specify the same complexity then they are equivalent in a strong sense. The expectations are also related to the so called generalised entropy.

KW - on-line prediction

KW - predictive complexity

KW - generalized entropy

KW - prediction with expert advice

U2 - 10.1016/j.tcs.2003.11.005

DO - 10.1016/j.tcs.2003.11.005

M3 - Article

SN - 0304-3975

VL - 313

SP - 195

EP - 207

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 2

ER -