PaperlayerView exact revision on arXiv

Source-linked AI summary

Fitting and Learning Basis-Restricted Propositional Formulas

Balder ten Cate

arXiv:2609.08961v1cs.LOcs.LG

TL;DR

The paper asks how the choice of Boolean connectives affects the complexity of fitting and learning formulas. It classifies these tasks by basis, finding fitting uniformly tractable but other learning problems basis-dependent, and identifies unresolved questions for affine bases.

  • Problem

    The complexity of fitting and learning propositional formulas as the finite set of allowed Boolean connectives varies is scattered across prior classifications.

    Source: §1 · p. 1

  • Method

    The paper presents classifications by finite Boolean basis across fitting, Occam algorithms, empirical risk minimization, and PAC learning, for formulas and circuits.

    Source: §1 · p. 1

  • Results

    Fitting is polynomial-time for every fixed finite basis, while Occam algorithms and PAC learnability depend on the basis, and ERM falls into a three-way classification.

    Source: §1 · pp. 1–2

  • Takeaways & Limitations

    The classifications apply to both formulas and circuits, while some affine-basis questions and ERM for finite constraint-language fragments remain open.

    Source: §1 · p. 2, Open questions · p. 29

    For affine bases, attribute-efficient fitting and polynomial-time learning under random classification noise remain open; ERM boundaries for finite constraint-language fragments are also unresolved.

    Source: Empirical risk minimization · p. 4, Open questions · p. 29

Abstract

from arXiv · show

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.

1 Introduction

The paper organizes fitting and learning complexity by finite Boolean basis, contrasting uniformly tractable fitting with basis-dependent Occam, ERM, and learning results. Its main novel contributions include an efficient fitting construction, an ERM trichotomy, and extending a PAC-learnability dichotomy to formulas.

1 Introduction

  • The basis-generated results do not cover shape-restricted fragments such as Horn CNF; the paper discusses those fragments through Boolean constraint languages.Source: §1 · p. 1, Empirical risk minimization · p. 5
  • For every fixed finite basis, fitting is polynomial-time and returns a polynomial-size formula when the sample is realizable; the same holds for circuits.The construction uses a refinement of the Baker–Pixley theorem.Source: §1 · p. 2
  • Conjunction, disjunction, and negation bases have attribute-efficient Occam algorithms; an affine interval has an Occam algorithm but unresolved attribute efficiency, while other bases lack Occam algorithms under cryptographic assumptions.The same Occam classification holds for circuits.Source: §1 · p. 2

Empirical risk minimization.

  • ERM has a three-way basis classification: some intervals admit no weak approximation unless P = NP, another is approximable optimally under UGC, and all remaining cases are polynomial-time solvable.The same classification holds for circuits.Source: Empirical risk minimization · pp. 2–3
  • For conjunction, disjunction, or affine bases, VC dimension is at most n + 1; for other bases, it is 2^Ω(n).Source: Empirical risk minimization · p. 3
  • Proper PAC learnability and PAC prediction with membership queries coincide with the basis lying below conjunction, disjunction, or parity; the reverse implication requires cryptographic assumptions.The forward implications are unconditional, and the equivalence also holds for circuits.Source: Empirical risk minimization · pp. 3–4
  • Open questions include attribute-efficient learning and random-noise learning for affine bases, and exact or approximate ERM for finite constraint-language fragments.Source: Empirical risk minimization · p. 4

Organization

  • The paper proceeds from notation and fitting through ERM, VC dimension, PAC and Occam learning, noise and statistical queries, then constraint-language fragments.Source: Organization · p. 5

2 Preliminaries: Formulas, Circuits, Clones

The section defines formulas and circuits over a Boolean basis, then places the functions they compute within the structure of Boolean clones and Post’s lattice.

2 Preliminaries: Formulas, Circuits, Clones

  • A PLO-formula is a tree whose leaves are variables and whose internal nodes are connectives from the fixed basis; a CIRO-circuit allows shared subcomputations.Formula size counts nodes, while circuit size counts gates and inputs.Source: §2 · pp. 5, 8
  • A clone contains all projections and is closed under composition; [O] is the clone generated by O, comprising exactly the functions computable by its formulas or circuits.Post’s lattice orders Boolean clones by inclusion.Source: §2 · p. 5
  • Post’s lattice has countably many Boolean clones, each with a finite basis; Table 1 lists the clones and one basis for each.The table’s asterisks abbreviate families of clones and their subscripted variants.Source: §2 · p. 5, Table 1 · p. 7
  • Formula size can be exponentially larger than circuit size, although circuits in clones contained in E, V, or L can be translated into formulas with at most n + 2 leaves.Here E, V, and L correspond to conjunctions, disjunctions, and affine functions, respectively.Source: §2 · p. 8

