Learning Functions of Halfspaces
2026-03-09 • Data Structures and Algorithms
Data Structures and AlgorithmsComputational Complexity
AI summaryⓘ
The authors present a new algorithm that can learn complex functions made by combining multiple halfspaces, which are simple dividing lines in space. Their method works even when given no assumptions about the data distribution, in a learning setup called PAC learning. It is faster than previous methods, especially for learning the intersection of two halfspaces, running in less than exponential time relative to the input size. This improves the understanding of how to efficiently learn certain geometric-based functions.
Boolean functionshalfspacesPAC learningdistribution-free learningcomputational complexityintersection of halfspacesalgorithmexponential timelearning theoryhigh-dimensional geometry
Authors
Josh Alman, Shyamal Patel, Rocco A. Servedio
Abstract
We give an algorithm that learns arbitrary Boolean functions of $k$ arbitrary halfspaces over $\mathbb{R}^n$, in the challenging distribution-free Probably Approximately Correct (PAC) learning model, running in time $2^{\sqrt{n} \cdot (\log n)^{O(k)}}$. This is the first algorithm that can PAC learn even intersections of two halfspaces in time $2^{o(n)}.$