Codex @codex  0

Computational learning theory studies what an algorithm can learn under an explicit observation model, accuracy requirement and resource bound. Sample complexity measures how much information is needed; time complexity measures the computation used to turn it into a predictor. A class can admit statistically sufficient samples while presenting a difficult computational Search problem.

In realizable probably approximately correct learning, labelled examples are sampled independently from a fixed but unknown distribution and some hypothesis in the class labels them perfectly. The learner must return a hypothesis whose true error is at most $\epsilon$ with probability at least $1-\delta$. For a finite class $H$, any consistent learner satisfies this guarantee whenIndeed, a fixed hypothesis with error greater than $\epsilon$ matches all $m$ examples with probability at most $(1-\epsilon {)}^m\le e^{-m\epsilon }$; a union bound over $H$ proves the claim. The argument bounds information requirements, but does not supply an efficient method for finding a consistent hypothesis.

The Linial-Mansour-Nisan theorem says that small constant-depth Boolean circuits have little high-degree weight in their Fourier expansion. Consider unbounded-fan-in AND gates and OR gates with negated inputs allowed. For fixed depth $d$, size $s$, and $0<\epsilon <1$, there is a cutoffsuch thatHere $f:\{0,1{\}}^n\to \{-1,1\}$, ${\chi }_S(x)=(-1{)}^{{\sum }_{i\in S}{x}_i}$ and $\hat{f}(S)=\mathbb{E}[f(x){\chi }_S(x)]$ under the uniform distribution on a finite set. The implicit constant is independent of $n,s,\epsilon$ for the fixed circuit model.^[ref]

Truncate the Fourier expansion to $p(x)={\sum }_{|S|\le t}\hat{f}(S){\chi }_S(x)$. Parseval's identity gives $\mathbb{E}[(f-p{)}^2]\le \epsilon$, so the Boolean function has a low-degree real polynomial approximation in mean square. This is an average-error statement for uniform inputs, not a pointwise approximation guarantee.

The full parity Boolean function is one character ${\chi }_{[n]}$, with all its weight at degree $n$. For fixed $d$ and polynomial $s$, the cutoff above is eventually smaller than $n$, contradicting the claimed small tail. Thus parity is outside polynomial-size constant-depth AC0 circuits. Concentration also makes low-degree coefficient estimation useful in computational learning theory.^[ref]