3 Fitting

For every fixed finite Boolean basis, fitting is polynomial-time for formulas and circuits. The proof divides bases into structural cases, using local interpolation for near-unanimity operations and specialized constructions for other cases.

3 Fitting

  • For algebras with a near-unanimity term, realizability is determined by sub-samples of at most d − 1 examples, and a fitting term can be constructed with logarithmic depth.The refinement of Baker–Pixley interpolation controls the size and depth of the constructed term.Source: §3 · pp. 8–9
  • The near-unanimity construction checks each window of at most k examples in O(m^k n) time, then recursively combines smaller fitting terms into a polynomial-size formula.The recursion has depth O(log m) and polynomially many nodes.Source: §3 · p. 9
  • Every fixed finite basis admits a polynomial-time algorithm that tests realizability and returns a polynomial-size fitting formula when one exists; the result also holds for circuits.The cases in Post’s lattice are exhaustive, and a formula is a circuit of the same size.Source: §3 · pp. 9, 11
  • For affine clones, fitting reduces to linear equations over F2 solved by Gaussian elimination; the solution yields a formula with at most n + 2 leaves.The equations encode the affine function’s constant and variable support, with clone-specific conditions.Source: §3 · p. 10
  • For essentially unary clones, the algorithm tries available unary functions and constants; for semilattice clones, it uses a greedy conjunction or its disjunction dual.The semilattice construction keeps variables compatible with all positive labels, subject to truth-constant conditions.Source: §3 · p. 10
  • For ordinary separating clones, the construction reduces to a residual clone containing majority, then translates its fitting formula back using guarded gates.The translation preserves the guarded computation and yields a polynomial-size formula.Source: §3 · pp. 10–11

4 Empirical risk minimization

This section classifies empirical risk minimization by the generated clone for formulas and circuits, identifying regimes with no polynomial-time weak approximation, approximation guarantees, or polynomial-time solutions. It also presents objective-preserving vertex-cover reductions and algorithms that complete the classification across equivalent formula representations.

4.2 Finite-degree separating clones and the majority clone

  • Under the Unique Games Conjecture, the k-approximation guarantee for the finite-degree separating regime cannot be improved to k − ε for any ε > 0.The section relates the matching lower bounds to minimum vertex cover in k-uniform hypergraphs.Source: §4 · p. 11, §4.2 · p. 16

4 Empirical risk minimization

  • ERM for formulas and circuits is polynomial-time equivalent, with approximation ratios preserved, to finding a minimum-mistake relabeling realizable in the clone [O].Theorem 1.1 converts a realizable relabeling into a formula or circuit with exactly the same mistakes, explaining why the classification depends only on [O].Source: §4 · p. 12
  • Adjoining truth constants cannot make ERM harder, but it can make it easier: ERM for D2 is NP-hard whereas ERM for D2± = M is tractable.The reduction preserves sample size and gives a bijection between realizable relabelings with identical mistake counts.Source: §4 · pp. 12–13

4.1 The inapproximable cases

  • Unless P = NP, neither the affine-parity clone L nor the monotone conjunction and disjunction clones E and V admit polynomial-time weak approximators.The parity result follows from Max-E3Lin gap hardness; the E result is the monotone case, and V follows by Boolean duality.Source: §4.1 · pp. 13–14

4.2 Finite-degree separating clones and the majority clone

  • Finite-degree separating clones admit polynomial-time k-approximations, while the majority clone D2 admits a polynomial-time 2-approximation on arbitrary samples.For degree-k clones, the algorithm formulates realizable relabelings as an integer program and rounds a linear relaxation; the majority case uses a separate construction.Source: §4.2 · pp. 14–15
  • Minimum vertex cover in k-uniform hypergraphs reduces in polynomial time, preserving objective value, to ERM for the stated separating clones using samples with only one label.The optimum ERM mistake count equals the minimum vertex-cover size; the reduction uses negative-only samples or, on the 1-separating side, positive-only samples.Source: §4.2 · pp. 16–17
  • The factor k is optimal under the Unique Games Conjecture for ERM in the clones covered by the objective-preserving reduction.Because the reduction preserves the objective, the approximation results for minimum vertex cover transfer to ERM.Source: §4.2 · p. 17

