Strong minimax lower bounds for learning
Mostra el registre complet Registre parcial de l'ítem
- dc.contributor.author Antos, Andrasca
- dc.contributor.author Lugosi, Gáborca
- dc.contributor.other Universitat Pompeu Fabra. Departament d'Economia i Empresa
- dc.date.accessioned 2017-07-26T10:50:19Z
- dc.date.available 2017-07-26T10:50:19Z
- dc.date.issued 1997-01-01
- dc.date.modified 2017-07-23T02:02:52Z
- dc.description.abstract Minimax lower bounds for concept learning state, for example, that for each sample size $n$ and learning rule $g_n$, there exists a distribution of the observation $X$ and a concept $C$ to be learnt such that the expected error of $g_n$ is at least a constant times $V/n$, where $V$ is the VC dimension of the concept class. However, these bounds do not tell anything about the rate of decrease of the error for a {\sl fixed} distribution--concept pair.\\ In this paper we investigate minimax lower bounds in such a--stronger--sense. We show that for several natural $k$--parameter concept classes, including the class of linear halfspaces, the class of balls, the class of polyhedra with a certain number of faces, and a class of neural networks, for any {\sl sequence} of learning rules $\{g_n\}$, there exists a fixed distribution of $X$ and a fixed concept $C$ such that the expected error is larger than a constant times $k/n$ for {\sl infinitely many n}. We also obtain such strong minimax lower bounds for the tail distribution of the probability of error, which extend the corresponding minimax lower bounds.
- dc.format.mimetype application/pdfca
- dc.identifier https://econ-papers.upf.edu/ca/paper.php?id=197
- dc.identifier.citation Machine Learning, 30, (1998), pp. 31-56
- dc.identifier.uri http://hdl.handle.net/10230/1223
- dc.language.iso eng
- dc.relation.ispartofseries Economics and Business Working Papers Series; 197
- dc.rights L'accés als continguts d'aquest document queda condicionat a l'acceptació de les condicions d'ús establertes per la següent llicència Creative Commons
- dc.rights.accessRights info:eu-repo/semantics/openAccess
- dc.rights.uri http://creativecommons.org/licenses/by-nc-nd/3.0/es/
- dc.subject.keyword estimation
- dc.subject.keyword hypothesis testing
- dc.subject.keyword statistical decision theory: operations research
- dc.subject.keyword Statistics, Econometrics and Quantitative Methods
- dc.title Strong minimax lower bounds for learningca
- dc.type info:eu-repo/semantics/workingPaper