在无限制条件下,实现最优混合密度估计的理论新边界。
Ratio Covers of Convex Sets and Optimal Mixture Density Estimation
- 提出无界密度比下的混合密度估计新方法
- 首次给出混合分布的最优高概率误差界
- 几何工具可推广至多目标优化问题
我们研究在KL散度意义下的密度估计:给定来自未知密度 $p^/star$ 的独立同分布样本,目标是构造估计器 $\\(widehat{p}$ 使得 $\mathrm{KL}(p^/star,\\widehat{p})$ 以高概率很小。考虑两种基础情形:(i) 模型聚合($p^/star$ 属于词典),(ii) 凸聚合(混合密度估计,$p^/star$ 是词典中密度的混合)。关键在于不假设基密度的性质:其比值可能无界,支撑集也可能不同。对两类问题,我们确定了基于词典大小、样本量和置信水平的最优高概率保证。这些最优率高于密度比有界的经典情形;对离散分布的混合估计,与已有下界一致。混合情形的分析依赖两个新的覆盖结果:第一,给出了 $M$ 个分布混合类的局部赫林格熵的紧致、无分布上界;第二,证明了凸集的最优比覆盖定理:对任意凸紧集 $K \subset \mathbb{R}_+^d$,存在子集 $A \subset K$,元素不超过 $2^{O(d)}$,且 $K$ 中每点坐标均被 $A$ 中某点按常数因子支配。该几何结果独立有趣,可导出多目标优化中凸可行集下 $\varepsilon$-近似帕累托集的新基数估计。
原文摘要 · Abstract (English)
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 $\widehat{p}$ such that $\mathrm{KL}(p^\star,\widehat{p})$ 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 \mathbb{R}_+^d$, there exists a subset $A \subset K$ with at most $2^{O(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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。