In the paper:
Avrim L. Blum and Pat Langley. 1997. Selection of relevant features and examples in machine learning. Artif. Intell. 97, 1-2 (December 1997), 245-271.
are several definitions of the term relevance.
In Definition 4 it says
Given a sample of data $S$ and a set of concepts $C$, let $r(S,C)$ be the number of features relevant using Definition 1 to a concept in $C$ that, out of all those whose error over $S$ is least, has the fewest relevant features.
A view lines later...
The above notions of relevance are independent of the specific learning algorithm being used. There is no guarantee that just because a feature is relevant, it will necessarily be useful to an algorithm (or vice versa).
What does error in definition 4 mean in this context? I first thought he refered to the classifier error but then it says those definitions are independent of a learning algorithm.