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.
@InProceedings{pmlr-v35-feldman14c,
title = {Open Problem: The Statistical Query Complexity of Learning Sparse Halfspaces},
author = {Vitaly Feldman},
booktitle = {Proceedings of The 27th Conference on Learning Theory},
pages = {1283--1289},
year = {2014},
editor = {Maria Florina Balcan and Vitaly Feldman and Csaba Szepesvári},
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 = {http://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.}
}
%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
%J Proceedings of Machine Learning Research
%P 1283--1289
%U http://proceedings.mlr.press
%V 35
%W PMLR
%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.
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
PY - 2014/05/29
DA - 2014/05/29
ED - Maria Florina Balcan
ED - Vitaly Feldman
ED - Csaba Szepesvári
ID - pmlr-v35-feldman14c
PB - PMLR
SP - 1283
DP - PMLR
EP - 1289
L1 - http://proceedings.mlr.press/v35/feldman14c.pdf
UR - http://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 -
Feldman, V.. (2014). Open Problem: The Statistical Query Complexity of Learning Sparse Halfspaces. Proceedings of The 27th Conference on Learning Theory, in PMLR 35:1283-1289
This site last compiled Mon, 16 Jul 2018 07:50:39 +0000