0
$\begingroup$

The following problem is motivated by the one here from more than half a decade ago:

Let $C$ be a concept class that is efficiently proper PAC-learnable, i.e. there exists a learning algorithm that outputs $h \in C$, such that $\mathrm{err}(h) \leq \epsilon$, in addition to the usual PAC-guarantees. Suppose that this same class $C$ is PAC-learnable in the presence of random classification noise, but that the learning algorithm for $C$ in this setting. Show that $C$ is also proper PAC-learnable in the presence of random classification noise.

In the standard setting without noise, the existence of an efficient proper PAC-learning algorithm for the class $C$ implies that we can find a hypothesis $h \in C$ with an error rate of at most $\epsilon$. However, when introducing random classification noise, the challenge is that the labels of the instances may be flipped with some probability, say $\eta$, which complicates the learning process.

My initial approach was to adapt the standard learning algorithm for $C$ to account for the noise. I considered techniques such as noise-tolerant variants of the algorithm or methods to estimate and correct the flipped labels. However, I am uncertain about how to guarantee that the modified algorithm still outputs a hypothesis from the class $C$ (thus ensuring proper learning) while maintaining the error rate within the desired bounds. I'd appreciate any help.

$\endgroup$

1 Answer 1

0
$\begingroup$

Let's put questions of efficiency aside -- these are orthogonal to generalization and depend on complexity-theoretic assumptions.

PAC learnability is characterized (modulo very mild measure-theoretic assumptions, which we'll ignore here) by a finite VC-dimension. If you have a shattered set of size $d$ and a uniform distribution on those $d$ points, whenever your sample size $n<d$, you have no information about the labels of the remaining $d-n$ unseen points. Hence finite VC-dim is necessary even for realizable (noiseless) PAC.

That finite VC-dim is sufficient even in the noisy case follows from the general Rademacher bound + Sauer's lemma. You'll find it in any ML theory book, such as Mohri, Rostamizadeh, Talwalkar. Note that learnability here means not small error but small excess error.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.