用模拟器学习复杂依赖数据，也能达到独立数据的最优误差界。
Learning with Simulators: No Regret in a Computationally Bounded World
- 通过可模拟过程框架，利用模拟器逼近复杂依赖数据分布。
- 算法在任意可多项式时间模拟的过程中，实现与VC维相关的误差上界。
- 适用于受限计算环境下的学习，对理论研究者和算法设计者有启发。
理解泛化所需的最小假设是学习理论的核心问题。然而，大多数结果严重依赖数据生成过程的独立性（或其近似），而对强相关数据的结果仍十分有限。为填补这一空白，我们提出可模拟过程框架：学习者可访问一个能近似真实数据分布的模拟器（该分布可为任意复杂且高度依赖的过程）。令人惊讶的是，在此框架下，我们可恢复经典独立数据设置中的学习保证，即误差界仅依赖于VC维。此外，我们利用该框架研究条件采样的能力，揭示其在统计与计算上的显著优势。作为框架亮点，我们提出一种单一算法，可在所有多项式时间可模拟的过程中学习任意给定的VC类，其遗憾由该过程的时间有界柯尔莫哥洛夫复杂度控制。这实现了对经典PAC模型的重要概念拓展。
原文摘要 · Abstract (English)
Understanding the minimal assumptions necessary for generalization is the fundamental question in learning theory. Unfortunately, most results rely heavily on independence (or some proxy thereof) of the data-generating process, while results for strongly dependent data are far more limited. Towards addressing this gap, we introduce the framework of simulatable processes, where the learner has access to a simulator that approximates the distribution generating the data (which may be an arbitrarily complex and dependent process). Surprisingly, given access to such a simulator, we show that we can recover the same learning guarantees as in the classical setting with independent data, namely, error bounds that depend on the VC dimension. Further, we use this framework to study the power of conditional sampling and show strict statistical and computational advantages in this setting. As a highlight of our framework, we exhibit a single algorithm that simultaneously learns any given VC class under all processes samplable in bounded polynomial time, with regret controlled by the time-bounded Kolmogorov complexity of the process. This provides a significant conceptual broadening of the classical PAC model.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。