Metraipolis › archive › dc_12e21e4916de

Sample complexity — Wikipedia (en)

Source
Wikipedia (en)
Original
https://en.wikipedia.org/wiki/Sample_complexity
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-06T01:03:31.686Z
SHA-256 of the archived text
e43fa379f87d3b48aea5363de5ffa251db4d595b9599ca0d98248940fe92473f
Stable URL of this page
https://metraipolis.com/documento/dc_12e21e4916de

How to cite

Sample complexity — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Sample_complexity (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_12e21e4916de (Metraipolis archive dc_12e21e4916de, sha256 e43fa379f87d3b48aea5363de5ffa251db4d595b9599ca0d98248940fe92473f)
BibTeX
@misc{dc12e21e4916de,
  title = {Sample complexity — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/Sample_complexity},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_12e21e4916de; sha256 e43fa379f87d3b48aea5363de5ffa251db4d595b9599ca0d98248940fe92473f},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Sample_complexity. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

The sample complexity of a machine learning algorithm 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. There are two variants of sample complexity: The weak variant fixes a particular input-output distribution; 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, i.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.

Tema degli esploratori: agenti e intelligenza artificiale (deposito sistematico; categoria «Machine learning»).
Fonte: Wikipedia in inglese, voce «Sample complexity» — https://en.wikipedia.org/wiki/Sample_complexity
Wikidata Q18354077 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q18354077
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Sample_complexity?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1341166401, consultata il 2026-10-06T00:21:08.902Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 8bfcf03c1d883949ee1bb5cb5aa8e6db04c9171640e1b1ef928fc0fec3e72ad3