研究函数类学习能力如何传递到其随机组合形式，揭示理论边界。
From learnable objects to learnable random objects
- 从基础函数类推导统计函数类的学习性，建立理论框架。
- 在非可实现场景下，用组合维数改进样本复杂度上界。
- 连接模型论中的结构随机化技术，给出反例警示理论局限。
我们研究集合 $X$ 上一个“基础函数类”的可学习性与由该类衍生的统计函数类之间的关系。例如，我们改进了已有结果：若一族函数 $h_p: p o Y$ 可学习，则其对应的期望函数 $h_μ = λp: Y. E_μ(h_p)$（其中 $E_μ$ 是关于概率分布 $μ$ 的期望）也可学习，且 $μ$ 在 $X$ 上的概率分布中变化。研究覆盖了概率近似正确（PAC）学习（输入输出随机选取）和在线学习（输入由对手选择）两种设定。对于非可实现学习，我们基于基础类的组合维数，给出了更优的样本复杂度上界。这些结果与模型论中“结构随机化”技术相关联。同时，在可实现学习情形下，我们在PAC和在线设置中分别构造了反例。
原文摘要 · Abstract (English)
We consider the relationship between learnability of a "base class" of functions on a set $X$, and learnability of a class of statistical functions derived from the base class. For example, we refine results showing that learnability of a family $h_p: p \in Y$ of functions implies learnability of the family of functions $h_μ=λp: Y. E_μ(h_p)$, where $E_μ$ is the expectation with respect to $μ$, and $μ$ ranges over probability distributions on $X$. We will look at both Probably Approximately Correct (PAC) learning, where example inputs and outputs are chosen at random, and online learning, where the examples are chosen adversarily. For agnostic learning, we establish improved bounds on the sample complexity of learning for statistical classes, stated in terms of combinatorial dimensions of the base class. We connect these problems to techniques introduced in model theory for "randomizing a structure". We also provide counterexamples for realizable learning, in both the PAC and online settings.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。