Attribute-Efficient Learning andWeight-Degree Tradeoffs for Polynomial Threshold Functions

Rocco Servedio, Li-Yang Tan, Justin Thaler
Proceedings of the 25th Annual Conference on Learning Theory, PMLR 23:14.1-14.19, 2012.

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-\emphk decision lists over \emphn 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 (Klivans and Servedio, 2006). Our main negative result is a new lower bound on the \emphweight of any degree-\emphd polynomial threshold function (PTF) that computes a particular decision list over \emphk variables (the “ODD-MAX-BIT” function). The main result of Beigel (Beigel, 1994) is a weight lower bound of 2^Ω(\emphk/\emphd^2), which was shown to be essentially optimal for \emphd ≤ \emphk^1/3 by Klivans and Servedio. Here we prove a 2^Ω(√\emphk/d) lower bound, which improves on Beigel’s lower bound for \emphd > \emphk^1/3. 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 \emphand the size of its coefficients.

Cite this Paper

BibTeX
@InProceedings{pmlr-v23-servedio12, title = {Attribute-Efficient Learning andWeight-Degree Tradeoffs for Polynomial Threshold Functions}, author = {Servedio, Rocco and Tan, Li-Yang and Thaler, Justin}, booktitle = {Proceedings of the 25th Annual Conference on Learning Theory}, pages = {14.1--14.19}, year = {2012}, editor = {Mannor, Shie and Srebro, Nathan and Williamson, Robert C.}, volume = {23}, series = {Proceedings of Machine Learning Research}, address = {Edinburgh, Scotland}, month = {25--27 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v23/servedio12/servedio12.pdf}, url = {https://proceedings.mlr.press/v23/servedio12.html}, 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-\emphk decision lists over \emphn 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 (Klivans and Servedio, 2006). Our main negative result is a new lower bound on the \emphweight of any degree-\emphd polynomial threshold function (PTF) that computes a particular decision list over \emphk variables (the “ODD-MAX-BIT” function). The main result of Beigel (Beigel, 1994) is a weight lower bound of 2^Ω(\emphk/\emphd^2), which was shown to be essentially optimal for \emphd ≤ \emphk^1/3 by Klivans and Servedio. Here we prove a 2^Ω(√\emphk/d) lower bound, which improves on Beigel’s lower bound for \emphd > \emphk^1/3. 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 \emphand the size of its coefficients.} }
Endnote
%0 Conference Paper %T Attribute-Efficient Learning andWeight-Degree Tradeoffs for Polynomial Threshold Functions %A Rocco Servedio %A Li-Yang Tan %A Justin Thaler %B Proceedings of the 25th Annual Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2012 %E Shie Mannor %E Nathan Srebro %E Robert C. Williamson %F pmlr-v23-servedio12 %I PMLR %P 14.1--14.19 %U https://proceedings.mlr.press/v23/servedio12.html %V 23 %X 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-\emphk decision lists over \emphn 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 (Klivans and Servedio, 2006). Our main negative result is a new lower bound on the \emphweight of any degree-\emphd polynomial threshold function (PTF) that computes a particular decision list over \emphk variables (the “ODD-MAX-BIT” function). The main result of Beigel (Beigel, 1994) is a weight lower bound of 2^Ω(\emphk/\emphd^2), which was shown to be essentially optimal for \emphd ≤ \emphk^1/3 by Klivans and Servedio. Here we prove a 2^Ω(√\emphk/d) lower bound, which improves on Beigel’s lower bound for \emphd > \emphk^1/3. 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 \emphand the size of its coefficients.
RIS
TY - CPAPER TI - Attribute-Efficient Learning andWeight-Degree Tradeoffs for Polynomial Threshold Functions AU - Rocco Servedio AU - Li-Yang Tan AU - Justin Thaler BT - Proceedings of the 25th Annual Conference on Learning Theory DA - 2012/06/16 ED - Shie Mannor ED - Nathan Srebro ED - Robert C. Williamson ID - pmlr-v23-servedio12 PB - PMLR DP - Proceedings of Machine Learning Research VL - 23 SP - 14.1 EP - 14.19 L1 - http://proceedings.mlr.press/v23/servedio12/servedio12.pdf UR - https://proceedings.mlr.press/v23/servedio12.html AB - 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-\emphk decision lists over \emphn 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 (Klivans and Servedio, 2006). Our main negative result is a new lower bound on the \emphweight of any degree-\emphd polynomial threshold function (PTF) that computes a particular decision list over \emphk variables (the “ODD-MAX-BIT” function). The main result of Beigel (Beigel, 1994) is a weight lower bound of 2^Ω(\emphk/\emphd^2), which was shown to be essentially optimal for \emphd ≤ \emphk^1/3 by Klivans and Servedio. Here we prove a 2^Ω(√\emphk/d) lower bound, which improves on Beigel’s lower bound for \emphd > \emphk^1/3. 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 \emphand the size of its coefficients. ER -
APA
Servedio, R., Tan, L. & Thaler, J.. (2012). Attribute-Efficient Learning andWeight-Degree Tradeoffs for Polynomial Threshold Functions. Proceedings of the 25th Annual Conference on Learning Theory, in Proceedings of Machine Learning Research 23:14.1-14.19 Available from https://proceedings.mlr.press/v23/servedio12.html.

Related Material