# On the Parameterized Complexity of Learning First-Order Logic

arXiv: https://arxiv.org/abs/2102.12201 · HTML: https://mlsanity.com/paper/2102.12201/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Feb 2021.

## Built on by (most cited first, 1 of 1)

- [A Parameterized Theory of PAC Learning](https://mlsanity.com/paper/2304.14058/) (2023)

## Abstract (arXiv)

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).