Beyond Multi-Index Models: Learning Intersections of Degree-2 PTFs

Source: arxiv.org/abs/2611.05114

Ilias Diakonikolas, Daniel M. Kane, Mingchen Ma, Lisheng Ren, Trung Tran

arXivarxiv/2611.05114Nov 3, 2026cs.LGscore 0

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…

JSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2611.05114
curl -X POST /api/v1/records/arxiv/2611.05114/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.05114/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'