# How (and when) can you fit examples to logic-based hypothesis classes over infinite structures?

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 51 references that are in the map.
- First posted on arXiv 31 May 2026.

## Builds on (most cited first, 8 of 8)

- [Understanding Deep Neural Networks with Rectified Linear Units](https://mlsanity.com/paper/1611.01491/) (2016)
- [Tight Hardness Results for Training Depth-2 ReLU Networks](https://mlsanity.com/paper/2011.13550/) (2020)
- [Training Neural Networks is NP-Hard in Fixed Dimension](https://mlsanity.com/paper/2303.17045/) (2023)
- [Training Fully Connected Neural Networks is existsℝ-Complete](https://mlsanity.com/paper/2204.01368/) (2022)
- [Complexity of Neural Network Training and ETR: Extensions with Effectively Continuous Functions](https://mlsanity.com/paper/2305.11833/) (2023)
- [From learnable objects to learnable random objects](https://mlsanity.com/paper/2504.00847/) (2025)
- [Learning first-order definable concepts over structures of small degree](https://mlsanity.com/paper/1701.05487/) (2017)
- [Embedded Finite Models Beyond Restricted Quantifier Collapse](https://mlsanity.com/paper/2304.09231/) (2023)

## Abstract (arXiv)

We study fitting problems, sometimes called ``training problems'', where we have a finite sample consisting of inputs and outputs, and we want to know whether there is a function in a certain class that could produce these outputs, exactly or approximately, on the given inputs. We focus on the computational and descriptive complexity of fitting for logically-defined classes in common decidable structures, like the real ordered field and Presburger arithmetic, and also for broader classes defined via combinatorial or model-theoretic properties. We isolate the complexity of these fitting problems, with particular attention to cases where we can use queries in a natural query language over the sample to determine whether a sample is fittable.