Questions tagged [sample-complexity]

For questions related to the sample complexity of a machine learning algorithm, which represents the number of training-samples that it needs in order to successfully learn a target function. More precisely, the sample complexity is the number of training-samples that we need to supply to the algorithm, so that the function returned by the algorithm is within an arbitrarily small error of the best possible function, with probability arbitrarily close to 1.

Filter by
Sorted by
Tagged with
1
vote
0answers
44 views

Is it better to split sequences into overlapping or non-overlapping training samples?

I have $N$ (time) sequences of data with length $2048$. Each of these sequences correseponds to a different target output. However, I know that only a small part of the sequence is needed to actually ...
2
votes
0answers
31 views

Can you find another reason for sample inefficiency of model-free on-policy Deep Reinforcement Learning?

The following mindmap gives an overview of multiple reasons for sample inefficiency. The list is definitely not complete. Can you see another reason not mentioned so far? Some related links: ...
2
votes
1answer
46 views

Is there any practical application of knowing whether a concept class is PAC-learnable?

A concept class $C$ is PAC-learnable if there exists an algorithm that can output a hypothesis with probability at least $(1-\delta)$ (the "probably" part), and an error that is less than $\epsilon$ (...