Worst Case Prediction over Sequences under Log Loss

  • Manfred Opper
  • David Haussler
Part of the The IMA Volumes in Mathematics and its Applications book series (IMA, volume 107)


We consider the game of sequentially assigning probabilities to future data based on past observations under logarithmic loss. We are not making probabilistic assumptions about the generation of the data, but consider a situation where a player tries to minimize his loss relative to the loss of the (with hindsight) best distribution from a target class for the worst sequence of data. We give bounds on the minimax regret in terms of the metric entropies of the target class with respect to suitable distances between distributions.


Minimax Regret Computational Learning Theory Probabilistic Assumption Target Family Good Expert 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. [1]
    Kolmogorov, A.N. and V.M. Tihomirov, e-Entropy and e-Capacity of Sets in Functional Spaces, Amer. Math. Soc. Translations (Ser. 2), 17, 277–364 (1961).MathSciNetGoogle Scholar
  2. [2]
    V.G. Vovk, Aggregating strategies, Proceedings of the 1990 conference on computational learning theory, Morgan Kaufmann, 2 371–381 (1990).Google Scholar
  3. [3]
    N. Cesa-Bianchi, Y. Freund, D.H. Helmbold, D. Haussler, R.E. Schapire, and M.K. Warmuth, How to use expert advice, in 25th Annual ACM Symposium on Theory of Computing, 382–392, San Diego, CA (1993).Google Scholar
  4. [4]
    Y. Freund, Predicting a binary sequence as well as the optimal biased coin, Proceedings of the ninth annual conference on computational learning theory, ACM Press (1996).Google Scholar
  5. [5]
    J. Shtarkov, Coding of discrete sources with unknown statistics, In: Topics in Information Theory, 559–574, I. Csiszar and P. Elias, editors, North Holland, Amsterdam, 1975.Google Scholar
  6. [6]
    A.R. Barron and Q. XIE, Asymptotic minimax loss for data compression, gambling, and prediction, Proceedings of the ninth annual conference on computational learning theory, ACM Press (1996).Google Scholar
  7. [7]
    J. RISSANEN, Fisher Information and Stochastic Complexity, IEEE Trans. on Inf. Theory 42, 40–47 (1996).MathSciNetzbMATHCrossRefGoogle Scholar
  8. [8]
    T. Cover and JOY A. Thomas, Elements of Information Theory, Wiley Series in Telecommunications, New York, 1991.zbMATHCrossRefGoogle Scholar
  9. [9]
    T.M Cover and E. ordentlich, Universal portfolios with side information, IEEE Transactions on Information Theory 42(2), 348–363 (1996).MathSciNetzbMATHCrossRefGoogle Scholar
  10. [10]
    AAD W. Van Der Vaart and JON A. Wellner, Weak Convergence and Empirical Processes, Springer Series in Statistics, 1996.Google Scholar
  11. [11]
    M. Ledoux and M. Talagrand, Probability in Banach Spaces: Isoperimetry and Processes, Springer Verlag, Berlin (1991).zbMATHGoogle Scholar
  12. [12]
    D. Haussler and M. Opper, Mutual Information, Metric Entropy, and Risk in Estimation of Probability Distributions, Annals of Statistics 25 (6) (December, 1997).Google Scholar
  13. [13]
    G.F. Clements, Entropy of several sets of real valued functions, Pacific J. Math. 13, 1085 (1963).MathSciNetzbMATHGoogle Scholar
  14. [14]
    M.J. Weinberger, N. Merhav and M. Feder, Optimal Sequential Probability Assignment for Individual Sequences, IEEE Trans. on Inf. Theory 40, 384–396 (1994).MathSciNetzbMATHCrossRefGoogle Scholar
  15. [15]
    W. Hoeffding, Probability Inequalities for Sums of Bounded Random Variables, American Statistical Association Journal 58, 13–30 (1963).MathSciNetzbMATHCrossRefGoogle Scholar

Copyright information

© Springer Science+Business Media New York 1999

Authors and Affiliations

  • Manfred Opper
    • 1
  • David Haussler
    • 2
  1. 1.Institut für Theoretische Physik IIIUniversität WürzburgWürzburgGermany
  2. 2.Department of Computer and Information SciencesUniversity of CaliforniaSanta CruzGermany

Personalised recommendations