论文标题
部分可观测时空混沌系统的无模型预测
Comparative Learning: A Sample Complexity Theory for Two Hypothesis Classes
论文作者
论文摘要
在许多学习理论问题中，假设类别扮演着核心角色：我们可以假设数据是根据班级中的假设标记的（通常称为可实现的设置），或者我们可以通过将学习模型与班级中的最佳假设进行比较（不可知的环境）来评估该模型。 Taking a step beyond these classic setups that involve only a single hypothesis class, we introduce comparative learning as a combination of the realizable and agnostic settings in PAC learning: given two binary hypothesis classes $S$ and $B$, we assume that the data is labeled according to a hypothesis in the source class $S$ and require the learned model to achieve an accuracy comparable to the best hypothesis in the benchmark class $B$.即使$ s $和$ b $都具有无限的VC维度，比较学习仍然可以具有较小的样本复杂性。我们表明，比较学习的样本复杂性的特征是相互VC维度$ \ Mathsf {vc}（s，b）$，我们将其定义为$ s $和$ b $损坏的子集的最大尺寸。我们还在在线环境中显示出类似的结果，在该环境中，我们以相互利用的尺寸$ \ mathsf {ldim}（s，s，b）$表示遗憾的特征。这些结果也适用于部分假设。 我们还表明，可以使用比较学习的样品复杂性所必需的见解来表征可实现的多辅助性的样品复杂性和使用共同脂肪的尺寸，这是相互vc维度的类似物，用于实现的假设。这不仅解决了HU，Peale，Reingold（2022）提出的一个开放问题，而且还导致了独立有趣的结果，该结果将有关回归，增强和覆盖数量的经典结果扩展到我们的两种高素质级环境。
In many learning theory problems, a central role is played by a hypothesis class: we might assume that the data is labeled according to a hypothesis in the class (usually referred to as the realizable setting), or we might evaluate the learned model by comparing it with the best hypothesis in the class (the agnostic setting). Taking a step beyond these classic setups that involve only a single hypothesis class, we introduce comparative learning as a combination of the realizable and agnostic settings in PAC learning: given two binary hypothesis classes $S$ and $B$, we assume that the data is labeled according to a hypothesis in the source class $S$ and require the learned model to achieve an accuracy comparable to the best hypothesis in the benchmark class $B$. Even when both $S$ and $B$ have infinite VC dimensions, comparative learning can still have a small sample complexity. We show that the sample complexity of comparative learning is characterized by the mutual VC dimension $\mathsf{VC}(S,B)$ which we define to be the maximum size of a subset shattered by both $S$ and $B$. We also show a similar result in the online setting, where we give a regret characterization in terms of the mutual Littlestone dimension $\mathsf{Ldim}(S,B)$. These results also hold for partial hypotheses. We additionally show that the insights necessary to characterize the sample complexity of comparative learning can be applied to characterize the sample complexity of realizable multiaccuracy and multicalibration using the mutual fat-shattering dimension, an analogue of the mutual VC dimension for real-valued hypotheses. This not only solves an open problem proposed by Hu, Peale, Reingold (2022), but also leads to independently interesting results extending classic ones about regression, boosting, and covering number to our two-hypothesis-class setting.
