Ratio Covers of Convex Sets and Optimal Mixture Density Estimation

We study density estimation in Kullback-Leibler divergence: given an i.i.d. sample from an unknown density p^star, the goal is to construct an estimator widehatp such that KL(p^star,widehatp) is small with high probability. We consider two fundamental settings involving a finite dictionary of densities: (i) model aggregation, where p^star belongs to the dictionary, and (ii) convex aggregation (mixture density estimation), where p^star is a mixture of densities from the dictionary. Crucially, we make no assumption on the base densities: their ratios may be unbounded and their supports may differ. For both problems, we identify the best possible high-probability guarantees in terms of the dictionary size, sample size, and confidence level. These optimal rates are higher than those achievable when density ratios are bounded by absolute constants; for mixture density estimation, they match existing lower bounds in the special case of discrete distributions. Our analysis of the mixture case hinges on two new covering results. First, we provide a sharp, distribution-free upper bound on the local Hellinger entropy of the class of mixtures of M distributions. Second, we prove an optimal ratio covering theorem for convex sets: for every convex compact set K subset ℝ_+d, there exists a subset A subset K with at most 2O(d) elements such that each element of K is coordinate-wise dominated by an element of A up to a universal constant factor. This geometric result is of independent interest; notably, it yields new cardinality estimates for varepsilon-approximate Pareto sets in multi-objective optimization with convex feasible set.