Learning algorithms from circuit lower bounds
Learning algorithms from circuit lower bounds
复制标题
从电路下界学习算法
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
J. Pich
中科院分区：
文献类型：
--
作者：
J. Pich
我们从构造性电路下界的各种概念重新审视有效学习算法的已知构造，例如破坏伪随机生成器的区分器或发现尝试计算硬函数的小电路的错误的有效见证算法。作为我们的主要结果，我们证明，如果能够以特定的交互方式有效地发现许多试图解决难题的 p 大小电路的错误，那么 p 大小电路可以通过次指数大小的电路通过成员查询通过均匀分布进行 PAC 学习。相反的含义也成立。这提供了学习算法的新特征，并扩展了 Razborov 和 Rudich 的自然证明障碍。该证明基于 Kraj\'{i}\v{c}ek (2010) 引入的利用 Nisan-Wigderson 生成器的方法，用于分析有界算术中电路下界的复杂性。根据电路下界学习算法的已知结构的一个有趣的结果是 Oliveira 和 Santhanam (2016) 的学习加速。我们提出了这种现象的另一种证明，并讨论了其推进硬度放大计划的潜力。
We revisit known constructions of efficient learning algorithms from various notions of constructive circuit lower bounds such as distinguishers breaking pseudorandom generators or efficient witnessing algorithms which find errors of small circuits attempting to compute hard functions. As our main result we prove that if it is possible to find efficiently, in a particular interactive way, errors of many p-size circuits attempting to solve hard problems, then p-size circuits can be PAC learned over the uniform distribution with membership queries by circuits of subexponential size. The opposite implication holds as well. This provides a new characterisation of learning algorithms and extends the natural proofs barrier of Razborov and Rudich. The proof is based on a method of exploiting Nisan-Wigderson generators introduced by Kraj\'{i}\v{c}ek (2010) and used to analyze complexity of circuit lower bounds in bounded arithmetic. An interesting consequence of known constructions of learning algorithms from circuit lower bounds is a learning speedup of Oliveira and Santhanam (2016). We present an alternative proof of this phenomenon and discuss its potential to advance the program of hardness magnification.
超越自然证据：硬度放大率和局部性
影响因子：
2.5
作者：
Chen L
通讯作者：
Chen L
了解 QBF 的 Gentzen 和 Frege 系统
DOI：
10.1145/2933575.2933597
发表时间：
2016
期刊：
--
影响因子：
--
作者：
Beyersdorff O
通讯作者：
Beyersdorff O