  We study Boolean classification problems over relational background
structures in the logical framework introduced by Grohe and Tur\'an (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.
