Beyond Multi-Index Models: Learning Intersections of Degree-2 PTFs
Abstract
We give an algorithm for PAC learning intersections of k degree-2 polynomial threshold functions over Rd under a Gaussian distribution. Our algorithm achieves classification error ε using dO(k)2Ok(log3(1/ε)) time and samples, improving over the dO(k2/ε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 the input to polynomial features turns the target into an intersection of k halfspaces. This suggests using the first two labeled moments for subspace recovery. In the lifted space, however, these moments can reveal nothing. Our starting point is a Gaussian comparison theorem showing that, for sufficiently regular defining quadratics, the labeled moments needed for subspace recovery are approximately preserved. To handle arbitrary defining quadratics, we establish a new structural result showing that every direction with significant resampling influence can be detected through degree-O(k) moments. These results yield an initial dO(k)2polyk(1/ε)-time learner using adaptive restrictions. To improve the exponential dependence on 1/ε, we develop a two-stage dimension-reduction approach that avoids the costly adaptive partitioning. After identifying a subspace containing all directions with large influence, we use generalized regularity and Gaussian comparison to recover the remaining relevant quadratic features through a new derivative-based moment operator. The recovered features support an intersection close to the target. Combining them with robust hinge-loss minimization gives our quasipolynomial-time learner.
Related
- Learning Orthogonal Multi-Index Models Beyond Small Initialization: Incremental Learning, Competitive Dynamics and Symmetry
- Multi-Index Recovery for Total-Degree Multivariate Vandermonde Matrices
- Spatial Mixing and Deterministic Approximate Counting of Multi-spin Systems beyond Bounded Degree Graphs
- Degree Growth of Iterates of Curves and Likely Intersections
- Symmetry-Aware Feature Learning: A Polynomial Separation for Multi-Index Models
BibTeX
@misc{diakonikolas2026beyond,
title = {{Beyond Multi-Index Models: Learning Intersections of Degree-2 PTFs}},
author = {Ilias Diakonikolas and Daniel M. Kane and Mingchen Ma and Lisheng Ren and Trung Tran},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.05114},
eprint = {2611.05114},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.05114},
}
RIS
TY - UNPB
TI - Beyond Multi-Index Models: Learning Intersections of Degree-2 PTFs
AU - Ilias Diakonikolas
AU - Daniel M. Kane
AU - Mingchen Ma
AU - Lisheng Ren
AU - Trung Tran
PY - 2026
DA - 2026/11/03
PB - arXiv
DO - 10.48550/arxiv.2611.05114
UR - https://arxiv.org/abs/2611.05114
AB - 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 the input to polynomial features turns the target into an intersection of k halfspaces. This suggests using the first two labeled moments for subspace recovery. In the lifted space, however, these moments can reveal nothing. Our starting point is a Gaussian comparison theorem showing that, for sufficiently regular defining quadratics, the labeled moments needed for subspace recovery are approximately preserved. To handle arbitrary defining quadratics, we establish a new structural result showing that every direction with significant resampling influence can be detected through degree-O(k) moments. These results yield an initial d^O(k)2^poly_k(1/ε)-time learner using adaptive restrictions. To improve the exponential dependence on 1/ε, we develop a two-stage dimension-reduction approach that avoids the costly adaptive partitioning. After identifying a subspace containing all directions with large influence, we use generalized regularity and Gaussian comparison to recover the remaining relevant quadratic features through a new derivative-based moment operator. The recovered features support an intersection close to the target. Combining them with robust hinge-loss minimization gives our quasipolynomial-time learner.
ER -