论文标题
迈向有限记忆学习的组合表征
Towards a combinatorial characterization of bounded memory learning
论文作者
论文摘要
组合维度在机器学习理论中起着重要作用。例如，VC维度表征PAC学习，SQ维度通过统计查询来表征弱学习，而Littlestone维度则表征了在线学习。 在本文中，我们旨在开发表征有限记忆学习的组合维度。我们根据相邻分布的SQ维度提出了一个可在已知分布下可实现的强大学习情况的候选解决方案。我们证明了我们的候选解决方案的上限和下限，这些解决方案匹配某些参数。在此参数方面，有限内存和SQ学习之间存在等效性。我们猜想我们的表征在更广泛的参数方面存在。
Combinatorial dimensions play an important role in the theory of machine learning. For example, VC dimension characterizes PAC learning, SQ dimension characterizes weak learning with statistical queries, and Littlestone dimension characterizes online learning. In this paper we aim to develop combinatorial dimensions that characterize bounded memory learning. We propose a candidate solution for the case of realizable strong learning under a known distribution, based on the SQ dimension of neighboring distributions. We prove both upper and lower bounds for our candidate solution, that match in some regime of parameters. In this parameter regime there is an equivalence between bounded memory and SQ learning. We conjecture that our characterization holds in a much wider regime of parameters.
