一句话：在可计算度量空间上定义二分类可计算 PAC 学习，刻画 ERM 可计算性，并给出无可计算 proper 学习器的反例。
本文研究连续特征空间上 PAC 学习的可计算性，弥补经典 PAC 理论通常忽略学习算法与样本函数可计算性这一问题。作者在可计算度量空间上定义二分类的可计算 PAC 学习，并给出假设类的充分条件，使得经验风险最小化器（ERM）是可计算的；在更一般的条件下，则用强 Weihrauch 度刻画 ERM 的可计算难度。作者还构造了一个假设类的表示：其底层假设类虽是 PAC 可学的，却不存在任何 proper 可计算 PAC 学习器且其样本函数可计算。该结果将可计算分析、Weihrauch 归约与学习理论联系起来。
We introduce definitions of computable PAC learning for binary classification over computable metric spaces. We provide sufficient conditions on a hypothesis class to ensure than an empirical risk minimizer (ERM) is computable, and bound the strong Weihrauch degree of an ERM under more general conditions. We also give a presentation of a hypothesis class that does not admit any proper computable PAC learner with computable sample function, despite the underlying class being PAC learnable.
@inproceedings{AckermanADFT22,
title = {Computable PAC Learning of Continuous Features},
author = {Nathanael Ackerman and Julian Asilis and Jieqi Di and Cameron Freer and Jean-Baptiste Tristan},
booktitle = {LICS},
year = {2022},
doi = {10.1145/3531130.3533330}
}