Machine Learning is an international forum for research on computational approaches to learning. The journal publishes articles reporting substantive results on a wide range of learning methods applied to a variety of learning problems.
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.