利用不完美先验信息，高效学习布尔超立方体上的分布。
Product distribution learning with imperfect advice
- 结合不完美的先验分布，设计高效学习算法。
- 样本复杂度降至 $\tilde{O}(d^{1-η}/\varepsilon^2)$，优于经典下界。
- 适用于有弱先验知识的高维分布学习场景。
给定来自未知分布 $P$ 的独立同分布样本，分布学习的目标是恢复一个与 $P$ 接近的分布参数。当 $P$ 是布尔超立方体 $\{0,1\}^d$ 上的乘积分布时，已知学习 $P$ 至总变差距离 $\varepsilon$ 需要 $Ω(d/\varepsilon^2)$ 个样本。本文研究当学习者同时获得另一乘积分布 $Q$ 的参数作为建议时的情形。我们证明：若 $\|\mathbf{p} - \mathbf{q}\|_1 < \varepsilon d^{0.5 - Ω(η)}$，存在高效算法可在 $\tilde{O}(d^{1-η}/\varepsilon^2)$ 个样本内完成学习，其中 $\mathbf{p}$、$\mathbf{q}$ 分别为 $P$ 与 $Q$ 的均值向量，且该边界无需预先知晓。
原文摘要 · Abstract (English)
Given i.i.d.~samples from an unknown distribution $P$, the goal of distribution learning is to recover the parameters of a distribution that is close to $P$. When $P$ belongs to the class of product distributions on the Boolean hypercube $\{0,1\}^d$, it is known that $Ω(d/\varepsilon^2)$ samples are necessary to learn $P$ within total variation (TV) distance $\varepsilon$. We revisit this problem when the learner is also given as advice the parameters of a product distribution $Q$. We show that there is an efficient algorithm to learn $P$ within TV distance $\varepsilon$ that has sample complexity $\tilde{O}(d^{1-η}/\varepsilon^2)$, if $\|\mathbf{p} - \mathbf{q}\|_1 < \varepsilon d^{0.5 - Ω(η)}$. Here, $\mathbf{p}$ and $\mathbf{q}$ are the mean vectors of $P$ and $Q$ respectively, and no bound on $\|\mathbf{p} - \mathbf{q}\|_1$ is known to the algorithm a priori.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。