ora-0107

8.4 Finite PACC bounds

Let \(\overline{\mathbf H}=\mathbf H/{\simeq _{\mathcal Q}}\) be the quotient of the hypothesis class by its answers to all probes, and suppose it has \(N{\lt}\infty \) equivalence classes. First take zero–one discrepancy and assume the target class is realizable.

Theorem 8.4 Finite realizable PACC

If a learner returns a hypothesis consistent with every sampled probe, then

\[ m\; \geq \; \frac{\log N+\log (1/\delta )}{\epsilon } \]

implies that its categorical probe risk exceeds \(\epsilon \) with probability at most \(\delta \).

Proof ▼

A fixed hypothesis of risk greater than \(\epsilon \) agrees with one random probe with probability less than \(1-\epsilon \), hence survives all \(m\) independent probes with probability at most \((1-\epsilon )^m\leq e^{-m\epsilon }\). A union bound over at most \(N\) query-equivalence classes gives failure probability at most \(Ne^{-m\epsilon }\leq \delta \).

The theorem counts observationally distinct categorical worlds rather than raw syntactic presentations. It therefore rewards the quotient that UOCL was already required to state. When the target need not lie in the hypothesis class, consistency is replaced by empirical risk minimization.

Theorem 8.5 Finite agnostic PACC

Assume \(0\leq d_q\leq 1\), let \(\overline{\mathbf H}\) have \(N{\lt}\infty \) classes, and let \(\widehat{\mathcal C}\) minimize empirical categorical probe risk. With probability at least \(1-\delta \),

\[ \mathsf{Err}_{P,\mathcal Q}(\widehat{\mathcal C},\mathcal C_\star ) \leq \inf _{\mathcal C\in \mathbf H} \mathsf{Err}_{P,\mathcal Q}(\mathcal C,\mathcal C_\star ) +2\sqrt{\frac{\log (2N/\delta )}{2m}}. \]

In particular, \(m\geq 2\log (2N/\delta )/\epsilon ^2\) suffices for excess risk at most \(\epsilon \).

Proof ▼

Hoeffding’s inequality and a union bound imply simultaneous deviation at most \(\alpha =\sqrt{\log (2N/\delta )/(2m)}\) between empirical and population risk for every query-equivalence class. Empirical optimality inserts two such deviations between the selected hypothesis and the population optimum.

These bounds are intentionally elementary. Their purpose is to expose the new modeling obligation: statistical control is only as meaningful as the categorical probes and invariances used to define risk.