Learning Discrete Distributions from Untrusted Batches
Learning Discrete Distributions from Untrusted Batches
复制标题
从不受信任的批次中学习离散分布
DOI：
10.4230/lipics.itcs.2018.47
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
G. Valiant
中科院分区：
文献类型：
--
作者：
Mingda Qiao;G. Valiant
我们考虑了在存在$\epsilon$分数恶意数据源的情况下学习离散分布的问题。具体地说，我们考虑这样的设置，其中存在一些基本分布$p$，并且每个数据源提供一批$k$样本，并保证至少$(1-\epsilon)$分数的源从总变异距离至多为$\p$的分布中提取样本。我们不对剩余的$\epsilon$部分来源提供的数据进行任何假设--该数据甚至可以被选为“好”批次的$(1-\epsilon)$部分的对抗函数。我们给出了两种算法：一种算法的运行时指数为支持度，$n$，但多项式为$k$，$1/\epsilon$和$1/\eta$，它需要$O((n+k)/\epsilon^2)$批，并将$p$恢复到错误$O(\eta+\epsilon/\sqrt{k})$。即使在给定无限数量的数据源的情况下，这种恢复精度对于恒定因素来说也是理论上最优的信息。我们的第二个算法适用于$\eta=0$设置，也实现了$O(\epsilon/\Sqrt{k})$Recover保证，尽管它运行在$\mathm{Poly}((Nk)^k)$时间。这第二种算法通过一个秩1张量来逼近某一张量，使得距离最小，考虑到许多低阶张量逼近问题的困难，它是令人惊讶的，并且可能是独立感兴趣的。
We consider the problem of learning a discrete distribution in the presence of an $\epsilon$ fraction of malicious data sources. Specifically, we consider the setting where there is some underlying distribution, $p$, and each data source provides a batch of $\ge k$ samples, with the guarantee that at least a $(1-\epsilon)$ fraction of the sources draw their samples from a distribution with total variation distance at most $\eta$ from $p$. We make no assumptions on the data provided by the remaining $\epsilon$ fraction of sources--this data can even be chosen as an adversarial function of the $(1-\epsilon)$ fraction of "good" batches. We provide two algorithms: one with runtime exponential in the support size, $n$, but polynomial in $k$, $1/\epsilon$ and $1/\eta$ that takes $O((n+k)/\epsilon^2)$ batches and recovers $p$ to error $O(\eta+\epsilon/\sqrt{k})$. This recovery accuracy is information theoretically optimal, to constant factors, even given an infinite number of data sources. Our second algorithm applies to the $\eta = 0$ setting and also achieves an $O(\epsilon/\sqrt{k})$ recover guarantee, though it runs in $\mathrm{poly}((nk)^k)$ time. This second algorithm, which approximates a certain tensor via a rank-1 tensor minimizing $\ell_1$ distance, is surprising in light of the hardness of many low-rank tensor approximation problems, and may be of independent interest.
DOI：
--
发表时间：
2017-03
期刊：
--
影响因子：
--
作者：
Ilias Diakonikolas;Gautam Kamath;D. Kane;Jerry Li;Ankur Moitra;Alistair Stewart
通讯作者：
Ilias Diakonikolas;Gautam Kamath;D. Kane;Jerry Li;Ankur Moitra;Alistair Stewart