PAC

Creator

Creator

Created

Created

2023 Nov 20 6:52

Editor

Editor

Edited

Edited

2025 Jun 2 16:30

Refs

Refs

Hoeffding inequality

Model Generalization

Probabilistic Approximately Correct framework

In statistical learning theory, what's important is not the "average error" but rather the guarantee that "the error is small with high confidence". Therefore, we approach this by calculating the probability tail where the error exceeds a certain value. We introduce a

Confidence Parameter similar to the

p-value in

Significance Testing. This ensures that the probability of the learning result being sufficiently accurate (approximately correct) is guaranteed to be at least 1−δ

Empirical risk $R_{in} (h) = \frac{1}{m} \sum_i^{m} l(h(X_i), Y_i)$ where $h(X)$ is the predicted output

Theoretical risk $R_{out} (h) = \mathbb{E} [l(h(X), Y)]$

Generalization gap $\Delta(h) = R_{out} (h) - R_{in} (h)$

Upper bounds $\Delta(h) \le \epsilon(m, \delta)$ , $R_{out}(h) \le R_{in} (h) + \epsilon(m, \delta)$ with high probability

With high probability, the generalization error of an hypothesis

h

is at most something we can control and even compute. There is a probabilistic guarantee that the true error can be upper bounded by adding a margin

ϵ

to the training error.

\mathbb{P}[R_{out} \le R_{in}(h) + \epsilon(m, \delta)] \ge 1 - \delta

The generalization error of an hypothesis

h

is at most something we can control and even compute for any

\delta > 0

.

Prior $P$ here means exploration mechanism of $\mathcal{H}$

Posterior $Q$ here means the twisted prior after confronting with data

R_{\mathrm{in}}(Q) \equiv \int_H R_{\mathrm{in}}(h)\,dQ(h), R_{\mathrm{out}}(Q) \equiv \int_H R_{\mathrm{out}}(h)\,dQ(h)

Prototypical bound (McAllester, 1998, 1999)

Analysis of expected error over probability distribution Q instead of single hypothesis

h

.

R_{\text{out}}(Q) \le R_{\text{in}}(Q) + \sqrt{\frac{\mathrm{KL}(Q \| P) + \ln \frac{\xi(m)}{\delta}}{2m}}.

when think of

\epsilon(m, \delta)

as

\frac{Complexity + log{1}{\delta}}{\sqrt{m}}

.

Probabilistic Approximately Correct Notion

Confidence Parameter

PAC Bayes theorem

Hypothesis Sensitivity

Loss Sensitivity

PAC Bayes results

Localized PAC-Bayes

A Primer on PAC-Bayesian Learning

Generalised Bayesian learning algorithms are increasingly popular in machine learning, due to their PAC generalisation properties and flexibility. The present paper aims at providing a...

https://arxiv.org/abs/1901.05353

https://arxiv.org/pdf/2309.04381

A Primer on PAC-Bayesian Learning

PAC-Bayesian inequalities were introduced by McAllester (1998, 1999), following earlier remarks by Shawe-Taylor and Williamson (1997). The goal was to produce PAC-type risk bounds for Bayesian-flavored estimators. The acronym PAC stands for Probably Approximately Correct and may be traced back to Valiant (1984). This framework allows to consider not only classical Bayesian estimators, but rather any randomized procedure from a data-dependent distribution.

https://bguedj.github.io/icml2019/

Backlinks

Recommendations

///////