Organizations: Department of Computer Science, Stanford University. · Department of Economics and Business, Pompeu Fabra University, Barcelona, Spain; ICREA, Barcelona, Spain; Barcelona Graduate School of Economics. · Department of Statistics, CREST/ENSAE Paris, Palaiseau, France. · Department of AI and Data Science, The University of Hong Kong. · Department of Statistics, University of California, Berkeley.
We study density estimation in Kullback-Leibler divergence: given an i.i.d. sample from an unknown density p⋆, the goal is to construct an estimator p such that KL(p⋆,p) is small with high probability. We consider two fundamental settings involving a finite dictionary of densities: (i) model aggregation, where p⋆ belongs to the dictionary, and (ii) convex aggregation (mixture density estimation), where p⋆ 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⊂R+d, there exists a subset A⊂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 ε-approximate Pareto sets in multi-objective optimization with convex feasible set.
Figures & tables
Simplex KL Covering Number Bounds of 53
Name
Regime
Lower Bound
Upper Bound
Hellinger method
0<ε<logd
(εc)2d−1
(εClogd)2d−1
χ2 method
0<ε<4(d+1)21
(εc)2d−1
log(ε1)(εC)2d−1
Subexponential
ε=r1logd+log(r+1),1⩽r⩽elogd
exp(e21d1−1/r)
exp(d1−1/rlogd)
Polynomial
ε=logγd,γ⩽2d
exp(eγ+loge2πγ)
exp(2γlogd)
Table 1: Covering number bounds for the simplex in 53 for different regimes of ε . Constants c and C may vary for each bound. This table corresponds to their Figure 3.2. Our ratio cover results will improve the regimes affected by the Hellinger method and the χ2 method.
We study the task of density estimation, where we hope to accurately estimate a probability density from n samples. A textbook method for density estimation in total variation distance is the minimum-distance estimator approach, where we conclude both the algorithm and the analysis merely from bounding the VC dimension of a particular concept class (the so-called Yatracos class). While this technique has originally yielded sharp guarantees primarily for total variation distance, in this work we extend the minimum-distance estimator approach for learning within Hellinger distance. Our main observation is that we may produce an analogous recipe for Hellinger (where we only require bounding the VC dimension of a related concept class) by drawing connections to recent results yielding reverse data processing inequalities. This recipe is flexible enough to accommodate fast algorithms originally designed for total variation distance; by modifying the approach of Acharya et al. (2017) we conclude the first near-linear time algorithm for learning classes including univariate mixtures of log-concave densities and mixtures of Gaussians (with arbitrary variances), with near-optimal sample complexity.
We revisit the classical problem of estimating an unknown distribution from its samples by fitting a mixture model that minimizes cross-entropy loss. Framing the task as a stochastic convex optimization problem over the space of M-component mixture distributions, we propose a family of estimators derived from the stochastic mirror descent (SMD) algorithm. This optimization-based approach provides a principled and flexible framework that generalizes traditional estimators and proposes a variety of novel estimators through the choice of Bregman divergences. A key advantage of our method is that it scales efficiently with the number of candidate components fi; that is, one can employ a large set of basis distributions in the mixture model without incurring significant computational overhead. This enables richer approximations and improved estimation accuracy. Moreover, in the case of categorical distribution (discrete outcomes) our estimators do not require a strict lower bound, in other words our framework does not require the precise knowledge of the support of the distribution. We demonstrate that, under mild conditions, the proposed φ-SMD estimators achieve near-optimal convergence rates in both Kullback-Leibler (KL) divergence and ℓ2-norm and offer practical benefits when computation is expensive. Our numerical analysis highlights improved performance guaranties over classical estimators, particularly in terms of sample efficiency and scalability.
We study density ratio estimation and importance-weighted regression under target shift with continuous outputs. Under target shift, the conditional distribution of the inputs given the outputs remains invariant across the training and test distributions, while the output marginal distribution may change. Although this problem has been extensively studied for discrete outputs, the continuous setting is substantially less understood: the importance weights are determined by an unknown density ratio function, for which existing estimation methods lack explicit finite-sample convergence rates. We propose a spectral regularization method in a reproducing kernel Hilbert space (RKHS) for estimating the continuous density ratio from labeled training samples and unlabeled test inputs. Under a source condition with regularity parameter ι>0, we establish high-probability finite-sample guarantees and show that the estimator achieves the capacity-independent minimax-optimal RKHS-norm rate O(nη−ι/(2ι+2)). We then incorporate the estimated density ratio into importance-weighted regression and characterize the propagation of density-ratio estimation error to the final predictor. When sufficiently many samples are available for density ratio estimation, the resulting regression estimator attains the minimax-optimal rates of standard kernel regression. These results establish a finite-sample theory for continuous density ratio estimation and importance-weighted learning under target shift.
Ren-Rui Liu, Zheng-Chu Guo
School of Mathematical Sciences, Zhejiang University, Hangzhou 310058, China