Reproduce “Beyond Multi-Index Models: Learning Intersections of Degree-2 PTFs” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Ilias Diakonikolas, Daniel M. Kane, Mingchen Ma, Lisheng Ren, Trung Tran
The authors give an algorithm for PAC learning intersections of k quadratic threshold rules under standard Gaussian inputs. For realizable targets, it achieves error at most ε with time and sample complexity d^{O(k)}2^{O_k(log^3(1/ε))}. Compared with polynomial regression’s d^{O(k²/ε²)} time bound, at k=2 the exponent on d becomes independent of ε; polynomial dependence on 1/ε remains unestablished.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.