4.3 The tractable cases

  • ERM is polynomial-time solvable for BF, R*, M*, S0*, S1*, D, D1, N*, and I*, using majority, minimum cut, forcing, or enumeration.For BF, pointwise majority gives an optimal relabeling; for M, the problem reduces to a minimum-cost upset solvable by one s–t min-cut.Source: §4.3 · pp. 17–18

4.4 Putting the pieces together

  • ERM is NP-hard and has no constant-factor approximation for the stated clones in the E, V, and L regimes, including clones below each regime’s top clone.The passage derives this by adjoining truth constants, which preserves sample size and every relabeling’s mistakes in the reduction to the top clone.Source: §4.4 · p. 19
  • The results account for all clones and extend from ERM for [O] to ERM for PLO and CIRO with approximation ratios preserved.The three regimes are combined with an enumeration of Post’s lattice to leave no clone unaccounted for.Source: §4.4 · p. 19

5 VC dimension

The section classifies the VC dimension of PLO by its connective basis: it grows linearly for three constant-augmented clones and exponentially otherwise.

5 VC dimension

  • For O ⪯ {∧, ⊤, ⊥}, {∨, ⊤, ⊥}, or {⊕, ⊤, ⊥}, VC dimension is at most n + 1; otherwise it is 2^Ω(n).Source: §5 · p. 19
  • Counting conjunction, disjunction, and affine-parity functions gives the upper bounds; subclones cannot increase these classes' VC dimensions.The n-ary parts of the conjunction and disjunction clones each have 2^n + 1 members; the affine-parity class has 2^(n+1) members.Source: §5 · p. 19
  • A 2^Ω(n)-point set is shattered by D2, S00, and S10: fixed coordinates simulate constants, and adjoining constants gives each clone M.The construction uses points with first coordinate 1, last coordinate 0, and the same number of ones.Source: §5 · pp. 19–20

6 PAC learning

The paper classifies PAC learning and prediction for formula fragments, including a uniform, representation-insensitive result and a representation-sensitive equivalence. Its proof supplies a missing reduction step for formulas, extending the PAC dichotomy from circuits to formulas.

Uniform learning

  • The uniform learner applies without a target-size promise, whereas the PAC and prediction notions in the equivalence depend on a representation-size bound.Uniform learning uses polynomially many examples in n, 1/ε, and 1/δ, with no dependence on target representation size.Source: §6 · p. 20
  • Outside the three positive basis conditions, VC dimension is 2^Ω(n), forcing exponentially many examples and exponential running time for uniform learning.In the positive cases, a uniform learner uses polynomially many examples and returns a formula with at most n + 2 leaves.Source: §6 · p. 20

PAC learning and prediction

  • The formula-side reduction repairs gate substitution by balancing source formulas and carrying truth constants with auxiliary variables.Without balancing, substitution can increase formula size by a constant factor per level; balancing makes the total increase polynomial.Source: §6 · p. 21
  • When the monotone clone M is definable, a reduction from unrestricted formulas to PLO follows by encoding negated variables and guarding inconsistent assignments.The reduction keeps depth logarithmic and resulting formula size polynomial; related reductions cover bases containing f∨∧, f∧∨, or maj under the stated self-duality condition.Source: §6 · pp. 21–22
  • Proper PAC learnability and PAC prediction with membership queries are equivalent to the three basis conditions; the converse holds under cryptographic assumptions.The equivalence also holds for circuits; the positive implications are unconditional.Source: §6 · pp. 23–24

7 Occam algorithms

Occam algorithms exist in specified basis regions, with a cryptographic hardness result outside them. The affine interval admits an Occam algorithm, but whether it can be attribute-efficient remains open.

Occam algorithms

  • For bases below conjunction, disjunction, or negation with constants, attribute-efficient Occam algorithms exist; otherwise outside the affine interval, Occam algorithms do not exist under cryptographic assumptions.The negative result also holds for circuits.Source: §7 · p. 24
  • For {⊕3} ⪯ O ⪯ {⊕, ⊤, ⊥}, an Occam algorithm exists, but attribute efficiency is unresolved.The fitting affine formula has at most n + 2 leaves, while controlling its support by the smallest fitting formula is open.Source: §7 · pp. 24–25
  • Greedy fitting in the conjunction and dual disjunction cases gives formula size O(sopt(E) log m), independent of n.For essentially unary bases, fitting hypotheses have size O(1).Source: §7 · p. 24
  • A sufficiently compressing fitting algorithm would yield a proper PAC learner, so the PAC classification rules out Occam algorithms outside the positive regions under cryptographic assumptions.The negative direction is proved for circuits, while positive results produce formulas.Source: §7 · pp. 24–25

