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

• URL: http://arxiv.org/abs/2606.01107v1
• Date: Sun, 31 May 2026 08:59:30 GMT
• Title: How (and when) can you fit examples to logic-based hypothesis classes over infinite structures?
• Abstract summary: We focus on the computational and descriptive complexity of fitting for logically-defined classes in common decidable structures.<n>We use queries in a natural query language over the sample to determine whether a sample is fittable.
• Score: 2.012461155840431
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Fitting and Learning Basis-Restricted Propositional Formulas [2.436681150766912]
  We consider the class of propositional formulas built using the functions in $O$ as connectives.<n>We determine, for each possible choice of $O$, the complexity of various fitting and learning problems.
  arXiv  Detail & Related papers  (2026-09-08T16:15:00Z)
• Causally Evaluating the Learnability of Formal Language Tasks [59.73001113068827]
  We rigorously investigate the relationship between data frequency and learnability.<n>We derive Kullback-Leibler divergence metrics to measure the learnability of specific sub-tasks.<n>Our experiments show that evaluating learnability without causal intervention leads to incorrect conclusions.
  arXiv  Detail & Related papers  (2026-06-08T17:58:36Z)
• Strategic PAC Learnability via Geometric Definability [69.34283267701421]
  Strategic classification studies learning settings in which individuals can modify their features, at a cost, in order to influence the classifier's decision.<n>A central question is how the sample complexity of the induced (strategic) hypothesis class depends on the complexities of the underlying hypothesis class and the cost structure governing feasible manipulations.<n>We introduce structure via a geometric definability assumption: both the hypothesis class and the cost-induced neighborhood relation can be defined by first-order formulas over $mathbbR_mathttexp$.<n>We prove that learnability is preserved, with sample complexity controlled by the complexity
  arXiv  Detail & Related papers  (2026-05-13T12:21:56Z)
• Classical and Quantum Query Complexity of Boolean Functions under Indefinite Causal Order [0.8192907805418583]
  Computational models typically assume that operations are applied in a fixed sequential order.<n>Recent years several works have looked at relaxing this assumption, considering computations without any fixed causal structure.<n>No separation in exact query complexity has thus-far been found.
  arXiv  Detail & Related papers  (2025-06-05T16:00:36Z)
• A Compositional Atlas for Algebraic Circuits [35.95450187283255]
  We show that a large class of queries correspond to a combination of basic operators over semirings: aggregation, product, and elementwise mapping.<n>Applying our analysis, we derive novel tractability conditions for many such compositional queries.
  arXiv  Detail & Related papers  (2024-12-07T00:51:46Z)
• The Hardness of Reasoning about Probabilities and Causality [5.190207094732672]
  We study languages capable of expressing quantitative probabilistic reasoning and do-calculus reasoning for causal effects. The main contribution of this work is establishing the exact computational complexity of satisfiability problems. We introduce a new natural complexity class, named succ$exists$R, which can be viewed as a succinct variant of the well-studied class $exists$R.
  arXiv  Detail & Related papers  (2023-05-16T15:01:22Z)
• Amortized Inference for Causal Structure Learning [72.84105256353801]
  Learning causal structure poses a search problem that typically involves evaluating structures using a score or independence test. We train a variational inference model to predict the causal structure from observational/interventional data. Our models exhibit robust generalization capabilities under substantial distribution shift.
  arXiv  Detail & Related papers  (2022-05-25T17:37:08Z)
• Quantifying and Understanding Adversarial Examples in Discrete Input Spaces [70.18815080530801]
  We formalize a notion of synonymous adversarial examples that applies in any discrete setting and describe a simple domain-agnostic algorithm to construct such examples. Our work is a step towards a domain-agnostic treatment of discrete adversarial examples analogous to that of continuous inputs.
  arXiv  Detail & Related papers  (2021-12-12T16:44:09Z)
• Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers [50.85524803885483]
  This work proposes a formal definition of statistically meaningful (SM) approximation which requires the approximating network to exhibit good statistical learnability. We study SM approximation for two function classes: circuits and Turing machines.
  arXiv  Detail & Related papers  (2021-07-28T04:28:55Z)
• Conjunctive Queries: Unique Characterizations and Exact Learnability [0.0]
  We present a new efficient exact learning algorithm for a class of conjunctive queries. We also discuss implications for constructing frontiers in the homomorphism lattice of finite structures.
  arXiv  Detail & Related papers  (2020-08-16T02:54:56Z)
• An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
  We present a general framework for mining constraints from data. In particular, we consider the inference in structured output prediction as an integer linear programming (ILP) problem. We show that our approach can learn to solve 9x9 Sudoku puzzles and minimal spanning tree problems from examples without providing the underlying rules.
  arXiv  Detail & Related papers  (2020-06-18T20:09:53Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.