Strong entropy concentration, game theory and algorithmic randomness

P.D. Grünwald

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

6 Citations (Scopus)
2 Downloads (Pure)

Abstract

We give a characterization of Maximum Entropy/Minimum Relative Entropy inference by providing two ‘strong entropy concentration’ theorems. These theorems unify and generalize Jaynes’ ‘concentration phenomenon’ and Van Campenhout and Cover’s ‘conditional limit theorem’. The theorems characterize exactly in what sense a ‘prior’ distribution Q conditioned on a given constraint and the distribution P minimizing D(P//Q) over all P satisfyingthe constraint are ‘close’ to each other. We show how our theorems are related to ‘universal models’ for exponential families, thereby establishinga link with Rissanen’s MDL/stochastic complexity. We then apply our theorems to establish the relationship (A) between entropy concentration and a game-theoretic characterization of Maximum Entropy Inference due to Topsøe and others; (B) between maximum entropy distributions and sequences that are random (in the sense of Martin-Löf/Kolmogorov) with respect to the given constraint. These two applications have strong implications for the use of Maximum Entropy distributions in sequential prediction tasks, both for the logarithmic loss and for general loss functions. We identify circumstances under which Maximum Entropy predictions are almost optimal.
Original languageEnglish
Title of host publicationComputational learning theory : proceedings 14th annual conference on computational learning theory, COLT 2001, and 5th European conference on computational learning theory, EuroCOLT 2001, Amsterdam, The Netherlands, july 16-19, 2001
EditorsD.P. Helmbold, B. Williamson
Place of PublicationBerlin
PublisherSpringer
Pages320-336
ISBN (Print)3-540-42343-5
DOIs
Publication statusPublished - 2001

Publication series

NameLecture Notes in Computer Science
Volume2111
ISSN (Print)0302-9743

Fingerprint

Dive into the research topics of 'Strong entropy concentration, game theory and algorithmic randomness'. Together they form a unique fingerprint.

Cite this