Entropic Strict Minimum Message Length and Its Connections to PAC-Bayes and NML

We introduce entropic strict minimum message length (SMML), a risk-sensitive generalization of strict minimum message length coding.

The proposed criterion replaces expected two-part codelength under the prior predictive distribution with an exponential certainty equivalent, thereby defining a one-parameter family of coding rules that interpolates between Bayesian average-case coding and worst-case minimax coding.

We show that ordinary SMML is recovered in the risk-neutral limit, while the extreme risk-sensitive limit yields a minimax codelength criterion.

Applying the same entropic soft maximum to regret relative to the oracle maximum likelihood codelength recovers the normalized maximum likelihood (NML) minimax-regret principle.

We further prove that entropic SMML admits a variational characterization as a Kullback--Leibler-regularized worst-case expected codelength, giving it a PAC--Bayes-type interpretation.

We establish joint \(n\)--\(\tau\) asymptotics that identify how the risk parameter must scale with sample size in order to recover Bayesian average-case, intermediate robust, and worst-case minimax coding behavior.

For regular exponential families, the fixed-codebook partition remains affine in sufficient-statistic space, while the codepoints satisfy a tilted moment-matching condition and admit an interpretation as tilted Bregman centroids.

These results position entropic SMML as an information theoretic bridge between MML, PAC--Bayes, and MDL.