一句话：将一阶逻辑可定义分类器的亚线性学习推广到带计数一阶逻辑 FOCN，并证明无界度下不可亚线性学习。
论文研究关系背景结构上的布尔分类问题，沿用 Grohe 与 Turán 提出的逻辑学习框架。已有工作表明，在度为多对数级的一阶可定义分类器可在亚线性时间内学习。本文把该结果推广到带计数的一阶逻辑 FOCN：证明在度为多对数级的结构类上，FOCN 可定义分类器可被一致地亚线性学习；并将结果扩展到度至多 (log log n)^c 的结构类上的 agnostic PAC 学习。最后，作者证明度为无界时，即使分类器仅由普通一阶逻辑定义，也不存在亚线性时间学习算法，表明度约束对亚线性可学习性至关重要。
We study Boolean classification problems over relational background structures in the logical framework introduced by Grohe and Turán (TOCS 2004). It is known (Grohe and Ritzert, LICS 2017) that classifiers definable in first-order logic over structures of polylogarithmic degree can be learned in sublinear time, where the degree of the structure and the running time are measured in terms of the size of the structure. We generalise the results to the first-order logic with counting FOCN, which was introduced by Kuske and Schweikardt (LICS 2017) as an expressive logic generalising various other counting logics. Specifically, we prove that classifiers definable in FOCN over classes of structures of polylogarithmic degree can be consistently learned in sublinear time. This can be seen as a first step towards extending the learning framework to include numerical aspects of machine learning. We extend the result to agnostic probably approximately correct (PAC) learning for classes of structures of degree at most $(\log \log n)^c$ for some constant $c$. Moreover, we show that bounding the degree is crucial to obtain sublinear-time learning algorithms. That is, we prove that, for structures of unbounded degree, learning is not possible in sublinear time, even for classifiers definable in plain first-order logic.