11:58
官方账号arXiv cs.LG@Jon Kleinberg, Amin Saberi, Xizhi Tan, Grigoris Velegkas
推荐理由：你想知道从多个供应商凑数据学分布有多难吗？这篇论文给出了从线性到二次的完整样本复杂度图谱，还找到了层次可比性这个好用的结构条件。
共现图
共 1 条相关 AI 资讯
7月28日
11:58
本文研究在有限域[n]上从多个数据提供者学习未知分布p的问题，每个查询返回条件分布p(·|S)的独立样本。可学习性由查询集的共现图决定：当图在目标支撑上连通时可达点态一致性，完全图时可达PAC学习。PAC学习的最优样本复杂度范围从近线性到二次：完全共现图族复杂度为Õ(n²/ε²)，紧界；当[n]本身可查询时复杂度为Θ(n/ε²)，即使所有子集可查询也无法改进。作者识别了层次可比性作为近线性复杂度（Õ(n/ε²)）的充分条件，并展示对于每个α∈(1,2)存在查询族达到最优PAC率Θ(n^α/ε²)。