This paper develops algorithms and mistake bounds for learning non-noisy boolean functions.  It considers the case when there is a very large number of possible attributes, but each example (and the concept) depends on only a few attributes, so we want ot avoid having to ever explicitly list or consider all possible attributes.  The concept classes it deals with learning are boolean formulas. The paper is a good cite but (for my work) probably not directly applicable.