A regularity lemma, and low-weight approximators, for low-degree polynomial threshold functions

2009/09/25 by Ilias Diakonikolas, Rocco A. Servedio, Diakonikolas, Ilias +5 · 2 citations
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Machine Learning and Algorithms #Commutative Algebra and Its Applications

paper · pdf · doi:10.48550/arxiv.0909.4727

Abstract

We give a "regularity lemma" for degree-d polynomial threshold functions (PTFs) over the Boolean cube -1,1ⁿ. This result shows that every degree-d PTF can be decomposed into a constant number of subfunctions such that almost all of the subfunctions are close to being regular PTFs. Here a "regular PTF is a PTF sign(p(x)) where the influence of each variable on the polynomial p(x) is a small fraction of the total influence of p. As an application of this regularity lemma, we prove that for any constants d ≥ 1, \eps ≥ 0, every degree-d PTF over n variables has can be approximated to accuracy eps by a constant-degree PTF that has integer weights of total magnitude O(n^d). This weight bound is shown to be optimal up to constant factors.

Citations

• Logarithmic Sobolev Inequalities
• Average sensitivity and noise sensitivity of polynomial threshold functions

Cited by

• Guaranteed Rank Minimization via Singular Value Projection
• Bounded Independence Fools Degree-2 Threshold Functions

Related

• Polynomial Threshold Functions: Structure, Approximation and Pseudorandomness
• On the weight and density bounds of polynomial threshold functions
• Polynomial threshold functions, hyperplane arrangements, and random\n tensors
• Average sensitivity and noise sensitivity of polynomial threshold functions
• Algorithmic regularity for polynomials and applications