Complexity theoretic limitations on learning halfspaces

DOI10.1145/2897518.2897520MaRDI QIDQ5361822zbMATH OpenOpenAlexFDO

Authors Amit Daniely

Publication date 29 September 2017

Published in Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1505.05800

zbMATH Keywords

halfspaceshardness of learningrandom XOR

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Learning and adaptive systems in artificial intelligence (68T05)

Abstract: We study the problem of agnostically learning halfspaces which is defined by a fixed but unknown distribution $mathcalD$ on $mathbb{Q}^{n}imespm1$. We define $mathrm{Err}_{mathrmHALF}(mathcalD)$ as the least error of a halfspace classifier for $mathcalD$. A learner who can access $mathcalD$ has to return a hypothesis whose error is small compared to $mathrm{Err}_{mathrmHALF}(mathcalD)$. Using the recently developed method of the author, Linial and Shalev-Shwartz we prove hardness of learning results under a natural assumption on the complexity of refuting random $K$-$mathrmXOR$ formulas. We show that no efficient learning algorithm has non-trivial worst-case performance even under the guarantees that $mathrm{Err}_{mathrmHALF}(mathcalD)leeta$ for arbitrarily small constant $eta>0$, and that $mathcalD$ is supported in ${pm1}^{n}imespm1$. Namely, even under these favorable conditions its error must be $gefrac12-frac1n^c$ for every $c>0$. In particular, no efficient algorithm can achieve a constant approximation ratio. Under a stronger version of the assumption (where $K$ can be poly-logarithmic in $n$), we can take $eta=2^{-lo{g}^{1-u}(n)}$ for arbitrarily small $u>0$. Interestingly, this is even stronger than the best known lower bounds (Arora et. al. 1993, Feldamn et. al. 2006, Guruswami and Raghavendra 2006) for the case that the learner is restricted to return a halfspace classifier (i.e. proper learning).

Recommendations

• Hardness of learning halfspaces with noise
• Agnostically Learning Halfspaces
• On agnostic learning of parities, monomials, and halfspaces
• From average case complexity to improper learning complexity

Cited in

(17)

• Embedding hard learning problems into Gaussian space
• Learning kernel-based halfspaces with the 0-1 loss
• On the Complexity of Learning Minimum Time-Bounded Turing Machines
• On agnostic learning of parities, monomials, and halfspaces
• Hardness of learning halfspaces with noise
• Learning finite binary sequences from half-space data
• scientific article; zbMATH DE number 6866335 (Why is no real title available?)
• Improper learning by refuting
• From average case complexity to improper learning complexity
• Resource Restricted Computability Theoretic Learning: Illustrative Topics and Problems
• Theory and Applications of Models of Computation
• scientific article; zbMATH DE number 7758323 (Why is no real title available?)
• Testing distributional assumptions of learning algorithms
• A moment-matching approach to testable learning and a new characterization of Rademacher complexity
• An algorithm for learning representations of models with scarce data
• Hardness of improper one-sided learning of conjunctions for all uniformly falsifiable CSPs
• The strongish planted clique hypothesis and its consequences

This page was built for publication: Complexity theoretic limitations on learning halfspaces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5361822)