Title: Attribute-efficient learning and weight-degree tradeoffs for polynomial threshold functions

Abstract:

We study the challenging problem of learning decision lists
attribute-efficiently, giving both positive and negative results.

Our main positive result is a new tradeoff between the running time
and mistake bound for learning length-k decision lists over n Boolean
variables.  When the allowed running time is relatively high, our new
mistake bound improves significantly on the mistake bound of the best
previous algorithm of Klivans and Servedio.

Our main negative result is a new lower bound on the weight of
any degree-d polynomial threshold function (PTF) that computes a
particular decision list over k variables.  This lower bound establishes strong
limitations on the effectiveness of the Klivans and Servedio approach and
suggests that it may be difficult to improve on our positive
result. The main tool used in our lower bound is a new variant of
Markov's classical inequality which may be of independent interest; it
provides a bound on the derivative of a univariate polynomial in terms
of both its degree and the size of its coefficients.

Joint work with Rocco Servedio and Justin Thaler