Learning Functions of Halfspaces

Josh Alman; Shyamal Patel; Rocco A. Servedio

doi:10.1145/3798129.3800866

STOC2026顶会

Learning Functions of Halfspaces

Josh Alman, Shyamal Patel, Rocco A. Servedio

arXiv DOI 出版方

2026年份

3被引次数

摘要

We give an algorithm that learns arbitrary Boolean functions of k arbitrary halfspaces over R n , in the challenging distribution-free Probably Approximately Correct (PAC) learning model, running in time 2 √ n•(log n) O(k) . This is the first algorithm that can PAC learn even intersections of two halfspaces in time 2 o(n) .