Open Problem: The Statistical Query Complexity of Learning Sparse Halfspaces

Vitaly Feldman
Proceedings of The 27th Conference on Learning Theory, PMLR 35:1283-1289, 2014.

Abstract

We consider the long-open problem of attribute-efficient learning of halfspaces. In this problem the learner is given random examples labeled by an unknown halfspace function f on \mathbbR^n. Further f is r-sparse, that is it depends on at most r out of n variables. An attribute-efficient learning algorithm is an algorithm that can output a hypothesis close to f using a polynomial in r and \log n number of examples (Blum, 1992). Despite a number of attempts and some partial progress, there are no efficient algorithms or hardness results for the problem. We propose a potentially easier question: what is the query complexity of this learning problem in the statistical query (SQ) model of Kearns (1998). We show that, as in the case of general PAC learning, the query complexity of attribute-efficient SQ learning of any concept class can be characterized by a combinatorial parameter of the concept class. The proposed question is then equivalent to estimating the value of this parameter for the concept class of halfspaces. A potentially simpler problem is to estimate this parameter for the concept class of decision lists, a subclass of halfspaces.

Cite this Paper

BibTeX
@InProceedings{pmlr-v35-feldman14c, title = {Open Problem: The Statistical Query Complexity of Learning Sparse Halfspaces}, author = {Feldman, Vitaly}, booktitle = {Proceedings of The 27th Conference on Learning Theory}, pages = {1283--1289}, year = {2014}, editor = {Balcan, Maria Florina and Feldman, Vitaly and Szepesvári, Csaba}, volume = {35}, series = {Proceedings of Machine Learning Research}, address = {Barcelona, Spain}, month = {13--15 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v35/feldman14c.pdf}, url = {https://proceedings.mlr.press/v35/feldman14c.html}, abstract = {We consider the long-open problem of attribute-efficient learning of halfspaces. In this problem the learner is given random examples labeled by an unknown halfspace function f on \mathbbR^n. Further f is r-sparse, that is it depends on at most r out of n variables. An attribute-efficient learning algorithm is an algorithm that can output a hypothesis close to f using a polynomial in r and \log n number of examples (Blum, 1992). Despite a number of attempts and some partial progress, there are no efficient algorithms or hardness results for the problem. We propose a potentially easier question: what is the query complexity of this learning problem in the statistical query (SQ) model of Kearns (1998). We show that, as in the case of general PAC learning, the query complexity of attribute-efficient SQ learning of any concept class can be characterized by a combinatorial parameter of the concept class. The proposed question is then equivalent to estimating the value of this parameter for the concept class of halfspaces. A potentially simpler problem is to estimate this parameter for the concept class of decision lists, a subclass of halfspaces.} }
Endnote
%0 Conference Paper %T Open Problem: The Statistical Query Complexity of Learning Sparse Halfspaces %A Vitaly Feldman %B Proceedings of The 27th Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2014 %E Maria Florina Balcan %E Vitaly Feldman %E Csaba Szepesvári %F pmlr-v35-feldman14c %I PMLR %P 1283--1289 %U https://proceedings.mlr.press/v35/feldman14c.html %V 35 %X We consider the long-open problem of attribute-efficient learning of halfspaces. In this problem the learner is given random examples labeled by an unknown halfspace function f on \mathbbR^n. Further f is r-sparse, that is it depends on at most r out of n variables. An attribute-efficient learning algorithm is an algorithm that can output a hypothesis close to f using a polynomial in r and \log n number of examples (Blum, 1992). Despite a number of attempts and some partial progress, there are no efficient algorithms or hardness results for the problem. We propose a potentially easier question: what is the query complexity of this learning problem in the statistical query (SQ) model of Kearns (1998). We show that, as in the case of general PAC learning, the query complexity of attribute-efficient SQ learning of any concept class can be characterized by a combinatorial parameter of the concept class. The proposed question is then equivalent to estimating the value of this parameter for the concept class of halfspaces. A potentially simpler problem is to estimate this parameter for the concept class of decision lists, a subclass of halfspaces.
RIS
TY - CPAPER TI - Open Problem: The Statistical Query Complexity of Learning Sparse Halfspaces AU - Vitaly Feldman BT - Proceedings of The 27th Conference on Learning Theory DA - 2014/05/29 ED - Maria Florina Balcan ED - Vitaly Feldman ED - Csaba Szepesvári ID - pmlr-v35-feldman14c PB - PMLR DP - Proceedings of Machine Learning Research VL - 35 SP - 1283 EP - 1289 L1 - http://proceedings.mlr.press/v35/feldman14c.pdf UR - https://proceedings.mlr.press/v35/feldman14c.html AB - We consider the long-open problem of attribute-efficient learning of halfspaces. In this problem the learner is given random examples labeled by an unknown halfspace function f on \mathbbR^n. Further f is r-sparse, that is it depends on at most r out of n variables. An attribute-efficient learning algorithm is an algorithm that can output a hypothesis close to f using a polynomial in r and \log n number of examples (Blum, 1992). Despite a number of attempts and some partial progress, there are no efficient algorithms or hardness results for the problem. We propose a potentially easier question: what is the query complexity of this learning problem in the statistical query (SQ) model of Kearns (1998). We show that, as in the case of general PAC learning, the query complexity of attribute-efficient SQ learning of any concept class can be characterized by a combinatorial parameter of the concept class. The proposed question is then equivalent to estimating the value of this parameter for the concept class of halfspaces. A potentially simpler problem is to estimate this parameter for the concept class of decision lists, a subclass of halfspaces. ER -
APA
Feldman, V.. (2014). Open Problem: The Statistical Query Complexity of Learning Sparse Halfspaces. Proceedings of The 27th Conference on Learning Theory, in Proceedings of Machine Learning Research 35:1283-1289 Available from https://proceedings.mlr.press/v35/feldman14c.html.

Related Material