Learning Functions of Halfspaces Using Prefix Covers

Parikshit Gopalan, Adam R. Klivans, Raghu Meka
Proceedings of the 25th Annual Conference on Learning Theory, PMLR 23:15.1-15.10, 2012.

Abstract

We present a simple query-algorithm for learning arbitrary functions of k halfspaces under any product distribution on the Boolean hypercube. Our algorithms learn any function of k halfspaces to within accuracy ε in time \emphO((nk/ε)^k+1) under any product distribution on 0, 1^\emphn using read-once branching programs as a hypothesis. This gives the first \emphpoly(n, 1/ε) algorithm for learning even the intersection of 2 halfspaces under the uniform distribution on 0, 1^\emphn previously known algorithms had an exponential dependence either on the accuracy parameter ε or the dimension \emphn. To prove this result, we identify a new structural property of Boolean functions that yields learnability with queries: that of having a small prefix cover.

Cite this Paper

BibTeX
@InProceedings{pmlr-v23-gopalan12, title = {Learning Functions of Halfspaces Using Prefix Covers}, author = {Gopalan, Parikshit and Klivans, Adam R. and Meka, Raghu}, booktitle = {Proceedings of the 25th Annual Conference on Learning Theory}, pages = {15.1--15.10}, 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/gopalan12/gopalan12.pdf}, url = {https://proceedings.mlr.press/v23/gopalan12.html}, abstract = {We present a simple query-algorithm for learning arbitrary functions of k halfspaces under any product distribution on the Boolean hypercube. Our algorithms learn any function of k halfspaces to within accuracy ε in time \emphO((nk/ε)^k+1) under any product distribution on 0, 1^\emphn using read-once branching programs as a hypothesis. This gives the first \emphpoly(n, 1/ε) algorithm for learning even the intersection of 2 halfspaces under the uniform distribution on 0, 1^\emphn previously known algorithms had an exponential dependence either on the accuracy parameter ε or the dimension \emphn. To prove this result, we identify a new structural property of Boolean functions that yields learnability with queries: that of having a small prefix cover.} }
Endnote
%0 Conference Paper %T Learning Functions of Halfspaces Using Prefix Covers %A Parikshit Gopalan %A Adam R. Klivans %A Raghu Meka %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-gopalan12 %I PMLR %P 15.1--15.10 %U https://proceedings.mlr.press/v23/gopalan12.html %V 23 %X We present a simple query-algorithm for learning arbitrary functions of k halfspaces under any product distribution on the Boolean hypercube. Our algorithms learn any function of k halfspaces to within accuracy ε in time \emphO((nk/ε)^k+1) under any product distribution on 0, 1^\emphn using read-once branching programs as a hypothesis. This gives the first \emphpoly(n, 1/ε) algorithm for learning even the intersection of 2 halfspaces under the uniform distribution on 0, 1^\emphn previously known algorithms had an exponential dependence either on the accuracy parameter ε or the dimension \emphn. To prove this result, we identify a new structural property of Boolean functions that yields learnability with queries: that of having a small prefix cover.
RIS
TY - CPAPER TI - Learning Functions of Halfspaces Using Prefix Covers AU - Parikshit Gopalan AU - Adam R. Klivans AU - Raghu Meka 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-gopalan12 PB - PMLR DP - Proceedings of Machine Learning Research VL - 23 SP - 15.1 EP - 15.10 L1 - http://proceedings.mlr.press/v23/gopalan12/gopalan12.pdf UR - https://proceedings.mlr.press/v23/gopalan12.html AB - We present a simple query-algorithm for learning arbitrary functions of k halfspaces under any product distribution on the Boolean hypercube. Our algorithms learn any function of k halfspaces to within accuracy ε in time \emphO((nk/ε)^k+1) under any product distribution on 0, 1^\emphn using read-once branching programs as a hypothesis. This gives the first \emphpoly(n, 1/ε) algorithm for learning even the intersection of 2 halfspaces under the uniform distribution on 0, 1^\emphn previously known algorithms had an exponential dependence either on the accuracy parameter ε or the dimension \emphn. To prove this result, we identify a new structural property of Boolean functions that yields learnability with queries: that of having a small prefix cover. ER -
APA
Gopalan, P., Klivans, A.R. & Meka, R.. (2012). Learning Functions of Halfspaces Using Prefix Covers. Proceedings of the 25th Annual Conference on Learning Theory, in Proceedings of Machine Learning Research 23:15.1-15.10 Available from https://proceedings.mlr.press/v23/gopalan12.html.

Related Material