Research map / Learning theory and algorithms / Sample complexity
Testably Learning Polynomial Threshold Functions
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that degree-d polynomial threshold functions can be testably learned w.r.t. the standard Gaussian in time n^{poly(1/eps)} by proving that approximately moment-matching distributions fool PTFs, and that a direct push-forward approach cannot work for PTFs.
Problem
Testable learning (Rubinfeld & Vasilyan) of polynomial threshold functions under a Gaussian marginal: whether PTFs of constant degree can be learned testably as efficiently as agnostic learning allows, and whether the direct polynomial-approximation approach used for halfspaces extends to PTFs.
Approach
Connects testable learning to fooling: distributions that approximately match poly(1/eps) Gaussian moments fool constant-degree PTFs, which via a moment-matching tester yields testable learning. The fooling proof adapts Kane's k-independent Gaussian construction to approximate moment matching, and a Bun-Steinke-style argument rules out the direct push-forward approach.
Key results
- Degree-d PTFs can be testably learned w.r.t. N(0,I_n) up to error eps in time and sample complexity n^{O_d(eps^{-4d*7^d})}, i.e. n^{poly(1/eps)} for constant d.
- Distributions that approximately match moments of N(0,I_n) up to degree k = Theta_d(eps^{-4d*7^d}) with slack eta <= n^{-Omega(k)}k^{-Omega(k)} fool degree-d PTFs up to error O_d(eps).
- There exists a square-free polynomial p with compact {p>=0} whose push-forward of the Gaussian is one-sided log-superlinear, so sign approximation by q(p(x)) fails for any polynomial q.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use approximate Gaussian moment matching and fooling to testably learn degree-d PTFs | Degree-d PTFs · Standard Gaussian N(0,I_n) | time and sample complexity: n^{O_d\left(\varepsilon^{-4d\cdot 7^d}\right)} \varepsilon^{-O_d\left(\varepsilon^{-4d \cdot 7^d}\right)} | Helped |
| Use an approximator of the restricted form h(x)=q(p(x)) | PTFs with degree at least 3 · Standard Gaussian | polynomial approximation error: there exists an ε > 0 such that, for any polynomial q, the error is > ε | Hurt |
Surprising findings
- The direct push-forward approach that works for halfspaces provably fails for PTFs of degree at least 3, even with square-free compact-sublevel-set assumptions.
Limitations
- Dependence on degree d and error eps is much worse than agnostic learning (k = eps^{-4d*7^d}).
- No matching lower bounds specific to testable learning of PTFs are known.
Experimental setup
Baselines: direct polynomial approximation approach (push-forward) agnostic learning of PTFs n^{O(d^2/eps^4)}
Builds on: Rubinfeld & Vasilyan testable learning Gollakota, Klivans & Kothari fooling-to-testable-learning Kane's fooling of PTFs by k-independent Gaussians Bun & Steinke impossibility for sign approximation
Closest papers by meaning
- An Efficient Tester-Learner for Halfspaces (ICLR 2024 · similarity 0.88)
- Reliable Learning of Halfspaces under Gaussian Marginals (NeurIPS 2024 · similarity 0.88)
- Smoothed Agnostic Learning of Halfspaces over the Hypercube (NeurIPS 2025 · similarity 0.87)
- Transductive Learning is Compact (NeurIPS 2024 · similarity 0.86)
- Scale-Sensitive Shattering: Learnability and Evaluability at Optimal Scale (NeurIPS 2026 · similarity 0.85)
- On Agnostic PAC Learning in the Small Error Regime (NeurIPS 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.