Paper #197

Title:

Strong minimax lower bounds for learning

Authors:

Andras Antos and Gábor Lugosi

Date:

January 1997

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.

Keywords:

Estimation, hypothesis testing, statistical decision theory: operations research

JEL codes:

C12, C13, C44

Area of Research:

Statistics, Econometrics and Quantitative Methods

Published in:

Machine Learning, 30, (1998), pp. 31-56

Download the paper in PDF format