On efficient agnostic learning of linear combinations of basis functions
Proceedings of the eighth annual conference on Computational learning theory, 1995•dl.acm.org
We consider efficient agnostic learning of linear combinations of basis functions when the
sum of absolute values of the weights of the linear combinations is bounded. With the
quadratic loss function, we show that the class of linear combinations of a set of basis
functions is efficiently agnostically learnable if and only if the class of basis functions is
efficiently agnostically learnable. We also show that the sample complexity for learning the
linear combinations grows polynomially if and only if a combinatorial property of the class of …
sum of absolute values of the weights of the linear combinations is bounded. With the
quadratic loss function, we show that the class of linear combinations of a set of basis
functions is efficiently agnostically learnable if and only if the class of basis functions is
efficiently agnostically learnable. We also show that the sample complexity for learning the
linear combinations grows polynomially if and only if a combinatorial property of the class of …
Abstract
We consider efficient agnostic learning of linear combinations of basis functions when the sum of absolute values of the weights of the linear combinations is bounded. With the quadratic loss function, we show that the class of linear combinations of a set of basis functions is efficiently agnostically learnable if and only if the class of basis functions is efficiently agnostically learnable. We also show that the sample complexity for learning the linear combinations grows polynomially if and only if a combinatorial property of the class of basis functions, called the fat-shattering function, grows at most polynomially. We also relate the problem to agnostic learning of {0, 1}-valued function classes by showing that if a class of {O, 1}-valued functions is efficiently agnostically learnable (using the same function class) with the discrete loss function, then the class of linear combinations of functions from the class is efficiently agnostically learnable with the quadratic loss function.
ACM Digital Library
顯示最佳搜尋結果。 查看所有結果