The uniform hardcore lemma via approximate Bregman projections
The uniform hardcore lemma via approximate Bregman projections
复制标题
通过近似 Bregman 投影得出的统一核心引理
DOI：
10.1137/1.9781611973068.129
复制
发表时间：
2009
影响因子：
3.9
通讯作者：
Satyen Kale
中科院分区：
文献类型：
--
作者：
B. Barak;Moritz Hardt;Satyen Kale
本文给出了复杂性理论中的一个基本结果--硬核引理的一个简单、有效和统一的证明，并将其应用于机器学习和密码学中。我们的结果源于Klivans和Servedio[11]发现的Boosting算法和硬核集合结构之间的联系。非正式地说，我们的结果如下：假设我们修复了一族布尔函数。假设有一个有效的算法，对于每个输入长度和输入上的每个平滑分布(即，不给任何单个输入分配太多权重的算法)，产生一个电路，使得该电路计算布尔函数明显好于随机。然后，有一个有效的算法，它为每一个输入长度产生一个电路，几乎在所有输入上都能正确地计算函数。
我们的算法大大简化了前人对一致和非一致硬核引理的证明，同时匹配或改进了以前最好的参数。该算法使用广义乘法更新规则和近似Bregman投影的自然概念相结合。Bregman投影在凸优化和机器学习中有着广泛的应用。当Kullback-Leibler散度作为距离函数时，我们提出了一种有效地将Bregman投影逼近到高密度度量集上的算法。我们的算法在任何域上都有一个对数运行时间，我们可以从中有效地进行采样。高密度度量对应于自然产生的平滑分布，例如，在在线学习的背景下。因此，我们的技术可能具有独立的意义。
We give a simple, more efficient and uniform proof of the hard-core lemma, a fundamental result in complexity theory with applications in machine learning and cryptography. Our result follows from the connection between boosting algorithms and hard-core set constructions discovered by Klivans and Servedio [11]. Informally stated, our result is the following: suppose we fix a family of boolean functions. Assume there is an efficient algorithm which for every input length and every smooth distribution (i.e. one that doesn't assign too much weight to any single input) over the inputs produces a circuit such that the circuit computes the boolean function noticeably better than random. Then, there is an efficient algorithm which for every input length produces a circuit that computes the function correctly on almost all inputs.
Our algorithm significantly simplifies previous proofs of the uniform and the non-uniform hard-core lemma, while matching or improving the previously best known parameters. The algorithm uses a generalized multiplicative update rule combined with a natural notion of approximate Bregman projection. Bregman projections are widely used in convex optimization and machine learning. We present an algorithm which efficiently approximates the Bregman projection onto the set of high density measures when the Kullback-Leibler divergence is used as a distance function. Our algorithm has a logarithmic runtime over any domain from which we can efficiently sample. High density measures correspond to smooth distributions which arise naturally, for instance, in the context of online learning. Hence, our technique may be of independent interest.