# Learning first-order definable concepts over structures of small degree

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Jan 2017.

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

- [How (and when) can you fit examples to logic-based hypothesis classes over infinite structures?](https://mlsanity.com/paper/2606.01107/) (2026)

## Abstract (arXiv)

We consider a declarative framework for machine learning where concepts and hypotheses are defined by formulas of a logic over some background structure. We show that within this framework, concepts defined by first-order formulas over a background structure of at most polylogarithmic degree can be learned in polylogarithmic time in the "probably approximately correct" learning sense.