提出两种新维度，完整刻画列表回归的样本复杂度。
A Characterization of List Regression
- 引入k-OIG维和k-fat-shattering维两个组合维度。
- 分别精确表征可实现与非可实现场景下的列表回归复杂度。
- 将列表学习理论从分类拓展至回归，适合理论研究者。
近期研究关注列表学习任务的样本复杂度，允许学习算法输出长度为k的预测列表，只要其中一个正确即可。本文对列表PAC回归进行了完整刻画，提出了两个组合维度：k-OIG维和k-fat-shattering维，分别对应可实现与非可实现场景下的列表回归。这些量推广了标准回归中的已知维度，首次将列表学习的理论分析从分类扩展到回归，推动了该领域的统一理解。
原文摘要 · Abstract (English)
There has been a recent interest in understanding and characterizing the sample complexity of list learning tasks, where the learning algorithm is allowed to make a short list of $k$ predictions, and we simply require one of the predictions to be correct. This includes recent works characterizing the PAC sample complexity of standard list classification and online list classification. Adding to this theme, in this work, we provide a complete characterization of list PAC regression. We propose two combinatorial dimensions, namely the $k$-OIG dimension and the $k$-fat-shattering dimension, and show that they characterize realizable and agnostic $k$-list regression respectively. These quantities generalize known dimensions for standard regression. Our work thus extends existing list learning characterizations from classification to regression.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。