Revision as of 11:55, 27 April 2017 edit E.pajouheshgar (talk \| contribs) 1 edit →An example of a PAC-learnable hypothesis space ← Previous edit		Revision as of 21:57, 24 January 2018 edit undo Keepssouth (talk \| contribs) Extended confirmed users 622 edits mNo edit summary Next edit →
Line 8: * The strong variant takes the worst-case sample complexity over all input-output distributions. The No Free Lunch theorem, discussed below, proves that, in general, the strong sample complexity is infinite., Ii.e,. that there is no algorithm that can learn the globally-optimal target function using a finite number of training samples. However, if we are only interested in a particular class of target functions (e.g, only linear functions) then the sample complexity is finite, and it depends linearly on the [[VC dimension]] on the class of target functions.

Sample complexity: Difference between revisions