Uniform-distribution PAC learning of DNF

An unknown rule says yes when either “A is on and B is off” or “C is on.” This is a DNF rule: several combinations joined by “or,” with the conditions inside each combination joined by “and.” A learner sees random switch settings and their correct yes/no labels, rather than the rule itself. All eight settings of these three switches are equally likely. Can a classical computer efficiently learn to predict every compact rule of this kind, to a chosen error tolerance and confidence, using only such ordinary random examples? The learned predictor may use a different representation from the hidden rule.[1] [2] [3]

Can a classical learner predict every small DNF accurately from uniform random labeled settings in polynomial time? A DNF is an “or” of terms, each an “and” of variables or their negations. For instance,$$f(a,b,c)=(a\land\neg b)\lor c$$has two terms. Of the eight equally likely inputs, $f$ is true on five; the predictor $h(a,b,c)=c$ errs only at $(1,0,0)$, so its uniform error is $1/8$. This tiny rule illustrates population error, not an algorithm for arbitrary DNF. For $n$ bits and a target with $s$ terms, the learner receives independent examples $(x,f(x))$, with $x$ uniformly distributed on $\{0,1\}^n$ and no label noise. It must output an efficiently evaluatable hypothesis $h$ such that$$\Pr_x[h(x)\ne f(x)]\le\varepsilon$$with probability at least $1-\delta$ over the training process. Here $\varepsilon$ is the error tolerance and $\delta$ the allowed chance of an unsuccessful training run. Seek time polynomial in $n,s,1/\varepsilon,\log(1/\delta)$. PAC learning means probably approximately correct learning; the uniform distribution is fixed, and no chosen-input membership queries or quantum example oracle are supplied.[1] [2] [3]

For uniform ordinary examples, polynomial-time learning remains unknown.[1] [2]

Known quasipolynomial learning and the reviewed distribution-shift preprint do not supply this algorithm.[1] [2]

A short rule need not be easy to discover from examples. This problem isolates that computational obstacle in a clean setting: correct labels, a known sampling distribution, and a target built from simple alternative conditions. The goal is reliable prediction on new settings, rather than merely memorizing the training examples or recovering the author’s exact formula. It asks when compact structure can actually be turned into efficient learning.[1] [2]

A compact DNF gives an efficient prediction method to someone who already knows it. Learning asks whether that benefit can be obtained efficiently from examples, while allowing a differently represented hypothesis. This exposes the gap between description length and computational accessibility of a rule. The cited distribution-shift work compares ordinary quasipolynomial PAC bounds with a model that receives unlabeled test examples and can abstain. That comparison helps identify what the basic learning task requires: a predictor with small overall uniform error, rather than selected reliable answers that leave other inputs unanswered.[1] [2]