{"id":"arxiv/2611.05114","url":"https://arxiv.org/abs/2611.05114","tags":["cs.LG","cs.DS","math.ST","stat.ML"],"score":0,"title":"Beyond Multi-Index Models: Learning Intersections of Degree-2 PTFs","domain":"cs.LG","source":"arxiv","authors":["Ilias Diakonikolas","Daniel M. Kane","Mingchen Ma","Lisheng Ren","Trung Tran"],"reviews":0,"subject":"cs.LG","summary":"We give an algorithm for PAC learning intersections of $k$ degree-2 polynomial threshold functions over $R^d$ under a Gaussian distribution. Our algorithm achieves classification error $ε$ using $d^{O(k)}2^{O_k(\\log^3(1/ε))}$ time and samples, improving over the $d^{O(k^2/ε^2)}$ running time of the polynomial regression approach. To our knowledge, our result is the first to obtain a dimension exponent independent of the accuracy parameter, even for $k=2$. We complement our algorithmic result with an SQ lower bound showing that the complexity dependence of $d^{Ω(k)}$ is unavoidable. Lifting…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-11-03","reactions":{}}