A generalized minmax bound for universal coding

Abstract

The normalized maximum likelihood distribution as a code minimizes the mean code length distance to the ideal target, defined by the negative logarithm of the maximized likelihood of a parametric class of models, where the mean is taken with respect to the worst case model outside the parametric class. The same minmax bound is in essence the lower bound for all codes when the mean is taken with respect to almost all distributions that minimize the mean ideal target. These results strengthen the known bound when the mean is restricted to the parametric class.