Learning Sparse Linear Combinations of Basis Functions over a Finite Domain

Abstract

We study the problem of identifying a GF (2)-valued (0,1-valued) or real-valued function over a finite domain by querying the values of the target function at points of the learner's choice. We analyze the ( function value query ) learning complexity of subclasses of such functions, namely, the number of queries needed to identify an arbitrary function in a given subclass. Since the whole class of GF (2)-valued functions, and the class of real-valued functions, over a domain with cardinality N is each an N -dimensional vector space, an arbitrary function in each of these classes can be written as a linear combination of N functions from an arbitrary basis. The size of function f with respect to basis B is defined to be the number of non-zero coefficients in the unique representation of f as a linear combination of functions in B . We show upper and lower bounds on the learning complexity of the size- k subclasses for various basis, including the basis that enjoys the minimum learning complexity (among all bases). We also consider subclasses of real-valued functions representable by a linear combination of basis functions with non-negative coefficients . We analyze the learning complexity of such subclasses for two bases, and show that neither of them attains the lower bound we obtained for the basis with the minimum learning complexity.