提出新方法高效学习截断布尔乘积分布，突破以往样本复杂度瓶颈。
Efficient Learning of Truncated Boolean Product Distributions: Influence to the Rescue
- 基于影响分析重构截断集几何结构，弱化对连通性要求
- 实现ℓ∞恢复的样本复杂度降至O(log n / ε²)，匹配最优下界
- 适用于低质量截断集，无需在任意参数下采样
从受限于子集 $S \subseteq \{0,1\}^n$ 的独立样本中学习离散分布 $μ_z$ 的自然参数 $z \in \mathbb{R}^n$ 是高维统计中的基础挑战。现有高效估计截断布尔乘积分布的方法，如 [Fotakis et al' COLT'20, Algorithmica '22]，需强局部连通性假设（即fatness）或严格的反集中假设，且要求截断集总质量为关于 $n$ 的常数。此外，当 $S$ 质量指数小（$e^{-Ω(n)}$）时，其结果样本复杂度达 $Ω(2^n)$。本文通过分析 $S$ 在 $μ_z$ 测度下的几何性质，改进了fatness假设下的参数估计，将ℓ∞恢复的样本复杂度优化至 $O(\log n / ε^2)$，达到未截断情形的极小极大率。进一步引入布尔函数分析中的影响概念推广fatness，给出高效推断的充分条件。与此前工作不同，本方法无需在模型任意参数化下采样。最后，建立理论下界，表明样本复杂度对模型宽度及集合元素间最小距离存在固有的指数依赖。
原文摘要 · Abstract (English)
Learning the natural parameters $z \in \mathbb{R}^n$ of discrete distributions $μ_z$ from independent samples constrained to a subset $S \subseteq \{0,1\}^n$ is a foundational challenge in high-dimensional statistics. Existing methods for efficiently estimating truncated Boolean product distributions, notably the work of [Fotakis et al' COLT'20, Algorithmica '22], require either strong local connectivity assumptions on $S$ -- a property denoted fatness -- or stringent anti-concentration assumptions and necessitate the total mass of the truncation set to be a constant with respect to $n$. Moreover, the results in [Fotakis et al' COLT'20, Algorithmica '22] suffer from sample complexities that scale as $Ω(2^n)$ if the mass of $S$ is exponentially small in $n$. In this work, we circumvent these limitations by analyzing the geometry of $S$ under the measure $μ_z$. We refine the existing parameter estimation guarantees under the fatness assumption, improving the prior sample complexity to $O( \log n / ε^2)$ for $\ell_\infty$-recovery, matching the untruncated minimax rate. We further generalize fatness using the notion of influence utilized in the analysis of Boolean functions and provide sufficient conditions for efficient inference. Notably, unlike previous work, our method does not require sampling at arbitrary parameterizations of the model. Lastly, we establish a theoretical lower bound demonstrating the sample complexity exhibits an intrinsic exponential dependence on the width of the model and the minimum distance between elements in the set.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。