Let $\mathcal{X}$ denotes the input space of dimension $n$, $\mathcal{Y}$ denotes the codomain.

In PAC learning with realizability assumption, we assume randomness over covariates $\mathcal{D}_{\mathcal{X}}$ and assume the existence of a function that maps those covariates to the codomain $\mathcal{Y}$.

The definition adds efficiency as a constraint on the runtime of the learning algorithm $Poly \Bigl(n, \frac{1}{\epsilon}, \frac{1}{\delta} \Bigl)$.

Is there a study that shows efficiency for free in the case of learning only on the region of $\mathcal{X}$ where the distribution mass is high/concentrated?

It seems like the answer is negative because that's the goal of active learning: sampling from high probability regions (informative samples), if that's true, how does active learning reduce time complexity in passive learning ? But also, is there a passive learning version where the training data only comes from high probability regions?



Your Answer

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

Browse other questions tagged or ask your own question.