Loss functions, complexities, and the Legendre transformation

Y Kalnishkan, V Vovk, M V Vyugin

Research output: Contribution to journalArticlepeer-review

69 Downloads (Pure)


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 languageEnglish
Pages (from-to)195-207
Number of pages13
JournalTheoretical Computer Science
Issue number2
Publication statusPublished - 17 Feb 2004


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

Cite this