从 Nisan 的自然证明中分布式 PAC-Learning

Oct, 2023

从 Nisan 的自然证明中分布式 PAC-Learning

Distributional PAC-Learning from Nisan's Natural Proofs

Ari Karchmer

TL;DR自然证明能够推导有效学习算法的条件在分布式 PAC 学习模型中得以推广，证明了我们的主要结果，以及对深度 - 2 多数电路、多面体和自然目标分布中的 DNFs 的分布式 PAC 学习算法的应用以及通过深度 - 2 多数电路评估的编码输入弱 PRF 的不存在性。

Abstract

(Abridged) Carmosino et al. (2016) demonstrated that natural proofs of circuit lower bounds for \Lambda imply efficient algorithms for learning \Lambda-circuits, but only over the uniform distribution, with membership queries, and provided \AC^0[p] \subseteq \Lambda. We consider whethe

natural proofs learning algorithms valiant's pac model distributional pac model depth-2 majority circuits

发现论文，激发创造

从平均情况复杂度到不当学习复杂度

这篇论文介绍了一种新的证明不适当学习难度的技术，基于难以处理的问题的规约，通过与密码假设相结合，发现了学习 $DNF$，半平面和超平面的交集等问题的困难性。

Nov, 2013

关于交互证明学习的能力

我们针对不均衡分布学习问题，构建了一种双效证明系统的交互式协议，该协议能够学习给定函数的最大傅立叶特征，学习类 AC^0 [2] 和 k-juntas。此外，我们还提供了一个用于布尔函数学习的新模型，样本复杂度与 n 无关。

Apr, 2024

本地量子电路输出分布的可学习性

本文研究了两种不同的神经网络模型下，量子电路 Born 机的可学习性，发现虽然当给定访问样本时可用于统计学习，但具有超对数深度的克里福德电路的输出分布在统计查询模型下不易于学习，这限制了学习本地量子电路输出分布的可能性，并提供了从概率建模角度学习本地量子电路输出分布的严格见解。

Oct, 2021

基于查询的 PAC 学习推理

本研究探讨了利用支持证明查询的数据集来学习规则的问题，通过修改足够不考虑知识库内容的后向证明搜索算法，可以同时学习这些规则，并使用它们进行证明搜索来给出像链接和解析这样的标准逻辑的算法。

Jun, 2019

分布式学习，通信复杂度和隐私

讨论分布式数据的 PAC 学习问题，分析了涉及的基本通信复杂性问题，包括教学维度和错误绑定。针对特定概念类别，如合取、奇偶函数和决策列表等，给出上下界限。讨论了如何通过增强来在分布式环境下进行一般性通信，以及如何在不确定环境下实现低通信回归。同时，还考虑了隐私性，包括差分隐私和分布式隐私。

Apr, 2012

多智体信仰的 PAC 语义学习性

此文介绍了使用多智能体认知逻辑演示 PAC 学习的技术基础，涉及逻辑和弱推理，以提供强大的模型理论框架来回答查询，并研究了该算法的正确性、样本复杂性以及其能够高效的情况，利用表述定理将模态推理纳入命题推理中。

Jun, 2023

私有的 PAC 学习可能比在线学习更困难

根据合理的密码学假设，我们展示了一个概念类别，该类别允许在多项式时间内以多项式错误边界运行的在线学习器，但不存在计算效率高的差异隐私 PAC 学习器。

Feb, 2024

一阶逻辑隐式学习推理

本文通过利用语言中常量的对称性，将隐式可学习性推广，提出了一种在第一阶逻辑中进行强健学习的新理论方法。

Jun, 2019

非均匀收敛下的最优 PAC 上界

本研究提出一种新的框架，超越了传统统一收敛方法的限制，将排列不变预测器的交叉检验误差转化为高概率风险界，并通过 Haussler, Littlestone, 和 Warmuth 的一种算法在二元分类中实现了最优 PAC 界限。在多类分类、部分假设分类和实现有限的回归等三种不同场合中，我们证明了该框架的优越性能。

Apr, 2023

PAC 学习的参量化理论

本文提出了一种参数化 PAC 学习理论，通过该理论可对 CNF、DNF 和图形学习等问题的可行性边界进行更精细的界定，并发展了机器学习领域的参数化固定参数学习的概念。

Apr, 2023