  We analyse the complexity of learning first-order queries 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 have
two main results. The first is a hardness result, showing that learning
first-order queries 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 second main contribution is a
fixed-parameter tractable agnostic PAC learning algorithm for first-order
queries over sparse relational data (more precisely, over nowhere dense
background structures).
