  We analyse the complexity of learning first-order definable concepts in a
model-theoretic framework for supervised learning introduced by (Grohe and
Tur\'an, TOCS 2004). Previous research on the complexity of learning in this
framework focussed on the question of when learning is possible in time
sublinear in the background structure.
  Here we study the parameterized complexity of the learning problem. We obtain
a hardness result showing that exactly learning first-order definable concepts
is at least as hard as the corresponding model-checking problem, which implies
that on general structures it is hard for the parameterized complexity class
AW[*]. Our main contribution is a fixed-parameter tractable agnostic PAC
learning algorithm for first-order definable concepts over effectively nowhere
dense background structures.
