The normalized maximum likelihood (NML) distribution achieves minimax log loss and coding regret for the multinomial model. In practice other
nearly minimax distributions are used instead as calculating the sequential probabilities needed for coding and prediction takes exponential time with NML. The Bayes mixture obtained with the Dirichlet prior Dir(1/2, . . . , 1/2) and asymptotically minimax modifications of it have been widely studied in the context of large sample sizes. Recently there has also been interest in minimax optimal coding distributions for large alphabets. We investigate Dirichlet priors that
achieve minimax coding regret when the alphabet size m is finite but large in comparison to the sample size n. We prove that a Bayes mixture with the Dirichlet prior Dir(1/3, . . . , 1/3) is optimal in this regime (in particular, when m > 5/(2n) + 4/(n-2) + 3/2). The worst-case regret of the resulting distribution approaches the NML regret as the alphabet size grows.

Joint work with: Elias Jääsaari, Janne Leppä-aho, and Tomi Silander.