Degree-d Chow Parameters Robustly Determine Degree-d PTFs (and Algorithmic Applications)

The degree-d Chow parameters of a Boolean function f: -1,1n → ℝ are its degree at most d Fourier coefficients. It is well-known that degree-d Chow parameters uniquely characterize degree-d polynomial threshold functions (PTFs) within the space of all bounded functions. In this paper, we prove a robust version of this theorem: For f any Boolean degree-d PTF and g any bounded function, if the degree-d Chow parameters of f are close to the degree-d Chow parameters of g in ℓ2-norm, then f is close to g in ℓ1-distance. Notably, our bound relating the two distances is completely independent of the dimension n. That is, we show that Boolean degree-d PTFs are em robustly identifiable from their degree-d Chow parameters. Results of this form had been shown for the d=1 case~citeOS11:chow, DeDFS14, but no non-trivial bound was previously known for d >1. Our robust identifiability result gives the following algorithmic applications: First, we show that Boolean degree-d PTFs can be efficiently approximately reconstructed from approximations to their degree-d Chow parameters. This immediately implies that degree-d PTFs are efficiently learnable in the uniform distribution d-RFA model~citeBenDavidDichterman:98. As a byproduct of our approach, we also obtain the first low integer-weight approximations of degree-d PTFs, for d>1. As our second application, our robust identifiability result gives the first efficient algorithm, with dimension-independent error guarantees, for malicious learning of Boolean degree-d PTFs under the uniform distribution.