On the Power of Learning from k-Wise Queries
On the Power of Learning from k-Wise Queries
复制标题
DOI：
10.4230/lipics.itcs.2017.41
复制
发表时间：
2017-02
期刊：
影响因子：
--
通讯作者：
V. Feldman;Badih Ghazi
中科院分区：
文献类型：
--
作者：
V. Feldman;Badih Ghazi
一些经过充分研究的数据样本访问模型，包括统计查询、本地差分隐私和低通信算法，都依赖于提供有关单个样本函数信息的查询。 （例如，统计查询 (SQ) 对于将 X 映射到实数的查询函数 q 的任何选择给出 Ex_{x ~ D}[q(x)] 的估计，其中 D 是 X 上的未知数据分布。）然而，一些数据分析算法依赖于依赖于多个样本的函数的属性。这样的算法自然可以使用 k 次查询来实现，每个查询都由将 X^k 映射到实数的函数 q 指定。因此，很自然地会问，使用 k 次查询的算法是否可以更有效地解决学习问题以及能提高多少。 Blum、Kalai 和 Wasserman (2003) 表明，对于固定分布上的任何弱 PAC 学习问题，使用 k 维 SQ 学习的复杂度比（一元）SQ 复杂度小最多 2^k 倍。我们表明，对于分布上更普遍的问题，情况要丰富得多。对于每个 k，使用 k 次查询进行的与分布无关的 PAC 学习的复杂性可能比使用 (k+1) 次查询进行的学习呈指数级增长。然后，我们给出两种使用一元查询模拟 k 次查询的方法。第一种方法利用需要解决的问题的结构。它概括并（指数地）强化了 Blum 等人的结果。它使我们能够导出用于学习 DNF 公式和随机约束满足问题的强大下限，这些问题与使用 k 次查询的算法相矛盾。第二种方法利用了 k 次查询函数的 k 方通信复杂性。
Several well-studied models of access to data samples, including statistical queries, local differential privacy and low-communication algorithms rely on queries that provide information about a function of a single sample. (For example, a statistical query (SQ) gives an estimate of Ex_{x ~ D}[q(x)] for any choice of the query function q mapping X to the reals, where D is an unknown data distribution over X.) Yet some data analysis algorithms rely on properties of functions that depend on multiple samples. Such algorithms would be naturally implemented using k-wise queries each of which is specified by a function q mapping X^k to the reals. Hence it is natural to ask whether algorithms using k-wise queries can solve learning problems more efficiently and by how much. Blum, Kalai and Wasserman (2003) showed that for any weak PAC learning problem over a fixed distribution, the complexity of learning with k-wise SQs is smaller than the (unary) SQ complexity by a factor of at most 2^k. We show that for more general problems over distributions the picture is substantially richer. For every k, the complexity of distribution-independent PAC learning with k-wise queries can be exponentially larger than learning with (k+1)-wise queries. We then give two approaches for simulating a k-wise query using unary queries. The first approach exploits the structure of the problem that needs to be solved. It generalizes and strengthens (exponentially) the results of Blum et al.. It allows us to derive strong lower bounds for learning DNF formulas and stochastic constraint satisfaction problems that hold against algorithms using k-wise queries. The second approach exploits the k-party communication complexity of the k-wise query function.