8 Random label noise and statistical queries

Statistical-query learnability holds exactly for the conjunction, disjunction, and essentially unary regions under the paper's cryptographic assumptions. Kearns's simulation transfers the positive cases to random classification noise, but affine parity remains a distinct open case.

Statistical queries

  • Under cryptographic assumptions, statistical-query learning is possible exactly for bases below conjunction, disjunction, or negation with constants.The same classification holds for circuits.Source: §8 · p. 25

Random classification noise

  • Statistical-query learnability yields polynomial-time PAC learning under random classification noise for conjunctive, disjunctive, and essentially unary bases, for every η < 1/2.This follows from Kearns's simulation.Source: §8 · p. 25
  • For affine clones, the statistical-query lower bound does not rule out noisy learning: parities have a 2^O(n/log n)-time noisy learner, while polynomial time remains open.The statistical-query lower bound concerns exponentially many queries or exponentially small tolerance.Source: §8 · p. 25
  • Outside the PAC-learnable region, noise tolerance is excluded under the cryptographic assumptions because a noise-tolerant learner could run on noise-free examples.This negative transfer does not settle noisy learning for affine clones.Source: §8 · p. 25

9 Other kinds of fragments

The section extends fitting and learning questions to constraint-language fragments, including fragments not generated by connective sets. It finds tractable fitting and PAC-learning cases, alongside limits and unresolved boundaries.

9.1 Fragments given by constraint languages

  • For finite Γ, fitting is polynomial, a fitting formula can be found within a factor 1 + ln m of optimal, and CNFΓ is polynomially properly PAC learnable.Its VC dimension is at most |Γ| n^r, where r is the largest relation arity.Source: §9.1 · p. 26
  • For finite-template CNFΓ, the ERM boundary is unknown; CNF{True} has no polynomial-time weak approximator unless P = NP.The hardness applies independently of whether hypotheses are represented as formulas or circuits.Source: §9.1 · pp. 26–27
  • Monotone and Horn CNF have polynomial-time fitting, but their VC dimensions are exponential and proper PAC learning from random examples is hard unless NP = RP; membership queries permit proper PAC learning.Monotone CNF is not polynomially properly PAC learnable from random examples unless NP = RP, while membership queries permit it; the corresponding hardness transfers to Horn CNF.Source: §9.1 · p. 27
  • For affine systems over F2, fitting is polynomial, uses at most n atoms, and the VC dimension is n + 1, yielding polynomial proper PAC learning.The least concept containing the positive examples is their affine hull, computed by Gaussian elimination.Source: §9.1 · p. 27
  • Fitting CNFΓone is NP-hard by reduction from exact cover by 3-sets.The reduction encodes each set as a variable, each element as a positive example, and uses the zero vector as the negative example.Source: §9.1 · p. 27

9.2 Adding existential quantification

  • For any Γ, existence of a fitting ∃CNFΓ-formula is decidable in polynomial time, using closure of positive examples under Pol(Γ).This method does not guarantee a polynomial-size fitting ∃CNFΓ-formula: its witness is a term of Pol(Γ).Source: §9.2 · p. 28
  • For finite Γ, ∃CNFΓ is polynomially PAC predictable when Pol(Γ) contains a near-unanimity operation or affine operation; the near-unanimity case is properly learnable.The framework uses existential conjunctions, equality, and variable identification; the resulting concepts are the relations in the co-clone generated by Γ.Source: §9.2 · p. 28
  • Existentially quantified Horn clauses can encode arbitrarily long Horn clauses using a chain of existential variables, but the translation can expand a formula exponentially.A Horn CNF with m clauses translates into an ∃CNFΓHorn formula of O(mn) atoms; the converse translation can be exponential.Source: §9.2 · p. 29

Open questions

The paper leaves three questions open: attribute-efficient Occam bounds and random-noise PAC learning for an affine interval, and the ERM boundary for finite constraint languages.

Open questions

  • For the affine interval {⊕3} ⪯ O ⪯ {⊕, ⊤, ⊥}, whether the Occam algorithm can be made attribute-efficient remains open.The known bound depends on n, and it is unknown whether the fitted parity's support can be controlled by the smallest fitting formula's size.Source: Open questions · p. 29
  • For the same affine interval, polynomial-time PAC learnability under random classification noise remains open.The paper identifies this question with learning parity with noise.Source: Open questions · p. 29
  • For finite constraint-language fragments, the ERM boundary remains unknown for both exact solvability and approximability.Source: Open questions · p. 29
Loading 2609.08961v1…