Fitting and Learning Basis-Restricted Propositional Formulas

• URL: http://arxiv.org/abs/2609.08961v1
• Date: Tue, 08 Sep 2026 16:15:00 GMT
• Title: Fitting and Learning Basis-Restricted Propositional Formulas
• Abstract summary: 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.
• Score: 2.436681150766912
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: For a finite set $O$ of Boolean functions, we consider the class of propositional formulas built using the functions in $O$ as connectives. We determine, for each possible choice of $O$, the complexity of various fitting and learning problems. These include: finding a formula that fits a given labeled sample, finding a small one (an Occam algorithm), minimizing the number of misclassified examples when the sample is not realizable (empirical risk minimization), and several forms of PAC learning. Our results apply both to formulas (represented as trees) and to circuits. We also briefly discuss the status of the same questions for other kinds of propositional fragments.

Related papers

• How (and when) can you fit examples to logic-based hypothesis classes over infinite structures? [2.012461155840431]
  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.
  arXiv  Detail & Related papers  (2026-05-31T08:59:30Z)
• 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)
• Learning Compositional Functions with Transformers from Easy-to-Hard Data [63.96562216704653]
  We study the learnability of the $k$-fold composition task, which requires computing an interleaved composition of $k$ input permutations and $k$ hidden permutations.<n>We show that this function class can be efficiently learned, with runtime and sample in $k$, by gradient descent on an $O(log k)$-depth transformer.
  arXiv  Detail & Related papers  (2025-05-29T17:22:00Z)
• Homomorphisms and Embeddings of STRIPS Planning Models [4.594173051888471]
  We show that the first is GI-complete, and can thus be solved, in theory, in quasi-polynomial time. While we prove the remaining problems to be NP-complete, we propose an algorithm to build an isomorphism, when possible.
  arXiv  Detail & Related papers  (2024-06-24T11:43:18Z)
• Optimal Multi-Distribution Learning [88.3008613028333]
  Multi-distribution learning seeks to learn a shared model that minimizes the worst-case risk across $k$ distinct data distributions.<n>We propose a novel algorithm that yields an varepsilon-optimal randomized hypothesis with a sample complexity on the order of (d+k)/varepsilon2.
  arXiv  Detail & Related papers  (2023-12-08T16:06:29Z)
• Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise [50.64137465792738]
  We study the problem of PAC $gamma$-margin halfspaces with Random Classification Noise. We establish an information-computation tradeoff suggesting an inherent gap between the sample complexity of the problem and the sample complexity of computationally efficient algorithms.
  arXiv  Detail & Related papers  (2023-06-28T16:33:39Z)
• A Fast Algorithm for the Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [55.2480439325792]
  We study the real-valued pure exploration problem in the multi-armed bandit (R-CPE-MAB)<n>We introduce an algorithm named the gap-based exploration (CombGapE) algorithm, whose sample complexity upper bound matches the lower bound up to a problem-dependent constant factor.<n>We numerically show that the CombGapE algorithm outperforms existing methods significantly in both synthetic and real-world datasets.
  arXiv  Detail & Related papers  (2023-06-15T15:37:31Z)
• On-Demand Sampling: Learning Optimally from Multiple Distributions [63.20009081099896]
  Social and real-world considerations have given rise to multi-distribution learning paradigms. We establish the optimal sample complexity of these learning paradigms and give algorithms that meet this sample complexity. Our algorithm design and analysis are enabled by our extensions of online learning techniques for solving zero-sum games.
  arXiv  Detail & Related papers  (2022-10-22T19:07:26Z)
• Active Learning for Contextual Search with Binary Feedbacks [2.6424064030995957]
  We study the learning problem in contextual search motivated by applications such as first-price auction. We propose a tri-section search approach combined with a margin-based active learning method.
  arXiv  Detail & Related papers  (2021-10-03T19:05:29Z)
• Bilinear Classes: A Structural Framework for Provable Generalization in RL [119.42509700822484]
  Bilinear Classes is a new structural framework which permits generalization in reinforcement learning. The framework incorporates nearly all existing models in which a sample complexity is achievable. Our main result provides an RL algorithm which has sample complexity for Bilinear Classes.
  arXiv  Detail & Related papers  (2021-03-19T16:34:20Z)
• A Provably Efficient Sample Collection Strategy for Reinforcement Learning [123.69175280309226]
  One of the challenges in online reinforcement learning (RL) is that the agent needs to trade off the exploration of the environment and the exploitation of the samples to optimize its behavior. We propose to tackle the exploration-exploitation problem following a decoupled approach composed of: 1) An "objective-specific" algorithm that prescribes how many samples to collect at which states, as if it has access to a generative model (i.e., sparse simulator of the environment); 2) An "objective-agnostic" sample collection responsible for generating the prescribed samples as fast as possible.
  arXiv  Detail & Related papers  (2020-07-13T15:17:35Z)
• Faster PAC Learning and Smaller Coresets via Smoothed Analysis [25.358415142404752]
  PAC-learning usually aims to compute a small subset ($varepsilon$-sample/net) from $n$ items. Inspired by smoothed analysis, we suggest a natural generalization: approximate the emphaverage (instead of the worst-case) error over the queries.
  arXiv  Detail & Related papers  (2020-06-09T18:25:34Z)
• Theory and Algorithms for Shapelet-based Multiple-Instance Learning [5.08418565337126]
  We propose a new formulation of Multiple-Instance Learning (MIL), in which a unit of data consists of instances called a bag. The goal is to find a good classifier of bags based on the similarity with a "shapelet" (or pattern) In our formulation, we use all possible, and thus infinitely many shapelets, resulting in a richer class of classifiers.
  arXiv  Detail & Related papers  (2020-05-31T17:10:59Z)

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.